Geodesic
New results on semidefinite bounds for ℓ 1 -constrained nonconvex quadratic optimization
RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 3, pp. 285-297

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ro/2013039
Classification : 90C20, 90C22
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :