A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs

• 成果类型: Article
• 署名作者: Liu, Yanli; Ryu, Ernest K.; Yin, Wotao
• 署名单位: University of California System; University of California Los Angeles
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1265-5
• 发表日期: 2019
• 页码: 225-253
• 关键词: facial reduction; optimization; SUM; algorithms

摘要

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.