Sparse Solutions of a Class of Constrained Optimization Problems

DOI10.1287/MOOR.2021.1194zbMATH Open1501.90078arXiv1907.00880OpenAlexW2996484635MaRDI QIDQ5868942FDOQ5868942

Xiaojun Chen, Lei Yang, Shuhuang Xiang

Publication date: 26 September 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Abstract: In this paper, we consider a well-known sparse optimization problem that aims to find a sparse solution of a possibly noisy underdetermined system of linear equations. Mathematically, it can be modeled in a unified manner by minimizing $$ subject to $$ for given $Ainmathbb{R}^{mimesn}$, $$, $sigmageq0$, $0leqpleq1$ and $qgeq1$. We then study various properties of the optimal solutions of this problem. Specifically, without any condition on the matrix $A$, we provide upper bounds in cardinality and infinity norm for the optimal solutions, and show that all optimal solutions must be on the boundary of the feasible set when $0<p<1$. Moreover, for $qin1,infty$, we show that the problem with $0<p<1$ has a finite number of optimal solutions and prove that there exists $0<p^{*}<1$ such that the solution set of the problem with any $0<p<p^{*}$ is contained in the solution set of the problem with $p=0$ and there further exists $$ such that the solution set of the problem with any $$ remains unchanged. An estimation of such $p^{*}$ is also provided. In addition, to solve the constrained nonconvex non-Lipschitz $L_p$-$L_1$ problem ($0<p<1$ and $q=1$), we propose a smoothing penalty method and show that, under some mild conditions, any cluster point of the sequence generated is a KKT point of our problem. Some numerical examples are given to implicitly illustrate the theoretical results and show the efficiency of the proposed algorithm for the constrained $L_p$-$L_1$ problem under different noises.

Full work available at URL: https://arxiv.org/abs/1907.00880

zbMATH Keywords

penalty methodsparse optimizationsmoothing approximationcardinality minimizationnonconvex non-Lipschitz optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probing the Pareto Frontier for Basis Pursuit Solutions
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Variational Analysis
• First-Order Methods in Optimization
• A Constrainedℓ₁Minimization Approach to Sparse Precision Matrix Estimation
• Decoding by Linear Programming
• Stable recovery of sparse overcomplete representations in the presence of noise
• Stable signal recovery from incomplete and inaccurate measurements
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• The \(L_1\) penalized LAD estimator for high dimensional linear regression
• Compressed sensing
• Smoothing methods for nonsmooth, nonconvex minimization
• Sparse Reconstruction by Separable Approximation
• Lower Bound Theory of Nonzero Entries in Solutions of $\ell_2$-$\ell_p$ Minimization
• Compressed sensing and best 𝑘-term approximation
• Uncertainty principles and ideal atomic decomposition
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Complexity of unconstrained \(L_2 - L_p\) minimization
• A note on the complexity of \(L _{p }\) minimization
• Atomic decomposition by basis pursuit
• Exact penalty and error bounds in DC programming
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• RSP-Based Analysis for Sparsest and Least $\ell_1$-Norm Solutions to Underdetermined Linear Systems
• Penalty Methods for a Class of Non-Lipschitz Optimization Problems
• $NP/CMP$ Equivalence: A Phenomenon Hidden Among Sparsity Models $l_{0}$ Minimization and $l_{p}$ Minimization for Information Processing
• Spherical Designs and Nonconvex Minimization for Recovery of Sparse Signals on the Sphere
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
• Least Sparsity of $p$-Norm Based Optimization Problems with $p>1$
• Weak Stability of ℓ₁-Minimization Methods in Sparse Data Reconstruction
• The sparsest solution of the union of finite polytopes via its nonconvex relaxation

Cited In (10)

• Restricted normal cones and sparsity optimization with affine constraints
• Nonnegative iterative reweighted method for sparse linear complementarity problem
• Sparse Optimization with Least-Squares Constraints
• DC formulations and algorithms for sparse optimization problems
• Global optimization for sparse solution of least squares problems
• Lifted stationary points of sparse optimization with complementarity constraints
• Sparse convex optimization toolkit: a mixed-integer framework
• Spherical designs for approximations on spherical caps
• A greedy Newton-type method for multiple sparse constraint problem
• Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance

Uses Software

• PDCO
• SPGL1

This page was built for publication: Sparse Solutions of a Class of Constrained Optimization Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5868942)