Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition

EI-ERIM-OR seminar
Speaker

Juan C. Vera Lizcano

Date
Friday 20 May 2022, 12:00 - 13:00
Type
Seminar
Spoken Language
English
Room
3-18
Building
Polak Building
Add to calendar

We provide new insight into the convergence properties of the Douglas-Rachford algorithm for the problem  min_x { f(x) + g(x) }, where f and g are convex functions. Our approach relies on and highlights the natural primal-dual symmetry between the above problem and its Fenchel dual.

Our main development is to show the linear convergence of the algorithm when a natural error bound condition on the Douglas-Rachford operator holds. We leverage our error bound condition approach to show and estimate the algorithm's linear rate of convergence for three special classes of problems. The first one is under are strongly convexity assumptions. The second one is when f and g are piecewise linear-quadratic functions. The third one is when f and g are the indicator functions of closed convex cones. In all three cases the rate of convergence is determined by a suitable measure of well-posedness of the problem. In the conic case, if the two closed convex cones are a linear subspace and the non-negative orthant, we establish a stronger finite termination result. Our developments have straightforward extensions to the more general linearly constrained problem thereby highlighting a direct and straightforward relationship between the Douglas-Rachford algorithm and the alternating direction method of multipliers (ADMM).

This is a joint work with Javier Peña (Carnegie Mellon University - USA) and Luis F. Zuluaga (Lehigh University - USA).

About Juan C. Vera Lizcano

Juan C. Vera Lizcano is an associate professor of optimization in the department of Econometrics and Operations Research at Tilburg University. His expertise includes polynomial and conic optimization and their applications to combinatorial optimization; relation between error bounds, condition numbers, and convergence of optimization algorithms; sparse methods for machine learning.

Coordinators

  • Michal Mankowski
  • Olga Kuryatnikova
More information

Zoom broadcasting:
https://eur-nl.zoom.us/j/95156986071?pwd=NmhWa2pYbWRoL3F1SWtxcElGZUhOQT09 
Meeting ID: 951 5698 6071
Passcode: 385550

Secretariat Econometrics
Phone: +31 (0)10 408 12 59/ 12 64
Email: eb-secr@ese.eur.nl

Related links
Department of Econometrics

Compare @count study programme

  • @title

    • Duration: @duration
Compare study programmes