Coauthor: A. Ben-Tal and A. Nemirovski

Title: Robust versions of convex quadratic and conic-quadratic problems

We consider a conic-quadratic (and in particular a quadraticallyconstrained) optimization problem with uncertain data, known onlyto reside in some uncertainty set U. The robust counterpartof such a problem leads usually to an NP-hard semidefiniteproblem; this is the case for example when U is given asintersection of ellipsoids, or as an n-dimensional box. Forthese cases we build a single, explicit semidefinite program,which approximates the NP-hard robust counterpart, and we derivean estimate on the quality of the approximation, which is essentiallyindependent of the dimensions of the underlying conic-quadraticproblem.