טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentLaevsky Dina
SubjectThe S-lemma: Extensions and Applications
DepartmentDepartment of Applied Mathematics
Supervisor Professor Emeritus Aharon Ben-Tal


Abstract

The S-lemma is a theorem about two quadratic forms stating that for two symmetric matrices A, B the implication

xTAx ³ 0 Þ xTBx ³ 0

holds iff

$l ³ 0 : B - lA ³ 0.


In this work we present several proofs and extensions of the S-lemma as well as an approximate version of the S-lemma and give a new proof of the S-lemma based on the proof of the approximate S-lemma.

One of the main results of the approximate S-lemma is the definition of a quantitative measure of the proximity of the approximate solution to the true one.

In the original version of the approximate S-lemma this measure depends on the sum of ranks of data matrices, whereas the improved result states that it depends only on the number of data matrices.

Recent applications of the S-lemma are in optimization problems with uncertain data. Such problems have been recently treated by the robust optimization paradigm.

Generally, the robust counterpart of a conic quadratic optimization problem is a problem with infinitely many quadratic constraints. However, when the uncertainty is modeled by a single ellipsoid, it can be shown, using the S-lemma, that the robust counterpart is equivalent to single deterministic semidefinite program.

When the uncertainty is modeled by intersection of ellipsoids, we use the approximate S-lemma to obtain deterministic semidefinite program, whose solution is an approximate robust solution to the original problem, with a  guarantied level of proximity to the true solution.

Finally we present an example of antenna design as a concrete application of the approximate S-lemma.