A linear-time algorithm for trust region problems

• 成果类型: Article
• 署名作者: Hazan, Elad; Koren, Tomer
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0933-y
• 发表日期: 2016
• 页码: 363-381
• 关键词: subproblems; EIGENVALUE; minimization

摘要

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.