We study convex optimization problems for which the data is not specified e
xactly and it is only known to belong to a given uncertainty set U, yet the
constraints must hold for all possible values of the data from U. The ensu
ing optimization problem is called robust optimization. In this paper we la
y the foundation of robust convex optimization. In the main part of the pap
er we show that if U is an ellipsoidal uncertainty set, then for some of th
e most important generic convex optimization problems (linear programming,
quadratically constrained programming, semidefinite programming and others)
the corresponding robust convex program is either exactly, or approximatel
y, a tractable problem which lends itself to efficient algorithms such as p
olynomial time interior point methods.