On the characterizations of solutions to perturbed l1 conic optimization problem. (3rd June 2019)

• Record Type: Journal Article
• Authors: Liu, Yong-Jin; Li, Ruonan; Wang, Bo
• Is Part Of: Optimization. Volume 68:Number 6(2019)
• Page Start: 1157
• Page End: 1186
• Publication Date: 2019-06-03
• Subjects: l1 regularization -- perturbation analysis -- second order optimality conditions -- strong regularity -- isolated calmness; 90C31 -- 49J53 -- 90C46; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2019.1576668
• Languages: English
• ISSNs: 0233-1934

Abstract

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.