Robust Quadratic Programming with Mixed-Integer Uncertainty
Robust Quadratic Programming with Mixed-Integer Uncertainty
复制标题
DOI：
10.1287/ijoc.2019.0901
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Areesh Mittal;C. Gokalp;G. A. Hanasusanto
中科院分区：
文献类型：
--
作者：
Areesh Mittal;C. Gokalp;G. A. Hanasusanto
我们研究鲁棒凸二次规划，其中不确定的问题参数可包含连续分量和整数分量。在对不确定集的自然有界性假设下，我们表明一般问题可转化为多项式规模的精确余正规划形式。这些凸优化问题是NP难的，但允许一个保守的半定规划（SDP）近似，该近似可有效求解。我们证明了流行的近似S - 引理方法——它仅在连续不确定性的情况下有效——比我们的近似方法弱。我们还表明，如果问题具有完全补偿，所有结果都可扩展到两阶段鲁棒二次优化设置。我们评估了我们提出的SDP形式的有效性，并在最小二乘法、项目管理和多物品报童问题的实例上证明了它们相对于现有最佳解决方案的优越性。
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact copositive programming reformulations of polynomial size. These convex optimization problems are NP-hard but admit a conservative semidefinite programming (SDP) approximation that can be solved efficiently. We prove that the popular approximate S-lemma method --- which is valid only in the case of continuous uncertainty --- is weaker than our approximation. We also show that all results can be extended to the two-stage robust quadratic optimization setting if the problem has complete recourse. We assess the effectiveness of our proposed SDP reformulations and demonstrate their superiority over the state-of-the-art solution schemes on instances of least squares, project management, and multi-item newsvendor problems.