  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.
