11institutetext: Krzysztof Postek 22institutetext: Faculty of Electrical
Enginnering, Mathematics and Computer Science
Delft University of Technology, Delft, The Netherlands
22email<EMAIL_ADDRESS>33institutetext: Shimrit Shtern
44institutetext: Faculty of Industrial Engineering and Management, Technion -
Israel Institute of Technology, Haifa, Israel
44email<EMAIL_ADDRESS>
# First-order algorithms for robust optimization problems via convex-concave
saddle-point Lagrangian reformulation

Krzysztof Postek  Shimrit Shtern

###### Abstract

Robust optimization (RO) is one of the key paradigms for solving optimization
problems affected by uncertainty. Two principal approaches for RO, the robust
counterpart method and the adversarial approach, potentially lead to
excessively large optimization problems. For that reason, first order
approaches, based on online-convex-optimization, have been proposed
bental2015oracle ; ho2018online  as alternatives for the case of large-scale
problems. However, these methods are either stochastic in nature or involve a
binary search for the optimal value. We propose deterministic first-order
algorithms based on a saddle-point Lagrangian reformulation that avoids both
of these issues. Our approach recovers the other approaches’
$\mathcal{O}(1/\epsilon^{2})$ convergence rate in the general case, and offers
an improved $\mathcal{O}(1/\epsilon)$ rate for problems with constraints which
are affine both in the decision and in the uncertainty. Experiment involving
robust quadratic optimization demonstrates the numerical benefits of our
approach.

##  1 Introduction

When solving optimization problems, one often has to deal with uncertainty
present in the parameters of the objective and constraint functions. This
uncertainty may stem from measurement, implementation or prediction errors. A
common paradigm used to ensure that the solution remains feasible under
uncertainty is _robust optimization (RO)_ bental2009robust . In RO, the
uncertainty is assumed to be adversarial to the decision maker and to lie in a
predefined _uncertainty set_ , and the decision maker finds the best solution
which remains feasible for all parameter values within this set.

Any RO algorithm involves simultaneous solving of two problems: the decision
maker’s problem of finding the best-possible decision which is feasible for
the given uncertainty set, and nature’s implicit adversarial problem of
selecting the worst possible realization of the parameters.

Denoting the decision maker’s decision as ${\mathbf{x}}$, taken from a
predefined set $X$, and the uncertain parameter for constraint $i$ as
${\mathbf{z}}_{i}$, taken from a predefined uncertainty set $Z^{i}$, a general
RO problem is given by:

$\displaystyle\min\limits_{{\mathbf{x}}\in X}\ $
$\displaystyle{\mathbf{c}}^{\top}{\mathbf{x}}$ (1) s.t.
$\displaystyle\sup\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\leq 0,$ $\displaystyle i\in[m].$

In this problem, the decision maker minimizes over ${\mathbf{x}}\in X$, while
the nature selects ${\mathbf{z}}\in Z=Z^{1}\times Z^{2}\times\ldots\times
Z^{m}$ such that the left-hand sides of the inequality constraints are
maximized, in an attempt to violate the constraints.

There are two key methods for handling the opposite optimization problems
simultaneously: (1) the _robust counterpart_ (RC) reformulation method
BenTal2015 ; bental2009robust , (2) _adversarial approach_ , also known as
cutting planes bienstock2007histogram ; mutapcic2009cutting . In the RC
approach, nature’s maximization problem for each constraint is dualized, and
the objective of the dual problem is required to be nonpositive. In this way,
a constraint is substituted by a system of inequalities that are satisfied for
a given ${\mathbf{x}}$ if and only if the original left-hand sides are
nonpositive. This method’s key advantage is that it requires to solve only one
optimization problem and it ensures by-design the robustness of the solution.
Its disadvantage is the increase of the problem size due to the added dual
variables and constraints generated by dualizing nature’s problems. Moreover,
for strong duality to hold for nature’s problem in each constraint, it has to
be convex, or equivalent to a convex problem.

In the adversarial approach, a finite subset $\underaccent{\bar}{Z}\subset Z$
of scenarios is iteratively built up, until it contains enough points to
ensure that ${\mathbf{x}}$ is feasible for all realizations in the subset if
and only if it is (almost) feasible for all realizations in $Z$. The set
$\underaccent{\bar}{Z}$ is intialized using an arbitrarily chosen realization
${\mathbf{z}}\in Z$. Then two steps are repeated alternatingly: an
optimization step, in which a solution ${\mathbf{x}}$ which minimizes the
objective function and is feasible for ${\mathbf{z}}\in\underaccent{\bar}{Z}$
is found; a _pessimization step_ , in which a new realization ${\mathbf{z}}$
violating at least one constraint is found and added to
$\underaccent{\bar}{Z}$. This iterative procedure continues until no violating
scenario is found. While this method is simple and enables solving problems in
which nature’s problem is not necessarily convex, the size of
$\underaccent{\bar}{Z}$ increases at each iteration, which may result in
extremely large optimization problems in ${\mathbf{x}}$ during the
optimization step.

Both of the above methods potentially lead to excessively large optimization
problems which creates space for approaches in which the decision maker’s and
the adversary’s problems are simultaneously solved in a lightweight fashion. A
recently suggested idea bental2015oracle ; ho2018online  is to use online
convex optimization to solve problem (1), proving that the number of
iterations needed to obtain an $\epsilon$-feasible solution is
$O(1/\epsilon^{2})$. Through the online optimization lens, the robust problem
is seen as a problem of minimizing a partly unknown objective with likewise
constraints, whose shape is learned throughout the algorithm via samples.

The approach of bental2015oracle  consists in iteratively solving a nominal
version of (1) in which the set $Z$ is replaced by a fixed realization
${\mathbf{z}}$. The value of ${\mathbf{z}}$ is updated at each iteration
through first-order updates/pessimization and randomization. The approach of
ho2018online  is to use binary search to determine the minimal $\tau$ for
which the feasibility problem

$\\{{\mathbf{c}}^{\top}{\mathbf{x}}\leq\tau,\ \sup_{{\mathbf{z}}\in
Z}g_{i}({\mathbf{x}},{\mathbf{z}})\leq 0,\quad i\in[m]\\}$

has a solution up to a given accuracy. This requires running an online first-
order algorithm for each tested $\tau$. Each of the feasibility problems is
solved by a first order iteration on ${\mathbf{x}}$, simultaneously with a
pessimization/first order steps on the dual parameter ${\mathbf{z}}$.

Thanks to the online optimization framework, both bental2015oracle ;
ho2018online  work directly with the functions
$\\{g_{i}(\cdot,\cdot)\\}_{i\in[m]}$, without the need to build an ever-
increasing list of scenarios, or to dualize the constraints. This has a price:
the functions $g_{i}$ have to be convex-concave, the set $X$ needs to be
bounded, and the maximum achievable convergence rate is
$\mathcal{O}(1/\epsilon^{2})$ to obtain an $\epsilon$-feasible and
$\epsilon$-optimal solution. Also, bental2015oracle  requires to solve
multiple nominal problems, while in ho2018online  one needs to run binary
search for the optimal objective value.

We address these issues by proposing to solve (1) with single-run first-order
algorithms. We leverage a natural convex-concave saddle-point reformulation of
(1), based on its Lagrangian. Although the existence of such a formulation was
noted and discussed in (ho2018online, , Appendix A), it has been claimed that
the problem loses a lot of convenient structure due to the lifting. In this
paper, we demonstrate that if the problem satisfies the Slater-type condition,
it can be solved using a subgradient saddle-point algorithm (SGSP) of
nedic2009subgradient  which requires $\mathcal{O}(1/\epsilon^{2})$ iterations
to obtain an $\epsilon$-feasible and $\epsilon$-optimal solution. For the
special case where $g_{i}(\cdot,\cdot)$ are biaffine, we show that the problem
can be solved using the proximal alternating predictor-corrector (PAPC)
algorithm of drori2015209 , which takes $\mathcal{O}(1/\epsilon)$ iterations.
Moreover, we show that when $Z^{i}$ are projection- or proximal-friendly one
may also find the projection onto the lifted space relatively easily, either
analytically or by using bi-section. Finally, we show that the saddle-point
formulation actually allows for more flexibility and enables to tackle
problems where either $Z^{i}$ or $X$ are more complicated by using splitting
techniques, where these problems prove to be more challenging for the
previously suggested methods.

The remainder of the paper is structured as follows. In Section 2, we
introduce the problem we solve along with the corresponding assumptions and
the Lagrangian saddle-point reformulation. In Section 3, we introduce the two
algorithms for the case of simple uncertainty sets and state the corresponding
convergence results. In Section 4, we present the convergence analysis of the
algorithms for a generalized problem form through a unified framework of
showing that both are ergodically bounded (EB) algorithms. In Section 5, we
compare the performance of our SGSP approach to the online first-order
approaches of ho2018online  and the adversarial approach on randomly sampled
robust quadratic optimization problems with and without constraints. Section 6
concludes the paper. All proofs not given in the body are given in Appendix A.

###  1.1 Notation

Throughout the paper we use bolded small letters ${\mathbf{x}}$,
${\mathbf{z}}$ for vectors, and bolded capital letters ${\mathbf{P}}$ for
matrices, and capital letters for sets. For any $k\in\mathbb{N}$, we use
shorthand notation $[k]$ to denote the set of indexes $\\{1,2,\ldots,k\\}$.
Unless specified otherwise, $\|\cdot\|$ refers to the Euclidean norm.

##  2 Problem setting and assumptions

###  2.1 Introduction

In this paper, we consider the following general RO problem.

$\displaystyle\min\limits_{{\mathbf{x}}\in X}\ $
$\displaystyle{\mathbf{c}}^{\top}{\mathbf{x}}$ (2) s.t. $\displaystyle
f_{i}({\mathbf{x}})\coloneqq\max\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\leq 0$ $\displaystyle i\in[m]$
$\displaystyle{\mathbf{A}}{\mathbf{x}}={\mathbf{b}}$

where $X\subseteq{}^{n}$ is a closed and convex set, for all $i\in[m]$ the set
$Z^{i}\subset\mathbb{R}^{d_{i}}$ is a convex and compact set and without loss
of generality ${\mathbf{0}}\in Z^{i}$,
$g_{i}(\cdot,{\mathbf{z}}_{i}):X\rightarrow\real$ is convex for any fixed
${\mathbf{z}}_{i}\in Z^{i}$, $g_{i}({\mathbf{x}},\cdot):Z^{i}\rightarrow\real$
is concave for any fixed ${\mathbf{x}}\in X$, and ${\mathbf{A}}\in{}^{r\times
n}$, ${\mathbf{b}}\in{}^{r}$. Note that, contrary to Problem 1, here we allow
to separate some of the affine constraints that may be involved in the
definition of the domain of ${\mathbf{x}}$ from the set $X$.

Note that formulation (2) also encompasses robust problems involving
uncertainty in the objective function, since such problems can be transformed
to form (2) using the epigraph formulation of the objective. Thus, formulation
(2) is general and includes many useful problems (_c.f._ , bertsimas2011theory
; gabrel2014recent ).

Functions $f_{i}({\mathbf{x}})$ are known as the robust counterpart
formulation of the robust constraint

$g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\leq 0,\;\forall{\mathbf{z}}_{i}\in
Z^{i}.$

Note that while $f_{i}({\mathbf{x}})$ are convex functions of ${\mathbf{x}}$
(as a maximum of convex functions), they are not necessarily easily
representable due to their implicit formulation as maxima.

Our aim is to solve (2) through its saddle point Lagrangian formulation. For
this formulation to be well-defined, we make three standard assumptions.

###### Assumption 1

Problem (2) has an optimal solution.

###### Assumption 2

There exists $\hat{{\mathbf{x}}}\in\text{int}(X)$ such that
${\mathbf{A}}\hat{{\mathbf{x}}}={\mathbf{b}}$ and there exists a
$\epsilon_{\hat{{\mathbf{x}}}}>0$ such that
$\hat{{\mathbf{x}}}+{\mathbf{y}}\in X$ and
$f_{i}(\hat{{\mathbf{x}}}+{\mathbf{y}})<0$ for all
$\left\|{{\mathbf{y}}}\right\|\leq\epsilon_{\hat{{\mathbf{x}}}}$.

###### Assumption 3

Matrix ${\mathbf{A}}$ has full row rank.

With respect to Assumption 1, if the problem does not have an optimal solution
there are three options: (i) it is infeasible, in which case the uncertainty
sets defined for the problem may be too large, (ii) it is unbounded, i.e., ,
it might not be constrained enough, or (iii) it is bounded but the optimal
solution is not attained, in which case we can restrict the set $X$ to a
subset containing $\epsilon$-optimal solutions of the original problem.
Assumption 2, known as the Slater condition, ensures that the problem is
stable, i.e., slight perturbations in the feasible set do make the problem
infeasible. Assumption 3 states that there are no redundant equality
constraints.

In order to solve problem (2) we consider its Lagrangian:

$L({\mathbf{x}},({\boldsymbol{\lambda}},{\mathbf{w}}))\equiv{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}f_{i}({\mathbf{x}})+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
(3)

Specifically, we are interested in saddle points of function $L(\cdot,\cdot)$
, i.e., points $({\mathbf{x}}^{*},{\boldsymbol{\lambda}}^{*})$ which satisfy

$L({\mathbf{x}}^{*},({\boldsymbol{\lambda}},{\mathbf{w}}))\leq
L({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))\leq
L({\mathbf{x}},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})),\quad\forall{\mathbf{x}}\in
X,\lambda\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}.$

Under Assumptions 1 and 2, the Lagrangian function $L(\cdot,\cdot)$ has a
saddle point, and
$({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ is a saddle
point of $L(\cdot,\cdot)$ if and only if ${\mathbf{x}}^{*}$ and
$({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})$ are optimal solutions to the
primal and dual problems respectively. Thus, instead of solving problem (2),
we want to find a solution to

$\displaystyle\operatorname*{inf\vphantom{p}}_{{\mathbf{x}}\in
X}\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}L({\mathbf{x}},({\boldsymbol{\lambda}},{\mathbf{w}})).$
(4)

This reformulation eliminates the constraints and renders the problem as a
saddle point one, enabling the use of various first-order methods. However,
such methods require computing at each iteration not only the functions
$f_{i}({\mathbf{x}})$, but also their sub-gradients or proximal operators,
which may be challenging with the implicitly-defined $f_{i}$ functions. We
will therefore consider an alternative formulation where our goal is to work
with functions $g_{i}$, and show how to obtain an $\epsilon$-optimal and
$\epsilon$-feasible solution of problem (2).

###  2.2 Conversion to a convex-concave saddle point problem

We begin our transformation of problem (4) plugging in the explicit
definitions of of functions $f_{i}$, using functions $g_{i}$, as follows:

$\displaystyle\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}\operatorname*{inf\vphantom{p}}_{{\mathbf{x}}\in
X}L({\mathbf{x}},({\boldsymbol{\lambda}},{\mathbf{w}}))$
$\displaystyle=\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}\operatorname*{inf\vphantom{p}}_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}\sup_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
$\displaystyle=\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}\operatorname*{inf\vphantom{p}}_{{\mathbf{x}}\in
X}\max_{{\mathbf{z}}_{i}\in
Z^{i},\;i\in[m]}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
$\displaystyle=\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}\sup_{{\mathbf{z}}_{i}\in
Z^{i},\;i\in[m]}\operatorname*{inf\vphantom{p}}_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
(5)

where the equalities follow from Sion’s Theorem, the fact $Z^{i}$ are convex
and compact, $X$ is convex, and $g_{i}$ are convex-concave. However, the
resulting saddle point problem (5) is over a function which is convex in
${\mathbf{x}}$ but is not jointly concave in
${\mathbf{z}}=({\mathbf{z}}_{1},\ldots,{\mathbf{z}}_{m})$ and
${\boldsymbol{\lambda}}=(\lambda_{1},\ldots,\lambda_{m})$. Since convergence
results for saddle point algorithms typically require a convex-concave
structure, we need to reformulate the problem to achieve such a structure. For
this, we will use a change of variables
$\tilde{{\mathbf{z}}}_{i}=\lambda_{i}{\mathbf{z}}_{i}$, and inversely

${\mathbf{z}}_{i}=\begin{cases}\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}},&\lambda_{i}>0,\\\
{\mathbf{0}},&\text{otherwise}.\end{cases}$

Using this definition we have
$\lambda_{i}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})=\lambda_{i}g_{i}({\mathbf{x}},\tilde{{\mathbf{z}}}_{i}/\lambda_{i})$,
and since $-g_{i}({\mathbf{x}},\cdot)$ is convex for every ${\mathbf{x}}$,
$-\lambda_{i}g_{i}({\mathbf{x}},\tilde{{\mathbf{z}}}_{i}/\lambda_{i})$ is
jointly convex in ${\mathbf{u}}_{i}=(\tilde{{\mathbf{z}}}_{i},\lambda_{i})$
for every ${\mathbf{x}}$, as a _perspective_ of a convex function
(bauschke2011convex, , Proposition 8.23). Moreover,
$\lambda_{i}g_{i}({\mathbf{x}},\tilde{{\mathbf{z}}}_{i}/\lambda_{i})$ is
continuous for all ${\mathbf{u}}_{i}\in U^{i},$ where
$U^{i}=\\{{\mathbf{u}}_{i}=(\tilde{{\mathbf{z}}}_{i},\lambda_{i}):\tilde{{\mathbf{z}}}_{i}\in\lambda_{i}Z^{i},\lambda_{i}\geq
0\\}$, obtaining a value of $0$ whenever $\lambda_{i}=0$. Defining
${\mathbf{u}}=({\mathbf{u}}_{1},\ldots,{\mathbf{u}}_{m})$ and the set
$U=U^{1}\times\ldots\times U^{m}$, we have

$\displaystyle\sup_{{\mathbf{u}}\in
U,{\mathbf{w}}\in\mathbb{R}^{r}}\operatorname*{inf\vphantom{p}}_{{\mathbf{x}}\in
X}\bar{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}}))$
$\displaystyle\coloneqq\sup_{{\mathbf{u}}\in
U,{\mathbf{w}}\in\mathbb{R}^{r}}\operatorname*{inf\vphantom{p}}_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}}\right)+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}}).$
(6)

For ease of notation, in henceforth we denote the perspective version of
$g_{i}$ as
$\tilde{g}_{i}({\mathbf{x}},{\mathbf{u}}_{i})\equiv\lambda_{i}g_{i}({\mathbf{x}},\tilde{{\mathbf{z}}}_{i}/\lambda_{i})$
where ${\mathbf{u}}_{i}=(\tilde{{\mathbf{z}}}_{i},\lambda_{i})$.

The following result shows that solving (6) is sufficient for solving (4),
i.e., , the saddle points of $\bar{L}$ can be reduced to those of $L$.

###### Proposition 1

Let $({{\mathbf{x}}}^{*},({{\mathbf{u}}}^{*},{\mathbf{w}}^{*}))\in X\times
U\times\mathbb{R}^{r}$, where
${\mathbf{u}}^{*}=({\mathbf{u}}^{*}_{1},\ldots,{\mathbf{u}}^{*}_{m})$ and
${\mathbf{u}}_{i}^{*}=(\tilde{{\mathbf{z}}}_{i}^{*},\lambda^{*}_{i})$ for
$i\in[m]$. Then $({{\mathbf{x}}}^{*},({{\mathbf{u}}}^{*},{\mathbf{w}}^{*}))\in
X\times U$ is a saddle point of $\bar{L}$ over $X\times U\times\mathbb{R}^{r}$
if and only if
$({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ is a saddle
point of $L$ over $X\times{}^{m}_{+}\times\mathbb{R}^{r}$.

##  3 Algorithms for solving saddle point formulation

With the robust problem (2) in the desired convex-concave structure (6), we
move towards introducing two algorithms for solving it. Before presenting
them, we show a property of the optimal dual solution
$({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})$ used for both algorithms
(either for running them or for obtaining their convergence guarantees).
Namely, thanks to Assumptions 1-3, we can bound (i) the optimal value of
${\boldsymbol{\lambda}}$, which implies that we can bound the sets $U^{i}$,
(ii) the optimal value of ${\mathbf{w}}$.

###### Proposition 2

Let Assumption 1 hold, let $\hat{{\mathbf{x}}}$ be the point satisfying
Assumption 2, let $({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$ be
a saddle point of $\bar{L}$ on the set $X\times U\times\mathbb{R}^{r}$, and
let $\underaccent{\bar}{v}$ be a strict lower bound on the optimal value of
problem (2). Then,
${\mathbf{u}}^{*}=({\mathbf{u}}^{*}_{1},\ldots,{\mathbf{u}}^{*}_{m})$, where
${\mathbf{u}}_{i}^{*}=(\tilde{{\mathbf{z}}}^{*}_{i},\lambda^{*}_{i})$, and
${\mathbf{w}}^{*}$ satisfy

$\displaystyle\lambda^{*}_{i}$
$\displaystyle\leq\bar{\lambda}:=\frac{{\mathbf{c}}^{\top}\hat{{\mathbf{x}}}-\underaccent{\bar}{v}}{-\min_{i\in[m]}f_{i}(\hat{{\mathbf{x}}})}$
$\displaystyle\|{\mathbf{u}}^{*}_{i}\|$
$\displaystyle\leq\bar{\lambda}\sqrt{1+R_{i}^{2}}$
$\displaystyle\|{\mathbf{w}}^{*}\|$ $\displaystyle\leq
R_{\mathbf{w}}:=\frac{1}{\sigma_{\min}({\mathbf{A}})}\left(\frac{{\mathbf{c}}^{\top}\hat{{\mathbf{x}}}-\underaccent{\bar}{v}}{\epsilon_{\hat{{\mathbf{x}}}}}+\|{\mathbf{c}}\|\right),$

where $R_{i}:=\max_{{\mathbf{z}}\in Z^{i}}\|{\mathbf{z}}\|$ and
$\sigma_{\min}({\mathbf{A}})>0$ is the smallest singular value of
${\mathbf{A}}$.

###### Proof

Boundedness of $\lambda^{*}_{i}$. Let ${\mathbf{x}}^{*}$ be an optimal
solution to (2). Let $\hat{{\mathbf{x}}}\in X$ be a Slater point. We have

$\displaystyle{\mathbf{c}}^{\top}{\mathbf{x}}^{*}$
$\displaystyle\leq{\mathbf{c}}^{\top}\hat{{\mathbf{x}}}+\sum_{i=1}^{m}\lambda^{*}_{i}f_{i}(\hat{{\mathbf{x}}})+({\mathbf{w}}^{*})^{\top}({\mathbf{A}}\hat{{\mathbf{x}}}-{\mathbf{b}})$
$\displaystyle={\mathbf{c}}^{\top}\hat{{\mathbf{x}}}+\sum_{i=1}^{m}\lambda^{*}_{i}f_{i}(\hat{{\mathbf{x}}})$
$\displaystyle\leq{\mathbf{c}}^{\top}\hat{{\mathbf{x}}}+\left\|{{\boldsymbol{\lambda}}^{*}}\right\|_{1}\max_{i\in[m]}f_{i}(\hat{{\mathbf{x}}})$

whence

$\left\|{{\boldsymbol{\lambda}}^{*}}\right\|_{1}\leq\frac{{\mathbf{c}}^{\top}(\hat{{\mathbf{x}}}-{\mathbf{x}}^{*})}{-\min_{i\in[m]}f_{i}(\hat{{\mathbf{x}}})}=\bar{\lambda}.$

Thus, we have that
$\lambda^{*}_{i}\leq\left\|{{\boldsymbol{\lambda}}^{*}}\right\|_{1}\leq\bar{\lambda}$
for all $i\in[m]$.

Boundedness of ${\mathbf{u}}_{i}^{*}$. Since
${\mathbf{u}}^{*}_{i}=(\tilde{{\mathbf{z}}}^{*}_{i},\lambda^{*}_{i})\in U^{i}$
we have that $\tilde{{\mathbf{z}}}^{*}_{i}\in\lambda^{*}_{i}Z^{i}$, by the
Cauchy-Schwartz inequality we have that
$\left\|{\tilde{{\mathbf{z}}}_{i}^{*}}\right\|\leq|\lambda^{*}_{i}|R_{i}\leq\bar{\lambda}R_{i}$.
Thus,
$\left\|{{\mathbf{u}}^{*}_{i}}\right\|^{*}=\left\|{\tilde{{\mathbf{z}}}_{i}^{*}}\right\|^{2}+|\lambda_{i}^{*}|^{2}\leq\bar{\lambda}^{2}(R_{i}^{2}+1)$.

Boundedness of ${\mathbf{w}}^{*}$ Consider the saddle point formulation:

$\displaystyle\inf\limits_{{\mathbf{x}}\in X}\sup\limits_{{\mathbf{u}}_{i}\in
U^{i},{\mathbf{w}}}{\mathbf{c}}^{\top}{\mathbf{x}}+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}({\mathbf{x}},{\mathbf{u}}_{i})=\inf\limits_{{\mathbf{x}}}\sup\limits_{{\mathbf{u}}_{i}\in
U^{i},{\mathbf{w}}}{\mathbf{c}}^{\top}{\mathbf{x}}+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}({\mathbf{x}},{\mathbf{u}}_{i})+\delta_{X}({\mathbf{x}})$

Assume ${\mathbf{x}}^{*}$, ${\mathbf{w}}^{*}$, ${\mathbf{u}}_{i}^{\ast}$ are
the saddle point of this problem. The optimality conditions of the problem
are:

$\displaystyle{\mathbf{A}}{\mathbf{x}}^{*}$ $\displaystyle={\mathbf{b}}$
$\displaystyle{\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}+\sum\limits_{i=1}^{m}{\boldsymbol{\alpha}}_{i}+{\boldsymbol{\beta}}$
$\displaystyle={\mathbf{0}}$

where
${\boldsymbol{\alpha}}_{i}\in\partial_{{\mathbf{x}}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i}^{*})$
and
${\boldsymbol{\beta}}\in\partial_{{\mathbf{x}}}\delta_{X}({\mathbf{x}}^{*})$.
Let $\hat{{\mathbf{x}}}\in\text{int}(X)$ be the Slater point so we have

$\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}}\in
X,\quad\tilde{g}_{i}(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}},{\mathbf{u}}_{i}^{*})\leq
0\ \qquad\
\forall{\boldsymbol{\kappa}}:\|{\boldsymbol{\kappa}}\|\leq\epsilon_{\hat{{\mathbf{x}}}}$
(7)

Since
${\boldsymbol{\alpha}}_{i}\in\partial_{{\mathbf{x}}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i}^{*})$,
we have that

$\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i}^{*})+{\boldsymbol{\alpha}}_{i}^{\top}\left(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}}-{\mathbf{x}}^{*}\right)\leq\tilde{g}_{i}(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}},{\mathbf{u}}_{i}^{*})$

so that

$\underbrace{\sum\limits_{i\in[m]}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i}^{*})}_{=0}+\sum\limits_{i\in[m]}{\boldsymbol{\alpha}}_{i}^{\top}\left(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}}-{\mathbf{x}}^{*}\right)\leq\underbrace{\sum\limits_{i\in[m]}\tilde{g}_{i}(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}},{\mathbf{u}}_{i}^{*})}_{\leq
0}$

where the first sum is equal to zero due to complementary slackness and the
second sum is nonpositive due to (7). Since
${\boldsymbol{\beta}}\in\partial_{{\mathbf{x}}}\delta_{X}({\mathbf{x}}^{*})$,
we also have that

$\delta_{X}({\mathbf{x}}^{*})+{\boldsymbol{\beta}}^{\top}(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}}-{\mathbf{x}}^{*})\leq\delta_{X}(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}})=0,$

which, combined with the optimality conditions, implies

$0\leq\left({\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}+\sum\limits_{i=1}^{m}{\boldsymbol{\alpha}}_{i}\right)^{\top}\left(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}}-{\mathbf{x}}^{*}\right)\leq\left({\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}\right)^{\top}\left(\hat{{\mathbf{x}}}+{\boldsymbol{\kappa}}-{\mathbf{x}}^{*}\right),\quad\forall\|{\boldsymbol{\kappa}}\|\leq\epsilon_{\hat{{\mathbf{x}}}}.$

This gives us the property

$\epsilon_{\hat{{\mathbf{x}}}}\left\|{\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}\right\|\leq\left({\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}\right)^{\top}\left(\hat{{\mathbf{x}}}-{\mathbf{x}}^{*}\right)$

Because
${\mathbf{A}}{\mathbf{x}}^{*}={\mathbf{A}}\hat{{\mathbf{x}}}={\mathbf{b}}$, we
obtain
$\epsilon_{\hat{{\mathbf{x}}}}\left\|{\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}\right\|\leq{\mathbf{c}}^{\top}\left(\hat{{\mathbf{x}}}-{\mathbf{x}}^{*}\right)$.
Since by Assumption 3, ${\mathbf{A}}$ has full row rank, by the reverse
triangle inequality we can bound ${\mathbf{w}}^{*}$ as follows:

$\epsilon_{\hat{{\mathbf{x}}}}\left(\sigma_{\text{min}}({\mathbf{A}}^{\top})\left\|{\mathbf{w}}^{*}\right\|-\left\|{\mathbf{c}}\right\|\right)\leq\epsilon_{\hat{{\mathbf{x}}}}\left(\left\|{\mathbf{A}}^{\top}{\mathbf{w}}^{*}\right\|-\left\|{\mathbf{c}}\right\|\right)\leq\epsilon_{\hat{{\mathbf{x}}}}\left\|{\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}\right\|\leq{\mathbf{c}}^{\top}\left(\hat{{\mathbf{x}}}-{\mathbf{x}}^{*}\right).$

∎

We now move to presenting the two algorithms, summarized in Table 1. We will
first state both for problem (6) and give their convergence without proofs. In
Section 4, we shall prove the convergence of a generalized problem in a
unified framework from which the ‘simple cases’ will follow as straightforward
corollaries.

The first algorithm, presented in Section 3.1, applies to the case with the
additional assumptions that $X$ is bounded and the functions $g_{i}$ have
bounded subgradients over $X\times Z^{i}$. For this setting, convergence rate
of $O(1/{\epsilon}^{2})$ is attained, similar to the one obtained by
ho2018online  under almost identical assumptions. In Section 3.2, we consider
the case where $g_{i}({\mathbf{x}},{\mathbf{z}}_{i})$ are biaffine functions
(or can be transformed to this form), and show that in this setting we can
obtain a superior convergence rate of $O(1/\epsilon)$.

Algorithm | SGSP | PAPC
---|---|---
Domain $X$ | Bounded | No restriction
Structure $g_{i}(\cdot)$ | Any | Biaffine or reducible to biaffine
Optimality convergence rate | $\mathcal{O}(1/\sqrt{N})$ | $\mathcal{O}(1/N)$
Feasibility convergence rate | $\mathcal{O}(1/\sqrt{N})$ | $\mathcal{O}(1/N)$
Slater point needed to compute the stepsize | Yes | No
Table 1: Comparison of the two saddle point algorithms.

###  3.1 Subgradient Saddle Point algorithm

In this section, we show how problem (6) can be solved using the SGSP
suggested in nedic2009subgradient . This algorithm requires that the both
primal and dual variables be contained in compact sets. Thus, we first need to
replace each set $U^{i}$ by its compact counterpart
$\tilde{U}^{i}=\\{(\tilde{{\mathbf{z}}}_{i},\lambda_{i})\in
U^{i}:\lambda_{i}\leq\bar{\lambda}\\}$. Indeed, by the property of
$\lambda^{*}$ presented in Proposition 2, this restriction of $U^{i}$ would
not change the set of saddle points of problem (6). Similarly, we can restrict
${\mathbf{w}}$ to reside in a set $W=\\{{\mathbf{w}}\in\mathbb{R}^{r}:\
\left\|{{\mathbf{w}}}\right\|\leq R_{\mathbf{w}}\\}$. Using these new sets,
the algorithm is as follows.

SGSP: SubGradient Algorithm for Saddle Point
Input: ${\tau>0},{\theta_{i}>0},\theta_{{\mathbf{w}}}>0$ for $i\in[m]$, and
$N\in\mathbb{N}$
Initialization. Initialize ${\mathbf{x}}^{0}\in X$ and
${\mathbf{u}}^{0}_{i}\in\tilde{U}^{i}$, for $i\in[m]$, ${\mathbf{w}}^{0}\in
W$.
General step: For $k\in[N]$
Compute subgradients
${\mathbf{v}}^{k}_{x}\in\partial_{\mathbf{x}}\bar{L}({\mathbf{x}}^{k},({\mathbf{u}}^{k},{\mathbf{w}}^{k}))$,
${\mathbf{v}}^{k}_{i}\in\partial_{{\mathbf{u}}_{i}}\left(-\bar{L}({\mathbf{x}}^{k},({\mathbf{u}}^{k},{\mathbf{w}}^{k}))\right)$,
for all $i\in[m]$ $\displaystyle{\mathbf{x}}^{k+1}$
$\displaystyle=P_{X}({\mathbf{x}}^{k}-\tau{\mathbf{v}}_{x}^{k}),$
$\displaystyle{\mathbf{u}}^{k+1}_{i}$
$\displaystyle=P_{\tilde{U}^{i}}({\mathbf{u}}_{i}^{k}-\theta_{i}{\mathbf{v}}_{i}^{k}),\qquad
i\in[m]$ $\displaystyle{\mathbf{w}}^{k+1}$
$\displaystyle=P_{W}({\mathbf{w}}^{k}+\theta_{\mathbf{w}}({\mathbf{A}}{\mathbf{x}}^{k}-{\mathbf{b}}))$

Note that the algorithm can be applied whenever the projections over
$\\{\tilde{U}^{i}\\}_{i\in[m]}$ and $X$ can be easily computed. We will see in
Section 4, that if any of the sets are intersections of multiple simpler sets,
we can utilize splitting methods that enable the use of projections only on
the components of the intersection. Moreover, note that at each iteration the
steps for all ${\mathbf{u}}_{i}$, ${\mathbf{x}}$ and ${\mathbf{w}}$ can be
done in parallel.

As in most algorithms solving saddle point problems, the SGSP algorithm’s
convergence is given in terms of the ergodic sequences, i.e., denoting

$\bar{{\mathbf{x}}}^{N}=\frac{1}{N}\sum_{k=1}^{N}{\mathbf{x}}^{k},\quad\bar{{\mathbf{u}}}^{N}=\frac{1}{N}\sum_{k=1}^{N}{\mathbf{u}}^{k},\quad\bar{{\mathbf{w}}}^{N}=\frac{1}{N}\sum_{k=1}^{N}{\mathbf{w}}^{k}$

the convergence result states the rate at which the sequence
$\\{\left(\bar{{\mathbf{x}}}^{N},\bar{{\mathbf{u}}}^{N},\bar{{\mathbf{w}}}^{N}\right)\\}_{N\in\mathbb{N}}$
converges to a saddle point. Here, we present the convergence in terms of the
total constraint violation and the distance from the optimal value.

###### Theorem 3.1

Let
$\\{{\mathbf{x}}^{k},{\mathbf{u}}^{k},{\mathbf{w}}^{k}\\}_{k\in\mathbb{N}}$ be
the sequences generated by the SGSP algorithm with step sizes

$\displaystyle\tau\coloneqq\
\tilde{\tau}/\sqrt{N},\quad\theta_{i}\coloneqq\tilde{\theta}_{i}/\sqrt{N},\quad\theta_{\mathbf{w}}\coloneqq\tilde{\theta}_{\mathbf{w}}/\sqrt{N}$

for $i\in[m]$. Assume that $X$ is compact and define
$R_{\mathbf{x}}:=\max_{{\mathbf{x}}\in X}\left\|{{\mathbf{x}}}\right\|$.
Further assume there exist constants $G_{\mathbf{x}}$, $G_{i}$ for $i\in[m]$
such that the subgradients $\\{{\mathbf{v}}_{x}^{k}\\}_{k\in\mathbb{N}}$,
$\\{{\mathbf{v}}_{i}^{k}\\}_{k\in\mathbb{N}}$, $i\in[m]$ generated by the
algorithm satisfy

$\left\|{{\mathbf{v}}^{k}_{x}}\right\|\leq
G_{\mathbf{x}},\;\left\|{{\mathbf{v}}^{k}_{i}}\right\|\leq
G_{i},\;i\in[m],\quad\forall k\in\mathbb{N}.$

Then, we have the following feasibility and optimality convergence guarantees.

$\displaystyle\sum_{i=1}^{m}[f_{i}(\bar{{\mathbf{x}}}^{N})]_{+}+\|{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}\|\leq$
$\displaystyle\frac{\max\\{2,\max_{i}\\{1+4R_{i}^{2}\\}\\}}{2\sqrt{N}}\left(\frac{2\max\\{\left\|{{\mathbf{x}}^{0}}\right\|^{2},R_{\mathbf{x}}^{2}\\}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{\bar{\lambda}+1,\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{R_{\mathbf{w}}+1,\|{\mathbf{w}}^{0}\|\\}^{2}}{\theta_{\mathbf{w}}}+\phi\right),$

and

$\displaystyle\left|{\mathbf{c}}^{\top}(\bar{{\mathbf{x}}}^{N}-{\mathbf{x}}^{*})\right|\leq$
$\displaystyle\frac{\max\\{2,\max_{i}\\{1+4R_{i}^{2}\\}\\}}{2\sqrt{N}}\left(\frac{2\max\\{\left\|{{\mathbf{x}}^{0}}\right\|^{2},R_{\mathbf{x}}^{2}\\}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{2\bar{\lambda},\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{2R_{\mathbf{w}},\|{\mathbf{w}}^{0}\|\\}^{2}}{\theta_{\mathbf{w}}}+\phi\right),$

where

$\phi:=\tilde{\tau}G_{\mathbf{x}}^{2}+\sum\limits_{i=1}^{m}\tilde{\theta}_{i}G_{i}^{2}+\tilde{\theta}_{\mathbf{w}}G_{\mathbf{w}}^{2},\quad
G_{\mathbf{w}}:=\left\|{{\mathbf{A}}}\right\|R_{\mathbf{x}}+\left\|{{\mathbf{b}}}\right\|,\quad
R_{i}:=\max_{{\mathbf{z}}\in Z^{i}}\|{\mathbf{z}}\|.$

Note that almost all conditions used in Theorem 3.1 are also needed in order
to apply the online first-order (OFO) approach of ho2018online . In fact, the
two approaches give similar convergence results with a few differences:

  1. 1.

_Assumptions._ SGSP requires the existence of a Slater point
$\hat{{\mathbf{x}}}$ while the OFO does not. Secondly, OFO requires
boundedness of the subgradients of $g({\mathbf{x}},\cdot)$ while SGSP requires
boundedness of the subgradients of its prespective function. In Section 3.3.2
we show that under mild assumptions on the problems, these requirements are
equivalent.

  2. 2.

_Implementation._ Since the OFO approach is meant to solve a feasibility,
rather than an optimality, problem, it requires to perform a binary search in
order to approximate the optimal value of (2). Thus, the number of needed
iteration to obtain feasibility and optimality guaranties is increased by a
factor of $\log(1/\epsilon)$. In the SGSP in turn, we do not need to perform
bi-section, however we must find a Slater point $\hat{{\mathbf{x}}}$, the
values of $f_{i}(\hat{{\mathbf{x}}})$ for $i\in[m]$, and
$\epsilon_{\hat{{\mathbf{x}}}}$, as well as a lower bound on the objective
function $\underaccent{\bar}{v}$, which are needed to compute both
$\bar{\lambda}$ and $R_{{\mathbf{w}}}$. While in some cases it may be easy to
find these quantities, in general it requires solving an auxiliary
optimization problem, as we discuss in Section 3.3.1.

  3. 3.

_Projections._ While OFO requires projections on sets $X$ and $Z^{i}$, SGSP
requires projection onto $X$ and the lifted set $\tilde{U}^{i}$. In Section
3.3.3 we show that for standard simple sets $Z^{i}$ the projections onto
$\tilde{U}^{i}$ can be simply computed.

  4. 4.

_Constants._ Although the convergence rate of both methods is
$O(1/\epsilon^{2})$, the constants obtained by the SGSP algorithm are worse
then those of OFO, if the same first order method (subgradient/mirror decent)
is used.

###  3.2 Proximal-Alternating Predictor Corrector

In this section, we present an algorithm with a superior rate of convergence
of $O(1/\epsilon)$ which does not require boundedness of $X$. This algorithm
requires the additional assumption that the functions
$g_{i}({\mathbf{x}},{\mathbf{z}}_{i})$ have a biaffine form:

$g_{i}({\mathbf{x}},{\mathbf{z}}_{i})={\mathbf{x}}^{\top}{\mathbf{Q}}_{i}{\mathbf{z}}_{i}+{\mathbf{d}}_{i}^{\top}{\mathbf{x}}+{\mathbf{q}}_{i}^{\top}{\mathbf{z}}_{i}+\gamma_{i}.$
(8)

and that the primal variable is not constrained. In Remark 1, we show how more
general problems of the form
$g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\coloneqq{\mathbf{h}}_{i}({\mathbf{x}})^{\top}{\mathbf{k}}_{i}({\mathbf{z}}_{i})$
with convex and concave ${\mathbf{h}}_{i}$ and ${\mathbf{k}}_{i}$,
respectively, can be reformulated to fit this case.

In order to state the algorithm, we first perform two operations on our
problem: (i) simplify its form due to the bi-linear structure, and (ii)
eliminate the explicit constraint $x\in X$ by dualizing it. Indeed, under (8)
function $\bar{L}$ reduces to

$\bar{L}({\mathbf{x}},{\mathbf{u}})\coloneqq{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\left({\mathbf{x}}^{\top}\tilde{{\mathbf{Q}}}_{i}{\mathbf{u}}_{i}+\tilde{{\mathbf{q}}}_{i}^{\top}{\mathbf{u}}_{i}\right)+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})={\mathbf{c}}^{\top}{\mathbf{x}}+{\mathbf{x}}^{\top}{\mathbf{A}}^{\top}{\mathbf{w}}+{\mathbf{x}}^{\top}\tilde{{\mathbf{Q}}}{\mathbf{u}}+\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}-{\mathbf{b}}^{\top}{\mathbf{w}},$

where,

$\tilde{{\mathbf{Q}}}_{i}=\begin{bmatrix}{\mathbf{Q}}_{i}&{\mathbf{d}}_{i}\end{bmatrix},\;\tilde{{\mathbf{q}}}_{i}=\begin{bmatrix}{\mathbf{q}}_{i}\\\
\gamma_{i}\end{bmatrix},\;\tilde{{\mathbf{Q}}}=(\tilde{{\mathbf{Q}}}_{1}^{\top},\ldots,\tilde{{\mathbf{Q}}}_{m}^{\top})^{\top},\;\tilde{{\mathbf{q}}}=(\tilde{{\mathbf{q}}}_{1}^{\top},\ldots,\tilde{{\mathbf{q}}}_{m}^{\top})^{\top}.$
(9)

In order to eliminate the restriction of ${\mathbf{x}}$ to lies in the set
$X$, we use the so-called _dual transportation trick_ , _i.e._ , dualizing the
indicator function of the domain set $X$. Thus, for the second transformation,
we shall use the indicator function $\delta_{X}$, and its dual representation
through the support function $\sigma_{X}$ given by:

$\delta_{X}({\mathbf{x}})=(\sigma_{X})^{*}({\mathbf{x}})=\sup_{{\boldsymbol{\pi}}\in{}^{n}}\left\\{{\boldsymbol{\pi}}^{\top}{\mathbf{x}}-\sigma_{X}({\boldsymbol{\pi}})\right\\},$

to obtain:

$\displaystyle\min_{{\mathbf{x}}\in X}\max_{{\mathbf{u}}\in
U,{\mathbf{w}}}\bar{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}}))$
$\displaystyle=$
$\displaystyle\min_{{\mathbf{x}}\in{}^{n}}\max_{{\mathbf{u}}\in
U,{\mathbf{w}}}{\mathbf{c}}^{\top}{\mathbf{x}}+\delta_{X}({\mathbf{x}})+{\mathbf{x}}^{\top}{\mathbf{A}}^{\top}{\mathbf{w}}+{\mathbf{x}}^{\top}\tilde{{\mathbf{Q}}}{\mathbf{u}}+\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}-{\mathbf{b}}^{\top}{\mathbf{w}}$
$\displaystyle=$
$\displaystyle\inf_{{\mathbf{x}}\in{}^{n}}\sup_{{\mathbf{u}}\in
U,{\boldsymbol{\pi}}\in{}^{n},{\mathbf{w}}}\tilde{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}},{\boldsymbol{\pi}}))\coloneqq{\mathbf{x}}^{\top}\left({\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}+\tilde{{\mathbf{Q}}}{\mathbf{u}}+{\boldsymbol{\pi}}\right)+\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}-{\mathbf{b}}^{\top}{\mathbf{w}}-\sigma_{X}({\boldsymbol{\pi}})$
(10) $\displaystyle=$
$\displaystyle\inf_{{\mathbf{x}}\in{}^{n}}\sup_{{\mathbf{y}}=({\mathbf{u}},{\mathbf{w}},{\boldsymbol{\pi}}),\
{\mathbf{u}}\in
U,{\boldsymbol{\pi}}\in{}^{n}}{\mathbf{c}}^{\top}{\mathbf{x}}+{\mathbf{x}}^{\top}\bar{{\mathbf{Q}}}{\mathbf{y}}+\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}-{\mathbf{b}}^{\top}{\mathbf{w}}-\sigma_{X}({\boldsymbol{\pi}})\equiv\tilde{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}},{\boldsymbol{\pi}}))$

where

$\bar{{\mathbf{Q}}}=\left[\begin{array}[]{ccc}\tilde{{\mathbf{Q}}},&{\mathbf{A}}^{\top},&{\mathbf{I}}\end{array}\right]$

The following lemma states that since the function
$\bar{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}}))$ has a saddle point, the
order of $\inf$ and $\sup$ in the above problem can be changed, and the
function
$\tilde{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}},{\boldsymbol{\pi}}))$ has a
saddle point.

###### Lemma 1

Let Assumptions 1-3 hold. Then,
$({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$ is a saddle point of
function $\bar{L}$ over $X\times U\times{}^{r}$ if and only if there exists a
${\boldsymbol{\pi}}^{*}$ such that
$({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*},{\boldsymbol{\pi}}^{*}))$
is a saddle point of $\tilde{L}$ over
${}^{n}\times(U\times{}^{r}\times{}^{n})$.

Having stated the necessary equivalence of saddle points result, we now state
the PAPC algorithm of drori2015209  for solving problem (10).

PAPC: Proximal Alternating Predictor–Corrector
Input: ${\tau>0},{\theta_{i}>0}$ for $i\in[m]$, and $N\in\mathbb{N}$
Initialization. Initialize ${\mathbf{x}}^{0}\in{}^{n}$,
${\mathbf{y}}^{0}=({\mathbf{u}}^{0},{\mathbf{w}}^{0},{\boldsymbol{\pi}}^{0})\in
U\times{}^{r}\times{}^{m}$.
General step: For $k\in[N]$ $\displaystyle{\mathbf{p}}^{k}$
$\displaystyle={\mathbf{x}}^{k-1}-\tau\left({\mathbf{c}}+\bar{{\mathbf{Q}}}{\mathbf{y}}^{k-1}\right),$
$\displaystyle{\mathbf{u}}^{k}_{i}$
$\displaystyle=P_{U^{i}}\left({\mathbf{u}}^{k-1}_{i}+\theta_{i}(\tilde{{\mathbf{Q}}}_{i}^{\top}{\mathbf{p}}^{k}+\tilde{{\mathbf{q}}}_{i})\right),\qquad
i\in[m]$ $\displaystyle{\mathbf{w}}^{k}$
$\displaystyle={\mathbf{w}}^{k-1}+\theta_{\mathbf{w}}({\mathbf{A}}{\mathbf{p}}^{k}-{\mathbf{b}})$
$\displaystyle{\boldsymbol{\pi}}^{k}$
$\displaystyle=\operatorname{prox}_{\theta_{{\boldsymbol{\pi}}}\sigma_{X}}({\boldsymbol{\pi}}^{k-1}+\theta_{{\boldsymbol{\pi}}}{{\mathbf{p}}}^{k})$
$\displaystyle{\mathbf{y}}^{k}$
$\displaystyle=({\mathbf{u}}^{k},{\mathbf{w}}^{k},{\boldsymbol{\pi}}^{k})$
$\displaystyle{\mathbf{x}}^{k}$
$\displaystyle={\mathbf{x}}^{k-1}-\tau\left({\mathbf{c}}+\bar{{\mathbf{Q}}}{\mathbf{y}}^{k}\right).$

With respect to the used proximal operator, note that using the Moreau
identity we have that for any ${\mathbf{y}}\in{}^{n}$

$\text{prox}_{\theta_{{\boldsymbol{\pi}}}\sigma_{X}}({\mathbf{y}})={\mathbf{y}}-\theta_{{\boldsymbol{\pi}}}P_{X}\left(\frac{{\mathbf{y}}}{\theta_{{\boldsymbol{\pi}}}}\right).$

Thus, similarly to the SGSP algorithm, PAPC can be applied whenever the
projections over $U^{i}$ and $X$ are easily computed.

Similarly to the SGSP, convergence results for the PAPC are in terms of the
ergodic sequence. To state them, we define square matrices
${\mathbf{S}}_{i}=\theta_{i}^{-1}{\mathbf{I}}_{\tilde{d}_{i}}$for $i\in[m]$,
${\mathbf{S}}_{m+1}=\theta_{\mathbf{w}}^{-1}{\mathbf{I}}_{r}$,
${\mathbf{S}}_{m+2}=\theta_{\boldsymbol{\pi}}^{-1}{\mathbf{I}}_{n}$ and
${\mathbf{S}}=\operatorname*{Diag}\left(\left[{\mathbf{S}}_{1},\ldots,{\mathbf{S}}_{m+2}\right]\right)$.

###### Theorem 3.2

Let Assumptions 1 and 2 hold and let
$\\{{\mathbf{x}}^{k},{\mathbf{w}}^{k},{\mathbf{v}}^{k}\\}_{k\in\mathbb{N}}$ be
the sequence generated by the PAPC algorithm with some $\tau>0$,
$\theta_{i}>0$, $i\in[m]$, $\theta_{\mathbf{w}}>0$ such that
${\mathbf{H}}={\mathbf{S}}-\tau\bar{{\mathbf{Q}}}^{\top}\bar{{\mathbf{Q}}}\succ
0$. Define

$R_{\boldsymbol{\pi}}:=\left\|{{\mathbf{c}}}\right\|+\bar{\lambda}\sum_{i=1}^{m}\left\|{\tilde{{\mathbf{Q}}}_{i}}\right\|(R_{i}+1)$

Then, for any $\alpha>0$ we have the following convergence guarantees:

$\displaystyle\sum_{i=1}^{N}[f_{i}(\bar{{\mathbf{x}}}^{N})]_{+}+\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|+\alpha\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)\leq$
$\displaystyle\frac{\max\\{2,\max_{i}(1+4R_{i}^{2})\\}}{2N}\left({\small\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{\bar{\lambda}+1,\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{R_{\mathbf{w}}+1,\|{\mathbf{w}}^{0}\|\\}^{2}}{\theta_{\mathbf{w}}}+\frac{1+(1+\alpha)^{2}}{\theta_{\boldsymbol{\pi}}}}\right),$

and

$\displaystyle\left|{\mathbf{c}}^{\top}(\bar{{\mathbf{x}}}^{N}-{\mathbf{x}}^{*})\right|\leq$
$\displaystyle\frac{\max\\{2,\max_{i}(1+4R_{i}^{2})\\}}{2N}\left({\small\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{2\bar{\lambda},\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{2R_{\mathbf{w}},\|{\mathbf{w}}^{0}\|\\}^{2}}{\theta_{\mathbf{w}}}+\frac{1+R_{\boldsymbol{\pi}}^{2})}{\theta_{\boldsymbol{\pi}}}}\right).$

###  3.3 Numerical implementation of saddle point algorithms

In this section, we discuss some technical aspects related to the
implementation of the above algorithms. These aspects relate to (i) finding a
Slater point for the SGSP algorithm using SGSP algorithm of an auxiliary
problem, (ii) computing subgradients of the lifted functions $\tilde{g}_{i}$
from the subgradients of the original functions $g_{i}$, (iii) computing
projections onto the lifted sets $U^{i}$.

####  3.3.1 Search for a Slater point in the SGSP algorithm

To run the SGSP algorithm, we require parameter values dependent on the
features of a Slater point of the problem. Therefore, before SGSP is run, we
first need to identify a Slater point and plug the appropriate values into the
algorithm. To find such a point, we need to solve the following optimization
problem

$\displaystyle\min\limits_{{\mathbf{x}},t}\ $ $\displaystyle t$ (11) s.t.
$\displaystyle\max\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\leq t$ $\displaystyle\forall
i\in[m]$ $\displaystyle{\mathbf{A}}{\mathbf{x}}={\mathbf{b}}$

This problem satisfies the Slater condition for any
${\mathbf{x}}^{0}\in\text{int}(X)$,
${\mathbf{A}}{\mathbf{x}}^{0}={\mathbf{b}}$, and $t=t^{0}+\delta$ such that

${t}^{0}=\max_{i\in[m]}\max\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({{\mathbf{x}}}^{0},{\mathbf{z}}_{i}).$

For that reason, we can first apply the SGSP algorithm to this problem by
transforming it to a saddle point form. To keep the domain of
$({\mathbf{x}},t)$ compact, we can restrict $t$ to belong to the interval
$[-1,\bar{t}]$ where $\bar{t}={t}^{0}+\delta$.

If we assume that the subgradients in the SGSP algorithm for the original
problem (2) are bounded, then it also holds for (11). Thus, one can run the
SGSP algorithm for (11), knowing that it will converge to the optimal value of
$t$. A complication is the moment at which the algorithm stops. Assuming that
the original problem satisfies the Slater condition with constant $\epsilon$
we would like to stop when both optimality and feasibility conditions are
satisfied with $\frac{\epsilon}{3}$ thus ensuring that the
$(\hat{{\mathbf{x}}},\hat{t})$ obtained by the procedure satisfies

$\max\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}(\hat{{\mathbf{x}}},{\mathbf{z}}_{i})\leq\hat{t}+\frac{\epsilon}{3}\leq
t^{*}+\frac{\epsilon}{3}+\frac{\epsilon}{3}=-\frac{\epsilon}{3}.$

However, in practice, $\epsilon$ can be unknown in advance, and therefore, we
construct a search procedure as follows:

Slater Point Search
Input: ${\tau>0},{\theta_{i}>0}$ for $i\in[m]$, $\delta>0$, $K=2$
Initialization. Initialize ${\mathbf{x}}^{0}\in\text{int}(X)$,
$t^{0}=\max_{i\in[m]}f_{i}({{\mathbf{x}}}^{0})+\delta$ and
${\mathbf{u}}^{0}_{i}\in U^{i}$, for $i\in[m]$.
General step: For $k\in 1,2,\ldots$
1. Run SGSP for the Lagrangian form of problem (11) starting from point $({\mathbf{x}}^{k-1},t^{k-1})$ and ${\mathbf{u}}^{k-1}$ for $K$ iterations, and obtain the ergodic values $({\mathbf{x}}^{k},t^{k})$ and ${\mathbf{u}}^{k}$.
2. Update $t^{k}=\max_{i\in[m]}f_{i}({{\mathbf{x}}}^{k})$.
3. If $t^{k}<0$ stop and return the Slater point $\hat{{\mathbf{x}}}={\mathbf{x}}^{k}$ and the Slater value $\epsilon=-t^{k}$.
Otherwise, update $\bar{t}=\min\\{\bar{t},t^{k}+\delta\\}$, $k=k+1$ and
$K=2K$.

As stated above, this procedure is guaranteed to converge. Moreover, since
${\mathbf{x}}^{0}\in\text{int}(X)$ then by properties of convex sets we will
also obtain that for each $k$ the iterate
${{\mathbf{x}}}^{k}\in\text{int}(X)$, as the average of points in $X$ with one
of them in the interior.

####  3.3.2 Determining the subgradients of $\tilde{g}_{i}$ from subgradients
of $g_{i}$

In order to prove the convergence of SGSP we require that the subgradients of
the perspective function $\tilde{g}_{i}$ are bounded. In this section, we show
that the subgradients of $\tilde{g}_{i}$ can be easily derived from
subgradients of $g_{i}$. Moreover, we will also show that under the following
mild assumptions the boundedness of the subgradients of $\tilde{g}_{i}$
follows from the boundedness of the subgradients of $g_{i}$.

###### Assumption 4

For every $Z^{i}$ there exists a constant $\epsilon_{i}>0$ such that
$B({\mathbf{0}},\epsilon_{i})\subseteq Z^{i}$.

###### Assumption 5

There exists a constant $\bar{\mu}_{i}>0$ such that
$-g_{i}({\mathbf{x}},{\mathbf{0}})\leq\bar{\mu}_{i}$ for any feasible
${\mathbf{x}}$ of problem (2).

Assumption 4 is a standard RO assumption that the uncertainty set is full
dimensional, note that this is always true, since under a linear
transformation we can always reduce the dimension of $Z^{i}$. Assumption 5
states the following: the feasible set of the robust problem does not contain
rays that make any of the constraints of the ‘nominal problem’ (where
${\mathbf{z}}=0$) be arbitrarily satisfied, i.e., make
$g_{i}({\mathbf{x}},{\mathbf{0}})$ arbitrarily small. We note that this
assumption can be verified by checking the following sufficient condition:

$\min\left\\{g_{i}({\mathbf{x}},{\mathbf{0}}):\;{\mathbf{x}}\in
X,\;g_{j}({\mathbf{x}},{\mathbf{0}})\leq 0,\forall
j\in[m]\setminus\\{i\\}\right\\}>-\infty,\;\forall i\in[m],$

which can, in turn, be shown to hold by solving $m$ convex (non-robust)
optimization problems.

In the course of the SGSP algorithm, one needs to compute the subgradients of
the perspective functions $\tilde{g}_{i}({\mathbf{x}},{\mathbf{u}})$. Ideally,
this is done using the subgradients of the original functions
$g_{i}({\mathbf{x}},{\mathbf{z}})$, which should typically be available. The
following lemma provides a ‘recipe’ for doing exactly this. The ‘recipe’ is
based on the convex analysis results for perspective functions of
combettes2018perspective .

###### Lemma 2

Let ${\mathbf{x}}\in X$ and
${\mathbf{u}}_{i}=(\tilde{{\mathbf{z}}}_{i},\lambda_{i})\in U^{i}$ for all
$i\in[m]$.

  * (i)

If
${\mathbf{v}}_{x}\in\partial_{\mathbf{x}}\bar{L}({\mathbf{x}},{\mathbf{u}})$,
${\mathbf{v}}_{i}\in\partial_{{\mathbf{u}}_{i}}\left(-\bar{L}({\mathbf{x}},{\mathbf{u}})\right)$,
then they are of the following form

$\displaystyle{\mathbf{v}}_{{\mathbf{x}}}={\mathbf{c}}+{\mathbf{d}}_{x}$ (12)
$\displaystyle{\mathbf{v}}_{i}=\begin{cases}\left({\mathbf{d}}_{i},-g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}}\right)-\frac{\tilde{{\mathbf{z}}}_{i}^{\top}{\mathbf{d}}_{i}}{\lambda_{i}}\right),&\lambda_{i}>0,\\\
({\mathbf{d}}_{i},\phi_{i}),&\text{otherwise}\end{cases}$ (13)

where
${\mathbf{d}}_{x}\in\sum_{i:\lambda_{i}>0}\lambda_{i}\partial_{\mathbf{x}}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}}\right)$,
${\mathbf{d}}_{i}\in\partial_{{\mathbf{z}}_{i}}\left(-g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}}\right)\right)$
for all $i\in[m]$ such that $\lambda_{i}>0$, and
${\mathbf{d}}_{i}\in\cup_{{\mathbf{z}}_{i}\in{}^{d_{i}}}\left(\partial_{{\mathbf{z}}_{i}}(-g_{i})\left({\mathbf{x}},{\mathbf{z}}_{i}\right)\right)$,
$\phi_{i}+(-g_{i})^{*}({\mathbf{x}},{\mathbf{d}}_{i})\leq 0$ for all $i\in[m]$
such that $\lambda_{i}=0$.

  * (ii)

Let ${\mathbf{z}}_{i}=\tilde{{\mathbf{z}}}_{i}/\lambda_{i}$ if $\lambda_{i}>0$
and ${\mathbf{z}}_{i}={\mathbf{0}}$ otherwise, and let
$\tilde{{\mathbf{d}}}_{x,i}\in\partial_{{\mathbf{x}}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})$
and
$\tilde{{\mathbf{d}}}_{z,i}\in\partial_{{\mathbf{z}}_{i}}\left(-g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\right)$
for all $i\in[m]$. Then,

$\displaystyle{\mathbf{v}}_{x}={\mathbf{c}}+\sum_{i=1}^{m}\lambda_{i}{\mathbf{d}}_{x,i}\in\partial_{\mathbf{x}}\bar{L}({\mathbf{x}},{\mathbf{u}})\text{
and
}{\mathbf{v}}_{i}=({\mathbf{d}}_{z,i},-g_{i}({\mathbf{x}},{\mathbf{z}}_{i})-({\mathbf{z}}_{i})^{\top}{\mathbf{d}}_{z,i})\in\partial_{{\mathbf{u}}_{i}}\left(-\bar{L}({\mathbf{x}},{\mathbf{u}})\right).$

####  3.3.3 Computing the projections

In this section, we discuss the projections needed to apply SGSP and PAPC.
Specifically, we will discuss how to project on set $U^{i}$ and
$\tilde{U}^{i}$, which are more complicated than $Z^{i}$. We shall assume that
the projection on set $Z^{i}$ is simple and formulate the projection on
$U^{i}$ in its terms. Note that, in this paper, we use $U^{i}$

$U^{i}=\\{(\tilde{{\mathbf{z}}}_{i},\lambda_{i}):\tilde{{\mathbf{z}}}_{i}\leq\lambda_{i}Z^{i},\lambda_{i}\geq
0\\}.$ (14)

for the PAPC setting, and $\tilde{U}^{i}$

$\tilde{U}^{i}=\\{(\tilde{{\mathbf{z}}}_{i},\lambda_{i}):\tilde{{\mathbf{z}}}_{i}\leq\lambda_{i}Z^{i},\;0\leq\lambda_{i}\leq\bar{\lambda}\\},$
(15)

which uses an additional upper bound on $\lambda_{i}$ for the more general
SGSP setting. We will start by showing a general way to compute the projection
over $U^{i}$.

###### Proposition 3

The projection of
${\mathbf{u}}_{i}=(\tilde{{\mathbf{z}}}_{i},\lambda_{i})\in{}^{d_{i}+1}$ on
the set $U^{i}$ defined by (14) is given by

$P_{U^{i}}({\mathbf{u}}_{i})=\begin{cases}{\mathbf{u}}_{i}&{\mathbf{u}}_{i}\in
U^{i}\\\
\left(\mu^{*}P_{Z^{i}}\left(\frac{\tilde{{\mathbf{z}}}_{i}}{\mu^{*}}\right),\mu^{*}\right)&{\mathbf{u}}_{i}\notin
U^{i},\sigma_{Z^{i}}(\tilde{{\mathbf{z}}}_{i})>-\lambda_{i}\\\
{\mathbf{0}}&\text{otherwise}\end{cases}$

where $\mu^{*}>0$ is the unique solution of

$\mu\left\|{P_{Z^{i}}\left(\frac{\tilde{{\mathbf{z}}}_{i}}{\mu}\right)}\right\|^{2}-\tilde{{\mathbf{z}}}_{i}^{\top}P_{Z^{i}}\left(\frac{\tilde{{\mathbf{z}}}_{i}}{\mu}\right)+\mu-\lambda_{i}=0.$

The same technique used to prove Proposition 3 can be used for the proof of
projection over $\tilde{U}^{i}$.

###### Corollary 1

The projection of
${\mathbf{u}}_{i}=(\tilde{{\mathbf{z}}}_{i},\lambda_{i})\in{}^{d_{i}+1}$ on
the set $\tilde{U}^{i}$ defined by (15) is given by

$P_{\tilde{U}^{i}}({\mathbf{u}}_{i})=\left(\mu^{*}P_{Z^{i}}\left(\frac{\tilde{{\mathbf{z}}}_{i}}{\mu^{*}}\right),\mu^{*}\right)$

where $\mu^{*}=\max\\{\min\\{\tilde{\mu},\bar{\lambda}\\},0\\}$ with
$\tilde{\mu}$ being the unique solution of

$\tilde{\mu}\left\|{P_{Z^{i}}\left(\frac{\tilde{{\mathbf{z}}}_{i}}{\tilde{\mu}}\right)}\right\|^{2}-\tilde{{\mathbf{z}}}_{i}^{\top}P_{Z^{i}}\left(\frac{\tilde{{\mathbf{z}}}_{i}}{\tilde{\mu}}\right)+\tilde{\mu}-\lambda_{i}=0,$

and $0P_{Z^{i}}\left(\frac{\tilde{{\mathbf{z}}}_{i}}{0}\right)=0$.

Proposition 3 and Corollary 1 suggest that we can always obtain the projection
onto sets $U^{i}$ and $\tilde{U}^{i}$, which are the conic extension of
$Z^{i}$, by applying a bi-section procedure to find the value of $\mu$ that
satisfies the appropriate equality constraint.

Table 2 illustrates three examples, the $\ell_{2}$, $\ell_{\infty}$,
$\ell_{1}$ balls, for which the projection onto $Z^{i}$ is obtained either
analytically or in $O(n)$, and similarly the value of the optimal $\mu^{*}$,
and therefore the projections onto their conic extensions can also be computed
in $O(n)$.

Table 2: Examples of projections onto $\tilde{U}$

$Z^{i}$ | $P_{Z^{i}}({\mathbf{y}})$ | $P_{\tilde{U}^{i}}({\mathbf{y}},\lambda)=\left(\mu^{*}P_{Z^{i}}\left(\frac{{\mathbf{y}}}{\mu^{*}}\right),\mu^{*}\right)$
---|---|---
$\\{{\mathbf{z}}:\left\|{{\mathbf{z}}}\right\|_{2}\leq 1\\}$ | $\begin{cases}{\mathbf{y}}&{\mathbf{y}}\in Z\\\ \frac{{\mathbf{y}}}{\left\|{{\mathbf{y}}}\right\|}&\text{otherwise}\end{cases}$ |  $\mu^{*}=\max\left\\{\min\left\\{\frac{\lambda+{\left\|{{\mathbf{y}}}\right\|_{2}}}{2},\bar{\lambda}\right\\},0\right\\}$22footnotemark: 2
$\\{{\mathbf{z}}:\left\|{{\mathbf{z}}}\right\|_{\infty}\leq 1\\}$ | $\min\left\\{{\mathbf{e}},{|{\mathbf{y}}|}\right\\}\circ\text{sign}({\mathbf{y}})$ |  $\mu^{*}=\min\left\\{\frac{\sum_{i\leq j^{*}}|q_{(i)}|+\lambda}{j^{*}+1},\bar{\lambda}\right\\}$22footnotemark: 2 $j^{*}=\max\left\\{j\in[d]:|q_{(j)}|\geq\frac{\sum_{i\leq j}|q_{(i)}|+\lambda}{j+1}\right\\}$11footnotemark: 1.
$\\{{\mathbf{z}}:\left\|{{\mathbf{z}}}\right\|_{1}\leq 1\\}$ |  $\max\\{|{\mathbf{q}}|-\theta^{*}{\mathbf{e}},{\mathbf{0}}\\}\circ\text{sign}({\mathbf{q}})$ where $\theta^{*}=\frac{\sum_{i\leq j^{*}}|q_{(i)}|-1}{j^{*}}$ $j^{*}=\max\left\\{j\in[d]:|q_{(j)}|\geq\frac{\sum_{i\leq j}|q_{(i)}|-1}{j}\right\\}$11footnotemark: 1. |  $\mu^{*}=\min\left\\{\frac{\sum_{i\leq j^{*}}|q_{(i)}|+\lambda}{j^{*}+1},\bar{\lambda}\right\\}$22footnotemark: 2 $j^{*}=\max\left\\{j\in[d]:|q_{(j)}|\geq\frac{\sum_{i\leq j}|q_{(i)}|-\lambda}{j+1}\right\\}$11footnotemark: 1.

  * 1

If the problem is not feasible $j^{*}=-\infty$

  * 2

For projection over $U^{i}$ set $\bar{\lambda}=\infty$

##  4 Convergence

###  4.1 EB algorithms

In order to unify analysis for all forms of the Lagrangian function and the
algorithms presented in this paper, we define now sufficient properties needed
for an algorithm to prove the feasibility and optimality convergence. These
sufficient properties will take the form of the algorithm being an
_ergodically bounded_ (EB) algorithm, as the following definition states.

###### Definition 1

Let $\mathcal{A}$ be an iterative algorithm to solve the saddle point problem
(2). We call the algorithm $\mathcal{A}$ _$\psi$ -ergodic bounded_ ($\psi$-EB)
if there exist constant scalars $\phi,\tau,\beta\geq 0$,
$\theta_{i},\theta_{\mathbf{w}}\in{}_{+}$, and a function
$\psi(N):\mathbb{N}\rightarrow{}_{+}$ with $\psi(N)\downarrow 0$ as
$N\rightarrow+\infty$, such that for any initial point
$({\mathbf{x}}^{0};{\boldsymbol{\lambda}}^{0},{\mathbf{w}}^{0})$ the algorithm
$\mathcal{A}$ generates a sequence
$\\{({\mathbf{x}}^{k},{\boldsymbol{\lambda}}^{k},{\mathbf{w}}^{k})\\}_{k\in\mathbb{N}}$
satisfying

$\displaystyle
L(\bar{{\mathbf{x}}}^{N},({\boldsymbol{\lambda}},{\mathbf{w}}))-L({\mathbf{x}}^{*},({{\boldsymbol{\lambda}}}^{*},{\mathbf{w}}^{*}))+\alpha\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)\leq$
$\displaystyle\qquad\qquad\psi(N)\left(\tau^{-1}\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}+\sum_{i=1}^{m}\theta_{i}^{-1}\max\\{\lambda_{i},\lambda_{i}^{0}\\}^{2}+\theta_{{\mathbf{w}}}^{-1}\max\\{\left\|{{\mathbf{w}}}\right\|,\left\|{{\mathbf{w}}^{0}}\right\|\\}^{2}+\phi(1+\alpha^{2})\right),$

and

$L(\bar{{\mathbf{x}}}^{N};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})-L({\mathbf{x}}^{*};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})+\beta\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)\geq
0.$

for all iterations $N\in\mathbb{N}$, dual variables
${\boldsymbol{\lambda}}\in{}^{m}_{+}$, ${\mathbf{w}}\in{}^{r}$, parameters
$\alpha\geq 0$ and saddle points
$({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ of (4).

The following theorem shows that the ergodic sequence of any $\psi$-EB
algorithm converges to feasibility and optimality at the rate at which $\psi$
converges to zero.

###### Theorem 4.1

Let problem (2) satisfy Assumption 1 and 2. Let $\mathcal{A}$ be an $\psi$-EB
algorithm to solve the saddle point problem (2) with parameters
$\phi,\tau,\beta$ and ${\boldsymbol{\theta}}$. For a given starting point
$({\mathbf{x}}^{0},({\boldsymbol{\lambda}}^{0},{\mathbf{w}}^{0}))\in{}^{n}\times{}_{+}^{m}\times{}^{p}$
let $\bar{{\mathbf{x}}}^{N}$ be the ergodic primal sequence generated by the
algorithm. Then, for any optimal solution ${\mathbf{x}}^{*}$ to (2) we have
that

$\displaystyle\sum_{i=1}^{m}[f_{i}(\bar{{\mathbf{x}}}^{N})]_{+}+\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|+\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)\leq$
$\displaystyle\quad\psi(N)\left(\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{\bar{\lambda}+1,\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{R_{\mathbf{w}}+1,\left\|{{\mathbf{w}}^{0}}\right\|\\}^{2}}{\theta_{{\mathbf{w}}}}+\phi(1+(1+\beta)^{2})\right),$

and

$\displaystyle|{\mathbf{c}}^{\top}(\bar{{\mathbf{x}}}^{N}-{\mathbf{x}}^{*})|\leq$
$\displaystyle\qquad\psi(N)\left(\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{2\bar{\lambda},\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{2R_{\mathbf{w}},\left\|{{\mathbf{w}}^{0}}\right\|\\}^{2}}{\theta_{{\mathbf{w}}}}+\phi(1+4\beta^{2})\right).$

###### Proof

Let $\kappa_{1}>0$ and let ${\mathbf{r}}\in{}_{+}^{m}$ be a multiplication of
indicator vector of constraint violations by $\kappa_{1}$, _i.e._ :

$r_{i}=\begin{cases}\kappa_{1},&f_{i}(\bar{{\mathbf{x}}}^{N})>0,\\\
0,&\text{otherwise},\end{cases},\ i\in[m]$

and let ${\boldsymbol{\lambda}}={\boldsymbol{\lambda}}^{*}+{\mathbf{r}}$ and
let $\kappa_{2}>0$ and
${\mathbf{w}}={\mathbf{w}}^{*}+\kappa_{2}\frac{\left({\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}\right)}{\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|}$
where $({\mathbf{x}}^{*};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})$ is a
saddle point of (3). Then,

$\displaystyle L(\bar{{\mathbf{x}}}^{N};{\boldsymbol{\lambda}},{\mathbf{w}})$
$\displaystyle={\mathbf{c}}^{\top}\bar{{\mathbf{x}}}^{N}+\sum_{i=1}^{m}\lambda_{i}f_{i}(\bar{{\mathbf{x}}}^{N})+{\mathbf{w}}^{\top}({\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}})$
$\displaystyle={\mathbf{c}}^{\top}\bar{{\mathbf{x}}}^{N}+\sum_{i=1}^{m}(\lambda_{i}^{*}+r_{i})f_{i}(\bar{{\mathbf{x}}}^{N})+{\mathbf{w}}^{*}\left({\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}\right)+\kappa_{2}\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|$
$\displaystyle={\mathbf{c}}^{\top}\bar{{\mathbf{x}}}^{N}+\sum_{i=1}^{m}\lambda^{*}_{i}f_{i}(\bar{{\mathbf{x}}}^{N})+\kappa_{1}\sum_{i=1}^{m}[f_{i}(\bar{{\mathbf{x}}}^{N})]_{+}+{\mathbf{w}}^{*}\left({\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}\right)+\kappa_{2}\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|$
$\displaystyle=L(\bar{{\mathbf{x}}}^{N};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})+\kappa_{1}\sum_{i=1}^{m}[f_{i}(\bar{{\mathbf{x}}}^{N})]_{+}+\kappa_{2}\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|$
(16)

Since $\mathcal{A}$ is an $\psi$-EB algorithm then

$L(\bar{{\mathbf{x}}}^{N};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})+\beta\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)\geq{\mathbf{c}}^{\top}{\mathbf{x}}^{*}=L({\mathbf{x}}^{*};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}),$
(17)

and for all $\kappa_{3}>0$

$\displaystyle
L(\bar{{\mathbf{x}}}^{N};{\boldsymbol{\lambda}},{\mathbf{w}})-L({\mathbf{x}}^{*};{{\boldsymbol{\lambda}}}^{*},{\mathbf{w}}^{*})+\kappa_{3}\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)\leq$
$\displaystyle\psi(N)\left(\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{\lambda_{i},\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{\left\|{{\mathbf{w}}}\right\|,\left\|{{\mathbf{w}}^{0}}\right\|\\}^{2}}{\theta_{{\mathbf{w}}}}+\phi(1+\kappa_{3}^{2})\right).$
(18)

Since Assumptions 1 and 2 hold, it follows from Proposition 2 that
$\lambda_{i}^{*}\leq\bar{\lambda}$ and thus

$\max\\{\lambda_{i},\lambda_{i}^{0}\\}=\max\\{\lambda_{i}^{*}+r_{i},\lambda_{i}^{0}\\}\leq\max\\{\bar{\lambda}+\kappa_{1},\lambda_{i}^{0}\\}.$

Similarly, since $\left\|{{\mathbf{w}}^{*}}\right\|\leq R_{\mathbf{w}}$, thus,

$\displaystyle\max\\{\left\|{{\mathbf{w}}}\right\|,\left\|{{\mathbf{w}}^{0}}\right\|\\}$
$\displaystyle=\max\left\\{\left\|{\mathbf{w}}^{*}+\kappa_{2}\frac{\left({\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}\right)}{\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|}\right\|,\left\|{{\mathbf{w}}^{0}}\right\|\right\\}$
$\displaystyle\leq\max\\{\left\|{{\mathbf{w}}^{*}}\right\|+\kappa_{2},\left\|{{\mathbf{w}}^{0}}\right\|\\}$
$\displaystyle\leq\max\\{R_{\mathbf{w}}+\kappa_{2},\left\|{{\mathbf{w}}^{0}}\right\|\\}.$
(19)

Combining inequalities (16)-(19) we obtain

$\displaystyle\kappa_{1}\sum_{i=1}^{m}[f_{i}(\bar{{\mathbf{x}}}^{N})]_{+}+\kappa_{2}\|{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}\|+(\kappa_{3}-\beta)\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)$
$\displaystyle\leq$
$\displaystyle\psi(N)\left(\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{\bar{\lambda}+\kappa_{1},\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{R_{\mathbf{w}}+\kappa_{2},\left\|{{\mathbf{w}}^{0}}\right\|\\}^{2}}{\theta_{{\mathbf{w}}}}+\phi(1+\kappa_{3}^{2})\right).$
(20)

Setting $\kappa_{1}=\kappa_{2}=1$ and $\kappa_{3}=\beta+1$ we obtain the first
result. For the second result, we need to upper and lower bound
${\mathbf{c}}^{\top}(\bar{{\mathbf{x}}}^{N}-{\mathbf{x}}^{*})$. First, we have

${\mathbf{c}}^{\top}(\bar{{\mathbf{x}}}^{N}-{\mathbf{x}}^{*})=L(\bar{{\mathbf{x}}}^{N};{\mathbf{0}},{\mathbf{0}})-L({\mathbf{x}}^{*};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}).$
(21)

where the equalities follow from
$L({\mathbf{x}}^{*};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})={\mathbf{c}}^{\top}{\mathbf{x}}^{*}$
and
$L(\bar{{\mathbf{x}}}^{N};{\mathbf{0}},{\mathbf{0}})={\mathbf{c}}^{\top}\bar{{\mathbf{x}}}^{N}$.
Using (18) with $\kappa_{3}=0$ we obtain

$L(\bar{{\mathbf{x}}}^{N};{\mathbf{0}},{\mathbf{0}})-L({\mathbf{x}}^{*};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})\leq\psi(N)\left(\tau^{-1}\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}+\sum_{i=1}^{m}\theta_{i}^{-1}(\lambda_{i}^{0})^{2}+\theta_{{\mathbf{w}}}^{-1}\left\|{{\mathbf{w}}^{0}}\right\|^{2}+\phi\right).$
(22)

Combining (21) with (22) we have that

${\mathbf{c}}^{\top}(\bar{{\mathbf{x}}}^{N}-{\mathbf{x}}^{*})\leq\psi(N)\left(\tau^{-1}\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}+\sum_{i=1}^{m}\theta_{i}^{-1}(\lambda_{i}^{0})^{2}+\theta_{{\mathbf{w}}}^{-1}\left\|{{\mathbf{w}}^{0}}\right\|^{2}+\phi\right).$
(23)

To obtain the other side of the bound, we use (17) to obtain

$\displaystyle{\mathbf{c}}^{\top}({\mathbf{x}}^{*}-\bar{{\mathbf{x}}}^{N})-\sum_{i=1}^{m}\lambda^{*}_{i}f_{i}(\bar{{\mathbf{x}}}^{N})-({\mathbf{w}}^{*})^{\top}({\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}})=L({\mathbf{x}}^{*};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})-L(\bar{{\mathbf{x}}}^{N};{\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})\leq\beta\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X),$

which in turn implies

$\displaystyle{\mathbf{c}}^{\top}({\mathbf{x}}^{*}-\bar{{\mathbf{x}}}^{N})$
$\displaystyle\leq\sum_{i=1}^{m}\lambda^{*}_{i}f_{i}(\bar{{\mathbf{x}}}^{N})+({\mathbf{w}}^{*})^{\top}({\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}})+\beta\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)$
$\displaystyle\leq\bar{\lambda}\sum_{i=1}^{m}[f_{i}(\bar{{\mathbf{x}}}^{N})]_{+}+R_{\mathbf{w}}\left\|{{\mathbf{A}}\bar{{\mathbf{x}}}^{N}-{\mathbf{b}}}\right\|+\beta\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X),$
(24)

where the last inequality follows from the the fact that
$0\leq\lambda^{*}_{i}\leq\bar{\lambda}$ and
$\left\|{{\mathbf{w}}^{*}}\right\|\leq R_{\mathbf{w}}$. Using (20) with
$\kappa_{1}=\bar{\lambda}$, $\kappa_{2}=R_{\mathbf{w}}$, and
$\kappa_{3}=2\beta$ to bound (24) we obtain that

$\displaystyle{\mathbf{c}}^{\top}({\mathbf{x}}^{*}-\bar{{\mathbf{x}}}^{N})\leq\psi(N)\left(\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+\sum_{i=1}^{m}\frac{\max\\{2\bar{\lambda},\lambda_{i}^{0}\\}^{2}}{\theta_{i}}+\frac{\max\\{2R_{\mathbf{w}},\left\|{{\mathbf{w}}^{0}}\right\|\\}^{2}}{\theta_{{\mathbf{w}}}}+\phi(1+(2\beta)^{2})\right)$
(25)

Combining (23) and (25) we obtain the desired result. ∎

###  4.2 Generalized model

So far, we kept the problem formulations simple and stated the convergence
results without proofs. In this section, we shall show the convergence of both
the SGSP and PAPC algorithms for a more general model using the EB-algorithm
definition.

The general model is needed to tackle the fact that projections onto sets $X$
or $Z^{i}$ are the main tools used in both algorithms, and therefore these
projections should be simple. Two issues that might arise is that either the
primal domain $X$ or at least one of the sets $Z^{i}$ is not ‘simple’, but
instead, it is an intersection of several simple sets.

###### Example 1

One of the popular uncertainty sets in RO is the so-called budgeted
uncertainty set, formulated as:

$Z=\\{{\mathbf{z}}:\ -1\leq{\mathbf{z}}\leq 1,\
\|{\mathbf{z}}\|_{1}\leq\Gamma\\}$

which is an intersection of two simple sets: the $\ell_{\infty}$ norm and
$\ell_{1}$ norm balls.

Our strategy for dealing with these complex sets shall be to disentangle the
projections onto the intersected sets. We will achieve this by including
‘copies’ of the respective primal or dual variables, together with the
relevant equality constraints, which are to be relaxed in the Lagrangian. The
saddle-point algorithm would then be applied to the new Lagrangian problem.

Consider, for example, the case where $X=\cap_{j=1}^{q}X_{i}$ is an
intersection of several ‘simple’ sets. Formulation 2 is ready to handle this
situation easily. One can ‘expand’ the vector ${\mathbf{x}}$ by having $q$
copies of it: ${\mathbf{x}}\mapsto[{\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{q}]$.
In the next step, each inequality constraint in the problem is made dependent
only on one of the ${\mathbf{x}}_{i}$’s and at the same time, equality
constraints ${\mathbf{x}}_{1}={\mathbf{x}}_{i}$, $i=2,\ldots,q$ become
embedded in the ${\mathbf{A}}{\mathbf{x}}={\mathbf{b}}$ system (where the rank
condition is easily verified).

Similarly, we can consider the case where
${Z}^{i}=\cap_{l=1,\ldots,s_{i}}Z^{i,l},\quad i=1,\ldots,m$ with $Z^{i,l}$
being compact convex sets. In this case, the constraint
${\mathbf{z}}_{i}\in\cap_{l=1,\ldots,s_{i}}Z^{i,l}$ can be written using
concatenated uncertain parameter vector
$\hat{{\mathbf{z}}}_{i}=({\mathbf{z}}_{i,1},\ldots,{\mathbf{z}}_{i,s_{i}})$,
defining

$\hat{Z}^{i}=\left\\{({\mathbf{z}}_{i,1},\ldots,{\mathbf{z}}_{i,s_{i}})\in
Z^{i,1}\times\ldots\times
Z^{i,s_{i}}:\;{\mathbf{z}}_{i,l}={\mathbf{z}}_{i,s_{i}},\;l=1,\ldots,s_{i}-1\right\\},$

and formulating the constraints as

$\max\limits_{\hat{{\mathbf{z}}}_{i}\in\hat{Z}^{i}}\hat{g}_{i}({\mathbf{x}}_{1},\hat{{\mathbf{z}}}_{i})\equiv{g}_{i}({\mathbf{x}}_{1},{\mathbf{z}}_{i,s_{i}})\leq
0$

where $Z^{i,l}$, $l=1,\ldots,s_{i}$ are ‘simple’ sets on which it is easy to
project. Thus, the general model we are going to address is the following:

$\displaystyle\min\limits_{{\mathbf{x}}\in X}\ $
$\displaystyle{\mathbf{c}}^{\top}{\mathbf{x}}$ (26) s.t. $\displaystyle
f_{i}({\mathbf{x}})\coloneqq\max\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\leq 0\quad i\in[m]$
$\displaystyle{\mathbf{A}}{\mathbf{x}}={\mathbf{b}}$

where $Z^{i}=\cap_{l=1}^{s_{i}}Z^{i,l}$. For both SGSP and PAPC we shall give
the problem generalizations together with the expanded Lagrangian that is to
be solved in Sections 4.3 and 4.4.

###  4.3 SGSP convergence

Consider problem (26) where we need to formulate a saddle point problem that
disentangles different components of the ${\mathbf{x}}$ and
${\mathbf{z}}_{i}$. We start by considering a saddle point
$({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$ of
$\bar{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}}))$ over the sets
${\mathbf{x}}\in X$ and ${\mathbf{u}}_{i}\in U^{i}$, which we already proved
exists. Thus, by the definition of the saddle point, we have that

$\displaystyle\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}^{*}_{i})=\sup_{{\mathbf{u}}_{i}\in
U^{i}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i})=\sup_{\begin{subarray}{c}{\mathbf{u}}_{i,l}\in
U^{i,l},\\\
u_{i,s_{i}}=u_{i,l},l\in[s_{i}-1]\end{subarray}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i,s_{i}})$

where the last equality follows from the definition of
$U^{i}=\cap_{i\in[s_{i}]}U^{i,l}$ where
$U^{i,l}=\\{(\tilde{{\mathbf{z}}},\lambda_{i}):\tilde{{\mathbf{z}}}\in\lambda_{i}Z^{i,l}\\}$,
similarly to what was explained in the previous section. Note that the
leftmost supremum has a solution
(${\mathbf{u}}_{i,1}={\mathbf{u}}_{i,2}=\ldots={\mathbf{u}}_{i,s_{i}}={\mathbf{u}}_{i}^{*}$).
Moreover, since $U^{i}\subseteq U^{i,l}$ for $l\in[s_{i}]$, the sets $U^{i,l}$
have a nonempty interior, therefore, dualizing the equality constraints, we
have that strong duality holds. Thus, denoting
$\tilde{{\mathbf{u}}}^{*}_{i}=({{\mathbf{u}}}^{*}_{i,1},\ldots,{{\mathbf{u}}}^{*}_{i,s_{i}})\equiv({\mathbf{u}}^{*}_{i},\ldots,{\mathbf{u}}^{*}_{i})$
there exists
${\boldsymbol{\omega}}^{*}_{i}=({\boldsymbol{\omega}}^{*}_{i,1},\ldots,{\boldsymbol{\omega}}^{*}_{i,s_{i}-1})$
such that $({\boldsymbol{\omega}}_{i}^{*},\tilde{{\mathbf{u}}}_{i}^{*})$
satisfies

$\displaystyle\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}^{*}_{i})$
$\displaystyle=\sup_{\begin{subarray}{c}{\mathbf{u}}_{i,l}\in U^{i,l},\\\
u_{i,s_{i}}=u_{i,l},l\in[s_{i}-1]\end{subarray}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i,s_{i}})$
$\displaystyle=\inf_{\omega_{i,l}\in{}^{d_{i}+1},l\in[s_{i}-1]}\sup_{\begin{subarray}{c}{\mathbf{u}}_{i,l}\in
U^{i,l},l\in[s_{i}-1]\end{subarray}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i,s_{i}})+\sum\limits_{l=1}^{s_{i}-1}{\boldsymbol{\omega}}_{i,l}^{\top}({\mathbf{u}}_{i,l}-{\mathbf{u}}_{i,s_{i}})$
$\displaystyle=\inf_{{\boldsymbol{\omega}}_{i,l},\
l\in[s_{i}-1]}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}^{*}_{i,s_{i}})+\sum\limits_{l=1}^{s_{i}-1}{\boldsymbol{\omega}}_{i,l}^{\top}({\mathbf{u}}^{*}_{i,l}-{\mathbf{u}}^{*}_{i,s_{i}})$
$\displaystyle=\sup_{\begin{subarray}{c}{\mathbf{u}}_{i,l}\in U^{i,l},\
l\in[s_{i}-1]\end{subarray}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i,s_{i}})+\sum\limits_{l=1}^{s_{i}-1}({\boldsymbol{\omega}}^{*}_{i,l})^{\top}({\mathbf{u}}_{i,l}-{\mathbf{u}}_{i,s_{i}}).$
(27)

Due to Proposition 2 we know that we can restrict $U^{i}$ to $\tilde{U}^{i}$,
and thus, the existence of the saddle point in this case follows the same
logic where $U^{i,l}$ is replaced by
$\tilde{U}^{i,l}=\\{{\mathbf{u}}_{i,l}\equiv(\tilde{{\mathbf{z}}}_{i,l},\lambda_{i,l})\in
U^{i,l}:\lambda_{i,l}\leq\bar{\lambda}\\}$. In the following, we will show
that we can restrict the domain over which we optimize ${\boldsymbol{\omega}}$
and still retrieve a saddle point of the original problem.

Denoting ${\boldsymbol{\chi}}=({\mathbf{x}},{\boldsymbol{\omega}})$ and
${\mathbf{y}}=(\tilde{{\mathbf{u}}},{\mathbf{w}})$ where
${\boldsymbol{\omega}}=({\boldsymbol{\omega}}_{1},\ldots,{\boldsymbol{\omega}}_{m})$,
$\tilde{{\mathbf{u}}}=(\tilde{{\mathbf{u}}}_{1},\ldots,\tilde{{\mathbf{u}}}_{m})$,
and
${\boldsymbol{\omega}}_{i}=({\boldsymbol{\omega}}_{i1},\ldots,{\boldsymbol{\omega}}_{i(s_{i}-1)})$,
$\tilde{{\mathbf{u}}}_{i}=({\mathbf{u}}_{i1},\ldots,{\mathbf{u}}_{is_{i}})$
for all $i\in[m]$, we can define a saddle point in the lifted space. Indeed,
let $({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ be a
saddle point of $L({\mathbf{x}},({\boldsymbol{\lambda}},{\mathbf{w}}))$, then,
by Proposition 1, and the reasoning leading to (27) above, there exists
$\tilde{{\mathbf{u}}}^{*}$ and ${\boldsymbol{\omega}}^{*}$ such that

$\displaystyle\sup\limits_{{\boldsymbol{\lambda}}\geq
0,{\mathbf{w}}}L({\mathbf{x}}^{*},({\boldsymbol{\lambda}},{\mathbf{w}}))$
$\displaystyle=\sup\limits_{\begin{subarray}{c}{\mathbf{w}}\in W,\\\
{\mathbf{u}}_{i}\in
U^{i},\;i\in[m]\end{subarray}}{\mathbf{c}}^{\top}{\mathbf{x}}^{*}+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}\left({\mathbf{x}}^{*},{\mathbf{u}}_{i}\right)$
$\displaystyle=\sup\limits_{\begin{subarray}{c}{\mathbf{w}}\in W,\\\
{\mathbf{u}}_{i,l}\in
U^{i,l},\;i\in[m],l\in[s_{i}-1]\end{subarray}}{\mathbf{c}}^{\top}{\mathbf{x}}^{*}+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}\left({\mathbf{x}},{\mathbf{u}}_{i,s_{i}}\right)+\sum\limits_{i=1}^{m}\sum\limits_{l=1}^{s_{i}-1}({\boldsymbol{\omega}}^{*}_{i,l})^{\top}({\mathbf{u}}_{i,l}-{\mathbf{u}}_{i,s_{i}})$

and

$\displaystyle\inf_{{\mathbf{x}}\in
X}L({\mathbf{x}},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$
$\displaystyle=\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+({\mathbf{w}}^{*})^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}\left({\mathbf{x}},{\mathbf{u}}^{*}_{i}\right)$
$\displaystyle=\inf_{\begin{subarray}{c}{\mathbf{x}}\in X\\\
{\boldsymbol{\omega}}_{i,l},\;i\in[m],l\in[s_{i}-1]\end{subarray}}{\mathbf{c}}^{\top}{\mathbf{x}}^{*}+({\mathbf{w}}^{*})^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}\left({\mathbf{x}},{\mathbf{u}}_{i,s_{i}}\right)+\sum\limits_{i=1}^{m}\sum\limits_{l=1}^{s_{i}-1}({\boldsymbol{\omega}}_{i,l})^{\top}({\mathbf{u}}^{*}_{i,l}-{\mathbf{u}}^{*}_{i,s_{i}}).$

Defining

$\displaystyle\breve{L}({\boldsymbol{\chi}},{\mathbf{y}}):={\mathbf{c}}^{\top}{\mathbf{x}}+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}\left({\mathbf{x}},{\mathbf{u}}_{i,s_{i}}\right)+\sum\limits_{i=1}^{m}\sum\limits_{l=1}^{s_{i}-1}{\boldsymbol{\omega}}_{i,l}^{\top}({\mathbf{u}}_{i,l}-{\mathbf{u}}_{i,s_{i}}).$
(28)

we obtain that $({\boldsymbol{\chi}}^{*},{\mathbf{y}}^{*})$ is a saddle point
of $\breve{L}$. Following similar logic, we can also obtain that given a
saddle point $({\boldsymbol{\chi}}^{*},{\mathbf{y}}^{*})$ of $\breve{L}$ with
${\mathbf{u}}_{i,s_{i}}^{*}=(\tilde{{\mathbf{z}}}^{*}_{i,s_{i}},\lambda_{i,s_{i}}^{*})$
we can obtain a saddle point
$({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ of $L$ by
defining $\lambda_{i}^{*}=\lambda_{i,s_{i}}^{*}$,
${\boldsymbol{\lambda}}^{*}=(\lambda_{1}^{*},\ldots,\lambda_{m}^{*})$.

Since we proved that $\breve{L}$ has a saddle point, we can now show that SGSP
algorithm applied to (28) meets the EB-algorithm assumptions. However, in
order to run the algorithm and prove its convergence, we need to show that the
feasible sets of the variables can be restricted without losing a saddle
point. Legitimacy of bounding ${\mathbf{u}}_{i,l}$ and ${\mathbf{w}}$ follows
from Proposition 2 and (27). The following proposition establishes our ability
to bound ${\boldsymbol{\omega}}_{i,l}$.

###### Proposition 4

Let Assumptions 1–5 hold. Let $i\in[m]$ and consider the saddle point problem

$\displaystyle\min_{{\boldsymbol{\omega}}_{i}}\max_{\begin{subarray}{c}{\mathbf{u}}_{i,l}\in\tilde{U}^{i,l},\
l\in[s_{i}],\\\
\underaccent{\tilde}{\lambda}\leq\lambda_{i,s_{i}}\leq\tilde{\lambda}\end{subarray}}\tilde{g}_{i}({\mathbf{x}}^{*},{\mathbf{u}}_{i,s_{i}})+\sum\limits_{l=1}^{s_{i}-1}{\boldsymbol{\omega}}_{i,l}^{\top}({\mathbf{u}}_{i,l}-{\mathbf{u}}_{i,s_{i}})$
(29)

where ${\mathbf{x}}^{*}$ is an optimal solution of (26), and
$0\leq\underaccent{\tilde}{\lambda}\leq\tilde{\lambda}\leq\bar{\lambda}$.
Then, there exists a saddle point
$({\boldsymbol{\omega}}_{i}^{*},\tilde{{\mathbf{u}}}_{i}^{*})$ with
${\boldsymbol{\omega}}^{*}_{i,l}=({\boldsymbol{\nu}}^{*}_{i,l},\mu^{*}_{i,l})$
such that ${\boldsymbol{\omega}}_{i,l}^{*}$ is contained in the set

$\displaystyle\Omega^{i,l}=\left\\{{\boldsymbol{\omega}}_{i,l}=({\boldsymbol{\nu}}_{i,l},\mu_{i,l}):-\bar{\mu}_{i}\leq\mu_{i,l}\leq
0,\;\left\|{{\boldsymbol{\nu}}_{i,l}}\right\|\leq\frac{-{\mu}_{i,l}}{\epsilon_{i}},\;i\in[m],\;l\in[s_{i}-1]\right\\},$

where $\epsilon_{i}$ and $\bar{\mu}_{i}$ is given by Assumptions 4 and 5,
respectively.

Now that we have shown that we can bound all variables in the saddle point of
function $\breve{L}({\boldsymbol{\chi}},{\mathbf{y}})$ over the sets
$\mathcal{X}=X\times(\times_{i=1}^{m}\times_{l=1}^{s_{i}-1}\Omega^{i,l})$ and
$\mathcal{Y}=(\times_{i=1}^{m}\times_{l=1}^{s_{i}}U^{i,l})\times W$, we can
apply SGSP to the problem with these bounded sets as follows.

SGSP for $\breve{L}$
Input: ${\tau>0},{\theta_{i}>0},\theta_{{\mathbf{w}}}>0$ for $i\in[m]$, and
$N\in\mathbb{N}$
Initialization. Initialize ${\boldsymbol{\chi}}^{0}\in\mathcal{X}$, and
${\mathbf{y}}^{0}\in\mathcal{Y}$ such that
$\lambda^{0}_{i,l}=\lambda^{0}_{i,1}$ for all $l\in[s_{i}]$,$i\in[m]$, and
define the diagonal matrix
$\Theta=\operatorname*{Diag}(\theta_{1}{\mathbf{e}};\ldots;\theta_{m}{\mathbf{e}};\theta_{\mathbf{w}}{\mathbf{e}})$.
General step: For $k\in[N]$
Compute subgradients
${\mathbf{v}}^{k-1}_{\chi}=({\mathbf{v}}^{k-1}_{x},{\mathbf{v}}^{k-1}_{\omega})\in\partial_{\boldsymbol{\chi}}\breve{L}({\boldsymbol{\chi}}^{k-1},{\mathbf{y}}^{k-1})$,
and for all $i\in[m]$
${\mathbf{v}}^{k-1}_{\tilde{{\mathbf{u}}}_{i}}=({\mathbf{v}}^{k-1}_{i,1},\ldots,{\mathbf{v}}^{k-1}_{i,s_{i}})\in\partial_{\tilde{{\mathbf{u}}}_{i}}\left(-\breve{L}({\boldsymbol{\chi}}^{k-1},{\mathbf{y}}^{k-1})\right)$.
$\displaystyle{\boldsymbol{\chi}}^{k}$
$\displaystyle=P_{\mathcal{X}}({\boldsymbol{\chi}}^{k-1}-\tau{\mathbf{v}}_{\chi}^{k-1})$
$\displaystyle\Longleftrightarrow\quad$
$\displaystyle{\mathbf{x}}^{k}=P_{X}({\mathbf{x}}^{k-1}-\tau{\mathbf{v}}_{x}^{k-1}),$
$\displaystyle{\boldsymbol{\omega}}_{i,l}^{k}=P_{\Omega^{i,l}}({\boldsymbol{\omega}}_{i,l}^{k-1}-\tau({\mathbf{u}}_{i,l}^{k-1}-{\mathbf{u}}_{i,s_{i}}^{k-1})),$
$\displaystyle i\in[m],\;l\in[s_{i}-1]$ $\displaystyle{\mathbf{y}}^{k}$
$\displaystyle=P_{\mathcal{Y}}({\mathbf{y}}^{k-1}-\Theta{\mathbf{v}}_{y}^{k-1})$
$\displaystyle\Longleftrightarrow\quad$
$\displaystyle{\mathbf{u}}^{k}_{i,l}=P_{\tilde{U}^{i,l}}({\mathbf{u}}_{i,l}^{k-1}+\theta_{i}{\boldsymbol{\omega}}^{k-1}_{i,l}),$
$\displaystyle i\in[m],\;l\in[s_{i}-1]$
$\displaystyle{\mathbf{u}}^{k}_{i,s_{i}}=P_{\tilde{U}^{i,s_{i}}}({\mathbf{u}}_{i,s_{i}}^{k-1}-\theta_{i}{\mathbf{v}}_{i,s_{i}}^{k-1}),$
$\displaystyle i\in[m]$
$\displaystyle{\mathbf{w}}^{k}=P_{W}({\mathbf{w}}^{k-1}+\theta_{\mathbf{w}}({\mathbf{A}}{\mathbf{x}}^{k-1}-{\mathbf{b}})).$

We will now prove that SGSP is an EB-algorithm and thus, it converges to the
optimal solution.

###### Proposition 5

Let Assumptions 1–5 hold. And let
$\\{(\chi^{k},{\mathbf{y}}^{k})\\}_{k\in\mathbb{N}}$ be the sequence generated
by SGSP algorithm with parameters $\tau=\frac{\tilde{\tau}}{\sqrt{N}}$,
$\theta_{i}=\frac{\tilde{\theta}_{i}}{\sqrt{N}}$,
$\theta_{{\mathbf{w}}}=\frac{\tilde{\theta}_{w}}{\sqrt{N}}$, where
${\boldsymbol{\chi}}^{k}=({\mathbf{x}}^{k},{\boldsymbol{\omega}}^{k})$ and
${\mathbf{y}}^{k}=(\tilde{{\mathbf{u}}}^{k},{\mathbf{w}}^{k})$. Then,

$\displaystyle\breve{L}(\bar{{\boldsymbol{\chi}}}^{N},{\mathbf{y}})-\breve{L}({\boldsymbol{\chi}},\bar{{\mathbf{y}}}^{N})$
$\displaystyle\quad\leq\frac{1}{2\sqrt{N}}\left(\frac{\left\|{{\boldsymbol{\chi}}^{0}-{\boldsymbol{\chi}}}\right\|^{2}}{\tilde{\tau}}+\tilde{\tau}G_{\boldsymbol{\chi}}^{2}+\sum\limits_{i=1}^{m}\left(\frac{\left\|{\tilde{{\mathbf{u}}}_{i}^{0}-\tilde{{\mathbf{u}}}_{i}}\right\|^{2}}{\tilde{\theta}_{i}}+\tilde{\theta}_{i}G_{\tilde{{\mathbf{u}}}_{i}}^{2}\right)+\frac{\left\|{{\mathbf{w}}^{0}-{\mathbf{w}}}\right\|^{2}}{\tilde{\theta}_{\mathbf{w}}}+\tilde{\theta}_{\mathbf{w}}G_{\mathbf{w}}^{2}\right)$
(30)

where

$\displaystyle G_{\boldsymbol{\chi}}$
$\displaystyle\coloneqq\left\|{{\mathbf{c}}}\right\|+\|{\mathbf{A}}\|R_{\mathbf{w}}+\sum_{i\in[m]}\bar{\lambda}G_{x,i}+\bar{\lambda}\sum_{i\in[m]}\left((s_{i}-1)(2+R_{i,s_{i}})+\sum_{l\in[s_{i}-1]}R_{i,l}\right)$
$\displaystyle G_{\tilde{{\mathbf{u}}}_{i}}$
$\displaystyle\coloneqq(\bar{\lambda}+R_{i,s_{i}})G_{z,i}+\bar{g}_{i}+2\bar{\mu}_{i}(s_{i}-1)\left(1+\frac{1}{\epsilon_{i}}\right)$
$\displaystyle G_{\mathbf{w}}$
$\displaystyle\coloneqq\left\|{{\mathbf{A}}}\right\|R_{\mathbf{x}}+\left\|{{\mathbf{b}}}\right\|$

Moreover, SGSP is an EB-algorithm. More precisely, let ${\mathbf{x}}^{*}$ an
optimal solution of (26), $({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})$ be
the optimal dual variables associated with its constraints, and let
${\boldsymbol{\lambda}}\in{}^{m}_{+}$, and ${\mathbf{w}}\in{}^{r}$ such that
$\lambda_{i}\equiv\lambda_{i,s_{i}}$ for all $i\in[m]$. Then,

$\displaystyle
L(\bar{{\mathbf{x}}}^{N},({\boldsymbol{\lambda}},{\mathbf{w}}))-L({\mathbf{x}}^{*},({{\boldsymbol{\lambda}}}^{*},{{\mathbf{w}}}^{*}))\leq$
$\displaystyle\qquad\frac{1}{2\sqrt{N}}\left(\tilde{\tau}^{-1}\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}+\sum_{i=1}^{m}\sigma_{i}\tilde{\theta}_{i}^{-1}\max\\{\lambda_{i},\lambda_{i}^{0}\\}^{2}+2\tilde{\theta}_{\mathbf{w}}^{-1}\max\\{\|{\mathbf{w}}\|,\|{\mathbf{w}}_{0}\|\\}^{2}+\phi\right),$
(31)

and

$L(\bar{{\mathbf{x}}}^{N};({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))\geq{\mathbf{c}}^{\top}{\mathbf{x}}^{*},$
(32)

where

$\displaystyle\sigma_{i}$ $\displaystyle=\sum_{l=1}^{s_{i}}(1+4R_{i,l}^{2})$
$\displaystyle\phi$
$\displaystyle=\tilde{\tau}G_{\boldsymbol{\chi}}^{2}+\sum_{i=1}^{m}\tilde{\theta}_{i}G_{{\mathbf{u}}_{i}}^{2}+4\frac{\left(\sum_{i=1}^{m}\bar{\mu}_{i}(s_{i}-1)\left(1+\frac{1}{\epsilon_{i}}\right)\right)^{2}}{\tilde{\tau}}+\tilde{\theta}_{\mathbf{w}}G_{\mathbf{w}}^{2}$

where $R_{\mathbf{x}}$ is the radius of $X$, $R_{\mathbf{w}}$ the radius of
$W$, $R_{i,l}$ is the radius of $Z^{i,l}$, $\bar{g}_{i}=\max_{{\mathbf{x}}\in
X,{\mathbf{z}}_{i}\in Z^{i}}|g_{i}({\mathbf{x}},{\mathbf{z}}_{i})|$,
$\bar{\lambda}$, $\bar{\mu}_{i}$ and $\epsilon_{i}$ are defined in Proposition
2, Assumption 5 and Assumption 4, respectively, and $G_{x,i},G_{z,i}$ are the
bounds on the subgradients ${\mathbf{d}}^{k}_{x,i}$, ${\mathbf{d}}^{k}_{z,i}$
generated as in Lemma 2.

###  4.4 PAPC convergence

In the case of PAPC, we proceed similarly to SGSP with one change – here, we
need to eliminate the explicit constraint that ${\mathbf{x}}$ lies in $X$,
which is also not assumed to be bounded. We achieve this, as in the simple
case, by performing the dual transportation trick. Compared to (28), we do an
extra step to obtain:

$\displaystyle\sup\limits_{{\boldsymbol{\lambda}}\geq
0,{\mathbf{w}}}\inf\limits_{{\mathbf{x}}\in
X}L({\mathbf{x}},({\boldsymbol{\lambda}},{\mathbf{w}}))$
$\displaystyle=\inf\limits_{{\boldsymbol{\omega}}_{i,l},{\mathbf{x}}}\sup\limits_{{\boldsymbol{\pi}},{\mathbf{w}},{\mathbf{u}}_{i,l}\in
U^{i,l}}{\mathbf{c}}^{\top}{\mathbf{x}}+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})+\sum\limits_{i=1}^{m}\tilde{g}_{i}\left({\mathbf{x}},{\mathbf{u}}_{i,s_{i}}\right)+\sum\limits_{i=1}^{m}\sum\limits_{l=1}^{s_{i}-1}{\boldsymbol{\omega}}_{i,l}^{\top}({\mathbf{u}}_{i,l}-{\mathbf{u}}_{i,s_{i}})+{\boldsymbol{\pi}}^{\top}{\mathbf{x}}-\sigma_{X}({\boldsymbol{\pi}})$
$\displaystyle=\inf_{{\boldsymbol{\chi}}}\sup\limits_{{\mathbf{y}}=(\tilde{{\mathbf{u}}},{\mathbf{w}},{\boldsymbol{\pi}}):{{\mathbf{u}}}_{i,l}\in
U^{i,l},l\in[s_{i}],\;i\in[m]}\check{L}({\boldsymbol{\chi}},{\mathbf{y}})$

where $\sigma_{X}({\boldsymbol{\pi}})$ is the support function of $X$ and
${\boldsymbol{\chi}}=({\mathbf{x}},{\boldsymbol{\omega}})$,
${\mathbf{y}}=(\tilde{{\mathbf{u}}},{\mathbf{w}},{\boldsymbol{\pi}})$, and
recall that where
${\boldsymbol{\omega}}_{i}=({\boldsymbol{\omega}}_{i,1},\ldots,{\boldsymbol{\omega}}_{i,s_{i}-1})$,
${\boldsymbol{\omega}}=({\boldsymbol{\omega}}_{1},\ldots,{\boldsymbol{\omega}}_{m})$,
$\tilde{{\mathbf{u}}}_{i}=({\mathbf{u}}_{i,1},\ldots,{\mathbf{u}}_{i,s_{i}})$,
and
$\tilde{{\mathbf{u}}}=(\tilde{{\mathbf{u}}}_{1},\ldots,\tilde{{\mathbf{u}}}_{m})$.

As the PAPC algorithm presumes bilinearity, we assume $f_{i}$ are of the form
given in (8), we obtain:

$\displaystyle\check{L}({\boldsymbol{\chi}},{\mathbf{y}})$
$\displaystyle\equiv{\mathbf{x}}^{\top}\left({\mathbf{c}}+\sum_{i\in[m]}\tilde{{\mathbf{Q}}}_{i}{\mathbf{u}}_{i,s_{i}}+{\mathbf{A}}^{\top}{\mathbf{w}}+{\boldsymbol{\pi}}\right)+$
$\displaystyle\quad\sum_{i\in[m]}\left(\tilde{{\mathbf{q}}}_{i}^{\top}{\mathbf{u}}_{i,s_{i}}+\sum_{l\in[s_{i}-1]}{\boldsymbol{\omega}}_{i,l}^{\top}({\mathbf{u}}_{i,l}-{{\mathbf{u}}}_{i,s_{i}})-\sum_{l\in[s_{i}]}\delta_{\tilde{U}^{i,l}}({\mathbf{u}}_{i,l})\right)-{\mathbf{b}}^{\top}{\mathbf{w}}-\sigma_{X}({\boldsymbol{\pi}})$
(33)
$\displaystyle={\mathbf{c}}^{\top}{\mathbf{x}}+{\boldsymbol{\chi}}^{\top}\bar{{\mathbf{Q}}}{\mathbf{y}}+\sum_{i\in[m]}\left(\tilde{{\mathbf{q}}}_{i}^{\top}{\mathbf{u}}_{i,s_{i}}-{\mathbf{b}}^{\top}{\mathbf{w}}-\sum_{l\in[s_{i}]}\delta_{\tilde{U}^{i,l}}({\mathbf{u}}_{i,l})-\sigma_{X}({\boldsymbol{\pi}})\right),$

where $\tilde{{\mathbf{Q}}}_{i}$ and $\tilde{{\mathbf{q}}}_{i}$ are defined in
(9), and

${\mathbf{P}}_{i}=\left[\begin{array}[]{ccccccccccccccccccccc}{\mathbf{I}}&{\mathbf{0}}&\ldots&&{\mathbf{0}}&-{\mathbf{I}}&\\\
{\mathbf{0}}&{\mathbf{I}}&{\mathbf{0}}&\ldots&{\mathbf{0}}&-{\mathbf{I}}\\\
\vdots&\ddots&\ddots&&&\\\ \vdots&&\ddots&\ddots&&\\\
{\mathbf{0}}&&\ldots&{\mathbf{0}}&{\mathbf{I}}&-{\mathbf{I}}&\end{array}\right]\in{}^{(d_{i}+1)(s_{i}-1)\times(d_{i}+1)s_{i}},\;\bar{{\mathbf{Q}}}=\left[\begin{array}[]{ccccccccccccccc}{\mathbf{0}}&\tilde{{\mathbf{Q}}}_{1}&{\mathbf{0}}&\tilde{{\mathbf{Q}}}_{2}&\ldots&{\mathbf{0}}&\tilde{{\mathbf{Q}}}_{m}&{\mathbf{A}}&{\mathbf{I}}\\\
{\mathbf{P}}_{1}&{\mathbf{0}}&&&\ldots&&{\mathbf{0}}&\ldots&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{P}}_{2}&{\mathbf{0}}&\ldots&&{\mathbf{0}}&\ldots&{\mathbf{0}}\\\
\vdots&\ddots&\ddots&\vdots&\ddots&&\vdots&&\vdots\\\
{\mathbf{0}}&&\ldots&&{\mathbf{0}}&{\mathbf{P}}_{m}&{\mathbf{0}}&\ldots&{\mathbf{0}}\\\
\end{array}\right]$

Now, we give a short argument for the boundedness of the optimal
${\boldsymbol{\pi}}^{*}$. For the case of PAPC the boundedness of variables
${\boldsymbol{\omega}}$, ${\mathbf{w}}$ and ${\mathbf{u}}$ at the saddle point
follows by the same arguments as in Propositions 2 and 4. From here, we argue
that at the saddle point ${\boldsymbol{\pi}}$ can be bounded as well.

###### Proposition 6

Under Assumptions 1-3, at the saddle point
$({\boldsymbol{\chi}}^{*},{\boldsymbol{\nu}}^{*})$ of (33) it holds that

$\left\|{{\boldsymbol{\pi}}^{*}}\right\|\leq
R_{\boldsymbol{\pi}}:=\left\|{{\mathbf{c}}}\right\|+\bar{\lambda}\sum_{i=1}^{m}\left\|{\tilde{{\mathbf{Q}}}_{i}}\right\|(R_{i,s_{i}}+1)$
(34)

###### Proof

Due to optimality conditions w.r.t. ${\mathbf{x}}$ in (33) we must have

${\mathbf{c}}+\sum_{i=1}^{m}\tilde{{\mathbf{Q}}}_{i}{\mathbf{u}}_{i,s_{i}}^{*}+{\mathbf{A}}{\mathbf{w}}+{\boldsymbol{\pi}}^{*}=0.$

Thus, we have

$\left\|{{\boldsymbol{\pi}}^{*}}\right\|=\left\|{{\mathbf{c}}+\sum_{i=1}^{m}\tilde{{\mathbf{Q}}}_{i}{\mathbf{u}}_{i,s_{i}}^{*}}\right\|\leq\left\|{{\mathbf{c}}}\right\|+\left\|{{\mathbf{A}}}\right\|R_{\mathbf{w}}+\bar{\lambda}\sum_{i=1}^{m}\left\|{\tilde{{\mathbf{Q}}}_{i}}\right\|(R_{i,s_{i}}+1)$

where the last inequality follows from the definition of induced norm, and the
boundedness of ${\mathbf{u}}_{i,s_{i}}^{*}$ and ${\mathbf{w}}$, proven in
Proposition 2. ∎

Note again, that in the case of PAPC, while the bounds on
${\boldsymbol{\omega}}^{*}$, $\tilde{{\mathbf{u}}}^{*}$, ${\mathbf{w}}^{*}$,
${\boldsymbol{\pi}}^{*}$ exist, they are needed to prove convergence, but not
to apply the algorithm. Now we can apply PAPC to generalized problem as
follows.

PAPC for $\breve{L}$
Input: ${\tau>0},{\theta_{i}>0}$ for $i\in[m]$, and $N\in\mathbb{N}$
Initialization. Initialize
${\boldsymbol{\chi}}^{0}=({\mathbf{x}}^{0},{\boldsymbol{\omega}}^{0})\in{}^{n}\times{}^{\sum_{i\in[m]}(s_{i}-1)}$,
${\mathbf{y}}^{0}=(\tilde{{\mathbf{u}}}^{0},{\mathbf{w}}^{0},{\boldsymbol{\pi}}^{0})\in\times_{i\in[m]}\times_{l\in[s_{i}]}U^{i,l}\times{}^{r}\times{}^{m}$.
General step: For $k\in[N]$:
_Predictor:_ $\displaystyle{\mathbf{p}}_{{\mathbf{x}}}^{k}$
$\displaystyle={\mathbf{x}}^{k-1}-\tau\left({\mathbf{c}}+\sum_{i\in[m]}\tilde{{\mathbf{Q}}}_{i}{\mathbf{u}}^{k-1}_{i,s_{i}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{k-1}+{\boldsymbol{\pi}}^{k-1}\right),$
$\displaystyle{\mathbf{p}}_{{\boldsymbol{\omega}}_{i,l}}^{k}$
$\displaystyle={\boldsymbol{\omega}}_{i,l}^{k-1}-\tau({\mathbf{u}}_{i,l}^{k-1}-{\mathbf{u}}_{i,s_{i}}^{k-1})),\qquad
i\in[m],\;l\in[s_{i}-1].$ _Dual update:_ $\displaystyle{\mathbf{u}}^{k}_{i,l}$
$\displaystyle=P_{U^{i,l}}\left({\mathbf{u}}^{k-1}_{i,l}+\theta_{i}{\mathbf{p}}_{{\boldsymbol{\omega}}_{i,l}}^{k}\right),$
$\displaystyle i\in[m],\;l\in[s_{i}-1]$
$\displaystyle{\mathbf{u}}^{k}_{i,s_{i}}$
$\displaystyle=P_{U^{i,s_{i}}}\left({\mathbf{u}}^{k-1}_{i,s_{i}}+\theta_{i}\left(\tilde{{\mathbf{Q}}}_{i}^{\top}{\mathbf{p}}_{{\mathbf{x}}}^{k}+\tilde{{\mathbf{q}}}_{i}-\sum_{l\in[s_{i}-1]}{\mathbf{p}}_{{\boldsymbol{\omega}}_{i,l}}^{k})\right)\right),$
$\displaystyle i\in[m]$ $\displaystyle{\mathbf{w}}^{k}$
$\displaystyle={\mathbf{w}}^{k-1}+\theta_{\mathbf{w}}({\mathbf{A}}{\mathbf{p}}_{{\mathbf{x}}}^{k}-{\mathbf{b}}),$
$\displaystyle{\boldsymbol{\pi}}^{k}$
$\displaystyle=\operatorname{prox}_{\theta_{{\boldsymbol{\pi}}}\sigma_{X}}({\boldsymbol{\pi}}^{k-1}+\theta_{{\boldsymbol{\pi}}}{\mathbf{p}}_{{\mathbf{x}}}^{k}).$
_Corrector:_ $\displaystyle{\mathbf{x}}^{k}$
$\displaystyle={\mathbf{x}}^{k-1}-\tau\left({\mathbf{c}}+\sum_{i\in[m]}\tilde{{\mathbf{Q}}}_{i}{\mathbf{u}}^{k}_{i,s_{i}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{k}+{\boldsymbol{\pi}}^{k}\right),$
$\displaystyle{{\boldsymbol{\omega}}_{i,l}}^{k}$
$\displaystyle={\boldsymbol{\omega}}_{i,l}^{k-1}-\tau({\mathbf{u}}_{i,l}^{k}-{\mathbf{u}}_{i,s_{i}}^{k})),\qquad
i\in[m],\;l\in[s_{i}-1]$

We are now ready to prove the convergence of PAPC for the general formulation
via showing that it is an EB-algorithm.

###### Proposition 7

Let Assumptions 1-5 hold true. Then, applying the PAPC algorithm to
$\check{L}({\boldsymbol{\chi}},{\mathbf{y}})$ with parameters
$\tau,\theta_{\lambda_{1}},\ldots,\theta_{\lambda_{m}},\theta_{{\mathbf{w}}},\theta_{\boldsymbol{\pi}}>0$
such that
${\mathbf{H}}={\mathbf{S}}-\tau\bar{{\mathbf{Q}}}^{\top}\bar{{\mathbf{Q}}}\succeq{\mathbf{0}}$
where

${\mathbf{S}}=\text{Diag}(\theta_{1}^{-1}{\mathbf{I}}_{s_{1}(d_{1}+1)},\ldots,\theta_{m}^{-1}{\mathbf{I}}_{s_{m}(d_{m}+1)},\theta_{{\mathbf{w}}}^{-1}{\mathbf{I}}_{r},\theta_{\boldsymbol{\pi}}^{-1}{\mathbf{I}}_{n})$

result in

$\check{L}(\bar{{\boldsymbol{\chi}}}^{N},{\mathbf{y}})-\check{L}({\boldsymbol{\chi}},\bar{{\mathbf{y}}}^{N})\leq\frac{\tau^{-1}\|{\boldsymbol{\chi}}-{\boldsymbol{\chi}}^{0}\|^{2}+\|{\mathbf{y}}-{\mathbf{y}}^{0}\|^{2}_{\mathbf{H}}}{2N}.$
(35)

Furthermore, SGSP is an EB algorithm. More precisely, let ${\mathbf{x}}^{*}$
be an optimal solution of (26) and let
$({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})$ be the optimal dual variables
associated with its constraints. Then, for any $\alpha>0$ and
${\boldsymbol{\lambda}}\in{}^{m}_{+}$ and ${\mathbf{w}}$ such that
$\lambda_{i}\equiv\lambda_{i,s_{i}}$ for all $i\in[m]$.

$\displaystyle
L(\bar{{\mathbf{x}}}^{N},({\mathbf{w}},{\boldsymbol{\lambda}}))-L({{\mathbf{x}}}^{*},({\mathbf{w}}^{*},{\boldsymbol{\lambda}}^{*})+\alpha\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)$
$\displaystyle\leq\frac{1}{2N}\left(\frac{\|{\mathbf{x}}^{*}-{\mathbf{x}}^{0}\|^{2}}{\tau}+2\sum\limits_{i=1}^{m}\frac{\sigma_{i}}{\theta_{i}}\max\\{\lambda_{i},\lambda_{i}^{0}\\}^{2}+\frac{2\max\\{\left\|{{\mathbf{w}}}\right\|,\left\|{{\mathbf{w}}^{0}}\right\|\\}^{2}}{\theta_{\mathbf{w}}}+\phi(1+\alpha^{2})\right).$
(36)

and

$L(\bar{{\mathbf{x}}}^{N},{\boldsymbol{\lambda}}^{*})+\beta\operatorname*{Dist}(\bar{{\mathbf{x}}}^{N},X)\geq{\mathbf{c}}^{\top}{\mathbf{x}}^{*},$

where $\sigma_{i}=\sum_{l\in[s_{i}]}(1+4R^{2}_{i,l})$, $R_{i,l}$ is the radius
of $Z^{i,l}$,
$\phi=\max\left\\{\frac{2}{\theta_{\boldsymbol{\pi}}},4\sum_{i=1}^{m}s_{i}\bar{\mu}_{i}^{2}\left(1+\frac{1}{\epsilon_{i}}\right)^{2}+\frac{2\left\|{\pi^{0}}\right\|^{2}}{\theta_{\boldsymbol{\pi}}}\right\\}$
with $\bar{\mu}_{i}$ and $\epsilon_{i}$ are defined in Assumptions 5 and 4,
respectively, and $\beta=R_{\pi}$ with $R_{\pi}$ defined in (34).

######  Remark 1 (PAPC: the non-biaffine case)

The PAPC algorithm can be extends to the case where
$g_{i}({\mathbf{x}},{\mathbf{z}}_{i})$ is not bilinear, but rather has the
following general form:

$g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\coloneqq{\mathbf{h}}_{i}({\mathbf{x}})^{\top}{\boldsymbol{\ell}}_{i}({\mathbf{z}}_{i}),$

where ${\mathbf{h}}_{i}(\cdot):X\rightarrow{}^{k_{i}}$ and
${\boldsymbol{\ell}}_{i}(\cdot):Z^{i}\rightarrow{}^{k_{i}}$, where each
element of the mapping ${\mathbf{h}}_{i}(\cdot)$ is a convex function, i.e.,
$h_{ij}(\cdot)$ is convex for all $j\in[l_{i}]$, and each element of
${\boldsymbol{\ell}}_{i}(\cdot)$ is a concave function, i.e., $k_{ij}(\cdot)$
is concave for all $j\in[l_{i}]$. To maintain the convex-concave structure, we
assume that

$\min_{j\in[k_{i}]}\min_{{\mathbf{z}}_{i}\in
Z^{i}}\ell_{ij}({\mathbf{z}}_{i})\geq
0,\quad\min_{j\in[k_{i}]}\min_{{\mathbf{x}}\in X}h_{ij}({\mathbf{x}})\geq
0\quad\forall i\in[m].$

We will show that we can transform such problems to the biaffine form of
Section 3.2. For this, we introduce vectors ${\boldsymbol{\varpi}}_{i}$
(${\boldsymbol{\zeta}}_{i}$ respectively) whose entries upper (lower) bound
the entries of ${\boldsymbol{\ell}}_{i}$ (${\mathbf{h}}_{i}$). With these
extra variables, the constraint $g_{i}({\mathbf{x}},{\mathbf{z}}_{i})\leq
0,\;\forall{\mathbf{z}}_{i}\in Z^{i}$ from problem (2) can be reformulated as

$\displaystyle{\boldsymbol{\varpi}}_{i}^{\top}{\boldsymbol{\zeta}}_{i}\leq
0,\;\forall({\mathbf{z}}_{i},{\boldsymbol{\zeta}}_{i})\in\Xi^{i}$
$\displaystyle{\mathbf{h}}_{i}({\mathbf{x}})\leq{\boldsymbol{\varpi}}_{i}$

where
$\Xi^{i}=\left\\{{\boldsymbol{\xi}}_{i}=({\mathbf{z}}_{i},{\boldsymbol{\zeta}}_{i}):{\mathbf{z}}_{i}\in
Z^{i},\;{\boldsymbol{\ell}}_{i}({\mathbf{z}}_{i})\geq{\boldsymbol{\zeta}}_{i}\right\\}$.
As we see, the first constraint becomes biaffine in the respective variables.
In order to decouple the constraint in ${\mathbf{x}}$, one can also duplicate
${\mathbf{x}}$ to ${\mathbf{x}}_{0},{\mathbf{x}}_{1},\ldots,{\mathbf{x}}_{m}$,
and add equality constraints ${\mathbf{x}}_{i}={\mathbf{x}}_{0}$ for all
$i\in[m]$.

Accordingly, we can define an extended primal variable vector
${\boldsymbol{\chi}}=({\mathbf{x}}_{0},\ldots,{\mathbf{x}}_{m},{\boldsymbol{\varpi}}_{1},\ldots,{\boldsymbol{\varpi}}_{m})\in{}^{n+\sum_{i=1}^{m}l_{i}}$
with feasible set

$\mathcal{X}=\left\\{{\boldsymbol{\chi}}=({\mathbf{x}}_{0},\ldots,{\mathbf{x}}_{m},{\boldsymbol{\varpi}}_{1},\ldots,{\boldsymbol{\varpi}}_{m}):{\mathbf{x}}_{0}\in
X,\;{\mathbf{h}}_{i}({\mathbf{x}}_{i})\leq{\boldsymbol{\varpi}}_{i}\right\\},$

and an extended new uncertain parameter
${\boldsymbol{\xi}}_{i}=({\mathbf{z}}_{i},{\boldsymbol{\zeta}}_{i})$ for
constraint $i$ such that ${\boldsymbol{\xi}}_{i}\in\Xi^{i}$. The $i$-th
constraint of problem (2) becomes then:

$\tilde{g}_{i}({\boldsymbol{\chi}},{\boldsymbol{\xi}})={\boldsymbol{\chi}}^{\top}{\mathbf{Q}}_{i}{\boldsymbol{\xi}}_{i}$

where

$\displaystyle{\mathbf{Q}}_{i}$
$\displaystyle=\begin{bmatrix}{\mathbf{0}}_{(n(m+1)+\sum_{j=1}^{i-1}k_{j})\times
d_{i}}&{\mathbf{0}}_{(n(m+1)+\sum_{j=1}^{i-1}k_{j})\times k_{i}}\\\
{\mathbf{0}}_{k_{i}\times d_{i}}&{\mathbf{I}}_{k_{i}}\\\
{\mathbf{0}}_{\sum_{j=i+1}^{m}k_{j}\times
d_{i}}&{\mathbf{0}}_{\sum_{j=i+1}^{m}l_{j}\times k_{i}}.\\\ \end{bmatrix}$

In the end, problem (2) can be shortly written as

$\displaystyle\min\limits_{{\boldsymbol{\chi}}\in\mathcal{X}}\ $
$\displaystyle\tilde{{\mathbf{c}}}^{\top}{\boldsymbol{\chi}}$ s.t.
$\displaystyle\sup\limits_{{\boldsymbol{\xi}}_{i}\in\Xi^{i}}\tilde{g}_{i}({\boldsymbol{\chi}},{\boldsymbol{\xi}}_{i})\leq
0,\quad i\in[m],$ $\displaystyle{\mathbf{A}}{\boldsymbol{\chi}}=0$

where $\tilde{{\mathbf{c}}}=({\mathbf{c}},{\mathbf{0}})$ and

${\mathbf{A}}=\begin{bmatrix}{\mathbf{I}}_{(n)}&-{\mathbf{I}}_{(n)}&{\mathbf{0}}_{(n\times
n)}&&\ldots&{\mathbf{0}}_{(n\times
n)}&{\mathbf{0}}_{(n\times\sum_{i\in[m]}k_{i})}\\\
{\mathbf{I}}_{(n)}&{\mathbf{0}}_{(n\times
n)}&-{\mathbf{I}}_{(n)}&{\mathbf{0}}_{(n\times
n)}&\ldots&{\mathbf{0}}_{(n\times
n)}&{\mathbf{0}}_{(n\times\sum_{i\in[m]}k_{i})}\\\
\vdots&\vdots&\ddots&\ddots&&&\vdots\\\
\vdots&\vdots&&\ddots&\ddots&&\vdots\\\
{\mathbf{I}}_{(n)}&{\mathbf{0}}_{(n\times n)}&&\ldots&{\mathbf{0}}_{(n\times
n)}&-{\mathbf{I}}_{(n)}&{\mathbf{0}}_{(n\times\sum_{i\in[m]}k_{i})}\\\
\end{bmatrix}$

Thus, we are back at the biaffine case for the lifted variables
$({\boldsymbol{\chi}},{\boldsymbol{\xi}})$, and PAPC can be applied as long as
the projections over $\Xi^{i}$ and $\mathcal{X}$ are easily attainable.

##  5 Numerical experiment: robust quadratic programming

###  5.1 Introduction

In this section, we compare the numerical performance of our SGSP algorithm to
the various approaches of ho2018online  and the standard cutting-plane
algorithm. To do this, we consider an extension of the experiment in
ho2018online , solving problems

$\displaystyle\min_{{\mathbf{x}}\in X}\ $
$\displaystyle\sup\limits_{{\mathbf{z}}\in Z}g_{0}({\mathbf{x}},{\mathbf{z}})$
(37) s.t. $\displaystyle g_{i}({\mathbf{x}},{\mathbf{z}})\leq 0$
$\displaystyle\forall{\mathbf{z}}\in Z,\ i\in[m]$

where the objective and constraint functions are:

$g_{i}({\mathbf{x}},{\mathbf{z}})=\left\|\left({\mathbf{P}}_{i0}+\sum\limits_{k=1}^{K}{\mathbf{P}}_{ik}z_{k}\right){\mathbf{x}}\right\|^{2}+{\mathbf{b}}_{i}^{\top}{\mathbf{x}}+c_{i}.$

with ${\mathbf{P}}_{ik}\in\mathbb{R}^{L\times n}$,
${\mathbf{b}}_{i}\in\mathbb{R}$ and $c_{i}\in\mathbb{R}$. We assume that
$Z=\\{{\mathbf{z}}\in{}^{K}:\|{\mathbf{z}}\|_{2}\leq 1\\}$ and
$X=\\{{\mathbf{x}}\in{}^{n}:\|{\mathbf{x}}\|_{2}\leq 1\\}$. The experiment is
an extension of the one performed in ho2018online , since the original
considers problem with uncertainty only in the objective, while ours captures
the more general setting with uncertain constraints.

Note that in (37), the functions $g_{i}({\mathbf{x}},\cdot)$ are convex, and
therefore the problem does not readily fit our framework. However, in the
pessimization problem

$\displaystyle\sup\limits_{\|{\mathbf{z}}\|\leq
1}g_{i}({\mathbf{x}},{\mathbf{z}}),$ (38)

known as the _trust region problem_ , the function $g_{i}(x,\cdot)$ can be
replaced by equivalent concave function, where the equivalence is in the sense
of the same maximal value. For this, $g_{i}$ is first rewritten as

$g_{i}({\mathbf{x}},{\mathbf{z}})={\mathbf{z}}^{\top}Q_{i}({\mathbf{x}}){\mathbf{z}}+2{\mathbf{r}}_{i}({\mathbf{x}})^{\top}{\mathbf{z}}+s_{i}({\mathbf{x}})$

where $Q_{i}({\mathbf{x}})=P_{i}({\mathbf{x}})^{\top}P_{i}({\mathbf{x}})$ with
$P_{i}({\mathbf{x}})\in\mathbb{R}^{n\times K}$ being a matrix whose columns
are the vectors ${\mathbf{P}}_{ik}{\mathbf{x}}$ for $k\in[K]$,
${\mathbf{r}}_{i}({\mathbf{x}})=P_{i}({\mathbf{x}})^{\top}P_{i0}{\mathbf{x}}$
and
$s_{i}({\mathbf{x}})=\|P_{i0}{\mathbf{x}}\|_{2}^{2}-{\mathbf{b}}_{i}^{\top}{\mathbf{x}}-c_{i}$.
For this function, by result of jeyakumar2014trust  problem (38) can be
reformulated as

$\sup\limits_{{\mathbf{z}}:\|{\mathbf{z}}\|\leq
1}g_{i}({\mathbf{x}},\cdot)=\sup\limits_{{\mathbf{z}}:\|{\mathbf{z}}\|\leq
1}{\mathbf{z}}^{\top}(Q_{i}({\mathbf{x}})-\lambda_{\text{max}}(Q_{i}({\mathbf{x}})){\mathbf{I}}){\mathbf{z}}+2{\mathbf{r}}_{i}({\mathbf{x}})^{\top}{\mathbf{z}}+s_{i}({\mathbf{x}})+\lambda_{\text{max}}(Q_{i}({\mathbf{x}}))$
(39)

where $\lambda_{\max}(\cdot)$ denotes the largest eigenvalue of the argument
matrix. Since

$\bar{g}_{i}({\mathbf{x}},{\mathbf{z}}):={\mathbf{z}}^{\top}(Q_{i}({\mathbf{x}})-\lambda_{\text{max}}(Q_{i}({\mathbf{x}})){\mathbf{I}}){\mathbf{z}}+2{\mathbf{r}}_{i}({\mathbf{x}})^{\top}{\mathbf{z}}+s_{i}({\mathbf{x}})+\lambda_{\text{max}}(Q_{i}({\mathbf{x}})),$

is convex-concave, using $\bar{g}_{i}({\mathbf{x}},{\mathbf{z}})$ instead of
$g_{i}(x,z)$ in the robust formulation is equivalent and our setting applies.
Therefore, in this set of experiments, whenever using first-order methods, we
solve the modified problem:

$\displaystyle\min_{{\mathbf{x}}\in X}\ $
$\displaystyle\sup\limits_{{\mathbf{z}}\in
Z}\bar{g}_{0}({\mathbf{x}},{\mathbf{z}})$ (40) s.t.
$\displaystyle\bar{g}_{i}({\mathbf{x}},{\mathbf{z}})\leq 0$
$\displaystyle\forall{\mathbf{z}}\in Z,\ i\in[m]$

We note that with respect ${\mathbf{x}}$, problem (40) is semidefinite
optimization problem. We are ready to state the four algorithms we compare:

  * •

Cutting planes algorithm applied directly to (37), where pessimization
subproblem (38) is solved using a generic solver to find ${\mathbf{z}}$
violating the constraints.

  * •

The SGSP algorithm applied to (40). As part of this method, we first apply
SGSP to find a Slater point for (40), and given the obtained Slater point we
run SGSP to solve problem (40).

  * •

The OCO algorithm of ho2018online , applied to (40), where both the variables
${\mathbf{x}}$ and ${\mathbf{z}}$ are solved using online gradient descent
(OGD).

  * •

The FO-pessimization approach of ho2018online  applied to (40), where the
primal problem is solved using OGD and for each constraint the worst-case
${\mathbf{z}}$ is found by solving (39) using a generic solver.

We will compare the algorithms on their speed of reducing the feasibility and
optimality gaps in the sense of Theorem 3.1. In the following Section, we
describe the exact numerical setup and the results.

###### Remark 2

In the presented experiments we do not compare to the ‘nominal‘ approach
suggested in bental2015oracle . Indeed, in the implementation of
bental2015oracle  presented in ho2018online , the authors suggests that in the
$k$-th iteration, the following problem will be solved:

$\displaystyle\min_{\mathbf{x}}\ $ $\displaystyle
g_{0}({\mathbf{x}},{\mathbf{z}}^{k}_{0})$ s.t. $\displaystyle
g_{i}({\mathbf{x}},{\mathbf{z}}^{k}_{i})\leq 0$ $\displaystyle\ i\in[m].$

However, since the convergence of such a method requires for there to be a
saddle point

$\inf_{{\mathbf{x}}\in X}\sup\limits_{{\mathbf{z}}_{i}\in
Z}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})=\sup\limits_{{\mathbf{z}}_{i}\in
Z}\inf_{{\mathbf{x}}\in X}g_{i}({\mathbf{x}},{\mathbf{z}}_{i}),$

which does not necessarily exist due to the convexity of
$g_{i}({\mathbf{x}},\cdot)$. Thus, in order to solve the (37) problem using
some kind of a ‘nominal’ approach with updated ${\mathbf{z}}^{k}_{i}$, one
would need to either (i) use the semidefinite program (40) as the nominal
oracle which contradicts the idea of solving ‘simple’ problems per iteration,
or (ii) use the dual-subgradient meta-algorithm of bental2015oracle  where
${\mathbf{z}}_{i}$ is lifted to a semidefinite matrix and the original nominal
oracle (37) is used w.r.t. ${\mathbf{x}}$ – however, running the dual step
would require projections on the spectahedron which, again, contradicts the
idea of solving ‘simple’ problems, or (iii) use the dual-perturbation meta-
algorithm of bental2015oracle  – however, as we focus on deterministic
algorithms, we do not include an implementation of bental2015oracle .

###  5.2 Expriment setting

We explored different problem sizes, with respect to $n$ the dimension of
${\mathbf{x}}$, $m$ the number of constraints, $K$ the dimension of
uncertainty ${\mathbf{z}}_{i}$, and $\ell$ the dimension of the vector in the
norm. For each problem size, we sampled the problem data for 50 problem
instances as follows. First, each entry of ${\mathbf{P}}_{ik}$ and
${\mathbf{b}}_{i}$ is sampled uniformly from interval $[-1,1]$. Fixed value
$c_{i}=-0.05$ is chosen deterministically to ensure Slater feasibility of the
problem. Next, ${\mathbf{P}}_{ik}$ and ${\mathbf{b}}_{i}$ are normalized as

$\displaystyle{\mathbf{P}}_{ik}$
$\displaystyle=\frac{{\mathbf{P}}_{ik}}{S_{i1}}$ $\displaystyle\text{ where
}S_{i1}=\left\|\left[{\mathbf{P}}_{i0}^{\top}\ \cdots\
{\mathbf{P}}_{iK}^{\top}\right]^{\top}\right\|_{2,2}$
$\displaystyle{\mathbf{b}}_{i}$
$\displaystyle=\frac{{\mathbf{b}}_{i}}{S_{i2}}$ $\displaystyle\text{ where
}S_{i2}=\|{\mathbf{b}}_{i}\|_{2}$

To compare the algorithms in a fair way, we will use the same starting point
for all of them. This point will be the optimal solution to the nominal
problem

$\displaystyle\min_{\mathbf{x}}\ $ $\displaystyle
g_{0}({\mathbf{x}},{\mathbf{0}})$ s.t. $\displaystyle
g_{i}({\mathbf{x}},{\mathbf{0}})\leq 0$ $\displaystyle\ i\in[m].$

The values ${\mathbf{z}}_{i}$ are initialized as the zero vectors. We consider
an $\epsilon$ tolerance of $0.001$ for both feasibility and optimality.

Note that the first-order algorithms require a choice of step-size. The step-
size for OGD is chosen to be
${2}/({\left\|{\nabla_{\mathbf{x}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})}\right\|\sqrt{k}})$
and
${2}/({\left\|{\nabla_{{\mathbf{z}}_{i}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})}\right\|\sqrt{k}})$
for the primal and dual steps at iteration $k$, respectively. These stepsizes
correspond with the analysis of OGD given in (Hazan2016, , Theorem 3.4).
Similarly, the step sizes for SGSP is given by
$\tau^{k}={2}/({\left\|{\nabla_{{\mathbf{x}}}L({\mathbf{x}},{\mathbf{u}})}\right\|\sqrt{k}})$
and
$\theta^{k}_{i}={2}/({\left\|{\nabla_{{\mathbf{u}}_{i}}L({\mathbf{x}},{\mathbf{u}})}\right\|\sqrt{k}})$
for the primal and dual steps at iteration $k$, respectively 111We note that
although the analysis of nedic2009subgradient  was done for a constant step-
size, a similar analysis to the one shown in (Hazan2016, , Theorem 3.4) can be
done for SGSP, with similar theoretical results.. In both cases, the average
solution $\bar{{\mathbf{x}}}^{N}$ is computed as a weighted sum of the
iterates ${\mathbf{x}}^{k}$ with weights corresponding to the step-sizes. We
note that these step-sizes were chosen instead of constant step-sizes, since
they produced better results for all methods while retaining theoretical
convergence guarantees.

Table 3 describes the different settings in which the algorithms were run. We
consider small, medium and large problem sizes, with either no constraints or
three constraints for each. For each problem size we specify the time limit we
gave the methods as well as the sampling frequency for the output (see
explanation below).

Table 3: Sizes of tested problems Name | $n$ | $K$ | $L$ | $m$ | maximum allowed time | Output frequency
---|---|---|---|---|---|---
|  |  |  |  | (seconds) | ($\tilde{N}$ iterations)
Small | 10 | 10 | 10 | 0 | 600 | 100 222Cutting planes method records every iteration.
|  |  |  | 3 |  |
Medium | 600 | 25 | 15 | 0 | 1200 | 100
|  |  |  | 3 |  |
Large | 3600 | 30 | 16 | 0 | 3600 | 100
|  |  |  | 3 |  |

In order to measure the feasibility and the optimality gap for each method,
for each parameter realization, we first define a constant $\tilde{N}$, such
that every $\tilde{N}$ iterations statistics on the solution are gathered.
Specifically, for all $k\in\mathbb{N}$, let ${\mathbf{x}}^{k\tilde{N}}$ be the
solution obtained after iteration $k\tilde{N}$ of the algorithm, and let
$T_{k}$ be the time it took to run these $k\tilde{N}$ iterations. The
feasibility gap at iteration $k\tilde{N}$ is given by

$\text{FG}_{k}:=\max_{i\in[m]}\max_{{\mathbf{z}}_{i}\in
Z}g_{i}({\mathbf{x}}^{k\tilde{N}},{\mathbf{z}}_{i}).$

Defining the optimality gap to be infinity if the feasibility gap is larger
than the defined $\epsilon$, the optimality gap ratio at iteration
$k\tilde{N}$ is given by

$\text{OGR}_{k}:=\frac{\delta_{\\{p:p\leq\epsilon\\}}(\text{FG}_{k})\max_{{\mathbf{z}}_{i}\in
Z}g_{0}({\mathbf{x}}^{k\tilde{N}},{\mathbf{z}}_{i})-\text{LB}}{\text{LB}}.$

In the above formula, $\delta_{\\{p:p\leq\epsilon\\}}$ is the indicator
function, and LB is the lower bound on the optimal solution obtained at the
end of the cutting planes algorithm, by only considering the cuts added during
the algorithm. Thus, for each time $t\geq 0$ we can record the minimal
feasibility gap up to time $t$ as

$\min_{k:T_{k}\leq t}\text{FG}_{k},$

and the minimal optimality gap ratio up to time $t$ as

$\min_{k:T_{k}\leq t}\text{OGR}_{k}.$

All the code was run using Python 3.7, with the CasADi package Andersson2019
as the optimization interface. The optimization problems were solved using
Gurobi 9.0.0 gurobi , with the exception of the trust-region subproblem (38)
that due to numerical difficulties was solved using the IPOPT solver
wachter2006implementation . The code was run on a PowerEdge R740xd server with
two Intel Xeon Cold 6254 3.1GHz processors, each with 18 cores, and a total
RAM of 384GB.

###  5.3 Results

In Figure 1, we show the optimality convergence for all methods for the small,
medium, and large instances without constraints. In the small instances, the
computational and memory requirements of the cutting planes algorithm are
negligible, and its performance dominates the other methods. Among the first
order methods, however, the SGSP algorithm attains the fastest convergence.

When the problem instances become larger, the memory and computational
requirements of the cutting planes algorithm become more significant, making
its performance similar (medium instances) and then worse than the performance
of the first-order methods. Among the first-order methods, our SGSP algorithm
consistently dominates the other methods, although the differences with the
OCO are rather small. Interestingly, we observe that for all methods it is the
medium instances that keep their optimality gaps rather large for the longest.
This might be related to the way we sample the problems where up to a certain
point the problem size growth effect outweighs the ‘averaging out’ effect of
the large matrices that make it easier to find a high-quality solution.

Figure 1: Optimality gap for all problem sizes with $m=0$.

We now proceed to discuss the constrained problems. In Figures 2-4 we show the
results for the small, medium, and large instances, respectively. We start
with discussing the small examples. Similarly to the unconstrained case, the
cutting planes algorithm is the fastest of all. Among the first-order methods,
OFO is better than SGSP at finding feasible solutions fast, but having found
them, it gets ‘stuck’ on improving optimality due to the need to run binary
search on the objective value. Specifically, the problem is with the bi-
section iterations which do not have a feasible solution, but this
infeasibility can only be identified after performing a very large number of
iterations. The FO-Pess method is the slowest across all three measures.

Figure 2: Small instances, $m=3$. Percentage of instances with a feasible
solution found, feasibility gap among infeasible instances, and optimality gap
among the feasible instances.

For the medium instances in Figure 3, we would expect the first order methods
to already perform better than the cutting planes algorithm. Indeed, the
cutting planes algorithm becomes worse in decreasing the feasibility gap and
the number of infeasible instances compared to all first-order methods. Among
the feasible first-order methods, again, it is the SGSP algorithm that manages
to reach optimality guarantees within the prescribed amount of time which are
equivalent to those of the cutting planes, while OFO and FO-Pess do get stuck
due to the need for running the binary search on the objective function value.

Figure 3: Medium instances, $m=3$. Percentage of instances with a feasible
solution found, feasibility gap among infeasible instances, and optimality gap
among the feasible instances.

Finally, for the largest instances in Figure 4, predictably, the cutting
planes does not only have inferior performance to all first order based
methods. We therefore focus on the comparison of computational performance of
the three first-order methods. We observe that all first order methods are
able to find feasible solutions faster than in the medium instances. We again
believe that this is due to the problem generation process. Among the first-
order methods, SGSP is relatively the slowest one to find a feasible solution
for all the instances. With respect to the optimality gap, we observe that OFO
slightly dominates the SGSP. The SGSPs performance on these instances is
affected by the fact that at each iteration, it requires gradient computations
with respect to all the constraints, whereas for the OFO this is done only for
the constraint with largest current value of the left-hand side. Since for
large dimensional problems these computations are substantial, the SGSP
performs slightly slower than OFO, while dominating over the FO-Pess method.

Figure 4: Large instances, $m=3$. Percentage of instances with a feasible
solution found, feasibility gap among infeasible instances, and optimality gap
among the feasible instances.

##  6 Conclusions

In this paper, we have proposed a first-order optimization approach to robust
optimization problems based on a convex-concave saddle-point reformulation of
the problem’s Lagrangian. Our approach recovers the
$\mathcal{O}(1/\epsilon^{2})$ convergence rate for general problems considered
also by bental2015oracle ; ho2018online , and offers an improved
$\mathcal{O}(1/\epsilon)$ convergence guarantee for problems with a biaffine
function structure. Similar to those algorithms, our method allows for a
convenient parallelization of the computations related to different constraint
functions and avoids problem size increase typical for the cutting planes and
robust counterparts approaches. At the same time, our approach has the
numerical benefit of avoiding a binary-search procedure for the optimal value
of the objective as in ho2018online , while providing a deterministic
algorithm which does not have to solve the nominal problem, contrary to
bental2015oracle .

## Acknowledgements

We thank Fatma Kılınç-Karzan and Nam Ho-Nguyen for their discussions and
sharing with us the implementation of their experiments. We also thank Shoham
Sabach for his work at the early stage of this work and valuable suggestions.

##  Appendix A Proofs

######  Proof (Proof of Proposition 1. )

Proof of $\Rightarrow$. We first note that from the definition of $f_{i}$ and
the construction of the lifted uncertainty set $U^{i}$ we have that for any
${\boldsymbol{\lambda}}\in{}^{m}_{+}$ and ${{\mathbf{x}}}\in X$ and $i\in[m]$.

$\displaystyle{\lambda}_{i}f_{i}({{\mathbf{x}}})$
$\displaystyle={\lambda}_{i}\sup\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})=\sup\limits_{\tilde{{\mathbf{z}}}_{i}:(\tilde{{\mathbf{z}}}_{i},{\lambda}_{i})\in
U^{i}}\lambda_{i}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}}\right).$

Indeed, if $({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$ is a
saddle point of $\bar{L}$ then, defining
${\mathbf{z}}_{i}^{*}=\tilde{{\mathbf{z}}}^{*}_{i}/\lambda_{i}^{*}$ if
$\lambda^{*}>0$ and ${\mathbf{z}}_{i}^{*}=0$ otherwise, gives:

$L({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))=\bar{L}({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*})),$
(41)

and

$\displaystyle\bar{L}({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$
$\displaystyle=$ $\displaystyle\sup_{{\mathbf{u}}\in
U,{\mathbf{w}}\in\mathbb{R}^{r}}\bar{L}({\mathbf{x}}^{*},({\mathbf{u}},{\mathbf{w}}))$
$\displaystyle=$
$\displaystyle\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},\;\tilde{{\mathbf{z}}}_{i}\in\lambda_{i}Z^{i},\;i\in[m],{\mathbf{w}}\in\mathbb{R}^{r}}{\mathbf{c}}^{\top}{{\mathbf{x}}}^{*}+\sum\limits_{i=1}^{m}\lambda_{i}g_{i}\left({\mathbf{x}}^{*},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}}\right)+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})$
$\displaystyle=$
$\displaystyle\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}{\mathbf{c}}^{\top}{{\mathbf{x}}}^{*}+\sum\limits_{i=1}^{m}\lambda_{i}\sup\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}}^{*},{\mathbf{z}}_{i})+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})$
$\displaystyle=$
$\displaystyle\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}{\mathbf{c}}^{\top}{{\mathbf{x}}}^{*}+\sum_{i=1}^{m}{\lambda}_{i}f_{i}({{\mathbf{x}}}^{*})+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})$
$\displaystyle=$
$\displaystyle\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}L({\mathbf{x}}^{*},({\boldsymbol{\lambda}},{\mathbf{w}})),$
(42)

where the subsequent equalities follow from (i) the definition of $\bar{L}$,
(ii) definition of $U^{i}$, (iii) the definition of $f_{i}$, and (iv) the
definition of $L$. Moreover,

$\displaystyle\bar{L}({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))=$
$\displaystyle\inf_{{\mathbf{x}}\in
X}\bar{L}({\mathbf{x}},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$ $\displaystyle=$
$\displaystyle\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\lambda^{*}_{i}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}^{*}_{i}}{\lambda^{*}_{i}}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
$\displaystyle\leq$ $\displaystyle\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum\limits_{i=1}^{m}\sup_{\tilde{{\mathbf{z}}}_{i}:(\tilde{{\mathbf{z}}}_{i},\lambda^{*}_{i})\in
U^{i}}\lambda^{*}_{i}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda^{*}_{i}}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
$\displaystyle=$ $\displaystyle\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum\limits_{i=1}^{m}\sup_{{\mathbf{z}}_{i}\in
Z^{i}}\lambda^{*}_{i}g_{i}({\mathbf{x}},{\mathbf{z}}_{i})+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
$\displaystyle=$ $\displaystyle\inf_{{\mathbf{x}}\in
X}L({\mathbf{x}},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*})),$ (43)

where the subsequent steps follow from (i) the definition of $\bar{L}$, (ii)
the definition of $U^{i}$, and (iii) the definition of $L$. Combining (41),
(42) and (43) we obtain that

$\displaystyle\inf_{{\mathbf{x}}\in
X}\bar{L}({\mathbf{x}},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))=$
$\displaystyle\inf_{{\mathbf{x}}\in
X}L({\mathbf{x}},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$
$\displaystyle=$ $\displaystyle
L({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$
$\displaystyle=$
$\displaystyle\bar{L}({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$
$\displaystyle=$ $\displaystyle\sup_{{\mathbf{u}}\in
U,{\mathbf{w}}\in\mathbb{R}^{r}}\bar{L}({\mathbf{x}}^{*},({\mathbf{u}},{\mathbf{w}}))$
$\displaystyle=$
$\displaystyle\sup_{{\boldsymbol{\lambda}}\in{}^{m}_{+},{\mathbf{w}}\in\mathbb{R}^{r}}L({\mathbf{x}}^{*},({\boldsymbol{\lambda}},{\mathbf{w}})),$

_i.e._ , $({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ is
a saddle point of $L$.

Proof of $\Leftarrow$. We shall show that
$({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ can be
extended to a saddle point of the lifted Lagrangian $\bar{L}$. Note that
defining $\tilde{{\mathbf{z}}}_{i}=\lambda_{i}{\mathbf{z}}_{i}$ we have that

$\displaystyle{\mathbf{c}}^{\top}{\mathbf{x}}^{*}+\sum_{i=1}^{m}\lambda_{i}^{*}f_{i}\left({\mathbf{x}}^{*}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})$
$\displaystyle=\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}^{*}\max\limits_{(\tilde{{\mathbf{z}}}_{i},\lambda_{i}^{*})\in
U^{i}}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}^{*}}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
$\displaystyle=\max\limits_{\begin{subarray}{c}(\tilde{{\mathbf{z}}}_{i},\lambda_{i}^{*})\in
U^{i},\;i\in[m]\end{subarray}}\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}^{*}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}^{*}}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})$
$\displaystyle=\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}^{*}g_{i}\left({\mathbf{x}},\frac{\hat{{\mathbf{z}}}_{i}}{\lambda_{i}^{*}}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}}).$

The first equality is due to
$({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ being a
saddle point of $L$ and the definition of $f_{i}$. The third equality follows
from Sion’s theorem, applicable due to boundedness of
$\\{(\tilde{{\mathbf{z}}},\lambda_{i})\in U^{i}:\
\lambda_{i}=\lambda_{i}^{*}\\}$ and where we define $\hat{{\mathbf{z}}}_{i}$
as a (necessarily-existing) maximizer:

$(\hat{{\mathbf{z}}}_{i})_{i\in[m]}\in\arg\max_{\tilde{{\mathbf{z}}}_{i}:(\tilde{{\mathbf{z}}}_{i},\lambda_{i}^{*})\in
U^{i}}\left\\{\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}^{*}g_{i}\left({\mathbf{x}},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}^{*}}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})\right\\}.$

Thus, defining
${\mathbf{u}}^{*}_{i}=(\hat{{\mathbf{z}}}^{*}_{i},\lambda^{*}_{i})$ we have
that

$L({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))=\bar{L}({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))=\inf_{{\mathbf{x}}\in
X}{\mathbf{c}}^{\top}{\mathbf{x}}+\sum_{i=1}^{m}\lambda_{i}^{*}g_{i}\left({\mathbf{x}},\frac{\hat{{\mathbf{z}}}_{i}^{*}}{\lambda_{i}^{*}}\right)+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}-{\mathbf{b}})=\inf_{{\mathbf{x}}\in
X}\bar{L}({\mathbf{x}},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$

Moreover,

$\displaystyle\bar{L}({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))=L({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$
$\displaystyle={\mathbf{c}}^{\top}{\mathbf{x}}^{*}+\sum_{i=1}^{m}\lambda_{i}^{*}f_{i}({\mathbf{x}}^{*})+{\mathbf{w}}^{*\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})$
$\displaystyle={\mathbf{c}}^{\top}{\mathbf{x}}^{*}+\sup\limits_{{\boldsymbol{\lambda}}\geq{}^{m}_{+},{\mathbf{w}}\in{}^{r}}\sum_{i=1}^{m}\lambda_{i}\sup\limits_{{\mathbf{z}}_{i}\in
Z^{i}}g_{i}({\mathbf{x}}^{*},{\mathbf{z}})+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})$
$\displaystyle={\mathbf{c}}^{\top}{\mathbf{x}}^{*}+\sup\limits_{{\mathbf{u}}_{i}=(\lambda_{i},\tilde{{\mathbf{z}}}_{i})\in
U^{i},\;i\in[m],{\mathbf{w}}}\sum_{i=1}^{m}\lambda_{i}g_{i}\left({\mathbf{x}}^{*},\frac{\tilde{{\mathbf{z}}}_{i}}{\lambda_{i}}\right)+{\mathbf{w}}^{\top}({\mathbf{A}}{\mathbf{x}}^{*}-{\mathbf{b}})$
$\displaystyle=\max_{{\mathbf{u}}_{i}\in
U^{i},\;i\in[m],{\mathbf{w}}\in{}^{r}}\bar{L}({\mathbf{x}}^{*},({\mathbf{u}},{\mathbf{w}})),$

where we used the fact that
$({\mathbf{x}}^{*},({\boldsymbol{\lambda}}^{*},{\mathbf{w}}^{*}))$ is a saddle
point of the original Lagrangian $L$, and the definition of $f_{i}$, $L$, and
$\bar{L}$. Thus, we showed that
$({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$ is a saddle point of
$\bar{L}$. ∎

######  Proof (Proof of Lemma 1. )

From Assumptions 1 and 2 we have that problem (4) has a saddle point, and due
to Proposition 1 so does problem (6). Note that for any
${\mathbf{x}}\in{}^{n}$, ${\mathbf{u}}\in U$, and
${\boldsymbol{\pi}}^{*}\in{}^{n}$ we have that

$\tilde{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}},{\boldsymbol{\pi}}^{*}))\leq\sup_{{\boldsymbol{\pi}}\in{}^{n}}\tilde{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}},{\boldsymbol{\pi}}))=\bar{L}({\mathbf{x}},({\mathbf{u}},{\mathbf{w}}))+\delta_{X}({\mathbf{x}}).$
(44)

Let $({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))$ be a saddle point
of $\bar{L}$, and let
${\boldsymbol{\pi}}^{*}=-{\mathbf{c}}-\tilde{{\mathbf{Q}}}{\mathbf{u}}^{*}-{\mathbf{A}}^{\top}{\mathbf{w}}^{*}$.
Then,

$\displaystyle\inf_{{\mathbf{x}}\in
X}\tilde{L}({\mathbf{x}},({\mathbf{u}}^{*},{\mathbf{w}}^{*},{\boldsymbol{\pi}}^{*}))$
$\displaystyle=\inf_{{\mathbf{x}}\in
X}{\mathbf{x}}^{\top}\left({\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}+\tilde{{\mathbf{Q}}}{\mathbf{u}}^{*}+{\boldsymbol{\pi}}^{*}\right)+\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}^{*}-{\mathbf{b}}^{\top}{\mathbf{w}}^{*}-\sigma_{X}({\boldsymbol{\pi}}^{*})$
$\displaystyle=\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}^{*}-{\mathbf{b}}^{\top}{\mathbf{w}}^{*}-\sigma_{X}({\boldsymbol{\pi}}^{*})$
$\displaystyle=\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}^{*}-{\mathbf{b}}^{\top}{\mathbf{w}}^{*}+\inf_{{\mathbf{x}}\in
X}-{\mathbf{x}}^{\top}{\boldsymbol{\pi}}^{*}$
$\displaystyle=\inf_{{\mathbf{x}}\in
X}{\mathbf{x}}^{\top}\left({\mathbf{c}}+{\mathbf{A}}^{\top}{\mathbf{w}}^{*}+\tilde{{\mathbf{Q}}}{\mathbf{u}}^{*}\right)-{\mathbf{b}}^{\top}{\mathbf{w}}^{*}+\tilde{{\mathbf{q}}}^{\top}{\mathbf{u}}^{*}=\inf_{{\mathbf{x}}\in
X}\bar{L}({\mathbf{x}},({\mathbf{u}}^{*},{\mathbf{w}}^{*})),$ (45)

where the first equality follows from the definition of $\tilde{L}$, the
second equality follows from the definition of ${\boldsymbol{\pi}}^{*}$, the
third equality follows from the definition of the support function, the fourth
equality follows from the definition of ${\boldsymbol{\pi}}^{*}$, and the last
equality follows from the definition of $\bar{L}$. Combining (44) and (45) we
have that

$\tilde{L}({\mathbf{x}}^{*},({\mathbf{u}}^{*},{\mathbf{w}}^{*},{\boldsymbol{\pi}}^{*}))=\bar{L}({\mathbf{x}}^{*},({\mathbf{w}}^{*},{\mathbf{u}}^{*}))=\inf_{{\mathbf{x}}\in
X}\bar{L}({\mathbf{x}},({\mathbf{u}}^{*},{\mathbf{w}}^{*}))=\inf_{{\mathbf{x}}\in
X}\tilde{L}({\mathbf{x}},({\mathbf{u}}^{*},{\mathbf{w}}^{*},{\boldsymbol{\pi}}^{*}))$

Moreover,