## 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 language | English (US) |
---|---|

Pages (from-to) | 363-381 |

Number of pages | 19 |

Journal | Mathematical Programming |

Volume | 158 |

Issue number | 1-2 |

DOIs | |

State | Published - Jul 1 2016 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Keywords

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