Second-Order-Cone Constraints for Extended Trust-Region Subproblems

Samuel Burer (samuel-bureruiowa.edu)
Kurt Anstreicher (kurt-anstreicheruiowa.edu)

Abstract: The classical trust-region subproblem (TRS) minimizes a nonconvex quadratic objective over the unit ball. In this paper, we consider extensions of TRS having extra constraints. When two parallel cuts are added to TRS, we show that the resulting nonconvex problem has an exact representation as a semidefinite program with additional linear and second-order-cone constraints. For the case where an additional ellipsoidal constraint is added to TRS, resulting in the ``two trust-region subproblem" (TTRS), we provide a new relaxation including second-order-cone constraints that strengthens the usual SDP relaxation.

Keywords: trust-region subproblem, second-order cone programming, semidefinite programming, nonconvex quadratic programming

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Linear, Cone and Semidefinite Programming

Citation: Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA 52242-1994.

Download: [PDF]

Entry Submitted: 03/07/2011
Entry Accepted: 03/07/2011
Entry Last Modified: 02/21/2013

Modify/Update this entry