The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. We consider extensions of TRS having additional constraints. It is known that TRS, and the extension of TRS that adds a single linear inequality, both admit convex programming representations. We show that when two parallel linear inequalities are added to TRS, the resulting nonconvex problem has an exact convex representation as a semidefinite programming (SDP) problem with additional linear and second-order-cone constraints. For the case where an additional ellipsoidal constraint is added to TRS, resulting in the well-known “two trust-region subproblem” (TTRS), we describe a new relaxation including second-order-cone constraints that significantly strengthens the usual SDP relaxation. Numerical experiments show that the strengthened relaxation provides an exact solution of TTRS in most instances, although the theoretical complexity of TTRS remains an open problem.

This is joint work with Sam Burer.

<?xml:namespace prefix = o />