M.Sc Student | Laevsky Dina |
---|---|

Subject | The S-lemma: Extensions and Applications |

Department | Department of Applied Mathematics |

Supervisor | Professor Emeritus Aharon Ben-Tal |

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

*x ^{T}Ax *³
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.