Sparse solutions of a class of constrained optimization problems

DOI10.1287/MOOR.2021.1194MaRDI QIDQ5868942zbMATH OpenOpenAlexFDO

Authors Lei Yang, Xiaojun Chen, Shuhuang Xiang

Publication date 26 September 2022

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

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)

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^{\ast }<1$ such that the solution set of the problem with any $0<p<p^{\ast }$ 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^{\ast }$ 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.

Recommendations

• The sparsity of underdetermined linear system via \(l_p\) minimization for \(0 < p < 1\)
• Least sparsity of \(p\)-norm based optimization problems with \(p>1\)
• On optimal solutions of the constrained \({\ell}_{0}\) regularization and its penalty problem
• An unconstrained \(\ell_q\) minimization with \(0<q\leq 1\) for sparse solution of underdetermined linear systems
• A smoothing method for sparse optimization over convex sets

Cites work

• scientific article; zbMATH DE number 1667417 (Why is no real title available?)
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• scientific article; zbMATH DE number 6438182 (Why is no real title available?)
• $NP/CMP$ Equivalence: A Phenomenon Hidden Among Sparsity Models $l_{0}$ Minimization and $l_{p}$ Minimization for Information Processing
• A constrained \(\ell _{1}\) minimization approach to sparse precision matrix estimation
• A note on the complexity of \(L _{p }\) minimization
• A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
• Atomic decomposition by basis pursuit
• Complexity of unconstrained \(L_2 - L_p\) minimization
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Decoding by Linear Programming
• Encyclopedia of mathematics. Springer online reference works
• Exact penalty and error bounds in DC programming
• First-order methods in optimization
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Least sparsity of \(p\)-norm based optimization problems with \(p>1\)
• Lower bound theory of nonzero entries in solutions of \(\ell_2-\ell_p\) minimization
• Penalty methods for a class of non-Lipschitz optimization problems
• Probing the Pareto frontier for basis pursuit solutions
• RSP-Based Analysis for Sparsest and Least $\ell_1$-Norm Solutions to Underdetermined Linear Systems
• Smoothing methods for nonsmooth, nonconvex minimization
• Sparse Reconstruction by Separable Approximation
• Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\)
• Spherical designs and nonconvex minimization for recovery of sparse signals on the sphere
• Stable recovery of sparse overcomplete representations in the presence of noise
• Stable signal recovery from incomplete and inaccurate measurements
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• The \(L_1\) penalized LAD estimator for high dimensional linear regression
• The sparsest solution of the union of finite polytopes via its nonconvex relaxation
• Theory of compressive sensing via _1-minimization: a non-RIP analysis and extensions
• Uncertainty principles and ideal atomic decomposition
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Variational Analysis
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction

Cited in

(19)

• On solutions of sparsity constrained optimization
• On optimal solutions of the constrained \({\ell}_{0}\) regularization and its penalty problem
• Restricted normal cones and sparsity optimization with affine constraints
• Constrained optimization involving nonconvex \(\ell_p\) norms: optimality conditions, algorithm and convergence
• Optimizing sparsity over lattices and semigroups
• Nonnegative iterative reweighted method for sparse linear complementarity problem
• Relationship between the optimal solutions of least squares regularized with \(\ell_{0}\)-norm and constrained by \(k\)-sparsity
• Sparse Optimization with Least-Squares Constraints
• Least sparsity of \(p\)-norm based optimization problems with \(p>1\)
• 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
• Solution sets of three sparse optimization problems for multivariate regression
• Spherical designs for approximations on spherical caps
• A smoothing method for sparse optimization over convex sets
• A greedy Newton-type method for multiple sparse constraint problem
• The sparsest solution of the union of finite polytopes via its nonconvex relaxation
• Exact Sparse Approximation Problems via Mixed-Integer Programming: Formulations and Computational Performance

Describes a project that uses

Uses Software

• SPGL1
• PDCO

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)