A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs

DOI10.1007/S10107-018-1265-5MaRDI QIDQ6287627arXivDBLPWikidataFDO

Authors Yanli Liu, Ernest K. Ryu, Wotao Yin

Publication date 7 June 2017

Numerical mathematical programming methods (65K05) Convex programming (90C25) Monotone operators and generalizations (47H05) Iterative procedures involving nonlinear operators (47J25) Numerical methods for variational inequalities and related problems (65K15)

Abstract: In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting, or equivalently ADMM. 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.

This page was built for publication: A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6287627)