New results on semidefinite bounds for ℓ 1 -constrained nonconvex quadratic optimization

Yong Xia

RAIRO - Operations Research - Recherche Opérationnelle (2013)

  • Volume: 47, Issue: 3, page 285-297
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Xia, Yong. "New results on semidefinite bounds for $\ell _1$-constrained nonconvex quadratic optimization." RAIRO - Operations Research - Recherche Opérationnelle 47.3 (2013): 285-297. <http://eudml.org/doc/275086>.

@article{Xia2013,
abstract = {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.},
author = {Xia, Yong},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {quadratic programming; semidefinite programming; $\ell _1$-unit ball; sparse principal component analysis; unit ball},
language = {eng},
number = {3},
pages = {285-297},
publisher = {EDP-Sciences},
title = {New results on semidefinite bounds for $\ell _1$-constrained nonconvex quadratic optimization},
url = {http://eudml.org/doc/275086},
volume = {47},
year = {2013},
}

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
PB - EDP-Sciences
VL - 47
IS - 3
SP - 285
EP - 297
AB - 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.
LA - eng
KW - quadratic programming; semidefinite programming; $\ell _1$-unit ball; sparse principal component analysis; unit ball
UR - http://eudml.org/doc/275086
ER -

References

top
  1. [1] K. Anstreicher, S. Burer and D.C. Versus, Copositive Bounds for Standard QP. J. Global Optim.33 (2005) 299–312. Zbl1093.90033MR2192210
  2. [2] K.M. Anstreicher and S. Burer, Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program.124 (2010) 33–43. Zbl1198.90311MR2679981
  3. [3] 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. J. Global Optim.18 (2000) 301–320. Zbl0970.90057MR1810401
  4. [4] I.M. Bomze, M. Locatelli and F. Tardella, New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. Ser. A115 (2008) 31–64. Zbl1171.90007MR2403752
  5. [5] A. d’Aspremont, L. El Ghaoui, M.I. Jordan and G.R.G. Lanckriet, A direct formulation for sparse PCA using semidefinite programming. SIAM Rev.48 (2007) 434–448. Zbl1128.90050
  6. [6] L. Lovasz and A. Schrijver, Cones of matrices and set-functions and 0-1 optimization, SIAM. J. Optim.1 (1991) 166–190. Zbl0754.90039MR1098425
  7. [7] R. Luss and M. Teboulle, Convex Approximations to Sparse PCA via Lagrangian Duality, Oper. Res. Lett.39 (2011) 57–61. Zbl1207.90082MR2748717
  8. [8] 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–384. 
  9. [9] M.Ç. Pinar and M. Teboulle, On semidefinite bounds for maximization of a non-convex quadratic objective over the ℓ1 unit ball. RAIRO-Oper. Res. 40 (2006) 253–265. Zbl1180.90222MR2276158
  10. [10] N.Z. Shor, Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences25 (1987) 1–11. Zbl0655.90055MR939596
  11. [11] H. Wolkowicz, R. Saigal and L. Vandenberghe eds., Handbook of semidefinite programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Boston, MA (2000). Zbl0962.90001MR1778223
  12. [12] Y. Xia, R.L. Sheu, X.L. Sun and D. Li, Tightening a copositive relaxation for standard quadratic optimization problems. Comput. Optim. Appl.55 (2013) 379–398. Zbl1294.90044MR3053790

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.