Consider the setting where each vertex of a graph has a function, and communications can only occur between vertices connected by an edge. We wish to minimize the sum of these functions. For the case when each function is the sum of a strongly convex quadratic and a convex function, we propose a distributed version of Dykstra's algorithm. This algorithm is distributed, decentralized, asynchronous, has deterministic convergence. We show how to extend to directed graphs with unreliable communications and some results on convergence rates.
We propose nonlinear forward-backward splitting with projection correction. The algorithm performs a forward-backward step that creates a separating hyperplane between the current point and the solution set. This is followed (if needed) by a correction step that projects onto the separating hyperplane. The metric in the backward step is an arbitrary strictly monotone single-valued mapping. This gives a very general method with known special cases such as, AFBA, Bregman PDHG, NoLips, FB(H)F, etc. Another special case is a novel four-operator splitting method for monotone inclusions.
joint work with Ernest Ryu, Carolina Bergeling, Pontus Giselsson
We propose a methodology for automatically studying the performance of common splitting methods. The methodology enjoys comfortable tightness guarantees and relies on appropriate uses of semidefinite programming and/or symbolic computations. We illustrate the use of the framework for generating tight contraction factors for Douglas--Rachford splitting that are likely too complicated for a human to find bare-handed. We show that the methodology can also be used for performing optimal parameter selection.