Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
Robust Solutions of Uncertain Quadratic and Conic-Quadratic Problems
复制标题
DOI：
10.1137/s1052623401392354
复制
发表时间：
2002-06
期刊：
影响因子：
--
通讯作者：
A. Ben-Tal;A. Nemirovski;Kees Roos
中科院分区：
文献类型：
--
作者：
A. Ben-Tal;A. Nemirovski;Kees Roos
我们考虑一个具有不确定数据的二次（特别是二次约束）优化问题，已知只存在于某些不确定集${\cal U}$中。这类问题的鲁棒对应物通常导致np困难半确定问题；例如，当${\cal U}$被给定为椭球的交点或作为一个n维方框时，就是这种情况。对于这些情况，我们建立了一个单一的，显式的半确定程序，它近似于NP-hard鲁棒对应物，并且我们得出了近似质量的估计，这基本上与潜在的二次问题的维度无关。
We consider a conic-quadratic (and in particular a quadratically constrained) optimization problem with uncertain data, known only to reside in some uncertainty set ${\cal U}$. The robust counterpart of such a problem leads usually to an NP-hard semidefinite problem; this is the case, for example, when ${\cal U}$ is given as the intersection of ellipsoids or as an n-dimensional box. For these cases we build a single, explicit semidefinite program, which approximates the NP-hard robust counterpart, and we derive an estimate on the quality of the approximation, which is essentially independent of the dimensions of the underlying conic-quadratic problem.