A Tutorial on a Lyapunov-Based Approach to the Analysis of Iterative Optimization Algorithms
A Tutorial on a Lyapunov-Based Approach to the Analysis of Iterative Optimization Algorithms
复制标题
DOI：
10.1109/cdc49753.2023.10384074
复制
发表时间：
2023-09
期刊：
影响因子：
--
通讯作者：
Bryan Van Scoy;Laurent Lessard
中科院分区：
文献类型：
--
作者：
Bryan Van Scoy;Laurent Lessard
基于迭代梯度的优化算法被广泛用于解决困难或大规模的优化问题。有许多算法可供选择，例如梯度下降及其加速变体，例如 Polyak 的重球方法或 Nesterov 的快速梯度方法。长期以来，人们一直认为迭代算法可以被视为动态系统，最近又被视为鲁棒控制器。这里，动力学中的“不确定性”是被优化函数的梯度。因此，可以使用鲁棒控制理论中的工具（例如积分二次约束 (IQC)）来分析最坏情况或平均情况性能。在本教程论文中，我们展示了如何使用另一种基于李雅普诺夫的方法进行此类分析。这种方法恢复了与 IQC 相同的性能范围，但具有构建 Lyapunov 函数的额外好处。
Iterative gradient-based optimization algorithms are widely used to solve difficult or large-scale optimization problems. There are many algorithms to choose from, such as gradient descent and its accelerated variants such as Polyak's Heavy Ball method or Nesterov's Fast Gradient method. It has long been observed that iterative algorithms can be viewed as dynamical systems, and more recently, as robust controllers. Here, the “uncertainty” in the dynamics is the gradient of the function being optimized. Therefore, worst-case or average-case performance can be analyzed using tools from robust control theory, such as integral quadratic constraints (IQCs). In this tutorial paper, we show how such an analysis can be carried out using an alternative Lyapunov-based approach. This approach recovers the same performance bounds as with IQCs, but with the added benefit of constructing a Lyapunov function.