Robust Solutions to Uncertain Semidefinite Programs
Laurent El Ghaoui, François Oustry, Hervé Lebret · SIAM Journal on Optimization · 1998
In this paper we consider semidefinite programs (SDPs) whose data depend on some unknown but bounded perturbation parameters. We seek "robust" solutions to such programs, that is, solutions which minimize the (worst-case) objective while satisfying the constraints for every possible value of parameters within the given bounds. Assuming the data matrices are rational functions of the perturbation parameters, we show how to formulate sufficient conditions for a robust solution to exist as SDPs. When the perturbation is "full," our conditions are necessary and sufficient. In this case, we provide sufficient conditions which guarantee that the robust solution is unique and continuous (Hölder-stable) with respect to the unperturbed problem's data. The approach can thus be used to regularize ill-conditioned SDPs. We illustrate our results with examples taken from linear programming, maximum norm minimization, polynomial interpolation, and integer programming.
Cited by 935 works. doi:10.1137/s1052623496305717
Authors
References
- Linear Matrix Inequalities in System and Control Theory
- Solutions of Ill-Posed Problems.
- Robust and optimal control
- Semidefinite Programming
- Stochastic Programming
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- Robust Solutions to Least-Squares Problems with Uncertain Data
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Method of centers for minimizing generalized eigenvalues
- Robustness in the presence of mixed parametric uncertainty and unmodeled dynamics