Paper Info
Title
The trust region subproblem with non-intersecting linear constraints
Abstract
This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with $$m$$ m linear inequality constraints. When $$m=0,\\,m = 1$$ m = 0 , m = 1 , or $$m = 2$$ m = 2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when $$m \\ge 2$$ m ¿ 2 and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same convex relaxation may admit a gap with eTRS. This paper shows that the convex relaxation has no gap for arbitrary $$m$$ m as long as the linear constraints are non-intersecting.
Year
DOI
Venue
2015
10.1007/s10107-014-0749-1
Math. Program.
Keywords
Field
DocType
nonconvex quadratic programming,90c20,90c25,90c22,90c30,semidefinite programming,second-order cone programming,90c26,trust-region subproblem,second order cone programming
Second-order cone programming,Discrete mathematics,Trust region,Mathematical optimization,Combinatorics,Time complexity,Linear inequality,Convex relaxation,Mathematics,Semidefinite programming,Unit sphere,The Intersect
Journal
Volume
Issue
ISSN
149
1-2
1436-4646
Citations 
PageRank 
References 
6
0.49
8
Authors
2
Name
Order
Citations
PageRank
Samuel Burer1114873.09
Boshi Yang2111.59