A new semidefinite relaxation for L₁-constrained quadratic

DOI10.3934/NACO.2015.5.185MaRDI QIDQ2353474zbMATH OpenOpenAlexFDO

Authors Sheng-Nan Han, Yu-Jun Gong, Yong Xia

Publication date 14 July 2015

Published in Numerical Algebra, Control and Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(\ell_1\) unit ballquadratic optimizationsemidefinite programmingsparse principal component analysis

Mathematics Subject Classification ID

Quadratic programming (90C20) Semidefinite programming (90C22)

Abstract: In this paper, by improving the variable-splitting approach, we propose a new semidefinite programming (SDP) relaxation for the nonconvex quadratic optimization problem over the $el{l}_1$ unit ball (QPL1). It dominates the state-of-the-art SDP-based bound for (QPL1). As extensions, we apply the new approach to the relaxation problem of the sparse principal component analysis and the nonconvex quadratic optimization problem over the $el{l}_p$ ($1<p<2$) unit ball and then show the dominance of the new relaxation.

Recommendations

• New results on semidefinite bounds forℓ₁-constrained nonconvex quadratic optimization
• Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization
• Semidefinite programming relaxation for nonconvex quadratic programs
• A new convex relaxation for quadratically constrained quadratic programming
• A new semidefinite programming relaxation scheme for a class of quadratic matrix problems

Cites work

• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Convex approximations to sparse PCA via Lagrangian duality
• Grothendieck-type inequalities in combinatorial optimization
• Improved SDP bounds for minimizing quadratic functions over the \(\ell^{1}\)-ball
• Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
• New results on semidefinite bounds forℓ₁-constrained nonconvex quadratic optimization
• On semidefinite bounds for maximization of a non-convex quadratic objective over thel₁unit ball
• Pivoting in an outcome polyhedron
• The UGC hardness threshold of the \(L_{p}\) Grothendieck problem
• Trust Region Methods
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(7)

• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic 0-1 optimization problems with linear constraints
• Improved SDP bounds for minimizing quadratic functions over the \(\ell^{1}\)-ball
• New semidefinite programming relaxations for box constrained quadratic program
• A new semidefinite programming relaxation scheme for a class of quadratic matrix problems
• New results on semidefinite bounds forℓ₁-constrained nonconvex quadratic optimization
• The spherical constraint in Boolean quadratic programs

Describes a project that uses

Uses Software

• CVX
• SeDuMi

This page was built for publication: A new semidefinite relaxation for \(L_{1}\)-constrained quadratic

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