We consider the non-convex quadratic maximization problem subject to the unit ball constraint. The nature of the norm structure makes this problem extremely hard to analyze, and as a consequence, the same difficulties are encountered when trying to build suitable approximations for this problem by some tractable convex counterpart formulations. We explore some properties of this problem, derive SDP-like relaxations and raise open questions.
@article{RO_2006__40_3_253_0, author = {Pinar, Mustafa \c{C}. and Teboulle, Marc}, title = {On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {253--265}, publisher = {EDP-Sciences}, volume = {40}, number = {3}, year = {2006}, doi = {10.1051/ro:2006023}, mrnumber = {2276158}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro:2006023/} }
TY - JOUR AU - Pinar, Mustafa Ç. AU - Teboulle, Marc TI - On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2006 SP - 253 EP - 265 VL - 40 IS - 3 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2006023/ DO - 10.1051/ro:2006023 LA - en ID - RO_2006__40_3_253_0 ER -
%0 Journal Article %A Pinar, Mustafa Ç. %A Teboulle, Marc %T On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 253-265 %V 40 %N 3 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2006023/ %R 10.1051/ro:2006023 %G en %F RO_2006__40_3_253_0
Pinar, Mustafa Ç.; Teboulle, Marc. On semidefinite bounds for maximization of a non-convex quadratic objective over the $\ell _1$ unit ball. RAIRO - Operations Research - Recherche Opérationnelle, Volume 40 (2006) no. 3, pp. 253-265. doi : 10.1051/ro:2006023. http://archive.numdam.org/articles/10.1051/ro:2006023/
[1] Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming. J. ACM 42 (1995) 1115-1145. | Zbl
and ,[2] Conditions for Global Optimality, in Handbook for Global Optimization. Kluwer Academic Publishers, Dordrecht, Holland (1999) 1-26. | Zbl
,[3] Conditions for Global Optimality 2. J. Global Optim. 13 (1998) 349-367. | Zbl
,[4] Global Optimality Conditions in Maximizing a Convex Quadratic Function under Convex Quadratic Constraints. J. Global Optim. 21 (2001) 445-455.
,[5] Matrix Analysis. Cambridge University Press, Cambridge (1985). | MR | Zbl
and ,[6] Non-convex Quadratic Minimization Problems with Quadratic Constraints: Global Optimality Conditions. Technical Report AMR05/19, University of South Wales, School of Mathematics (2005).
, and ,[7] Sufficient Global Optimality Conditions for Non-convex Quadratic Minimization Problems with Box Constraints. Technical Report AMR05/20, University of South Wales, School of Mathematics (2005). | MR
, and ,[8] Global Optimization with Polynomials and the problem of moments. SIAM J. Optim. 11 (2001) 796-817. | Zbl
,[9] GloptiPoly: Global Optimization over Polynomials with Matlab and SeDuMi. ACM Trans. Math. Software 29 (2003) 165-194. | Zbl
,[10] A comparison of the Sherali-Adams, Lovasz-Schrijver and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28 (2003) 470-496. | Zbl
,[11] Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1 (1991) 166-190. | Zbl
and ,[12] Semidefinite Relaxation and Non-convex Quadratic Optimization. Optim. Methods Softw. 12 (1997) 1-20. | Zbl
,[13] Global Quadratic Optimization via Conic Relaxation, in Handbook of Semidefinite Programming, edited by H. Wolkowicz, R. Saigal and L. Vandenberghe. Kluwer Academic Publishers, Boston (2000) 363-384.
,[14] Convex Analysis. Princeton University Press, Princeton, NJ (1970). | MR | Zbl
,[15] On a bounding method for quadratic extremal problems with 0-1 variables. Kibernetika 2 (1985) 48-50. | Zbl
,[16] Handbook of semidefinite programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Boston, MA (2000). | MR | Zbl
, and (Editors),[17] Approximating Quadratic Programming with Bound and Quadratic Constraints. Math. Program. 84 (1999) 219-226. | Zbl
,[18] Quadratic Maximization and Semidefinite Relaxation. Math. Program. 87 (2000) 453-465. | Zbl
,Cited by Sources: