S-Lemma with Equality and Its Applications

Abstract

Let $f(x)=x^{T}Ax+2a^{T}x+c$ and $h(x)=x^{T}Bx+2b^{T}x+d$ be two quadratic functions having symmetric matrices $A$ and $B$. The S-lemma with equality asks when the unsolvability of the system $f(x)<0,h(x)=0$ implies the existence of a real number $\mu$ such that $f(x)+\mu h(x)\ge 0,\forall x\in {\mathbb{R}}^n$. The problem is much harder than the inequality version which asserts that, under Slater condition, $f(x)<0,h(x)\le 0$ is unsolvable if and only if $f(x)+\mu h(x)\ge 0,\forall x\in {\mathbb{R}}^n$ for some $\mu \ge 0$. In this paper, we show that the S-lemma with equality does not hold only when the matrix $A$ has exactly one negative eigenvalue and $h(x)$ is a non-constant linear function ($B=0,b\ne 0$). As an application, we can globally solve $\inf \{f(x)|h(x)=0\}$ as well as the two-sided generalized trust region subproblem $\inf \{f(x)|l\le h(x)\le u\}$ without any condition. Moreover, the convexity of the joint numerical range $\{(f(x),h_1(x),\dots ,h_p(x)):x\in {\mathbb{R}}^n\}$ where $f$ is a (possibly non-convex) quadratic function and $h_1(x),\dots ,h_p(x)$ are affine functions can be characterized using the newly developed S-lemma with equality.

34 pages