A Linear-Time Algorithm for Generalized Trust Region Subproblems
From MaRDI portal
Publication:5853724
DOI10.1137/18M1215165zbMath1461.90086arXiv1807.07563OpenAlexW3012188060MaRDI QIDQ5853724
Publication date: 11 March 2021
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.07563
semidefinite programmingapproximation algorithmsgeneralized trust region subproblemlinear-time complexity
Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Approximation algorithms (68W25)
Related Items
On the tightness of SDP relaxations of QCQPs ⋮ Positive semidefinite interval of matrix pencil and its applications to the generalized trust region subproblems ⋮ On the exactness of a simple relaxation for the extended Celis–Dennis–Tapia subproblem ⋮ Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem ⋮ 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
Cites Work
- Unnamed Item
- A linear-time algorithm for trust region problems
- The generalized trust region subproblem
- Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices
- An efficient algorithm for solving the generalized trust region subproblem
- A linear-time algorithm for the trust region subproblem based on hidden convexity
- Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint
- Hidden convexity in some nonconvex quadratically constrained quadratic programming
- Hidden conic quadratic representation of some nonconvex quadratic optimization problems
- The trust region subproblem with non-intersecting linear constraints
- A Two-Variable Approach to the Two-Trust-Region Subproblem
- Simultaneous Diagonalization of Matrices and Its Applications in Quadratically Constrained Quadratic Programming
- A Derivative-Free Algorithm for Least-Squares Minimization
- Computing a Trust Region Step
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
- New Results on Quadratic Minimization
- Trust Region Methods
- Consensus-ADMM for General Quadratically Constrained Quadratic Programming
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem
- 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
- A Survey of the S-Lemma
