M.P. Friedlander, A. Goodwin, and T. Hoheisel

From perspective maps to epigraphical projections

From perspective maps to epigraphical projections

Michael P. Friedlander
Department of Computer Science/Department of Mathematics,
University of British Columbia

2366 Main Mall
Vancouver, BC, V6T 1Z4, Canada

<EMAIL_ADDRESS>https://friedlander.io

Ariel Goodwin
Department of Mathematics and Statistics, McGill University
805 Sherbrooke St West, Montréal, Québec,  H3A 0B9, Canada

<EMAIL_ADDRESS>https://github.com/arielgoodwin

Tim Hoheisel
Department of Mathematics and Statistics, McGill University
805 Sherbrooke St West, Montréal, Québec,  H3A 0B9, Canada

<EMAIL_ADDRESS>https://www.math.mcgill.ca/hoheisel/

Dedicated to  James V. Burke, our  collaborator and friend,  on the occasion of his 65th birthday

The projection onto the epigraph or a level set of a closed  proper convex function can be achieved by finding a root of  a scalar equation  that involves the proximal operator as a function of the proximal parameter.
This paper develops the variational analysis of this scalar equation. The approach is based on a study of the variational-analytic properties of general convex optimization problems that are (partial) infimal projections of the the sum of the function in question and the perspective map of a convex kernel. When the kernel is the Euclidean norm squared, the solution map corresponds to the proximal map, and thus the variational properties derived for the general case apply to the proximal case. Properties of the value function and the corresponding solution map—including local Lipschitz continuity, directional differentiability, and semismoothness—are derived. An SC$^1$ optimization framework for computing epigraphical and level-set projections is thus established. Numerical experiments on 1-norm projection illustrate the effectiveness of the approach as compared with specialized algorithms.

Proximal map,   Moreau envelope, subdifferential, Fenchel conjugate, perspective map, epigraph, infimal projection,  infimal convolution, set-valued map,  coderivative, graphical derivative,  semismoothness*, SC$^{1}$ optimization
52A4, 65K10, 90C25, 90C46

§ INTRODUCTION

The Moreau proximal map of a closed proper convex function $f$ that maps a finite-dimensional Euclidean space $\bE_f$ to $\rbar:=\R\cup\{+\infty\}$ is given by the minimizing set

\begin{equation*}
P_{\lambda} f( x)=\argmin_{u\in \bE_f}\left\{ f(u)+(1/2\lambda) \|x-u\|^2\right\}\quad (\lambda>0).
\end{equation*}

The proximal map is a central operation of algorithms for nonsmooth optimization, including first-order methods such as proximal gradient and operator splitting [43, 4]. Geometrically, the proximal map corresponds to the Euclidean  projection  $\proj_{\epi f}$ onto the epigraph $\epi f$; see <ref>. Indeed, for all positive $\lambda$ and  $x_\lambda:=\prox_{\lambda}f(x)$,

\begin{equation}\label{eq:EpiProx}
\big(x_\lambda,\, f(x_\lambda)\big)
= P_{\epi f}(x,\,f(x_\lambda)-\lambda).
\end{equation}

Thus, the projection of an arbitrary point $(x,\alpha)\in\bE_f\times\R\not\in\epi f$ corresponds to the proximal map of the base point $x$ using the parameter $\lambda$ that is the unique positive root of the function

\begin{equation}\label{eq:root}
0<\lambda\mapsto f(x_\lambda)-\lambda-\alpha.
\end{equation}

This connection between epigraphical projection and the proximal map—described by Beck [5], Bauschke and Combettes <cit.>, Chierchia et al. <cit.>, and Meng et al. [39, 40]—is a defining feature of a class of epigraphical first-order methods for structured convex optimization over $\bE_f$ that operate through a sequence of projections onto the epigraphs of the underlying functions. In effect, these methods operate on an equivalent optimization problem over $\bE_f\times\R$ [16, 53, 51, 52].

The proximal map $x_\lambda:=P_\lambda f(x)$ corresponds to the projection of the pair $(x,\,f(x_\lambda)-\lambda))$ onto the epigraph of $f$; see (<ref>).

This paper develops a general analysis that provides, among other things, the variational properties of the maps

\begin{align*}
(x,\,\lambda)\mapsto x_\lambda:= P_\lambda f(x)
\quad\UND\quad
(x,\,\lambda)\mapsto f(x_\lambda),
\end{align*}

defined on $\bE_f\times\bR$. This analysis and its supporting calculus allows us to determine the sensitivity of the epigraphical projection with respect to the simultaneous variation of the base point $x$ and the scaling parameter $\lambda$.  Although the resulting mathematical statements are key for our deeper understanding of epigraphical first-order methods, the overall analysis applies much more generally.

The approach we take is based on the variational analysis of the optimal value function

\begin{equation}\label{eq:PerOpt}
\pLwf:(x,\,\lambda)\in\bE_x\times\R\mapsto\inf_{u\in\bE_f}
\end{equation}

and its corresponding solution map. Here, $L$ is a linear map, and the perspective transform $\omega^\pi$ of a closed proper convex function $\omega$ is defined by $\epi\omega^\pi=\cl\R_+(\epi\omega\times\{1\})$. When the linear map $L$ is defined as $(u,\,x)\mapsto x-u$, the value function (<ref>) is the infimal convolution of the functions $f$ and $\omega^\pi(\cdot,\,\lambda)$. For this reason, we refer to this value function as the generalized convolution of these two functions.

The convex calculus we establish in <ref> for the analysis of the generalized convolution (<ref>) provides a key tool for understanding several important cases. These include the variational properties of infimal convolution (<ref>); parametric constrained optimization (<ref>); the Moreau envelope of a convex function and the corresponding proximal map (<ref>); and epigraphical and level-set projections, including an SC${^1}$ optimization [25, 44] method for numerically evaluating these projections (<ref>).

§.§ Contributions and related work

The perspective map used in generalized convolution (<ref>) first appears in Rockafellar <cit.>, without a particular name attached to it. More recently, Combettes [18], Combettes and Müller [19, 20], and Aravkin et al. [2], describe in detail the properties and applications of this map. Our systematic study of parametric optimization problems with perspective maps, outlined in <ref>, appears to be new.

§.§.§ Infimal convolution
<Ref> establishes the variational properties of infimal convolution, which occurs when the map $L$ is $(u,x)\mapsto x-u$. These results complement the functional smoothing framework described by Beck and Teboulle <cit.> and Burke and Hoheisel [10, 12], wherein a smooth approximation to a function $f$ is constructed through the infimal convolution with the perspective map of a smooth and strongly convex regularizer $\omega$. Bougeard et al. [9] and Strömberg [50] provide early contributions to this topic. <ref> describes the Lipschitzian properties of the corresponding optimal solution map—as a function of $(x,\lambda)$.   <ref> establishes sufficient conditions for this solution map to be semismooth* [28]. These conditions hold, for instance, when $f$ is piecewise linear-quadratic. This analysis complements the study of the proximal case by Meng et al. [39, 40] and Milzarek [41].

§.§.§ Parametric constrained optimization
A general form of parametric constrained optimization occurs when we specialize the convolution kernel $\omega$ in (<ref>) to be the indicator function to a closed convex set. <Ref> focuses the variational analysis of the generalized convolution operation to obtain formulas for the sensitivity of the optimal value of parametric optimization problems with relaxed linear constraints. This analysis includes perturbations to the relaxation parameter and to the right-hand side.

§.§.§ Moreau envelope and proximal map
In <ref> we further focus our analysis of infimal convolution on the proximal case, which occurs when $\omega=\frac12\|\cdot\|_2^2$. Here we develop the variational properties of the Moreau envelope and the associated proximal map as a function of the base point $x$ and the proximal parameter $\lambda$, simultaneously.  We also establish conditions under which the proximal map is semismooth*. Special attention is given to the limiting properties as $\lambda\downarrow 0$ (<ref>) and to  continuity and smoothness properties of the proximal map (<ref>). Milzarek's dissertation [41] includes a related analysis that generalizes the proximal parameter $\lambda$ to a positive-definite matrix, but makes no statements regarding the limiting case where $\lambda$ (or its matrix counterpart) vanishes, as we do in our general analysis. See also Attouch's seminal monograph [3].

§.§.§ Proximal value map

In <ref> we describe the main continuity properties of the proximal value function

\begin{equation}\label{eq:proximal-value-fn}
0<\lambda\mapsto f(P_\lambda f(\bar x)),
\end{equation}

where $\bar x\in\bE$ is held fixed. <Ref> establishes its Lipschitzian properties and <ref> characterizes it as the derivative of the map $\lambda\mapsto \lambda e_\lambda f(\bar x)$ on $\R_{++}$.  <Ref> describes sufficient conditions under which the proximal value function is semismooth.

§.§.§ Post compositions, and  epigraphical and level-set projection

We use our analysis of the proximal value function (<ref>) to establish, via <ref>, novel variational formulas for the Moreau envelope and proximal map of post-compositions, i.e., functions of the form $g\circ \psi$, where the scalar function $g$ is increasing and convex, and $\psi$ is  closed proper convex. As a consequence, <ref> provides a refined version of the epigraphical projection conditions in (<ref>), including analogous results for the projection onto the level set of $f$ (<ref>). This analysis does not require the function to be finite-valued, and extends existing results [4, 5]. Importantly, <ref> shows that the root of the aligning equation (<ref>) coincides with the unique minimizer of a strongly convex scalar optimization problem. It follows from <ref> that the objective for this problem is continuously differentiable with a locally Lipschitz derivative.  We use this latter property to derive a novel SC$^1$ optimization method to find the root of the function (<ref>) and its analog in the level-set case. Numerical experiments in <ref> show that for projection onto the 1-norm unit ball, the resulting SC$^1$ method is competitive with two specialized state-of-the-art methods: CONDAT [21] and IBIS [37].

§.§ Notation

Let $\Gamma_0(\bE)$ denote the set of functions $f:\bE\to\rbar$ that are proper closed convex, i.e., the epigraph $\epi f=\set{(x,\alpha)\in\bE\times\R}{f(x)\le\alpha}$ contains no vertical lines and is closed convex. Its level sets  are given by $\lev{\alpha}{f}:=\set{x\in\bE}{f(x)\leq \alpha}$. The Fenchel conjugate of any function $f:\bE\to\rbar$ is $f^*(y) = \sup_{x\in\bE}\{\ip y x - f(x)\}$. The Jacobian of a differentiable map $F:\R^n\to \R^m$ at $x\in \R^n$ is denoted by $F'(x)$.

We denote the Euclidean projection of $\bar x$ onto $C$ by $P_C(\bar x)$. Throughout, fractions such as $(1/(2\lambda))$ are abbreviated as $(1/2\lambda)$.

For a set $C\subset\bE$,  its indicator function is $\delta_C:\bE\to\rbar$ given by $ \delta_C(x):=0$ if $x\in C$ and $\delta_C(x)=+\infty$ otherwise. The subdifferential of $\delta_C$ is the normal cone of $C$, i.e., $N_C(\bar x):=\p \delta_C(\bar x):=\set{v\in\bE}{\ip{v}{x-\bar x}\leq 0\ (x\in C)}$, which is empty if $\bar x\not\in C$. The relative interior of $C$ is the set $\ri C$ <cit.>, and the horizon cone  is $C^\infty:=\set{v\in \bE}{\exists \{\lambda_k\}\downarrow 0,\ \{x_k\in C\}: \lambda_kx_k\to v}$. The horizon function of $f\in \Gamma_0(\bE)$ is the  closed proper convex and positively homogeneous function $f^\infty:\bE\to\rbar$ defined via $\epi f^\infty=(\epi f)^\infty$.

Let  $f_k:\bE\to \rbar$. Then we say that the sequence $\{f_k\}$ epi-converges to a function $f:\bE\to\rbar$ if

\begin{equation*}\label{eq:epi1}
\forall x\in\bE:\,\left\{\begin{array}{ll}  \forall \{x_k\}\to x: &    \liminf_{k\to\infty} f_k(x_k) \geq f(x),\\ \exists \{x_k\}\to x: &   \limsup_{k\to\infty} f_k(x_k)\leq f(x), \end{array}\right.
\end{equation*}

and we write $f_k\eto f$.

The sequence $\{f_k\}$ is said to converge continuously to $f$ if

\[
\lim_{k\to\infty} f_k(x_k)=f(x) \quad
\forall x\in\bE\ \mbox{and}\ \{x_k\}\to x,
\]

and we write $f_k\cto f$.

Furthermore, $\{f_k\}$ is said to converge pointwise to $f$ if

\lim_{k\to\infty} f_k(x)=f(x)\quad\forall x\in\bE,

and we write $f_k\pto f$.

We extend these notions  to families of functions
$\{f_\lambda\}_{\{\lambda\downarrow 0\}}$ via

\[
f_\lambda \overset{\xi}{\to} f\quad  :\Longleftrightarrow \quad\forall\{\lambda_k\}\downarrow 0:\; f_{\lambda_k} \overset{\xi}{\to} f\quad (\xi\in \{p,e,c\}).
\]

§ PROPERTIES OF THE PERSPECTIVE MAP

The perspective map $\omega^\pi$ that appears in the generalized infimal convolution <ref> provides a mechanism for controlling, through the parameter $\lambda$, the degree to which the functions $f$ and $\omega$ are combined. Beck and Teboulle [7] and Burke and Hoheisel [10] promoted this technique for generating smooth approximations to nonsmooth functions.

We work with the following definition of the perspective map of $\omega$, which appears in Rockafellar <cit.>:

\begin{equation}\label{eq:OmegaPersp}
\omega^\pi:(z,\lambda)\in\bE_\omega\times\R\mapsto
\begin{cases}
\lambda \omega\left(z/\lambda\right) & \mbox{if $\lambda >0$,}\\
\omega^\infty(z) & \mbox{if $\lambda=0$,}\\
+\infty & \mbox{if $\lambda<0$.}
\end{cases}
\end{equation}

For positive values of the parameter $\lambda$, the perspective map corresponds to epi-multiplication:

\[
(\lambda \star \omega)(x):=\lambda\omega\left(x/\lambda\right).
\]

The following result confirms the consistency of the perspective map (<ref>) as the parameter $\lambda$ decreases towards zero.

Let $\phi\in \Gamma_0(\bE)$. Then as $\lambda\downarrow0$, $(\lambda\star\phi)(x) \to \phi^\infty(x)$ for all $x\in\dom\phi$, and $\lambda\star\phi \eto \phi^\infty$.

The pointwise convergence of $(\lambda\star\phi)$ over $\dom\phi$ follows from <cit.>. To prove epi-convergence, observe that, for all $\lambda>0$ and $x\in\bE$,
(\lambda\star \phi)(x)=\phi^\pi(x,\lambda).

\[
\liminf_{\overset{x\to \bar x}{\lambda\downarrow 0}}\, (\lambda\star \phi)(x)=\liminf_{\overset{x\to \bar x}{\lambda\downarrow 0}} \phi^\pi(x,\lambda)\geq  \phi^\pi(\bar x,0) =  \phi^\infty(\bar x)
\quad \forall \bar x\in\bE,
\]

where the inequality follows because $\omega^\pi$ is a support function <cit.> and thus closed <cit.>.

Fix any sequence $\{\lambda_k\}\downarrow 0$ and take $\bar x\in \dom \phi$. Then $(\lambda_k\star \phi)(\bar x)\to \phi^\infty(\bar x)$. Hence, in particular, with $x_k:=\bar x\;(k\in \mathbb N)$,

\begin{equation}\label{eq:limsup}
\limsup_{k\to\infty}\, (\lambda_k\star \phi)(x_k)\leq \phi^\infty(\bar x)
\end{equation}
for all $\bar x\in \dom \phi$. Now let $\bar x\notin \dom \phi$,      take $\hat x\in \dom \phi$ and define $x_k:=\lambda_k \hat x+(1-\lambda_k)\bar x\to \bar x$.  Then

\begin{equation*}
\phi^\infty(\bar x)  =  \sup_{t>0} \frac{\phi(\hat x+t\bar x)-\phi(\hat x)}{t}
\geq   \frac{\phi\left(\hat x+\left(\frac{1}{\lambda_k}-1\right)\bar x\right)-\phi(\hat x)}{\frac{1}{\lambda_k}-1}
=  \lambda_k\cdot\frac{\phi\left(\hat x+\left(\frac{1}{\lambda_k}-1\right)\bar x\right)-\phi(\hat x)}{1-\lambda_k}
\end{equation*}

for all $k\in\bN$ sufficiently large. Hence for such $k\in \bN$,

\[
(\lambda_k\star \phi)(x_k)=\lambda_k \phi\left(\frac{\lambda_k \hat x+(1-\lambda_k)\bar x}{\lambda_k}\right)\leq (1-\lambda_k)\phi^\infty(\bar x)+\lambda_k\phi(\hat x).
\]

Take the limit superior to obtain (<ref>) here.

This establishes epi-convergence.
The following result summarizes key properties of the perspective map. It also provides a support-function representation, which means that it can be written as the support function $\sigma_\cD(y)\equiv\delta^*_\cD(y)=\sup_{x\in\cD}\ip{x}{y}$
for some set $\cD$.

For $\omega\in \Gamma_0(\bE_\omega)$, the following hold:

* $\omega^\pi(z,\lambda)=\sig_{\epi \omega^*}(z,-\lambda)$, hence  $\omega^\pi\in \Gamma_0(\bE_\omega\times\R)$ is sublinear with $\dom \omega^\pi=\R_+(\dom \omega\times \{1\})$;

* $(\omega^\pi)^*(y,\beta)=\delta_{\epi\omega^*}(y,-\beta)$;

* for all $(z,\lambda) \in \dom \omega^\pi$,

\begin{equation}\label{eq:subdiff-omega-pi}
\p \omega^\pi(z,\lambda)
\set{(y,-\beta)}{y\in \p\omega(z/\lambda),\ \beta=\omega^*(y)} & \mbox{if $\lambda>0$,}
\\[6pt]
\set{(y,-\beta)}{y\in\p\omega^\infty(z),\ (y,\beta)\in\epi\omega^*} & \mbox{if $\lambda=0$.}
\end{cases}
\end{equation}

Proof.  For Parts (a) and (b) see <cit.>. Part (c) follows from <cit.> or <cit.>.

The expression for the subdifferential <ref>, evaluated at the origin, reduces to $\p\omega^\pi(0,0)=\{(y,-\beta)\in\epi\omega^*\}$, which is just the epigraph of $\omega^*$ under the reflection $(z,\lambda)\mapsto(z,-\lambda)$. This follows because the subdifferential formula $\p\omega^\infty(0)=\p\sigma_{\dom\omega^*}(0)=\dom\omega^*$; cf. <cit.>. Combettes <cit.> provides a simplified characterization of <ref> under the additional assumption that $\omega$ is supercoercive <cit.>.

§ PARTIAL INFIMAL PROJECTION WITH PERSPECTIVE MAPS

Our main objective in this section is to deduce the variational properties of the generalized infimal convolution $\pLwf$ defined by <ref>. Throughout this section, we make the assumptions that $L$ is a linear map from $\bE_f\times\bE_x$ to $\bE_\omega$ for Euclidean spaces $\bE_i$, $i\in\{f,x,\omega\}$, that $f\in\Gamma_0(\bE_f)$ and $\omega\in\Gamma_0(\bE_\omega)$, and that $\range L\subseteq\R_+\dom\omega$. Under these standing assumptions, it follows from <ref>  below that $\pLwf$ is convex.

§.§ Infimal projection
We lead with a general result on infimal projections.

For a function $\psi\in \Gamma_0(\bE_1\times \bE_2)$, the infimal projection

\begin{equation}\label{eq:inf-proj}
p:x\in\bE_1\mapsto\inf_{u}\, \psi(x,u)
\end{equation}

is convex and

* $p^*=\psi^*(\cdot,0)$,  which is  closed and  convex;

* $\p p(x)=\set{v}{(v,0)\in \p \psi(x,\bar u)}$ for all $\bar u\in \argmin \psi(x,\cdot)$;

* $p^*\in \Gamma_0(\bE_1)$ if and only if
$\dom \psi^*(\cdot,0)\neq\emptyset$;

* $p\in \Gamma_0(\bE_1)$ if $\dom \psi^*(\cdot,0)\neq\emptyset$, and hence the infimum in <ref> is attained when finite.

Proof. For convexity of $p$ and Parts (a,b,d,e), see, e.g., <cit.>. Part (c) follows from Part (b) via Rockafellar <cit.>.

§.§ Generalized infimal convolution

The following auxiliary result is used in this section to derive conjugate and a subdifferential formulas for the value function $\pLwf$.

The function

\[
\eta:(u,x,\lambda)\in\bE_f\times\bE_x\times\R\mapsto\omega^\pi(L(u,x),\lambda)
\]

is closed proper convex, i.e., $\eta\in\Gamma_0(\bE_f\times\bE_x\times\R)$. The nonempty domain and its (possibly empty) relative interior are given by

\begin{align*}
\dom\eta\phantom)
&= \set{(u,x,\lambda)}{\lambda \geq 0,\; L(u,x)\in \lambda \cdot \dom \omega},
\\\ri(\dom\eta)
&=\set{(u,x,\lambda)}{\lambda > 0,\; L(u,x)\in \lambda\cdot\ri(\dom\omega)}.
\end{align*}

If $\ri(\dom\eta)$ is nonempty, then $\eta^*$ is the indicator to the set

\begin{equation}\label{eq:conjugate-domain}
C=\set{(w,z,\mu)}{\exists y\mid (y,-\mu)\in\epi\omega^*,\; L^*(y)=(w,z)}.
\end{equation}

<Ref>(a) asserts that $\eta\in\Gamma_0(\bE_f\times\bE_x\times\R)$, and also yields the expression for its domain. Now assume that $\ri(\dom\eta)$ is nonempty, and that there exists an element $(u,x)$ such that $L(u,x)\in\lambda\cdot\ri(\dom\omega)$ for some $\lambda>0$. Define the linear map $\tilde L:(u,x,\lambda)\mapsto (L(u,x), \lambda)$. Then,

\begin{eqnarray*}
\emptyset & \neq  & \set{(u,x,t)}{ t>0, \;L(u,x)\in t\cdot \ri(\dom\omega)}\\
& = &  \set{(u,x,\lambda)}{ \exists t>0: \;L(u,x)\in t\cdot \ri(\dom\omega),\ \lambda=t}\\
& = & \tilde L^{-1}\R_{++}(\dom \omega \times \{1\})\\
& \overset{\rm(i)}= & \tilde L^{-1} \ri(\R_+(\dom \omega \times \{1\}))\\
& \overset{\rm(ii)}= &  \ri(\tilde L^{-1}\R_+(\dom \omega \times \{1\}))\\
& = & \ri (\tilde L^{-1} \dom \omega^\pi)
= \ri(\dom\eta),
\end{eqnarray*}

where (i) uses <cit.> and (ii) uses <cit.> and the fact that $L^{-1}\ri(\R_+(\dom \omega \times \{1\}))\neq \emptyset$.

To derive the formula for $\eta^*$, observe that  by our reasoning above $ \tilde L^{-1}\ri(\dom\omega^\pi)=\ri(\dom\eta)\neq \emptyset$. Hence, by <cit.> and <ref>(b),

\begin{eqnarray*}
\eta^*(w,z,\mu) & = & (\omega^\pi\circ \tilde L)^*(w,z,\mu)\\
%& = & \tilde L^*(\omega^\pi)^*(v,y,\mu) \\
& = & \inf_{(u,\alpha)} \set{(\omega^\pi)^*(u,\alpha)}{\tilde L^*(u,\alpha)=(w,z,\mu)}\\
& = & \inf_u \set{(\omega^\pi)^*(u,\mu)}{ L^*(u)=(w,z)}\\
& = & \inf_u\set{\delta_{\epi\omega^*}(u,-\mu)}{L^*(u)=(w,z)}\\
%&= & \delta_{\set{(w,z,\delta)}{\exists a:\; w^*(a)+\delta\leq 0,\; L^*(a)=(w,z)}}(v,y,\mu)\\
& = & \delta_C(w,z,\mu),
\end{eqnarray*}

which establishes (<ref>)

We can now deduce the subdifferential and conjugate of the generalized convolution (<ref>).

Under the assumptions of <ref>, suppose in addition that

\begin{equation}\label{eq:CQ1}
\exists (u,x)\in \ri(\dom f)\times \bE_x:\; L(u,x)\in \R_{++}\ri(\dom\omega).
\end{equation}

Then the following hold for the convex function $\pLwf$ defined in (<ref>).

* $
\pLwf^*(y,\mu)=\inf_w \set{f^*(w)}{\exists a:(a,-\mu)\in\epi\omega^*,\ L^*(a)=(-w,y)}
and the infimum is attained when finite.

* For all $(x,\lambda)\in \dom \pLwf$ and all  $\bar u\in \argmin_{u\in \bE_f}\{\,f(u)+\omega^\pi(L(u,x),\lambda)\,\}$,

\begin{equation*}
\p \pLwf(x,\lambda)
\begin{cases}
\set{(v,-\omega^*(y))}{ y\in \p \omega\left(L(\bar u,x)/\lambda\right),\ (0,v)\in\cD(\bar u,y) } &\mbox{if $\lambda>0,$}
\\[6pt]
\set{(v,-\beta)}{y\in\p\omega^\infty(L(\bar u,x)),\ (0,v)\in\cD(\bar u,y),\ (y,\beta)\in\epi\omega^*} & \mbox{if $\lambda=0$,}
\end{cases}
\end{equation*}

where $\cD(u,y):=\p f(u)\times\{0\}+L^*(y)$.

* $\pLwf^*\in \Gamma_0(\bE_x\times \R)$ if and only if there exist $w\in \dom f^*, a\in \dom \omega^*, (y,\mu)\in \bE_x\times \R $ such that
$(a,-\mu)\in\epi\omega^*$ and $L^*(a)=(-w,y)$. In this case, $\pLwf\in \Gamma_0(\bE_x\times \R)$ and the infimum is attained when finite.

Proof. Set $p=\pLwf$. Part (a). Observe that $p(x,\lambda)=\inf_u\psi(u,x,\lambda)$ for $\psi=\phi+\eta$ with $\phi(u,x,\lambda)=f(u)$ (and $\eta$ as in <ref>).
We hence compute

\begin{eqnarray*}
p^*(y,\mu) & = & \psi^*(0,y,\mu)\\
& = & (\phi+\eta)^*(0,y,\mu)\\
%&= & (\phi^*\#\eta^*)(0,y,\mu)\\
& = & \inf_{(w,z,\delta)} \phi^*(w,z,\delta)+\eta^*(-w,y-z,\mu-\delta)\\
&= & \inf_{w} f^*(w)+\delta_C(-w,y,\mu)\\
&= & \inf_w \set{f^*(w)}{\exists a:(a,-\mu)\in\epi\omega^*,\ L^*(a)=(-w,y)}.
\end{eqnarray*}

Here the first identity uses <ref>.   The second is clear from our definitions above. The third relies on <cit.> and the fact that assumption (<ref>) is, in view  of <ref>(b) and the fact that $\ri(\dom\phi) = \ri(\dom f)\times\bE_x\times\R$, equivalent to the condition $\ri(\dom\eta)\cap \ri(\dom\phi)\neq \emptyset$.  The fifth uses the
fact that  $\phi^*(v,y,\mu)=f^*(v)+\delta_{\{0\}}(y,\mu)$ and <ref>  b). The last identity is simply the definition of the set $C$ in said proposition.

Part (b).  By (<ref>) we  can apply <cit.>   to find

\begin{align*}
\p \psi(u,x,\lambda)
&= \p f(u)\times \{0\}\times \{0\}+\tilde L^*\p \omega^\pi(\tilde L(u,x,\lambda))
\\&= \p f(u)\times \{0\}\times \{0\}+(L^*\times \id)\p\omega^\pi(L(u,x),\lambda).
\end{align*}

Apply  <ref>(c) and combine with <ref> to obtain the desired result.

Part(c) follows from <ref>(d).

§.§ Infimal convolution

We now consider the value function

\begin{equation}\label{eq:InfConv}
\pwf:(x,\lambda)\in\bE\times\bR\mapsto\inf_{u\in\bE} f(u)+\omega^\pi(x-u,\lambda),
\end{equation}

which corresponds to the standard infimal convolution between $f$ and $\omega^\pi$.
This is a special case of (<ref>) where $L(u,x)= x-u$  and $\bE_i=\bE$ with $i=f,x,w$. The following result specializes <ref>.

For the function $\pwf$ given by (<ref>), assume that $f,\omega\in\Gamma_0(\bE)$ and

\begin{equation}\label{eq:ICCQ}
\exists (u,x)\in \ri(\dom f)\times  \bE: \;x-u\in \R_{++}\ri(\dom\omega).
\end{equation}

Then the following hold.

* $\pwf^*(y,\mu)=f^*(y)+\delta_{\epi \omega^*}(y,-\mu)$.

* For all $(x,\lambda)\in \dom \pwf$ and all $\bar u\in \argmin_{u\in \bE}\left\{ f(u)+\omega^\pi(x-u,\lambda)\right\}$ we have

\begin{equation*}
\p \pwf(x,\lambda)=
\begin{cases}
\set{(y,-\beta)}{y\in \p f(\bar u)\cap \p\omega\left(\frac{x-\bar u}{\lambda}\right),\ \beta=\omega^*(y)} & \mbox{if $\lambda>0$,}\\[6pt]
\set{(y,-\beta)}{y\in \p f(\bar u)\cap \p w^\infty(x-\bar u),\ (y,\beta)\in \epi \omega^*}&\mbox{if $\lambda =0$.}
\end{cases}
\end{equation*}

* $\pwf^*\in \Gamma_0(\bE)$ if and only if $\dom \pwf^*=(\dom f^*\times \bE)\cap \epi \omega^*\neq \emptyset$. In this case, $\pwf\in \Gamma_0(\bE)$ also, and the infimum is attained when finite.

Proof. Use <ref>(a)–(c) and observe that $L^*(a)=(-a,a)$.

§.§.§ Infimal convolution solution map

Thus far, our analysis has focused exclusively on the variational properties of the optimal value function <ref> and its specializations. We now turn our attention to the  optimal solution map

\begin{equation}\label{eq:SolMap}
\Pwf:(x,\lambda)\in\bE_x\times\bR\mapsto\argmin_{u\in\bE_f} f(u)+\omega^\pi(x-u,\lambda)
\end{equation}

for the infimal convolution defined by (<ref>). In this section we describe the variational-analytic properties of the solution map, including (Lipschitz) continuity and (directional) smoothness. To this end, we introduce required technical machinery from variational analysis [47, 42].

Let $S:\bE_1\rightrightarrows\bE_2$ be a set-valued map between spaces $\bE_1$ and $\bE_2$. The domain and graph of $S$, respectively, are the sets $\dom S:=\set{x}{S(x)\neq \emptyset}$ and $\gph S:=\set{(x,u)\in \bE_1\times \bE_2}{u\in S(x)}$. The outer limit of $S$ at $\bar x$  is

\[
\Limsup_{x\to \bar x} S(x):=\set{y\in\bE_x}{\exists \{x_k\}\to \bar x,  \{y_k\in S(x_k)\}\to y}.
\]

Now let $A\subset  \bE$.  The tangent  cone of $A$ at $\bar x\in A$ is
T_A(\bar x):=\Limsup_{t\downarrow 0} (A-\bar x)/t.
The regular normal cone of $A$ at $\bar x\in A$ is the polar of the tangent cone, i.e.,
\hat N_A(\bar x):=\set{v}{\ip{v}{y}\leq 0\;\;\forall y\in T_{A}(\bar x)}.
The limiting normal cone   of $A$ at $\bar x\in A$ is
N_A(\bar x):=\Limsup_{x\to \bar x} \hat N_A(x).
The coderivative of $S$ at $(\bar x,\bar y)\in \gph S$ is the map $D^*S(\bar x\mid\bar y):\bE_2\rightrightarrows\bE_1$ defined via

\[
v\in D^*S(\bar x\mid\bar y)(y) \IFF (v,-y)\in N_{\gph S}(\bar x,\bar y).
\]

The    graphical derivative of $S$ at $(\bar x,\bar y)$ is the map $DS(\bar x\mid\bar y):\bE_f\rightrightarrows \bE_x$ given by

\[
v\in DS(\bar x \mid \bar y)( u) \IFF (u,v) \in T_{\gph S}(\bar x,\bar y),
\]

or, equivalently, $DS(\bar x \mid \bar y)( u)=DS(\bar x | \bar y)( u)=\Limsup_{\overset{t\downarrow 0,}{u'\to u}} \frac{S(\bar x+tu')-\bar y}{t}$ <cit.>.

The strict graphical derivative of $S$ at $(\bar x,\bar y)$ is  $D_*S(\bar x\mid\bar y):\bE_f\rightrightarrows \bE_x$ given by

\begin{eqnarray*}
D_*S(\bar x\mid\bar y)(w)=
\set{z}{\exists \left\{\begin{array}{l}\vspace{0.1cm}\{t_k\}\downarrow 0,\, \{w_k\}\to w,\, \{z_k\}\to z,\\
\{(x_k,y_k)\in\gph S\}\to (\bar x,\bar y) \end{array}\right\}: z_k\in\frac{S(x_k+t_kw_k)-y_k}{t_k}}.
\end{eqnarray*}

We adopt the convention to set $D^*S(\bar x):=D^*S(\bar x\mid\bar u)$ if $S(\bar x)$ is a singleton, and  proceed  analogously for the graphical derivatives.

The above generalized derivatives possess the following definiteness properties when applied to a maximally monotone operator $T:\bE\rightrightarrows\bE$, which (by definition) satisfies the inequality

\[
\ip{v-w}{x-y}\ge0
\quad
\forall (v,w)\in T(x)\times T(y),
\]

and there is no enlargement of $\gph T$ without destroying this inequality.
Our conclusion relies on Minty parameterization.

Let $T:\bE\rightrightarrows\bE$ be maximally monotone and let $(\bar y,\bar u) \in \gph T$. Then the pair $(w,z)\in\bE\times\bE$ satisfies $\ip w z \ge 0$ if one of the following conditions hold:

* $w\in D^*T(\bar y\mid\bar u)(z)$;

* $z\in D_*T(\bar y\mid\bar u)(w)$;

* $z\in DT(\bar y\mid\bar u)(w)$.

Proof. Part (a). See <cit.>.

Part (b). For $z\in D_*T(\bar y\mid\bar u)(w)$ there exist  $\{z_k\}\to z,  \{t_k\downarrow 0\}, \{(y_k,u_k)\in\gph T\}\to (\bar y,\bar u)$, and $\{w_k\}\to w$ such that

\begin{equation}\label{eq:Strict}
t_k z_k\in T(y_k+t_k w_k)-u_k\quad \forall k\in \bN.
\end{equation}

Now let $\lambda>0$ and set $J_{\lambda T}:=(\lambda T+\id)^{-1}$. By Minty parameterization <cit.>, there exists $\{x_k\}$ such that
(y_k,u_k) = \left(J_{\lambda T} (x_k),\ (x_k-J_\lambda (x_k)/\lambda\right)
for all $k\in \bN$.
Combining this with (<ref>) yields $ x_k+t_k(\lambda z_k+w_k)\in (\lambda T+\id)(y_k+t_kw_k)$.

Thus, as $y_k=J_{\lambda T}(x_k)$, we have
t_kw_k=J_{\lambda T}(x_k+t_k(\lambda z_k+w_k)-J_{\lambda T}(x_k)\;(k\in\bN).
Because $J_{\lambda T}$ is firmly nonexpansive <cit.> and hence 1-Lipschitz, it follows that
\|w_k\|\leq \|\lambda z_k+w_k\| \;(k\in\bN)$,  hence
\|w\|\leq \|\lambda z+w\|.
We infer that
-(\lambda/2)\|z\|^2\leq \ip{z}{w}.
Since $\lambda>0$ was arbitrary, letting $\lambda\downarrow 0$ gives the desired inequality.

Part (c). Follows from Part (b)  and the fact that
$DS(\bar x\mid\bar u)(w)\subset D_*S(\bar x\mid\bar u)(w)$
for all $ w\in\bE_f$.

We record another auxiliary result. Here  we call $S:\bE_f\rightrightarrows \bE_x$ proto-differentiable  at $(\bar x,\bar u)\in \gph S$ if for any $\bar z\in DS(\bar x\mid\bar u)(\bar w)$ and any $\{t_k\}\downarrow 0$ there exist $\{w_k\}\to \bar w$ and $\{z_k\}\to\bar z$ such that
z_k\in (S(\bar x+ t_kw_k)-\bar u)/t_k
$ for all $k\in \bN$.

Let $S:\bE_1\rightrightarrows \bE_2$ be given by $S=F+T$, where $F$ is smooth and $T$ is proto-differentiable at $(\bar x,\bar u-F(\bar x))$. Then $S$ is proto-differentiable at $(\bar x,\bar u)$.

Proof. Let $z\in DS(\bar x\mid\bar u)(w)$ and $\{t_k\}\downarrow 0$. Then
z-F'(\bar x)w\in DT(\bar x\mid\bar u-F(\bar x))(w),
cf.   <cit.>.
By assumption on $T$, there exist $\tilde z_k\to z-F'(\bar x)w$ and $w_k\to w$ such that
\tilde z_k\in [T(\bar x+t_kw_k)-(\bar u-F(\bar x))]/t_k,
\tilde z_k+[F(\bar x+t_kw_k)-F(\bar x)]/t_k\in[S(\bar x+t_kw_k)-\bar u]/t_k
for all $k\in\bN$.
z_k:=\tilde z_k+[F(\bar x+t_kw_k)-F(\bar x)]/t_k\to z$ and  $z_k\in[S(\bar x+t_kw_k)-\bar u]/t_k$ for all $k\in \bN$
which  shows the proto-differentiability of $S$ at $(\bar x,\bar u)$.

The next and main result in this subsection is based on  the implicit mapping framework described by Rockafellar and Wets <cit.> together with <ref>.

Let $f\in \Gamma_0(\bE)$ and let $\omega:\bE\to \R$  be strictly convex, level-bounded and  twice continuously differentiable. Let $\bar x\in\bE$ and $\bar \lambda>0$,  set $\bar y:=\Pwf(\bar x,\bar\lambda)$ and  $\bar V:=\nabla^2\omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)$. Then for the solution map
$\Pwf$ from (<ref>) the following hold:

* We have $\dom \Pwf\subset\bE\times \R_{+}$ and  $\Pwf(\cdot,\lambda)$ is   single-valued for all $\lambda>0$.

* If $\bar V$ is positive definite, then $\Pwf$ is locally Lipschitz at $(\bar x,\bar \lambda)$.

* If $\bar V$ is positive definite and
$\p f$ is  proto-differentiable at $\left(\bar y,\nabla \omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)\right)$, then $\Pwf$ is  is directionally differentiable[In fact,  semidifferentiable  at $(\bar x,\bar \lambda)$ in the sense of <cit.>. ] at $(\bar x,\bar \lambda)$. Concretely, for all $(d,\Delta)\in \bE\times \R$, we have

\begin{eqnarray*}
\Pwf'((\bar x,\bar \lambda);(d,\Delta))  =
\left[\bar \lambda D(\p f)\left(\bar y\ \Big\vert\ \nabla \omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)\right)+\bar V\right]^{-1}\hspace{-0.1cm}\left(\bar Vd-\frac{\Delta}{\bar \lambda}\bar V(\bar x-\bar y)\right).
\end{eqnarray*}

Proof. Set $P:=\Pwf$. Part (a). For $\lambda>0$ and $x\in\bE$, the function $u\mapsto f(y)+\omega^\pi(x-y,\lambda)$ is lsc, proper, strictly convex and level-bounded, and therefore attains a unique minimum.

Part (b). Without loss of generality, let $\bE=\R^n$, and  observe that, for $\lambda>0$, we have
P(x,\lambda)=\set{y}{0\in S(x,\lambda,y)},
where  $S(x,\lambda,u):= \p f(y)-\nabla \omega\left(\frac{x-u}{\lambda}\right)\;(\lambda>0)$.   Use <cit.> to deduce

\begin{eqnarray*}
D^*S(\bar x,\bar \lambda,\bar y \mid 0)(y) =
\left[-\frac{1}{\bar \lambda} \bar Vy, \frac{(\bar x-\bar y)^T}{\bar \lambda^2}\bar Vy,\frac{1}{\bar \lambda} \bar Vy\right]+\{0\}\times \{0\}\times D^*(\p f)\left(\bar y\ \Big\vert\ \nabla \omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)\right)(y).
\end{eqnarray*}

Hence, $(r,\gamma,0)\in D^*S(\bar x,\bar \lambda,\bar y\mid 0)(y)$ if and only if

\begin{eqnarray*}
r=-\frac{1}{\bar \lambda}\bar Vy,
\quad \gamma=\frac{(\bar x-\bar y)^T}{\bar \lambda^2}\bar Vy,
\quad -\frac{1}{\bar \lambda}\bar Vy\in D^*(\p f)\left(\bar y\Big\vert\nabla \omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)\right)(y).
\end{eqnarray*}

Invoke <ref>(a) and use $\bar V\succ 0$ to deduce $y=0$, hence $r=0$ and $\gamma=0$.
Therefore, by <cit.>, we see that $P$ has the Aubin property at $(\bar x,\bar \lambda)$ for $\bar y$, and since $P$ is single-valued, it is locally Lipschitz at $(\bar x,\bar \lambda)$.

Part (c).  With the definitions from Part (b), recall that the implication

\[
(r,\gamma,0)\in D^*S(\bar x,\bar \lambda,\bar y \mid 0)(y) \quad \Rightarrow \quad (r,\gamma)=0,\;y=0
\]

was proved.  Now let

\[
0\in D_*S(\bar x,\bar \lambda,\bar y\mid 0)\left(\begin{smallmatrix}0\\0\\w
\end{smallmatrix}\right)=\frac{1}{\bar \lambda}\bar Vw+D_*(\p f)\left(\bar y\mid \nabla \omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)\right)(w),
\]

see <cit.>, i.e.,

\[
-\frac{1}{\bar \lambda}\bar Vw\in  D_*(\p f)\left(\bar y\mid \nabla \omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)\right)(w).
\]

By <ref>(b), we find that $w=0$. Since $\p f$ is assumed to be proto-differentiable  at $\left(\bar y,\nabla \omega\left(\frac{\bar x-\bar y}{\bar \lambda}\right)\right)$,  <ref> yields that $S$ is proto-differentiable at $((\bar x,\bar \lambda,\bar y), 0)$. We can now apply <cit.> to obtain the desired result.

Let  $f\in \Gamma_0(\bE)$ and $\bar x\in \dom f$.  By <cit.>, there exists a neighborhood $V$ of $\bar x$ such that   $\p f$ is proto-differentiable at $x\in V\cap \dom f$ for any $ v\in \p f(x)$
if $f$ is fully amenable  at $\bar x$ in the sense that (on a neighborhood of $\bar x$)  $f=g\circ F$ with $g\in \Gamma_0(\bE_x)$ piecewise linear-quadratic and $F\in C^2(\bE_f,\bE_x)$  such that

\[
\ker F'(\bar x)^*\cap N_{\cl(\dom g)}(F(\bar x))=\{0\}.
\]

This comprises the following special cases:

* $f(x)=\max_{i=1}^m f_i(x)$ with $f_i\in \Gamma_0(\bE)\cap C^2$;

* $f$ is (convex and) piecewise linear quadratic;

* $f$ is (convex and) twice continuously differentiable.

Since  a strongly convex function is both strictly convex and level-bounded (in fact supercoercive) and has positive definite Hessian everywhere, and since we have $D(\p f)=\nabla^2 f$ wherever $f$ is twice continuously differentiable, we immediately obtain the following result  which, of course, can also be derived directly from the implicit function theorem.

Let $(\bar x,\bar \lambda)\in \bE\times \R_{++}$ such that  $f\in\Gamma_0(\bE)$ is  twice continuously differentiable around  $\Pwf(\bar x,\bar \lambda)$, and let $\omega\in\Gamma_0(\bE)$ be strongly convex and twice continuously differentiable. Then  $\Pwf$ from (<ref>) is continuously differentiable around $(\bar x,\bar \lambda)$. Concretely, for   all $(x,\lambda)$ sufficiently close to $(\bar x,\bar \lambda)$  and for all  $(d,\Delta)\in\bE\times \R$,  we have

\begin{eqnarray*}
\Pwf'(x,\lambda)(d,\Delta)=\left(\lambda\nabla^2f(y)+V\right)^{-1}\left[Vd -\Delta\cdot V\left(\frac{x-y}{\lambda}\right)\right],
\end{eqnarray*}

where   $ y:=\Pwf(x,\lambda) $ and $V:=\nabla^2\omega\left(\frac{x-y}{\lambda}\right)$.

§.§.§ Semismoothness*

We now refine our study of smoothness properties of the solution map $\Pwf$. We base our analysis on the notion of semismoothness* recently established by Gfrerer and Outrata [28], which, in turn, relies on the  notion of the directional normal cone   introduced by Ginchev and Mordukohovich [29] and further advanced  by  Gfrerer et al. [26, 27, 8].

For $\bar x\in A\subset \bE$, the directional normal cone in the direction $\bar u\in\bE$ is given by

\[
N(\bar x;\bar u)=\Limsup_{u\to \bar u,\; t\downarrow 0} \hat N_{A}(\bar x+tu).
\]

Note that $N(\bar x;\bar u)=\emptyset$ if $\bar u\notin T_A(\bar x)$ and that $N(\bar x;\bar u)\subset N_A(\bar x)$ for all $u\in \bE$. Given a set-valued map $S:\bE_f\rightrightarrows \bE_x$, based on the directional normal cone, we  define the directional coderivative  [26] $D^*S((\bar x,\bar u); (u,v)):\bE_x\rightrightarrows \bE_f$ of $S$ at $(\bar x,\bar y)\in\gph S$ in the direction $(u,v)$ via

\[
\gph D^*S((\bar x,\bar u); (u,v))(v^*)=\set{u^*\in\bE_f}{(u^*,-v^*)\in N_{\gph S}((\bar x,\bar y); (u,v))}.
\]

As $N(\bar x;\bar u)=\emptyset$ if $\bar u\notin T_A(\bar x)$, we also have

\begin{equation}\label{eq:DirCoD}
\dom D^*S((\bar x,\bar u); (u,v))=\emptyset\quad  \forall (u,v)\notin DS(\bar x\mid\bar u).
\end{equation}

The set $A\subset \bE$ is semismooth* at $\bar x\subset A$ if

\[
\ip{x^*}{u}=0\quad \forall u\in \bE,\;  x^*\in N_A(\bar x;u).
\]

The map $S:\bE_1\rightrightarrows \bE_2$ is semismooth* at $(\bar x,\bar y)\in \gph S$ if $\gph S$ is semismooth* at $(\bar x,\bar y)$, i.e.,

\[
\ip{u}{u^*}=\ip{v}{v^*}\quad \forall (u,v)\in \bE_1\times \bE_2,\; (v^*,u^*)\in\gph D^*S((\bar x,\bar u); (u,v)).
\]

The notion of  metric (sub)regularity is  used only in the next  two results, and hence we refer the reader to the abundant literature  for a definition, e.g., [23].

Let $F:\bE_1\to \bE_2$ be continuously differentiable at $\bar x$,  let $Q\subset \bE_2$ be semismooth*  (as a set) at $F(\bar x)$ and let $S:\bE_1\rightrightarrows \bE_2,\; S(x):=F(x)-Q$ be metrically  subregular at $(\bar x,0)$. Then $ F^{-1}(Q)$ is semismooth* at $\bar x$ (as a set).

Proof. By <cit.>, for any $h\in\bE_1$,

\begin{equation}\label{eq:DirIncl}
N_{F^{-1}(Q)}(\bar x;h)\subset F'(\bar x)^*N_{Q}(F(\bar x);F'(\bar x)h),
\end{equation}

see also <cit.>.  Since $Q$ is semismooth* at $F(\bar x)$,

\[
\ip{v}{z}=0\quad \forall z\in \bE_2,\ v\in N_{Q}(F(\bar x);z).
\]

\[
\ip{v}{F'(\bar x)h}=0\quad \forall h\in\bE_1,\ v\in N_{Q}(F(\bar x);F'(\bar x)h),
\]

and hence

\[
\ip{u}{h}=0\quad \forall  h\in\bE_1,\ u\in F'(\bar x)^* N_{Q}(F(\bar x);F'(\bar x)h).
\]

By (<ref>) this implies that

\[
\ip{u}{h}=0\quad \forall  h\in\bE_1,\ u\in N_{F^{-1}(Q)}(\bar x;h),
\]

i.e., $F^{-1}(Q)$ is semismooth* at $\bar x$.

Let $f\in \Gamma_0(\bE)$, let $(\bar x,\bar \lambda)\in \bE\times \R_{++}$ and let $\omega$ be strongly convex and twice continuously differentiable. Then the map $\Pwf$ from (<ref>) is semismooth* at $((\bar x,\bar \lambda), \Pwf(\bar x,\bar \lambda))$ if $\p f$ is semismooth* at $\left(\Pwf(\bar x,\bar \lambda), \nabla \omega (\frac{1}{\bar\lambda}[\bar x-\Pwf(\bar x,\bar \lambda)])\right)$.

Proof. Without loss of generality, assume $\bE=\R^n$.  Let $F:\R^n\times \R_{++}\times \R^n\to  \R^{2n}$,
F(x,\lambda,z):=(z, \nabla\omega([x-z]/\lambda).
Then for all $x,z\in \R^n$ and $\lambda>0$, setting $V:=\nabla^2\omega([x-z]/\lambda)\succ 0$ we have

\[
F'(x,\lambda,z)=\begin{pmatrix} 0 & 0 & I\\
\frac{1}{\lambda}V & -\frac{1}{\lambda^2}V(x-z) & -\frac{1}{\lambda}V
\end{pmatrix}.
\]

Hence, $\ker F'(x,\lambda,z)^*=\{0\}$ for all $x,z\in \R^n$, $\lambda>0$. Thus, $(x,\lambda,z)\mapsto F(x,\lambda,z)-\gph \p f$ is metrically regular. As $\gph\Pwf=F^{-1}(\gph \p f)$,  if $\p f$ is semismooth* at $\left(\Pwf(\bar x,\bar x), \nabla \omega \left(\frac{\bar x-\Pwf(\bar x,\bar \lambda)}{\bar \lambda}\right)\right)=F(\bar x,\bar \lambda,\Pwf(\bar x,\bar \lambda)) $, by <ref>,  $\Pwf$ is semismooth* at $((\bar x,\bar \lambda), \Pwf(\bar x,\bar \lambda))$.

<Ref> provides a sufficient criterion for  establishing semismoothness* of the solution map $P$ on the interior of its domain. It will be a topic of future research to exploit this on a broad scale, but we can immediately state the following result for  a function $f\in\Gamma_0(\bE)$ which is either twice continuously differentiable or  piecewise linear-quadratic (PLQ) in the sense of Rockafellar and Wets <cit.>.

For $f \in\Gamma_0(\bE)$, the subgradient $\p f$ is semismooth* at $(\bar x,\bar y)\in \gph \p f$ under one of the following conditions:

* $f$ is twice continuously differentiable at $\bar x$;

* $f$ is piecewise linear-quadratic (in which case $\p f$ is semismooth* on $\bE$).

Assume condition (a) holds.  If  $f$ is twice continuously differentiable, then $D(\p f)(\bar x\mid\bar y)=\nabla^2 f(\bar x)=D^*(\p f)(\bar x\mid\bar y)$, see <cit.>. Now  let $(u,v)\in T_{\gph \p f}(\bar x, \bar y)$, i.e., $ v\in D(\p f)(\bar x\mid\bar y)(u) =\{\nabla^2 f(\bar x)u\}$, and  let $(x^*,y^*)\in N_{\gph \p f}((\bar x,\bar y);(u,v))\subset N_{\gph \p f}(\bar x,\bar y)$, hence $ x^*\in D^*(\p f)(\bar x\mid\bar y)(-y^*)=\{-\nabla^2 f(\bar x)y^*\}$. Thus,  we have
\ip{(x^*,y^*)}{(u,v)}=\ip{y^*}{\nabla^2 f(\bar x)u}-\ip{\nabla^2 f(\bar x)y^*}{u}=0.

Now assume condition (b) holds. It follows from <cit.> that $\gph \p f$ is a finite union of polyhedra. Then <cit.> yields that $\gph  \p f$ is semismooth*, which gives the desired statement.

§.§ Constrained optimization

We now consider an application of <ref> to derive the variational properties of the optimal value of the constrained optimization problem

\begin{equation}\label{eq:LevelSetOpt}
v:(x,\lambda)\in\bE_x\times\bR\mapsto\inf_{u\in\bE_f}\set{f(u)}{L(u,x)\in \lambda S},
\end{equation}

where $S\subset\bE_\omega$ is a closed convex set. This function can be viewed as a special case of (<ref>), where $\omega=\delta_S$ for some closed convex set $S\subset \bE_{\omega}$. To see this, it is sufficient to note that

\[
\delta^\pi_S(z,t)=\begin{cases}
\delta_{\lambda S}(z) & \mbox{if $\lambda>0$,}\\
\delta_{S^\infty}(z) & \mbox{if $\lambda=0$,}\\
+\infty & \mbox{otherwise,}
\end{cases}
\]

and thus $L(u,x)\in\lambda S$ if and only if $\delta_S^\pi(L(u,x),\lambda)$ vanishes.
Let $S^\circ:=\set{v}{\ip{v}{s}\leq 1\;\forall x\in S}$ be the polar to the set $S$.

The following result is an immediate consequence of the general study in <ref>.

Let $v$ be given by (<ref>) with $S\subset \bE_{\omega}$  closed and convex,  and    assume that

\begin{equation*}
\exists u\in \ri\dom f,\ x\in \bE_x\; : \; L(u,x)\in \bR_{++}(\ri S).
\end{equation*}

Then the following hold.

* We have

\[
v^*(y,\mu)=\inf_{w}\set{f^*(w)}{\exists a\in-\mu S^\circ\;:\; L^*(a)=(-w,y)}.
\]

If $S$ is a cone then
v^*(y,\mu)=\inf_w\set{f^*(w)+\delta_{\R_-}(\mu)}{(-w,y)\in L^*(S^\circ)}.

* For any $(x,\lambda)\in \dom v$ and  $\bar u\in \argmin_{u}\set{f(u)}{L(u,x)\in\lambda S} $,

\begin{eqnarray*}
\p  v(x,\lambda)& = &
\begin{cases}
\set{(v,-\sigma_S(y))}{y\in N_S(L(\bar u,x)/\lambda),\; (0,v)\in\cD(\bar u, y)}
& \mbox{if $\lambda>0$,}\\
\set{(v,-\beta)}{\exists y\in N_{S^\infty}(L(\bar u,y))\cap (\beta S^\circ)\;: \;(0,v)\in\cD(\bar u, y) } & \mbox{if $\lambda=0$,}
\end{cases}
\end{eqnarray*}

where $\cD(u,y) := \p f(u)\times\{0\}+L^*(y)$.
If $S$ is bounded (hence compact), then

\begin{eqnarray*}
\p  v(x,\lambda)& = & \begin{cases}
\set{(v,-\sigma_S(y))}{y\in N_S\left(L(\bar u,x)/\lambda\right),\; (0,v)\in\cD(\bar u,y)}&\mbox{if $\lambda>0$,}\\
\set{(v,-\beta)}{\exists y\in\beta S^\circ\;: \;(0,v)\in\cD(\bar u,y)}&\mbox{if $\lambda=0$.}
\end{cases}
\end{eqnarray*}

* We have  $v^*\in\Gamma_0(\bE_x\times \R)$ if and only if  there exist $y\in \bE_x$, $w\in\dom f^*$, $\beta\in\R$ such that $(-w,y)\in -\beta L^*(S^\circ)$. In this case, also $v\in\Gamma_0(\bE_x\times \R)$ and the infimum is attained when finite.

Part (a) follows from <ref>(a) with $w^*=\sigma_S$. If $S$ is a cone then $w^*=\delta_{S^\circ}$.
Part (b) follows from <ref>(b), observing that $\omega^\infty=\delta_{S^\infty}$ and that $S^\infty=\{0\}$ if $S$ is bounded, in which case $N_{S^\infty}=\bE_\omega$.
Part (c) follows from (a) and <ref>(c).

§.§.§ Relaxed linear constraints

As an immediate specialization of <ref> we obtain a result on the value function

\begin{equation}\label{eq-value-fn-linear-constraints}
v:(b,\lambda)\in\R^m\times\R\mapsto\inf_{x\in \R^n}\set{f(x)}{\|Ax-b\| \le \lambda},
\end{equation}

where $f\in\Gamma_0(\R^n)$, $A\in\R^{m\times n}$ is a matrix, and $\|\cdot\|$ is any norm in $\R^n$. Denote the associated dual norm by $\|\cdot\|^\circ$, and the corresponding unit-norm ball by $\bB$.

If there exists a pair $(x,\lam)\in \dom f\times\R_{++}$ such that $\|Ax-b\|<\lam$, then the following hold.

* (conjugate) $v^*(y,\mu)=f^*(A^Ty)+\delta_{\mu\bB^\circ}(y)$, which is closed proper convex if and only if there exists $\beta$ and $\|y\|^\circ\le \beta$ such that $A^Ty\in \dom f^*$. In this case, $v$ is closed proper convex and the infimum is attained when finite.

* (subdifferential) For any $(b,\lambda)\in \dom v$ and $\bar x$ that achieves the infimum in <ref> (and hence $\|A\bar x-b\|\le\lambda$),

\begin{eqnarray*}  \p  v(b,\lambda)& = & \begin{cases}
\set{(y,-\|y\|^\circ)}{y\in N_\bB\left([A\bar x-b]/\lambda\right),\; -A^Ty\in \p f(\bar x)}&\mbox{if $\lambda>0$,}\\
\set{(y,-\beta)}{\|y\|^\circ\leq\beta, \;-A^Ty\in \p f(\bar x)} & \mbox{if $\lambda=0$.}
\end{cases}
\end{eqnarray*}

* (primal existence) For $\lambda>0$ and any $b\in \R^m$, if

\begin{equation}\label{eq:Primal}
f^\infty(y)>0 \quad\forall y\in \ker A\setminus\{0\},
\end{equation}

$ \argmin_{x}\left\{f(x)+\delta^\pi_\bB(Ax-b,\lambda)\right\} \neq \emptyset$. This holds, e.g., when $f$ is level-bounded or $\rank A=n$.

Proof. Part (a). The expression for the conjugate $v^*$ follows from <ref>(a) by observing that $L:(x,b)\mapsto Ax-b$ has adjoint $L^*:z\mapsto (A^Tz,-z)$ and that $\sigma_\bB=\|\cdot\|^\circ$. The remaining claims for Part (a) follow from <ref>.

Part (b) follows from <ref>(b) with the foregoing observations.
d) For $\lambda>0$ and $b\in \R^m$, the effective objective function in <ref> is $\phi(x):=f(x)+\delta_{\lambda\bB}(Ax-b)$. With $\hat x$ such that $\|A\hat x-b\|\leq\lambda$, which exists by the hypothesis of the theorem, we have

\[
(\delta_{\lambda\bB}\circ(A(\cdot)-b))^\infty(x) =\sup_{\tau>0}\delta_{\lambda\bB}(A\hat x-b+\tau Ax)=\delta_{\ker A}(x),
%(\delta_{t\bB}\circ A)^\infty(u)=\lim_{\lambda\downarrow 0}\delta_{t\bB}(Au/\lambda)= \delta_{\ker A}(u).
\]

where  the second identity  uses the property that $\lambda\bB$ is bounded. With <cit.> we hence find that $\phi^\infty=f^\infty+\delta_{\ker A}$, which shows, using <cit.>, that $\phi$ is level-bounded if (<ref>)  holds.

§ MOREAU ENVELOPE AND PROXIMAL MAP

In this section we outline existing and new results regarding the variational properties of the Moreau envelope and the proximal map of a closed proper convex function.

§.§ The Moreau envelope

The Moreau envelope of $f\in \Gamma_0(\bE)$ is defined by

\[
e_\lambda f(x):=\min_{u\in \bE}
\left\{ f(u)+(1/2\lambda)\|x-u\|^2\right\} \quad \forall x\in \bE,\ \lambda>0,
\]

which has a Lipschitz gradient given by $\nabla e_\lambda f(x)=\frac1\lambda(x-P_\lambda f(x))$.

The following result summarizes limiting properties of the Moreau envelope as $\lambda\downarrow 0$.

For $f\in \Gamma_0(\bE)$, the following hold as $\lambda \downarrow 0$:

* $e_\lambda f\eto f$ and $e_\lambda f\pto f$ (in fact $e_\lambda f(x)\uparrow f(x)$ for all $x\in \bE$);

* $\lambda f\eto \delta_{\cl(\dom f)}$;

* $\lambda e_\lambda f(x)\to \frac{1}{2}d^2_{\cl(\dom f)}(\bar x)$ as $x\to \bar x$;

* $\lambda \p f$  converges to $N_{\cl(\dom f)}$ graphically in the sense of <cit.>;

* for $x\in\dom \p f$ we have  $\nabla e_\lambda f(x)\to \argmin_{g\in\p f(x)} \|g\|$.

Proof. Part (a). See, e.g., <cit.>.

Part (b).  By <ref>(b) and <cit.>,
\lambda\star f^* \eto (f^*)^\infty=\sigma_{\dom f}.
Wijsman's theorem <cit.> then yields
\lambda f=(\lambda\star f^*)^*\eto
% \sigma^*_{\dom f}=
\delta_{\cl(\dom f)}.

Part (c). By Part (b),  $\lambda f\eto \delta_{\cl (\dom f)}$. Hence, by <cit.>,

\[
\lambda e_\lambda f=e_1(\lambda f)\cto e_1\delta_{\cl(\dom f)}=\tfrac{1}{2}d^2_{\cl(\dom f)}.
\]

Part (d).  Follows from Part (b) and Attouch <cit.>.

Part (e). See <cit.>.

Note that <ref>(e)  implies that there exists $K>0$ such that

\begin{equation}\label{eq:PFrac}
\forall \bar x\in \dom \p f\; \exists K>0\;\forall \lambda>0: \; \|P_\lambda f(\bar x)-\bar x\|\leq K \lambda.
\end{equation}

<Ref>(a) suggests the following extension of the Moreau envelope at $\lambda=0$:

\begin{equation*}
\begin{cases}
e_\lambda f(x) & \mbox{if $\lambda>0$,}\\
f(x)           & \mbox{if $\lambda=0$,}\\
+\infty        & \mbox{if $\lambda<0$.}
\end{cases}
\end{equation*}

This is exactly the value function $\pwf$ from (<ref>) with $\omega=\frac{1}{2}\|\cdot\|^2$. Hence, we may rely on our general study on infimal convolution from <ref> to understand the properties of this extension of the Moreau envelope.

Let $f\in \Gamma_0(\bE)$. Then $p_f\in\Gamma_0(\bE\times\R)$  and

* $p_f^*(y,\mu)=f^*(y)+\delta_{\epi \frac{1}{2}\|\cdot\|^2}(y,-\mu)$ and $p_f^*\in \Gamma_0(\bE\times\R)$;

* for all  $(x,\lambda)\in\dom p_f$,

\[
\p p_f(x,\lambda)=\begin{cases}
\vspace{0.1cm}
\left(\frac{1}{\lambda}[x-P_\lambda f(x)],\ -\frac{1}{2}\|\frac1\lambda[x-P_\lambda f(x)]\|^2\right) & \mbox{if $\lambda>0$},\\
\set{(v,\beta)}{-v\in \p f(x),\ \frac{1}{2}\|v\|^2\leq \beta} & \mbox{if $\lambda=0$}.
\end{cases}
\]

Proof. We are in the situation of <ref> with $\omega=\frac{1}{2}\|\cdot\|^2$. In particular,  the qualification condition (<ref>) is trivially satisfied.

§.§ Properties of the proximal map

We now turn our attention to the proximal map. It is straightforward to show $P_\lambda f( x)\to x$ as $\lambda\downarrow 0$ for any $x\in \dom f$. The following proposition, which generalizes this statement, can be derived from monotone operator theory <cit.>. The proof that we provide here instead relies on epigraphical convergence.

Let $f\in \Gamma_0(\bE)$ and $\bar x\in \bE$. Then
\lim_{\overset{\lambda \downarrow 0,}{x\to \bar x}} P_\lambda f(x)=P_{\cl (\dom f)}(\bar x).

Let $\{\lambda_k\}\downarrow 0$,  $\{x_k\}\to \bar x$, and $\phi_k(u):=\lambda_k f(u)+\half \|u-x_k\|^2$. Use <ref>(b) to deduce $\lambda_k f\eto \delta_{\cl(\dom f)}$. Then because $\half \|(\cdot)-x_k\|^2\cto \half \|(\cdot)-\bar x\|^2$, we obtain
\phi_k\eto \phi:=\delta_{\cl(\dom f)}+\half \|(\cdot)-\bar x\|^2;
see <cit.>.  Now observe that
$P_{\lambda_k} f(x_k)=\argmin \phi_k$ and $P_{\cl(\dom f)}(\bar x)=\argmin \phi$. Since all functions $\phi_k$  are convex and $\phi$ is level-bounded (in fact, strongly convex), the sequence $\{\phi_k\}$ is, by <cit.>, eventually level-bounded (in the sense of <cit.>). Therefore,   we can apply <cit.>, with $\varepsilon_k=0\;(k\in \bN)$, to deduce
P_{\lambda_k}f(x_k)\to P_{\cl(\dom f)}(\bar x).

We record  the following auxiliary result.

Let $f\in\Gamma_0(\bE)$ and fix positive scalars $\lambda$ and $\mu$. Then for all $x\in\bE$,

\begin{equation}\label{eq:p-bound1}
\begin{aligned}
\frac{1}{2\mu}\big(\|P_\mu f(x)&-x\|^2-\|P_\lambda f(x)-x\|^2+\|P_\mu f(x)-P_\lambda f(x)\|^2\big)\\
&\leq  f(P_{\lambda}f(x))-f(P_\mu f(x))\\
&\leq  \frac{1}{2\lambda}\left(\|P_\mu f( x)- x\|^2-\|P_\lambda f( x)- x\|^2-\|P_\mu f( x)-P_\lambda f( x)\|^2\right),
\end{aligned}
\end{equation}

\begin{equation}\label{eq:p-bound2}
\|P_{\lambda}f( x)-P_\mu f( x)\|^2\leq \frac{\mu-\lambda}{\lambda+\mu}\left(\|P_\mu f( x)- x\|^2-\|P_{\lambda}f( x)- x\|^2\right).
\end{equation}

Proof.  Set $P(\tau):=P_\tau f(\bar x)$ for all $\tau>0$.  To obtain the bounds in (<ref>), use <cit.> to infer

\[
f(x)+\frac{1}{2\tau}\|x-\bar x\|^2-f(P(\tau))-\frac{1}{2\tau}\|P(\tau)-\bar x\|^2\geq \frac{1}{2\tau}\|x-P(\tau)\|^2\quad\forall \tau>0,\ \forall x\in \bE.
\]

For $\tau=\lambda$ and $x=P(\mu)$, we hence obtain

\[
f(P(\mu))+\frac{1}{2\lambda}\|P(\mu)-\bar x\|^2-f(P(\lambda))-\frac{1}{2\lambda}\|P(\lambda)-\bar x\|^2\geq \frac{1}{2\lambda}\|P(\mu)-P(\lambda)\|^2.
\]

Analogously, for $\tau=\mu$ and $x=P(\lambda)$, we find that

\[
f(P(\lambda))+\frac{1}{2\mu}\|P(\lambda)-\bar x\|^2-f(P(\mu))-\frac{1}{2\mu}\|P(\mu)-\bar x\|^2\geq \frac{1}{2\mu}\|P(\lambda)-P(\mu)\|^2.
\]

Combining the last two inequalities now yields (<ref>).

Next, use (<ref>) to obtain

\begin{align*}
\frac{1}{\mu}\big(\|P(\mu)-x\|^2-\|P(\lambda)&-x\|^2+\|P(\lambda)-P(\mu)\|^2 \big)
\\&\leq  \frac{1}{\lambda} \left(\|P(\mu)-x\|^2-\|P(\lambda)-x\|^2-\|P(\lambda)-P(\mu)\|^2 \right),
\end{align*}

or, equivalently

\[
\left(\frac{1}{\lambda}+\frac{1}{\mu}\right)\|P(\lambda)-P(\mu)\|^2\leq \left(\frac{1}{\lambda}-\frac{1}{\mu}\right)\left(\|P(\mu)-x\|^2-\|P(\lambda)-x\|^2\right),
\]

which  is equivalent to the desired inequality (<ref>)

§.§ Proximal map extension

<Ref> suggests the following extension of the proximal map of $f\in\Gamma_0(\bE)$:

\begin{equation*}
P_f:\bE\times \R\rightrightarrows \bE,\quad
\begin{cases}
P_\lambda f(x) & \mbox{if $\lambda>0$,}\\
P_{\cl(\dom f)}(x) & \mbox{if $\lambda=0$,}\\
\emptyset & \mbox{if $\lambda<0$.}
\end{cases}
\end{equation*}

The next result clarifies continuity properties of the proximal map extension $P_f$.

Let $f\in \Gamma_0(\bE)$. Then $P_f$ is continuous on $\dom P_f=\bE\times \R_+$ and is locally Lipschitz on $\inter(\dom P_f)$. If $\bar x\in \dom \p f$, then $P_f$ is upper Lipschitz (or calm) at $(\bar x,0)$, and the map $\R_+\ni\mu\mapsto P_f(\bar x,\mu)$ is locally Lipschitz at $0$, i.e., there exist positive scalars $\kappa$ and $\varepsilon$  such that

P_f(x̅,0)-P_f(x,λ)   ≤κ(x̅-x,λ)      ∀(x,λ)   ∈B_ε(x̅,0)∩P_f,

P_f(x̅,λ)-P_f(x̅,μ)   ≤κ|μ-λ|    ∀λ,μ   ∈[0,ε].

Proof. The continuity to the boundary of the domain follows from <ref>.  The local Lipschitz continuity on $\inter (\dom P_f)$ follows from
<ref> with $\omega=\frac{1}{2}\|\cdot\|^2$.

Now assume that $\bar x\in\dom\p f$, which implies $P_f(\bar x,0)=\bar x\in \dom f$. Then for all $\lambda>0$,

\[
\|P_f(x,\lambda)-P_f(\bar x,0)\|\leq \|P_\lambda f(x)-P_\lambda f(\bar x)\|+\|\bar x-P_\lambda f(\bar x)\|\leq \|x-\bar x\|+K\lambda,
\]

where $K>0$ is given via (<ref>) and we use the property that $P_\lambda f$ is  1-Lipschitz [4].  Set $\kappa:=\max\{1,K\}$ to obtain (<ref>).

Let $P:=P_f(\bar x, \cdot)$.  By (<ref>), there exist positive scalars $\kappa$ and $\varepsilon$ such that $\|P(\tau)-\bar x\|\leq \kappa\tau$ for all $\tau\in(0, \varepsilon]$. Hence for $\mu$ and $\lambda$ in $(0,\varepsilon]$,

\begin{equation*}
\begin{array}{rcl}
\|P(\mu)-P(\lambda)\|^2
& \leq & \frac{\mu-\lambda}{\mu+\lambda}\left(\|P(\mu)-\bar x\|^2-\|P(\lambda)-\bar x\|^2\right)\\[6pt]
& = &  \frac{\mu-\lambda}{\mu+\lambda}\left(\|P(\mu)-\bar x\|-\|P(\lambda)-\bar x\|\right)\cdot\left(\|P(\mu)-\bar x\|+\|P(\lambda)-\bar x\|\right)
\\[6pt]
& \leq  &  \frac{\mu-\lambda}{\mu+\lambda}\kappa (\mu+\lambda)\left(\|P(\mu)-\bar x\|-\|P(\lambda)-\bar x\|\right)
\\[6pt]
& \leq & \kappa |\mu-\lambda |\cdot \|P(\mu)-P(\lambda)\|,
\end{array}
\end{equation*}

where the first inequality follows from (<ref>) of <ref>, and the last inequality uses the reverse triangle inequality. Use (<ref>) to obtain (<ref>).

The following example shows that the assumption $\bar x\in\dom\p f$ required for <ref> is not redundant.

[Upper Lipschitz continuity of proximal map]
Consider the following two functions, both contained in $\Gamma_0(\R)$:

\begin{align*}
f(x) &=\begin{cases} -\log {x} & \mbox{if $x>0$,}\\
+\infty   & \mbox{otherwise},
\end{cases}
&   g(x) &=\begin{cases} -\sqrt{x} & \mbox{if $x\geq 0$,}\\
+\infty   & \mbox{otherwise}.
\end{cases}
\\\intertext{The corresponding extended proximal maps are}
&= \begin{cases}
\half(x+\sqrt{x^2+4\lambda}) & \mbox{if $\lambda>0$,} \\
\max\{x,0\}                       & \mbox{if $\lambda=0$,}
\end{cases}
P_g(0,\lambda)&=\left(\frac{\lambda}{2}\right)^{2/3} \quad\forall \lambda\ge0;
\end{align*}

cf. Beck <cit.> for the expression for $P_f$. Observe that $\dom f$ does not include the origin, and $|P_f(0,0)-P_f(0,\lambda)|=\sqrt{\lambda}$ for all $\lambda>0$, which is not upper Lipschitz at $(0,0)$. Next, observe that $\dom \p g$ does not include the origin, and $P_g$ is not upper Lipschitz at $(0,0)$.

The next result  on directional differentiability of $P_f$ follows from <ref>(c) with $\omega=\frac{1}{2}\|\cdot\|^2$.

Let $f\in \Gamma_0(\bE)$ and fix $(x,\lambda)\in\bE\times \R_{++}$. If $\p f$ is proto-differentiable at $\left(P_f(x,\lambda),\, \frac1\lambda[x-P_f(x, \lambda)]\right)$, then $P_f$ is directionally differentiable at $(x,\lambda)$ with

\begin{eqnarray*}
= \left[ \lambda D(\p f)\left(P_f(x,\lambda)\ \big\vert\  \tfrac1\lambda[x-P_f(x,\lambda)]\right)+I\right]^{-1}
\left(d-\Delta\tfrac1\lambda[x-P_f(x,\lambda)]\right)
\end{eqnarray*}

for all $(d,\Delta)\in\bE\times \R$. In particular, for any $\lambda>0$,

\[
(P_{\lambda} f)'(x;\cdot)=\left[\lambda D(\p f)
\left(P_f(x,\lambda)\,\big\vert\,\tfrac1\lambda[x-P_f(x,\lambda)]\right)+I\right]^{-1}(\cdot)
\]

§.§.§ Semismoothness* of $P_f$

We now  establish semismoothness* of the extended proximal map $P_f$ on $\bE\times \R_{++}$. We lead with an auxiliary

The map $S:\bE_1\rightrightarrows \bE_2$ is semismooth* at $(y, z- y)$ if and only is $S+\id$ is semismooth* at $(y,z)$.

Proof. The map $S$ is semismooth* at $(y,z-y)$ if and only if

\[
\begin{array}{rcl}
& & v\in DS(y\mid z-y)(u), \; u^*\in D^*S((y,z-y);(u,v))(v^*)\Rightarrow \ip{u}{u^*}=\ip{v}{v^*}
\\\\
& \Longleftrightarrow &\left\{\begin{array}{l}v+u\in D(S+\id)(y|z)(u),
\\[3pt]
u^*+v^*\in D^*(S+\id)((y,z);(u,u+v))(v^*)\end{array}\right\}\Rightarrow \ip{u}{u^*+v^*}=\ip{u+v}{v^*}
\\\\
& \Longleftrightarrow & S+\id\;\text{semismooth* at}\;(y,z).
\end{array}
\]

Here the first equivalence is  the definition of semismoothness* and (<ref>). The second  uses the sum rule for the
graphical derivative <cit.> and the directional coderivative <cit.>, respectively,  when one summand is smooth (here the identity map). The last equivalence is
a variable change and the definition of semismoothness*  and (<ref>) again.

For $f\in \Gamma_0(\bE)$,

* $P_f$ is semismooth* at $(x,\lambda)$ if $\p f$ semismooth* at $\left(P_f(x,\lambda),\, \frac1\lambda[x-P_f(x,\lambda)]\right)$;

* $P_{\lambda} f$ is semismooth*  at $x$ if and only if $\p f$ is semismooth* at $\left(P_{\lambda} f(x),\frac1\lambda[x-P_{\lambda} f(x)]\right)$.

Part (a) follows from <Ref> with $\omega=\frac{1}{2}\|\cdot\|^2$. For Part (b), observe that $P_{\lambda} f=(\lambda \p f+\id)^{-1}$ is semismooth* at $x$ if and only if $\lambda \p f+\id$ is semismooth* at $(P_{\lambda} f(x),\,x)$ <cit.>. By <ref>, this is the case if and only if $\lambda \p f$ is semismooth* at $(P_{\lambda} f(x),\,x-P_{\lambda} f(x))$ which, in turn,  holds if and only if $\p f$ is semismooth* at $\left(P_{\lambda} f(x),\,\tfrac1\lambda[x-P_{\lambda} f(x)]\right)$.

Various papers study the semismoothness à la Qi and Sun  [45]  of $P_f$ on $\bE\times \R_{++}$.  Most of these results, trace the semismoothness of the latter back to the semismoothness
of the Euclidean projection onto $\epi f$. The work by Meng et al.  [39, 40] deserves explicit mention, and a good discussion of these results can be found in Milzarek's thesis [41]. Bearing our applications in <ref>  in mind, this is somewhat of a circular strategy, and hence
we opened up a different path  via our study in <ref> on semismooth* properties of solution maps.  For a map that is locally Lipschitz at a point, semismoothness* differs from traditional semismoothness only in directional differentiability as the following result by Gfrerer and Outrata <cit.> shows.

Let $F:D\subset \bE_1\to\bE_2$ be locally Lipschitz at $x\in\inter D$.  Then the following are equivalent:

* $F$ is semismooth at $x$;

* $F$ is semismooth* and directionally differentiable at $x$.

This lemma gives the following immediate consequence about semismoothness of $P_f$.

Let $f\in \Gamma_0(\bE)$ and fix $(x,\lambda)\in \bE\times \R_{++}$. If $\p f$ is proto-differentiable and semismooth* at
$\left(P_f(x,\lambda),\,\tfrac1\lambda[x-P_f(x, \lambda)]\right)$, then $P_f$ is semismooth at $( x,\lambda)$. This holds, in particular, if $f$ is PLQ or  twice continuously differentiable at $P_f( x, \lambda)$, in which case $P_f$ is continuously differentiable at $( x, \lambda)$.

Proof. For the first statement combine <ref>, <ref>, and <ref>. For the second, invoke <ref> and <ref>.

Note that semismoothness* does not require directional differentiability of the function in question. However, semismoothness* is still sufficient to yield convergence of  Newton-type methods under suitable regularity conditions [28, 32].  In view of the above discussion, this is  important because  the Euclidean projector onto a closed convex set may not be directionally differentiable [48], in which case the arguments and methods  based on (standard)  semismoothness  are invalidated.

§ THE PROXIMAL VALUE

The projection onto the epigraph of a function $f\in\Gamma_0(\bE)$ requires a particular value of $\lambda$ so that the equation (<ref>) holds. In this section we examine the variational properties of the value of the proximal map as a function of $\lambda$, i.e., the function

\begin{equation}\label{eq:prox-value-lambda}
0<\lambda\mapsto f(P_\lambda{f}(\bar x)),
\end{equation}

where $\bar x\in\bE$ is fixed. Note that this map is not generally convex, as illustrated by the following counterexample.

[Nonconvexity of the proximal value] Define $f=|\cdot|+\delta_{[-1,1]}\in \Gamma_0(\R)$. By Beck <cit.>,

\[
P_{\lambda} f(x)=\min\{\max\{|x|-\lambda,0\},\,1\}\cdot\sgn(x)
\quad \forall x\in \R,\ \lambda>0.
\]

Hence, for $\bar x=2$, we obtain the nonconvex function

\[
f(P_{\lambda}f(\bar x)) =
\begin{cases}
1         & \mbox{if $\lambda \in (0,1]$,}\\
2-\lambda & \mbox{if $\lambda\in (1,2]$,}\\
0         & \mbox{if $\lambda>2$.}
\end{cases}
\]

The next result describes the monotonicity and continuity of the map (<ref>).

Let $f\in \Gamma_0(\bE)$ and fix $\bar x\in \bE$. Then

* $
0<\lambda\mapsto f(P_\lambda{f}(\bar x))
is  decreasing (i.e., increasing as $\lambda\downarrow 0$);

* $
0<\lambda \mapsto \|\bar x-P_{\lambda}f(\bar x)\|
is increasing;

* $\lim_{\lambda\to 0} f(P_\lambda{f}(\bar x))=f(P_{\cl(\dom f)}(\bar x))$.

Proof. Parts (a) and (b).  Let $0<\lambda<\mu$ and set $P(\lambda):=P_\lambda{f}(\bar x)$, $P(\mu):=P_\mu{f}(\bar x)$, and

$\delta:=\frac{1}{2}(\|P(\mu)-x\|^2-\|P(\lambda)-x\|^2)$. Then from (<ref>) of <ref>, we obtain

\[
\frac{1}{\mu}\delta\leq f(P(\lambda))-f(P(\mu))\leq \frac{1}{\lambda} \delta.
\]

As  $\lambda<\mu$, this implies that $\delta \geq 0$, i.e.,  $\|P(\mu)-x\|^2\geq  \|P(\lambda)-x\|^2$, and hence
f(P(\mu))\leq f(P(\lambda))$.

Part (c).  Let $\{\lambda_k\} \downarrow 0$.  Then $p_k:=P_{\lambda_k}f(\bar x)\to p:=P_{\cl(\dom f)}(\bar x)$; see  <ref>. It follows that

\begin{eqnarray*}
f(p)& \geq &  \limsup_{k\to\infty} \big[  f(p_k)+\tfrac{1}{2\lambda_k}\left(\|\bar x-p_k\|^2-\|\bar x-p\|^2\right)\big]\\
& \geq &\limsup_{k\to\infty} f(p_k)\\
& \geq &\liminf_{k\to\infty} f(p_k)\\
& \geq & f(p).
\end{eqnarray*}

Here the first inequality uses that $f(p)+\frac{1}{2\lambda_k}\|\bar x-p\|^2\geq  f(p_k)+\frac{1}{2\lambda_k}\|\bar x-p_k\|^2$ for all $k\in \bN$, by definition of $p_k$.  The second is due to  $\|\bar x-p_k\|\geq \|\bar x-p\|$, by the definition of $p$ and since  $p_k\in \dom f$.  The last one is just lower semicontinuity of $f$.

As we did with the Moreau envelope and proximal map, we define the extension of the map (<ref>) to include negative values of $\lambda$:

\begin{equation*}
\eta^f_{\bar x}:\lambda\in\R \mapsto
\begin{cases}
f(P_{\lambda}f(\bar x)) & \mbox{if $\lambda>0$,}\\
f(P_{\cl(\dom f)}(\bar x)) & \mbox{if $\lambda\leq 0$.}
\end{cases}
\end{equation*}

We call this the proximal value function. Observe that

\begin{equation}\label{eq:eta-as-remainder}
\eta^f_{\bar x}(\lambda)
e_\lambda f(\bar x) - (1/2\lambda)\|\bar x-P_\lambda f(\bar x)\|^2
\quad (\lambda>0).
\end{equation}

We use <ref> to derive the following result.

Let $f\in \Gamma_0(\bE)$ and fix $\bar x\in \bE$. Then the following hold:

* $\eta^f_{\bar x}$ is   decreasing,  continuous (possibly in an extended real-valued sense), and finite-valued if (and only if)  $ P_{\cl(\dom f)}(\bar x)=\bar x\in \dom f$.

* $\eta^f_{\bar x}$  is  locally Lipschitz on  $\R_{++}$.

* If $\bar x\in \dom \p f$, then the assertion in (b) holds on $\R$.

Proof. Set $\eta:=\eta^f_{\bar x}$. Parts (a) and (b). The fact that $\eta$ is decreasing follows from <ref>(a). Now consider (<ref>).
By Corollary <ref>, the map $0<\lambda\mapsto e_\lambda f(\bar x)$ is convex and finite-valued, hence locally Lipschitz. By <ref>(a), this conclusion also holds for $0<\lambda\mapsto \frac{1}{2\lambda}\|x-P_\lambda f(\bar x)\|^2$. This gives the local Lipschitz continuity of $\eta$ on $\R_{++}$. The continuity at 0 is due to <ref>(c).

Part (c).   By Parts (a) and (b), and because $\eta$ is constant (and finite by assumption) on $\R_-$, we only need to be concerned about
the desired properties at $0$. To this end, let $\mu>\lambda$. If $\lambda<0$, then

\[
\left| \frac{\eta(\mu)-\eta(\lambda)}{\mu-\lambda}\right|\leq \left|\frac{\eta(\mu)-\eta(0)}{\mu-0}\right|.
\]

Thus we can restrict ourselves to the case $0\leq \lambda<\mu$.
Set $P(\tau):=P_{\tau}f(\bar x)$ for all $\tau> 0$ and $P(0):=\bar x$.  Then by <ref>(c), there  exist positive scalars $\varepsilon$ and $\kappa$ such that

\begin{equation}\label{eq:Lip1}
\|P(\mu)-P(\lambda)\|\leq \kappa(\mu-\lambda)\quad \forall 0\leq \lambda\leq \mu\leq \varepsilon.
\end{equation}

For $0<\lambda<\mu\leq \varepsilon$, we have

\begin{equation*}
\begin{array}{rcl}
\vspace{0.2cm}
& = & \eta(\lambda)-\eta(\mu)\\
\vspace{0.2cm}
& \leq &\frac{1}{2\lambda}\left(\|P(\mu)-\bar x\|^2-\|P(\lambda)-\bar x\|^2-\|P(\mu)-P(\lambda)\|^2\right)\\
\vspace{0.2cm}
& = & \frac{1}{2\lambda}\left[\left(\|P(\mu)-\bar x\|-\|P(\lambda)-\bar x\|\right)\cdot\left(\|P(\mu)-\bar x\|+\|P(\lambda)-\bar x\|\right)-\|P(\mu)-P(\lambda)\|^2\right]\\
\vspace{0.2cm}
& \leq& \frac1{2\lambda}\|P(\mu)-P(\lambda)\|\cdot\left(\right \|P(\mu)-\bar x\|+\|P(\lambda)-\bar x\|-\|P(\mu)-P(\lambda)\|)\\
\vspace{0.2cm}
& \leq & \frac{\kappa}{2\lambda}|\mu-\lambda|\left(  \|P(\mu)-\bar x\|+\|P(\lambda)-\bar x\|-( \|P(\mu)-\bar x\|-\|P(\lambda)-\bar x\|)\right)\\
\vspace{0.2cm}
& = & \frac\kappa\lambda\|\bar x-P(\lambda)\|\cdot|\mu-\lambda|\\
& \leq & \kappa^2|\mu-\lambda|.
\end{array}
\end{equation*}

Here, the first identity follows from <ref>(a), where the first inequality uses <ref>(a). The rest the follows from the reverse triangle inequality and (<ref>), recalling that $P(0)=\bar x$.

The requirement that $\bar x\in\p f$, made in <ref>, cannot be relaxed to $\bar x\in \dom f$. To see this, we again use <ref>(b), where

\[
\eta^f_{\bar x}(\lambda)=
\begin{cases}
-\left(\lambda/2\right)^{\frac{1}{3}} & \mbox{if $\lambda\geq 0$,}\\
0  & \mbox{if $\lambda<0$,}
\end{cases}
\]

which is neither locally Lipschitz nor directionally differentiable at $\lambda=0$. We also conclude from this example that the lack of calmness of the proximal map at $\lambda=0$ is not necessarily compensated by applying $f$.

Under certain assumptions described by <ref>, we may interpret the extended proximal value function $\eta^f_{\bar x}$ as the derivative of the convex function

\begin{equation}\label{eq:phibar}
\bar \phi_{\bar x}^f:\lambda\in\R\mapsto
\begin{cases}
-\lambda e_\lambda f(\bar x) & \mbox{if $\lambda>0$,}\\
-\frac{1}{2}d^2_{\cl(\dom f)}(\bar x) & \mbox{if $\lambda=0$,}\\
-\lambda f(P_{\cl(\dom f)}(\bar x))-\frac{1}{2}d^2_{\cl(\dom f)}(\bar x)
& \mbox{if $\lambda<0$;}
\end{cases}
\end{equation}

cf. Attouch <cit.>.

Let $f\in \Gamma_0(\bE)$ and fix $\bar x\in \bE$. Then the following hold:

* $\bar \phi_{\bar x}^f$ is proper, convex and continuous (possibly in an extended real-valued sense), and continuously differentiable on $\R_{++}$ with $\frac{d}{d\lambda}\bar \phi_{\bar x}^f(\lambda)=-f(P_{\lambda}f(\bar x))$ locally Lipschitz

for  all $\lambda>0$.

* If $\bar x\in \dom f$, then $ \bar \phi_{\bar x}^f$ is continuously differentiable on $\R$ with  derivative given by

\[
\frac{d}{d\lambda}\bar \phi_{\bar x}^f(\lambda)
= -\eta_{\bar x}^f(\lambda)
\begin{cases}
-f(P_{\lambda}f(\bar x))& \mbox{if $\lambda>0$,}\\
-f(P_{\cl(\dom f)}(\bar x)) & \mbox{if $\lambda \leq 0$.}
\end{cases}
\]

If, more strictly, $\bar x\in\dom \p f$, then this derivative is locally Lipschitz

on all of $\R$.

* If $P_{\cl(\dom f)}(\bar x)\notin \dom f$, then $\dom \bar \phi_{\bar x}^f=\R_+$ and

\[
\p \bar \phi_{\bar x}^f(\lambda)=
\begin{cases}
-f(P_{\lambda}f(\bar x)) & \mbox{if $\lambda>0$,}\\
\emptyset & \mbox{if $\lambda \leq 0$.}
\end{cases}
\]

Proof. Set  $\bar \phi:=\bar \phi_{\bar x}^f(\lambda)$.
Part (a).  It is an easy computation to see that

\[
0<\lambda\mapsto -\bar \phi(\lambda)=\inf_{u}\left\{\lambda f(y)+\tfrac{1}{2}\|u-\bar x\|^2\right\}
\]

is concave, i.e., $0<\lambda \mapsto \bar \phi(\lambda)$ is convex. By setting $\bar \phi(0)=-\frac{1}{2}d^2_{\cl(\dom f)}(\bar x)$ and using <ref>(a), we see that $\bar \phi$ is a continuous convex function on $\R_+$, which is  linearly extended to $\R_-$.  All in all, $\bar \phi$
is convex, proper and continuous (possibly in an extended real-valued) sense.
From <ref>(b) (and the product rule) we infer, for all $\lambda>0$, that

\begin{equation*}
\bar \phi'(\lambda)
=  -e_\lambda f(\bar x)-\lambda\left(-\tfrac{1}{2}\left\|\tfrac1\lambda[\bar x-P_\lambda f(\bar x)]\right\|^2\right)
=  (1/2\lambda)\|\bar x-P_\lambda f(\bar x)\|^2-e_\lambda f(\bar x)
=  -f(P_\lambda f(\bar x)),
\end{equation*}

where the last equality follows from (<ref>). Hence, the local Lipschitz continuity  follows from <ref>(b).

Part (b). Here we assume that $P_{\cl(\dom f}(\bar x)\in \dom f$.  Then by definition of $\bar \phi$, we have  $\bar \phi'(\lambda)=-f(P_{\cl(\dom f)}(\bar x))$ for all $\lambda<0$.
It remains to establish the case $\lambda =0$. To this end, use the subgradient inequality to deduce that $g\in \p\bar \phi(0)$ if and only if $\bar \phi(0)+\lambda g\leq \bar \phi(\lambda)$ for all $\lambda$ if and only if

g + e_λf(x̅) - 12λd^2_(f)(x̅)    ≤0      ∀λ   >0,

λg + λf(P_(f)(x̅))    ≤0     ∀λ   <0,

hold simultaneously. (The case with $\lambda=0$ holds trivially.) From (<ref>), we infer that

\begin{eqnarray*}
g\le\inf_{\lambda >0}
\frac{\half d^2_{\cl(\dom f)}(\bar x)-\lambda e_\lambda f(\bar x)}{\lambda}
&\overset{\rm(i)}{=}& \inf_{\lambda >0}\frac{\bar \phi(\lambda)-\bar \phi(0)}{\lambda}
\\&\overset{\rm(ii)}{=}& \lim_{\lambda\downarrow 0} \frac{\bar \phi(\lambda)-\bar \phi(0)}{\lambda}
\\&\overset{\rm(iii)}{=}& \lim_{\lambda\downarrow 0}\frac{\half d^2_{\cl(\dom f)}(\bar x)-\lambda e_\lambda f(\bar x)}{\lambda} \\
&\overset{\rm(iv)}{=}& \lim_{\lambda\downarrow 0} \frac{-f(P_{\lambda} f(\bar x))}{1}\\
&\overset{\rm(v)}{=}& -f(P_{\cl(\dom f)}(\bar x)).
\end{eqnarray*}

Here, (i) is simply the definition of $\bar \phi$; (ii) holds because $\bar \phi$ is convex <cit.>; (iii) follows from the definition of $\bar \phi$; and (iv) follows from  l'Hôpital's rule, which is applicable because the last limit exists by <ref>(c), which implies (v). Hence, (<ref>) is equivalent to $g\leq -f(P_{\cl(\dom f}(\bar x))$. Combined with (<ref>), which is equivalent to $g\geq -f(P_{\cl(\dom f}(\bar x))$, establishes that $\p \bar \phi(0)=\{-f(P_{\cl(\dom f}(\bar x))\}$. Thus, $P_{\cl(\dom f}(\bar x)\in \dom f$, $\bar \phi$ is  differentiable, and hence continuously differentiable by convexity <cit.>. The remainder follows from <ref>(c).

Part (c). Here we assume that $P_{\cl(\dom f}(\bar x)\notin \dom f$.  Suppose $g\in \p \phi(0)$, i.e., analogous to some arguments in b),

\[
g\leq (1/2\lambda)d^2_{\cl(\dom f)} (\bar x)-e_\lambda f(\bar x)\quad \forall \lambda>0.
\]

On the other hand, using e.g., <ref>(b), we have

\begin{align*}
(1/2\lambda)d^2_{\cl(\dom f)} (\bar x)-e_\lambda f(\bar x)
&= (1/2\lambda)\|\bar x-P_{\cl(\dom f)}(\bar x)\|^2- (1/2\lambda)\|\bar x-P_\lambda f(\bar x)\|^2-f(P_\lambda f(\bar x))\\
&\leq  -f(P_\lambda f(\bar x)).
%& \to & -\infty.
\end{align*}

Since $ -f(P_\lambda f(\bar x))\to  -\infty $ as $\lambda\downarrow 0$,
this concludes the proof.

§.§ Semismoothness of the proximal value function

In view of the properties of the proximal value function, as outlined by <ref>,   the  question for  semismoothness of $\eta_{\bar x}^f$ on $\R_{++}$ arises naturally.  Now consider the expression (<ref>). The map $0<\lambda \mapsto e_{\lambda}f(\bar x)$ is continuously differentiable by <ref>(a), hence semismooth <cit.>. Moreover,
the map $0<\lambda\mapsto(1/2\lambda)\|\bar x-P_{\lambda}f(\bar x)\|^2$ is semismooth if $0<\lambda\mapsto P_{\lambda}f(\bar x)$ is semismooth <cit.>. Thus, when the latter holds,  we can conclude that $\eta^f_{\bar x}$ is semismooth. We can in addition use <ref>, which establishes conditions for  the semismoothness of the map $(x,\lambda)\in \bE\times \R_{++}\mapsto P_{\lambda}f(x)$, to obtain the following result.

Let $f\in\Gamma_0(\bE)$ and $\bar x\in\bE$. Then
$\eta_{\bar x}^f$ is semismooth at $\bar \lambda>0$ if $\p f$ is proto-differentiable and semismooth* at
$\left(P_{\bar\lambda}f(\bar x),\tfrac1\lambda[\bar x-P_{\bar\lambda}f(\bar x)]\right)$. This is the case   under either of the following conditions:

* (PLQ case) $f$ is piecewise-linear quadratic.

* ($C^2$ case) $f$ is twice continuously differentiable around $P_{\bar \lambda}f(\bar x)$. In this case, $\eta_{\bar x}^f$ is continuously differentiable.

§ POST-COMPOSITION ENVELOPES AND PROXIMAL MAPS

Given functions $\psi\in \Gamma_0(\bE)$ and  $g\in \Gamma_0(\R)$, we  consider the composition

\begin{equation*}\label{eq:comp}
(g\circ \psi)(x):=\begin{cases} g(\psi(x)) & \mbox{if $x\in \dom \psi$,}\\
+\infty & \mbox{otherwise.}
\end{cases}
\end{equation*}

It is well known that $g\circ \psi$ is closed proper convex if $g$ is increasing and that the intersection $\psi(\bE)\cap \dom g$ is nonempty; see, for example, Hiriart-Urruty and Lemaréchal <cit.>, who describe this operation as post-composition. We establish variational formulas for the Moreau envelope  and proximal map of the composition $g\circ \psi$ under a regularity assumption involving the intersection of domains. These results provide us with tools to infer properties of projections onto the epigraph and level sets of a closed proper convex function, as covered in <ref>.

Let $g\in \Gamma_0(\R)$   be increasing and let $\psi\in \Gamma_0(\bE)$ such that
\begin{equation}\label{eq:PCCQ}
(\ri\dom g) \cap \psi(\ri\dom \psi)\neq \emptyset.
\end{equation}

Then  the following properties hold.

* $e_1(g\circ \psi)(\bar x)=-\min_{\lambda\geq 0}\left\{g^*(\lambda)+\bar \phi^{\psi}_{\bar x}(\lambda)\right\}$, where $\bar \phi^{\psi}_{\bar x}$ is given by (<ref>).

* $P_1(g\circ \psi)(\bar x)=P_1(\bar \lambda\cdot \psi)(\bar x)$ for every $\bar \lambda\in\argmin_{\lambda\geq 0}\left\{ g^*(\lambda)+\bar \phi^{\psi}_{\bar x}(\lambda)\right\}\neq\emptyset$.

* If $\psi (P_{\cl(\dom \psi)}(\bar x))\notin\p g^*(0)$, then
\argmin_{\lambda\geq 0}\left\{ g^*(\lambda)+\bar \phi^{\psi}_{\bar x}(\lambda)\right\}\subset \R_{++}$.
This is, in particular, the case if $P_{\cl(\dom \psi)}(\bar x)\notin \dom \psi$.

Proof. Part (a). We find that

\begin{eqnarray*}
e_1 (g\circ \psi)(\bar x) & = & \min_{x\in \bE} \left\{\tfrac{1}{2}\|x-\bar x\|^2+(g\circ \psi)(x)\right\}\\
& = & {}{-}\left(\tfrac{1}{2}\|(\cdot)-\bar x\|^2+g\circ \psi\right)^*(0)\\
& = & \max_{y\in\bE,\lambda\geq 0} -\left\{g^*(\lambda)-\tfrac{1}{2}\|y\|^2+\ip{\bar x}{y}+(\lambda\cdot\psi)^*(-y)\right\}\\
& = & \max_{\lambda\geq 0}\big\{ -g^*(\lambda)+\max_{y\in\bE}\big[-\tfrac{1}{2}\|y\|^2-\ip{\bar x}{y}-(\lambda\cdot\psi)^*(-y)\big]\big\}\\
&= & \max_{\lambda\geq 0}\ -g^*(\lambda)-\bar \phi^{\psi}_{\bar x}(\lambda).
\end{eqnarray*}

Here, the third identity uses   <cit.>  with $f:=\frac{1}{2}\|(\cdot)-\bar x\|^2$, $F:=\psi$, and $K=\R_+$, realizing that (<ref>) is equivalent to qualification condition <cit.> because $\dom g-\R_+=\dom g$, and observing that attainment is guaranteed by finiteness of the left-hand side. The last identity uses Fenchel duality <cit.> and the definition of $\bar \phi^{\psi}_{\bar x}$ in (<ref>).

Part (b). Note that by <cit.>,

\begin{equation}\label{eq:SDPC}
\p(g\circ \psi)(x)=\ \bigcup_{\mathclap{\lambda \in \p g(\psi(x))}}\ \p(\lambda\cdot\psi)(x)\quad \forall x\in \dom g\circ \psi,
\end{equation}

and observe that $\p g(x)\subset \R_+$ because $g$ is increasing.
Next, observe that

\begin{equation*}
\begin{array}{rcl}
\bar \lambda \in \argmin_{\lambda\geq 0} \{g^*(\lambda)+\bar \phi^{\psi}_{\bar x}(\lambda)\},\; \bar u=P_{1}(\bar \lambda\cdot\psi)(\bar x)
&\overset{\rm(i)}\Longleftrightarrow & 0\in \p g^*(\bar \lambda)+\p\bar \phi^\psi_{\bar x}(\bar \lambda),\; \bar u=P_{1}(\bar \lambda\cdot\psi)(\bar x)\\
&\overset{\rm(ii)}\Longleftrightarrow & \psi(\bar u)\in \p g^*(\bar \lambda), \; \bar u=P_{1}(\bar \lambda\cdot\psi)(\bar u)\\
&\overset{\rm(iii)}\Longleftrightarrow & \bar \lambda \in \p g( \psi(\bar u)),\; \bar u=P_{1}(\bar \lambda\cdot\psi)(\bar x)\\
&\overset{\rm(iv)}\Longleftrightarrow &  \bar \lambda \in \p g(\psi(\bar u)),\; 0\in  \bar u-\bar x+\p (\bar \lambda\cdot\psi)(\bar x)\\
&\overset{\rm(v)}\Longrightarrow &  \bar u=P_{1}(g\circ \psi)(\bar x).
\end{array}
\end{equation*}

Equivalence (i) is valid because $\inter(\dom g^*)\subset \R_{++}\subset \inter(\dom \bar \phi^{\psi}_{\bar x})$; see <cit.>  and  <ref>, respectively.  <Ref>(b) justifies equivalence (ii). Equivalence (iii) is the inversion formula for the subdifferential <cit.>. Equivalence (iv) uses the optimality conditions that uniquely determines $\bar u=P_{1}(\bar \lambda\cdot\psi)(\bar x)$. Implication (v) follows from (<ref>) and the optimality conditions that uniquely determine $P_1(g\circ \psi)(\bar x)$. Taken together, we deduce that for any $\bar \lambda\in  \argmin_{\lambda\geq 0} g^*(\lambda)+\bar \phi^{\psi}_{\bar x}(\lambda)$, we have $P_1(g\circ \psi)(\bar x)=P_1(\lambda\cdot \psi)(\bar x)$. The fact that $\argmin_{\lambda\geq 0}\left\{ g^*(\lambda)+\bar \phi^{\psi}_{\bar x}(\lambda)\right\}\neq \emptyset$ follows from Part (a).

Part (c). Recall from Part (b) that $0\in \argmin_{\lambda \geq 0}\{g^*+\phi_{\bar x}^\psi\}$ entails
0\in \p g^*(0)+\p\phi_{\bar x}^f(0).
In view of <ref>(c), we must have $P_{\cl(\dom \psi)}(\bar x)\in \dom \psi$, in which case $\p\phi_{\bar x}^\psi(0)=-\psi(P_{\cl(\dom \psi)}(\bar x))$, by <ref>(b). This proves the claim.

§ EPIGRAPHICAL AND LEVEL-SET PROJECTIONS

We are now equipped to answer the initial question about computing epigraphical and level-set projections via proximal mappings. Our approach is based on the Moreau envelopes of the indicator functions to the epigraph and level set of a function $f$, which we express as the post-compositions

\[
\delta_{\lev{\alpha}{f}} = (\delta_{\R_-})\circ(f(\cdot)-\alpha)
\quad\UND\quad
\delta_{\epi f} = (\delta_{\R_-})\circ(f(\cdot)-(\cdot)).
\]

<Ref> provides the required tools.

Let $f\in \Gamma_0(\bE)$, $(\bar x,\,\bar \alpha)\in\bE\times\R$, and assume there exists $\hat x\in\bE$ such that $f(\hat x)<\bar \alpha$. Then the following statements hold.

* (Dual representation of distance to level set)

\[
\tfrac{1}{2}d^2_{\lev{\bar \alpha}{f}}(\bar x)=-\min_{\lambda\geq 0}\left\{ \bar \phi_{\bar x}^f(\lambda)+\bar \alpha\lambda\right\}.
\]

* (Projection onto level set)

\[
P_{\lev{\bar \alpha}{f}}(\bar x)=
\begin{cases}
P_{\cl(\dom f)}(\bar x) & \mbox{if $f(P_{\cl(\dom f)}(\bar x))\leq \bar\alpha$,}  \\
P_{\bar \lambda}f(\bar x) & \mbox{otherwise,}
\end{cases}
\]

for any positive $\bar\lambda$ in the optimal solution set

\begin{equation*}
\argmin_{\lambda\geq 0}\ \{\bar \phi_{\bar x}^f(\lambda)+\bar \alpha\lambda\}
=\set{\lambda\geq 0}{f(P_{\lambda}f(\bar x))=\bar \alpha}\neq\emptyset.
\end{equation*}

Set $g:=\delta_{\R_-}$ and $\psi:x\in\bE\mapsto f(x)-\bar\alpha$. Then $g\in\Gamma_0(\R)$ is increasing and $\psi\in \Gamma_0(\bE)$ with $\dom \psi =\dom f$ and
$\delta_{\lev{\bar \alpha}{f}}=g\circ \psi$. Now observe that (<ref>) applied to this setting is equivalent to saying that there exists $\bar y\in \ri(\dom f)$ such that $f(\bar y)<\bar \alpha$. We (only) assume that there exists $\hat x\in\dom f$ such that $f(\hat x)<\bar \alpha$. However, take any $z\in \ri(\dom f)$, then, by the line segment principle <cit.>,  we have $y_\lambda:=\lambda z+(1-\lambda)\hat x\in \ri(\dom f)$ for all $\lambda \in (0,1]$. Moreover,
$f(y_\lambda)< \lambda f(z)+(1-\lambda)\bar\alpha\to \bar\alpha$ as $\lambda \downarrow 0$. Hence there exists $\hat \lambda\in(0,1]$ sufficiently small such that $f(y_{\hat \lambda})<\bar\alpha$. Hence $\hat y:=y_{\hat \lambda}\in\ri(\dom f)$ with $f(\hat y)<\bar \alpha$, and (<ref>) holds.

Part (a). For all $\lambda \geq 0$,

\begin{equation*}
\begin{array}{rcl}
\vspace{0.2cm}
\bar \phi_{\bar x}^\psi(\lambda)& = &
\begin{cases}
-\lambda e_{\lambda}\psi(\bar x) & \mbox{if $\lambda>0$,}\\
-\frac{1}{2}d^2_{\cl(\dom \psi)}(\bar x) & \mbox{if $\lambda=0$,}
\end{cases}\\
\vspace{0.2cm}
& =&
\begin{cases}
-\lambda( e_{\lambda}f(\bar x)-\bar \alpha) & \mbox{if $\lambda>0$,}\\
-\frac{1}{2}d^2_{\cl(\dom f)}(\bar x) & \mbox{if $\lambda=0$,}
\end{cases}\\
&= & \bar \phi_{\bar x}^f(\lambda)+\bar \alpha\lambda.
\end{array}
\end{equation*}

Use <ref>(a) and the fact that  $ g^*=\delta_{\R_+}$ to deduce that

\[
\tfrac{1}{2}d^2_{\lev{\bar \alpha}{f}}(\bar x)
= e_1\delta_{\lev{\bar \alpha}{f}}(\bar x)
= e_1(g\circ \psi)(\bar x)
= -\min_{\lambda\geq 0}\left\{ \bar \phi_{\bar x}^f(\lambda)+\bar \alpha\lambda\right\}.
\]

Part (b). The equality of the two sets in question is clear from the (necessary and sufficient) optimality conditions and <ref>.   The rest follows from <ref>, Parts (b) and (c) because $P_{\lev{\bar \alpha}{f}}(\bar x)=P_1(g\circ \psi)(\bar x)$.

Let $f\in \Gamma_0(\bE)$ and $(\bar x,\,\bar \alpha)\in\bE\times\R$. Then the following statements hold.

* (Dual representation of distance to epigraph)

\[
\tfrac{1}{2}d^2_{\epi f}(\bar x,\bar \alpha)
=-\min_{\lambda\geq 0}\left\{
\bar \phi_{\bar x}^f(\lambda)+\bar \alpha\lambda+\tfrac12\lambda^2
\right\}.
\]

* (Projection onto epigraph)

\[
P_{\epi f}(\bar x)=
\begin{cases}
[P_{\cl(\dom f)}(\bar x),\ \bar \alpha] & \mbox{if $f(P_{\cl(\dom f)}(\bar x))\leq \bar\alpha$,}
\\ [P_{\bar \lambda}f(\bar x),\ \bar \alpha+\bar \lambda] & \mbox{otherwise,}
\end{cases}
\]

where $\bar \lambda>0$ is the unique solution of the strongly convex optimization problem

\begin{equation*}
\min_{\lambda \geq 0}\ \tfrac{1}{2}\lambda^2+\bar \alpha \lambda+ \bar \phi_{\bar x}^f(\lambda).
\end{equation*}

Equivalently, $\lambda$ is the  unique root of the strictly decreasing function  $0<\lambda\mapsto f(P_{\lambda}f(\bar x))-\lambda-\bar \alpha$.

Proof. Analogous to the proof of <ref>, we define closed proper convex functions $g:=\delta_{\R_-}$ and $\psi:(x,\alpha)\in \bE\times \R\mapsto f(x)-\alpha $ so that $\delta_{\epi f}=g\circ \psi$. Therefore,

\[
\psi(\ri(\dom \psi))=\psi(\ri(\dom f)\times \R)=f(\ri(\dom f))-\R=\R,
\]

and thus the qualification condition (<ref>) is trivially satisfied in this setting.

Part (a). Note that $e_\lambda \psi( x,\alpha)=e_\lambda f(x)+e_\lambda (-\id)(\alpha)$ for all $\lambda>0$ <cit.>, and since $\dom \psi=\dom f$,

\[
\bar \phi^\psi_{\bar x,\bar \alpha}(\lambda)=\bar  \phi^f_{\bar x}(\lambda)+\bar \alpha \cdot\lambda+\tfrac12\lambda^2\quad (\lambda\geq 0).
\]

Apply <ref>(a) to obtain the desired result.

Part (b). Apply <ref>(b), observing that $P_{\epi f}(\bar x,\bar \alpha)=P_1 \delta_{\epi f}(\bar x,\bar \alpha)$ and  $P_1(\lambda\cdot\psi)(\bar x,\bar \alpha)=[P_1(\lambda  f)(\bar x),\bar \alpha+\lambda]$ for all $\lambda\geq 0$ <cit.>. The  fact that  $\bar \lambda>0$ is due to  <ref>(c).

The level-set projection result <Ref> encompasses the result described by Beck <cit.>. For epigraphical projection, <ref> generalizes Beck <cit.> to include functions that aren't finite-valued.
For functions $f\in \Gamma_0(\bE)$ with open domain, Chierchia et al. <cit.> describe an alternative formula for epigraphical projections via proximal maps.

§.§ An SC$^1$ optimization framework

In this section we present a unified algorithmic framework  for  computing projections onto the level sets and the epigraph of a closed proper convex function. <Ref>, respectively, guide us in how to compute these projections. For a given $f\in \Gamma_0(\bE)$ and $(\bar x,\bar \alpha)\in \bE\times \R$ such that $f(\bar x)>\bar \alpha$, the epigraphical and level-set projections, respectively, correspond to the proximal map of $f$ with parameter $\lambda$ that solves the scalar problem

\begin{equation}\label{eq:min-theta}
\min_{\lambda\geq 0}\ \theta_\xi(\lambda)\quad (\xi\in \{\epi, \lev{}{}\}),
\end{equation}

for  $\theta_\xi:\R\to\rbar$ given by

\begin{equation}\label{eq:thetaLev}
\theta_{\xi}(\lambda)=
\begin{cases}
\bar \phi^f_{\bar x}(\lambda) + \bar \alpha \lambda & \mbox{if $\xi=\lev{}{}$,}\\
\bar \phi^f_{\bar x}(\lambda) + \bar \alpha \lambda+ \tfrac{1}{2}\lambda^2& \mbox{if $\xi=\epi$.}
\end{cases}
\end{equation}

<Ref> asserts that $\theta_\xi$ is convex, continuous (possibly in an extended real-valued sense), and continuously differentiable with monotonically increasing, locally Lipschitz

derivative on  $\R_{++}$. In particular, for any $\lambda>0$,

\begin{equation} \label{eq:theta-prime}
\theta_\xi'(\lambda)=\begin{cases}
-\eta_{\bar x}^f(\lambda) + \bar \alpha & \mbox{if $\xi=\lev{}{}$,}\\
-\eta_{\bar x}^f(\lambda) + \bar \alpha +\lambda& \mbox{if $\xi =\epi$,}
\end{cases}
\end{equation}

The minimization of $\phi_\eta$ could be accomplished using bisection if an upper bound on the optimal $\lambda$ is available. However, the semismoothness of the derivative (<ref>), described by <ref>, allows us to tap into the powerful SC$^1$ optimization framework [25, 44] that operates on functions $\theta:\R\to\rbar$ that are semismoothly differentiable (i.e., SC$^1$), which means that at points $\bar \lambda\in\inter(\dom \theta)$, the gradient $\theta'$ exists, and it is locally Lipschitz around $\bar\lambda$ and  semismooth at $\bar \lambda$. The semismooth method, outlined by <ref>, applies to the problem (<ref>) whenever conditions (A1) and (A2) of Pang and Qi [44] hold, which is the case when $\bar x\in\dom \p f$; see <ref>.

<Ref> uses the notion of a Bouligand subdifferential, which for a function $\phi:\R^n\to \rbar$ that is locally Lipschitz at a point $\bar x \in\inter (\dom \phi)$, is defined at $\bar x$ as
\p_B \phi(\bar x)=\set{v}{\exists \{x_k\in D_\phi,\ x_k\to\bar x\}: \nabla \phi(x_k)\to v},
where $D_\phi$ is the set of points of differentiability of $\phi$. The  Clarke subdifferential [17] of $\phi$ at $\bar x$ is
\p_C\phi(\bar x):=\co  \p_B \phi(\bar x),
which coincides (on the interior of $\dom \phi$) with the convex subdifferential if $\phi$ is convex.

(S.0) Choose $\lambda_0,\delta>0$, $\{\varepsilon_k\}\downarrow 0$,  and let $\beta,\sigma\in  (0,1)$. Set $k:=0$.

(S.1) If $|\theta'(\lambda_k)|\leq \delta:$ STOP.

(S.2) Choose $g_k\in \p_B(\theta_\xi')(\lambda_k)$ and set

\[
\Delta_k:=P_{[-\lambda_k,\infty)}\left( -\frac{\theta_\xi'(\lambda_k)}{g_k+\varepsilon_k}\right).
\]

(S.3) Set

\[
t_k:=\max_{l\in \bN_0}\set{\beta^l}{\theta_\xi(\lambda_k+\beta^l\Delta_k)\leq \theta_\xi(\lambda_k)+\beta^l\sigma \theta_\xi'(\lambda)\Delta_k}.
\]

(S.4) Set $\lambda_{k+1}:=\lambda_k+t_k\Delta_k$, $k\leftarrow k+1$, and go to (S.1).

SC$^1$ Newton method for minimizing $\theta_\xi$

Because $\theta_{\xi}$ is convex  and differentiable with  locally Lipschitz derivative on $\R_{++}$, all elements in the  Clarke subdifferential $\p_C(\theta_\xi')(\lambda)$ are nonnegative for all $\lambda>0$ [25]. In the epigraphical case (i.e., $\xi=\epi$),  the quadratic term in the expression for $\theta_\epi$ in (<ref>) implies that the elements are bounded below by $1$. Thus, the sequence of regularization parameters $\{\varepsilon_k\}\downarrow 0$ in <ref> is not necessary, and in fact, if $\theta'$ is piecewise affine, the regularization could be eliminated by setting the constant regularization $\varepsilon_k:=0$ for all $k$, which would improve numerical convergence regardless of the optimality parameter $\delta>0$.

§.§.§ The case where $\theta_\xi'$ is concave on $(0,\lambda_l)$

<Ref> imply that there exists positive parameters $\lambda_l\leq\lambda_u$ such that

\begin{equation} \label{eq:SolLam}
[\lambda_l,\lambda_u]=\argmin_{\lambda\geq 0}\theta_{\xi}=\set{\lambda>0}{\theta_\xi'(\lambda)=0},
\end{equation}

for both the epigraphical and level-set cases. In the epigraphical case in particular, the solution is unique, and thus $\lambda_u=\lambda_l$; see <ref>(b). If the derivative $\phi_\xi$ is concave on the interval $(0,\lambda_\ell)$, it is possible to take a full Newton step at every iteration while respecting positivity of the iterates, thus saving the computational cost of a backtracking line-search. The simplified iteration is described by <ref>.

For many important functions, e.g., the 1-norm or negative $\log$,  (and their spectral counterparts), the respective map $\theta_\xi'$ is concave on  $\R_{++}$, but, as suggested above,  we only need the following:

[Concavity $(0,\lambda_l)$]
The function $\theta'_\xi$ is concave on $(0,\lambda_l)$.

(S.0) Choose $\lambda_0 >0$, $\delta>0$, and $\{\varepsilon_k\} \downarrow 0$.  Set $k:=0$.

(S.1) If $|\theta'_\xi(\lambda_k)|\leq \delta:$ STOP.

(S.2) Choose $g_k\in \p_{C}(\theta'_\xi)(\lambda_k)$ and set

\[
\Delta_k:=\max\left\{\frac{-\lambda_k}{2},\ \frac{-\theta'_\xi(\lambda_k)}{g_k+\varepsilon_k}\right\}.
\]

(S.3) Set $\lambda_{k+1} := \lambda_k + \Delta_k$, $k\leftarrow k+1$, and go to (S.1).

Full-step SC$^1$ Newton method

Under <ref>, the full-step Newton method from <ref> converges to a minimizer of $\theta_\xi$.

Set $\theta=\theta_\xi$. If $0<\lambda_k<\lambda_l$ for some $k\in \bN$, then by <ref>(a), $\theta'(\lambda_k)<0$ by monotonicity of $-\theta'$. Therefore,

\[
\lambda_{k+1}=\lambda_k-\frac{\theta'(\lambda_k)}{g_k+\varepsilon_k}>\lambda_k.
\]

Since $ -(g_k+\varepsilon_k)$ is a convex subgradient of $-(\theta'+\varepsilon_k(\cdot))$, the concavity of $\theta'_\xi$ implies that

\[
-\theta'(\lambda_{k+1})-\varepsilon_k(\lambda_{k+1}-\lambda_k)\geq -\theta'(\lambda_k)-(\lambda_{k+1}-\lambda_k)(g_k+\varepsilon_k)=0,
\]

and hence $\theta'(\lambda_{k+1})<0$, thus $0<\lambda_k<\lambda_{k+1}<\lambda_l$. Consequently, by an inductive argument, $\{\lambda_k\}$ converges to some $\tilde\lambda$. Therefore,  the sequence $\{g_k\in \p_C(\theta_\xi)(\lambda_k)\}$ is bounded, and hence

\begin{equation*}
0 = (\lambda_{k+1} - \lambda_{k})(g_k + \varepsilon_k) + \theta'(\lambda_k) \to
\theta'(\tilde{\lambda}),
\end{equation*}

which shows that $\tilde \lambda $ has the desired properties. We hence still  need to cover the case where
$ \lambda_l<\lambda_k$ for all $k\in\bN$.   In view of (<ref>), we can assume that $\lambda_u<\lambda_k$ for all $k\in\bN$. (Otherwise, a solution has already been obtained.) Since $\theta'(\lambda_k)> 0$ here,  we observe that

\[
0<\lambda_u<\lambda_{k+1} =\lambda_k+ \max\left\{\frac{-\lambda_k}{2},\ \frac{-\theta'(\lambda_k)}{g_k+\varepsilon_k}\right\}\leq \lambda_k,
\]

hence the sequence $\{\lambda_k\}$ converges  to some $\hat \lambda$.   In particular, $\lambda_{k+1}=\tfrac12\lambda_k$ only finitely many times. Hence, without loss of generality,
0= (\lambda_{k+1} - \lambda_{k})(g_k + \varepsilon_k) + \theta'(\lambda_k)\to \theta'(\hat \lambda),
which gives $\theta'(\hat \lambda)=0$ also here.

The next example illustrates that cycling may occur in <ref> if Assumption <ref> fails.

Consider the scalar function $f(x) = 2|x| + \delta_{\left[-1,1\right]}(x)$, and the task of projecting the $(\bar{x},\bar{\alpha}) = (4,-1)$ onto $\epi f$. <Ref> illustrates the function $\theta'_\epi$ whose root we seek.  Then for $\lambda_0$ outside of the interval $\left[1.5,2\right]$ the iterates $\lambda_k\;(k\in\bN)$ generated by <ref> oscillate between $1.5$ and $3$.

§.§ Numerical Experiments

We present numerical experiments that hint at the computational effectiveness of the SC$^1$ optimization framework described in <ref>. The two experiments in this section were run on an Apple Macbook Air with a 1.8GHz Intel Core i5 and 8Gb RAM running OS 10.14.6. The code was written in C and available at <https://github.com/arielgoodwin/epi-proj>.

§.§.§ Level-set projection: 1-norm
An important instance of the level-set case ($\xi=\lev{}{}$) is the projection onto the unit 1-norm ball $\lev{1}{\|\cdot\|_1}=\set{x\in\R^n}{\|x\|_1\leq 1}$. The derivative of the corresponding function $\theta_{\lev{}{}}$ reads

\[
\theta_{\lev{}{}}'(\lambda)
\begin{cases}
1 - \sum_{i = 1}^n\max\{|x_i| - \lambda, 0\} & \mbox{if $\lambda \geq 0$,}\\
1-||x||_1 & \mbox{if $\lambda < 0$,}
\end{cases}
\]

which is concave on $\R_+$ (as required) and piecewise affine, as shown by <ref>.

[scale = 0.9,
declare function=
func() = (<= 0) * (-6.1) +
and(> 0, <= 0.8) * (4*- 6.1) +
and(> 0.8, <= 1.3) * (3*-5.3) +
and(> 1.3, <= 2) * (2*-4) +
and(> 2, <= 3) * (- 2) +
(> 3) * (1)

axis x line=middle, axis y line=middle,
ymin=-6.5, ymax=2, ytick=-5,-3,-1,1, ylabel=
xmin=-4, xmax=5, xtick={-5,-3,-1,1,3,5}, xlabel=$$
[thick] func(x);

figureThe function $\theta'_\epi$ corresponding to the projection of point $\bar x = (-2,0.8,3,1.3)$ onto the 1-norm unit ball.

[scale = 0.9]
[thin,->] (-1,0) – (3.5,0) ;
[thin,->] (0,-2.5) – (0,2.5);
[very thick](0.4,-2.6) – (1.5,-1.5) – (2,1) – (3,2) node[anchor=west] $\phi'_\xi$;
[dotted,very thick] (2,1) –  (1,0);
[dotted,very thick] (0.4,-2.6) – (3,0);
in 1,2,3
(cm,-1pt) – (cm,1pt) node[anchor=north] $\x$;
in -2,-1,1,2
(-1pt,cm) – (1pt,cm) node[anchor=east] $\y$;

figureThe function $\theta'_\epi$ for <ref>, for which <ref> may cycle.

We implemented <ref> and compared it numerically to two state-of-the-art algorithms specifically tailored to 1-norm-ball projection, namely Condat's sorting-based method [21] as implemented in the code , and Liu and Ye's improved bisection algorithm (IBIS) [37] implemented in the  module in SLEP [49].

$n$ 		    Algorithm 2 			    Condat 	        IBIS				     Algorithm 2 			    Condat  	  	    IBIS

3c|$\sigma = 0.1$ 					    3c$\sigma = 0.05$

$20$ 		   1.94e-6		    1.53e-6 	   1.83e-6		    1.93e-6	    1.41e-6 	   1.99e-6

$10^3$ 	   3.33e-5		    2.11e-5 	   3.65e-5		    3.38e-5	    2.23e-5	   4.15e-5

$10^6$ 	   2.08e-2		    1.44e-2 	   2.89e-2		    2.18e-2 	   1.44e-2		   3.42e-2

3c|$\sigma = 0.01$
3c$\sigma = 0.005$

$20$ 	       2.05e-6		   1.45e-6		   1.87e-6		    1.92e-6	    1.36e-6 	   2.32e-6

$10^3$        3.14e-5		   2.57e-5		   4.07e-5		    3.06e-5	    2.68e-5	   4.46e-5

$10^6$        1.93e-2		   1.48e-2 	   3.73e-2		    1.89e-2 	   1.50e-2		   4.00e-2

Average time (seconds) for projecting vectors onto the 1-norm unit ball in dimension $n$, with coordinates chosen using Gaussian distributions with standard deviation $\sigma$.

The entries of the projected vectors $\bar x\in\R^n$ are drawn from a Gaussian distribution with zero mean and standard deviations $\sigma=\{0.1,0.05,0.01,0.005\}$. The optimality tolerance was fixed at $\delta=10^{-15}$, as in step (S.1) of <ref>.

<Ref> reports the average time required to compute the projection over $10^5$ trials for vectors of dimension $n \in \{20, 10^3\}$, and over 500 trials for $n=10^6$. The initial point $\lambda_0>0$ <ref> was chosen by sampling $\sqrt{n}\log n$ coordinates randomly from the vector $\bar x$ and setting $\lambda_0$ to be the largest of their absolute values.
Observe that <ref> exhibits comparable performance relative to the specialized algorithms.

§.§.§ Level-set projection: negative sum-log

We now consider the epigraphical projection for a function that is not polyhedral. Define the function $f:x\in\R^n\mapsto - \sum_{i = 1}^n\log x_i$, where we take the negative logarithm to be $\infty$ outside the positive orthant. <Ref> illustrate the function $\phi'_\epi$ for the case when $P_{\cl(\dom f)}(\bar x)$ is in, and not in, the domain of $f$. These functions are concave over $(0,\infty)$. Hence $-\theta'_\xi$ is convex over this interval and <ref> applies.

[scale = 0.85,
declare function=
func() = (<= 0) * (- 1) +
(> 0) * (- 1 + ln((1+sqrt(1+4*))/2))

axis x line=middle, axis y line=middle,
ymin=-4, ymax=6, ytick=-3,-1,...,5, ylabel=,
xmin=-3, xmax=5, xtick=-3,-1,...,5, xlabel=,
domain=-3:5,samples = 100,
[thick] func(x);

[scale = 0.85,
declare function=
func() = (> 0) * (- 1 + ln((-1+sqrt(1+4*))/2)) +
(<= 0) * (-10)

axis x line=middle, axis y line=middle,
ymin=-4, ymax=6, ytick=-3,-1,...,5, ylabel=,
xmin=-2, xmax=5, xtick=-1,0,...,5, xlabel=,
[thick] func(x);

$(\bar x, \bar \alpha)=(+1,-1)$     $(\bar x, \bar \alpha)=(-1,-1)$

The graph of the function $\theta'_\epi(\lambda)$ that corresponds to the base points $(\bar x,\bar \alpha)$ shown for each figure. The left panel depicts the case where $P_{\cl(\dom f)}(\bar x)\in\dom f$; the right panel depicts the case where $P_{\cl(\dom f)}(\bar x)\notin\dom f$.

We numerically compare <ref> and the bisection method as solution approaches for (<ref>). The coordinates of $\bar x$ were chosen uniformly at random on the interval $[-1,1]$, and the value $\bar \alpha$ was chosen uniformly at random on the interval $[-2,-0.5]$. The initial value $\lambda_0$ was chosen to be $\sqrt N$. The termination condition for <ref> was $|\theta'_\xi(\lambda)| < 10^{-4}$, and the termination conditions for bisection was $|\theta'_\xi(\lambda)| < 10^{-4}$ (labeled Bisection 1) and $|b-a| < 10^{-8}$ (labeled Bisection 2), where $a,b$ denote the endpoints of the bisection interval. <Ref> shows the average times over $10^5$ trials when $n \in \{1, 10^3\}$, and over 500 trials when $n=10^6$.

$n = 1$			    $n = 10^3$		    $n = 10^6$
SSN				    8.76e-7	   1.69e-4		   1.90e-1

Bisection 1         	    2.36e-6       	   1.88e-3		   2.89e0

Bisection 2		    2.66e-6           1.08e-3	   1.16e0

Time (seconds) for projecting vectors onto the epigraph of $f(x)=-\sum_{i=1}^n\log x_i$ in various dimensions $n$.

§.§.§ Discussion

The numerical examples we presented extend easily to other useful cases involving matrices, such as the nuclear norm on $\R^{m\times n}$ and the barrier function $-\log\det $ on the space of symmetric matrices, using variational formulas that depend on matrix spectra [34, 35].  In these cases, the main computational effort involves computing singular value and eigenvalue decompositions, respectively, of the matrix iterates.

The cases where $\theta'_\xi$ does not satisfy either Assumption <ref> or the domain condition $P_{\cl(\dom f)}(\bar x) \in \dom f$  lies  outside the theoretical guarantees presented in this section, though the algorithms we present may still work in practice. In the case where $\dom f\subsetneq\bE$ is open, the formula provided by Chierchia et al. <cit.> is a viable option.

§ FINAL REMARKS

Our analysis on the variational properties of epigraphical projections and infimal convolution is motivated by the authors' larger research interests on variations of first-order methods that operate in a lifted space. The promising work by Chierchia et al. [16] on epigraphical-projection methods for minimizing convex functions over $p$-norm constraints shows promise for this algorithmic approach, and we aim to develop methods for more general problem classes. We are also motivated by statistical M-estimation approaches that include as an additional unknown a particular parameter that characterizes data distribution [20]. The variational calculus that we derive is a useful tool for developing algorithmic approaches for solving these lifted M-estimation problems.

There are at least two avenues of future research that extend our analysis in this paper.

$\bm{K}$-epigraphical projections. A significant generalization of the post-composition operation defined in <ref> occurs when we allow compositions of the form $f=g\circ H:\bE_1\to\rbar$, where

* $K\subset \bE_1$ a  closed convex cone;

* $H:\bE_1\to \bE_2$ $K$-convex, i.e., the $K$-epigraph $\set{(X,Y)}{Y-H(x)\in K}$ is convex;

* $g\in \Gamma_0(\bE_2)$ $K$-increasing, i.e., $g \leq g((\cdot)+v)$ for all $v\in K$.

This convex convex-composite setting was studied by Burke et al. [15], and  the required subdifferential formulas for the analysis are readily available. This may lead to a proximal calculus and ultimately to formulas and algorithms for projecting onto $K$-epigraphs, thus encompassing the study in <ref>.

Semismoothness* of subdifferential operators. The notion of semismooth* sets and maps is recent and still in development. One of the critical conditions in our study is the semismoothness* of the subdifferential operator $\p f$, which also occurs in a recent report by Khanh et al. [32]. This suggests an important avenue of research that relaxes the overarching convexity assumption and, in particular, establishes verifiable  sufficient conditions.

§ ACKNOWLEDGMENTS
M.P. Friedlander and T. Hoheisel are supported by NSERC Discovery grants, while A. Goodwin's work was partially supported by an NSERC summer research stipend.
T. Hoheisel would like to thank Dr. Matus Benko,  University of Vienna, for valuable discussions on semismoothness*.

[2]A.Y. Aravkin , J.V. Burke, D. Drusvyatskiy, M.P. Friedlander, and K.J. MacPhee:
Foundations of Gauge and Perspective Duality.
SIAM Journal on Optimization, 28(3), 2018,  pp. 2406–2434.

[3]H. Attouch:
Variational Convergence for Functions and Operators. Applied Mathematics Series, Pittman, Boston, 1984.

[4]H.H. Bauschke and P.L. Combettes:
Convex analysis and Monotone Operator Theory in Hilbert Spaces.
CMS Books in Mathematics, Springer, New York, 2nd Edition,  2017.

[5]A. Beck:
First-Order Methods in Optimization.
MOS-SIAM Series on Optimization, 2017.

[7]A. Beck and M. Teboulle:
Smoothing and first order methods: A unified framework.
SIAM Journal on Optimization 22 (2), 2012, pp. 557–580.

[8]M. Benko, H. Gfrerer, and J.V. Outrata: Calculus for Directional Limiting Normal Cones and Subdifferentials.
Set-Valued and Variational Analysis 27,  2019, pp. 713–745.

[9]M. Bougeard, J.P. Penot, and A. Pommellet:
Towards minimal assumptions for the infimal convolution regularization.
Journal of Approximation Theory 64(3), 1991, pp. 245–270.

[10]J.V. Burke and T. Hoheisel: Epi-convergent smoothing with applications to convex composite functions. SIAM Journal on Optimization 23(3), 2013, pp. 1457–1479.

[12]J.V. Burke and T. Hoheisel:
Epi-convergence properties of smoothing by infimal convolution.
Set-Valued and Variational Analysis 25, 2017, pp. 1–23.

[15] 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, to appear.

[16]G. Chierchia, N. Pustelnik, J.-C. Pesquet, B. Pesquet-Popescu:
Epigraphical projection and proximal tools for solving constrained convex optimization problems.
Signal, Image and Video Processing 9, 2015,  pp. 1737–1749.

[17] F.H. Clarke:
Optimization and Nonsmooth Analysis.
John Wiley & Sons, New York, 1983.

[18] P.L. Combettes: Perspective functions: properties, constructions, and examples.
Set-Valued and Variational Analysis 26, 2019, pp. 247–264.

[19] P.L. Combettes and C.L. Müller:
Perspective functions: proximal calculus and applications in high-dimensional statistics.
Journal of Mathematical Analysis and Applications 457(2), 2018, pp. 1283–1306.

[20] P.L. Combettes and C.L. Müller:
Perspective maximum likelihood-type estimation via proximal decomposition.
Electronic Journal of Statistics 14, 2020, pp. 207–238.

[21]L. Condat: Fast projection onto the simplex and l1 ball.
Mathematical Programming, Series A, Springer, 2016, 158 (1), pp. 575–585.

[22]L. Condat: URL <https://lcondat.github.io/software.html>
Last accessed January 27, 2021.

[23]A.L. Dontchev and R.T. Rockafellar:
Implicit Functions and Solution Mappings. A View from Variational Analysis.
Springer Series in Operations Research and Financial Engineering, Springer-Verlag New York, 2014.

[24]J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra:
Efficient projections onto the l1-ball for learning in high dimensions.
ICML '08: Proceedings of the 25th international conference on Machine learning, ACM, New York, NY, USA,  2008, pp. 272–279.

[25] F. Facchinei and J.-S. Pang: Finite-Dimensional
Variational Inequalitites and Complementarity Problems, Volumes I
and II, Springer, New York, 2003.

[26]H. Gfrerer:
On directional metric subregularity and second-order optimality conditions for a class of nonsmooth mathematical programs.
SIAM Journal  on  Optimization  23(1), 2013, pp. 63–665.

[27]H. Gfrerer:
On directional metric regularity, subregularity  and optimality conditions for nonsmooth mathematical programs.
Set-Valued and Variational Analysis 21, 2013, pp. 151–176.

[28] H. Gfrerer and J.V. Outrata:
On a semismooth* Newton method for solving generalized equations.
SIAM Journal on Optimization. 31(1), 2021, pp. 489–517.

[29]I. Ginchev and B.S. Mordukhovich:
Directional subdifferentials and optimality conditions.
Positivity 16,  2012, pp. 707–737.

[30]J.-B. Hiriart-Urruty and C. Lemaréchal:
Fundamentals of Convex Analysis.
Grundlehren Text Editions, Springer, Berlin, Heidelberg, 2001.

[31]T. Hoheisel: Topics in Convex Analysis in Matrix Space. Lecture Notes, Spring School on Variational Analysis,
Paseky nad Jizerou, Czech Republic, 2019.

[32] P.D. Khanh, B.S. Mordukhovich, and V.T. Phat:
A generalized Newton method for subgradient systems. arXiv:2009.10551, 2020.

[34] A.S. Lewis:
The convex analysis of unitarily invariant matrix functions.
Journal of Convex Analysis 2(1–2), 1995, pp. 173–183.

[35] A.S. Lewis:Convex analysis on the Hermitian Matrices.
SIAM Journal on  Optimization  6(1), 1996, pp. 164–177.

[37] J. Liu and J. Ye: Efficient Euclidean projections in linear time.
Proceedings of the 26th Annual International Conference on Machine Learning, 2009, pp. 657–664.

[39]F. Meng, D. Sun, and G. Zhao:
Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization. Mathematical Programming  104, 2005, pp. 561–581.

[40] F. Meng, G. Zhao, M. Goh, and R. De Souza:
Lagrangian-dual functions and Moreau-Yosida regularization. SIAM Journal on Optimization  19, 2008, pp. 39–61.

[41] A. Milzarek: Numerical Methods and Second Order Theory for Nonsmooth Problems. Dissertation,  Technical University of Munich,  2016.

[42] B.S. Mordukhovich:
Variational Analysis and Applications.
Springer Monographs in Mathematics book series, Springer International Publishing AG, 2018.

[43]P. Neal and S. Boyd:
Proximal algorithms.
Foundations and Trends in Optimization 1(3), 2013, pp. 123–231.

[44]J.S. Pang and L. Qi: A Globally convergent Newton method for convex SC$^1$ minimization problems.  Journal of Optimization Theory and Applications  85(3), 1995, pp. 633–648.

[45]L. Qi and  J. Sun:  A nonsmooth version of Newton's method.
Mathematical Programming 58, 1993, pp. 353–367.

[46]
R.T. Rockafellar: Convex Analysis. Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J. 1970.

[47]
R.T. Rockafellar and R.J.-B. Wets: Variational Analysis.
Grundlehren der Mathematischen Wissenschaften, Vol. 317, Springer-Verlag, Berlin, 1998.

[48]A. Shapiro:
Directionally nondifferentiable metric projection.
Journal of Optimization Theory and Applications 81(1), 1994, pp. 203–204.

[49]J. Liu, S. Ji, and J. Ye:
SLEP: Sparse Learning with Efficient Projections, <http://www.yelabs.net/software/SLEP/>
Arizona State University, 2009.

[50]  T. Strömberg:
The Operation of Infimal Convolution.
Dissertationes Mathematicae (Rozprawy Matematyczne)  352, 1996.

[51]M. Tofighi, K. Kose, and A.E. Cetin:
Denoising using projections onto the epigraph set of convex cost functions. IEEE International Conference on Image Processing (ICIP), Paris, 2014, pp. 2709–2713.

[52] M. Tofighi, A. Bozkurt, K. Kose, and A.E. Cetin:
Deconvolution using projections onto the epigraph set of a convex cost function.
22nd Signal Processing and Communications Applications Conference (SIU), 2014, pp. 1638–1641.

[53]P.-W. Wang, M. Wytock, and J.Z. Kolter:
Epigraph projections for fast general convex programming.
Proceedings of the 33rd International Conference on International Conference on Machine Learning 48, New York, 2016, pp. 2868–2877.