Convergence of the Preconditioned Proximal Point Method and Douglas-Rachford Splitting in the Absence of Monotonicity

arXiv2305.03605MaRDI QIDQ6435521FDOQ6435521

Authors: Brecht Evens, Pieter Pas, Puya Latafat, Panagiotis Patrinos 

Publication date: 5 May 2023

Abstract: The proximal point algorithm (PPA) is the most widely recognized method for solving inclusion problems and serves as the foundation for many numerical algorithms. Despite this popularity, its convergence results have been largely limited to the monotone setting. In this work, we study the convergence of (relaxed) preconditioned PPA for a class of nonmonotone problems that satisfy an oblique weak Minty condition. Additionally, we study the (relaxed) Douglas-Rachford splitting (DRS) method in the nonmonotone setting by establishing a connection between DRS and the preconditioned PPA with a positive semidefinite preconditioner. To better characterize the class of problems covered by our analysis, we introduce the class of semimonotone operators, offering a natural extension to (hypo)monotone and co(hypo)monotone operators, and describe some of their properties. Sufficient conditions for global convergence of DRS involving the sum of two semimonotone operators are provided. Notably, it is shown that DRS converges even when the sum of the involved operators (or of their inverses) is nonmonotone. Various example problems are provided, demonstrating the tightness of our convergence results and highlighting the wide range of applications our theory is able to cover.

Has companion code repository: https://github.com/brechtevens/Minty-DRS-examples

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonsmooth analysis (49J52) Set-valued operators (47H04) Set-valued and variational analysis (49J53) Numerical methods for variational inequalities and related problems (65K15)

This page was built for publication: Convergence of the Preconditioned Proximal Point Method and Douglas-Rachford Splitting in the Absence of Monotonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435521)