Last-iterate Convergence of ADMM on Multi-affine Quadratic Equality Constrained Problem

本文证明了交替方向乘子法（ADMM）在应用于多仿射二次等式约束非凸优化问题时具有迭代收敛性，并在非凸程度受限时实现了线性收敛速率，同时通过机器人运动学实例验证了理论结果。

要点

这篇论文主要研究了一个数学难题：如何让一种叫"ADMM"的算法，在处理一类非常棘手的“非线性”问题时，不仅能找到答案，还能保证“跑得快”且“跑得稳”。

为了让你轻松理解，我们可以把这个问题想象成指挥一个复杂的机器人团队去跳舞。

1. 核心挑战：一群“爱捣乱”的舞者（非凸问题）

想象你有一个机器人舞团（比如波士顿动力的那种），你要指挥它们走出完美的舞步（生成轨迹）。

• 目标：让它们动作优美、省力（这是“目标函数”）。
• 规则：它们必须遵守物理定律，比如脚不能穿墙、手不能穿过身体、重心不能倒（这是“约束条件”）。

在大多数情况下，这些物理规则是线性的（像走直线），很好算。但在机器人接触地面（比如跳跃、抓东西）的瞬间，规则变得非常复杂且非线性。

• 比喻：这就好比舞者们不仅要按节拍跳舞，还要在跳舞时互相“推搡”或“借力”。这种“推搡”的关系是**多仿射（Multi-affine）**的——意思是，如果你固定住其他所有人的动作，只看某一个人，他的动作看起来是简单的直线；但一旦所有人一起动，关系就变得像一团乱麻，非常难解。

以前的算法在处理这种“乱麻”时，要么算不出来，要么算得很慢，或者根本不知道什么时候能停下来。

2. 主角登场：ADMM（聪明的协调员）

ADMM（交替方向乘子法）就像一位超级协调员。

• 它的工作方式：它不会试图一次性解决所有人的复杂关系。相反，它采用“逐个击破”的策略：
  1. 先让舞者 A 动，其他人不动，A 调整到最佳位置。
  2. 再让舞者 B 动，其他人（包括刚调整好的 A）不动，B 调整。
  3. 以此类推，一轮一轮地循环。
• 优点：这种方法把一个大难题拆成了很多小问题，每个小问题都很容易解。

3. 这篇论文的突破：不仅“能解”，还能“快解”

以前的研究知道 ADMM 能解这类问题，但有两个大疑问：

1. 收敛性：它真的能最终停下来找到一个好答案吗？（就像问：这个协调员会不会永远在原地打转，永远找不到完美的队形？）
2. 速度：它收敛得有多快？是像蜗牛爬（线性收敛慢），还是像火箭飞（线性收敛快）？

这篇论文给出了两个令人兴奋的结论：

结论一：只要条件温和，它一定能停下来（收敛性保证）

作者证明了，只要机器人的物理规则不是“完全疯狂”的（满足一些温和的假设），这个协调员（ADMM）最终一定能找到完美的队形，而且这个队形是稳定的（不会一会儿变这样，一会儿变那样）。

结论二：如果“乱麻”不太乱，它跑得飞快（线性收敛）

这是最精彩的部分。作者发现，虽然规则是非线性的（像乱麻），但如果这种“非线性”的程度不太大（比如机器人的动作幅度没那么大，或者时间步长很短），那么 ADMM 的收敛速度依然是线性的。

• 通俗比喻：想象你在解一个复杂的绳结。如果绳结只是稍微有点乱，你拉几下就能解开（线性收敛，速度很快）。如果绳结乱成一团死结，你可能要解很久（次线性收敛，速度慢）。
• 论文发现：在机器人走路或抓东西的场景中，虽然物理规则是非线性的，但这种“乱”的程度通常很小（就像绳结只是稍微有点乱）。因此，ADMM 依然能像火箭一样快速找到答案。

4. 实际效果：机器人真的变聪明了

作者不仅在理论上证明了这一点，还做了实验：

• 场景：让机器人在二维平面上走路，或者让四足机器人跳跃。
• 结果：
  • 当时间步长（把动作切分的颗粒度）很细时，非线性影响变小，ADMM 确实展现出了直线下降的误差曲线（意味着速度极快，很快就能算出完美动作）。
  • 即使初始位置很糟糕（机器人一开始站得歪歪扭扭），ADMM 也能迅速调整回来。
  • 对比其他现有的算法，他们的 ADMM 在处理这种复杂的非线性接触问题时，表现更稳定、更快速。

总结

这篇论文就像给机器人控制领域发了一张“通行证”：

“别怕那些复杂的非线性物理规则（比如接触、碰撞），只要用 ADMM 这个协调员，并且控制好‘乱度’，我们不仅能保证机器人能找到路，还能保证它算得飞快，足以在毫秒级的时间内做出反应。”

这对于让机器人从“实验室里的玩具”变成“能真正帮人类干活的助手”（比如快速奔跑、灵活抓取）至关重要，因为实时控制需要算法在极短的时间内给出完美的指令。

技术摘要

1. 研究背景与问题定义 (Problem)

核心问题：
本文研究一类多仿射二次等式约束优化问题（Multi-affine Quadratic Equality Constrained Problems）。这类问题在机器人（如足式机器人和机械臂的轨迹生成）、矩阵分解以及神经网络训练中广泛存在。

数学形式：
问题形式化如下（公式 1）：
$$\min_{x,z} F(x) + \phi(z)$$
$$\text{s.t. } A(x) + Qz = 0$$

其中：

• $x = (x_1, \dots, x_n)^T$ 被划分为 $n$ 个块。
• $A(x)$ 是一个多仿射二次算子。对于每个约束分量 $i$，形式为 $(A(x))_i = \frac{1}{2}x^T C_i x + d_i^T x + e_i$。关键性质是：当固定除一个块 $x_j$ 以外的所有变量时，$A(x)$ 关于 $x_j$ 是仿射的（即多仿射性）。
• $F(x)$ 和 $\phi(z)$ 是目标函数，通常包含强凸部分和指示函数（用于处理凸集约束）。
• $Q$ 是线性约束矩阵。

挑战：
尽管这类问题在固定其他变量时表现出凸性（块凸性），但整体是非凸的。传统的交替方向乘子法（ADMM）在非线性约束下的收敛性分析非常困难，尤其是最后迭代收敛（Last-iterate convergence）和收敛速率的保证。现有的工作要么假设约束是线性的，要么仅保证平均迭代收敛，或者需要极强的假设（如 KL 性质下的特定求解器）。

2. 方法论 (Methodology)

作者提出并分析了**增广拉格朗日 ADMM（Augmented Lagrangian ADMM）**算法（算法 1）在该类问题上的表现。

算法流程：

1. 块坐标更新： 依次更新每个变量块 $x_i$ 和 $z$，最小化增广拉格朗日函数 $L(x, z, w)$。由于多仿射性质，当其他块固定时，子问题是线性约束下的强凸问题，易于求解。
2. 对偶变量更新： 根据约束违反程度更新拉格朗日乘子 $w$。

理论分析框架：

• 假设条件：
  • $F(x)$ 可分解为强凸光滑函数 $f(x)$ 和块可分离的指示函数。
  • $\phi(z)$ 是强凸且光滑的。
  • 矩阵 $Q$ 行满秩（比现有文献中要求的列满秩更弱）。
  • 目标函数满足子解析性（Subanalytic），从而满足 $\alpha$-PL 性质（Kurdyka-Łojasiewicz 性质的一种形式）。
• 收敛性证明策略：
  1. 证明增广拉格朗日函数序列是单调递减的。
  2. 证明迭代序列有界且存在极限点。
  3. 利用 $\alpha$-PL 性质建立收敛速率。
  4. 通过分析非凸项系数 $\|C\|$ 与线性项系数 $Q$ 之间的关系，推导线性收敛的充分条件。

3. 主要贡献 (Key Contributions)

1. 最后迭代收敛性证明：
   在温和假设下，证明了 ADMM 应用于多仿射二次等式约束问题时，其迭代序列**最后迭代（Last-iterate）**收敛到增广拉格朗日函数的驻点（KKT 点），且该驻点具有类似纳什均衡的性质（即固定其他块时，当前块是最优的）。

2. 线性收敛速率的充分条件：
   这是本文的核心突破。作者证明了：

   • 如果非凸项的“程度”（由矩阵 $C_i$ 的范数 $\|C\|$ 衡量）相对于线性项（由 $Q$ 决定）足够小，ADMM 具有线性收敛速率（$O(c^{-k})$）。
   • 具体条件（公式 4）表明，当 $\|C\| \in O(\|Q\|^{-1} \cdot \dots)$ 时，线性收敛成立。
   • 这解释了为什么在非线性项较弱的情况下，ADMM 依然能保持线性收敛，填补了从纯线性约束到非线性约束的理论空白。

3. 非光滑约束下的线性收敛：
   针对指示函数定义在多面体（Polyhedral）上的情况（即 $x_i$ 属于多面体集合），即使拉格朗日函数在极限点不可二次微分，作者也证明了线性收敛性依然成立。

4. 近似 ADMM 的扩展：
   讨论了子问题求解不精确（Inexact ADMM）的情况，证明了在误差满足一定衰减条件时，上述收敛结果依然有效。

4. 实验结果 (Results)

理论验证实验：

• 非线性影响测试： 构造了一个包含 $x_1x_2$ 项的简单问题。实验表明，随着线性项系数 $q$ 的增大（即非线性相对减弱），收敛速率从次线性过渡到线性，验证了理论中关于 $\|C\|$ 与 $Q$ 比例关系的结论。
• 对比实验： 与 PADMM、IPDS-ADMM 和 IADMM 等现有方法对比。在非线性约束场景下，本文提出的 ADMM 表现更优且收敛更快；在线性约束场景下表现相当。

机器人应用实验：

• 2D 步态规划： 将问题转化为多仿射约束形式。实验显示，随着时间离散化步长 $\Delta t$ 的减小，非线性项（与 $(\Delta t)^3$ 成正比）迅速衰减，ADMM 表现出稳定的线性收敛。
• 动态运动（人形与四足机器人）： 将理论应用于实际的高维机器人轨迹规划（跳跃、奔跑）。
  • 结果显示，ADMM 能够高效求解包含接触动力学约束的轨迹优化问题。
  • 不同离散化步长下的约束违反值（Constraint Violation）随迭代次数呈指数下降，验证了线性收敛理论。
  • 计算时间随 $\Delta t$ 减小而增加，但在合理范围内，证明了算法的实用性。

5. 意义与影响 (Significance)

1. 理论突破： 解决了非凸优化中 ADMM 收敛性分析的一个长期难题。以往工作多关注平均迭代收敛或需要强假设，本文首次为多仿射二次约束下的最后迭代线性收敛提供了严格的理论保证。
2. 机器人领域的直接应用： 为机器人接触规划（Contact Planning）和动态轨迹生成提供了强有力的数学工具。接触动力学中的交叉项（如角动量中的 $r \times f$）天然形成多仿射结构，本文理论直接解释了为何 ADMM 在该领域如此有效。
3. 指导算法设计： 提出的收敛条件（非凸系数需足够小）为实际工程应用提供了指导：在轨迹规划中，可以通过调整时间步长或问题参数来确保算法快速收敛。
4. 通用性： 虽然主要应用于机器人，但该理论框架同样适用于矩阵分解、神经网络训练等其他涉及多仿射约束的领域。

总结：
这篇论文通过深入分析多仿射二次约束问题的结构特性，证明了 ADMM 在该类非凸问题上的强大收敛性能，特别是确立了在非线性程度可控时的线性收敛速率。这不仅完善了优化理论，也为机器人动态控制中的实时轨迹规划提供了坚实的理论支撑。