A new semidefinite relaxation for $L_{1}$-constrained quadraticoptimization and extensions

Yong  Xia; Yu-Jun  Gong; Sheng-Nan  Han

doi:10.3934/naco.2015.5.185

Article Contents

2015, Volume 5, Issue 2: 185-195. Doi: 10.3934/naco.2015.5.185

This issue Previous Article A wedge trust region method with self-correcting geometry for derivative-free optimization Next Article Continuity and stability of two-stage stochastic programs with quadratic continuous recourse

A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions

1.
State Key Laboratory of Software Development Environment, School of Mathematics and System Sciences, Beihang University, Beijing 100191
2.
LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing 100191

Received: August 31, 2014

Revised: March 31, 2015

Published: May 2015

Abstract Related Papers Cited by

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 $\ell_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 $\ell_p$ ($1< p<2$) unit ball and then show the dominance of the new relaxation.

Keywords:

Mathematics Subject Classification: 90C20, 90C22.

Citation:

Related Papers

Cited by

References

[1]	I. M. Bomze, M. Dür, E. De Klerk, C. Roos, A. J. Quist and T. Terlaky, On copositive programming and standard quadratic optimization problems, Journal of Global Optimization, 18 (2000), 301-320.doi: 10.1023/A:1008364005245.
[2]	I. M. Bomze, F. Frommlet and M. Rubey, Improved SDP bounds for minimizing quadratic functions over the l1-ball, Optimization Letters, 1 (2007), 49-59.doi: 10.1007/s11590-006-0018-1.
[3]	A. R. Conn, N. I. M. Gould and P. L. Toint, Trust-Region Methods, MPS/SIAM Series on Optimization. SIAM, Philadelphia, PA, 2000doi: 10.1137/1.9780898719857.
[4]	A. d'Aspremont, L. El Ghaoui, M. I. Jordan and G. R. G. Lanckriet, A direct formulation for sparse PCA using semidefinite programming, SIAM Review, 48 (2007), 434-448.
[5]	M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 1. 21, 2010. Available: http://cvxr.com/cvx.
[6]	Y. Hsia, Complexity and Nonlinear Semidefinite Programming Reformulation of l1-constrained Nonconvex Quadratic Optimization, Optimization Letters, 8 (2014), 1433-1442.doi: 10.1007/s11590-013-0670-1.
[7]	S. Khot and A. Naor, Grothendieck-type inequalities in combinatorial optimization, Communications on Pure and Applied Mathematics, 65 (2012), 992-1035.doi: 10.1002/cpa.21398.
[8]	G. Kindler, A. Naor and G. Schechtman, The UGC hardness threshold of the Grothendieck problem, Math. Oper. Res., 35 (2010), 267-283.doi: 10.1287/moor.1090.0425.
[9]	L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM. J. Optimization, 1 (1991), 166-190.doi: 10.1137/0801013.
[10]	R. Luss and M. Teboulle, Convex Approximations to Sparse PCA via Lagrangian Duality, Operations Research Letters, 39 (2011), 57-61.doi: 10.1016/j.orl.2010.11.005.
[11]	J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM. J. Optimization. 4 (1994), 159-176.doi: 10.1137/0804009.
[12]	Y. Nesterov, Global Quadratic Optimization via Conic Relaxation, in Handbook of Semidefinite Programming, H. Wolkowicz, R. Saigal and L. Vandenberghe, eds., Kluwer Academic Publishers, Boston, (2000), 363-387.
[13]	M.Ç. Pinar and M. Teboulle, On semidefinite bounds for maximization of a non-convex quadratic objective over the l1 unit ball, RAIRO-Operations Research, 40 (2006), 253-265.doi: 10.1051/ro:2006023.
[14]	J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimation over symmetric cones, Optimization Methods and Software, 11-12 (1999), 625-653.doi: 10.1080/10556789908805766.
[15]	Y. Xia, New results on semidefinite bounds for l1-constrained nonconvex quadratic optimization, RAIRO-Operations Research, 47 (2013), 285-297.doi: 10.1051/ro/2013039.