A new semidefinite relaxation for ℓ₁-constrained quadratic optimization and extensions

2013/12/31 by Yong Xia, Xia, Yong, Yu-Jun Gong +3
Mathematics · #90C20 #90C22 #FOS: Mathematics #Optimization and Control (math.OC) #math.OC #msc:90C20 #msc:90C22

paper · pdf · doi:10.48550/arxiv.1401.0081

13pages,1figure

arxiv created 2013/12/31 · arxiv updated 2014/01/03

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 ℓ₁ 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 ℓ_p (1< p<2) unit ball and then show the dominance of the new relaxation.

Related

• A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints
• Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints
• SDP-quality bounds via convex quadratic relaxations for global\n optimization of mixed-integer quadratic programs
• Valid inequalities and global solution algorithm for Quadratically Constrained Quadratic Programs
• Parabolic Relaxation for Quadratically-constrained Quadratic Programming -- Part I: Definitions & Basic Properties