Convergence of the Preconditioned Proximal Point Method and Douglas-Rachford Splitting in the Absence of Monotonicity
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916235837440000 |
|---|---|
| author | Evens, Brecht Pas, Pieter Latafat, Puya Patrinos, Panagiotis |
| author_facet | Evens, Brecht Pas, Pieter Latafat, Puya Patrinos, Panagiotis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_03605 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Convergence of the Preconditioned Proximal Point Method and Douglas-Rachford Splitting in the Absence of Monotonicity Evens, Brecht Pas, Pieter Latafat, Puya Patrinos, Panagiotis Optimization and Control 47H04, 49J52, 49J53, 65K05, 65K15, 90C26 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. |
| title | Convergence of the Preconditioned Proximal Point Method and Douglas-Rachford Splitting in the Absence of Monotonicity |
| topic | Optimization and Control 47H04, 49J52, 49J53, 65K05, 65K15, 90C26 |
| url | https://arxiv.org/abs/2305.03605 |