American Institute of Mathematical Sciences

Advanced
2015, 5(2): 185-195. doi: 10.3934/naco.2015.5.185

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

Yong Xia 1, , Yu-Jun Gong 2, and  Sheng-Nan Han 2,

1. 

State Key Laboratory of Software Development Environment, School of Mathematics and System Sciences, Beihang University, Beijing 100191, China
2. 

LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing 100191, China, China

Received  September 2014 Revised  April 2015 Published  June 2015

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: $\ell_1$ unit ball, Semidefinite programming, Sparse principal component analysis., Quadratic optimization.
Mathematics Subject Classification: 90C20, 90C2.
Citation: Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185
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.  doi: 10.1023/A:1008364005245.  Google Scholar

[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.  doi: 10.1007/s11590-006-0018-1.  Google Scholar

[3]

A. R. Conn, N. I. M. Gould and P. L. Toint, Trust-Region Methods,, MPS/SIAM Series on Optimization. SIAM, (2000).  doi: 10.1137/1.9780898719857.  Google Scholar

[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.   Google Scholar

[5]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming,, version 1. 21, (2010).   Google Scholar

[6]

Y. Hsia, Complexity and Nonlinear Semidefinite Programming Reformulation of l1-constrained Nonconvex Quadratic Optimization,, Optimization Letters, 8 (2014), 1433.  doi: 10.1007/s11590-013-0670-1.  Google Scholar

[7]

S. Khot and A. Naor, Grothendieck-type inequalities in combinatorial optimization,, Communications on Pure and Applied Mathematics, 65 (2012), 992.  doi: 10.1002/cpa.21398.  Google Scholar

[8]

G. Kindler, A. Naor and G. Schechtman, The UGC hardness threshold of the Grothendieck problem,, Math. Oper. Res., 35 (2010), 267.  doi: 10.1287/moor.1090.0425.  Google Scholar

[9]

L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization,, SIAM. J. Optimization, 1 (1991), 166.  doi: 10.1137/0801013.  Google Scholar

[10]

R. Luss and M. Teboulle, Convex Approximations to Sparse PCA via Lagrangian Duality,, Operations Research Letters, 39 (2011), 57.  doi: 10.1016/j.orl.2010.11.005.  Google Scholar

[11]

J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres,, SIAM. J. Optimization. 4 (1994), 4 (1994), 159.  doi: 10.1137/0804009.  Google Scholar

[12]

Y. Nesterov, Global Quadratic Optimization via Conic Relaxation,, in Handbook of Semidefinite Programming, (2000), 363.   Google Scholar

[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.  doi: 10.1051/ro:2006023.  Google Scholar

[14]

J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimation over symmetric cones,, Optimization Methods and Software, 11-12 (1999), 11.  doi: 10.1080/10556789908805766.  Google Scholar

[15]

Y. Xia, New results on semidefinite bounds for l1-constrained nonconvex quadratic optimization,, RAIRO-Operations Research, 47 (2013), 285.  doi: 10.1051/ro/2013039.  Google Scholar

show all references

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.  doi: 10.1023/A:1008364005245.  Google Scholar

[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.  doi: 10.1007/s11590-006-0018-1.  Google Scholar

[3]

A. R. Conn, N. I. M. Gould and P. L. Toint, Trust-Region Methods,, MPS/SIAM Series on Optimization. SIAM, (2000).  doi: 10.1137/1.9780898719857.  Google Scholar

[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.   Google Scholar

[5]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming,, version 1. 21, (2010).   Google Scholar

[6]

Y. Hsia, Complexity and Nonlinear Semidefinite Programming Reformulation of l1-constrained Nonconvex Quadratic Optimization,, Optimization Letters, 8 (2014), 1433.  doi: 10.1007/s11590-013-0670-1.  Google Scholar

[7]

S. Khot and A. Naor, Grothendieck-type inequalities in combinatorial optimization,, Communications on Pure and Applied Mathematics, 65 (2012), 992.  doi: 10.1002/cpa.21398.  Google Scholar

[8]

G. Kindler, A. Naor and G. Schechtman, The UGC hardness threshold of the Grothendieck problem,, Math. Oper. Res., 35 (2010), 267.  doi: 10.1287/moor.1090.0425.  Google Scholar

[9]

L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization,, SIAM. J. Optimization, 1 (1991), 166.  doi: 10.1137/0801013.  Google Scholar

[10]

R. Luss and M. Teboulle, Convex Approximations to Sparse PCA via Lagrangian Duality,, Operations Research Letters, 39 (2011), 57.  doi: 10.1016/j.orl.2010.11.005.  Google Scholar

[11]

J. M. Martínez, Local minimizers of quadratic functions on Euclidean balls and spheres,, SIAM. J. Optimization. 4 (1994), 4 (1994), 159.  doi: 10.1137/0804009.  Google Scholar

[12]

Y. Nesterov, Global Quadratic Optimization via Conic Relaxation,, in Handbook of Semidefinite Programming, (2000), 363.   Google Scholar

[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.  doi: 10.1051/ro:2006023.  Google Scholar

[14]

J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimation over symmetric cones,, Optimization Methods and Software, 11-12 (1999), 11.  doi: 10.1080/10556789908805766.  Google Scholar

[15]

Y. Xia, New results on semidefinite bounds for l1-constrained nonconvex quadratic optimization,, RAIRO-Operations Research, 47 (2013), 285.  doi: 10.1051/ro/2013039.  Google Scholar

[1]

Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems & Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[2]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[3]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014
[4]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[5]

Sujit Kumar Samanta, Rakesh Nandi. Analysis of $GI^{[X]}/D$-$MSP/1/\infty$ queue using $RG$-factorization. Journal of Industrial & Management Optimization, 2021, 17 (2) : 549-573. doi: 10.3934/jimo.2019123
[6]

Lingju Kong, Roger Nichols. On principal eigenvalues of biharmonic systems. Communications on Pure & Applied Analysis, 2021, 20 (1) : 1-15. doi: 10.3934/cpaa.2020254
[7]

Xuemei Chen, Julia Dobrosotskaya. Inpainting via sparse recovery with directional constraints. Mathematical Foundations of Computing, 2020, 3 (4) : 229-247. doi: 10.3934/mfc.2020025
[8]

Andreas Kreuml. The anisotropic fractional isoperimetric problem with respect to unconditional unit balls. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020290
[9]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374
[10]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081
[11]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[12]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364
[13]

Yoshitsugu Kabeya. Eigenvalues of the Laplace-Beltrami operator under the homogeneous Neumann condition on a large zonal domain in the unit sphere. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3529-3559. doi: 10.3934/dcds.2020040
[14]

Simone Fiori. Error-based control systems on Riemannian state manifolds: Properties of the principal pushforward map associated to parallel transport. Mathematical Control & Related Fields, 2021, 11 (1) : 143-167. doi: 10.3934/mcrf.2020031
[15]

Kien Trung Nguyen, Vo Nguyen Minh Hieu, Van Huy Pham. Inverse group 1-median problem on trees. Journal of Industrial & Management Optimization, 2021, 17 (1) : 221-232. doi: 10.3934/jimo.2019108
[16]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[17]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[18]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[19]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[20]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

 Impact Factor: 

Tools

Metrics

  • PDF downloads (49)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences