Narrowing the difficulty gap for the Celis-Dennis-Tapia problem

• 成果类型: Article
• 署名作者: Bomze, Immanuel M.; Overton, Michael L.
• 署名单位: University of Vienna; New York University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0836-3
• 发表日期: 2015
• 页码: 459-476
• 关键词: 2 quadratic constraints; optimality conditions; cdt subproblem; Strong Duality; optimization; minimization

摘要

We study the Celis-Dennis-Tapia (CDT) problem: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that occurs when the Hessian of the Lagrangian is indefinite at all Karush-Kuhn-Tucker points. We prove new sufficient and necessary conditions both for local and global optimality, based on copositivity, giving a complete characterization in the degenerate case.