Analysis of the Heavy-ball Algorithm using Integral Quadratic Constraints
Analysis of the Heavy-ball Algorithm using Integral Quadratic Constraints
复制标题
使用积分二次约束的重球算法分析
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
P. Seiler
中科院分区：
文献类型：
--
作者：
Apurva Badithela;P. Seiler
本文分析了用于优化一类连续可微函数的重球算法的收敛速度。在二次函数子类上调整重球以达到最佳收敛速度进行了分析。我们回顾了最近用积分二次约束(IQC)来刻画优化算法收敛速度上界的工作。这产生了线性矩阵不等式(LMI)条件，该条件通常通过数值求解来获得收敛速度界。我们使用特定的“加权1”IQC构造了这种LMI条件的解析解。我们还构造了一个特定的目标函数，使重球算法进入极限环。这些结果表明，对于调谐重球的分析，IQC条件是紧的，即它产生了区分算法全局收敛和非全局收敛的精确条件比。
In this paper, we analyze the convergence rate of the Heavy-ball algorithm applied to optimize a class of continuously differentiable functions. The analysis is performed with the Heavy-ball tuned to achieve the best convergence rate on the sub-class of quadratic functions. We review recent work to characterize convergence rate upper bounds for optimization algorithms using integral quadratic constraints (IQC). This yields a linear matrix inequality (LMI) condition which is typically solved numerically to obtain convergence rate bounds. We construct an analytical solution for this LMI condition using a specific “weighted off-by-one” IQC. We also construct a specific objective function such that the Heavy-ball algorithm enters a limit cycle. These results demonstrate that IQC condition is tight for the analysis of the tuned Heavy-ball, i.e. it yields the exact condition ratio that separates global convergence from non-global convergence for the algorithm.