A linear-time algorithm for trust region problems

DOI10.1007/S10107-015-0933-YMaRDI QIDQ304248zbMATH OpenOpenAlexFDO

Authors Elad Hazan, Tomer Koren

Publication date 25 August 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingapproximation algorithmslinear time complexitytrust region methodstrust region subproblem

Mathematics Subject Classification ID

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

Abstract: We consider the fundamental problem of maximizing a general quadratic function over an ellipsoidal domain, also known as the trust region problem. We give the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving this problem. Specifically, our algorithm returns an $epsilon$-approximate solution in time $ildeO(N/sqrtepsilon)$, where $N$ is the number of non-zero entries in the input. This matches the runtime of Nesterov's accelerated gradient descent, suitable for the special case in which the quadratic function is concave, and the runtime of the Lanczos method which is applicable when the problem is purely quadratic.

Recommendations

• A linear-time algorithm for generalized trust region subproblems
• A linear-time algorithm for the trust region subproblem based on hidden convexity
• The generalized trust region subproblem: solution complexity and convex hull results
• Computing a Trust Region Step
• Solving the trust-region subproblem by a generalized eigenvalue problem

Cites work

• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• A Subspace Minimization Method for the Trust-Region Step
• A constrained eigenvalue problem
• A derivative-free algorithm for least-squares minimization
• A new matrix-free algorithm for the large-scale trust-region subproblem
• A new trust region technique for the maximum weight clique problem
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A trust-region approach to the regularization of large-scale discrete forms of ill-posed problems
• Computing Optimal Locally Constrained Steps
• Computing a Trust Region Step
• Computing correlated equilibria in multi-player games
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• 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
• Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
• New Results on Quadratic Minimization
• On Cones of Nonnegative Quadratic Functions
• On general minimax theorems
• On solving trust-region and other regularised subproblems in optimization
• Solving the Trust-Region Subproblem using the Lanczos Method
• Trust Region Methods

Cited in

(27)

• The generalized trust region subproblem: solution complexity and convex hull results
• Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
• Continuation methods with the trusty time-stepping scheme for linearly constrained optimization with noisy data
• Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem
• Newton-type methods for non-convex optimization under inexact Hessian information
• First-Order Methods for Nonconvex Quadratic Minimization
• Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
• A partial ellipsoidal approximation scheme for nonconvex homogeneous quadratic optimization with quadratic constraints
• A second-order cone based approach for solving the trust-region subproblem and its variants
• 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
• Novel reformulations and efficient algorithms for the generalized trust region subproblem
• A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint
• On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint
• A survey of hidden convex optimization
• Accelerated methods for nonconvex optimization
• Gradient descent finds the cubic-regularized nonconvex Newton step
• Globally solving the trust region subproblem using simple first-order methods
• A linear-time algorithm for generalized trust region subproblems
• A linear-time algorithm for globally maximizing the sum of a generalized Rayleigh quotient and a quadratic form on the unit sphere
• On Conic Relaxations of Generalization of the Extended Trust Region Subproblem
• Sublinear-time quadratic minimization via spectral decomposition of matrices
• Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem
• Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem
• Solving the cubic regularization model by a nested restarting Lanczos method
• Accelerated first-order methods for a class of semidefinite programs
• Oracle-based robust optimization via online learning

Describes a project that uses

Uses Software

• QUALEX
• GQTPAR
• HSL-VF05

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

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