A linear-time algorithm for trust region problems

DOI10.1007/S10107-015-0933-YzbMATH Open1346.90654arXiv1401.6757OpenAlexW1483062147MaRDI QIDQ304248FDOQ304248

Authors: Elad Hazan, Tomer Koren 

Publication date: 25 August 2016

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

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.

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

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

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)

Cites Work

• Computing a Trust Region Step
• Solving the Trust-Region Subproblem using the Lanczos Method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trust Region Methods
• Hidden convexity in some nonconvex quadratically constrained quadratic programming
• New Results on Quadratic Minimization
• Indefinite Trust Region Subproblems and Nonsymmetric Eigenvalue Perturbations
• On Cones of Nonnegative Quadratic Functions
• On general minimax theorems
• A trust-region approach to the regularization of large-scale discrete forms of ill-posed problems
• Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• A constrained eigenvalue problem
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A new trust region technique for the maximum weight clique problem
• A new matrix-free algorithm for the large-scale trust-region subproblem
• A derivative-free algorithm for least-squares minimization
• Iterative methods for finding a trust-region step
• A Subspace Minimization Method for the Trust-Region Step
• Computing Optimal Locally Constrained Steps
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Computing correlated equilibria in multi-player games
• On solving trust-region and other regularised subproblems in optimization

Cited In (27)

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

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)