A linear-time algorithm for trust region problems

Elad Hazan, Tomer Koren

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

We consider the fundamental problem of minimizing a general quadratic function over an ellipsoidal domain, also known as the trust region (sub)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 ϵ-approximate solution in runtime of order N/ϵ, 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 objective is convex, and the runtime of the Lanczos method which is applicable when the problem is purely quadratic.

Original languageEnglish (US)
Pages (from-to)363-381
Number of pages19
JournalMathematical Programming
Volume158
Issue number1-2
DOIs
StatePublished - Jul 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Approximation algorithms
  • Linear time complexity
  • Semidefinite programming
  • Trust region methods
  • Trust region subproblem

Fingerprint Dive into the research topics of 'A linear-time algorithm for trust region problems'. Together they form a unique fingerprint.

  • Cite this