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

DOI10.1137/16M1065197zbMath1370.90170arXiv1603.03366MaRDI QIDQ5348458

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

Publication date: 16 August 2017

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

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

zbMATH Keywords

iterative methodsconvex hulltrust-region subproblemconvex reformulationsecond-order conic programming

Mathematics Subject Classification ID

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

Related Items (31)

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

Uses Software

• GQTPAR
• HSL-VF05

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trust region subproblem with an additional linear inequality constraint
• A linear-time algorithm for trust region problems
• Exactness conditions for an SDP relaxation of the extended trust region problem
• The generalized trust region subproblem
• Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
• Local nonglobal minima for solving large-scale extended trust-region subproblems
• How to convexify the intersection of a second order cone and a nonconvex quadratic
• On solving trust-region and other regularised subproblems in optimization
• Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
• A constrained eigenvalue problem
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality
• Quadratic programs with hollows
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• A gentle, geometric introduction to copositive optimization
• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• Hidden conic quadratic representation of some nonconvex quadratic optimization problems
• The trust region subproblem with non-intersecting linear constraints
• A New Matrix-Free Algorithm for the Large-Scale Trust-Region Subproblem
• Lectures on Modern Convex Optimization
• A Note on Polynomial Solvability of the CDT Problem
• An Exact Algorithm for Nonconvex Quadratic Integer Minimization Using Ellipsoidal Relaxations
• Solving the Trust-Region Subproblem By a Generalized Eigenvalue Problem
• A Derivative-Free Algorithm for Least-Squares Minimization
• Theory and Applications of Robust Optimization
• Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
• Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
• Computing a Trust Region Step
• 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
• New Results on Quadratic Minimization
• Trust Region Methods
• The trust region subproblem and semidefinite programming*
• Solving the Trust-Region Subproblem using the Lanczos Method
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• Online First-Order Framework for Robust Convex Optimization
• Second-Order-Cone Constraints for Extended Trust-Region Subproblems
• A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants
• On Cones of Nonnegative Quadratic Functions
• Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
• A Survey of the S-Lemma
• On the mapping of quadratic forms

This page was built for publication: A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants