有些迭代算法的失败,很容易看出来:数值越来越大,最后溢出。但还有一种更不显眼的情况——迭代始终停留在一个有限区域里,不断经过同一组状态,却始终没有走向问题的解。
三块 ADMM 的这个项目,关心的就是后一种情形。
问题从哪里来
ADMM 是一种把优化问题拆开、交替求解的方法。把一个问题分成更多块,常常让每一步更容易计算,但也会改变整个迭代的性质。一个看起来很自然的推广,未必继承原方法的收敛保证。
这里的具体问题是:当第三个约束块恰好是单位阵时,未经修正的直接三块 ADMM,是否就能得到相应的收敛保证?
公开仓库给出了两个固定的凸二次规划实例。它们都具有唯一的 KKT 点,但直接三块 ADMM 可以产生有界、非 KKT 的周期轨道。这说明,第三块是单位阵这一结构,本身不足以排除这样的失败。
两个周期,两个不同的结论
第一个实例给出一条最小周期为 66 的轨道。从一个特定的初始状态出发,迭代经过 66 步精确返回原状态,然后继续重复。
第二个实例的最小周期为 23。除了周期本身,项目还给出了一个局部的吸引性结论:在相应缩减状态空间的一个开放不变集合内,初始状态会按周期相位趋近这条非 KKT 轨道。
这两个结论回答的问题不完全相同。前者说明某个指定初始化会一直循环;后者进一步描述了一个固定问题上,一部分邻近初始化的行为。它们都不能被扩大为所有初始化、所有问题数据的结论。
从“看起来在循环”到精确验证
数值实验可以帮助找到候选轨道,但有限精度下看起来重合的状态,还不是精确的周期证明。
从现象走向明确结论,需要回答几个具体问题:
- 每一步是否确实遵循原来的算法更新?
- 投影或分支选择所需的条件是否全部成立?
- 走完一个周期后,状态是否精确回到起点?
- 这个周期是否还能缩短?
- 周期轨道上的状态为何不是 KKT 点?
公开项目为这些问题提供了可重新计算的精确验证材料。周期 66 的实例还有不同实现之间的交叉检查;周期 23 的实例使用有理数数据,并给出了局部不变集合的验证。
AI 辅助发现之后,还需要什么
这个项目也记录了 AI 辅助寻找反例的过程。这里有一个很值得保留的区分:找到候选、解释现象、验证结论,是相互联系但不同的工作。
计算能指出值得追踪的方向,数学分析则要说明结论在什么条件下成立。一个完整的研究记录,应当让读者知道哪部分是探索,哪部分已有明确论证。
对这个问题来说,最有价值的产物不是一张“似乎不收敛”的曲线,而是一个可清楚陈述、可逐项检查的具体反例。
继续阅读
本文是根据公开仓库整理的项目导读,不包含新的证明。
阅读时可以先看仓库中的结论范围,再选择数学论证或验证代码作为入口。