# Alternating Subgradient Methods for Convex-Concave Saddle-Point Problems

Hui Ouyang Department of Electrical Engineering, Stanford University

(May 24, 2023)

###### Abstract

We propose an alternating subgradient method with non-constant step sizes for
solving convex-concave saddle-point problems associated with general convex-
concave functions. We assume that the sequence of our step sizes is not
summable but square summable. Then under the popular assumption of uniformly
bounded subgradients, we prove that a sequence of convex combinations of
function values over our iterates converges to the value of the function at a
saddle-point. Additionally, based on our result regarding the boundedness of
the sequence of our iterates, we show that a sequence of the function
evaluated at convex combinations of our iterates also converges to the value
of the function over a saddle-point.

We implement our algorithms in examples of a linear program in inequality
form, a least-squares problem with $\ell_{1}$ regularization, a matrix game,
and a robust Markowitz portfolio construction problem. To accelerate
convergence, we reorder the sequence of step sizes in descending order, which
turned out to work very-well in our examples. Our convergence results are
confirmed by our numerical experiments. Moreover, we also numerically compare
our iterate scheme with iterates schemes associated with constant step sizes.
Our numerical results support our choice of step sizes. Additionally, we
observe the convergence of the sequence of function values over our iterates
in multiple experiments, which currently lacks theoretical support.

##  1 Introduction

In the whole work, $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ are Hilbert spaces
and $X\subseteq\mathcal{H}_{1}$ and $Y\subseteq\mathcal{H}_{2}$ are nonempty
closed and convex sets. The Hilbert direct sum
$\mathcal{H}_{1}\times\mathcal{H}_{2}$ of $\mathcal{H}_{1}$ and
$\mathcal{H}_{2}$ is equipped with the inner product

$\displaystyle(\forall(x,y)\in X\times Y)(\forall(u,v)\in X\times
Y)\quad\left\langle(x,y),(u,v)\right\rangle=\left\langle
x,u\right\rangle+\left\langle y,v\right\rangle$ (1.1)

and the induced norm

$\displaystyle(\forall(x,y)\in X\times
Y)\quad\left\lVert(x,y)\right\rVert^{2}=\left\langle(x,y),(x,y)\right\rangle=\left\langle
x,x\right\rangle+\left\langle y,y\right\rangle=\left\lVert
x\right\rVert^{2}+\left\lVert y\right\rVert^{2}.$ (1.2)

Throughout this work, $f:X\times Y\to\mathbf{R}\cup\\{-\infty,+\infty\\}$
satisfies that $(\forall y\in Y)$ $f(\cdot,y):X\to\mathbf{R}\cup\\{+\infty\\}$
is proper and convex, and that $(\forall x\in X)$
$f(x,\cdot):Y\to\mathbf{R}\cup\\{-\infty\\}$ is proper and concave. (It is
referred to as _convex-concave function_ from now on.)

In this work, we aim to solve the following _convex-concave saddle-point
problem_

$\displaystyle\underset{x\in X}{\operatorname{minimize}}~{}\,\underset{y\in
Y}{\operatorname{maximize}}~{}f(x,y).$ (1.3)

We assume that $(\forall(\bar{x},\bar{y})\in X\times Y)$
$\partial_{x}f(\bar{x},\bar{y})\neq\varnothing$ and
$\partial_{y}(-f(\bar{x},\bar{y}))\neq\varnothing$. We also suppose that the
solution set of 1.3 is nonempty, that is, there exists a _saddle-point_
$(x^{*},y^{*})\in X\times Y$ of $f$ satisfying

$\displaystyle(\forall x\in X)(\forall y\in Y)\quad f(x^{*},y)\leq
f(x^{*},y^{*})\leq f(x,y^{*}).$ (1.4)

###  1.1 Related work

Convex-concave saddle-point problems arise in a wide range of applications
such as resource allocation problems for networked-systems, game theory,
finance, robust and minimax optimization, image processing, generative
adversarial networks, adversarial training, robust optimization, primal-dual
reinforcement learning, and machine learning (see, e.g., [9], [4], [12], [6],
[13], and [14] for details). Based on the easy implementation, low memory
requirement, and low barrier for usage, the subgradient method is one of the
most popular methods for solving convex-concave saddle-point problems.

For interested readers, we recommend [9, Section 1] with a summary of various
subgradient methods for solving convex-concave saddle-point problems and [13,
Section 3] with a list of different algorithms and literature on solving
special cases or more general versions of convex-concave saddle-point
problems. Among the literature on subgradient methods for solving convex-
concave saddle-point problems, the author in [10] proposed a primal-dual
subgradient method with two control sequences (one aggregates the support
functions in the dual space, and the other establishes a dynamically updated
scale between the primal and dual spaces) for different types of nonsmooth
problems with convex structure. Moreover, the author provides a variant of the
proposed subgradient scheme for convex-concave saddle-point problems in [10,
Section 4], and shows an upper bound on a sequence constructed by their
iterates under some assumptions, including the existence of certain strongly
convex prox-functions and the uniform boundedness of subgradients. In
addition, the authors of [12] worked on saddle problems including the partial
supremum or infimum of convex-concave functions, which is a more general
version of the convex-concave saddle-point problem considered in this work.
They applied the language and methods presented in [8], used the idea of
conic-representable saddle-point programs to automatically reduce a saddle
problem to a single convex optimization problem, and developed an open-source
package called DSP for users to easily formulate and solve saddle problems.

###  1.2 Comparison with related work

Main theoretical results in this work are mainly inspired by [9, Section 3] by
Nedić and Ozdaglar and [1, Section 6] by Boyd. In [9, Section 3], the authors
worked on a subgradient algorithm with an averaging scheme for generating
approximate saddle-points of a convex-concave function. They also showed the
convergence of function values at iterate averages to the the function value
at a saddle-point, with the error level being a function of the step-size
value, under some assumptions regarding the boundedness of the sequence of
iterates or compactness of related sets. [1] is a lecture note by Boyd for the
course EE364b in Stanford University, which covers various subgradient methods
and techniques of their convergence proofs. Convex-concave saddle-point
problems are not considered in [1] yet. Here, we apply some convergence proofs
techniques and popular assumptions on sequences of step sizes, as presented in
[1]. We state main differences between this work and [9] below.

  * •

Our iterate scheme 3.1 replaces the constant step-size $\alpha$ in the iterate
scheme worked in [9] by a sequence $(t_{k})_{k\in\mathbf{N}}$.

  * •

Under some boundedness of the sequence of iterates or compactness of related
sets, authors in [9, Section 3] considered the convergence of
$\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\to f(x^{*},y^{*})$ and
$f(\tfrac{1}{k}\sum^{k-1}_{i=0}x^{i},\tfrac{1}{k}\sum^{k-1}_{i=0}y^{i})\to
f(x^{*},y^{*})$, where $(x^{*},y^{*})$ is a saddle-point of $f$ and
$\left((x^{k},y^{k})\right)_{k\in\mathbf{N}}$ is generated by the iterate
scheme 3.1 below with $(\forall k\in\mathbf{N})$
$t_{k}\equiv\alpha\in\mathbf{R}_{++}$.

In this work, we directly establish the boundedness of the sequence
$((x^{k},y^{k}))_{k\in\mathbf{N}}$ of iterates generated by our scheme 3.1. So
without any assumption on the boundedness of the sequence of iterates or
compactness of related sets, we prove
$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\to
f(x^{*},y^{*})$ in Theorem 3.1 and
$f\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}x^{i},\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}y^{i}\right)\to
f(x^{*},y^{*})$ in Theorem 3.2.

  * •

In [9], after section 3, by replacing the second projector in their original
iterate scheme with a projector onto a compact convex set containing the set
of dual optimal solutions, the authors introduced their primal-dual
subgradient method; moreover, under some standard Slater constraint
qualification and uniformly boundedness assumption of related subgradients,
the authors theoretically studied the estimate on the convergence rate of
generated primal sequences for finding approximate primal-dual optimal
solutions as approximate saddle points of the Lagrangian function of a convex
constrained optimization problem.

Although we don’t theoretically work on finding saddle-points of Lagrangian
(which are special cases of convex-concave functions), we numerically apply
our algorithm to Lagrangian functions of linear program in inequality form and
of least-squares problem with $\ell_{1}$ regularization in Sections 4.2 and
4.3. Furthermore, in Sections 4.4 and 4.5, we also numerically confirm our
theoretical results with problems of matrix game and robust Markowitz
portfolio construction problem. In addition, we also apply our algorithm to
another Lagrangian of an easy constrained convex problem in Section 4.1 to
show the importance or benefit of replacing the constant step-size $\alpha$
with a sequence $(t_{k})_{k\in\mathbf{N}}$ satisfying some popular constraints
of step sizes.

###  1.3 Outline

We mainly present some examples of convex-concave saddle-point problems in
Section 2. In Section 3, we introduce our alternating subgradient methods for
convex-concave saddle-point problems associated with a general convex-concave
function. Then in the same section, we prove two desired results on the
convergence to the value of function over a saddle-point. In Section 4, we
implement our algorithm and compare it to some other schemes of iterates in
examples of the following problems: linear program in inequality form, least-
squares problem with $\ell_{1}$ regularization, matrix game, and robust
Markowitz portfolio construction problem. To accelerate convergence, in our
numerical experiments, we reorder the sequence $(t_{k})_{k\in\mathbf{N}}$ of
step sizes in descending order, which turns out to work very-well in our
examples. We sum up our work in Section 5.

##  2 Preliminaries

We point out some notation used in this work below. $\mathbf{R}$,
$\mathbf{R}_{+}$, $\mathbf{R}_{++}$, and $\mathbf{N}$ are the set of all real
numbers, the set of all nonnegative real numbers, the set of all positive real
numbers, and the set of all nonnegative integers, respectively. Let $C$ be a
nonempty closed and convex subset of $\mathcal{H}$. The _projector_ (or
_projection operator_) onto $C$ is the operator, denoted by
$\operatorname{P}_{C}$, that maps every point in $\mathcal{H}$ to its unique
projection onto $C$, that is, $(\forall x\in\mathcal{H})$ $\left\lVert
x-\operatorname{P}_{C}x\right\rVert=\inf_{c\in C}\left\lVert x-c\right\rVert$.
Let $\mathcal{H}$ be a Hilbert space and let
$g:\mathcal{H}\to\left]-\infty,+\infty\right]$ be proper. The _subdifferential
of $g$_ is the set-valued operator

$\partial g:\mathcal{H}\to
2^{\mathcal{H}}:x\mapsto\\{u\in\mathcal{H}~{}:~{}(\forall
y\in\mathcal{H})~{}\left\langle u,y-x\right\rangle+f(x)\leq f(y)\\}.$

The following result is well-known and will be used several times later. For
completeness, we show some details below.

######  Fact 2.1.

Let $(\bar{x},\bar{y})\in X\times Y$. The following statements are equivalent.

  1. (i)

$(\bar{x},\bar{y})$ is a saddle-point of the function $f$.

  2. (ii)

$(\forall(x,y)\in X\times Y)$ $f(\bar{x},y)-f(x,\bar{y})\leq 0$.

  3. (iii)

$0\in\partial_{x}f(\bar{x},\bar{y})$ and
$0\in\partial_{y}(-f(\bar{x},\bar{y}))$.

###### Proof.

(i) $\Leftrightarrow$ (ii): This is trivial by recalling the definition 1.4 of
the saddle-point.

(i) $\Leftrightarrow$ (iii): According to the definition of saddle-point 1.4,
we observe that (i) is equivalent to the following

$(\forall x\in X)~{}\left\langle
0,x-\bar{x}\right\rangle+f(\bar{x},\bar{y})\leq f(x,\bar{y})\text{ and
}(\forall y\in Y)~{}\left\langle
0,y-\bar{y}\right\rangle+(-f(\bar{x},\bar{y}))\leq-f(\bar{x},y),$

which is exactly (iii). ∎

We present some examples of saddle-points below.

######  Example 2.1.

Let $(\forall i\in\\{1,2\\})$ $f_{i}:\mathcal{H}_{i}\to\mathbf{R}$ be proper,
convex, and differentiable function. Define
$f:\mathcal{H}_{1}\times\mathcal{H}_{2}\to\mathbf{R}$ as
$(\forall(x,y)\in\mathcal{H}_{1}\times\mathcal{H}_{2})$
$f(x,y)=f_{1}(x)-f_{2}(y)$. Let
$(\bar{x},\bar{y})\in\mathcal{H}_{1}\times\mathcal{H}_{2}$. Then, by Fact 2.1,
$(\bar{x},\bar{y})$ is a saddle-point of the function $f$ if and only if
$0=\nabla f_{1}(\bar{x})$ and $0=\nabla f_{2}(\bar{y})$.

We shall revisit examples below in Section 4 on numerical experiments.

######  Example 2.2 (Lagrange duality).

Note that when strong duality holds, a pair of primal and dual optimal points
turns out to be a saddle-point; and the value of the Lagrangian over a saddle-
point equals to both the optimal solutions of corresponding primal and dual
problems. We display Lagrangian of some problems for which strong duality
obtains below.

  1. (i)

[4, Exercise 5.1] Consider the primal problem

$\displaystyle\operatorname{minimize}~{}x^{2}+1$ (P1)
$\displaystyle\operatorname{subject~{}to}~{}(x-2)(x-4)\leq 0,$

with variable $x\in\mathbf{R}$. The corresponding Lagrangian
$L:\mathbf{R}\times\mathbf{R}_{+}\to\mathbf{R}$ is

$\makebox[0.0pt][r]{(L${}_{1}$)\hskip
20.00003pt}L(x,y)=x^{2}+1+y(x-2)(x-4)=x^{2}(1+y)-6xy+8y+1,$

and the dual problem is

$\displaystyle\operatorname{maximize}~{}10-y-\frac{9}{y+1}$ (D1)
$\displaystyle\operatorname{subject~{}to}~{}y\geq 0,$

with variable $y\in\mathbf{R}$. It is easy to know that the primal and dual
optimal points are $x^{*}=2$ and $y^{*}=2$, respectively, and that the primal
and dual optimal values are $p^{*}=d^{*}=5$. Then we deduce that
$(x^{*},y^{*})=(2,2)$ is a saddle-point of the function $L(x,y)$ and that

$\sup_{y\in\mathbf{R}_{+}}\inf_{x\in\mathbf{R}}L(x,y)=L(2,2)=5=\inf_{x\in\mathbf{R}}\sup_{y\in\mathbf{R}_{+}}L(x,y).$

  2. (ii)

[4, Section 5.2.1] Consider the inequality form LP

$\displaystyle\operatorname{minimize}~{}c^{T}x$ (P2)
$\displaystyle\operatorname{subject~{}to}~{}Ax\leq b,$

where $x\in\mathbf{R}^{n}$ is the variable, and $A\in\mathbf{R}^{m\times n}$,
$c\in\mathbf{R}^{n}$, and $b\in\mathbf{R}^{m}$. As it is stated on [4, Page
225], the Lagrangian $L:\mathbf{R}^{n}\times\mathbf{R}^{m}_{+}\to\mathbf{R}$
is

$\makebox[0.0pt][r]{(L${}_{2}$)\hskip
20.00003pt}L(x,y)=c^{T}x+y^{T}(Ax-b)=-b^{T}y+(A^{T}y+c)^{T}x=y^{T}Ax+c^{T}x-b^{T}y,$

and the dual problem is

$\displaystyle\operatorname{maximize}~{}-b^{T}y$ (D2)
$\displaystyle\operatorname{subject~{}to}~{}y\geq 0$
$\displaystyle\quad\quad\quad\quad\quad A^{T}y+c=0,$

with variable $y\in\mathbf{R}^{m}$. Suppose that $x^{*}$ and $y^{*}$ are the
optimal points of (P2) and (D2), respectively. It is clear that Slater’s
condition holds, so $(x^{*},y^{*})$ is a saddle-point of the function $L(x,y)$
and that

$\sup_{y\in\mathbf{R}^{m}_{+}}\inf_{x\in\mathbf{R}^{n}}L(x,y)=L(x^{*},y^{*})=\inf_{x\in\mathbf{R}^{n}}\sup_{y\in\mathbf{R}^{m}_{+}}L(x,y).$

  3. (iii)

[5, Exercise 5.34(b)] Consider the following least-squares problem with
$\ell_{1}$ regularization

$\operatorname{minimize}~{}\frac{1}{2}\left\lVert
Ax-b\right\rVert^{2}_{2}+\gamma\left\lVert x\right\rVert_{1}$

where $x\in\mathbf{R}^{n}$ is the variable, and $A\in\mathbf{R}^{m\times n}$,
$b\in\mathbf{R}^{m}$, and $\gamma\in\mathbf{R}_{++}$. Clearly, it is
equivalent to

$\displaystyle\operatorname{minimize}~{}\frac{1}{2}\left\lVert
u\right\rVert^{2}_{2}+\gamma\left\lVert x\right\rVert_{1}$ (P3)
$\displaystyle\operatorname{subject~{}to}~{}u=Ax-b.$

The corresponding Lagrangian
$L:\mathbf{R}^{n}\times\mathbf{R}^{m}\times\mathbf{R}^{m}\to\mathbf{R}$ is

$\displaystyle\makebox[0.0pt][r]{(L${}_{3}$)\hskip 20.00003pt}L(x,u,y)=$
$\displaystyle\frac{1}{2}\left\lVert u\right\rVert^{2}_{2}+\gamma\left\lVert
x\right\rVert_{1}+y^{T}(Ax-b-u)$ $\displaystyle=$ $\displaystyle
y^{T}\begin{pmatrix}A&-I\end{pmatrix}\begin{pmatrix}x\\\
u\end{pmatrix}+\frac{1}{2}\left\lVert u\right\rVert^{2}_{2}+\gamma\left\lVert
x\right\rVert_{1}-y^{T}b.$

Note that

$\displaystyle\inf_{x\in\mathbf{R}^{n},u\in\mathbf{R}^{m}}L(x,u,y)=$
$\displaystyle\inf_{x\in\mathbf{R}^{n},u\in\mathbf{R}^{m}}\frac{1}{2}\left\lVert
u\right\rVert^{2}_{2}+\gamma\left\lVert x\right\rVert_{1}+y^{T}(Ax-b-u)$
$\displaystyle=$
$\displaystyle-b^{T}y+\inf_{x\in\mathbf{R}^{n}}\left((A^{T}y)^{T}x+\gamma\left\lVert
x\right\rVert_{1}\right)+\inf_{u\in\mathbf{R}^{m}}\left(-y^{T}u+\frac{1}{2}\left\lVert
u\right\rVert^{2}_{2}\right),$

that, by [4, Section 5.1.6 and Example 3.26],

$\displaystyle\inf_{x\in\mathbf{R}^{n}}(A^{T}y)^{T}x+\gamma\left\lVert
x\right\rVert_{1}=$
$\displaystyle-\gamma\sup_{x\in\mathbf{R}^{n}}-\frac{1}{\gamma}(A^{T}y)^{T}x-\left\lVert
x\right\rVert_{1}$ $\displaystyle=$ $\displaystyle\begin{cases}0\quad&\text{if
}\left\lVert-\frac{1}{\gamma}A^{T}y\right\rVert_{\infty}\leq 1\\\
-\infty\quad&\text{otherwise},\end{cases}$

and that

$\inf_{u\in\mathbf{R}^{m}}-y^{T}u+\frac{1}{2}\left\lVert
u\right\rVert^{2}_{2}=\frac{1}{2}\inf_{u\in\mathbf{R}^{m}}\left\lVert
u-y\right\rVert^{2}_{2}-\frac{1}{2}\left\lVert
y\right\rVert^{2}_{2}=-\frac{1}{2}\left\lVert y\right\rVert^{2}_{2}.$

We derive that

$\inf_{x\in\mathbf{R}^{n},u\in\mathbf{R}^{m}}L(x,u,y)=-b^{T}y+\frac{1}{2}\left\lVert
y\right\rVert^{2}_{2},$

with $\left\lVert A^{T}y\right\rVert_{\infty}\leq\gamma$, and that the dual
problem is

$\displaystyle\operatorname{maximize}~{}-b^{T}y+\frac{1}{2}\left\lVert
y\right\rVert^{2}_{2}$ (D3)
$\displaystyle\operatorname{subject~{}to}~{}\left\lVert
A^{T}y\right\rVert_{\infty}\leq\gamma,$

with variable $y\in\mathbf{R}^{m}$. Suppose that $(x^{*},u^{*})$ and $y^{*}$
are the optimal points of (P3) and (D3), respectively. In view of Slater’s
theorem, $((x^{*},u^{*}),y^{*})$ is s a saddle-point of the function
$L((x,u),y)$ and that

$\sup_{y\in\mathbf{R}^{m}}\inf_{x\in\mathbf{R}^{n},u\in\mathbf{R}^{m}}L((x,u),y)=L((x^{*},u^{*}),y^{*})=\inf_{x\in\mathbf{R}^{n},u\in\mathbf{R}^{m}}\sup_{y\in\mathbf{R}^{m}}L((x,u),y).$

##  3 Alternating subgradient methods

Results in this section are inspired by [9, Section 3] by Nedić and Ozdaglar
and [1] by Boyd for the course EE364b in Stanford University. In particular,
the technique in the proof of Theorem 3.1 mimics that in [9, Section 3]. The
authors in [9, Section 3] considered the convergence of
$\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\to f(x^{*},y^{*})$ and
$f(\tfrac{1}{k}\sum^{k-1}_{i=0}x^{i},\tfrac{1}{k}\sum^{k-1}_{i=0}y^{i})\to
f(x^{*},y^{*})$ under some assumptions including boundedness or compactness,
where $(x^{*},y^{*})$ is a saddle-point of $f$ and
$\left((x^{k},y^{k})\right)_{k\in\mathbf{N}}$ is generated by 3.1 below with
$(\forall k\in\mathbf{N})$ $t_{k}\equiv\alpha\in\mathbf{R}_{++}$. In addition,
the proof of the boundedness of the iteration sequence
$\left((x^{k},y^{k})\right)_{k\in\mathbf{N}}$ in Lemma 3.4 is motivated from
[1, Section 6], which is essential to our convergence result in Theorem 3.2.

###  3.1 Algorithm

Let $(x^{0},y^{0})\in X\times Y$. We consider the sequence of iterations
generated by

$\displaystyle(\forall k\in\mathbf{N})\quad
x^{k+1}=\operatorname{P}_{X}(x^{k}-t_{k}g_{k})\quad\text{and}\quad
y^{k+1}=\operatorname{P}_{Y}(y^{k}-t_{k}h_{k}),$ (3.1)

where $\operatorname{P}_{X}$ and $\operatorname{P}_{Y}$ are projectors onto
$X$ and $Y$, respectively, $(\forall k\in\mathbf{N})$
$g_{k}\in\partial_{x}f(x^{k},y^{k})$ and
$h_{k}\in\partial_{y}(-f(x^{k},y^{k}))$, and $(\forall
k\in\mathbf{N}\smallsetminus\\{0\\})$ $t_{k}\in\mathbf{R}_{+}$ and
$t_{0}\in\mathbf{R}_{++}$.

Let’s revisit the Lagrangian function of a least-squares problem with
$\ell_{1}$ regularization, presented in Example 2.2(iii), and illustrate the
algorithm 3.1 on this particular function.

######  Example 3.1.

Consider the convex-concave function
$f:\mathbf{R}^{n+m}\times\mathbf{R}^{m}\to\mathbf{R}$ defined as

$(\forall((x,u),y)\in\mathbf{R}^{n+m}\times\mathbf{R}^{m})\quad
f((x,u),y)=\frac{1}{2}\left\lVert u\right\rVert^{2}_{2}+\gamma\left\lVert
x\right\rVert_{1}+y^{T}(Ax-b-u).$

In view of [2, Section 3.4],

$(\forall x\in\mathbf{R}^{n})\quad{\mbox{\bf sign}}(x)\in\partial\left\lVert
x\right\rVert_{1},\quad\text{where}\quad(\forall
i\in\\{1,\ldots,n\\})~{}({\mbox{\bf
sign}}(x))_{i}=\begin{cases}1\quad&\text{if }x_{i}>0\\\ 0\quad&\text{if
}x_{i}=0\\\ -1\quad&\text{if }x_{i}<0.\end{cases}$

Therefore, it is easy to see that in this case, the algorithm 3.1 is simply
that $((x_{0},Ax_{0}-b),y_{0}))\in\mathbf{R}^{n+m}\times\mathbf{R}^{m}$ and
for every $k\in\mathbf{N}$,

$\displaystyle(x^{k+1},u^{k+1})=$
$\displaystyle(x^{k},u^{k})-t_{k}\left(A^{T}y^{k}+\gamma{\mbox{\bf
sign}}(x^{k}),-y^{k}+u^{k}\right)$ $\displaystyle y^{k+1}=$ $\displaystyle
y^{k}-t_{k}\left(-Ax^{k}+u^{k}+b\right).$

###  3.2 Convergence results

Henceforth, $((x^{k},y^{k}))_{k\in\mathbf{N}}$ is constructed by our iterate
scheme 3.1; moreover,

$(\forall
k\in\mathbf{N})\quad\hat{x}_{k}=\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}x^{i}\text{
and }\hat{y}_{k}=\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}y^{i},$

where $(\forall k\in\mathbf{N}\smallsetminus\\{0\\})$ $t_{k}\in\mathbf{R}_{+}$
and $t_{0}\in\mathbf{R}_{++}$ are step sizes used in our iterate scheme 3.1.

Suppose $(x^{*},y^{*})\in X\times Y$ is a saddle point of a convex-concave
function $f$. In this subsection, we present convergence results Theorems 3.1
and 3.2 on $\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\to
f(x^{*},y^{*})$ and $f(\hat{x}_{k},\hat{y}_{k})\to f(x^{*},y^{*})$,
respectively. To this end, we need the following auxiliary results.

######  Lemma 3.1.

Let $x\in X$ and $y\in Y$. The following results hold.

  1. (i)

For every $k\in\mathbf{N}$,

$\displaystyle
t_{k}(f(x^{k},y^{k})-f(x,y^{k}))\leq\tfrac{1}{2}\left(\left\lVert
x^{k}-x\right\rVert^{2}-\left\lVert
x^{k+1}-x\right\rVert^{2}\right)+\tfrac{1}{2}t_{k}^{2}\left\lVert
g_{k}\right\rVert^{2};$ (3.2a) $\displaystyle
t_{k}(f(x^{k},y)-f(x^{k},y^{k}))\leq\tfrac{1}{2}\left(\left\lVert
y^{k}-y\right\rVert^{2}-\left\lVert
y^{k+1}-y\right\rVert^{2}\right)+\tfrac{1}{2}t_{k}^{2}\left\lVert
h_{k}\right\rVert^{2}.$ (3.2b)

  2. (ii)

For every $k\in\mathbf{N}$,

$\displaystyle\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x,\hat{y}_{k})\leq\frac{\left\lVert
x^{0}-x\right\rVert^{2}-\left\lVert
x^{k+1}-x\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}};$ (3.3a) $\displaystyle
f(\hat{x}_{k},y)-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\leq\frac{\left\lVert
y^{0}-y\right\rVert^{2}-\left\lVert
y^{k+1}-y\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}.$ (3.3b)

###### Proof.

(i): Let $k\in\mathbf{N}$. Because $g_{k}\in\partial_{x}f(x^{k},y^{k})$ and
$h_{k}\in\partial_{y}(-f(x^{k},y^{k}))$, we have that

$\displaystyle(\forall x\in X)\quad\left\langle g_{k},x-x^{k}\right\rangle\leq
f(x,y^{k})-f(x^{k},y^{k});$ (3.4a) $\displaystyle(\forall y\in
Y)\quad\left\langle h_{k},y-y^{k}\right\rangle\leq-f(x^{k},y)+f(x^{k},y^{k}).$
(3.4b)

Note that $x=\operatorname{P}_{X}x$ and $\operatorname{P}_{X}$ is
nonexpansive. According to 3.1,

$\displaystyle\left\lVert x^{k+1}-x\right\rVert^{2}=$
$\displaystyle\left\lVert\operatorname{P}_{X}(x^{k}-t_{k}g_{k})-\operatorname{P}_{X}x\right\rVert^{2}$
$\displaystyle\leq$ $\displaystyle\left\lVert
x^{k}-t_{k}g_{k}-x\right\rVert^{2}$ $\displaystyle=$ $\displaystyle\left\lVert
x^{k}-x\right\rVert^{2}-2t_{k}\left\langle
g_{k},x^{k}-x\right\rangle+t_{k}^{2}\left\lVert g_{k}\right\rVert^{2}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:gkineq}}}{{\leq}}$
$\displaystyle\left\lVert
x^{k}-x\right\rVert^{2}-2t_{k}(f(x^{k},y^{k})-f(x,y^{k}))+t_{k}^{2}\left\lVert
g_{k}\right\rVert^{2},$

which implies 3.2a.

Similarly, employing 3.1 again and $y=\operatorname{P}_{Y}y$ in the first
equality below and applying the fact that $\operatorname{P}_{Y}$ is
nonexpansive in the first inequality below, we have that

$\displaystyle\left\lVert y^{k+1}-y\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\left\lVert\operatorname{P}_{Y}(y^{k}-t_{k}h_{k})-\operatorname{P}_{Y}y\right\rVert^{2}$
$\displaystyle\leq$ $\displaystyle\left\lVert
y^{k}-t_{k}h_{k}-y\right\rVert^{2}$ $\displaystyle=$ $\displaystyle\left\lVert
y^{k}-y\right\rVert^{2}-2t_{k}\left\langle
h_{k},y^{k}-y\right\rangle+t_{k}^{2}\left\lVert h_{k}\right\rVert^{2}$
$\displaystyle\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:hkineq}}}{{\leq}}$
$\displaystyle\left\lVert
y^{k}-y\right\rVert^{2}-2t_{k}(f(x^{k},y)-f(x^{k},y^{k}))+t_{k}^{2}\left\lVert
h_{k}\right\rVert^{2},$

which yields 3.2b.

(ii): Let $k\in\mathbf{N}$. Because $f(x,\cdot)$ is concave and $f(\cdot,y)$
is convex, we observe that

$\displaystyle\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x,y^{i})\leq
f\left(x,\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}y^{i}\right)=f(x,\hat{y}_{k});$
(3.5a)
$\displaystyle\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y)\geq
f\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}x^{i},y\right)=f(\hat{x}_{k},y).$
(3.5b)

Sum 3.2a over $i\in\\{0,1,\ldots,k\\}$ to get that

$\sum^{k}_{i=0}t_{i}(f(x^{i},y^{i})-f(x,y^{i}))\leq\tfrac{1}{2}(\left\lVert
x^{0}-x\right\rVert^{2}-\left\lVert
x^{k+1}-x\right\rVert^{2})+\tfrac{1}{2}\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}.$

Divide both sides of the inequality above by $\sum^{k}_{j=0}t_{j}$ to see that

$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x,y^{i})\leq\frac{\left\lVert
x^{0}-x\right\rVert^{2}-\left\lVert
x^{k+1}-x\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}},$

which, combining with 3.5a, derives 3.3a.

Similarly, sum 3.2b over $i\in\\{0,1,\ldots,k\\}$ to get that

$\sum^{k}_{i=0}t_{i}(f(x^{i},y)-f(x^{i},y^{i}))\leq\tfrac{1}{2}(\left\lVert
y^{0}-y\right\rVert^{2}-\left\lVert
y^{k+1}-y\right\rVert^{2})+\tfrac{1}{2}\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}.$

Divide also both sides of the inequality above by $\sum^{k}_{j=0}t_{j}$ to get
that

$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y)-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\leq\frac{\left\lVert
y^{0}-y\right\rVert^{2}-\left\lVert
y^{k+1}-y\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}},$

which, connecting with 3.5b, establishes 3.3b. ∎

######  Lemma 3.2.

Let $(x^{*},y^{*})\in X\times Y$ be a solution of 1.3, and let
$k\in\mathbf{N}$. The following results hold.

  1. (i)

$-\frac{\left\lVert x^{0}-\hat{x}_{k}\right\rVert^{2}-\left\lVert
x^{k+1}-\hat{x}_{k}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}\leq
f(\hat{x}_{k},\hat{y}_{k})-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\leq\frac{\left\lVert
y^{0}-\hat{y}_{k}\right\rVert^{2}-\left\lVert
y^{k+1}-\hat{y}_{k}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}$. Consequently,

$-\frac{\left\lVert
x^{0}-\hat{x}_{k}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}\leq
f(\hat{x}_{k},\hat{y}_{k})-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\leq\frac{\left\lVert
y^{0}-\hat{y}_{k}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}.$

  2. (ii)

$-\frac{\left\lVert y^{0}-y^{*}\right\rVert^{2}-\left\lVert
y^{k+1}-y^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}\leq\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x^{*},y^{*})\leq\frac{\left\lVert
x^{0}-x^{*}\right\rVert^{2}-\left\lVert
x^{k+1}-x^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}$. Consequently,

$-\frac{\left\lVert
y^{0}-y^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}\leq\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x^{*},y^{*})\leq\frac{\left\lVert
x^{0}-x^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}.$

  3. (iii)

$-\frac{\left\lVert x^{0}-\hat{x}_{k}\right\rVert^{2}+\left\lVert
y^{0}-y^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{\sum^{k}_{i=0}t_{i}^{2}(\left\lVert
g_{i}\right\rVert^{2}+\left\lVert
h_{i}\right\rVert^{2})}{2\sum^{k}_{j=0}t_{j}}\leq
f(\hat{x}_{k},\hat{y}_{k})-f(x^{*},y^{*})\leq\frac{\left\lVert
x^{0}-x^{*}\right\rVert^{2}+\left\lVert
y^{0}-\hat{y}_{k}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}(\left\lVert
g_{i}\right\rVert^{2}+\left\lVert
h_{i}\right\rVert^{2})}{2\sum^{k}_{j=0}t_{j}}$.

###### Proof.

(i): Substitute $x$ in 3.3a of Lemma 3.1 with $\hat{x}_{k}$ to observe that

$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(\hat{x}_{k},\hat{y}_{k})\leq\frac{\left\lVert
x^{0}-\hat{x}_{k}\right\rVert^{2}-\left\lVert
x^{k+1}-\hat{x}_{k}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}.$

Replace $y$ in 3.3b of Lemma 3.1 by $\hat{y}_{k}$ to get that

$f(\hat{x}_{k},\hat{y}_{k})-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\leq\frac{\left\lVert
y^{0}-\hat{y}_{k}\right\rVert^{2}-\left\lVert
y^{k+1}-\hat{y}_{k}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}.$

Combine the last two inequalities to deduce the desired inequality in (i).

(ii): Note that $(x^{k})_{k\in\mathbf{N}}$ and $(y^{k})_{k\in\mathbf{N}}$ are
sequences in $X$ and $Y$, respectively, and that $X$ and $Y$ are convex. We
know that $\hat{x}_{k}\in X$ and $\hat{y}_{k}\in Y$. Recall that
$(x^{*},y^{*})\in X\times Y$ is a solution of 1.3. Employing 1.4, we obtain
that

$\displaystyle f(x^{*},\hat{y}_{k})\leq f(x^{*},y^{*});$ (3.6a) $\displaystyle
f(x^{*},y^{*})\leq f(\hat{x}_{k},y^{*}).$ (3.6b)

Set $x=x^{*}$ in 3.3a to get that

$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x^{*},\hat{y}_{k})\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:ineqhatxkhatyk:x}}}{{\leq}}\frac{\left\lVert
x^{0}-x^{*}\right\rVert^{2}-\left\lVert
x^{k+1}-x^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}},$

which, connecting with 3.6a, derives

$\displaystyle\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x^{*},y^{*})\leq\frac{\left\lVert
x^{0}-x^{*}\right\rVert^{2}-\left\lVert
x^{k+1}-x^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}},$ (3.7)

Similarly, setting $y=y^{*}$ in 3.3b, we have that

$f(\hat{x}_{k},y^{*})-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\stackrel{{\scriptstyle\lx@cref{creftype~refnum}{eq:ineqhatxkhatyk:y}}}{{\leq}}\frac{\left\lVert
y^{0}-y^{*}\right\rVert^{2}-\left\lVert
y^{k+1}-y^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}},$

which, combining with 3.6b, entails

$\displaystyle
f(x^{*},y^{*})-\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\leq\frac{\left\lVert
y^{0}-y^{*}\right\rVert^{2}-\left\lVert
y^{k+1}-y^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}.$ (3.8)

Combine 3.7 and 3.8 to reach the required inequality in (ii).

(iii): This follows immediately from (i) and (ii) above. ∎

The following result is inspired by [9, Proposition 3.1] in which, under some
extra boundedness or compactness assumptions, the authors considered the
convergence $\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\to f(x^{*},y^{*})$ and
$f(\tfrac{1}{k}\sum^{k-1}_{i=0}x^{i},\tfrac{1}{k}\sum^{k-1}_{i=0}y^{i})\to
f(x^{*},y^{*})$, where $(x^{*},y^{*})$ is a saddle-point of $f$ and
$\left((x^{k},y^{k})\right)_{k\in\mathbf{N}}$ is generated by 3.1 with
$(\forall k\in\mathbf{N})$ $t_{k}\equiv\alpha\in\mathbf{R}_{++}$.

######  Theorem 3.1.

Let $(x^{*},y^{*})\in X\times Y$ be a solution of 1.3. Let $R$, $G$, and $S$
be in $\mathbf{R}_{++}$. Suppose that

$\displaystyle\left\lVert(x^{0},y^{0})\right\rVert\leq
R,\quad\left\lVert(x^{*},y^{*})\right\rVert\leq R,\quad\text{and}\quad(\forall
k\in\mathbf{N})\left\lVert(g_{k},h_{k})\right\rVert\leq G,$ (3.9)

and that the step sizes satisfy that

$\displaystyle(\forall i\in\mathbf{N})~{}t_{i}\geq 0\text{ with
}t_{0}>0,\quad\sum^{\infty}_{j=0}t_{j}=\infty,\quad\text{and}\quad\sum^{\infty}_{j=0}t_{j}^{2}=S<\infty.$
(3.10)

Then $\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})$ converges
to $f(x^{*},y^{*})$.

###### Proof.

According to Lemma 3.2(ii), we have that

$-\frac{\left\lVert
y^{0}-y^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
h_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}\leq\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x^{*},y^{*})\leq\frac{\left\lVert
x^{0}-x^{*}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{\sum^{k}_{i=0}t_{i}^{2}\left\lVert
g_{i}\right\rVert^{2}}{2\sum^{k}_{j=0}t_{j}},$

which, combined with our assumptions, 3.9 and 3.10, guarantees that

$-\frac{4R^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{G^{2}S}{2\sum^{k}_{j=0}t_{j}}\leq\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x^{*},y^{*})\leq\frac{4R^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{G^{2}S}{2\sum^{k}_{j=0}t_{j}},$

The inequalities above ensure
$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})-f(x^{*},y^{*})\to
0$ since $\sum^{\infty}_{i=0}t_{i}=\infty$. ∎

Below we shall prove the boundedness of the sequence
$((x^{k},y^{k}))_{k\in\mathbf{N}}$, which plays a critical role in our proof
of Theorem 3.2 below.

######  Lemma 3.3.

Let $(x^{*},y^{*})\in X\times Y$ be a solution of 1.3. Then

$(\forall
k\in\mathbf{N})\quad\left\langle(x^{k},y^{k})-(x^{*},y^{*}),(g_{k},h_{k})\right\rangle\geq
0.$

###### Proof.

As a result of [11, Theorem 1], the operator

$T:X\times
Y\to\mathcal{H}_{1}\times\mathcal{H}_{2}:(\bar{x},\bar{y})\mapsto(u,v),\quad\text{where
}u\in\partial_{x}f(\bar{x},\bar{y})\text{ and
}v\in\partial_{y}(-f(\bar{x},\bar{y}))$

is monotone.

In view of our assumption and Fact 2.1,

$\displaystyle 0\in\partial_{x}f(x^{*},y^{*})\quad and\quad
0\in\partial_{y}(-f(x^{*},y^{*})).$ (3.11)

Recall from the construction of the algorithm 3.1 that $(\forall
k\in\mathbf{N})$ $g_{k}\in\partial_{x}f(x^{k},y^{k})$ and
$h_{k}\in\partial_{y}(-f(x^{k},y^{k}))$. Combine this with 3.11 to derive that

$(\forall
k\in\mathbf{N})\quad\left\langle(x^{k},y^{k})-(x^{*},y^{*}),(g_{k},h_{k})\right\rangle=\left\langle(x^{k},y^{k})-(x^{*},y^{*}),T(x^{k},y^{k})-T(x^{*},y^{*})\right\rangle\geq
0,$

where we use the monotonicity of $T$ in the last inequality. ∎

######  Lemma 3.4.

Let $(x^{*},y^{*})\in X\times Y$ be a solution of 1.3. Let $R$, $G$, and $S$
be in $\mathbf{R}_{++}$. Suppose that

$\left\lVert(x^{0},y^{0})\right\rVert\leq
R,\quad\left\lVert(x^{*},y^{*})\right\rVert\leq R,\quad\text{and}\quad(\forall
k\in\mathbf{N})\left\lVert(g_{k},h_{k})\right\rVert\leq G,$

and that the step sizes satisfy that

$(\forall i\in\mathbf{N})~{}t_{i}\geq 0\text{ with
}t_{0}>0\quad\text{and}\quad\sum^{\infty}_{j=0}t_{j}^{2}=S<\infty.$

Then $((x^{k},y^{k}))_{k\in\mathbf{N}}$ is bounded.

###### Proof.

Let $k\in\mathbf{N}$. Applying 3.1 in the first equation, we have that

$\displaystyle\left\lVert(x^{k+1},y^{k+1})-(x^{*},y^{*})\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\left\lVert(\operatorname{P}_{X}(x^{k}-t_{k}g_{k}),\operatorname{P}_{Y}(y^{k}-t_{k}h_{k}))-(x^{*},y^{*})\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\left\lVert\operatorname{P}_{X}(x^{k}-t_{k}g_{k})-x^{*}\right\rVert^{2}+\left\lVert\operatorname{P}_{Y}(y^{k}-t_{k}h_{k})-y^{*}\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\left\lVert\operatorname{P}_{X}(x^{k}-t_{k}g_{k})-\operatorname{P}_{X}x^{*}\right\rVert^{2}+\left\lVert\operatorname{P}_{Y}(y^{k}-t_{k}h_{k})-\operatorname{P}_{Y}y^{*}\right\rVert^{2}$
$\displaystyle\leq$ $\displaystyle\left\lVert
x^{k}-t_{k}g_{k}-x^{*}\right\rVert^{2}+\left\lVert
y^{k}-t_{k}h_{k}-y^{*}\right\rVert^{2}$ $\displaystyle=$
$\displaystyle\left\lVert x^{k}-x^{*}\right\rVert^{2}-2t_{k}\left\langle
x^{k}-x^{*},g_{k}\right\rangle+t_{k}^{2}\left\lVert
g_{k}\right\rVert^{2}+\left\lVert
y^{k}-y^{*}\right\rVert^{2}-2t_{k}\left\langle
y^{k}-y^{*},h_{k}\right\rangle+t_{k}^{2}\left\lVert h_{k}\right\rVert^{2}$
$\displaystyle=$
$\displaystyle\left\lVert(x^{k},y^{k})-(x^{*},y^{*})\right\rVert^{2}-2t_{k}\left\langle(x^{k},y^{k})-(x^{*},y^{*}),(g_{k},h_{k})\right\rangle+t_{k}^{2}\left\lVert(g_{k},h_{k})\right\rVert^{2}.$

Note that we use 1.2 in the second equation, that we use the fact $x^{*}\in
X$, $y^{*}\in Y$, $x^{*}=\operatorname{P}_{X}x^{*}$, and
$y^{*}=\operatorname{P}_{Y}y^{*}$ in the third equation, that the
nonexpansiveness of $\operatorname{P}_{X}$ and $\operatorname{P}_{Y}$ is used
in the inequality above, and that we use both 1.2 and 1.1 in the last
equation.

The result above actually tells us that for every $i\in\\{0,1,\ldots,k\\}$,

$\left\lVert(x^{i+1},y^{i+1})-(x^{*},y^{*})\right\rVert^{2}-\left\lVert(x^{i},y^{i})-(x^{*},y^{*})\right\rVert^{2}+2t_{i}\left\langle(x^{i},y^{i})-(x^{*},y^{*}),(g_{i},h_{i})\right\rangle\leq
t_{i}^{2}\left\lVert(g_{i},h_{i})\right\rVert^{2}.$

Sum the inequality above over $i\in\\{0,1,\ldots,k\\}$ to obtain that

$\displaystyle\left\lVert(x^{k+1},y^{k+1})-(x^{*},y^{*})\right\rVert^{2}-\left\lVert(x^{0},y^{0})-(x^{*},y^{*})\right\rVert^{2}+2\sum^{k}_{i=0}t_{i}\left\langle(x^{i},y^{i})-(x^{*},y^{*}),(g_{i},h_{i})\right\rangle$
$\displaystyle\leq$
$\displaystyle\sum^{k}_{i=0}t_{i}^{2}\left\lVert(g_{i},h_{i})\right\rVert^{2},$

which, combined with the assumptions, implies that

$\displaystyle\left\lVert(x^{k+1},y^{k+1})-(x^{*},y^{*})\right\rVert^{2}+2\sum^{k}_{i=0}t_{i}\left\langle(x^{i},y^{i})-(x^{*},y^{*}),(g_{i},h_{i})\right\rangle\leq
4R^{2}+SG^{2}.$ (3.12)

In view of Lemma 3.3,
$\sum^{k}_{i=0}t_{i}\left\langle(x^{i},y^{i})-(x^{*},y^{*}),(g_{i},h_{i})\right\rangle\geq
0$. Hence, by 3.12,

$\left\lVert(x^{k+1},y^{k+1})-(x^{*},y^{*})\right\rVert^{2}\leq
4R^{2}+SG^{2},$

which yields the boundedness of $((x^{k},y^{k}))_{k\in\mathbf{N}}$. ∎

######  Lemma 3.5.

Let $(x^{*},y^{*})\in X\times Y$ be a solution of 1.3. Let $R$, $G$, and $S$
be in $\mathbf{R}_{++}$. Suppose that

$\left\lVert(x^{0},y^{0})\right\rVert\leq
R,\quad\left\lVert(x^{*},y^{*})\right\rVert\leq R,\quad\text{and}\quad(\forall
k\in\mathbf{N})\left\lVert(g_{k},h_{k})\right\rVert\leq G,$

and that the step sizes satisfy that

$(\forall i\in\mathbf{N})~{}t_{i}\geq 0\text{ with
}t_{0}>0\quad\text{and}\quad\sum^{\infty}_{j=0}t_{j}^{2}=S<\infty.$

Then $((\hat{x}_{k},\hat{y}_{k}))_{k\in\mathbf{N}}$ is bounded.

###### Proof.

The required result is clear from the definition of the sequence
$((\hat{x}_{k},\hat{y}_{k}))_{k\in\mathbf{N}}$ and the boundedness of
$((x^{k},y^{k}))_{k\in\mathbf{N}}$ proved in Lemma 3.4. ∎

######  Theorem 3.2.

Let $(x^{*},y^{*})\in X\times Y$ be a solution of 1.3. Let $R$, $G$, and $S$
be in $\mathbf{R}_{++}$. Suppose that

$\left\lVert(x^{0},y^{0})\right\rVert\leq
R,\quad\left\lVert(x^{*},y^{*})\right\rVert\leq R,\quad\text{and}\quad(\forall
k\in\mathbf{N})\left\lVert(g_{k},h_{k})\right\rVert\leq G,$

and that the step sizes satisfy that

$(\forall i\in\mathbf{N})~{}t_{i}\geq 0\text{ with
}t_{0}>0,\quad\sum^{\infty}_{j=0}t_{j}=\infty,\quad\text{and}\quad\sum^{\infty}_{j=0}t_{j}^{2}=S<\infty.$

Then $f(\hat{x}_{k},\hat{y}_{k})$ converges to $f(x^{*},y^{*})$.

###### Proof.

As a result of our assumptions and Lemma 3.5, there exists a constant
$Q\in\mathbf{R}_{++}$ such that

$(\forall
k\in\mathbf{N})\quad\left\lVert(\hat{x}_{k},\hat{y}_{k})\right\rVert\leq Q.$

Combine this with our assumptions and Lemma 3.2(iii) to establish that

$-\frac{4R^{2}+(R+Q)^{2}}{2\sum^{k}_{j=0}t_{j}}-\frac{SG^{2}}{2\sum^{k}_{j=0}t_{j}}\leq
f(\hat{x}_{k},\hat{y}_{k})-f(x^{*},y^{*})\leq\frac{4R^{2}+(R+Q)^{2}}{2\sum^{k}_{j=0}t_{j}}+\frac{SG^{2}}{2\sum^{k}_{j=0}t_{j}},$

which, combining with the assumption $\sum^{\infty}_{j=0}t_{j}=\infty$,
entails that $f(\hat{x}_{k},\hat{y}_{k})\to f(x^{*},y^{*})$. ∎

##  4 Numerical experiments

In this section, we implement our alternating subgradient method on some
particular examples to verify our convergence results presented in previous
Section 3 and also to analyze convergence rates of our algorithms. Moreover,
we compare our iterate scheme with step sizes $(t_{k})_{k\in\mathbf{N}}$ and
iterate schemes considered in [9] with constant step sizes. Based on our
numerical results presented in Figure 1, we see benefits of replacing constant
step sizes by step sizes $(t_{k})_{k\in\mathbf{N}}$ satisfying $(\forall
i\in\mathbf{N}\smallsetminus\\{0\\})$ $t_{i}\geq 0$, $t_{0}>0$,
$\sum^{\infty}_{j=0}t_{j}=\infty$, and $\sum^{\infty}_{j=0}t_{j}^{2}<\infty$.
In addition, in view of Figure 2, Figure 3, Figure 4, and Figure 6 below
obtained from our numerical experiments, we discover the convergence
$f(x^{k},y^{k})\to f(x^{*},y^{*})$ in multiple examples, which doesn’t have
any theoretical support yet.

We know that generally subgradient methods converge slowly. Normally, the
iterate point corresponding to larger iterate number has better convergence
performance. Therefore, to accelerate our subgradient methods for solving
convex-concave saddle-point problems, in our experiments below we reorder
sequence $(t_{k})_{k\in\mathbf{N}}$ in descending order. Based on our
numerical results, this trick works very well.

In this section, unless stated otherwise, $\left((x^{k},y^{k})\right)_{0\leq
k\leq K}$ is generated by 3.1 with $K$ being the number of iterates and step
sizes $(\forall k\in\\{1,\ldots,K\\})$ $t_{k}=\frac{1}{K+1-k}$. Moreover, we
have

$(\forall
k\in\mathbf{N})\quad(\hat{x}_{k},\hat{y}_{k})=\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}x^{i},\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}y^{i}\right).$

Note that the choice of step sizes

$(\forall k\in\\{1,\ldots,K\\})\quad t_{k}=\frac{1}{K+1-k}$

satisfies $(\forall i\in\mathbf{N}\smallsetminus\\{0\\})$ $t_{i}\geq 0$,
$t_{0}>0$, $\sum^{\infty}_{j=0}t_{j}=\infty$, and
$\sum^{\infty}_{j=0}t_{j}^{2}<\infty$, which is required in our convergence
results $\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\to
f(x^{*},y^{*})$ and $f(\hat{x}_{k},\hat{y}_{k})\to f(x^{*},y^{*})$ provided in
Theorem 3.1 and Theorem 3.2, respectively.

###  4.1 Toy example

In [9, Proposition 3.1], the authors considered the convergence of
$\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\to f(x^{*},y^{*})$ and
$f(\tfrac{1}{k}\sum^{k-1}_{i=0}x^{i},\tfrac{1}{k}\sum^{k-1}_{i=0}y^{i})\to
f(x^{*},y^{*})$ within certain error level and with some boundedness and
compactness assumptions, where $f:X\times Y\to\mathbf{R}$ is a convex-concave
function, $(x^{*},y^{*})$ is a saddle-point of $f$, and
$\left((x^{k},y^{k})\right)_{k\in\mathbf{N}}$ is generated by 3.1 with
$(\forall k\in\mathbf{N})$ $t_{k}\equiv\alpha\in\mathbf{R}_{++}$.

In this subsection, we compare our iterate scheme with iterate schemes
associated with step sizes being a constant to show the drawback of constant
step sizes.

We consider the toy convex-concave function
$f:\mathbf{R}\times\mathbf{R}_{+}\to\mathbf{R}$ defined by

$(\forall(x,y)\in\mathbf{R}\times\mathbf{R}_{+})\quad
f(x,y)=x^{2}(1+y)-6xy+8y+1.$

which is considered in Example 2.2(i). As a consequence of Fact 2.1, $(2,2)$
is a saddle-point of $f$. So all desired sequences of iterates must converge
to $f(2,2)=5$.

In our experiments related to Figure 1, we mainly consider
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{k\in\mathbf{N}}$
and $\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{k\in\mathbf{N}}$ with $(\forall
k\in\mathbf{N})$ $t_{i}=\alpha\in\mathbf{R}_{++}$ and for different values of
$\alpha$. Note that although when $(\forall k\in\mathbf{N})$
$t_{i}=\alpha\in\mathbf{R}_{++}$, $(\forall i\in\mathbf{N})$
$\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}=\frac{1}{k+1}$ independent of $\alpha$, the
sequence of iterates $((x^{k},y^{k}))_{k\in\mathbf{N}}$ generated by the
iterate scheme 3.1 is dependent on the sequence $(t_{i})_{i\in\mathbb{N}}$. So
different values of $\alpha$ indeed deduce different sequences of iterates in
consideration. Based on our results, when $\alpha>1$, both
$\left(\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\right)_{k\in\mathbf{N}}$ and
$\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{k\in\mathbf{N}}$ generally don’t
converge to the desired value $5$.

To get the following Figure 1, we calculate
$\left(\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\right)_{0\leq k\leq 200}$ and
$\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{0\leq k\leq 200}$ with a random
chosen initial point and with setting
$\alpha=1,\alpha=0.8,\alpha=0.5,\alpha=0.1,\alpha=0.01$, and $\alpha=0.0001$,
respectively. Moreover, we also calculate
$\left(\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\right)_{0\leq k\leq 200}$ and
$\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{0\leq k\leq 200}$ with $(\forall
k\in\\{1,\ldots,200\\})$ $t_{k}=\frac{1}{200+1-k}$ as a reference.

According to the first subplot of Figure 1, we observe that generally
sequences of iterates associated with constant step sizes don’t converge to
required optimal values. (In our numerous related experiments for this
particular example, we found that only when $(\forall i\in\mathbf{N})$
$t_{i}=0.1$, the sequences
$\left(\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\right)_{k\in\mathbf{N}}$ and
$\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{k\in\mathbf{N}}$ converge to the
required value $5$ consistently, regardless of the random initial points and
problem data. ) Moreover, the second subplot of Figure 1 shows that the
convergence rate of our iterate scheme with $(\forall k\in\\{1,\ldots,200\\})$
$t_{k}=\frac{1}{200+1-k}$ is faster than iterates schemes associated with
constant step sizes. Figure 1 shows some drawbacks of constant step sizes and
explains why should we consider $(t_{k})_{k\in\mathbf{N}}$ not being a
sequence of constant.

In fact, in our experiments associated with this example, we calculated
$(f(x^{k},y^{k}))_{1\leq k\leq 200}$ together with
$\left(\frac{1}{k+1}\sum^{k}_{i=0}f(x^{i},y^{i})\right)_{1\leq k\leq 200}$ and
$\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 200}$. We don’t present
them in Figure 1 because when step sizes are constant, the performance of
$(f(x^{k},y^{k}))_{1\leq k\leq 200}$ is much worse than performances of
sequences presented in Figure 1 below.

Figure 1: Comparison with iterate scheme associated with constant step sizes

Then we randomly chose initial points and calculate the sequence
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 500}$, $\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 500}$, and
$(f(x^{k},y^{k}))_{1\leq k\leq 500}$ with $(\forall k\in\\{1,\ldots,500\\})$
$t_{k}=\frac{1}{500+1-k}$. Our result is presented in Figure 2 below. Note
that to get a clearer view on the convergence rate, we zoom in more
interesting part and set the range of y-axis view as $[4.5,5.5]$.

The theoretical convergence of
$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\to
f(x^{*},y^{*})$ and $f(\hat{x}_{k},\hat{y}_{k})\to f(x^{*},y^{*})$ is
presented in Theorems 3.1 and 3.2. Although the convergence of
$f(x^{k},y^{k})\to f(x^{*},y^{*})$ is not provided theoretically yet, it is
shown numerically in Figure 2, which motivates our future work on the
convergence of $f(x^{k},y^{k})\to f(x^{*},y^{*})$ or
$(x^{k},y^{k})\to(x^{*},y^{*})$.

Figure 2: Convergence result with randomly chosen initial points

###  4.2 Linear program in inequality form

Let $A\in\mathbf{R}^{m\times n}$, $b\in\mathbf{R}^{m}$, and
$c\in\mathbf{R}^{n}$. In this part, we consider the convex-concave function
$f:\mathbf{R}^{n}\times\mathbf{R}^{m}_{+}\to\mathbf{R}$ defined as

$(\forall(x,y)\in\mathbf{R}^{n}\times\mathbf{R}^{m}_{+})\quad
f(x,y)=y^{T}Ax+c^{T}x-b^{T}y,$

which is presented in Example 2.2(ii).

In our experiments, after randomly choosing $A\in\mathbf{R}^{100\times 10}$,
$b\in\mathbf{R}^{100}$, and $c\in\mathbf{R}^{10}$, we apply the Python-
embedded modeling language CVXPY (see [7] for details) to find bounded and
feasible problems. Recall from Example 2.2(ii) that the convex-concave
function $f$ above is the Lagrangian of a linear programming with an
inequality constraint and that the optimal solutions of the related primal and
dual problem are both equal to the value of $f$ over a saddle-point. We also
solve the corresponding primal and dual problems by CVXPY to check the
correctness of results from our algorithms.

After finding problems with optimal solutions, we randomly choose initial
points $(x^{0},y^{0})\in\mathbf{R}^{10}\times\mathbf{R}^{100}$ and calculate
the sequence
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 100}$, $\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 100}$, and
$(f(x^{k},y^{k}))_{1\leq k\leq 100}$ with $(\forall k\in\\{1,\ldots,100\\})$
$t_{k}=\frac{1}{100+1-k}$. We presented one result in Figure 3 below. Note
that to see only the important range of y-axis, we zoom in and set the y-axis
limit on the picture as $[f(x^{*},y^{*})-1,f(x^{*},y^{*})+1]$, where the
optimal value $f(x^{*},y^{*})$ is obtained from our CVXPY code. Because in
this case $f$ is linear, it’s not a surprise that
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 100}$ and $\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 100}$ on
Figure 3 are consistent.

Figure 3: Lagrangian of the inequality form LP

In all our experiments, the convergent point of our sequence of iterates is
identical with the optimal solutions obtained by CVXPY. The convergence of
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 100}$ and $\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 100}$
confirms numerically our theoretical results in Theorems 3.1 and 3.2. Again,
$(f(x^{k},y^{k}))_{1\leq k\leq 100}$ converges to our required point although
we have no theoretical support of the convergence yet.

###  4.3 Least-squares problem with $\ell_{1}$ regularization

Let $A\in\mathbf{R}^{m\times n}$, $b\in\mathbf{R}^{m}$, and
$\gamma\in\mathbf{R}_{++}$. We consider the convex-concave function
$f:\mathbf{R}^{n+m}\times\mathbf{R}^{m}\to\mathbf{R}$ defined as

$(\forall((x,u),y)\in\mathbf{R}^{n+m}\times\mathbf{R}^{m})\quad
f((x,u),y)=\frac{1}{2}\left\lVert u\right\rVert^{2}_{2}+\gamma\left\lVert
x\right\rVert_{1}+y^{T}(Ax-b-u),$

which is considered in Example 2.2(iii) and Example 3.1. As stated in Example
2.2(iii), $f$ is the Lagrangian of a least-squares problem with $\ell_{1}$
regularization. In our experiments, we set $\gamma=1$ and randomly choosing
$A\in\mathbf{R}^{100\times 50}$ and $b\in\mathbf{R}^{100}$. Note that in this
case the problem is always feasible and bounded. Similarly with Section 4.2,
we apply CVXPY to solve related primal and dual problems.

Consider $X=\mathbf{R}^{100+50}$ and
$Y=\\{y\in\mathbf{R}^{100}~{}:~{}\left\lVert
A^{T}y\right\rVert_{\infty}\leq\gamma\\}$. We randomly choose initial points
$(x^{0},y^{0})\in\mathbf{R}^{100+50}\times\mathbf{R}^{100}$ and implement the
sequences
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 500}$, $\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 500}$, and
$(f(x^{k},y^{k}))_{1\leq k\leq 500}$ with $(\forall k\in\\{1,\ldots,500\\})$
$t_{k}=\frac{1}{500+1-k}$. We show one result in Figure 4 in which the
convergent point is consistent with the optimal solution obtained by CVXPY for
corresponding primal and dual problems. With the optimal value
$f(x^{*},y^{*})$ obtained by our related CVXPY code, we zoom in and set the
y-axis limit on the picture as $[f(x^{*},y^{*})-1,f(x^{*},y^{*})+1]$ to see
only the important range of y-axis. It’s interesting that
$(f(x^{k},y^{k}))_{1\leq k\leq 500}$ converges to the required optimal value
in this example as well.

Figure 4: Lagrangian of the least-squares problem with $\ell_{1}$
regularization

###  4.4 Matrix game

We consider an easy version of the game interpretation of saddle-point
problems below (see, e.g., [4, Section 5.4.3] for details). Let
$C\in\mathbf{R}^{m\times n}$ and let $X\subseteq\mathbf{R}^{n}$ and
$Y\subseteq\mathbf{R}^{m}$ be nonempty closed and convex subsets. The subject
function in this case is $f:\mathbf{R}^{n}\times\mathbf{R}^{m}\to\mathbf{R}$
defined as

$(\forall(x,y)\in X\times Y)\quad f(x,y)=x^{T}Cy.$

In our experiment, we use the example of matrix game in [12, Sections 5.2 and
5.3] and set

$\displaystyle C=\begin{pmatrix}1&2\\\ 3&1\end{pmatrix},$ $\displaystyle
X:=\\{x\in\mathbf{R}^{2}~{}:~{}\sum^{2}_{i=1}x_{i}=1\text{ and }(\forall
i\in\\{1,2\\})~{}x_{i}\geq 0\\},\text{ and}$ $\displaystyle
Y:=\\{y\in\mathbf{R}^{2}~{}:~{}\sum^{2}_{i=1}y_{i}=1\text{ and }(\forall
i\in\\{1,2\\})~{}y_{i}\geq 0\\}.$

In view of [12, Section 5.3], the optimal value (that is the value of $f$ over
the saddle-point) is $1.6667$ with keeping 4 decimal places.

In our experiments, we randomly choose initial points $(x^{0},y^{0})\in
X\times Y$ and calculate the sequences
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 1000}$, $\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 1000}$,
and $(f(x^{k},y^{k}))_{1\leq k\leq 1000}$ with multiple choices of
$(t_{k})_{k\in\mathbf{N}}$ but we noticed that in our experiments
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 1000}$ and $(f(x^{k},y^{k}))_{1\leq k\leq 1000}$ converge very slow. To
get the following Figure 5, we randomly choose initial points
$(x^{0},y^{0})\in X\times Y$ and implement
$\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{1\leq k\leq 1000}$ with two cases of
the parameter $(t_{k})_{k\in\mathbf{N}}$: $(\forall i\in\mathbf{N})$
$t_{i}=0.1$ and $(\forall i\in\mathbf{N})$ $t_{i}=0.01$. (We considered also
other choices of $(t_{k})_{k\in\mathbf{N}}$ including $(\forall
k\in\\{1,\ldots,1000\\})$ $t_{k}=\frac{1}{1000+1-k}$, but their convergence
performances are not good. We calculated also
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 1000}$ and $(f(x^{k},y^{k}))_{1\leq k\leq 1000}$ in the experiment
associated with Figure 5, but they converge very slowly.) We observe that, in
Figure 5, the convergent point is indeed the optimal solution obtained by [12,
Section 5.3].

Figure 5: Matrix game with constant step sizes

###  4.5 Robust Markowitz portfolio construction problem

As a last example in this section, we consider the robust Markowitz portfolio
construction problem. (See, e.g., [12] or [3] for details.) We consider the
robust Markowitz portfolio construction problem presented in [12, Sections 3.4
and 6.3] here. Let $\bar{\mu}\in\mathbf{R}^{n}$ be the nominal mean, let
$\bar{\Sigma}\in{\mbox{\bf S}}^{n}_{++}$ be the nominal covariance, and let
$\gamma\in\mathbf{R}_{++}$. Let $\mathcal{W}\subseteq\mathbf{R}^{n}$ be a
convex set of feasible portfolios and let

$\displaystyle\mathcal{M}=$ $\displaystyle\\{\bar{\mu}+\delta~{}:~{}(\forall
i\in\\{1,2,\ldots,n\\})\left|\delta_{i}\right|\leq\rho_{i}\\},$
$\displaystyle\mathcal{S}=$
$\displaystyle\\{\bar{\Sigma}+\Delta~{}:~{}\bar{\Sigma}+\Delta\in{\mbox{\bf
S}}^{n}_{+}\text{ and }(\forall
i,j\in\\{1,2,\ldots,n\\})\left|\Delta_{ij}\right|\leq\eta(\bar{\Sigma}_{ii}\bar{\Sigma}_{jj})^{\tfrac{1}{2}}\\},$

where $\rho\in\mathbf{R}^{n}_{++}$ is a vector of uncertainties in the
forecast returns, $\delta\in\mathbf{R}^{n}$ is the perturbation of the nominal
mean $\bar{\mu}$, $\Delta\in{\mbox{\bf S}}^{n}$ is the perturbation of the
nominal covariance $\bar{\Sigma}$, and $\eta\in(0,1)$ is a parameter scaling
the perturbation to the forecast covariance matrix.

In this case, the convex-concave function is
$f:\mathcal{M}\times\mathcal{S}\times\mathcal{W}\to\mathbf{R}$ defined as

$(\forall(x,y)=((\mu,\Sigma),w)\in(\mathcal{M}\times\mathcal{S})\times\mathcal{W})\quad
f(x,y)=f((\mu,\Sigma),w)=\mu^{T}w-\gamma w^{T}\Sigma w.$

We also use the data ($\bar{\mu}$, $\bar{\Sigma}$, $\rho$, $\eta$, and
$\gamma$) worked in [12, Sections 6.3] where $n=6$. In view of the result
obtained therein, the optimal value (that is, the value
$f((\mu^{*},\Sigma^{*}),w^{*})$ over the saddle-point) is $0.076$.

We randomly choose $x^{0}=(\mu^{0},\Sigma^{0})\in\mathcal{M}\times\mathcal{S}$
and $y^{0}=w^{0}\in\mathcal{W}$ and calculate the sequences
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 1000}$ and $(f(x^{k},y^{k}))_{1\leq k\leq 1000}$ with $(\forall
k\in\\{1,\ldots,1000\\})$ $t_{k}=\frac{1}{1000+1-k}$. We present one result in
Figure 6 and see clearly that
$\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\right)_{1\leq
k\leq 1000}$ and $\left(f(x_{k},y_{k})\right)_{k\in\mathbf{N}}$ converge to
the required optimal value $0.076$ in $1000$ iterates. The performance of
$\left(f(\hat{x}_{k},\hat{y}_{k})\right)_{k\in\mathbf{N}}$ in our experiments
of this example is not good so we don’t present it in Figure 6 below.

Figure 6: Convergence of robust Markowitz portfolio construction problem

##  5 Conclusion

In this work, we proved some convergence results of our alternating
subgradient method for convex-concave saddle-point problems associated with
general convex-concave functions. Let $(x^{*},y^{*})\in X\times Y$ be a
saddle-point of a convex-concave function $f$, and let
$((x^{k},y^{k}))_{k\in\mathbf{N}}$ be a sequence of iterates generated by our
alternating subgradient method associated with the sequence
$(t_{k})_{k\in\mathbf{N}}$ of step sizes. We presented the convergence
$\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}f(x^{i},y^{i})\to
f(x^{*},y^{*})$ under some popular assumptions on the step-size. With the same
assumption, we also showed
$f\left(\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}x^{i},\sum^{k}_{i=0}\frac{t_{i}}{\sum^{k}_{j=0}t_{j}}y^{i}\right)\to
f(x^{*},y^{*})$.

Our convergence results were confirmed by our numerical experiments in
examples of a linear program in inequality form, a least-squares problem with
$\ell_{1}$ regularization, a matrix game, and a robust Markowitz portfolio
construction problem. We also compared our iterate scheme (associated with a
not summable but square summable sequence $(t_{k})_{k\in\mathbf{N}}$ of step
sizes) with iterate schemes associated with constant step sizes on a
Lagrangian of an easy convex constrained optimization problem. Our numerical
result showed some benefits of replacing constant step sizes with our step
sizes $(t_{k})_{k\in\mathbf{N}}$. Additionally, in our numerical experiments,
we displayed the convergence $f(x^{k},y^{k})\to f(x^{*},y^{*})$ in multiple
examples, which currently lacks theoretical support, to the best of our
knowledge. This motivates our future work on theoretical proof of the
convergence of $(x^{k},y^{k})\to(x^{*},y^{*})$ and $f(x^{k},y^{k})\to
f(x^{*},y^{*})$.

## Acknowledgments

Hui Ouyang acknowledges the support of the Natural Sciences and Engineering
Research Council of Canada (NSERC), [funding reference number PDF – 567644 –
2022].

## References

  * [1] S. Boyd.  Subgradient methods, notes for course EE364b in stanford university, https://web.stanford.edu/class/ee364b/lectures/subgrad_method_notes.pdf.
  * [2] S. Boyd.  Subgradients, notes for course EE364b in stanford university, https://web.stanford.edu/class/ee364b/lectures/subgradients_notes.pdf.
  * [3] S. Boyd, E. Busseti, S. Diamond, R. N. Kahn, K. Koh, P. Nystrup, and J. Speth.  Multi-period trading via convex optimization.  Foundations and Trends in Optimization, 3(1):1–76, 2017.
  * [4] S. Boyd and L. Vandenberghe.  Convex optimization.  Cambridge University Press, Cambridge, 2004.
  * [5] S. Boyd and L. Vandenberghe.  Additional exercises for convex optimization, https://github.com/cvxgrp/cvxbook_additional_exercises/blob/main/additional_exercises.pdf, 2023\.
  * [6] A. Chambolle and T. Pock.  A first-order primal-dual algorithm for convex problems with applications to imaging.  Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011\.
  * [7] S. Diamond and S. Boyd.  CVXPY: a Python-embedded modeling language for convex optimization.  Journal of Machine Learning Research, 17:Paper No. 83, 5, 2016.
  * [8] A. Juditsky and A. Nemirovski.  On well-structured convex-concave saddle point problems and variational inequalities with monotone operators.  Optimization Methods & Software, 37(5):1567–1602, 2022.
  * [9] A. Nedić and A. Ozdaglar.  Subgradient methods for saddle-point problems.  Journal of Optimization Theory and Applications, 142(1):205–228, 2009.
  * [10] Y. Nesterov.  Primal-dual subgradient methods for convex problems.  Mathematical Programming, 120(1, Ser. B):221–259, 2009.
  * [11] R. T. Rockafellar.  Monotone operators associated with saddle-functions and minimax problems.  In Nonlinear Functional Analysis (Proc. Sympos. Pure Math., Vol. XVIII, Part 1, Chicago, Ill., 1968), pages 241–250. Amer. Math. Soc., Providence, R.I., 1970.
  * [12] P. Schiele, E. Luxenberg, and S. Boyd.  Disciplined saddle programming.  arXiv preprint arXiv:2301.13427, 2023.
  * [13] Y. Wang and J. Li.  Improved algorithms for convex-concave minimax optimization.  Advances in Neural Information Processing Systems, 33:4800–4810, 2020.
  * [14] G. Zhang, Y. Wang, L. Lessard, and R. B. Grosse.  Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization.  In International Conference on Artificial Intelligence and Statistics, pages 7659–7679. PMLR, 2022.