Volume 47, Number 3, July-September 2013
|Page(s)||285 - 297|
|Published online||26 August 2013|
New results on semidefinite bounds for ℓ1-constrained nonconvex quadratic optimization∗
1 State Key Laboratory of Software Development
Environment, LMIB of the Ministry of Education, School of Mathematics and System
Sciences, Beihang University, Beijing
Accepted: 20 June 2013
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.
Mathematics Subject Classification: 90C20 / 90C22
Key words: Quadratic programming / semidefinite programming / ℓ1unit ball / sparse principal component analysis
This research was supported by National Natural Science Foundation of China under grants 11001006 and 91130019/A011702, by the fundamental research funds for the central universities under grant YWF-13-A01, and by the fund of State Key Laboratory of Software Development Environment under grant SKLSDE-2013ZX-13.
© EDP Sciences, ROADEF, SMAI, 2013
Initial download of the metrics may take a while.