This post aims at proving a standard result in quadratic programming called S-Lemma. The use of this result will be obvious in a future post. We begin with a lemma.

**Lemma 1.** Let be two real symmetric matrices such that and . Then there exists such that and .

*Proof.* First write where is orthogonal and is diagonal. Also consider a random vector where each takes values with probability 1/2-1/2, and ‘s are independent. Since (Kronecker delta),

.

Thus there is a vector such that . Set . Then . On the other hand, for any ,

.

Thus our choice of does the job.

Then we go to the main course. When we say it means are symmetric matrices and is positive semidefinite.

**Theorem 2 (S-Lemma).** Let be two real symmetric matrices. Suppose there is such that . Then the following are equivalent:

(1) If is such that , then .

(2) There is such that (i.e., for any ).

*Proof.* (2) clearly implies (1). To show the converse, suppose (1) holds. By the existence of in the statement and (1) we know the problem

(i)

is strictly feasible and has nonnegative value. We consider the following semidefinite relaxation of (i) (comes from replacing by ):

(ii)

One can show by linear algebra that is compact in , hence (ii) is bounded from below. By setting to be the normalized (trace ) matrix of for small positive one sees that (ii) is strictly feasible (i.e., , and is symmetric positive definite). By the strong duality of conic linear programming (Remark: I don’t have a good reference of this now, probably I will write another post discussing this topic which is indeed interesting), the dual problem of (ii), which is

(iii) ,

has an optimal solution of which the optimal value is the same as that of (ii). So there exists and such that

If the CLAIM “the optimal value of (ii) is nonnegative” is true, then strong duality says so which is the conclusion. Thus it remains to prove the CLAIM as follows.

Suppose is the optimal solution for (ii). Since , by diagonalization we know there is such that . Let and . Then

We want to show . Suppose not. Then . So by Lemma 1 there is such that and . Unwinding these and set , we see that

contradicting the assumption (1).

Since and are homogeneous quadratic polynomials, some people call the above S-Lemma the homogeneous S-Lemma. This result also works for inhomogeneous quadratic polynomials. It follows from Theorem 2 and homogenization:

**Corollary 3.** Let and where are symmetric matrices, and . Notice that

and

where , , .

Suppose there exists with . Then the following assertions are equivalent:

(1) If is such that , then .

(2) There exists such that .

(3) There exists such that for all .

Reference of this article: A. Nemirovski, Lectures on Modern Convex Optimization.

Hi, thanks for sharing this post. I have some little questions as below:

(a) (ii) indeed is equivalent to (i) rather than relaxation because X always positive definite.

(b) The CLAIM is just the restatement of (1) because every feasible x in (i) (i.e., X in (ii)), x’Bx>=0, so the optimal value of (ii) is nonnegative.

Sorry, TYPO. X is always positive semidefinite.

No, I don’t think (i) and (ii) are equivalent because not every can be decomposed into .

I see. Thank you.