Optimization Online


The Trust Region Subproblem with Non-Intersecting Linear Constraints

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

Abstract: This paper studies an extended trust region subproblem (eTRS)in which the trust region intersects the unit ball with m linear inequality constraints. When m=0, m=1, or 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>=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 as long as the linear constraints are non-intersecting.

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

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Department of Management Sciences, University of Iowa, Iowa City, IA 52242, USA. February 2013

Download: [PDF]

Entry Submitted: 02/23/2013
Entry Accepted: 02/24/2013
Entry Last Modified: 02/23/2013

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