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

Yanli Liu, Ernest K. Ryu, and Wotao Yin

Submitted:

Overview

First-order methods such as ADMM and Douglas-Rachford splitting are known for their easy implementations and low per-iteration costs. What is less known is their usefulness for “solving” infeasible problems and unbounded (though feasible) problems.

In this paper, we present a method for classifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting, or equivalently ADMM. When an optimization program is infeasible, unbounded, or pathological, the z^k iterates of Douglas-Rachford splitting or ADMM diverge. Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for classification. They help us identify some of the cases where existing solvers cannot do reliably.

When the problem is infeasible or weakly feasible, it is useful to know how to minimally modify the problem data to achieve strong feasibility, where “strong” makes it easier to find a solution. We also get this information via the divergent iterates.

Citation

Y. Liu, E. Ryu, and W. Yin, A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs, UCLA CAM Report 17-31, 2017.


« Back