Strong Convergence Theorem for the Lexicographic Ky Fan Inequality

Abstract

In this paper, building upon subgradient techniques and viscosity-type approximations, we propose a simple projection algorithm for solving the lexicographic Ky Fan inequality in a real Hilbert space, where the lower level is a variational inequality problem. By choosing suitable regularization parameters, a strong convergence of the proposed algorithm is established under mild assumptions imposed on the cost function. Some simple numerical examples are given to illustrate the performance of the proposed algorithm.

1 Introduction

Let $\mathcal {H}$ be a real Hilbert space equipped with an inner product 〈⋅,⋅〉 and its induced norm ∥⋅∥. Let C be a nonempty closed convex subset of $\mathcal {H}$. In this paper, we consider the lexicographic Ky Fan inequality, shortly L K F(g, F, C), as follows:

$$\text{Find}~x^{\ast}\in\text{Sol}(F, C) \text{ such that}~ g(x^{\ast}, x)\geq 0\quad \forall x\in \text{Sol}(F,C), $$

where $g: C\times C\to \mathcal {R}$, Sol(F, C) denotes the set of all solutions of the variational inequality problem:

$$\text{Find}~ y^{\ast}\in C \text{ such that } \langle F(y^{\ast}), y-y^{\ast}\rangle\geq 0\quad \forall y\in C, $$

and $F: C\to \mathcal {H}$. As usual, the bifunction g and the mapping F are called to be the cost bifunction and cost mapping.

Although Problem L K F(g, F, C) has a simple bilevel form, it coverts the following as special cases:

• 1. Ky Fan inequality problem: Let C be a nonempty closed convex subset of $\mathcal {H}$ and the bifunction $g: C\times C\to \mathcal {R}$. We consider the Ky Fan inequality problem (see [12]):

  $$ \text{Find}~x^{\ast}\in C~\text{such that}~g(x^{\ast}, x)\geq 0\quad \forall x\in C. $$

  (1)

  Setting F(x) = 0 for all x ∈ C, it is easy to see that Problem (1) coincides with the form L K F(g, F, C).

• 2. Bilevel variational inequality problem: Let C be a nonempty closed convex subset of $\mathcal {H}$, $G: C\to \mathcal {H}$ and $F: C\to \mathcal {H}$. The following problem is called the bilevel variational inequality problem (see [7, 16]), shortly B V I(G, F, C):

  $$\text{Find}~x^{\ast}\in \text{Sol}(F, C)~\text{such that}~\langle G(x^{\ast}), y-x^{\ast}\rangle\geq 0\quad \forall x\in \text{Sol}(F,C). $$

  By setting g(x, y) := 〈G(x), y − x〉 for all x, y ∈ C, we can easily see that B V I(G, F, C) is equivalent to L K F(G, F, C).

• 3. Minimum-norm problem: Let C be a nonempty closed convex subset of $\mathcal {H}$, $x^{0}\in \mathcal {H}$ and $F: C\to \mathcal {H}$. The minimum-norm problem, in [31], shortly M N(F, C), is formulated in the following:

  $$\min\{\|x^{0}-x\|: x\in \text{Sol}(F, C)\}. $$

  Taking g(x, y) := ∥y − x ⁰∥−∥x − x ⁰∥ for all x, y ∈ C, we can see that B V I(G, F, C) collapses into the minimum-norm problem M N(F, C).

Some methods for solving Problem L K F(g, F, C) and its special cases can be found, for instance, in [4, 5, 7, 14,15,16, 25, 28, 30]. A majority of existing methods is based on the proximal method which consists of solving a regularized Ky Fan problem, i.e., at current iteration, given the current iterate x ⁿ, we compute the next iterate x ⁿ⁺¹ by solving the following problem:

$$\text{Find}~x^{\ast}\in C \text{ such that } g(x^{\ast}, y) +\frac 1 r\langle y-x^{\ast}, x^{\ast}-x^{n}\rangle\geq 0\quad \forall y\in C, $$

where $g: C\times C\to \mathcal {R}$ and r > 0. It is well-known that the viscosity method is a fundamental method to solve variational inequalities where the constraint set is the fixed point set of a nonexpansive mapping (shortly, the hierarchical variational inequality). That is the problem of finding x ^∗∈Fix(T) (the fixed point set of a nonexpansive mapping T : C → C) such that

$$\langle (I-V)(x^{\ast}), x-x^{\ast}\rangle\geq 0\quad \forall x\in \text{Fix}(T), $$

where V : C → C is nonexpansive and I is the identity mapping. There are two schemes to solve the hierarchical variational inequality in a real Hilbert space that one implicit and one explicit as follows:

$$x_{t}=tf(x_{t})+(1-t)T(x_{t}) $$

and

$$x^{k+1}=\lambda_{k}f(x^{k})+(1-\lambda_{k})T(x^{k}), $$

where f is a contraction mapping on C, t ∈ (0,1) and {λ _k } ⊂ [0, 1].

In [22], Maingé and Moudafi considered the viscosity method for the hierarchical variational inequality as follows:

$$x^{0}\in C, x^{k+1}:=\lambda_{k} f(x^{k})+(1-\lambda_{k})[\alpha_{k} V(x^{k})+(1-\alpha_{k})T(x^{k})], $$

where f : C → C is a contraction. Under concrete conditions, the authors have shown that the iterative sequence strongly converges to a solution of the hierarchical variational inequality. We note that the method can be regarded as a generalized version of Halpern’s algorithm. In [18], Lu et al. investigated other hybrid viscosity approximation methods for solving the hierarchical variational inequality. By combining viscosity approximation methods with projected subgradient techniques, Maingé in [20] established a strong convergence theorem for optimization with variational inequality constraints in $\mathcal {H}$. Xu in [29] introduced a viscosity method for hierarchical fixed point approach to variational inequalities. Here, the author showed that the sequence defined by the implicit hierarchical scheme converges strongly in norm to a solution of the hierarchical variational inequality. Recently, the viscosity method has been studied to develop iteration algorithms for variational inequalities, Ky Fan inequalities, and other problems (see [9, 21]). Methods for solving Problem L K F(g, F, C) have also been studied extensively in the literature (see [1,2,3, 17, 23]).

The purpose of this paper is to extend the above viscosity approximation method in [22] to Problem L K F(g, F, C), with suitable modifications and subgradient techniques. Through this way, we obtain a strongly convergent algorithm for solving the problem in a real Hilbert space $\mathcal {H}$. The iterative algorithm is quite simple. At each iteration, we only require computing the subgradient of a subdifferentiable convex function and the projection of a point onto the domain.

This paper is organized as follows. In Section 2, we recall some definitions and lemmas used in the paper. Section 3 deals with proposing and analyzing the convergence of the algorithm. Finally, we present some numerical experiments to illustrate the behavior of the proposed algorithms in Section 4.

2 Preliminaries

In this section, we collect some definitions and lemmas that will be used in the sequel. Let C be a nonempty closed convex subset of $\mathcal {H}$, for every $x\in \mathcal H$, there exists a unique element Pr _C (x), defined by

$$\text{Pr}_{C} (x)=\arg\min\{\|y-x\|: y\in C\}. $$

It is also known that Pr _C is firmly nonexpansive, or 1-inverse strongly monotone, i.e.,

$$\langle \text{Pr}_{C} (x)-\text{Pr}_{C} (y), x-y\rangle \geq \|\text{Pr}_{C} (x)-\text{Pr}_{C} (y)\|^{2}\quad \forall x,y \in C. $$

Besides, we recall some other properties of the projection as follows (see [21, Proposition 4.1]):

$$\begin{array}{@{}rcl@{}} &&\|x-Pr_{C} (x)\|^{2}+\|Pr_{C} (x)-y\|^{2}\leq \|x-y\|^{2}\quad \forall x\in\mathcal H, y \in C,\\ &&\|x-\text{Pr}_{C} (x-y)\|\leq \|y\|\quad \forall x\in C, y\in\mathcal H,\\ &&\|z-\text{Pr}_{C}(x-y)\|^{2} \leq \|x-z\|^{2}-2\langle x-z, y\rangle+5\|y\|^{2} \quad \forall x, z\in C, y\in\mathcal H. \end{array} $$

(2)

A mapping $F: C\to \mathcal H$ is said to be monotone on C, if

$$\langle F(x) -F(y), x-y\rangle \ge 0\quad \forall x,y \in C; $$

paramonotone on C, if F is monotone on C and

$$\langle F(x) -F(y), x-y\rangle =0 \quad\Rightarrow\quad F(x)=F(y); $$

weakly closed on C, if

$$\left\{\{x^{k}\}\subset C, x^{k} \rightharpoonup x \text{ (weakly) and } F(x^{k}) \rightharpoonup w \text{ (weakly) } \right\} \Rightarrow w=F(x). $$

A bifunction $g: C\times C\to \mathcal R$ is said to be monotone on C, if

$$g(x,y)+g(y, x)\leq 0\quad \forall x, y\in C; $$

ρ-strongly monotone on C, if

$$g(x,y)+g(y, x)\leq -\rho\|x-y\|^{2}\quad \forall x, y\in C. $$

Throughout this paper, we consider the bifunction g, the mapping F and regularization parameters with the following assumptions:

• (A ₁) g is ρ-strongly monotone and for each x ∈ C, g(x,⋅) is weakly continuous and convex on the domain $C, \partial _{2} g(x,\cdot )(x):=\{w_{x}\in \mathcal H: g(x,y)\geq \langle w_{x}, y-x\rangle \forall y\in C\}$ is upper semicontinuous and g(x, x) = 0 for all x ∈ C.

• (A ₂) $F: C \to \mathcal H$ is paramonotone and weakly closed on C, and Lipschitz continuous on the domain C.

• (A ₃) The solution set $\text {Sol}(F, C):=\{\bar x\in C: \langle F(\bar x), y-\bar x\rangle \geq 0\, \forall y \in C\}$ is nonempty.

• (A ₄) μ ∈ (0, ∞), there are two nonnegative real sequences {α _k } and {λ _k } such that

  $$\sum\limits_{k=0}^{\infty} \lambda_{k} =\infty,\quad \sum\limits_{k=0}^{\infty} {\lambda_{k}^{2}}<\infty,\quad \lim_{ k\to \infty} \alpha_{k}=0,\quad \sum\limits_{k=0}^{\infty} \alpha_{k}=\infty,\quad \sum\limits_{k=0}^{\infty} \alpha_{k}\lambda_{k}=\infty. $$

It is easy to check again that condition (A ₄) is satisfied by

$$\lambda_{k}:=\frac 1{(k+1)^{\lambda}},\quad \alpha_{k}:=\frac 1 {(k+1)^{\alpha}},\qquad \text{with } \lambda\in\left( \frac{1}{2}, 1\right) \text{ and } \alpha\in (0, 1-\lambda). $$

We recall a series of preliminary results needed for our convergence analysis.

Lemma 1

[8] Let {a _n }, {b _n }, and {c _n } be three sequences of nonnegative real numbers satisfying the inequality

$$a_{n+1}\leq (1+b_{n})a_{n}+c_{n}\quad \forall n\geq n_{0}, $$

for some integer n ₀ ≥ 1, where ${\sum }_{n=n_{0}}^{\infty }b_{n}<+\infty$ and ${\sum }_{n=n_{0}}^{\infty }c_{n}<+\infty$. Then $\lim _{n\to \infty }a_{n}$ exists. If in addition {a _n } has a subsequence whichconverges to zero, then $\lim _{n\to \infty }a_{n}=0$.

Lemma 2

[20] Let {b _n } be a sequence of real numbers that is not decreased at infinity, in the sense that there exists a subsequence $\{b_{n_{j}}\}$ of {b _n } which satisfies $b_{n_{j}} < b_{n_{j}+1}$ for all j ≥ 0 . We also consider a sequence of integers {τ _n } defined by

$$\tau_{n} =\max\{k\le n: b_{k}<b_{k+1}\}. $$

Then, {τ _n }(n ≥ n ₀) is a nondecreasingsequence verifying $\lim _{n\to \infty }\tau _{n}=\infty$, and for all n ≥ 0, it holds that

$$b_{\tau_{n}}< b_{\tau_{n}+1}\quad\text{ and } \quad b_{n} <b_{\tau_{n}+1}. $$

Lemma 3

[20] Let {λ _n } and {β _n } be nonnegative sequences such that

$$\sum\limits_{n=0}^{\infty}\lambda_{n} =\infty, \quad \sum\limits_{n=0}^{\infty}{\lambda_{n}^{2}} <\infty, \quad \text{and}\quad \sum\limits_{n=0}^{\infty}\lambda_{n}\beta_{n} <\infty. $$

Then, the following two results hold:

• (i) There exists a subsequence $\{\beta _{n_{k}}\}$ of {β _n } such that $\lim _{k\to \infty }\beta _{n_{k}}=0$.

• (ii) If {λ _n } and {β _n } are also such that β _n+1 − β _n < 𝜃 λ _n (for some positive 𝜃), then {β _n } satisfies $\lim _{n\to \infty }\beta _{n}=0$.

Lemma 4

[21] Let ϕ be the functional defined on C as ϕ(⋅) := 〈F(⋅),⋅− q〉, where $q \in \mathcal {H}$ and $F : C \to \mathcal {H}$ is monotone and weakly closed on C, and Lipschitz continuous on bounded subsets of C. Then, ϕ is weakly lower semicontinuous on C.

3 Convergence Results

In order to solve Problem L K F(g, F, C), we investigate the convergence analysis of the sequence {x ^k} given by the following iterative scheme.

We begin with the following lemma.

Lemma 5

Let the sequences {x ^k} and {w ^k} be generated by Algorithm 1. Then

• (i) ∥x ^k+1 − x ^k∥ ≤ λ _k for all k ≥ 0.

• (ii) The following holds for all x ^∗ ∈ Sol(F, C)

  $$ \|x^{k+1}-x^{\ast}\|^{2}\leq \|x^{k}-x^{\ast}\|^{2}-\frac{2\lambda_{k}}{\eta_{k}}\langle F(x^{k}), x^{k}-x^{\ast}\rangle-\frac{2\alpha_{k}\lambda_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle+5{\lambda_{k}^{2}}. $$

  (3)

Proof

(i) Since Pr _C is firmly nonexpansive, x ^k ∈ C and Step 2 of the algorithm provided for ∥d ^k∥≤ η _k , we have

$$\begin{array}{@{}rcl@{}} \|x^{k+1}-x^{k}\| &=& \left\|\text{Pr}_{C}\left( x^{k}-\frac{\lambda_{k}}{\eta_{k}}d^{k}\right)-x^{k}\right\|\\ &=& \left\|\text{Pr}_{C}\left( x^{k}-\frac{\lambda_{k}}{\eta_{k}}d^{k}\right)-\text{Pr}_{C}(x^{k})\right\|\\ &\leq& \left\|\left( x^{k}-\frac{\lambda_{k}}{\eta_{k}}d^{k}\right)-x^{k}\right\|\\ &=& \frac{\lambda_{k}}{\eta_{k}}\|d^{k}\|\leq \lambda_{k}. \end{array} $$

This implies (i).

(ii) Applying property (2) for x := x ^k ∈ C, z := x ^∗∈ C, and $y:=\frac {\lambda _{k}}{\eta _{k}}d^{k}\in \mathcal {H}$, and using $x^{k+1}=\text {Pr}_{C}\left (x^{k}-\frac {\lambda _{k}}{\eta _{k}}d^{k}\right )$, we obtain

$$\begin{array}{@{}rcl@{}} \|x^{k+1}-x^{\ast}\|^{2}&= &\left\|x^{\ast}-\text{Pr}_{C}\left( x^{k}-\frac{\lambda_{k}}{\eta_{k}}d^{k}\right)\right\|^{2}\\ &\leq&\|x^{k}-x^{\ast}\|^{2}-2\frac{\lambda_{k}}{\eta_{k}}\langle d^{k}, x^{k}-x^{\ast}\rangle+5\left( \frac{\lambda_{k}}{\eta_{k}}\|d^{k}\|\right)^{2}. \end{array} $$

Combining the latter inequality with the bound ∥d ^k∥≤ η _k , and d ^k = T(x ^k) + α _k w ^k, we get

$$\begin{array}{@{}rcl@{}} \|x^{k+1}-x^{\ast}\|^{2}&\leq&\|x^{k}-x^{\ast}\|^{2}-2\frac{\lambda_{k}}{\eta_{k}}\langle d^{k}, x^{k}-x^{\ast}\rangle+5\left( \frac{\lambda_{k}}{\eta_{k}}\|d^{k}\|\right)^{2}\\ &\leq&\|x^{k}-x^{\ast}\|^{2}-2\frac{\lambda_{k}}{\eta_{k}}\langle d^{k}, x^{k}-x^{\ast}\rangle+5{\lambda_{k}^{2}}\\ &=&\|x^{k}-x^{\ast}\|^{2}-2\frac{\lambda_{k}}{\eta_{k}}\langle F(x^{k}), x^{k}-x^{\ast}\rangle-2\frac{\lambda_{k}\alpha_{k}}{\eta_{k}}\langle w^{k}, x^{k}-x^{\ast}\rangle+5{\lambda_{k}^{2}}. \end{array} $$

This implies (3). □

Theorem 1

Let the above assumptions (A ₁) – (A ₄) hold. Then, the sequence {x ^k} generated by Algorithm 1 converges strongly to the unique solution of Problem L K F(g, F, C).

Proof

We divide the proof into several claims.

Claim 1

The sequence {x ^k} is bounded.

Indeed, for each x ^∗ ∈ Sol(F, C), we have 〈F(x ^∗), x − x ^∗〉 ≥ 0 for all x ∈ C. By the monotonicity of F and x ^k ∈ C, we get 〈F(x ^k), x ^k − x ^∗〉 ≥ 0. Combining this and inequality (3), we have

$$\|x^{k+1}-x^{\ast}\|^{2}\leq \|x^{k}-x^{\ast}\|^{2}-\frac{2\alpha_{k}\lambda_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle+5{\lambda_{k}^{2}}. $$

Consequently,

$$\|x^{k+1}-x^{\ast}\|^{2}-5\sum\limits_{j=0}^{k}{\lambda^{2}_{j}}\leq \|x^{k}-x^{\ast}\|^{2}-5\sum\limits_{j=0}^{k-1}{\lambda^{2}_{j}}-\frac{2\alpha_{k}\lambda_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle. $$

For each k ≥ 1, set $a_{k}:=\|x^{k}-x^{\ast }\|^{2}-5{\sum }_{j=0}^{k-1}{\lambda ^{2}_{j}}$. Then,

$$ a_{k+1}-a_{k}+\frac{2\alpha_{k}\lambda_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle\leq 0\quad \forall k\geq 1. $$

(4)

Case 1

There exists an index k ₀ > 0 such that the sequence {a _k } is nonincreasing with k ≥ k ₀. It implies that {a _k } is bounded above by $a_{k_{0}}$ for all k ≥ k ₀, i.e., $a_{k}:=\|x^{k}-x^{\ast }\|^{2}-5{\sum }_{j=0}^{k-1}{\lambda ^{2}_{j}}\leq a_{k_{0}} \forall k\geq k_{0}$. Using assumption (A ₄) that ${\sum }_{k=0}^{\infty }{\lambda ^{2}_{k}}<\infty$, we have

$$\|x^{k}-x^{\ast}\|^{2}\leq 5\sum\limits_{j=0}^{k-1}{\lambda^{2}_{j}}+a_{k_{0}}<\infty. $$

It follows that the sequence {x ^k} is bounded.

Case 2

There exists a subsequence $\{a_{k_{j}}\}$ of {a _k } such that $a_{k_{j}}<a_{k_{j}+1}$ for all j ≥ 0. By Lemma 2, we have a subsequence {τ _k } such that

$$ a_{\tau_{k}}<a_{\tau_{k}+1} \quad \text{ and} \quad a_{k}<a_{\tau_{k}+1}\qquad \forall k\geq 1. $$

(5)

Replacing k := τ _k in (4) and using (5), we obtain

$$\langle x^{\tau_{k}}-x^{\ast}, w^{\tau_{k}}\rangle \leq 0. $$

Combining this with the convexity of g(x,⋅), the ρ-strong monotonicity of g and g(x, x) = 0 for all x ∈ C, we get

$$\begin{array}{@{}rcl@{}} 0&\leq&\langle w^{\tau_{k}}, x^{\ast}- x^{\tau_{k}}\rangle\\ &\leq &g(x^{\tau_{k}}, x^{\ast})-g(x^{\tau_{k}}, x^{\tau_{k}})\\ &=&g(x^{\tau_{k}}, x^{\ast})\\ &\leq&-g(x^{\ast}, x^{\tau_{k}})-\rho\|x^{\tau_{k}}-x^{\ast}\|^{2}. \end{array} $$

Then, for all w ^∗∈ ∂ ₂ g(x ^∗, x ^∗), we have

$$\begin{array}{@{}rcl@{}} \rho\|x^{\tau_{k}}-x^{\ast}\|^{2} &\leq& -g(x^{\ast}, x^{\tau_{k}})\\ &\leq& -g(x^{\ast}, x^{\ast})-\langle w^{\ast}, x^{\tau_{k}}-x^{\ast}\rangle\\ &=&-\langle w^{\ast}, x^{\tau_{k}}-x^{\ast}\rangle\\ &\leq&\| w^{\ast}\| \| x^{\tau_{k}}-x^{\ast}\|. \end{array} $$

This shows that the sequence $\{x^{\tau _{k}}\}$ is bounded and hence $\{a_{\tau _{k}}\}$ defined as $a_{\tau _{k}}=\|x^{\tau _{k}}-x^{\ast }\|^{2}-5{\sum }_{k=0}^{\tau _{k}-1}\lambda ^{2}_{\tau _{k}}$ is also bounded. It follows from this and (5) that the sequence {a _k } is bounded. By a similar argument as in Case 1, we conclude that the sequence {x ^k} is bounded.

Claim 2

For each x ^∗ ∈ Sol(F, C) and a bounded sequence {z ^k} in C such that

$$ \lim_{k\to \infty}\langle F(z^{k}), z^{k}-x^{\ast}\rangle=0, $$

(6)

we claim that any weak cluster point of {z ^k} belongs to Sol(F, C).

Indeed, suppose that $\{z^{k_{j}}\}$ is a subsequence of {z ^k} such that $z^{k_{j}}$ converges weakly to $\hat z$ in $\mathcal {H}$. Obviously, $\hat z\in C$, because C is assumed to be closed and convex. Applying Lemma 4 for q := x ^∗, ϕ(x) := 〈F(x), x − x ^∗〉 and using Assumption (A ₂), we have that ϕ is weakly lower semicontinuous on C and hence

$$ \langle F(\hat z), \hat z-x^{\ast}\rangle=\phi(z)\leq \liminf\limits_{j\to \infty}\phi(z^{k_{j}})=\liminf\limits_{j\to \infty}\langle F(z^{k_{j}}), z^{k_{j}}-x^{\ast}\rangle. $$

(7)

From the monotonicity of F and x ^∗∈Sol(F, C), it follows that

$$ 0\leq \langle F(x^{\ast}), \hat z-x^{\ast}\rangle\leq \langle F(\hat z), \hat z-x^{\ast}\rangle. $$

(8)

Assumption (6) yields

$$\liminf_{j\to \infty}\langle F(z^{k_{j}}), z^{k_{j}}-x^{\ast}\rangle=0. $$

Combining this, (7) and (8), we obtain $\langle F(\hat z), \hat z-x^{\ast }\rangle =0$. Since F is paramonotone and x ^∗∈Sol(F, C), we also have $\hat z\in \text {Sol}(F, C)$.

Claim 3

We show that, for all x ^∗ ∈ Sol(F, C), there exists γ > 0 such that

$$\langle F(x^{k+1}), x^{k+1}-x^{\ast}\rangle- \langle F(x^{k}), x^{k}-x^{\ast}\rangle\leq \gamma\lambda_{k}. $$

Indeed, by Lemma 5 and the Lipschitz continuity of F, we have

$$\begin{array}{@{}rcl@{}} &&\langle F(x^{k+1}), x^{k+1}-x^{\ast}\rangle- \langle F(x^{k}), x^{k}-x^{\ast}\rangle\\ &&=\langle F(x^{k+1}), x^{k+1}{}-{}x^{\ast}\rangle{}-{} \langle F(x^{k+1}), x^{k}{}-{}x^{\ast}\rangle{}+{}\langle F(x^{k+1}), x^{k}{}-{}x^{\ast}\rangle{}-{} \langle F(x^{k}), x^{k}{}-{}x^{\ast}\rangle\\ &&=\langle F(x^{k+1}), x^{k+1}-x^{k}\rangle+ \langle F(x^{k+1})-F(x^{k}), x^{k}-x^{\ast}\rangle\\ &&\leq \|F(x^{k+1})\| \|x^{k+1}-x^{k}\|+ L \|x^{k+1}-x^{k}\| \|x^{k}-x^{\ast}\|\\ &&=(\|F(x^{k+1})\| + L\|x^{k}-x^{\ast}\|)\|x^{k+1}-x^{k}\|\\ &&=(\|F(x^{k+1})\| + L\|x^{k}-x^{\ast}\|)\lambda_{k}\\ &&\leq \gamma\lambda_{k}, \end{array} $$

where γ := sup{∥F(x ^k+1)∥ + L∥x ^k − x ^∗∥ : k ≥ 1}. By Claim 1, we have γ < + ∞.

Claim 4

The sequence {x ^k} converges strongly to the unique solution x ^∗ of L K F(g, F, C).

Indeed, Claim 1 ensures the boundedness of the sequence {x ^k}, hence {F(x ^k)} is bounded (by the Lipschitz continuity of F on bounded subsets of C), and so is {w ^k} (from Assumption (A ₁)). By the definition of η _k , we easily observe that {η _k } is bounded, so that there exists a positive constant δ such that

$$ \mu\leq \eta_{k} \leq \delta\quad \forall k\geq 0. $$

(9)

Set

$$b_{j}=\|x^{j}-x^{\ast}\|^{2}+\sum\limits_{i=0}^{j-1}\frac{\lambda_{i}\beta_{i}}{\eta_{i}}-5\sum\limits_{i=0}^{j-1}{\lambda_{i}^{2}}. $$

By Lemma 5, form (3) can be equivalently rewritten as

$$\begin{array}{@{}rcl@{}} &&\|x^{k+1}-x^{\ast}\|^{2}+\sum\limits_{i=0}^{k}\frac{\lambda_{i}\langle F(x^{i}), x^{i}-x^{\ast}\rangle}{\eta_{i}}-5\sum\limits_{i=0}^{k}{\lambda_{i}^{2}}\\ &&\leq \|x^{k}-x^{\ast}\|^{2}+\sum\limits_{i=0}^{k-1}\frac{\lambda_{i}\langle F(x^{i}), x^{i}-x^{\ast}\rangle}{\eta_{i}}-5\sum\limits_{i=0}^{k-1}{\lambda_{i}^{2}}-\frac{\lambda_{k}}{\eta_{k}}\langle F(x^{k}), x^{k}-x^{\ast}\rangle\\ &&\quad-\frac{2\alpha_{k}\lambda_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle. \end{array} $$

This means that

$$ b_{k+1}\leq b_{k} -\frac{\lambda_{k}}{\eta_{k}}\langle F(x^{k}), x^{k}-x^{\ast}\rangle-\frac{2\alpha_{k}\lambda_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle. $$

(10)

Now, we consider two cases as follows:

Case 1

There exists k ₀ such that {b _k }(k ≥ k ₀) is nonincreasing, i.e., b _k+1 ≤ b _k for all k ≥ k ₀, namely

$$\|x^{k+1}-x^{\ast}\|^{2}\leq \|x^{k}-x^{\ast}\|^{2}- \frac{\lambda_{k}\langle F(x^{k}), x^{k}-x^{\ast}\rangle}{\eta_{k}}+ 5{\lambda_{k}^{2}}. $$

From the above proof 〈F(x ^k), x ^k − x ^∗〉≥〈F(x ^∗), x ^k − x ^∗〉≥ 0, we have

$$ \|x^{k+1}-x^{\ast}\|^{2}\leq \|x^{k}-x^{\ast}\|^{2}+ 5{\lambda_{k}^{2}}. $$

Since ${\sum }_{k=0}^{\infty }{\lambda _{k}^{2}}<\infty$ and Lemma 1, we obtain

$$ \lim_{k\to \infty}\|x^{k}-x^{\ast}\| \text{ exists and } \sum\limits_{k=0}^{\infty}\frac{\lambda_{k}\langle F(x^{k}), x^{k}-x^{\ast}\rangle}{\eta_{k}}<\infty. $$

(11)

From (9), together with the second estimate in (11), we immediately have

$$\sum\limits_{k=0}^{\infty}\lambda_{k}\langle F(x^{k}), x^{k}-x^{\ast}\rangle<\infty. $$

Then, by Claim 3, together with our assumptions ${\sum }_{k=0}^{\infty }{\lambda _{k}^{2}}<\infty$, ${\sum }_{k=0}^{\infty }\lambda _{k}=\infty$, and using Lemma 3, we obtain $\lim _{k\to \infty }\langle F(x^{k}), x^{k}-x^{\ast }\rangle =0$. As a consequence, Claim 2 shows that any weak cluster point of {x ^k} belongs to Sol(F, C). By Lemma 5, we obviously have

$$ \frac{\lambda_{k}\alpha_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle \leq \frac{1}{2}\left( \|x^{k}-x^{\ast}\|^{2}-\|x^{k+1}-x^{\ast}\|^{2}+5{\lambda_{k}^{2}}\right). $$

From the boundedness of the sequence {x ^k} and ${\sum }_{k=0}^{\infty }{\lambda _{k}^{2}}<\infty$, we have

$$ \sum\limits_{k=0}^{\infty}\frac{\lambda_{k}\alpha_{k}}{\eta_{k}}\langle x^{k}-x^{\ast}, w^{k}\rangle <\infty. $$

(12)

Moreover, from (9) and the assumption ${\sum }_{k=0}^{\infty }\lambda _{k}\alpha _{k}=\infty$, it is easily seen that ${\sum }_{k=0}^{\infty }\frac {\lambda _{k}\alpha _{k}}{\eta _{k}}=\infty$. This together with (12), leads immediately to

$$ \liminf_{k\to\infty}\langle x^{k}-x^{\ast}, w^{k}\rangle \leq 0. $$

(13)

By the ρ-strong monotonicity of g and w ^k ∈ ∂ ₂ g(x ^k, x ^k), we also have

$$\begin{array}{@{}rcl@{}} \rho\|x^{k}-x^{\ast}\|^{2}&\leq& -g(x^{k}, x^{\ast})- g(x^{\ast}, x^{k})\\ &\leq&\langle w^{k}, x^{k}-x^{\ast}\rangle- g(x^{\ast}, x^{k}). \end{array} $$

(14)

Consequently, we get

$$\rho\liminf_{k\to \infty}\|x^{k}-x^{\ast}\|^{2}\leq \liminf_{k\to \infty}\langle w^{k}, x^{k}-x^{\ast}\rangle - \liminf_{k\to \infty} g(x^{\ast}, x^{k}). $$

Taking into account this and (13), we therefore obtain

$$ \liminf_{k\to \infty}\|x^{k}-x^{\ast}\|^{2}\leq -\frac 1{\rho}\liminf_{k\to \infty} g(x^{\ast}, x^{k}). $$

(15)

Since {x ^k} is bounded and using the weak continuity of g(x ^∗,⋅), there exists a subsequence $\{x^{k_{j}}\}$ of {x ^k} converging weakly to an element $\bar x$ in $\mathcal H$ such that

$$ \liminf_{k\to \infty} g(x^{\ast}, x^{k})=\liminf_{j\to \infty} g(x^{\ast}, x^{k_{j}})=g(x^{\ast}, \bar x). $$

(16)

By Claim 2 and x ^∗ is the unique solution of Problem L K F(g, F, C), $\bar x\in \text {Sol}(F, C)$ and hence $g(x^{\ast }, \bar x)\geq 0$. Then, combining (15) and (16), we obtain

$$\liminf_{k\to \infty}\|x^{k}-x^{\ast}\|^{2}=0. $$

As a consequence, by the first estimate in (11), we deduce that

$$\lim_{k\to \infty}\|x^{k}-x^{\ast}\|^{2}=0. $$

Case 2

There does not exist k ₀ such that {b _k }(k ≥ k ₀) is nonincreasing. This implies that there exists a subsequence $\{b_{k_{j}}\}$ of {b _k } such that $b_{k_{j}}<b_{k_{j}+1}$ for all j ≥ 0. In this case, we have a sequence of indexes {τ _k } as defined in Lemma 2 such that $b_{\tau _{k}}<b_{\tau _{k}+1}$ and $b_{k}<b_{\tau _{k}+1}$. Denote by $\mathcal W(x^{\tau _{k}})$ the set of weak cluster-points of $\{x^{\tau _{k}}\}$. By Claim 2, we have $\mathcal W(x^{\tau _{k}})\subset \text {Sol}(F, C)$. From (10), the ρ-trong monotonicity of g and $w^{\tau _{k}}\in \partial _{2} g(x^{\tau _{k}},x^{\tau _{k}})$, we have

$$\begin{array}{@{}rcl@{}} \langle F(x^{\tau_{k}}), x^{\tau_{k}}-x^{\ast}\rangle&\leq& -2\alpha_{\tau_{k}}\langle x^{\tau_{k}}-x^{\ast}, w^{\tau_{k}}\rangle \\ &\leq &2 \alpha_{\tau_{k}}[g(x^{\tau_{k}}, x^{\ast})-g(x^{\tau_{k}}, x^{\tau_{k}})]\\ &=&2 \alpha_{\tau_{k}}g(x^{\tau_{k}}, x^{\ast})\\ &\leq&-2 \alpha_{\tau_{k}}\rho\|x^{\tau_{k}}-x^{\ast}\|^{2}-2 \alpha_{\tau_{k}}g(x^{\ast}, x^{\tau_{k}}) \\ &\leq &-2 \alpha_{\tau_{k}}\rho\|x^{\tau_{k}}-x^{\ast}\|^{2}-2 \alpha_{\tau_{k}}\langle w^{\ast}, x^{\tau_{k}}-x^{\ast}\rangle, \end{array} $$

(17)

where w ^∗∈ ∂ ₂ g(x ^∗, x ^∗). Consequently,

$$\langle F(x^{\tau_{k}}), x^{\tau_{k}}-x^{\ast}\rangle\leq -2 \alpha_{\tau_{k}}[\rho\|x^{\tau_{k}}-x^{\ast}\|^{2}+\langle w^{\ast}, x^{\tau_{k}}-x^{\ast}\rangle]. $$

Combining this, $\langle F(x^{\tau _{k}}), x^{\tau _{k}}-x^{\ast }\rangle \geq 0$ and the boundedness of {x ^k}, we can derive

$$\lim_{k\to\infty}\langle F(x^{\tau_{k}}), x^{\tau_{k}}-x^{\ast}\rangle=0. $$

Furthermore, since $\langle F(x^{\tau _{k}}), x^{\tau _{k}}-x^{\ast }\rangle \geq 0$ and (17), we obviously have

$$\langle w^{\tau_{k}}, x^{\tau_{k}}-x^{\ast}\rangle\le 0, $$

which, in light of (14), leads to

$$g(x^{\ast}, x^{\tau_{k}})\leq -\rho\|x^{\tau_{k}}-x^{\ast}\|^{2}. $$

Passing to the upper limit, we obtain

$$\limsup_{k\to \infty}\|x^{\tau_{k}}-x^{\ast}\|^{2}\leq-\frac{1}{\rho}\limsup_{k\to \infty} g(x^{\ast}, x^{\tau_{k}})=-\frac{1}{\rho}g(x^{\ast}, \bar z)\leq 0, $$

so that

$$\lim_{k\to \infty}\|x^{\tau_{k}}-x^{\ast}\|^{2}=0\quad\Rightarrow\quad x^{\tau_{k}}\to x^{\ast} \text{ as } k\to\infty. $$

Using the inequality $b_{k}< b_{\tau _{k}+1}$ for all k ≥ k ₀, i.e.,

$$\begin{array}{@{}rcl@{}} &&\|x^{k}-x^{\ast}\|^{2}+\sum\limits_{j=0}^{k-1}\frac{\lambda_{j}\langle F(x^{j}), x^{j}-x^{\ast}\rangle}{\eta_{j}}-5\sum\limits_{j=0}^{k-1}{\lambda_{j}^{2}}\\ &&\qquad\leq \|x^{\tau_{k}+1}-x^{\ast}\|^{2}+\sum\limits_{j=0}^{\tau_{k}}\frac{\lambda_{j}\langle F(x^{j}), x^{j}-x^{\ast}\rangle}{\eta_{j}}-5\sum\limits_{j=0}^{\tau_{k}}{\lambda_{j}^{2}}. \end{array} $$

By the definition of τ _k and 〈F(x ^j), x ^j − x ^∗〉≥ 0, we get τ _k ≤ k and hence

$$ \|x^{k}-x^{\ast}\|^{2}\leq\|x^{\tau_{k}+1}-x^{\ast}\|^{2}+\sum\limits_{j=\tau_{k}}^{k}\frac{\lambda_{j}\langle F(x^{j}), x^{j}-x^{\ast}\rangle}{\eta_{j}}+5\sum\limits_{j=\tau_{k}}^{k}{\lambda_{j}^{2}}. $$

(18)

Combining this and Assumption (A ₄), we have

• $\lim _{k\to \infty }{\sum }_{j=\tau _{k}}^{k}{\lambda _{j}^{2}}=0$ (because τ _k → + ∞) and ${\sum }_{j=1}^{\infty }{\lambda _{j}^{2}}<\infty$;

• $\lim _{k\to \infty }{\sum }_{j=\tau _{k}}^{k}\frac {\lambda _{j}\langle F(x^{j}), x^{j}-x^{\ast }\rangle }{\eta _{j}}=0$, because ${\sum }_{j=\tau _{k}}^{k}\langle F(x^{j}), x^{j}-x^{\ast }\rangle \to 0$, λ _k → 0 and η _k is bounded away from zero;

• $\lim _{k\to \infty }\|x^{\tau _{k}+1}-x^{\ast }\|=0$.

From this and (18), we deduce that $\lim _{k\to \infty }\|x^{k} -x^{\ast }\|=0$ and the sequence {x ^k} converges strongly to x ^∗. □

4 Examples and Numerical Results

In this section, we illustrate the proposed algorithms by applying it to solve a class of the lexicographic Ky Fan inequality defined by L K F(g, F, C). Here, C is a polyhedral convex set given by

$$C:=\{x\in\mathcal R^{n}: Ax\leq b\}, $$

and the bifunction $g: C\times C\to \mathcal R$ is of the form

$$g(x, y):=\langle G(x)+Qy+q, y-x\rangle, $$

where $G: C\to \mathcal R^{n}$, $Q\in \mathcal R^{n\times n}$ is a symmetric positive semidefinite matrix and $q\in \mathcal R^{n}$. Since Q is symmetric positive semidefinite, g(x,⋅) is convex for each fixed x ∈ C. The cost mapping F will be specified in detail in the following examples. It is well-known that if G is ξ-strongly monotone on C and ξ > ∥Q∥, then g is strongly monotone on C × C with constant ξ −∥Q∥ (see [27], later [26]). As usual, we can say that x ^k is an 𝜖-solution of Problem L K F(g, F, C) if ∥x ^k+1 − x ^k∥≤ 𝜖.

Example 1

Consider the mapping $F: \mathcal R^{3}\to \mathcal R^{3}$ given in [28] which is paramonotone (not strictly monotone) of the form

$$F(x):= \left( \begin{array}{ccc} 2&2&0\\ 1&2&0\\ 0&0&0 \end{array}\right) x,\quad G(x):=Px, \quad \text{and} \quad P:= \left( \begin{array}{ccc} 6.1&2&0\\ 2&5.6&0\\ 0&0&4.5 \end{array}\right). $$

In this example, let C, Q and q be defined by

$$C:=\{x\in\mathcal R^{3}: x_{i}\geq 0\, \forall i=1, 2, 3, x_{1}+x_{2}+x_{3}\leq 10\} $$

and

$$Q:= \left( \begin{array}{ccc} 1.6&1&0\\ 1&1.6&0\\ 0&0&1.5 \end{array}\right),\quad q:= \left( \begin{array}{c} 1\\ -3\\ 4\end{array}\right). $$

It is easy to see that G is strongly monotone with constant ξ = 3.8344, F is Lipschitz continuous with the constant L = 3.5616 and ∥Q∥ = 2.6. Then, g is strongly monotone with the constant ξ −∥Q∥ = 1.2344 and ∂ ₂ g(x, x) = {(P + Q)x + q}. To test Algorithm 1, we choose parameters:

$$\mu=5,\quad \lambda:=0.75,\quad \alpha:=0.2,\quad \lambda_{k}:=\frac 1 {(k+1)^{0.75}},\quad \alpha_{k}:=\frac 1{(k+1)^{0.2}}\quad \forall k\geq 0. $$

Then, the iterative scheme for solving L K F(g, F, C) is formulated as follows:

$$ d^{k} = F(x^{k})+\alpha_{k} [(P+Q)x^{k}+q], \eta_{k}=\max\{\mu, \|d^{k}\|\}\ \text{ and } x^{k+1}:=\text{Pr}_{C}\left( x^{k}-\frac{\lambda_{k}}{\eta_{k}}d^{k}\right). $$

(19)

The experiments are implemented in Matlab R2013a running on a Laptop Intel(R) Core(TM) i3-3110M CPU @ 2.40 GHz 2.40 GHz 4 Gb RAM.

Example 2

Consider the mapping $F: \mathcal R^{4}\to \mathcal R^{4}$ described in [13] which is paramonotone of the form

$$\begin{array}{@{}rcl@{}} &&F(x)=(x_{1}-2x_{2}, -2x_{1}+4x_{2}, x_{3}-2x_{4}, -2x_{3}+4x_{4})^{T}\quad\text{ and } \\ &&\qquad\quad\qquad G(x):=Px,\quad P:= \left( \begin{array}{cccc} 7&2.5&0&0\\ 2.5&5.5&0&0\\ 0&0&4&1\\ 0&0&1&2.7 \end{array}\right). \end{array} $$

Take C, Q, and q as follows:

$$C:=\{x\in\mathcal R^{4}: x_{i}\geq 0\, \forall i=1,\dots, 4, x_{1}+x_{2}+x_{3}+x_{4}\leq 9\}, $$

and

$$Q:= \left( \begin{array}{cccc} 1.2&1&0&0\\ 1&1.5&0&0\\ 0&0&1.2&0\\ 0&0&0&3.5 \end{array}\right),\quad q:= \left( \begin{array}{c} -1\\ 2\\ 3\\ 5\end{array}\right). $$

Then, F is Lipschitz continuous and g is strongly monotone on $\mathcal R^{4}$ which satisfy Assumptions (A ₁)– (A ₃).

From the preliminary numerical results reported in Tables 1 and 2, we observe that

• (a) As with other methods for Ky Fan inequalities such as the proximal point algorithm, or the auxiliary principle for equilibrium problems, the convergence speed of the algorithm depends very much on the starting point.

• (b) The algorithm is quite sensitive to the choice of the parameters λ _k and α _k .

Table 1 Scheme (19) with different starting points, Example 1, the tolerance 𝜖 = 10⁻³

Table 2 Scheme (19) with different parameters, Example 2, x ⁰ = (0,1,2,3), 𝜖 = 10⁻³, and μ = 5