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-320. 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-59. 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, Philadelphia, PA, 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-448. Google Scholar

[5]

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

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

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

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

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

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

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

[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. 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-265. 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), 625-653. 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-297. 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-320. 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-59. 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, Philadelphia, PA, 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-448. Google Scholar

[5]

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

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

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

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

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

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

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

[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. 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-265. 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), 625-653. 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-297. doi: 10.1051/ro/2013039.  Google Scholar

[1]

Pengbo Geng, Wengu Chen. Unconstrained $ \ell_1 $-$ \ell_2 $ minimization for sparse recovery via mutual coherence. Mathematical Foundations of Computing, 2020, 3 (2) : 65-79. doi: 10.3934/mfc.2020006
[2]

Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
[3]

Huining Qiu, Xiaoming Chen, Wanquan Liu, Guanglu Zhou, Yiju Wang, Jianhuang Lai. A fast $\ell_1$-solver and its applications to robust face recognition. Journal of Industrial & Management Optimization, 2012, 8 (1) : 163-178. doi: 10.3934/jimo.2012.8.163
[4]

Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305
[5]

Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 165-175. doi: 10.3934/naco.2019046
[6]

Hui Huang, Eldad Haber, Lior Horesh. Optimal estimation of $\ell_1$-regularization prior from a regularized empirical Bayesian risk standpoint. Inverse Problems & Imaging, 2012, 6 (3) : 447-464. doi: 10.3934/ipi.2012.6.447
[7]

Azam Moradi, Jafar Razmi, Reza Babazadeh, Ali Sabbaghnia. An integrated Principal Component Analysis and multi-objective mathematical programming approach to agile supply chain network design under uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (2) : 855-879. doi: 10.3934/jimo.2018074
[8]

Yitong Guo, Bingo Wing-Kuen Ling. Principal component analysis with drop rank covariance matrix. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2345-2366. doi: 10.3934/jimo.2020072
[9]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[10]

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
[11]

Ying Lin, Rongrong Lin, Qi Ye. Sparse regularized learning in the reproducing kernel banach spaces with the $ \ell^1 $ norm. Mathematical Foundations of Computing, 2020, 3 (3) : 205-218. doi: 10.3934/mfc.2020020
[12]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[13]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[14]

Zongming Guo, Fangshu Wan. Weighted fourth order elliptic problems in the unit ball. Electronic Research Archive, 2021, 29 (6) : 3775-3803. doi: 10.3934/era.2021061
[15]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[16]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[17]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[18]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[19]

Charles Curry, Stephen Marsland, Robert I McLachlan. Principal symmetric space analysis. Journal of Computational Dynamics, 2019, 6 (2) : 251-276. doi: 10.3934/jcd.2019013
[20]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy