Tractable approximations to robust conic optimization problems

Abstract

In earlier proposals, the robust counterpart of conic optimization problems exhibits a lateral increase in complexity, i.e., robust linear programming problems (LPs) become second order cone problems (SOCPs), robust SOCPs become semidefinite programming problems (SDPs), and robust SDPs become NP-hard. We propose a relaxed robust counterpart for general conic optimization problems that (a) preserves the computational tractability of the nominal problem; specifically the robust conic optimization problem retains its original structure, i.e., robust LPs remain LPs, robust SOCPs remain SOCPs and robust SDPs remain SDPs, and (b) allows us to provide a guarantee on the probability that the robust solution is feasible when the uncertain coefficients obey independent and identically distributed normal distributions.