Convergence of Augmented Lagrangian Methods for Composite Optimization
Problems
NGUYEN T. V. HANG111School of Physical and Mathematical Sciences, Nanyang
Technological University, Singapore 639798 and Institute of Mathematics,
Vietnam Academy of Science and Technology, Hanoi, Vietnam
(thivanhang.nguyen@ntu.edu.sg). Research of this author is partially supported
by Singapore National Academy of Science under the grant RIE2025 NRF
International Partnership Funding Initiative. and EBRAHIM
SARABI222Corresponding author, Department of Mathematics, Miami University,
Oxford, OH 45065, USA (sarabim@miamioh.edu). Research of this author is
partially supported by the U.S. National Science Foundation under the grant
DMS 2108546.

Abstract. Local convergence analysis of the augmented Lagrangian method (ALM)
is established for a large class of composite optimization problems with
nonunique Lagrange multipliers under a second-order sufficient condition. We
present a new second-order variational property, called the semi-stability of
second subderivatives, and demonstrate that it is widely satisfied for
numerous classes of functions, important for applications in constrained and
composite optimization problems. Using the latter condition and a certain
second-order sufficient condition, we are able to establish Q-linear
convergence of the primal-dual sequence for an inexact version of the ALM for
composite programs.
Keywords. augmented Lagrangian, nonunique Lagrange multiplier, second-order
sufficient condition, ${\cal C}^{2}$-decomposable functions, Q-linear
convergence.
Mathematics Subject Classification (2000) 90C31, 65K99, 49J52, 49J53

##  1 Introduction

The augmented Lagrangian method, also known as the method of multipliers, was
introduced and studied independently by Hestenes in [13] and Powell in [25]
for nonlinear programming problems (NLPs) with equality constraints. It was
later extended in [27] for problems of convex programming with inequality
constraints by Rockafellar, where its convergence analysis was carried out by
applying the proximal point algorithm to the dual of the augmented Lagrangian
problem and ensuring the Q-linear convergence of the dual sequence and
R-linear convergence of the primal sequence in the ALM. Most of the
publications about the ALM afterwards exploited a different approach to
establish the local convergence of this method, since the original idea in
[27] relied heavily on duality, which was not available for nonconvex
settings. The pioneering work of Fernández and Solodov in [9] was perhaps the
culmination of those efforts over the last three decades to find conditions
under which the Q-linear convergence of the primal-dual sequence, constructed
by the ALM, can be achieved for NLPs with nonunique Lagrange multipliers.
Instead of looking for duality in the augmented Lagrangian problem, the
authors in [9] showed that the primal-dual iterates of the ALM are indeed a
solution to a particular perturbation of the KKT system of the original
problem. That paved the path for them to utilize a general framework by
Fischer in [10] for solving generalized equations and demonstrate that the
classical second-order sufficient condition alone suffices for local
convergence analysis of the ALM and no constraint qualification is necessary
for such a result.

Another possible approach to conduct local convergence analysis of the ALM for
nonconvex optimization problems was recently developed by Rockafellar in [29],
where he extended his original idea in [27] of using duality and the proximal
point algorithm to obtain convergence of the dual sequence in the ALM. The
principal idea therein was to assume the strong variational convexity (see
page 166 in [28]) of the augmented Lagrangian function, which was
characterized in [28, Theorem 5] to be equivalent to the strong second-order
sufficient conditions for NLPs. While the approach in [29] provides a general
framework for the local convergence analysis of the ALM, it operates under a
rather strong assumption, namely the strong second-order sufficient condition
for constrained optimization problems. This, in particular, can be a
challenging assumption to disentangle when we deal with important classes of
optimization problems such as eigenvalue optimization problems.

Following the approach by Fernández and Solodov in [9], we aim to analyze the
local convergence of the ALM for a class of composite optimization problems
that have a representation of the form

$\begin{cases}\mbox{minimize}\;\;\psi(x)\quad\mbox{subject
to}\;\;x\in\Theta,\\\
\mbox{with}\;\;\psi(x):=\varphi(x)+g(\Phi(x)),\end{cases}$ (1.1)

where $\varphi:{\bf X}\to{\bf R}$ and $\Phi:{\bf X}\to{\bf Y}$ are twice
continuously differentiable functions, $g:{\bf Y}\to\overline{{\bf
R}}:=[-\infty,\infty]$ is a proper lsc convex function, $\Theta$ is a
polyhedral convex set, and ${\bf X}$ and ${\bf Y}$ are finite dimensional
Hilbert spaces. The composite problem in (1.1) encompasses many important
classes of constrained and composite optimization problems such as NLPs and
nonlinear semidefinite programming problems (SDPs), convex piecewise linear-
quadratic composite optimization problems, and eigenvalue related optimization
problems. We reveal two major second-order variational conditions for the
convex function $g$ in (1.1), which together with the second-order sufficient
condition allow us to establish Q-linear convergence of the primal-dual
sequence of the ALM for (1.1). In particular, we do not assume any constraint
qualification, and hence are able to deal with composite problems with
nonunique Lagrange multipliers.

The main idea of the ALM is to smooth out the nondifferentiable parts in the
composite function $\psi$ in (1.1) and to minimize then the obtained augmented
function for the next iterate of the method. To elaborate more, consider the
augmented Lagrangian function ${\mathscr{L}}:{\bf X}\times{\bf
Y}\times(0,\infty)\to{\bf R}$, defined by

${\mathscr{L}}(x,y,\rho):=\inf_{u\in{\bf
Y}}\big{\\{}\psi(x,u)+\frac{1}{2\rho}\|u\|^{2}-\langle
y,u\rangle\big{\\}},\quad(x,y,\rho)\in{\bf X}\times{\bf Y}\times(0,\infty),$

where $\psi(x,u)$ is a partial perturbation of $\psi$ in (1.1), given by
$\psi(x,u):=\varphi(x)+g(\Phi(x)+u)$ for any $(x,u)\in{\bf X}\times{\bf Y}$.
Note that the full perturbation of $\psi$ requires to replace $\psi$ with
$\psi+\delta_{\Theta}$ and consider then a second perturbation variable for
$\Theta$. This complicates our convergence analysis and seems unnecessary,
however. A direct calculation then shows that for any $(x,y,\rho)\in{\bf
X}\times{\bf Y}\times(0,\infty)$, the augment Lagrangian ${\mathscr{L}}$ can
be equivalently expressed as

${\mathscr{L}}(x,y,\rho)=\varphi(x)+e_{{1}/{\rho}}g\big{(}\Phi(x)+\rho^{-1}y\big{)}-\hbox{${1\over
2}$}\rho^{-1}\|y\|^{2},$ (1.2)

where $e_{1/\rho}g$ stands for the Moreau envelope of $g$, given by

$(e_{1/{\rho}}g)(y):=\inf_{z\in{\bf
Y}}\big{\\{}g(z)+\tfrac{1}{2}\rho\|y-z\|^{2}\big{\\}},\quad y\in{\bf Y}.$

Given the current triple $({x^{k}},y^{k},{\rho_{k}})\in{\bf X}\times{\bf
Y}\times(0,\infty)$, the exact version of the ALM generates the next primal
iterate ${x^{k+1}}$ and the dual iterate $y^{k+1}$, respectively, by

${x^{k+1}}\in\operatorname*{arg\,min}_{x\in\Theta}{\mathscr{L}}(x,y^{k},{\rho_{k}})\quad\mbox{and}\quad
y^{k+1}=y^{k}+{\rho_{k}}\nabla_{y}{\mathscr{L}}({x^{k+1}},y^{k},{\rho_{k}}).$
(1.3)

Since selecting ${x^{k+1}}$ as an exact minimizer of the augmented Lagrangian
function does not seem practical, we are going to consider a more realistic
scenario and demand that the next primal iterate ${x^{k+1}}$ be an approximate
stationary solution to the constrained augmented problem

$\mbox{minimize}\;\;{\mathscr{L}}(x,y^{k},{\rho_{k}})\quad\mbox{subject
to}\quad x\in\Theta,$ (1.4)

namely it satisfies the condition

${\rm
dist}\big{(}-\nabla_{x}{\mathscr{L}}({x^{k+1}},y^{k},{\rho_{k}}),N_{\Theta}({x^{k+1}})\big{)}\leq{\epsilon_{k}},$
(1.5)

where ${\epsilon_{k}}\geq 0$ is called the tolerance parameter. Note that an
exact minimizer ${x^{k+1}}$ as the one in (1.3) satisfies (1.5) with
${\epsilon_{k}}=0$.

As pointed earlier, the local convergence of the ALM for (1.1) was conducted
in [9] for NLPs when the second-order sufficient condition is satisfied. Using
the tools of second-order variational analysis, we showed in [12] that a
similar convergence analysis can be achieved for (1.1) when $g$ therein
belongs to the class of convex piecewise linear-quadratic functions. For SDP,
the Q-linear convergence of the primal-dual sequence for the exact ALM was
justified in [34] when the nondegeneracy condition and the strong second-order
sufficient condition are satisfied. In the same setting, it was recently shown
in [35, Theorem 2] that if a relative interior condition for the underlying
Lagrange multiplier and the SOSC are satisfied, the inexact version of the ALM
is Q-linearly convergent. Using a stronger version of the SOSC, the authors in
[36] obtained the R-linear convergence for the primal sequence and Q-linear
convergence for the dual sequence of the ALM without assuming the strict
complementarity condition. We should also mention that a modified version of
the ALM, called the safeguarded ALM in which the $y^{k}$ in (1.4) is replaced
with a certain vector $w^{k}$ chosen from a bounded set, was studied in [1, 4,
19], where it was shown that this modification has an interesting global
convergence. The main motivation for this modification comes from the fact
that the dual sequence, constructed by the ALM, may be unbounded in general.

In our recent work [12], we extended the local convergence analysis of the ALM
in [9] for a class of composite optimization problems that the modeling
function therein, the function $g$ in (1.1), was assumed to be convex
piecewise linear-quadratic (CPLQ). In the present paper, our primary goal is
twofold. First, we are going to demonstrate that a similar result can be
obtained for composite optimization problem in (1.1) with the modeling
function $g$ belonging to a large class of functions, called ${\cal
C}^{2}$-decomposable; see (3.6). Second, we provide two major conditions under
which the local convergence of the ALM for (1.1) can be achieved. In doing so,
we introduce two new concepts, the semi-strict graphical derivative and semi-
strict second subderivative, and calculate them for some important classes of
functions. We also introduce a new concept, called semi-stability of second
subderivatives, and demonstrate that it holds for various important classes of
functions in optimization. This property is then utilized to ensure a uniform
version of the quadratic growth condition for the augmented Lagrangian
function in (1.2), which is a major tool in our approach to analyze the
convergence of the ALM.

The outline of the paper is as follows. We begin in Section 2 by recalling an
iterative framework for our inexact ALM and reviewing our notation. The goal
of Section 3 is to provide a general property under which we can ensure the
metric subregualrity of the Karush-Kuhn-Tucker (KKT) system associated with
(1.1). In Section 4, we introduce the concept of semi-stability of second
subderivatives and use it to justify the quadratic growth condition for the
augmented Lagrangian function. Section 5 is devoted to establishing the
Q-linear convergence of the primal-dual sequence generated by the proposed
inexact ALM. Finally, in Section 6, we present two independent results that
are important for our developments in this paper.

##  2 Prelimenaries

###  2.1 Notation

In what follows, suppose that ${\bf X}$ and ${\bf Y}$ are finite dimensional
Hilbert spaces. We denote by $\mathbb{B}$ the closed unit ball in the space in
question and by $\mathbb{B}_{r}(x):=x+r\mathbb{B}$ the closed ball centered at
$x$ with radius $r>0$. In the product space ${\bf X}\times{\bf Y}$, we use the
norm $\|(w,u)\|=\sqrt{\|w\|^{2}+\|u\|^{2}}$ for any $(w,u)\in{\bf X}\times{\bf
Y}$. Given a nonempty set $C\subset{\bf X}$, the symbols ${\rm int}\,C$, ${\rm
ri}\,C$, $C^{*}$, and ${\rm par}\,C$ signify its interior, relative interior,
polar cone, and the linear subspace parallel to the affine hull of $C$,
respectively. For any set $C$ in ${\bf X}$, its indicator function is defined
by $\delta_{C}(x)=0$ for $x\in C$ and $\delta_{C}(x)=\infty$ otherwise. We
denote by $P_{C}$ the projection mapping onto $C$ and by ${\rm dist}(x,C)$ the
distance between $x\in{\bf X}$ and a set $C$. For a vector $w\in{\bf X}$, the
subspace $\\{tw|\,t\in{\bf R}\\}$ is denoted by $[w]$. The set of nonnegative
number is denoted by ${\bf R}_{+}$.

Let $\\{C^{t}\\}_{t>0}$ be a parameterized family of sets in ${\bf X}$. Its
outer limit is defined by

$\limsup_{t\searrow 0}C^{t}=\big{\\{}x\in{\bf X}|\;\exists\;t_{k}\searrow
0\;\exists\;\;x^{t_{k}}\to x\;\;\mbox{with}\;\;x^{t_{k}}\in
C^{t_{k}}\big{\\}}.$

Given a nonempty set $\Omega\subset{\bf X}$ with ${\bar{x}}\in\Omega$, the
tangent cone to $\Omega$ at ${\bar{x}}$, denoted $T_{\Omega}({\bar{x}})$, is
defined by $T_{\Omega}({\bar{x}})=\limsup_{t\searrow
0}\frac{\Omega-{\bar{x}}}{t}.$ The regular/Fréchet normal cone
${\widehat{N}}_{\Omega}({\bar{x}})$ to $\Omega$ at ${\bar{x}}$ is defined by
${\widehat{N}}_{\Omega}({\bar{x}})=T_{\Omega}({\bar{x}})^{*}$. For
$x\notin\Omega$, we set ${\widehat{N}}_{\Omega}(x)=\emptyset$. The
limiting/Mordukhovich normal cone $N_{\Omega}({\bar{x}})$ to $\Omega$ at
${\bar{x}}$ is the set of all vectors $\bar{v}\in{\bf X}$ for which there
exist sequences $\\{x^{k}{\\}_{k\in{\rm I\\!N}}}$ and $\\{v^{k}{\\}_{k\in{\rm
I\\!N}}}$ with $v^{k}\in{\widehat{N}}_{\Omega}({x^{k}})$ such that
$(x^{k},v^{k})\to({\bar{x}},\bar{v})$. When $\Omega$ is convex, both normal
cones boil down to that of convex analysis. Given a function $f:{\bf
X}\to\overline{{\bf R}}$ and a point ${\bar{x}}\in{\bf X}$ with $f({\bar{x}})$
finite, the subderivative function ${\rm d}f({\bar{x}})\colon{\bf
X}\to\overline{{\bf R}}$ is defined by

${\rm d}f({\bar{x}})(w)=\liminf_{\begin{subarray}{c}t\searrow 0\\\
w^{\prime}\to
w\end{subarray}}\frac{f({\bar{x}}+tw^{\prime})-f({\bar{x}})}{t}.$

A vector $v\in{\bf X}$ is called a regular subgradient of $f$ at ${\bar{x}}$
if $(v,-1)\in\widehat{N}_{{\rm epi}\,f}({\bar{x}},f({\bar{x}}))$ with ${\rm
epi}\,f=\\{(x,\alpha)\in{\bf X}\times{\bf R}\,|\,f(x)\leq\alpha\\}$ being the
epigraph of $f$. The set of all regular subgradients of $f$ at ${\bar{x}}$ is
denoted by $\widehat{\partial}f({\bar{x}})$. Similarly, we can define
$\partial f({\bar{x}})$ using the limiting normal cone $N_{{\rm
epi}\,f}({\bar{x}},f({\bar{x}}))$. When $f$ is a convex function, both sets
reduce to the well-known subdifferential of convex functions. The critical
cone of $f$ at ${\bar{x}}$ for $\bar{v}$ with $\bar{v}\in\partial
f({\bar{x}})$ is defined by

${K_{f}}({\bar{x}},\bar{v})=\big{\\{}w\in{\bf
X}\,\big{|}\,\langle\bar{v},w\rangle={\rm d}f({\bar{x}})(w)\big{\\}}.$

When $f=\delta_{\Omega}$, where $\Omega$ is a nonempty subset of ${\bf X}$,
the critical cone of $\delta_{\Omega}$ at ${\bar{x}}$ for $\bar{v}$ is denoted
by $K_{\Omega}({\bar{x}},\bar{v})$. In this case, the above definition of the
critical cone of a function boils down to the well-known concept of the
critical cone of a set (see [8, page 109]), namely
$K_{\Omega}({\bar{x}},\bar{v})=T_{\Omega}({\bar{x}})\cap[\bar{v}]^{\perp}$.
The second subderivative of $f$ at ${\bar{x}}$ for $\bar{v}\in\partial
f({\bar{x}})$, denoted ${\rm d}^{2}f(\bar{x},\bar{v})$, is an extended-real-
valued function defined by

${\rm d}^{2}f(\bar{x},\bar{v})(w)=\liminf_{\begin{subarray}{c}t\searrow 0\\\
w^{\prime}\to
w\end{subarray}}\Delta_{t}^{2}f({\bar{x}},\bar{v})(w^{\prime}),\;\;w\in{\bf
X},$

where $\Delta_{t}^{2}f({\bar{x}},\bar{v})$ is the parametric family of second-
order difference quotients of $f$ at ${\bar{x}}$ for $\bar{v}$ and is defined
for any $w\in{\bf X}$ and $t>0$ by

$\Delta_{t}^{2}f(\bar{x},\bar{v})(w)=\frac{f({\bar{x}}+tw)-f({\bar{x}})-t\langle\bar{v},\,w\rangle}{\frac{1}{2}t^{2}}.$
(2.1)

The function $f$ is called twice epi-differentiable at ${\bar{x}}$ for
$\bar{v}$ if for any $w\in{\bf X}$ and any $t_{k}\searrow 0$, there exists
$w^{k}\to w$ such that $\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w^{k})\to{\rm
d}^{2}f(\bar{x},\bar{v})(w)$; see [30, Definition 13.6(b)]. For a set-valued
mapping $F:{\bf X}\rightrightarrows{\bf Y}$, its graph and domain are defined,
respectively, by ${\rm gph}\,F=\big{\\{}(x,y)\in{\bf X}\times{\bf
Y}\,\big{|}\,y\in F(x)\big{\\}}$ and ${\rm dom}\,F=\big{\\{}x\in{\bf
X}\,\big{|}\,F(x)\neq\emptyset\big{\\}}.$ We say that $F$ is calm at $x$ for
$y\in F(x)$ if there are neighborhoods $U$ of $x$ and $V$ of $y$ and a
positive constant $\kappa$ for which we have

$F(x^{\prime})\cap V\subset
F(x)+\kappa\,\|x-x^{\prime}\|\mathbb{B}\quad\mbox{for all}\;\;x^{\prime}\in
U.$

The mapping $F$ is called metrically subregular at $x$ for $y\in F(x)$ if
there are a neighborhood $U$ of $x$ and a positive constant $\ell$ such that
${\rm dist}(x^{\prime},F^{-1}(y))\leq\ell\,{\rm dist}(y,F(x^{\prime}))$ for
any $x^{\prime}\in U$.

###  2.2 An Iterative Framework for ALM

As shown later in this section, the primal-dual sequence
$\\{({x^{k}},y^{k}){\\}_{k\in{\rm I\\!N}}}$, generated by the ALM considered
in this paper, are solutions to a particular perturbation of the KKT system
associated with the composite optimization problem in (1.1), which is given by

$0\in\nabla_{x}L(x,y)+N_{\Theta}(x),\;\;y\in\partial g(\Phi(x)),$ (2.2)

where $L(x,y)=\varphi(x)+\langle y,\Phi(x)\rangle$ with $(x,y)\in{\bf
X}\times{\bf Y}$ is the Lagrangian of (1.1) and where the functions $g$,
$\Phi$, and the set $\Theta$ are taken from (1.1). It is easy to see that
(2.2) can be written as the generalized equation

$\begin{bmatrix}0\\\ 0\end{bmatrix}\in\begin{bmatrix}\nabla_{x}L(x,y)\\\
-\Phi(x)\end{bmatrix}+\begin{bmatrix}N_{\Theta}(x)\\\ (\partial
g)^{-1}(y)\end{bmatrix}.$ (2.3)

To elaborate more on the kind of perturbation we should consider for this
generalized equation, we briefly recall an abstract iterative framework,
suggested by Fischer in [10], for solving generalized equations with
nonisolated solutions. Given the mappings $\Psi:{\bf H}\to{\bf H}^{\prime}$
and $G:{\bf H}\rightrightarrows{\bf H}^{\prime}$, where ${\bf H}$ and ${\bf
H}^{\prime}$ are finite dimensional Hilbert spaces, consider the generalized
equation formulated by

$0\in\Psi(u)+G(u).$ (2.4)

Define the solution mapping ${\Upsilon}:{\bf H}^{\prime}\rightrightarrows{\bf
H}$ to the canonical perturbation of (2.4) by

${\Upsilon}(v)=\big{\\{}u\in{\bf H}|\,v\in\Psi(u)+G(u)\big{\\}},\;\;v\in{\bf
H}^{\prime}.$ (2.5)

Given a set of parameters $\bf{P}$, iterative algorithms for solving (2.4)
often generate a sequence $\\{u^{k}{\\}_{k\in{\rm I\\!N}}}$ by iteratively
solving subproblems of the form

$0\in{\cal A}(u,u^{k},p_{k})+G(u),$ (2.6)

in which the single-valued part in (2.4) is replaced with a set-valued mapping
${\cal A}:{\bf H}\times{\bf H}\times\bf{P}\rightrightarrows{\bf H}^{\prime}$,
which gives an approximation of $\Psi$ around the current iterate, while the
set-valued part is kept unchanged. In order to ensure the convergence and to
establish the rate of convergence of $\\{u^{k}{\\}_{k\in{\rm I\\!N}}}$, we
have to choose a solution to (2.6) satisfying certain properties. Namely,
given the current iterate $u^{k}$ and a parameter $p_{k}$, we choose the next
iterate $u^{k+1}$ sufficiently close to $u^{k}$ satisfying

$u^{k+1}\in\big{\\{}u\in{\bf H}\,\big{|}\,0\in{\cal
A}(u,u^{k},p_{k})+G(u)\;\textrm{ and }\;\|u-u^{k}\|\leq c\,{\rm
dist}(u^{k},{\Upsilon}(0))\big{\\}},$ (2.7)

where $c>0$ is arbitrary yet fixed, and ${\Upsilon}(0)$, taken from (2.5) with
$v=0$, is the set of solutions to (2.4). Below, we recall a result,
established in [15, Theorem 4.1] (see also [17, Theorem 7.13]), in which the
local convergence analysis of the sequence $\\{u^{k}{\\}_{k\in{\rm I\\!N}}}$
was obtained under rather mild assumptions. We should point out that
assumption (a) in the theorem below was expressed in [15, Theorem 4.1] in a
slightly stronger sense, namely the solution mapping ${\Upsilon}$ was assumed
to be upper Lipschitzian instead of being calm. It is not hard to see from its
proof, however, that calmness suffices for this result. The nonparametric
version of this result was later appeared in [17, Theorem 7.13] with upper
Lipschitzian replaced by calmness.

######  Theorem 2.1.

Let $\bar{u}\in{\Upsilon}(0)$, where ${\Upsilon}$ is the solution mapping from
(2.5). Assume that ${\Upsilon}(0)$ is locally closed around $\bar{u}$ and that
the following properties hold for some positive constant $c$:

  1. (a)

(calmness of solution mapping) the solution mapping ${\Upsilon}$ is calm at
$\bar{u}$ for $0\in{\bf H}^{\prime}$ with constant $\ell_{1}>0$;

  2. (b)

(solvability of subproblems) there exists a positive constant
$\varepsilon_{1}$ such that for any
$\tilde{u}\in\mathbb{B}_{\varepsilon_{1}}(\bar{u})$ and any $p\in\bf{P}$ the
localized solution set

$\big{\\{}u\in{\bf X}\,\big{|}\,0\in{\cal A}(u,\tilde{u},p)+G(u)\;\textrm{ and
}\;\|u-\tilde{u}\|\leq c\,{\rm dist}(\tilde{u},{\Upsilon}(0))\big{\\}}$

is nonempty;

  3. (c)

(precision of approximation) there exist a positive constant $\varepsilon_{2}$
and a function $\omega:{\bf H}\times{\bf H}\times\bf{P}:\to{\bf R}_{+}$ such
that

$\sup\big{\\{}\omega(u,\tilde{u},p)\,\big{|}\,\tilde{u}\in\mathbb{B}_{\varepsilon_{2}}(\bar{u}),\,\|u-\tilde{u}\|\leq
c\,{\rm dist}(\tilde{u},{\Upsilon}(0)),\,p\in{\bf{P}}\big{\\}}<1/\ell_{1},$

where constant $\ell_{1}>0$ is taken from (a), and the estimate

$\sup\big{\\{}\|w\|\,\big{|}\,w\in\Psi(u)-{\cal
A}(u,\tilde{u},p)\big{\\}}\leq\omega(u,\tilde{u},p)\,{\rm
dist}(\tilde{u},{\Upsilon}(0))$

holds for all $\tilde{u}\in\mathbb{B}_{\varepsilon_{2}}(\bar{u})$, all
$u\in{\bf H}$ with $\|u-\tilde{u}\|\leq c\,{\rm
dist}(\tilde{u},{\Upsilon}(0))$, and all $p\in\bf{P}$.

Then there exists $\varepsilon_{0}>0$ such that for any starting point $u^{0}$
chosen from $\mathbb{B}_{\varepsilon_{0}}(\bar{u})$ and any sequence
$\\{p_{k}\\}_{k\in{\rm I\\!N}}\subset\bf{P}$, the iterative scheme in (2.7)
generates a sequence $\\{u^{k}\\}_{k\in{\rm I\\!N}}$ converging to some
$\hat{u}\in{\Upsilon}(0)$. The rates of convergence of $\\{u^{k}{\\}_{k\in{\rm
I\\!N}}}$ to $\hat{u}$ and of $\\{{\rm
dist}(u^{k},{\Upsilon}(0)){\\}_{k\in{\rm I\\!N}}}$ to $0$ are Q-linear, and
they are Q-superlinear provided that $\omega(u^{k+1},u^{k},p_{k})\to 0$ as
$k\to\infty$. Moreover, for any $\varepsilon>0$, we have
$\|\hat{u}-\bar{u}\|<\varepsilon$ if $u^{0}$ is chosen sufficiently close to
$\bar{u}$.

Our main objective in this paper is to show that if a second-order sufficient
condition for optimality (see (3.18)) holds for the composite optimization
problem in (1.1) and a certain calmness of the multiplier mapping associated
with this problem (see (3.20)) is satisfied, then all assumptions (a)-(c) in
Theorem 2.1 can be verified for many important classes of constrained and
composite optimization problems.

Our final goal in this section is to show that the primal-dual sequence
$\\{({x^{k}},y^{k}){\\}_{k\in{\rm I\\!N}}}$, generated by the inexact ALM in
this paper, can be fit into the iterative pattern described above. To this
end, recall first that the proximal mapping of a convex function $g:{\bf
Y}\to\overline{{\bf R}}$ is defined by

${\rm{prox}}_{rg}(y)=\underset{z\in{\bf
Y}}{\operatorname*{arg\,min}}\big{\\{}g(z)+\hbox{${1\over
2r}$}\|y-z\|^{2}\big{\\}},\quad y\in{\bf Y},$

where $r$ is a positive constant. In what follows, when $r=1$, the proximal
mapping of $g$ will be denoted by ${\rm prox}_{g}$. It follows from [30,
Proposition 12.19] and [30, Theorem 2.26], respectively, that for any
$y\in{\bf Y}$ we always have

${\rm{prox}}_{rg}(y)=\big{(}I+r\partial
g\big{)}^{-1}(y)\quad\mbox{and}\quad\nabla e_{r}g(y)=\big{(}rI+(\partial
g)^{-1}\big{)}^{-1}(y),$ (2.8)

where $I$ stands for the identity mapping from ${\bf Y}$ onto ${\bf Y}$. Using
these relationships, one can equivalently reformulate the dual update
$y^{k+1}$ in (1.3) as

$y^{k+1}\in\partial
g\big{(}\Phi({x^{k+1}})-\rho_{k}^{-1}(y^{k+1}-y^{k})\big{)}\quad\mbox{or}\quad
y^{k+1}=\nabla(e_{1/{\rho_{k}}}g)\big{(}\Phi({x^{k+1}})+\rho_{k}^{-1}{y^{k}}\big{)}.$
(2.9)

To express the KKT system in (2.2) in the form of the generalized equation in
(2.4), we define the mappings $\Psi:{\bf X}\times{\bf Y}\to{\bf X}\times{\bf
Y}$ and $G:{\bf X}\times{\bf Y}\rightrightarrows{\bf X}\times{\bf Y}$ by

$\Psi(x,y)=\begin{bmatrix}\nabla_{x}L(x,y)\\\
-\Phi(x)\end{bmatrix}\quad\textrm{ and }\quad
G(x,y)=\begin{bmatrix}N_{\Theta}(x)\\\ (\partial g)^{-1}(y)\end{bmatrix},$
(2.10)

which clearly demonstrates that (2.2) can be covered by (2.4). Moreover, the
inexact primal update ${x^{k+1}}$, satisfying (1.5), can be equivalently
described via (2.9) by

$\displaystyle 0$
$\displaystyle\in\nabla_{x}{\mathscr{L}}({x^{k+1}},y^{k},{\rho_{k}})+{\epsilon_{k}}\mathbb{B}+N_{\Theta}({x^{k+1}})$
$\displaystyle=\nabla\varphi({x^{k+1}})+\nabla\Phi({x^{k+1}})^{*}\nabla(e_{1/{\rho_{k}}}g)\big{(}\Phi({x^{k+1}})+\rho_{k}^{-1}{y^{k}}\big{)}+{\epsilon_{k}}\mathbb{B}+N_{\Theta}({x^{k+1}})$
$\displaystyle=\nabla_{x}L({x^{k+1}},y^{k+1})+{\epsilon_{k}}\mathbb{B}+N_{\Theta}({x^{k+1}}).$

In order to show that the primal-dual iterate $({x^{k+1}},y^{k+1})$ satisfies
(2.6), we define the mapping ${\cal A}:{\bf X}\times{\bf Y}\times{\bf
X}\times{\bf Y}\times{\bf R}_{+}\times(0,\infty)\rightrightarrows{\bf
X}\times{\bf Y}$ by

${\cal
A}(x,y,\tilde{x},\tilde{y},\epsilon,\rho):=\begin{bmatrix}\nabla_{x}L(x,y)+\epsilon\mathbb{B}\\\
-\Phi(x)+\rho^{-1}(y-\tilde{y})\end{bmatrix}$ (2.11)

for a given quadruple $(\tilde{x},\tilde{y},\epsilon,\rho)\in{\bf X}\times{\bf
Y}\times{\bf R}_{+}\times(0,\infty)$. Combining these with the first inclusion
in (2.9) tells us that the primal-dual iterate $({x^{k+1}},y^{k+1})$ is a
solution to the subproblem

$(0,0)\in{\cal A}(x,y,{x^{k}},y^{k},\epsilon_{k},{\rho_{k}})+G(x,y).$

We close this section by recording some properties of the augmented Lagrangian
function in (1.2), which directly result from (2.8). Note that for any
$(x,\rho)\in{\bf X}\times(0,\infty)$, the mapping
$y\mapsto{\mathscr{L}}(x,y,\rho)$ is ${\cal C}^{1}$ and its gradient can be
calculated via (2.8) as

$\nabla_{y}{\mathscr{L}}(x,y,\rho)=\rho^{-1}\big{(}\nabla(e_{1/{\rho}}g)\big{(}\Phi(x)+\rho^{-1}{y}\big{)}-y\big{)}=\Phi(x)-{\rm{prox}}_{\rho^{-1}{g}}\big{(}\Phi(x)+\rho^{-1}y\big{)}.$
(2.12)

######  Proposition 2.2.

Let $({\bar{x}},\bar{y})$ be a solution to the KKT system in (2.2). Then for
any $\rho>0$, the following properties are satisfied.

  1. (a)

${\mathscr{L}}({\bar{x}},\bar{y},\rho)=\psi({\bar{x}})=\varphi({\bar{x}})+g\big{(}\Phi({\bar{x}})\big{)}$.

  2. (b)

$\nabla_{x}{\mathscr{L}}({\bar{x}},\bar{y},\rho)=\nabla_{x}L({\bar{x}},\bar{y})$
and $\nabla_{y}{\mathscr{L}}({\bar{x}},\bar{y},\rho)=0$.

##  3 Metric Subregularity of KKT Systems

As shown in Theorem 2.1, the calmness of the solution mapping in (2.5) is
required for local convergence analysis of the ALM for the composite
optimization problem (1.1). In this section, we aim to provide a sufficient
condition for an error bound estimate for the generalized equation in (2.3),
which will be shown in Proposition 5.2 that is equivalent to the
aforementioned calmness of (2.5). To achieve our goal, recall that the
graphical derivative of a set-valued mapping $F:{\bf X}\rightrightarrows{\bf
Y}$ at ${\bar{x}}$ for $\bar{y}\in F({\bar{x}})$, denoted by
$DF({\bar{x}},\bar{y})$, is a set-valued mapping from ${\bf X}$ into ${\bf
Y}$, defined by

${\rm gph}\,DF({\bar{x}},\bar{y})=T_{{\rm gph}\,F}({\bar{x}},\bar{y}).$

Employing the definition of the tangent cone, one can easily obtain an
equivalent sequential description of ${\rm gph}\,DF({\bar{x}},\bar{y})$. If,
in addition, for any $\eta\in DF({\bar{x}},\bar{y})(w)$ and any choice of
$t_{k}\searrow 0$, there exist sequences $w^{k}\to w$ and $\eta^{k}\to\eta$
with $\bar{y}+t_{k}\eta^{k}\in F({\bar{x}}+t_{k}w^{k})$, then $F$ is said to
be proto-differentiable at ${\bar{x}}$ for $\bar{y}$; see [30, page 331] for
more details. One of the main source of proto-differentiability in variational
analysis is subgradient mappings of various classes of functions including
CPLQ functions; see [21, 22, 30] for more examples.

######  Definition 3.1 (semi-strict graphical derivatives).

The semi-strict graphical derivative of $F:{\bf X}\rightrightarrows{\bf Y}$ at
${\bar{x}}$ for $\bar{y}\in F({\bar{x}})$, denoted by
$\widehat{D}F({\bar{x}},\bar{y})$, is a set-valued mapping from ${\bf X}$ to
${\bf Y}$ defined by

$\eta\in\widehat{D}F({\bar{x}},\bar{y})(w)\iff\begin{cases}\exists\;t_{k}\searrow
0,\,(x^{k},y^{k})\to({\bar{x}},\bar{y}),\;\widehat{y}^{k}\to\bar{y}\;\;\mbox{with}\;y^{k}\in
F(x^{k}),\;\widehat{y}^{k}\in F({\bar{x}})\\\ \mbox{such
that}\;(\frac{x^{k}-{\bar{x}}}{t_{k}},\frac{y^{k}-\widehat{y}^{k}}{t_{k}})\to(w,\eta).\end{cases}$

Using the definition of the outer limit of a family of sets, one can see that
the semi-strict graphical derivative of $F$ can be equivalently expressed as

$\widehat{D}F({\bar{x}},\bar{y})(w)=\limsup_{\begin{subarray}{c}t\searrow
0,\,w^{\prime}\to w\\\ y\to\bar{y},\;y\in
F({\bar{x}})\end{subarray}}\frac{F({\bar{x}}+tw^{\prime})-y}{t},\quad w\in{\bf
X}.$ (3.1)

By definition, we can immediately conclude that
$DF({\bar{x}},\bar{y})(w)\subset\widehat{D}F({\bar{x}},\bar{y})(w)$ for any
$w\in{\bf X}$. Our interest in the semi-strict graphical derivative resides in
Theorem 3.9 in which we show using this notion that the second-order
sufficient condition in (3.18) ensures an error bound for the KKT system of
(1.1). In order to do so, we should investigate how $DF({\bar{x}},\bar{y})$
and $\widehat{D}F({\bar{x}},\bar{y})$ relate to each other when $F$ is
subgradient mappings. We begin with a result that can be used as our guide to
pursue such a relationship. Recall first from [30, Definition 7.25] that an
lsc function $f:{\bf X}\to\overline{{\bf R}}$ is said to be subdifferentially
regular at ${\bar{x}}\in{\bf X}$ if $f({\bar{x}})$ is finite and
${\widehat{N}}_{{\rm epi}\,f}({\bar{x}},f({\bar{x}}))=N_{{\rm
epi}\,f}({\bar{x}},f({\bar{x}}))$.

######  Proposition 3.2.

Assume that $f:{\bf X}\to\overline{{\bf R}}$ and $({\bar{x}},\bar{v})\in{\rm
gph}\,\partial f$. If $\partial f$ is proto-differentiable at ${\bar{x}}$ for
$\bar{v}$, then we have

${\rm cl}\,\big{(}D(\partial f)({\bar{x}},\bar{v})(w)-T_{\partial
f({\bar{x}})}(\bar{v})\big{)}\subset\widehat{D}(\partial
f)({\bar{x}},\bar{v})(w)\quad\textrm{ for all }\quad w\in{\bf X}.$ (3.2)

In addition, if $f$ is subdifferentially regular at ${\bar{x}}$, then
$T_{\partial f({\bar{x}})}(\bar{v})$ in the left-hand side of (3.2) can be
replaced with $K_{f}({\bar{x}},\bar{v})^{*}$.

[Proof. ]Observe that the set $\widehat{D}(\partial f)({\bar{x}},\bar{y})(w)$
is closed due to (3.1) and the fact that the outer limit of a sequence of sets
is always closed (cf. [30, Prposition 4.4]). To prove (3.2), it suffices to
take $\eta\in D(\partial f)({\bar{x}},\bar{v})(w)$ and $\zeta\in T_{\partial
f({\bar{x}})}(\bar{v})$, and show that $\eta-\zeta\in\widehat{D}(\partial
f)({\bar{x}},\bar{v})(w)$. By $\zeta\in T_{\partial f({\bar{x}})}(\bar{v})$,
we find sequences $t_{k}\searrow 0$ and $\zeta^{k}\to\zeta$ with
$\bar{v}+t_{k}\zeta^{k}\in\partial f({\bar{x}})$. Moreover, proto-
differentiability of $f$ at ${\bar{x}}$ for $\bar{v}$ implies that there exist
sequences $w^{k}\to w$ and $\eta^{k}\to\eta$ with
$\bar{v}+t_{k}\eta^{k}\in\partial f({\bar{x}}+t_{k}w^{k})$. Putting all of
these together, we have
$(\bar{v}+t_{k}\zeta^{k})+t_{k}(\eta^{k}-\zeta^{k})\in\partial
f({\bar{x}}+t_{k}w^{k})$, which leads us to $\eta-\zeta\in\widehat{D}(\partial
f)({\bar{x}},\bar{v})(w)$ and hence proves (3.2).

Assume now that $f$ is subdifferentially regular at ${\bar{x}}$. According to
[30, Theorem 8.30], we know that $\partial f({\bar{x}})$ is closed and convex
and that

$K_{f}({\bar{x}},\bar{v})=N_{\partial f({\bar{x}})}(\bar{v}),$ (3.3)

which clearly justifies the final claim.

We next examine whether the opposite inclusion in (3.2) holds for important
classes of the modeling function $g$ in the composite optimization problem
(1.1). Before moving any further, let us show that if $f:{\bf
X}\to\overline{{\bf R}}$ is convex and $({\bar{x}},\bar{v})\in{\rm
gph}\,\partial f$, then we always have

${\rm dom}\,\widehat{D}(\partial f)({\bar{x}},\bar{v})\subset
K_{f}({\bar{x}},\bar{v}).$ (3.4)

Indeed, assume that for $w\in{\bf X}$ there exists
$\eta\in\widehat{D}(\partial f)({\bar{x}},\bar{v})(w)$. By definition, we can
select sequences $t_{k}\searrow 0$, $w^{k}\to w$, $v^{k}\in\partial
f({\bar{x}}+t_{k}w^{k})$, and $\widehat{v}^{k}\to\bar{v}$ with
$\widehat{v}^{k}\in\partial f({\bar{x}})$ such that
$(v^{k}-\widehat{v}^{k})/t_{k}\to\eta$. In particular, we have
$v^{k}\to\bar{v}$ and

$\frac{f({\bar{x}}+t_{k}w^{k})-f({\bar{x}})}{t_{k}}\leq\langle
v^{k},w^{k}\rangle$

for all $k$. Passing to the limit as $k\to\infty$ gives us ${\rm
d}f({\bar{x}})(w)\leq\langle\bar{v},w\rangle$ that actually holds as equality
due to $\bar{v}\in\partial f({\bar{x}})$ and [30, Exercise 8.4]. Thus, $w\in
K_{f}({\bar{x}},\bar{v})$, which proves (3.4).

######  Example 3.3.

Assume that $f:{\bf X}\to\overline{{\bf R}}$ with ${\bf X}={\bf R}^{n}$ is a
CPLQ function. Recall that $f$ is called piecewise linear-quadratic if ${\rm
dom}\,f=\cup_{i=1}^{s}C_{i}$ with $s\in{\rm I\\!N}$ and $C_{i}$ being
polyhedral convex sets for $i=1,\ldots,s$, and if $f$ has a representation of
the form

$f(x)=\hbox{${1\over 2}$}\langle A_{i}x,x\rangle+\langle
a_{i},x\rangle+\alpha_{i}\quad\mbox{for all}\quad x\in C_{i},$

where $A_{i}$ is an $n\times n$ symmetric matrix, $a_{i}\in{\bf R}^{n}$, and
$\alpha_{i}\in{\bf R}$ for $i=1,\ldots,s$. Pick ${\bar{x}}\in{\rm dom}\,f$ and
$\bar{v}\in\partial f({\bar{x}})$. Since $f$ is convex, it is
subdifferentially regular at ${\bar{x}}$, and $\partial f$ is proto-
differentiable at ${\bar{x}}$ for $\bar{v}$ according to [30, Proposition
13.9] and [30, Theorem 13.40]. Proposition 3.2 tells us that the inclusion in
(3.2) holds. If $w\notin{\rm dom}\,\widehat{D}(\partial
f)({\bar{x}},\bar{v})$, then the opposite inclusion is trivial. We now verify
the opposite inclusion for any $w\in{\rm dom}\,\widehat{D}(\partial
f)({\bar{x}},\bar{v})$. It follows from (3.4) that $w\in
K_{f}({\bar{x}},\bar{v})$. Take $\eta\in\widehat{D}(\partial
f)({\bar{x}},\bar{v})(w)$ and find, by definition, sequences $t_{k}\searrow
0$, $w^{k}\to w$, $v^{k}\in\partial f({\bar{x}}+t_{k}w^{k})$, and
$\widehat{v}^{k}\to\bar{v}$ with $\widehat{v}^{k}\in\partial f({\bar{x}})$
such that $(v^{k}-\widehat{v}^{k})/t_{k}\to\eta$. We then have

$(t_{k}w^{k},v^{k}-\bar{v})=({\bar{x}}+t_{k}w^{k},v^{k})-({\bar{x}},\bar{v})\in\big{(}{\rm
gph}\,\partial f\big{)}-({\bar{x}},\bar{v}).$

It follows from the reduction lemma for CPLQ functions from [31, Theorem 2.3]
that there exists a neighborhood ${\cal O}$ of $(0,0)\in{\bf R}^{n}\times{\bf
R}^{n}$ for which we have

$\big{(}\big{(}{\rm gph}\,\partial
f\big{)}-({\bar{x}},\bar{v})\big{)}\cap{\cal O}=\big{(}{\rm gph}\,D(\partial
f)({\bar{x}},\bar{v})\big{)}\cap{\cal O}.$

We can assume for any $k$ sufficiently large that
$(t_{k}w^{k},v^{k}-\bar{v})\in{\cal O}$ and therefore obtain
$(w^{k},(v^{k}-\bar{v})/t_{k})\in{\rm gph}\,D(\partial g)({\bar{x}},\bar{v})$.
By [31, Proposition 2.4(b)] and $w\in K_{f}({\bar{x}},\bar{v})$, there exists
a constant $\tau\geq 0$ such that for any $k$ sufficiently large we have

$\frac{v^{k}-\bar{v}}{t_{k}}\in D(\partial f)({\bar{x}},\bar{v})(w^{k})\subset
D(\partial f)({\bar{x}},\bar{v})(w)+\tau\|w^{k}-w\|\mathbb{B}.$ (3.5)

Note also that $\widehat{v}^{k}-\bar{v}\in\partial f({\bar{x}})-\bar{v}\subset
T_{\partial f({\bar{x}})}(\bar{v})$. This, coupled with (3.3), which holds for
the CPLQ function $f$, brings us to $(\widehat{v}^{k}-\bar{v})/t_{k}\in
K_{f}({\bar{x}},\bar{v})^{*}$ for all $k$. Using this and (3.5), we find
$\eta^{k}\in D(\partial f)({\bar{x}},\bar{v})(w)$ and $\zeta^{k}\in\mathbb{B}$
such that

$\frac{v^{k}-\widehat{v}^{k}}{t_{k}}-\tau\|w^{k}-w\|\zeta^{k}=\eta^{k}-\frac{\widehat{v}^{k}-\bar{v}}{t_{k}}\in
D(\partial f)({\bar{x}},\bar{v})(w)-K_{f}({\bar{x}},\bar{v})^{*}$

for any $k$ sufficiently large. Passing to the limit as $k\to\infty$ and using
the boundedness of $\zeta^{k}$, we arrive at the inclusion

$\eta\in{\rm cl}\,\big{(}D(\partial
f)({\bar{x}},\bar{v})(w)-K_{f}({\bar{x}},\bar{v})^{*}\big{)},$

which in turn demonstrates that the inclusion in (3.2) becomes equality for
any $w\in{\bf R}^{n}$ for CPLQ functions. Note that in this framework, we can
drop the closure in (3.2) to obtain

$\widehat{D}(\partial f)({\bar{x}},\bar{v})(w)=D(\partial
f)({\bar{x}},\bar{v})(w)-K_{f}({\bar{x}},\bar{v})^{*}\quad\mbox{for
any}\;\;w\in{\bf X},$

since the right-hand side is the sum of two polyhedral convex sets, which is
known to be a polyhedral convex set, and hence is always closed.

Our next goal is to show that we should expect a similar result as the one in
Example 3.3 outside the polyhedral framework. We begin with proving the
following result, which is of its own interest. Recall from [32] that a
function $g:{\bf Y}\to\overline{{\bf R}}$ is called ${\cal
C}^{2}$-decomposable at $\bar{u}\in{\bf Y}$ if $g(\bar{u})$ is finite and $g$
enjoys the composite representation

$g(u)=g(\bar{u})+\vartheta(\Xi(u))\quad\textrm{ for }\quad u\in{\cal O},$
(3.6)

where ${\cal O}\subset{\bf Y}$ is an open neighborhood of $\bar{u}$,
$\vartheta:{\bf Z}\to\overline{{\bf R}}$ is proper, lsc, and sublinear, and
$\Xi:{\cal O}\to{\bf Z}$ is ${\cal C}^{2}$-smooth with
$\bar{z}:=\Xi(\bar{u})=0$, and where ${\bf Z}$ is a finite dimensional Hilbert
space. Note that by [30, Definition 3.18 and Exercise 3.19], we always have
$g(\bar{z})=0$, since $g$ is proper and sublinear. As shown in [32, Example
2.4], the class of ${\cal C}^{2}$-decomposable functions is a generalization
of ${\cal C}^{2}$-cone reducible sets in the sense of [5, Definition 3.135]
through which many important constrained optimization problems can be studied.
Recall that a closed convex set $C\subset{\bf Y}$ is ${\cal C}^{2}$-cone
reducible at $\bar{u}\in{\bf Y}$ to the closed convex cone $\Theta\subset{\bf
Z}$ if there exist a neighborhood ${\cal O}\subset{\bf Y}$ of $\bar{u}$ and a
${\cal C}^{2}$-smooth mapping $\Xi:{\bf Y}\to{\bf Z}$ such that

$C\cap{\cal O}=\big{\\{}u\in{\cal
O}\,\big{|}\,\Xi(u)\in\Theta\big{\\}},\quad\Xi(\bar{u})=0,\;\textrm{ and
}\quad\nabla\Xi(\bar{u}):{\bf Y}\to{\bf Z}\;\textrm{ is surjective}.$ (3.7)

Note that the surjectivity condition in (3.7) is not covered by (3.6) and has
its own counterpart, called the nondegeneracy condition; see (3.13). Besides
the indicator functions of ${\cal C}^{2}$-cone reducible sets, it was shown in
[32, Examples 2.1 and 2.3] that polyhedral functions and the sum of the
largest eigenvalues of a symmetric matrix are ${\cal C}^{2}$-decomposable. The
later was extended for singular values of a matrix in [20, Example 5.3.18].
The readers can find more examples of ${\cal C}^{2}$-decomposable functions in
[20, Section 5.3.3]. Note that CPLQ functions may not enjoy the composite
representation in (3.6) in general; see Remark 3.7.

Suppose that the proper function $g:{\bf Y}\to\overline{{\bf R}}$ is ${\cal
C}^{2}$-decomposable at $\bar{u}\in{\bf Y}$ with representation (3.6). Define
the (Lagrange) multiplier mapping $M_{\bar{u},g}:{\bf Y}\times{\bf
Y}\rightrightarrows{\bf Z}$ by

$M_{\bar{u},g}(y,w)=\big{\\{}\mu\in{\bf
Z}\,\big{|}\,\nabla\Xi(\bar{u})^{*}\mu=y,\,\mu\in\partial\vartheta(\Xi(\bar{u})+w)\big{\\}}.$
(3.8)

Given $\bar{y}\in\partial g(\bar{u})$, the set $M_{\bar{u},g}(\bar{y},0)$ is
called the set of Lagrange multipliers associated with $(\bar{u},\bar{y})$.
Below, we summerize some of the main properties of the composite
representation in (3.6), used often in our proofs in this paper.

######  Proposition 3.4.

Assume that $g:{\bf Y}\to\overline{{\bf R}}$ is ${\cal C}^{2}$-decomposable at
$\bar{u}\in{\bf Y}$ with representation (3.6) and that $\bar{y}\in\partial
g(\bar{u})$ and $\bar{\mu}\in M_{\bar{u},g}(\bar{y},0)$. Then the following
properties hold.

  1. (a)

If the basic constraint qualification (BCQ) condition

$N_{{\rm dom}\,\vartheta}(\Xi(\bar{u}))\cap{\rm
ker}\,\nabla\Xi(\bar{u})^{*}=\\{0\\}$ (3.9)

holds, then $g$ is subdifferentially regular at $\bar{u}$.

  2. (b)

For any $z\in{\rm dom}\,\vartheta$, it holds that
$\partial\vartheta(z)\subset\partial\vartheta(\Xi(\bar{u}))$.

  3. (c)

It always holds that
$K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})=N_{\partial\vartheta(\Xi(\bar{u}))}(\bar{\mu})$.
If, in addition, (3.9) is satisfied, then $K_{g}(\bar{u},\bar{y})=N_{\partial
g(\bar{u})}(\bar{y})$.

  4. (d)

If the dual condition

$D(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(0)\cap{\rm
ker}\,\nabla\Xi(\bar{u})^{*}=\\{0\\}$ (3.10)

holds, then
$K_{g}(\bar{u},\bar{y})^{*}=\nabla\Xi({\bar{x}})^{*}K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})^{*}$.

  5. (e)

If (3.9) is satisfied, the subgradient mapping $\partial g$ is calm at
$\bar{u}$ for $\bar{y}$.

[Proof. ]The conclusion in (a) is well-known; see [30, Exercise 10.25]. The
inclusion in (b) results from [30, Corollary 8.25]. Both claims in (c) result
from (a) and (3.3). To prove (d), the inclusion in (6.5) tells us that the
dual condition in (3.10) yields (3.9). Thus, it follows from the chain rule
for the subderivative in [30, Theorem 10.6] that

$\displaystyle K_{g}(\bar{u},\bar{y})$
$\displaystyle=\big{\\{}w\,\big{|}\,{\rm d}g(\bar{u})(w)={\rm
d}\vartheta(\Xi(\bar{u}))(\nabla\Xi(\bar{u})w)=\langle\bar{y},w\rangle=\langle\bar{\mu},\nabla\Xi({\bar{x}})w\rangle\big{\\}}$
$\displaystyle=\big{\\{}w\,\big{|}\,\nabla\Xi({\bar{x}})w\in
K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})\big{\\}}.$ (3.11)

Employing the chain rule for normal cones in [30, Exercise 10.26] allows us to
conclude that

$K_{g}(\bar{u},\bar{y})^{*}=N_{K_{g}(\bar{u},\bar{y})}(0)=\nabla\Xi(\bar{u})^{*}N_{K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})}(0)=\nabla\Xi(\bar{u})^{*}K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})^{*},$

which proves (d). The claim in (e) results from (b) and [29, Theorem 4.1].

As pointed out earlier, the equality in (3.2) plays a crucial role in our main
result of this section. Below, we establish a chain rule for this property.

######  Proposition 3.5.

Assume that $g:{\bf Y}\to\overline{{\bf R}}$ is ${\cal C}^{2}$-decomposable at
$\bar{u}\in{\bf Y}$ with representation (3.6) and that $\bar{y}\in\partial
g(\bar{u})$ and $\bar{\mu}\in M_{\bar{u},g}(\bar{y},0)$. If the outer function
$\vartheta$ in (3.6) enjoys the property

$\widehat{D}(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(\xi)={\rm
cl}\,\big{(}D(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(\xi)-K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})^{*}\big{)}\quad\textrm{
for all }\quad\xi\in K_{\vartheta}(\Xi(\bar{u}),\bar{\mu}),$ (3.12)

and the nondegeneracy condition

${\rm par}\,\\{\partial\vartheta(\Xi(\bar{u}))\\}\cap{\rm
ker}\,\nabla\Xi(\bar{u})^{*}=\\{0\\}$ (3.13)

holds, then $g$ satisfies the same property, meaning that

$\widehat{D}(\partial g)(\bar{u},\bar{y})(w)={\rm cl}\,\big{(}D(\partial
g)(\bar{u},\bar{y})(w)-K_{g}(\bar{u},\bar{y})^{*}\big{)}\quad\textrm{ for all
}\quad w\in{\bf Y}.$ (3.14)

[Proof. ]Pick $w\in{\rm dom}\,\widehat{D}(\partial g)(\bar{u},\bar{y})$ and
$\eta\in\widehat{D}(\partial g)(\bar{u},\bar{y})(w)$. By definition, we find
sequences $t_{k}\searrow 0$, $w^{k}\to w$, $y^{k}\in\partial
g(\bar{u}+t_{k}w^{k})$, and $\widehat{y}^{k}\to\bar{y}$ with
$\widehat{y}^{k}\in\partial g(\bar{u})$ such that
$(y^{k}-\widehat{y}^{k})/t_{k}\to\eta$. By the subdifferential chain rule from
[30, Example 10.8] available due to the assumed nondegeneracy condition, we
find $\mu^{k}\in\partial\vartheta(\Xi(\bar{u}+t_{k}w^{k}))$ and
$\widehat{\mu}^{k}\in\partial\vartheta(\Xi(\bar{u}))$ such that
$\nabla\Xi(\bar{u}+t_{k}w^{k})^{*}\mu^{k}=y^{k}$ and
$\nabla\Xi(\bar{u})^{*}\widehat{\mu}^{k}=\widehat{y}^{k}$, respectively. Thus,
we have $\mu^{k}\in
M_{\bar{u},g}(y^{k},t_{k}\nabla\Xi(\bar{u})w^{k}+o(t_{k}))$ and
$\widehat{\mu}^{k}\in M_{\bar{u},g}(\widehat{y}^{k},0)$. Note that it follows
from (6.4) and Proposition 3.4(c) that

$D(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(0)=K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})^{*}=T_{\partial\vartheta(\Xi(\bar{u}))}(\bar{\mu})\subset{\rm
par}\,\\{\partial\vartheta(\Xi(\bar{u}))\\},$ (3.15)

where the last inclusion results from the definition of the tangent cone.
Thus, we conclude from the assumed nondegeneracy condition that the dual
condition in (3.10) is satisfied. Appealing now to Theorem 6.1(d), we can
conclude that both sequences $\\{\mu^{k}{\\}_{k\in{\rm I\\!N}}}$ and
$\\{\widehat{\mu}^{k}{\\}_{k\in{\rm I\\!N}}}$ converge to $\bar{\mu}$ as
$k\to\infty$. By passing to a subsequence, we can assume without loss of
generality that the sequence
$\\{\nabla\Xi({\bar{x}})^{*}(\mu^{k}-\widehat{\mu}^{k})/t_{k}{\\}_{k\in{\rm
I\\!N}}}$ is convergent, since

$\displaystyle\frac{y^{k}-\widehat{y}^{k}}{t_{k}}$
$\displaystyle=\frac{\nabla\Xi(\bar{u}+t_{k}w^{k})^{*}\mu^{k}-\nabla\Xi(\bar{u})^{*}\widehat{\mu}^{k}}{t_{k}}$
$\displaystyle=\Big{(}\frac{\nabla\Xi(\bar{u}+t_{k}w^{k})-\Xi(\bar{u})}{t_{k}}\Big{)}^{*}\mu^{k}+\nabla\Xi(\bar{u})^{*}\frac{\mu^{k}-\widehat{\mu}^{k}}{t_{k}}.$
(3.16)

We claim now that the sequence
$\\{\|\mu^{k}-\widehat{\mu}^{k}\|/t_{k}{\\}_{k\in{\rm I\\!N}}}$ is bounded.
Otherwise, passing to a subsequence, if necessary, we can assume that
$\|\mu^{k}-\widehat{\mu}^{k}\|/t_{k}\to\infty$, which implies that
$\mu^{k}-\widehat{\mu}^{k}\neq 0$ for any $k$ sufficiently large. Again, we
can assume by passing to a subsequence, if necessary, that
$\\{(\mu^{k}-\widehat{\mu}^{k})/\|\mu^{k}-\widehat{\mu}^{k}\|{\\}_{k\in{\rm
I\\!N}}}$ converges to some $\xi\neq 0$. Thus, we get $\xi\in{\rm
ker}\,\nabla\Xi({\bar{x}})^{*}$, since

$\nabla\Xi({\bar{x}})^{*}\xi=\lim_{k\to\infty}\nabla\Xi({\bar{x}})^{*}\frac{\mu^{k}-\widehat{\mu}^{k}}{\|\mu^{k}-\widehat{\mu}^{k}\|}=\lim_{k\to\infty}\nabla\Xi({\bar{x}})^{*}\frac{\mu^{k}-\widehat{\mu}^{k}}{t_{k}}\cdot\frac{t_{k}}{\|\mu^{k}-\widehat{\mu}^{k}\|}=0.$

On the other hand, it follows from Proposition 3.4(b) that
$\mu^{k}\in\partial\vartheta(\Xi(\bar{u}+t_{k}w^{k}))\subset\partial\vartheta(\Xi(\bar{u}))$,
which in turn yields
$(\mu^{k}-\widehat{\mu}^{k})/\|\mu^{k}-\widehat{\mu}^{k}\|\in{\rm
par}\,\\{\partial\vartheta(\Xi(\bar{u}))\\}$. Thus, we arrive at $\xi\in{\rm
par}\,\\{\partial\vartheta(\Xi(\bar{u})\\}$, which leads us to $\xi=0$ due to
(3.13), a contradiction. This tells us that
$\\{(\mu^{k}-\widehat{\mu}^{k})/t_{k}{\\}_{k\in{\rm I\\!N}}}$ is convergent to
some $\zeta\in{\bf Z}$. Recall that
$\mu^{k}\in\partial\vartheta(\Xi(\bar{u}+t_{k}w^{k}))$ and
$\widehat{\mu}^{k}\in\partial\vartheta(\Xi(\bar{u}))$. Since
$\big{(}\Xi(\bar{u}+t_{k}w^{k})-\Xi(\bar{u})\big{)}/t_{k}\to\nabla\Xi(\bar{u})w$,
it follows from Definition 3.1 that
$\zeta\in\widehat{D}(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(\nabla\Xi(\bar{u})w)$.
Passing to the limit in (3.16) brings us to

$\eta-\nabla^{2}\langle\bar{\mu},\Xi\rangle(\bar{u})w=\nabla\Xi(\bar{u})^{*}\zeta\in\nabla\Xi(\bar{u})^{*}\widehat{D}(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(\nabla\Xi({\bar{x}})w),$

which in turn implies via (3.12), Theorem 6.2(b), and Proposition 3.4 that

$\displaystyle\eta$
$\displaystyle\in\nabla^{2}\langle\bar{\mu},\Xi\rangle(\bar{u})w+\nabla\Xi(\bar{u})^{*}{\rm
cl}\,\big{(}\widehat{D}(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(\nabla\Xi(\bar{u})w)-K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})^{*}\big{)}$
$\displaystyle={\rm
cl}\,\big{(}\nabla^{2}\langle\bar{\mu},\Xi\rangle(\bar{u})w+\nabla\Xi(\bar{u})^{*}\widehat{D}(\partial\vartheta)(\Xi(\bar{u}),\bar{\mu})(\nabla\Xi(\bar{u})w)-\nabla\Xi(\bar{u})^{*}K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})^{*}\big{)}$
$\displaystyle={\rm cl}\,\big{(}D(\partial
g)(\bar{u},\bar{y})(w)-K_{g}(\bar{u},\bar{y})^{*}\big{)}.$

This proves the inclusion ‘$\subset$’ in (3.14). To justify the opposite
inclusion, observe from (6.5) and (3.13) that the BCQ in (3.9) is satisfied.
By Proposition 3.4, $g$ is subdifferentially regular at $\bar{u}$. Moreover,
it follows from Theorem 6.2(b) that $\partial g$ is proto-differentiable at
$\bar{u}$ for $\bar{y}$. Thus, Proposition 3.2, together with (3.3), proves
the inclusion ‘$\supset$’ in (3.14) and hence completes the proof.

Using the established chain rule in the proposition above, we are going next
to show that the inclusion in (3.2) becomes equality for the second-order
cone.

######  Example 3.6.

Let ${\cal Q}$ stand for the second-order cone in ${\bf R}^{n}$ described by

${\cal Q}:=\big{\\{}u=(u_{0},u_{r})\in{\bf R}\times{\bf
R}^{n-1}\,\big{|}\,\|u_{r}\|\leq u_{0}\big{\\}}.$

Our goal is to show that the inclusion in (3.2) becomes equality when
$f=\delta_{\cal Q}$. To achieve this goal, we should consider there different
cases for a point $\bar{u}\in{\cal Q}$. If $\bar{u}\in{\rm int}\,{\cal Q}$, it
is easy to see that ${\cal Q}$ can be locally represented by the set
$\\{u\in{\cal O}\,|\;\Xi(u)\in\Theta\\}$, where $\Xi:{\bf R}^{n}\to\\{0\\}$
and $\Theta=\\{0\\}$. If $\bar{u}\in{\rm bd}\,{\cal Q}\setminus\\{0\\}$, one
can see that ${\cal Q}$ can be locally represented by $\\{u\in{\cal
O}\,|\;\Xi(u)\in\Theta\\}$, where $\Xi:{\bf R}^{n}\to{\bf R}$ is defined by
$\Xi(u)=\|u_{r}\|-u_{0}$ for any $u=(u_{0},u_{r})\in{\bf R}\times{\bf
R}^{n-1}$ and $\Theta={\bf R}_{-}$. Thus, in both cases, ${\cal Q}$ is ${\cal
C}^{2}$-cone reducible to a polyhedral convex cone in the sense of (3.7) and
hence $\delta_{\cal Q}$ is ${\cal C}^{2}$-decomposable with the outer function
$\vartheta$ in the composite representation in (3.6) being either
$\delta_{\\{0\\}}$ or $\delta_{{\bf R}_{-}}$. Since these functions are CPLQ,
it follows from Proposition 3.5 and Example 3.3 that the inclusion in (3.2)
becomes equality for $f=\delta_{\cal Q}$ at any nonzero $\bar{u}\in{\cal Q}$
and $\bar{y}\in N_{\cal Q}(\bar{u})$.

The last case to consider is $\bar{u}=0$. Take $\bar{y}\in N_{\cal
Q}(\bar{u})$ and observe from [11, Corollary 3.4] that $N_{\cal Q}$ is proto-
differentiable at $\bar{u}$ for $\bar{y}$ and that $DN_{\cal
Q}(\bar{u},\bar{y})(w)=N_{K_{\cal Q}(\bar{u},\bar{y})}(w)$ for any $w\in{\bf
R}^{n}$ with $K_{\cal Q}(\bar{u},\bar{y})={\cal Q}\cap[\bar{y}]^{\perp}$. To
achieve our goal, we only need to justify the inclusion

$\widehat{D}N_{\cal Q}(\bar{u},\bar{y})(w)\subset{\rm cl}\,\big{(}DN_{\cal
Q}(\bar{u},\bar{y})(w)-K_{\cal Q}(\bar{u},\bar{y})^{*}\big{)}={\rm
cl}\,\big{(}N_{K_{\cal Q}(\bar{u},\bar{y})}(w)-K_{\cal
Q}(\bar{u},\bar{y})^{*}\big{)}\quad\mbox{for all}\;\;w\in{\bf R}^{n},$

since the opposite inclusion always holds according to Proposition 3.2. By
[30, Corolalary 11.25(b)], we can equivalently express the latter as

$\widehat{D}N_{\cal Q}(\bar{u},\bar{y})(w)\subset\big{(}T_{K_{\cal
Q}(\bar{u},\bar{y})}(w)\cap-K_{\cal Q}(\bar{u},\bar{y})\big{)}^{*}.$ (3.17)

To prove this inclusion, pick $w\in{\rm dom}\,\widehat{D}N_{\cal
Q}(\bar{u},\bar{y})$, $\eta\in\widehat{D}N_{\cal Q}(\bar{u},\bar{y})(w)$ and
conclude from (3.4) that $w\in K_{\cal Q}(\bar{u},\bar{y})$. To verify (3.17),
we must show that $\langle\eta,q\rangle\leq 0$ for any $q\in C(w)$, where
$C(w):=T_{K_{\cal Q}(\bar{u},\bar{y})}(w)\cap-K_{\cal Q}(\bar{u},\bar{y})$. If
$w=0$, we clearly have

$C(w)=K_{\cal Q}(\bar{u},\bar{y})\cap-K_{\cal Q}(\bar{u},\bar{y})=({\cal
Q}\cap[\bar{y}]^{\perp})\cap-({\cal Q}\cap[\bar{y}]^{\perp})=\\{0\\},$

which proves (3.17). If $w\neq 0$, it follows from $\eta\in\widehat{D}N_{\cal
Q}(\bar{u},\bar{y})(w)$ that there exist sequences $t_{k}\searrow 0$,
$w^{k}\to w$, $y^{k}\in N_{\cal Q}(w^{k})$, and $\widehat{y}^{k}\to\bar{y}$
with $\widehat{y}^{k}\in-{\cal Q}$ such that
$(y^{k}-\widehat{y}^{k})/t_{k}\to\eta$. We split our verification of (3.17)
into three cases depending on the position of $\bar{y}$ in ${\cal Q}$:

  * (i)

$\bar{y}\in-{\rm int}\,{\cal Q}$. In this case, we have $K_{\cal
Q}(\bar{u},\bar{y})=\\{0\\}$. Since $w\in K_{\cal Q}(\bar{u},\bar{y})$, we get
$w=0$, which is not possible.

  * (ii)

$\bar{y}\in-({\rm bd}\,{\cal Q})\setminus\\{0\\}$. In this case, since $0\neq
w\in K_{\cal Q}(\bar{u},\bar{y})$, it is not hard to see that $K_{\cal
Q}(\bar{u},\bar{y})=\\{tw|\;t\geq 0\\}$. This leads us to

$C(w)=T_{K_{\cal Q}(\bar{u},\bar{y})}(w)\cap-K_{\cal
Q}(\bar{u},\bar{y})=[w]\cap\\{tw|\;t\leq 0\\}=\\{tw|\;t\leq 0\\}.$

On the other hand, it follows from $y^{k}\in N_{\cal Q}(w^{k})$ and
$\widehat{y}^{k}\in-{\cal Q}$ that

$\langle\frac{y^{k}-\widehat{y}^{k}}{t_{k}},w^{k}\rangle=-\langle\frac{\widehat{y}^{k}}{t_{k}},w^{k}\rangle\geq
0,$

which in turn results in $\langle\eta,w\rangle\geq 0$. Pick now $q\in C(w)$.
So, $q=tw$ for some $t\leq 0$. Combining these shows $\langle\eta,q\rangle\leq
0$, which again proves (3.17).

  * (iii)

$\bar{y}=0$. In this case, we have $K_{\cal Q}(\bar{u},\bar{y})={\cal Q}$.
Recall that $w\in K_{\cal Q}(\bar{u},\bar{y})$. If $w\in{\rm int}\,{\cal Q}$,
it follows from $w^{k}\to w$ that $w^{k}\in{\rm int}\,{\cal Q}$ for any $k$
sufficiently large and therefore $y^{k}=0$ for any such $k$. Thus,
$-\widehat{y}^{k}/t_{k}\to\eta$, which, together with
$\widehat{y}^{k}\in-{\cal Q}$, yields $\eta\in{\cal Q}$. Note that for such
$w$, we have

$C(w)=T_{K_{\cal Q}(\bar{u},\bar{y})}(w)\cap-K_{\cal Q}(\bar{u},\bar{y})={\bf
R}^{n}\cap-{\cal Q}=-{\cal Q}.$

Thus, we obtain $\eta\in C(w)^{*}$, which again proves (3.17). If $w\in{\rm
bd}\,{\cal Q}$, we conclude that

$C(w)=T_{K_{\cal Q}(\bar{u},\bar{y})}(w)\cap-K_{\cal
Q}(\bar{u},\bar{y})=T_{\cal Q}(w)\cap-{\cal Q}=\\{tw|\;t\leq 0\\}.$

Using the same argument as case (ii) shows that $\eta\in C(w)^{*}$ and hence
proves (3.17).

Combining these cases shows that the inclusion in (3.2) holds as equality for
$f=\delta_{\cal Q}$ when $\bar{u}=0$.

######  Remark 3.7.

Note that CPLQ functions may not be ${\cal C}^{2}$-decomposable. To delineate
this, it is important to mention that most functions, enjoying the composite
representation in (3.6), automatically satisfy the nondegenracy condition in
(3.13); see [32, Examples 2.1 and 2.3]. Assume that a function $g:{\bf
Y}\to\overline{{\bf R}}$ is ${\cal C}^{2}$-decomposable at $\bar{u}$, that the
nondegenracy condition in (3.13) holds, and that $\bar{y}\in\partial
g(\bar{u})$. Employing now Theorem 6.2 and (6.2) tells us that the second
subderivaive of $g$ at $\bar{u}$ for $\bar{y}$ has a single quadratic piece,
namely $\langle\bar{\mu},\nabla^{2}\Xi(\bar{u})(w,w)\rangle$, whenever
$\nabla\Xi(\bar{u})w\in K_{\vartheta}(\Xi(\bar{u}),\bar{y})$. If $g$ were a
CPLQ, it would follow from (4.2) that ${\rm d}^{2}g(\bar{u},\bar{y})$ may have
several different quadratic pieces depending on how many polyhedral convex
sets $C_{i}$ exist in the representation of $g$; see the beginning of Example
3.3 for the definition of $C_{i}$. That contradicts our earlier observation
about ${\rm d}^{2}g(\bar{u},\bar{y})$ and demonstrates that CPLQ functions
cannot be ${\cal C}^{2}$-decomposable in general.

We are now going to establish an error bound for the KKT system in (2.2)
associated with the composite optimization problem (1.1). Such a result was
perviously established under the second-order sufficient condition (SOSC) for
different classes of constrained optimization problems in [23, Theorem 5.9].
For a solution $({\bar{x}},\bar{y})$ to the KKT system (2.2), the latter
result motivates us to consider the SOSC

$\begin{cases}\langle\nabla_{xx}^{2}L(\bar{x},\bar{y})w,w\rangle+{\rm
d}^{2}g(\Phi(\bar{x}),\bar{y})(\nabla\Phi({\bar{x}})w)>0\quad\mbox{ for all
}\;w\in{\mathscr{D}}\setminus\\{0\\},\\\ \textrm{where
}\;{\mathscr{D}}:=K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))\cap\big{\\{}w\in{\bf
X}\,\big{|}\,\nabla\Phi({\bar{x}})w\in
K_{g}(\Phi({\bar{x}}),\bar{y})\big{\\}},\end{cases}$ (3.18)

and investigate whether our desired error bound can be derived under this
condition. Note that the SOSC in (3.18) boils down to the classical second-
order sufficient condition formulated for different classes of constrained
optimization problems including NLPs, second-order cone programming, and SDPs;
see [21, Section 6] for a detailed discussion about the SOSC. For the
composite programming problems in (1.1) with $g$ therein being CPLQ, one can
find recent developments about the SOSC in [12, 31].

It is well-known that the SOSC alone does not ensure the error bound for the
KKT system in (2.2); see the discussion after [23, Theorem 5.9]. What is
needed further is calmness of a multiplier mapping associated with the
composite problem in (1.1), which is defined as the one for $g$ in (3.8).
Given ${\bar{x}}\in{\bf X}$ and $\psi$ taken from (1.1), the multiplier
mapping $M_{{\bar{x}},\psi}\colon{\bf X}\times{\bf Y}\rightrightarrows{\bf
Y}$, associated with the canonically perturbed KKT system (2.2), is defined by

$M_{{\bar{x}},\psi}(v,w):=\big{\\{}y\in{\bf
Y}\;\big{|}\;v\in\nabla_{x}L({\bar{x}},y)+N_{\Theta}({\bar{x}}),\;y\in\partial
g\big{(}\Phi({\bar{x}})+w\big{)}\big{\\}},\;\;(v,w)\in{\bf X}\times{\bf Y}.$
(3.19)

It is easy to see that if ${\bar{x}}$ is a local minimum of the composite
problem in (1.1), $M_{{\bar{x}},\psi}(0,0)$ reduces to the set of Lagrange
multipliers associated with ${\bar{x}}$. Note also that for any $\bar{y}\in
M_{{\bar{x}},\psi}(0,0)$, the pair $({\bar{x}},\bar{y})$ is a solution to the
KKT system in (2.2). While, throughout this paper, we always assume that a
Lagrange multiplier exists, it is well-known in general that the existence of
such a Lagrange multiplier requires a constraint qualification. Getting into
the question of which constraint qualification to choose is unnecessary for
our developments in this paper, however.

Given a solution $({\bar{x}},\bar{y})$ to the KKT system (2.2), the calmness
of the multiplier mapping $M_{{\bar{x}},\psi}$ in (3.19) at $(0,0)$ for
$\bar{y}$ amounts to the existence of a positive constant $\tau$ and
neighborhoods $U$ of $(0,0)$ and $V$ of $\bar{y}$ such that

$M_{{\bar{x}},\psi}(v,w)\cap V\subset
M_{{\bar{x}},\psi}(0,0)+\tau\|(w,v)\|\mathbb{B}\quad\mbox{for all}\;\;(v,w)\in
U.$

It follows from [8, Theorem 3H.3] that this property is equivalent to the
metric subregualrity of its inverse mapping $M_{{\bar{x}},\psi}^{-1}$ at
$\bar{y}$ for $(0,0)$, which means that there exist a positive constant $\ell$
and a neighborhood $V$ of $\bar{y}$ for which the estimate

${\rm dist}\big{(}y,M_{{\bar{x}},\psi}(0,0)\big{)}\leq\ell\,\big{(}{\rm
dist}(-\nabla_{x}L({\bar{x}},y),N_{\Theta}({\bar{x}}))+{\rm
dist}(\Phi({\bar{x}}),(\partial g)^{-1}(y))\big{)}\quad\mbox{for all}\;y\in V$
(3.20)

holds. Below, we record some conditions under which the clamness of the
multiplier mapping $M_{{\bar{x}},\psi}$ is satisfied.

######  Proposition 3.8.

Assume that $({\bar{x}},\bar{y})$ is a solution to the KKT system (2.2). Then
the multiplier mapping $M_{{\bar{x}},\psi}$ is calm at $(0,0)$ for $\bar{y}$
if one of the following conditions holds:

  * (a)

the convex function $g$ in (1.1) is CPLQ;

  * (b)

the subgradient mapping $\partial g$ is calm at $\Phi({\bar{x}})$ for
$\bar{y}$ and there exists $\tilde{y}\in M_{{\bar{x}},\psi}(0,0)$ such that
$-\nabla_{x}L({\bar{x}},\tilde{y})\in{\rm ri}\,N_{\Theta}({\bar{x}})$ and
$\tilde{y}\in{\rm ri}\,\partial g(\Phi({\bar{x}}))$.

[Proof. ]Observe first that the set $M_{{\bar{x}},\psi}(0,0)$ can be
equivalently written as

$M_{{\bar{x}},\psi}(0,0)=\Omega\cap\partial
g(\Phi({\bar{x}}))\quad\mbox{with}\quad\Omega:=\big{\\{}y\in{\bf
Y}\;\big{|}\;0\in\nabla_{x}L({\bar{x}},y)+N_{\Theta}({\bar{x}})\big{\\}}.$

If (a) holds, $\partial g(\Phi({\bar{x}}))$ is a polyhedral convex set. By
assumption, $\Omega$ is a polyhedral convex set as well. It follows then from
[14, Theorem 8.35] that there is a constant $\rho\geq 0$ such that for any
$y\in Y$ the estimate

${\rm dist}(y,M_{{\bar{x}},\psi}(0,0))\leq\rho\big{(}{\rm dist}(y,\Omega)+{\rm
dist}(y,\partial g(\Phi({\bar{x}}))\big{)}$

holds. If (b) holds, the same estimate holds for any $y$ sufficiently close to
$\bar{y}$ due to the existence of $\tilde{y}$, which can be equivalently
translated as ${\rm ri}\,\Omega\cap{\rm ri}\,\partial
g(\Phi({\bar{x}}))\neq\emptyset$; see [3, Corollary 3]. Using the classical
Hoffman lemma (cf. [8, Lemma 3C.4]) gives us a constant $\rho^{\prime}\geq 0$
such that the estimate

${\rm dist}(y,\Omega)\leq\rho^{\prime}{\rm
dist}\big{(}-\nabla_{x}L({\bar{x}},y),N_{\Theta}({\bar{x}})\big{)}$

is satisfied for any $y\in{\bf Y}$. If $g$ is CPLQ, it follows from the proof
of [30, Theorem 11.14(b)] that ${\rm gph}\,\partial g$ is a union of finitely
many polyhedral convex sets. So, we conclude from [26, Proposition 1] (see
also [8, Theorem 3D.1]) that the subgradient mapping $\partial g$ is calm at
$\Phi({\bar{x}})$ for $\bar{y}$. Thus, if either (a) or (b) holds, $(\partial
g)^{-1}$ is metrically subregular at $\bar{y}$ for $\Phi({\bar{x}})$ (cf. [8,
Theorem 3H.3]), meaning that there are a positive constant
$\rho^{\prime\prime}$ and a neighborhood $V$ of $\bar{y}$ for which the
estimate

${\rm dist}(y,\partial g(\Phi({\bar{x}}))\big{)}\leq\rho^{\prime\prime}\,{\rm
dist}(\Phi({\bar{x}}),(\partial g)^{-1}(y)\big{)}$

holds for any $y\in V$. Combining all these estimates proves the calmness of
the multiplier mapping $M_{{\bar{x}},\psi}$ at $(0,0)$ for $\bar{y}$.

It is worth mentioning that the existence of $\tilde{y}$ in Proposition 3.8(b)
boils down to the classical strict complementarity assumption in case
$\Theta={\bf X}$ in the composite problem in (1.1), which reads as the
existence of a multiplier $\tilde{y}$ such that
$\nabla_{x}L({\bar{x}},\tilde{y})=0$ and $\tilde{y}\in{\rm ri}\,\partial
g(\Phi({\bar{x}}))$. Furthermore, according to [2, Theorem 3.3], the calmness
of the subgradient mapping $\partial g$ in Proposition 3.8(b) is equivalent to
the conjugate function $g^{*}$ satisfying the quadratic growth condition

$g^{*}(y)\geq
g^{*}(\bar{y})+\langle\Phi({\bar{x}}),y-\bar{y}\rangle+\kappa\,{\rm
dist}\big{(}y,\partial g(\Phi({\bar{x}}))\big{)}\quad\mbox{whenever}\;\;y\in
V,$

where $\kappa$ is a positive constant and $V$ is a neighborhood of $\bar{y}$.
It is known that this calmness condition holds for the subgradient mapping of
CPLQ functions (cf. [26, Proposition 1]) as well as the ${\cal
C}^{2}$-decomposable functions under the condition (3.9) (cf. Propsoition
3.4(e)).

To proceed, define the residual function $r\colon{\bf X}\times{\bf Y}\to{\bf
R}$ of the KKT system (2.2) by

$r(x,y):={\rm dist}(-\nabla_{x}L(x,y),N_{\Theta}(x))+\|\Phi(x)-{\rm
prox}_{g}\big{(}\Phi(x)+y\big{)}\|,\;\;(x,y)\in{\bf X}\times{\bf Y}.$ (3.21)

It is easy to see that a pair $(x,y)$ is a solution to the KKT system in (2.2)
if and only if $r(x,y)=0$. The residual function $r$, indeed, measures the
violation of the KKT system in (2.2) for a given pair $(x,y)$ and plays an
important role as a surrogate for the tolerance parameter ${\epsilon_{k}}$ in
(1.5).

######  Theorem 3.9.

Assume that $({\bar{x}},\bar{y})$ is a solution to the KKT system (2.2) for
which the SOSC in (3.18) holds. Assume further that one of the following
conditions holds:

  * (a)

the convex function $g$ in (1.1) is ${\cal C}^{2}$-decomposable and the
nondegeneracy condition in (3.13) is satisfied for $\bar{u}=\Phi({\bar{x}})$;

  * (b)

the convex function $g$ in (1.1) is twice epi-differentiable at
$\Phi({\bar{x}})$ for $\bar{y}$ and the equality in (3.14) holds for
$\bar{u}=\Phi({\bar{x}})$ and $\bar{y}$.

If the multiplier mapping $M_{{\bar{x}},\psi}$ in (3.19) is calm at
$(0,0)\in{\bf X}\times{\bf Y}$ for $\bar{y}$, then there exist constants
$\gamma>0$ and $\kappa\geq 0$ such that

$\|x-{\bar{x}}\|+{\rm
dist}\big{(}y,M_{{\bar{x}},\psi}(0,0)\big{)}\leq\kappa\,r(x,y)\quad\mbox{ for
all }\;\;(x,y)\in\mathbb{B}_{\gamma}({\bar{x}},\bar{y}).$ (3.22)

[Proof. ]We begin by showing that that there exists a neighborhood $U$ of
$({\bar{x}},\bar{y})$ such that

$\|x-{\bar{x}}\|=O\big{(}r(x,y)\big{)}\quad\textrm{for all}\quad(x,y)\in U.$
(3.23)

If this claim fails, we find a sequence
$({x^{k}},y^{k})\to({\bar{x}},\bar{y})$ such that

$t_{k}:=\|{x^{k}}-{\bar{x}}\|>k\,r({x^{k}},y^{k})\geq 0\quad\mbox{for
all}\;\,k\in{\rm I\\!N},$

meaning that $r({x^{k}},y^{k})=o(t_{k})$. Thus, by (3.21), we find
${\alpha^{k}}\in{\bf X}$ and ${\beta^{k}}\in{\bf Y}$ such that
${\alpha^{k}}=o(t_{k})$ and ${\beta^{k}}=o(t_{k})$, where

$-\nabla_{x}L({x^{k}},y^{k})+{\alpha^{k}}\in
N_{\Theta}({x^{k}})\quad\textrm{and }\quad{\beta^{k}}=\Phi\big{(}{x^{k}})-{\rm
prox}_{g}(\Phi({x^{k}})+y^{k}\big{)}.$ (3.24)

It then follows from the first identity in (2.8) that

$y^{k}+{\beta^{k}}\in\partial g(\Phi({x^{k}})-{\beta^{k}}).$ (3.25)

The calmness of multiplier mapping $M_{{\bar{x}},\psi}$ at $(0,0)$ for
$\bar{y}$ implies that there exist a positive constant $\ell$ and a
neighborhood $V$ of $\bar{y}$ for which the estimate in (3.20) holds. This
allows us to conclude for any $k$ sufficiently large that

${\rm
dist}\big{(}y^{k}+{\beta^{k}},M_{{\bar{x}},\psi}(0,0)\big{)}\leq\ell\big{(}{\rm
dist}(-\nabla_{x}L({\bar{x}},y^{k}+{\beta^{k}}),N_{\Theta}({\bar{x}}))+{\rm
dist}(\Phi({\bar{x}}),(\partial g)^{-1}(y^{k}+{\beta^{k}}))\big{)}.$

Recall that $\Theta$ is a polyhedral set and that ${x^{k}}\to{\bar{x}}$ as
$k\to\infty$. We then deduce that $N_{\Theta}({x^{k}})\subset
N_{\Theta}({\bar{x}})$ for $k$ sufficiently large and get the estimates

$\displaystyle{\rm
dist}(-\nabla_{x}L({\bar{x}},y^{k}+{\beta^{k}}),N_{\Theta}({\bar{x}}))\leq$
$\displaystyle\,{\rm
dist}(-\nabla_{x}L({\bar{x}},y^{k}+{\beta^{k}}),N_{\Theta}({x^{k}}))$
$\displaystyle\leq$
$\displaystyle\,\|-\nabla_{x}L({\bar{x}},y^{k}+{\beta^{k}})-(-\nabla_{x}L({x^{k}},y^{k})+{\alpha^{k}})\|$
$\displaystyle\leq$
$\displaystyle\,\|\nabla\varphi({x^{k}})-\nabla\varphi({\bar{x}})\|+\|(\nabla\Phi({x^{k}})-\nabla\Phi({\bar{x}}))^{*}y^{k}\|$
$\displaystyle+\|\nabla\Phi({\bar{x}})^{*}{\beta^{k}}\|+\|{\alpha^{k}}\|=O(t_{k}),$

where the last equality comes from the Lipschitz continuity of mappings
$\nabla\varphi$ and $\nabla\Phi$ around ${\bar{x}}$ and the estimates in
(3.24). Moreover, by (3.25), we have $\Phi({x^{k}})-{\beta^{k}}\in(\partial
g)^{-1}({\lambda^{k}}+{\beta^{k}})$, which coupled with the Lipschitz
continuity of $\Phi$ around ${\bar{x}}$ and ${\beta^{k}}=o(t_{k})$ leads us to

${\rm dist}\big{(}\Phi({\bar{x}}),(\partial
g)^{-1}({\lambda^{k}}+{\beta^{k}})\big{)}\leq\|\Phi({x^{k}})-{\beta^{k}}-\Phi({\bar{x}})\|=O(t_{k})$

for any $k$ sufficiently large. Combining these estimates demonstrates that

${\rm dist}\big{(}y^{k}+{\beta^{k}},M_{{\bar{x}},\psi}(0,0)\big{)}=O(t_{k})$

for any $k$ sufficiently large. Since $M_{{\bar{x}},\psi}(0,0)$ is a closed
convex set, set $\widehat{y}^{k}:=P_{M_{{\bar{x}},\psi}(0,0)}(y^{k})$. This,
the above estimate, and ${\beta^{k}}=o(t_{k})$ allow us to obtain
$y^{k}-\widehat{y}^{k}=O(t_{k})$. Passing to subsequences if necessary, we can
assume that

$\dfrac{{x^{k}}-{\bar{x}}}{t_{k}}\to w\neq
0\quad\textrm{and}\quad\dfrac{y^{k}-\widehat{y}^{k}}{t_{k}}\to\eta\;\mbox{ as
}\;k\to\infty.$ (3.26)

Recall from (2.2) that $-\nabla_{x}L({\bar{x}},\bar{y})\in
N_{\Theta}({\bar{x}})$. This, coupled with the first inclusion in (3.24) and
the reduction lemma for polyhedral convex sets (cf. [8, Lemma 2E.4]), allows
us to conclude for any $k$ sufficiently large that

$-\big{(}\nabla_{x}L({x^{k}},y^{k})-\nabla_{x}L({\bar{x}},\bar{y})\big{)}+{\alpha^{k}}\in
N_{K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))}({x^{k}}-{\bar{x}}).$

By the definition of $\widehat{y}^{k}$, we have
$-\nabla_{x}L({\bar{x}},\widehat{y}^{k})\in N_{\Theta}({\bar{x}})$. Applying
again the reduction lemma from [8, Lemma 2E.4] brings us to

$-\big{(}\nabla_{x}L({\bar{x}},\widehat{y}^{k})-\nabla_{x}L({\bar{x}},\bar{y})\big{)}\in
N_{K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))}(0)=K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))^{*}$

for any $k$ sufficiently large. On the other hand, we have

$\displaystyle\nabla_{x}L({x^{k}},y^{k})-\nabla_{x}L({\bar{x}},\bar{y})$
$\displaystyle=\nabla_{x}L({x^{k}},\bar{y})-\nabla_{x}L({\bar{x}},\bar{y})+\nabla\Phi(x^{k})^{*}(y^{k}-\bar{y})$
$\displaystyle=\nabla^{2}_{xx}L({\bar{x}},\bar{y})({x^{k}}-{\bar{x}})+\nabla\Phi({x^{k}})^{*}(y^{k}-\widehat{y}^{k})+\nabla\Phi({\bar{x}})^{*}(\widehat{y}^{k}-\bar{y})+o(t_{k}),$

and

$\nabla_{x}L({\bar{x}},\widehat{y}^{k})-\nabla_{x}L({\bar{x}},\bar{y})=\nabla\Phi({\bar{x}})^{*}(\widehat{y}^{k}-\bar{y}).$

Combining these and remembering that ${\alpha^{k}}=o(t_{k})$ lead us to the
inclusion

$\displaystyle\nabla^{2}_{xx}L({\bar{x}},\bar{y})(\frac{{x^{k}}-{\bar{x}}}{t_{k}})$
$\displaystyle+\nabla\Phi({x^{k}})^{*}(\frac{y^{k}-\widehat{y}^{k}}{t_{k}})+\frac{o(t_{k})}{t_{k}}$
$\displaystyle\in
K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},{\bar{\lambda}}))^{*}-N_{K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))}(\frac{{x^{k}}-{\bar{x}}}{t_{k}})$
$\displaystyle\subset
K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},{\bar{\lambda}}))^{*}-N_{K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))}(w)$

for any $k$ sufficiently large, where the last inclusion results from the
first limit in (3.26) and
$K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},{\bar{\lambda}}))$ being a
polyhedral convex set. The right-hand side of this inclusion is the sum of two
polyhedral convex sets, which is again a polyhedral convex set and hence is
closed. Passing to the limit brings us to

$\nabla^{2}_{xx}L({\bar{x}},\bar{y})w+\nabla\Phi({\bar{x}})^{*}\eta\in
K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))^{*}-N_{K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))}(w).$

This implies that $w\in K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))$
and that there are $\nu_{1}\in
K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))^{*}$ and $\nu_{2}\in
N_{K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))}(w)=K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))^{*}\cap[w]^{\bot}$
such that
$\nabla^{2}_{xx}L({\bar{x}},\bar{y})w+\nabla\Phi({\bar{x}})^{*}\eta=\nu_{1}-\nu_{2}$,
which yields

$\langle\nabla^{2}_{xx}L({\bar{x}},\bar{y})w,w\rangle+\langle\eta,\nabla\Phi({\bar{x}})w\rangle=\langle\nu_{1},w\rangle-\langle\nu_{2},w\rangle\leq
0.$ (3.27)

We claim now $\nabla\Phi({\bar{x}})w\in K_{g}(\Phi({\bar{x}}),\bar{y})$. It
follows from the convexity of $g$, $\bar{y}\in\partial g(\Phi({\bar{x}}))$ and
[30, Theorem 8.30] that $\langle\bar{y},\nabla\Phi({\bar{x}})w\rangle\leq{\rm
d}g(\Phi({\bar{x}}))(\nabla\Phi({\bar{x}})w)$. To prove the opposite
inequality, we deduce from (3.25) that

$\displaystyle\langle
y^{k}+{\beta^{k}},\Phi({x^{k}})-\Phi({\bar{x}})-{\beta^{k}}\rangle$
$\displaystyle\geq g(\Phi({x^{k}})-{\beta^{k}})-g(\Phi({\bar{x}}))$
$\displaystyle=g\big{(}\Phi({\bar{x}})+t_{k}\frac{\Phi({x^{k}})-\Phi({\bar{x}})-{\beta^{k}}}{t_{k}}\big{)}-g(\Phi({\bar{x}})).$

Dividing both sides by $t_{k}$ and passing then to the limit result in
$\langle\bar{y},\nabla\Phi({\bar{x}})w\rangle\geq{\rm
d}g(\Phi({\bar{x}}))(\nabla\Phi({\bar{x}})w)$. Thus we get
$\langle\bar{y},\nabla\Phi({\bar{x}})w\rangle={\rm
d}g(\Phi({\bar{x}}))(\nabla\Phi({\bar{x}})w)$, which proves our claim. To
arrive at a contradiction with the SOSC in (3.18), we need to prove that the
second subderivative of $g$ satisfies

$\langle\eta,\nabla\Phi\big{(}{\bar{x}})w\rangle\geq{\rm
d}^{2}g(\Phi({\bar{x}}),\bar{y})(\nabla\Phi({\bar{x}})w).$ (3.28)

Assume first that (b) holds, meaning that $g$ satisfies in (3.14). By (3.26)
and ${\beta^{k}}=o(t_{k})$, we have

$\big{(}\frac{\Phi({x^{k}})-{\beta^{k}}-\Phi({\bar{x}})}{t_{k}},\frac{y^{k}+{\beta^{k}}-\widehat{y}^{k}}{t_{k}}\big{)}\to(\nabla\Phi({\bar{x}})w,\eta).$

This, together with (3.25), the fact $\widehat{y}^{k}\in\partial
g(\Phi({\bar{x}}))$ and Definition 3.1, tells us that
$\eta\in\widehat{D}(\partial
g)(\Phi({\bar{x}}),\bar{y})(\nabla\Phi({\bar{x}})w)$. By (3.14), we find
sequences $\\{\eta_{1}^{k}{\\}_{k\in{\rm I\\!N}}}\subset D(\partial
g)(\Phi({\bar{x}}),\bar{y})(\nabla\Phi({\bar{x}})w)$ and
$\\{\eta_{2}^{k}{\\}_{k\in{\rm I\\!N}}}\subset
K_{g}(\Phi({\bar{x}}),\bar{y})^{*}$ for which we have
$\eta_{1}^{k}-\eta_{2}^{k}\to\eta$ as $k\to\infty$. It follows from [30,
Theorem 13.40] and [7, Lemma 3.6] that ${\rm
d}^{2}g(\Phi({\bar{x}}),\bar{y})(\nabla\Phi({\bar{x}})w)=\langle\eta_{1}^{k},\nabla\Phi({\bar{x}})w\rangle$
and from $\nabla\Phi({\bar{x}})w\in K_{g}(\Phi({\bar{x}}),\bar{y})$ that
$\langle\eta_{2}^{k},\nabla\Phi({\bar{x}})w\rangle\leq 0$ for all $k\in{\rm
I\\!N}$. So, we get

$\langle\eta_{1}^{k}-\eta_{2}^{k},\nabla\Phi({\bar{x}})w\rangle\geq{\rm
d}^{2}g(\Phi({\bar{x}}),\bar{y})(\nabla\Phi({\bar{x}})w).$

Passing to the limit then proves (3.28) when (b) holds. Assume now that (a) is
satisfied. It follows from the nondegeneracy condition in (3.13) and the
inclusions in (6.5) and (3.15) that the BCQ condition in (3.9) holds. This
tells us that there is a neighborhood ${\cal O}$ of $\bar{u}=\Phi({\bar{x}})$
such that for any $u\in{\cal O}\cap{\rm dom}\,\vartheta$, we have

$N_{{\rm dom}\,\vartheta}(\Xi(u))\cap{\rm ker}\,\nabla\Xi(u)^{*}=\\{0\\}.$

So, for any $k$ sufficiently large, we conclude from the chain rule for
subdifferentials in [30, Theorem 10.6], $\widehat{y}^{k}\in\partial
g(\Phi({\bar{x}}))$, and (3.25) that there are
$\widehat{\mu}^{k}\in\partial\vartheta(\Xi(\bar{u}))$ and
$\mu^{k}\in\partial\vartheta(\Xi(u^{k}))$ with
$u^{k}=\Phi({x^{k}})-{\beta^{k}}$ such that

$\widehat{y}^{k}=\nabla\Xi(\bar{u})^{*}\widehat{\mu}^{k}\quad\mbox{and}\quad
y^{k}+{\beta^{k}}=\nabla\Xi(u^{k})^{*}\mu^{k}.$

These allow us to obtain

$\big{\langle}\frac{y^{k}+{\beta^{k}}-\widehat{y}^{k}}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}=\big{\langle}\frac{\nabla\Xi(\bar{u})^{*}(\mu^{k}-\widehat{\mu}^{k})}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}+\big{\langle}\frac{(\nabla\Xi(u^{k})-\nabla\Xi(\bar{u}))^{*}\mu^{k}}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}.$

The first term in the right-hand side of the above equality can be estimated
by

$\displaystyle\big{\langle}\frac{\nabla\Xi(\bar{u})^{*}(\mu^{k}-\widehat{\mu}^{k})}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}$
$\displaystyle=\big{\langle}\frac{\mu^{k}-\widehat{\mu}^{k}}{t_{k}},\frac{\nabla\Xi(\bar{u})(u^{k}-\bar{u})}{t_{k}}\big{\rangle}$
$\displaystyle=\big{\langle}\frac{\mu^{k}-\widehat{\mu}^{k}}{t_{k}},\frac{\Xi(u^{k})-\Xi(\bar{u})}{t_{k}}\big{\rangle}+\big{\langle}\frac{\mu^{k}-\widehat{\mu}^{k}}{t_{k}},\frac{o(\|u^{k}-\bar{u}\|)}{t_{k}}\big{\rangle}$
$\displaystyle\geq\big{\langle}\frac{\mu^{k}-\widehat{\mu}^{k}}{t_{k}},\frac{o(t_{k})}{t_{k}}\big{\rangle},$

where the last inequality results from the monotonicity of the subgradient
mapping $\partial\vartheta$ and the fact that $u^{k}-\bar{u}=O(t_{k})$. Also,
we have

$\big{\langle}\frac{(\nabla\Xi(u^{k})-\nabla\Xi(\bar{u}))^{*}\mu^{k}}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}=\big{\langle}\frac{(\nabla^{2}\Xi(\bar{u})(u^{k}-\bar{u})+o(t_{k}))^{*}\mu^{k}}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}.$

Combining these results in the estimate

$\big{\langle}\frac{y^{k}+{\beta^{k}}-\widehat{y}^{k}}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}\geq\big{\langle}\frac{\mu^{k}-\widehat{\mu}^{k}}{t_{k}},\frac{o(t_{k})}{t_{k}}\big{\rangle}+\big{\langle}\frac{(\nabla^{2}\Xi(\bar{u})(u^{k}-\bar{u})+o(t_{k}))^{*}\mu^{k}}{t_{k}},\frac{u^{k}-\bar{u}}{t_{k}}\big{\rangle}.$
(3.29)

By (3.26) and ${\beta^{k}}=o(t_{k})$, we can conclude that the left-hand side
in (3.29) converges to $\langle\eta,\nabla\Phi({\bar{x}})w\rangle$. Moreover,
a similar argument as the one after (3.16) and the fact that
$y^{k}-\widehat{y}^{k}=O(t_{k})$ tell us that
$\mu^{k}-\widehat{\mu}^{k}=O(t_{k})$. Thus, the first term on the right-hand
side in (3.29) converges to $0$. Finally, the nondegeneracy condition in
(3.13) and the inclusion in (6.5) implies that the dual condition in (3.10) is
satisfied. By Theorem 6.1(d), we obtain that the sequence
$\\{\mu^{k}{\\}_{k\in{\rm I\\!N}}}$ converges to $\bar{\mu}$ as $k\to\infty$,
where $\bar{\mu}$ is the unique element in $M_{\bar{u},g}(\bar{y},0)$ with
$M_{\bar{u},g}(\bar{y},0)$ taken from (3.8); see Theorem 6.1. Passing to the
limit in (3.29) then shows that

$\langle\eta,\nabla\Phi({\bar{x}})w\rangle\geq\big{\langle}\bar{\mu},\nabla^{2}\Xi(\bar{u})(\nabla\Phi({\bar{x}})w,\nabla\Phi({\bar{x}})w)\big{\rangle}.$

Recall that $\nabla\Phi({\bar{x}})w\in K_{g}(\Phi({\bar{x}}),\bar{y})$, which
together with (3.11) brings us to
$\nabla\Xi(\bar{u})(\nabla\Phi({\bar{x}})w)\in
K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})$. Employing now the established formula
for the second subderivative of $g$ in Theorem 6.1(a) and using (6.2) result
in

$\big{\langle}\bar{\mu},\nabla^{2}\Xi(\bar{u})(\nabla\Phi({\bar{x}})w,\nabla\Phi({\bar{x}})w)\big{\rangle}={\rm
d}^{2}g(\bar{u},\bar{y})(\nabla\Phi({\bar{x}})w).$

Combining these two estimates proves (3.28) when (a) holds. By (3.28) and
(3.27), we obtain

$\langle\nabla^{2}_{xx}L({\bar{x}},\bar{y})w,w\rangle+{\rm
d}^{2}g(\bar{u},\bar{y})(\nabla\Phi({\bar{x}})w)\leq\langle\nabla^{2}_{xx}L({\bar{x}},\bar{y})w,w\rangle+\langle\eta,\nabla\Phi({\bar{x}})w\rangle\leq
0,$

which contradicts the SOSC in (3.18), since $w\neq 0$ and $w\in{\mathscr{D}}$
with ${\mathscr{D}}$ taken from (3.18). This proves the estimate in (3.23).

To justify (3.22), we need to show that shrinking the neighborhood $U$ from
(3.23), if necessary, we have

${\rm
dist}\big{(}y,M_{{\bar{x}},\psi}(0,0)\big{)}=O\big{(}r(x,y)\big{)}\quad\textrm{for
all}\quad(x,y)\in U.$ (3.30)

To this end, pick $(x,y)$ satisfying (3.23) and set $z:={\rm
prox}_{g}(\Phi(x)+y)-\Phi(x)$, which results in $y-z\in\partial g(\Phi(x)+z)$
or $\Phi(x)+z\in(\partial g)^{-1}(y-z)$. It is easy to see that $z\to 0$ as
$(x,y)\to({\bar{x}},\bar{y})$. Thus, shrinking the neighborhood $U$ from
(3.23), if necessary, we can assume without loss of generality that $y-z\in
V$, where $V$ is taken from (3.20), and hence conclude from the estimate in
(3.20) and the polyhedrality of $\Theta$ that

$\displaystyle{\rm dist}(y$
$\displaystyle-z,M_{{\bar{x}},\psi}(0,0))\leq\ell\,\big{(}{\rm
dist}(-\nabla_{x}L({\bar{x}},y-z),N_{\Theta}({\bar{x}}))+{\rm
dist}(\Phi({\bar{x}}),(\partial g)^{-1}(y-z))\big{)}$
$\displaystyle\leq\ell\,\big{(}\|\nabla_{x}L(x,y)-\nabla_{x}L({\bar{x}},y-z)\|+{\rm
dist}(-\nabla_{x}L(x,y);N_{\Theta}(x))+\|\Phi(x)+z-\Phi({\bar{x}})\|\big{)}$
$\displaystyle\leq O\big{(}\|x-{\bar{x}}\|+\|z\|\big{)}+\ell\,{\rm
dist}(-\nabla_{x}L(x,y),N_{\Theta}(x))$ $\displaystyle=O\big{(}r(x,y)\big{)},$

where the last equality comes from (3.23) and the definition of the residual
function $r$. Since the distance function is Lipschitz continuous, we get

${\rm dist}\big{(}y,M_{{\bar{x}},\psi}(0,0)\big{)}-{\rm
dist}\big{(}y-z,M_{{\bar{x}},\psi}(0,0)\big{)}=O(\|z\|)=O(\|{\rm
prox}_{g}(\Phi(x)+y)-\Phi(x)\|)=O\big{(}r(x,y)\big{)}.$

Combining these estimates, we arrive at (3.30). This completes the proof.

The error bound in Theorem 3.9 was obtained previously in [23, Theorem 5.9]
for ${\cal C}^{2}$-cone reducible constrained optimization problems using a
rather lengthy reduction process, a path that was not followed here. It was
extended for CPLQ composite optimization problems in [31, Theorem 3.6].
Theorem 3.9 provides a general property – condition (b) in this theorem– under
which the error bound can be achieved. The main question that remains open
here is whether ${\cal C}^{2}$-decomposable functions satisfy in (3.14). It is
worth reiterating here that ${\cal C}^{2}$-decomposable functions do not
contain CPLQ functions (see Remark 3.7) and hence condition (b) in Theorem 3.9
cannot be covered by condition (a) therein.

##  4 Semi-Stability of Second Subderivatives

In parallel with the notion of semi-strict graphical derivative in Definition
3.1, we define in this section a semi-strict counterpart of the second
subderivative of functions and use it to introduce a new regularity condition
associated with the latter construction that plays a crucial role in our local
convergence analysis of the ALM.

######  Definition 4.1.

Assume that $f\colon{\bf X}\to\overline{{\bf R}}$, ${\bar{x}}\in{\bf X}$ with
$f({\bar{x}})$ finite, and $\bar{v}\in\partial f({\bar{x}})$.

  * (a)

The semi-strict second subderivative of $f$ at $\bar{x}$ for $\bar{v}$ is
defined by

$\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})(w)=\liminf_{\begin{subarray}{c}t\searrow
0,\,w^{\prime}\to w\\\ v\to\bar{v},\;v\in\partial
f({\bar{x}})\end{subarray}}\Delta_{t}^{2}f({\bar{x}},v)(w^{\prime}),\quad
w\in{\bf X}.$

  * (b)

The second subderivative of $f$ at $\bar{x}$ for $\bar{v}$ is said to be semi-
stable if $\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)={\rm
d}^{2}f({\bar{x}},\bar{v})(w)$ for any $w\in K_{f}({\bar{x}},\bar{v})$.

As demonstrated below, the semistability of second subderivatives is satisfied
for various classes of functions, important for modeling constrained and
composite optimization problems. Note that the inequality $\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})(w)\leq{\rm d}^{2}f({\bar{x}},\bar{v})(w)$ always
holds for any $w\in{\bf X}$. Thus justifying semi-stability of second
subderivatives reduces to investigating whether or not the latter inequality
holds as equality.

######  Proposition 4.2.

Assume that $f\colon{\bf X}\to\overline{{\bf R}}$, ${\bar{x}}\in{\bf X}$ with
$f({\bar{x}})$ finite, and $\bar{v}\in\widehat{\partial}f({\bar{x}})$. Then we
have

${\rm dom}\,\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})\subset{K_{f}}({\bar{x}},\bar{v}).$

[Proof. ]Take $w\in{\rm dom}\,\widehat{\rm d}^{2}f({\bar{x}},\bar{v})$ and
conclude that $\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)<\infty$. Since we
obtain for any $t>0$ that

$\Delta_{t}^{2}f(\bar{x},v)(w^{\prime})=\frac{\Delta_{t}f({\bar{x}})(w^{\prime})-\langle
v,w^{\prime}\rangle}{\hbox{${1\over
2}$}t}\quad\mbox{with}\;\;\Delta_{t}f({\bar{x}})(w^{\prime}):=\frac{f({\bar{x}}+tw^{\prime})-f({\bar{x}})}{t},$

it follows from the definition of $\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)$
that

$\alpha:=\liminf_{\begin{subarray}{c}t\searrow 0,\,w^{\prime}\to w\\\
v\to\bar{v},\;v\in\partial
f({\bar{x}})\end{subarray}}\Delta_{t}f({\bar{x}})(w^{\prime})-\langle
v,w^{\prime}\rangle<\infty.$

If $\alpha>0$, we would get $\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})(w)=\infty$, a contradiction. Thus, we must have
$\alpha\leq 0$, which clearly tells us that ${\rm
d}f({\bar{x}})(w)\leq\langle\bar{v},w\rangle$. Noting that the opposite
inequality always holds because of $\bar{v}\in\widehat{\partial}f({\bar{x}})$
(cf. [30, Exercise 8.4]), we arrive at the claimed inclusion.

Which classes of functions enjoy the semi-stability of second subserivatives?
To answer this question, we begin with the following observation. Suppose that
$f\colon{\bf X}\to\overline{{\bf R}}$ is a polyhedral function, meaning that
its epigraph is a polyhedral convex set in ${\bf X}\times{\bf R}$. Given
$({\bar{x}},\bar{v})\in{\rm gph}\,\partial f$, it is known (cf. [30,
Proposition 13.9]) that

${\rm d}^{2}f({\bar{x}},\bar{v})=\delta_{{K_{f}}({\bar{x}},\bar{v})}.$

It follows from the convexity of $f$ that
$\Delta_{t}^{2}f(\bar{x},v)(w^{\prime})\geq 0$ for any $v\in\partial
f({\bar{x}})$, $w^{\prime}\in{\bf X}$, and $t>0$. Thus, we get $\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})(w)\geq 0$ for any $w\in{\bf X}$ and conclude from
the inequality $\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)\leq{\rm
d}^{2}f({\bar{x}},\bar{v})(w)$, satisfied for any $w\in{\bf X}$, that
$\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)=0$ for any
$w\in{K_{f}}({\bar{x}},\bar{v})$. Combining this and Proposition 4.2 confirms
that

$\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})=\delta_{{K_{f}}({\bar{x}},\bar{v})}={\rm
d}^{2}f({\bar{x}},\bar{v}),$ (4.1)

which means that the second subderivative of a polyhedral function is always
semi-stable. This motivates us to explore further whether or not a similar
result holds for CPLQ functions.

######  Example 4.3.

Assume that the function $f:{\bf X}\to\overline{{\bf R}}$ with ${\bf X}={\bf
R}^{n}$ is CPLQ with the representation given in Example 3.3. It was proven in
[30, Propsoition 13.9] that the second subderivative of $f$ at ${\bar{x}}$ for
$\bar{v}\in\partial f({\bar{x}})$ can be calculated by

${\rm d}^{2}f({\bar{x}},\bar{v})(w)=\begin{cases}\langle
A_{i}w,w\rangle&\mbox{if}\;\;w\in K_{C_{i}}({\bar{x}},\bar{v}_{i}),\\\
\infty&\mbox{otherwise},\end{cases}$ (4.2)

where $\bar{v}_{i}:=\bar{v}-A_{i}{\bar{x}}-a_{i}$. We claim that $\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})(w)={\rm d}^{2}f({\bar{x}},\bar{v})(w)$ for any
$w\in{\bf X}$, which proves that the second subderivative of a CPLQ function
is always semi-stable. Take $w\in K_{f}({\bar{x}},\bar{v})$ and select
sequences $t_{k}\searrow 0$, $v^{k}\to\bar{v}$ with $v^{k}\in\partial
f({\bar{x}})$, and $w^{k}\to w$ such that

$\widehat{\rm
d}^{2}f({\bar{x}},\bar{v})(w)=\lim_{k\to\infty}\Delta_{t_{k}}^{2}f(\bar{x},v^{k})(w^{k}).$

Since $\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)\leq{\rm
d}^{2}f({\bar{x}},\bar{v})(w)<\infty$, we can assume without loss of
generality that ${\bar{x}}+t_{k}w^{k}\in{\rm dom}\,f=\cup_{i=1}^{s}C_{i}$ for
any $k$. Passing to a subsequence, if necessary, we find
$j\in\\{1,\ldots,s\\}$ such that ${\bar{x}}+t_{k}w^{k}\in C_{j}$ for all $k$
and therefore conclude that $w^{k}\in T_{C_{j}}({\bar{x}})$ for all $k$.
Clearly, we have ${\bar{x}}\in C_{j}$. Moreover, we derive from $w\in
K_{f}({\bar{x}},\bar{v})$ and [31, Proposition 2.1(b)] that

$\langle A_{j}{\bar{x}}+a_{j},w\rangle={\rm
d}f({\bar{x}})(w)=\langle\bar{v},w\rangle,$

which in turn brings us to $w\in K_{C_{j}}({\bar{x}},\bar{v}_{j})$. On the
other hand, it follows from [30, page 487] that

$\partial f({\bar{x}})=\bigcap_{i\in I({\bar{x}})}\big{\\{}v\in{\bf
X}|\,v-A_{i}{\bar{x}}-a_{i}\in N_{C_{i}}({\bar{x}})\big{\\}},$ (4.3)

where $I({\bar{x}})=\\{i\in\\{1,\ldots,s\\}\,|\,{\bar{x}}\in C_{i}\\}$. By
$v^{k}\in\partial f({\bar{x}})$ and $j\in I({\bar{x}})$, we get
$v^{k}-A_{j}{\bar{x}}-a_{j}\in N_{C_{j}}({\bar{x}})$. This, coupled with
$w^{k}\in T_{C_{j}}({\bar{x}})$, implies that

$\langle w^{k},v^{k}-A_{j}{\bar{x}}-a_{j}\rangle\leq 0\quad\mbox{for
all}\;\;k.$

Using this, we conclude from a simple calculation that

$\displaystyle\Delta_{t_{k}}^{2}f(\bar{x},v^{k})(w^{k})=\dfrac{f({\bar{x}}+t_{k}w^{k})-f({\bar{x}})-t_{k}\langle
v^{k},\,w^{k}\rangle}{\frac{1}{2}t_{k}^{2}}$ $\displaystyle\hskip
21.68121pt=\dfrac{\frac{1}{2}\langle
A_{j}({\bar{x}}+t_{k}w^{k}),{\bar{x}}+t_{k}w^{k}\rangle+\langle
a_{j},{\bar{x}}+t_{k}w^{k}\rangle+\alpha_{j}-\frac{1}{2}\langle
A_{j}{\bar{x}},{\bar{x}}\rangle-\langle
a_{j},{\bar{x}}\rangle-\alpha_{j}-t_{k}\langle
v^{k},\,w_{k}\rangle}{\frac{1}{2}t_{k}^{2}}$ $\displaystyle\hskip
21.68121pt=\langle A_{j}w^{k},w^{k}\rangle-\dfrac{\langle
w^{k},v^{k}-A_{j}{\bar{x}}-a_{j}\rangle}{\frac{1}{2}t_{k}}\geq\langle
A_{j}w^{k},w^{k}\rangle.$

This, combined with (4.2) and $w\in K_{C_{j}}({\bar{x}},\bar{v}_{j})$, leads
us to

$\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)\geq\langle A_{j}w,w\rangle={\rm
d}^{2}f({\bar{x}},\bar{v})(w).$

Since the opposite inequality always holds, we arrive at

$\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)={\rm
d}^{2}f({\bar{x}},\bar{v})(w)\quad\mbox{for all}\;\;w\in
K_{f}({\bar{x}},\bar{v}).$

If $w\notin K_{f}({\bar{x}},\bar{v})$, we get from Proposition 4.2 and (4.2)
that $\widehat{\rm d}^{2}f({\bar{x}},\bar{v})(w)={\rm
d}^{2}f({\bar{x}},\bar{v})(w)=\infty$, which proves our claim.

The next example reveals that the semi-stability of second subderivatives also
holds for ${\cal C}^{2}$-decomposable functions.

######  Example 4.4.

Assume that $g:{\bf Y}\to\overline{{\bf R}}$ is ${\cal C}^{2}$-decomposable at
$\bar{u}\in{\bf Y}$ with representation (3.6) and that $\bar{y}\in\partial
g(\bar{u})$ and $\bar{\mu}\in M_{\bar{u},g}(\bar{y},0)$. Assume further that
the dual condition in (3.10) is satisfied. We claim that $\widehat{\rm
d}^{2}g(\bar{u},\bar{y})(w)={\rm d}^{2}g(\bar{u},\bar{y})(w)$ for any
$w\in{\bf Y}$. To justify it, observe from $\bar{\mu}\in
M_{\bar{u},g}(\bar{y},0)$ and (3.8) that
$\bar{y}=\nabla\Xi(\bar{u})^{*}\bar{\mu}$ with
$\bar{\mu}\in\partial\vartheta(\Xi(\bar{u}))$. It follows from the convexity
of the sublinear function $\vartheta:{\bf Z}\to\overline{{\bf R}}$ that

$0\leq\widehat{\rm d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\xi)\leq{\rm
d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\xi)=\delta_{K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})}(\xi)\quad\mbox{for
all}\;\;\xi\in{\bf Z},$

where the last equality comes from (6.2). This implies that $\widehat{\rm
d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\xi)={\rm
d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\xi)$ for any $\xi\in
K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})$. If $\xi\notin
K_{\vartheta}(\Xi(\bar{u}),\bar{\mu})$, we infer from (6.2) and Proposition
4.2 that $\widehat{\rm d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\xi)={\rm
d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\xi)=\infty$. These prove that the
second subderivative of $\vartheta$ at $\Xi(\bar{u})$ for $\bar{\mu}$ is semi-
stable. To obtain the same conclusion for $g$, we first observe, for any
$w\in{\bf Y}$, that

$\displaystyle\widehat{\rm d}^{2}g(\bar{u},\bar{y})(w)$ $\displaystyle\leq{\rm
d}^{2}g(\bar{u},\bar{y})(w)$
$\displaystyle=\langle\bar{\mu},\nabla^{2}\Xi(\bar{u})(w,w)\rangle+{\rm
d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\nabla\Xi(\bar{u})w)$
$\displaystyle=\langle\bar{\mu},\nabla^{2}\Xi(\bar{u})(w,w)\rangle+\widehat{\rm
d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\nabla\Xi(\bar{u})w),$

where the penultimate step results from Theorem 6.2(a). Take $w\in{\bf Y}$ and
select $t_{k}\searrow 0$, $y^{k}\to\bar{y}$ with $y^{k}\in\partial
g(\bar{u})$, and $w^{k}\to w$ such that $\widehat{\rm
d}^{2}g(\bar{u},\bar{y})(w)=\lim_{k\to\infty}\Delta_{t_{k}}^{2}g(\bar{u},y^{k})(w^{k}).$
We know from the dual condition (3.10) and (6.5) that the BCQ condition in
(3.9) holds. Employing the chain rule for subdifferentials from [30, Theorem
10.6], we find $\mu^{k}\in\partial\vartheta(\Xi(\bar{u}))$ such that
$y^{k}=\nabla\Xi(\bar{u})^{*}\mu^{k}$. We can also conclude from Theorem
6.1(d) that $\mu^{k}\to\bar{\mu}$ as $y\to\bar{y}$. Set
$\xi^{k}:=\Xi(\bar{u}+t_{k}w^{k})/{t_{k}}$ and conclude from (3.6) that

$\displaystyle\Delta^{2}_{t_{k}}g(\bar{u},y^{k})(w^{k})$
$\displaystyle=\dfrac{\vartheta\big{(}\Xi(\bar{u}+t_{k}w^{k})\big{)}-\vartheta\big{(}\Xi(\bar{u})\big{)}-t_{k}\langle\nabla\Xi(\bar{u})^{*}\mu^{k},w^{k}\rangle}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle=\dfrac{\vartheta\big{(}\Xi(\bar{u})+t_{k}\xi^{k}\big{)}-\vartheta\big{(}\Xi(\bar{u})\big{)}-t_{k}\langle\mu^{k},\xi^{k}\rangle}{\frac{1}{2}t_{k}^{2}}+\dfrac{\langle\mu^{k},\Xi(\bar{u}+t_{k}w^{k})-t_{k}\nabla\Xi(\bar{u})w^{k}\rangle}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle=\Delta^{2}_{t_{k}}\vartheta(\Xi(\bar{u}),\mu^{k})(\xi^{k})+\langle\mu^{k},\nabla^{2}\Xi(\bar{u})(w^{k},w^{k})\rangle+\dfrac{o(t_{k}^{2})}{t_{k}^{2}}.$

Passing to the limit as $k\to\infty$ and using the facts that
$\mu^{k}\to\bar{\mu}$ and $\xi^{k}\to\nabla\Xi(\bar{u})w$ lead us to

$\widehat{\rm d}^{2}g(\bar{u},\bar{y})(w)\geq\widehat{\rm
d}^{2}\vartheta(\Xi(\bar{u}),\bar{\mu})(\nabla\Xi(\bar{u})w)+\langle\bar{\mu},\nabla^{2}\Xi(\bar{u})(w,w)\rangle.$

Combining the above estimates tells us that $\widehat{\rm
d}^{2}g(\bar{u},\bar{y})(w)={\rm d}^{2}g(\bar{u},\bar{y})(w)$ for any
$w\in{\bf X}$, which proves our claim.

We are now in a position to establish our main result of this section, a
uniform quadratic growth condition for the augmented Lagrangian in (1.2) when
the SOSC (3.18) is satisfied. To provide a motivation for this result, we
should remind the readers that it was proven in [12, Theorem 4.1] that for the
composite optimization problem in (1.1) with $g$ therein being CPLQ, the SOSC
is equivalent to the quadratic growth condition for the augmented Lagrangian
function. While the framework in [12] requires that $g$ be CPLQ, it is not
hard to see from the proofs therein that what actually is required is twice
epi-differentiability of the convex function $g$ in (1.1), a property that is
satisfied for numerous classes of functions and sets; see [21, 22, 30]. Below,
we record this characterization of the quadratic growth condition for the
augmented Lagrangian function via the SOSC. Since its proof can be gleaned
from [12, Theorem 4.1] and since it will not be exploited in this paper, we do
not supply it with a proof.

######  Proposition 4.5.

Let $({\bar{x}},\bar{y})$ be a solution to the KKT system (2.2). Then the
following properties are equivalent:

  1. (a)

the SOSC in (3.18) holds at $({\bar{x}},\bar{y})$;

  2. (b)

there exist positive constants $\bar{\rho}$, $\gamma$, and $\ell$ such that
for any $\rho\geq\bar{\rho}$, the quadratic growth condition

${\mathscr{L}}(x,\bar{y},\rho)\geq{\mathscr{L}}({\bar{x}},\bar{y},\rho)+\ell\|x-\bar{x}\|^{2}\quad\mbox{
for all }\;x\in\mathbb{B}_{\gamma}({\bar{x}})\cap\Theta$

holds.

While the characterization above seems appealing, we will see in the next
section when establishing the error bound for consecutive terms of the ALM
that the quadratic growth condition in Proposition 4.5(b) is not sufficient.
In fact, what is needed is a stronger version of this condition, called the
uniform quadratic growth condition, which allows for the Lagrangian multiplier
$\bar{y}$ to move slightly and the same quadratic growth condition still
holds. To achieve it, we begin with the calculation of the second-order
difference quotient of the augmented Lagrangian (1.2). Note that $\bar{v}$ in
the second-order difference quotient of $f$ in (2.1) is taken from $\partial
f({\bar{x}})$. When $f$ is ${\cal C}^{1}$, it is known that $\partial
f({\bar{x}})=\\{\nabla f({\bar{x}})\\}$. In such a case, we drop $\bar{v}$
from the notation of the second-order difference quotient of $f$ in (2.1) and
simply write $\Delta_{t}^{2}f({\bar{x}})(w)$. The second-order difference
quotient of the Moreau envelope was calculated in the proof of [24, Theorem
6.1] (see equation (6.8) in [24]). For the augmented Lagrangian (1.2), a
similar calculation was done in the proof of [18, Lemma 3.2]. Since the set
$\Theta$ in (1.1) was not considered in [18], we provide a proof for the
readers’ convenience.

######  Lemma 4.6.

Let $({\bar{x}},\bar{y})$ be a solution to the KKT system (2.2) and set
$\bar{v}:=\nabla_{x}{\mathscr{L}}({\bar{x}},\bar{y},\rho)$ and
$\Delta_{t}^{2}{\mathscr{L}}({\bar{x}},\bar{y},\rho)(w):={({\mathscr{L}}({\bar{x}}+tw,\bar{y},\rho)-{\mathscr{L}}({\bar{x}},\bar{y},\rho)-\langle\bar{v},w\rangle)}/{\hbox{${1\over
2}$}t^{2}}$ for $\rho>0$. Then for any $\rho>0$, $t>0$, and $w\in{\bf X}$, we
have

$\displaystyle\Delta_{t}^{2}{\mathscr{L}}({\bar{x}},\bar{y},\rho)(w)=\Delta_{t}^{2}\varphi(\bar{x})(w)+\Delta_{t}^{2}\langle\bar{y},\Phi\rangle(\bar{x})(w)+\inf_{u\in{\bf
Y}}\big{\\{}\Delta_{t}^{2}g(\Phi(\bar{x}),\bar{y})(u)+\rho\|\Delta_{t}\Phi({\bar{x}})(w)-u\|^{2}\big{\\}},$

where $\Delta_{t}^{2}\langle\bar{y},\Phi\rangle(\bar{x})$ stands for the
second-order difference quotient of the mapping
$x\mapsto\langle\bar{y},\Phi(x)\rangle$ at ${\bar{x}}$ and where
$\Delta_{t}\Phi({\bar{x}})(w):=(\Phi({\bar{x}}+tw)-\Phi({\bar{x}}))/t$ for any
$t>0$.

[Proof. ]We can conclude from Proposition 2.2(a)-(b) that
$\bar{v}=\nabla\varphi({\bar{x}})+\nabla\Phi({\bar{x}})^{*}\bar{y}$ and

$\displaystyle\tfrac{2}{t^{2}}\big{(}{\mathscr{L}}({\bar{x}}+tw,\bar{y},\rho)-{\mathscr{L}}({\bar{x}},\bar{y},\rho)-t\langle\bar{v},w\rangle\big{)}$
$\displaystyle=$
$\displaystyle\,\tfrac{2}{t^{2}}\big{(}\varphi({\bar{x}}+tw)-\varphi({\bar{x}})+e_{{1}/{\rho}}g\big{(}\Phi({\bar{x}}+tw)+\rho^{-1}\bar{y}\big{)}-g(\Phi({\bar{x}}))-\hbox{${1\over
2}$}\rho^{-1}\|\bar{y}\|^{2}-t\langle\bar{v},w\rangle\big{)}$ $\displaystyle=$
$\displaystyle\;\Delta_{t}^{2}\varphi(\bar{x})(w)-\tfrac{2}{t}\langle\nabla\Phi({\bar{x}})^{*}\bar{y},w\rangle$
$\displaystyle+\tfrac{2}{t^{2}}\big{(}\inf_{z\in{\bf
Y}}\left\\{\right.g(z)-g(\Phi({\bar{x}}))-\langle\bar{y},z-\Phi({\bar{x}})\rangle+\tfrac{1}{2}\rho\|z-\Phi({\bar{x}})-(\Phi({\bar{x}}+tw)-\Phi({\bar{x}}))\|^{2}$
$\displaystyle+\tfrac{1}{2}\rho\|z-\Phi({\bar{x}}+tw)-\rho^{-1}\bar{y}\|^{2}-\tfrac{1}{2}\rho\|z-\Phi({\bar{x}}+tw)\|^{2}-\tfrac{1}{2}\rho^{-1}\|\bar{y}\|^{2}+\langle\bar{y},z-\Phi({\bar{x}})\rangle\left.\right\\}\big{)}$
$\displaystyle=$
$\displaystyle\;\Delta_{t}^{2}\varphi(\bar{x})(w)+\inf_{u\in{\bf
Y}}\big{\\{}\Delta_{t}^{2}g(\Phi({\bar{x}}),\bar{y})(u)+\rho\|u-\Delta_{t}\Phi({\bar{x}})(w)\|^{2}\big{\\}}$
$\displaystyle+\tfrac{2}{t^{2}}\langle\bar{y},\Phi({\bar{x}}+tw)-\Phi({\bar{x}})-t\nabla\Phi({\bar{x}})w\rangle$
$\displaystyle=$
$\displaystyle\;\Delta_{t}^{2}\varphi(\bar{x})(w)+\Delta_{t}^{2}\langle\bar{y},\Phi\rangle({\bar{x}})(w)+\inf_{u\in{\bf
Y}}\big{\\{}\Delta_{t}^{2}g(\Phi({\bar{x}}),\bar{y})(u)+\rho\|u-\Delta_{t}\Phi({\bar{x}})(w)\|^{2}\big{\\}}.$

This clearly completes the proof.

The main consequence of the semi-stability of second subderivatives resides in
the following observation in which we ensure the uniform quadratic growth
condition for the augmented Lagrangian function.

######  Theorem 4.7.

Let $({\bar{x}},\bar{y})$ be a solution to the KKT system (2.2). Assume that
the second subderivative of $g$ at $\Phi({\bar{x}})$ for $\bar{y}$ is semi-
stable and that there is a positive constant $\ell$ such that the SOSC

$\langle\nabla_{xx}^{2}L(\bar{x},{\bar{\lambda}})w,w\rangle+{\rm
d}^{2}g(\Phi(\bar{x}),\bar{y})(\nabla\Phi({\bar{x}})w)\geq\ell\|w\|^{2}\quad\mbox{
for all }\;w\in{\mathscr{D}}$ (4.4)

holds, where ${\mathscr{D}}$ is taken from (3.18). Then, there exist positive
constants $\bar{\rho}$ and $\gamma$ for which the uniform quadratic growth
condition

$\begin{cases}{\mathscr{L}}(x,y,\rho)\geq{\mathscr{L}}({\bar{x}},y,\rho)+\frac{\kappa}{2}\|x-{\bar{x}}\|^{2}\\\
\mbox{for all}\;\;x\in\Theta\cap\mathbb{B}_{\gamma}({\bar{x}}),\;y\in
M_{{\bar{x}},\psi}(0,0)\cap\mathbb{B}_{\gamma}(\bar{y}),\;\rho\geq\bar{\rho},\end{cases}$
(4.5)

is fulfilled for all $\kappa\in[0,\ell)$, where $M_{{\bar{x}},\psi}(0,0)$ is
the set of Lagrange multipliers associated with ${\bar{x}}$ and is taken from
(3.19).

[Proof. ]Suppose by contradiction that (4.5) fails. Thus, there exist
$x^{k}\to{\bar{x}}$ with ${x^{k}}\in\Theta$, $y^{k}\to\bar{y}$ with $y^{k}\in
M_{{\bar{x}},\psi}(0,0)$, and $\rho_{k}\to\infty$ such that

${\mathscr{L}}(x^{k},y^{k},\rho_{k})<{\mathscr{L}}({\bar{x}},y^{k},\rho_{k})+\frac{\kappa}{2}\|x^{k}-{\bar{x}}\|^{2},$

holds for some $\kappa\in[0,\ell)$. Set $t_{k}:=\|x^{k}-{\bar{x}}\|$ and
$w^{k}:=(x^{k}-{\bar{x}})/t_{k}$. Passing to a subsequence if necessary, we
can assume that $w^{k}\to w$ for some $w\in{\bf X}$ with $\|w\|=1$.
Substituting $x^{k}={\bar{x}}+t_{k}w^{k}$ into the latter estimate, we arrive
at

$\Delta_{t_{k}}^{2}{\mathscr{L}}({\bar{x}},y^{k},\rho_{k})(w^{k})+\frac{2}{t_{k}}\langle
v^{k},w^{k}\rangle=\frac{{\mathscr{L}}({\bar{x}}+t_{k}w^{k},y^{k},\rho_{k})-{\mathscr{L}}({\bar{x}},y^{k},\rho_{k})}{\hbox{${1\over
2}$}t_{k}^{2}}<\kappa.$

where $v^{k}:=\nabla_{x}{\mathscr{L}}({\bar{x}},y^{k},\rho_{k})$. It follows
from $y^{k}\in M_{{\bar{x}},\psi}(0,0)$ that $({\bar{x}},y^{k})$ is a solution
to the KKT system in (2.2). By Proposition 2.2(b), we have
$-v^{k}=-(\nabla\varphi({\bar{x}})+\nabla\Phi({\bar{x}})^{*}y^{k})\in
N_{\Theta}({\bar{x}})$. Set
$\alpha_{k}:=\Delta_{t_{k}}^{2}\varphi(\bar{x})(w^{k})+\Delta_{t_{k}}^{2}\langle
y^{k},\Phi\rangle(\bar{x})(w^{k})$ and observe that

$\alpha_{k}\to\langle\nabla_{xx}^{2}L(\bar{x},\bar{y})w,w\rangle\quad\textrm{
and }\quad
v^{k}\to\nabla_{x}L({\bar{x}},\bar{y})\quad\mbox{as}\;\;k\to\infty.$ (4.6)

It follows from Lemma 4.6 that

$\alpha_{k}+\frac{2}{t_{k}}\langle v^{k},w^{k}\rangle+\inf_{u\in{\bf
Y}}\big{\\{}\Delta_{t_{k}}^{2}g(\Phi(\bar{x}),y^{k})(u)+\rho_{k}\|u-\Delta_{t_{k}}\Phi({\bar{x}})(w^{k})\|^{2}\big{\\}}<\kappa.$

Since $g$ is convex and $y^{k}\in\partial g(\Phi({\bar{x}}))$, we get that
$\Delta_{t_{k}}^{2}g(\Phi(\bar{x}),y^{k})(\cdot)$ is nonnegative. So, for any
$k\in{\rm I\\!N}$, we find $u^{k}\in{\bf Y}$ such that

$\alpha_{k}+\frac{2}{t_{k}}\langle
v^{k},w^{k}\rangle+\Delta_{t_{k}}^{2}g(\Phi(\bar{x}),y^{k})(u^{k})+\rho_{k}\|u^{k}-\Delta_{t_{k}}\Phi({\bar{x}})(w^{k})\|^{2}<\kappa+\frac{1}{k}.$
(4.7)

It also follows from the convexity of $\Theta$ that $\tfrac{2}{t_{k}}\langle
v^{k},w^{k}\rangle=\Delta_{t_{k}}^{2}\delta_{\Theta}({\bar{x}},-v^{k})(w^{k})\geq
0$. Using these and (4.7), we obtain

$\|\Delta_{t_{k}}\Phi({\bar{x}})(w^{k})-u^{k}\|^{2}\leq\frac{1}{{\rho_{k}}}\big{(}\kappa+\tfrac{1}{k}-\alpha_{k}\big{)},$

which clearly yields $\Delta_{t_{k}}\Phi({\bar{x}})(w^{k})-u^{k}\to 0$ as
$k\to\infty$. Combining this with
$\Delta_{t_{k}}\Phi({\bar{x}})(w^{k})\to\nabla\Phi({\bar{x}})w$, we arrive at
$u^{k}\to\nabla\Phi({\bar{x}})w$. Employing (4.7) again, we conclude that

$\frac{2}{t_{k}}\big{(}\Delta_{t_{k}}g(\Phi({\bar{x}}))(u^{k})-\langle
y^{k},u^{k}\rangle\big{)}=\Delta_{t_{k}}^{2}g(\Phi(\bar{x}),y^{k})(u^{k})<\kappa+\frac{1}{k}-\alpha_{k},$

which implies that

$\liminf_{k\to\infty}\frac{2}{t_{k}}\big{(}\Delta_{t_{k}}g(\Phi({\bar{x}}))(u^{k})-\langle
y^{k},u^{k}\rangle\big{)}<\infty.$

In particular, it holds that
$\liminf_{k\to\infty}\Delta_{t_{k}}g(\Phi({\bar{x}}))(u^{k})-\langle
y^{k},u^{k}\rangle\leq 0$. This, coupled with
$u^{k}\to\nabla\Phi({\bar{x}})w$, confirms that ${\rm
d}g(\Phi({\bar{x}}))(\nabla\Phi({\bar{x}})w)\leq\langle\bar{y},\nabla\Phi({\bar{x}})w\rangle$.
It follows from the convexity of $g$ and $\bar{y}\in\partial
g(\Phi({\bar{x}}))$ that the opposite inequality ${\rm
d}g(\Phi({\bar{x}}))(\nabla\Phi({\bar{x}})w)\geq\langle\bar{y},\nabla\Phi({\bar{x}})w\rangle$
always holds. Thus, we get $\nabla\Phi({\bar{x}})w\in
K_{g}(\Phi({\bar{x}}),\bar{y})$. Repeating the above arguments for the second-
order quotient of $\delta_{\Theta}$ at ${\bar{x}}$ for $-v^{k}$ and $w^{k}$
yields $w\in K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))$. Thus, it
results from the definition of ${\mathscr{D}}$ in (3.18) that
$w\in{\mathscr{D}}$. Observe again that (4.7) gives us the estimate

$\alpha_{k}+\Delta_{t_{k}}^{2}g(\Phi(\bar{x}),y^{k})(u^{k})+\Delta_{t_{k}}^{2}\delta_{\Theta}({\bar{x}},-v^{k})(w^{k})<\kappa+\frac{1}{k}.$

Passing to the limit, using (4.6), and remembering that
$u^{k}\to\nabla\Phi({\bar{x}})w$ demonstrate that

$\langle\nabla_{xx}^{2}L(\bar{x},\bar{y})w,w\rangle+\widehat{\rm
d}^{2}g(\Phi(\bar{x}),\bar{y})(\nabla\Phi({\bar{x}})w)+\widehat{\rm
d}^{2}\delta_{\Theta}\big{(}{\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y})\big{)}(w)\leq\kappa.$
(4.8)

Since $\Theta$ is a polyhedral convex set, $\delta_{\Theta}$ is CPLQ. By
Example 4.3, the second subderivative of $\delta_{\Theta}$ is semi-stable at
${\bar{x}}$ for $-\nabla_{x}L({\bar{x}},\bar{y})$. Moreover, (4.1) and $w\in
K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))$ imply that

$\widehat{\rm
d}^{2}\delta_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))(w)=\delta_{K_{\Theta}({\bar{x}},-\nabla_{x}L({\bar{x}},\bar{y}))}(w)=0,$

which, coupled with semi-stability of the second subderivative of $g$ at
$\Phi({\bar{x}})$ for $\bar{y}$, results in

$\langle\nabla_{xx}^{2}L(\bar{x},\bar{y})w,w\rangle+{\rm
d}^{2}g(\Phi(\bar{x}),\bar{y})(\nabla\Phi({\bar{x}})w)\leq\kappa,$

a contradiction with (4.4), since $\kappa\in[0,\ell)$, $\|w\|=1$, and
$w\in{\mathscr{D}}$. This completes the proof.

It is worth adding here that the SOSCs in (3.18) and (4.4) are equivalent.
This, in fact, results from the lower semicontinuity of the second
subderivative function ${\rm d}^{2}g(\Phi({\bar{x}}),\bar{y})$ therein, which
is due to [30, Propsoition 13.5]. Note that the proof of Theorem 4.7 is
inspired by that of [33, Theorem 3.4(b)], which was replicated in [19,
Proposition 3.3].

The uniform quadratic growth condition for augmented Lagrangian functions was
first established in [9, Proposition 3.1] for NLPs without appealing to the
concept of the second subderivative. It was generalized in [12, Theorem 4.3]
for the composite problem in (1.1) with the modeling function $g$ therein
being CPLQ via a different approach. It was recently generalized in [35,
Theorem 1] for SDPs when the multiplier $\bar{y}$ is taken from the relative
interior of the set of Lagrange multipliers. Theorem 4.7 goes far beyond these
frameworks and provides a relatively easy proof of this important result,
which is based on the new concept of semi-stability of second subderivatives,
introduced in this section. We should also add here that the uniform quadratic
growth condition in (4.5) implies the validity of the SOSC in (4.4) for some
$\ell>0$. This can be proven using Proposition 4.5. Since such a result will
not be used in our convergence analysis and since it requires calculation of
the second subderivative of the augmented Lagrangian function, we did not
state it in Theorem 4.7.

##  5 Local Convergence Analysis of ALM

After some preparations in Sections 3 and 4, we are ready to analyze the local
convergence of an inexact version of the ALM described below.

######  Algorithm 5.1 (ALM).

Choose $(x^{0},y^{0})\in{\bf X}\times{\bf Y}$, $\bar{\rho}>0$, and
$\hat{c}>0$. Pick a sequence $\\{{\rho_{k}}{\\}_{k\geq 0}}$ with
${\rho_{k}}\geq\bar{\rho}$ for all $k$ and a function $\epsilon:{\bf
R}_{+}\to{\bf R}_{+}$ satisfying $\epsilon(t)=o(t)$ and set $k:=0$. Then

  * (1)

if $({x^{k}},y^{k})$ satisfies a suitable termination criterion, stop;

  * (2)

otherwise, set $\epsilon_{k}:=\epsilon(r({x^{k}},{\lambda^{k}}))$ with the
residual function $r$ taken from (3.21) and choose the primal-dual update
$({x^{k+1}},y^{k+1})$ according to (1.5) and (2.9) such that

$\|{x^{k+1}}-{x^{k}}\|+\|y^{k+1}-y^{k}\|\leq\hat{c}\,r({x^{k}},y^{k});$ (5.1)

  * (3)

set $k\leftarrow k+1$ and go to Step 1.

The roadmap to ensure the convergence of the sequence
$\\{({x^{k}},y^{k}){\\}_{k\in{\rm I\\!N}}}$, constructed by Algorithm 5.1, was
already established in Theorem 2.1. To this end, we are going to demonstrate
that assumptions (a)-(c) in the latter result are satisfied under the same
assumptions utilized in Theorem 3.9. To begin, define the solution mapping
${\Upsilon}:{\bf X}\times{\bf Y}\to{\bf X}\times{\bf Y}$ to the canonical
perturbation of the generalized equation in (2.3) by

${\Upsilon}(v,w):=\big{\\{}(x,y)\in{\bf X}\times{\bf
Y}\,\big{|}\,(v,w)\in\Psi(x,y)+G(x,y)\big{\\}},\;\;(v,w)\in{\bf X}\times{\bf
Y},$ (5.2)

where $\Psi$ and $G$ are taken from (2.10). Observe that assumption (a) in
Theorem 2.1 requires that ${\Upsilon}$ enjoy a calmness property. Below, we
show that a certain calmness property of ${\Upsilon}$ is equivalent to the
error bound estimate in (3.22).

######  Proposition 5.2.

Let $({\bar{x}},\bar{y})$ be a solution to the KKT system in (2.2). Then, the
following properties are equivalent.

  1. (a)

There exist constants $\gamma>0$ and $\kappa\geq 0$ for which the error bound
estimate in (3.22) holds.

  2. (b)

There are positive constants $\delta^{\prime}$ and $\ell$ for which the
solution mapping ${\Upsilon}$ from (5.2) enjoys the calmness property

${\Upsilon}(v,w)\cap\mathbb{B}_{\delta^{\prime}}({\bar{x}},\bar{y})\subset\big{(}\\{{\bar{x}}\\}\times
M_{{\bar{x}},\psi}(0,0)\big{)}+\ell\,\|(v,w)\|\mathbb{B}\quad\mbox{for
all}\;\;(v,w)\in\delta^{\prime}\mathbb{B},$ (5.3)

where $M_{{\bar{x}},\psi}(0,0)$ is the set of Lagrange multipliers associated
with ${\bar{x}}$ and is defined by (3.19).

[Proof. ]The equivalence of (a) and (b) was established in [31, Proposition
3.8] for the composite problem in (1.1) with $g$ therein being CPLQ. A close
look into its proof, however, tells us that the latter assumption on $g$ was
not exploited and the given argument works for any convex function $g$.

We now proceed with an elaboration of assumption (b) in Theorem 2.1 for the
inexact ALM from Algorithm 5.1, which consists of two steps: (1) verifying the
solvability of the subproblem in (1.4) and (2) establishing an error bound
estimate for consecutive iterates of the ALM. We begin with solvability of
subproblems. This was already justified in [12, Propsoition 5.2] when the
convex function $g$ in (1.1) is CPLQ. The given proof therein did not utilize
such an assumption on $g$ and indeed works for any convex function $g$. Below,
we record this result and skip its proof.

######  Proposition 5.3.

Assume that $({\bar{x}},\bar{y})$ is a solution to the KKT system (2.2) such
that the SOSC in (4.4) hold at $({\bar{x}},\bar{y})$. Assume further that the
second subderivative of $g$ at $\Phi({\bar{x}})$ for $\bar{y}$ be semi-stable.
Take the positive constants $\gamma$ and $\bar{\rho}$ from Theorem 4.7. Then,
there exist positive constants $\hat{\ell}$ and $\hat{\gamma}\in(0,\gamma)$
such that for any $\rho\in[\bar{\rho},\infty)$, the optimal solution mapping
$S_{\rho}:{\bf Y}\rightrightarrows{\bf X}$, defined by

$S_{\rho}(y):=\operatorname*{arg\,min}\big{\\{}{\mathscr{L}}(x,y,\rho)\;\big{|}\;x\in\Theta\cap\mathbb{B}_{\hat{\gamma}}({\bar{x}})\big{\\}},\;\;y\in{\bf
Y},$ (5.4)

enjoys the uniform isolated calmness property

$S_{\rho}(y)\subset\\{{\bar{x}}\\}+\hat{\ell}\|y-\bar{y}\|\mathbb{B}$ (5.5)

and satisfies the inclusion $\emptyset\neq S_{\rho}(y)\subset{\rm
int}\,\mathbb{B}_{\hat{\gamma}}({\bar{x}})$ for all
$y\in\mathbb{B}_{\hat{\gamma}/(2\hat{\ell})}(\bar{y})$.

Next, we address the second property, required in assumption (b) in Theorem
2.1, which is an error bound estimate for consecutive terms of our inexact
ALM. While the proof of the result below mostly uses a similar argument in our
recent work in [12, Theorem 5.7], it differs from the proof of the latter
result in the second half part. In fact, some parts of the proof of [12,
Theorem 5.7] depend heavily on that fact that $g$ from (1.1) was assumed to be
CPLQ. In those parts, we proceed with a new idea, used recently in [35,
Proposition 5].

######  Proposition 5.4.

Assume that $({\bar{x}},\bar{y})$ is a solution to the KKT system in (2.2) for
which all the assumptions in Theorem 3.9 hold and that the second
subderivative of $g$ at $\Phi({\bar{x}})$ for $\bar{y}$ is semi-stable. Take
$\bar{\rho}$ from Theorem 4.7 and $\hat{\gamma}$ from Proposition 5.3. Then,
there exist positive constants $\hat{\varepsilon}$ and $\hat{c}$ such that for
any $\rho\geq\bar{\rho}$, any
$(x,y)\in\mathbb{B}_{\hat{\varepsilon}}({\bar{x}},\bar{y})$ satisfying
$r(x,y)>0$, and any optimal solution ${s}$ to the regularized problem

$\operatorname*{minimize\;}{\mathscr{L}}(u,y,\rho)\quad\mbox{subject to}\quad
u\in\Theta\cap\mathbb{B}_{\hat{\gamma}}({\bar{x}})$ (5.6)

the error bound estimate

$\|{s}-x\|+\|y_{s}-y\|\leq\hat{c}\,r(x,y)\quad\mbox{with}\;\;y_{s}:=y+\rho\nabla_{y}{\mathscr{L}}(s,y,\rho)$
(5.7)

holds, where the residual function $r$ is defined by (3.21).

[Proof. ]Since the SOSC in (3.18) holds, it follows from lower semicontinuity
of ${\rm d}^{2}g(\Phi(\bar{x}),\bar{y})$ therein (cf. [30, Proposition 13.5])
that there is a positive constant $\ell$ for which the SOSC in (4.4) is
satisfied. By Theorem 4.7, we find positive constants $\bar{\rho}$, $\gamma$,
and $\kappa$ for which the uniform quadratic growth condition in (4.5) holds
for all $x\in\Theta\cap\mathbb{B}_{\gamma}({\bar{x}})$, all $y\in
M_{{\bar{x}},\psi}(0,0)\cap\mathbb{B}_{\gamma}(\bar{y})$, and all
$\rho\geq\bar{\rho}$. According to Proposition 5.3, the solution mapping
$S_{\rho}$ enjoys the uniform isolated calmness property in (5.5) and
$S_{\rho}(\tilde{y})\subset{\rm int}\,\mathbb{B}_{\hat{\gamma}}({\bar{x}})$
for all $\tilde{y}\in\mathbb{B}_{\hat{\gamma}/(2\hat{\ell})}(\bar{y})$ and all
$\rho\geq\bar{\rho}$, where both positive constants $\hat{\ell}$ and
$\hat{\gamma}$ are taken from this proposition. Thus, for every
$\tilde{y}\in\mathbb{B}_{\hat{\gamma}/(2\hat{\ell})}(\bar{y})$ and every
$\rho\geq\bar{\rho}$, any optimal solution ${s}$ to (5.6) satisfies the first-
order optimality condition

$0\in\nabla_{x}{\mathscr{L}}({s},\tilde{y},\rho)+N_{\Theta}({s}).$ (5.8)

To justify (5.7), assume by contradiction that it does not hold. Thus, we find
a sequence $\\{({x^{k}},y^{k},{\rho_{k}}){\\}_{k\in{\rm I\\!N}}}\subset{\bf
X}\times{\bf Y}\times[\bar{\rho},\infty)$ with
$({x^{k}},y^{k})\to({\bar{x}},\bar{y})$ and an optimal solution ${s}^{k}$ to
(5.6) associated with $(y,\rho)=(y^{k},{\rho_{k}})$ such that

$\|{s}^{k}-{x^{k}}\|+\|q^{k}-y^{k}\|>k\,r_{k}\quad\mbox{with}\;\;q^{k}:=y^{k}+{\rho_{k}}\nabla_{y}{\mathscr{L}}(s^{k},y^{k},{\rho_{k}}),$
(5.9)

where $r_{k}:=r({x^{k}},y^{k})>0$. The latter particularly tells us that
$r_{k}$ is finite, which yields ${x^{k}}\in\Theta$ for all $k$ due to (3.21).
Denoting by $\beta_{k}$ the left-hand side of (5.9), we get
$r_{k}=o(\beta_{k})$. The definition of the residual function $r$ in (3.21)
then leads us to

$-\nabla_{x}L({x^{k}},y^{k})+o({\beta_{k}})\in
N_{\Theta}({x^{k}})\quad\textrm{and}\quad\Phi({x^{k}})+o({\beta_{k}})={\rm{prox}}_{g}\big{(}\Phi({x^{k}})+y^{k}\big{)}.$
(5.10)

Using the definition of $\beta_{k}$ and passing to a subsequence, if
necessary, we can find $(\zeta,\eta)\in{\bf X}\times{\bf Y}$ such that

$\dfrac{{s}^{k}-{x^{k}}}{{\beta_{k}}}\to\zeta\quad\mbox{and}\quad\dfrac{q^{k}-y^{k}}{{\beta_{k}}}\to\eta\quad\mbox{with}\;\;(\zeta,\eta)\neq
0.$ (5.11)

Since the set of Lagrange multiplier $M_{{\bar{x}},\psi}(0,0)$ from (3.19) is
convex and closed, $P_{M_{{\bar{x}},\psi}(0,0))}(y^{k})$ exists and is a
singleton. Set $\tilde{y}^{k}:=P_{M_{{\bar{x}},\psi}(0,0))}(y^{k})$. By
Theorem 3.9, the estimate in (3.22) is satisfied, which allows us to conclude
that ${x^{k}}-{\bar{x}}=O(r_{k})$ and $y^{k}-\tilde{y}^{k}=O(r_{k})$ for all
$k$ sufficiently large. Thus, we have

${x^{k}}-{\bar{x}}=o({\beta_{k}})\quad\textrm{and}\quad
y^{k}-\tilde{y}^{k}=o({\beta_{k}})\quad\textrm{as }k\to\infty,$ (5.12)

which together with $y^{k}\to\bar{y}$ yields $\tilde{y}^{k}\to\bar{y}$ and
hence $\tilde{y}^{k}\in
M_{{\bar{x}},\psi}(0,0)\cap\mathbb{B}_{\gamma}(\bar{y})$ for all $k$
sufficiently large. Combining the latter with
${s}^{k}\in\Theta\cap\mathbb{B}_{\gamma}({\bar{x}})$,
$\rho_{k}\geq\bar{\rho}$, and (4.5) brings us to

$\displaystyle\|{s}^{k}-{\bar{x}}\|^{2}$
$\displaystyle\leq\frac{2}{\kappa}\big{(}{\mathscr{L}}({s}^{k},\tilde{y}^{k},{\rho_{k}})-{\mathscr{L}}({\bar{x}},\tilde{y}^{k},{\rho_{k}})\big{)}$
$\displaystyle\leq\frac{2}{\kappa}\big{(}{\mathscr{L}}({s}^{k},y^{k},{\rho_{k}})+\langle\nabla_{y}{\mathscr{L}}({s}^{k},y^{k},{\rho_{k}}),\tilde{y}^{k}-y^{k}\rangle-{\mathscr{L}}({\bar{x}},\tilde{y}^{k},{\rho_{k}})\big{)},$

where the last inequality results from the fact that the mapping
$y\mapsto{\mathscr{L}}({s}^{k},y,{\rho_{k}})$ is ${\cal C}^{1}$ and concave;
see [30, Exercise 11.56]. Since ${s}^{k}\in S_{\rho_{k}}(y^{k})$, we can
conclude from the definition of the augmented Lagrangian function in (1.2)
that

${\mathscr{L}}({s}^{k},y^{k},{\rho_{k}})\leq{\mathscr{L}}({\bar{x}},y^{k},{\rho_{k}})\leq\varphi({\bar{x}})+g(\Phi({\bar{x}}))={\mathscr{L}}({\bar{x}},\tilde{y}^{k},{\rho_{k}}),$

where the equality comes from Proposition 2.2(a) and $\tilde{y}^{k}\in
M_{{\bar{x}},\psi}(0,0)$. Combining the last two estimates and using then
(5.9) lead us to

$\|{s}^{k}-{\bar{x}}\|^{2}\leq\frac{2}{\kappa\rho_{k}}\langle
q^{k}-y^{k},\tilde{y}^{k}-y^{k}\rangle\leq\dfrac{2}{\kappa{\rho_{k}}}\|q^{k}-y^{k}\|\cdot\|\tilde{y}^{k}-y^{k}\|.$
(5.13)

Claim I. We have ${s}^{k}-{\bar{x}}=o(\beta_{k})$,
${\rho_{k}}\|{s}^{k}-{\bar{x}}\|^{2}=o(\beta_{k})$, and
${\rho_{k}}\|{s}^{k}-{\bar{x}}\|^{2}=o(\beta_{k}^{2})$.

To prove the first estimate, we use (5.13) together with (5.11)-(5.12) and
${\rho_{k}}\geq\bar{\rho}$ to obtain

$\dfrac{\|{s}^{k}-{\bar{x}}\|^{2}}{{\beta_{k}}^{2}}\leq\dfrac{2}{\kappa{\rho_{k}}}\dfrac{\|q^{k}-y^{k}\|}{{\beta_{k}}}\cdot\frac{\|\tilde{y}^{k}-y^{k}\|}{{\beta_{k}}}\leq\dfrac{2}{\kappa\bar{\rho}}\dfrac{\|q^{k}-y^{k}\|}{{\beta_{k}}}\cdot\frac{\|\tilde{y}^{k}-y^{k}\|}{{\beta_{k}}}\to
0.$

The remaining estimates can be verified by a similar argument via
(5.11)-(5.13).
Claim II. We have $s^{k}\to{\bar{x}}$ as $k\to\infty$.

To prove this claim, we infer from $\tilde{y}^{k}\in M_{{\bar{x}},\psi}(0,0)$
that $\tilde{y}^{k}\in\partial g(\Phi({\bar{x}}))$, and hence
$\Phi({\bar{x}})={\rm{prox}}_{\rho^{-1}{g}}\big{(}\Phi({\bar{x}})+\rho^{-1}\tilde{y}^{k}\big{)}$
for any $\rho>0$ due to (2.8). Thus, we derive from (5.9), (5.13), (2.12), and
${\rho_{k}}\geq\bar{\rho}$ that

$\displaystyle\|{s}^{k}-{\bar{x}}\|^{2}$
$\displaystyle\leq\dfrac{2}{\kappa}\|\Phi({s}^{k})-{\rm{prox}}_{\rho_{k}^{-1}g}\big{(}\Phi({s}^{k})+\rho_{k}^{-1}y^{k}\big{)}\|\cdot\|\tilde{y}^{k}-y^{k}\|$
$\displaystyle=\frac{2}{\kappa}\big{\|}\Phi({s}^{k})-\Phi({\bar{x}})+{\rm{prox}}_{\rho_{k}^{-1}g}\big{(}\Phi({\bar{x}})+\rho_{k}^{-1}\tilde{y}^{k}\big{)}-{\rm{prox}}_{\rho_{k}^{-1}g}\big{(}\Phi({s}^{k})+\rho_{k}^{-1}y^{k}\big{)}\big{\|}\cdot\|\tilde{y}^{k}-y^{k}\|$
$\displaystyle\leq\frac{2}{\kappa}\big{(}2\|\Phi(s^{k})-\Phi({\bar{x}})\|+(\bar{\rho})^{-1}\|\tilde{y}^{k}-y^{k}\|\big{)}\|\tilde{y}^{k}-y^{k}\|$
$\displaystyle=\big{(}O(\|{s}^{k}-{\bar{x}}\|)+\tfrac{2}{\kappa}(\bar{\rho})^{-1}\|\tilde{y}^{k}-y^{k}\|\big{)}\|\tilde{y}^{k}-y^{k}\|,$
(5.14)

where the inequality is due to the fact that the proximal mapping
${\rm{prox}}_{\rho^{-1}{g}}$ is nonexpansive (cf. [30, Proposition 12.19]).
Since $\|s^{k}-{\bar{x}}\|$ is bounded and $\|y^{k}-\tilde{y}^{k}\|\to 0$, we
deduce from (5.14) that $\|{s}^{k}-{\bar{x}}\|\to 0$, which proves the claim.

To proceed, we use the first estimate in Claim I and (5.12) to get

$\zeta=\lim_{k\to\infty}\dfrac{{s}^{k}-{x^{k}}}{{\beta_{k}}}=\lim_{k\to\infty}\dfrac{s^{k}-{\bar{x}}}{{\beta_{k}}}-\lim_{k\to\infty}\dfrac{{x^{k}}-{\bar{x}}}{{\beta_{k}}}=0-0=0.$

Our goal is to show that $\eta=0$, which together with $\zeta=0$ leads us to a
contradiction with (5.11). To this end, we proceed with considering two cases.
Assume first that either $\\{{\rho_{k}}{\\}_{k\in{\rm I\\!N}}}$ or
$\\{{{\rho_{k}}}/{{\beta_{k}}}{\\}_{k\in{\rm I\\!N}}}$ is bounded. Using a
similar argument as the one for (5.14), we obtain via (5.9) and (2.12) that

$\displaystyle\dfrac{\|q^{k}-y^{k}\|}{{\beta_{k}}}=\frac{{\rho_{k}}}{{\beta_{k}}}\big{\|}\Phi({s}^{k})-{\rm{prox}}_{\rho_{k}^{-1}g}\big{(}\Phi({s}^{k})+\rho_{k}^{-1}y^{k}\big{)}\big{\|}\leq
O\big{(}\frac{{\rho_{k}}}{{\beta_{k}}}\|{s}^{k}-{\bar{x}}\|\big{)}+\dfrac{\|\tilde{y}^{k}-y^{k}\|}{{\beta_{k}}}.$

It also follows from $s^{k}-{\bar{x}}=o(\beta_{k})$ that
${{\rho_{k}}}\|{s}^{k}-{\bar{x}}\|/{\beta_{k}}\to 0$. Using this and (5.12)
and passing to the limit in the inequality above, we get $\eta=0$, a
contradiction with (5.11).

Assume now that both sequences $\\{{\rho_{k}}{\\}_{k\in{\rm I\\!N}}}$ and
$\\{{{\rho_{k}}}/{{\beta_{k}}}{\\}_{k\in{\rm I\\!N}}}$ are unbounded. We can
assume by passing to a subsequence if necessary that

${\rho_{k}}\to\infty\quad\mbox{and}\quad\frac{{\rho_{k}}}{\beta_{k}}\to\infty\;\;\mbox{as}\;\;k\to\infty.$
(5.15)

Since ${s}^{k}$ is an optimal solution to (5.6) associated with
$(y^{k},{\rho_{k}})$, we deduce from (5.8) that

$0\in\nabla_{x}{\mathscr{L}}({s}^{k},y^{k},{\rho_{k}})+N_{\Theta}({s}^{k})=\nabla\varphi({s}^{k})+\nabla\Phi({s}^{k})^{*}q^{k}+N_{\Theta}({s}^{k}),$

where the equality comes from (2.12) and the definition of $q^{k}$ from (5.9).
By the definition of the normal cone, we have

$\displaystyle 0\leq$
$\displaystyle\;\langle\nabla\varphi({s}^{k})+\nabla\Phi({s}^{k})^{*}q^{k},{\bar{x}}-s^{k}\rangle=\langle\nabla\varphi({s}^{k}),{\bar{x}}-s^{k}\rangle-\langle
q^{k},\nabla\Phi({s}^{k})(s^{k}-{\bar{x}})\rangle$ $\displaystyle=$
$\displaystyle\;\langle\nabla\varphi({s}^{k}),{\bar{x}}-s^{k}\rangle-\langle
q^{k},\nabla\Phi({\bar{x}})(s^{k}-{\bar{x}})\rangle-\langle
q^{k},(\nabla\Phi(s^{k})-\nabla\Phi({\bar{x}}))(s^{k}-{\bar{x}})\rangle.$
(5.16)

Recall also that $\tilde{y}^{k}\in M_{{\bar{x}},\psi}(0,0)$. By (3.19), the
latter implies that $\tilde{y}^{k}\in\partial g(\Phi({\bar{x}}))$ and

$0\in\nabla_{x}L({\bar{x}},\tilde{y}^{k})+N_{\Theta}({\bar{x}})=\nabla\varphi({\bar{x}})+\nabla\Phi({\bar{x}})^{*}\tilde{y}^{k}+N_{\Theta}({\bar{x}}).$

Again, the definition of the normal cone leads us to

$\displaystyle 0$
$\displaystyle\leq\langle\nabla\varphi({\bar{x}})+\nabla\Phi({\bar{x}})^{*}\tilde{y}^{k},s^{k}-{\bar{x}}\rangle=\langle\nabla\varphi({\bar{x}}),s^{k}-{\bar{x}}\rangle+\langle\tilde{y}^{k},\nabla\Phi({\bar{x}})(s^{k}-{\bar{x}})\rangle.$
(5.17)

Adding both sides of (5.16) and (5.17) brings us to

$\displaystyle\langle
q^{k}-\tilde{y}^{k},\nabla\Phi({\bar{x}})(s^{k}-{\bar{x}})\rangle$
$\displaystyle\leq-\langle\nabla\varphi(s^{k})-\nabla\varphi({\bar{x}}),s^{k}-{\bar{x}}\rangle-\langle
q^{k},(\nabla\Phi(s^{k})-\nabla\Phi({\bar{x}}))(s^{k}-{\bar{x}})\rangle$
$\displaystyle\leq(1+\|q^{k}\|)O(\|s^{k}-{\bar{x}}\|^{2}).$ (5.18)

On the other hand, it follows from (2.9) and the definition of $q^{k}$ in
(5.9) that $q^{k}\in\partial g(z^{k})$ where
$z^{k}:=\Phi({s}^{k})-\rho_{k}^{-1}(q^{k}-y^{k})$. Recall that
$\tilde{y}^{k}\in\partial g(\Phi({\bar{x}}))$. Thus, we get from the
monotonicity of $\partial g$ that

$\displaystyle 0\leq$ $\displaystyle\;\langle
q^{k}-\tilde{y}^{k},\Phi(s^{k})-\rho_{k}^{-1}(q^{k}-y^{k})-\Phi({\bar{x}})\rangle$
$\displaystyle=$ $\displaystyle\;\langle
q^{k}-\tilde{y}^{k},\nabla\Phi({\bar{x}})(s^{k}-{\bar{x}})+O(\|s^{k}-{\bar{x}}\|^{2})-\rho_{k}^{-1}(q^{k}-y^{k})\rangle$
$\displaystyle\leq$ $\displaystyle\;\langle
q^{k}-\tilde{y}^{k},\nabla\Phi({\bar{x}})(s^{k}-{\bar{x}})\rangle-\rho_{k}^{-1}\|q^{k}-y^{k}\|^{2}$
$\displaystyle+\|q^{k}-\tilde{y}^{k}\|O(\|s^{k}-{\bar{x}}\|^{2})+{\rho_{k}}^{-1}\|y^{k}-\tilde{y}^{k}\|\cdot\|q^{k}-y^{k}\|.$
(5.19)

Combining (5.18) and (5.19) brings us to

$\displaystyle\|q^{k}-y^{k}\|^{2}\leq$
$\displaystyle\;{\rho_{k}}(1+\|q^{k}\|+\|q^{k}-\tilde{y}^{k}\|)O(\|s^{k}-{\bar{x}}\|^{2})+\|y^{k}-\tilde{y}^{k}\|\cdot\|q^{k}-y^{k}\|$
$\displaystyle\leq$
$\displaystyle\;(1+\|y^{k}\|)O({\rho_{k}}\|s^{k}-{\bar{x}}\|^{2})+(2\|q^{k}-y^{k}\|+\|y^{k}-\tilde{y}^{k}\|)O({\rho_{k}}\|s^{k}-{\bar{x}}\|^{2})$
$\displaystyle+\|y^{k}-\tilde{y}^{k}\|\cdot\|q^{k}-y^{k}\|$ $\displaystyle=$
$\displaystyle\;o(\beta_{k}^{2})+O(\beta_{k})o(\beta_{k})+o(\beta_{k})O(\beta_{k})=o(\beta_{k}^{2}),$

where the last estimate comes from Claim I, (5.11), (5.12), and boundedness of
the sequence $\\{y^{k}\\}$. Dividing both sides by $\beta_{k}^{2}$ and passing
then to the limit tell us via (5.11) that $\|\eta\|^{2}=0$, implying that
$\eta=0$. This is a contradiction with $(\zeta,\eta)\neq(0,0)$ and thus
completes the proof.

To finish our discussion about assumption (b) in Theorem 2.1, we should point
out that one more step is required to be taken. Comparing the right-hand side
of (5.7) with the estimate in assumption (b) indicates that the residual
function $r$ in (5.7) should be replaced with the distance function to the
solution set of the KKT system in (2.2). That requires to assume that $\Theta$
in (1.1) be an affine set, as recorded below.

######  Proposition 5.5.

Assume that $({\bar{x}},\bar{y})$ is a solution to the KKT system (2.2) with
$\Theta$ therein being an affine set. Then there exist a positive constant
$\kappa$ and a neighborhood $U$ of $({\bar{x}},\bar{y})$ such that

$r(x,\lambda)\leq\kappa\big{(}\|x-{\bar{x}}\|+{\rm
dist}(y,M_{{\bar{x}},\psi}(0,0)))\big{)}\quad\textrm{for all }\;\;(x,y)\in U,$
(5.20)

where $M_{{\bar{x}},\psi}(0,0)$ is defined in (3.19).

[Proof. ]The claimed estimate was recently justified for the KKT system in
(2.2) with $g$ being CPLQ. Its proof, however, did not use the latter
condition on $g$ and works for any convex function $g$. Thus, we omit the
proof and refer the readers to the latter result.

What remains is to show that assumption (c) of Theorem 2.1 holds automatically
for the inexact ALM proposed in Algorithm 5.1. That will be done inside the
proof of the next result in which we establish the wellposedness and local
convergence of our inexact ALM.

######  Theorem 5.6.

Assume that $({\bar{x}},\bar{y})$ is a solution to the KKT system in (2.2) for
which all the assumptions in Theorem 3.9 hold and that $\Theta$ in (1.1) is an
affine set. Assume further that the second subderivative of $g$ at
$\Phi({\bar{x}})$ for $\bar{y}$ is semi-stable. Then, there exist positive
constants $\hat{c},\,\bar{\rho}$, and $\varepsilon_{0}$ such that for any
starting point
$(x^{0},y^{0})\in\mathbb{B}_{\varepsilon_{0}}({\bar{x}},\bar{y})$ and any
sequence $\\{{\rho_{k}}\\}_{k\in{\rm I\\!N}}$ with ${\rho_{k}}\geq\bar{\rho}$,
there is a primal-dual sequence $\\{({x^{k}},y^{k})\\}_{k\in{\rm I\\!N}}$
satisfying (1.5) with ${\epsilon_{k}}=o(r({x^{k}},y^{k}))$ and the estimate
(5.1), where $r$ is the residual function defined by (3.21). Moreover, any
such a sequence converges to $({\bar{x}},\widehat{y})$ for some
$\widehat{y}\in M_{{\bar{x}},\psi}(0,0)$, and the rates of convergence of
$\\{({x^{k}},y^{k}){\\}_{k\in{\rm I\\!N}}}$ to $({\bar{x}},\widehat{y})$ and
of $\\{{\rm dist}\big{(}({x^{k}},y^{k}),\\{{\bar{x}}\\}\times
M_{{\bar{x}},\psi}(0,0)\big{)}{\\}_{k\in{\rm I\\!N}}}$ to zero are Q-linear.
Furthermore, if ${\rho_{k}}\to\infty$, the rates of convergence of both
sequences are Q-superlinear.

[Proof. ]To justify the claims, we need to show that assumptions (a)-(c) in
Theorem 2.1 are satisfied. We begin with assumption (a), namely the calmness
of the solution mapping ${\Upsilon}$ from (5.2) at $(0,0)$ for
$({\bar{x}},\bar{y})$. To achieve it, observe from Theorem 3.9 that the error-
bound estimate in (3.22) holds. Take the neighborhood $U$ of
$({\bar{x}},\bar{y})$ from (3.22) and choose $\delta>0$ such that
$\mathbb{B}_{\delta}({\bar{x}},\bar{y})\subset U$. By (3.22), we get

${\Upsilon}(0,0)\cap\mathbb{B}_{\delta}({\bar{x}},\bar{y})=\big{(}\\{{\bar{x}}\\}\times
M_{{\bar{x}},\psi}(0,0)\big{)}\cap\mathbb{B}_{\delta}({\bar{x}},\bar{y}).$
(5.21)

Moreover, it follows from Proposition 5.2 that there are positive constants
$\delta^{\prime}$ and $\ell$ for which (5.3) holds. Shrinking
$\delta^{\prime}$ if necessary, we can assume that
$\max\\{\delta^{\prime},\ell\delta^{\prime}\\}\leq\delta/2$. Thus, it results
from (5.3) that

$\displaystyle{\Upsilon}(v,w)\cap\mathbb{B}_{\delta^{\prime}}({\bar{x}},\bar{y})$
$\displaystyle\subset\Big{(}\big{(}\\{{\bar{x}}\\}\times
M_{{\bar{x}},\psi}(0,0)\big{)}+\ell\,\|(v,w)\|\mathbb{B}\Big{)}\cap\mathbb{B}_{\delta/2}({\bar{x}},\bar{y})$
$\displaystyle\subset(\big{(}\\{{\bar{x}}\\}\times
M_{{\bar{x}},\psi}(0,0)\big{)}\cap\mathbb{B}_{\delta}({\bar{x}},\bar{y})+\ell\,\|(v,w)\|\mathbb{B}$
$\displaystyle={\Upsilon}(0,0)\cap\mathbb{B}_{\delta}({\bar{x}},\bar{y})+\ell\,\|(v,w)\|\mathbb{B}\subset{\Upsilon}(0,0)+\ell\,\|(v,w)\|\mathbb{B},$

for all $(v,w)\in\delta^{\prime}\mathbb{B}$, which confirms the calmness of
${\Upsilon}$ at $(0,0)$ for $({\bar{x}},\bar{y})$.

We turn next to assumption (b) in Theorem 2.1. Take the positive constants
$\hat{\varepsilon}$ and $\hat{c}$ from Proposition 5.4 and assume without loss
of generality that $\mathbb{B}_{\hat{\varepsilon}}({\bar{x}},\bar{y})\subset
U$ and $\hat{\varepsilon}\leq 2\delta$, where $U$ is taken from (5.20) and
$\delta$ comes from (5.21). Combining now the estimates in (5.7) and (5.20)
implies that

$\displaystyle\|{s}-x\|+\|y_{s}-y\|\leq\hat{c}\,r(x,y)$
$\displaystyle\leq\hat{c}\kappa\big{(}\|x-{\bar{x}}\|+{\rm
dist}(y,M_{{\bar{x}},\psi}(0,0))\big{)}$ $\displaystyle\leq 2\hat{c}\kappa{\rm
dist}((x,y),\\{{\bar{x}}\\}\times M_{{\bar{x}},\psi}(0,0))$

for all $(x,y)\in\mathbb{B}_{\hat{\varepsilon}}({\bar{x}},\bar{y})$ such that
$r(x,y)>0$. If $(x,y)\in\mathbb{B}_{\hat{\varepsilon}}({\bar{x}},\bar{y})$ and
$r(x,y)=0$, one can set $s:=x$, $y_{s}:=y$ and observes that $(s,y_{s})$ is a
solution to the KKT system in (2.2). It then follows from Proposition 2.2(b)
that $s$ and $y_{s}$ satisfy (1.5) and (2.9), respectively. Combining this