1 Background
The distinguishing feature of a complementarity problem is the set of complementarity conditions. Each of these conditions requires that the product of two or more nonnegative quantities should be zero. Complementarity conditions made their first appearance in the optimality conditions for continuous variable nonlinear programs involving inequality constraints, which were derived by Karush [
14] in 1939. But the significance of complementarity conditions goes far beyond this. They appear prominently in the study of equilibrium problems and arise naturally in numerous applications from economics, engineering and the sciences.
The motivation for studying the linear complementarity problem (LCP) was because the KKT optimality conditions for linear and quadratic programs (QPs) constitute an LCP of the form (
1.1). The complementarity problem is one of the basic problems in nonlinear analysis along with such problems as optimization, fixed point problems, equilibrium problems and variational inequalities. The nonlinear complementarity problem (NCP) was introduced by Cottle in his Ph.D. thesis in 1964 [
5], and the closely related variational inequality problem (VIP) was introduced by Hartman and Stampacchia in 1966 [
10], primarily with the goal of computing stationary points for nonlinear programs. While these problems were introduced soon after the LCP, most of the progress in developing algorithms for these problems did not begin until the late 1970s.
Recall that the conventional complementarity problem requires that, for a given single-valued mapping
\(F:\mathbb{R}^{n}\longrightarrow \mathbb{R}^{n}\), one finds a point
\(x\in \mathbb{R}^{n}\) such that
$$ x\geq 0, \quad F(x)\geq 0,\qquad x^{\top }F(x) = 0. $$
(1.1)
The bulk of the above publications concern problems of the form (
1.1), it is especially true of the work related to numerical methods for searching solutions.
Meanwhile, many applications lead to set-valued mappings. As a result, set-valued complementarity problems must be solved; that is, a point
\(x\in \mathbb{R}^{n}\) must be found such that
$$ x\geq 0, \quad\exists g\in G(x),\quad g\geq 0,\qquad x^{\top }g = 0, $$
(1.2)
where
\(G:\mathbb{R}^{n}\longrightarrow \prod (\mathbb{R}^{n})\) is a set-valued mapping, hereafter, the symbol
\(\prod (S)\) stands for the collection of all subsets of the set
S.
The simplest and most widely studied of the complementarity problems is the LCP, which has often been described as a fundamental problem for given
\(M \in \mathbb{R}^{n\times n}\),
\(q\in \mathbb{R}^{n}\), and
\(w = (w_{j})\in \mathbb{R}^{n}\),
\(z = (z_{j})\in \mathbb{R}^{n}\) satisfying
$$ w - Mz = q,\quad w,z > 0,\qquad w^{\top }z = 0. $$
(1.3)
We denote this LCP by the symbol
\((q,M)\). The LCP
\((q,M)\) is said to be monotone if the matrix
M is positive semi-definite (PSD). A slight generalization of the LCP is the mixed LCP (mLCP): given
\(A\in \mathbb{R}^{n\times n}\),
\(B\in \mathbb{R}^{m\times m}\),
\(C \in \mathbb{R} ^{n\times m}\),
\(D\in \mathbb{R}^{m\times n}\),
\(a\in \mathbb{R}^{n}\),
\(b \in \mathbb{R}^{m}\), find
\(u \in \mathbb{R}^{n}\),
\(v\in \mathbb{R}^{m}\) satisfying
$$ a + Au + Cv = 0, \qquad b+ Du + Bv \geq 0,\quad v \geq 0, \qquad v^{\top }(b + Du + Bv) = 0. $$
(1.4)
Another generalization of the LCP is the horizontal LCP or hLCP: given
\(N \in \mathbb{R}^{n\times n}\),
\(M \in \mathbb{R}^{n\times n}\),
\(q\in \mathbb{R}^{n}\), find
\(w \in \mathbb{R}^{n}\),
\(z \in \mathbb{R}^{n}\) satisfying
$$ Nw - Mz = q,\quad w,z>0,\qquad w^{\top }z = 0. $$
(1.5)
The hLCP (
1.5) becomes the standard LCP if
\(N =I\). Also, if
N is nonsingular, then (
1.5) is equivalent to the LCP
\((N^{-1}q,N^{-1}M)\). The hLCP is said to be monotone if for any two pairs of points
\((w^{1}, z^{1})\) and
\((w^{2}, z^{2})\) satisfying
\(Nw - Mz = q\) we have
$$ \bigl(w^{1} - w^{2} \bigr)^{\top } \bigl(z^{1} - z^{2} \bigr)>0. $$
Note that if
\(N = I\), this is equivalent to the matrix
M being PSD.
Now, we will present nonlinear generalizations of the LCP. The most important of these is the NCP: given a mapping
\(F(z)=(F_{i}(z)): \mathbb{R}^{n} \longrightarrow \mathbb{R}^{n}\), and a
\(z \in \mathbb{R}^{n}\) satisfying
$$ z >0,\quad F(z)>0, \qquad z^{\top }F(z) = 0, $$
(1.6)
If
\(F(z)\) is the affine function
\(q+ Mz\), then (
1.6) becomes the LCP
\((q,M)\).
A further generalizations of the NCP is the VIP which is defined thus: given a mapping
\(F(x)=(F_{i}(x)):\mathbb{R}^{n}\longrightarrow \mathbb{R}^{n}\), and
\(\emptyset \neq C\subset \mathbb{R}^{n}\), find a
\(x^{\ast }\in C\) satisfying
$$ \bigl(y - x^{\ast } \bigr)^{\top }F \bigl(x^{\ast } \bigr)\geq 0,\quad \forall y \in C, $$
(1.7)
denoted by
\(VIP(C,F)\) where
C is a nonempty closed convex subset of
\(\mathbb{R}^{n}\). If
C is polyhedral and
F is affine, it can be verified that
\(VIP(C,F)\) is an LCP.
C is a rectangular region defined by
$$ C = \prod_{i=1}^{n}[\ell _{i},u_{i}],\quad -\infty \leq \ell _{i}< u_{i} \leq \infty ,i=1,2,\dots ,n. $$
This is called the box constrained VIP (BCVIP), which is also commonly referred to as the (nonlinear) mixed complementarity problem (MCP).
Our main goal is to analyse the convergence rates for projection methods under mild assumptions and together with strict contraction property, we establish convergence rates in asymptotical sense under certain error bound condition. More specifically, we want to derive the worst-case sub-linear convergence rate measured by the iteration complexity. This kind of convergence rate analysis based on iteration complexity traces back to [
1,
4,
12,
16,
18]. Furthermore, our convergence rate analysis does not need to assume the boundedness of the feasible set which is usually required by iteration complexity analysis of projection methods for generalized complementarity problems; see, [
7‐
9,
13,
15].
We assume that
\(x^{\ast }\) is a fixed but arbitrary point in the solution set
\(C^{\ast }\) of generalized complementarity problems and
\(x^{\ell }\) refers to specific vector usually denotes an iteration index. For any matrix
M and vector
y, we denote their transposes by
\(M^{T}\) and
\(y^{T}\), respectively. The Euclidean norm is denoted by
\(\Vert \cdot \Vert \). Let
C be a nonempty closed convex subset of
\(\mathbb{R}^{n}, M\in \mathbb{R}^{n\times n}\) and
\(q\in \mathbb{R} ^{n}\). We consider the generalized complementarity problems for finding a vector
\(x^{\ast }\in C\) such that
$$ x^{\ast }\geq 0,\quad \bigl\langle x-x^{\ast },Mx^{\ast }+q \bigr\rangle = 0. $$
(1.8)
We consider the case where the matrix
M is positive semi-definite (but not necessary symmetric). Moreover, the solution set of (
1.8), denoted by
\(C^{\ast }\), is assumed to be nonempty.
Moreover, for given
\(x\in \mathbb{R}^{n}\), we denote
$$ \bar{x}=P_{C} \bigl[x-(Mx+q) \bigr]. $$
Hence, we have
$$ \bar{x}^{\ell }=P_{C} \bigl[x^{\ell }- \bigl(Mx^{\ell }+q \bigr) \bigr]. $$
(1.10)
We further use the notation
$$ e \bigl(x^{\ell } \bigr)=x^{\ell }- \bar{x}^{\ell }. $$
(1.11)
From (
1.10),
x is a solution of (
1.8) if and only if
\(x=\bar{x}\). Thus the residual of projection equation
\(\Vert e(x^{ \ell }) \Vert ^{2}\) can be used to measure the accuracy of an iterate
\(x^{\ell }\) to a solution of (
1.8).
More specifically, we proposed the following iterative scheme:
$$ x^{\ell +1}=x^{\ell }-\zeta \alpha ^{\ast }_{\ell }G^{-1} \bigl(I+M^{T} \bigr) \bigl(x ^{\ell }-\bar{x}^{\ell } \bigr), $$
(1.12)
where
\(\zeta \in (0,1)\) is a relaxation factor and the step size
\(\alpha ^{\ast }_{\ell }\) is determined by
$$ \alpha ^{\ast }_{\ell }=\frac{ \Vert x^{\ell }-\bar{x}^{\ell } \Vert ^{2}}{ \Vert G ^{-1}(I+M^{T})(x^{\ell }-\bar{x}^{\ell }) \Vert ^{2}_{G}}. $$
(1.13)
Obviously, for the step size
$$ \alpha ^{\ast }_{\ell }\geq \frac{1}{ \Vert (I+M)G^{-1}(I+M)^{T} \Vert _{2}}= \alpha _{\mathrm{min}}, $$
(1.14)
where
\(\Vert \cdot \Vert _{2}\) denotes the spectral norm of a matrix.
The sequence
\(\{x^{\ell }\}\) generated by (
1.12) satisfies the following inequality:
$$ \bigl\Vert x^{\ell +1}-x^{\ast } \bigr\Vert ^{2}_{G} \leq \bigl\Vert x^{\ell }-x^{\ast } \bigr\Vert ^{2}_{G}- \zeta (2-\zeta )\alpha ^{\ast }_{\ell } \bigl\Vert x^{\ell }- \bar{x}^{\ell } \bigr\Vert ^{2}, $$
(1.15)
where
\(x^{\ast }\) is an arbitrary solution of (
1.8). We note that
$$ \bigl\Vert x^{\ell }-\bar{x}^{\ell } \bigr\Vert ^{2}=0 $$
if and only if
\(x^{\ell }\) is a solution of (
1.8).
Now, we consider another iterative scheme for projection method:
$$ x^{\ell +1}=P_{C}^{G} \bigl[x^{\ell }-\zeta \alpha _{\ell }^{\ast }G^{-1} \bigl\{ \bigl(Mx ^{\ell }+q \bigr)+M^{T} \bigl(x^{\ell }- \bar{x}^{\ell } \bigr) \bigr\} \bigr], $$
(1.16)
where the step size
\(\alpha _{\ell }^{\ast }\) is also defined in (
1.13).
We note that the sequence
\(\{x^{\ell }\}\) is generated by (
1.16) also satisfies the property (
1.15) and thus its convergence is ensured.
In this work, we establish the worst-case
\(O(\frac{1}{t})\)-convergence rate measured by the iteration complexity for (
1.12) and (
1.16), where
t is the iteration counter.
In our analysis, we know that
$$ P_{C}^{G}(y)=\arg \min \biggl\{ \frac{1}{2} \Vert x-y \Vert ^{2}_{G} \Bigm| x\in C \biggr\} $$
and
$$ \bigl\langle y-P_{C}^{G}(y) , G \bigl(x-P_{C}^{G}(y) \bigr) \bigr\rangle \leq 0,\quad \forall y \in \mathbb{R}^{n},x\in C. $$
(1.17)
Let
\(x^{\ast }\) be any fixed solution of generalized complementarity problems. Since
\(\bar{x}^{\ell }\in C\), it follows from (
1.8) that
$$ \bigl\langle \bar{x}^{\ell }-x^{\ast }, Mx^{\ast }+q \bigr\rangle = 0,\quad \forall x ^{\ast }\in C^{\ast }. $$
(1.18)
Setting
\(y=x^{\ell }-(Mx^{\ell }+q)\),
\(G=I\) and
\(x=x^{\ast }\) in (
1.17), because of the notation
\(\bar{x}^{\ell }\), we have
$$ \bigl\langle \bar{x}^{\ell }-x^{\ast }, \bigl[x^{\ell }- \bigl(Mx^{\ell }+q \bigr) \bigr]- \bar{x}^{\ell } \bigr\rangle \geq 0,\quad \forall x^{\ast }\in C^{\ast }. $$
(1.19)
Adding Eqs. (
1.18) and (
1.19) we have
$$ \bigl\langle \bar{x}^{\ell }-x^{\ast }, \bigl(x^{\ell }- \bar{x}^{\ell } \bigr)-M \bigl(x ^{\ell }- x^{\ast } \bigr) \bigr\rangle \geq 0,\quad \forall x^{\ast }\in C^{\ast }, $$
and consequently
$$ \bigl\langle x^{\ell }-x^{\ast }, \bigl(I+M^{T} \bigr) \bigl(x^{\ell }- \bar{x}^{\ell } \bigr) \bigr\rangle \geq \bigl\Vert x^{\ell }-\bar{x}^{\ell } \bigr\Vert ^{2},\quad \forall x^{\ast } \in C^{\ast }. $$
(1.20)
2 An ϵ-approximated solution of generalized complementarity problems
To estimate the worst-case convergence rates measured by the iteration complexity for (
1.12) and (
1.16), we need to precisely define an
ϵ-approximated solution of (
1.8). We will consider the following two definitions, which are based on the generalized complementarity problems characterization and projection equation residual, respectively.
From [
6], we know that
\(C^{\ast }\) is a convex and it can be characterized as follows:
$$ C^{\ast }=\bigcap_{x\in C} \bigl\{ y\in C:\langle x-y, Mx+q\rangle = 0 \bigr\} . $$
Therefore, from [
17]
\(y\in C\) is an
ϵ-approximated solution point of (
1.8) if it satisfies
$$ y\in C \quad\text{and}\quad \inf_{x\in \mathcal{D}(y)} \bigl\{ \langle x-y, Mx+q\rangle \bigr\} \geq -\epsilon , $$
where
$$ \mathcal{D}(y)=\bigl\{ x\in C: \Vert x-y \Vert _{G}\leq 1\bigr\} . $$
Later, we show that, for given
\(\epsilon >0\), after at most
\(O(\frac{1}{\epsilon })\) iterations, both (
1.12) and (
1.16) can find
y such that
$$ y\in C \quad\text{and} \quad\sup_{x\in \mathcal{D}(y)} \bigl\{ \langle y-x, Mx+q\rangle \bigr\} \leq \epsilon. $$
(2.1)
As we mentioned as regards
\(e(x)\) defined in (
1.11),
\(\Vert e(x) \Vert ^{2}\) is a measure of the distance between the iterate
x and the solution set
\(C^{\ast }\). We call
y an
ϵ-approximation solution of generalized complementarity problems in the sense of a projection equation residual if
\(\Vert e(y) \Vert ^{2}\leq \epsilon \).
Now, we define
$$ q^{\ell }(\zeta )=\zeta (2-\zeta )\alpha _{\ell }^{\ast } \bigl\Vert x^{\ell }- \bar{x}^{\ell } \bigr\Vert ^{2}, $$
(2.2)
where
\(\alpha _{\ell }^{\ast }\) is given by (
1.13) and use the notation
where
M is the matrix in (
1.8). We show that the sequence
\(\{x^{\ell }\}\) generated by either (
1.12) or (
1.16) satisfies the inequality
$$ \zeta \alpha _{\ell }^{\ast } \bigl\langle x- \bar{x}^{\ell }, Mx+q \bigr\rangle \geq \frac{1}{2} \bigl( \bigl\Vert x-x^{\ell +1} \bigr\Vert ^{2}_{G}- \bigl\Vert x-x^{\ell } \bigr\Vert ^{2}_{G} \bigr)+ \frac{1}{2}q^{\ell }(\zeta ),\quad \forall x\in C, $$
(2.3)
where
\(q^{\ell }(\zeta )\) is defined in (
2.2).
Now, we prove the assertion (
2.3) for (
1.16) in the following lemma.
Based on Lemma
2.1 and
2.2, the strict contraction property of the sequences generated by (
1.12) and (
1.16) can easily be derived. On the basis of the above two lemmas, we have the following corollary.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.