Optimization Online


A Two-Variable Approach to the Two-Trust-Region Subproblem

Boshi Yang (boshi-yang***at***uiowa.edu)
Samuel Burer (samuel-burer***at***uiowa.edu)

Abstract: The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing algorithms do not use SDP. In this paper, we investigate the use of SDP for TTRS. Starting from the basic SDP relaxation of TTRS, which admits a gap, recent research has tightened the basic relaxation using valid second-order-cone inequalities. Even still, closing the gap requires more. For the special case of TTRS in dimension $n=2$, we fully characterize the remaining valid inequalities, which can be viewed as strengthened versions of the second-order-cone inequalities just mentioned. We also demonstrate that these valid inequalities can be used computationally even when $n > 2$ to solve TTRS instances that were previously unsolved using SDP-based techniques.

Keywords: trust-region subproblem, semidefinite programming, nonconvex quadratic programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: University of Iowa, Iowa City, IA 52242, USA. November 2013

Download: [PDF]

Entry Submitted: 11/18/2013
Entry Accepted: 11/18/2013
Entry Last Modified: 10/15/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society