A second-order cone based approach for solving the trust-region subproblem and its variants

DOI10.1137/16M1065197zbMATH Open1370.90170arXiv1603.03366MaRDI QIDQ5348458FDOQ5348458

Authors: Nam Ho-Nguyen, Fatma Kılınç-Karzan 

Publication date: 16 August 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1603.03366

Recommendations

• Second-order-cone constraints for extended trust-region subproblems
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• The generalized trust region subproblem: solution complexity and convex hull results
• A two-variable approach to the two-trust-region subproblem
• The trust region subproblem with non-intersecting linear constraints

zbMATH Keywords

convex hulliterative methodstrust-region subproblemconvex reformulationsecond-order conic programming

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Cites Work

• Computing a Trust Region Step
• Solving the Trust-Region Subproblem using the Lanczos Method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Survey of the S-Lemma
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Theory and applications of robust optimization
• Robust optimization
• Trust Region Methods
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• Hidden conic quadratic representation of some nonconvex quadratic optimization problems
• New Results on Quadratic Minimization
• The generalized trust region subproblem
• Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• On Cones of Nonnegative Quadratic Functions
• Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
• On the mapping of quadratic forms
• The trust region subproblem with non-intersecting linear constraints
• Trust region subproblem with an additional linear inequality constraint
• Second-order-cone constraints for extended trust-region subproblems
• Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• A constrained eigenvalue problem
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A new matrix-free algorithm for the large-scale trust-region subproblem
• A linear-time algorithm for trust region problems
• A derivative-free algorithm for least-squares minimization
• Iterative methods for finding a trust-region step
• A Subspace Minimization Method for the Trust-Region Step
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• On solving trust-region and other regularised subproblems in optimization
• A gentle, geometric introduction to copositive optimization
• Exactness conditions for an SDP relaxation of the extended trust region problem
• Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
• How to convexify the intersection of a second order cone and a nonconvex quadratic
• The trust region subproblem and semidefinite programming*
• Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
• Title not available (Why is that?)
• An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations
• Interior point gradient algorithm for totally nonnegative least-squares problems in inequality sense
• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• Solving the trust-region subproblem by a generalized eigenvalue problem
• Local nonglobal minima for solving large-scale extended trust-region subproblems
• A note on polynomial solvability of the CDT problem
• Title not available (Why is that?)
• Quadratic programs with hollows
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• A second-order cone based approach for solving the trust-region subproblem and its variants
• Online First-Order Framework for Robust Convex Optimization

Cited In (38)

• Semidefinite representable reformulations for two variants of the trust-region subproblem
• Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step
• Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
• Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
• Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
• First-Order Methods for Nonconvex Quadratic Minimization
• Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem
• A Linear-Time Algorithm for Generalized Trust Region Subproblems
• Accelerated methods for nonconvex optimization
• A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint
• On the tightness of SDP relaxations of QCQPs
• A second-order cone based approach for solving the trust-region subproblem and its variants
• A survey of hidden convex optimization
• An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem
• A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
• Solving the Cubic Regularization Model by a Nested Restarting Lanczos Method
• On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints
• Second-order-cone constraints for extended trust-region subproblems
• An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
• Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem
• A block Lanczos method for the extended trust-region subproblem
• The generalized trust region subproblem: solution complexity and convex hull results
• The equivalence of optimal perspective formulation and Shor's SDP for quadratic programs with indicator variables
• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• Title not available (Why is that?)
• On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem
• On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
• On Convex Hulls of Epigraphs of QCQPs
• Online First-Order Framework for Robust Convex Optimization
• A two-variable approach to the two-trust-region subproblem
• Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem
• Accelerated first-order methods for a class of semidefinite programs
• (Global) optimization: historical notes and recent developments
• An Inexact Augmented Lagrangian Method for Second-Order Cone Programming with Applications
• Title not available (Why is that?)
• Globally solving the trust region subproblem using simple first-order methods
• Finding second-order stationary points in constrained minimization: a feasible direction approach
• Refined bounds on the convergence of block Lanczos method for extended trust-region subproblem

Uses Software

• GQTPAR
• HSL-VF05

This page was built for publication: A second-order cone based approach for solving the trust-region subproblem and its variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5348458)