Optimization Online


A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants

Nam Ho-Nguyen (hnh***at***andrew.cmu.edu)
Fatma Kilinc-Karzan (fkilinc***at***andrew.cmu.edu)

Abstract: We study the trust region subproblem (TRS) of minimizing a nonconvex quadratic function over the unit ball with additional conic constraints. Despite having a nonconvex objective, it is known that the TRS and a number of its variants are polynomial-time solvable. In this paper, we follow a second-order cone based approach to derive an exact convex formulation of the TRS, and under slightly stronger conditions, give a low-complexity characterization of the convex hull of its epigraph. As a result, we make the connection between the nonconvex TRS and smooth convex quadratic minimization, which allows for the application of cheap iterative methods to the TRS. We also explore the inclusion of additional hollow constraints to the domain of the TRS, and convexify the associated epigraph.

Keywords: trust region subproblem, second-order cone programming, convex reformulation, convex hull, iterative methods

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

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

Citation: Technical report, Tepper School of Business, Carnegie Mellon University, March 2016

Download: [PDF]

Entry Submitted: 03/10/2016
Entry Accepted: 03/10/2016
Entry Last Modified: 03/10/2016

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