Wotao Yin, University of California, Los Angeles

Abstract

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 feasible-yet-unbounded problems. In this talk, we present a method for classifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting, or ADMM. When an optimization program is infeasible, unbounded, or pathological, the z^k iterates of Douglas-Rachford splitting diverge. 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.

This is joint work with Yanli Liu and Ernest Ryu.

Slides     Video