Volume 25, 2019
|Number of page(s)||27|
|Published online||25 October 2019|
Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained ℓ1 minimization
Department of Mathematics and Statistics, University of Maryland Baltimore County,
* Corresponding author: firstname.lastname@example.org
Accepted: 5 November 2018
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.
Mathematics Subject Classification: 65K05 / 90C05 / 90C25 / 90C30 / 90C46
Key words: Solution existence and uniqueness / convex polyhedral function / ℓ1 minimization / basis pursuit / LASSO
© EDP Sciences, SMAI 2019
Initial download of the metrics may take a while.