The generalized trust region subproblem: solution complexity and convex hull results
From MaRDI portal
Publication:2118085
DOI10.1007/S10107-020-01560-8zbMATH Open1489.90099arXiv1907.08843OpenAlexW3092375986MaRDI QIDQ2118085FDOQ2118085
Authors: Alex L. Wang, Fatma Kılınç-Karzan 
Publication date: 22 March 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We consider the Generalized Trust Region Subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this nonconvex set in terms of the generalized eigenvalues of an associated matrix pencil. This result may be of interest in building relaxations for nonconvex quadratic programs. Moreover, this result allows us to reformulate the GTRS as the minimization of two convex quadratic functions in the original space. Our next set of contributions is algorithmic: we present an algorithm for solving the GTRS up to an epsilon additive error based on this reformulation. We carefully handle numerical issues that arise from inexact generalized eigenvalue and eigenvector computations and establish explicit running time guarantees for these algorithms. Notably, our algorithms run in linear (in the size of the input) time. Furthermore, our algorithm for computing an epsilon-optimal solution has a slightly-improved running time dependence on epsilon over the state-of-the-art algorithm. Our analysis shows that the dominant cost in solving the GTRS lies in solving a generalized eigenvalue problem -- establishing a natural connection between these problems. Finally, generalizations of our convex hull results allow us to apply our algorithms and their theoretical guarantees directly to equality-, interval-, and hollow- constrained variants of the GTRS. This gives the first linear-time algorithm in the literature for these variants of the GTRS.
Full work available at URL: https://arxiv.org/abs/1907.08843
Recommendations
- A linear-time algorithm for generalized trust region subproblems
- The generalized trust region subproblem
- Novel reformulations and efficient algorithms for the generalized trust region subproblem
- A second-order cone based approach for solving the trust-region subproblem and its variants
- An efficient algorithm for solving the generalized trust region subproblem
Quadratic programming (90C20) Convex programming (90C25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- Computing a Trust Region Step
- Solving the Trust-Region Subproblem using the Lanczos Method
- HSL-VF05
- Title not available (Why is that?)
- A Survey of the S-Lemma
- Trust Region Methods
- Hidden convexity in some nonconvex quadratically constrained quadratic programming
- Hidden conic quadratic representation of some nonconvex quadratic optimization problems
- The generalized trust region subproblem
- Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
- Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- A semidefinite framework for trust region subproblems with applications to large scale minimization
- A linear-time algorithm for trust region problems
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Some results for quadratic problems with one or two quadratic constraints
- How to convexify the intersection of a second order cone and a nonconvex quadratic
- Two-term disjunctions on the second-order cone
- The trust region subproblem and semidefinite programming*
- An Improved Arc Algorithm for Detecting Definite Hermitian Pairs
- An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations
- Convex hull of two quadratic or a conic quadratic and a quadratic inequality
- Convex hull of two quadratic constraints is an LMI set
- An efficient algorithm for solving the generalized trust region subproblem
- Lectures on convex optimization
- Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming
- Title not available (Why is that?)
- Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint
- SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices
- Novel reformulations and efficient algorithms for the generalized trust region subproblem
- A linear-time algorithm for generalized trust region subproblems
- Quadratic programs with hollows
- A linear-time algorithm for the trust region subproblem based on hidden convexity
- Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint
- 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 (22)
- Semidefinite representable reformulations for two variants of the trust-region subproblem
- On the global optimality of generalized trust region subproblems
- Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
- The generalized trust region subproblem
- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- A new technique to derive tight convex underestimators (sometimes envelopes)
- On the tightness of SDP relaxations of QCQPs
- A second-order cone based approach for solving the trust-region subproblem and its variants
- An efficient algorithm for solving the generalized trust region subproblem
- A linear-time algorithm for trust region problems
- SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices
- Projectively and Weakly Simultaneously Diagonalizable Matrices and their Applications
- Novel reformulations and efficient algorithms for the generalized trust region subproblem
- A linear-time algorithm for generalized trust region subproblems
- Toward nonquadratic S-lemma: new theory and application in nonconvex optimization
- On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
- On the convexification of constrained quadratic optimization problems with indicator variables
- On Convex Hulls of Epigraphs of QCQPs
- A linear-time algorithm for the trust region subproblem based on hidden convexity
- Accelerated first-order methods for a class of semidefinite programs
- Global strong convexity and characterization of critical points of time-of-arrival-based source localization
- Convex hull results on quadratic programs with non-intersecting constraints
Uses Software
This page was built for publication: The generalized trust region subproblem: solution complexity and convex hull results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118085)
