Semidefinite Relaxation and Nonconvex Quadratic Optimization under a
Polyhedral Norm Constraint

by

Mustafa Pinar
Bilkent University 

Semidefinite relaxation is a useful method to obtain polynomially computable bounds on difficult nonconvex quadratic optimization problems. Using a cplicated proof technique S. Zhang gave simple conditions on the case where the semidefinite bound is exact for a class of nonconvex quadratic problems. We give a very simple proof of this result with extensions. Then we investigate the applicability of this simple proof technique to nonconvex quadratic optimization under a polyhedral norm constraint. The latter problem was defined by Yu. Nesterov who also proposed a semidefinite relaxation. We study the quality of Nesterov relaxation, and explore the possibilities of obtaining tighter relaxations. We show that this may not be possible. In fact, we conjecture that the Nesterov relaxation is the tightest possible. Avenues for further work are discussed. This is joint research with Marc Teboulle of Tel-Aviv University, Israel.