Proximal Point Algorithms for Problems with Structure

Proximal point algorithms are variants of the well-known proximal method, a mathematical tool of paramount importance for analysing a broad class of practical algorithms covering both smooth and non-smooth settings. For instance, the celebrated method of multipliers for non-linear optimization and the progressive hedging algorithm in stochastic programming are two variants of the proximal method. The latter can be applied to mathematical problems other than optimization-related ones. This is the case of variational inequalities and monotone inclusion problems. When applied to optimization problems, proximal point algorithms require some structure: the only assumption of having a (first-order) oracle does not suffice in general. The reason is that the method’s base operation evaluates the proximal operator of a function, which involves solving a convex optimization subproblem per iteration. Without any structure other than convexity, subproblems must be solved via oracle-based algorithms, leading to a path less attractive than applying these algorithms directly to the original problem. This chapter presents the proximal method in an abstract setting of monotone inclusion problems. In doing that, we will be able to study the celebrated Douglas-Rachford splitting method and the more recent progressive decoupling algorithm for solving the broad class of linkage problems, covering several families of optimization and variational inequality problems. As we will show, the progressive decoupling algorithm boils down to several well-known algorithms depending on the linkage problem. We start with a brief review of monotone operators.