Open Collections

On the Approximation Guarantee for a Semidefinite Relaxation of a Class of Robust Quadratic Optimization Problems

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Operations research, mathematical programming; Probability theory and stochastic processes; Operation research

video/mp4

Author affiliation: The Chinese University of Hong Kong

2018-09-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/67099

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/