Complexity and nonlinear semidefinite programming reformulation of e_1-constrained nonconvex quadratic optimization

摘要

In this article, we show that the e_1-constrained nonconvex quadratic optimization problem (QPL1) is NP-hard, even when the off-diagonal elements are all nonnegative. Then we give an answer to Pinar and Teboulle's open problem on the nonlinear semidefinite programming relaxation of (QPL1). The analytical approach is extended to e_p-constrained quadratic programs with 1< p< 2.