A linear-time algorithm for generalized trust region subproblems

DOI10.1137/18M1215165MaRDI QIDQ5853724zbMATH OpenOpenAlexFDO

Authors Rujun Jiang, Duan Li

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

zbMATH Keywords

semidefinite programmingapproximation algorithmsgeneralized trust region subproblemlinear-time complexity

Mathematics Subject Classification ID

Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22) Approximation algorithms (68W25)

Abstract: In this paper, we provide the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regular conditions. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 2016, 158(1-2): 363-381]. However, due to the non-convexity and non-compactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regular condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS.

Recommendations

• The generalized trust region subproblem: solution complexity and convex hull results
• A linear-time algorithm for trust region problems
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem

Cites work

• scientific article; zbMATH DE number 3368525 (Why is no real title available?)
• A Survey of the S-Lemma
• A derivative-free algorithm for least-squares minimization
• 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
• A two-variable approach to the two-trust-region subproblem
• An efficient algorithm for solving the generalized trust region subproblem
• Computing a Trust Region Step
• Consensus-ADMM for General Quadratically Constrained Quadratic Programming
• 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
• Hidden conic quadratic representation of some nonconvex quadratic optimization problems
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
• New Results on Quadratic Minimization
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• On Cones of Nonnegative Quadratic Functions
• SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices
• Second-order-cone constraints for extended trust-region subproblems
• Simultaneous diagonalization of matrices and its applications in quadratically constrained quadratic programming
• The generalized trust region subproblem
• The trust region subproblem with non-intersecting linear constraints
• Trust Region Methods

Cited in

(11)

• On the global optimality of generalized trust region subproblems
• Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
• 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
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• The generalized trust region subproblem: solution complexity and convex hull results
• 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
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem

Describes a project that uses

Uses Software

• GQTPAR

This page was built for publication: A linear-time algorithm for generalized trust region subproblems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853724)