Consistent Approximations in Composite Optimization Johannes O. Royset
Operations Research Department Naval Postgraduate School<EMAIL_ADDRESS>
Abstract. Approximations of optimization problems arise in computational
procedures and sensitivity analysis. The resulting effect on solutions can be
significant, with even small approximations of components of a problem
translating into large errors in the solutions. We specify conditions under
which approximations are well behaved in the sense of minimizers, stationary
points, and level-sets and this leads to a framework of consistent
approximations. The framework is developed for a broad class of composite
problems, which are neither convex nor smooth. We demonstrate the framework
using examples from stochastic optimization, neural-network based machine
learning, distributionally robust optimization, penalty and augmented
Lagrangian methods, interior-point methods, homotopy methods, smoothing
methods, extended nonlinear programming, difference-of-convex programming, and
multi-objective optimization. An enhanced proximal method illustrates the
algorithmic possibilities. A quantitative analysis supplements the development
by furnishing rates of convergence.

Keywords: set-convergence, epi-convergence, graphical convergence,
approximation theory.
---
Date:

##  1 Introduction

A fundamental approach to optimization is to replace an actual problem by an
approximating one, which is then solved using an existing algorithm. In
sensitivity analysis, the actual problem of interest is also replaced by
approximating ones for the purpose of identifying the effect of perturbations.
These situations raise the questions: If some portion of an optimization
problem is changed and the resulting problem is solved, would the obtained
solution be a reasonable approximation of a solution of the actual problem?
How large would the solution error be relative to the magnitude of the initial
change? These questions are further complicated by the need for considering
both optimal and stationary points in the nonconvex setting. Thus, we aspire
to construct approximations that have minimizers and stationary points near
the corresponding points for the actual problem. We may even seek
approximating objective functions and feasible sets that are near those of the
actual problem in a broad sense.

In this paper, we provide a comprehensive framework for constructing and
analyzing approximations of optimization problems with a composite structure.
We provide sufficient conditions for consistent approximations, which
guarantee that the approximating problems eventually become accurate relative
to the actual problem in the sense of minimizers, stationary points, and
level-sets. Examples from stochastic optimization, neural-network based
machine learning, distributionally robust optimization, penalty and augmented
Lagrangian methods, interior-point methods, homotopy methods, smoothing
methods, extended nonlinear programming, difference-of-convex programming, and
multi-objective optimization demonstrate the framework. The algorithmic
possibilities are illustrated by a proximal composite method for solving an
array of nonconvex composite problems via a sequence of convex problems. A
quantitative analysis supplements the development by furnishing rates of
convergence.

We consider the broad class of composite optimization problems in the form

$\mathop{\rm
minimize}_{x\in\mathbb{R}^{n}}~{}\varphi(x)=\iota_{X}(x)+h\big{(}F(x)\big{)},$
(1.1)

where the objective function
$\varphi:\mathbb{R}^{n}\to\overline{\mathbb{R}}=\mathbb{R}\cup\\{-\infty,\infty\\}$
is defined in terms of a nonempty closed set $X\subset\mathbb{R}^{n}$, often
representing “basic” constraints such as bounds on the variables, and a
locally Lipschitz continuous mapping $F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ that
models $m$ quantities of interest with $f_{1},\dots,f_{m}$ being the component
functions, i.e., $F(x)=(f_{1}(x),\dots,f_{m}(x))$. For any set $C$,
$\iota_{C}(x)=0$ if $x\in C$ and $\iota_{C}(x)=\infty$ otherwise. The
quantities of interest are combined by a convex function
$h:\mathbb{R}^{m}\to\overline{\mathbb{R}}$, which might assign an infinite
penalty to certain values of $F(x)$. For example, $h=\iota_{\\{0\\}^{m}}$ sets
$h(F(x))=\infty$ whenever $F(x)$ deviates from the zero vector and thus
encodes the equality constraint $F(x)=0$. The actual problem (1.1) captures
classical nonlinear programming as well as many other problem formulations. In
general, $\varphi$ is nonconvex. The convexity assumption imposed on $h$ is
not as restrictive as it might appear and helps us to leverage convexity
properties when present.

The study of (1.1) and similar problems goes at least back to [45, 46]. Recent
efforts [35, 11, 21, 23, 17, 18, 22, 13] suggest that the problem class might
be among the most important ones in the nonconvex setting. Its structural
properties are theoretically and computationally attractive, especially to
address large-scale problems in machine learning and elsewhere. Nevertheless,
the actual problem may not be solvable directly and often needs
approximations. The mapping $F$ may be approximated by a smooth or even an
affine mapping. It might be specified by integrals, suprema, or other
expressions that necessitate imprecise, numerical evaluation. The function $h$
could be nonsmooth and extended real-valued, and then approximated by real-
valued functions, piecewise affine or smooth, acting as penalties. The set $X$
might be approximated by a polyhedron or other simplifications. The
approximations can be computationally motivated or introduced as part of
sensitivity, stability, or error analysis.

Our approach is traced back to 1902 when P. Painlevé defined set-convergence.
It is now well-known that set-convergence of epigraphs (i.e., epi-convergence)
of approximating functions and set-convergence of graphs (i.e., graphical
convergence) of approximating set-valued mappings furnish the desired
convergence guarantees about the solutions of the corresponding minimization
problems and generalized equations; see [50, Chap. 4, 5, and 7]. If the set-
valued mappings represent optimality conditions for the approximating
problems, then graphical convergence translates into convergence of stationary
points. We define approximating problems and their optimality conditions as
being consistent approximations of the actual problem (1.1), paired with an
optimality condition, when they exhibit such epi-convergence and graphical
convergence.

In the convex setting, epi-convergence of approximating functions
$\varphi^{\nu}$ to the actual objective function $\varphi$ suffices for the
subgradient mappings $\partial\varphi^{\nu}$ to graphically converge to
$\partial\varphi$ by Attouch’s theorem; see for example [50, Thm. 12.35].
Thus, epi-convergence of the approximating functions ensures that the
approximations are consistent. In the nonconvex case, one explicitly needs to
impose conditions related to the optimality conditions to guarantee
convergence of stationary points and this is recognized by the added
requirement about graphical convergence of set-valued mappings in the
definition of consistent approximations. If the approximating functions
$\varphi^{\nu}$ are smooth, their epi-convergence to $\varphi$ does provide
some relation between $\nabla\varphi^{\nu}$ and $\partial\varphi$ but in a
less-than-ideal “outer” sense; cf. [10, Lem. 3.4] and [50, Cor. 8.47]. A far-
reaching extension of Attouch’s theorem for nonconvex functions is provided by
[44], which implies in the context of (1.1) that epi-convergence of certain
approximating functions $h^{\nu}$ to $h$ combined with a smooth $F$ and a
constraint qualification suffice for graphical convergence in a local sense of
the resulting subgradient mappings [11].

Approximations of (1.1) may stem from the smoothing of $h$ and/or $F$. The
specific function $\gamma\mapsto\max\\{0,\gamma\\}$ can be approximated by
smooth functions via convolution [15]. The approximations exhibit both epi-
convergence as well as certain convergence of gradients to the subgradients of
the max-function [14]; the reference includes many examples of such smoothing.
This approach is closely related to mollifiers, which may even approximate
discontinuous functions [25]. Further developments in these directions are
furnished by [10, 11], where in the context of (1.1), $h$ is approximated by a
smooth function constructed using inf-convolution; see also [12] for details
about smoothing of finite max-functions. For approximations of a weakly convex
expectation function caused by sample averages, [19] gives rates by which
subdifferentials of the approximating functions graphically converge to the
subdifferential of the expectation function.

In contrast to these efforts, we consider broad sets of approximations; $X$,
$h$, and $F$ in (1.1) may all be approximated and not necessarily smoothly. In
sensitivity and error analysis, nonsmooth approximations are especially
relevant as computational concerns tend to be secondary. We also deviate from
the focus on the subgradient mapping of $\varphi$ and that of its
approximations, and instead express optimality conditions using (generalized)
multipliers, which provide additional flexibility for absorbing inaccuracies.
Thus, consistent approximations emerge as widely available under mild
assumptions. As compared to [19] specifically, we consider a broader range of
approximations beyond sample averages and also do not rely on weak convexity.
While $\varphi$ is weakly convex when $X=\mathbb{R}^{n}$, $h$ is real-valued,
convex, and Lipschitz continuous, and $F$ is continuously differentiable with
Lipschitz continuous Jacobian, we emphasize situations with a nontrivial $X$,
even nonconvex, an extended real-valued $h$, and nonsmooth $F$.

There is an extensive literature on general approximations and related
stability analysis; see the monographs [42, 50, 7, 37, 16] as well as efforts
based on metric regularity and calmness [31, 40], tilt-stability [24, 36, 20],
full-stability [38], convergence of abstract iteration schemes [32], and the
truncated Hausdorff distance [1, 2, 3, 52, 53]. The latter approach is closely
related to the present paper, with direct relevance to our rate of convergence
analysis.

Our choice of the term “consistent approximations” is motivated by E. Polak’s
concept in [42, Chap. 3-4]. There epi-convergence of approximating objective
functions combined with an outer epi-limit of approximating optimality
functions (after a sign change) are defined as consistent; see [51, 54, 27,
41, 55] for applications in stochastic optimization, semi-infinite
programming, nonsmooth optimization, and optimal control. Since optimality
functions are essentially gap-functions of generalized equations representing
optimality conditions, Polak’s concept is, roughly, equivalent to weak
consistency as we define it below. A related concept based on epigraphical
nesting of directional derivatives is defined in [29]. We deviate from these
earlier developments by viewing optimality conditions as generalized equations
defined by set-valued mappings and thus bypass the need for defining
optimality functions. This brings into play well-developed calculus rules and
computational procedures for generalized equations. The flexibility of this
approach is demonstrated by a set of sufficient conditions for consistency
(Theorem 2.4). An introductory treatment of consistent approximations under
the assumption of a smooth mapping $F$ is, in parallel, provided by the
textbook [56]. While we limit the discussion to finite-dimensional problems,
many of the concepts can be extended; see [41, 34] for such efforts.

We continue in Section 2 by stating the approximating problems, defining
consistency, and specifying sufficient conditions. Section 3 furnishes 12
examples. Section 4 describes a specific algorithm. Section 5 applies the
framework to machine learning problems. Section 6 discusses rates of
convergence.

Terminology. A ball under norm $\|\cdot\|$ is denoted by
$\mathbb{B}(\bar{x},\rho)=\\{x\in\mathbb{R}^{n}~{}|~{}\|x-\bar{x}\|\leq\rho\\}$.
A function $f:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ has a domain
$\operatorname{dom}f=\\{x\in\mathbb{R}^{n}~{}|~{}f(x)<\infty\\}$ and an
epigraph
$\operatorname{epi}f=\\{(x,\alpha)\in\mathbb{R}^{n+1}~{}|~{}f(x)\leq\alpha\\}$.
The function is lower semicontinuous (lsc) if $\operatorname{epi}f$ is closed
and is convex if $\operatorname{epi}f$ is convex. It is proper if
$\operatorname{epi}f$ is nonempty and $f(x)>-\infty$ for all
$x\in\mathbb{R}^{n}$. It is continuous relative to $C\subset\mathbb{R}^{n}$ if
$x^{\nu}\in C\to x\in C$ implies that $f(x^{\nu})\to f(x)$. It is locally
Lipschitz continuous (lLc) at $\bar{x}$ when there are $\delta\in(0,\infty)$
and $\kappa\in[0,\infty)$ such that
$|f(x)-f(x^{\prime})|\leq\kappa\|x-x^{\prime}\|_{2}$ whenever
$x,x^{\prime}\in\mathbb{B}(\bar{x},\delta)$. If $f$ is lLc at every
$\bar{x}\in\mathbb{R}^{n}$, then $f$ is lLc. A mapping
$F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is lLc (at $\bar{x}$) if its component
functions $f_{1},\dots,f_{m}$ are lLc (at $\bar{x}$). Functions and mappings
are smooth (at $\bar{x}$) if they are continuously differentiable (at
$\bar{x}$). Moreover, $\inf f=\inf\\{f(x)~{}|~{}x\in\mathbb{R}^{n}\\}$ and
$\varepsilon\mbox{-}\mathop{\rm argmin}\nolimits
f=\\{x\in\operatorname{dom}f~{}|~{}f(x)\leq\inf f+\varepsilon\\}$, which is
simply written as $\mathop{\rm argmin}\nolimits f$ if $\varepsilon=0$. A lower
level-set $\\{f\leq\alpha\\}=\\{x\in\mathbb{R}^{n}~{}|~{}f(x)\leq\alpha\\}$.
The convex hull of a set $C$ is denoted by $\operatorname{con}C$. The $j$th
component of a vector $x\in\mathbb{R}^{n}$ is typically indicated by $x_{j}$.
We let $\operatorname{bdry}C$ be the boundary111We exclude points in the
closure of $C$ that are not in $C$, which is most natural in the present
context. of a set $C\subset\mathbb{R}^{n}$, i.e.,
$\operatorname{bdry}C=C\setminus\operatorname{int}C$, where
$\operatorname{int}C$ is the interior of $C$. We adopt the usual rules for
extended arithmetic, including $\infty-\infty=\infty$.

Sequences of points, sets, and so forth are usually indexed by superscript
$\nu\in\mathbb{N}=\\{1,2,\dots\\}$. The collection of subsequences of
$\mathbb{N}$ is denoted by ${\cal N}_{\infty}^{\scriptscriptstyle\\#}$, with
convergence of $\\{x^{\nu},\nu\in\mathbb{N}\\}$ to $x$ along a subsequence
$N\in{\cal N}_{\infty}^{\scriptscriptstyle\\#}$ being denoted by
$x^{\nu}\,{\raise 1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower
3.0pt\hbox{$\,\scriptstyle N$}}\hskip 7.0ptx$. The symbols $\exists$ and
$\forall$ mean “there exist” and “for all,” respectively. The inner limit of a
sequence of sets $\\{C^{\nu}\subset\mathbb{R}^{n},\nu\in\mathbb{N}\\}$ is
$\mathop{\rm LimInn}\nolimits C^{\nu}=\\{x\in\mathbb{R}^{n}~{}|~{}\exists
x^{\nu}\in C^{\nu}\to x\\}$. The outer limit is $\mathop{\rm LimOut}\nolimits
C^{\nu}=\\{x\in\mathbb{R}^{n}~{}|~{}\exists N\in{\cal
N}_{\infty}^{\scriptscriptstyle\\#}\mbox{ and }x^{\nu}\in C^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0ptx\\}$. Thus, $C^{\nu}$ set-converges to
$C\subset\mathbb{R}^{n}$, denoted by $C^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptC$, if $\mathop{\rm LimOut}\nolimits C^{\nu}\subset
C\subset\mathop{\rm LimInn}\nolimits C^{\nu}$. The functions
$\\{f^{\nu}:\mathbb{R}^{n}\to\overline{\mathbb{R}},\nu\in\mathbb{N}\\}$ epi-
converge to $f:\mathbb{R}^{n}\to\overline{\mathbb{R}}$, denoted by
$f^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0ptf$, if
$\operatorname{epi}f^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0pt\operatorname{epi}f$. This takes place if and only if

$\displaystyle\forall x^{\nu}\to x,~{}\mathop{\rm liminf}\nolimits
f^{\nu}(x^{\nu})\geq f(x)$ (1.2) $\displaystyle\forall x,~{}\exists x^{\nu}\to
x\mbox{ with }\mathop{\rm limsup}\nolimits f^{\nu}(x^{\nu})\leq f(x).$ (1.3)

A set-valued mapping $T:\mathbb{R}^{n}\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-12.0pt\hbox{\raise
2.5pt\hbox{$\rightarrow$}}\;\mathbb{R}^{m}$ has subsets of $\mathbb{R}^{m}$ as
its “values” and a graph written as
$\operatorname{gph}T=\\{(x,y)\in\mathbb{R}^{n+m}~{}|~{}y\in T(x)\\}$. A
sequence of set-valued mappings $\\{T^{\nu}:\mathbb{R}^{n}\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-12.0pt\hbox{\raise
2.5pt\hbox{$\rightarrow$}}\;\mathbb{R}^{m},\nu\in\mathbb{N}\\}$ converges
graphically to $T:\mathbb{R}^{n}\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-12.0pt\hbox{\raise
2.5pt\hbox{$\rightarrow$}}\;\mathbb{R}^{m}$, denoted by $T^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.5pt\hbox{$\,\scriptstyle
g$}}\hskip 7.0ptT$, if $\operatorname{gph}T^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0pt\operatorname{gph}T$. The set of solutions to the generalized
equation $v\in T(x)$ is written as $T^{-1}(v)=\\{x\in\mathbb{R}^{n}~{}|~{}v\in
T(x)\\}$.

We denote the normal cone to $C\subset\mathbb{R}^{n}$ at $x\in C$ by
$N_{C}(x)$ and let $N_{C}(x)=\emptyset$ for $x\not\in C$. Likewise, the set of
subgradients of $f:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ at a point $x$ with
$f(x)\in\mathbb{R}$ is $\partial f(x)$; $\partial f(x)=\emptyset$ when
$f(x)\not\in\mathbb{R}$. These quantities are understood in the general
(Mordukhovich) sense; see [50, Chap. 6 and 8].

##  2 Consistent Approximations

Parallel to the actual problem (1.1), we define the approximating problems

$\bigg{\\{}\mathop{\rm
minimize}_{x\in\mathbb{R}^{n}}~{}\varphi^{\nu}(x)=\iota_{X^{\nu}}(x)+h^{\nu}\big{(}F^{\nu}(x)\big{)},~{}~{}~{}~{}\nu\in\mathbb{N}\bigg{\\}}$
(2.1)

where $X^{\nu}\subset\mathbb{R}^{n}$,
$h^{\nu}:\mathbb{R}^{m}\to\overline{\mathbb{R}}$, and
$F^{\nu}:\mathbb{R}^{n}\to\mathbb{R}^{m}$ are approximations of the
corresponding components of the actual problem. We seek to confirm that small
discrepancies between the respective components of the approximating and
actual problems indeed translate into small errors in the solutions of the
approximating problems relative to those of the actual problem. It is clear
that pointwise convergence $\varphi^{\nu}(x)\to\varphi(x)$ for all
$x\in\mathbb{R}^{n}$ would not suffice; see [50, Figure 7-1]. Uniform
convergence of $\varphi^{\nu}$ to $\varphi$ on $\mathbb{R}^{n}$ ensures that
cluster points of $\\{x^{\nu}\in\mathop{\rm
argmin}\nolimits\varphi^{\nu},\nu\in\mathbb{N}\\}$ indeed are minimizers of
$\varphi$, but such a requirement is too stringent, especially when $X^{\nu}$
is different than $X$ or $\operatorname{dom}h^{\nu}$ is different than
$\operatorname{dom}h$. We also would like to address convergence of stationary
points for the approximating problems to those of the actual problem and then
neither pointwise nor uniform convergence of $\varphi^{\nu}$ to $\varphi$ is
sufficient.

We make the following universal assumptions for the remainder of the paper:

$X,X^{\nu}\mbox{ are nonempty and closed};~{}~{}~{}h,h^{\nu}\mbox{ are proper,
lsc, and convex};~{}~{}~{}F,F^{\nu}\mbox{ are lLc.}$

This limits the scope to a well-structured class of problems for which
convenient calculus rules can be brought in, while still addressing a vast
array of applications. In particular, [50, Thm. 10.46, Exer. 10.52] lead to
optimality conditions for the actual and approximating problems.

If both $h$ and $F$ were smooth, then $0\in\nabla F(x)^{\top}\nabla
h(F(x))+N_{X}(x)$ is a necessary condition for a local minimizer of $\varphi$
by [50, Thm. 6.12]. Here, $\nabla F(x)$ is the Jacobian matrix of $F$ at $x$
with rows corresponding to the gradients of $f_{1},\dots,f_{m}$ at $x$. This
condition is equivalently written as

$0=F(x)-z,~{}~{}~{}~{}0=\nabla
h(z)-y,~{}~{}~{}~{}0\in\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\nabla
f_{i}(x)+N_{X}(x),$

where $y=(y_{1},\dots,y_{m})\in\mathbb{R}^{m}$ and $z\in\mathbb{R}^{m}$ are
multiplier vectors. This condition naturally extends to nonsmooth $h$ and $F$
by essentially “replacing” gradients by subgradients. Thus, we express
optimality conditions for the actual and approximating problems concisely as
the generalized equations

$0\in S(x,y,z)~{}~{}~{}~{}~{}~{}\mbox{ and }~{}~{}~{}~{}~{}~{}0\in
S^{\nu}(x,y,z)$

using the set-valued mappings $S,S^{\nu}:\mathbb{R}^{n+2m}\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-12.0pt\hbox{\raise
2.5pt\hbox{$\rightarrow$}}\;\mathbb{R}^{2m+n}$ given by

$\displaystyle S(x,y,z)$
$\displaystyle=\big{\\{}F(x)-z\big{\\}}\times\big{\\{}\partial
h(z)-y\big{\\}}\times\Big{(}\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\operatorname{con}\partial
f_{i}(x)+N_{X}(x)\Big{)}$ $\displaystyle S^{\nu}(x,y,z)$
$\displaystyle=\big{\\{}F^{\nu}(x)-z\big{\\}}\times\big{\\{}\partial
h^{\nu}(z)-y\big{\\}}\times\Big{(}\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\operatorname{con}\partial
f^{\nu}_{i}(x)+N_{X^{\nu}}(x)\Big{)}.$

If $x$ satisfies $0\in S(x,y,z)$ for some $y\in\mathbb{R}^{m}$ and
$z\in\mathbb{R}^{m}$, then $x$ is a stationary point for the actual problem,
with similar terminology being adopted for the approximating problems. The set
of subgradients $\partial f_{i}(x)$ is convex when $f_{i}$ is epi-regular222A
function $f$ is epi-regular at $x$ if its epigraph is Clarke regular [50, Def.
6.4] at $(x,f(x))$. at $x$, which, for example, is the case if $f_{i}$ is
smooth at $x$ or if $f_{i}$ is convex [50, Thm. 8.30]. Under such
circumstances, “con” in the expression for $S$ is superfluous. Since $f_{i}$
is lLc, $\operatorname{con}\partial f_{i}(x)$ coincides with the set of Clarke
subgradients [50, Thm. 8.49] of $f_{i}$ at $x$. Aligned with the approach in
[50], we shy away from this terminology. We view the convexification in the
optimality condition as stemming from a slight relaxation of otherwise valid
optimality conditions and resulting in an additional “buffer” to absorb
approximations.

The optimality conditions generalize many familiar ones. For example, $0\in
S(x,y,z)$ if and only if the KKT condition hold for the actual problem with
$X=\mathbb{R}^{n}$,
$h(z)=z_{1}+\sum_{i=2}^{s}\iota_{\\{0\\}}(z_{i})+\sum_{i=s+1}^{m}\iota_{(-\infty,0]}(z_{i})$,
and $F$ being smooth. We see this by deriving $N_{X}(x)=\\{0\\}$, $\partial
h(z)=\\{1\\}\times N_{\\{0\\}^{s-1}}(z_{2},\dots,z_{s})\times
N_{(-\infty,0]^{m-s}}(z_{s+1},\dots,z_{m})$, and

$\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\operatorname{con}\partial
f_{i}(x)+N_{X}(x)=\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\nabla f_{i}(x)$

so that $y_{1}=1$, $y_{2},\dots,y_{s}$ are unrestricted in sign, and, for
$i=s+1,\dots,m$, $y_{i}=0$ if $f_{i}(x)<0$ and $y_{i}\geq 0$ if $f_{i}(x)=0$.
Since even the KKT condition requires a constraint qualification (such as the
Mangasarian-Fromovitz), it is not surprising that $0\in S(x,y,z)$ likewise
requires a qualification for it to be a necessary optimality condition. This
is formalized in the next proposition.

###### 2.1 Proposition

(optimality condition). Suppose that the following qualification holds at
$x^{\star}$:

$y\in N_{\operatorname{dom}h}\big{(}F(x^{\star})\big{)}~{}~{}\mbox{ and
}~{}~{}0\in\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\operatorname{con}\partial
f_{i}(x^{\star})+N_{X}(x^{\star})~{}~{}~{}\Longrightarrow~{}~{}~{}y=0.$ (2.2)

If $x^{\star}$ is a local minimizer of (1.1), then

$0\in S(x^{\star},y^{\star},z^{\star})$

for some $y^{\star}\in\mathbb{R}^{m}$ and $z^{\star}\in\mathbb{R}^{m}$, with
this optimality condition being equivalent to $0\in\partial\varphi(x^{\star})$
under the additional assumptions that $X$ is Clarke regular at $x^{\star}$
and, for each $y\in\partial h(F(x^{\star}))$ and $i=1,\dots,m$, $y_{i}f_{i}$
is epi-regular at $x^{\star}$.

Proof. Guided by [50, Exer. 10.52], the first conclusion follows
straightforwardly when recalling that $l_{F}(x,y)=\langle F(x),y\rangle$
implies

$\partial_{x}l_{F}(x,y)\subset\mathop{\sum}\nolimits_{i=1}^{m}\partial(y_{i}f_{i})(x)\subset\mathop{\sum}\nolimits_{i=1}^{m}\operatorname{con}\big{\\{}\partial(y_{i}f_{i})(x)\big{\\}}=\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\operatorname{con}\partial
f_{i}(x)$

via [50, Cor. 10.9, Thm. 9.61].

The second conclusion about equivalence with $0\in\partial\varphi(x^{\star})$
holds by the following argument. For
$\tilde{h}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\overline{\mathbb{R}}$ and
$\tilde{F}:\mathbb{R}^{n}\to\mathbb{R}^{n+m}$ given by

$\tilde{h}(z_{0},z)=\iota_{X}(z_{0})+h(z)~{}~{}~{}\mbox{ and
}~{}~{}~{}\tilde{F}(x)=\big{(}x,F(x)\big{)},$

we obtain that $\varphi(x)=\tilde{h}(\tilde{F}(x))$. Clearly, $\tilde{F}$ is
lLc and $\tilde{h}$ is lsc and proper. Let
$l_{\tilde{F}}(x,(w,y))=\langle\tilde{F}(x),(w,y)\rangle$. Under a
qualification, [56, Thm. 6.23] confirms that

$\partial\varphi(x^{\star})=\bigcup_{(w,y)\in\partial\tilde{h}(\tilde{F}(x^{\star}))}\partial_{x}l_{\tilde{F}}\big{(}x^{\star},(w,y)\big{)}$

as long as $\tilde{h}$ is epi-regular at $\tilde{F}(x^{\star})$ and
$l_{\tilde{F}}(\cdot\,,(w,y))$ is epi-regular at $x^{\star}$ for all
$(w,y)\in\partial\tilde{h}(\tilde{F}(x^{\star}))$. A closer examination shows
that (2.2) ensure that the qualification of the theorem indeed holds. By [56,
Prop. 4.63], we conclude that $\tilde{h}$ is epi-regular at
$\tilde{F}(x^{\star})$ because $X$ is Clarke regular at $x^{\star}$ and
$\partial h(F(x^{\star}))\neq\emptyset$. Moreover,
$l_{\tilde{F}}(\cdot\,,(w,y))$ is epi-regular at $x^{\star}$ because
$y_{i}f_{i}$ is assumed to be epi-regular at $x^{\star}$; see [56, Exam.
4.70]. Thus, it only remains to untangle the expression for
$\partial\varphi(x^{\star})$. We obtain that

$0\in\partial\varphi(x^{\star})~{}~{}~{}\Longleftrightarrow~{}~{}~{}\exists
y\in\partial
h\big{(}F(x^{\star})\big{)},~{}~{}0\in\mathop{\sum}\nolimits_{i=1}^{m}\partial(y_{i}f_{i})(x^{\star})+N_{X}(x^{\star}),$

where we again appeal to [56, Exam. 4.70] to compute
$\partial_{x}l_{\tilde{F}}(x^{\star},(w,y))$. Since $y_{i}f_{i}$ is epi-
regular at $x^{\star}$, $\partial(y_{i}f_{i})(x^{\star})$ is a convex set and
we conclude that

$\partial(y_{i}f_{i})(x^{\star})=\operatorname{con}\big{\\{}\partial(y_{i}f_{i})(x^{\star})\big{\\}}=y_{i}\operatorname{con}\partial
f_{i}(x^{\star}),$

which implies the assertion.

In the absence of regularity of the kind invoked in the second part of the
proposition, the optimality condition $0\in\partial\varphi(x^{\star})$ could
be strictly stronger than $0\in S(x^{\star},y^{\star},z^{\star})$. For
example, let $X=\mathbb{R}$, $h(z)=z_{1}+z_{2}$, and
$F(x)=(\max\\{-x,x/2\\},\min\\{0,-x\\})$. Then,
$\varphi(x)=\iota_{X}(x)+h(F(x))=\max\\{-x,-x/2\\}$ with
$0\not\in\partial\varphi(0)=[-1,-1/2]$. In contrast, $0\in
S(0,y^{\star},z^{\star})$ for $y^{\star}=(1,1)$ and $z^{\star}=(0,0)$ because

$S(0,y^{\star},z^{\star})=\big{\\{}F(0)-z^{\star}\big{\\}}\times\big{\\{}\partial
h(z^{\star})-y^{\star}\big{\\}}\times\big{(}y_{1}^{\star}\operatorname{con}[-1,1/2]+y_{2}^{\star}\operatorname{con}\\{-1,0\\}\big{)}.$

Generally, the advantage of the optimality condition $0\in S(x,y,z)$ is its
explicit form in terms of the “primitives” of the actual problem (1.1). It is
therefore much more computationally accessible than $0\in\partial\varphi(x)$,
which can be checked numerically only in special cases.

Proposition 2.1 likewise confirms that $0\in S^{\nu}(x,y,z)$ is a necessary
optimality condition for an approximating problem under a qualification
parallel to (2.2). We are now in a position to state what it means for the
approximating problems, paired with their optimality conditions, to be well-
justified surrogates of the actual problem and its optimality condition.

###### 2.2 Definition

(consistent approximations). The pairs
$\\{(\varphi^{\nu},S^{\nu}),\nu\in\mathbb{N}\\}$ are consistent approximations
of $(\varphi,S)$ when

$\varphi^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pt\varphi~{}~{}~{}~{}\mbox{ and
}~{}~{}~{}~{}S^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.5pt\hbox{$\,\scriptstyle
g$}}\hskip 7.0ptS.$

If the graphical convergence is relaxed to merely $\mathop{\rm
LimOut}\nolimits(\operatorname{gph}S^{\nu})\subset\operatorname{gph}S$, then
$\\{(\varphi^{\nu},S^{\nu}),\nu\in\mathbb{N}\\}$ are weakly consistent
approximations of $(\varphi,S)$.

Under consistency, even in its weak form, we are on solid ground because the
approximating problems indeed produce approximating solutions of the actual
problem as formalized next using the following notation. For
$T:\mathbb{R}^{n}\;{\lower 1.0pt\hbox{$\rightarrow$}}\kern-12.0pt\hbox{\raise
2.5pt\hbox{$\rightarrow$}}\;\mathbb{R}^{m}$, the set of $\delta$-solutions to
the generalized equation $0\in T(x)$ is defined as

$T^{-1}\big{(}\mathbb{B}(0,\delta)\big{)}=\bigcup_{v\in\mathbb{B}(0,\delta)}T^{-1}(v)=\bigcup_{v\in\mathbb{B}(0,\delta)}\big{\\{}x\in\mathbb{R}^{n}~{}\big{|}~{}v\in
T(x)\big{\\}}.$

Thus, a $\delta$-solution $\hat{x}\in T^{-1}(\mathbb{B}(0,\delta))$ “almost”
satisfies $0\in T(x)$ in the sense that $v\in T(\hat{x})$ for some $v$ with
$\|v\|\leq\delta$. We observe that such near-solutions may depend on the
choice of norm $\|\cdot\|$.

###### 2.3 Proposition

(consequences of consistency). Suppose that
$\\{(\varphi^{\nu},S^{\nu}),\nu\in\mathbb{N}\\}$ are weakly consistent
approximations of $(\varphi,S)$, the tolerances $\varepsilon^{\nu}$ and
$\delta^{\nu}$ vanish, and $\alpha<\beta$. Then, the following hold:

  1. (a)

$\mathop{\rm LimOut}\nolimits\big{(}\varepsilon^{\nu}\mbox{-}\mathop{\rm
argmin}\nolimits\varphi^{\nu}\big{)}\subset\mathop{\rm
argmin}\nolimits\varphi$, provided that
$\operatorname{dom}\varphi\neq\emptyset$.

  2. (b)

$\mathop{\rm
LimOut}\nolimits\\{\varphi^{\nu}\leq\alpha\\}\subset\\{\varphi\leq\alpha\\}\subset\mathop{\rm
LimInn}\nolimits\\{\varphi^{\nu}\leq\beta\\}$.

  3. (c)

$\mathop{\rm
LimOut}\nolimits(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)}\subset
S^{-1}(0)$.

Moreover, if the approximations are consistent (and not merely weakly
consistent), then there are $\gamma^{\nu}\to 0$ such that $\mathop{\rm
LimInn}\nolimits(S^{\nu})^{-1}(\mathbb{B}(0,\gamma^{\nu}))\supset S^{-1}(0)$.

Proof. This is a compilation of well-known facts; see [50, Thm. 7.31] for (a);
[50, Prop. 7.7] for (b); and [50, Thm. 5.37] for (c) and the final statement.

Consistency indeed guarantees a comprehensive sense of approximation tailored
to the need of minimization problems. From (a) in the proposition, we see that
every cluster point of a sequence of near-minimizers of the approximating
problems is a minimizer of the actual problem provided that the tolerances
vanish. That is, if $x^{\nu}\in\varepsilon^{\nu}\mbox{-}\mathop{\rm
argmin}\nolimits\varphi^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{x}$ along a subsequence $N\in{\cal
N}_{\infty}^{\scriptscriptstyle\\#}$, then $\bar{x}\in\mathop{\rm
argmin}\nolimits\varphi$. This is a valuable property, but remains somewhat
conceptual in nonconvex settings because there might be no practical algorithm
for computing near-minimizers of the approximating problems. Item (b) shows
that the lower level-sets of $\varphi^{\nu}$ eventually become essentially
indistinguishable from those of $\varphi$. For example, if
$\varphi^{\nu}(x^{\nu})\leq\alpha$ and $x^{\nu}\to\bar{x}$, then
$\varphi(\bar{x})\leq\alpha$ by the first inclusion in (b). The second
inclusion in (b) establishes that any $\bar{x}$ with
$\varphi(\bar{x})\leq\alpha$ can be approached by points $x^{\nu}$ with
$\varphi^{\nu}(x^{\nu})\leq\beta$. Thus, $\varphi^{\nu}$ accurately “predicts”
the values of $\varphi$ as $\nu\to\infty$.

Item (c) confirms that any cluster point $(\bar{x},\bar{y},\bar{z})$ of a
sequence $\\{(x^{\nu},y^{\nu},z^{\nu}),\,\nu\in\mathbb{N}\\}$, with $0\in
S^{\nu}(x^{\nu},y^{\nu},z^{\nu})$, satisfies $0\in
S(\bar{x},\bar{y},\bar{z})$. This holds even if the points
$(x^{\nu},y^{\nu},z^{\nu})$ are computed with tolerances $\delta^{\nu}$ as
long as they vanish. The approximating problems and their optimality
conditions are often constructed such that computing nearly stationary points
is indeed possible in finite time; see Section 3 for examples. Combining the
facts from (b) and (c), we summarize: If $N\in{\cal
N}_{\infty}^{\scriptscriptstyle\\#}$ and
$(x^{\nu},y^{\nu},z^{\nu})\in(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt(\bar{x},\bar{y},\bar{z})$, then

$(\bar{x},\bar{y},\bar{z})\in S^{-1}(0)~{}~{}\mbox{ and
}~{}~{}\varphi(\bar{x})\leq\mathop{\rm liminf}\nolimits_{\nu\in
N}\varphi^{\nu}(x^{\nu}).$

Thus, $\bar{x}$ is stationary for the actual problem, with an objective
function value at least as good as predicted by the approximations.

These consequences occur under weak consistency. Passing to consistency, we
achieve enhanced robustness in the sense that every stationary point of the
actual problem can be approached by nearly stationary points of the
approximating problems. In fact, the proposition guarantees that for some
tolerances $\gamma^{\nu}\to 0$, one has
$(S^{\nu})^{-1}(\mathbb{B}(0,\gamma^{\nu}))\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptS^{-1}(0)$.

The proposition justifies the following broad algorithmic framework for
solving the actual problem.

Consistent Approximation Algorithm.

Data.

$\delta^{\nu}\geq 0$, with $\delta^{\nu}\to 0$.

Step 0.

Set $\nu=1$.

Step 1.

Minimize $h^{\nu}\,{\raise 1.0pt\hbox{$\scriptstyle\circ$}}\,F^{\nu}$ over
$X^{\nu}$ until one obtains $x^{\nu}$, with corresponding $(y^{\nu},z^{\nu})$,
satisfying

$(x^{\nu},y^{\nu},z^{\nu})\in(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)}.$

Step 2.

Replace $\nu$ by $\nu+1$ and go to Step 1.

A multitude of implementation details remain unsettled. What approximations
are most suitable for the actual problem at hand? What subroutine should be
used in Step 1 and with what $\delta^{\nu}$? We list many examples of
approximations in Section 3 and describe a concrete algorithm in Section 4.

Verification of consistency is supported by sufficient conditions for epi-
convergence of $\varphi^{\nu}$ to $\varphi$ and graphical convergence of
$S^{\nu}$ to $S$. There are several known results. For example, if
$X=X^{\nu}=\mathbb{R}^{n}$, $F=F^{\nu}$ are smooth with $\nabla F$ having rank
$m$, and $h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pth$, then $\varphi^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pt\varphi$ by [10, Thm. 3.2]; see also [50, Chap. 5 and 7]. The
following conditions appear especially versatile by allowing for
approximations of $X$, $h$, and $F$ under relatively mild assumptions.

###### 2.4 Theorem

(sufficient conditions for consistent approximations). Suppose that
$h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pth$, $X^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptX$ with these sets being convex, and, for $i=1,\dots,m$, one
has the property:

$\begin{rcases}x^{\nu}\in X^{\nu}\to x\in X\\\ v^{\nu}\in\partial
f_{i}^{\nu}(x^{\nu})\end{rcases}~{}\Longrightarrow~{}\begin{cases}f_{i}^{\nu}(x^{\nu})\to
f_{i}(x)\\\ \\{v^{\nu},\nu\in\mathbb{N}\\}\mbox{ is bounded with all its
cluster points in }\operatorname{con}\partial f_{i}(x).\end{cases}$ (2.3)

Then, each one of the following conditions is sufficient for
$\\{(\varphi^{\nu},S^{\nu}),\nu\in\mathbb{N}\\}$ to be weakly consistent
approximations of $(\varphi,S)$:

  1. (a)

(real-valuedness): $h$ is real-valued.

  2. (b)

(pointwise convergence): $h^{\nu}(z)\to h(z)$ for all
$z\in\operatorname{bdry}(\operatorname{dom}h)$ and, in addition,
$F^{\nu}(x)=F(x)$ for all $x\in X$ and $X\subset X^{\nu}$ for each $\nu$.

  3. (c)

(monotonicity): For each $\nu$: $h^{\nu}(z)\leq h^{\nu}(\bar{z})$ when
$z\leq\bar{z}$, $h^{\nu}(z)\leq h(z)$ for all $z$, $X\subset X^{\nu}$, and
$F^{\nu}(x)\leq F(x)$ for all $x\in X$.

  4. (d)

(interior points): $h$ is continuous relative to $\operatorname{dom}h$,
$X\subset X^{\nu}$ for each $\nu$, and for all $x\in X$ with
$F(x)\in\operatorname{bdry}(\operatorname{dom}h)$, there is $x^{\nu}\in X\to
x$ such that $F(x^{\nu})\in\operatorname{int}(\operatorname{dom}h)$.

  5. (e)

(separability): For $\sum_{k=1}^{r}m_{k}=m$, lLc
$F_{k}^{\nu},F_{k}:\mathbb{R}^{n}\to\mathbb{R}^{m_{k}}$, and proper, lsc, and
convex $h^{\nu}_{k},h_{k}:\mathbb{R}^{m_{k}}\to\overline{\mathbb{R}}$,
$k=1,\dots,r$, one can express
$F^{\nu}(x)=(F^{\nu}_{1}(x),\dots,F^{\nu}_{r}(x))$,
$F(x)=(F_{1}(x),\dots,F_{r}(x))$,
$h^{\nu}(z)=\mathop{\sum}\nolimits_{k=1}^{r}h_{k}^{\nu}(z_{k})$, and
$h(z)=\mathop{\sum}\nolimits_{k=1}^{r}h_{k}(z_{k})$ with $h_{k}$ being either
real-valued or $h_{k}$ satisfying $h^{\nu}_{k}(z_{k})\to h_{k}(z_{k})$ for all
$z_{k}\in\operatorname{bdry}(\operatorname{dom}h_{k})$ and
$F^{\nu}_{k}(x)=F_{k}(x)$ for all $x\in X$. Moreover, $X\subset X^{\nu}$.

We also have the refinements:

If $X^{\nu}=X$, then each of (a)-(e) remains sufficient without the convexity
assumption on $X$.

If $f_{i}^{\nu}=f_{i}$, then (2.3) holds automatically.

If $f_{i}^{\nu},f_{i}$ are convex and $f_{i}^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0ptf_{i}$, then (2.3) holds automatically.

If $X^{\nu}=X$ and (c) holds, then $f_{i}^{\nu}(x^{\nu})\to f_{i}(x)$ in (2.3)
is relaxed to $\mathop{\rm liminf}\nolimits f_{i}^{\nu}(x^{\nu})\geq
f_{i}(x)$.

If $X^{\nu}=X$ and $f_{i}^{\nu}=f_{i}$, then each of (a)-(e) is sufficient for
consistent approximations.

If $f_{i}^{\nu},f_{i}$ are smooth, then (2.3) is equivalent to
$f_{i}^{\nu}(x^{\nu})\to f_{i}(x)$ and $\nabla f_{i}^{\nu}(x^{\nu})\to\nabla
f_{i}(x)$ as $x^{\nu}\in X^{\nu}\to x$.

If $f_{i}^{\nu},f_{i}$ are smooth, then each of (a)-(e) is sufficient for
consistent approximations.

Proof. We start by establishing $\varphi^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pt\varphi$. To prove the liminf-condition (1.2) for
$\varphi^{\nu}$ and $\varphi$, let $x^{\nu}\to x$. Since neither
$\iota_{X}(x)$ nor $h(F(x))$ is equal to $-\infty$,

$\mathop{\rm
liminf}\nolimits\Big{(}\iota_{X^{\nu}}(x^{\nu})+h^{\nu}\big{(}F^{\nu}(x^{\nu})\big{)}\Big{)}\geq\mathop{\rm
liminf}\nolimits\iota_{X^{\nu}}(x^{\nu})+\mathop{\rm liminf}\nolimits
h^{\nu}\big{(}F^{\nu}(x^{\nu})\big{)}.$

Certainly, $X^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptX$ implies that $\iota_{X^{\nu}}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pt\iota_{X}$ and then also $\mathop{\rm
liminf}\nolimits\iota_{X^{\nu}}(x^{\nu})\geq\iota_{X}(x)$. If $x^{\nu}\not\in
X^{\nu}$, then $\iota_{X^{\nu}}(x^{\nu})=\infty$. Thus, we assume without loss
of generality that $x^{\nu}\in X^{\nu}$. This implies that $x\in X$ because
$X^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle s$}}\hskip 7.0ptX$. By assumption,
$F^{\nu}(x^{\nu})\to F(x)$ and $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$. These facts ensure that $\mathop{\rm liminf}\nolimits
h^{\nu}(F^{\nu}(x^{\nu}))$ $\geq$ $h(F(x))$. When combined with the earlier
inequalities, this relation establishes the liminf-condition (1.2) for
$\varphi^{\nu}$ and $\varphi$, which thus holds without any of the additional
conditions (a)-(e).

Next, we establish the limsup-condition (1.3) for $\varphi^{\nu}$ and
$\varphi$. Let $x\in\mathbb{R}^{n}$ be arbitrary. If $x\not\in X$ or
$F(x)\not\in\operatorname{dom}h$, then $\varphi(x)=\infty$ and the limsup-
condition holds trivially. If $x\in X$ and $F(x)\in\operatorname{dom}h$, then
we argue as follows:

First, suppose that (a) holds. Since $X^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptX$, there exists $x^{\nu}\in X^{\nu}\to x$. Moreover,
$h^{\nu}$ converges uniformly to $h$ on compact sets because $h$ is convex and
real-valued; see [50, Thm. 7.17]. Consequently, $h^{\nu}(F^{\nu}(x^{\nu}))\to
h(F(x))$ and one has

$\mathop{\rm
limsup}\nolimits\Big{(}\iota_{X^{\nu}}(x^{\nu})+h^{\nu}\big{(}F^{\nu}(x^{\nu})\big{)}\Big{)}\leq\mathop{\rm
limsup}\nolimits\iota_{X^{\nu}}(x^{\nu})+\mathop{\rm limsup}\nolimits
h^{\nu}\big{(}F^{\nu}(x^{\nu})\big{)}=h\big{(}F(x)\big{)}.$

Second, suppose that (c) holds. Since $X\subset X^{\nu}$, we construct
$\\{x^{\nu}=x,\nu\in\mathbb{N}\\}$ and simply need to prove that $\mathop{\rm
limsup}\nolimits h^{\nu}(F^{\nu}(x))\leq h(F(x))$. This holds because
$F^{\nu}(x)\leq F(x)$ and then $h^{\nu}(F^{\nu}(x))\leq h^{\nu}(F(x))\leq
h(F(x))$ for all $\nu\in\mathbb{N}$.

Third, suppose that (d) holds. We consider two cases. Suppose that
$F(x)\in\operatorname{int}(\operatorname{dom}h)$. Then, construct
$\\{x^{\nu}=x,\nu\in\mathbb{N}\\}$ and note that $h^{\nu}(F^{\nu}(x))\to
h(F(x))$ because $h^{\nu}$ converges uniformly to $h$ on bounded subsets of
the interior of $\operatorname{dom}h$; see [50, Thm. 7.17]. Next, suppose that
$F(x)\in\operatorname{bdry}(\operatorname{dom}h)$. Then, by condition (d),
there are $\bar{x}^{k}\in X\to x$ with
$F(\bar{x}^{k})\in\operatorname{int}(\operatorname{dom}h)$. Consequently,
there exist $\delta_{k}\in(0,\infty)\to 0$ such that
$\mathbb{B}(F(\bar{x}^{k}),\delta_{k})\subset\operatorname{int}(\operatorname{dom}h)$
for all $k$. Let $\varepsilon_{k}\in(0,\infty)\to 0$. Fix $k$. Since
$\bar{x}^{k}\in X\cap X^{\nu}$, $F^{\nu}(\bar{x}^{k})\to F(\bar{x}^{k})$ as
$\nu\to\infty$. Let $\nu_{k}\in\mathbb{N}$, with $\nu_{k}\geq k$, be such that
$F^{\nu}(\bar{x}^{k})\in\mathbb{B}(F(\bar{x}^{k}),\delta_{k})$ for all
$\nu\geq\nu_{k}$. Since $h^{\nu}$ converges uniformly to $h$ on
$\mathbb{B}(F(\bar{x}^{k}),\delta_{k})$ by virtue of that set being in the
interior of $\operatorname{dom}h$ (again cf. [50, Thm. 7.17]), there is
$\bar{\nu}_{k}\geq\nu_{k}$ such that $h^{\nu}(F^{\nu}(\bar{x}^{k}))\leq
h(F(\bar{x}^{k}))+\varepsilon_{k}$ for all $\nu\geq\bar{\nu}_{k}$. We repeat
these arguments for all $k\in\mathbb{N}$. Now, we construct
$x^{\nu}=\bar{x}^{1}$ for $\nu=1,\dots,\bar{\nu}_{2}$ and
$x^{\nu}=\bar{x}^{k}$ for $\bar{\nu}_{k}<\nu\leq\bar{\nu}_{k+1}$. Then,
$x^{\nu}\to x$ and $h^{\nu}(F^{\nu}(x^{\nu}))\leq
h(F(x^{\nu}))+\varepsilon_{k}$ for all $\bar{\nu}_{k}<\nu\leq\bar{\nu}_{k+1}$.
As $\nu\to\infty$, $k$ tends to $\infty$ as well in this expression. Thus, its
right-hand side converges to $h(F(x))$; recall that $h$ is continuous on its
domain. We have shown that $\mathop{\rm limsup}\nolimits
h^{\nu}(F^{\nu}(x^{\nu}))\leq h(F(x))$.

Fourth, suppose that (e) holds. Since $X\subset X^{\nu}$, one has $x\in
X^{\nu}$ for all $\nu$ and we construct $\\{x^{\nu}=x,\nu\in\mathbb{N}\\}$.
Certainly, $F^{\nu}(x)\to F(x)$ and

$\mathop{\rm
limsup}\nolimits\Big{(}\iota_{X^{\nu}}(x^{\nu})+\mathop{\sum}\nolimits_{k=1}^{r}h_{k}^{\nu}\big{(}F_{k}^{\nu}(x^{\nu})\big{)}\Big{)}\leq\mathop{\rm
limsup}\nolimits\iota_{X^{\nu}}(x)+\mathop{\sum}\nolimits_{k=1}^{r}\mathop{\rm
limsup}\nolimits h_{k}^{\nu}\big{(}F^{\nu}_{k}(x)\big{)}.$

Suppose that $h_{k}$ is real-valued. Then, $h_{k}^{\nu}$ converges uniformly
to $h_{k}$ on compact sets because $h_{k}$ is convex; see [50, Thm. 7.17].
This implies that $h_{k}^{\nu}(F^{\nu}_{k}(x))\to h_{k}(F_{k}(x))$.
Alternatively, suppose that $h^{\nu}_{k}(z_{k})\to h_{k}(z_{k})$ for all
$z_{k}\in\operatorname{bdry}(\operatorname{dom}h_{k})$ and
$F^{\nu}_{k}(x^{\prime})=F_{k}(x^{\prime})$ for all $x^{\prime}\in X$. Since
$F(x)\in\operatorname{dom}h$, we have $F_{k}(x)\in\operatorname{dom}h_{k}$. If
$F_{k}(x)\in\operatorname{bdry}(\operatorname{dom}h_{k})$, then, by
assumption, $h^{\nu}_{k}(F_{k}(x))\to h_{k}(F_{k}(x))$. If
$F_{k}(x)\in\operatorname{int}(\operatorname{dom}h_{k})$, then
$h^{\nu}_{k}(F_{k}(x))\to h_{k}(F_{k}(x))$ as well because these functions are
convex. In summary,

$\mathop{\sum}\nolimits_{k=1}^{r}\mathop{\rm limsup}\nolimits
h_{k}^{\nu}\big{(}F^{\nu}_{k}(x)\big{)}=\mathop{\sum}\nolimits_{k=1}^{r}h_{k}\big{(}F_{k}(x)\big{)}$

and the needed limsup-condition holds.

Fifth, suppose that (b) holds. This is a special case of (e) with $r=1$.

We have confirmed that each one of (a)-(e) suffices for
$\varphi^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pt\varphi$ and, in fact, this holds
even without the convexity of $X^{\nu}$ and $X$.

We next turn to the relation between $\operatorname{gph}S^{\nu}$ and
$\operatorname{gph}S$ and start by showing $\mathop{\rm
LimOut}\nolimits(\operatorname{gph}S^{\nu})\subset\operatorname{gph}S$. Let
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})\in\mathop{\rm
LimOut}\nolimits(\operatorname{gph}S^{\nu})$. Then, there are $N\in{\cal
N}_{\infty}^{\scriptscriptstyle\\#}$, $x^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{x}$, $y^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{y}$, $z^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{z}$, $u^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{u}$, $v^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{v}$, and $w^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{w}$ with
$(x^{\nu},y^{\nu},z^{\nu},u^{\nu},v^{\nu},w^{\nu})\in\operatorname{gph}S^{\nu}$.
Consequently,

$u^{\nu}=F^{\nu}(x^{\nu})-z^{\nu},~{}~{}~{}v^{\nu}\in\partial
h^{\nu}(z^{\nu})-y^{\nu},~{}~{}~{}w^{\nu}\in\mathop{\sum}\nolimits_{i=1}^{m}y_{i}^{\nu}\operatorname{con}\partial
f_{i}^{\nu}(x^{\nu})+N_{X^{\nu}}(x^{\nu}).$

The existence of $w^{\nu}$ implies that $x^{\nu}\in X^{\nu}$ because otherwise
$N_{X^{\nu}}(x^{\nu})$ would have been an empty set. Since $X^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptX$, we also have $\bar{x}\in X$. Thus,
$F^{\nu}(x^{\nu})\,{\raise 1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower
3.0pt\hbox{$\,\scriptstyle N$}}\hskip 7.0ptF(\bar{x})$ and we conclude that
$\bar{u}=F(\bar{x})-\bar{z}$. Attouch’s theorem [50, Thm. 12.35] states that
$h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pth$ implies $\partial
h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.5pt\hbox{$\,\scriptstyle g$}}\hskip 7.0pt\partial h$. Consequently,
$\bar{v}\in\partial h(\bar{z})-\bar{y}$.

The inclusion for $w^{\nu}$ implies that there exist

$a_{i}^{\nu}\in\operatorname{con}\partial
f_{i}^{\nu}(x^{\nu}),~{}i=1,\dots,m,~{}~{}~{}\mbox{ such that
}~{}~{}~{}w^{\nu}-\mathop{\sum}\nolimits_{i=1}^{m}y_{i}^{\nu}a_{i}^{\nu}\in
N_{X^{\nu}}(x^{\nu}).$ (2.4)

By Caratheodory’s theorem, there are $\lambda_{ij}^{\nu}\geq 0$ and
$b_{ij}^{\nu}\in\partial f_{i}^{\nu}(x^{\nu})$, $j=0,1,\dots,n$, such that
$\sum_{j=0}^{n}\lambda_{ij}^{\nu}=1$ and
$a_{i}^{\nu}=\sum_{j=0}^{n}\lambda_{ij}^{\nu}b_{ij}^{\nu}$. The sequence
$\\{(\lambda_{i0}^{\nu},\dots,\lambda_{in}^{\nu}),\nu\in N\\}$ is contained in
a compact set and thus has a convergent subsequence. By assumption (2.3),
$\\{b_{ij}^{\nu},\nu\in N\\}$ is bounded with all its cluster points in
$\operatorname{con}\partial f_{i}(\bar{x})$. Consequently, there exist
$\bar{\lambda}_{i}=(\bar{\lambda}_{i0},\dots,\bar{\lambda}_{in})\in\mathbb{R}^{1+n}$,
$\bar{b}_{i0},\dots,\bar{b}_{in}$, and a subsequence of $N$, which we also
denote by $N$, such that

$(\lambda_{i0}^{\nu},\dots,\lambda_{in}^{\nu})\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{\lambda}_{i}\geq 0,~{}\mbox{ with
}~{}\mathop{\sum}\nolimits_{j=0}^{n}\bar{\lambda}_{ij}=1,~{}~{}~{}\mbox{ and
}~{}~{}~{}b_{ij}^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{b}_{ij}\in\operatorname{con}\partial f_{i}(\bar{x}).$

This means that

$a_{i}^{\nu}\,{\raise 1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower
3.0pt\hbox{$\,\scriptstyle N$}}\hskip
7.0pt\bar{a}_{i}=\mathop{\sum}\nolimits_{j=0}^{n}\bar{\lambda}_{ij}\bar{b}_{ij}\in\operatorname{con}\partial
f_{i}(\bar{x}).$

Via Attouch’s theorem [50, Thm. 12.35], $\iota_{X^{\nu}}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pt\iota_{X}$ implies $N_{X^{\nu}}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.5pt\hbox{$\,\scriptstyle
g$}}\hskip 7.0ptN_{X}$ because $X^{\nu}$ and $X$ are convex. Using this fact
as well as the observations that $y_{i}^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{y}_{i}$ and
$w^{\nu}-\sum_{i=1}^{m}y_{i}^{\nu}a_{i}^{\nu}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{w}-\sum_{i=1}^{m}\bar{y}_{i}\bar{a}_{i}$, we obtain from
(2.4) that $\bar{w}-\mathop{\sum}\nolimits_{i=1}^{m}\bar{y}_{i}\bar{a}_{i}\in
N_{X}(\bar{x})$. Thus, because $\bar{a}_{i}\in\operatorname{con}\partial
f_{i}(\bar{x})$, one has

$\bar{w}\in\mathop{\sum}\nolimits_{i=1}^{m}\bar{y}_{i}\operatorname{con}\partial
f_{i}(\bar{x})+N_{X}(\bar{x})$

and we conclude that $(\bar{u},\bar{v},\bar{w})\in
S(\bar{x},\bar{y},\bar{z})$. We have established that $\mathop{\rm
LimOut}\nolimits(\operatorname{gph}S^{\nu})\subset\operatorname{gph}S$ and
this holds without leveraging any of the conditions (a)-(e).

Under the modified assumption that $X^{\nu}=X$, but not necessarily convex, we
still have $N_{X^{\nu}}=N_{X}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.5pt\hbox{$\,\scriptstyle
g$}}\hskip 7.0ptN_{X}$ because $N_{X}$ is outer semicontinuous; see [50, Prop.
6.6]. Thus, the above argument carries over.

If $f_{i}^{\nu}=f_{i}$, then (2.3) holds automatically because $f_{i}$ is lLc
and $\partial f_{i}$ is outer semicontinuous; see [50, Prop. 8.7].

If $X^{\nu}=X$ and (c) holds, then $\mathop{\rm limsup}\nolimits
f_{i}^{\nu}(x^{\nu})\leq\mathop{\rm limsup}\nolimits f_{i}(x^{\nu})=f_{i}(x)$,
with the last equality following by continuity of $f_{i}$.

If $f_{i}^{\nu},f_{i}$ are convex and $f_{i}^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0ptf$, then [56, Prop. 4.18] establishes that
$f_{i}^{\nu}(x^{\nu})\to f_{i}(\bar{x})$ if $x^{\nu}\to\bar{x}$. Cluster
points of the sequence $\\{v^{\nu}\in\partial
f_{i}^{\nu}(x^{\nu}),\nu\in\mathbb{N}\\}$ must be in $\partial f_{i}(\bar{x})$
by Attouch’s theorem; see [50, Thm. 12.35]. It only remains to show that the
sequence is bounded. We recall that

$\partial f(x)=\mathop{\rm argmin}\nolimits_{v}\big{\\{}f^{*}(v)-\langle
v,x\rangle\big{\\}}~{}~{}~{}\mbox{ and }~{}~{}~{}\partial
f^{\nu}(x)=\mathop{\rm argmin}\nolimits_{v}\big{\\{}f^{\nu*}(v)-\langle
v,x\rangle\big{\\}}$

for every $x\in\mathbb{R}^{n}$; see [50, Prop. 11.3]. Here, $f^{*}$ and
$f^{\nu*}$ are the conjugates of $f$ and $f^{\nu}$, respectively, which are
also proper, lsc, and convex by the Fenchel-Moreau theorem 5.23 in [56]. By
Wijsman’s theorem [50, Thm. 11.34], $f^{\nu*}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0ptf^{*}$ and then we also have
$g^{\nu}=f^{\nu*}-\langle\cdot\,,x^{\nu}\rangle\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0ptg=f^{*}-\langle\cdot\,,\bar{x}\rangle$ as seen from [56, Prop.
4.19(a)]. Since $\partial f(\bar{x})$ is compact by [56, Prop. 2.54], there is
$\rho\in(0,\infty)$ such that $\partial f(\bar{x})=\mathop{\rm
argmin}\nolimits g\subset\mathbb{B}(0,\rho/2)$. Let $B=\mathbb{B}(0,\rho)$.
Set $\eta=\inf_{\operatorname{bdry}B}g$. If $\eta<\infty$, then $g(v)<\infty$
for some $v\in\operatorname{bdry}B$ so [56, Thm. 4.9] applies, $\mathop{\rm
argmin}\nolimits_{\operatorname{bdry}B}g\neq\emptyset$, and
$\eta=g(v^{\star})$ for all $v^{\star}\in\mathop{\rm
argmin}\nolimits_{\operatorname{bdry}B}g$. Since $\mathop{\rm argmin}\nolimits
g\cap\operatorname{bdry}B=\emptyset$, $g(v^{\star})>\inf g$ for
$v^{\star}\in\mathop{\rm argmin}\nolimits_{\operatorname{bdry}B}g$. Thus,
regardless of $\eta$ being finite or not, there is $\delta\in(0,\infty)$ such
that

$g(v)\geq\inf g+\delta~{}~{}~{}\forall v\in\operatorname{bdry}B.$ (2.5)

Since $\partial f(\bar{x})$ is nonempty by [56, Prop. 2.25], there is
$\bar{v}\in\mathop{\rm argmin}\nolimits g$. From the definition of epi-
convergence, $g^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0ptg$ implies that there are points $w^{\nu}\to\bar{v}$ such that
$\mathop{\rm limsup}\nolimits g^{\nu}(w^{\nu})\leq g(\bar{v})$. Thus, there
exists $\nu_{0}$ such that $g^{\nu}(w^{\nu})\leq\inf
g+{\raisebox{1.0pt}{$\frac{1}{3}$}}\delta$ and $w^{\nu}\in B$ for all
$\nu\geq\nu_{0}$. For the sake of contradiction, suppose that there are
$N\in{\cal N}_{\infty}^{\scriptscriptstyle\\#}$ such that $\\{v^{\nu}\not\in
B,\nu\in N\\}$. Since $v^{\nu}\in\mathop{\rm argmin}\nolimits g^{\nu}$, one
has $g^{\nu}(v^{\nu})\leq g^{\nu}(w^{\nu})$ for all $\nu\in N$. For $\nu\in N$
with $\nu\geq\nu_{0}$, let $z^{\nu}$ be the unique point in
$\operatorname{bdry}B$ on the line segment between $v^{\nu}$ and $w^{\nu}$,
i.e., $z^{\nu}=(1-\lambda^{\nu})v^{\nu}+\lambda^{\nu}w^{\nu}$ for some
$\lambda^{\nu}\in[0,1]$. The convexity inequality ([56, Prop. 1.10]) applied
to $g^{\nu}$ implies that

$\displaystyle g^{\nu}(z^{\nu})$
$\displaystyle\leq(1-\lambda^{\nu})g^{\nu}(v^{\nu})+\lambda^{\nu}g^{\nu}(w^{\nu})$
$\displaystyle\leq(1-\lambda^{\nu})g^{\nu}(w^{\nu})+\lambda^{\nu}g^{\nu}(w^{\nu})=g^{\nu}(w^{\nu})\leq\inf
g+{\raisebox{1.0pt}{$\frac{1}{3}$}}\delta$ (2.6)

for $\nu\in N$ with $\nu\geq\nu_{0}$. Since $\\{z^{\nu},\nu\in
N,\nu\geq\nu_{0}\\}$ is contained in the compact set $\operatorname{bdry}B$,
it has a cluster point $\bar{z}\in\operatorname{bdry}B$. After passing to the
corresponding subsequence, which we also denote by $N$, we find that
$\mathop{\rm liminf}\nolimits_{\nu\in N}g^{\nu}(z^{\nu})\geq
g(\bar{z})\geq\inf g+\delta$, where the first inequality follows from the fact
that $g^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0ptg$ and the second one by (2.5).
Thus, for sufficiently large $\nu\in N$, $g^{\nu}(z^{\nu})\geq\inf
g+{\raisebox{1.0pt}{$\frac{2}{3}$}}\delta$. However, this contradicts (2) and
we conclude that $v^{\nu}\in B$ for all but a finite number of $\nu$.

Under the assumption that $X^{\nu}=X$ and $f_{i}^{\nu}=f_{i}$, we show that
$\mathop{\rm
LimInn}\nolimits(\operatorname{gph}S^{\nu})\supset\operatorname{gph}S$. Let
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})\in\operatorname{gph}S$.
This means that

$\bar{u}=F(\bar{x})-\bar{z},~{}~{}~{}\bar{v}\in\partial
h(\bar{z})-\bar{y},~{}~{}~{}\bar{w}\in\mathop{\sum}\nolimits_{i=1}^{m}\bar{y}_{i}\operatorname{con}\partial
f_{i}(\bar{x})+N_{X}(\bar{x}).$

Set $x^{\nu}=\bar{x}$, $y^{\nu}=\bar{y}$, and $w^{\nu}=\bar{w}$. Since
$h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pth$, it follows by Attouch’s theorem
[50, Thm. 12.35] that $\partial h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.5pt\hbox{$\,\scriptstyle
g$}}\hskip 7.0pt\partial h$ and there are $v^{\nu}\to\bar{v}$ and
$z^{\nu}\to\bar{z}$ such that $v^{\nu}+\bar{y}\in\partial h^{\nu}(z^{\nu})$.
Let $u^{\nu}=F(\bar{x})-z^{\nu}$. This means that
$(x^{\nu},y^{\nu},z^{\nu},u^{\nu},v^{\nu},w^{\nu})\in\operatorname{gph}S^{\nu}\to(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})$.
Consequently, $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})\in\mathop{\rm
LimInn}\nolimits(\operatorname{gph}S^{\nu})$ and $\mathop{\rm
LimInn}\nolimits(\operatorname{gph}S^{\nu})\supset\operatorname{gph}S$ holds.
In view of the earlier results, $S^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.5pt\hbox{$\,\scriptstyle
g$}}\hskip 7.0ptS$ and we conclude that the approximations are consistent.

For the case with smooth $f_{i}^{\nu},f_{i}$, the claim about (2.3) is trivial
and it only remains to show $\mathop{\rm
LimInn}\nolimits(\operatorname{gph}S^{\nu})\supset\operatorname{gph}S$. Now,
we obtain the simplification

$\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\operatorname{con}\partial
f_{i}(x)=\Big{\\{}\mathop{\sum}\nolimits_{i=1}^{m}y_{i}\nabla
f_{i}(x)\Big{\\}}=\big{\\{}\nabla F(x)^{\top}y\big{\\}},$

with a similar expression for the approximating functions. Let
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})\in\operatorname{gph}S$.
This means that $\bar{u}=F(\bar{x})-\bar{z}$, $\bar{v}\in\partial
h(\bar{z})-\bar{y}$, and $\bar{w}\in\nabla
F(\bar{x})^{\top}\bar{y}+N_{X}(\bar{x})$. In particular, $\bar{x}\in X$. Set
$y^{\nu}=\bar{y}$. Since $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$, it follows by Attouch’s theorem [50, Thm. 12.35] that
$\partial h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.5pt\hbox{$\,\scriptstyle g$}}\hskip 7.0pt\partial h$ and there are
$v^{\nu}\to\bar{v}$ and $z^{\nu}\to\bar{z}$ such that
$v^{\nu}+\bar{y}\in\partial h^{\nu}(z^{\nu})$.

Since $N_{X^{\nu}}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.5pt\hbox{$\,\scriptstyle g$}}\hskip 7.0ptN_{X}$, as argued above, there’s
$(x^{\nu},t^{\nu})\in\operatorname{gph}N_{X^{\nu}}$ with $x^{\nu}\in
X^{\nu}\to\bar{x}$ and $t^{\nu}\to\bar{w}-\nabla F(\bar{x})^{\top}\bar{y}$.
Construct $w^{\nu}=t^{\nu}+\nabla F^{\nu}(x^{\nu})^{\top}\bar{y}$. We then
have $w^{\nu}\to\bar{w}$ and $w^{\nu}-\nabla F^{\nu}(x^{\nu})^{\top}\bar{y}\in
N_{X^{\nu}}(x^{\nu})$. Also, construct $u^{\nu}=F^{\nu}(x^{\nu})-z^{\nu}$,
which converges to $\bar{u}$. In summary, we have constructed
$(x^{\nu},y^{\nu},z^{\nu},u^{\nu},v^{\nu},w^{\nu})\in\operatorname{gph}S^{\nu}\to(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})$.
This means that
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})\in\mathop{\rm
LimInn}\nolimits(\operatorname{gph}S^{\nu})$ and, thus, $\mathop{\rm
LimInn}\nolimits(\operatorname{gph}S^{\nu})\supset\operatorname{gph}S$ holds.

While we believe weak consistency is the natural goal in most applications, in
some cases one might be willing to sacrifice some assurances with the benefit
of relaxed assumptions.

###### 2.5 Corollary

(approximations without full epi-convergence). Suppose that $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$, $X^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptX$ with these sets being convex, and (2.3) holds for
$i=1,\dots,m$. Then, for $\alpha\in\overline{\mathbb{R}}$ and vanishing
$\delta^{\nu}$, one has

$\mathop{\rm
LimOut}\nolimits\\{\varphi^{\nu}\leq\alpha\\}\subset\\{\varphi\leq\alpha\\}~{}~{}~{}~{}~{}\mbox{
and }~{}~{}~{}~{}~{}\mathop{\rm
LimOut}\nolimits(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)}\subset
S^{-1}(0).$

If $X^{\nu}=X$, then the assertions hold without the convexity assumption on
$X$.

Proof. Following the proof of Theorem 2.4, we see that the present assumption
suffices for $\mathop{\rm liminf}\nolimits\varphi^{\nu}(x^{\nu})$ $\geq$
$\varphi(x)$ to hold whenever $x^{\nu}\to x$. By [50, Prop. 7.7], the
assertion about level-sets follows. Again following the proof, we deduce that
$\mathop{\rm
LimOut}\nolimits(\operatorname{gph}S^{\nu})\subset\operatorname{gph}S$ holds
without the conditions (a)-(e) in the theorem and we invoke [50, Thm. 5.37] to
reach the conclusion.

The assumptions of the corollary permit the approximating $\varphi^{\nu}$ to
be arbitrarily “high” relative to $\varphi$, i.e., $\mathop{\rm
LimOut}\nolimits(\operatorname{epi}\varphi^{\nu})$ could be a strict subset of
$\operatorname{epi}\varphi$. This is a main reason why we avoid calling the
approximations consistent in this case. Still, the mild assumptions make the
corollary widely applicable.

##  3 Examples

An array of examples illustrate the breadth of the framework, but numerous
possibilities are omitted including those involving polyhedral approximations
of $X$ as in [6]. We recall that $X,X^{\nu}$ and $f_{i},f_{i}^{\nu}$ are
nonconvex unless specified otherwise.

###### 3.1 Example

(goal optimization). For parameters $\alpha_{i}\in[0,\infty)$ and
$\tau_{i}\in\mathbb{R}$, we consider the problem

$\mathop{\rm minimize}_{x\in
X}\mathop{\sum}\nolimits_{i=1}^{m}\alpha_{i}\max\big{\\{}0,~{}f_{i}(x)-\tau_{i}\big{\\}},$

which aims to lower each $f_{i}(x)$ down to the goal of $\tau_{i}$, with
$\alpha_{i}$ being the per-unit penalty for failing to do so. The problem is
of the form (1.1) with
$h(z)=\mathop{\sum}\nolimits_{i=1}^{m}\alpha_{i}\max\\{0,z_{i}-\tau_{i}\\}$. A
possible approximation is to set $X^{\nu}=X$ and $F^{\nu}=F$, but replace $h$
by

$h^{\nu}(z)=\mathop{\sum}\nolimits_{i=1}^{m}\alpha_{i}\psi^{\nu}(z_{i}-\tau_{i}),~{}\mbox{
where
}\psi^{\nu}(\gamma)=\frac{1}{\theta^{\nu}}\ln\big{(}1+\exp(\theta^{\nu}\gamma)\big{)},~{}~{}~{}\theta^{\nu}\in(0,\infty).$

Since $h^{\nu}$ is convex and differentiable any number of times, it offers
computational benefits over $h$. The resulting approximating problems and
their optimality conditions are consistent approximations provided that
$\theta^{\nu}\to\infty$. We refer to [14, 12] for more general smoothing
schemes.

Detail. By Theorem 2.4, condition (a), and the refinements, we only need to
show $h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pth$. Since
$\sup_{\gamma\in\mathbb{R}}|\psi^{\nu}(\gamma)-\max\\{0,\gamma\\}|\leq(\ln
2)/\theta^{\nu}$ as seen from [43], (1.2) and (1.3) hold.

For an illustration of the optimality conditions, suppose that
$f_{1},\dots,f_{m}$ are smooth. Then, $0\in S^{\nu}(x,y,z)$ simplifies to
$F(x)=z$, $y=\nabla h^{\nu}(z)$, $-\nabla F(x)^{\top}y\in N_{X}(x)$. In fact,
this can be written as $-\nabla F(x)^{\top}\nabla h^{\nu}(F(x))\in N_{X}(x)$,
with

$\nabla
h^{\nu}(z)=\begin{bmatrix}\alpha_{1}\nabla\psi^{\nu}(z_{1}-\tau_{1})\\\
\vdots\\\
\alpha_{m}\nabla\psi^{\nu}(z_{m}-\tau_{m})\end{bmatrix}~{}~{}~{}\mbox{ and
}~{}~{}~{}~{}\nabla\psi^{\nu}(\gamma)=\frac{\exp(\theta^{\nu}\gamma)}{1+\exp(\theta^{\nu}\gamma)}.$

Similarly, the optimality condition $0\in S(x,y,z)$ specializes to $F(x)=z$,
$y\in\partial h(z)$, $-\nabla F(x)^{\top}y\in N_{X}(x)$. Since $\partial
h(z)=C_{1}\times\cdots\times C_{m}$, where $C_{i}=\\{0\\}$ if
$z_{i}<\tau_{i}$, $C_{i}=[0,\alpha_{i}]$ if $z_{i}=\tau_{i}$, and
$C_{i}=\\{\alpha_{i}\\}$ otherwise, the optimality condition simplifies
further to $-\nabla F(x)^{\top}y\in N_{X}(x)$ with $y_{i}=0$ if
$f_{i}(x)<\tau_{i}$, $y_{i}\in[0,\alpha_{i}]$ if $f_{i}(x)=\tau_{i}$, and
$y_{i}=\alpha_{i}$ otherwise. These conditions are necessary for optimality in
the actual and approximating problems by Proposition 2.1; the qualification
(2.2) holds in each case because
$\operatorname{dom}h=\operatorname{dom}h^{\nu}=\mathbb{R}^{m}$.

###### 3.2 Example

(stochastic optimization). For probabilities $p=(p_{1},\dots,p_{m})\in P$,
where $P\subset\mathbb{R}^{m}$ is the set of nonnegative vectors with
components summing to one, consider the problem

$\mathop{\rm minimize}_{x\in X}\mathop{\sum}\nolimits_{i=1}^{m}p_{i}f_{i}(x),$

which appears in stochastic optimization and machine learning. The problem is
of the form (1.1) with $h(z)=\mathop{\sum}\nolimits_{i=1}^{m}p_{i}z_{i}$. In
practice, the probabilities might not be fully known and this leads to
approximating problems with $p$ replaced by $p^{\nu}\in P$, i.e.,
$h^{\nu}(z)=\mathop{\sum}\nolimits_{i=1}^{m}p_{i}^{\nu}z_{i}$ in (2.1). The
change may also be part of a sensitivity analysis such as when developing
influence functions [33, 4]. The approximations are consistent provided that
$p^{\nu}\to p$.

Detail. Since $h^{\nu}(z^{\nu})\to h(z)$ whenever $z^{\nu}\to z$, we obtain
$h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pth$; see (1.2) and (1.3). Thus, the
consistency follows via condition (a) of Theorem 2.4. The optimality condition
$0\in S(x,y,z)$ is necessary by Proposition 2.1 because the qualification
(2.2) holds. In fact, the optimality condition simplifies to
$0\in\mathop{\sum}\nolimits_{i=1}^{m}p_{i}\operatorname{con}\partial
f_{i}(x)+N_{X}(x)$ because $y=\nabla h(z)=p$.

###### 3.3 Example

(distributionally robust optimization). Let $P\subset\mathbb{R}^{m}$ be as in
the previous example and let $A$ and $A^{\nu}$ be nonempty closed subsets of
$P$. We consider the problem

$\mathop{\rm minimize}_{x\in X}\,\mathop{\rm max}\nolimits_{p\in
A}\mathop{\sum}\nolimits_{i=1}^{m}p_{i}f_{i}(x)$

and its approximation obtained by replacing $A$ by $A^{\nu}$. The set $A$
might consist of a single, true probability vector and be approximated by a
set $A^{\nu}$ “centered” on a current best estimate of the true probability
vector with some “radius” reflecting the uncertainty about this estimate. The
resulting problems fit the forms of (1.1) and (2.1) with $h(z)=\mathop{\rm
max}\nolimits_{p\in A}\langle p,z\rangle$ and $h^{\nu}(z)=\mathop{\rm
max}\nolimits_{p\in A^{\nu}}\langle p,z\rangle$. If $A^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptA$, then the approximations are consistent.

Detail. Let $\hat{A}(z)=\mathop{\rm argmax}\nolimits_{p\in A}\langle
p,z\rangle$ and $\hat{A}^{\nu}(z)=\mathop{\rm argmax}\nolimits_{p\in
A^{\nu}}\langle p,z\rangle$. The functions $h$ and $h^{\nu}$ are convex. They
are also real-valued, and thus continuous, because $A$ and $A^{\nu}$ are
compact. To establish $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$, we argue using (1.2) and (1.3). Suppose that $z^{\nu}\to
z$. Let $\bar{p}\in\hat{A}(z)$. Since $A^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptA$, there exists $p^{\nu}\in A^{\nu}\to\bar{p}$. This implies
that

$\mathop{\rm liminf}\nolimits\big{(}\mathop{\rm max}\nolimits_{p\in
A^{\nu}}\langle p,z^{\nu}\rangle\big{)}\geq\mathop{\rm liminf}\nolimits\langle
p^{\nu},z^{\nu}\rangle=\langle\bar{p},z\rangle=\mathop{\rm max}\nolimits_{p\in
A}\langle p,z\rangle.$

Thus, (1.2) holds for $h$ and $h^{\nu}$. For fixed $z$, let
$p^{\nu}\in\hat{A}^{\nu}(z)$. Then, for any $\\{\bar{p}^{\nu}\in
A,\nu\in\mathbb{N}\\}$, one has

$\mathop{\rm max}\nolimits_{p\in A^{\nu}}\langle p,z\rangle=\langle
p^{\nu},z\rangle=\langle
p^{\nu}-\bar{p}^{\nu},z\rangle+\langle\bar{p}^{\nu},z\rangle\leq\|p^{\nu}-\bar{p}^{\nu}\|_{2}\|z\|_{2}+\mathop{\rm
max}\nolimits_{p\in A}\langle p,z\rangle.$

Since there are $\bar{p}^{\nu}\in A$ such that
$\|p^{\nu}-\bar{p}^{\nu}\|_{2}\to 0$ because $A^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptA$, $\mathop{\rm limsup}\nolimits h^{\nu}(z)\leq h(z)$.
Consequently, $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$ and we again invoke condition (a) of Theorem 2.4 and the
refinements.

###### 3.4 Example

(augmented Lagrangian methods). With
$h(z)=z_{1}+\sum_{i=2}^{m}\iota_{\\{0\\}}(z_{i})$, the problem

$\mathop{\rm minimize}_{x\in X}f_{1}(x)~{}\mbox{ subject to
}~{}f_{2}(x)=0,\dots,f_{m}(x)=0$

fits the mold (1.1). An approximation stemming from augmented Lagrangian
methods utilizes

$h^{\nu}(z)=z_{1}+\mathop{\sum}\nolimits_{i=2}^{m}\big{(}y_{i}^{\nu}z_{i}+{\raisebox{1.0pt}{$\frac{1}{2}$}}\theta^{\nu}z_{i}^{2}\big{)},$

where $y^{\nu}=(y_{2}^{\nu},\dots,y_{m}^{\nu})\in\mathbb{R}^{m-1}$ and
$\theta^{\nu}\in[0,\infty)$. If $\\{y^{\nu},\nu\in\mathbb{N}\\}$ is bounded
and $\theta^{\nu}\to\infty$, then the resulting approximations are consistent.

Detail. The function $h$ is not real-valued and we turn to condition (b) of
Theorem 2.4. For $z\in$ $\operatorname{dom}h$ $=$
$\mathbb{R}\times\\{0\\}^{m-1}$, one has $h^{\nu}(z)=z_{1}=h(z)$ and the
condition holds. This also confirms the limsup-condition (1.3) for $h^{\nu}$
and $h$. For the liminf-condition (1.2), suppose that $z^{\nu}\to z$. Then,

$\mathop{\rm liminf}\nolimits h^{\nu}(z^{\nu})\geq
z_{1}+\mathop{\sum}\nolimits_{i=2}^{m}\mathop{\rm
liminf}\nolimits(y_{i}^{\nu}z_{i}^{\nu})+{\raisebox{1.0pt}{$\frac{1}{2}$}}\mathop{\sum}\nolimits_{i=2}^{m}\mathop{\rm
liminf}\nolimits\big{(}\theta^{\nu}(z_{i}^{\nu})^{2}\big{)}.$

If any $z_{2},\dots,z_{m}$ is nonzero, then the right-hand side equals
$\infty$, which coincides with $h(z)$. If $z_{2}=\cdots=z_{m}=0$, then the
right-hand size is no smaller than $z_{1}=h(z)$. Thus, $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$.

###### 3.5 Example

(min-functions). For smooth $g_{ik}:\mathbb{R}^{n}\to\mathbb{R}$,
$k=1,\dots,s_{i}$, $i=1,\dots,m$, let

$f_{i}(x)=\min_{k=1,\dots,s_{i}}g_{ik}(x).$

We adopt smooth approximations of $f_{i}$ by defining

$f_{i}^{\nu}(x)=-\frac{1}{\theta^{\nu}}\ln\Big{(}\mathop{\sum}\nolimits_{k=1}^{s_{i}}\exp\big{(}-\theta^{\nu}g_{ik}(x)\big{)}\Big{)},$

where $\theta^{\nu}\in(0,\infty)$; see [39, 14, 5, 12] for related smoothing
techniques. If $\theta^{\nu}\to\infty$, then (2.3) holds. Moreover, if in
addition $X^{\nu}\supset X$, $X^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptX$, with these sets being convex, $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$, $h^{\nu}(z)\leq h^{\nu}(\bar{z})$ when $z\leq\bar{z}$, and
$h^{\nu}(z)\leq h(z)$ for all $z$, then the approximations are weakly
consistent.

Detail. We leverage condition (c) of Theorem 2.4 and observe that
$F^{\nu}(x)\leq F(x)$ because (see [43])

$0\leq f_{i}(x)-f_{i}^{\nu}(x)\leq\frac{\ln
s_{i}}{\theta^{\nu}}~{}~{}~{}\forall x\in\mathbb{R}^{n}.$ (3.1)

Moreover, we need to confirm (2.3). Let $x^{\nu}\to\bar{x}$. The previous
inequalities show that $f_{i}^{\nu}(x^{\nu})\to f_{i}(\bar{x})$ because
$\theta^{\nu}\to\infty$. It is apparent that $f_{i}^{\nu}$ is smooth and, in
fact,

$\nabla
f_{i}^{\nu}(x)=\mathop{\sum}\nolimits_{k=1}^{s_{i}}\mu^{\nu}_{ik}(x)\nabla
g_{ik}(x),~{}~{}\mbox{ with
}~{}\mu^{\nu}_{ik}(x)=\frac{\exp\big{(}\theta^{\nu}(f_{i}(x)-g_{ik}(x))\big{)}}{\mathop{\sum}\nolimits_{j=1}^{s_{i}}\exp\big{(}\theta^{\nu}(f_{i}(x)-g_{ij}(x))\big{)}}.$

Since $\mu^{\nu}_{ik}(x)\in(0,1)$ regardless of $x$, we have that $\\{\nabla
f_{i}^{\nu}(x^{\nu}),\nu\in\mathbb{N}\\}$ is bounded. For some $N\in{\cal
N}^{\scriptscriptstyle\\#}_{\infty}$, suppose that $\nabla
f_{i}^{\nu}(x^{\nu})\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\bar{v}$. We would like to show
$\bar{v}\in\operatorname{con}\partial f_{i}(\bar{x})$. We observe that

$\operatorname{con}\partial
f_{i}(x)=-\operatorname{con}\partial(-f_{i})(x)=-\operatorname{con}\big{\\{}\nabla(-g_{ik})(x)~{}\big{|}~{}k\in\mathbb{A}_{i}(x)\big{\\}}=\operatorname{con}\big{\\{}\nabla
g_{ik}(x)~{}\big{|}~{}k\in\mathbb{A}_{i}(x)\big{\\}},$

where $\mathbb{A}_{i}(x)=\mathop{\rm
argmin}\nolimits_{k=1,\dots,s_{i}}g_{ik}(x)$. If
$k\not\in\mathbb{A}_{i}(\bar{x})$, then the continuity of $f_{i}$ and $g_{ik}$
implies that

$\exp\big{(}\theta^{\nu}(f_{i}(x^{\nu})-g_{ik}(x^{\nu}))\big{)}\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt0.$

The denominator in the defining expression for $\mu^{\nu}_{ik}(x^{\nu})$ is
greater than one because $f_{i}(x^{\nu})-g_{ij}(x^{\nu})=0$ for
$j\in\mathbb{A}_{i}(x^{\nu})$. Thus, $\mu^{\nu}_{ik}(x^{\nu})\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt0$.

For any $k$, $\mu^{\nu}_{ik}(x^{\nu})\in(0,1)$. Consequently, after passing to
another subsequence which we also denote by $N$, there are
$\mu^{\infty}_{ik}\in[0,1]$, $k=1,\dots,s_{i}$, such that
$\mu^{\nu}_{ik}(x^{\nu})\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt\mu_{ik}^{\infty}$. Since
$\mathop{\sum}\nolimits_{k=1}^{s_{i}}\mu^{\nu}_{ik}(x^{\nu})=1$ for all $\nu$,
we must also have $\mathop{\sum}\nolimits_{k=1}^{s_{i}}\mu_{ik}^{\infty}=1$,
with $\mu_{ik}^{\infty}=0$ if $k\not\in\mathbb{A}_{i}(\bar{x})$ as already
seen. We conclude that

$\nabla
f^{\nu}_{i}(x^{\nu})=\mathop{\sum}\nolimits_{k=1}^{s_{i}}\mu^{\nu}_{ik}(x^{\nu})\nabla
g_{ik}(x^{\nu})\,{\raise 1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower
3.0pt\hbox{$\,\scriptstyle N$}}\hskip
7.0pt\bar{v}=\mathop{\sum}\nolimits_{k\in\mathbb{A}_{i}(\bar{x})}\mu^{\infty}_{ik}\nabla
g_{ik}(\bar{x})\in\operatorname{con}\partial f_{i}(\bar{x})$

and (2.3) holds. An instance of $h$ and $h^{\nu}$ satisfying condition (c) of
Theorem 2.4 follows next.

###### 3.6 Example

(penalty methods). With
$h(z)=z_{1}+\iota_{(-\infty,0]^{m-1}}(z_{2},\dots,z_{m})$, we consider the
problem

$\mathop{\rm minimize}_{x\in X}f_{1}(x)\mbox{ subject to }f_{2}(x)\leq
0,\dots,f_{m}(x)\leq 0,$

which is of the form (1.1). An approximation stemming from penalty methods
utilizes

$h^{\nu}(z)=z_{1}+\theta^{\nu}\mathop{\sum}\nolimits_{i=2}^{m}\big{(}\max\\{0,z_{i}\\}\big{)}^{2},$

where $\theta^{\nu}\in[0,\infty)$. If $X^{\nu}=X$, $F^{\nu}=F$, and
$\theta^{\nu}\to\infty$, then the resulting approximations are consistent.

Detail. We turn to condition (c) of Theorem 2.4. Certainly, $h^{\nu}(z)\leq
h^{\nu}(\bar{z})$ when $z\leq\bar{z}$ and the other requirements hold as well.
To confirm $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$, we leverage the characterization (1.2) and (1.3). Let
$z^{\nu}\to z$. We note that $\mathop{\rm liminf}\nolimits
h^{\nu}(z^{\nu})\geq h(z)$ when $z=(z_{1},\dots,z_{m})$ has $z_{i}\leq 0$ for
$i=2,\dots,m$. If any of these $z_{i}$ are positive, then $z_{i}^{\nu}>0$ for
sufficiently large $\nu$. Thus, $h^{\nu}(z^{\nu})\to\infty=h(z)$ and (1.2)
holds for $h^{\nu}$ and $h$. For any $z$, $\mathop{\rm limsup}\nolimits
h^{\nu}(z)\leq h(z)$ and (1.3) holds as well. Consequently, $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$.

Condition (c) of Theorem 2.4 also permits outer approximations of $X$ and
lower bounding approximations of $F$ (see Example 3.5) while retaining weak
consistency.

###### 3.7 Example

(interior-point methods). For the actual problem in Example 3.6, we consider
the approximation

$h^{\nu}(z)=\begin{cases}z_{1}-\frac{1}{\theta^{\nu}}\mathop{\sum}\nolimits_{i=2}^{m}\ln(-z_{i})&\mbox{
if }z_{2}<0,\dots,z_{m}<0\\\ \infty&\mbox{ otherwise,}\end{cases}$

where $\theta^{\nu}\in(0,\infty)$. This logarithmic penalty approach is the
basis for (primal) interior-point methods. If $\theta^{\nu}\to\infty$ and for
all $x\in X$, with $f_{i}(x)\leq 0$ for all $i=2,\dots,m$, there exists
$x^{\nu}\in X\to x$ such that $f_{i}(x^{\nu})<0$ for all $i=2,\dots,m$, then
the approximations are consistent.

Detail. We leverage condition (d) of Theorem 2.4. Trivially, $h$ is continuous
relative to its domain. We establish $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$ via (1.2) and (1.3). Let $z^{\nu}\to z$. If $z_{i}>0$ for
some $i=2,\dots,m$, then $z_{i}^{\nu}\geq 0$ for sufficiently large $\nu$ and
$\mathop{\rm liminf}\nolimits h^{\nu}(z^{\nu})\geq h(z)$ because both sides
are $\infty$. If $z_{i}\leq 0$ for $i=2,\dots,m$, then $h(z)=z_{1}$ and the
liminf-condition holds again. The condition $\mathop{\rm limsup}\nolimits
h^{\nu}(z^{\nu})\leq h(z)$ holds because for any $z_{i}=0$, one can select
$z_{i}^{\nu}=-\exp(-\sqrt{\theta^{\nu}})$. Then, $z_{i}^{\nu}\to z_{i}$ and
$-(\ln(-z_{i}^{\nu}))/\theta^{\nu}=\sqrt{\theta^{\nu}}/\theta^{\nu}\to 0$.

###### 3.8 Example

(expectation functions). Expectation functions arise in stochastic
optimization and machine learning and then the component functions
$f_{1},\dots,f_{m}$ may take the form

$f_{i}(x)=\mathbb{E}\big{[}g_{i}(\mbox{\boldmath$\xi$},x)\big{]},$

where $g_{i}:\Xi\times\mathbb{R}^{n}\to\overline{\mathbb{R}}$ is defined in
terms of a probability space $(\Xi,{\cal B},\mathbb{P})$. An independent and
identically distributed sample
$\mbox{\boldmath$\xi$}_{1},\dots,\mbox{\boldmath$\xi$}_{\nu}$ according to
$\mathbb{P}$ defines a sample average approximation

$f_{i}^{\nu}(x)=\frac{1}{\nu}\mathop{\sum}\nolimits_{j=1}^{\nu}g_{i}(\mbox{\boldmath$\xi$}_{j},x).$

If both $g_{i}$ and $-g_{i}$ are random lower semicontinuous and locally inf-
integrable (see [56, Sec. 8.G] for definitions), then, with probability one,
$f_{i}^{\nu}(x^{\nu})\to f_{i}(x)$ whenever $x^{\nu}\to x$ by [56, Thm. 8.56].

Detail. If there is a set $B\in{\cal B}$ such that $\mathbb{P}(B)=1$ and
$g_{i}(\xi,\cdot)$ is smooth for all $\xi\in B$, then one can attempt to
repeat the above arguments with $f_{i}$ replaced by the partial derivatives of
$f_{i}$ and conclude that $\nabla f^{\nu}_{i}(x^{\nu})\to\nabla f_{i}(x)$
whenever $x^{\nu}\to x$. This would allow us to satisfy the requirement (2.3).
For further details and refinements about approximations of expectation
functions and their subgradients, we refer to [19].

###### 3.9 Example

(oracle functions). Suppose that $h$ is real-valued, but not available in an
explicit form. If for each $z$ we can compute $h(z)$ and a subgradient
$v\in\partial h(z)$, then the approximation

$h^{\nu}(z)=\max_{k=1,\dots,\nu}h(z^{k})+\langle
v^{k},z-z^{k}\rangle,~{}~{}\mbox{ with
}~{}z^{k}\in\mathbb{R}^{m},~{}~{}v^{k}\in\partial h(z^{k}),$

remains available. Now, $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$ if $\\{z^{k},k\in\mathbb{N}\\}$ is a countable dense subset
of $\mathbb{R}^{m}$.

Detail. By [50, Thm. 7.17], $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$ whenever the functions converge pointwise on a countable
dense subset of $\mathbb{R}^{m}$. Let $\bar{z}\in\\{z^{k},k\in\mathbb{N}\\}$.
Obviously, $h^{\nu}(\bar{z})\leq h(\bar{z})$ because $h$ is the pointwise
supremum of its affine supports; see [50, Thm. 8.13]. Moreover, there is
$\bar{\nu}$ such that $\bar{z}\in\\{z^{1},\dots,z^{\bar{\nu}}\\}$. Thus,
$h^{\nu}(\bar{z})\geq h(\bar{z})$ for all $\nu\geq\bar{\nu}$. By [50, Thm.
7.17], this also means that $h^{\nu}(z)\to h(z)$ for all $z\in\mathbb{R}^{m}$.

###### 3.10 Example

(homotopy method). For proper, lsc, and convex
$\hat{h}:\mathbb{R}^{m-1}\to\overline{\mathbb{R}}$ and lLc
$\hat{F}:\mathbb{R}^{n}\to\mathbb{R}^{m-1}$, consider the problem

$\mathop{\rm minimize}_{x\in X}\hat{h}\big{(}\hat{F}(x)\big{)},$

which is of the form (1.1) with $h(z)=\hat{h}(z_{1},\dots,z_{m-1})$ for
$z=(z_{1},\dots,z_{m})$ and $F(x)=(\hat{F}(x),f_{m}(x))$ for some lLc
$f_{m}:\mathbb{R}^{n}\to\mathbb{R}$. A homotopy method for the problem solves
the approximations

$\mathop{\rm minimize}_{x\in
X}\,(1-\lambda^{\nu})\hat{h}\big{(}\hat{F}(x)\big{)}+\lambda^{\nu}f_{m}(x)$

as $\lambda^{\nu}\to 0$. If $f_{m}$ is chosen wisely, then the approximating
problems might be simpler to solve than the actual one while benefitting from
warm starts. The approximations are of the form (2.1) with

$h^{\nu}(z)=(1-\lambda^{\nu})\hat{h}(z_{1},\dots,z_{m-1})+\lambda^{\nu}z_{m}.$

If $\lambda^{\nu}\to 0$, then the approximations are consistent.

Detail. To establish $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$ via (1.2) and (1.3), we note that for $z^{\nu}\to z$, one
has

$\mathop{\rm
liminf}\nolimits(1-\lambda^{\nu})\hat{h}(z_{1}^{\nu},\dots,z_{m-1}^{\nu})+\lambda^{\nu}z_{m}^{\nu}\geq\mathop{\rm
liminf}\nolimits\hat{h}(z_{1}^{\nu},\dots,z_{m-1}^{\nu})+\mathop{\rm
liminf}\nolimits\lambda^{\nu}z_{m}^{\nu}\geq\hat{h}(z_{1},\dots,z_{m-1})=h(z).$

Moreover, for $z\in\operatorname{dom}h$,
$(1-\lambda^{\nu})\hat{h}(z_{1},\dots,z_{m-1})+\lambda^{\nu}z_{m}\to\hat{h}(z_{1},\dots,z_{m-1})$.
We therefore have both epi-convergence and pointwise convergence (on
$\operatorname{dom}h$) and condition (b) of Theorem 2.4, with refinements,
establishes consistency.

###### 3.11 Example

(monitoring functions). In extended nonlinear programming [49], one utilizes

$h(z)=\mathop{\rm sup}\nolimits_{y\in Y}\big{\\{}\langle
z,y\rangle-{\raisebox{1.0pt}{$\frac{1}{2}$}}\langle
y,By\rangle\big{\\}}~{}~{}~{}\mbox{ and }~{}~{}~{}h^{\nu}(z)=\mathop{\rm
sup}\nolimits_{y\in Y^{\nu}}\big{\\{}\langle
z,y\rangle-{\raisebox{1.0pt}{$\frac{1}{2}$}}\langle
y,B^{\nu}y\rangle\big{\\}},$

where $Y,Y^{\nu}\subset\mathbb{R}^{m}$ are nonempty polyhedral sets and
$B,B^{\nu}$ are symmetric positive semidefinite $m\times m$-matrices. If
$B^{\nu}\to B$ and $Y^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptY$, then $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$. If in addition $B$ is positive definite or $Y$ is bounded,
then $h$ is real-valued and $h^{\nu}(z)\to h(z)$ for $z\in\mathbb{R}^{m}$.
Thus, main steps toward (weak) consistency via Theorem 2.4 are immediately
accomplished.

Detail. The epi-convergence $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$ is established via the corresponding conjugate functions
$h^{\nu*}$ and $h^{*}$. By Wijsman’s theorem [50, Thm. 11.34], it suffices to
show that $h^{\nu*}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth^{*}$. Since
$h^{*}(y)={\raisebox{1.0pt}{$\frac{1}{2}$}}\langle y,By\rangle+\iota_{Y}(y)$,
$h^{\nu*}(y)={\raisebox{1.0pt}{$\frac{1}{2}$}}\langle
y,B^{\nu}y\rangle+\iota_{Y^{\nu}}(y)$, and $\iota_{Y^{\nu}}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pt\iota_{Y}$, we conclude that $h^{\nu*}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth^{*}$.

It follows by [50, Thm. 7.17] that the pointwise convergence $h^{\nu}(z)\to
h(z)$ holds when $h$ is real-valued. This is the case when $B$ is positive
definite or when $Y$ is bounded.

###### 3.12 Example

(difference-of-convex functions). For a proper, lsc, and convex
$f:\mathbb{R}^{n}\to\overline{\mathbb{R}}$ and convex
$g:\mathbb{R}^{n}\to\mathbb{R}$, consider the problem

$\mathop{\rm minimize}_{x\in X}f(x)-g(x),$

which involves an objective function of the difference-of-convex kind. As the
only approximation, suppose that $g$ is replaced by smooth functions
$g^{\nu}:\mathbb{R}^{n}\to\mathbb{R}$ that also satisfy the property:

$x^{\nu}\in X\to x~{}~{}\Longrightarrow~{}~{}g^{\nu}(x^{\nu})\to g(x)\mbox{
and }\big{\\{}\nabla g^{\nu}(x^{\nu}),\nu\in\mathbb{N}\big{\\}}\mbox{ is
bounded with all cluster points in }\partial g(x),$

which holds, for instance, when $g^{\nu}$ is convex and $g^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0ptg$; see the arguments leading to the third refinement of
Theorem 2.4. This produces weakly consistent approximations.

Detail. For $z=(z_{1},z_{2})$, with $z_{1}\in\mathbb{R}^{n}$ and
$z_{2}\in\mathbb{R}$, we set $h(z)=h_{1}(z_{1})+h_{2}(z_{2})$, where
$h_{1}(z_{1})=f(z_{1})$ and $h_{2}(z_{2})=-z_{2}$. Moreover, let
$F(x)=(x,g(x))$ and $F^{\nu}(x)=(x,g^{\nu}(x))$ so that $m=n+1$, $m_{1}=n$,
$m_{2}=1$, and $r=2$ in the notation of condition (e) of Theorem 2.4. Since
$g$ is real-valued and convex, it is lLc and then $F$ is also lLc. With
$h^{\nu}=h$, we trivially obtain $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$. The requirement (2.3) translates into the assumed
property. We then invoke condition (e) of Theorem 2.4 to conclude weak
consistency. For instance $g(x)=\max_{k=1,\dots,s}g_{k}(x)$, with
$g_{k}:\mathbb{R}^{n}\to\mathbb{R}$ being smooth, could be approximated
parallel to Example 3.5. In this case, $0\in S(x,y,z)$ reduces to
$0\in\partial f(x)-\partial g(x)+N_{X}(x)$.

##  4 Enhanced Proximal Composite Algorithm

As an example of an implementable version of the consistent approximation
algorithm, we consider the setting where $X^{\nu}$ is convex, $h^{\nu}$ is
real-valued, and $F^{\nu}$ is twice continuously differentiable. Then, the
approximating problems (2.1) are solvable by proximal composite methods, which
can be traced back to [26, 47, 8]; see also [48, 57, 9] for trust-region
versions and [22] for details about rates of convergence under the assumption
that $h^{\nu}$ and $\nabla F^{\nu}$ are Lipschitz continuous. Let
$\operatorname{prj}_{X^{\nu}}(x)$ be the projection of $x$ on $X^{\nu}$.

Enhanced Proximal Composite Algorithm (EPCA).

Data.

$x^{0}\in\mathbb{R}^{n}$, $\tau\in(1,\infty),\sigma\in(0,1)$,
$\bar{\lambda}\in(0,\infty)$, $\lambda^{0}\in(0,\bar{\lambda}]$,
$\\{\delta^{\nu}>0,\nu\in\mathbb{N}\\}\to 0$.

Step 0.

Set $\nu=1$.

Step 1.

Set $k=0$ and $\bar{x}^{0}=\operatorname{prj}_{X^{\nu}}(x^{\nu-1})$.

Step 2.

Compute $x^{\star}\in\mathop{\rm argmin}\nolimits_{x\in
X^{\nu}}h^{\nu}\big{(}F^{\nu}(\bar{x}^{k})+\nabla
F^{\nu}(\bar{x}^{k})(x-\bar{x}^{k})\big{)}+\tfrac{1}{2\lambda^{k}}\|x-\bar{x}^{k}\|_{2}^{2}$.

If $x^{\star}=\bar{x}^{k}$, then go to Step 4.

Step 3.

If
$h^{\nu}\big{(}F^{\nu}(\bar{x}^{k})\big{)}-h^{\nu}\big{(}F^{\nu}(x^{\star})\big{)}\geq\sigma\Big{(}h^{\nu}\big{(}F^{\nu}(\bar{x}^{k})\big{)}-h^{\nu}\big{(}F^{\nu}(\bar{x}^{k})+\nabla
F^{\nu}(\bar{x}^{k})(x^{\star}-\bar{x}^{k})\big{)}\Big{)}$,

then set $\lambda^{k+1}=\min\\{\tau\lambda^{k},\bar{\lambda}\\}$ and go to
Step 5.

Else, replace $\lambda^{k}$ by $\lambda^{k}/\tau$ and go to Step 2.

Step 4.

Set $x^{\nu}=x^{\star}$, $z^{\nu}=F^{\nu}(x^{\nu})$, and $y^{\nu}$ such that
$y^{\nu}\in\partial h^{\nu}(z^{\nu})$ and $-\nabla
F^{\nu}(x^{\nu})^{\top}y^{\nu}\in N_{X^{\nu}}(x^{\nu})$.

Replace $\nu$ by $\nu+1$ and go to Step 1.

Step 5.

Set $\bar{x}^{k+1}=x^{\star}$, $\bar{z}^{k+1}=F^{\nu}(\bar{x}^{k})+\nabla
F^{\nu}(\bar{x}^{k})(\bar{x}^{k+1}-\bar{x}^{k})$, and $\bar{y}^{k+1}$ such
that

$\bar{y}^{k+1}\in\partial h^{\nu}(\bar{z}^{k+1})~{}~{}\mbox{ and
}~{}~{}-\nabla
F^{\nu}(\bar{x}^{k})^{\top}\bar{y}^{k+1}-\tfrac{1}{\lambda^{k}}(\bar{x}^{k+1}-\bar{x}^{k})\in
N_{X^{\nu}}(\bar{x}^{k+1}).$

Set $\bar{u}^{k+1}=F^{\nu}(\bar{x}^{k+1})-\bar{z}^{k+1}$ and
$\bar{w}^{k+1}=\big{(}\nabla F^{\nu}(\bar{x}^{k+1})-\nabla
F^{\nu}(\bar{x}^{k})\big{)}^{\top}\bar{y}^{k+1}-\tfrac{1}{\lambda^{k}}(\bar{x}^{k+1}-\bar{x}^{k})$.

If
$\max\big{\\{}\|\bar{u}^{k+1}\|_{2},\|\bar{w}^{k+1}\|_{2}\big{\\}}\leq\delta^{\nu}$,
then set $x^{\nu}=\bar{x}^{k+1}$, $y^{\nu}=\bar{y}^{k+1}$,
$z^{\nu}=\bar{z}^{k+1}$, replace $\nu$ by $\nu+1$,

and go to Step 1.

Else, replace $k$ by $k+1$, and go to Step 2.

###### 4.1 Theorem

(enhanced proximal composite algorithm). Suppose that $X^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
s$}}\hskip 7.0ptX$ with these sets being convex, $h^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pth$ with $h^{\nu}$ real-valued, and (2.3) holds with
$f_{i}^{\nu}$ twice continuously differentiable for $i=1,\dots,m$. If
$\\{(x^{\nu},y^{\nu},z^{\nu}),\nu\in\mathbb{N}\\}$ is generated by EPCA and
$(x^{\nu},y^{\nu},z^{\nu})\,{\raise
1.0pt\hbox{$\rightarrow$}}\kern-13.0pt\hbox{\lower 3.0pt\hbox{$\,\scriptstyle
N$}}\hskip 7.0pt(\hat{x},\hat{y},\hat{z})$ for some $N\in{\cal
N}_{\infty}^{\scriptscriptstyle\\#}$, then

$\hat{x}\in X,~{}~{}~{}~{}~{}~{}h\big{(}F(\hat{x})\big{)}\leq\mathop{\rm
liminf}\nolimits_{\nu\in
N}h^{\nu}\big{(}F^{\nu}(x^{\nu})\big{)},~{}~{}~{}~{}~{}~{}0\in
S(\hat{x},\hat{y},\hat{z}).$

Proof. The two first claims follow by Corollary 2.5. The construction in Steps
4 and 5 ensures that
$(x^{\nu},y^{\nu},z^{\nu})\in(S^{\nu})^{-1}(\mathbb{B}(0,\delta^{\nu}))$ for
all $\nu$ when the norm on $\mathbb{R}^{2m+n}$ is
$(u,v,w)\mapsto\max\\{\|u\|_{2},\|v\|_{2},\|w\|_{2}\\}$; see the discussion
below. Thus, Corollary 2.5 also confirms that $0\in
S(\hat{x},\hat{y},\hat{z})$.

EPCA solves the sequence of approximating problems using a composite proximal
method of the kind proposed in [35] for each problem. The outer loop indexed
by $\nu$ represents refinement of the approximating problems. The inner loop
indexed by $k$ corresponds to the iterative solution of each approximating
problem by means of solving the convex subproblems in Step 2 obtained by
linearization of $F^{\nu}$. (For inexact solution of such subproblems, we
refer to [22].) The proximal parameter $\lambda^{k}$ is controlled adaptively
using the test in Step 3.

A concern is whether EPCA terminates after a finite $k$ in Step 4 or 5 and
thus always produces the next $(x^{\nu},y^{\nu},z^{\nu})$. This turns out to
be the case as long as

$\big{\\{}\iota_{X^{\nu}}+h^{\nu}\circ F^{\nu}\leq
h^{\nu}\big{(}F^{\nu}(\bar{x}^{0})\big{)}\big{\\}}~{}\mbox{ is bounded,}$
(4.1)

where $\bar{x}^{0}=\operatorname{prj}_{X^{\nu}}(x^{\nu-1})$. We see this as
follows:

An optimality condition for the subproblem in Step 2 states that $x^{\star}$
satisfies

$-\nabla
F^{\nu}(\bar{x}^{k})^{\top}y-\tfrac{1}{\lambda^{k}}(x^{\star}-\bar{x}^{k})\in
N_{X^{\nu}}(x^{\star})~{}\mbox{ for some }~{}y\in\partial
h^{\nu}\big{(}F^{\nu}(\bar{x}^{k})+\nabla
F^{\nu}(\bar{x}^{k})(x^{\star}-\bar{x}^{k})\big{)}.$ (4.2)

Thus, when $x^{\star}=\bar{x}^{k}$, one has $y\in\partial
h^{\nu}(F^{\nu}(\bar{x}^{k}))$ and $-\nabla F^{\nu}(\bar{x}^{k})^{\top}y\in
N_{X^{\nu}}(x^{\star})$. This means that there exists $y^{\nu}$ in Step 4. The
best way to compute such $y^{\nu}$ depends on the nature of $h^{\nu}$ and
$X^{\nu}$, but it can be achieved by convex optimization since it at most
involves finding points in two convex sets. Then,
$(x^{\nu},y^{\nu},z^{\nu})\in(S^{\nu})^{-1}(0)$. In Step 5, there exists
likewise $\bar{y}^{k+1}$ by (4.2), again computable by convex optimization.
The construction in Step 5 ensures that $(\bar{u}^{k+1},0,\bar{w}^{k+1})\in
S^{\nu}(\bar{x}^{k+1},\bar{y}^{k+1},\bar{z}^{k+1})$.

For the sake of contradiction, suppose that the algorithm iterates
indefinitely without generating the next $(x^{\nu},y^{\nu},z^{\nu})$. Let
$\\{\bar{x}^{k},k\in\mathbb{N}\\}$ be the resulting sequence, which has a
cluster point in view of (4.1), say $\bar{x}$. We deduce from [35], especially
Theorem 5.4 and is proof, that $\bar{x}^{k+1}-\bar{x}^{k}\to 0$ as
$k\to\infty$ and $(\bar{x}^{k+1}-\bar{x}^{k})/\lambda^{k}\to 0$ as
$k\to\infty$ along the subsequence corresponding to $\bar{x}$. (We note that
EPCA eventually exits Steps 2-3 and moves to Step 4 or 5, and that
$\\{1/\lambda^{k},k\in\mathbb{N}\\}$ is bounded along the subsequence
corresponding to the cluster point $\bar{x}$.) Then, for $k$ along the
subsequence corresponding to $\bar{x}$, $\bar{z}^{k+1}\to F^{\nu}(\bar{x})$,
which means that the associated sets of subgradients $\partial
h^{\nu}(\bar{z}^{k+1})$ are contained in a compact set and then the same holds
for $\bar{y}^{k+1}$. This fact as well as the recognition that
$F^{\nu}(\bar{x}^{k+1})\to F^{\nu}(\bar{x})$ and $\nabla
F^{\nu}(\bar{x}^{k+1})-\nabla F^{\nu}(\bar{x}^{k})\to 0$ imply that
$\bar{u}^{k+1}\to 0$ and $\bar{w}^{k+1}\to 0$ as $k\to\infty$ along the
subsequence. Consequently, there’s $k^{\star}$ such that
$\max\\{\|\bar{u}^{k^{\star}+1}\|_{2},\|\bar{w}^{k^{\star}+1}\|_{2}\\}\leq\delta^{\nu}$.
We have shown that EPCA augments $\nu$ after some finite $k$ in either Step 4
or 5.

##  5 Inverse Problems in Machine Learning

An inverse problem in machine learning is that of determining an input to a
collection of neural networks such that their outputs best match a given
quantity [28, 30]. Specifically, we are given $s$ neural networks represented
by the mappings $F_{i}:\mathbb{R}^{n_{0}}\to\mathbb{R}^{n_{q}}$,
$i=1,\dots,s$. Each network associates an input vector
$x\in\mathbb{R}^{n_{0}}$ with an output vector
$F_{i}(x)\in\mathbb{R}^{n_{q}}$. The goal is to determine an input vector $x$
such that the output vectors $F_{1}(x),\dots,F_{s}(x)$ are optimized in the
sense of a convex function $\hat{h}:\mathbb{R}^{sn_{q}}\to\mathbb{R}$, i.e.,

$\mathop{\rm
minimize}_{x\in\hat{X}}~{}\hat{h}\big{(}F_{1}(x),\dots,F_{s}(x)\big{)},$ (5.1)

where $\hat{X}\subset\mathbb{R}^{n_{0}}$ is a nonempty closed set that could
impose restrictions on the choice of input vector. For some target output
vector $t\in\mathbb{R}^{n_{q}}$ and nonnegative weights $p_{1},\dots,p_{s}$,
we may simply have

$\hat{h}\big{(}F_{1}(x),\dots,F_{s}(x)\big{)}=\mathop{\sum}\nolimits_{i=1}^{s}p_{i}\big{\|}t-F_{i}(x)\big{\|}_{2}^{2}.$

Suppose that the neural networks are of the feed-forward kind producing their
output from passing through $q$ affine mappings composed with an activation
function. For each layer $k=1,\dots,q$, there is a given $n_{k}\times
n_{k-1}$-matrix $A_{i,k}$, a given vector $b_{i,k}\in\mathbb{R}^{n_{k}}$, and
$F_{i,k}:\mathbb{R}^{n_{k-1}}\to\mathbb{R}^{n_{k}}$ with

$F_{i,k}(x)=G_{i,k}(A_{i,k}x+b_{i,k})~{}~{}\mbox{ for
}~{}x\in\mathbb{R}^{n_{k-1}},$

where $G_{i,k}:\mathbb{R}^{n_{k}}\to\mathbb{R}^{n_{k}}$ has
$G_{i,k}(y)=(g_{i,1,k}(y_{1}),\dots,g_{i,n_{k},k}(y_{n_{k}}))$ for
$y=(y_{1},\dots,y_{n_{k}})\in\mathbb{R}^{n_{k}}$ and
$g_{i,j,k}:\mathbb{R}\to\mathbb{R}$ are given epi-regular lLc functions. For
example, the ReLU function $g_{i,j,k}(\gamma)=\max\\{0,\gamma\\}$ is a common
such activation function; it is epi-regular and lLc. Then,
$F_{i}=F_{i,q}\circ\dots\circ F_{i,1}$.

It is convenient to express (5.1) using additional variables as follows: We
think of $x_{1,i,k}\in\mathbb{R}^{n_{k}}$ as the output of the $k$th layer for
neural network $i$. Let $r=\sum_{k=1}^{q}n_{k}$,
$X=\hat{X}\times\mathbb{R}^{sr}$, and $x=(x_{0},x_{1})$, with
$x_{0}\in\mathbb{R}^{n_{0}}$ and
$x_{1}=(x_{1,1,1},\dots,x_{1,s,q})\in\mathbb{R}^{sr}$. Set

$F(x)=\big{(}x_{1,1,q},\dots,x_{1,s,q},H_{1}(x),\dots,H_{s}(x)\big{)}\in\mathbb{R}^{sn_{q}+sr}~{}~{}~{}\mbox{
and }~{}~{}~{}h(z)=\hat{h}(z_{0})+\iota_{\\{0\\}^{sr}}(z_{1},\dots,z_{s}),$

where, for $z=(z_{0},z_{1},\dots,z_{s})$, with $z_{0}\in\mathbb{R}^{sn_{q}}$
and $z_{i}\in\mathbb{R}^{r}$, $i=1,\dots,s$, and

$H_{i}(x)=\begin{bmatrix}G_{i,1}\big{(}A_{i,1}\,x_{0}+b_{i,1}\big{)}-x_{1,i,1}\\\
G_{i,2}\big{(}A_{i,2}\,x_{1,i,1}+b_{i,2}\big{)}-x_{1,i,2}\\\ \vdots\\\
G_{i,q}\big{(}A_{i,q}\,x_{1,i,q-1}+b_{i,q}\big{)}-x_{1,i,q}\end{bmatrix}.$

Thus, the inverse problem (5.1) is equivalently expressed in the form (1.1)
with $n=n_{0}+sr$ and $m=sn_{q}+sr$; $h$ is proper, lsc, and convex and $F$ is
lLc. For theoretical and computational reasons, several approximations may
arise. Suppose that $A_{i,k}^{\nu}$, $b^{\nu}_{i,k}$, convex
$\hat{h}^{\nu}:\mathbb{R}^{sn_{q}}\to\mathbb{R}$, and epi-regular lLc
$g_{i,j,k}^{\nu}:\mathbb{R}\to\mathbb{R}$ approximate $A_{i,k}$, $b_{i,k}$,
$\hat{h}$, and $g_{i,j,k}$, respectively. The approximating quantities define
$h^{\nu}$ and $F^{\nu}$ via $H_{i}^{\nu}$ and $G_{i,k}^{\nu}$ in the manner
laid out for $h$, $F$, $H_{i}$, and $G_{i,k}$. For simplicity, $\hat{X}$ is
not approximated so that $X^{\nu}=X$. It turns out that weak consistency
follows naturally.

###### 5.1 Proposition

(weak consistency in inverse machine learning). In the notation of this
section, suppose that for each $(i,j,k)$, the following property holds:

$\begin{rcases}\gamma^{\nu}\in\mathbb{R}\to\gamma\\\ \alpha^{\nu}\in\partial
g_{i,j,k}^{\nu}(\gamma^{\nu})\end{rcases}~{}\Longrightarrow~{}\begin{cases}g_{i,j,k}^{\nu}(\gamma^{\nu})\to
g_{i,j,k}(\gamma)\\\ \\{\alpha^{\nu},\nu\in\mathbb{N}\\}\mbox{ is bounded with
all its cluster points in }\partial g_{i,j,k}(\gamma).\end{cases}$ (5.2)

If $A_{i,k}^{\nu}\to A_{i,k}$, $b^{\nu}_{i,k}\to b_{i,k}$, and
$\hat{h}^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pt\hat{h}$, then the resulting pairs
$\\{(\varphi^{\nu},S^{\nu}),\nu\in\mathbb{N}\\}$ are weakly consistent
approximations of $(\varphi,S)$.

Proof. We establish $\varphi^{\nu}\,{\lower
1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise 4.0pt\hbox{$\,\scriptstyle
e$}}\hskip 7.0pt\varphi$ using (1.2) and (1.3). The liminf-condition holds
because $h^{\nu}\,{\lower 1.0pt\hbox{$\rightarrow$}}\kern-10.0pt\hbox{\raise
4.0pt\hbox{$\,\scriptstyle e$}}\hskip 7.0pth$ and $H_{i}^{\nu}(x^{\nu})\to
H_{i}(x)$ whenever $x^{\nu}\to x$. For the limsup-condition, it suffices to
consider $\bar{x}=(\bar{x}_{0},\bar{x}_{1})$ such that $\bar{x}_{0}\in\hat{X}$
and $H_{i}(\bar{x})=0$ for $i=1,\dots,s$. Construct
$x^{\nu}=(x_{0}^{\nu},x_{1}^{\nu})$ with $x_{0}^{\nu}=\bar{x}_{0}$ and
$x_{1}^{\nu}=(x_{1,1,1}^{\nu},\dots,x_{1,s,q}^{\nu})$, where for each
$i=1,\dots,s$,

$x_{1,i,1}^{\nu}=G_{i,1}^{\nu}\big{(}A_{i,1}^{\nu}\,\bar{x}_{0}+b_{i,1}^{\nu}\big{)},~{}~{}x_{1,i,2}^{\nu}=G_{i,2}^{\nu}\big{(}A_{i,2}^{\nu}\,x_{1,i,1}^{\nu}+b_{i,2}^{\nu}\big{)},~{}\dots,~{}x_{1,i,q}^{\nu}=G_{i,q}^{\nu}\big{(}A_{i,q}^{\nu}\,x_{1,i,q-1}^{\nu}+b_{i,q}^{\nu}\big{)}.$

Thus, we have $H_{i}^{\nu}(x^{\nu})=0$ and $x^{\nu}\to\bar{x}$. Since
$\hat{h}$ is real-valued and convex,
$\hat{h}^{\nu}(x_{1,1,q}^{\nu},\dots,x_{1,s,q}^{\nu})$ $\to$
$\hat{h}(\bar{x}_{1,1,q},\dots,\bar{x}_{1,s,q})$ by [50, Thm. 7.17]. This
implies that $\varphi^{\nu}(x^{\nu})\to\varphi(\bar{x})$.

Next, we turn to the optimality conditions. Suppose that
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})$$\in$$\mathop{\rm
LimOut}\nolimits(\operatorname{gph}S^{\nu})$. Then, there are $N\in{\cal
N}_{\infty}^{\scriptscriptstyle\\#}$ and
$(x^{\nu},y^{\nu},z^{\nu},u^{\nu},v^{\nu},w^{\nu})$
$\rightarrow$$\,\scriptstyle N$
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})$ with
$(u^{\nu},v^{\nu},w^{\nu})\in S^{\nu}(x^{\nu},y^{\nu},z^{\nu})$.

Let $A_{i,j,k}$ be the $j$th row of $A_{i,k}$ and $b_{i,j,k}$ be the $j$th
component of $b_{i,k}$, with parallel definitions of $A^{\nu}_{i,j,k}$ and
$b^{\nu}_{i,j,k}$. The $j$th component of $x_{1,i,k}\in\mathbb{R}^{n_{k}}$ is
denoted by $x_{1,i,j,k}$. Moreover, the affine function
$a_{i,j,k}:\mathbb{R}^{n_{0}+sr}\to\mathbb{R}$ has

$a_{i,j,k}(x)=\langle A_{i,j,k},\,x_{1,i,k-1}\rangle+b_{i,j,k}$

with the convention that $x_{1,i,0}=x_{0}$. The function
$f_{i,j,k}:\mathbb{R}^{n_{0}+sr}\to\mathbb{R}$ has

$f_{i,j,k}(x)=g_{i,j,k}\big{(}a_{i,j,k}(x)\big{)}-x_{1,i,j,k}.$

The approximations $a^{\nu}_{i,j,k}$ and $f^{\nu}_{i,j,k}$ are defined
similarly.

Since $u^{\nu}=F^{\nu}(x^{\nu})-z^{\nu}$, we conclude that
$\bar{u}=F(\bar{x})-\bar{z}$; recall that $g_{i,j,k}^{\nu}(\gamma^{\nu})\to
g_{i,j,k}(\gamma)$ when $\gamma^{\nu}\to\gamma$. The fact that
$v^{\nu}+y^{\nu}\in\partial h^{\nu}(z^{\nu})$ implies that
$v^{\nu}_{0}+y^{\nu}_{0}\in\partial\hat{h}^{\nu}(z_{0}^{\nu})$ and
$z_{i}^{\nu}=0$, $v_{i}^{\nu}+y_{i}^{\nu}\in\mathbb{R}^{r}$, $i=1,\dots,s$,
where $v^{\nu}=(v_{0}^{\nu},v_{1}^{\nu},\dots,v_{s}^{\nu})$, with
$v_{0}^{\nu}\in\mathbb{R}^{sn_{q}}$ and $v_{i}^{\nu}\in\mathbb{R}^{r}$ for
$i=1,\dots,s$; the vectors $\bar{v}$, $\bar{y}$, $\bar{z}$, $y^{\nu}$, and
$z^{\nu}$ are partitioned similarly. By Attouch’s theorem [50, Thm. 12.35], we
conclude that $\bar{v}_{0}+\bar{y}_{0}\in\partial\hat{h}(\bar{z}_{0})$. Thus,
$\bar{v}+\bar{y}\in\partial h(\bar{z})$.

It remains to confirm the last portion of $(\bar{u},\bar{v},\bar{w})\in
S(\bar{x},\bar{y},\bar{z})$ involving subgradients of the component functions
of $F$. Since $g_{i,j,k}$ is lLc and epi-regular, the component function
$f_{i,j,k}$ has

$\partial f_{i,j,k}(x)=c_{i,j,k}^{\top}\partial
g_{i,j,k}\big{(}a_{i,j,k}(x)\big{)}-e_{i,j,k},$

where $c_{i,j,k}=\nabla a_{i,j,k}(x)$ and $e_{i,j,k}\in\mathbb{R}^{n_{0}+sr}$
is a vector with a single 1 placed appropriately and with zero elsewhere.
Likewise,

$\partial f^{\nu}_{i,j,k}(x)=(c^{\nu}_{i,j,k})^{\top}\partial
g^{\nu}_{i,j,k}\big{(}a^{\nu}_{i,j,k}(x)\big{)}-e_{i,j,k},$

where $c^{\nu}_{i,j,k}=\nabla a^{\nu}_{i,j,k}(x)$. The assumption (5.2)
implies that any sequence $\\{d_{i,j,k}^{\nu}\in\partial
f^{\nu}_{i,j,k}(x^{\nu}),\nu\in N\\}$ is bounded and thus has a cluster point,
with any such point in $\partial f_{i,j,k}(\bar{x})$. Since $N_{\hat{X}}$ is
outer semicontinuous, we deduce that the last requirement holds and, thus,
$(\bar{u},\bar{v},\bar{w})\in S(\bar{x},\bar{y},\bar{z})$.

A typical activation function is the ReLU with
$g_{i,j,k}(\gamma)=\max\\{0,\gamma\\}$. A smooth approximation could be
$g^{\nu}_{i,j,k}(\gamma)=\frac{1}{\theta^{\nu}}\ln(1+\exp(\theta^{\nu}\gamma))$.
The assumption (5.2) holds in this case; see Example 3.1.

##  6 Rates and Error Estimates

Consistency furnishes guarantees about the limiting behavior of
approximations, but it also can be beneficial to quantify the rate of
convergence. In this section, we refine results from [53] and estimate the
discrepancy between near-solutions of the optimality condition $0\in
S^{\nu}(x,y,z)$ and those of $0\in S(x,y,z)$. Chapter 8 of [16] addresses
similar issues using different techniques, especially for problems with affine
structure. For error estimates of minimizers, minima, and level-sets, we refer
to [52, 53].

The point-to-set distance between $\bar{x}\in\mathbb{R}^{n}$ and
$C\subset\mathbb{R}^{n}$ under norm $\|\cdot\|$ is denoted by

$\operatorname{dist}(\bar{x},C)=\mathop{\rm inf}\nolimits_{x\in
C}\|x-\bar{x}\|~{}\mbox{ when }~{}C\neq\emptyset~{}~{}\mbox{ and
}~{}\operatorname{dist}(\bar{x},\emptyset)=\infty.$

The excess of $C\subset\mathbb{R}^{n}$ over $D\subset\mathbb{R}^{n}$ is
defined as

$\operatorname{exs}(C;D)=\begin{cases}\mathop{\rm sup}\nolimits_{x\in
C}\operatorname{dist}(x,D)&\mbox{ if }C\neq\emptyset,D\neq\emptyset\\\
\infty&\mbox{ if }C\neq\emptyset,D=\emptyset\\\ 0&\mbox{
otherwise.}\end{cases}$

We concentrate on a truncated version given by

$\operatorname{exs}_{\rho}(C;D)=\operatorname{exs}\big{(}C\cap\mathbb{B}(0,\rho);D\big{)}~{}~{}\mbox{
for }\rho\in[0,\infty).$

All these concepts rely on the choice of norm. The Euclidean norm remains the
default, but in the context of $S,S^{\nu}:\mathbb{R}^{n+2m}\;{\lower
1.0pt\hbox{$\rightarrow$}}\kern-12.0pt\hbox{\raise
2.5pt\hbox{$\rightarrow$}}\;\mathbb{R}^{2m+n}$ we adopt the norms given by

$\|(x,y,z)\|_{\rm
in}=\max\big{\\{}\|x\|_{2},\|y\|_{2},\|z\|_{2}\big{\\}}~{}~{}\mbox{ and
}~{}~{}\|(u,v,w)\|_{\rm
out}=\max\big{\\{}\|u\|_{2},\|v\|_{2},\|w\|_{2}\big{\\}}$ (6.1)

for the argument and value spaces, respectively, where $x\in\mathbb{R}^{n}$,
$y\in\mathbb{R}^{m}$, $z\in\mathbb{R}^{m}$, $u\in\mathbb{R}^{m}$,
$v\in\mathbb{R}^{m}$, and $w\in\mathbb{R}^{n}$. The graphs of $S,S^{\nu}$ are
subsets of $\mathbb{R}^{n+2m}\times\mathbb{R}^{2m+n}$, for which we adopt the
norm given by

$\max\big{\\{}\|(x,y,z)\|_{\rm in},\|(u,v,w)\|_{\rm out}\big{\\}}.$ (6.2)

Thus, $S^{-1}(\mathbb{B}(0,\varepsilon))$ is the set of near-solutions of
$0\in S(x,y,z)$ with the tolerance now being specified by $\|\cdot\|_{\rm
out}$, i.e., $(\bar{x},\bar{y},\bar{z})\in S^{-1}(\mathbb{B}(0,\varepsilon))$
if and only if $(\bar{u},\bar{v},\bar{w})\in S(\bar{x},\bar{y},\bar{z})$ and
$\|(\bar{u},\bar{v},\bar{w})\|_{\rm out}\leq\varepsilon$.

###### 6.1 Proposition

(solution error in optimality conditions). Suppose that
$0\leq\delta^{\nu}\leq\rho<\infty$ and
$\varepsilon\geq\delta^{\nu}+\operatorname{exs}_{\rho}(\operatorname{gph}S^{\nu};~{}\operatorname{gph}S)$.
Then, under the norms (6.1) and (6.2), one has

$\operatorname{exs}_{\rho}\Big{(}\,(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)};\,~{}S^{-1}\big{(}\mathbb{B}(0,\varepsilon)\big{)}\,\Big{)}\leq\operatorname{exs}_{\rho}\big{(}\operatorname{gph}S^{\nu};~{}\operatorname{gph}S\big{)}.$

Proof. A slight modification of the proof of Theorem 5.1 in [53] yields this
fact.

The proposition ensures that if
$(\hat{x},\hat{y},\hat{z})\in\mathbb{B}(0,\rho)$ nearly satisfies the
optimality condition $0\in S^{\nu}(x,y,z)$ with tolerance
$\delta^{\nu}\in[0,\infty)$, i.e.,
$\operatorname{dist}(0,S^{\nu}(\hat{x},\hat{y},\hat{z}))\leq\delta^{\nu}$,
then $(\hat{x},\hat{y},\hat{z})$ is no further away than
$\operatorname{exs}_{\rho}(\operatorname{gph}S^{\nu};~{}\operatorname{gph}S)$
from a point that nearly satisfies the optimality condition $0\in S(x,y,z)$
with tolerance $\varepsilon$. Thus, the rate of convergence of near-solutions
of the approximating problems is governed by the rate of decay of
$\operatorname{exs}_{\rho}(\operatorname{gph}S^{\nu};~{}\operatorname{gph}S)$
as $\nu\to\infty$.

In the context of the consistent approximation algorithm, Proposition 6.1
asserts that the solution tolerance $\varepsilon$ (for the actual problem) is
bounded by the sum of $\delta^{\nu}$ (the tolerance adopted when solving the
approximating problem) and the error in the approximation as expressed by
$\operatorname{exs}_{\rho}(\operatorname{gph}S^{\nu};\operatorname{gph}S)$.
Thus, it would be “optimal” to make $\delta^{\nu}$ in the consistent
approximation algorithm vanish at the same rate as
$\operatorname{exs}_{\rho}(\operatorname{gph}S^{\nu};\operatorname{gph}S)$
tends to zero. Concrete illustrations follow in the examples below.

###### 6.2 Theorem

(estimate of excess). Suppose that $\rho\in[0,\infty)$ and $X=X^{\nu}$. Let

$\displaystyle\eta_{0}^{\nu}$
$\displaystyle=\sup\Big{\\{}\big{\|}F^{\nu}(x)-F(x)\big{\|}_{2}~{}\Big{|}~{}x\in
X\cap\mathbb{B}(0,\rho)\Big{\\}}$ $\displaystyle\eta^{\nu}$
$\displaystyle=\sup\Big{\\{}\operatorname{exs}\big{(}\partial
f_{i}^{\nu}(x);\operatorname{con}\partial f_{i}(x)\big{)}~{}\Big{|}~{}x\in
X\cap\mathbb{B}(0,\rho),~{}i=1,\dots,m\Big{\\}}.$

If the norm on $\mathbb{R}^{n+2m}\times\mathbb{R}^{2m+n}$ is (6.2) and the
norm on $\mathbb{R}^{m}\times\mathbb{R}^{m}$ is
$\max\\{\|z\|_{2},\|v\|_{2}\\}$, then one has

$\operatorname{exs}_{\rho}(\operatorname{gph}S^{\nu};~{}\operatorname{gph}S)\leq\max\big{\\{}\sqrt{m}\rho\eta^{\nu},~{}\eta^{\nu}_{0}+\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};~{}\operatorname{gph}\partial h)\big{\\}}.$

Proof. Suppose that
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})\in\operatorname{gph}S^{\nu}\cap\mathbb{B}(0,\rho)$,
where the ball is specified by (6.2). Then,

$\bar{u}=F^{\nu}(\bar{x})-\bar{z},~{}~{}~{}~{}\bar{v}+\bar{y}\in\partial
h^{\nu}(\bar{z}),~{}~{}~{}~{}\bar{w}\in\mathop{\sum}\nolimits_{i=1}^{m}\bar{y}_{i}\operatorname{con}\partial
f_{i}^{\nu}(\bar{x})+N_{X}(\bar{x}).$

We construct a point $(\bar{x},\bar{y},z,u,v,w)\in\operatorname{gph}S$ that is
near $(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})$ in the norm (6.2).

Since
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})\in\mathbb{B}(0,\rho)$, one
has $\max\\{\|\bar{z}\|_{2},\|\bar{v}+\bar{y}\|_{2}\\}\leq 2\rho$. Moreover,
$\operatorname{gph}\partial h$ is nonempty, which follows largely from the
definition of subgradients; cf. [50, Corollary 8.10]. These facts ensure that
there are $z,v\in\mathbb{R}^{m}$ such that
$(z,v+\bar{y})\in\operatorname{gph}\partial h$ and

$\max\Big{\\{}\|z-\bar{z}\|_{2},\big{\|}(v+\bar{y})-(\bar{v}+\bar{y})\big{\|}_{2}\Big{\\}}\leq\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};~{}\operatorname{gph}\partial h).$

There are $\bar{a}_{i}\in\operatorname{con}\partial f_{i}^{\nu}(\bar{x})$ such
that $\bar{w}-\mathop{\sum}\nolimits_{i=1}^{m}\bar{y}_{i}\bar{a}_{i}\in
N_{X}(\bar{x})$. By Caratheodory’s theorem, there exist $\lambda_{i}^{k}\geq
0$ and $a_{i}^{k}\in\partial f_{i}^{\nu}(\bar{x})$, $k=0,1,\dots,n$, such that
$\sum_{k=0}^{n}\lambda_{i}^{k}=1$ and
$\bar{a}_{i}=\sum_{k=0}^{n}\lambda_{i}^{k}a_{i}^{k}$. By assumption, there
exists $b_{i}^{k}\in\operatorname{con}\partial f_{i}(\bar{x})$ such that
$\|a_{i}^{k}-b_{i}^{k}\|_{2}\leq\eta^{\nu}$ and this holds for each $i$ and
$k$. Let $\bar{b}_{i}=\sum_{k=0}^{n}\lambda_{i}^{k}b_{i}^{k}$, which then also
is in $\operatorname{con}\partial f_{i}(\bar{x})$. We construct

$w=\bar{w}+\mathop{\sum}\nolimits_{i=1}^{m}\bar{y}_{i}(\bar{b}_{i}-\bar{a}_{i})~{}~{}~{}\mbox{
and }~{}~{}~{}u=F(\bar{x})-z.$

It now follows that $(\bar{x},\bar{y},z,u,v,w)\in\operatorname{gph}S$ and it
remains to compute the distance between this point and
$(\bar{x},\bar{y},\bar{z},\bar{u},\bar{v},\bar{w})$. We already have
$\max\\{\|z-\bar{z}\|_{2},\|v-\bar{v}\|_{2}\\}\leq\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};~{}\operatorname{gph}\partial h)$. Moreover,

$\|u-\bar{u}\|_{2}\leq\big{\|}F^{\nu}(\bar{x})-F(\bar{x})\big{\|}_{2}+\|z-\bar{z}\|_{2}\leq\eta_{0}^{\nu}+\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};~{}\operatorname{gph}\partial h).$

Finally, one has
$\|w-\bar{w}\|_{2}\leq\mathop{\sum}\nolimits_{i=1}^{m}|\bar{y}_{i}|\|\bar{b}_{i}-\bar{a}_{i}\|_{2}\leq\sqrt{m}\rho\eta^{\nu}$.

The theorem allows us to bound the solution error associated with a particular
approximation in terms of the error in the individual components $h^{\nu}$ and
$F^{\nu}$. (We refer to [53] for error estimates involving $X^{\nu}\neq X$ in
the simplified setting with smooth $F$.) Thus, the focus turns to estimating
the component errors. For that purpose, the following fact, which is a direct
application of Theorem 5.2 in [1], is useful. It leverages the truncated
Hausdorff distance between the sets $C$ and $D$:

$d\hat{\kern-1.49994ptl}_{\rho}(C,D)=\max\big{\\{}\operatorname{exs}_{\rho}(C;D);\,\operatorname{exs}_{\rho}(D;C)\big{\\}}.$

###### 6.3 Proposition

(approximation of subgradients). Suppose that the norm on $\mathbb{R}^{m+1}$
is $\max\\{\|z\|_{2},|\alpha|\\}$, the norm on
$\mathbb{R}^{m}\times\mathbb{R}^{m}$ is $\max\\{\|z\|_{2},\|v\|_{2}\\}$, and
$\rho>\max\\{\operatorname{dist}(0,\operatorname{epi}h^{\nu}),\operatorname{dist}(0,\operatorname{epi}h)\\}$.
Then, there are $\alpha,\bar{\rho}\in[0,\infty)$, dependent on $\rho$, such
that

$\operatorname{exs}_{\rho}\big{(}\operatorname{gph}\partial
h^{\nu};\,\operatorname{gph}\partial h\big{)}\leq
d\hat{\kern-1.49994ptl}_{\rho}\big{(}\operatorname{gph}\partial
h^{\nu},\,\operatorname{gph}\partial
h\big{)}\leq\alpha\sqrt{d\hat{\kern-1.49994ptl}_{\bar{\rho}}(\operatorname{epi}h^{\nu},\operatorname{epi}h)}\leq\alpha\sqrt{\mathop{\rm
sup}\nolimits_{z\in\mathbb{B}(0,\bar{\rho})}\big{|}h(z)-h^{\nu}(z)\big{|}}.$

The truncated Hausdorff distance between epigraphs can be computed using
results from [53], with the sup-expression given above being among the crudest
possibilities.

###### 6.4 Example

(goal optimization; cont.). In Example 3.1, smoothing of $h^{\nu}$ causes a
solution error

$\operatorname{exs}_{\rho}\Big{(}\,(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)};\,~{}S^{-1}\big{(}\mathbb{B}(0,\varepsilon)\big{)}\,\Big{)}\leq\beta/\sqrt{\theta^{\nu}}$

for a constant $\beta$ when $0\leq\delta^{\nu}\leq\rho<\infty$,
$\varepsilon\geq\delta^{\nu}+\beta/\sqrt{\theta^{\nu}}$, and
$\rho>{\raisebox{1.0pt}{$\frac{1}{2}$}}\max\\{\sqrt{\sum_{i=1}^{m}\min\\{0,\tau_{i}\\}^{2}},\bar{\alpha}/\theta^{\nu}\\}$,
where $\bar{\alpha}=(\ln 2)(\sum_{i=1}^{m}\alpha_{i})$.

Detail. Since $\mathop{\rm
sup}\nolimits_{z\in\mathbb{R}^{m}}|h^{\nu}(z)-h(z)|\leq\bar{\alpha}/\theta^{\nu}$
by Example 3.1, we obtain via Proposition 6.3 that

$\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};\,\operatorname{gph}\partial
h)\leq\alpha\sqrt{\bar{\alpha}/\theta^{\nu}}$

for some $\alpha\in[0,\infty)$ when $\rho$ is sufficiently large as indicated.
The claim then follows by Theorem 6.2 and Proposition 6.1.

###### 6.5 Example

(distributionally robust optimization; cont.). For Example 3.3, there is a
constant $\beta\in[0,\infty)$ such that

$\operatorname{exs}_{\rho}\Big{(}\,(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)};\,~{}S^{-1}\big{(}\mathbb{B}(0,\varepsilon)\big{)}\,\Big{)}\leq\beta\sqrt{\alpha^{\nu}}$

as long as $0\leq\delta^{\nu}\leq\rho<\infty$ and
$\varepsilon\geq\delta^{\nu}+\beta\sqrt{\alpha^{\nu}}$, where
$\alpha^{\nu}=\max\\{\operatorname{exs}(A;A^{\nu}),\operatorname{exs}(A^{\nu};A)\\}$.

Detail. Since
$\operatorname{dist}(0,\operatorname{epi}h^{\nu})=\operatorname{dist}(0,\operatorname{epi}h)=0$,
it follows by Proposition 6.3 that

$d\hat{\kern-1.49994ptl}_{2\rho}(\operatorname{gph}\partial
h^{\nu},\operatorname{gph}\partial h)\leq\alpha\sqrt{\mathop{\rm
sup}\nolimits_{z\in\mathbb{B}(0,\bar{\rho})}\big{|}h(z)-h^{\nu}(z)\big{|}}$
(6.3)

for some $\alpha,\bar{\rho}\in[0,\infty)$. Fix $z\in\mathbb{B}(0,\bar{\rho})$
and let $p^{\nu}\in\hat{A}^{\nu}(z)$; see Example 3.3 for notation. Then,
there exists $\bar{p}\in A$ such that
$\|p^{\nu}-\bar{p}\|_{2}\leq\alpha^{\nu}$. Thus, $h^{\nu}(z)-h(z)\leq\langle
p^{\nu}-\bar{p},z\rangle\leq\|p^{\nu}-\bar{p}\|_{2}\|z\|_{2}\leq\bar{\rho}\alpha^{\nu}$.
We repeat this argument with the roles of $h$ and $h^{\nu}$ reversed and
conclude that $|h(z)-h^{\nu}(z)|\leq\bar{\rho}\alpha^{\nu}$. In combination
with (6.3), Theorem 6.2, and Proposition 6.1, the claim follows.

###### 6.6 Example

(augmented Lagrangian methods; cont.). For Example 3.4, we obtain that

$\operatorname{exs}_{\rho}\Big{(}\,(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)};\,~{}S^{-1}\big{(}\mathbb{B}(0,\varepsilon)\big{)}\,\Big{)}\leq\beta^{\nu}/\theta^{\nu},~{}\mbox{
where }\beta^{\nu}=\big{(}2\rho+\|y^{\nu}\|_{\infty}\big{)}\sqrt{m-1},$

provided that $0\leq\delta^{\nu}\leq\rho<\infty$ and
$\varepsilon\geq\delta^{\nu}+\beta^{\nu}/\theta^{\nu}$.

Detail. In this case, $\operatorname{gph}\partial
h=(\mathbb{R}\times\\{0\\}^{m-1})\times(\\{1\\}\times\mathbb{R}^{m-1})$ and

$\operatorname{gph}\partial
h^{\nu}=\big{\\{}(z,v)\in\mathbb{R}^{2m}~{}\big{|}~{}v=(1,y_{2}^{\nu}+\theta^{\nu}z_{2},\dots,y_{m}^{\nu}+\theta^{\nu}z_{m})\big{\\}}.$

In view Proposition 6.1 and Theorem 6.2, it suffices to bound
$\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};\operatorname{gph}\partial h)$. Let
$(z^{\nu},v^{\nu})\in\operatorname{gph}\partial
h^{\nu}\cap\mathbb{B}(0,2\rho)$. We construct
$(\bar{z},\bar{v})\in\operatorname{gph}\partial h$ by setting $\bar{v}_{1}=1$,
$\bar{z}_{1}=z_{1}^{\nu}$, $\bar{z}_{i}=0$,
$\bar{v}_{i}=y_{i}^{\nu}+\theta^{\nu}z_{i}^{\nu}$ for $i=2,\dots,m$. Since
$\|v^{\nu}\|_{2}\leq 2\rho$, one has $|v_{i}^{\nu}|\leq 2\rho$ and
$|y_{i}^{\nu}+\theta^{\nu}z_{i}^{\nu}|\leq 2\rho$ for $i=2,\dots,m$. Moreover,
$\|v^{\nu}-\bar{v}\|_{2}^{2}=0$ and

$\|z^{\nu}-\bar{z}\|_{2}^{2}=\mathop{\sum}\nolimits_{i=2}^{m}(z_{i}^{\nu}-\bar{z}_{i})^{2}=\mathop{\sum}\nolimits_{i=2}^{m}(z_{i}^{\nu})^{2}\leq\mathop{\sum}\nolimits_{i=2}^{m}\Big{(}\frac{2\rho+|y_{i}^{\nu}|}{\theta^{\nu}}\Big{)}^{2}\leq(\beta^{\nu}/\theta^{\nu})^{2}.$

Thus, the distance (in the appropriate norm) between $(z^{\nu},v^{\nu})$ and
$(\bar{z},\bar{v})$ is at most $\beta^{\nu}/\theta^{\nu}$.

###### 6.7 Example

(exact penalty methods). We next approach the problem in Example 3.4 using an
exact penalty method. Thus, $h(z)=z_{1}+\sum_{i=2}^{m}\iota_{\\{0\\}}(z_{i})$
as before, but for $\theta^{\nu}\in[0,\infty)$ we set

$h^{\nu}(z)=z_{1}+\mathop{\sum}\nolimits_{i=2}^{m}\theta^{\nu}|z_{i}|.$

If $\theta^{\nu}\to\infty$, then the resulting approximations are consistent;
the details are omitted. Interestingly,

$(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)}\cap\mathbb{B}(0,\rho)\subset
S^{-1}\big{(}\mathbb{B}(0,\varepsilon)\big{)}$

provided that $0\leq\delta^{\nu}\leq\rho<\infty$,
$\varepsilon\geq\delta^{\nu}$, and $\theta^{\nu}\geq 2\rho$. This means that
the approximating problem has a certain “exactness” property: for sufficiently
large $\theta^{\nu}$, satisfaction of the optimality condition for the
approximation problem locally in $\mathbb{B}(0,\rho)$ implies satisfaction of
the condition for the actual problem.

Detail. Example 6.6 furnishes $\operatorname{gph}\partial h$. Moreover,
$\partial h^{\nu}(z)=\\{1\\}\times C_{2}\times\cdots\times C_{m}$, where
$C_{i}=\\{\theta^{\nu}\\}$ if $z_{i}>0$, $C_{i}=[-\theta^{\nu},\theta^{\nu}]$
if $z_{i}=0$, and $C_{i}=\\{-\theta^{\nu}\\}$ otherwise.

Suppose that $\theta^{\nu}\geq 2\rho$. Let
$(z^{\nu},v^{\nu})\in\operatorname{gph}\partial
h^{\nu}\cap\mathbb{B}(0,2\rho)$. Then, $v_{1}^{\nu}=1$ and $v_{i}^{\nu}\in
C_{i}$ for $i=2,\dots,m$. Since $\|v^{\nu}\|_{2}\leq 2\rho$, one has
$|v_{i}^{\nu}|<2\rho\leq\theta^{\nu}$ for $i=2,\dots,m$. This means that
$z_{i}^{\nu}=0$ for such $i$ in view of the definition of $C_{i}$. We conclude
that $(z^{\nu},v^{\nu})\in\operatorname{gph}\partial h$ and
$\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};\,\operatorname{gph}\partial h)=0$. This in turn implies that
$\operatorname{exs}_{\rho}(\operatorname{gph}S^{\nu};\,\operatorname{gph}S)=0$
by Theorem 6.2. The claim follows from Proposition 6.1.

###### 6.8 Example

(homotopy method; cont.). In Example 3.10, we obtain for
$\lambda^{\nu}\in(0,1)$ that

$\operatorname{exs}_{\rho}\Big{(}\,(S^{\nu})^{-1}\big{(}\mathbb{B}(0,\delta^{\nu})\big{)};\,~{}S^{-1}\big{(}\mathbb{B}(0,\varepsilon)\big{)}\,\Big{)}\leq\beta^{\nu}\lambda^{\nu},\mbox{
where
}\beta^{\nu}=\sqrt{1+\frac{4\rho^{2}-(\lambda^{\nu})^{2}}{(1-\lambda^{\nu})^{2}}},$

provided that $0\leq\delta^{\nu}\leq\rho<\infty$,
$\varepsilon\geq\delta^{\nu}+\beta^{\nu}\lambda^{\nu}$, and
$\rho\geq\lambda^{\nu}/2$.

Detail. In this case, $\partial
h(z)=\partial\hat{h}(z_{1},\dots,z_{m-1})\times\\{0\\}$ and $\partial
h^{\nu}(z)=(1-\lambda^{\nu})\partial\hat{h}(z_{1},\dots,z_{m-1})\times\\{\lambda^{\nu}\\}$.
To bound $\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};\,\operatorname{gph}\partial h)$, let
$(z^{\nu},v^{\nu})\in\operatorname{gph}\partial
h^{\nu}\cap\mathbb{B}(0,2\rho)$. Then
$v^{\nu}=((1-\lambda^{\nu})\hat{y}^{\nu},\lambda^{\nu})$ with
$\hat{y}^{\nu}\in\partial\hat{h}(z_{1}^{\nu},\dots,z_{m-1}^{\nu})$. We
construct $(\bar{z},\bar{v})\in\operatorname{gph}\partial h$ by setting
$\bar{v}=(\hat{y}^{\nu},0)$ and $\bar{z}=z^{\nu}$. Then, one has
$\|z^{\nu}-\bar{z}\|_{2}=0$ and
$\|v^{\nu}-\bar{v}\|_{2}^{2}=(1+\|\hat{y}^{\nu}\|_{2}^{2})(\lambda^{\nu})^{2}$.
Since
$\|v^{\nu}\|_{2}^{2}=(1-\lambda^{\nu})^{2}\|\hat{y}^{\nu}\|_{2}^{2}+(\lambda^{\nu})^{2}\leq
4\rho^{2}$, we obtain that $1+\|\hat{y}^{\nu}\|_{2}^{2}\leq(\beta^{\nu})^{2}$.
From this we conclude that
$\operatorname{exs}_{2\rho}(\operatorname{gph}\partial
h^{\nu};\,\operatorname{gph}\partial h)\leq\beta^{\nu}\lambda^{\nu}$. The
result then follows by Theorem 6.2 and Proposition 6.1.

Acknowledgement. The author is thankful to K. Balasubramanian (UC Davis) for
introducing him to the inverse problem in Section 5. The research is supported
in part by ONR Science of Autonomy (N0001421WX00142) and AFOSR (18RT0599,
21RT0484).

## References

  * [1] H. Attouch and R. J-B Wets.  Quantitative stability of variational systems: I. The epigraphical distance.  Transactions of the American Mathematical Society, 328(2):695–729, 1991.
  * [2] H. Attouch and R. J-B Wets.  Quantitative stability of variational systems: II. A framework for nonlinear conditioning.  SIAM J. Optimization, 3:359–381, 1993.
  * [3] H. Attouch and R. J-B Wets.  Quantitative stability of variational systems: III. $\varepsilon$-approximate solutions.  Mathematical Programming, 61:197–214, 1993.
  * [4] S. Basu, P. Pope, and S. Feizi.  Influence functions in deep learning are fragile.  arXiv:2006.14651, 2020.
  * [5] A. Beck and M. Teboulle.  Smoothing and first order methods: A unified framework.  SIAM J. Optimization, 22(2):557–580, 2012.
  * [6] A. Ben-Tal and A. Nemirovski.  On polyhedral approximations of the second-order cone.  Mathematics of Operations Research, 26(2):193–205, 2001.
  * [7] J.F. Bonnans and A. Shapiro.  Perturbation Analysis of Optimization Problems.  Springer, 2000.
  * [8] J.V. Burke.  Descent methods for composite nondifferentiable optimization problems.  Mathematical Programming, 33(3):260–279, 1985.
  * [9] J.V. Burke and M.C. Ferris.  A Gauss-Newton method for convex composite optimization.  Mathematical Programming, 71:179–194, 1995.
  * [10] J.V. Burke and T. Hoheisel.  Epi-convergent smoothing with applications to convex composite functions.  SIAM J. Optimization, 23(3):1457–1479, 2013.
  * [11] J.V. Burke and T. Hoheisel.  Epi-convergence properties of smoothing by infimal convolution.  Set-Valued and Variational Analysis, 25:1–23, 2017.
  * [12] J.V. Burke, T. Hoheisel, and C. Kanzow.  Gradient consistency for integral-convolution smoothing functions.  Set-Valued and Variational Analysis, 21(2):359–376, 2013.
  * [13] J.V. Burke, T. Hoheisel, and Q.V. Nguyen.  A study of convex convex-composite functions via infimal convolution with applications.  Mathematics of Operations Research, 46(4):1324–1348, 2021.
  * [14] X. Chen.  Smoothing methods for nonsmooth, nonconvex minimization.  Mathematical Programming, 134:71–99, 2012.
  * [15] X. Chen and O. L. Mangasarian.  A class of smoothing functions for nonlinear and mixed complementarity problems.  Mathematical Programming, 71:51–70, 1995.
  * [16] Y. Cui and J.-S. Pang.  Modern Nonconvex Nondifferentiable Optimization.  SIAM, 2021.
  * [17] Y. Cui, J.-S. Pang, and B. Sen.  Composite difference-max programs for modern statistical estimation problems.  SIAM J. Optimization, 28(4):3344–3374, 2018.
  * [18] D. Davis and D. Drusvyatskiy.  Stochastic model-based minimization of weakly convex functions.  SIAM J. Optimization, 29(1):207–239, 2019.
  * [19] D. Davis and D. Drusvyatskiy.  Graphical convergence of subgradients in nonconvex optimization and learning.  Mathematics of Operations Research, 47(1):209–231, 2022.
  * [20] D. Drusvyatskiy and A.S. Lewis.  Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential.  SIAM J. Optimization, 23:256–267, 2013.
  * [21] D. Drusvyatskiy and A.S. Lewis.  Error bounds, quadratic growth, and linear convergence of proximal methods.  Mathematics of Operations Research, 43(3):919–948, 2018.
  * [22] D. Drusvyatskiy and C. Paquette.  Efficiency of minimizing compositions of convex functions and smooth maps.  Mathematical Programming, 178:503–558, 2019.
  * [23] J.C. Duchi and F. Ruan.  Stochastic methods for composite and weakly convex optimization problems.  SIAM J. Optimization, 28(4):3229–3259, 2018.
  * [24] A.C. Eberhard and R. Wenczel.  A study of tilt-stable optimality and sufficient conditions.  Nonlinear Analysis, 75:1260–1281, 2012.
  * [25] Y.M. Ermoliev, V.I. Norkin, and R.J-B Wets.  The minimization of discontinuous functions: mollifier subgradients.  SIAM J. Control and Optimization, 33(1):149–167, 1995.
  * [26] R. Fletcher.  Nondifferential and variational techniques in optimization.  In D.C. Sorensen and R. J-B Wets, editors, Nondifferential and variational techniques in optimization, Mathematical Programming Study 17, page 67–76. Academic Press, 1982.
  * [27] J.C. Foraker, J.O. Royset, and I. Kaminer.  Search-trajectory optimization: Part 1, formulation and theory.  J. Optimization Theory and Applications, 169(2):530–549, 2016.
  * [28] P. Hand and V. Voroninski.  Global guarantees for enforcing deep generative priors by empirical risk.  In 31st Annual Conference On Learning Theory, 2018.
  * [29] J.L. Higle and S. Sen.  Epigraphical nesting: A unifying theory for the convergence of algorithms.  J. Optimization Theory and Applications, 84(2):339–360, 1995.
  * [30] W. Huang, P. Hand, R. Heckel, and V. Voroninski.  A provably convergent scheme for compressive sensing under random generative priors.  J. Fourier Analysis and Applications, 27(2):1–34, 2021.
  * [31] A.D. Ioffe and J.V. Outrata.  On metric and calmness qualification conditions in subdifferential calculus.  Set-Valued and Variational Analysis, 16(2-3):199–227, 2008.
  * [32] D. Klatte, A. Kruger, and B. Kummer.  From convergence principles to stability and optimality conditions.  J. Convex Analysis, 19(4):1043–1072, 2012.
  * [33] P.W. Koh and P. Liang.  Understanding black-box predictions via influence functions.  arXiv:1703.04730, 2017.
  * [34] D.P. Kouri and T.M. Surowiec.  Epi-regularization of risk measures.  Mathematics of Operations Research, 45(2):774–795, 2020.
  * [35] A.S. Lewis and S.J. Wright.  A proximal method for composite minimization.  Mathematical Programming, 158:501–546, 2016.
  * [36] A.S. Lewis and S. Zhang.  Partial smoothness, tilt stability, and generalized Hessians.  SIAM J. Optimization, 23:74–94, 2013.
  * [37] B.S. Mordukhovich.  Variational Analysis and Generalized Differentiation I: Basic Theory.  Grundlehren der mathematischen Wissenschaften. Springer, 2. edition, 2013\.
  * [38] B.S. Mordukhovich, R.T. Rockafellar, and M.E. Sarabi.  Characterizations of full stability in constrained optimization.  SIAM J. Optimization, 23:1810–1849, 2013.
  * [39] Y. Nesterov.  Smooth minimization of non-smooth functions.  Mathematical Programming, 103:127–152, 2005.
  * [40] J.P. Penot.  Error bounds, calmness and their applications in nonsmooth analysis.  Contemporary Mathematics, 514:225–247, 2010.
  * [41] C. Phelps, J.O. Royset, and Q. Gong.  Optimal control of uncertain systems using sample average approximations.  SIAM J. Control and Optimization, 54(1):1–29, 2016.
  * [42] E. Polak.  Optimization. Algorithms and Consistent Approximations, volume 124 of Applied Mathematical Sciences.  Springer, 1997.
  * [43] E. Polak, J.O. Royset, and R.S. Womersley.  Algorithms with adaptive smoothing for finite minimax problems.  J. Optimization Theory and Applications, 119(3):459–484, 2003.
  * [44] R.A. Poliquin.  An extension of Attouch’s theorem and its application to second-order epi-differentiation of convexly composite functions.  Transactions of the American Mathematical Society, 332(2):861–874, 1992.
  * [45] M.J.D. Powell.  Algorithms for nonlinear constraints that use Lagrangian functions.  Mathematical Programming, 14(2):224–248, 1978.
  * [46] M.J.D. Powell.  A fast algorithm for nonlinearly constrained optimization calculations.  In G.A. Watson, editor, Numerical Analysis, Lecture Notes in Mathematics, vol. 630, page 144–157. Springer, 1978.
  * [47] M.J.D. Powell.  General algorithms for discrete nonlinear approximation calculations.  In Approximation Theory, IV, page 187–218. Academic Press, 1983\.
  * [48] M.J.D. Powell.  On the global convergence of trust region algorithms for unconstrained minimization.  Mathematical Programming, 29(3):299–303, 1984.
  * [49] R.T. Rockafellar.  Extended nonlinear programming.  In G. Di Pillo and R. Giannessi, editors, Nonlinear Optimization and Related Topics, pages 381–399. Kluwer, 1999.
  * [50] R.T. Rockafellar and R. J-B Wets.  Variational Analysis.  Springer, 3rd printing-2009 edition, 1998.
  * [51] J.O. Royset.  Optimality functions in stochastic programming.  Mathematical Programming, 135(1):293–321, 2012.
  * [52] J.O. Royset.  Approximations and solution estimates in optimization.  Mathematical Programming, 170(2):479–506, 2018.