Journal article
A TWO-VARIABLE APPROACH TO THE TWO-TRUST-REGION SUBPROBLEM
SIAM journal on optimization, Vol.26(1), pp.661-680
01/01/2016
DOI: 10.1137/130945880
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.
Details
- Title: Subtitle
- A TWO-VARIABLE APPROACH TO THE TWO-TRUST-REGION SUBPROBLEM
- Creators
- Boshi Yang - University of IowaSamuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.26(1), pp.661-680
- Publisher
- Siam Publications
- DOI
- 10.1137/130945880
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Number of pages
- 20
- Language
- English
- Date published
- 01/01/2016
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380392302771
Metrics
1 Record Views