BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

On the Approximation Guarantee for a Semidefinite Relaxation of a Class of Robust Quadratic Optimization Problems So, Anthony Man-Cho


We consider a class of robust quadratic optimization problems that arise in various applications in signal processing and wireless communications. Although the class of problems under consideration is NP-hard in general, by applying the well-known lifting technique and S-lemma, one can obtain a semidefinite relaxation that yields an approximate solution to the original problem in polynomial time. However, so far there is no approximation guarantee for such semidefinite relaxation. In fact, despite the many available approximation results for semidefinite relaxations of quadratically constrained quadratic optimization problems, none of them apply to the setting where robust constraints are present. In this talk, we present the first approximation guarantee for the aforementioned class of robust quadratic optimization problems. The key to establishing such guarantee is the so-called epsilon-net technique from functional analysis, which allows us to handle the semi-infinite robust quadratic constraints in the problem. If time permits, we will illustrate our result via the problem of robust beamforming with cognitive radio constraints in wireless communications.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International