Lipschitz continuity of solution multifunctions of extended $\ell_{1}$
regularization problems

Kaiwen Meng

School of Mathematics, Southwestern University of Finance and Economics,
Chengdu 611130, China
Email<EMAIL_ADDRESS>
Pengcheng Wu

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong
Kong
Email<EMAIL_ADDRESS>
Xiaoqi Yang
Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong
Kong
Email<EMAIL_ADDRESS>
Abstract
In this paper we obtain a verifiable sufficient condition for a polyhedral
multifunction to be Lipschitz continuous on its domain. We apply this
sufficient condition to establish the Lipschitz continuity of the solution
multifunction for an extended $\ell_{1}$ regularization problem with respect
to the regularization parameter and the observation parameter under the
assumption that the data matrix is of full row rank. In doing so, we show that
the solution multifunction is a polyhedral one by expressing its graph as the
union of the polyhedral cones constructed by the index sets defined by
nonempty faces of the feasible set of an extended dual $\ell_{1}$
regularization problem. We demonstrate that the domain of the solution
multifunction is partitioned as the union of the projections of the above
polyhedral cones onto the parameters space and that the graph of the
restriction of the multifunction on each of these projections is convex. In
comparing with the existing result of the local Lipschitz continuity of the
Lasso problem in the literature where certain linear independence condition
was assumed, our condition (i.e., full row rank of data matrix) is very weak
and our result (i.e., Lipschitz continuity on the domain) is much more
stronger. As corollaries of the Lipschitz continuity of the solution
multifunction, we show that the single-valuedness and linearity (or piecewise
linearity) of the solution multifunction on a particular polyhedral set of the
domain are equivalent to certain linear independence conditions of the
corresponding columns of the data matrix proposed in the literature.

Keywords: polyhedral multifunction, $\ell_{1}$ regularization problem,
solution multifunction, face, Lipschitz continuity

MSC:  65K05 90C25 90C31

##  1 Introduction

Let $A$ be an $m\times n$ data matrix of full row rank. The following sparse
optimization problem has been proposed in machine learning and compressed
sensing to find the sparest solution for a system of linear equations:

$\min_{x\in\mathbbm{R}^{n}}\;\|x\|_{0}\quad\mbox{subject to}\quad Ax-b=0,$ (1)

where $\|x\|_{0}$ is the $\ell^{0}$-norm of vector $x$, denoting the number of
nonzero components of $x$. This problem is known to be NP-hard [6]. To find an
approximate sparse solution of the problem (1), the following convex
optimization problems, called Basis Pursuit (BP) and Lasso (or $\ell_{1}$
regularization problem) respectively, have been investigated:

$\min_{x\in\mathbbm{R}^{n}}\;\|x\|_{1}\quad\mbox{subject to}\;Ax-b=0,$ (2)
$\min_{x\in\mathbbm{R}^{n}}\;\lambda\|x\|_{1}+\frac{1}{2}\|Ax-b\|^{2}\quad\mbox{
with }\lambda>0.$ (3)

The Basis Pursuit problem (2) and Lasso problem (3) have attracted extensive
attention from optimization, statistics and computer science communities and
have been accepted as two of the most useful approximate models for problem
(1) (see Tibshirani [22], Candes et al. [4] and Donoho [5] and the references
therein). Many effective algorithms have been designed for solving problems
(2) and (3). However the study of stability properties of the optimal
solutions of (2) and (3) is very limited. The recovery bound or so-called
relative upper Lipschitz property of optimal solutions of problem (3) with
respect to parameter $\lambda$ only was obtained under various assumptions
such as restricted isometric property and restricted eigenvalue condition on
data matrix $A$. Only recently Berk et al. [3] established local Lipschitz
continuity and smoothness properties of the optimal solution of the Lasso
problem (3) with $(\lambda,b)\in\mathbbm{R}_{++}\times\mathbbm{R}^{m}$, where
the coderivative and variational analysis tools have been employed in their
study and in particular the authors established in [3, Theorem 4.13 (a)] the
local Lipschitz continuity property under a condition proposed in [22] as a
sufficient condition for the uniqueness of the optimal solution of the Lasso.

In this paper, to investigate the Lipschitz continuity in terms of parameters
$(\lambda,b)\in\mathbbm{R}_{+}\times\mathbbm{R}^{m}$ of the optimal solutions
of problems (2) and (3) in a unified way, we consider the following extended
$\ell_{1}$ regularization problem:

$\min_{x\in\mathbbm{R}^{n}}\;\|x\|_{1}+\frac{1}{2\lambda}\|Ax-b\|^{2},$ (4)

where, in comparing with $\ell_{1}$ regularization problem (3), $\lambda=0$ is
allowed. Indeed, for $\lambda>0$, the problem (3) and problem (4) have the
same set of optimal solutions and for $\lambda=0$, problem (2) can be viewed
as the problem (4) from the view point of penalization. Let us define the
multifunction
$S:\mathbbm{R}_{+}\times\mathbbm{R}^{m}\rightrightarrows\mathbbm{R}^{n}$ as
the optimal solution set of the extended $\ell_{1}$ regularization problem
(4). As the function $\|\cdot\|_{1}$ is coercive and the linear equation
$Ax-b=0$ always has a solution due to $A$ being of full row rank, the
multifunction $S$ is always nonempty, that is,

$\operatorname*{dom}S=\mathbbm{R}_{+}\times\mathbbm{R}^{m}.$

Furthermore, by virtue of first-order optimality conditions, we get

$S(\lambda,b)=\left\\{\begin{array}[]{ll}\left\\{x\in\mathbbm{R}^{n}\mid
Ax-b=0,\;0\in\operatorname*{rge}A^{\top}+\partial\|\cdot\|_{1}(x)\right\\}&\mbox{if}\;\lambda=0,\,b\in\mathbbm{R}^{m},\\\\[2.84544pt]
\left\\{x\in\mathbbm{R}^{n}\mid 0\in
A^{\top}(Ax-b)+\lambda\partial\|\cdot\|_{1}(x)\right\\}&\mbox{if}\;\lambda>0,\,b\in\mathbbm{R}^{m}.\end{array}\right.$
(5)

We also consider the Lipschitz continuity of the following dual problem
(called extended dual $\ell_{1}$ regularization problem):

$\max_{y\in\mathbbm{R}^{m}}\;\langle
b,y\rangle-\frac{1}{2}\lambda\|y\|^{2}\quad\mbox{subject to}\;y\in
Y^{0}:=\\{y\in\mathbbm{R}^{m}\mid\|A^{\top}y\|_{\infty}\leq 1\\}.$ (6)

According to the Fenchel-type duality scheme [20, Example 11.41], the duals of
the BP problem (2) and the LASSO problem in the form of (4) correspond to the
extended dual $\ell_{1}$ regularization problem (6) with $\lambda=0$ and with
$\lambda>0$, respectively. Hence (6) is the dual of the problem (4). In fact
the dual feasible set $Y^{0}$ will play an important role in our study of the
Lipschitz continuity of $S$.

Stability properties of multifunctions have extensively been investigated, see
[1, 7, 24, 20, 9, 16] and the references therein. Robinson [18] obtained the
local upper Lipschitz continuity of a polyhedral multifunction (i.e., its
graph is expressed as the union of finitely many polyhedral sets). Mangasarian
and Shiau [15] established the Lipschitz continuity for solutions of linear
inequalities, linear programs and certain linear complementarity problems.
Rockafellar and Wets [20, Example 9.35] (see also Walkup and Wets [23])
obtained the Lipschitz continuity for a multifunction with graph being one
polyhedron. In [12] Han and Pang derived the (Lipschitz) continuous (single-
valued) solution function of parametric variational inequalities under
functional and constraint perturbations. Mordukhovich et al. [17] established
characterizations of the single-valuedness and local Lipschitz continuity of
the local optimal solutions for parametric second-order cone programs. Beer et
al. [2] analyzed the Lipschitz modulus of the feasible set of linear and
convex inequality systems. Under a strong regularity assumption Guo and Xu
[11] obtained the Lipschitz continuity of isolated solutions of perturbed
stochastic generalized equations around the given point. It is worth noting
that for a polyhedral multifunction with convex domain, Gowda and Sznajder
[10] showed that it is Lipschitz continuous on the domain if and only if the
inverse of the multifunction is open. This seemly complete characterization of
Lipschitz continuity may not be easily applied, as the verification of the
openness of the inverse of the multifunction can be as difficult as verifying
the Lipschitz continuity of the multifunction itself.

In this paper we will employ face theory and polyhedral theory to establish
the Lipschitz continuity of the optimal solution multifunction $S$ of problem
(4). For this purpose, we first obtain a verifiable sufficient condition for
polyhedral multifunctions to be Lipschitz continuous on its domain by imposing
two assumptions: the first one is that its domain is convex and the second one
is that the graph of the restriction of the multifunction on the projection of
each of the polyhedral sets (in the polyhedral multifunction decomposition)
onto the variable space is convex. The convexity assumption of the domain
allows one to connect any two points in the domain by a straight line, while
this straight line can be divided into a finite number of line segments and
each line segment lies in one of the polyhedral sets on which the
multifunction is Lipschitz continuous, as the result of the second assumption.
The Lipschitz continuity of the multifunction on its domain is acquired by
that of these arbitrary line segments with a Lipschitz constant being the
maximum of the Lipschitz constants corresponding to the finitely many
polyhedral sets. We apply the sufficient condition to establish the Lipschitz
continuity of optimal solution multifunction $S$ of extended $\ell_{1}$
regularization problem (4) on its domain only under the assumption that $A$ is
of full row rank. This full row rank assumption is very weak, which is almost
universally used as a basic assumption in the study of theory and algorithms
for problems (2) and (3). Therefore our results are very general.

In our approach, we employ non-empty faces of the polyhedral feasible set
$Y^{0}$ of the dual problem (6) to construct some partitions of index set
$I:=\\{1,\cdots,n\\}$ of the variable space. We show that the graph of $S$ is
expressed as the union of some polyhedral cones which are constructed by these
index partitions of $I$. Thus $S$ is verified to be a polyhedral
multifunction. Moreover, we establish that the domain of the solution
multifunction $S$ is partitioned as the union of the projections of the above
polyhedral cones onto the parameters space. We then prove that the graph of
the restriction of $S$ on each of these projections is convex, where we employ
the single-valuedness property of the mapping $(\lambda,b)\to Ax$ on the
solution set $S(\lambda,b)$ as established in [25]. We obtain the Lipschitz
continuity of $S(\lambda,b)$ on its convex domain by applying the established
sufficient condition.

As corollaries of the Lipschitz continuity of multifunction $S$ in (5), we
obtain some properties for structures of $S$. Although we have already know
that $S$ is a polyhedral multifunction, the explicit structure of $S$ is not
known yet. By applying the Lipschitz continuity of $S$, we obtain the explicit
representation of $S(\lambda,b)$ as the intersection of finitely many half-
spaces by virtue of non-empty faces of the dual feasible set $Y^{0}$.
Moreover, for a given face of the dual feasible set $Y^{0}$ such that the
columns of $A$ identified by certain index set is linearly independent (or
equivalently a condition used in [25]), we show that $S$ is single-valued and
linear on the polyhedral set constructed by the face. We further show that $S$
is piecewise linear (resp. linear) around the given point if and only if
certain strengthened linear independence condition at the point proposed in
[22] (resp. [8]) holds. As consequences, we obtain the directional
differentiability and differentiability illustrated in [3] as special cases.

Throughout the paper we use the standard notations of variational analysis;
see the seminal book [20] by Rockafellar and Wets. The Euclidean
$\ell_{2}$-norm, $\ell_{1}$-norm and $\ell_{\infty}$-norm of a vector
$x\in\mathbbm{R}^{n}$ are denoted by $||x||$, $\|x\|_{1}$ and $\|x\|_{\infty}$
respectively. Let ${\mathbb{B}}$ denote the closed unit Euclidean ball,
$\mathbb{R}_{+}:=[0,\infty)$ and $\mathbb{R}_{++}:=(0,\infty)$. For
$x,y\in\mathbb{R}^{n}$, we define
$[x,y]:=\\{x+\theta(y-x)\mid\theta\in[0,1]\\}$ and
$(x,y):=\\{x+\theta(y-x)\mid\theta\in(0,1)\\}$.

Let $A$ be an $m\times n$ matrix, $x\in\mathbb{R}^{n}$, $i\in I$ and $K\subset
I$. We denote that $A_{i}$ is the $i$th column of $A$ and
$A_{K}\in\mathbb{R}^{m\times|K|}$ is the submatrix of $A$ consisting of all
$A_{i}$’s with $i\in K$. We also denote that $x_{K}\in\mathbb{R}^{|K|}$ is the
subvector of $x$ consisting of all $x_{i}$’s with $i\in K$.

Let $C\subset\mathbbm{R}^{n}$. We denote the interior, the relative interior,
the boundary, the closure and the affine set of $C$ respectively by
$\operatorname*{int}C$, $\operatorname*{ri}C$, $\operatorname*{bdry}C$,
$\operatorname*{cl}C$ and $\operatorname*{aff}C$.

A polyhedral set $C$ is defined as the intersection of a finite family of
closed half-spaces in $\mathbbm{R}^{n}$, i.e., as the set of solutions to some
finite system of inequalities of the form

$\alpha_{j}^{\top}x\leq\beta_{j},\quad j=1,\cdots,k,$ (7)

for $\alpha_{1},\cdots,\alpha_{k}\in\mathbb{R}^{n}$ and
$\beta_{1},\cdots,\beta_{k}\in\mathbb{R}$. For a nonempty subset $F$ of
polyhedral set $C$, $F$ is said to be a face of $C$ if there exists a vector
$v\in\mathbbm{R}^{n}$ (possibly $v=0$) such that

$F=\operatorname*{arg\,max}\\{\;v^{\top}x\mid x\in C\\}.$

The zero-dimensional faces of $C$ are called the extreme points of $C$ and the
collection of all such points is denoted as $\operatorname*{extr}(C)$. In
general, if $F$ is a half-line face of $C$, we shall call the direction of $F$
an extreme direction of $C$. Moreover, we deduce from [21, Page 101] that $F$
is a nonempty face of $C$ represented by (7) if and only if there exists
$J\subset\\{1,\cdots,k\\}$ such that

$F=\\{x\in C\mid\alpha_{j}^{\top}x=\beta_{j}\quad\forall j\in
J\\}\not=\emptyset.$

For a multifunction $G:\mathbbm{R}^{n}\rightrightarrows\mathbbm{R}^{m}$, we
denote by

$\operatorname*{gph}G:=\\{(x,y)\mid y\in
G(x)\\},\quad\operatorname*{dom}G:=\\{x\mid
G(x)\not=\emptyset\\}\quad\mbox{and}\quad\operatorname*{rge}G:=\\{y\mid\exists
x\in\operatorname*{dom}G~{}\mbox{s.t.}~{}y\in G(x)\\}$

the graph, the domain and the range of $G$, respectively. For a set
$\Omega\subset\mathbbm{R}^{n}$, we denote by

$G|_{\Omega}(x):=\left\\{\begin{array}[]{ll}G(x)&\mbox{if}\;x\in\Omega,\\\\[5.69046pt]
\emptyset&\mbox{if}\;x\not\in\Omega,\end{array}\right.$

the multifunction of $G$ restricted on $\Omega$. It is clear to see that

$\operatorname*{gph}G|_{\Omega}=\operatorname*{gph}G\cap(\Omega\times\mathbbm{R}^{m})\quad\mbox{and}\quad\operatorname*{dom}G|_{\Omega}=\Omega\cap\operatorname*{dom}G.$

A multifunction $G:\mathbbm{R}^{n}\rightrightarrows\mathbbm{R}^{m}$ is said to
be a polyhedral one if its graph is the union of finitely many polyhedra in
$\mathbb{R}^{n}\times\mathbb{R}^{m}$. Moreover, for a polyhedral multifunction
$G$, if it is further single-valued, we called it a piecewise linear function.
Let $G:\mathbbm{R}^{n}\to\mathbbm{R}^{m}$ be single-valued. We say that $G$ is
linear if there exists some matrix $B\in\mathbbm{R}^{m\times n}$ such that
$G(x)=Bx$ and that $G$ is linear on some nonempty subset $D$ of
$\mathbbm{R}^{n}$ if there exists a linear function $G^{\prime}$ such that
$G|_{D}=G^{\prime}|_{D}$.

The definition below is borrowed from [20, Definition 9.26].

######  Definition 1.1 (Lipschitz continuity of multifunctions).

A multifunction $G:\mathbbm{R}^{n}\rightrightarrows\mathbbm{R}^{m}$ is
Lipschitz continuous on $X$, a subset of $\mathbbm{R}^{n}$, if it is nonempty-
closed-valued on $X$ and there exists $\kappa\in\mathbbm{R}_{+}$, called a
Lipschitz constant, such that

$G(x^{\prime})\subset G(x)+\kappa\|x^{\prime}-x\|{\mathbb{B}}\quad\forall
x^{\prime},x\in X.$

Let $g:\mathbbm{R}^{n}\to\mathbbm{R}$ be a convex function and let
$\bar{x}\in\mathbbm{R}^{n}$ be a point. The vector $v\in\mathbbm{R}^{n}$ is a
subgradient of $g$ at $\bar{x}$, written $v\in\partial g(\bar{x})$, if

$g(x)\geq g(\bar{x})+v^{\top}(x-\bar{x})\quad\forall x\in\mathbbm{R}^{n}.$

##  2 A sufficient condition

In this section we obtain a verifiable sufficient condition for a polyhedral
multifunction $G$ to be Lipschitz continuous on its domain. We make use of the
decomposition of the graph of the polyhedral multifunction
($\operatorname*{gph}G$) as the union of some polyhedral sets and the
convexity of the graph of the restriction of $G$ on the projection of each
polyhedral set in the decomposition of $\operatorname*{gph}G$ onto the first
variable.

######  Theorem 2.1 (Lipschitz continuity of polyhedral multifunctions).

Consider a polyhedral multifunction $G$, whose graph $\operatorname*{gph}G$ is
expressed as the union of finitely many polyhedral sets $G_{i}$ with $1\leq
i\leq l$. Assume that the following conditions hold:

(i)

$\operatorname*{dom}G$ is convex;

(ii)

$\operatorname*{gph}G|_{Q_{i}}$ is convex for all $1\leq i\leq l$, where
$Q_{i}$ is the image set of $G_{i}$ under the projection mapping $(x,y)\mapsto
x$.

Then $G$ is Lipschitz continuous not only on each $Q_{i}$ with some constant
$\kappa_{i}>0$, but also on its domain with constant $\max_{1\leq i\leq
l}\kappa_{i}$.

###### Proof.

To begin with, we notice from assumption (ii) that
$\operatorname*{dom}G=\bigcup_{i=1}^{l}Q_{i}$ with $Q_{i}$ being a polyhedral
set and

$\operatorname*{gph}G|_{Q_{i}}=\\{(x,y)\in\operatorname*{gph}G\mid x\in
Q_{i}\\}=\left\\{(x,y)\in\bigcup_{j=1}^{l}G_{j}\mid x\in
Q_{i}\right\\}=\bigcup_{j=1}^{l}\left\\{(x,y)\in G_{j}\mid x\in
Q_{i}\right\\}.$

That is, $\operatorname*{gph}G|_{Q_{i}}$ is expressed as a union of finitely
many polyhedral sets. It then follows from assumption (ii) again and [19,
Theorem 19.6] that $\operatorname*{gph}G|_{Q_{i}}$ is a polyhedral set.
Applying [20, Example 9.35], $G$ is Lipschitz continuous on each $Q_{i}$ with
some constant $\kappa_{i}>0$. That is,

$G(x^{\prime})\subset G(x)+\kappa_{i}\|x^{\prime}-x\|\mathbb{B},\quad\forall
x^{\prime},x\in Q_{i}.$ (8)

Next, we will prove the Lipschitz continuity of $G$ on $\operatorname*{dom}G$.
Indeed, for any $x^{\prime},x\in\operatorname*{dom}G$, we denote

$x_{\theta}:=x^{\prime}+\theta(x-x^{\prime}),\quad\theta\in[0,1].$

It follows from the convexity of $\operatorname*{dom}G$ (see assumption (i))
that we get that $x_{\theta}\in\operatorname*{dom}G$ for all $\theta\in[0,1]$.
This, combined with the fact that
$\operatorname*{dom}G=\bigcup_{i=1}^{l}Q_{i}$ and $Q_{i}$ is closed and convex
for each $i\in\\{1,\cdots,l\\}$, yields that there exist
$i_{j}\in\\{1,\cdots,l\\}$ and $\theta_{j}\in[0,1]$ ($j=0,1,\cdots,k$), with

$0=\theta_{0}<\theta_{1}<\cdots<\theta_{k-1}<\theta_{k}=1,$

such that

$x_{\theta}\in Q_{i_{j}},\quad\forall\theta\in[\theta_{j-1},\theta_{j}].$

Then we deduce from (8) that

$G(x_{\theta_{j-1}})\subset
G(x_{\theta_{j}})+\kappa_{i_{j}}\|x_{\theta_{j-1}}-x_{\theta_{j}}\|\mathbb{B}=G(x_{\theta_{j}})+\kappa_{i_{j}}(\theta_{j}-\theta_{j-1})\|x^{\prime}-x\|\mathbb{B},\quad
j\in\\{1,\cdots,k\\}.$

Thus,

$\begin{array}[]{rlc}G(x^{\prime})=G(x_{\theta_{0}})\subset&G(x_{\theta_{k}})+\sum\limits_{j=1}^{k}\kappa_{i_{j}}(\theta_{j}-\theta_{j-1})\|x^{\prime}-x\|\mathbb{B}\\\
\subset&G(x)+\max\limits_{j\in\\{1,\cdots,k\\}}\kappa_{i_{j}}\|x^{\prime}-x\|\mathbb{B}\\\
\subset&G(x)+\max\limits_{1\leq i\leq
l}\kappa_{i}\|x^{\prime}-x\|\mathbb{B}.\end{array}$

This completes the proof. ∎

######  Remark 2.1.

In [15], Mangasarian and Shiau studied the Lipschitz continuity of solution
multifunctions to system of linear inequalities, linear program and linear
complementarity problem. The solution multifunctions of these problems have a
polyhedral multifunction graph. Theorem 2.1 can be applied to study the
Lipschitz continuity of these multifunctions. However, the details are not
presented in here.

Next, we give an example to show that in Theorem 2.1, when $G$ is Lipschitz
continuous, both assumptions (i) and (ii) are not necessarily held.

######  Example 2.1.

Let $\Omega_{1}=\mathbbm{R}\times\\{1\\}$,
$\Omega_{2}=\mathbbm{R}\times\\{-1\\}$, $\Omega_{3}=\\{0\\}\times[-1,1]$ be
polyhedral sets and $\Omega=\Omega_{1}\cup\Omega_{2}\cup\Omega_{3}$, and
define $G:\Omega\rightrightarrows\mathbbm{R}$ as $G(x,y)=\\{0,1\\}$ for all
$(x,y)\in\Omega$. Clearly, $G(x,y)$ is a constant, and thus $G$ is a
polyhedral multifunction and Lipschitz continuous on $\Omega$. However,
$\operatorname*{dom}G=\Omega$ is not convex and, for any $i=1,2,3$,
$\operatorname*{gph}G|_{\Omega_{i}}$ is the union of two parallel lines/line
segments, which is not convex.

While both assumptions (i) and (ii) in Theorem 2.1 are not necessary, we next
provide two examples to show that the Lipschitz continuity may not be valid
whenever either assumption (i) or (ii) in Theorem 2.1 does not hold.

######  Example 2.2.

Take $\Omega$ as in Example 2.1 and define $G:\Omega\to\mathbbm{R}$ as
$G(x,y)=xy$, i.e., $G(x,y)=x$ if $(x,y)\in\Omega_{1}$, $G(x,y)=-x$ if
$(x,y)\in\Omega_{2}$ and $G(x,y)=0$ if $(x,y)\in\Omega_{3}$. Then
$\operatorname*{gph}G|_{\Omega_{1}}=\\{(x,1,x)~{}|~{}x\in\mathbbm{R}\\}$,
$\operatorname*{gph}G|_{\Omega_{2}}=\\{(x,-1,-x)~{}|~{}x\in\mathbbm{R}\\}$ and
$\operatorname*{gph}G|_{\Omega_{3}}=\\{(0,y,0)~{}|~{}y\in[-1,1]\\}$.
Therefore, all $\operatorname*{gph}G|_{\Omega_{i}}$, $i=1,2,3$, are polyhedral
and $G$ is thus a polyhedral multifunction. However,
$\operatorname*{dom}G=\Omega$ is not convex. Thus assumption (i) does not
hold. And $G$ is not Lipschitz continuous on $\Omega$. Indeed, taking
$(x_{1}^{\nu},y_{1}^{\nu})=(\nu,1)$ and $(x_{2}^{\nu},y_{2}^{\nu})=(\nu,-1)$
for all $\nu\in\mathbb{N}$, we have

$|G(x_{1}^{\nu},y_{1}^{\nu})-G(x_{2}^{\nu},y_{2}^{\nu})|=2\nu=\nu\|(x_{1}^{\nu},y_{1}^{\nu})-(x_{2}^{\nu},y_{2}^{\nu})\|,~{}~{}\forall\nu\in\mathbb{N}.$

######  Example 2.3.

This example is borrowed from [15]. We consider the linear complementarity
problem

$Mx+q\geq 0,\quad x\geq 0,\quad x^{\top}(Mx+q)=0,$

with $M=\left[~{}\begin{aligned} 0~{}~{}1\\\
-1~{}~{}0\end{aligned}~{}\right].$ For any $q\in\mathbb{R}^{2}$, the solution
set of the linear complementarity problem is denoted by $G(q)$. We find that
$\operatorname*{dom}G=\mathbbm{R}\times\mathbbm{R}_{+}$, which is convex. Let

$\displaystyle
Q_{1}:=(-\infty,0]\times[0,+\infty),~{}Q_{2}:=\\{0\\}\times[0,+\infty),$
$\displaystyle
Q_{3}:=(0,+\infty)\times[0,+\infty),~{}Q_{4}:=\mathbbm{R}\times\\{0\\}.$

Then $\operatorname*{dom}G=Q_{1}\cup Q_{2}\cup Q_{3}\cup Q_{4}$ and

$G(q)=\left\\{\begin{aligned}
&(q_{2},-q_{1})^{\top}~{}~{}~{}&&\mbox{if}~{}q\in\operatorname*{ri}Q_{1},\\\
&([0,q_{2}]\times\\{0\\})^{\top}~{}~{}~{}&&\mbox{if}~{}q\in\operatorname*{ri}Q_{2},\\\
&(0,0)^{\top}~{}~{}~{}&&\mbox{if}~{}q\in\operatorname*{ri}Q_{3},\\\
&(0,\max\\{-q_{1},0\\})^{\top}~{}~{}~{}&&\mbox{if}~{}q\in
Q_{4}.\end{aligned}\right.$

It is easy to show that $G$ is a polyhedral multifunction, which is not
Lipschitz continuous on $\operatorname*{dom}G$. Indeed
$\operatorname*{gph}G|_{Q_{1}}$ and $\operatorname*{gph}G|_{Q_{3}}$ are not
convex. Thus assumption (ii) does not hold.

##  3 Main results

In this section we will establish the Lipschitz continuity of the solution
multifunction $S$ (see (5)) for the extended $\ell_{1}$ regularization problem
(4) under the assumption that $A$ is of full row rank. Recall
$\operatorname*{dom}S=\mathbbm{R}_{+}\times\mathbbm{R}^{n}$ is a closed and
convex set. Therefore we establish the Lipschitz continuity of $S$ by
verifying that $S$ is a polyhedral multifunction and condition (ii) in Theorem
2.1 is satisfied.

We first verify that $S$ is a polyhedral multifunction. Let
$I:=\\{1,\cdots,n\\}$ and $\mathcal{I}$ denote the collection of all
partitions $(I^{+},I^{0},I^{-})$ of $I$ (i.e., $I^{+},I^{0}$ and $I^{-}$ have
no common index and $I^{+}\cup I^{0}\cup I^{-}=I$.) For each
$(I^{+},I^{0},I^{-})\in\mathcal{I}$, define

$W(I^{+},I^{0},I^{-}):=\\{x\in\mathbbm{R}^{n}\mid x_{i}>0\;\forall i\in
I^{+},x_{i}=0\;\forall i\in I^{0},\;x_{i}<0\;\forall i\in I^{-}\\}.$

It is clear that the collection of
$\\{W(I^{+},I^{0},I^{-})\mid(I^{+},I^{0},I^{-})\in\mathcal{I}\\}$ is a
partition of $\mathbbm{R}^{n}$ (i.e.,
$\operatorname*{ri}W(\bar{I}^{+},\bar{I}^{0},\bar{I}^{-})\cap
W(\tilde{I}^{+},\tilde{I}^{0},\tilde{I}^{-})=\emptyset\;\forall(\bar{I}^{+},\bar{I}^{0},\bar{I}^{-})\not=(\tilde{I}^{+},\tilde{I}^{0},\tilde{I}^{-})\in{\cal
I}$ and
$\bigcup_{(I^{+},I^{0},I^{-})\in\mathcal{I}}W(I^{+},I^{0},I^{-})=\mathbbm{R}^{n}.$)

Recall that the feasible set

$Y^{0}:=\\{y\in\mathbbm{R}^{m}\mid\|A^{\top}y\|_{\infty}\leq 1\\}$

of the extended dual $\ell_{1}$ regularization problem (6) is a polytope (due
to $A$ being of full row rank). Let $\mathcal{F}$ denote the collection of all
nonempty faces of the feasible set $Y^{0}$. For each nonempty convex subset
$F$ of $Y^{0}$, define

$\left\\{\begin{array}[]{lll}\mathcal{A}^{+}(F)&:=&\\{i\in I\mid
A_{i}^{\top}y=1\quad\forall y\in F\\},\\\ \mathcal{A}^{-}(F)&:=&\\{i\in I\mid
A_{i}^{\top}y=-1\quad\forall y\in F\\},\\\ \mathcal{A}^{0}(F)&:=&\\{i\in
I\mid-1<A_{i}^{\top}y<1\quad\exists y\in F\\}.\end{array}\right.$ (9)

We have
$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))\in\mathcal{I}$ for
all nonempty convex subsets $F$ of $Y^{0}$. Otherwise there exists $i\in I$
such that
$i\notin\mathcal{A}^{+}(F)\cup\mathcal{A}^{0}(F)\cup\mathcal{A}^{-}(F)$. Thus
$|A_{i}^{\top}y|=1$ for all $y\in F$, due to $i\notin\mathcal{A}^{0}(F)$.
Moreover, since $i\notin\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)$, there exist
$\hat{y},\bar{y}\in F$ such that $A_{i}^{\top}\hat{y}=-1$ and
$A_{i}^{\top}\bar{y}=1$. Let $\tilde{y}=(\hat{y}+\bar{y})/2$. Then
$\tilde{y}\in F$ and $A_{i}^{\top}\tilde{y}=0$, this contradicts
$|A_{i}^{\top}y|=1$ for all $y\in F$.

The index sets $(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$
will be used to construct the polyhedral cones in the graph of $S$ in
Proposition 3.1. Below we show some properties of element $F\in\mathcal{F}$
and the corresponding index partition
$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$ of $I$.

######  Lemma 3.1.

The following properties of the nonempty faces of $Y^{0}$ hold:

(i)

For each $F\in\mathcal{F}$ and $\bar{y}\in\operatorname*{ri}F$,

$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))=(\mathcal{A}^{+}(\bar{y}),\mathcal{A}^{0}(\bar{y}),\mathcal{A}^{-}(\bar{y})).$

(ii)

For each $F\in\mathcal{F}$, we have

$F=\\{y\in\mathbbm{R}^{m}\mid A_{i}^{\top}y=1\forall
i\in\mathcal{A}^{+}(F),\;-1\leq A_{i}^{\top}y\leq 1\forall
i\in\mathcal{A}^{0}(F),\;A_{i}^{\top}y=-1\forall i\in\mathcal{A}^{-}(F)\\}$

and

$\operatorname*{ri}F=\\{y\in\mathbbm{R}^{m}\mid A_{i}^{\top}y=1\forall
i\in\mathcal{A}^{+}(F),\;-1<A_{i}^{\top}y<1\forall
i\in\mathcal{A}^{0}(F),\;A_{i}^{\top}y=-1\forall i\in\mathcal{A}^{-}(F)\\}.$

(iii)

For each $F,F^{\prime}\in\mathcal{F}$ with $F\not=F^{\prime}$,
$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))\not=(\mathcal{A}^{+}(F^{\prime}),\mathcal{A}^{0}(F^{\prime}),\mathcal{A}^{-}(F^{\prime}))$.

###### Proof.

To show (i), let $F\in\mathcal{F}$ and $\bar{y}\in\operatorname*{ri}F$. By
definition we have $\mathcal{A}^{+}(F)\subset\mathcal{A}^{+}(\bar{y})$. We
claim that $\mathcal{A}^{+}(\bar{y})\subset\mathcal{A}^{+}(F)$. Suppose by
contradiction there is some $i_{0}\in\mathcal{A}^{+}(\bar{y})$ but
$i_{0}\not\in\mathcal{A}^{+}(F)$, i.e., $A_{i_{0}}^{\top}y<1$ for some $y\in
F$. As $F$ is convex and $\bar{y}\in\operatorname*{ri}F$, we have
$[\bar{y},y)\subset\operatorname*{ri}F$. Thus, there is some $\tilde{y}$ close
enough to $y$ in $[\bar{y},y)$ such that $A_{i_{0}}^{\top}\tilde{y}<1$.
Applying [13, Proposition 7] to the system of linear inequalities $-1\leq
A_{i}^{\top}y\leq 1$ for all $i\in I$, we have
$(\mathcal{A}^{+}(\bar{y}),\mathcal{A}^{0}(\bar{y}),\mathcal{A}^{-}(\bar{y}))=(\mathcal{A}^{+}(\tilde{y}),\mathcal{A}^{0}(\tilde{y}),\mathcal{A}^{-}(\tilde{y}))$.
This implies that $i_{0}\in\mathcal{A}^{+}(\tilde{y})$ or equivalently
$A_{i_{0}}^{\top}\tilde{y}=1$, a contradiction. Therefore, we have
$\mathcal{A}^{+}(F)=\mathcal{A}^{+}(\bar{y})$. Similarly, we have
$\mathcal{A}^{-}(F)=\mathcal{A}^{-}(\bar{y})$. Furthermore, we get
$\mathcal{A}^{0}(F)=\mathcal{A}^{0}(\bar{y})$. This verifies (i).

In view of [13, Proposition 4] and (i), we get the first equality in (ii)
immediately. By [26, Corollary 2.1] and the first equality in (ii), we get the
second equality in (ii) in a direct way.

(iii) follows readily from the first equality in (ii). This completes the
proof. ∎

Note that $|\cal F|$, the cardinality of $\mathcal{F}$, is finite. We show
that $S$ is a polyhedral multifunction by constructing finitely many
polyhedral cones by virtue of the index sets
$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$ with $F\in{\cal
F}$.

######  Proposition 3.1.

Assume that $A$ is of full row rank. The graph of $S$ can be expressed as

$\operatorname*{gph}S=\bigcup_{F\in\mathcal{F}}S_{F},$ (10)

where for each $F\in\mathcal{F}$, $S_{F}$ is a polyhedral cone defined by

$\begin{array}[]{rl}S_{F}:=&\left\\{(\lambda,b,x)\in\mathbbm{R}_{+}\times\mathbbm{R}^{m}\times\mathbbm{R}^{n}\left|\begin{array}[]{lcl}\lambda\geq
0&&\\\ x_{i}\geq
0,&\hskip-5.69046ptA_{i}^{\top}(b-Ax)=\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{+}(F)\\\ x_{i}=0,&\hskip-5.69046pt-\lambda\leq
A_{i}^{\top}(b-Ax)\leq\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{0}(F)\\\ x_{i}\leq
0,&\hskip-5.69046ptA_{i}^{\top}(b-Ax)=-\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{-}(F)\end{array}\right.\right\\},\end{array}$ (11)

which can be equivalently written as

$S_{F}=\\{(\lambda,Ax+\lambda y,x)\mid\lambda\geq
0,x\in\operatorname*{cl}W(\mathcal{A}^{+}(F),\;\mathcal{A}^{0}(F),\mathcal{A}^{-}(F)),\;y\in
F\\}.$ (12)

###### Proof.

Note by definition that

$W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))=\\{x\in\mathbb{R}^{n}\mid
x_{i}>0\;\forall i\in\mathcal{A}^{+}(F),\;x_{i}=0\;\forall
i\in\mathcal{A}^{0}(F),\;x_{i}<0\;\forall i\in\mathcal{A}^{-}(F)\\}.$

We will divide the proof into the following four steps.

Step 1. We first prove (12). Indeed, for any $F\in\mathcal{F}$, we denote the
right-hand-side of (12) as $K_{F}$. Take any $(\lambda,b,x)\in S_{F}$. We have
$x\in\operatorname*{cl}W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$
and

$A_{i}^{\top}(b-Ax)=\lambda\;\forall i\in\mathcal{A}^{+}(F),\;-\lambda\leq
A_{i}^{\top}(b-Ax)\leq\lambda\;\forall
i\in\mathcal{A}^{0}(F),\;A_{i}^{\top}(b-Ax)=-\lambda\;\forall
i\in\mathcal{A}^{-}(F).$ (13)

If $\lambda=0$, it follows from (13) that $A^{\top}(b-Ax)=0$, which implies
$Ax=b$, due to $A$ being full row rank. Therefore, $b=Ax+0y$ for any $y\in F$,
and hence $(\lambda,b,x)\in K_{F}$. If $\lambda>0$, let $y=(b-Ax)/\lambda$. It
follows from (13) and Lemma 3.1 (ii) that $y\in F$. Therefore,
$(\lambda,b,x)\in K_{F}$ and hence $S_{F}\subset K_{F}$.

Take any $(\lambda,b,x)\in K_{F}$. Then $\lambda\geq 0$,
$x\in\operatorname*{cl}W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$
and there exists $y\in F$ such that $b=Ax+\lambda y$. Thus, by Lemma 3.1 (ii)
again, we have

$\begin{array}[]{ll}\;\;\;\;A_{i}^{\top}(b-Ax)=\lambda
A_{i}^{\top}y=\lambda&\forall i\in\mathcal{A}^{+}(F),\\\ -\lambda\leq
A_{i}^{\top}(b-Ax)=\lambda A_{i}^{\top}y\leq\lambda&\forall
i\in\mathcal{A}^{0}(F),\\\ \;\;\;\;A_{i}^{\top}(b-Ax)=\lambda
A_{i}^{\top}y=-\lambda&\forall i\in\mathcal{A}^{-}(F).\end{array}$

Therefore, we have $(\lambda,b,x)\in S_{F}$ by definition and hence
$K_{F}\subset S_{F}$. This proves (12).

Step 2. We show that $\operatorname*{gph}S$ is closed. In fact, we note that

$\partial\|\cdot\|_{1}(x)=\\{v\mid
v_{i}=1\;\mbox{if}\;x_{i}>0,\;v_{i}=-1\;\mbox{if}\;x_{i}<0,\;v_{i}\in[-1,1]\;\mbox{if}\;x_{i}=0\\}\quad\forall
x\in\mathbbm{R}^{n},$ (14)

and that

$S(\lambda,b)=\left\\{x\in\mathbbm{R}^{n}\mid
0\in\partial\|\cdot\|_{1}(x)+\operatorname*{rge}A^{\top},\;A^{\top}(b-Ax)\in\lambda\partial\|\cdot\|_{1}(x)\right\\}\quad\forall(\lambda,b)\in\mathbbm{R}_{+}\times\mathbbm{R}^{m}.$

The latter equality follows readily from (5), by noticing for $x\in
S(\lambda,b)$ that $0\in\partial\|\cdot\|_{1}(x)+\operatorname*{rge}A^{\top}$
holds if $A^{\top}(b-Ax)\in\lambda\partial\|\cdot\|_{1}(x)$ with $\lambda>0$
and that $Ax-b=0$ holds if $A^{\top}(b-Ax)\in\lambda\partial\|\cdot\|_{1}(x)$
with $\lambda=0$ (due to $A$ being of full row rank).

Therefore, we have

$\operatorname*{gph}S=\left\\{(\lambda,b,x)\in\mathbbm{R}_{+}\times\mathbbm{R}^{m}\times\mathbbm{R}^{n}\mid\lambda\geq
0,\;0\in\partial\|\cdot\|_{1}(x)+\operatorname*{rge}A^{\top},\;A^{\top}(b-Ax)\in\lambda\partial\|\cdot\|_{1}(x)\right\\}.$
(15)

By virtue of (15), we now show that $\operatorname*{gph}S$ is closed. To that
end, let $(\lambda^{\nu},b^{\nu},x^{\nu})\to(\lambda,b,x)$ with
$(\lambda^{\nu},b^{\nu},x^{\nu})\in\operatorname*{gph}S$ for all $\nu$.
According to (15), we have

$\lambda^{\nu}\geq 0,\quad
0\in\partial\|\cdot\|_{1}(x^{\nu})+\operatorname{rge}~{}A^{\top}~{}~{}~{}\mbox{and}~{}~{}~{}A^{\top}(b^{\nu}-Ax^{\nu})\in\lambda^{\nu}\partial\|\cdot\|_{1}(x^{\nu})\quad\forall\nu.$

Then we get $\lambda\geq 0$ and there exist
$y^{\nu},z^{\nu}\in\partial\|\cdot\|_{1}(x^{\nu})$ such that

$y^{\nu}\in\operatorname{rge}~{}A^{\top}~{}~{}~{}\mbox{and}~{}~{}~{}A^{\top}(b^{\nu}-Ax^{\nu})=\lambda^{\nu}z^{\nu}~{}~{}~{}\forall\nu.$

As $\\{y^{\nu}\\}$ and $\\{z^{\nu}\\}$ are bounded according to (14), by
taking some subsequences if necessary, we assume that $y^{\nu}\to y$ and
$z^{\nu}\to z$. Thus,

$y\in\operatorname{rge}~{}A^{\top}~{}~{}~{}\mbox{and}~{}~{}~{}A^{\top}(b-Ax)=\lambda
z.$

Moreover, it follows from the outer semicontinuity of the subdifferential
(cf.[20, Proposition 8.7]) that $y,z\in\partial\|\cdot\|_{1}(x)$. Therefore,

$\lambda\geq 0,\quad
0\in\partial\|\cdot\|_{1}(x)+\operatorname{rge}~{}A^{\top}~{}~{}~{}\mbox{and}~{}~{}~{}A^{\top}(b-Ax)\in\lambda\partial\|\cdot\|_{1}(x).$

By (15) again, we have $(\lambda,b,x)\in\operatorname*{gph}S$. This verifies
the closedness of $\operatorname*{gph}S$.

Step 3. We prove $\operatorname*{gph}S\subset\bigcup_{F\in\mathcal{F}}S_{F}$.
Fix any $(\lambda,b,x)\in\operatorname*{gph}S$. Define

$I^{+}:=\\{i\in I\mid x_{i}>0\\},\quad I^{0}:=\\{i\in I\mid x_{i}=0\\},\quad
I^{-}:=\\{i\in I\mid x_{i}<0\\},$

and

$F:=\\{y\in\mathbb{R}^{m}\mid A_{i}^{\top}y=1\;\forall i\in I^{+},\;-1\leq
A_{i}^{\top}y\leq 1\;\forall i\in I^{0},\;A_{i}^{\top}y=-1\;\forall i\in
I^{-}\\}.$

Then by (15), we have
$0\in\partial\|\cdot\|_{1}(x)+\operatorname*{rge}A^{\top}$, which implies
$F\in\mathcal{F}$. For any $i\in\mathcal{A}^{+}(F)$, by Lemma 3.1 (ii) we have
$A_{i}^{\top}y=1$ for all $y\in F$, implying that $i\notin I^{-}$ and hence
that $x_{i}\geq 0$. Similarly, $x_{i}\leq 0$ for any $i\in\mathcal{A}^{-}(F)$.
For any $i\in\mathcal{A}^{0}(F)$, it is obvious that $i\notin I^{+}\cup I^{-}$
and hence that $x_{i}=0$. All above imply that
$x\in\operatorname*{cl}W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$.

If $\lambda=0$, it follows from (15) that $A^{\top}(b-Ax)=0$, which implies
$Ax=b$, due to $A$ being full row rank. Therefore, $b=Ax+0y$ for any $y\in F$.
Then we deduce from (12) that $(\lambda,b,x)\in S_{F}$.

If $\lambda>0$, let $y:=(b-Ax)/\lambda$. It follows from (15) that
$A^{\top}y\in\partial\|\cdot\|_{1}(x)$ and hence by (14) that $y\in F$. Then
by (12), we have $(\lambda,b,x)\in S_{F}$.

Step 4. We prove that
$\bigcup_{F\in\mathcal{F}}S_{F}\subset\operatorname*{gph}S$. Fix any
$F\in\mathcal{F}$ and $(\lambda,b,x)\in K^{0}_{F}$, where

$K^{0}_{F}:=\\{(\lambda,Ax+\lambda y,x)\mid\lambda\geq 0,x\in
W(\mathcal{A}^{+}(F),\;\mathcal{A}^{0}(F),\mathcal{A}^{-}(F)),\;y\in F\\},$

Then $\lambda\geq 0$ and it is clear to see from (12) that
$\operatorname*{cl}K_{F}^{0}=S_{F}$. We deduce from Lemma 3.1 (ii) that

$\begin{array}[]{lcl}x_{i}>0&A_{i}^{\top}(b-Ax)=\lambda&\forall
i\in\mathcal{A}^{+}(F),\\\ x_{i}=0&-\lambda\leq
A_{i}^{\top}(b-Ax)\leq\lambda&\forall i\in\mathcal{A}^{0}(F),\\\
x_{i}<0&A_{i}^{\top}(b-Ax)=\lambda&\forall i\in\mathcal{A}^{-}(F).\end{array}$

Then it follows from (14) that
$A^{\top}(b-Ax)\in\lambda\partial\|\cdot\|_{1}(x)$. For any $y\in F$, we get
from Lemma 3.1 (ii) and (14) that $A^{\top}y\in\partial\|\cdot\|_{1}(x)$ and
hence that $0\in\partial\|\cdot\|_{1}(x)+\operatorname*{rge}A^{\top}$. It then
follows from (15) that $(\lambda,b,x)\in\operatorname*{gph}S$ and hence that
$K^{0}_{F}\subset\operatorname*{gph}S$. As $\operatorname*{cl}K_{F}^{0}=S_{F}$
and $\operatorname*{gph}S$ is closed, we thus have
$S_{F}\subset\operatorname*{gph}S$. This completes the proof. ∎

An analytic expression of $S_{F}$ is obtained in (11). Below we give the
analytic expressions of $\operatorname*{ri}S_{F}$ and
$\operatorname*{aff}S_{F}$ respectively, which will be used to obtain an
explicit formula of the interior of the projection of $S_{F}$ onto its first
two variables $(\lambda,b)$.

######  Lemma 3.2.

For $F\in\mathcal{F}$, we have

$\begin{array}[]{rl}\operatorname*{ri}S_{F}=&\left\\{(\lambda,b,x)\left|\begin{array}[]{lcl}\lambda>0&&\\\
x_{i}>0,&\hskip-5.69046ptA_{i}^{T}(b-Ax)=\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{+}(F)\\\
x_{i}=0,&\hskip-5.69046pt-\lambda<A_{i}^{T}(b-Ax)<\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{0}(F)\\\
x_{i}<0,&\hskip-5.69046ptA_{i}^{T}(b-Ax)=-\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{-}(F)\end{array}\right.\right\\}\\\\[28.45274pt]
=&\\{(\lambda,Ax+\lambda y,x)\mid\lambda>0,x\in
W(\mathcal{A}^{+}(F),\;\mathcal{A}^{0}(F),\mathcal{A}^{-}(F)),\;y\in\operatorname*{ri}F\\},\end{array}$
(16)

and

$\operatorname*{aff}S_{F}=\left\\{(\lambda,b,x)\left|\begin{array}[]{rl}A_{i}^{\top}(b-Ax)=\lambda&\forall
i\in\mathcal{A}^{+}(F)\\\ x_{i}=0&\forall i\in\mathcal{A}^{0}(F)\\\
A_{i}^{\top}(b-Ax)=-\lambda&\forall
i\in\mathcal{A}^{-}(F)\end{array}\right.\right\\}.$ (17)

Moreover, $\operatorname*{ri}S_{F}\cap S_{F^{\prime}}=\emptyset$ for all
$F,F^{\prime}\in\mathcal{F}$ with $F\not=F^{\prime}$.

###### Proof.

We first get the second equality in (16) from Lemma 3.1 (ii) by taking
$y=(b-Ax)/\lambda$. This implies that the right-hand-side of the first
equality in (16) is nonempty due to $\operatorname*{ri}F\not=\emptyset$. Then
we get the first equality in (16) directly from [26, Corollary 2.1]. Then from
the definition of affine hulls and the first equality in (16), we get (17).

Next, we will show that $\operatorname*{ri}S_{F}\cap S_{F^{\prime}}=\emptyset$
for all $F,F^{\prime}\in\mathcal{F}$ with $F\not=F^{\prime}$. Otherwise, fix
$F,F^{\prime}\in\mathcal{F}$ with $F\not=F^{\prime}$ and let
$(\lambda,b,x)\in\operatorname*{ri}S_{F}\cap S_{F^{\prime}}$. We claim that
$\mathcal{A}^{+}(F)=\mathcal{A}^{+}(F^{\prime})$. Indeed, for any
$i\in\mathcal{A}^{+}(F)$, we deduce from
$(\lambda,b,x)\in\operatorname*{ri}S_{F}$ and (16) that $x_{i}>0$. This,
combined with (11) and $(\lambda,b,x)\in S_{F^{\prime}}$, yields that
$i\in\mathcal{A}^{+}(F^{\prime})$. Thus,
$\mathcal{A}^{+}(F)\subset\mathcal{A}^{+}(F^{\prime})$. To prove the opposite
inclusion, take any $i\in\mathcal{A}^{+}(F^{\prime})$. It follows from (11)
that $A_{i}^{\top}(b-Ax)=\lambda$. Moreover, in view of the fact that
$(\lambda,b,x)\in\operatorname*{ri}S_{F}$, we deduce from (16) that
$\lambda>0$ and hence $i\in\mathcal{A}^{+}(F)$. Thus,
$\mathcal{A}^{+}(F^{\prime})\subset\mathcal{A}^{+}(F)$ and hence
$\mathcal{A}^{+}(F)=\mathcal{A}^{+}(F^{\prime})$. Similarly, we have
$\mathcal{A}^{-}(F)=\mathcal{A}^{-}(F^{\prime})$. Thus,
$\mathcal{A}^{0}(F)=\mathcal{A}^{0}(F^{\prime})$. Then by Lemma 3.1 (iii), we
have $F=F^{\prime}$. This is a contradiction. ∎

For each $F\in\mathcal{F}$, we introduce the following projections of the
polyhedral cone $S_{F}$:

$D_{F}=P_{1,2}(S_{F})\quad\mbox{and}\quad R_{F}=P_{3}(S_{F}),$

where
$P_{1,2}:\mathbbm{R}\times\mathbbm{R}^{m}\times\mathbbm{R}^{n}\to\mathbbm{R}\times\mathbbm{R}^{m}$
and
$P_{3}:\mathbbm{R}\times\mathbbm{R}^{m}\times\mathbbm{R}^{n}\to\mathbbm{R}^{n}$
are the projection mappings $(\lambda,b,x)\mapsto(\lambda,b)$ and
$(\lambda,b,x)\mapsto x$, respectively. It is clear that $D_{F}$ and $R_{F}$
are polyhedral cones. We list some basic properties of $D_{F}$ and $R_{F}$ as
follows and show that the $D_{F}^{\prime}s$ provide a partition of
$\operatorname*{dom}S$.

######  Lemma 3.3.

The following properties of $D_{F}$ and $R_{F}$ hold:

(i)

For any $F\in\mathcal{F}$, $D_{F}$ is a polyhedral cone having nonempty
interior with

$D_{F}=\\{(\lambda,Ax+\lambda y)\mid\lambda\geq
0,x\in\operatorname*{cl}W(\mathcal{A}^{+}(F),\;\mathcal{A}^{0}(F),\mathcal{A}^{-}(F)),\;y\in
F\\}$

and

$\operatorname*{int}D_{F}=P_{1,2}(\operatorname*{ri}S_{F})=\\{(\lambda,Ax+\lambda
y)\mid\lambda>0,\;x\in
W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F)),\;y\in\operatorname*{ri}F\\}.$

In particular, $D_{F}$ can be generated from the vectors
$(0,A_{i}^{\top})^{\top}$, $(0,-A_{j}^{\top})^{\top}$ and
$(1,V^{\top})^{\top}$ with $i\in\mathcal{A}^{+}(F)$, $j\in\mathcal{A}^{-}(F)$
and $V\in{\rm extr}(F)$ (some of these generators could be superfluous, and by
removing them, the remaining vectors serve as the extreme directions of
$D_{F}$).

(ii)

The following partition of $\operatorname*{dom}S$ holds:

$\operatorname*{dom}S=\bigcup_{F\in\mathcal{F}}D_{F},$

where $\operatorname*{int}D_{F}\cap D_{F^{\prime}}=\emptyset$ for all
$F,F^{\prime}\in\mathcal{F}$ with $F\not=F^{\prime}$.

(iii)

$\|\cdot\|_{1}$ is linear on the polyhedral cone $R_{F}$ with

$R_{F}=\operatorname*{cl}W((\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F)))\;\mbox{and}\;\operatorname*{ri}R_{F}=W((\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))).$

(iv)

For any $F,F^{\prime}\in\mathcal{F}$ with $F\not=F^{\prime}$ and any
$(\lambda,b,x),(\lambda^{\prime},b^{\prime},x^{\prime})\in\operatorname*{gph}S$
such that $(\lambda,b)\in\operatorname*{int}D_{F}$ and
$(\lambda^{\prime},b^{\prime})\in\operatorname*{int}D_{F^{\prime}}$, there is
some $\theta\in(0,1)$ such that

$\theta(\lambda,b,x)+(1-\theta)(\lambda^{\prime},b^{\prime},x^{\prime})\not\in\operatorname*{gph}S.$

###### Proof.

To show (i), we note from definition that $D_{F}$ is the image set of the
polyhedral cone $S_{F}$ under the projection mapping $P_{1,2}$, entailing that
$D_{F}$ is also a polyhedral cone. In view of (12), we get the formula for
$D_{F}$ immediately. Moreover, it is clear to see that

$D_{F}=C_{1}+C_{2},$

where

$C_{1}:=\\{(0,Ax)\mid
x\in\operatorname*{cl}W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F)))\\}$

and

$C_{2}:=\\{(\lambda,\lambda y)\mid\lambda\geq 0,y\in F\\}$

are two polyhedral cones. As $C_{1}$ can be generated from vectors of the form
$(0,A_{i}^{\top})^{\top}$ and $(0,-A_{j}^{\top})^{\top}$ with
$i\in\mathcal{A}^{+}(F)$ and $j\in\mathcal{A}^{-}(F)$, and $C_{2}$ can be
generated from vectors of the form $(1,V^{\top})^{\top}$ with $V\in{\rm
extr}(F)$, we confirm that $D_{F}$ can therefore be generated from these
vectors.

We now show that $C_{1}+C_{2}$ has a nonempty interior. In the case of
$F=Y^{0}$, we have $C_{1}+C_{2}=\\{(\lambda,\lambda y)\mid\lambda\geq 0,y\in
Y^{0}\\}$ which obviously has a nonempty interior due to
$0\in\operatorname*{int}Y^{0}$. Now consider the case that $F\not=Y^{0}$. In
this case, it is trivial to verify that

${\rm aff}(F)=\\{y\in\mathbbm{R}^{m}\mid A_{i}^{\top}y=1\;\forall
i\in\mathcal{A}^{+}(F),\;A_{i}^{\top}y=-1\;\forall i\in\mathcal{A}^{-}(F)\\}$

and hence that the dimension of $\operatorname*{aff}F$ is equal to
$m-\operatorname*{rank}\\{A_{i}^{\top},i\in\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)\\}$
(see [14, Theorem 2.3.3]). It is obvious that $0\notin\operatorname*{aff}F$.
As $0\in\operatorname*{int}Y^{0}$ and $F\subsetneq Y^{0}$ is a face of
$Y^{0}$, $\operatorname*{rank}({\rm extr}(F))$ is equal to the dimension of
$\operatorname*{aff}F$ plus 1. Noting from (9) that $A_{i}^{\top}V=1$ and
$A_{j}^{\top}V=-1$ for all $i\in\mathcal{A}^{+}(F)$, $j\in\mathcal{A}^{-}(F)$
and $V\in{\rm extr}(F)$, the rank of the vectors $(0,A_{i}^{\top})^{\top}$
($i\in\mathcal{A}^{+}(F)$), $(0,-A_{j}^{\top})^{\top}$
($j\in\mathcal{A}^{-}(F)$) and $(1,V^{\top})^{\top}$ ($\forall V\in{\rm
extr}(F)$) is thus equal to $m+1$, implying that $C_{1}+C_{2}$ has a nonempty
interior. Therefore, $D_{F}$ has a nonempty interior. Then according to [19,
Theorem 6.6], we have
$\operatorname*{int}D_{F}=P_{1,2}(\operatorname*{ri}S_{F})$ and then from (16)
we get the formula for $\operatorname*{int}D_{F}$.

To show (ii), we first get the formula for $\operatorname*{dom}S$ from (10) by
observing that $\operatorname*{dom}S=P_{1,2}(\operatorname*{gph}S)$. Moreover,
let $F,F^{\prime}\in\mathcal{F}$ be such that $F\not=F^{\prime}$. Suppose by
contradiction that $\operatorname*{int}D_{F}\cap D_{F^{\prime}}\not=\emptyset$
and there is some $(\lambda,b)\in\operatorname*{int}D_{F}\cap D_{F^{\prime}}$.
Then we can find some
$(\lambda^{\prime},b^{\prime})\in\operatorname*{int}D_{F^{\prime}}$ and some
$(\tilde{\lambda},\tilde{b})$ close enough to $(\lambda,b)$ in the line
segment $((\lambda,b),(\lambda^{\prime},b^{\prime})]$ such that
$(\tilde{\lambda},\tilde{b})\in\operatorname*{int}D_{F}\cap\operatorname*{int}D_{F^{\prime}}$.
By (i), we have $\tilde{\lambda}>0$ and
$\tilde{b}=Ax+\tilde{\lambda}y=Ax^{\prime}+\tilde{\lambda}y^{\prime}$ for some
$x\in W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$,
$x^{\prime}\in
W(\mathcal{A}^{+}(F^{\prime}),\mathcal{A}^{0}(F^{\prime}),\mathcal{A}^{-}(F^{\prime}))$,
$y\in\operatorname*{ri}F$ and $y^{\prime}\in\operatorname*{ri}F^{\prime}$. By
(12), we have $(\tilde{\lambda},\tilde{b},x)\in S_{F}$ and
$(\tilde{\lambda},\tilde{b},x^{\prime})\in S_{F^{\prime}}$. In view of (10),
we thus have $x,x^{\prime}\in S(\tilde{\lambda},\tilde{b})$. Then we get from
[25, Lemma 4.1] that $Ax=Ax^{\prime}$ and hence $y=y^{\prime}$. By [19,
Theorem 18.1], we have $F=F^{\prime}$, a contradiction. Therefore, we have
$\operatorname*{int}D_{F}\cap D_{F^{\prime}}=\emptyset$.

To show (iii), we note from definition that $R_{F}$ is the image sets of the
polyhedral cone $S_{F}$ under the projection mapping $P_{3}$, entailing that
$S_{F}$ is also a polyhedral cone. While the formula for $R_{F}$ follows
directly from (12), the formula for $\operatorname*{ri}R_{F}$ is trivial. By
the formula for $R_{F}$, $\|\cdot\|_{1}$ is clearly linear on $R_{F}$.

To show (iv), let $F,F^{\prime}\in\mathcal{F}$ be such that $F\not=F^{\prime}$
and let
$(\lambda,b,x),(\lambda^{\prime},b^{\prime},x^{\prime})\in\operatorname*{gph}S$
such that $(\lambda,b)\in\operatorname*{int}D_{F}$ and
$(\lambda^{\prime},b^{\prime})\in\operatorname*{int}D_{F^{\prime}}$. Suppose
by contradiction that

$(\lambda_{\theta},b_{\theta},x_{\theta}):=\theta(\lambda,b,x)+(1-\theta)(\lambda^{\prime},b^{\prime},x^{\prime})\in\operatorname*{gph}S\quad\forall\theta\in[0,1].$
(18)

Then by (ii), $(\lambda_{\theta},b_{\theta})\in\operatorname*{int}D_{F}$ and
$(\lambda_{\theta},b_{\theta},x_{\theta})\in S_{F}$ for all $\theta$ close
enough to 1 in $[0,1]$. This implies that
$(\lambda_{\theta},b_{\theta},x_{\theta})\in\operatorname*{aff}S_{F}$ for all
$\theta\in[0,1]$. By letting $\theta=0$, we have
$(\lambda^{\prime},b^{\prime},x^{\prime})\in\operatorname*{aff}S_{F}$.
According to (17), we have

$A_{i}^{\top}(b^{\prime}-Ax^{\prime})=\lambda^{\prime}\quad\forall
i\in\mathcal{A}^{+}(F)$

or equivalently,

$A_{i}^{\top}\left(\frac{b^{\prime}-Ax^{\prime}}{\lambda^{\prime}}\right)=1\quad\forall
i\in\mathcal{A}^{+}(F).$ (19)

As $(\lambda^{\prime},b^{\prime})\in\operatorname*{int}D_{F^{\prime}}$, we get
from (ii) the existence of some $\tilde{x}^{\prime}\in
W(\mathcal{A}^{+}(F^{\prime}),\mathcal{A}^{0}(F^{\prime}),\mathcal{A}^{-}(F^{\prime}))$
such that
$\frac{b^{\prime}-A\tilde{x}^{\prime}}{\lambda^{\prime}}\in\operatorname*{ri}F^{\prime}$.
It then follows from Lemma 3.2 that
$(\lambda^{\prime},b^{\prime},\tilde{x}^{\prime})\in\operatorname*{ri}S_{F^{\prime}}$.
In view of the fact that $x^{\prime},\tilde{x}^{\prime}\in
S(\lambda^{\prime},b^{\prime})$, we get from [25, Lemma 4.1] that
$A\tilde{x}^{\prime}=Ax^{\prime}$. Thus, we have
$\frac{b^{\prime}-Ax^{\prime}}{\lambda^{\prime}}\in\operatorname*{ri}F^{\prime}$.
Then by Lemma 3.1 (i) and (19), we get
$\mathcal{A}^{+}(F)\subset\mathcal{A}^{+}(F^{\prime})$. In a parallel manner,
we can show $\mathcal{A}^{+}(F^{\prime})\subset\mathcal{A}^{+}(F)$. That is,
we have $\mathcal{A}^{+}(F)=\mathcal{A}^{+}(F^{\prime})$. Similarly, we can
obtain $\mathcal{A}^{-}(F)=\mathcal{A}^{-}(F^{\prime})$. So we actually have
$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))=(\mathcal{A}^{+}(F^{\prime}),\mathcal{A}^{0}(F^{\prime}),\mathcal{A}^{-}(F^{\prime}))$.
Then by Lemma 3.1 (iii), we have $F=F^{\prime}$, a contradiction. This
verifies (v) and completes the proof. ∎

Now we verify condition (ii) in Theorem 2.1.

######  Proposition 3.2.

The graph $\operatorname*{gph}S|_{D_{F}}$ of the restriction of $S$ on $D_{F}$
is convex for all $F\in\mathcal{F}$.

###### Proof.

Fix any $F\in\mathcal{F}$ and any
$(\hat{\lambda},\hat{b},\hat{x}),(\bar{\lambda},\bar{b},\bar{x})\in\operatorname*{gph}S|_{D_{F}}$
and $\theta\in(0,1)$. As $(\hat{\lambda},\hat{b}),(\bar{\lambda},\bar{b})\in
D_{F}$ and $D_{F}=P_{1,2}(S_{F})$, there exist
$\hat{x}^{\prime},\bar{x}^{\prime}\in\mathbbm{R}^{n}$ such that

$(\hat{\lambda},\hat{b},\hat{x}^{\prime}),(\bar{\lambda},\bar{b},\bar{x}^{\prime})\in
S_{F}.$

Let

$(\lambda_{\theta},b_{\theta},x_{\theta}^{\prime}):=\theta(\hat{\lambda},\hat{b},\hat{x}^{\prime})+(1-\theta)(\bar{\lambda},\bar{b},\bar{x}^{\prime})\mbox{
and }x_{\theta}:=\theta\hat{x}+(1-\theta)\bar{x}.$ (20)

It follows from the convexity of $S_{F}$ and (10) that
$(\lambda_{\theta},b_{\theta},x_{\theta}^{\prime})\in S_{F}$ and hence that

$x_{\theta}^{\prime}\in S(\lambda_{\theta},b_{\theta}).$ (21)

Moreover, as $\hat{x},\hat{x}^{\prime}\in S(\hat{\lambda},\hat{b})$ and
$\bar{x},\bar{x}^{\prime}\in S(\bar{\lambda},\bar{b})$ (due to
$S_{F}\subset\operatorname*{gph}S|_{D_{F}}\subset\operatorname*{gph}S$), we
have that

$A\hat{x}=A\hat{x}^{\prime},~{}~{}\|\hat{x}\|_{1}=\|\hat{x}^{\prime}\|_{1}~{}~{}\mbox{and}~{}~{}A\bar{x}=A\bar{x}^{\prime},~{}~{}\|\bar{x}\|_{1}=\|\bar{x}^{\prime}\|_{1},$
(22)

which follow from [25, Lemma 4.1] for the cases of $\hat{\lambda}>0$ or
$\bar{\lambda}>0$, and from the definition for the cases of $\hat{\lambda}=0$
or $\bar{\lambda}=0$.

If $\hat{\lambda}=\bar{\lambda}=0$, then $\lambda_{\theta}=0$. Thus,
$Ax_{\theta}=\theta
A\hat{x}+(1-\theta)A\bar{x}=\theta\hat{b}+(1-\theta)\bar{b}=b_{\theta}$ and

$\|x_{\theta}\|_{1}=\|\theta\hat{x}+(1-\theta)\bar{x}\|_{1}\leq\theta\|\hat{x}\|_{1}+(1-\theta)\|\bar{x}\|_{1}\hskip-2.84544pt=\theta\|\hat{x}^{\prime}\|_{1}+(1-\theta)\|\bar{x}^{\prime}\|_{1}\hskip-2.84544pt=\|x_{\theta}^{\prime}\|_{1},$

where the second last equality follows from (22), the last equality comes from
(20) and the linearity of $\|\cdot\|_{1}$ on $R_{F}$ (see Lemma 3.3 (iii)). In
view of (21), we get $x_{\theta}\in S(\lambda_{\theta},b_{\theta})$.

If $\hat{\lambda}>0$ or $\bar{\lambda}>0$, then $\lambda_{\theta}>0$. Thus

$\begin{array}[]{ll}&\frac{1}{2\lambda_{\theta}}\|Ax_{\theta}-b_{\theta}\|^{2}+\|x_{\theta}\|_{1}\\\
=&\frac{1}{2\lambda_{\theta}}\|\theta(A\hat{x}-\hat{b})+(1-\theta)(A\bar{x}-\bar{b})\|^{2}+\|\theta\hat{x}+(1-\theta)\bar{x}\|_{1}\\\
\leq&\frac{1}{2\lambda_{\theta}}\|\theta(A\hat{x}-\hat{b})+(1-\theta)(A\bar{x}-\bar{b})\|^{2}+\theta\|\hat{x}\|_{1}+(1-\theta)\|\bar{x}\|_{1}\\\
=&\frac{1}{2\lambda_{\theta}}\|\theta(A\hat{x}^{\prime}-\hat{b})+(1-\theta)(A\bar{x}^{\prime}-\bar{b})\|^{2}+\theta\|\hat{x}^{\prime}\|_{1}+(1-\theta)\|\bar{x}^{\prime}\|_{1}\\\
=&\frac{1}{2\lambda_{\theta}}\|Ax_{\theta}^{\prime}-b_{\theta}\|^{2}+\|x_{\theta}^{\prime}\|_{1},\end{array}$

where the first equality comes from (20), the second last equality comes from
(22), and the last equality comes from (20) and the linearity of
$\|\cdot\|_{1}$ on $R_{F}$ (see Lemma 3.3 (iii)). In view of (21), we get
$x_{\theta}\in S(\lambda_{\theta},b_{\theta})$.

In both cases, we have shown that $x_{\theta}\in
S(\lambda_{\theta},b_{\theta})$. Noting that due to
$(\hat{\lambda},\hat{b},\hat{x}),(\bar{\lambda},\bar{b},\bar{x})\in S_{F}$, we
have $(\lambda_{\theta},b_{\theta})\in D_{F}$. Thus
$(\lambda_{\theta},b_{\theta},x_{\theta})\in\operatorname*{gph}S|_{D_{F}}$.
This verifies the convexity of $\operatorname*{gph}S|_{D_{F}}$ and thus
completes the proof. ∎

In what follows, we obtain the Lipschitz continuity property of $S(\lambda,b)$
on $\operatorname*{dom}S$ under the assumption that $A$ is of full row rank by
noting that $\operatorname*{dom}S$ is convex and by applying Theorem 2.1,
Proposition 3.1 and Proposition 3.2 directly.

######  Theorem 3.1.

Assume that $A$ is of full row rank. Then $S$ is Lipschitz continuous on its
domain.

By virtue of the Lipschitz continuity of $S$ on $\operatorname*{dom}S$, we can
further show that the graph of the restriction of $S$ on each $D_{F}$
coincides with $S_{F}$, or in other words, an explicit formula for
$S(\lambda,b)$ can be given in connection with some $F\in\mathcal{F}$ such
that $(\lambda,b)\in D_{F}$.

######  Corollary 3.1.

Assume that $A$ is of full row rank. Then

$\operatorname*{gph}S|_{D_{F}}=S_{F}\quad\forall F\in\mathcal{F},$

or in other words, for all $(\lambda,b)\in\operatorname*{dom}S$ and
$F\in\mathcal{F}$ with $(\lambda,b)\in D_{F}$, we have

$\begin{array}[]{rl}S(\lambda,b)=&\left\\{x\left|\begin{array}[]{lcl}x_{i}\geq
0,&\hskip-5.69046ptA_{i}^{\top}(b-Ax)=\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{+}(F)\\\ x_{i}=0,&\hskip-5.69046pt-\lambda\leq
A_{i}^{\top}(b-Ax)\leq\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{0}(F)\\\ x_{i}\leq
0,&\hskip-5.69046ptA_{i}^{\top}(b-Ax)=-\lambda&\hskip-5.69046pt\forall
i\in\mathcal{A}^{-}(F)\end{array}\right.\right\\}.\end{array}$ (23)

###### Proof.

As $D_{F}=P_{1,2}(S_{F})$ by definition, we get from (10) that

$S_{F}\subset\operatorname*{gph}S|_{D_{F}}.$

According to Lemma 3.3 (ii), we have
$\operatorname*{dom}S=\bigcup_{F\in\mathcal{F}}D_{F}$ and
$\operatorname*{int}D_{F}\cap D_{F^{\prime}}=\emptyset$ for all
$F^{\prime}\in\mathcal{F}$ with $F^{\prime}\not=F$. Thus, we have

$\operatorname*{gph}S|_{\operatorname*{int}D_{F}}\subset S_{F}.$ (24)

Therefore, to show $\operatorname*{gph}S|_{D_{F}}\subset S_{F}$, it suffices
to show

$\operatorname*{gph}S|_{\operatorname*{bdry}D_{F}}\subset S_{F}.$ (25)

To that end, let $(\lambda,b)\in\operatorname*{bdry}D_{F}$ and $x\in
S(\lambda,b)$. Since $\operatorname*{int}D_{F}\not=\emptyset$ (see Lemma 3.3
(ii)), there exist $(\lambda^{\nu},b^{\nu})\in\operatorname*{int}D_{F}$ such
that $(\lambda^{\nu},b^{\nu})\to(\lambda,b)$. According to the Lipschitz
continuity of $S$ established in Theorem 3.1, there exist
$x^{\nu}\in\mathbbm{R}^{n}$ such that $x^{\nu}\in S(\lambda^{\nu},b^{\nu})$
for all $\nu$ and $x^{\nu}\to x$. In view of (24), we have
$(\lambda^{\nu},b^{\nu},x^{\nu})\in S_{F}$ for all $\nu$. As $S_{F}$ is
closed, we have $(\lambda,b,x)\in S_{F}$. This verifies (25) and hence the
equality $\operatorname*{gph}S|_{D_{F}}=S_{F}$. Then by the definition of
$S_{F}$, we get (23) in a straightforward way. This completes the proof. ∎

Recall that $I=\\{1,\cdots,n\\}$. For some later developments, we define some
index sets as follows:

$\begin{array}[]{l}I^{+}(\bar{x}):=\\{i\in I\mid\bar{x}_{i}>0\\},\\\
I^{0}(\bar{x}):=\\{i\in I\mid\bar{x}_{i}=0\\},\\\ I^{-}(\bar{x}):=\\{i\in
I\mid\bar{x}_{i}<0\\},\\\ J(\bar{\lambda},\bar{b},\bar{x}):=\\{i\in
I\mid|A_{i}^{\top}(\bar{b}-A\bar{x})|=\bar{\lambda}\\}.\end{array}$

In terms of these index sets, we now review some existing conditions as
follows, for a given $(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$:

Condition 3.1

There are some $\bar{x}\in S(\bar{\lambda},\bar{b})$ and $y\in\mathbbm{R}^{m}$
such that the columns $A_{i}$ of $A$ with $i\in I^{+}(\bar{x})\cup
I^{-}(\bar{x})$ are linearly independent and

$A_{i}^{\top}y=1\;\forall i\in I^{+}(\bar{x}),\;-1<A_{i}^{\top}y<1\;\forall
i\in I^{0}(\bar{x}),\;A_{i}^{\top}y=-1\;\forall i\in I^{-}(\bar{x}).$ (26)

Condition 3.2

There is some $\bar{x}\in S(\bar{\lambda},\bar{b})$ such that the columns
$A_{i}$ of $A$ with $i\in J(\bar{\lambda},\bar{b},\bar{x})$ are linearly
independent.

Condition 3.3

There is some $\bar{x}\in S(\bar{\lambda},\bar{b})$ such that the columns
$A_{i}$ of $A$ with $i\in I^{+}(\bar{x})\cup I^{-}(\bar{x})$ are linearly
independent and

$|A_{i}^{\top}(\bar{b}-A\bar{x})|<\bar{\lambda}\quad\forall i\in
I^{0}(\bar{x}).$ (27)

In the case of $I^{+}(\bar{x})\cup I^{-}(\bar{x})=\emptyset$, the columns
$A_{i}$ of $A$ with $i\in I^{+}(\bar{x})\cup I^{-}(\bar{x})$ are claimed to be
linearly independent by convention. While Conditions 3.1 was proposed in [25]
in a later time, Conditions 3.2 and 3.3 have appeared earlier in [22] and [8],
respectively. It has been shown in [3, Lemma 4.6] that the following
implications hold for the case of
$(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$ with $\bar{\lambda}>0$:

$\mbox{Condition 3.3}\Longrightarrow\mbox{Condition
3.2}\Longrightarrow\mbox{Condition 3.1},$

which hold also in the case of
$(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$ with $\bar{\lambda}=0$, as
they can be verified in a straightforward way from the definitions.

By virtue of the Lipschitz continuity of $S$ on $\operatorname*{dom}S$, we now
give a simple criterion for verifying the single-valuedness and linearity of
$S$ on each $D_{F}$ with $F\in\mathcal{F}$. Our analysis relies on the
necessary and sufficient condition [25, Theorem 2.1] for the solution
uniqueness of the Lasso and the BP problems, which says that Condition 3.1
holds at $(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$ if and only if $S$
is single-valued at $(\bar{\lambda},\bar{b})$. This further implies that
whenever Condition 3.2 or 3.3 holds at
$(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$, the single-valuedness of $S$
at $(\bar{\lambda},\bar{b})$ is at hand.

Recall that $\cal F$ is the set of all nonempty faces of $Y^{0}$. In what
follows, let $\mathcal{F}^{0}$ consist of all faces $F\in\mathcal{F}$ such
that the columns $A_{i}$ of $A$ with
$i\in\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)$ are linearly independent.
Noting that $Y^{0}\in\mathcal{F}$ and by definition
$\mathcal{A}^{+}(Y^{0})\cup\mathcal{A}^{-}(Y^{0})=\emptyset$, we set by
convention that $Y^{0}\in\mathcal{F}^{0}$. It will be clear from the sequel
that $S$ is single-valued on $D_{F}$ if and only if $F\in\mathcal{F}^{0}$.

######  Corollary 3.2.

Assume that $A$ is of full row rank. The following hold:

(i)

If $F\in\mathcal{F}^{0}$, then $S$ is single-valued and linear on $D_{F}$ with

$S(\lambda,b)=\\{x\\}\quad\forall(\lambda,b)\in D_{F},$

where for a given $(\lambda,b)\in D_{F}$, $x$ is the unique solution to the
system of linear equations

$\left\\{\begin{array}[]{rlll}A_{i}^{\top}Ax&=&A_{i}^{\top}b-\lambda&\forall
i\in\mathcal{A}^{+}(F),\\\ x_{i}&=&0&\forall i\in\mathcal{A}^{0}(F),\\\
A_{i}^{\top}Ax&=&A_{i}^{\top}b+\lambda&\forall
i\in\mathcal{A}^{-}(F).\end{array}\right.$ (28)

Alternatively if $F\not\in\mathcal{F}^{0}$, then $S(\lambda,b)$ is not single-
valued for every $(\lambda,b)\in\operatorname*{int}D_{F}$.

(ii)

If $S$ is single-valued at some $(\bar{\lambda},\bar{b})$ with
$S(\bar{\lambda},\bar{b})=\\{\bar{x}\\}$, then $S$ is single-valued and linear
on the polyhedral cone $D_{F}$ containing $(\bar{\lambda},\bar{b})$, where

$F:=\left\\{y\in\mathbbm{R}^{m}\mid A_{i}^{\top}y=1\;\forall i\in
I(\bar{x}),\;-1\leq A_{i}^{\top}y\leq 1\;\forall i\in
I^{0}(\bar{x}),\;A_{i}^{\top}y=-1\;\forall i\in I^{-}(\bar{x})\right\\}.$ (29)

###### Proof.

(i) Let $F\in\mathcal{F}^{0}$. Fix any
$(\lambda,b)\in\operatorname*{int}D_{F}$. In view of the fact that
$\operatorname*{int}D_{F}=P_{1,2}(\operatorname*{ri}S_{F})$ (see Lemma 3.3
(i)), we get from Lemma 3.2 that there are some $x\in
W(\mathcal{A}^{+}(F),\;\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$ and
$y\in\operatorname*{ri}F$ such that $b=Ax+\lambda y$ and
$(\lambda,b,x)\in\operatorname*{ri}S_{F}$ (hence $x\in S(\lambda,b)$ due to
(10)). As $y\in\operatorname*{ri}F$, we get from Lemma 3.1 (ii) that,

$A_{i}^{\top}y=1\;\forall i\in\mathcal{A}^{+}(F),\;-1<A_{i}^{\top}y<1\;\forall
i\in\mathcal{A}^{0}(F),\;A_{i}^{\top}y=-1\;\forall i\in\mathcal{A}^{-}(F).$

In view of the fact that $I^{+}(x)=\mathcal{A}^{+}(F)$ and
$I^{-}(x)=\mathcal{A}^{-}(F)$, we get from [25, Theorem 2.1] that $S$ is
single-valued at $(\lambda,b)$ with $S(\lambda,b)=\\{x\\}$, due to the
definition of $\mathcal{F}^{0}$ and the fact that (26) with $x$ in place of
$\bar{x}$ is satisfied for $y$ given above. As
$(\lambda,b)\in\operatorname*{int}D_{F}$ is given arbitrarily, $S$ is thus
single-valued on $\operatorname*{int}D_{F}$. In view of the Lipschitz
continuity of $S$ on $\operatorname*{dom}S$ (see Theorem 3.1), the single-
valuedness of $S$ on $\operatorname*{int}D_{F}$ can be easily extended to the
boundary of $D_{F}$. That is, $S$ is indeed single-valued on $D_{F}$, i.e.,
$S(\lambda,b)=\\{x\\}$ for all $(\lambda,b)\in D_{F}$, where, due to (23), $x$
must be a solution to the system of linear equations (28). As the columns
$A_{i}$ with $i\in\mathcal{A}^{+}\cup\mathcal{A}^{-}$ are linearly independent
(due to $F\in\mathcal{F}^{0}$), $x$ must be the unique solution to the system
of linear equations (28). Moreover, it is clear to see from (28) that the
dependence of $x$ on $(\lambda,b)$ must be linear.

Now let $F\not\in\mathcal{F}^{0}$ and fix any
$(\lambda,b)\in\operatorname*{int}D_{F}$. In view of the fact that
$\operatorname*{int}D_{F}=P_{1,2}(\operatorname*{ri}S_{F})$ (see Lemma 3.3
(i)), we get from Lemma 3.2 that there are some $x\in
W(\mathcal{A}^{+}(F),\;\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$ and
$y\in\operatorname*{ri}F$ such that $b=Ax+\lambda y$ and
$(\lambda,b,x)\in\operatorname*{ri}S_{F}$ (hence $x\in S(\lambda,b)$ due to
(10)). In view of the fact that $I^{+}(x)=\mathcal{A}^{+}(F)$ and
$I^{-}(x)=\mathcal{A}^{-}(F)$, we get from [25, Theorem 2.1] that $S$ is not
single-valued at $(\lambda,b)$, due to the columns $A_{i}$ with
$i\in\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)=I^{+}(x)\cup I^{-}(x)$ are not
linearly independent as $F\not\in\mathcal{F}^{0}$. This verifies (i).

To show (ii), assume that $S$ is single-valued at some
$(\bar{\lambda},\bar{b})$ with $S(\bar{\lambda},\bar{b})=\\{\bar{x}\\}$ and
that $F$ is given by (29). According to [25, Theorem 2.1], Condition 3.1 is
satisfied for $(\bar{\lambda},\bar{b},\bar{x})$, and in particular the set

$\\{y\in\mathbbm{R}^{m}\mid A_{i}^{\top}y=1\;\forall i\in
I^{+}(\bar{x}),\;-1<A_{i}^{\top}y<1\;\forall\in
I^{0}(\bar{x}),\;A_{i}^{\top}y=-1\;\forall i\in I^{-}(\bar{x})\\}$

is nonempty and hence the relative interior of $F$ (see [26, Corollary 2.1]).
So $F\in\mathcal{F}$. By Lemma 3.1 (i), we have
$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))=(\mathcal{A}^{+}(y),\mathcal{A}^{0}(y),\mathcal{A}^{-}(y))=(I^{+}(\bar{x}),I^{0}(\bar{x}),I^{-}(\bar{x}))$
for all $y\in\operatorname*{ri}F$. Then we have $F\in\mathcal{F}^{0}$ due to
the columns $A_{i}$ of $A$ with $i\in I^{+}(\bar{x})\cup
I^{-}(\bar{x})=\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)$ being linearly
independent (guaranteed by Condition 3.1). As
$S(\bar{\lambda},\bar{b})=\\{\bar{x}\\}$, we have
$(\bar{\lambda},\bar{b},\bar{x})\in\operatorname*{gph}S$. It follows from (15)
that
$A^{\top}(\bar{b}-A\bar{x})\in\bar{\lambda}\partial\|\cdot\|_{1}(\bar{x})$.
Then by (14), we have

$\begin{array}[]{lcl}\bar{x}_{i}>0,&\hskip-5.69046ptA_{i}^{\top}(\bar{b}-A\bar{x})=\bar{\lambda}&\hskip-5.69046pt\forall
i\in\mathcal{A}^{+}(F)\\\ \bar{x}_{i}=0,&\hskip-5.69046pt-\bar{\lambda}\leq
A_{i}^{\top}(\bar{b}-A\bar{x})\leq\bar{\lambda}&\hskip-5.69046pt\forall
i\in\mathcal{A}^{0}(F)\\\
\bar{x}_{i}<0,&\hskip-5.69046ptA_{i}^{\top}(\bar{b}-A\bar{x})=-\bar{\lambda}&\hskip-5.69046pt\forall
i\in\mathcal{A}^{-}(F).\end{array}$

Then by (11) and by noting that $\bar{\lambda}\geq 0$, we have
$(\bar{\lambda},\bar{b},\bar{x})\in S_{F}$ (and hence
$(\bar{\lambda},\bar{b})\in D_{F}$), and the single-valuedness and linearity
of $S$ on $D_{F}$ follow from (i) due to $F\in\mathcal{F}^{0}$. This completes
the proof. ∎

######  Remark 3.1.

Let $F\in\mathcal{F}^{0}\backslash\\{Y^{0}\\}$ and $\tilde{A}$ be the
submatrix of $A$ consisting of the columns $A_{i}$ of $A$ with
$i\in\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)$. Then
$\tilde{A}^{\top}\tilde{A}$ is positive-definite (thus invertible) due to
$\tilde{A}$ being of full column rank, and for any $y\in F$, we have by
definition

$A_{i}^{\top}y=1\quad\forall i\in\mathcal{A}^{+}(F),\quad\quad
A_{i}^{\top}y=-1\quad\forall i\in\mathcal{A}^{-}(F),$

that is, $\tilde{A}^{\top}y$ is a constant vector (independent of a particular
choice of $y\in F$). As $S$ is single-valued and linear on $D_{F}$ and the
element of $S(\lambda,b)$ with $(\lambda,b)\in D_{F}$ is uniquely determined
by the linear system (28), it is clear to see that for any choice of $y\in F$,
the Lipschitz constant of $S$ on $D_{F}$ is

$\kappa:=\|(\tilde{A}^{\top}\tilde{A})^{-1}\tilde{A}^{\top}[-y,\;E]\|,$

where $E\in\mathbbm{R}^{m\times m}$ is the identity matrix. In fact, it
follows from [20, Example 9.3] that $\kappa$ is the Lipschitz constant of the
linear mapping

$M:(\lambda,b)\mapsto(\tilde{A}^{\top}\tilde{A})^{-1}\tilde{A}^{\top}[-y,\;E]\binom{\lambda}{b}.$

In view of the facts that $S(\lambda,b)=\\{x\\}$ for each $(\lambda,b)\in
D_{F}$ if and only if $x_{\mathcal{A}^{0}(F)}=0$ and
$x_{\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)}=M(\lambda,b)$ and that $D_{F}$
has a nonempty interior (see Lemma 3.3 (i)), we confirm that $\kappa$ is also
the Lipschitz constant of $S$ on $D_{F}$.

Alternatively, if $F=Y^{0}$, we get from (28) that $S(\lambda,b)=\\{0\\}$ for
each $(\lambda,b)\in D_{F}$, implying that the Lipschitz constant of $S$ on
$D_{F}$ is 0.

Assume that $S$ is single-valued at some
$(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$ or equivalently that
Condition 3.1 is satisfied. It turns out from the above corollary that, the
single-valuedness and linearity of $S$ can be maintained not only on the ray
through $(\bar{\lambda},\bar{b})$ (due to $\operatorname*{gph}S$ being a
cone), but also on some polyhedral cone $D_{F}$ containing
$(\bar{\lambda},\bar{b})$, where $F$ is a nonempty face of $Y^{0}$. However,
the single-valuedness and/or linearity of $S$ may not be maintained around
$(\bar{\lambda},\bar{b})$, as it is possible that $(\bar{\lambda},\bar{b})$
belongs to the boundary of some $D_{F^{\prime}}$ with
$F^{\prime}\in\mathcal{F}\backslash\mathcal{F}^{0}$ (see Example 4.1 below).
To maintain the single-valuedness and/or linearity of $S$ around some
$(\bar{\lambda},\bar{b})$, we resort to some stronger conditions, i.e.,
Conditions 3.2 and 3.3 introduced above.

######  Corollary 3.3.

Assume that $A$ is of full row rank. Let
$(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$ with $\bar{\lambda}>0$. The
following equivalences hold:

(i)

$S$ is single-valued and linear on each $D_{F}$ containing
$(\bar{\lambda},\bar{b})$ if and only if Condition 3.2 is satisfied.

(ii)

$S$ is single-valued and linear on the unique $D_{F}$ having
$(\bar{\lambda},\bar{b})$ in its interior if and only if Condition 3.3 is
satisfied.

###### Proof.

(i) To verify the ‘only if’ part of (i), we assume that $S$ is single-valued
and linear on $D_{F}$ for any $F\in\mathcal{F}$ with
$(\bar{\lambda},\bar{b})\in D_{F}$. Let $\bar{x}\in S(\bar{\lambda},\bar{b})$.
In view of $\bar{\lambda}>0$, we denote
$\bar{y}:=(\bar{b}-A\bar{x})/\bar{\lambda}$. It follows from
$(\bar{\lambda},\bar{b},\bar{x})\in\operatorname*{gph}S$ and (15) that
$A^{\top}(\bar{b}-A\bar{x})\in\bar{\lambda}\partial\|\cdot\|_{1}(\bar{x})$.
Then by (14), we have $I^{+}(\bar{x})\subset\mathcal{A}^{+}(\bar{y})$ and
$I^{-}(\bar{x})\subset\mathcal{A}^{-}(\bar{y})$. It follows from the
definition that
$J(\bar{\lambda},\bar{b},\bar{x})=\mathcal{A}^{+}(\bar{y})\cup\mathcal{A}^{-}(\bar{y})$.
Moreover, define

$\hat{F}:=\\{y\in\mathbbm{R}^{m}\mid A_{i}^{\top}y=1\;\forall
i\in\mathcal{A}^{+}(\bar{y}),\;-1\leq A_{i}^{\top}y\leq
1\;\forall\in\mathcal{A}^{0}(\bar{y}),\;A_{i}^{\top}y=-1\;\forall
i\in\mathcal{A}^{-}(\bar{y})\\}.$

Thus, $\hat{F}\in\mathcal{F}$ and $\bar{y}\in\operatorname*{ri}\hat{F}$ (see
[26, Corollary 2.1]). Then we deduce from Lemma 3.1 (i) that

$(\mathcal{A}^{+}(\hat{F}),\mathcal{A}^{0}(F),\mathcal{A}^{-}(\hat{F}))=(\mathcal{A}^{+}(\bar{y}),\mathcal{A}^{0}(\bar{y}),\mathcal{A}^{-}(\bar{y})),$

and hence that

$J(\bar{\lambda},\bar{b},\bar{x})=\mathcal{A}^{+}(\hat{F})\cup\mathcal{A}^{-}(\hat{F}).$

As $\bar{x}\in
W(I^{+}(\bar{x}),I^{0}(\bar{x}),I^{-}(\bar{x}))\subset\operatorname*{cl}W((\mathcal{A}^{+}(\hat{F}),\mathcal{A}^{0}(\hat{F}),\mathcal{A}^{-}(\hat{F}))$
and $\bar{y}\in\operatorname*{ri}\hat{F}$, we get from that Lemma 3.3 (i) that
$(\bar{\lambda},\bar{b})\in D_{\hat{F}}$. By assumption, we get that $S$ is
single-valued and linear on $D_{\hat{F}}$. Then we deduce from Corollary 3.2
(i) that $\hat{F}\in\mathcal{F}^{0}$, or in other words the columns $A_{i}$
with $i\in J(\bar{\lambda},\bar{b},\bar{x})$ are linearly independent. That
is, Condition 3.2 is satisfied.

To verify the ‘if’ part of (i), assume that Condition 3.2 is satisfied for
some $(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$ with $\bar{x}\in
S(\bar{\lambda},\bar{b})$. Fix any $F\in\mathcal{F}$ with
$(\bar{\lambda},\bar{b})\in D_{F}$, by Corollary 3.1, we have
$(\bar{\lambda},\bar{b},\bar{x})\in S_{F}$. Thus by Proposition 3.1 we have

$A_{i}^{\top}(\bar{b}-A\bar{x})=\bar{\lambda},\quad\forall
i\in\mathcal{A}^{+}(F)\quad\mbox{and}\quad
A_{i}^{\top}(\bar{b}-A\bar{x})=-\bar{\lambda},\quad\forall
i\in\mathcal{A}^{-}(F).$

Thus, $\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)\subset
J(\bar{\lambda},\bar{b},\bar{x})$. This, combined with Condition 3.2, yields
that $F\in\mathcal{F}^{0}$. Then we deduce from Corollary 3.2 that $S$ is
single-valued and linear on $D_{F}$.

(ii) We introduce a face of $Y^{0}$ as

$F:=\\{y\in\mathbb{R}^{m}\mid A_{i}^{\top}y=1~{}\mbox{if}~{}i\in
I^{+}(\bar{x}),~{}-1\leq A_{i}^{\top}y\leq 1~{}\mbox{if}~{}i\in
I^{0}(\bar{x}),~{}A_{i}^{\top}y=-1~{}\mbox{if}~{}i\in I^{-}(\bar{x})\\}.$

It is obvious that $(\bar{\lambda},\bar{b})\in D_{F}$.

To verify the ‘only if’ part of (ii), we assume that
$(\bar{\lambda},\bar{b})\in\operatorname*{int}D_{F}$, and $S$ is single-valued
and linear on $D_{F}$. Let $\bar{x}\in S(\bar{\lambda},\bar{b})$. This,
combined with Lemma 3.3 (i) that there exists $x\in\mathbbm{R}^{n}$ such that
$(\bar{\lambda},\bar{b},x)\in\operatorname*{ri}S_{F}$. Moreover, $S$ is
single-valued at $(\bar{\lambda},\bar{b})$, thus, $\bar{x}=x$, and hence
$(\bar{\lambda},\bar{b},\bar{x})\in\operatorname*{ri}S_{F}$. Then we deduce
from Lemma 3.2 that $|A_{i}^{\top}(\bar{b}-A\bar{x})|<\bar{\lambda}$ for all
$i\in\mathcal{A}^{0}(F)$ and $I^{0}(\bar{x})=\mathcal{A}^{0}(F)$. Moreover,
$S$ is single-valued at $(\bar{\lambda},\bar{b})$ with
$S(\bar{\lambda},\bar{b})=\\{\bar{x}\\}$, then we deduce from [25, Theorem
2.1] that the columns $A_{i}$ of $A$ with $i\in I^{+}(\bar{x})\cup
I^{-}(\bar{x})$ are linearly independent. Thus Condition 3.3 holds.

To verify the ‘if’ part of (ii), we assume that Condition 3.3 is satisfied for
some $(\bar{\lambda},\bar{b})\in\operatorname*{dom}S$ with $\bar{x}\in
S(\bar{\lambda},\bar{b})$. It follows from (15) that
$A^{\top}(\bar{b}-A\bar{x})\in\bar{\lambda}\partial\|\cdot\|_{1}(\bar{x})$.
Then by (14), we have

$\begin{array}[]{lcl}\bar{x}_{i}>0,&\hskip-5.69046ptA_{i}^{\top}(\bar{b}-A\bar{x})=\bar{\lambda}&\hskip-5.69046pt\forall
i\in I^{+}(\bar{x})\\\
\bar{x}_{i}<0,&\hskip-5.69046ptA_{i}^{\top}(\bar{b}-A\bar{x})=-\bar{\lambda}&\hskip-5.69046pt\forall
i\in I^{-}(\bar{x}).\end{array}$ (30)

Moreover, we deduce from Condition 3.3 that

$x_{0}=0,~{}~{}-\bar{\lambda}<A_{i}^{\top}(\bar{b}-A\bar{x})<\bar{\lambda}~{}~{}\forall
i\in I^{0}(\bar{x}).$ (31)

Let $\bar{y}:=(\bar{b}-A\bar{x})/\bar{\lambda}$, then by [26, Corollary 2.1],
we have $\bar{y}\in\operatorname*{ri}F$. Thus, we deduce from Lemma 3.1 (i),
(30) and (31) that

$(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))=(\mathcal{A}^{+}(\bar{y}),\mathcal{A}^{0}(\bar{y}),\mathcal{A}^{-}(\bar{y}))=(I^{+}(\bar{x}),I^{0}(\bar{x}),I^{-}(\bar{x})).$

Therefore, $\bar{x}\in
W(\mathcal{A}^{+}(F),\mathcal{A}^{0}(F),\mathcal{A}^{-}(F))$. This, combined
with $\bar{b}=A\bar{x}+\bar{\lambda}\bar{y}$, $\bar{y}\in\operatorname*{ri}F$
and Lemma 3.3 (i) that $(\bar{\lambda},\bar{b})\in\operatorname*{int}D_{F}$.
Moreover, from Condition 3.3, we dedcue that the columns $A_{i}$ of $A$ with
$i\in\mathcal{A}^{+}(F)\cup\mathcal{A}^{-}(F)$ are linearly independent, due
to $(\mathcal{A}^{+}(F),\mathcal{A}^{-}(F))=(I^{+}(\bar{x}),I^{-}(\bar{x}))$.
Thus, $F\in\mathcal{F}^{0}$, i.e., $S$ is single-valued and linear on $D_{F}$.
This completes the proof. ∎

######  Remark 3.2.

In [3], Berk et al. proved that if Condition 3.2 (resp. Condition 3.3) holds
at $(\bar{\lambda},\bar{b})$ with $\bar{\lambda}>0$, then Condition 3.2 (resp.
Condition 3.3) holds in a neighborhood of $(\bar{\lambda},\bar{b})$, entailing
the single-valuedness of $S$ around $(\bar{\lambda},\bar{b})$. Furthermore,
they established the directional differentiability and continuous
differentiability of $S$ under Conditions 3.2 and 3.3 respectively by virtue
of graphical coderivative. From the perspective of polyhedral structure, the
above corollary tells us that $S$ is single-valued and piecewise linear around
$(\bar{\lambda},\bar{b})$ if and only if Condition 3.2 holds at
$(\bar{\lambda},\bar{b})$ with $\bar{\lambda}>0$ and that $S$ is single-valued
and linear around $(\bar{\lambda},\bar{b})$ if and only if Condition 3.3 holds
at $(\bar{\lambda},\bar{b})$ with $\bar{\lambda}>0$. In view of the
linear/piecewise linear structure of $S$ around $(\bar{\lambda},\bar{b})$ just
mentioned, the directional differentiability and continuous differentiability
of $S$ at $(\bar{\lambda},\bar{b})$ can be obtained in a straightforward way
by assuming Conditions 3.2 and 3.3, respectively.

In Proposition 3.1, we obtain a partition of $\operatorname*{gph}S$ by virtue
of $S_{F}$ with $F\in{\cal F}$, the set of nonempty faces of $Y^{0}$, as we
have shown in Lemma 3.2 that $\operatorname*{ri}S_{F^{\prime}}\cap
S_{F}=\emptyset$ for all $F^{\prime},F\in{\cal F}$ with $F^{\prime}\not=F$.
Next we show that this partition is optimal and unique in the sense described
below.

######  Corollary 3.4 (Optimal and Unique Partition).

Assume that $A$ is of full row rank and that there are closed and convex sets
$C_{l}$ ($l=1,\cdots,L$) such that

$\operatorname*{gph}S=\bigcup_{l=1}^{L}C_{l}.$

Then $L\geq|\mathcal{F}|$, and if in addition $L=|\mathcal{F}|$, then
$\\{C_{l}\mid l=1,\cdots,L\\}=\\{S_{F}\mid F\in\mathcal{F}\\}.$

###### Proof.

Suppose by contradiction that $L<|\mathcal{F}|$. Following (10) and Lemma 3.2,
we have $\operatorname*{ri}S_{F}\subset\operatorname*{gph}S$ and
$\operatorname*{ri}S_{F}\cap\operatorname*{ri}S_{F^{\prime}}=\emptyset$ for
all $F,F^{\prime}\in\mathcal{F}$ with $F\not=F^{\prime}$. Then there are some
$C_{l}$ with $1\leq l\leq L$ and $F,F^{\prime}\in\mathcal{F}$ with
$F\not=F^{\prime}$ such that $C_{l}\cap\operatorname*{ri}S_{F}\not=\emptyset$
and $C_{l}\cap\operatorname*{ri}S_{F^{\prime}}\not=\emptyset$. Let
$(\bar{\lambda},\bar{b},\bar{x})\in C_{l}\cap\operatorname*{ri}S_{F}$ and
$(\tilde{\lambda},\tilde{b},\tilde{x})\in
C_{l}\cap\operatorname*{ri}S_{F^{\prime}}$ be two distinct triples and
$(\lambda_{\theta},b_{\theta},x_{\theta}):=(1-\theta)(\bar{\lambda},\bar{b},\bar{x})+\theta(\tilde{\lambda},\tilde{b},\tilde{x}),\theta\in[0,1]$.
Then it follows from Lemma 3.3 (ii) that
$(\bar{\lambda},\bar{b})\in\operatorname*{int}D_{F}$ and
$(\tilde{\lambda},\tilde{b})\in\operatorname*{int}D_{F^{\prime}}$. As $C_{l}$
is convex, we have $(\lambda_{\theta},b_{\theta},x_{\theta})\in
C_{l}\subset\operatorname*{gph}S$ for all $\theta\in[0,1]$, contradicting to
Lemma 3.3 (iv). This indicates that $L\geq|\mathcal{F}|$.

Now we consider the case that $L=|\mathcal{F}|$. For the sake of simplicity of
notation, let $\mathcal{F}:=\\{F_{1},\cdots,F_{L}\\}$. According to the
previous argument, each $C_{l}$ can contain at most one
$\operatorname*{ri}S_{F}$ for some $F\in{\cal F}$. Without loss of generality
we can assume that $\operatorname*{ri}S_{F_{l}}\subset C_{l}$ for all
$l=1,\cdots,L$. As the $S_{F_{l}}$’s are closed and convex and $C_{l}$’s are
closed, we have
$S_{F_{l}}=\operatorname*{cl}(\operatorname*{ri}S_{F_{l}})\subset C_{l}$ for
all $l=1,\cdots,L$. Now we claim that $S_{F_{l}}=C_{l}$ for all
$l=1,\cdots,L$. Suppose by contradiction that there is some
$l^{\prime}\in\\{1,\cdots,L\\}$ such that $S_{F_{l^{\prime}}}\subsetneq
C_{l^{\prime}}$. Then we get by definition and Corollary 3.1 that

$D_{F_{l^{\prime}}}=P_{1,2}(S_{F_{l^{\prime}}})\subsetneq
P_{1,2}(C_{l^{\prime}}).$

Noting that $D_{F_{l^{\prime}}}$ is closed with
$\operatorname*{int}(D_{F_{l^{\prime}}})\not=\emptyset$ (see Lemma 3.3 (i))
and that $P_{1,2}(C_{l^{\prime}})$ is convex, we have
$\operatorname*{int}\left(P_{1,2}(C_{l^{\prime}})\backslash
D_{F_{l^{\prime}}}\right)\not=\emptyset$. It then follows from Lemma 3.3 (ii)
that there is some $l\in\\{1,\cdots,L\\}$ such that $F_{l}\not=F_{l^{\prime}}$
and

$\operatorname*{int}\left(P_{1,2}(C_{l^{\prime}})\backslash
D_{F_{l^{\prime}}}\right)\cap\operatorname*{int}(D_{F_{l}})\not=\emptyset.$

Let $(\lambda,b)\in\operatorname*{int}\left(P_{1,2}(C_{l^{\prime}})\backslash
D_{F_{l^{\prime}}}\right)\cap\operatorname*{int}(D_{F_{l}})$. Then there is
some $x$ such that $(\lambda,b,x)\in C_{l^{\prime}}$. Let
$(\lambda^{\prime},b^{\prime},x^{\prime})\in S_{F_{l^{\prime}}}$ with
$(\lambda^{\prime},b^{\prime})\in\operatorname*{int}(D_{F_{l^{\prime}}})$.
Then we have $(\lambda^{\prime},b^{\prime},x^{\prime})\in C_{l^{\prime}}$. As
$C_{l^{\prime}}$ is convex, we have

$[(\lambda,b,x),\,(\lambda^{\prime},b^{\prime},x^{\prime})]\subset
C_{l^{\prime}}\subset\operatorname*{gph}S,$

contradicting to Lemma 3.3 (iv) due to
$(\lambda,b)\in\operatorname*{int}(D_{F_{l}})$ and
$(\lambda^{\prime},b^{\prime})\in\operatorname*{int}(D_{F_{l^{\prime}}})$.
This completes the proof. ∎

To conclude this section, we present the Lipschitz continuity of the optimal
solution multifunction of the extended dual $\ell_{1}$ regularization problem
(6).

Let $T:\mathbbm{R}_{+}\times\mathbbm{R}^{m}\rightrightarrows\mathbbm{R}^{m}$
be the optimal solution multifunction of extended dual $\ell_{1}$
regularization problem (6). Then it follows from [20, Example 11.41] that

$\left.\begin{array}[]{l}x\in S(\lambda,b)\\\ y\in
T(\lambda,b)\end{array}\right\\}\Longleftrightarrow\left\\{\begin{array}[]{l}Ax+\lambda
y=b\\\ A^{\top}y\in\partial\|\cdot\|_{1}(x)\end{array}\right\\}.$ (32)

Although $S$ is not always single-valued, it follows from (22) in the proof of
Proposition 3.2 (see also [25]) that the mapping $(\lambda,b)\mapsto Ax$ is
single-valued, where $x\in S(\lambda,b)$. Moreover, we deduce from Corollary
3.1 that it is also piecewise linear. This, combined with (32), implies the
Lipschitz continuity and linearity of $(\lambda,b)\mapsto\lambda T(\lambda,b)$
directly.

######  Proposition 3.3.

Assume that $A$ is of full row rank. Then $\lambda T(\lambda,b)$ is piecewise
linear.

######  Remark 3.3.

(i)

Due to the fact that $T$ is a bounded multifunction as $T(\lambda,b)\subset
Y^{0}$, it follows from Proposition 3.3 that $T$ is Lipschitz continuous on
$[\lambda_{0},+\infty)\times\mathbb{R}^{m}$ for any $\lambda_{0}>0.$

(ii)

While (6) is the dual of the problem (4), however, when $\lambda=0$, (6) is
not the dual of problem (2) but is the dual of problem (3) with $\lambda=0$.
Actually, let $L(\lambda,b):=\lambda T(\lambda,b)\
\forall(\lambda,b)\in\mathbbm{R}_{+}\times\mathbbm{R}^{m}.$ Then it is easy to
see that $L$ is the optimal solution multifunction of

$\max_{y\in\mathbbm{R}^{m}}\;\langle
b,y\rangle-\frac{1}{2}\|y\|^{2}\quad\mbox{subject to}\;y\in\lambda
Y^{0}=\\{y\in\mathbbm{R}^{m}\mid\|A^{\top}y\|_{\infty}\leq\lambda\\},$

which is the dual of problem (3) with $\lambda\geq 0.$

##  4 An illustrative example

We give an example to illustrate the decomposition of $\operatorname*{dom}S$
as the union of some polyhedral cones as well as the analytic expressions of
$S(\lambda,b)$ on each of these polyhedral cones.

Figure 1: Tilted half unit ball with $\lambda$-axis facing the readers:
Truncations of the polyhedral cones $D_{F_{i}}$ ($i=1,\cdots,9$) with the unit
ball, where the $U_{i}$’s denote their unit extreme directions.

######  Example 4.1.

Consider the extended $\ell_{1}$ regularization problem (4) with the following
matrix of full row rank:

$A=\left[\begin{array}[]{ccc}1&0&2\\\ 0&2&-2\end{array}\right],$

which has appeared both in [3, Example 4.18] and [25]. Denote by $A_{i}$
($i=1,2,3$) the $i$-th column of $A$. By definition we have

$Y^{0}:=\\{y\in\mathbbm{R}^{2}\mid-1\leq A_{i}^{\top}y\leq 1\;\forall
i=1,2,3\\}=\operatorname*{conv}\\{V_{1},V_{2},V_{3},V_{4}\\},$

where $V_{1}:=(1,1/2)^{\top}$, $V_{2}:=(0,-1/2)^{\top}$,
$V_{3}:=(-1,-1/2)^{\top}$ and $V_{4}:=(0,1/2)^{\top}$ are extreme points of
$Y^{0}$. Clearly, the polygon $Y^{0}$ has 9 nonempty faces $F_{i}$
($i=1,\cdots,9$). For each $F_{i}$, we rely on the equality in Lemma 3.1 (i)
to calculate the index partition sets
$(\mathcal{A}^{+}(F_{i}),\mathcal{A}^{0}(F_{i}),\mathcal{A}^{-}(F_{i}))$.
According to Lemma 3.3 (ii), we have
$\operatorname*{dom}S=\mathbbm{R}_{+}\times\mathbbm{R}^{2}=\displaystyle\bigcup_{i=1}^{9}D_{F_{i}},$
where the extreme directions of each polyhedral cone $D_{F_{i}}$ can be
constructed in terms of columns $A_{j}$ with
$j\in\mathcal{A}^{+}(F_{i})\cup\mathcal{A}^{-}(F_{i})$ and extreme points
$V_{k}\;(k=1,\cdots,4)$ of $Y^{0}$ (see the last statement of Lemma 3.3 (i).)
These extreme directions are recorded as columns $U_{j}(j=1,\cdots,8)$ of the
matrix

$U:=\left[\begin{array}[]{cccccccc}0&0&0&0&1&1&1&1\\\
A_{2}&A_{3}&-A_{2}&-A_{3}&V_{1}&V_{2}&V_{3}&V_{4}\\\ \end{array}\right].$

Therefore, by virtue of (23) and (28), we can also get the formulas of
$S(\lambda,b)$ on each $D_{F_{i}}$. Note that $(0,A_{1}^{\top})^{\top}$ is not
an extreme direction of $D_{F_{1}}$. Indeed, we have
$(\mathcal{A}^{+}(F_{1}),\mathcal{A}^{0}(F_{1}),\mathcal{A}^{-}(F_{1}))=(\\{1,2,3\\},\emptyset,\emptyset)$.
Although $D_{F_{1}}$ can be generated from $(0,A_{1}^{\top})^{\top}$, $U_{1}$,
$U_{2}$ and $U_{5}$ according to the rule presented in Lemma 3.3 (i), we
notice that $(0,A_{1}^{\top})^{\top}$ is not an extreme direction of
$D_{F_{1}}$ due to

$(0,A_{1}^{\top})^{\top}=\frac{1}{2}U_{1}+\frac{1}{2}U_{2}.$

Similarly, we note that $(0,-A_{1}^{\top})^{\top}$ is merely a generator of
$D_{F_{2}}$, but not an extreme direction of $D_{F_{2}}$.

In Figure 1, we plot the truncated partitions of $\operatorname*{dom}S$ with
the unit ball.

In Table 1, we summarize the details of the extreme points (labelled
Ext($F_{i}$)) of $F_{i}$, the partitions
$(\mathcal{A}^{+}(F_{i}),\mathcal{A}^{0}(F_{i}),\mathcal{A}^{-}(F_{i}))$ of
the index set $I$, the extreme directions (labelled Ext-Dir($D_{F_{i}}$) of
$D_{F_{i}}$ and the formulas of $S_{i}(\lambda,b):=S|_{D_{F_{i}}}(\lambda,b)$
on each $D_{F_{i}}(i=1,\cdots,9)$, where

$S_{1}(\lambda,b)=\left\\{\left(b_{1}-\lambda-2t,\,\frac{b_{2}}{2}-\frac{\lambda}{4}+t,\,t\right)\
\left|\ \left(\frac{\lambda}{4}-\frac{b_{2}}{2}\right)_{+}\leq
t\leq\frac{b_{1}-\lambda}{2}\right.\right\\}\quad\forall(\lambda,b)\in
D_{F_{1}}$ (33)

and

$S_{2}(\lambda,b)=\left\\{\left(b_{1}+\lambda-2t,\,\frac{b_{2}}{2}+\frac{\lambda}{4}+t,\,t\right)\
\left|\ \frac{b_{1}+\lambda}{2}\leq
t\leq-\left(\frac{\lambda}{4}+\frac{b_{2}}{2}\right.\right)_{+}\right\\}\quad\forall(\lambda,b)\in
D_{F_{2}}.$ (34)

Clearly, $S$ is not single-valued on both of the interiors of $D_{F_{1}}$ and
$D_{F_{2}}$, but single-valued on both of the boundaries of $D_{F_{1}}$ and
$D_{F_{2}}$. Moreover, $S$ is single-valued and linear on
$D_{F_{i}}(i=3,\cdots,9)$.

$i$ |  Ext($F_{i}$) | $(\mathcal{A}^{+}(F_{i}),\mathcal{A}^{0}(F_{i}),\mathcal{A}^{-}(F_{i}))$ |  Ext-Dir($D_{F_{i}}$) | $S_{i}(\lambda,b)$
---|---|---|---|---
1 | $V_{1}$ | $(\\{1,2,3\\},\emptyset,\emptyset)$ | $U_{1},U_{2},U_{5}$ |  see (33)
2 | $V_{3}$ | $(\emptyset,\emptyset,\\{1,2,3\\})$ | $U_{3},U_{4},U_{7}$ |  see (34)
3 | $V_{1},V_{4}$ | $(\\{2\\},\\{1,3\\},\emptyset)$ | $U_{1},U_{5},U_{8}$ | $\\{(0,\,-\frac{\lambda}{4}+\frac{b_{2}}{2},\,0)\\}$
4 | $V_{3},V_{2}$ | $(\emptyset,\\{1,3\\},\\{2\\})$ | $U_{3},U_{6},U_{7}$ | $\\{(0,\,\frac{\lambda}{4}+\frac{b_{2}}{2},\,0)\\}$
5 | $V_{1},V_{2}$ | $(\\{3\\},\\{1,2\\},\emptyset)$ | $U_{2},U_{5},U_{6}$ | $\\{(0,\,0,\,\frac{b_{1}}{4}-\frac{b_{2}}{4}-\frac{\lambda}{8})\\}$
6 | $V_{3},V_{4}$ | $(\emptyset,\\{1,2\\},\\{3\\})$ | $U_{4},U_{7},U_{8}$ | $\\{(0,\,0,\,\frac{b_{1}}{4}-\frac{b_{2}}{4}+\frac{\lambda}{8})\\}$
7 | $V_{4}$ | $(\\{2\\},\\{1\\},\\{3\\})$ | $U_{1},U_{4},U_{8}$ | $\\{(0,\,\frac{b_{1}}{2}+\frac{b_{2}}{2}-\frac{\lambda}{4},\,\frac{b_{1}}{2})\\}$
8 | $V_{2}$ | $(\\{3\\},\\{1\\},\\{2\\})$ | $U_{2},U_{3},U_{6}$ | $\\{(0,\,\frac{b_{1}}{2}+\frac{b_{2}}{2}+\frac{\lambda}{4},\,\frac{b_{1}}{2})\\}$
9 | $V_{1},V_{2},V_{3},V_{4}$ | $(\emptyset,\\{1,2,3\\},\emptyset)$ | $U_{5},U_{6},U_{7},U_{8}$ | $\\{(0,\,0,\,0)\\}$
Table 1: Decomposition of $\operatorname*{dom}S$ into 9 polyhedral cones,
constructed from columns $A_{i}$ of $A$ and extreme points $V_{k}$ of $Y^{0}$,
and expressions of $S(\lambda,b)$ on each of the polyhedral cones.

## References

  * [1] J.-P. Aubin and I. Ekeland.  Applied Nonlinear Analysis.  Wiley, New York, 1984.
  * [2] G. Beer, M. J. Cánovas, M. A. López, and J. Parra.  Lipschitz modulus of linear and convex inequality systems with the Hausdorff metric.  Math. Program., 189(1-2):75–98, 2021.
  * [3] A. Berk, S. Brugiapaglia, and T. Hoheisel.  Lasso reloaded: A variational analysis perspective with applications to compressed sensing.  SIAM J. Math. Data Sci., 5(4):1102–1129, 2023.
  * [4] Emmanuel J Candès, Justin Romberg, and Terence Tao.  Stable signal recovery from incomplete and inaccurate measurements.  Comm. Pure Appl. Math., 59:1207–1223, 2006.
  * [5] David L Donoho.  Compressed sensing.  IEEE Transactions on Information Theory, 52(4):1289–1306, 2006\.
  * [6] David L. Donoho and Michael Elad.  Optimally sparse representation in general (nonorthogonal) dictionaries via $\ell^{1}$ minimization.  Proc. Natl. Acad. Sci. USA, 100(5):2197–2202, 2003.
  * [7] Asen L Dontchev and R Tyrrell Rockafellar.  Characterizations of strong regularity for variational inequalities over polyhedral convex sets.  SIAM J. Optim., 6(4):1087–1105, 1996.
  * [8] J.-J. Fuchs.  On sparse representations in arbitrary redundant bases.  IEEE Trans. Inform. Theory, 50(6):1341–1344, 2004.
  * [9] Helmut Gfrerer and Jiří V Outrata.  On Lipschitzian properties of implicit multifunctions.  SIAM J. Optim., 26(4):2160–2189, 2016.
  * [10] M Seetharama Gowda and R. Sznajder.  On the Lipschitzian properties of polyhedral multifunctions.  Mathematical Programming, 74:267–278, 1996.
  * [11] Shaoyan Guo and Huifu Xu.  Data perturbations in stochastic generalized equations: statistical robustness in static and sample average approximated models.  Math. Program., 202(1-2):135–168, 2023.
  * [12] Shaoning Han and Jong-Shi Pang.  Continuous selections of solutions to parametric variational inequalities.  SIAM Journal on Optimization, 34(1):870–892, 2024.
  * [13] Alexander D Ioffe.  On variational inequalities over polyhedral sets.  Math. Program., 168(1):261–278, 2018.
  * [14] Dinh The Luc.  Multiobjective linear programming.  Springer, Cham, 2016.  An introduction.
  * [15] Olvi L Mangasarian and T-H Shiau.  Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems.  SIAM J. Control Optim., 25(3):583–595, 1987.
  * [16] K.W. Meng, M.H. Li, W.F. Yao, and X.Q. Yang.  Lipschitz-like property relative to a set and the generalized Mordukhovich criterion.  Math. Program., 189(1):455–489, 2021.
  * [17] Boris S. Mordukhovich, Jiří V. Outrata, and M. Ebrahim Sarabi.  Full stability of locally optimal solutions in second-order cone programs.  SIAM Journal on Optimization, 24(4):1581–1613, 2014.
  * [18] Stephen M Robinson.  Some continuity properties of polyhedral multifunctions.  Math. Program. Stud., 14:206–214, 1981.
  * [19] R Tyrrell Rockafellar.  Convex Analysis.  Press Princeton Landmarks in Mathematics and Physics, 18, Revised Edition, 1997.
  * [20] R Tyrrell Rockafellar and Roger J-B Wets.  Variational Analysis.  Springer Science & Business Media, 2009.
  * [21] A. Schrijver.  Theory of Linear and Integer Programming.  Wiley-Intersci. Publ., 1986.
  * [22] R. Tibshirani.  The Lasso problem and uniqueness.  Electron. J. Stat., 7:1456–1490, 2013.
  * [23] D. W. Walkup and R. J.-B. Wets.  A Lipschitzian characterization of convex polyhedra.  Proc. Amer. Math. Soc., 20:167–173, 1969.
  * [24] Nguyen Dong Yen.  Lipschitz continuity of solutions of variational inequalities with a parametric polyhedral constraint.  Math. Oper. Res., 20(3):695–708, 1995.
  * [25] H. Zhang, W. Yin, and L. Cheng.  Necessary and sufficient conditions of solution uniqueness in 1-norm minimization.  J. Optim. Theory Appl., 164:109–122, 2015.
  * [26] X.Y. Zheng and X.Q. Yang.  Fully piecewise linear vector optimization problems.  J. Optim. Theory Appl., 190(2):461–490, 2021.