Robust solutions to uncertain semidefinite programs
Robust solutions to uncertain semidefinite programs
复制标题
DOI：
10.1137/s1052623496305717
复制
发表时间：
1998-11-20
影响因子：
3.1
通讯作者：
Lebret, H
中科院分区：
文献类型：
--
作者：
El Ghaoui, L;Oustry, F;Lebret, H
在本文中，我们考虑半定规划（SDPs）的数据依赖于一些未知的，但有界的扰动参数。我们寻求“强大”的解决方案，这样的程序，即解决方案，最大限度地减少（最坏情况下）的目标，同时满足给定范围内的参数的每个可能的值的约束。假设数据矩阵是摄动参数的有理函数，我们将展示如何制定一个强大的解决方案存在的SDPs的充分条件。当扰动是“满的”时，我们的条件是充分必要的。在这种情况下，我们提供了充分的条件，保证鲁棒的解决方案是唯一的和连续的（持有人稳定）相对于未扰动问题的数据。因此，该方法可以用于正则化病态的SDP。我们说明我们的结果与线性规划，最大范数最小化，多项式插值和整数规划的例子。
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 (Holder-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.