论文标题
在乘数的交替方向方法的双步长上
On the dual step length of the alternating direction method of multipliers
论文作者
论文摘要
乘数的交替方向方法（ADMM）是一种最广泛使用的优化方案，用于求解线性约束的可分离凸优化问题。当双步长度小于黄金比率时，可以保证ADMM的收敛性，而大量的数值证据表明，甚至更大的双步长通常会加速融合。还已经证明，在某些特殊情况下，双步长可以扩大到不到2个，即，目标函数中的可分离功能之一是线性的，或者两者都是二次函数以及一些其他假设。但是，尚不清楚在一般凸环境中是否可以超过黄金比率。在本文中，绩效估计框架用于分析ADMM的收敛性，并在数值和符号计算的辅助下，构建了一个反示例，这表明随着二步长度超过黄金比率，传统措施可能会失去单调性，从而排除了在此常规分析框架内违反黄金比率的可能性。
The alternating direction method of multipliers (ADMM) is a most widely used optimization scheme for solving linearly constrained separable convex optimization problems. The convergence of the ADMM can be guaranteed when the dual step length is less than the golden ratio, while plenty of numerical evidence suggests that even larger dual step length often accelerates the convergence. It has also been proved that the dual step length can be enlarged to less than 2 in some special cases, namely, one of the separable functions in the objective function is linear, or both are quadratic plus some additional assumptions. However, it remains unclear whether the golden ratio can be exceeded in the general convex setting. In this paper, the performance estimation framework is used to analyze the convergence of the ADMM, and assisted by numerical and symbolic computations, a counter example is constructed, which indicates that the conventional measure may lose monotonicity as the dual step length exceeds the golden ratio, ruling out the possibility of breaking the golden ratio within this conventional analytic framework.
