The generalized trust region subproblem: solution complexity and convex hull results

DOI10.1007/S10107-020-01560-8MaRDI QIDQ2118085zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

convex hullgeneralized trust region subproblemlinear time complexity

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)

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.

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

Cites work

• scientific article; zbMATH DE number 3658558 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A Survey of the S-Lemma
• A linear-time algorithm for generalized trust region subproblems
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• A linear-time algorithm for trust region problems
• 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 Improved Arc Algorithm for Detecting Definite Hermitian Pairs
• An efficient algorithm for solving the generalized trust region subproblem
• An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations
• Computing a Trust Region Step
• Convex hull of two quadratic constraints is an LMI set
• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint
• Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• HSL-VF05
• 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
• Lectures on convex optimization
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• Online first-order framework for robust convex optimization
• Quadratic programs with hollows
• SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices
• Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming
• Solving the Trust-Region Subproblem using the Lanczos Method
• Some results for quadratic problems with one or two quadratic constraints
• The generalized trust region subproblem
• The trust region subproblem and semidefinite programming*
• Trust Region Methods
• Two-term disjunctions on the second-order cone

Cited in

(22)

• Convex hull results on quadratic programs with non-intersecting constraints
• Semidefinite representable reformulations for two variants of the trust-region subproblem
• On the global optimality of generalized trust region subproblems
• The generalized trust region subproblem
• Implicit Regularity and Linear Convergence Rates for 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 linear-time algorithm for trust region problems
• An efficient algorithm for solving the generalized trust region subproblem
• SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices
• A second-order cone based approach for solving the trust-region subproblem and its variants
• 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

Describes a project that uses

Uses Software

• HSL-VF05
• GQTPAR

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)