A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid

• 成果类型: Article
• 署名作者: Beck, Amir; Teboulle, Marc
• 署名单位: Technion Israel Institute of Technology; Tel Aviv University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0181-x
• 发表日期: 2009
• 页码: 13-35
• 关键词: trust region subproblems; Strong Duality; relaxation

摘要

We consider the nonconvex problem (RQ) of minimizing the ratio of two nonconvex quadratic functions over a possibly degenerate ellipsoid. This formulation is motivated by the so-called regularized total least squares problem (RTLS), which is a special case of the problem's class we study. We prove that under a certain mild assumption on the problem's data, problem (RQ) admits an exact semidefinite programming relaxation. We then study a simple iterative procedure which is proven to converge superlinearly to a global solution of (RQ) and show that the dependency of the number of iterations on the optimality tolerance epsilon grows as O(root ln epsilon(-1)).