Robust solutions to uncertain semidefinite programs

In this paper we consider semidefinite programs (SDPs) whose data depend on some unknown but bounded perturbation parameters. We seek "robust" solutio ns to such programs, that is, solutions which minimize the (worst-case) obj ective while satisfying the constraints for every possible value of paramet ers within the given bounds. Assuming the data matrices are rational functi ons of the perturbation parameters, we show how to formulate sufficient con ditions for a robust solution to exist as SDPs. When the perturbation is "f ull," our conditions are necessary and sufficient. In this case, we provide sufficient conditions which guarantee that the robust solution is unique a nd continuous (Holder-stable) with respect to the unperturbed problem's dat a. The approach can thus be used to regularize ill-conditioned SDPs. We ill ustrate our results with examples taken from linear programming, maximum no rm minimization, polynomial interpolation, and integer programming.