A linear-time algorithm for trust region problems

Elad Hazan, Tomer Koren

Research output: Contribution to journalArticlepeer-review

35 Scopus citations


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
Issue number1-2
StatePublished - Jul 1 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


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


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

Cite this