May 30, 2026
We study perturbation and stability properties of solution mappings associated with convex regularized least-squares problems. We first establish an implicit function theorem for generalized equations governed by maximally monotone operators and smooth perturbations, yielding conditions for local Lipschitz continuity, directional differentiability, and semismoothness of solution mappings. We then characterize the kernel of generalized Hessians of convex functions through the subspace parallel to the subdifferential under \(\mathcal{C}^2\)-cone reducibility assumptions on the conjugate of the regularizer, thereby replacing difficult second-order objects by tractable first-order conditions. As applications, we derive stability results for broad classes of regularized least-squares problems, including weighted polyhedral support-function regularizers and piecewise linear-quadratic penalties. Our framework unifies and extends several recent results on Lipschitz stability for LASSO-type models and monotone generalized equations.
Sensitivity or stability analysis constitutes a central theme in optimization theory. Broadly speaking, one seeks to understand how solutions of optimization problems and generalized equations vary under perturbations of the underlying data. Classical developments in this direction were driven largely by smooth nonlinear programming and variational inequalities, beginning with the foundational works of Robinson Rob?, 80?, Rob?, 84?, Rob?, 87? and Kojima Koj?, 80?. We refer the reader to the standard reference by Bonnans and Shapiro BS?, 00? for a very comprehensive account of the state-of-the art (even in infinite dimensions) up to the early 2000s. Over the last two decades, however, the rapid emergence of modern applications in machine learning, statistics, imaging, compressed sensing, and signal processing has shifted attention toward nonsmooth and structured optimization models involving, e.g., sparsity-promoting or low-complexity regularizers. Such problems often exhibit rich variational structure while simultaneously lacking smoothness or even polyhedrality. Among the most prominent examples are sparse (or low-rank) recovery problems such as the LASSO SaS?, 86?, T?, 96?, group LASSO MiL?, 06?, square-root LASSO BCW?, 11?, BCW?, 14?, and nuclear norm minimization CaR?, 09?, Faz?, 02?, RFP?, 10?. The vast majority of these problems are of the form
\[\begin{align} \label{eq:generalLeastSquares} \min_{x \in \mathbb{R}^n} \frac{1}{2}\|Ax-b\|^2 + \lambda r(x) \end{align}\tag{1}\] where \(\frac{1}{2}\|\cdot\|^2\) denotes the Euclidean norm squared, \(A \in \mathbb{R}^{m \times n}\) is a linear (forward) operator, \(b \in \mathbb{R}^m\) is a measurement vector, \(\lambda > 0\) is a regularization parameter, and \(r : \mathbb{R}^n \to \overline{\mathbb{R}}\) is a closed, proper, convex regularizer that promotes structure on the solution.
Remark 1. Without much further effort, we could consider the (seemingly) more general problem where \(\frac{1}{2}\|\cdot\|^2\) is replaced by any convex and (locally) \(\mathcal{C}^2\)-smooth fidelity term. This, however, just increases notational burden, and the focus of this paper is on different classes of regularizers.
The overarching goal of this paper is to contribute to the study of the variational-analytic properties of the solution map of 1 , i.e., the map \[\begin{align} \label{eq:S} S(A,b,\lambda):= \underset{x \in \mathbb{R}^n}{\operatorname{argmin}}\; \frac{1}{2}\|Ax-b\|^2 + \lambda r(x). \end{align}\tag{2}\] Like the majority of results on solution maps to parametric optimization problems, in particular the ones pointed out in 1.2 below, we approach the study of \(S\) via the fact that \(S\) can be equivalently written using the optimality conditions for 1 , i.e., \[\begin{align} \label{eq:S2} S(A,b,\lambda)= \left\{x\in \mathbb{R}^n\,\left\vert\; 0\in \frac{1}{\lambda}A^T(Ax-b)+\partial r(x)\right.\right\}. \end{align}\tag{3}\] Our study is now divided into three steps:
I) We first provide a general implicit function theorem (4) for solution maps \[S(p)=\left\{x\,\left\vert\; 0\in f(p,x)+F(x)\right.\right\}\] defined by a generalized equation governed by maximally monotone and set-valued part \(F\) and a smooth part \(f\) that is monotone in \(x\). This, obviously, covers the generalized equation for \(S\) in 3 . This implicit function theorem provides sufficient conditions for local Lipschtiz continuity and directional differentiability of \(S\) as well semismoothness*, a more recent property coined by Gfrerer and Outrata GfO?, 21?, intimately connected to the more traditional notion of semismoothness popularized by Qi and Sun in their seminal paper QS?, 93?. The obligatory regularity condition for an implicit function theorem in our case is simply the celebrated Mordukhovich criterion Mor?, 84?, Mor?, 92?, RoW?, 98? for metric regularity of the set-valued map \(x\mapsto f(\bar p,x)+F(x)\) around the parameter \(\bar p\) in question. This criterion here reads \[\label{eq:KernelCQ1Intro} \ker D_xf(\bar p,\bar x) \;\cap\; \ker D^*F(\bar x|-f(\bar p,\bar x))=\{0\},\tag{4}\] where \(D^*\) is the coderivative operator (see 2 for details) applied to the set-valued map \(F\).
II) When applied to 3 , the Mordukhovich criterion 4 simplifies to \[\label{eq:MordDataIntro} \ker A \cap \ker \partial^2 r(\bar{x} | -f(\bar{p}, \bar{x})) = \{0\},\tag{5}\] where \(\partial^2 r:=D^*(\partial r)\) is the generalized Hessian operator (see 2 for details) of the convex regularizer \(r\). Since this object involves a coderivative operator (applied to a subdifferential operator) it is, in general, arduous to compute. Therefore, as a second main contribution, we show in 4 that for (closed, proper, convex) functions whose (Fenchel) conjugate is \(\mathcal{C}^2\)-cone reducible the kernel of the generalized Hessian can be expressed via the subspace parallel to the subdifferential - an object which is much more expedient to compute.
III) As a third main contribution, we prove stability results for the solution map 2 for various choices of \(r\):
We establish semismoothness (in particular local Lipschitz continuity and directional differentiability) for the case when \(r^*\) is \(\mathcal{C}^2\)-cone reducible (5).
We prove explicit Lipschitz bounds and expressions for the directional derivative for the case where \(r\) is the composition of a polyedral support function and a linear map (2).
We discuss the case where \(r\) is a piecewise linear-quadratic (PLQ) without appealing to \(\mathcal{C}^2\)-cone reducibility (7), and prove quantitative results in the special case where \(r\) is a PLQ penalty in the sense of RoW?, 98? (3).
The related work recently published decomposes into roughly three camps based on what variational-analytical tools are being employed. One line of research, to which this paper belongs, employs and refines tools from variational analysis à la Mordukhovich Mor?, 06?, Mor?, 18?, Rockafellar and Wets RoW?, 98? and Dontchev and Rockafellar DoR?, 14? based on graphical differentiation. Representative contributions include the work of Berk et al. BBH?, 22?, BBH?, 24? for LASSO and Square-root LASSO, where results on Lipschitzness and directional differentiability are obtained through second-order variational analysis in a particular instance of this paper here. Other work on LASSO-type problems exploits the explicit polyhedral structure of \(\ell_1\)-type regularization problems HYZ?, 24?, MWY?, 25?. More recently, Cui et. al CHNS?, 26? established a new perspective based on Robinson’s strong regularity of suitably constructed dual problems and the geometry of \(\mathcal{C}^2\)-cone reducible conjugates. Their framework yielded elegant first-order characterizations for Lipschitz stability, tilt stability, and full stability of broad classes of convex regularized least-squares problems while bypassing explicit second-order calculations on the nonsmooth regularizer itself. A central feature of this approach is that the relevant generalized second-order conditions arise automatically from the structure of the dual problem and the geometry of the epigraph of the conjugate regularizer. Our work here adds to that by also providing quantitative results, and by using an implicit function theorem for the the primal problem rather than looking at strong regularity of the dual.
Another, rather different approach was developed by Bolte et al. BLPS?, 21?, BPS?, 24? who studied differentiability properties of solution mappings to monotone inclusion problems (thus including optimality condtions of convex problems) through the lens of path differentiability and conservative Jacobian calculus.
Finally, stability analysis for linear least-squares problems in the form of 1 based on partial smoothness can be found in the body of work by Vaiter et al., e.g., VDF?, 15?, VDF?, 17?.
The paper is organized as follows: In 2 we provide the necessary background material from convex and variational analysis as well as some elementary linear-algebraic facts useful to our study. 3 contains the advertized implicit function theorem (4) along with its technical prerequisites, including the notion of semismoothness*. In turn, 4 is devoted to the study of the kernel of the generalized Hessian of a convex function \(g\), culminating in its characterization via the subspace parallel to the subdifferential in the case where its conjugate \(g^*\) is \(\mathcal{C}^2\)-cone reducible (4). Finally, the stability results for the solution map 2 for different instances of the regularizer \(r\) can be found in 5. We close with final remarks in 6.
Notation: We use \(\overline{\mathbb{R}}:=\mathbb{R}\cup\{\pm\infty\}\) to denote the extended real numbers. \(\mathbb{R}_{++}\) denotes the set of positive real numbers, and similarly, \(\mathbb{R}_{+}\) denotes the set of nonnegative real numbers and \(\mathbb{R}_{-}\) denotes the set of nonpositive real numbers. \(\mathbb{B}_{\varepsilon}(\bar{x})\) denotes the closed ball of radius \(\varepsilon\) centered at \(\bar{x}\), and we set \(\mathbb{B}:=\mathbb{B}_1(0)\). The distance from a point \(x \in \mathbb{R}^d\) to a set \(C \subseteq \mathbb{R}^d\) is denoted \(d(x, C)\). All these are measured in the Euclidean norm \(\|\cdot\|\) on \(\mathbb{R}^d\). For a function \(f : \mathbb{R}^d \to \mathbb{R}\), at a point \(\bar{x}\) at which \(f\) is differentiable, \(\nabla f(\bar{x}) \in \mathbb{R}^d\) is the gradient of \(f\). If \(f : \mathbb{R}^d \to \mathbb{R}\) is twice differentiable at \(\bar{x}\), then we denote the Hessian at that point by \(\nabla^2 f(\bar{x})\). If \(f : \mathbb{R}^n \to \mathbb{R}^m\) is differentiable at \(\bar{x}\), then we denote its Jacobian at \(\bar{x}\) by \(Df(\bar{x})\). For a subset \(S\) of a real vector space, we denote the conical and linear hulls of \(S\) by \(\mathrm{cone}\,S\) and \(\mathrm{span}\,S\), respectively. The subspace parallel to a convex set \(C\) is defined as \(\mathrm{span}\,(C - x)\), for any \(x \in C\), and is denoted \(\mathrm{par}\,C\). The (topological) closure of \(C\) is denoted by \({\rm cl\;}C\). The kernel and range of a matrix \(A\) are denoted by \(\ker A\) and \(\operatorname{rge}A\), respectively. \(\mathbb{S}^n_{+}\) denotes the set of \(n \times n\) symmetric positive semidefinite matrices. The smallest and largest singular values of \(A\) are denoted \(\sigma_{\min}(A)\) and \(\sigma_{\max}(A)\), respectively. For \(A \in \mathbb{R}^{n \times n}\) symmetric, we use \(\lambda_{\min}(A)\) and \(\lambda_{\max}(A)\) to refer to the smallest and largest eigenvalues of \(A\), respectively.
Throughout we transition seamlessly between the notation \(\left\langle x,\, y\right\rangle\) and \(x^Ty\) for the standard inner product between \(x,y\in \mathbb{R}^d\), depending on what is more expedient in the respective situation.
We present here some necessary concepts and results from variational analysis which are needed for our study and which, in large parts, come from the standard references DoR?, 14?, RoW?, 98?. The initiated reader may skip this section and come back to it only when needed.
For a function \(f : \mathbb{R}^d \to \overline{\mathbb{R}}\), its epigraph is the set \(\mathrm{epi}\;f:=\left\{(x,\alpha)\in \mathbb{R}^{d+1}\,\left\vert\; f(x)\leq \alpha\right.\right\}\). Its domain is \(\mathrm{dom}\;f:=\left\{x\in \mathbb{R}^d\,\left\vert\; f(x) < \infty\right.\right\}\). We call \(f\) proper if \(\mathrm{dom}\;f\neq \emptyset\) and \(f>-\infty\). We say that \(f\) is closed if \(\mathrm{epi}\;f\) is closed, and convex if \(\mathrm{epi}\;f\) is convex.
The (convex) subdifferential of \(f: \mathbb{R}^d \to \overline{\mathbb{R}}\) at \(\bar{x}\) is \[\begin{align} \partial f (\bar{x}) := \{v \in \mathbb{R}^d \;| \;f(\bar{x})+\langle v, x - \bar{x}\rangle \le f(x), \; \forall x \in \mathbb{R}^d \}. \end{align}\] The (Fenchel) conjugate of \(f\) is the function \(f^* : \mathbb{R}^d \to \overline{\mathbb{R}}\) defined by \[f^*(y) := \sup_{x \in \mathbb{R}^d} \{\langle x, y \rangle - f(x)\}.\] As a special case of conjugacy, we note that for any (nonempty) set \(C\subseteq\mathbb{R}^d\), its indicator (function) \(\delta_C:\mathbb{R}^d\to\overline{\mathbb{R}}\) defined by \[\delta_C(x):=\begin{cases}0, & x\in C,\\ +\infty,& x\notin C \end{cases}\] has the conjugate \[\sigma_C(y):=\delta_C^*(y)=\sup_{x\in C} \left\langle y,\, x\right\rangle,\] which we call the support function of \(C\). In turn, if \(C\) is closed and convex we have also that \(\sigma_C^*=\delta_C\). We call a proper function \(f\) polyhedral convex (or convex piecewise linear) if \(\mathrm{epi}\;f\) is polyhedral convex, i.e., the interection of finitely many half space. This is equivalent to \(f\) having the form \[f(x)=\max_{i=1,\dots,r}\{a_i^Tx+\beta_i\}+\delta_\mathcal{P}(x)\] for some (nonempty) polyhedron \(\mathcal{P}\subseteq\mathbb{R}^d\) and \((a_i,\beta_i)\in \mathbb{R}^d\times \mathbb{R}\;(i=1,\dots,r)\). In particular, compositions of polyhedral convex functions with affine maps are polyhedral convex. We point out that RoW?, 98? \(f\) is polyhedral convex if and only if \(f^*\) is. In particular, \(\sigma_C\) is polyhedral convex if and only if \(C\) is polyhedral.
It is known RoW?, 98? that \(f\) is closed, proper, convex if and only if \(f=f^{**}(:=(f^*)^*)\) in which case we have the important relation RoW?, 98? \[\label{eq:SDInversion} \partial f^* = (\partial f)^{-1},\tag{6}\] where this inversion has to be understood in the set-valued sense, to which we allude now.
For a set-valued map \(S : \mathbb{R}^{n} \rightrightarrows \mathbb{R}^{m}\), we define \(S^{-1}:\mathbb{R}^m\rightrightarrows \mathbb{R}^n\) via \[S^{-1}(y):=\left\{x\in \mathbb{R}^n\,\left\vert\; y\in S(x)\right.\right\}.\] In particular, \((S^{-1})^{-1}=S\). The graph of \(S\) is the set \(\operatorname{gph}S := \{(x, y) \in \mathbb{R}^{n} \times \mathbb{R}^{m} \;| \;y \in S(x)\}\). The kernel of \(S\) is \(\ker S := S^{-1}(0)\).
The outer limit of a set-valued map \(S : \mathbb{R}^{n} \rightrightarrows \mathbb{R}^{m}\) at \(\bar{x}\) is defined as \[\underset{x \to \bar{x}}{\operatorname{Lim \, sup}} \;S(x) := \{y \in \mathbb{R}^{m} \;| \;\exists \{x^k\} \to \bar{x}, \;\{y^k \in S(x^k)\} \to y \}.\] For \(\Omega \subseteq \mathbb{R}^d\) and \(\bar{x} \in \Omega\), we define the tangent cone to \(\Omega\) at \(\bar{x}\) as \[\begin{align} T_\Omega(\bar{x}) = \underset{t \downarrow 0}{\operatorname{Lim \, sup}} \frac{\Omega - \bar{x}}{t}. \end{align}\] When \(\Omega\) is convex, by RoW?, 98?, we can write \(T_\Omega(\bar{x})\) as \[\begin{align} T_\Omega(\bar x) = \mathrm{cl} \left \{ w \, \big| \, \exists \lambda > 0 \text{ such that }\bar x + \lambda w \in \Omega \right\}. \end{align}\] We define the regular normal cone to \(\Omega\) at \(\bar{x}\) as \[\begin{align} \hat{N}_\Omega(\bar{x}) = \{v \in \mathbb{R}^d \;| \;\langle v, x - \bar{x}\rangle \le o(\lVert x - \bar{x}\rVert), \;\forall x \in \Omega\} \end{align}\] and the (limiting) normal cone to \(\Omega\) at \(\bar{x}\) as \[N_\Omega(\bar x) = \underset{x \to \bar{x}}{\operatorname{Lim \, sup}} \;\hat{N}_\Omega(x).\] At a point \((\bar{x}, \bar{y}) \in \operatorname{gph}S\), the graphical derivative is defined as the set-valued map \(DS(\bar{x}|\bar{y}) : \mathbb{R}^{n} \rightrightarrows \mathbb{R}^{m}\) defined by \[\begin{align} DS(\bar{x}|\bar{y})(w) := \{z \;| \;(w, z) \in T_{\operatorname{gph}S}(\bar{x}, \bar{y})\}, \end{align}\] and the coderivative is the set-valued map \(D^*S(\bar{x}|\bar{y}) : \mathbb{R}^{m} \rightrightarrows \mathbb{R}^{n}\) defined by \[\begin{align} D^*S(\bar{x}|\bar{y})(u) := \{v \;| \;(v, -u) \in N_{\operatorname{gph}S}(\bar{x}, \bar{y})\}. \end{align}\] A simple observation that follows from the definition is the following.
Lemma 1. Let \(F:\mathbb{R}^n\to \mathbb{R}^m\), and let \(G:\mathbb{R}^d\times \mathbb{R}^n\to \mathbb{R}^m\) be defined by \(G(p,x)=F(x)\). Then, for \((\bar p,\bar x, \bar z)\in \operatorname{gph}G\), we have \[D^*G(\bar p, \bar x|\bar z)(y)= \{0\}\times D^*F(\bar x|\bar z)(y).\]
The following is a sum rule for the graphical derivative and coderivative, respectively, in the presence of continuous differentiability.
Lemma 2 (RoW?, 98?). Let \(S=f+F\) for \(f: \mathbb{R}^{n} \to \mathbb{R}^{m}\) and \(F: \mathbb{R}^{n} \rightrightarrows \mathbb{R}^{m}\). Let \((\bar x,\bar u)\in \operatorname{gph}S\) and assume that \(f\) is continuously differentiable at \(\bar x\). Then:
\(DS(\bar x|\bar u)(w)=Df(\bar x)w+DF(\bar x|\bar u-f(\bar x))(w),\quad \forall w\in \mathbb{R}^{n}\);
\(D^*S(\bar x|\bar u)(y)=Df(\bar x)^*y+D^*F(\bar x|\bar u-f(\bar x))(y),\quad \forall y\in \mathbb{R}^{m}\).
For a convex function \(g\), at a point \((\bar{x}, \bar{v}) \in \operatorname{gph} \partial g\), we refer to the coderivative of \(\partial g\) at such a point as the generalized Hessian and denote it as follows: \[\textcolor{purple}{} \partial^2 g(\bar{x} | \bar{v})(\cdot) := D^* \partial g(\bar{x} | \bar{v})(\cdot).\] For \(f : \mathbb{R}^d \to \overline{\mathbb{R}}\) and a point \(\bar{x}\in \mathbb{R}^d\) at which \(f\) is finite, let us define the quotient \[\Delta^2_tf(\bar x|\bar v)(w):=\dfrac{f(x+tw)-f(x)-t\langle\bar v,w\rangle}{\frac{1}{2}t^2}\quad for\quad t>0.\] The second subderivative of \(f\) at \(\bar x\) for \(\bar v\) is defined by \[d^2 f(\bar x|\,\bar v)(w)=\liminf\limits_{ \begin{subarray}\quad \,\;\tau\downarrow 0\\ w'\rightarrow w\end{subarray}}\Delta^2_\tau f(\bar x|\bar v)(w').\] The function \(f\) is said to be twice epi-differentiable RoW?, 98? at \(\bar x\in \mathbb{R}^d\) for \(\bar v\) if the functions \(\Delta^2_tf(\bar x|\bar v)\) epi-converge to \(d^2f(\bar x|\, \bar v)\) as \(t\downarrow 0\) in the sense that for every \(w\in \mathbb{R}^d\) and any choice of sequence \(t_k\downarrow 0\) there exist \(w_k\to w\) such that \[\lim_{k\to \infty}\frac{f(\bar x+t_k w_k)-f(\bar x)-t_k \langle \bar v, w_k\rangle}{ \frac{1}{2}t_k^2}= d^2f(\bar x|\, \bar v)(w).\] The function \(f\) is twice epi-differentiable at \(\bar x\), if it is twice epi-differentiable at \(\bar x\) for any \(v\in \partial f(\bar x)\); see MS?, 20? for recent developments for twice epi-differentiable functions.
The map \(F : \mathbb{R}^n \rightrightarrows \mathbb{R}^m\) is said to be proto-differentiable at \(\bar x \in \mathbb{R}^n\) if there exists \(\bar u \in F(\bar{x})\) such that \[\begin{align} \frac{\operatorname{gph}F - (\bar x, \bar u)}{\tau} \overset{\tau \downarrow 0}{\to} \operatorname{gph}DF(\bar x | \bar u), \end{align}\] where the convergence of sets is in the sense of RoW?, 98?.
A set-valued map \(Q : \mathbb{R}^{n} \rightrightarrows \mathbb{R}^{m}\) is called metrically regular at a point \((\bar{x}, \bar{y}) \in \operatorname{gph}Q\) if there exists a neighborhood \(V\) of \(\bar{x}\), a neighborhood \(W\) of \(\bar{y}\), and \(\kappa \ge 0\) such that \[\begin{align} d(x, Q^{-1}(y)) \le \kappa d(y, Q(x)), \;\forall x \in V, y \in W. \end{align}\] For \(S : \mathbb{R}^n \rightrightarrows \mathbb{R}^m\) and \((\bar{x}, \bar y) \in \operatorname{gph}S\), then we say \(S\) has a localization at \(\bar{x}\) for \(\bar y\) if there are neighborhoods \(V\) of \(\bar{x}\) and \(W\) of \(\bar y\) such that \(x \in V \mapsto S(x) \cap W\) is single-valued. We say \(S\) has a Lipschitz continuous localization at \(\bar x\) for \(\bar y\) if this localization is Lipschitz continuous.
\(Q : \mathbb{R}^n \rightrightarrows \mathbb{R}^m\) is called strongly metrically regular at \((\bar{x}, \bar{y}) \in \operatorname{gph}Q\) if \(Q^{-1}\) has a Lipschitz continuous localization around \(\bar{y}\) for \(\bar{x}\).
Lemma 3 (Single-valuedness of localization from convex-valuedness). Let \(S : \mathbb{R}^n \rightrightarrows \mathbb{R}^m\) be convex-valued 1, let \((\bar x, \bar y) \in \operatorname{gph}S\), and suppose \(S\) has a Lipschitz continuous localization at \(\bar x\) for \(\bar y\). Then, \(S\) is locally (single-valued and) Lipschitz continuous at \(\bar x\).
Proof. Let \(V\) be the associated neighborhood of \(\bar{x}\), and \(W\) be the associated neighborhood of \(\bar y\) such that \(x \in V \mapsto S(x) \cap W\) is single-valued. Without loss of generality (by shrinking \(V\) is necessary), we may assume \(S\) is convex-valued on \(V\). Fix \(x \in V\) and let \(y \in S(x)\). Let \(s : V \to W\) be a localization of \(S\) which is Lipschitz continuous. By convexity of \(S(x)\), for all \(\lambda \in (0, 1)\), we have \(s(x) + \lambda(y - s(x)) \in S(x)\). For \(\lambda\) sufficiently small, \(s(x) + \lambda(y - s(x)) \in S(x) \cap W = \{s(x)\}\), so \(s(x) + \lambda(y - s(x)) = s(x) \implies s(x) = y\). Therefore, \(S(x) = \{s(x)\}\) for \(x \in V\), which establishes that \(S\) is in fact locally single-valued and Lipschitz continuous at \(\bar x\). ◻
A set-valued map \(Q : \mathbb{R}^d \rightrightarrows \mathbb{R}^d\) is called monotone if \[\begin{align} \langle v_1 - v_0, x_1 - x_0 \rangle \ge 0, \;\forall v_0 \in Q(x_0), \;v_1 \in Q(x_1), \end{align}\] and is called maximally monotone if no enlargement of its graph is possible in \(\mathbb{R}^d \times \mathbb{R}^d\) without destroying monotonicity.
The following result from DoR?, 14? will be one of the central tools we use to develop the implicit function theorem.
Proposition 2. If \(Q : \mathbb{R}^d \rightrightarrows \mathbb{R}^d\) is monotone and metrically regular at \((\bar{x}, \bar y) \in \operatorname{gph}S\), then in fact \(Q\) is strongly metrically regular at \((\bar{x}, \bar y).\)
Multiple times in this paper, we will employ (explicitly or implicitly) the following result, which is now known as the Mordukhovich criterion, see, e.g., RoW?, 98?.
Theorem 1 (Mordukhovich criterion). Let \(Q : \mathbb{R}^n \rightrightarrows \mathbb{R}^m\) with \((\bar{x}, \bar y) \in \operatorname{gph}Q\) and suppose \(\operatorname{gph}Q\) is closed. Then, \(Q\) is metrically regular at \((\bar{x}, \bar y)\) if and only if \[\begin{align} \ker D^*Q(\bar{x} | \bar{y}) = \{0\}, \end{align}\] or, equivalently, if \[\begin{align} 0 \in D^*Q(\bar{x}| \bar y)(w) \implies w = 0. \end{align}\]
We present here some auxiliary results from linear algebra which are useful to our study.
The first two lemma are more generally relevant and certainly known, but we provide proofs for completeness.
Lemma 4. Let \(M\in \mathbb{R}^{l\times n}\), \(U,V\subseteq\mathbb{R}^l\) subspaces. Then:
\(M^{-1}(V^\perp)=(M^T(V))^\perp\);
\(\left(M^{-1}(U)\right)^\perp=M^T(U^\perp)\).
Proof. (a) We have \[\begin{align} M^{-1}(V^\perp) & =& \left\{x\,\left\vert\; Mx\in V^\perp\right.\right\}\\ & = & \left\{x\,\left\vert\; \left\langle x,\, M^Tv\right\rangle=0\; , \, \forall v\in V\right.\right\}\\ & = & \left\{x\,\left\vert\; \left\langle x,\, s\right\rangle=0\;, \, \forall s\in M^T(V)\right.\right\}\\ & = & (M^T(V))^\perp. \end{align}\] (b) We have \[\begin{align} (M^{-1}(U))^\perp & = & (M^{-1}\left((U^\perp)^\perp\right))^\perp\\ &\overset{(a)}{=} & \left(\left(M^T(U^\perp)\right)^\perp\right)^\perp\\ & = & M^T(U^\perp). \end{align}\] ◻
Lemma 5. Let \(C, D \in \mathbb{R}^{n \times n}\) be symmetric positive semidefinite matrices. Then, \(I + CD\) is invertible.
Proof. Take \(v \in \ker (I + CD)\), i.e., \(v + CDv = 0\). Left-multiplying this expression by \((Dv)^T\), we get \[\begin{align} v^TDv + v^TDCDv = 0. \end{align}\] By positive semidefiniteness of \(C\) and \(D\), both \(v^TDv=0\) and \(v^TDCDv=0\). However, \(v^TDv = 0\) implies that \(Dv=0\), thus \(0=v + CDv = v\), so we have \(v = 0\). This proves the statement. ◻
The last lemma is more tailored to our specific needs and will come into play in our quantitative analysis of the solution maps in 3.
Lemma 6. Let \(C \in \mathbb{R}^{n \times n}\) be symmetric positive semidefinite, \(A \in \mathbb{R}^{m \times n}\), \(E \subseteq \mathbb{R}^n\) be a subspace such that \(\ker A \cap E = \{0\}\). Let \(H := I + CA^TA\) and let \(U\) have columns \(\begin{bmatrix} u_1 \cdots u_r \end{bmatrix}\) which form an orthonormal basis of \(H^{-1}(E)\). Then the following hold:
\(\ker AHU = \{0\}\);
\(H(\ker A) \subseteq \ker A\);
\(\ker AU = \{0\}\);
\((AHU)^T AU\) is symmetric positive definite.
Proof. (a) \(\ker A \cap E = \{0\}\) gives us that \(H^{-1} (\ker A) \cap H^{-1}(E) = \ker H=\{0\}\), where the latter uses 5. Observe that \(H^{-1}(\ker A)=\ker AH\), and that \(\operatorname{rge}U =H^{-1}(E)\) by construction. Thus, \(\ker AH \cap \operatorname{rge}U = \{0\}\), which implies \(\ker AHU = \{0\}\).
(b) Let \(y \in \ker A\). Then, \(Hy = y + C A^TAy\), but \(Ay = 0\), so \(Hy = y\). Thus, \(Hy \in \ker A\), which tells us \(H(\ker A) \subseteq \ker A\).
(c) Let \(y \in \ker AU\). Then, \(Uy \in \ker A\), so by (c), \(HUy \in \ker A\). This gives us \(y \in \ker AHU\), hence \(y=0\) by (a). Thus, \(\ker AU = \{0\}\).
(d) Note that \[\begin{align} (AHU)^T (AU) = U^T \left(I + A^TA C\right) A^TAU = (AU)^T(AU) + (AU)^TC(AU). \end{align}\] Thus, \((AHU)^T (AU)\) is symmetric and by (c), \((AU)^T(AU)\) is positive definite which then gives the desired statement. ◻
In this section we present an implicit function theorem for monotone (set-valued) maps that will be a main tool for establishing the (variational-)analytic properties (such as directional differentiability, local Lipschitzness) of the solution maps in which we are interested. To this end, we need to extend our variational analysis toolkit by a notion of semismoothness for set-valued maps which was popularized by Gfrerer and Outrata GfO?, 21?.
Definition 1 (Semismoothness*). The set \(A\subseteq \mathbb{R}^d\) is semismooth** at \(\bar x\in A\) if \[\left\langle x^*,\, u\right\rangle=0\quad \forall u\in \textcolor{purple}{\mathbb{R}^d},\; x^*\in N_A(\bar x;u)\] where \(N_A(\bar{x}; u)\) is the directional normal cone to \(A\) at \(\bar{x}\) in direction \(u\) (see GfO?, 21? for definition.) The map \(S:\mathbb{R}^{n} \rightrightarrows \mathbb{R}^{m}\) is semismooth* at \((\bar x,\bar y)\in \operatorname{gph}S\) if \(\operatorname{gph}S\) is semismooth* at \((\bar x,\bar y)\), i.e., \[\left\langle u,\, u^*\right\rangle=\left\langle v,\, v^*\right\rangle\quad \forall (u,v)\in \mathbb{R}^{n} \times \mathbb{R}^{m},\; (v^*,u^*)\in\operatorname{gph}D^*S((\bar x,\bar u); (u,v))\] where \(D^*S((\bar{x}, \bar u) ; (u, v))\) is the directional coderivative (also in GfO?, 21?.)*
Recall also the classical notion of semismoothness, initally introduced by Mifflin in Mif?, 77?, and later generalized to the vector-valued case by Qi and Sun QS?, 93?.
Definition 2 (Semismoothness). A function \(F : \mathbb{R}^{n} \to \mathbb{R}^{m}\) is called semismooth* at \(\bar{x}\) if \(F\) is locally Lipschitz at \(\bar{x}\), and for any \(h \in \mathbb{R}^{n}\), the following limit exists: \[\begin{align} \lim_{ \substack{V \in \partial_CF(x + t h') \\ h' \to h, \;t \downarrow 0 }} Vh' \end{align}\] where \(\partial_C F\) is Clarke’s generalized Jacobian operator 2 Cla?, 83?.*
The significance of semismoothness* for our study is highlighted by the following result from GfO?, 21?, which illustrates the intimate connection between the notions of semismoothness and semismoothness*.
Lemma 7 (Semismooth vs. semismooth*). Let \(F:D\subseteq \mathbb{R}^{n} \to \mathbb{R}^{m}\) be locally Lipschitz at \(x\in\mathrm{int}\,D\). Then the following are equivalent:
\(F\) is semismooth at \(x\);
\(F\) is semismooth* and directionally differentiable at \(x\).
We emphasize that, in particular, a semismooth function is always locally Lipschitz (by definition) and directionally differentiable.
Recall the following result from FGH?, 22? which is a preimage rule for semismooth* sets.
Proposition 3 (Metric regularity and semismoothness*). Let \(H: \mathbb{R}^{n} \to \mathbb{R}^{m}\) be continuously differentiable at \(\bar z\), let \(Q\subseteq\mathbb{R}^{m}\) be semismooth* (as a set) at \(H(\bar z)\) and let \(\Psi: \mathbb{R}^{n} \rightrightarrows \mathbb{R}^{m},\; \Psi(z):=H(z)-Q\) be metrically (sub)regular at \((\bar z,0)\). Then \(H^{-1}(Q)\) is semismooth* at \(\bar z\) (as a set).
As a consequence we obtain a result about semismoothness* of implicit functions.
Corollary 1. Let \(f: \mathbb{R}^m \times \mathbb{R}^n \to \mathbb{R}^n\) be continuously differentiable at \((\bar p,\bar x)\), and let \(F:\mathbb{R}^n \rightrightarrows \mathbb{R}^n\) be semismooth* at \((\bar x,-f(\bar p,\bar x))\) (in particular, \(0\in f(\bar p,\bar x)+ F(\bar x)\)). Define \(S:\mathbb{R}^m \rightrightarrows \mathbb{R}^n\) via \[S(p)=\left\{x\in \mathbb{R}^n\,\left\vert\; 0\in f(p,x)+F(x)\right.\right\}.\] Then \(S\) is semismooth* at \((\bar p,\bar x)\) provided that the set-valued mapping \(\Psi:\mathbb{R}^m\times \mathbb{R}^n \rightrightarrows \mathbb{R}^n \times \mathbb{R}^n\) defined by \(\Psi(p,x)=(x,-f(p,x))-\operatorname{gph}F\) is metrically regular at \((\bar p,\bar x,0)\) 3. This is equivalent to the following implication being satisfied: \[\label{eq:MordSemi} \left.\begin{array}{rcl} -(v,w)&\in &N_{\operatorname{gph}F}(\bar x,-f(\bar p,\bar x)),\\ 0 & = & D_pf(\bar p,\bar x)^*w,\\ v & = & D_xf(\bar p,\bar x)^*w \end{array}\right\} \quad \Longrightarrow\quad (v,w)=(0,0).\qquad{(1)}\]
Proof. Define the function \(H:\mathbb{R}^m \times \mathbb{R}^n \to \mathbb{R}^n \times \mathbb{R}^n,\; H(p,x)=(x,-f(p,x))\), which is continuously differentiable at \((\bar p,\bar x)\). We note that \[\begin{align} (p,x)\in \operatorname{gph}S & \Longleftrightarrow & (x,-f(p,x)) \in \operatorname{gph}F\\ & \Longleftrightarrow & (p,x) \in H^{-1}(\operatorname{gph}F), \end{align}\] i.e. \(\operatorname{gph}S=H^{-1}(\operatorname{gph}F)\). Since \(F\) is assumed semismooth* at \((\bar x,-f(\bar p,\bar x))\), by definition, \(\operatorname{gph}F\) is semismooth* (as a set) at \((\bar p,\bar x)\). Consequently, 3 (with \(Q=\operatorname{gph}F\)) yields that \(\operatorname{gph}S=H^{-1}(\operatorname{gph}F)\) is semismooth* at \((\bar p,\bar x,0)\) if \(\Psi\) is metrically subregular at \((\bar p,\bar x,0)\).
To prove the remainder, recall that, by the Mordukhovich criterion (1), \(\Psi\) is metrically regular at \((\bar p,\bar x,0)\) if and only if the following implication holds: \[0\in D^*\Psi(\bar p,\bar x|0)(v,w) \quad \Longrightarrow \quad (v,w)=(0,0).\] Now, observe that, by the coderivative sum rule 2, we have \[\begin{align} D^*\Psi(\bar p,\bar x|0)(v,w) & = & DH(\bar p,\bar x)^*(v,w)+\begin{cases} \{0\}\times \{0\}, &-(v,w) \in N_{\operatorname{gph}F}(H(\bar p,\bar x)),\\ \emptyset, & \text{else}.\end{cases} \end{align}\] Since \(DH(\bar p,\bar x)^*(v,w)=[-D_pf(\bar p,\bar x)^*w, \; v-D_xf(\bar p,\bar x)^*w]\), we find that \(0\in D^*\Psi(\bar p,\bar x|0)(v,w)\) holds if and only if
\[\begin{array}{rcl} -(v,w)&\in &N_{\operatorname{gph}F}(\bar x,-f(\bar p,\bar x)),\\ 0 & = & D_pf(\bar p,\bar x)^*w,\\ v & = & D_xf(\bar p,\bar x)^*w. \end{array}\] This concludes the proof. ◻
We now present the advertized implicit function theorem which constitutes a polished and substantially amended version of BBH?, 22?.
Proposition 4. Let \((\bar p,\bar x)\in \mathbb{R}^d\times \mathbb{R}^n\), let \(F:\mathbb{\mathbb{R}}^n\rightrightarrows \mathbb{R}^n\) be maximally monotone, and let \(f:\mathbb{R}^d\times \mathbb{R}^n\to \mathbb{R}^n\) be continuously differentiable at \((\bar p, \bar x)\) such that \(f(p,\cdot)\) is monotone for any \(p\) near \(\bar p\). Define \(S:\mathbb{R}^d\rightrightarrows\mathbb{R}^n\) by \[S(p)=\left\{x\in \mathbb{R}^n\,\left\vert\; 0\in f(p,x)+F(x)\right.\right\}, \quad \forall p \in \mathbb{R}^d.\] Assume that \((\bar p,\bar x)\in \operatorname{gph}S\) (i.e., \(0\in f(\bar p,\bar x)+F(\bar x)\)) such that \[\label{eq:MordCrit} 0\in D_x f(\bar p,\bar x)^*w+D^*F(\bar x\mid -f(\bar p,\bar x))(w)\quad\Longrightarrow \quad w=0,\qquad{(2)}\] or, equivalently, \[\label{eq:KernelCQ} \ker D_xf(\bar p,\bar x) \cap \ker D^*F(\bar x|-f(\bar p,\bar x))=\{0\}.\qquad{(3)}\] Then the following hold:
\(Q:=f(\bar p,\cdot)+F:\mathbb{R}^n\rightrightarrows \mathbb{R}^n\) is strongly metrically regular* at \((\bar x,0) \in \operatorname{gph}Q\) (and maximally monotone).*
\(S\) is (single-valued) locally Lipschitz at \(\bar p\).
If \(F\) is proto-differentiable* at \((\bar x, -f(\bar p,\bar x))\), then the graphical derivative \(DS(\bar p|\bar x)\) is single-valued and locally Lipschitz with \[\label{eq:graphical95derivative} DS(\bar p)(q)=\left\{w \in \mathbb{R}^n\,\left\vert\; 0\in DG(\bar p,\bar x|0)(q,w)\right.\right\}, \quad \forall q \in \mathbb{R}^d,\tag{7}\] for \(G(p,x):=f(p,x)+F(x)\). In particular, \(S\) is directionally differentiable4 at \(\bar p\) with (locally Lipschitz) directional derivative \[S'(\bar p;\cdot)=DS(\bar p)(\cdot).\] In addition, \(S\) is locally Lipschitz at \(\bar p\) with modulus \[L\leq\limsup_{p\to \bar p} \max_{\|q\|\leq 1} \|DS(p)(q)\|.\]*
If \(F\) is semismooth* at \(\bar x\), then \(S\) is semismooth* at \(\bar p\). Thus, if \(F\) is also proto-differentiable at \(\bar x\), then \(S\) is semismooth at \(\bar p\).
Proof. We first show that ?? and ?? are equivalent. To this end, observe that \[0\in D_x f(\bar p,\bar x)^*w+D^*F(\bar x\mid -f(\bar p,\bar x))(w)\] is, equivalent to, \[- D_x f(\bar p,\bar x)^*w\in D^*F(\bar x\mid -f(\bar p,\bar x))(w).\] By the monotonicity properties of \(f(\bar p, \cdot)\) and \(F\) combined with PR?, 98?, this implies \[0\leq-\left\langle D_x f(\bar p,\bar x)^*w,\, w\right\rangle\leq 0,\] and hence, \(w\in \ker D_x f(\bar p,\bar x)\). Therefore, we have \[0\in D^*F(\bar x\mid -f(\bar p,\bar x))(w),\] or, equivalently, \[w\in \ker D^*F(\bar x| -f(\bar p,\bar x)).\] Therefore, ?? implies ?? . The reverse implication follows from the same observations, yet starting at ?? .
(a) Because \(Q\) is a sum of maximally monotone maps5 and \(\mathrm{dom}\;f(\bar p,\cdot)=\mathbb{R}^n\), it is maximally monotone RoW?, 98?. Hence \(Q\) has closed graph and is convex-valued, see., e.g., RoW?, 98?. Since \(Q\) has closed graph with \((\bar{x}, 0) \in \operatorname{gph}Q\) and \(\ker D^{*}Q(\bar{x}|0) = \{0\}\), it holds that \(Q\) is metrically regular at \((\bar{x}, 0)\) by 1. Together with the monotonicity property, 2 immediately gives that \(Q\) is strongly metrically regular there.
(b) We first prove that that the function \(h:=f(\bar p,\cdot)\) is a strict estimator of \(f\) with respect to \(x\) uniformly in \(p\) at \((\bar p,\bar x)\) with constant \(\mu=0\) in the sense of DoR?, 14? (cf. also DoR?, 14?): To this end, observe that with \(e(p,x):=f(p,x)-h(x)\), we have \[\begin{align} \\ & = & \|f(p,x')-f(p,x) + f(\bar p,x)-f(\bar p,x')\|\\ & \leq & \|f(p,x')-f(p,x)-D_x f(p,x)(x'-x)\|+\|f(\bar p,x')-f(\bar p,x)-D_x f(\bar p,x)(x'-x)\|\\ & & + \|D_x f(\bar p,x)-D_x f(p,x)\|\cdot\|x-x'\|. \end{align}\] Therefore, we find that \[\lim_{\substack{x, x' \to \bar{x}\\ p \to \bar p}} \frac{e(p,x')-e(p,x)}{\|x-x'\|}=0.\] By (a), the mapping \(f(\bar p,\cdot)+F\) is strongly metrically regular at \((\bar x,0)\). By Theorem DoR?, 14?, the solution mapping \(S\) has a Lipschitz continuous single-valued localization around \(\bar p\) for \(\bar x\). We now find that \(S(p)=G(p,\cdot)^{-1}(0)\) is convex-valued for \(p\) near \(\bar p\), by maximal monotonicity of \(G(p,\cdot)\) (see the arguments used for \(Q\) above), see RoW?, 98?. By 3, \(S\) is thus locally single-valued and Lipschitz which proves (b).
(c) Realize, by FGH?, 22?, that \(G\) is proto-differentiable at \(((\bar p, \bar x),0)\). Therefore, by RoW?, 98?, we get that \(S\) is semidifferentiable (cf., RoW?, 98?) at \(\bar p\) and that 7 holds. The claim about single-valuedness and Lipschitzness of \(DS(\bar p)\) also follows from RoW?, 98? realizing that strong metric regularity from (a) implies the strict graphical derivative condition that is needed in said reference. The fact that the semiderivative is the directional derivative is due to local Lipschitzness of \(S\) near \(\bar p\). The formula for the estimate of the Lipschitz constant comes from DoR?, 14?.
(d) By \((a)\), \(Q=f(\bar p,\cdot)+F\) is (strongly) metrically regular at \((\bar x,0)\), i.e. \[0\in D^*Q(\bar x|0)(w)\quad\Longrightarrow\quad w=0.\] By 2 and the definition of the coderivative, this is equivalent to \[-(D_x f(\bar p,\bar x)^*w,w)\in N_{\operatorname{gph}F}(\bar x,-f(\bar p,\bar x))\quad\Longrightarrow\quad w=0.\] Hence, given \((v,w)\in N_{\operatorname{gph}F}(\bar x,-f(\bar p,\bar x))\) such that \(v=(D_x f(\bar p,\bar x)^*w\), it follows that \(w=0\), and hence \(v=0\). Consequently, \(D_pf(\bar p,\bar x)^*w=0\), and altogether the implication ?? holds. Therefore, by 1, \(S\) is semismooth* at \(\bar p\). But by (b), \(S\) is locally Lipschitz at \(\bar p\), hence 7 gives the desired result. If \(F\) is proto-differentiable at \((\bar x, -f(\bar p, \bar{x}))\), then \(S\) is directionally differentiable at \(\bar p\), so by 7, \(S\) is semismooth at \(\bar p\). ◻
We want to use the implicit function theorem from 4 to study the solution map 2 . This can be done by letting \[\label{eq:Data} p:=(A,b,\lambda), \quad f(p,x) := \frac{1}{\lambda} A^T(Ax - b), \quad F := \partial r,\tag{8}\] and realizing that now, by convexity, the optimal solution map in 2 can be written simply as \[S(p)=\left\{x\in \mathbb{R}^n\,\left\vert\; 0\in f(p,x)+F(x)\right.\right\}\] which is exactly the format in 4. The central condition to deploy this result is the Mordukhovich criterion from ?? or, equivalently, ?? which in the case defined by 8 reduces to \[\begin{align} \ker A \cap D^* \partial r^* (-f(\bar{p}, \bar{x}))(0) = \{0\}, \end{align}\] which, by 6 and RoW?, 98?, can be written as \[\label{eq:MordData} \ker A \cap \ker \partial^2 r(\bar{x} | -f(\bar{p}, \bar{x})) = \{0\}.\tag{9}\]
It is therefore paramount to understand the kernel of the generalized Hessian of a closed, proper, convex function. This is where the notion of \(\mathcal{C}^2\)-cone reducibility BS?, 00? in the following sense comes into play:
Definition 3 (\(\mathcal{C}^2\)-cone reducible functions). A closed, convex set \(\Theta \subseteq \mathbb{R}^m\) is said to be \(\mathcal{C}^2\)-cone reducible at \(\bar{v}\in \Theta\) if there exists a neighborhood \(V\) of \(\bar{v}\), a pointed6, closed, convex cone \(K \subseteq \mathbb{R}^{\ell}\) and a \(\mathcal{C}^2\) mapping \(h : V \to \mathbb{R}^{\ell}\) such that \(h(\bar{v}) = 0\), \(D h(\bar{v})\) is surjective, and \[\begin{align} \Theta \cap V = \{v \in V \;| \;h(v) \in K\}. \end{align}\] A closed, proper, convex function \(f : \mathbb{R}^n \to \overline{\mathbb{R}}\) is called \(\mathcal{C}^2\)-cone reducible at \(\bar{u} \in \operatorname{dom}f\) if the set \(\operatorname{epi} f\) is \(\mathcal{C}^2\)-cone reducible at \((\bar{u}, f(\bar{u}))\). We say \(f\) is \(\mathcal{C}^2\)-cone reducible if it is \(\mathcal{C}^2\)-cone reducible at every point of its domain.
Many important sets in optimization are \(\mathcal{C}^2\)-cone reducible such as convex polyhedral sets, the cone of positive semidefinite matrices, and the second-order cone [1], [2], BS?, 00?. Moreover, convex piecewise-linear functions and many typical spectral functions are \(\mathcal{C}^2\)-cone reducible [3], BS?, 00?; see also CHNS?, 26? for several other classes of \(\mathcal{C}^2\)-cone reducible functions.
The central result of this section is obtaining the formula for the kernel of the generalized Hessian of conjugate \(\mathcal{C}^2\)-cone reducible functions, i.e., functions whose conjugates are \(\mathcal{C}^2\)-cone reducible. In order to do so, we need the landmark definition of tilt stability PR?, 98? introduced by Poliquin and Rockafellar and several related results.
Definition 4 (Tilt stability). Given a function \(\varphi : \mathbb{R}^n \to \overline{\mathbb{R}}\), we say that a point \(\bar{x}\in \operatorname{dom} \varphi\) is a tilt-stable minimizer* of \(\varphi\) if there exists \(\gamma > 0\) such that the mapping \[\begin{align} M_{\gamma} : v \mapsto \operatorname{argmin}\{\varphi(x) - \left\langle v,\, x\right\rangle \;| \;x \in \mathbb{B}_{\gamma}(\bar{x})\} \end{align}\] is single-valued and Lipschitz continuous on some neighborhood of \(0\in \mathbb{R}^n\) with \(M_\gamma(0)=\bar{x}\).*
We recall PR?, 98?, with some modifications for the convex case.
Theorem 2 (Characterization of tilt-stability via the generalized Hessian). Let \(\varphi:\mathbb{R}^n \to \overline{\mathbb{R}}\) be a proper, lsc, convex function. Suppose \(\bar{x}\) is a minimizer of \(\varphi\) with \(0 \in \partial \varphi (\bar{x})\). Then, the following are equivalent:
The point \(\bar{x}\) is a tilt-stable minimizer of \(\varphi\).
The generalized Hessian \(\partial^2 \varphi (\bar{x} | 0)\) is positive definite, in the sense that \[\begin{align} \label{eq:PHes} \left\langle z,\, x\right\rangle > 0 \text{ whenever } z \in \partial^2 \varphi(\bar{x} | 0)(w), \;w \not = 0. \end{align}\qquad{(4)}\]
A large portion of the following result is taken from CHNS?, 26?.
Theorem 3 (Characterization of tilt stability for convex problems). Let \(f : \mathbb{R}^n \to \overline{\mathbb{R}}\) be a twice continuously differentiable convex function and let \(g : \mathbb{R}^n \to \overline{\mathbb{R}}\) be a proper lsc convex function. Suppose that \(\bar{x}\in \operatorname{argmin}f+g\). Then \(\bar{x}\) is a tilt-stable minimizer of \(f + g\) if and only if \[\begin{align} \label{eq:Nes} \ker \nabla^2 f(\bar{x}) \cap \ker \partial^2 g(\bar{x} | \bar{v}) = \{0\} \text{ where } \bar{v} = -\nabla f(\bar{x}). \end{align}\qquad{(5)}\] Moreover, if \(\bar{x}\) is a tilt-stable minimizer of \(f + g\), we have \[\begin{align} \label{eq:Kpar} \ker \nabla^2 f(\bar{x}) \cap \operatorname{par} \partial g^*(\bar{v}) = \{0\}. \end{align}\qquad{(6)}\] If, additionally, \(g^*\) is \(\mathcal{C}^2\)-cone reducible at \(\bar{v}\), then ?? is also sufficient for tilt stability of \(f + g\) at \(\bar{x}\).
Proof. Define \(\varphi := f + g\) and note that \(0\in\partial \varphi(\bar{x})\), as \(\bar{x}\) is a minimizer of \(\varphi\). By the second-order subdifferential sum rule or 2, we have that \[\begin{align} \partial^2 \varphi(\bar{x} | 0)(w) = \nabla^2 f(\bar{x})w + \partial^2 g(\bar{x} | \bar v)(w) \;\text{ for all } w \in \mathbb{R}^n. \end{align}\] If \(\bar{x}\) is a tilt-stable minimizer of \(\varphi\), we claim ?? . Indeed, pick any \(w \in \ker \nabla^2 f(\bar{x}) \cap \ker \partial^2 g(\bar{x} | \bar{v})\). The above equation leads us to \(0\in \partial^2 \varphi (\bar{x} | 0)(w)\). By 2, particularly ?? , \(w = 0\). This verifies ?? . On the other hand, if ?? holds, applying 4(a) with \(f(p,x)=\nabla f(x)\) and \(F=\partial g(x)\) tells us that \(\partial \varphi=\nabla f(x)+\partial g(x)\) is strongly metrically regular at \((\bar{x},0)\in \operatorname{gph}\partial \varphi\). Since \(\varphi\) is convex, this ensures \(\bar{x}\) is a tilt-stable minimizer of \(\varphi\); see e.g., [4].
The necessary and sufficient condition for tilt stability in ?? follows from CHNS?, 26?, when the conjugate function \(g^*\) is \(\mathcal{C}^2\)-cone reducible at \(\bar v\). ◻
Part of the following lemma is from [5].
Lemma 8. Suppose \(h: \mathbb{R}^n \to \overline{\mathbb{R}}\) is \(\mathcal{C}^2\)-cone reducible at \(\bar {u}\in {\rm dom}\, g\). Then, \(h\) is twice epi-differentiable at \(\bar u\), and \(\partial h\) is proto-differentiable at \(\bar{u}\) for every \(\bar v \in \partial h(\bar{u})\).
Proof. The twice epi-differentibility of \(h\) at \(\bar u\) for \(\bar v\in \partial h(\bar u)\) follows from [5]. By R?, 90? and convexity of \(h\), this is equivalent to proto-differentiability of \(\partial h\). ◻
The following result from sheds light onto the relationship between the subspace parallel to the subdifferential of the the conjugate of a convex function and the kernel of its generalized Hessian.
Theorem 4 (The kernel of the generalized Hessian of convex functions). Let \(g:\mathbb{R}^n\to \mathbb{R}\cup\{\infty\}\) be a proper, lsc, convex function and \((\bar{x}, \bar{v}) \in \operatorname{gph} \partial g\). We have \[\begin{align} \label{eq:pargenhess} \mathrm{par}\,\partial g^* (\bar{v}) \subseteq \ker \partial^2 g(\bar{x} | \bar{v}) \cup (- \ker \partial^2 g(\bar{x} | \bar{v})). \end{align}\qquad{(7)}\] If \(g^*\) is twice epi-differentiable at \(\bar{v}\), then we have \[\begin{align} \label{eq:pargenhesstw} \mathrm{par}\,\partial g^* (\bar{v}) \subseteq \ker \partial^2 g(\bar{x} | \bar{v}). \end{align}\qquad{(8)}\] Moreover, if \(g^*\) is \(\mathcal{C}^2\)-cone reducible at \(\bar{v}\), the above inclusion turns to equality \[\begin{align} \label{eq:pargenhessc2} \mathrm{par}\,\partial g^* (\bar{v}) = \ker \partial^2 g(\bar{x} | \bar{v}). \end{align}\qquad{(9)}\]
Proof. To justify ?? , pick any \(w \in \operatorname{par} \partial g^* (\bar{v}) \setminus \{0\}\) and define \(L := \operatorname{span}\{w\}\). Let \(A\) be an \(n\times n\) matrix with \(\ker A = L\). Define \(f(x) := \frac{1}{2} \lVert Ax - A \bar{x} \rVert^2 - \bar{v}^T x\). Note that \(\nabla f(\bar{x}) = - \bar{v}\) and \[\begin{align} \ker \nabla^2 f(\bar{x}) = \ker A^TA = \ker A = L. \end{align}\] It follows that \[\begin{align} \ker \nabla^2 f(\bar{x}) \cap \operatorname{par} \partial g^* (\bar{v}) = L \not = \{0\}. \end{align}\] By 3, \(\bar{x}\) is not a tilt-stable minimizer of \(f + g\) and \[\ker \nabla^2 f(\bar{x}) \cap \ker \partial^2 g(\bar{x}| \bar{v}) \not = \{0\}.\] Hence, there exists \(\alpha \in \mathbb{R}\setminus \{0\}\) such that \(\alpha w \in \ker \partial^2 g (\bar{x}| \bar{v})\), i.e., \((0, - \alpha w) \in N_{\operatorname{gph} \partial g}(\bar{x}, \bar{v})\). As \(N_{\operatorname{gph} \partial g}(\bar{x}, \bar{v})\) is a (not necessarily convex) cone and \(\alpha \not = 0\), we obtain that \[\begin{align} (0, w) \in N_{\operatorname{gph} \partial g}(\bar{x}, \bar{v}) \text{ or } (0, -w) \in N_{\operatorname{gph} \partial g}(\bar{x}, \bar{v}), \end{align}\] which implies that \(w\in \ker \partial^2 g(\bar{x} | \bar{v}) \cup (- \ker \partial^2 g(\bar{x} | \bar{v}))\) for any \(w\in\mathrm{par}\,\partial g^* (\bar{v}) \setminus \{0\}\). This verifies the inclusion ?? .
To prove the inclusion “\(\subseteq\)” in ?? , suppose further \(g^*\) is twice epi-differentiable at \(\bar{v}\). By the convexity and closedness of \(\partial g^* (\bar{v})\), we have that R?, 70? \[\begin{align} \bar{x} \in \partial g^* (\bar{v}) = \operatorname{cl}(\operatorname{ri} \partial g^* (\bar{v})). \end{align}\] Hence, there exists a sequence \(\{x^k\} \subseteq \operatorname{ri} \partial g^*(\bar{v})\) such that \(x^k \to \bar{x}\). We claim that \[\begin{align} \label{eq:coderivativeInclusion} T_{\partial g^* (\bar{v})}(x^k) = \operatorname{par} \partial g^* (\bar{v}) \subseteq \ker D \partial g( x^k | \bar{v}). \end{align}\tag{10}\] The equality holds due to the fact that \(x^k \in \operatorname{ri} \partial g^* (\bar{v})\) and \[\begin{align} T_{\partial g^* (\bar{v})}(x^k) = \operatorname{cl}(\operatorname{cone}(\partial g^*(\bar{v}) - x^k)) = \operatorname{cl} (\operatorname{par} \partial g^* (\bar{v})) = \operatorname{par} \partial g^* (\bar{v}). \end{align}\] To see the inclusion on the right-hand side of 10 , take \(w \in T_{\partial g^* (\bar{v})}(x^k)\). There exist sequences \(\{t_{k_n}\} \downarrow 0\) and {\(w^{k_n}\} \to w\) such that \(x^k + t_{k_n} w^{k_n} \in \partial g^* (\bar{v})\) for all \(n\). It follows that \[\begin{align} (x^k,\bar v)+t_{k_n}(w^{k_n},0)= (x^k + t_{k_n}w^{k_n}, \bar{v}) \in \operatorname{gph} \partial g, \end{align}\] which gives that \(0 \in D \partial g (x^k | \bar{v})(w)\) or equivalently, \(w \in \ker D \partial g^* (\bar{v} | x^k)\). Since \(g^*\) is twice epi-differentiable at \(\bar v\), \(g\) is twice epi-differentiable at any \(x_k\) for \(\bar v\) by RoW?, 98?. The Rockafellar-Zagrodny derivative-coderivative inclusion (RoW?, 98?) tells us that \[\begin{align} D \partial g (x^k | \bar{v}) \subseteq \partial^2 g(x^k | \bar{v}). \end{align}\] This along with 10 implies that, for all \(k\in\mathbb{N}\), we have \[\begin{align} \operatorname{par} \partial g^* (\bar{v}) \subseteq \ker \partial^2 g(x^k | \bar{v})=\{w\in \mathbb{R}^n|\, (0,-w)\in N_{{\rm gph}\, \partial g}(x_k,\bar v)\}. \end{align}\] As the normal cone \(N_{{\rm gph}\, \partial g}\) is a closed set-valued mapping, letting \(x^k \to \bar{x}\) in the above inclusion gives us that \(\operatorname{par} \partial g^* (\bar{v}) \subseteq \ker \partial^2 g(\bar{x}| \bar{v})\), which shows the “\(\subseteq\)" inclusion in ?? .
Next, let us suppose that \(g^*\) is \(\mathcal{C}^2\)-cone reducible at \(\bar{v}\). By applying 8 for \(h=g^*\), \(g^*\) is twice epi-differentiable at \(\bar{v}\). Hence, ?? holds. We just need to justify the inclusion “\(\supseteq\)” in ?? . To do so, repeat some of the arguments from the beginning of the proof: Take \(z \in \ker \partial^2 g(\bar{x}| \bar{v}) \setminus \{0\}\) and define \(L := \operatorname{span}\{z\}\). Let \(A\) be an \(n\times n\) matrix with \(\ker A = L\). Define \(f(x) := \frac{1}{2} \lVert Ax - A\bar{x} \rVert^2 - \bar v^T x\). Again, we have \(\nabla f(\bar{x}) = -\bar{v}\) and \(\ker \nabla^2 f(\bar{x}) = L\). As \(z \in L \cap \ker \partial^2 g(\bar{x}| \bar{v})\), \(\bar{x}\) is not a tilt-stable minimizer of \(f + g\). By 3, \(L \cap \operatorname{par} \partial g^*(\bar{v}) \not = \{0\}\). Thus, \(z \in \operatorname{par} \partial g^* (\bar{v})\) for every nonzero \(z \in \ker \partial^2 g(\bar{x} | \bar{v})\). ◻
The most important part for our study is the equality ?? which furnishes a simple way of computing the generalized Hessian of a (closed, proper) convex function whose conjugate is \(\mathcal{C}^2\)-cone reducible and thus a tractable way of verifying the key condition ?? to deploy the implicit function theorem in 4 to study the solution map 2 .
The following theorem extends the recent result CHNS?, 26?.
Theorem 5. Let \(S : \mathbb{R}^{m \times n} \times \mathbb{R}^m \times \mathbb{R}_{++} \rightrightarrows \mathbb{R}^n\) be the solution of problem 1 given by \[\begin{align} S(A, b, \lambda) := \underset{x \in \mathbb{R}^n}{\operatorname{argmin}} \left\{\frac{1}{2}\lVert Ax - b \rVert^2 + \lambda r(x)\right\}. \end{align}\] Let \((\bar{A}, \bar{b}, \bar{\lambda}, \bar{x}) \in \operatorname{gph} S\) and \(\bar{v} := -\frac{1}{\bar{\lambda}} \bar{A}^T(\bar{A} \bar{x} - \bar{b})\). Suppose that \(r^*\) is \(\mathcal{C}^2\)-cone reducible at \(\bar v\). Then the following condition \[\begin{align} \label{eq:CQ} \ker \bar{A} \cap \mathrm{par}\,\partial r^* (\bar{v}) = \{0\} \end{align}\qquad{(10)}\] is equivalent to any of the following conditions:
\(S\) is single-valued at \((\bar A, \bar b, \bar \lambda)\).
\(S\) is locally Lipschitz at \((\bar A, \bar b, \bar \lambda)\).
\(S\) is directionally differentiable \((\bar A, \bar b, \bar \lambda)\).
Additionally, the following condition implies ?? , and if \(\partial r\) is semismooth* at \((\bar x, \bar v)\), then it is equivalent to ?? :
Proof. Apply 4 to \(F = \partial r\), and \(f\) defined by \(f(p, x) = \frac{1}{\lambda} A^T(Ax - b)\), as was alluded to earlier. If condition ?? is satisfied, by ?? the Mordukhovich criterion ?? that reads \[\begin{align} \ker \bar{A} \cap \ker \partial^2 r(\bar{x} | \bar{v}) = \{0\} \end{align}\] holds. This gives that \(S\) is (a) single-valued and (b) locally Lipschitz at \((\bar A, \bar b, \bar \lambda)\). By 8, \(\partial r^*\) is proto-differentiable at \(\bar v\), so by RoW?, 98?, \(\partial r\) is proto-differentiable at \(\bar{x}\), therefore 4 also tells us that \(S\) is (c) directionally differentiable at \((\bar A, \bar b, \bar \lambda)\). When \(\partial r\) is semismooth* at \((\bar x, \bar v)\), 4 tells us that \(S\) is semismooth* at \((\bar b, \bar \lambda)\). Thus, by 7, \(S\) is semismooth at \((\bar b, \bar \lambda)\).
On the other hand, (b), (c), and (d) all imply (a), which by CHNS?, 26?, is equivalent to ?? . ◻
Remark 5 (Conjugate \(\mathcal{C}^2\)-cone reducible functions). The class of proper, closed, convex functions with Fenchel conjugates which are \(\mathcal{C}^2\)-cone reducible includes polyhedral convex functions and support functions of \(\mathcal{C}^2\)-cone reducible sets (which encompasses the \(\ell_1/\ell_2\) norm and the nuclear norm). See CHNS?, 26? for a more comprehensive list.
5 is a solely qualitative statement. In order to obtain quantitative results regarding the stability of the solution map \(S\), we need to impose more structure on the regularizer \(r\) to arrive at computable expressions. In fact, we will first study the special case where the regularizer \(r\) has the form \(r=\sigma_\mathcal{P}\circ M\), i.e., a support function of a polyhedral set composed with a linear map. This encapsulates, in particualar, all (weighted) polyhedral norms, and therefore stability results for the (weighted) LASSO BBH?, 22?, GKM?, 18?. Functions of this form are polyhedral and are known to be \(\mathcal{C}^2\)-cone-reducible (CHNS?, 26?
We start our study of this special case by a simple conjugacy result which appeals, in particular, to the fact that the support and indicator of a polyehdral set are polydreal convex functions.
Lemma 9 (Conjugate of \(\sigma_\mathcal{P}\circ M\)). Consider \(r = \sigma_{\mathcal{P}} \circ M\) where \(\mathcal{P}\subseteq \mathbb{R}^{\ell}\) is a polyhedron and \(M \in \mathbb{R}^{\ell \times n}\). Let \((\bar{x}, \bar v) \in \operatorname{gph}\partial r\) and set \[\label{eq:Lambda} \Lambda(\bar{x}, \bar v) := \{y\in \mathbb{R}^{\ell} \;| \;M^Ty = \bar v , \;y \in N_{\mathcal{P}}^{-1}(M\bar{x})\}.\qquad{(11)}\] Then \[\begin{align} \partial r^* (\bar v) = M^{-1} (N_{\mathcal{P}}(\bar y)), \;\forall \bar y \in \Lambda (\bar{x}, \bar v). \end{align}\] In particular, we have \[\begin{align} \label{eq:rpara} \mathrm{par}\,\partial r^*(\bar v) = \operatorname{span} M^{-1}( N_{\mathcal{P}}(\bar y)) , \;\forall \bar y \in \Lambda(\bar{x}, \bar v). \end{align}\qquad{(12)}\]
Proof. Using the relations \(\partial r^* = (\partial r)^{-1}\) and \(\partial \sigma_\mathcal{P}=N_\mathcal{P}^{-1}\) as well as the subdifferential chain rule R?, 70? with the fact that \(\sigma_\mathcal{P}\) is polyhedral, we find: \[\begin{align} u \in \partial r^*(\bar v) \iff \bar v \in M^{T} N_{\mathcal{P}}^{-1}(Mu) \iff \exists y \in N_{\mathcal{P}}^{-1}(Mu):\; v = M^Ty \end{align}\] So, if \(\bar y \in \Lambda(\bar{x}, \bar v)\), then \[\begin{align} \partial r^*(\bar v) = M^{-1}(N_{\mathcal{P}}(\bar y)). \end{align}\] And because \(0 \in \partial r^*(\bar v)\), we have \[\begin{align} \mathrm{par}\,\partial r^*(\bar v) = \mathrm{span}\,M^{-1}(N_{\mathcal{P}}(\bar y))\quadfor any\quad \bar y\in \Lambda(\bar x,\bar v). \end{align}\] ◻
The next example shows that, in general, the \(\mathrm{span}\,\) cannot be moved inside in ?? , and at the same time, that the subspace parallel to the subdifferential of the conjugate is readily available.
Example 1. Let \(M = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}\), \(\mathcal{P}= [0, 1]^2\), \(\bar{x}= 0\), \(\bar v = \begin{pmatrix} 1 \\ 1 \end{pmatrix}\), and \(\bar y = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\). First, we verify that \(\bar y \in \Lambda (\bar x, \bar v)\). \(M^T \bar y = \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \bar v\), and \(M \bar{x}= 0\), so \(N_{\mathcal{P}}^{-1}(M \bar{x}) = \mathbb{R}^2 \ni \bar y\). Now, we compute \(\mathrm{par}\,\partial r^*(\bar v)\): \(N_{\mathcal{P}}(\bar y) = N_{[0,1]}(1) \times N_{[0, 1]}(0) = \mathbb{R}_{+} \times \mathbb{R}_{-}\), by RoW?, 98?. Thus, \[\begin{align} M^{-1}N_{\mathcal{P}}(\bar{y}) = \left\{z \in \mathbb{R}^2 \;| \;\begin{pmatrix} z_1 + z_2 \\ z_1 + z_2 \end{pmatrix} \in \mathbb{R}_{+} \times \mathbb{R}_{-}\right\} = \{z \;| \;z_1 + z_2 = 0\} = \mathrm{span}\,\left\{\begin{pmatrix} 1 \\ -1 \end{pmatrix}\right\}. \end{align}\] This tells us that \(\mathrm{span}\,M^{-1} N_{\mathcal{P}} (\bar y) = \mathrm{span}\,\left\{\begin{pmatrix} 1 \\ -1 \end{pmatrix}\right\}\). However, if we move the \(\mathrm{span}\,\) inside, we obtain \[\begin{align} \mathrm{span}\,N_{\mathcal{P}}(\bar y) = \mathbb{R}^2 \implies M^{-1}(\mathrm{span}\,N_{\mathcal{P}}(\bar y)) = \mathbb{R}^2 \neq \mathrm{span}\,\left\{\begin{pmatrix} 1 \\ -1 \end{pmatrix}\right\}. \end{align}\] \(\diamond\)
The next result is a technical lemma needed for the upcoming stability result.
Lemma 10. Let \(\{(x_k,v_k)\in \operatorname{gph} \partial r\}\to (\bar x,\bar v)\), and let \(\bar y \in \Lambda(\bar x,\bar v)\) in ?? . Then there exists \(\{y_k\in \Lambda(x_k,v_k)\}\to\bar y\).
Proof. Observe that \(\operatorname{gph}\Lambda\) is given by \[\begin{align} \{(x, v, y) \;| \;M^Ty = v, \, Mx \in N_{\mathcal{P}}(y)\}. \end{align}\] Because \(N_{\mathcal{P}}\) is polyhedral, we have that \(\operatorname{gph}\Lambda\) is polyhedral, and therefore the set-valued map \(\Lambda^{-1}\) has a graph which is a polyhedral convex set. For \(k \in \mathbb{N}\), define \(y_k := P_{\Lambda(x_k, v_k)}(\bar y)\), the projection of \(\bar y\) onto \(\Lambda (x_k, v_k)\). By RoW?, 98?, the set-valued map \(\Lambda^{-1} : \mathbb{R}^{\ell} \rightrightarrows \mathbb{R}^{2n}\) is globally metrically regular, so there exists \(\kappa > 0\), which does not depend on \(k\), such that we have \[\begin{align} \lVert y_k - \bar y \rVert = d(\bar y, \Lambda (x_k, v_k)) \le \kappa d((x_k, v_k), \Lambda^{-1}(\bar y)) \le \kappa \left\lVert \begin{pmatrix} x_k \\ v_k \end{pmatrix} - \begin{pmatrix} \bar x \\ \bar v \end{pmatrix}\right\rVert \to 0 \end{align}\] so \(y_k \to \bar y\). ◻
Corollary 2. Let \(S : \mathbb{R}^m \times \mathbb{R}_{++} \rightrightarrows \mathbb{R}^n\) be given by \[\begin{align} S(b, \lambda) = \underset{x \in \mathbb{R}^n}{\operatorname{argmin}} \left\{ \frac{1}{2} \lVert Ax - b \rVert^2 + \lambda r(x) \right\}, \end{align}\] where \(r = \sigma_{\mathcal{P}} \circ M\) for \(\mathcal{P}\subseteq \mathbb{R}^{\ell}\) polyhedral and \(M \in \mathbb{R}^{\ell \times n}\). Let \(\Lambda(\bar{x}, \bar v)\) be defined as in 9. If for any \(\bar y \in \Lambda(\bar{x}, \bar v)\), we have \[\begin{align} \label{eq:MordCritpolyhedral} \ker A \cap \operatorname{span} M^{-1} (N_{\mathcal{P}}(\bar{y})) = \{0\} \end{align}\qquad{(13)}\] then it holds that
\(S\) is semismooth (in particular, single-valued, locally Lipschitz, and directionally differentiable) at \((\bar{b}, \bar{\lambda})\), and for each direction \((q, \alpha)\), there exists a matrix \(Q\) with orthonormal columns such that the directional derivative in direction \((q, \alpha)\) is given by \[\begin{align} S'(\bar{b}, \bar{\lambda} ; q, \alpha) = Q[(AQ)^T(AQ)]^{-1} (AQ)^T \left(q + \frac{\alpha}{\bar{\lambda}}(A \bar{x}- \bar{b})\right). \end{align}\]
For any \(\bar{y} \in \Lambda(\bar{x}, \bar v)\), the modulus of Lipschitz continuity of \(S\) can be bounded by \[\begin{align} L \le \frac{1}{\sigma_{\min}(A \overline{Q})^2} \left( \sigma_{\max}(A \overline{Q}) + \frac{1}{\bar{\lambda}} \lVert (A\overline{Q})^T(A \bar{x}- \bar{b}) \rVert \right), \end{align}\] where \(\overline{Q}\) is a matrix with columns which form an orthonormal basis of \(\operatorname{span} M^{-1} N_{\mathcal{P}}(\bar{y})\).
Proof. First, observe that \(r\) is polyhedral convex, so by RoW?, 98?, \(r^*\) is also polyhedral convex, and is therefore \(\mathcal{C}^2\)-cone reducible. Also, polyhedral convex functions are in particular, piecewise linear-quadratic, so by FGH?, 22?, we have that \(\partial r\) is semismooth* at every point. Lemma 9 tells us that \(\mathrm{par}\,\partial r^*(\bar v) = \mathrm{span}\,M^{-1} (N_{\mathcal{P}} (\bar{y}))\), for any \(\bar y \in \Lambda(\bar{x}, \bar v)\). It will be useful going forward to parameterize \(\mathcal{P}\) as \(\{z \;| \;P^Tz \preceq \beta\}\) for \(P \in \mathbb{R}^{\ell \times k}\), \(\beta \in \mathbb{R}^{k}\), and we will use \(p_i\) to refer to the \(i\)th column of \(P\). Proposition 4 tells us that the directional derivative of \(S\) in direction \((q, \alpha)\) is given by the unique \(w\) which satisfies \[\begin{align} 0 \in DG(\bar{b}, \bar{\lambda}, \bar{x}| 0)(q, \alpha, w) \end{align}\] where \(G(b, \lambda, x) = \frac{1}{\lambda} A^T(Ax - b) + \partial r(x)\). Observe that for any \(\bar{y} \in \Lambda (\bar{x}, \bar{v})\), by MMS?, 22?, we have this is equivalent to \[\begin{align} \frac{1}{\bar{\lambda}} A^T \left(q + \frac{\alpha}{\bar{\lambda}} (A \bar{x}- \bar{b}) - Aw\right) \in D \partial r (\bar{x} | \bar{v})(w) = M^T D(N_{\mathcal{P}})^{-1}(M \bar{x}| \bar{y})(Mw). \end{align}\] Now, observe that \[\begin{align} z \in D(N_{\mathcal{P}})^{-1}(M \bar{x}| \bar{y})(Mw) \iff Mw \in D N_{\mathcal{P}} (\bar{y} | M \bar{x})(z) = N_{\mathcal{K}}(z), \end{align}\] where \(\mathcal{K} = T_{\mathcal{P}}(\bar{y}) \cap \{M \bar{x}\}^{\bot}\) is the critical cone, by RoW?, 98?. Notice that \[\begin{align} N_{\mathcal{K}}(z) = N_{T_{\mathcal{P}}(\bar{y})}(z) + N_{\{M \bar{x}\}^{\bot}}(z) = \operatorname{cone} \{p_i \;| \;i \in I(\bar{y}), \;p_i^Tz = 0\} + \operatorname{span}\{M \bar{x}\} \end{align}\] where \(I(\bar{y}) := \{i \;| \;p_i^T \bar{y} = \beta_i\}\). We claim that \(M\bar{x}\in \operatorname{cone} \{p_i \;| \;i \in K\}\). To see this, let \(K := \{i \in I(\bar{y}) \;| \;p_i^Tz = 0\}\). Set \(C := \operatorname{cone} \{p_i \;| \;i \in K\} \subseteq N_{\mathcal{P}}(\bar{y})\). We know that \(M \bar{x}\in N_{\mathcal{P}}(\bar{y})\), and we in fact claim that \(M \bar{x}\in C\). We know \(M\bar{x}\) can be written as \(\sum_{i \in I(\bar{y})} \gamma_i p_i\) for \(\gamma_i \ge 0\). Using the fact that \(z^T(M\bar{x}) = 0\) with the fact that \(p_i^Tz < 0\) for \(i \in I(\bar{y}) \setminus K\), (which come from \(z \in T_{\mathcal{P}}(\bar{y})\) and \(z \in \{M \bar{x}\}^{\bot}\)) we get \[\begin{align} 0 = \sum\limits_{i \in I(\bar{y})} \gamma_i p_i^Tz = \sum\limits_{i \in K} \gamma_i \underbrace{p_i^Tz}_{ = 0} + \sum\limits_{i \in I(\bar{v}) \setminus K} \gamma_i \underbrace{p_i^Tz}_{< 0}. \end{align}\] So \(\gamma_i = 0\) for \(i \not \in K\). We can then write \[\begin{align} Mw \in C + \operatorname{span}\{M\bar{x}\}. \end{align}\] Set \(E := \operatorname{span} M^{-1}(C)\) and notice that \[\begin{align} E =\operatorname{span} M^{-1}(C) \subseteq M^{-1} \operatorname{span} C = M^{-1} (\operatorname{rge}P_{K}). \end{align}\] Since \(M \bar{x}\in C\), we have \(\bar{x}\in E\). Therefore, \(Mw \in C\), so \(w \in E\). Then, since \(z \in \ker P_K^T = (\operatorname{rge}P_K)^{\bot}\), we have \[\begin{align} \label{eq:inEperp} M^Tz \in M^T ((\operatorname{rge}P_K)^{\bot}) \overset{\eqref{lem:Sub}}{=} \left(M^{-1}(\operatorname{rge}P_K)\right)^{\bot} \subseteq E^{\bot}. \end{align}\tag{11}\] Now, let \(q_1,...,q_r\) be an orthonormal basis of \(E\) and set \(Q = \begin{bmatrix} q_1 \cdots q_r \end{bmatrix}\). Then, \(QQ^T\) is the orthogonal projection onto \(E\), and consequently \(QQ^Tw = w\). Setting \(\bar{u} := \frac{1}{\bar{\lambda}} (A \bar{x}- \bar{b})\), we now infer that \[\begin{align} 0 \overset{\eqref{eq:inEperp}}{=} Q^T (\lambda M^Tz) = Q^T A^T (q + \alpha \bar{u} - Aw). \end{align}\] Using \(w \in E\), this implies \[\begin{align} (AQ)^T AQQ^Tw = (AQ)^T(q + \alpha \bar{u}). \end{align}\] Since \(E \subseteq \operatorname{span} M^{-1} N_{\mathcal{P}}(\bar{y})\), using ?? gives \(\ker A \cap \operatorname{rge}Q = \{0\}\), so \((AQ)^T(AQ)\) is invertible. Thus, we obtain \[\begin{align} w = Q[(AQ)^T(AQ)]^{-1} (AQ)^T (q + \alpha \bar{u}). \end{align}\] In view of [prop:Implicit], this establishes the directional derivative of \(S\) at \((\bar{b}, \bar{\lambda})\) in direction \((q, \alpha)\) is given by \[\begin{align} S'(\bar{b}, \bar{\lambda} ; q, \alpha) = Q[(AQ)^T(AQ)]^{-1} (AQ)^T (q + \alpha \bar{u}). \end{align}\] We now argue ?? holds locally:
to this end, take any sequence \((b_k,\lambda_k)\to (\bar b, \bar \lambda)\) with \(x_k=S(b_k,\lambda_k)\to\bar x\) and \(v_k:=\frac{1}{\lambda_k}A^T (Ax_k-b_k)\in \partial r(x_k)\to \bar v.\) Then for \(\bar y\in \Lambda(\bar x,\bar v)\), by 10, there exists \(y_k\in \Lambda(x_k,v_k)\to \bar y\), and thus (for \(k\) sufficiently large) \[I(y_k)\subseteq I(\bar y)\] hence \(\partial r^*(v_k)\subseteq\partial r^*(\bar v)\). Consequently, \[\mathrm{par}\,\partial r^*(v_k)\cap \ker A \subseteq\mathrm{par}\,\partial r^*(\bar v)\cap \ker A,\] for \(k\) sufficiently large. Therefore, assuming ?? at \((\bar b,\bar \lambda)\) yields that this property holds for all \((b,\lambda)\) sufficiently close.
Hence, by reiterating the above reasoning for nearby points, \(S\) is directionally differentiable at \((b,\lambda)\) sufficiently close to \((\bar b,\bar \lambda)\), and \(S'((b,\lambda);(\cdot,\cdot))\) is, in particular, continuous. Thus, from 4(c) we infer that \[L:=\limsup_{(b,\lambda)\to (\bar b,\bar \lambda)} \max_{\|(q,\alpha)\|\leq 1}\|S'((b,\lambda);(q,\alpha))\|\] is a local Lipschitz bound for \(S\) at \((\bar b,\bar \lambda)\). Now let \((b_k,\lambda_k)\to (\bar b,\bar \lambda)\) such that \[\max_{\|(q,\alpha)\|\leq 1}\|S'((b_k,\lambda_k);(q,\alpha))\|\to L.\] As \(S'((b_k,\lambda_k);(\cdot,\cdot))\) is continuous (for all \(k\in \mathbb{N}\)), there exists \(\{(q_k,\alpha_k)\in \mathbb{B}\}\to (\bar q,\bar \alpha)\in \mathbb{B}\) such that \[\|S'((b_k,\lambda_k);(q_k,\alpha_k))\|\to L.\] Let \(x_k\in S(b_k,\lambda_k)\to \bar x\), \(v_k=\frac{1}{\lambda_k}A^T(Ax_k-b_k)\in \partial r(x_k)\to \bar v\). With 10, we choose \(y^k\in \Lambda(x_k,v_k)\to \bar y\). Let \[K_k\subseteq I(y_k)=\left\{p_i\,\left\vert\; \left\langle p_i,\, y_k\right\rangle=\beta_i\right.\right\}.\] be the associated index set from earlier with \((b_k,\lambda_k, x_k,v_k, y_k, q_k, \alpha_k)\) (instead of \((\bar b,\bar \lambda, \bar x,\bar v,\bar y, \bar q, \bar \alpha)\)). By finiteness, we may assume w.l.o.g. that \(K_k= K\subseteq I(\bar y)\). And thus we can assume w.l.o.g. that for some subspace \(E\) we have \[E_k=\mathrm{span}\,M^{-1}(\mathrm{cone}\,\left\{p_i\,\left\vert\; i\in K_k\right.\right\})\equiv E\subseteq\mathrm{par}\,\partial r^*(\bar v).\] for the associated subspace \(E_k\). Now let \(q_1,\dots, q_t\in \mathbb{R}^n\) be an orthonormal basis of \(E\) such that \(QQ^T\in\mathbb{R}^{n\times n}\) with \(Q=[q_1,\dots, q_t]\) is the orthogonal projection onto \(E\). Since \(E\subseteq\mathrm{par}\,\partial r^*(\bar v)\), we can pad \(Q\) to a matrix \(\bar Q:=[Q\; \hat{Q}]\) whose columns form an orthonormal basis of \(\mathrm{par}\,\partial r^*(\bar v)\) such that \(\bar Q \bar Q^T\in \mathbb{R}^{n\times n}\) is the orthogonal projection onto \(\mathrm{par}\,\partial r^*(\bar v)\).
With our derivations above we therefore find that \[\begin{align} \|S'((b_k,\lambda_k);(q_k,\alpha_k))\|\;& = & \left\|Q[(AQ)^T(AQ)]^{-1}(AQ)^T\left[q_k+\frac{\alpha_k}{\lambda_k}(Ax_k-b_k)\right]\right\|\\ & \leq & \|[(AQ)^T(AQ)]^{-1}\|\cdot \left\|(AQ)^T\left[q_k+\frac{\alpha_k}{\lambda_k}(Ax_k-b_k)\right]\right\|\\ & = & \frac{1}{\lambda_{\min}((AQ)^T(AQ))}\cdot \left\|(AQ)^T\left[q_k+\frac{\alpha_k}{\lambda_k}(Ax_k-b_k)\right]\right\|. \end{align}\] Now observe that \[\begin{align} \lambda_{\min}((AQ)^T(AQ))& = & \min_{x\in \mathbb{R}^n\setminus\{0\}}\frac{(Qx)^TA^TAQx}{\|x\|^2}\\ &=& \min_{y\in E\setminus\{0\}}\frac{y^TA^TAy}{\|y\|^2}\\ & \geq & \min_{y\in \mathrm{par}\,\partial r^*(\bar v)\setminus\{0\}}\frac{y^TA^TAy}{\|y\|^2}\\ & = & \lambda_{\min}((A\bar Q)^T(A\bar Q)). \end{align}\] Here the first identity uses, e.g., HoJ?, 13?, while the second one relies on the fact that \(\left\{Qx\,\left\vert\; x\in \mathbb{R}^n\setminus\{0\}\right.\right\}=E\setminus\{0\}\), and that \(\|Q^Ty\|=\|y\|\) for all \(y\in E\). The inequality uses that \(E\subseteq\mathrm{par}\,\partial r^*(\bar v)\), and the last identity uses the arguments from the first one and that the columns of \(\bar Q\) form an orthonormal basis of \(\mathrm{par}\,\partial r^*(\bar v)\). Using this bound we get \[\begin{align} \|S'((b_k,\lambda_k);(q_k,\alpha_k))\|\;\le \frac{1}{\lambda_{\min}((A \bar Q)^T(A \bar Q))}\cdot \left\|(AQ)^T\left[q_k+\frac{\alpha_k}{\lambda_k}(Ax_k-b_k)\right]\right\| \\ = \frac{1}{\sigma_{\min}(A \bar Q)^2} \cdot \left\|(AQ)^T\left[q_k+\frac{\alpha_k}{\lambda_k}(Ax_k-b_k)\right]\right\|. \end{align}\] Taking the limit in \(k\), we get \[\begin{align} L \le \frac{1}{\sigma_{\min}(A \bar Q)^2} \cdot \left\|(AQ)^T\left[\bar q+\frac{\bar \alpha}{\bar \lambda}(A \bar{x}- \bar b)\right]\right\| \\ \le \frac{1}{\sigma_{\min}(A \bar Q)^2} \left( \max_{q \in \mathbb{B}} \lVert (AQ)^T q \rVert + \max_{\alpha \in [-1, 1]} \lVert \frac{1}{\bar \lambda} (AQ)^T \alpha (A \bar{x}- \bar{b}) \rVert \right) \\ = \frac{1}{\sigma_{\min}(A \bar Q)^2} \left( \lVert (AQ)^T \rVert + \lVert \frac{1}{\bar \lambda} (AQ)^T (A \bar{x}- \bar{b}) \rVert \right) \\ = \frac{1}{\sigma_{\min}(A \bar Q)^2} \left( \sigma_{\max}(AQ) + \frac{1}{\bar \lambda} \lVert (AQ)^T (A \bar{x}- \bar{b}) \rVert \right) . \end{align}\] By a similar argument to the one above, we have \[\begin{align} \lambda_{\max}((AQ)^T AQ) = \max_{x \in \mathbb{R}^n \setminus \{0\}} \frac{x^TQ^TA^TAQx}{\lVert x \rVert^2} = \max_{y \in E \setminus \{0\}} \frac{y^TA^TAy}{\lVert y \rVert^2} \le \lambda_{\max}((A \bar Q)^T A \bar Q) \end{align}\] which implies that \(\sigma_{\max}(AQ) \le \sigma_{\max}(A \bar Q)\). This gives a further bound of \[\begin{align} L \le \frac{1}{\sigma_{\min}(A \bar Q)^2} \left( \sigma_{\max}(A \bar Q) + \frac{1}{\bar \lambda} \lVert (AQ)^T (A \bar{x}- \bar{b}) \rVert \right) . \end{align}\] Finally, because \(\bar Q^T = \begin{bmatrix} Q^T \\ \hat{Q}^T \end{bmatrix}\), we have that \[\begin{align} \frac{1}{\sigma_{\min}(A \bar Q)^2} \left( \sigma_{\max}(A \bar Q) + \frac{1}{\bar \lambda} \lVert (AQ)^T (A \bar{x}- \bar{b}) \rVert \right) \\ \le \frac{1}{\sigma_{\min}(A \bar Q)^2} \left( \sigma_{\max}(A \bar Q) + \frac{1}{\bar \lambda} \lVert (A \bar Q)^T (A \bar{x}- \bar{b}) \rVert \right). \end{align}\] which gives \[\begin{align} L \le \frac{1}{\sigma_{\min}(A \bar Q)^2} \left( \sigma_{\max}(A \bar Q) + \frac{1}{\bar \lambda} \lVert (A \bar Q)^T (A \bar{x}- \bar{b}) \rVert \right). \end{align}\] ◻
Remark 6. The above result could have been stated for \(p = (A, b, \lambda)\) as opposed to \((b, \lambda)\), but due to space and legibility constraints, we have stated a simplified version. We could have also stated both 5 and 2 for the more general setting where the data fidelity term is given by a generic twice continuously differentiable convex function \(\varphi\), instead of \(\frac{1}{2} \lVert \cdot \rVert^2\). Under this setting, the Mordukhovich criterion ?? instead reads \[\begin{align} \ker \bar{A}^T \nabla^2 \varphi(\bar A \bar x - \bar b) \bar{A} \cap \mathrm{par}\,\partial r^*(\bar v) = \{0\}. \end{align}\]
Example 2 (LASSO). A popular choice of regularizer which can be written in the form \(\sigma_{\mathcal{P}} \circ M\) is the \(\ell_1\) norm, in which case 1 becomes the celebrated LASSO problem T?, 96?. Stability results for the solution map of the LASSO problem can be found in BBH?, 22?. In order to apply 2, we take \(\mathcal{P}= \{z \, | \, P^Tz \preceq \beta \}\) for \(P = \begin{bmatrix} I & -I \end{bmatrix}\), \(\beta\) equal to the vector with every component equal to one (which makes \(\mathcal{P}\) the unit ball under the \(\ell_{\infty}\) norm), and \(M = I\). Let \((\bar b, \bar \lambda, \bar x) \in \operatorname{gph}S\) and set \(\bar v = -\frac{1}{\bar \lambda} A^T(A \bar x - \bar b)\). First, notice that when \(M = I\), the set \(\Lambda(\bar x, \bar v)\) defined in 9 reduces to \(\{\bar v\}\). By RoW?, 98?, \(N_{\mathcal{P}}(\bar v) = \mathrm{cone}\,\{p_i \;| \;i \in J(\bar v)\}\) for \(J(\bar v) = \{i \;| \;p_i^T\bar v = \beta_i\}\). From our choice of \(P\) and \(\beta\), this further simplifies to \(N_{\mathcal{P}}(\bar v) = \mathrm{cone}\,\{e_i \;| \;|\bar{v}_i| = 1\}\). Putting these facts together, we get that the Mordukhovich criterion ?? becomes \[\begin{align} \ker A \cap \mathrm{span}\,\{e_i \;| \;i \in J(\bar{v})\}=\{0\}. \end{align}\] This written as simply \[\begin{align} \ker A_{J(\bar v)} = \{0\}. \end{align}\] When this holds, we may apply 2 and obtain that \(S\) is (single-valued) directionally differentiable and locally Lipschitz at \((\bar b, \bar \lambda)\). Furthermore, by noticing that \(\{e_i \;| \;i \in J(\bar v) \}\) gives an orthonormal basis of \(\mathrm{span}\,N_{\mathcal{P}}(\bar v)\), we can obtain that the directional derivative in direction \((q, \alpha)\) given by \[\begin{align} S'(\bar b, \bar \lambda ; q, \alpha) = I_K\left((A_K^TA_K)^{-1} A_K^T (q + \frac{\alpha}{\bar \lambda}(A \bar{x}- \bar b)\right) \end{align}\] for some index set \(K = K(q, \alpha) \subseteq J(\bar v)\) and the Lipschitz modulus given by \[\begin{align} L \le \frac{1}{\sigma_{\min}(A_J)^2} \left(\sigma_{\max}(A_J) + \frac{1}{\bar \lambda} \lVert A_J^T (A \bar x - \bar b) \rVert\right). \end{align}\] Note that this agrees with the result in BBH?, 22?. \(\diamond\)
As discussed in 8, a \(\mathcal{C}^2\)-cone reducible function is twice epi-differentiable. However, a twice epi-differentiable may be not \(\mathcal{C}^2\)-cone reducible. In particular, convex piecewise linear-quadratic functions (in the sense of RoW?, 98?), which are twice epi-differentiable, are not necessarily \(\mathcal{C}^2\)-cone reducible, as shown in the following example.
Example 3. Let \(r^* : \mathbb{R}^2 \to \mathbb{R}\) be given by \[\begin{align} r^*(v_1, v_2) = v_1^2 + v_2^2 + |v_1v_2|=\begin{cases} v_1^2 + v_2^2 + v_1v_2, & \text{if }v_1,v_2\ge 0,\\ v_1^2 + v_2^2 - v_1v_2 & \text{if }v_1\le0,v_2\ge 0,\\ v_1^2 + v_2^2 + v_1v_2 & \text{if }v_1\le0,v_2\le 0,\\ v_1^2 + v_2^2 - v_1v_2 & \text{if }v_1\ge0,v_2\le 0.\\ \end{cases} \end{align}\] Thus, \(r^*\) is a convex piecewise linear-quadratic function; so is \(r\) by RoW?, 98?. Set \(\bar{v} = (0, 0)\) and note that \[\begin{align} \partial r^*(v_1, v_2) = \begin{cases} (2v_1 + v_2, 2v_2 + v_1) & \text{if } v_1v_2 > 0, \\ (2v_1 - v_2, 2v_2 - v_1) & \text{if } v_1v_2 < 0, \\ (2v_1, 2v_2) + [-|v_2|, |v_2|] \times \{0\} & \text{if } v_1 = 0, v_2 \not = 0, \\ (2v_1, 2v_2) + \{0\} \times [-|v_1|, |v_1|] & \text{if } v_2 = 0, v_1 \not = 0. \\ \end{cases} \end{align}\] This also implies that \(\partial r^* (0,0) = \{(0,0)\}\). Set \(\bar{x} = (0,0)\). Using the formula for the kernel of the generalized Hessian as a union of parallel subspaces (see RM?, 11?), we get \[\begin{align} \ker \partial^2 r(\bar{x}, \bar{v}) = \mathbb{R}\times \{0\} \cup \{0\} \times \mathbb{R}\not = \mathrm{par}\,\partial r^* (\bar{v}) = \{0\}. \end{align}\] Thus, \(r^*\) cannot be \(\mathcal{C}^2\)-cone reducible at \(\bar{v}\) by 4. \(\diamond\)
However, in some cases of \(r\) being piecewise linear-quadratic, we still have the relation that the kernel of the generalized Hessian of \(r\) is equal to the subspace parallel to \(\partial r^*\).
Definition 5 (Piecewise Linear-Quadratic Penalty). Let \(\mathcal{P}\subseteq \mathbb{R}^{n}\) be nonempty and polyhedral and let \(B \in \mathbb{R}^{n \times n}\) be symmetric positive semidefinite. The function \(\theta_{\mathcal{P},B}\) defined by \[\begin{align} \theta_{\mathcal{P},B}(x) = \sup_{z \in \mathcal{P}} \left\{x^Tz - \frac{1}{2} z^TBz \right\} \end{align}\] is called a piecewise linear-quadratic penalty. Note that \(\theta_{\mathcal{P},B}\) is proper, closed, and convex, and \(\theta_{\mathcal{P},B}^*(y) = \delta_{\mathcal{P}}(y) + \frac{1}{2} y^TBy\) for \(y\in \mathbb{R}^n\).
As \(\theta_{\mathcal{P},B}^*(y) = \delta_{\mathcal{P}}(y) + \frac{1}{2} y^TBy\), its epigraph is computed by \[\operatorname{epi} \theta_{\mathcal{P},B}^* =h^{-1}(\mathcal{P}\times\mathbb{R}_-)\;\; with\;\; h(y,r):=\left(y,\frac{1}{2}y^TBy-r\right).\] Since \(D h(y,r)=\begin{pmatrix} I& By\\ 0&-1\end{pmatrix}\) is surjective for any \((y,r)\in \mathbb{R}^n\times \mathbb{R}\) and the polyhedral set \(\mathcal{P}\times\mathbb{R}_-\) is \(\mathcal{C}^2\)-cone reducible, \(\operatorname{epi} \theta_{\mathcal{P},B}^*\) is also a \(\mathcal{C}^2\)-cone reducible set by [1], i.e., \(\theta_{\mathcal{P},B}^*\) is a \(\mathcal{C}^2\)-cone reducible function.
In what follows, \(r = \theta_{\mathcal{P},B}\circ M\) where \(M \in \mathbb{R}^{\ell \times n}\) and \(\theta_{\mathcal{P},B}\) is a piecewise linear-quadratic penalty, parameterized by a positive semidefinite matrix \(B \in \mathbb{S}^{\ell}_{+}\) and a polyhedral set \(\mathcal{P}\subseteq \mathbb{R}^{\ell}\). Although \(\theta_{\mathcal{P},B}^*\) is \(\mathcal{C}^2\)-cone reducible, it is not presently clear to us if \(r^*\) is \(\mathcal{C}^2\)-cone reducible. However, in 6 below, we show that the kernel of the generalized Hessian of the function \(r\) enjoys the formula ?? under a mild condition ?? in the next result.
Lemma 11 (Compactness constraint qualification). Let \(r = \theta_{\mathcal{P},B}\circ M\) and suppose the following condition holds: \[\begin{align} \label{eq:compactnessCQ} \mathcal{P}^{\infty} \cap \ker B \cap \ker M^T = \{0\} \end{align}\qquad{(14)}\] Then, for all \(\bar{v} \in \operatorname{rge}M^T\), the following set is nonempty and compact: \[\begin{align} \label{eq:Tv} T(v) := \operatorname{argmin}\{q_B(y) + \delta_{\mathcal{P}}(y) \;| \;M^Ty = v\} = \{y \;| \;r^*(v) = \theta_{\mathcal{P},B}^*(y)\} \end{align}\qquad{(15)}\]
Proof. Let \(v \in \operatorname{rge}M^T\). First, \(T(v)\) may be written as the \(\operatorname{argmin}\) of an unconstrained problem as follows:\[\begin{align} T(v) = \underset{\mathbb{Y}}{\operatorname{argmin}} \, \varphi_v \end{align}\] for \(\varphi_v(y) = q_B(y) + \delta_{\mathcal{P}}(y) + \delta_{(M^T)^{-1}\{v\}}(y)\). \(\varphi_v\) is proper, closed, and convex, so by AT?, 03?, nonemptiness and compactness of \(\operatorname{argmin}\varphi_v\) is equivalent to positivity of the horizon function \(\varphi_v^{\infty}(d)\) for all nonzero \(d\). The horizon function of \(\varphi_v\) can be computed to be \[\begin{align} \varphi_v^{\infty}(d) = \delta_{\ker B}(d) + \delta_{\mathcal{P}^{\infty}}(d) + \delta_{\ker M^T}(d) = \delta_{\ker B \cap \ker M^T \cap \mathcal{P}^{\infty}} (d), \end{align}\] which is equal to \(0\) if and only if \(d \in \ker B \cap \ker M^T \cap \mathcal{P}^{\infty}\). ◻
The condition ?? is very mild. In particular, it holds when either \(\mathcal{P}\) is a compact polyhedral set or \(M\) is a surjective map.
The following result shows that when \(r\) is a piecewise linear-quadratic penalty composed with a linear operator, we still have the aforementioned relation.
Theorem 6. Let \(r = \theta_{\mathcal{P},B}\circ M\). Let \((\bar{x}, \bar{v}) \in \operatorname{gph}\partial r\). Suppose ?? holds. Then \[\begin{align} \ker \partial^2 r(\bar{x} | \bar{v}) = \mathrm{par}\,\partial r^* (\bar{v}). \end{align}\]
Proof. According to the proof of RM?, 11?, for a sufficiently small neighborhood \(\mathcal{O}\) of \(\bar{v}\), we have \[\begin{align} \partial^2 r^* (\bar{v} | \bar{x})(0) = \bigcup\limits_{v \in \mathcal{O}} \mathrm{par}\,\partial r^*(v). \end{align}\] Because \(\partial^2 r^*(\bar{v} | \bar{x})(0)\) is a union of subspaces, we can write it as \(\ker \partial^2 r(\bar{x} | \bar{v})\). By shrinking the neighborhood to \(\mathcal{O} \cap \operatorname{rge}M^T\), we get \[\begin{align} \label{eq:parker} \mathrm{par}\,\partial r^*(\bar{v}) \subseteq \ker \partial^2 r(\bar{x} | \bar{v}) = \bigcup\limits_{v \in \mathcal{O} \cap \operatorname{rge}M^T} \mathrm{par}\,\partial r^* (v). \end{align}\tag{12}\] By RoW?, 98?, we have that \(r^*(v)\) is given by \[\begin{align} r^*(v) = (M^T \theta_{\mathcal{P},B}^*)(v) = \inf\{ \theta_{\mathcal{P},B}^*(y) \;| \;M^Ty = v\}. \end{align}\] Recall the set \(T(v)\) in ?? . Note that \(T\) is nonempty and compact-valued for all \(v \in \operatorname{rge}M^T\) by 11. We can write \(T(v)\) as \[\begin{align} \{y \;|\;M^Ty=v, 0 \in By + N_{\mathcal{P}}(y) + \operatorname{rge}M^T\}. \end{align}\] Observe that \(T(v)\) is the intersection of polyhedra, so \(T\) is polyhedral. By DoR?, 14?, \(T\) is outer Lipschitz continuous relative to its domain \(\operatorname{rge}M^T\). Thus, shrinking \(\mathcal{O}\) if necessary, we can obtain a (uniform) constant \(\kappa > 0\) such that \[\begin{align} \label{eq:TVV} T(v) \subseteq T(\bar{v}) + \kappa \lVert v - \bar{v} \rVert \mathbb{B} \text{ for all } v \in \mathcal{O} \cap \operatorname{rge}M^T. \end{align}\tag{13}\] For such a \(v\), NVV?, 25? guarantees that we may write \[\begin{align} \mathrm{par}\,\partial r^* (v) = M^{-1}(\mathrm{par}\,(\partial \theta_{\mathcal{P},B}^*(y) \cap \operatorname{rge}M)) \end{align}\] for every \(y \in T(v)\). We also have \[\begin{align} \mathrm{par}\,\partial \theta_{\mathcal{P},B}^*(y) = \mathrm{par}\,(N_{\mathcal{P}}(y) + By) = \operatorname{span} N_{\mathcal{P}}(y). \end{align}\] By polyhedrality of \(\delta_{\mathcal{P}}\), for every \(y \in T(v)\), there exists a neighborhood \(V_y\) of \(y\) such that \[\begin{align} N_{\mathcal{P}}(y') \subseteq N_{\mathcal{P}}(y) \text{ for every } y' \in V_y. \end{align}\] By compactness of \(T(\bar{v})\), there exist finitely many \(y_1,...,y_{\ell} \in T(\bar{v})\) such that \[\begin{align} T(\bar{v}) \subseteq \bigcup\limits_{i=1}^{\ell} V_{y_{i}} := V. \end{align}\] \(V\) is an open set containing \(T(\bar{v})\), so shrinking \(\mathcal{O}\) further if necessary, we can obtain \[\begin{align} T(\bar{v}) + \kappa \lVert v - \bar{v} \rVert \mathbb{B} \subseteq V \text{ for } v \in \mathcal{O} \cap \operatorname{rge}M^T. \end{align}\] This together with 13 tells us \(T(v) \subseteq V\) for any \(v \in \mathcal{O} \cap \operatorname{rge}M^T\), so for any \(y \in T(v)\), there is some \(i \in [\ell]\) such that \(y \in N_{y_{i}}\). Thus, we have \[\begin{align} \mathrm{par}\,\partial r^*(v) = M^{-1} (\mathrm{par}\,(N_{\mathcal{P}}(y) \cap \operatorname{rge}M)) \subseteq M^{-1} (\mathrm{par}\,(N_{\mathcal{P}}(y_i) \cap \operatorname{rge}M))\\ = \mathrm{par}\,\partial r^* (\bar{v}). \end{align}\] Combining this with 12 gives \[\begin{align} \label{eq:kerr} \ker \partial^2 r(\bar{x} | \bar{v}) = \mathrm{par}\,\partial r^* (\bar{v}) = M^{-1}(\mathrm{par}\,(N_{\mathcal{P}}(y) \cap \operatorname{rge}M)) \end{align}\tag{14}\] for any \(y \in T(\bar{v})\). ◻
Applying this to the least squares case, we obtain the following:
Theorem 7. Let \(r = \theta_{\mathcal{P},B}\circ M\) and suppose \(r\) satisfies the compactness qualification ?? . Let \(\mathcal{P}\) be parameterized as \(\{z \;| \;P^Tz \preceq \beta\}\) for \(P \in \mathbb{R}^{\ell \times k}\), \(\beta \in \mathbb{R}^{k}\), and let \(p_i\) refer to column \(i\) of \(P\). Let \(S : \mathbb{R}^{m \times n} \times \mathbb{R}^m \times \mathbb{R}_{++} \rightrightarrows \mathbb{R}^n\) be given by \[\begin{align} S(A, b,\lambda)= \underset{x \in \mathbb{R}^n}{\operatorname{argmin}} \left\{ \frac{1}{2} \lVert Ax-b \rVert^2 +\lambda r(x) \right\}. \end{align}\] Let \((\bar{A}, \bar{b}, \bar{\lambda}, \bar{x}) \in \operatorname{gph}S\) (i.e. \(\bar{x}\) solves 1 with parameters \(\bar{A}\), \(\bar{b}\), and \(\bar{\lambda}\) and regularizer \(r\)). Set \(\bar{v} = -\frac{1}{\bar{\lambda}} \bar{A}^T(\bar{A}\bar{x} - \bar{b})\). The condition that for some \(\bar y \in T(\bar v)\), we have \[\begin{align} \label{eq:CQPLQM} \ker \bar{A} \cap M^{-1}(\operatorname{span}\{p_i \;| \;i \in I(\bar{y})\}) = \{0\} \end{align}\qquad{(16)}\] where \(I(\bar{y}) = \{i \;| \;p_i^T \bar y = \beta_i\}\), is equivalent to any of the following conditions:
\(S\) is single-valued at \((\bar{A}, \bar{b}, \bar{\lambda})\).
\(S\) is locally Lipschitz at \((\bar{A}, \bar{b}, \bar{\lambda})\).
\(S\) is directionally differentiable at \((\bar{A}, \bar{b}, \bar{\lambda})\).
\(S\) is semismooth at \((\bar{A}, \bar{b}, \bar{\lambda})\).
Proof. Let \(\bar{x} \in S(\bar{A}, \bar{b}, \bar{\lambda})\). As was discussed in 4, the condition to apply 4 to the regularized least squares setting is \[\begin{align} \ker \bar{A} \cap \ker \partial^2 r(\bar x | \bar v) = \{0\}. \end{align}\] By the previous result, this is equivalent to \[\begin{align} \label{eq:PLQMpara} \ker \bar{A} \cap \mathrm{par}\,\partial r^*(\bar v) = \{0\}. \end{align}\tag{15}\] As discussed in the proof of 6, the object \(\mathrm{par}\,\partial r^* (\bar v)\) can be written as \(M^{-1}(\mathrm{span}\,N_{\mathcal{P}}(\bar y)\) for any \(\bar y \in T(\bar v)\). Also, by RoW?, 98?, \(N_{\mathcal{P}}(\bar y) = \mathrm{cone}\,\{p_i \;| \;i \in I(\bar y)\}\), so putting these facts together, we obtain that the condition to apply 4 is \[\begin{align} \ker \bar{A} \cap M^{-1}(\operatorname{span}\{p_i \;| \;i \in I(\bar{y})\}) = \{0\}. \end{align}\] This tells us that when this holds, \(S\) is (a) single-valued and (b) locally Lipschitz at \((\bar A, \bar b, \bar \lambda)\), and because \(r\) is piecewise linear-quadratic, by FGH?, 22?, \(\partial r\) is proto-differentiable at \((\bar{x}, \bar v)\), so \(S\) is also (c) directionally differentiable at \((\bar A, \bar b, \bar \lambda)\). By FGH?, 22?, \(\partial r\) is semismooth* at \((\bar x, \bar v)\), so \(S\) is semismooth* at \((\bar A, \bar b, \bar \lambda)\). Combining this with (c), we get that \(S\) is (d) semismooth at \((\bar A, \bar b, \bar \lambda)\). On the other hand, (b)-(d) all imply (a), which by CHNS?, 26? is equivalent to 15 which as established, is equivalent to ?? ◻
In the case that \(M = I\), we have a closed-form expression for the directional derivative and Lipschitz constant of \(S\):
Corollary 3. Let \(S : \mathbb{R}^m \times \mathbb{R}_{++} \rightrightarrows \mathbb{R}^n\) be given by \[\begin{align} S(b, \lambda) = \underset{x \in \mathbb{R}^n}{\operatorname{argmin}} \left\{ \frac{1}{2} \lVert Ax - b \rVert^2 + \lambda \theta_{\mathcal{P},B}(x) \right\}. \end{align}\] Let \(\bar x \in S(\bar b, \bar \lambda)\) and set \(\bar v = - \frac{1}{\bar \lambda}A^T(A\bar{x}- \bar b)\). Note that under this setup, the assumption in [CCQ] is automatically satisfied. In this case, the Mordukhovich criterion simplifies to \[\begin{align} \label{eq:CQsimple2} \ker A \cap \operatorname{span}\{p_i \;| \;i \in I(\bar{v})\} \end{align}\qquad{(17)}\] where \(I(\bar{v}) = \{i \;| \;p_i^T \bar y = \beta_i\}\). Then, if ?? holds, we have the following:
\(S\) is directionally differentiable at \((\bar{b}, \bar{\lambda})\), and for every direction \((q, \alpha)\), there exists a matrix \(U\) with orthonormal columns such that the directional derivative in direction \((q, \alpha)\) is given by \[\begin{align} (H^{-1}BA^T + U[(AHU)^T (AU)]^{-1} (AHU)^{T} (I - AH^{-1}BA^T)) \left(q + \frac{\alpha}{\bar{\lambda}}(A \bar{x} - \bar{b})\right) \end{align}\] for \(H = I + \frac{1}{\bar \lambda} BA^TA\).
\(S\) is single-valued and locally Lipschitz around \((\bar{b}, \bar{\lambda})\), and the modulus of Lipschitz continuity can be bounded by \[\begin{align} L \le \max_{U' \in \mathcal{V}} \left\lVert (H^{-1}BA^T + U'[(AH U')^T (AU')]^{-1} (AH U')^{T} (I - AH^{-1}BA^T)) \left(\bar q - \frac{\bar \alpha}{\bar \lambda}(A \bar x - \bar b)\right) \right\rVert \end{align}\] for \(\mathcal{V}:=\{V\in \mathbb{R}^{n\times r} \;| \;V^TV=I, r\le |I(\bar v)|\}\).
Proof. By 4, at a point \((\bar{b}, \bar{\lambda}, \bar{x}) \in \operatorname{gph}S\) such that ?? holds, we have that \(S\) is directionally differentiable, 4 tells us that the directional derivative in direction \((q, \alpha)\) given by \(S'(\bar{b}, \bar{\lambda}; q, \alpha) = w\) for the unique \(w\) such that \[\begin{align} \label{eq:0DG} 0 \in D G(\bar{b}, \bar{\lambda}, \bar{x} | 0)(q, \alpha, w), \end{align}\tag{16}\] where \(G(b, \lambda, x) = \frac{1}{\lambda} A^T(Ax - b) + \partial \theta_{\mathcal{P},B}(x)\). By 2(a) this is equivalent to \[\begin{align} \frac{1}{\bar{\lambda}} A^T(q + \frac{\alpha}{\bar{\lambda}}(A \bar{x} - \bar{b}) - Aw) \in D \partial \theta_{\mathcal{P},B}(\bar{x} | \bar{v})(w). \end{align}\] Set \(z := \frac{1}{\bar{\lambda}} A^T(q + \frac{\alpha}{\bar{\lambda}}(A \bar{x} - \bar{b}) - Aw)\). Applying the inversion formula for graphical derivatives RoW?, 98?, this can be written as \[\begin{align} w \in D(\partial \theta_{\mathcal{P},B}^*)(\bar{v} | \bar{x})(z) = D(N_{\mathcal{P}} + B)(\bar{v} | \bar{x})(z) = D N_{\mathcal{P}} (\bar{v} | \bar{x} - B \bar{v})(z) + Bz \\ \iff w - Bz \in D N_{\mathcal{P}} (\bar{v} | \bar{x} - B \bar{v})(z). \end{align}\] Let \(\mathcal{K} := T_{\mathcal{P}}(\bar{v}) \cap \{\bar{x} - B\bar{v}\}^{\bot}\) being the critical cone of \(\mathcal{P}\) at \(\bar v\) for \(\bar{x} - B\bar{v}\). By RoW?, 98?, we can write the graphical derivative of the normal cone as follows: \[\begin{align} w - Bz \in N_{\mathcal{K}}(z) = N_{T_{\mathcal{P}}(\bar{v})}(z) + N_{\{\bar{x} - B \bar{v}\}^{\bot}}(z). \end{align}\] So \(z \in T_{\mathcal{P}}(\bar{v})\) and \(z^T(\bar{x} - B \bar{v}) = 0\). These can be written as \[\begin{align} &N_{T_{\mathcal{P}}(v)}(z) = \operatorname{cone} \{p_i \;| \;i \in I(\bar{v}), p_i^Tz = 0\},\\ &N_{\{\bar{x} - B \bar{v}\}^{\bot}}(z) = \operatorname{span}\{\bar{x} - B \bar{v}\}. \end{align}\] It follows that \[w - Bz \in \operatorname{cone} \{p_i \;| \;i \in I(\bar{v}), \;p_i^Tz = 0\} + \operatorname{span}\{\bar{x} - B \bar{v}\}.\] Using a similar argument to the proof of Corollary 2, let \(J := \{i \in I(\bar{v}) \;| \;p_i^Tz = 0\}\). The fact that \(\bar{v} \in \partial \theta_{\mathcal{P},B}(\bar{x}) = (N_{\mathcal{P}} + B)^{-1}(\bar{x})\) gives us \[\bar{x} - B \bar{v} \in N_{\mathcal{P}}(\bar{v}) = \operatorname{cone}\{p_i \;| \;i \in I(\bar{v})\}.\] We claim that in fact \(\bar{x} - B \bar{v} \in \operatorname{cone} \{p_i \;| \;i \in J\}\). Indeed, as \(\bar{x} - B \bar{v}\) can be written as \(\sum_{i \in I(\bar{v})} \gamma_i p_i\) for \(\gamma_i \ge 0\), we have \[\begin{align} 0 = z^T(\bar x-B\bar{v})=\sum\limits_{i \in I(\bar{v})} \gamma_i p_i^Tz = \sum\limits_{i \in J} \gamma_i \underbrace{p_i^Tz}_{ = 0} + \sum\limits_{i \in I(\bar{v}) \setminus J} \gamma_i \underbrace{p_i^Tz}_{< 0}. \end{align}\] So \(\gamma_i = 0\) for \(i \not \in J\). This clarifies the claim. It follows that \[\begin{align} w - Bz \in \operatorname{cone}\{p_i \;| \;i \in J\} + \operatorname{span}\{\bar{x} - B \bar{v}\} \subseteq \operatorname{span}\{p_i \;| \;i \in J\} + \operatorname{span}\{p_i \;| \;i \in J\} \\ = \operatorname{span}\{p_i \;| \;i \in J\}. \end{align}\]
Let \(E := \operatorname{span}\{p_i\;|\;i \in J\}\). We have that \(w - Bz \in E\) and \(z \in E^{\bot}\). Let \(\bar{u} := - \frac{1}{\bar{\lambda}}(A \bar{x} - \bar{b})\), \(H := I + \frac{1}{\bar{\lambda}} BA^{T} A\), and \(h := -\frac{1}{\bar{\lambda}} BA^{T}(q - \alpha \bar{u})\). Recall that \(z = \frac{1}{\bar{\lambda}} A^T(q + \frac{\alpha}{\bar{\lambda}}(A \bar{x} - \bar{b}) - Aw)\). Thus we can rewrite \(w - Bz\) as follows: \[\begin{align} &w - Bz = w - \frac{1}{\bar{\lambda}}BA^{T}(q - \alpha \bar{u} - Aw) = \\ &w + \frac{1}{\bar{\lambda}} BA^{T} Aw - \frac{1}{\bar{\lambda}} BA^{T} (q - \alpha \bar{u}) = Hw + h \end{align}\] Note that \(H\) is invertible by 5. As \(Hw + h \in E\), we have \(w + H^{-1}h \in H^{-1}(E)\). Let \(\begin{bmatrix} u_1 \ldots u_r \end{bmatrix} = U\) be an orthonormal basis of \(H^{-1}(E)\). Since \(J\subset I(\bar v)\), the qualification condition ?? implies that \(\ker A \cap E = \{0\}\) with \(r=|J|\), the cardinality of \(J\). Moreover, the fact that \(z \in E^{\bot}\) gives us \(H^Tz \in H^T(E^{\bot}) \overset{\eqref{lem:Sub}}{=} (H^{-1}(E))^{\bot}\), so \(U^TH^Tz = 0\). We can rewrite this as \((AHU)^T(q - \alpha \bar{u} - Aw) = 0\), which gives \[\begin{align} (AHU)^T Aw = (AHU)^T (q - \alpha \bar{u}). \end{align}\] Adding \((AHU)^T AH^{-1}h\) to both sides and using the fact \(UU^T\) is the orthogonal projection onto \(H^{-1}(E)\), we obtain \[\begin{align} (AHU)^{T} (q - \alpha \bar{u} + AH^{-1}h) = (AHU)^{T} A UU^{T}\underbrace{(w + H^{-1}h)}_{\in H^{-1}(E)}. \end{align}\] By Lemma 6, \((AHU)^T AU\) is invertible. We can then write \[\begin{align} & U^T(w + H^{-1}h) = [(AHU)^T (AU)]^{-1} (AHU)^{T} (q - \alpha \bar{u} + AH^{-1}h) \end{align}\] and isolate \(w\) as follows: \[\begin{align} w = -H^{-1}h + U[(AHU)^T (AU)]^{-1} (AHU)^{T} (q - \alpha \bar{u} + AH^{-1}h). \end{align}\] Plugging back in the definition of \(h\), this yields \[\begin{align} w = (H^{-1}BA^T + U[(AHU)^T (AU)]^{-1} (AHU)^{T} (I - AH^{-1}BA^T)) (q - \alpha \bar{u}), \end{align}\] which verifies the formula of directional derivative of \(S\) at \((\bar b,\bar \lambda)\) at \((q,\alpha)\) in (i).
To verify (ii), we first notice that ?? holds locally around \((\bar{b}, \bar{\lambda}, \bar{x})\). Indeed, let \(\{(b_k, \lambda_k, x_k)\} \subseteq \operatorname{gph}S\) be a sequence converging to \((\bar{b}, \bar{\lambda}, \bar{x})\). Set \(v_k := - \frac{1}{\lambda_k} A^T(Ax_k - b_k)\). For \(k\) sufficiently large, we have \(I(v_k) \subseteq I(\bar{v})\), so for such \(k\) we have \[\begin{align} \ker A \cap \operatorname{span} \{p_i \;| \;i \in I(v_k)\} \subseteq \ker A \cap \operatorname{span} \{p_i \;| \;i \in I(\bar{v})\} = \{0\}. \end{align}\] This establishes that for \((b, \lambda)\) sufficiently close to \((\bar{b}, \bar{\lambda})\), \(S\) is directionally differentiable. Because we eventually have the containment \(I(v_k) \subseteq I(\bar{v})\), the formula for the directional derivative holds for \((b, \lambda)\) close enough to \((\bar{b}, \bar{\lambda})\) (if we replace \(\bar{\lambda}\) for \(\lambda\) and \(b\) for \(\bar{b}\)).
When ?? holds at \((\bar{b}, \bar{\lambda}, \bar{x}) \in \operatorname{gph}S\), we have that \(S\) is locally Lipschitz at \((\bar{b}, \bar{\lambda})\) with modulus \[\begin{align} L \le \limsup_{(b, \lambda) \to (\bar{b}, \bar{\lambda})} \max_{\lVert (q, \alpha) \rVert \le 1} \lVert S'(b, \lambda ; q, \alpha) \rVert. \end{align}\] Let \(\{(b_k, \lambda_k)\}\) be a sequence converging to \((\bar b, \bar \lambda)\) such that \[\begin{align} L \le \lim_{k \to \infty} \max_{(q, \alpha) \in \mathbb{B}} \lVert S'(b_k, \lambda_k ; q, \alpha) \rVert. \end{align}\] We may also choose a corresponding sequence \(\{(q_k, \alpha_k)\} \subseteq \mathbb{B}\) such that \[\begin{align} L \le \lim_{k \to \infty} \lVert S'(b_k, \lambda_k ; q_k, \alpha_k) \rVert. \end{align}\] Let \(\{x_k \in S(b_k, \lambda_k)\}\) such that \(x_k \to \bar{x}\). For \(k\) sufficiently large, we have that \((b_k, \lambda_k)\) are in a neighborhood of \((\bar b, \bar \lambda)\) such that ?? holds, so by the same arguments as in the proof for (i), we can define \(H_k := I + \frac{1}{\lambda_k}BA^TA\), and we have that for the direction \((q_k, \alpha_k)\) there exists a subspace \(E_k\) and matrix with orthonormal columns \(U_k\in \mathbb{R}^{n\times r_k}\) with \(\operatorname{rge}U_k = H_k^{-1}(E_k)\) and \(r_k\le|I(v_k)|\le |I(\bar v)|\) such that the directional derivative of \(S\) at \((b_k, \lambda_k)\) in direction \((q_k, \alpha_k)\) is given by \[\begin{align} &S'(b_k, \lambda_k ; q_k, \alpha_k) = \\ &(H_k^{-1}BA^T + U_k[(AH_kU_k)^T AU_k]^{-1}(AH_kU_k)^T (I - AH_k^{-1}BA^T))(q_k - \frac{\alpha_k}{\lambda_k}(Ax_k - b_k)). \end{align}\] The sequence \(\{(q_k, \alpha_k)\} \subseteq \mathbb{B}\) is bounded, so we can assume without loss of generality that it converges to some \((\bar q, \bar \alpha)\) and \(r_k=r\). Also, every \(U_k\in \mathbb{R}^{n\times r}\) satisfies \(U_k^TU_k = I\), so the sequence \(\{U_k\}\) is bounded, and therefore we can also assume it converges to some \(\bar U\in \mathbb{R}^{n\times r}\) such that \(\bar U^T \bar U = I\). Then, passing to the limit and upper bounding by taking a maximum over the space of \(n \times r\) matrices satisfying \(V^TV = I\), we get \[\begin{align} &L \le \left\lVert (H^{-1}BA^T + \bar{U}[(AH \bar{U})^T (A \bar{U})]^{-1} (AH \bar{U})^{T} (I - AH^{-1}BA^T)) \left(\bar q - \frac{\bar \alpha}{\bar \lambda}(A \bar x - \bar b)\right) \right\rVert \\ & \le \max_{U' \in \mathcal{V}_{n,r}} \left\lVert (H^{-1}BA^T + U'[(AH U')^T (AU')]^{-1} (AH U')^{T} (I - AH^{-1}BA^T)) \left(\bar q - \frac{\bar \alpha}{\bar \lambda}(A \bar x - \bar b)\right) \right\rVert \end{align}\] where \(\mathcal{V}_{n,r} := \{V \in \mathbb{R}^{n \times r}\;| \;V^TV = I\}\), which is compact. Finally, we take a maximum over \(\mathcal{V} := \{V \in \mathbb{R}^{n \times r} \;| \;V^TV = I, \;r \le |I(\bar v)|\}\) to obtain \[\begin{align} L \le \max_{U' \in \mathcal{V}} \left\lVert (H^{-1}BA^T + U'[(AH U')^T (AU')]^{-1} (AH U')^{T} (I - AH^{-1}BA^T)) \left(\bar q - \frac{\bar \alpha}{\bar \lambda}(A \bar x - \bar b)\right) \right\rVert. \end{align}\] ◻
Remark 7. Again, as with 2, we could have stated this result for the least squares problem parameterized by \((A, b, \lambda)\) instead of \((b, \lambda)\), but we have stated a simpler result due to space and legibility constraints. We could also have stated 7 for the setting where a (locally) twice continuously differentiable convex function \(\varphi\) is used for data fidelity, in which case ?? reads \[\begin{align} \ker \bar{A}^T\nabla^2 \varphi(\bar{A} \bar{x}- \bar b)\bar{A} \cap M^{-1}(\mathrm{span}\,\{p_i \;| \;i \in I(\bar y)\}) = \{0\}. \end{align}\]
In this paper, we studied stability properties of solution mappings associated with convex regularized least-squares problems through a variational-analytic framework. Our approach combines an implicit-function perspective for monotone generalized equations with second-order tools from generalized differentiation, leading to conditions for local Lipschitz continuity, directional differentiability, and semismoothness of the associated solution maps.
A central aspect of the analysis was the relationship between generalized Hessians and the geometry of the subdifferential of the conjugate regularizer. In particular, for conjugate \(\mathcal{C}^2\)-cone reducible regularizers, we showed that the kernel of the generalized Hessian admits a tractable characterization in terms of the parallel subspace of the subdifferential. This allows one to replace difficult second-order calculations by more explicit first-order geometric conditions.
Our framework applies to a broad range of regularizers arising in optimization, statistics, and machine learning, including weighted polyhedral support functions and piecewise linear-quadratic penalties. In addition to qualitative stability results, we also derived quantitative sensitivity estimates and explicit formulas for directional derivatives in structured settings.
Several directions remain open for future research:
A natural question is to extend the family of regularizers that satisfy the generalized Hessian expression ?? beyond the ones given here so that the implicit function theorem from 3 can be readily applied.
The semismoothness results for the optimal solution maps in 5 beg the question if explicit formulae for the Clarke Jacobians of said solution maps can be computed. This would be appealing for semismooth Newton methods.
In 5.2, we discuss that it is presently unclear whether the composition of a PLQ penalty with a linear map is conjugate \(\mathcal{C}^2\)-cone reducible. A positive answer would make the compactness ?? redundant. We would like to resolve this question in the future.
The first author would like to thank Ebrahim Sarabi (Miami Unversity) for fruitful discussions about material related to this work.
i.e. \(S(x)\) is a convex set for all \(x \in \mathbb{R}^n\).↩︎
\(\partial_C F(x):=\mathrm{conv}\,\left\{V\,\left\vert\; \exists \{x_k\in D_F \}\to x: DF(x_k)\to V\right.\right\}\) where \(D_F\) is the set of differentiability of \(F\).↩︎
In fact, we only require \(\Psi\) to be metrically subregular* at the point in question (see DoR?, 14?)*↩︎
i.e., \(S'(\bar x;d):=\lim_{t\downarrow 0}\frac{S(\bar x+td)}{t}\) exists for all \(d\in \mathbb{R}^d\).↩︎
Note that a single-valued continuous monotone map is maximally monotone, see, e.g., RoW?, 98?.↩︎
A cone \(K\) is called poined if \(K\cap (-K)=\{0\}\).↩︎