Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: 90C20, 90C22.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    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.


    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.


    M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 1. 21, 2010. Available: http://cvxr.com/cvx.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(123) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint