A new use of Douglas–Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
A new use of Douglas–Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
复制标题
DOI：
10.1007/s10107-018-1265-5
复制
发表时间：
2018-04
影响因子：
2.7
通讯作者：
Yanli Liu;Ernest K. Ryu;W. Yin
中科院分区：
文献类型：
--
作者：
Yanli Liu;Ernest K. Ryu;W. Yin
在本文中，我们提出了一种方法来识别不可行的，无界的，和病理锥规划的基础上道格拉斯-Rachford分裂。当一个优化程序是不可行的，无界的，或病态的，道格拉斯-拉赫福德分裂的迭代发散。令人惊讶的是，这种发散迭代仍然提供了有用的信息，我们的方法用于识别。此外，对于强不可行的问题，该方法产生一个分离的超平面，并告知用户如何最小限度地修改给定的问题，以实现强可行性。作为一阶方法，该算法依赖于简单的子程序，因此实现简单，每次迭代的成本低。
In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas–Rachford splitting. When an optimization program is infeasible, unbounded, or pathological, the iterates of Douglas–Rachford splitting diverge. Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for identification. In addition, for strongly infeasible problems the method produces a separating hyperplane and informs the user on how to minimally modify the given problem to achieve strong feasibility. As a first-order method, the proposed algorithm relies on simple subroutines, and therefore is simple to implement and has low per-iteration cost.