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

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 classical TRS and a number of its variants are polynomial-time solvable. In this paper, we follow a second-order cone (SOC) based approach to derive an exact convex reformulation of the TRS under a structural condition on the conic constraint. Our structural condition is immediately satisfied when there is no additional conic constraints, and it generalizes several such conditions studied in the literature. As a result, our study highlights an explicit connection between the classical nonconvex TRS and smooth convex quadratic minimization, which allows for the application of cheap iterative methods such as Nesterov's accelerated gradient descent, to the TRS. Furthermore, under slightly stronger conditions, we give a low-complexity characterization of the convex hull of the epigraph of the nonconvex quadratic function intersected with the constraints defining the domain without any additional variables. We also explore the inclusion of additional hollow constraints to the domain of the TRS, and convexification of the associated epigraph.

References in corpus (1)

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

Cited by in corpus (18)

• A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants
• Accelerated Methods for Non-Convex Optimization
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• First-Order Methods for Nonconvex Quadratic Minimization
• The Generalized Trust Region Subproblem: solution complexity and convex hull results
• 2x2 convexifications for convex quadratic optimization with indicator variables
• The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
• A Geometric View of SDP Exactness in QCQPs and its Applications
• Potential-based analyses of first-order methods for constrained and composite optimization
• Online First-Order Framework for Robust Convex Optimization
• An Inexact Augmented Lagrangian Method for Second-order Cone Programming with Applications
• New notions of simultaneous diagonalizability of quadratic forms with applications to QCQPs
• A survey of hidden convex optimization
• An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
• Exactness in SDP relaxations of QCQPs: Theory and applications
• A linear-time algorithm for generalized trust region subproblems
• On local minimizers of generalized trust-region subproblem