Paper Info
Title
A Two-Variable Approach to the Two-Trust-Region Subproblem.
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.
Year
DOI
Venue
2016
10.1137/130945880
SIAM JOURNAL ON OPTIMIZATION
Keywords
Field
DocType
trust-region subproblem,semidefinite programming,nonconvex quadratic programming
Trust region,Ellipsoid,Mathematical optimization,Feasible region,Quadratic function,Time complexity,Mathematics,Semidefinite programming,Special case
Journal
Volume
Issue
ISSN
26
1
1052-6234
Citations 
PageRank 
References 
4
0.40
16
Authors
2
Name
Order
Citations
PageRank
Boshi Yang1111.59
Samuel Burer2114873.09