ON LOCAL MINIMIZERS OF NONCONVEX HOMOGENEOUS QUADRATICALLY CONSTRAINED QUADRATIC OPTIMIZATION WITH AT MOST TWO CONSTRAINTS

We study nonconvex homogeneous quadratically constrained quadratic optimization with m(∈{ 1, 2} ) constraints, denoted by (QQm). (QQ2) contains (QQ1), the trust region subproblem (TRS) and its generalization (GTRS), and the ellipsoid regularized total least squares problem as special cases. It is known that there is a necessary and sufficient optimality condition for the global minimizer of (QQ2). In this paper, we first show that any local minimizer of (QQ1) is globally optimal. Unlike its special case (TRS) with at most one local nonglobal minimizer, (QQ2) may have infinitely many local nonglobal minimizers. At any local nonglobal minimizer of (QQ2), both the linear independence constraint qualification and the strict complementary slackness condition hold, and the Hessian of the Lagrangian has exactly one negative eigenvalue. As the main contribution, we prove that the standard second-order sufficient optimality condition for any strict local nonglobal minimizer of (QQ2) remains necessary. It turns out that finding all local nonglobal minimizers of (GTRS) or proving the nonexistence can be done in polynomial time. More applications and the impossibility of extending our main result are discussed.