Optimization Online


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

Immanuel M. Bomze (immanuel.bomze***at***univie.ac.at)
Michael L. Overton (overton***at***overton.cs.nyu.edu)

Abstract: We study the {\em 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.

Keywords: Copositive matrices, non-convex optimization, global optimality condition, polynomial optimization, trust region problem

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Global Optimization (Theory )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Preprint NI13063-POP, Isaac Newton Institute for Mathematical Sciences, University of Cambridge UK, submitted

Download: [PDF]

Entry Submitted: 11/17/2013
Entry Accepted: 11/17/2013
Entry Last Modified: 12/01/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society