Douglas-Rachford Splitting for Pathological Convex Optimization

Ernest K. Ryu, Yanli Liu, and Wotao Yin

Submitted:

Overview

Despite the vast literature on Douglas-Rachford splitting (DRS), there has been very little work analyzing their behavior under pathologies. Most analyses assume a primal solution exists, a dual solution exists, and strong duality holds. When these assumptions are not met, i.e., under pathologies, the theory often breaks down and the empirical performance may degrade signi´Čücantly.

In this paper, we establish that DRS only requires strong duality to work, in the sense that asymptotically iterates are approximately feasible and approximately optimal.

Citation

E. Ryu, Y. Liu, and W. Yin, Douglas-Rachford Splitting for Pathological Convex Optimization, UCLA CAM Report 18-06, 2018.


« Back