Solution Uniqueness of Convex Piecewise Affine Functions Based Optimization with Applications to Constrained ℓ 1 Minimization
Loading...
Links to Files
Permanent Link
Author/Creator
Author/Creator ORCID
Date
2017-11-16
Type of Work
Department
Program
Citation of Original Publication
Seyedahmad Mousavi, Jinglai Shen , Solution Uniqueness of Convex Piecewise Affine Functions Based Optimization with Applications to Constrained ℓ 1 Minimization, Mathematics, Optimization and Control, 2017, https://arxiv.org/abs/1711.05882
Rights
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
Abstract
In this paper, we study the solution uniqueness of an individual feasible vector of a class of convex
optimization problems involving convex piecewise affine functions and subject to general polyhedral
constraints. This class of problems incorporates many important polyhedral constrained ℓ1 recovery
problems arising from sparse optimization, such as basis pursuit, LASSO, and basis pursuit denoising,
as well as polyhedral gauge recovery. By leveraging the max-formulation of convex piecewise affine
functions and convex analysis tools, we develop dual variables based necessary and sufficient uniqueness
conditions via simple and yet unifying approaches; these conditions are applied to a wide range of
ℓ1 minimization problems under possible polyhedral constraints. An effective linear program based
scheme is proposed to verify solution uniqueness conditions. The results obtained in this paper not only
recover the known solution uniqueness conditions in the literature by removing restrictive assumptions
but also yield new uniqueness conditions for much broader constrained ℓ1-minimization problems.