Strong duality in minimizing a quadratic form subject to two homogeneous quadratic inequalities over the unit sphere

Ruey-Lin Sheu

Department of Mathematics

National Cheng Kung University

rsheu@mail.ncku.edu.tw

    This problem, called (P), is a contrast with a simpler version (P`'`) which also minimizes a quadratic form but has just one homogeneous quadratic constraint over the unit sphere. The inclusion of an additional homogeneous quadratic constraint can cause (P) to have a positive duality gap, although the simpler version (P`'`) has been proved to adopt strong duality under Slater's condition. On the surface the underlined problem (P) appears to be different from the CDT (Celis-Dennis-Tapia) problem. Their SDP relaxations, however, share a very similar format. The minute observation turns out to be valuable in deriving a necessary and sufficient condition for (P) to admit strong duality. We will see that, in the sense of strong duality results, problem (P) is a generalization of the CDT problem. Many nontrivial examples are constructed in the paper to help understand the mechanism. Finally, as the strong duality in quadratic optimization is closely related to the S-lemma, we derive a new extension of the S-Lemma with three homogeneous quadratic inequalities over the unit sphere, with and without the Slater condition.

Keyword: Quadratically constrained quadratic programming, CDT problem, S-lemma, Slater condition, Joint numerical range