Variational inequality; Bregman distance; KL divergence; Sparse logistic regression; Matrix games

MSC 47J20, 49J40, 65K15, 65Y20

1 Introduction↩︎

Let \(\mathcal{H}\) be a real finite dimentional Hilbert space. A mixed variational inequality problem (MVIP) is a problem to find \(w^*\in\mathcal{H}\) such that \[\label{eqn95defvi} \langle A(w^*),w-w^*\rangle+g(w)-g(w^*)\geq 0~\forall w\in \mathcal{H},\tag{1}\] where \(A:\mathcal{H}\to\mathcal{H}\) is the cost operator, and \(g:\mathcal{H}\to\mathbb{R}\cup\{+\infty\}\) is an extended real-valued function. We denote the set of solutions of (1 ) by \(S\). Mixed variational inequality problems (MVIPs) of the form (1 ) generalize various optimization problems encountered in nonlinear programming and variational analysis, including minimization problems, linear complementarity problems, and variational inequalities, see [1]–[4]. These problems have widespread applications in diverse fields, such as data science, image processing, mechanics, control theory, economics, structural engineering, and many more; see [1], [5]–[11], and the references therein.

Many algorithms solving the variational inequality (1 ) (for example; see [3], [12], [13]), need the exact value of the global Lipschitz constant of the cost operator \(A\). This assumption is often overly restrictive, as determining the Lipschitz constant of \(A\) can be more challenging than solving the original problem itself. Furthermore, even when the Lipschitz constant \(L\) is known, using a constant step size rule that inversely depends on \(L\) can be highly restrictive. In particular, when \(L\) is large, the step size \(\lambda\) is restricted to a very small value, which greatly limits the possible choices for \(\lambda\) and may slow down convergence for a given number of iterations. To overcome these issues, several researchers proposed step size sequences which do not require the value of Lipschitz constant, rather these algorithms approximate the local Lipschitz constant at each iterate. To generate such step size sequences the authors used backtracking procedures (see [14]–[18]). Although these methods address the aforementioned drawbacks, they can become costly in terms of overall run time due to the potentially large number of steps required for the backtracking procedure in each iteration.

To address this issue, Malitsky [19] proposed an adaptive strategy for step size selection. Subsequently, several authors adopted the adaptive step size technique to address the limitations of the backtracking procedure [20]–[22]. To build upon earlier methods, Hoai [23] recently proposed an algorithm to solve (1 ), in which the step size sequence increases after a finite number of iterations. One advantage of using an increasing step size is that it allows for adaptation when the initial step size is too small, particularly in cases where the Lipschitz constant is very large. If the step size begins at a low value, an increasing sequence can gradually adjust it over iterations, improving efficiency. This flexibility provides a key advantage over fixed or nonincreasing step size strategies.

Another approach to improve algorithms to solve (1 ) is to replace the Euclidean distance by other nonlinear distances such as Bregman distance. The usage of Bregman distance and Bregman proximal operators provides flexibility when deciding which projection to compute. For example, in convex-concave matrix games, the Bregman proximal operator appears as a projection onto the probability simplex, that has a straightforward closed form expression with regard to the Kullback-Leibler (KL) divergence but not with respect to the conventional Euclidean distance. For further advantages of the Bregman distance over the Euclidean distance, we refer the reader to [24]–[27]. The extant literature has several approaches for solving (1 ) with Bregman proximal operators [15], [28]–[36].

Most of these methods assume a Lipschitz condition without requiring the explicit value of the Lipschitz constant. Nevertheless, they often rely on a backtracking procedure. Recently, Tam and Uteda [27], studied the Bregman modifications of the Golden Ratio Algorithm, which iterates as follows.

This method does not require the backtracking procedure. However, to implement the algorithm, one needs to know the exact value of the global Lipschitz constant. To overcome this issue, in the same article [27], the authors proposed the Bregman adaptive Golden Ratio Algorithm (B-aGRAAL). Implementation of the B-aGRAAL algorithm requires neither backtracing nor the value of the Lipschitz constant.

Motivated by the work of Tam and Uteda [27], in this article, we propose a modification to the B-GRAAL algorithm. We study the B-GRAAL algorithm with a new step size rule. Our choice of step size sequence is motivated by the step size used by Hoai in [23]. This choice of step size sequence eliminates the need to know the value of global Lipschitz constant to implement the B-GRAAL algorithm. Furthermore, unlike previous approaches that utilize Bregman divergence to solve MVIP (1 ), our step size sequence increases after a finite number of iterations. We present a comprehensive convergence analysis of the proposed algorithm. Further, we establish the R linear rate of convergence of the algorithm. The numerical results given in Section 4 reveal that the proposed algorithm significantly improves the performance of the B-GRAAL algorithm.

This paper is structured as follows. Section 2 begins with the essential definitions and fundamental results as a foundation for the convergence analysis. Section 3 introduces the main results, including the proposed algorithm and its convergence analysis. Section 4 presents numerical results to illustrate the effectiveness of the proposed method.

2 Preliminaries↩︎

In this article, \(\mathcal{H}\) represents a real, finite-dimensional Hilbert space equipped with an inner product \(\langle \cdot, \cdot\rangle\) and the corresponding norm \(\lVert\cdot\rVert\). Given \(g:\mathcal{H}\rightarrow (-\infty, +\infty]\), domain of \(g\) is represented by \(\mathop{\mathrm{dom}}g:=\{x\in\mathcal{H}:g(x)<+\infty\}.\) The subdifferential of \(g\) at \(x\in\mathop{\mathrm{dom}}g\) is given by \[\partial g(x):=\{w\in\mathcal{H}:g(x)-g(y)-\langle w, x-y\rangle\leq 0~\forall y\in\mathcal{H}\}.\]

For \(h:\mathcal{H}\rightarrow (-\infty, +\infty]\), the Bregman distance with respect to \(h\) is the function \(B_{h}:\mathcal{H}\times \mathop{\mathrm{int}}\mathop{\mathrm{dom}}h\rightarrow (-\infty,+\infty]\) defined as \[B_{h}(x,y):=h(x)-h(y)-\langle\nabla h(y), x-y\rangle.\] For \(\alpha\)-strongly convex function \(h\), \(B_{h}\) satisfies \[B_{h}(x,y)\geq\frac{\alpha}{2}\lVert x-y\rVert^{2}~\forall (x,y)\in \mathcal{H}\times \mathop{\mathrm{int}}\mathop{\mathrm{dom}}h.\] The Bregman distance with respect to two different choices of \(h\) is given as follows [30], [37]. Let \(z=(z_1,z_2,\ldots,z_n)^\top\) and \(w=(w_1,w_2,\ldots,w_n)^\top\) be two points in \({\mathbb{R}}^n.\)

(i) The Kullback-Leibler distance is given as \[B^{KL}_h(z,w):=\sum\limits_{{i=1}}^n z_i\left(\log\left(\frac{z_i}{w_i}\right)-1\right)+\sum\limits_{i=1}^n w_i,\] which is induced by the function \(h(z)=\sum\limits_{i=1}^n z_i\log z_i\), with the domain \(\mathop{\mathrm{dom}}h^{KL}=\{z\in{\mathbb{R}}^n:z_i>0\}.\)

(ii) The squared Mahalanobis distance is given as \[B^{SM}_h(z,w)=\frac{1}{2}(z-w)^\top Q(z-w),\] which is induced by the function \(h^{SM}(z)=\frac{1}{2}z^\top Q z\), with \(\mathop{\mathrm{dom}}h^{SM}={\mathbb{R}}^n\), where \(Q=\text{diag}(1,2,\ldots,n).\)

In this work, we use the following properties of the Bregman distance.

The (left) Bregman proximal operator of a function \(f:\mathcal{H}\rightarrow (-\infty,\infty]\) is the operator given by \[{\mathop{\mathrm{{prox}}}}^h_f(y):=\mathop{\mathrm{argmin}}_{x\in\mathcal{H}}\{f(x)+B_{h}(x,y)\}~\forall y\in\mathop{\mathrm{int}}\mathop{\mathrm{dom}}h.\] Since this work exclusively requires the left Bregman proximal operator, we will henceforth refer to it simply as the Bregman proximal operator. Next, we state some properties of the Bregman proximal operator useful in our algorithm analysis.

3 The Modified Bregman-Golden Ratio Algorithm↩︎

In this section, we present the modified Bregman Golden Ratio algorithm and discuss its convergence. We take the following assumptions for our subsequent convergence analysis.

1. \(g:\mathcal{H}\rightarrow (-\infty, +\infty]\) is proper, convex, and lower semicontinuous.

2. \(h:\mathcal{H}\rightarrow (-\infty, +\infty]\) is continuously differentiable, Legendre, and \(\alpha\)-strongly convex. Further, we assume that for any sequence \((w_n)\subseteq \mathop{\mathrm{int}}\mathop{\mathrm{dom}}h\) converging to some \(w\in \mathop{\mathrm{dom}}h,\) \(B_{h}(w, w_n)\rightarrow 0\).

3. \(A:\mathcal{H}\rightarrow \mathcal{H}\) is monotone and \(L\)-Lipschitz continuous on \(\mathop{\mathrm{dom}}g \cap \mathop{\mathrm{int}}\mathop{\mathrm{dom}}h\neq\emptyset\).

4. \(\mathcal{S}:=S\cap\mathop{\mathrm{dom}}h\neq\emptyset\).

Let \(\phi:= \frac{\sqrt{5}+1}{2}\) represent the Golden Ratio that follows the identity \({\phi}^2=\phi +1.\) The proposed algorithm is formally outlined in Algorithm 2.

It is interesting to note that ([eqn95step952]) in Algorithm 2, can be equivalently written in the following forms [27]: \[\begin{align} w_{k+1} =& \mathop{\mathrm{{prox}}}^{h}_{\lambda_k f}(\bar{w}_k), ~\text{where}~f(w) = \langle A(w_k),w - w_k \rangle + g(w)\\=&\mathop{\mathrm{{prox}}}^{h}_{\lambda_k g} \left( (\nabla h)^{-1} (\nabla h(\bar{w}_k) - \lambda_k A(w_k)) \right). \end{align}\] By applying a proof analogous to that of Lemma 3.1 in [23], it can be established that the step size sequence \((\lambda_k)\) satisfies the following properties.

Next, we present two key lemmas that play a fundamental role in proving the convergence of the algorithm.

Proof We consider the following two possible cases.

1. \(\lVert A(w_k)-A(w_{k-1})\rVert>\frac{\eta_0\alpha}{\lambda_{k-1}}\lVert w_k-w_{k-1}\rVert.\)
   By using Cauchy-Schwarz inequality, relation ([eqn95roc952]), definition of \(\lambda_k\) and \(\alpha\)- strong convexity of \(h\), we get \[\begin{align} &\lambda_k\langle A(w_k)-A(w_{k-1}),w_k-w_{k+1}\rangle\\& \leq \lambda_k\lVert A(w_k)-A(w_{k-1})\rVert~ \lVert w_k-w_{k+1}\rVert\\&=\eta_1 \alpha\lVert w_k-w_{k-1}\rVert ~\lVert w_k-w_{k+1}\rVert\\&<\frac{\phi}{2}\alpha\lVert w_k-w_{k-1}\rVert~ \lVert w_k-w_{k+1}\rVert\\&\leq\frac{\phi}{2}\frac{\alpha}{2}\Big(\lVert w_k-w_{k-1}\rVert^2+\lVert w_k-w_{k+1}\rVert^2\Big)\\ &\leq\frac{\phi}{2}\Big(B_{h}(w_k,w_{k-1})+B_{h}(w_{k+1},w_k)\Big). \end{align}\]

2. \(\lVert A(w_k)-A(w_{k-1})\rVert\leq\frac{\eta_0\alpha}{\lambda_{k-1}}\lVert w_k-w_{k-1}\rVert\).
   By applying the Cauchy-Schwarz inequality, relation ([eqn95roc953]), Remark 2 and \(\alpha\)- strong convexity of \(h\), we obtain the following \(\forall k\geq\bar{k}\), \[\begin{align} &\lambda_k\langle A(w_k)-A(w_{k-1}),w_k-w_{k+1}\rangle\\&\leq \lambda_k\lVert A(w_k)-A(w_{k-1})\rVert~ \lVert w_k-w_{k+1}\rVert\\ &\leq \lambda_k\frac{\eta_0\alpha}{\lambda_{k-1}}\lVert w_k-w_{k-1}\rVert~\lVert w_k-w_{k+1}\rVert\\&=\eta_0(1+\gamma_{k-1})\alpha\lVert w_k-w_{k-1}\rVert~\lVert w_k-w_{k+1}\rVert\\& <\frac{\phi}{2}\frac{\alpha}{2}\Big(\lVert w_k-w_{k-1}\rVert^2+\lVert w_k-w_{k+1}\rVert^2\Big)\\&\leq\frac{\phi}{2}\Big(B_{h}(w_k,w_{k-1})+B_{h}(w_{k+1},w_k)\Big). \end{align}\]

Thus, from Case [lm95cs951] and Case [lm95cs952], we have \[\lambda_k\langle A(w_k)-A(w_{k-1}), w_k-w_{k+1}\rangle<\frac{\phi}{2}\Big(B_{h}(w_k,w_{k-1})+B_{h}(w_{k+1},w_k)\Big)~\forall k\geq \bar{k}.\]

Proof From ([eqn95step952]), we have \[\label{eqn95lmprf951} w_{k+1}=\mathop{\mathrm{argmin}}_{w\in \mathcal{H}}\left\{\langle A(w_k),w-w_k\rangle + g(w)+\frac{1}{\lambda_k}B_{h}(w,\bar{w}_k)\right\}.\tag{3}\] Equation (3 ) can be equivalently written in terms of Bregman proximal operator as follows: \[w_{k+1}=\mathop{\mathrm{{prox}}}^{h}_{\lambda_{k}f}(\bar{w}_k), \text{where}~f(w)=\langle A(w_k),w-w_k\rangle+g(w).\] By applying Proposition [prp952](2) with \(z:=w\in \mathop{\mathrm{dom}}h\cap\mathop{\mathrm{dom}}g\) arbitrary, \(x:=w_{k+1}\) and \(y:=\bar{w}_k\) followed by Proposition [prp951]([prp95195itm951]), we get \[\begin{align} &\lambda_k (\langle A(w_k), w_{k+1}-w\rangle + g(w_{k+1})-g(w))\nonumber\\&\leq\langle\nabla h(\bar{w}_k)-\nabla h(w_{k+1}), w_{k+1}-w\rangle\nonumber\\& =B_{h}(w,\bar{w}_k)-B_{h}(w,w_{k+1})-B_{h}(w_{k+1}, \bar{w}_k).\label{eqn95lmprf952} \end{align}\tag{4}\] By putting \(k=k-1,w=w_{k+1}\) in (4 ) and using \(\phi\nabla h(\bar{w}_k)=(\phi-1)\nabla h(w_k)+\nabla h(\bar{w}_{k-1})\) followed by Proposition [prp951]([prp95195itm951]), we get \[\begin{align} &\lambda_{k-1}(\langle A(w_{k-1}), w_k-w_{k+1}\rangle + g(w_k)-g(w_{k+1}))\nonumber \\&\leq \langle \nabla h(\bar{w}_{k-1})-\nabla h(w_k), w_k-w_{k+1}\rangle\nonumber\\&=\phi\langle\nabla h(\bar{w}_k)-\nabla h(w_k), w_k-w_{k+1}\rangle\nonumber\\&=\phi\Big(B_{h}(w_{k+1},\bar{w}_k)-B_{h}(w_{k+1},w_k)-B_{h}(w_k,\bar{w}_k)\Big).\label{eqn95lmprf953} \end{align}\tag{5}\] On multiplying both sides of (5 ) by \(\frac{\lambda_k}{\lambda_{k-1}}\), we get \[\begin{align} &\lambda_k(\langle A(w_{k-1}),w_k-w_{k+1}\rangle +g(w_k)-g(w_{k+1}))\nonumber\\&\leq \frac{\lambda_k}{\lambda_{k-1}}\phi\Big(B_h(w_{k+1},\bar{w}_k)-B_h(w_{k+1},w_k)-B_h(w_k,\bar{w}_k)\Big).\label{eqn95mp95new951} \end{align}\tag{6}\] By Lemma [mm95lm](2), there exists \(k_1\in\mathbb{N}\) such that for all \(k\geq k_1\) \[\lambda_k=(1+\gamma_{k-1})\lambda_{k-1}.\] Also, since \(\displaystyle\sum_{k=0}^\infty \gamma_k < +\infty\), there exists \(k_2\in\mathbb{N}\) such that \[\gamma_{k-1}\leq \frac{1}{2\phi^2}~\forall k\geq k_2.\] Therefore, by taking \(k''=\max\{k_1,k_2\}\), we get \[\frac{\lambda_k}{\lambda_{k-1}}\phi\leq \left(\phi+\frac{1}{2\phi}\right)~\forall k\geq k''.\] Thus, we can rewrite (6 ) as \[\begin{align} &\lambda_k(\langle A(w_{k-1}),w_k-w_{k+1}\rangle +g(w_k)-g(w_{k+1}))\nonumber\\&\leq \left(\phi + \frac{1}{2\phi}\right)\Big(B_h(w_{k+1},\bar{w}_k)-B_h(w_{k+1},w_k)-B_h(w_k,\bar{w}_k)\Big)~\forall k\geq k''.\label{eqn95mp95new952} \end{align}\tag{7}\] Let \(w^{*}\in \mathcal{S}\). By setting \(w=w^*\) in (4 ) and summing with (7 ), and then rearranging yields \[\begin{align} &\lambda_k(\langle A(w_k),w_{k}-w^*\rangle +g(w_{k})-g(w^*))\nonumber\\ &\leq B_h(w^*,\bar{w}_k)-B_h(w^*,w_{k+1})-B_h(w_{k+1},\bar{w}_k)\nonumber\\&~~~~+\left(\phi + \frac{1}{2\phi}\right)\Big(B_h(w_{k+1},\bar{w}_k)-B_h(w_{k+1},w_k)-B_h(w_k,\bar{w}_k)\Big)\nonumber\\&~~~~+\lambda_k\langle A(w_k)-A(w_{k-1}),w_k-w_{k+1}\rangle~\forall k\geq k''\label{eqn95mp95new953}. \end{align}\tag{8}\] By (1 ) and the monotonicity of \(A\), we get \[\label{eqn95lmprf955} \begin{align} 0&\leq \langle A(w^*),w_k-w^*\rangle+g(w_k)-g(w^*)\leq \langle A(w_k),w_k-w^*\rangle + g(w_k)-g(w^*). \end{align}\tag{9}\] Combining (8 ) and (9 ) followed by Lemma 3, we get \[\begin{align} B_h(w^*,w_{k+1})&\leq B_h(w^*,\bar{w}_k)+\left(\phi+\frac{1}{2\phi}-1\right)B_h(w_{k+1},\bar{w}_k)\nonumber\\&~~~-\left(\phi+\frac{1}{2\phi}\right)B_h(w_k,\bar{w}_k)-\left(\frac{\phi}{2}+\frac{1}{2\phi}\right)B_h(w_{k+1},w_k)\nonumber\\&~~~+\frac{\phi}{2}B_h(w_k,w_{k-1})~\forall k\geq k':=\max\{\bar{k},k''\}.\label{eqn95mp95new954} \end{align}\tag{10}\] From ([eqn95stp2951]), we have \[\nabla h(w_{k+1})=\frac{\phi}{\phi-1}\nabla h(\bar{w}_{k+1})-\frac{1}{\phi-1}\nabla h(\bar{w}_k)=(\phi+1)\nabla h(\bar{w}_{k+1})-\phi\nabla h(\bar{w}_k).\] Now, by applying Proposition [prp951](1), we get \[\label{eqn95lmprf95895new} \begin{align} (\phi +1)B_{h}(w^*,\bar{w}_{k+1})&=B_{h}(w^*,w_{k+1})+(\phi +1)B_{h}(w_{k+1},\bar{w}_{k+1})\\&~~~+\phi\Big(B_{h}(w^*,\bar{w}_k)-B_{h}(w_{k+1},\bar{w}_k)\Big). \end{align}\tag{11}\] On combining (10 ) and (11 ), the following is true for all \(k\geq k'\) \[\begin{align} &(\phi +1)B_h(w^*,\bar{w}_{k+1})+\frac{\phi}{2}B_h(w_{k+1},w_k)-\phi B_h(w_{k+1},\bar{w}_{k+1})\nonumber\\&\leq (\phi +1)B_h(w^*,\bar{w}_k)+\frac{\phi}{2}B_h(w_k,w_{k-1})-\phi B_h(w_k,\bar{w}_k)+B_h(w_{k+1},\bar{w}_{k+1})\nonumber\\&~~~~+\left(\frac{1}{2\phi}-1\right)B_h(w_{k+1},\bar{w}_k).\label{eqn95mp95new955} \end{align}\tag{12}\] From ([eqn95stp2951]), \(\nabla h(\bar{w}_{k+1})=\frac{\phi-1}{\phi}\nabla h(w_{k+1})+\frac{1}{\phi}\nabla h(\bar{w}_k)\). Proposition [prp951](1) gives \[\begin{align} B_{h}(w_{k+1},\bar{w}_{k+1})&=\frac{\phi-1}{\phi}\Big(B_{h}(w_{k+1},w_{k+1})-B_{h}(\bar{w}_{k+1},w_{k+1})\Big)\nonumber\\&~~~+\frac{1}{\phi}\Big(B_{h}(w_{k+1},\bar{w}_k)-B_{h}(\bar{w}_{k+1},\bar{w}_k)\Big)\nonumber\\&\leq\frac{1}{\phi} B_{h}(w_{k+1},\bar{w}_k). \label{eqn95lmprf9510} \end{align}\tag{13}\] On combining (12 ) and (13 ), we get the second inequality in (2 ).
Next, we show the first inequality in (2 ). Applying Proposition [prp951]([prp95195itm951]) with \(w=w^*, x=\bar{w}_{k+1}, y=w_{k+1}\), followed by (4 ), we get \[\begin{align} &B_{h}(w^*,w_{k+1})+B_{h}(w_{k+1},\bar{w}_{k+1})\nonumber\\&=B_{h}(w^*,\bar{w}_{k+1})+\langle\nabla h(\bar{w}_{k+1})-\nabla h(w_{k+1}),w^*-w_{k+1}\rangle\nonumber\\&=B_{h}(w^*,\bar{w}_{k+1})+\frac{1}{\phi}\langle\nabla h(\bar{w}_k)-\nabla h(w_{k+1}),w^*-w_{k+1}\rangle\nonumber\\&\leq B_{h}(w^*,\bar{w}_{k+1})+\frac{\lambda_k}{\phi}\Big(\langle A(w_k),w^*-w_{k+1}\rangle-g(w_{k+1})+g(w^*)\Big)\nonumber\\&=B_{h}(w^*,\bar{w}_{k+1})+\frac{\lambda_k}{\phi}\langle A(w_k)-A(w_{k+1}),w^*-w_{k+1}\rangle\nonumber\\&~~~~+\frac{\lambda_k}{\phi}\Big(\langle A(w_{k+1}),w^*-w_{k+1}\rangle-g(w_{k+1})+g(w^*)\Big)\nonumber\\&\leq B_{h}(w^*,\bar{w}_{k+1})+\frac{\lambda_k}{\phi}\langle A(w_k)-A(w_{k+1}),w^*-w_{k+1}\rangle.\label{eqn95lmprf9511} \end{align}\tag{14}\] By Cauchy-Schwarz inequality, Lemma [mm95lm](2), and \(\alpha\)-strong convexity of \(h\), it follows that for all \(k\geq k_1\), \[\label{eqn95lmprf9512} \begin{align} &\frac{\lambda_k}{\phi}\langle A(w_k)-A(w_{k+1}),w^*-w_{k+1}\rangle\\&\leq \frac{\lambda_k}{\phi}\lVert A(w_k)-A(w_{k+1})\rVert~\lVert w^*-w_{k+1}\rVert\\&\leq \frac{\lambda_{k}}{\phi}\frac{\eta_0\alpha}{\lambda_k}\lVert w_{k+1}-w_k\rVert~\lVert w^*-w_{k+1}\rVert\\&\leq\frac{1}{2}\frac{\alpha}{2}\Big(\lVert w_{k+1}-w_k\rVert^{2}+\lVert w^*-w_{k+1}\rVert^{2}\Big)\\&\leq \frac{1}{2}\Big(B_{h}(w_{k+1},w_k)+B_{h}(w^*,w_{k+1})\Big). \end{align}\tag{15}\] From (14 ) and (15 ), for all \(k\geq k'\), the following inequality holds \[\label{eqn95roc958} \begin{align} B_{h}(w_{k+1},\bar{w}_{k+1})&\leq B_{h}(w^*,\bar{w}_{k+1})+\frac{1}{2}B_{h}(w_{k+1},w_k)-\frac{1}{2}B_{h}(w^*,w_{k+1})\\&\leq B_{h}(w^*,\bar{w}_{k+1})+\frac{1}{2}B_{h}(w_{k+1},w_k), \end{align}\tag{16}\] and thus for all \(k \geq k'\), we get \[\begin{align} 0\leq&~B_{h}(w^*,\bar{w}_{k+1})+\frac{1}{2}B_{h}(w_{k+1},w_k)-B_{h}(w_{k+1},\bar{w}_{k+1})\\\implies 0 \leq&~ (\phi+1)B_{h}(w^*,\bar{w}_{k+1})+\frac{\phi}{2}B_{h}(w_{k+1},w_k)-\phi B_{h}(w_{k+1},\bar{w}_{k+1}), \end{align}\] which is the first inequality of (2 ), and thus the proof is complete. 0◻

Proof Let \(w^*\in\mathcal{S}\) be arbitrary and let \((\mu_k)\) denote the sequence given by \[\label{eqn95roc956} \mu_k:=(\phi +1)B_{h}(w^*,\bar{w}_k)+\frac{\phi}{2}B_{h}(w_k,w_{k-1})-\phi B_{h}(w_k,\bar{w}_k)~\forall k\in\mathbb{N}.\tag{17}\] From Lemma 4, it is evident that there exists \(k'\in\mathbb{N}\) such that the following is true for all \(k\geq k'\) \[0\leq \mu_{k+1}\leq\mu_k -\left(1-\frac{3}{2\phi}\right)B_h(w_{k+1},\bar{w}_k).\] Therefore, by Lemma 1, it follows that \(\lim_{k\rightarrow\infty}\mu_k\) exists and \(B_{h}(w_{k+1},\bar{w}_k)\rightarrow 0\) as \(k\rightarrow\infty.\) Then, (13 ) implies that \(B_{h}(w_{k+1},\bar{w}_{k+1})\rightarrow 0\). Also, by Proposition [prp951](1) with \(\nabla h(w_k)=(\phi +1)\nabla h(\bar{w}_k)-\phi\nabla h(\bar{w}_{k-1})\), we get \[\begin{align} B_{h}(w_{k+1},w_k)&=(\phi +1)\Big(B_{h}(w_{k+1}, \bar{w}_k)-B_{h}(w_k,\bar{w}_k)\Big)-\phi \Big(B_{h}(w_{k+1},\bar{w}_{k-1})\\&~~~-B_{h}(w_k,\bar{w}_{k-1})\Big)\\&\leq (\phi +1)B_{h}(w_{k+1},\bar{w}_k)+\phi B_{h}(w_k,\bar{w}_{k-1})\rightarrow 0. \end{align}\] Thus, we get \[\lim_{k\rightarrow\infty}\mu_k=(\phi +1)\lim_{k\rightarrow \infty}B_{h}(w^*,\bar{w}_k),\] and, in particular, \(\lim_{k\rightarrow\infty}B_{h}(w^*,\bar{w}_k)\) exists.
Using \(\alpha\)-strong convexity of \(h\), we conclude that \(w_{k+1}-\bar{w}_k\rightarrow 0\) and that \((w_k)\) and \((\bar{w}_k)\) are bounded. Thus, let \(\bar{w}\in \mathcal{H}\) be a cluster point of \((\bar{w}_k)\). Then, there exists a subsequence \((\bar{w}_{{k}_{j}})\) such that \(\bar{w}_{{k}_{j}}\rightarrow \bar{w}\) and \(w_{k_{j}+1}\rightarrow\bar{w}\) as \(j\rightarrow\infty\). Referring back to (4 ), for all \(w\in \mathcal{H}\), we obtain \[\begin{gather} \lambda_k(\langle A(w_{{k}_{j}}), w_{k_{j}+1}-w\rangle+ g(w_{k_{j}+1})-g(w))\\\leq \langle\nabla h(\bar{w}_{{k}_{j}})-\nabla h(w_{k_{j}+1}), w_{k_{j}+1}-w\rangle, \end{gather}\] and taking the limit infimum on both sides as \(j\rightarrow \infty\) shows that \(\bar{w}\in\mathcal{S}\). Since \(w^*\in\mathcal{S}\) in Lemma 4 was arbitrary, we now set \(w^*=\bar{w}\). This implies that \(\lim_{j\rightarrow\infty}B_{h}(w^*,\bar{w}_{{k}_{j}})=0\), leading to \(\lim_{j\rightarrow\infty}\mu_{{k}_{j}}=0\). Also, from Lemma 4, for \(n\geq k_j\), we have \(\mu_{n}\leq\mu_{{k}_{j}}\), and thus, \[(\phi+1)\lim_{n\rightarrow\infty}B_{h}(w^*,\bar{w}_n)=\lim_{n\rightarrow\infty}\mu_n\leq\lim_{j\rightarrow\infty}\mu_{{k}_{j}}=0,\] and thus \(\bar{w}_k\rightarrow w^*\) from strong convexity of \(h\). The convergence \(w_k\rightarrow w^*\) follows from the fact that \(w_k-\bar{w}_k\rightarrow 0.\) 0◻

3.1 Linear Convergence of Modified B-GRAAL↩︎

We next establish the R-linear convergence rate of Algorithm 2. For this, we assume that for some \(\sigma>0\), \[\label{eqn95roc951} \langle A(z)-A(w),z-w\rangle\geq \sigma B_h(z,w)~\forall (z,w)\in\mathop{\mathrm{dom}}h\times \mathop{\mathrm{int}}\mathop{\mathrm{dom}}h.\tag{18}\] Observe that when \(h=\frac{1}{2}\lVert .\rVert^2\), (18 ) simplifies to the standard definition of \(\sigma\)-strong monotonicity.

Proof  Without loss of generality, we assume that \(\sigma<\frac{1}{2}\). Also, in the definition of \(\lambda_k\) by multiplying right hand sides of ([eqn95roc952]) and ([eqn95roc953]) by \(\sqrt{1-\sigma}\), and by replacing these updated values of \(\lambda_k\) in the proof of Lemma 3, we get the following updated bound. \[\begin{align} \label{eqn95roc954} &\lambda_k\langle A(w_k)-A(w_{k-1}), w_k-w_{k+1}\rangle\nonumber\\&\leq \frac{\phi}{2}(1-\sigma)B_h(w_k,w_{k-1})+\frac{\phi}{2}B_h(w_{k+1},w_k)~\forall k\geq \bar{k}. \end{align}\tag{19}\] Let \(w^*\in\mathcal{S}\). Since (18 ) holds, we get \[\begin{align} \label{eqnn} 0&\leq \langle A(w^*), w_k-w^*\rangle + g(w_k)-g(w^*)\nonumber\\&\leq \langle A(w_k),w_k-w^*\rangle+g(w_k)-g(w^*)-\sigma B_h(w^*,w_k). \end{align}\tag{20}\] Following a similar approach to the proof of Lemma 4, with (20 ) replacing (9 ) and (19 ) replacing Lemma 3, the corresponding form of (10 ) becomes \[\begin{align} \label{eqn95roc957} &B_h(w^*,w_{k+1})\leq B_h(w^*,\bar{w}_k)+(\phi-1)B_h(w_{k+1},\bar{w}_k)-\phi B_h(w_k,\bar{w}_k)\nonumber\\&-\sigma B_h(w^*,w_k) -\frac{\phi}{2}B_h(w_{k+1},w_k)+\frac{(1-\sigma)\phi}{2}B_h(w_k,w_{k-1})~\forall k\geq k'. \end{align}\tag{21}\] Proposition [prp951](1) with \(\nabla h(w_{k+1})=(\phi+1)\nabla h(\bar{w}_{k+1})-\phi\nabla h(\bar{w}_k)\) gives \[\label{eqn95roc955} \begin{align} B_h(w^*,w_{k+1})=&(\phi+1)\Big(B_h(w^*,\bar{w}_{k+1})-B_h(w_{k+1},\bar{w}_{k+1})\Big)\\&-\phi\Big(B_h(w^*,\bar{w}_k)-B_h(w_{k+1},\bar{w}_k)\Big). \end{align}\tag{22}\] Let \(\mu_k\) represent the sequence defined by (17 ). Then, applying (22 ) to substitute \(B_h(w^*,w_{k+1})\) and \(B_h(w^*,w_{k})\) in (21 ), and subsequently using (13 ), we get the following for all \(k\geq k'\), \[\begin{align} \mu'_{k+1}:=&~(\phi+1)B_h(w^*,\bar{w}_{k+1})+\frac{\phi}{2}B_h(w_{k+1},w_k)-B_h(w_{k+1},\bar{w}_{k+1})\\\leq&~ (1-\sigma)(\phi+1)B_h(w^*,\bar{w}_k)+\frac{(1-\sigma)\phi}{2}B_h(w_k,w_{k-1})+\\&~(\sigma(1+\phi)-\phi)B_h(w_k,\bar{w}_k)+\sigma\phi B_h(w^*,\bar{w}_{k-1})-\sigma\phi B_h(w_k,\bar{w}_{k-1})\\&~+\phi B_h(w_{k+1},\bar{w}_{k+1})+\left(\frac{1}{2\phi}-1\right)B_h(w_{k+1},\bar{w}_k)\\\leq&~ (1-\sigma)\mu_k+\sigma\phi B_h(w^*,\bar{w}_{k-1}). \end{align}\] Since \((\mu_k)\) is non increasing by Lemma 4 and \(\frac{(1-\sigma)\phi}{1-\sigma(2-\phi)}\geq 1\), we get \[\begin{align} \mu'_{k+1}\leq&~(1-\sigma)\mu_{k-1}+\sigma(\phi-1)(\phi+1)B_h(w^*,\bar{w}_{k-1})\\=&~(1-\sigma(2-\phi))(\phi+1)B_h(w^*,\bar{w}_{k-1})+(1-\sigma)\frac{\phi}{2}B_h(w_{k-1},w_{k-2})\\&-(1-\sigma)\phi B_h(w_{k-1},\bar{w}_{k-1})\\\leq&~ (1-\sigma(2-\phi))\Big((\phi +1)B_h(w^*,\bar{w}_{k-1})+\frac{\phi}{2}B_h(w_{k-1},w_{k-2})\\&~-B_h(w_{k-1},\bar{w}_{k-1})\Big)\\=&~q\mu'_{k-1},~\text{where}~q=(1-\sigma(2-\phi))\in(0,1). \end{align}\] Therefore, \(\mu'_k\) converges Q-linearly to \(0\). By (16 ) and \(\alpha\)-strong convexity of \(h\), it follows that \[\begin{align} \mu'_{k+1}=&~\phi B_h(w^*,\bar{w}_{k+1})+\frac{\phi-1}{2}B_h(w_{k+1},w_k)\\&+\left(B_h(w^*,\bar{w}_{k+1})+\frac{1}{2}B_h(w_{k+1},w_k)-B_h(w_{k+1},\bar{w}_{k+1})\right)\\\geq&~\frac{\alpha\phi}{2}\lVert w^*-\bar{w}_{k+1}\rVert^2+\frac{\alpha(\phi-1)}{4}\lVert w_{k+1}-w_k\rVert^2. \end{align}\] This shows that \(\bar{w}_k\) converges to \(w^*\) with R-linear convergence, and the difference \(\lVert w_{k+1} - w_k \rVert\) also converges to zero at the same rate. As a result, the sequence \((w_k)\) exhibits R-linear convergence to \(w^*\). Since the choice of \(w^*\) from the set \(\mathcal{S}\) was arbitrary, \(w^*\) is unique. 0◻

4 Numerical Results↩︎

In this section, we compare our Algorithm 2 with B-GRAAL [27], and B-aGRAAL [27]. Specifically, in Section 4.1, we present the comparison results for matrix game problem. In Section 4.2, we compare the algorithms in the context of the the sparse logistic regression problem. We run all the experiments in Python 3 on a Macbook Air with M1 chip and 8GB RAM.

Both the considered problems can be formulated as MVIP (1 ) for different choices of the operator \(A\) and the function \(g\). Note that the solution of MVIP (1 ) can also be formulated as the monotone inclusion: find \(w^*\in\mathcal{H}\) such that \[0\in A(w^*)+\partial g(w^*).\] Thus, by ([eqn95step952]), we get \[0\in A(w_k)+\partial g(w_{k+1})+\frac{1}{\lambda_k}(\nabla h(w_{k+1})-\nabla h(\bar{w}_k)),\] and we track the quantity \(J_k\) defined as \[\begin{gather} J_k:=\frac{1}{\lambda_k}(\nabla h(\bar{w}_k)-\nabla h(w_{k+1}))+A(w_{k+1})-A(w_k)\in A(w_{k+1})+\partial g(w_{k+1}). \end{gather}\] as a natural residual for Algorithm 2. The parameters used for the execution of each algorithm are as follows.

1. B-GRAAL: \(\phi= \frac{\sqrt{5}+1}{2}, \lambda= \frac{\phi}{2L}.\)

2. B-aGRAAL: \(\varphi=1.5\), \(\lambda_0=\frac{\varphi}{2}\frac{\lVert w_1-w_0 \rVert}{\lVert A(w_1)-A(w_0)\rVert}\), \(\rho= \frac{1}{\phi}+\frac{1}{{\phi}^2}\), \(\lambda_{\max}=10^6.\)

3. Algorithm 2: \(\eta_1=0.75, \eta_0=0.80, \lambda_0=\frac{\phi}{2}\frac{\lVert w_1-w_0 \rVert}{\lVert A(w_1)-A(w_0)\rVert}\), and the sequence of positive terms \(\gamma_{k}=\frac{r(\log (k+1))^s}{(k+1)^t}, r, s>0; t>1~\forall k\geq 1.\)

4.1 Matrix Games↩︎

In this instance, we examine the following matrix game: \[\label{eqn95app3951} \min_{x\in\triangle ^k}\max_{y\in\triangle^k}\langle Px, y\rangle,\tag{23}\] where \(\triangle^k:= \left\{x\in {\mathbb{R}}^{k}_+: \sum_{i=1}^k x_i=1\right\}\) denotes the unit simplex and \(P\in {\mathbb{R}}^{k\times k}\) is a given matrix. Note that (23 ) can be formulated as a MVIP (1 ). Specifically, we examine the problem in the form (23 ), which involves positioning a server within a network \(G = (U, E)\) consisting of \(k\) vertices, with the objective of minimizing its response time. In this scenario, a request arises from an unknown vertex \(u_j \in U\), and the goal is to position the server at a vertex \(u_i \in U\) in a manner that minimizes the response time, which is determined by the graphical distance \(d(u_i, u_j)\). We analyze the scenario where the request location \(u_j \in U\) is strategically determined by an adversary. The decision variable \(x \in \triangle^k\) (similarly, \(y \in \triangle^k\)) represents mixed strategies for server placement (and request origin, respectively). More precisely, \(x_t\) (respectively, \(y_t\)) denotes the probability of the server (or request origin) being positioned at node \(u_t\) for \(t = 1, 2, \ldots, k\). The matrix \(P\) is defined as the distance matrix of the graph \(G\), where each entry is given by \(P_{ij} = d(u_i, u_j)\) for all vertices \(( u_i, u_j) \in U\). Consequently, the objective function in (23 ) quantifies the expected response time, which we aim to minimize, while the adversary attempts to maximize it.

We conducted three experiments with \(k = 10\), \(k= 20\) and \(k = 100\), with the corresponding results presented in Figs. 3, 4, and 5. The initial points are selected as \(x_0 = y_0 = \left(\frac{1}{k}, \frac{1}{k}, \dots, \frac{1}{k}\right) \in \triangle^k\), with \(w_0 = (x_0, y_0)\). Subsequently, \(w_1\) is set as a randomly perturbed version of \(w_0\). Lipschitz constant of \(A\) is calculated as \(L=\lVert P \rVert_2\) and \(r=0.0007, s=7.5, t=1.1\).

4.2 Sparse Logistic Regression↩︎

In this problem, we are interested to find \(x\in\mathbb{R}^n\) such that the following loss function is minimized \[k(x)=\displaystyle\sum_{i=1}^M \log(1+\exp(-c_i\langle d_i,x\rangle))+\bar{\beta}\lVert x\rVert_1,\] where \(d^i\in{\mathbb{R}}^n, c_i\in\{-1,1\}, i=1,2,\ldots, M\) are observations; and \(\bar{\beta}>0\) is a regularization parameter. It can be seen that (for details, see [23]) the problem \(\min_{x\in{\mathbb{R}}^n} k(x)\) can be formulated as problem (1 ) with \[A(x)=\nabla h(x);~ h(x)=\displaystyle\sum_{i=1}^M \log(1+\exp(-c_i\langle d_i,x\rangle)); ~g(x)=\bar{\beta}\lVert x\rVert_1.\] The tested datasets are sourced from the LIBSVM¹ library, including ijcnn1.bz2, a9a, and duke.bz2. We choose \(w_0=zeros(n), w_1=w_0+10^{-9}random(n),\\ \bar{\beta}=0.005\lVert C^{T}c\rVert_{\infty}(C~\text{composed by}~d^i, i=1,2,\ldots,M, c=(c_i)_{i=1}^N)\) for all algorithms. For the datasets ijcnn1 and a9a, we take \(r=0.0001, s=7.2,\) and \(t=1.01\). For duke.bz2, \(r=0.0005, s=7\) and \(t=1.1\). The numerical results for the datasets ijcnn1.bz2, a9a, and duke.bz2 are presented in Figs. 6, 7, and 8, respectively.

5 Conclusion↩︎

In this article, we explored a modification of the B-GRAAL algorithm to solve mixed variational inequality problems. Under standard assumptions, we established the R-linear convergence of the modified algorithm. Unlike the B-GRAAL algorithm, the implementation of the modified algorithm does not require knowledge of the Lipschitz constant \(L\) and the numerical experiments on the sparse logistic regression problem and the matrix game problem demonstrate that this modification significantly enhances the performance of the B-GRAAL algorithm.

Acknowledgements↩︎

The authors wishes to thank Dr. P.T. Hoai and Dr. D. Uteda for sharing Python codes of their papers [23] and [27], respectively. This helped the authors to write the Python codes for this paper.

References↩︎