Computer-aided Lyapunov analyses in optimization

This technical blog post explains how semidefinite programming can be used to verify and search for Lyapunov functions in optimization. It develops the SDP formulations explicitly for two examples in smooth and strongly convex optimization: a gradient method with relatively inexact gradients, with a fixed Lyapunov function, and a gradient method with memory, for which a Lyapunov function is sought within a chosen family. The post uses interpolation inequalities and shows how numerical SDP certificates can lead to exact proofs of tight contraction guarantees. Interactive figures and expandable derivations accompany the discussion. Blog URL: https://manuupadhyaya.github.io/blog/computer-aided-lyapunov-analyses-in-optimization/