We use the notations $\langle\cdot ,\cdot\rangle$ and $\|\cdot\|$ for the {standard inner} product and norm on $\RR^d${, respectively}. Gradient of differentiable $f:\RR^d\rightarrow\RR$ at $x$ is denoted by $\nabla f(x)$. For a differentiable map $A:\RR^d\rightarrow\RR^m$, $\D A(x$ denote its Jacobian at $x$.
For a convex function $g:\RR^d\rightarrow\RR$, the subdifferential at $x$ is denoted by $\partial g(x)$ and the proximal operator $P_g:\RR^d\rightarrow\RR^d$ takes $x$ to
In addition, if $g=1_C$ is the indicator function of a convex set or cone, we use the simpler notation $P_C$, instead of $P_{1_C}$, to denote the orthogonal projection onto $C$.
Throughout, $g^*$ and $\partial g^*$ will denote the Fenchel conjugate of $g$ and its subdifferential, respectively. For a cone $C$, we denote its polar by $C^*$, namely,
\begin{align}
C^* = \{x: \langle x,x'\rangle\le 0,\,\,\forall x' \in C \}.
\end{align}
An integer interval is denoted by $[k_0:k_1]=\{k_0,\cdots,k_1\}$ for integers $k_0\le k_1$. For matrices, $\|\cdot\|$ and $\|\cdot\|_F$ denote the spectral and Frobenius norms, respectively.
{First-order necessary optimality conditions} for \eqref{prob:01} are well-studied~\cite{rockafellar2009variational}. {Indeed, $x$ is a (first-order) stationary point of \eqref{prob:01} if there exists $y\in\RR^m$ for which
\begin{align}
\begin{cases}
-\nabla f(x) - \D A(x)^\top y \in\partial g(x)\\
A(x) = 0.
\end{cases}
\label{e:inclu1}
\end{align}
Recalling \eqref{eq:Lagrangian}, we observe that \eqref{e:inclu1} is equivalent to
which is in turn the first-order optimality condition for \eqref{eq:minmax}. }\notea{have to add 2nd optimality?}
\paragraph{\emph{\textbf{Technical lemmas.}}} The following standard results and notions are frequently used throughout this paper and proved in the appendix for completeness. The first result below shows that the augmented Lagrangian is smooth, see Appendix~\ref{sec:proof of smoothness lemma} for the proof.
\begin{lemma}[Smoothness]\label{lem:smoothness}
For fixed $y\in\RR^m$ and $\b,\rho,\rho'\ge0$, it holds that
and $\lambda_f,\lambda_A$ were defined in (\ref{eq:smoothness basic}).
\end{lemma}
Gradient mapping~\notea{what to cite?}, defined below, plays an important role in our convergence analysis.
\begin{definition}\label{def:grad map}\textbf{{(Gradient mapping)}} Given $y\in\RR^d$ and $\gamma >0$, the gradient mapping $G_{\beta,\gamma}(\cdot; y): \RR^d\rightarrow\RR^d$ takes $x\in\RR^d$ to
\begin{equation}
G_{\b,\gamma}(x,y) = \frac{x-x^+}{\gamma},
\label{eq:grad map}
\end{equation}
where $x^+=P_{g}(x-\gamma\nabla_x \mathcal{L}_ {\beta}(x,y))$.
\end{definition}
As the name suggests, if in particular we set $g\equiv0$ in \eqref{prob:01}, the gradient mapping reduces to $G_{\beta,\gamma}(x,y)=\nabla f(x)$. For a sufficiently small step size $\g$, the gradient mapping controls the descent in the objective function of \eqref{eq:minmax}. The following result is standard \cite[Lemma 3.2, Remark 3.2(i)]{bolte2014proximal}, but the proof is given in Appendix \ref{sec:proof of descent lemma} for completeness.
\begin{lemma}[Descent lemma]\label{lem:11}
For $x\in\RR^d$ and $y\in\RR^m$, let $x^+= P_g(x -\g\nabla_x \L_\b(x,y))$, where $\g< 1/\lambda_\b$. For $\rho,\rho'\ge0$, suppose that
\| G_{\beta,\gamma}(x,y)\|^{2}\leq\frac{2}{\gamma} (\mathcal{L}_\beta(x,y) + g (x)- \mathcal{L}_\beta(x^+,y)- g(x^+) ).
\end{equation}
\end{lemma}
In {practice}, determining the step size $\gamma$ by computing the right-hand side of \eqref{eq:smoothness of Lagrangian} is infeasible, since $\lambda_f,\lambda_A,\lambda'_A$ are often unknown. Instead, we can resort to the line search technique, reviewed below and proved in Appendix~\ref{sec:proof of linesearch}.
\begin{lemma}[Line search] \label{lem:eval Lipsc cte} Fix $\theta\in(0,1)$ and ${\gamma}_0>0$. For $\gamma'>0$, let