A second-order cone based approach for solving the trust-region subproblem and its variants
From MaRDI portal
Publication:5348458
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.
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
Cites work
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3903874 (Why is no real title available?)
- scientific article; zbMATH DE number 3658558 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Subspace Minimization Method for the Trust-Region Step
- A Survey of the S-Lemma
- A constrained eigenvalue problem
- A derivative-free algorithm for least-squares minimization
- A gentle, geometric introduction to copositive optimization
- A linear-time algorithm for the trust region subproblem based on hidden convexity
- A linear-time algorithm for trust region problems
- A new matrix-free algorithm for the large-scale trust-region subproblem
- A note on polynomial solvability of the CDT problem
- A second-order cone based approach for solving the trust-region subproblem and its variants
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations
- Computing a Trust Region Step
- Convex hull of two quadratic or a conic quadratic and a quadratic inequality
- Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
- Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Exactness conditions for an SDP relaxation of the extended trust region problem
- Hidden conic quadratic representation of some nonconvex quadratic optimization problems
- Hidden convexity in some nonconvex quadratically constrained quadratic programming
- How to convexify the intersection of a second order cone and a nonconvex quadratic
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Iterative methods for finding a trust-region step
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Local nonglobal minima for solving large-scale extended trust-region subproblems
- Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
- New Results on Quadratic Minimization
- On Cones of Nonnegative Quadratic Functions
- On solving trust-region and other regularised subproblems in optimization
- On the mapping of quadratic forms
- Online first-order framework for robust convex optimization
- Quadratic programs with hollows
- Robust optimization
- Second-order-cone constraints for extended trust-region subproblems
- Solving the Trust-Region Subproblem using the Lanczos Method
- Solving the trust-region subproblem by a generalized eigenvalue problem
- Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
- The generalized trust region subproblem
- The trust region subproblem and semidefinite programming*
- The trust region subproblem with non-intersecting linear constraints
- Theory and applications of robust optimization
- Trust Region Methods
- Trust region subproblem with an additional linear inequality constraint
- Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization
Cited in
(38)- 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
- Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem
- First-Order Methods for Nonconvex Quadratic Minimization
- Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
- scientific article; zbMATH DE number 6961226 (Why is no real title available?)
- An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
- Semidefinite representable reformulations for two variants of the trust-region subproblem
- A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
- On Convex Hulls of Epigraphs of QCQPs
- A second-order cone based approach for solving the trust-region subproblem and its variants
- Finding second-order stationary points in constrained minimization: a feasible direction approach
- A two-variable approach to the two-trust-region subproblem
- On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem
- (Global) optimization: historical notes and recent developments
- An SOCP relaxation based branch-and-bound method for generalized trust-region subproblem
- Novel reformulations and efficient algorithms for the generalized trust region subproblem
- Refined bounds on the convergence of block Lanczos method for extended trust-region subproblem
- A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint
- On the tightness of SDP relaxations of QCQPs
- On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints
- scientific article; zbMATH DE number 5232303 (Why is no real title available?)
- A survey of hidden convex optimization
- Accelerated methods for nonconvex optimization
- Gradient descent finds the cubic-regularized nonconvex Newton step
- Second-order-cone constraints for extended trust-region subproblems
- Globally solving the trust region subproblem using simple first-order methods
- An inexact augmented Lagrangian method for second-order cone programming with applications
- A linear-time algorithm for generalized trust region subproblems
- On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
- Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem
- Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
- Online first-order framework for robust convex optimization
- Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
- Solving the cubic regularization model by a nested restarting Lanczos method
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- A block Lanczos method for the extended trust-region subproblem
- Accelerated first-order methods for a class of semidefinite programs
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)
