On the characterizations of solutions to perturbed l₁ conic optimization problem

ABSTRACT

This paper focuses on perturbation analysis of the $l_1$ conic optimization problem, which is defined as the optimization problem over the epigraph of the weighted $l_1$ norm. The motivation for studying such problem comes from recent interest in the $l_1$ regularized (possibly non-convex) optimization problems arising in a wide variety of fields such as compressive sensing, signal processing and statistical learning. This paper first derives some important geometrical properties of relevant closed convex cone, including the tangent cone, the normal cone and the critical cone. We then show that under the Robinson's constraint qualification, the following conditions are equivalent: the constraint nondegeneracy and the strong second order sufficient optimality condition, the strong regularity of the Karush–Kuhn–Tucker (KKT) point, and the nonsingularity of Clarke's generalized Jacobian of the KKT system, and others. We further provide an important characterization of the isolated calmness for the $l_1$ conic optimization problem, namely, under the Robinson's constraint qualification, the isolated calmness of the KKT solution mapping holds if and only if the strict constraint qualification and the second order sufficient condition hold at a locally optimal solution. These characterizations provide theoretical results to design and analyse efficient algorithms for the $l_1$ conic optimization problem.

KEYWORDS:

• $l_1$ regularization
• perturbation analysis
• second order optimality conditions
• strong regularity
• isolated calmness

AMS SUBJECT CLASSIFICATION (2010):

• 90C31
• 49J53
• 90C46

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Yong-Jin Liu http://orcid.org/0000-0002-6586-2862

Additional information

Funding

The author's research is supported by the National Natural Science Foundation of China [grant numbers 11371255, 11871153 and 11701091], Fujian Education and Research Program for Young Teachers [grant number JAT170096].