I am making some code available here so that that colleagues and researchers can reproduce and build upon my work. If you find this code useful, discover bugs, or have any other comments, I would be happy to hear your feedback!

Disclaimer: the code I’m providing is not optimized. I prioritized legibility and accessibility in these public versions because it is more useful to those not familiar with my work.

 

Optimization algorithms as robust control

This code reproduces some figures from two papers on using IQC techniques to analyze exponential convergence properties of optimization algorithms or other interconnected systems. The code is written in Matlab, and you must have a working installation of CVX. Instructions:

• Download the code (version 3, updated 10/26/2015) and extract all files to the same location.
• main_iqcopt.m finds upper bounds for the worst-case convergence rate of various iterative optimization algorithms under the assumption that the function being optimized is strongly convex with Lipschitz gradients. To evaluate different algorithms, change the “algo” variable. Here are the results for each algorithm (~2 min. runtime per algorithm).
  1. Gradient method (conservative tuning)
  2. Gradient method (optimal tuning for quadratics)
  3. Nesterov’s method (standard tuning)
  4. Nesterov’s method (optimal tuning for quadratics)
  5. Heavy-ball method (optimal tuning for quadratics)
  Although the Heavy-ball method has the best performance when tuned for quadratics, this algorithm fails to converge in the worst case when applied to strongly convex functions! These results appear in the paper with A. Packard and B. Recht titled: “Analysis and design of optimization algorithms via integral quadratic constraints”.
• main_saturation_tight.m finds upper bounds for the worst-case exponential convergence rate of a discrete-time linear time-invariant system in feedback with a saturating nonlinearity. Different IQCs used provide different bounds, and we can compare these bounds to the exact worst-case rate computed analytically. Here is the result, a plot comparing different rates and showing sample trajectories. A tight bound is achieved using a small number of IQCs. Runtime is about 8 minutes.
• main_saturation_loose.m is similar to the simulation above, but with a different linear time-invariant system. This time, using more IQCs leads to better bounds, but there is still a gap when comparing to the exact (analytic) worst-case rate. Here is the result, a plot comparing different rates and showing sample trajectories. These results appear in the paper with R. Boczar and B. Recht titled: “Exponential convergence bounds using integral quadratic constraints”.