In this paper, we show that the direct semidefinite programming (SDP) bound for the nonconvex quadratic optimization problem over ℓ1 unit ball (QPL1) is equivalent to the optimal d.c. (difference between convex) bound for the standard quadratic programming reformulation of QPL1. Then we disprove a conjecture about the tightness of the direct SDP bound. Finally, as an extension of QPL1, we study the relaxation problem of the sparse principal component analysis, denoted by QPL2L1. We show that the existing direct SDP bound for QPL2L1 is equivalent to the doubly nonnegative relaxation for variable-splitting reformulation of QPL2L1.
Mots clés : quadratic programming, semidefinite programming, $\ell _1$-unit ball, sparse principal component analysis
@article{RO_2013__47_3_285_0,
author = {Xia, Yong},
title = {New results on semidefinite bounds for $\ell _1$-constrained nonconvex quadratic optimization},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {285--297},
publisher = {EDP-Sciences},
volume = {47},
number = {3},
year = {2013},
doi = {10.1051/ro/2013039},
mrnumber = {3143753},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2013039/}
}
TY - JOUR AU - Xia, Yong TI - New results on semidefinite bounds for $\ell _1$-constrained nonconvex quadratic optimization JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2013 SP - 285 EP - 297 VL - 47 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2013039/ DO - 10.1051/ro/2013039 LA - en ID - RO_2013__47_3_285_0 ER -
%0 Journal Article %A Xia, Yong %T New results on semidefinite bounds for $\ell _1$-constrained nonconvex quadratic optimization %J RAIRO - Operations Research - Recherche Opérationnelle %D 2013 %P 285-297 %V 47 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2013039/ %R 10.1051/ro/2013039 %G en %F RO_2013__47_3_285_0
Xia, Yong. New results on semidefinite bounds for $\ell _1$-constrained nonconvex quadratic optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 3, pp. 285-297. doi : 10.1051/ro/2013039. http://archive.numdam.org/articles/10.1051/ro/2013039/
[1] , and , Copositive Bounds for Standard QP. J. Global Optim. 33 (2005) 299-312. | MR | Zbl
[2] and , Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124 (2010) 33-43. | MR | Zbl
[3] , , , , and , On copositive programming and standard quadratic optimization problems. J. Global Optim. 18 (2000) 301-320. | MR | Zbl
[4] , and , New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. Ser. A 115 (2008) 31-64. | MR | Zbl
[5] , , and , A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 48 (2007) 434-448. | Zbl
[6] and , Cones of matrices and set-functions and 0-1 optimization, SIAM. J. Optim. 1 (1991) 166-190. | MR | Zbl
[7] and , Convex Approximations to Sparse PCA via Lagrangian Duality, Oper. Res. Lett. 39 (2011) 57-61. | MR | Zbl
[8] , 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-384.
[9] and , On semidefinite bounds for maximization of a non-convex quadratic objective over the ℓ1 unit ball. RAIRO-Oper. Res. 40 (2006) 253-265. | Numdam | MR | Zbl
[10] , Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences 25 (1987) 1-11. | MR | Zbl
[11] H. Wolkowicz, R. Saigal and L. Vandenberghe eds., Handbook of semidefinite programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Boston, MA (2000). | MR | Zbl
[12] , , and , Tightening a copositive relaxation for standard quadratic optimization problems. Comput. Optim. Appl. 55 (2013) 379-398. | MR | Zbl
Cité par Sources :
