Convergence rate analysis of the gradient descent–ascent method for convex–concave saddle-point problems

Abstract

In this paper, we study the gradient descent–ascent method for convex–concave saddle-point problems. We derive a new non-asymptotic global convergence rate in terms of distance to the solution set by using the semidefinite programming performance estimation method. The given convergence rate incorporates most parameters of the problem and it is exact for a large class of strongly convex-strongly concave saddle-point problems for one iteration. We also investigate the algorithm without strong convexity and we provide some necessary and sufficient conditions under which the gradient descent–ascent enjoys linear convergence.

Keywords:

• Saddle-point problems
• minimax optimization problem
• gradient descent–ascent method
• convergence rate
• performance estimation
• semidefinite programming

Mathematic Subject Classifications:

• 90C25
• 90C47
• 65K10

1. Introduction

We consider the convex–concave saddle point problem (1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) where $F:{\mathbb{R}}^n\times {\mathbb{R}}^m\to (-\mathrm{\infty },\mathrm{\infty })$, and $F(\cdot ,y)$ and $F(x,\cdot )$ are convex and concave, respectively, for any fixed $x\in {\mathbb{R}}^n$ and $y\in {\mathbb{R}}^m$. We assume that problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) has some solution, that is, there exists a saddle point $(x^{\star },y^{\star })\in {\mathbb{R}}^n\times {\mathbb{R}}^m$ with $F(x^{\star },y)\le F(x^{\star },y^{\star })\le F(x,y^{\star }),\mathrm{\forall }x\in {\mathbb{R}}^n,\mathrm{\forall }y\in {\mathbb{R}}^m.$We denote the solution set of problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) with $S^{\star }$. We call F smooth if for some $L_x,L_y,L_{\mathrm{xy}}$, we have $\begin{array}{rl}(\mathrm{i})& \Vert {\mathrm{\nabla }}_{x}F(x_2,y)-{\mathrm{\nabla }}_{x}F(x_1,y)\Vert \le L_x\Vert x_2-x_1\Vert \mathrm{\forall }{x}_1,x_2,y\\ (\mathrm{ii})& \Vert {\mathrm{\nabla }}_{y}F(x,y_2)-{\mathrm{\nabla }}_{y}F(x,y_1)\Vert \le L_y\Vert y_2-y_1\Vert \mathrm{\forall }x,y_1,y_2\\ (\mathrm{iii})& \Vert {\mathrm{\nabla }}_{x}F(x,y_2)-{\mathrm{\nabla }}_{x}F(x,y_1)\Vert \le L_{\mathrm{xy}}\Vert y_2-y_1\Vert \mathrm{\forall }x,y_1,y_2\\ (\mathrm{iv})& \Vert {\mathrm{\nabla }}_{y}F(x_2,y)-{\mathrm{\nabla }}_{y}F(x_1,y)\Vert \le L_{\mathrm{xy}}\Vert x_2-x_1\Vert \mathrm{\forall }{x}_1,x_2,y.\end{array}$The function F is said to be strongly convex-strongly concave if $\begin{array}{rl}(\mathrm{i})& F(\cdot ,y)-\frac{{\mu }_x}{2}\Vert \cdot {\Vert }^2\mathrm{is}\mathrm{convex}\mathrm{for}\mathrm{any}\mathrm{fixed}y\\ (\mathrm{ii})& F(x,\cdot )+\frac{{\mu }_y}{2}\Vert \cdot {\Vert }^2\mathrm{is}\mathrm{concave}\mathrm{for}\mathrm{any}\mathrm{fixed}x,\end{array}$for some ${\mu }_x,{\mu }_y>0$. Note that strong convex-strong concavity implies that problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) has a unique solution $(x^{\star },y^{\star })$. We denote the set of smooth strongly convex-strongly concave functions by $\mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$.

Problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) has applications in game theory [4], robust optimization [5], adversarial training [14], and reinforcement learning [30], to name but a few. In addition, various other algorithms have been developed for solving saddle point problems; see e.g. [15,16,18,25,26,28,29].

One of the simplest approaches for handling problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) introduced in [2, Chapter 6] is the gradient-descent–ascent method, which may be regarded as a generalization of the gradient method for saddle point problems. The gradient descent–ascent method is described in Algorithm 1.

The local and global linear convergence of Algorithm 1 have been investigated in the literature; see [3,13,17,33] and the references therein. As we investigate the global linear convergence rate of Algorithm 1, we mention one known global convergence result, which is derived by using variational inequality techniques. Suppose that $z=(x,y)$. Let the function $\varphi :{\mathbb{R}}^{n+m}\to {\mathbb{R}}^{n+m}$ given by $\varphi (z)=({\mathrm{\nabla }}_{x}F(z)-{\mathrm{\nabla }}_{y}F(z){)}^T$. It is shown that, see e.g. [22], $\begin{array}{rl}& \Vert \varphi (\overline{z})-\varphi (\hat{z})\Vert \le 2L\Vert \overline{z}-\hat{z}\Vert ,\\ & ⟨\varphi (\overline{z})-\varphi (\hat{z}),\overline{z}-\hat{z}⟩\ge \mu \Vert \overline{z}-\hat{z}{\Vert }^2,\end{array}$where $L=max\{L_x,L_y,L_{\mathrm{xy}}\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}$. Indeed, ϕ is Lipschitz continuous and strongly monotone. By Facchinei and Pang [12, Theorem 12.1.2], for $t\in (0,\frac{\mu }{2L^2})$, we have (2) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le (1+4L^2{t}^2-2\mathrm{\mu t})(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$(2) In this study, we revisit Algorithm 1 and improve the convergence rate (2(2) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le (1+4L^2{t}^2-2\mathrm{\mu t})(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$(2) ). Indeed, we derive a new convergence rate involving most parameters of problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ). It is worth noting that if one sets $L=max\{L_x,L_y,L_{\mathrm{xy}}\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}$, the new bound dominates the convergence rate (2(2) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le (1+4L^2{t}^2-2\mathrm{\mu t})(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$(2) ) for any step length $t\in (0,\frac{\mu }{2L^2})$. Furthermore, by setting $t=\frac{\mu }{4L^2}$, one can infer that Algorithm 1 has a complexity of $\mathcal{O}(\frac{L^2}{{\mu }^2}\ln (\frac{1}{ϵ}))$ to compute iterates $(x^k,y^k)$ such that $\Vert x^k-x^{\star }{\Vert }^2+\Vert y^k-y^{\star }{\Vert }^2\le ϵ(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2)$, which is the known iteration complexity bound in the literature; see e.g. [6,32]. In this study, thanks to the new convergence rate given in Theorem 2.2, the order of complexity of $\mathcal{O}((\frac{L}{\mu }+\frac{L_{\mathrm{xy}}^2}{{\mu }^2})\ln (\frac{1}{ϵ}))$ is obtained when $L=max\{L_x,L_y\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}$, which is more informative in comparison with the above-mentioned one. Moreover, by providing some example, we show that the given convergence rate is exact for one iteration.

The goal of this work is not to achieve the optimal algorithmic complexity for the class of saddle point problems introduced above. Rather, we have the more modest goal of giving the best possible worst-case complexity analysis of the gradient descent–ascent method (Algorithm 1). It is important to note that there are accelerated and extra gradient descent–ascent methods with better worst-case complexity than Algorithm 1; see e.g. [18,28]. In particular, the accelerated methods may be shown to have a worst-case complexity $\mathcal{O}(\sqrt{\frac{L_x^2}{{\mu }_x^2}+\frac{L_{\mathrm{xy}}^2}{{\mu }_x{\mu }_y}+\frac{L_y^2}{{\mu }_y^2}}\cdot \ln (\frac{1}{ϵ}))$, which may be compared to the best-known lower complexity bound $\mathcal{O}(\sqrt{\frac{L_x}{{\mu }_x}+\frac{L_{\mathrm{xy}}^2}{{\mu }_x{\mu }_y}+\frac{L_y}{{\mu }_y}}\cdot \ln (\frac{1}{ϵ}))$ for the class of pure first-order algorithms [34].

The paper is organized as follows. First, we present basic definitions and preliminaries used to establish the results. Section 2 is devoted to the study of the linear convergence of Algorithm 1. In Section 3, we study the linear convergence of the gradient descent–ascent method without strong convexity. Indeed, we let $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},0,0)$ and give some necessary and sufficient conditions for the linear convergence. Moreover, we derive a convergence rate under this setting.

Notation 1

The n-dimensional Euclidean space is denoted by ${\mathbb{R}}^n$. We use $⟨\cdot ,\cdot ⟩$ and $\Vert \cdot \Vert$ to denote the Euclidean inner product and norm, respectively. For a matrix A, $A_{\mathrm{ij}}$ denotes its $(i,j)$th entry, and $A^T$ represents the transpose of A. We use ${\lambda }_{max}(A)$ and ${\lambda }_{min}(A)$ to denote the largest and the smallest eigenvalue of symmetric matrix A, respectively.

Let $X\subseteq {\mathbb{R}}^n$. We denote the distance function to X by $d_X(x):=\underset{\overline{x}\in X}{inf}\Vert x-\overline{x}\Vert$ and the set-valued mapping ${\mathrm{\Pi }}_X(x)$ stands for the projection of x on X, i.e. ${\mathrm{\Pi }}_X(x):=\{y\in X:\Vert x-y\Vert =d_X(x)\}$.

We call a differentiable function $f:{\mathbb{R}}^n\to (-\mathrm{\infty },\mathrm{\infty })$ L-smooth if $\Vert \mathrm{\nabla }f(x_1)-\mathrm{\nabla f}(x_2)\Vert \le L\Vert x_1-x_2\Vert \mathrm{\forall }{x}_1,x_2\in {\mathbb{R}}^n.$The function $f:{\mathbb{R}}^n\to \mathbb{R}$ is called μ-strongly convex function if the function $x\mapsto f(x)-\frac{\mu }{2}\Vert x{\Vert }^2$ is convex. Clearly, any convex function is 0-strongly convex. We denote the set of real-valued convex functions which are L-smooth and μ-strongly convex by ${\mathcal{F}}_{\mu ,L}({\mathbb{R}}^n)$.

Let $\mathcal{I}$ be a finite index set and let $\{(x^i;g^i;f^i){\}}_{i\in \mathcal{I}}\subseteq {\mathbb{R}}^n\times {\mathbb{R}}^n\times \mathbb{R}$. A set $\{(x^i;g^i;f^i){\}}_{i\in \mathcal{I}}$ is called ${\mathcal{F}}_{\mu ,L}$-interpolable if there exists $f\in {\mathcal{F}}_{\mu ,L}({\mathbb{R}}^n)$ with $f(x^i)=f^i,g^i\in \mathrm{\partial f}(x^i)i\in \mathcal{I}.$The next theorem gives necessary and sufficient conditions for ${\mathcal{F}}_{\mu ,L}$-interpolability.

Theorem 1.1

[27, Theorem 4]

Let $L\in (0,\mathrm{\infty })$ and $\mu \in [0,\mathrm{\infty })$ and let $\mathcal{I}$ be a finite index set. The set $\{(x^i;g^i;f^i){\}}_{i\in \mathcal{I}}\subseteq {\mathbb{R}}^n\times {\mathbb{R}}^n\times \mathbb{R}$ is ${\mathcal{F}}_{\mu ,L}$-interpolable if and only if for any $i,j\in \mathcal{I}$, we have

(3) $\frac{1}{2(1-\frac{\mu }{L})}(\frac{1}{L}{\Vert g^i-g^j\Vert }^2+\mu {\Vert x^i-x^j\Vert }^2-\frac{2\mu }{L}⟨g^j-g^i,x^j-x^i⟩)\le f^i-f^j-⟨g^j,x^i-x^j⟩.$(3)

It is worth mentioning that, under the assumptions of Theorem 1.1, the set $\{(x^i;g^i;f^i){\}}_{i\in \mathcal{I}}$ is interpolable with an L-smooth μ-strongly concave function if and only if for any $i,j\in \mathcal{I}$, we have

(4) $\frac{1}{2(1-\frac{\mu }{L})}(\frac{1}{L}{\Vert g^i-g^j\Vert }^2+\mu {\Vert x^i-x^j\Vert }^2+\frac{2\mu }{L}⟨g^j-g^i,x^j-x^i⟩)\le -f^i+f^j+⟨g^j,x^i-x^j⟩.$(4)

2. The gradient descent–ascent method

In this section, we study the convergence rate of gradient descent–ascent method when $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$ with $min\{{\mu }_x,{\mu }_y\}>0$. Indeed, we investigate the worst-case behaviour of one step of Algorithm 1 in terms of distance to the unique saddle point $(x^{\star },y^{\star })$ for one iterate. Let $(x^2,y^2)$ be generated by the algorithm using the starting point $(x^1,y^1)$. The worst-cast convergence rate is in essence an optimization problem. Indeed, the worst-cast convergence rate of Algorithm 1 is given by the solution of the following abstract optimization problem: (5) $\begin{array}{rl}max& \frac{\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2}{\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& (x^2,y^2)\mathrm{is}\mathrm{generated}\mathrm{by}\mathrm{Algorithm}1\mathrm{w}.\mathrm{r}.\mathrm{t}.F,x^1,y^1\\ & (x^{\star },y^{\star })\mathrm{is}\mathrm{the}\mathrm{unique}\mathrm{saddle}\mathrm{point}\mathrm{of}\mathrm{problem}(1)\\ & F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)\\ & x^1\in {\mathbb{R}}^n,y^1\in {\mathbb{R}}^m.\end{array}$(5) In problem (5(5) $\begin{array}{rl}max& \frac{\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2}{\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& (x^2,y^2)\mathrm{is}\mathrm{generated}\mathrm{by}\mathrm{Algorithm}1\mathrm{w}.\mathrm{r}.\mathrm{t}.F,x^1,y^1\\ & (x^{\star },y^{\star })\mathrm{is}\mathrm{the}\mathrm{unique}\mathrm{saddle}\mathrm{point}\mathrm{of}\mathrm{problem}(1)\\ & F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)\\ & x^1\in {\mathbb{R}}^n,y^1\in {\mathbb{R}}^m.\end{array}$(5) ), $F,x^1,x^2,x^{\star },y^1,y^2,y^{\star }$ are decision variables and ${\mu }_x,L_x,{\mu }_y,L_y,L_{\mathrm{xy}},t$ are fixed parameters. At first glace, problem (5(5) $\begin{array}{rl}max& \frac{\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2}{\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& (x^2,y^2)\mathrm{is}\mathrm{generated}\mathrm{by}\mathrm{Algorithm}1\mathrm{w}.\mathrm{r}.\mathrm{t}.F,x^1,y^1\\ & (x^{\star },y^{\star })\mathrm{is}\mathrm{the}\mathrm{unique}\mathrm{saddle}\mathrm{point}\mathrm{of}\mathrm{problem}(1)\\ & F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)\\ & x^1\in {\mathbb{R}}^n,y^1\in {\mathbb{R}}^m.\end{array}$(5) ) seems completely intractable, but its solution may in fact be approximated using a suitable semidefinite programming (SDP) problem, as shown below. This type of approximation is an example of the so-called SDP performance estimation method, that was introduced by Drori and Teboulle [10].

Suppose that $\begin{array}{rl}& F^{i,j}=F(x^i,y^j)i,j\in \{1,2,\star \},\\ & G_x^{i,j}={\mathrm{\nabla }}_{x}F(x^i,y^j)i,j\in \{1,2,\star \},\\ & G_y^{i,j}={\mathrm{\nabla }}_{y}F(x^i,y^j)i,j\in \{1,2,\star \},\end{array}$where indices $\{1,2,\star \}$ refers to the starting point, the point generated by Algorithm 1 and the saddle point of the problem, respectively. Note that due to the the necessary and sufficient conditions for convex–concave saddle point problems, we have $G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.$By using Theorem 1.1, problem (5(5) $\begin{array}{rl}max& \frac{\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2}{\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& (x^2,y^2)\mathrm{is}\mathrm{generated}\mathrm{by}\mathrm{Algorithm}1\mathrm{w}.\mathrm{r}.\mathrm{t}.F,x^1,y^1\\ & (x^{\star },y^{\star })\mathrm{is}\mathrm{the}\mathrm{unique}\mathrm{saddle}\mathrm{point}\mathrm{of}\mathrm{problem}(1)\\ & F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)\\ & x^1\in {\mathbb{R}}^n,y^1\in {\mathbb{R}}^m.\end{array}$(5) ) may be relaxed as a finite dimensional optimization problem, (6) $\begin{array}{rl}max& \frac{\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2}{\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^2;G_x^{2,k};F^{2,k}),(x^{\star };G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^2;G_y^{k,2};F^{k,2}),(y^{\star };G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & \Vert G_x^{k,i}-G_x^{k,j}\Vert \le L_{\mathrm{xy}}\Vert y^i-y^j\Vert ,i,j,k\in \{1,2,\star \}\\ & \Vert G_y^{i,k}-G_y^{j,k}\Vert \le L_{\mathrm{xy}}\Vert x^i-x^j\Vert ,i,j,k\in \{1,2,\star \}\\ & x^2=x^1-t{G}_x^{1,1}\\ & y^2=y^1+t{G}_y^{1,1},\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(6) In problem (6(6) $\begin{array}{rl}max& \frac{\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2}{\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^2;G_x^{2,k};F^{2,k}),(x^{\star };G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^2;G_y^{k,2};F^{k,2}),(y^{\star };G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & \Vert G_x^{k,i}-G_x^{k,j}\Vert \le L_{\mathrm{xy}}\Vert y^i-y^j\Vert ,i,j,k\in \{1,2,\star \}\\ & \Vert G_y^{i,k}-G_y^{j,k}\Vert \le L_{\mathrm{xy}}\Vert x^i-x^j\Vert ,i,j,k\in \{1,2,\star \}\\ & x^2=x^1-t{G}_x^{1,1}\\ & y^2=y^1+t{G}_y^{1,1},\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(6) ), $\{(x^i;G_x^{i,j};F^{i,j})\}$ and $\{(y^i;G_y^{j,i};F^{j,i})\}$ $(i,j\in \{1,2,\star \})$ are decision variables. We may assume that $x^{\star }=0$ and $y^{\star }=0$ as Algorithm 1 is invariant under translation. By elimination, problem (6(6) $\begin{array}{rl}max& \frac{\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2}{\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^2;G_x^{2,k};F^{2,k}),(x^{\star };G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^2;G_y^{k,2};F^{k,2}),(y^{\star };G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & \Vert G_x^{k,i}-G_x^{k,j}\Vert \le L_{\mathrm{xy}}\Vert y^i-y^j\Vert ,i,j,k\in \{1,2,\star \}\\ & \Vert G_y^{i,k}-G_y^{j,k}\Vert \le L_{\mathrm{xy}}\Vert x^i-x^j\Vert ,i,j,k\in \{1,2,\star \}\\ & x^2=x^1-t{G}_x^{1,1}\\ & y^2=y^1+t{G}_y^{1,1},\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(6) ) may be reformulated as follows, (7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) To approximate the solution of problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ), we reformulate it as a semidefinite program by using the Gram matrix of the unknown vectors in the problem. Indeed, we form the Gram matrices X and Y as follows, $\begin{array}{rl}& U=\left(\begin{array}{cccccccccc}{x}^1& x^2& G_x^{1,1}& G_x^{1,2}& G_x^{1,\star }& G_x^{2,1}& G_x^{2,2}& G_x^{2,\star }& G_x^{\star ,1}& G_x^{\star ,2}\end{array}\right)\\ & V=\left(\begin{array}{cccccccccc}{y}^1& y^2& G_y^{1,1}& G_y^{1,2}& G_y^{1,\star }& G_y^{2,1}& G_y^{2,2}& G_y^{2,\star }& G_y^{\star ,1}& G_y^{\star ,2}\end{array}\right)\\ & X=U^{T}U,Y=V^{T}V.\end{array}$This results in an SDP problem, as long as we view the value $\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2$, that appears in the denominator of the objective of problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ), as a fixed parameter. For this reason we may indeed view problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ) as an SDP problem in the positive semidefinite matrix variables X and Y. The interested reader may refer to [27,31] for more details concerning the Gram matrix formulation, and SDP performance estimation in general.

For the convenience of the analysis, we investigate the linear convergence of Algorithm 1 in terms of $L=max\{L_x,L_y\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}$. Before we present the main theorem in this section, we need to present a lemma.

Lemma 2.1

Let $0<\mu \le L$, $c\ge 0$ and let $I=(0,\frac{2\mu }{\mathrm{\mu L}+c^2})$. Suppose that the function $u:I\to \mathbb{R}$ given by $u(t)=\frac{1}{2}(L^2+{\mu }^2+2c^2)t^2-(L+\mu )t+\frac{1}{2}(L-\mu )t\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4c^2{t}^2}.$Then u is convex on I and $u(I)\subseteq [-1,0)$.

Proof.

Consider the function $v:I\to \mathbb{R}$ given by $v(t)=(L^2+{\mu }^2+2c^2)t+(L-\mu )\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4c^2{t}^2}.$The function v is convex and positive on I. By elementary calculus, one can show that $v^{\mathrm{\prime }}(0)>0$. So v is increasing on I due to the convexity. As the product of positive monotone convex functions is a convex function, the function $t\mapsto \mathrm{tv}(t)$ is also convex, which implies the convexity of u. Indeed, u is strictly convex on I. Since strictly convex functions attain their maximum on endpoints of a given interval, $u(t)<max\{u(0),u(\frac{2\mu }{\mathrm{\mu L}+c^2})\}=0$ for $t\in I$. It remains to show that $\underset{t\in I}{min}u(t)\ge -1$. This follows from the point that $u(t)\ge \frac{1}{2}(L^2+{\mu }^2)t^2-(L+\mu )t\ge \frac{-1}{2}(1+\frac{2\mathrm{L\mu }}{L^2+{\mu }^2})\ge -1,$and the proof is complete.

By the weak duality theorem for SDP, one may demonstrate an upper bound for the optimal value of the SDP problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ), by constructing a feasible solution to its dual problem, i.e. feasible dual multipliers for the constraints of problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ). This is done in the next theorem. In the proof, the correct value of the dual multipliers are simply given, and their correctness is verified. The correct values were obtained by solving the SDP problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ) repeatedly for different numerical values of the parameters, and noting the (numerical) optimal dual multiplier values. Based on these values, it was possible to deduce the analytical expressions for the multipliers. For this reason, the proof was found in a computer-assisted way, but it does not rely on any numerical calculations. Having said that, the proof involves a long identity, given in full in Appendix 2 to this paper, that is so long that it could only be obtained in a computer-assisted way.

Theorem 2.2

Let $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$. Suppose that $L=max\{L_x,L_y\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}>0$. If $t\in (0,\frac{2\mu }{\mathrm{\mu L}+L_{\mathrm{xy}}^2})$, then Algorithm 1 generates $(x^2,y^2)$ such that (8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) where $\alpha =1+\frac{1}{2}(L^2+{\mu }^2+2L_{\mathrm{xy}}^2)t^2-(L+\mu )t+\frac{1}{2}(L-\mu )t\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4L_{\mathrm{xy}}^2{t}^2}.$

Proof.

As mentioned earlier, we may assume without loss of generality that $x^{\star }=0$ and $y^{\star }=0$. By assumption, $F(\cdot ,y)\in {\mathcal{F}}_{\mu ,L}({\mathbb{R}}^n)$ and $F(x,\cdot )\in {\mathcal{F}}_{\mu ,L}({\mathbb{R}}^m)$ for any fixed x, y. Without loss of generality, we may also assume that $L_{\mathrm{xy}}=1$, by replacing F by $\frac{1}{L_{\mathrm{xy}}}F$. This follows from the observation that Algorithm 1 generates the same point $(x^2,y^2)$ for the problem $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}\frac{1}{L_{\mathrm{xy}}}F(x,y),$with the step length $L_{\mathrm{xy}}t$. Moreover, one has $\frac{1}{L_{\mathrm{xy}}}F\in \mathcal{F}(\frac{L_x}{L_{\mathrm{xy}}},\frac{L_y}{L_{\mathrm{xy}}},1,\frac{{\mu }_x}{L_{\mathrm{xy}}},\frac{{\mu }_y}{L_{\mathrm{xy}}})$ if and only if $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$. Now let $t\in (0,\frac{2\mu }{\mathrm{\mu L}+1})$ and define (the multipliers): $\begin{array}{rl}& \overline{\alpha }=1+\frac{1}{2}(L^2+{\mu }^2+2)t^2-(L+\mu )t+\frac{1}{2}(L-\mu )t\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2},\\ & \beta =\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2},{\gamma }_1=\frac{t(t^2(2+L^2+\mathrm{L\mu })-t(3L+\mu )+(\mathrm{Lt}-1)\beta +2)}{\beta },\\ & {\gamma }_2=\frac{t(t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})\beta +2)}{\beta },{\gamma }_3=\frac{t^2(\beta +\mathrm{Lt}-\mathrm{\mu t})}{2\beta }.\end{array}$It is readily verified that ${\gamma }_1,{\gamma }_2,{\gamma }_3\ge 0$, but since this calculation is somewhat tedious we present it in Appendix 1. Moreover, Lemma 2.1 implies that $\overline{\alpha }\in [0,1)$.

The idea of the proof is now as follows: we first establish that, for any feasible solution of the SDP problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ), it holds that (9) ${\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2-\overline{\alpha }\left({\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2\right)\le 0.$(9) We do this by establishing an algebraic identity for the left-hand side of the inequality (9(9) ${\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2-\overline{\alpha }\left({\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2\right)\le 0.$(9) ). The first and last terms of this identity (shown in full in Appendix 2 to this paper) are as follows: $\begin{array}{rl}& {\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2-\overline{\alpha }\left({\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2\right)\\ & =-{\gamma }_1(F^{1,1}-F^{\star ,1}-⟨G_x^{\star ,1},x^1⟩\\ & -\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_x^{1,1}-G_x^{\star ,1}\Vert }^2+\mu {\Vert x^1\Vert }^2-\frac{2\mu }{L}⟨G_x^{\star ,1}-G_x^{1,1},-x^1⟩))\\ & ⋮\\ & -\frac{t{(\beta +\mathrm{Lt}-\mathrm{\mu t})}^2}{4(L-\mu )\beta }{\Vert G_y^{1,1}-G_y^{\star ,1}-G_y^{1,\star }\Vert }^2.\end{array}$Note that the first term on the right-hand side is indeed non-positive, since ${\gamma }_1\ge 0$, and the expression in brackets is non-negative at any feasible solution of the SDP problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ), since it corresponds to one of the constraints in (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ). The last term is non-positive as well, since it is the product of a non-positive multiplier with a squared expression. The remaining terms in the identity are similarly non-positive (see Appendix 2), proving the inequality (9(9) ${\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2-\overline{\alpha }\left({\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2\right)\le 0.$(9) ). All that remains is to recognize that, in (9(9) ${\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2-\overline{\alpha }\left({\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2\right)\le 0.$(9) ), $G_x^{1,1}$ corresponds to ${\mathrm{\nabla }}_{x}F(x^1,y^1)$, so that $x^1-t{G}_x^{1,1}$ corresponds to $x^2$, etc. This yields the statement of the theorem, after rescaling to remove the assumption $L_{\mathrm{xy}}=1$.

One may wonder how we obtained the (analytical) expression for α in Theorem 2.2. Consider the optimization problem (10) $\underset{x\in {\mathbb{R}}^n}{min}f(x),$(10) where $f\in {\mathcal{F}}_{\mu ,L}$. It is known that the quadratic function $q(x)=x^T\mathrm{Qx}$ with ${\lambda }_{max}(Q)=L$ and ${\lambda }_{min}(Q)=\mu$ attains the worst-case convergence rate for the gradient method; see e.g. [9]. We guessed that this property may hold for problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) and we investigated the bilinear saddle point problem (11) $\underset{x\in {\mathbb{R}}^2}{min}\underset{y\in {\mathbb{R}}^2}{max}\frac{1}{2}{x}^T\left(\begin{array}{cc}{L}_x& 0\\ 0& {\mu }_x\end{array}\right)x+x^T\left(\begin{array}{cc}0& L_{\mathrm{xy}}\\ L_{\mathrm{xy}}& 0\end{array}\right)y-\frac{1}{2}{y}^T\left(\begin{array}{cc}{L}_y& 0\\ 0& {\mu }_y\end{array}\right)y,$(11) where $L_x\ge {\mu }_x>0$, $L_y\ge {\mu }_y>0$ and $L_{\mathrm{xy}}$ are fixed parameters and we derived the worst case convergence of Algorithm 1 with respect to this problem. Our numerical experiments showed that the derived convergence rate is the same as the optimal value of the semidefinite programming problem corresponding to problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ). Moreover, as a by-product, we exhibit that the convergence rate (8(8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) ) is exact for one iteration by using problem (11(11) $\underset{x\in {\mathbb{R}}^2}{min}\underset{y\in {\mathbb{R}}^2}{max}\frac{1}{2}{x}^T\left(\begin{array}{cc}{L}_x& 0\\ 0& {\mu }_x\end{array}\right)x+x^T\left(\begin{array}{cc}0& L_{\mathrm{xy}}\\ L_{\mathrm{xy}}& 0\end{array}\right)y-\frac{1}{2}{y}^T\left(\begin{array}{cc}{L}_y& 0\\ 0& {\mu }_y\end{array}\right)y,$(11) ); see Proposition 2.4.

Theorem 2.2 provides some new information concerning Algorithm 1. Firstly, Theorem 2.2 improves the known convergence factor in the literature; see our discussion in Introduction. In addition, it investigates the convergence rate for a step length in a larger interval. Secondly, it does not assume the second order continuous differentiability of F, which is commonly used for deriving a local convergence rate; see [17,20,33]. Finally, the given convergence rate incorporates three parameter $\mu =min\{{\mu }_x,{\mu }_y\}$, $L=max\{L_x,L_y\}$ and $L_{\mathrm{xy}}$, which is more informative in comparison with the results in the literature mostly given in terms of $\mu =min\{{\mu }_x,{\mu }_y\}$ and $L=max\{L_x,L_y,L_{\mathrm{xy}}\}$; see [21,33,34] and references therein. Even though if one considers $L=max\{L_x,L_y,L_{\mathrm{xy}}\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}$, convergence rate (8(8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) ) dominates (2(2) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le (1+4L^2{t}^2-2\mathrm{\mu t})(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$(2) ). This follows from that for $t\in (0,\frac{\mu }{2L^2})$, one has

$\begin{array}{rl}& (1+4L^2{t}^2-2\mathrm{\mu t})-(1+\frac{1}{2}(3L^2+{\mu }^2)t^2-(L+\mu )t+\frac{1}{2}(L-\mu )t\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4L^2{t}^2})\\ & \ge (2L^2+\mathrm{L\mu }-{\mu }^2)t^2\ge 2L^2{t}^2,\end{array}$where the first inequality results from $\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4L^2{t}^2}\le (2-\mathrm{Lt}-\mathrm{\mu t})+2\mathrm{Lt}$. In addition, in this case, the step length can take value in a larger interval as $(0,\frac{\mu }{2L^2})\subseteq (0,\frac{2\mu }{L(L+\mu )})$. Moreover, Conjecture 2.6 discusses the convergence rate in terms of $L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y$.

The next proposition gives the optimal step length with respect to the worst case convergence rate.

Proposition 2.3

Let $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$. If $L=max\{L_x,L_y\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}>0$, then the optimal step length for Algorithm 1 with respect to the bound (8(8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) ) is (12) $t^{\star }=\frac{2((L+\mu )\sqrt{L_{\mathrm{xy}}^2+\mathrm{L\mu }}+L_{\mathrm{xy}}(\mu -L))}{(4L_{\mathrm{xy}}^2+(L+\mu {)}^2)\sqrt{L_{\mathrm{xy}}^2+\mathrm{L\mu }}}.$(12) Moreover, the convergence rate with respect to $t^{\star }$ is (13) ${\alpha }^{\star }=\frac{8L_{\mathrm{xy}}(L^2-{\mu }^2)\sqrt{\mathrm{L\mu }+L_{\mathrm{xy}}^2}+{(L^2-{\mu }^2)}^2+16L_{\mathrm{xy}}^2(\mathrm{L\mu }+L_{\mathrm{xy}}^2)}{{((L+\mu {)}^2+4L_{\mathrm{xy}}^2)}^2}.$(13)

Proof.

Let $\alpha :[0,\frac{2\mu }{\mathrm{\mu L}+L_{\mathrm{xy}}^2}]\to \mathbb{R}$ given by $\alpha (t)=1+\frac{1}{2}(L^2+{\mu }^2+2L_{\mathrm{xy}}^2)t^2-(L+\mu )t+\frac{1}{2}(L-\mu )t\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4L_{\mathrm{xy}}^2{t}^2}.$By Lemma 2.1, α is a strictly convex function on its domain. By doing some algebra, one can verify that ${\alpha }^{\mathrm{\prime }}(t^{\star })=0$, which implies that $t^{\star }$ is the minimum.

If $L_{\mathrm{xy}}=0$, problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) reduces to a separable optimization problem. Indeed, the variables x and y are independent. Under this assumption, the optimal step length given by Proposition 2.3 is $t^{\star }=\frac{2}{L+\mu }$, which is the well-known optimal step length for the optimization problem $\underset{x\in {\mathbb{R}}^n}{min}f(x),$where $f\in {\mathcal{F}}_{\mu ,L}$; see [24, Theorem 2.1.15]. Moreover, the convergence rate corresponding to $t^{\star }$ is ${\alpha }^{\star }=(\frac{L-\mu }{L+\mu }{)}^2$. By some algebra, one can show that under the assumptions of Proposition (2.3), Algorithm 1 has a complexity of $\mathcal{O}((\frac{L}{\mu }+\frac{L_{\mathrm{xy}}^2}{{\mu }^2})\ln (\frac{1}{ϵ}))$. Note that the lower iteration complexity bound for first-order methods with $L=max\{L_x,L_y\}$ and $\mu =min\{{\mu }_x,{\mu }_y\}$ is $\mathrm{\Omega }(\sqrt{\frac{L}{\mu }+\frac{L_{\mathrm{xy}}^2}{{\mu }^2}}\ln (\frac{1}{ϵ}))$; see [34].

As mentioned earlier, we calculated the convergence rate by using problem (11(11) $\underset{x\in {\mathbb{R}}^2}{min}\underset{y\in {\mathbb{R}}^2}{max}\frac{1}{2}{x}^T\left(\begin{array}{cc}{L}_x& 0\\ 0& {\mu }_x\end{array}\right)x+x^T\left(\begin{array}{cc}0& L_{\mathrm{xy}}\\ L_{\mathrm{xy}}& 0\end{array}\right)y-\frac{1}{2}{y}^T\left(\begin{array}{cc}{L}_y& 0\\ 0& {\mu }_y\end{array}\right)y,$(11) ). The next proposition states that the bound (8(8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) ) is tight for some class of bilinear saddle point problems.

Proposition 2.4

Let $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$. Suppose that $L_x=L_y$ and $min\{{\mu }_x,{\mu }_y\}>0$. If $t\in (0,\frac{2\mu }{\mathrm{\mu L}+L_{\mathrm{xy}}^2})$, then convergence rate (8(8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) ) is exact for one iteration.

Proof.

To establish the proposition, it suffices to introduce a problem for which Algorithm 1 generates $(x^2,y^2)$ with respect to the initial point $(x^1,y^1)$ such that $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2=\alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$where α is the convergence rate factor given in Theorem 2.2. Consider problem (11(11) $\underset{x\in {\mathbb{R}}^2}{min}\underset{y\in {\mathbb{R}}^2}{max}\frac{1}{2}{x}^T\left(\begin{array}{cc}{L}_x& 0\\ 0& {\mu }_x\end{array}\right)x+x^T\left(\begin{array}{cc}0& L_{\mathrm{xy}}\\ L_{\mathrm{xy}}& 0\end{array}\right)y-\frac{1}{2}{y}^T\left(\begin{array}{cc}{L}_y& 0\\ 0& {\mu }_y\end{array}\right)y,$(11) ). Due to the symmetry of Algorithm 1 and the class of problems, we may assume ${\mu }_x\ge {\mu }_y$. Moreover, without loss of generality, we can take $L_{\mathrm{xy}}=1$; see our discussion in the proof of Theorem 2.2. Suppose $L=L_x$, $\mu ={\mu }_y$ and $\beta =\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}$. One can verify that Algorithm 1 with the initial point $\begin{array}{rl}& x_1^1=0,x_2^1=\sqrt{\frac{2-t(L+\mu )+\beta }{2\beta }},\\ & y_1^1=-t\sqrt{\frac{2}{\beta (2-t(L+\mu )+\beta )}},y_2^1=0.\end{array}$generates $(x^2,y^2)$ with the desired equality.

One may wonder why we stress on one iteration in Proposition 2.4. Based on our numerical results if $L_{\mathrm{xy}}>0$, under the setting of Theorem 2.2, we observed that $\Vert x^k-x^{\star }{\Vert }^2+\Vert y^k-y^{\star }{\Vert }^2<{\alpha }^{k-1}(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),k\ge 3,$for some $t\in (0,\frac{2\mu }{\mathrm{\mu L}+L_{\mathrm{xy}}^2})$. The reason may be related to the fact that the vector field ${\left(\begin{array}{cc}{\mathrm{\nabla }}_{x}F(x,y)& -{\mathrm{\nabla }}_{y}F(x,y)\end{array}\right)}^T$ is not conservative.

It may be of interest whether inequality (8(8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) ) may hold without strong convexity. By removing strong convexity, the solution set may not be singleton. Hence, we investigate distance to the solution set, that is, if there exists $0\le \alpha <1$ with $d_{S^{\star }}^2((x^2,y^2))\le \alpha d_{S^{\star }}^2((x^1,y^1)).$The next proposition says in general the answer is negative. Indeed, it gives an example with $min\{{\mu }_x,{\mu }_y\}=0$ and a unique saddle point for which $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\ge \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$for some $\alpha \ge 1$, no matter how close $(x^1,y^1)$ is to the unique saddle point and which positive step length t is taken. In the next proposition, we may assume without loss of generality ${\mu }_x=0$ and make an example analogous to that given in Proposition 2.4.

Proposition 2.5

Let $L,L_{\mathrm{xy}},{\mu }_y,t,r>0$ be given. Then there exist $\alpha \ge 1$ and a function $F\in \mathcal{F}(L,L,L_{\mathrm{xy}},0,{\mu }_y)$ with the unique saddle point $(x^{\star },y^{\star })$ and $(x^1,y^1)$ such that, for $(x^2,y^2)$ generated by Algorithm 1, we have $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\ge \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$and $\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2=r^2$.

Proof.

As discussed before, we may assume $L_{\mathrm{xy}}=1$. Consider the bilinear saddle point problem, $\underset{x\in {\mathbb{R}}^2}{min}\underset{y\in {\mathbb{R}}^2}{max}F(x,y)=\frac{1}{2}{x}^T\left(\begin{array}{cc}L& 0\\ 0& 0\end{array}\right)x+x^T\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)y-\frac{1}{2}{y}^T\left(\begin{array}{cc}L& 0\\ 0& {\mu }_y\end{array}\right)y.$It is clear that $F\in \mathcal{F}(L,L,L_{\mathrm{xy}},0,{\mu }_y)$, and the unique saddle point is $(x^{\star },y^{\star })=(0,0)$. Suppose that $\begin{array}{rl}& x_1^1=0,x_2^1=r\sqrt{\frac{2-\mathrm{tL}+\beta }{2\beta }},\\ & y_1^1=-\mathrm{rt}\sqrt{\frac{2}{\beta (2-\mathrm{tL}+\beta )}},y_2^1=0,\end{array}$where $\beta =\sqrt{(\mathrm{Lt}-2{)}^2+4t^2}$. One can verify Algorithm 1 generates $(x^2,y^2)$ with $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\ge \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2)=\alpha r^2,$where $\alpha =1+\frac{1}{2}(L^2+2)t^2-\mathrm{Lt}+\frac{1}{2}\mathrm{Lt}\sqrt{(\mathrm{Lt}-2{)}^2+4t^2}$. By Proposition 2.3, one can infer that $\alpha \ge 1$.

Note that r can take any positive value in Proposition 2.5. By Proposition 2.4, one can infer that the convergence rate factor for bilinear saddle point problems may not be improved for one iteration since the given example is a bilinear saddle point problem. Furthermore, the given convergence rate factor is tight whether $L_x=L_y$. As discussed in [28], the function $H(x,y)=F(\sqrt[4]{\frac{L_y}{L_x}}x,\sqrt[4]{\frac{L_x}{L_y}}y)$ shares the same smoothness constants with respect to x and y, that is, ${\mathrm{\nabla }}_{x}H(\cdot ,y)$ and ${\mathrm{\nabla }}_{y}H(x,\cdot )$ are Lipschitz continuous with the same modulus $\sqrt{L_x{L}_y}$. However, the gradient methods are not invariant under scaling; see [8, Chapter 9]. Hence, we may lose the generality of our discussion by assuming this condition.

Based on our numerical results and analysis of problem (11(11) $\underset{x\in {\mathbb{R}}^2}{min}\underset{y\in {\mathbb{R}}^2}{max}\frac{1}{2}{x}^T\left(\begin{array}{cc}{L}_x& 0\\ 0& {\mu }_x\end{array}\right)x+x^T\left(\begin{array}{cc}0& L_{\mathrm{xy}}\\ L_{\mathrm{xy}}& 0\end{array}\right)y-\frac{1}{2}{y}^T\left(\begin{array}{cc}{L}_y& 0\\ 0& {\mu }_y\end{array}\right)y,$(11) ), we conjecture the following (exact) convergence rate of Algorithm 1 in terms of $L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y$. Due to the symmetry of Algorithm 1, we may assume that $L_x\ge L_y$. Moreover, Proposition 2.4 implies that bound (8(8) $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2),$(8) ) is tight when ${\mu }_y\le {\mu }_x$. Hence, we need only consider ${\mu }_y>{\mu }_x$.

Conjecture 2.6

Let $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$. Suppose that ${\mu }_y>{\mu }_x>0$, $max\{L_x,L_y\}=L_x$ and $\begin{array}{rl}& c=\frac{1}{2}(L_y^2+{\mu }_x^2)t-(L_y+{\mu }_x)+\frac{1}{2}(L_y-{\mu }_x)\sqrt{(L_{y}t+{\mu }_{x}t-2{)}^2+4L_{\mathrm{xy}}^2{t}^2},\\ & \overline{\mu }=\frac{c+2L_x-L_x^{2}t+L_x{L}_{\mathrm{xy}}^2{t}^2-(c+L_x(2-L_{x}t))\sqrt{1+t(c+t{L}_{\mathrm{xy}}^2)}}{t{L}_{\mathrm{xy}}(c+t{L}_{\mathrm{xy}}^2+L_x(2-L_{x}t))},\\ & \alpha (\mu ,L,L_{\mathrm{xy}},t)=1+\frac{1}{2}(L^2+{\mu }^2+2L_{\mathrm{xy}}^2)t^2-(L+\mu )t\\ & +\frac{1}{2}(L-\mu )t\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4L_{\mathrm{xy}}^2{t}^2}.\end{array}$Then, one of the following scenarios holds.

1. Assume that ${\mu }_x{\mu }_y(L_x-L_y)\ge L_{\mathrm{xy}}^2({\mu }_y-{\mu }_x)$ and $t\in (0,\frac{2{\mu }_y}{L_x{\mu }_y+L_{\mathrm{xy}}^2})$.

   1. If ${\mu }_y\le \overline{\mu }$, then $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha ({\mu }_y,L_x,L_{\mathrm{xy}},t)(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$

   2. If ${\mu }_y\ge \overline{\mu }$, then $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha ({\mu }_x,L_y,L_{\mathrm{xy}},t)(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$

2. Assume that ${\mu }_x{\mu }_y(L_x-L_y)\le L_{\mathrm{xy}}^2({\mu }_y-{\mu }_x)$ and $t\in (0,\frac{2{\mu }_x}{L_y{\mu }_x+L_{\mathrm{xy}}^2})$.

   1. If ${\mu }_y\le \overline{\mu }$, then $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha ({\mu }_y,L_x,L_{\mathrm{xy}},t)(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$

   2. If ${\mu }_y\ge \overline{\mu }$, then $\Vert x^2-x^{\star }{\Vert }^2+\Vert y^2-y^{\star }{\Vert }^2\le \alpha ({\mu }_x,L_y,L_{\mathrm{xy}},t)(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$

Although we have extensive numerical evidence supporting Conjecture 2.6, we have been unable to prove either part (a) or part (b). To be more precise, we have verified numerically that the optimal value of the SDP problems (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ) and (11(11) $\underset{x\in {\mathbb{R}}^2}{min}\underset{y\in {\mathbb{R}}^2}{max}\frac{1}{2}{x}^T\left(\begin{array}{cc}{L}_x& 0\\ 0& {\mu }_x\end{array}\right)x+x^T\left(\begin{array}{cc}0& L_{\mathrm{xy}}\\ L_{\mathrm{xy}}& 0\end{array}\right)y-\frac{1}{2}{y}^T\left(\begin{array}{cc}{L}_y& 0\\ 0& {\mu }_y\end{array}\right)y,$(11) ) corresponds to the expressions in Conjecture 2.6 for many different numerical values of the parameters $L_x$, $L_y$, $L_{\mathrm{xy}}$, ${\mu }_x$, and ${\mu }_y$, but we could not manage to derive analytical expressions for the dual multipliers of SDP problem (7(7) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y,L_y\\ & {\Vert G_x^{k,1}-G_x^{k,2}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{2,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,1}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2\Vert y^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{1,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2\Vert x^1{\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_x^{k,2}-G_x^{k,\star }\Vert }^2\le L_{\mathrm{xy}}^2{\Vert y^1+t{G}_y^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & {\Vert G_y^{2,k}-G_y^{\star ,k}\Vert }^2\le L_{\mathrm{xy}}^2{\Vert x^1-t{G}_x^{1,1}\Vert }^2,k\in \{1,2,\star \}\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(7) ) for proving the conjecture.

2.1. Numerical illustration

In this section we provide randomly generated examples to compare the optimal step length (12(12) $t^{\star }=\frac{2((L+\mu )\sqrt{L_{\mathrm{xy}}^2+\mathrm{L\mu }}+L_{\mathrm{xy}}(\mu -L))}{(4L_{\mathrm{xy}}^2+(L+\mu {)}^2)\sqrt{L_{\mathrm{xy}}^2+\mathrm{L\mu }}}.$(12) ) given in this paper to the known step length $t=\mu /(4L^2)$ for the bilinear problem $\underset{x\in {\mathbb{R}}^5}{min}\underset{y\in {\mathbb{R}}^4}{max}\frac{1}{2}{x}^T{A}_{x}x+x^T{A}_{\mathrm{xy}}y-\frac{1}{2}{y}^T{A}_{y}y,$where $A_x$ and $A_y$ are symmetric positive definite matrices. Moreover, the instances are constructed such that the spectra of $A_x$ and $A_y$ are contained in the interval $[0.5,5]$. For this class of instances, one has $L=max\{{\lambda }_{max}(A_x),{\lambda }_{max}(A_y)\}\in [0.5,5]$ and $\mu =min\{{\lambda }_{min}(A_x),{\lambda }_{min}(A_y)\}\in [0.5,L]$. The matrix $A_{\mathrm{xy}}\in {\mathbb{R}}^{5\times 4}$ has entries chosen uniformly at random from $[0,1]$, and subsequently we set $L_{\mathrm{xy}}=\Vert A_{\mathrm{xy}}{\Vert }_2$. By construction, the solution (saddle point) is $(x^{\star },y^{\star })=(0,0)$. The starting points $x^1$ and $y^1$ are randomly drawn unit vectors so that the initial condition $\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2=2$ is satisfied.

In Figure 1 we show average values (over 100 randomly generated instances) for the convergence indicator $\Vert x^k-x^{\star }{\Vert }^2+\Vert y^k-y^{\star }{\Vert }^2$ after k iterations, for the two step lengths.¹ Note that our new step length (12(12) $t^{\star }=\frac{2((L+\mu )\sqrt{L_{\mathrm{xy}}^2+\mathrm{L\mu }}+L_{\mathrm{xy}}(\mu -L))}{(4L_{\mathrm{xy}}^2+(L+\mu {)}^2)\sqrt{L_{\mathrm{xy}}^2+\mathrm{L\mu }}}.$(12) ) gives a clear improvement over the known step length $\mu /(4L^2)$.

Figure 1. Mean values of $\Vert x^k-x^{\star }{\Vert }^2+\Vert y^k-y^{\star }{\Vert }^2$ for 100 randomly generated instances for each iteration k using the two different step lengths t.

3. Linear convergence without strong convexity

In this section, we study the linear convergence of Algorithm 1 without assuming strong convexity. Indeed, we suppose that $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},0,0)$ and we propose some necessary and sufficient conditions for the linear convergence. This subject has received some attention in recent years and some sufficient conditions have been proposed in [11,33] under which Algorithm 1 enjoys local linear convergence rate or it is linearly convergent for bilinear saddle point problems. This topic has been investigated extensively in the context of optimization. The interested reader can refer to [1,7,19,23] and references therein. In this study, we extend the quadratic gradient growth property introduced in [19] for saddle point problems.

Recall that we denote the non-empty solution set of problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) by $S^{\star }$. As we do not assume the strong convexity (concavity), $S^{\star }$ may not be singleton. Note that $S^{\star }$ is a closed convex set under our assumptions. Recall that ${\mathrm{\Pi }}_{S^{\star }}((x,y))$ denotes the projection of $(x,y)$ onto $S^{\star }$.

Definition 3.1

Let ${\mu }_F>0$. A function F has a quadratic gradient growth if for any $x\in {\mathbb{R}}^n$ and $y\in {\mathbb{R}}^m$, (14) $⟨{\mathrm{\nabla }}_{x}F(x,y),x-x^{\star }⟩-⟨{\mathrm{\nabla }}_{y}F(x,y),y-y^{\star }⟩\ge {\mu }_F{d}_{S^{\star }}^2((x,y)),$(14) where $(x^{\star },y^{\star })={\mathrm{\Pi }}_{S^{\star }}((x,y))$.

Note that if we set $y=y^{\star }$ in (14(14) $⟨{\mathrm{\nabla }}_{x}F(x,y),x-x^{\star }⟩-⟨{\mathrm{\nabla }}_{y}F(x,y),y-y^{\star }⟩\ge {\mu }_F{d}_{S^{\star }}^2((x,y)),$(14) ), we have $⟨{\mathrm{\nabla }}_{x}F(x,y^{\star }),x-x^{\star }⟩\ge {\mu }_F\Vert x-x^{\star }{\Vert }^2.$Hence, $L_x$-smoothness implies that ${\mu }_F\le L_x$. Consequently, due to the symmetry, we have ${\mu }_F\le min\{L_x,L_y\}$. The next proposition states that the quadratic gradient growth condition is weaker than the strong convexity-strong concavity. Indeed, the strong convexity–strong concavity implies the quadratic gradient growth property.

Proposition 3.2

Let $F\in \mathcal{F}\mathcal{(}{L}_x,L_y,L_{\mathrm{xy}},{\mu }_x,{\mu }_y)$. If $min\{{\mu }_x,{\mu }_y\}>0$, then F has a quadratic gradient growth with ${\mu }_F=min\{{\mu }_x,{\mu }_y\}$.

Proof.

Under the assumptions, problem (1(1) $\underset{x\in {\mathbb{R}}^n}{min}\underset{y\in {\mathbb{R}}^m}{max}F(x,y),$(1) ) has a unique solution $(x^{\star },y^{\star })$ and ${\mathrm{\nabla }}_{x}F(x^{\star },y^{\star })=0$ and ${\mathrm{\nabla }}_{y}F(x^{\star },y^{\star })=0$. Let $\mu =min\{{\mu }_x,{\mu }_y\}$ and $L=max\{L_x,L_y\}$. Suppose that $(x,y)\in {\mathbb{R}}^n\times {\mathbb{R}}^m$. By Theorem 1.1, we have

$\begin{array}{rl}0& \le (F(x^{\star },y)-F(x,y)+⟨{\mathrm{\nabla }}_{x}F(x,y),x-x^{\star }⟩-\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert {\mathrm{\nabla }}_{x}F(x^{\star },y)-{\mathrm{\nabla }}_{x}F(x,y)\Vert }^2\\ & +\mu {\Vert x-x^{\star }\Vert }^2-\frac{2\mu }{L}⟨{\mathrm{\nabla }}_{x}F(x,y)-{\mathrm{\nabla }}_{x}F(x^{\star },y),x-x^{\star }⟩))+(F(x,y^{\star })-F(x^{\star },y^{\star })\\ & -\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert {\mathrm{\nabla }}_{x}F(x,y^{\star })\Vert }^2+\mu {\Vert x-x^{\star }\Vert }^2-\frac{2\mu }{L}⟨{\mathrm{\nabla }}_{x}F(x,y^{\star }),x-x^{\star }⟩))+(F(x,y)\\ & -F(x,y^{\star })-⟨{\mathrm{\nabla }}_{y}F(x,y),y-y^{\star }⟩-\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert {\mathrm{\nabla }}_{y}F(x,y^{\star })-{\mathrm{\nabla }}_{y}F(x,y)\Vert }^2+\mu {\Vert y-y^{\star }\Vert }^2\\ & -\frac{2\mu }{L}⟨{\mathrm{\nabla }}_{y}F(x,y^{\star })-{\mathrm{\nabla }}_{y}F(x,y),y-y^{\star }⟩))+(F(x^{\star },y^{\star })-F(x^{\star },y)-\frac{L}{2(L-\mu )}\\ & \times (\frac{1}{L}{\Vert {\mathrm{\nabla }}_{y}F(x^{\star },y)\Vert }^2+\mu {\Vert y-y^{\star }\Vert }^2-\frac{2\mu }{L}⟨{\mathrm{\nabla }}_{y}F(x^{\star },y),y^{\star }-y⟩))\\ & =\frac{-{\mu }^2}{L-\mu }{\Vert (x-x^{\star })-\frac{1}{2\mu }({\mathrm{\nabla }}_{x}F(x,y)+{\mathrm{\nabla }}_{x}F(x,y^{\star })-{\mathrm{\nabla }}_{x}F(x^{\star },y))\Vert }^2\\ & -\frac{1}{4(L-\mu )}{\Vert {\mathrm{\nabla }}_{x}F(x,y)-{\mathrm{\nabla }}_{x}F(x,y^{\star })-{\mathrm{\nabla }}_{x}F(x^{\star },y)\Vert }^2\\ & -\frac{{\mu }^2}{L-\mu }{\Vert (y-y^{\star })+\frac{1}{2\mu }({\mathrm{\nabla }}_{y}F(x,y)-{\mathrm{\nabla }}_{y}F(x,y^{\star })+{\mathrm{\nabla }}_{y}F(x^{\star },y))\Vert }^2\\ & -\frac{1}{4(L-\mu )}{\Vert {\mathrm{\nabla }}_{y}F(x,y)-{\mathrm{\nabla }}_{y}F(x,y^{\star })-{\mathrm{\nabla }}_{y}F(x^{\star },y)\Vert }^2\\ & -\mu ({\Vert x-x^{\star }\Vert }^2+{\Vert y-y^{\star }\Vert }^2)+⟨{\mathrm{\nabla }}_{x}F(x,y),x-x^{\star }⟩-⟨{\mathrm{\nabla }}_{y}F(x,y),y-y^{\star }⟩.\end{array}$Hence, $\mu ({\Vert x-x^{\star }\Vert }^2+{\Vert y-y^{\star }\Vert }^2)\le ⟨{\mathrm{\nabla }}_{x}F(x,y),x-x^{\star }⟩-⟨{\mathrm{\nabla }}_{y}F(x,y),y-y^{\star }⟩,$and the proof is complete.

Note that the converse of Proposition 3.2 does not hold necessarily. Consider the following saddle point problem (15) $\underset{x\in \mathbb{R}}{min}\underset{y\in \mathbb{R}}{max}F(x,y):=f(x+y)-2y^2,$(15) where $f(s)=\{\begin{array}{ll}0& |s|\le 1\\ (s-1{)}^2& s>1\\ (s+1{)}^2& s<-1.\end{array}$It is seen that F is not strongly convex-strongly concave and the solution set of problem (15(15) $\underset{x\in \mathbb{R}}{min}\underset{y\in \mathbb{R}}{max}F(x,y):=f(x+y)-2y^2,$(15) ) is $\{(x,0):|x|\le 1\}$. By doing some algebra, one can check that F has a quadratic gradient growth with ${\mu }_F=1$ while it is not strongly convex with respect to the first component. For the case that $F(\cdot ,y)$ is neither strongly convex nor is $F(x,\cdot )$ strongly concave, one may consider uncoupled problem $\underset{x\in \mathbb{R}}{min}\underset{y\in \mathbb{R}}{max}f(x)-f(y)$.

In what follows, by using performance estimation, we establish that Algorithm 1 enjoys the linear convergence whether $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},0,0)$ has a quadratic gradient growth. Without loss of generality, we may assume that $(0,0)={\mathrm{\Pi }}_{S^{\star }}((x^1,y^1))$. To establish the linear convergence, it suffices to show that $d_{S^{\star }}^2((x^2,y^2))\le \Vert x^2{\Vert }^2+\Vert y^2{\Vert }^2\le \alpha d_{S^{\star }}^2((x^1,y^1)),$for some $\alpha \in [0,1)$. Similarly to Section 2, we formulate the following optimization problem (16) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x=0,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star ,\ast \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y=0,L_y\\ & \Vert G_x^{k,i}-G_x^{k,j}\Vert \le L_{\mathrm{xy}}\Vert y^i-y^j\Vert ,i,j,k\in \{1,2,\star \}\\ & \Vert G_y^{i,k}-G_y^{j,k}\Vert \le L_{\mathrm{xy}}\Vert x^i-x^j\Vert ,i,j,k\in \{1,2,\star \}\\ & {\mu }_F(\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2)\le ⟨G_x^{1,1},x^1⟩-⟨G_y^{1,1},y^1⟩,\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(16) Note that in the formulation (16(16) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x=0,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star ,\ast \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y=0,L_y\\ & \Vert G_x^{k,i}-G_x^{k,j}\Vert \le L_{\mathrm{xy}}\Vert y^i-y^j\Vert ,i,j,k\in \{1,2,\star \}\\ & \Vert G_y^{i,k}-G_y^{j,k}\Vert \le L_{\mathrm{xy}}\Vert x^i-x^j\Vert ,i,j,k\in \{1,2,\star \}\\ & {\mu }_F(\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2)\le ⟨G_x^{1,1},x^1⟩-⟨G_y^{1,1},y^1⟩,\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(16) ), we only use a subset of constraints for the performance estimation. In the next theorem, we prove the linear convergence of Algorithm 1 when F has a quadratic gradient growth.

Theorem 3.3

Let $F\in \mathcal{F}(L_x,L_y,L_{\mathrm{xy}},0,0)$ and $L=max\{L_x,L_y\}$. Assume that F has a quadratic gradient growth with ${\mu }_F>0$. If $t\in (0,\frac{2{\mu }_F}{L{\mu }_F+2L_{\mathrm{xy}}\sqrt{{\mu }_F(L-{\mu }_F)}+L_{\mathrm{xy}}^2})$, then Algorithm 1 generates $(x^2,y^2)$ such that (17) $d_{S^{\star }}^2((x^2,y^2))\le \alpha d_{S^{\star }}^2((x^1,y^1)),$(17) where $\alpha =t(2t{L}_{\mathrm{xy}}\sqrt{{\mu }_F(L-{\mu }_F)}+{\mu }_F(\mathrm{Lt}-2)+t{L}_{\mathrm{xy}}^2)+1.$

Proof.

The argument is similar to that of Theorem 2.2. It is seen that for any step length t in the given interval, $\alpha \in [0,1)$. We may assume without loss of generality $L_{\mathrm{xy}}=1$. By the assumptions, $F(\cdot ,y)\in {\mathcal{F}}_{0,L}({\mathbb{R}}^n)$ and $F(x,\cdot )\in {\mathcal{F}}_{0,L}({\mathbb{R}}^m)$ for any fixed x, y. Suppose that

$\begin{array}{rl}& \overline{\alpha }=t(2t\sqrt{{\mu }_F(L-{\mu }_F)}+{\mu }_F(\mathrm{Lt}-2)+t)+1,\beta =t^2({\mu }_F\sqrt{L-{\mu }_F}+\sqrt{{\mu }_F}),\\ & {\gamma }_1=t^2(\frac{{\mu }_F}{\sqrt{{\mu }_F(L-{\mu }_F)}}+{\mu }_F),{\gamma }_2=\frac{t^2({\mu }_F(L-{\mu }_F)+\sqrt{{\mu }_F(L-{\mu }_F)})}{{\mu }_F},\\ & {\gamma }_3=-\frac{t^2({\mu }_F(L+{\mu }_F)+\sqrt{{\mu }_F(L-{\mu }_F)})}{{\mu }_F}+\frac{\beta }{\sqrt{L-{\mu }_F}}+2t,{\gamma }_4=\frac{1}{2}{t}^2(\sqrt{{\mu }_F(L-{\mu }_F)}+1).\end{array}$One may readily verify that ${\gamma }_1,{\gamma }_2,{\gamma }_3,{\gamma }_4\ge 0$. By doing some algebra, one can show that $\begin{array}{rl}& {\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2-\overline{\alpha }(\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2)+{\gamma }_1(F^{1,1}-F^{\star ,1}-⟨G_x^{\star ,1},x^1⟩\\ & -\frac{1}{2L}{\Vert G_x^{1,1}-G_x^{\star ,1}\Vert }^2)+{\gamma }_2(F^{\star ,1}-F^{1,1}+⟨G_x^{1,1},x^1⟩-\frac{1}{2L}{\Vert G_x^{\star ,1}-G_x^{1,1}\Vert }^2)+{\gamma }_2(F^{1,\star }\\ & -F^{\star ,\star }-\frac{1}{2L}{\Vert G_x^{1,\star }\Vert }^2)+{\gamma }_1(F^{\star ,\star }-F^{1,\star }+⟨G_x^{1,\star },x^1⟩-\frac{1}{2L}{\Vert G_x^{1,\star }\Vert }^2)+{\gamma }_1(F^{1,\star }-F^{1,1}\\ & +⟨G_y^{1,\star },y^1⟩-\frac{1}{2L}{\Vert G_y^{1,1}-G_y^{1,\star }\Vert }^2)+{\gamma }_2(F^{1,1}-F^{1,\star }-⟨G_y^{1,1},y^1⟩-\frac{1}{2L}{\Vert G_y^{1,\star }-G_y^{1,1}\Vert }^2)\\ & +{\gamma }_2(-F^{\star ,1}+F^{\star ,\star }-\frac{1}{2L}{\Vert G_y^{\star ,1}\Vert }^2)+{\gamma }_1(-F^{\star ,\star }+F^{\star ,1}+⟨G_y^{\star ,1},-y^1⟩-\frac{1}{2L}{\Vert G_y^{\star ,1}\Vert }^2)\\ & +{\gamma }_3(⟨G_x^{1,1},x^1⟩-⟨G_y^{1,1},y^1⟩-{\mu }_F({\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2))+{\gamma }_4(\Vert x^1{\Vert }^2-{\Vert G_y^{1,1}-G_y^{\star ,1}\Vert }^2)\\ & +{\gamma }_4(\Vert x^1{\Vert }^2-{\Vert G_y^{1,\star }\Vert }^2)+{\gamma }_4(\Vert y^1{\Vert }^2-{\Vert G_x^{1,1}-G_x^{1,\star }\Vert }^2)+{\gamma }_4(\Vert y^1{\Vert }^2-{\Vert G_x^{\star ,1}\Vert }^2)\\ & =-{\zeta }_1{\Vert x^1+{\zeta }_2{G}_x^{1,1}-{\zeta }_3(G_x^{1,\star }-G_x^{\star ,1})\Vert }^2-{\zeta }_4{\Vert G_x^{1,1}-G_x^{1,\star }-G_x^{\star ,1}\Vert }^2\\ & -{\zeta }_1{\Vert y^1-{\zeta }_2{G}_y^{1,1}-{\zeta }_3(G_y^{1,\star }-G_y^{\star ,1})\Vert }^2-{\zeta }_4{\Vert G_y^{1,1}-G_y^{\star ,1}-G_y^{1,\star }\Vert }^2\le 0,\end{array}$where the multipliers ${\zeta }_1,{\zeta }_2,{\zeta }_3,{\zeta }_4$ are given as follows $\begin{array}{rl}& {\zeta }_1={\mu }_F(\frac{\beta }{\sqrt{L-{\mu }_F}}-{\mu }_F{t}^2),{\zeta }_2=\frac{\beta }{2{\mu }_F\sqrt{{\mu }_F}{t}^2}-\frac{1}{{\mu }_F},{\zeta }_3=\frac{t^2(\sqrt{{\mu }_F(L-{\mu }_F)}+1)}{2{\mu }_F{t}^2},\\ & {\zeta }_4=\frac{1}{4}(\frac{2t^2({\mu }_F(L-{\mu }_F)+1)}{\sqrt{{\mu }_F(L-{\mu }_F)}}-\frac{{(2{\mu }_F{t}^2({\mu }_F-L)+\beta \sqrt{L-{\mu }_F})}^2}{{\mu }_F(L-{\mu }_F)t^2\sqrt{{\mu }_F(L-{\mu }_F)}}).\end{array}$One can show by some algebra that ${\zeta }_1,{\zeta }_4\ge 0$. Hence, for any feasible solution of problem (16(16) $\begin{array}{rl}max& \frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2}\\ \mathrm{s}.\mathrm{t}.& \{(x^1;G_x^{1,k};F^{1,k}),(x^1-t{G}_x^{1,1};G_x^{2,k};F^{2,k}),(0;G_x^{\star ,k};F^{\star ,k})\}\mathrm{satisfy}(3)\mathrm{for}\\ & k\in \{1,2,\star \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_x=0,L_x\\ & \{(y^1;G_y^{k,1};F^{k,1}),(y^1+t{G}_y^{1,1};G_y^{k,2};F^{k,2}),(0;G_y^{k,\star };F^{k,\star })\}\mathrm{satisfy}(4)\mathrm{for}\\ & k\in \{1,2,\star ,\ast \}\mathrm{w}.\mathrm{r}.\mathrm{t}.{\mu }_y=0,L_y\\ & \Vert G_x^{k,i}-G_x^{k,j}\Vert \le L_{\mathrm{xy}}\Vert y^i-y^j\Vert ,i,j,k\in \{1,2,\star \}\\ & \Vert G_y^{i,k}-G_y^{j,k}\Vert \le L_{\mathrm{xy}}\Vert x^i-x^j\Vert ,i,j,k\in \{1,2,\star \}\\ & {\mu }_F(\Vert x^1{\Vert }^2+\Vert y^1{\Vert }^2)\le ⟨G_x^{1,1},x^1⟩-⟨G_y^{1,1},y^1⟩,\\ & G_x^{\star ,\star }=0,G_y^{\star ,\star }=0.\end{array}$(16) ), we have $\frac{{\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2}{{\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2}\le \overline{\alpha },$and the proof is complete.

We obtained the linear convergence by using quadratic gradient growth in Theorem 3.3. The next theorem states that quadratic gradient growth property is also a sufficient condition for the linear convergence.

Theorem 3.4

If Algorithm 1 is linearly convergent for any initial point, then F has a quadratic gradient growth for some ${\mu }_F>0$.

Proof.

Let $(x^1,y^1)\in {\mathbb{R}}^n\times {\mathbb{R}}^m$ and $(x^2,y^2)$ be generated by Algorithm 1. Suppose that $(x^{\star },y^{\star })={\mathrm{\Pi }}_{S^{\star }}((x^2,y^2))$. As Algorithm 1 is linearly convergent, there exist $\alpha \in [0,1)$ with (18) $d_{S^{\star }}^2((x^2,y^2))\le \alpha d_{S^{\star }}^2((x^1,y^1))\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$(18) By setting $x^2=x^1-t{\mathrm{\nabla }}_{x}F(x^1,y^1)$ and $y^2=y^1+t{\mathrm{\nabla }}_{y}F(x^1,y^1)$ in inequality (18(18) $d_{S^{\star }}^2((x^2,y^2))\le \alpha d_{S^{\star }}^2((x^1,y^1))\le \alpha (\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2).$(18) ), we get $\frac{1-\alpha }{2t}(\Vert x^1-x^{\star }{\Vert }^2+\Vert y^1-y^{\star }{\Vert }^2)\le ⟨{\mathrm{\nabla }}_{x}F(x^1,y^1),x^1-x^{\star }⟩-⟨{\mathrm{\nabla }}_{y}F(x^1,y^1),y^1-y^{\star }⟩,$which implies that ${\mu }_F{d}_{S^{\star }}^2(x^1,y^1)\le ⟨{\mathrm{\nabla }}_{x}F(x^1,y^1),x^1-x^{\star }⟩-⟨{\mathrm{\nabla }}_{y}F(x^1,y^1),y^1-y^{\star }⟩,$for ${\mu }_F=\frac{1-\alpha }{2t}$ and the proof is complete.

4. Concluding remarks

In this study, we provided a new convergence rate for the gradient descent–ascent method for saddle point problems. Furthermore, we gave some necessary and sufficient conditions for the linear convergence without strong convexity. We employed performance estimation method for proving the results. For future work, it would be interesting to consider the case where the variables x and y in the saddle point problem are constrained to lie in given, compact convex sets, since many saddle point problems fall in this category. In this case, one could use the performance estimation framework to analyse other methods, e.g. proximal type algorithms.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the Dutch Scientific Council (NWO) grant OCENW.GROOT.2019.015, Optimization for and with Machine Learning (OPTIMAL).

Notes on contributors

Moslem Zamani

Moslem Zamani obtained his PhD degree from the University of Avignon and the University of Tehran. He worked as a postdoctoral researcher at Tilburg University. He is currently a researcher at UCLouvain. His main research interests include non-linear optimization and machine learning algorithms.

Hadi Abbaszadehpeivasti

Hadi Abbaszadehpeivasti earned his bachelor's degree in applied mathematics from the University of Zanjan and subsequently obtained master's degrees in industrial engineering from both Sharif University of Technology and Sabancı University. He is currently a PhD. student at Tilburg University, focusing on the complexity of first-order methods. His primary research interests include mathematical optimization and machine learning algorithms.

Etienne de Klerk

Etienne de Klerk obtained his PhD degree from the Delft University of Technology in The Netherlands in 1997. From January 1998 to September 2003, he held assistant professorships at the Delft University of Technology, and from September 2003 to September 2005 an associate professorship at the University of Waterloo, Canada, in the Department of Combinatorics & Optimization. In September 2004 he was appointed at Tilburg University, The Netherlands, first as an associate professor, and then as full professor (from June 2009). From August 29th, 2012, until August 31st, 2013, he was also appointed as full professor in the Division of Mathematics of the School of Physical and Mathematical Sciences at the Nanyang Technological University in Singapore. From September 1st, 2015 to August 31st 2019, he also held a part-time full professorship at the Delft University of Technology. Dr. De Klerk's main research interest is mathematical optimization, and, in particular, semidefinite programming.

Notes

1 The 100 random instances and starting points that we generated to produce Figure 1 may be found on GitHub; see: https://github.com/molsemzamani/Bilinear-Minimax.

Appendices

Appendix 1.

Non-negativity of multipliers in Theorem 2.2

Recall that, in the proof of Theorem 2.2, ${\gamma }_1$ is defined by ${\gamma }_1=\frac{t(t^2(2+L^2+\mathrm{L\mu })-t(3L+\mu )+(\mathrm{Lt}-1)\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2)}{\sqrt{(Lt+\mu t-2{)}^2+4t^2}}.$Since t is non-negative, we only need to prove that ${\hat{\gamma }}_1:=2t^2-3\mathrm{Lt}-\mathrm{\mu t}+(\mathrm{Lt}-1)\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+L^2{t}^2+\mathrm{L\mu }{t}^2+2$ is non-negative. We show that the following optimization problem is lower bounded by zero, $\begin{array}{rl}\underset{L,t,\mu }{min}& {\hat{\gamma }}_1\\ \mathrm{s}.\mathrm{t}.& L\ge \mu ,\mu \ge 0,t\ge 0,\end{array}$where $L,t,\mu$ are decision variables. First we consider the case that $\mathrm{Lt}-1\le 0$. We have the following optimization problem (A1) $\begin{array}{rl}\underset{L,t}{min}& (\underset{0\le \mu \le L}{min}2t^2+L^2{t}^2+\mathrm{L\mu }{t}^2-3\mathrm{Lt}-\mathrm{\mu t}+(\mathrm{Lt}-1)\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2)\\ \mathrm{s}.\mathrm{t}.& \mathrm{Lt}\le 1,L\ge \mu ,t\ge 0.\end{array}$(A1) The function ${\hat{\gamma }}_1$ is concave in μ, therefore, we just consider $\mu =0$ and $\mu =L$.

First we consider the case that $\mu =0$. By substituting $\mu =0$ in ${\hat{\gamma }}_1$ we have ${\hat{\gamma }}_1=2t^2+(\mathrm{Lt}-1)(\mathrm{Lt}-2+\sqrt{(\mathrm{Lt}-2{)}^2+4t^2}).$We argue that the above function is non-negative on the feasible set of problem (A1(A1) $\begin{array}{rl}\underset{L,t}{min}& (\underset{0\le \mu \le L}{min}2t^2+L^2{t}^2+\mathrm{L\mu }{t}^2-3\mathrm{Lt}-\mathrm{\mu t}+(\mathrm{Lt}-1)\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2)\\ \mathrm{s}.\mathrm{t}.& \mathrm{Lt}\le 1,L\ge \mu ,t\ge 0.\end{array}$(A1) ). By a conjugate multiplication of $\mathrm{Lt}-2+\sqrt{(\mathrm{Lt}-2{)}^2+4t^2}$ one has ${\hat{\gamma }}_1=2t^2(1-\frac{2(1-\mathrm{Lt})}{(2-\mathrm{Lt})+\sqrt{(\mathrm{Lt}-2{)}^2+4t^2}}),$since $(2-\mathrm{Lt})+\sqrt{(\mathrm{Lt}-2{)}^2+4t^2}\ge 2(2-\mathrm{Lt})$ we conclude that $0\le \frac{2(\mathrm{Lt}-1)}{(\mathrm{Lt}-2)+\sqrt{(\mathrm{Lt}-2{)}^2+4t^2}}\le 1$ which proves ${\hat{\gamma }}_1$ is non-negative.

Now we consider the case that $\mu =L$. By substituting $\mu =L$ we have ${\hat{\gamma }}_1=2t^2+2L^2{t}^2-4\mathrm{Lt}+2(\mathrm{Lt}-1)\sqrt{(\mathrm{Lt}-1{)}^2+t^2}+2.$Now we show that $\frac{1}{2}{\hat{\gamma }}_1=t^2+(\mathrm{Lt}-1)((\mathrm{Lt}-1)+\sqrt{(\mathrm{Lt}-1{)}^2+t^2})$ is non-negative on the given set. Note that, again by conjugate multiplication, $\frac{1}{2}{\hat{\gamma }}_1=t^2(1-\frac{(1-\mathrm{Lt})}{(1-\mathrm{Lt})+\sqrt{(\mathrm{Lt}-1{)}^2+t^2}}),$which always is non-negative due to the non-negativity of $(1-\mathrm{Lt})$.

Now we consider the case that tL−1>0. We have $\begin{array}{rl}{\hat{\gamma }}_1& =2t^2+L^2{t}^2+\mathrm{L\mu }{t}^2-3\mathrm{Lt}-\mathrm{\mu t}+(\mathrm{Lt}-1)\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2\\ & \ge 2t^2+L^2{t}^2+\mathrm{L\mu }{t}^2-3\mathrm{Lt}-\mathrm{\mu t}+(\mathrm{Lt}-1)|\mathrm{Lt}+\mathrm{\mu t}-2|+2.\end{array}$ Here, we need to consider two sub-cases. Firstly, when $2-\mathrm{Lt}-\mathrm{\mu t}\ge 0$, we have $2t^2+L^2{t}^2+\mathrm{L\mu }{t}^2-3\mathrm{Lt}-\mathrm{\mu t}+(\mathrm{Lt}-1)(2-\mathrm{Lt}-\mathrm{\mu t})+2-=2t^2\ge 0.$If $\mathrm{Lt}+\mathrm{\mu t}-2\ge 0$, we have $\begin{array}{rl}& 2t^2+L^2{t}^2+\mathrm{L\mu }{t}^2-3\mathrm{Lt}-\mathrm{\mu t}+(\mathrm{Lt}-1)(\mathrm{Lt\mu t}-2)+2\\ & =(\mathrm{Lt}-2{)}^2+(L-\mu )t+t^2+\mathrm{L\mu }{t}^2\ge 0,\end{array}$which completes the proof.

To show that ${\gamma }_2$ is non-negative we follow the same procedure. Recall the definition of ${\gamma }_2$ ${\gamma }_2=\frac{t(t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2)}{\sqrt{(Lt+\mu t-2{)}^2+4t^2}}.$We define ${\hat{\gamma }}_2$ as ${\hat{\gamma }}_2=t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2.$Due to $t\ge 0$, we only need to show that ${\hat{\gamma }}_2$ is non-negative. To this end, we show that the following optimization problem is lower bounded by zero. $\begin{array}{rl}\underset{L,t,\mu }{min}& {\hat{\gamma }}_2=t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2\\ \mathrm{s}.\mathrm{t}.& L\ge \mu ,\mu \ge 0,t\ge 0.\end{array}$First we consider the case that $1-\mathrm{\mu t}\ge 0$. We have ${\hat{\gamma }}_2\ge t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})|\mathrm{Lt}+\mathrm{\mu t}-2|+2.$We consider two sub-cases. Firstly, $\mathrm{Lt}+\mathrm{\mu t}-2\ge 0$: $\begin{array}{rl}{\hat{\gamma }}_2& =t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2\\ & \ge t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})(\mathrm{Lt}+\mathrm{\mu t}-2)+2=2t^2\ge 0.\end{array}$Now assume that $\mathrm{Lt}+\mathrm{\mu t}-2\le 0$. $\begin{array}{rl}{\hat{\gamma }}_2& =t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2\\ & \ge t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})(2-\mathrm{Lt}-\mathrm{\mu t})+2\\ & =2((\mathrm{\mu t}-1{)}^2+(2-\mathrm{\mu t}-\mathrm{Lt})+\mathrm{\mu L}{t}^2+t^2)\ge 0.\end{array}$Now we consider the case that $1-\mathrm{\mu t}\le 0$. $\begin{array}{rl}\underset{t,\mu }{min}& (\underset{\mu \le L\le \frac{2\mu -t}{\mathrm{\mu t}}}{min}{\hat{\gamma }}_2=t^2(2+{\mu }^2+\mathrm{L\mu })-t(3\mu +L)+(1-\mathrm{\mu t})\sqrt{(\mathrm{Lt}+\mathrm{\mu t}-2{)}^2+4t^2}+2)\\ \mathrm{s}.\mathrm{t}.& \mathrm{\mu t}\ge 1,\mu \ge 0,t\ge 0.\end{array}$Note that ${\hat{\gamma }}_2$ is concave with respect to the variable L. Therefore, we should study the boundaries of L. If we set $L=\mu$ we have $\begin{array}{rl}{\hat{\gamma }}_2& =2(t^2+{\mu }^2{t}^2-2\mathrm{\mu t}+(1-\mathrm{\mu t})\sqrt{(\mathrm{\mu t}-1{)}^2+t^2}+1)\\ & =2t^2+2(\mathrm{\mu t}-1)((\mathrm{\mu t}-1)-\sqrt{(\mathrm{\mu t}-1{)}^2+t^2}).\end{array}$ By conjugate multiplication, we have ${\hat{\gamma }}_2=2t^2(1-\frac{(\mathrm{\mu t}-1)}{\mathrm{\mu t}-1+\sqrt{(\mathrm{\mu t}-1{)}^2+t^2}})\ge 0.$By $L\le \frac{2\mu -t}{\mathrm{\mu t}}$ one can see that $L\le \frac{2}{t}$. Setting $L=\frac{2}{t}$: $\begin{array}{rl}{\hat{\gamma }}_2& =-\mathrm{\mu t}+2t^2+{\mu }^2{t}^2+(1-\mathrm{\mu t})\sqrt{4t^2+{\mu }^2{t}^2}\\ & =2t^2(1-\frac{2(\mathrm{\mu t}-1)}{\mathrm{\mu t}+\sqrt{{\mu }^2{t}^2+4t^2}})\ge 0.\end{array}$This completes the proof.

Appendix 2.

Identity used in the proof of Theorem 2.2

The proof of Theorem 2.2 requires the following identity, that may be verified through direct (symbolic) calculation:

$\begin{array}{rl}& {\Vert x^1-t{G}_x^{1,1}\Vert }^2+{\Vert y^1+t{G}_y^{1,1}\Vert }^2-\overline{\alpha }({\Vert x^1\Vert }^2+{\Vert y^1\Vert }^2)+{\gamma }_1(F^{1,1}-F^{\star ,1}-⟨G_x^{\star ,1},x^1⟩\\ & -\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_x^{1,1}-G_x^{\star ,1}\Vert }^2+\mu \Vert x^1{\Vert }^2-\frac{2\mu }{L}⟨G_x^{\star ,1}-G_x^{1,1},-x^1⟩))+{\gamma }_2(F^{\star ,1}-F^{1,1}\\ & +⟨G_x^{1,1},x^1⟩-\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_x^{\star ,1}-G_x^{1,1}\Vert }^2+\mu \Vert x^1{\Vert }^2-\frac{2\mu }{L}⟨G_x^{1,1}-G_x^{\star ,1},x^1⟩))+{\gamma }_2(F^{1,\star }\\ & -F^{\star ,\star }-\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_x^{1,\star }\Vert }^2+\mu {\Vert x^1\Vert }^2-\frac{2\mu }{L}⟨G_x^{1,\star },x^1⟩))+{\gamma }_1(F^{\star ,\star }-F^{1,\star }+⟨G_x^{1,\star },x^1⟩\\ & -\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_x^{1,\star }\Vert }^2+\mu {\Vert x^1\Vert }^2-\frac{2\mu }{L}⟨G_x^{1,\star },x^1⟩))+{\gamma }_1(F^{1,\star }-F^{1,1}+⟨G_y^{1,\star },y^1⟩-\frac{L}{2(L-\mu )}\\ & \times (\frac{1}{L}{\Vert G_y^{1,1}-G_y^{1,\star }\Vert }^2+\mu \Vert y^1{\Vert }^2-\frac{2\mu }{L}⟨G_y^{1,\star }-G_y^{1,1},y^1⟩))+{\gamma }_2(F^{1,1}-F^{1,\star }-⟨G_y^{1,1},y^1⟩\\ & -\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_y^{1,\star }-G_y^{1,1}\Vert }^2+\mu {\Vert y^1\Vert }^2-\frac{2\mu }{L}⟨-G_y^{1,1}+G_y^{1,\star },y^1⟩))+{\gamma }_2(-F^{\star ,1}+F^{\star ,\star }\\ & -\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_y^{\star ,1}\Vert }^2+\mu {\Vert y^1\Vert }^2-\frac{2\mu }{L}⟨G_y^{\star ,1},-y^1⟩))+{\gamma }_1(-F^{\star ,\star }+F^{\star ,1}+⟨G_y^{\star ,1},-y^1⟩\\ & -\frac{L}{2(L-\mu )}(\frac{1}{L}{\Vert G_y^{\star ,1}\Vert }^2+\mu {\Vert y^1\Vert }^2-\frac{2\mu }{L}⟨-G_y^{\star ,1},y^1⟩))+{\gamma }_3(\Vert x^1{\Vert }^2-{\Vert G_y^{1,1}-G_y^{\star ,1}\Vert }^2)\\ & +{\gamma }_3(\Vert x^1{\Vert }^2-{\Vert G_y^{1,\star }\Vert }^2)+{\gamma }_3({\Vert y^1\Vert }^2-{\Vert G_x^{1,1}-G_x^{1,\star }\Vert }^2)+{\gamma }_3(\Vert y^1{\Vert }^2-{\Vert G_x^{\star ,1}\Vert }^2)\\ & =-{\zeta }_1{\Vert x^1-{\zeta }_2{G}_x^{1,1}-{\zeta }_3(G_x^{1,\star }-G_x^{\star ,1})\Vert }^2-{\zeta }_4{\Vert G_x^{1,1}-G_x^{1,\star }-G_x^{\star ,1}\Vert }^2\\ & -{\zeta }_1{\Vert y^1+{\zeta }_2{G}_y^{1,1}-{\zeta }_3(G_y^{1,\star }-G_y^{\star ,1})\Vert }^2-{\zeta }_4{\Vert G_y^{1,1}-G_y^{\star ,1}-G_y^{1,\star }\Vert }^2,\end{array}$where ${\zeta }_1,{\zeta }_2,{\zeta }_3,{\zeta }_4$ are given by $\begin{array}{rl}{\zeta }_1& =\frac{1}{2}t(\frac{(L^2+{\mu }^2)\beta }{L-\mu }-\frac{2t^2(L-\mu )}{\beta }+(L+\mu )(t(L+\mu )-2)),\\ {\zeta }_2& =-\frac{(L^{2}t-L-{\mu }^{2}t+\mu )\beta -L^{2}t(\mathrm{Lt}+\mathrm{\mu t}-3)-(L+\mu )({\mu }^2{t}^2-2\mathrm{\mu t}+2t^2+2)+{\mu }^{2}t}{2t^2(L+\mu {)}^2(\mathrm{L\mu }+1)-8\mathrm{L\mu t}(L+\mu )+8\mathrm{L\mu }},\\ {\zeta }_3& =-\frac{t(L^2+6\mathrm{L\mu }+{\mu }^2)-2t^2(L+\mu )(\mathrm{L\mu }+1)-(L-\mu )\beta -2(L+\mu )}{2t^2(L+\mu {)}^2(\mathrm{L\mu }+1)-8\mathrm{L\mu t}(L+\mu )+8\mathrm{L\mu }},\\ {\zeta }_4& =\frac{t{(\beta +\mathrm{Lt}-\mathrm{\mu t})}^2}{4(L-\mu )\beta }.\end{array}$Note that ${\zeta }_1,{\zeta }_4\ge 0$, as required.