ProximalGradientMethod

This code can be used to reproduce the results from the work (arXiv, JOTA):

[1] Taylor, Adrien B., Julien M. Hendrickx, and François Glineur (2018). "Exact worst-case convergence rates of the proximal gradient method for composite convex minimization". Journal of Optimization Theory and Applications, 178(2), 455-476.

Getting started

To use the code, download the repository and execute the scripts on a one-by-one basis.

Notes:

• This code requires YALMIP along with a suitable SDP solver (e.g., Sedumi, SDPT3, Mosek).
• The files whose name starts with PESTO_* requires the installation of the Performance Estimation Toolbox (PESTO).

Content

The repository contains:

(1) The symbolic validations for the main proofs contained in the work.

• Symbolic_Validations Symbolically verify the different proofs presented in the work (meant to be executed in 6 parts--one for each part of the three proofs presented).

(2) Numerical validations (using the Performance Estimation Toolbox PESTO) of the results of the last section (Mixed performance measures and sublinear convergence rates).

• PESTO_DistanceToFunctionValues Numerically verifies the conjectured tight worst-case bound (for given values of the parameters N, mu and L) on the final objective function accuracy, from a bounded initial distance to optimality.
• PESTO_DistanceToGradient Numerically verifies the conjectured tight worst-case bound (for given values of the parameters N, mu and L) on the final gradient norm, from a bounded initial distance to optimality.
• PESTO_FunctionValuesToDistance Numerically verifies the conjectured tight worst-case bound (for given values of the parameters N, mu and L) on the final distance to optimality, from a bounded initial objective function accuracy.
• PESTO_FunctionValuesToGradient Numerically verifies the conjectured tight worst-case bound (for given values of the parameters N, mu and L) on the final gradient norm, from a bounded initial objective function accuracy.
• PESTO_GradientToDistance Numerically verifies the conjectured tight worst-case bound (for given values of the parameters N, mu and L) on the final distance to optimality, from a bounded initial gradient norm.
• PESTO_GradientToFunctionValues Numerically verifies the conjectured tight worst-case bound (for given values of the parameters N, mu and L) on the final objective function accuracy, from a bounded initial gradient norm.

Authors

• Adrien Taylor
• Julien Hendrickx
• François Glineur