形式陈述
在有限维实空间 R n 中,设 f , g 是 proper、闭凸函数:允许取 + ∞ ,但不恒为 + ∞ ,也不取 − ∞ 。考虑将同一个变量复制成两份的问题
min x , z f ( x ) + g ( z ) , x − z = 0. 约束使它与 min v { f ( v ) + g ( v ) } 等价。本页研究这一恒等一致性约束下的 ADMM,假设存在 ( v ∗ , y ∗ ) 满足
− y ∗ ∈ ∂ f ( v ∗ ) , y ∗ ∈ ∂ g ( v ∗ ) . 这里 ∂ 是凸次微分 理路 次梯度与次微分 Subgradient · Subdifferential 以全局仿射下界刻画凸函数在不可微点的支撑斜率集合。 。这两个条件给出原问题的最优点和拆分问题的乘子证书;在拉格朗日对偶 理路 拉格朗日对偶 Lagrange duality 通过拉格朗日函数构造原问题下界的对偶问题,并研究弱对偶、强对偶与最优性条件。 语言中,( v ∗ , v ∗ , y ∗ ) 是未增广拉格朗日函数的鞍点。它比单独假设原问题有最小点更强,保证两部分在该点能够以相反的次梯度平衡。
固定 ρ > 0 ,增广拉格朗日函数为
L ρ ( x , z , y ) = f ( x ) + g ( z ) + ⟨ y , x − z ⟩ + ρ 2 ‖ x − z ‖ 2 . 任取初值 z 0 , u 0 ,令 y 0 = ρ u 0 。ADMM 每轮依次精确最小化 x 、精确最小化 z ,再更新乘子:
x k + 1 = prox f / ρ ( z k − u k ) , z k + 1 = prox g / ρ ( x k + 1 + u k ) , u k + 1 = u k + x k + 1 − z k + 1 , y k + 1 = ρ u k + 1 . 按近端算子 理路 近端算子 Proximal operator · Proximity operator 在降低凸函数值与保持靠近输入点之间取得精确平衡的单值算子。 的约定,prox f / ρ ( a ) 最小化 f ( x ) + ( ρ / 2 ) ‖ x − a ‖ 2 。闭凸性与二次项保证每个子问题有唯一解。上述鞍点假设下,整个序列 ( x k , z k , y k ) 收敛到某个 ( v ¯ , v ¯ , y ¯ ) ,后者也满足鞍点条件;下文给出这一有限维结论的完整证明。
直觉
拆分的好处是分别利用 f 和 g 的计算结构。平方损失可能适合解线性系统,绝对值惩罚则适合逐坐标软阈值;复制变量后,两种操作可以各做一次,再逐渐让两份答案一致。
更新式可以直接从配方得到。记 u = y / ρ ,则
⟨ y , x − z ⟩ + ρ 2 ‖ x − z ‖ 2 = ρ 2 ‖ x − z + u ‖ 2 − ρ 2 ‖ u ‖ 2 . 固定 z k , u k 时,第一份二次中心是 z k − u k ;固定刚得到的 x k + 1 , u k 时,第二份中心变为 x k + 1 + u k 。第二步必须使用第一步的新结果,所以这是一轮交替最小化,并没有联合求出整个增广子问题的最小点。增广 Lagrange 乘子法 理路 增广 Lagrange 乘子法 Augmented Lagrangian method · Method of multipliers 联合最小化增广目标后累加约束违背,借对偶近端机制在固定罚参数下改善可行性,并分别检查内层与外层误差。 在每轮联合最小化后才更新乘子;它的精确对偶近端关系不能直接套在一次 ADMM 扫掠上。
乘子记录的是历轮未消除的一致性误差:
u k + 1 = u 0 + ∑ j = 1 k + 1 ( x j − z j ) . 当两份变量长期朝同一方向偏离时,这份累积会改变后续子问题的中心。固定的二次惩罚配合乘子更新,就能驱动约束误差趋零,无需仅靠不断增大惩罚系数。
两个残差分别检查什么
定义原始残差、相邻 z 位移和对偶残差
r k + 1 = x k + 1 − z k + 1 , d k + 1 = z k + 1 − z k , s k + 1 = − ρ d k + 1 . 负号对应这里的约束写法 x − z = 0 。从两个子问题分别得到
0 ∈ ∂ f ( x k + 1 ) + y k + ρ ( x k + 1 − z k ) , 0 ∈ ∂ g ( z k + 1 ) − y k − ρ ( x k + 1 − z k + 1 ) . 代入 y k + 1 = y k + ρ r k + 1 ,便有精确关系
− y k + 1 − ρ d k + 1 ∈ ∂ f ( x k + 1 ) , y k + 1 ∈ ∂ g ( z k + 1 ) . 因此 z 的驻点条件在每轮结束时已经满足;s k + 1 是集合 ∂ f ( x k + 1 ) + y k + 1 中一个明确的元素,衡量 x 驻点条件的偏差;r k + 1 则衡量两份变量是否可行地一致。二者同时为零时就得到完整鞍点证书。二者仅仅很小时,首先得到的是近似最优性条件;若要换算成目标值或变量距离的误差,还需要额外的误差界或对偶证书。
例子与边界
同一个耦合 Lasso 的四轮精确计算
沿用Lasso 的最优性与对偶间隙 理路 Lasso 的最优性与对偶间隙 Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate 从残差相关性核验 Lasso 的零与非零坐标,并用可行对偶值认证剩余优化误差。 中的数据:
A = ( 1 1 1 0 0 1 ) , b = ( 3 / 2 3 / 2 0 ) , f ( x ) = 1 2 ‖ A x − b ‖ 2 , g ( z ) = ‖ z ‖ 1 . 记 Q = A T A = ( 2 1 1 2 ) 、c = A T b = ( 3 , 3 / 2 ) T ,取 ρ = 1 、z 0 = u 0 = 0 。第一步的最优性方程和第二步的软阈值为
( Q + I ) x k + 1 = c + z k − u k , ( Q + I ) − 1 = 1 8 ( 3 − 1 − 1 3 ) , z k + 1 = S 1 ( x k + 1 + u k ) , 其中 S 1 对各坐标施加阈值 1 。逆矩阵的非对角项保留了损失的耦合;可分的是后面的惩罚子问题。
第一轮解线性系统得 x 1 = ( 15 / 16 , 3 / 16 ) ,两坐标都落在阈值区间内,于是 z 1 = 0 、u 1 = x 1 。第二轮的右端为 ( 33 / 16 , 21 / 16 ) ,故 x 2 = ( 39 / 64 , 15 / 64 ) ;加上旧乘子后,阈值输入为 ( 99 / 64 , 27 / 64 ) ,所以 z 2 = ( 35 / 64 , 0 ) 。继续同样的有理数运算得到:
k
x k
z k
u k
r k
s k
1
( 15 / 16 , 3 / 16 )
( 0 , 0 )
( 15 / 16 , 3 / 16 )
( 15 / 16 , 3 / 16 )
( 0 , 0 )
2
( 39 / 64 , 15 / 64 )
( 35 / 64 , 0 )
( 1 , 27 / 64 )
( 1 / 16 , 15 / 64 )
( − 35 / 64 , 0 )
3
( 105 / 128 , 11 / 128 )
( 105 / 128 , 0 )
( 1 , 65 / 128 )
( 0 , 11 / 128 )
( − 35 / 128 , 0 )
4
( 239 / 256 , 5 / 256 )
( 239 / 256 , 0 )
( 1 , 135 / 256 )
( 0 , 5 / 256 )
( − 29 / 256 , 0 )
第一轮已经有 s 1 = 0 ,但 r 1 ≠ 0 ,两份变量尚未一致。只看对偶残差就会在这里错误停止。z k 的第二坐标从一开始就是零,x k 的第二坐标则逐渐减小;中间变量分别承担各自子问题的结构,无需每轮拥有相同的稀疏模式。
反过来,原始残差为零也未必已经最优。取一维 f ( x ) = x 2 / 2 、g ( z ) = 0 、ρ = 1 ,从 z 0 = 1 , u 0 = 0 开始,第一轮得到 x 1 = z 1 = 1 / 2 、u 1 = 0 。此时 r 1 = 0 ,但 s 1 = 1 / 2 ,共同变量还没有到最小点零。
用证书确定极限
四行迭代可以展示算法如何运行,但极限应由最优性条件确定。取
v ∗ = ( 1 , 0 ) , y ∗ = ( 1 , 1 / 2 ) . 直接计算 Q v ∗ − c = ( − 1 , − 1 / 2 ) = − y ∗ 。同时,v 1 ∗ > 0 要求绝对值次梯度的第一坐标为 1 ,v 2 ∗ = 0 允许第二坐标取 [ − 1 , 1 ] 中任意值,所以 y ∗ ∈ ∂ ‖ v ∗ ‖ 1 。这正是本页的鞍点假设;而 Q 的特征值为 1 , 3 ,平方损失严格凸,故原变量的最优点唯一。
原回归残差为 b − A v ∗ = ( 1 / 2 , 1 / 2 , 0 ) ,目标最优值为
P ∗ = f ( v ∗ ) + g ( v ∗ ) = 1 2 ( 1 / 4 + 1 / 4 ) + 1 = 5 / 4. 下文的收敛证明于是保证 x k , z k → ( 1 , 0 ) 。若在有限轮结束时认证目标误差,可以把 z k 作为原问题候选,计算 P ( z k ) = f ( z k ) + g ( z k ) ,再使用上述 Lasso 条目的可行对偶间隙。f ( x k ) + g ( z k ) 使用了两份尚未一致的变量,不能直接当成某个原问题可行点的目标值。
推论与应用
从单调性到 Fejér 不等式
证明只需凸次微分的单调性 理路 单调算子与极大单调性 Monotone operator · Maximal monotone operator · 极大单调算子 用图上的内积不等式统一凸次微分与旋转关系,并以极大性保证稳定隐式步对每个输入都有唯一解。 :a ∈ ∂ h ( p ) 、b ∈ ∂ h ( q ) 蕴含 ⟨ p − q , a − b ⟩ ≥ 0 。固定任意鞍点对 ( v ∗ , y ∗ ) ,在一轮中简记 x = x k + 1 、z = z k + 1 、y = y k + 1 、r = r k + 1 、d = d k + 1 。对两个精确次梯度关系分别应用单调性,得到
⟨ x − v ∗ , − ( y − y ∗ ) − ρ d ⟩ ≥ 0 , ⟨ z − v ∗ , y − y ∗ ⟩ ≥ 0. 相加并利用 x − z = r ,得到控制原始与对偶误差的关键式
⟨ r , y − y ∗ ⟩ + ρ ⟨ x − v ∗ , d ⟩ ≤ 0. 定义乘积空间中的加权平方距离
E k = 1 ρ ‖ y k − y ∗ ‖ 2 + ρ ‖ z k − v ∗ ‖ 2 . 因为 y k = y − ρ r 、z k = z − d ,直接展开平方有
E k + 1 − E k = 2 ⟨ r , y − y ∗ ⟩ − ρ ‖ r ‖ 2 + 2 ρ ⟨ d , z − v ∗ ⟩ − ρ ‖ d ‖ 2 ≤ − ρ ‖ r ‖ 2 − ρ ‖ d ‖ 2 − 2 ρ ⟨ r , d ⟩ . 这里尚有一个交叉项。当 k ≥ 1 时,上一轮的 z 更新已保证 y k ∈ ∂ g ( z k ) ,本轮又有 y ∈ ∂ g ( z ) ,故单调性给出
0 ≤ ⟨ z − z k , y − y k ⟩ = ρ ⟨ d , r ⟩ . 于是得到所需的 Fejér 不等式:
E k + 1 ≤ E k − ρ ( ‖ r k + 1 ‖ 2 + ‖ d k + 1 ‖ 2 ) , k ≥ 1. 任意初值未必满足 y 0 ∈ ∂ g ( z 0 ) ,所以证明从第一轮结束后开始。若初值恰好满足该关系,不等式也适用于 k = 0 ;任意初值只多出有限的一轮,不影响以下结论。
为什么整个点序列收敛
从 k = 1 到 N 求和,并用 E N + 1 ≥ 0 ,得到
ρ ∑ k = 1 N ( ‖ r k + 1 ‖ 2 + ‖ d k + 1 ‖ 2 ) ≤ E 1 . 因此 r k → 0 、d k → 0 ,从而 s k → 0 。同时 E k ≤ E 1 保证 ( z k , y k ) 有界;x k = z k + r k 也有界。在有限维空间中可以取子列 ( z k j , y k j ) → ( v ¯ , y ¯ ) ,于是 x k j → v ¯ 。
闭凸函数的次微分图在有限维中闭合。这一点也能从 prox 的连续性看出:a j ∈ ∂ h ( p j ) 等价于 p j = prox h ( p j + a j ) ,若 ( p j , a j ) → ( p , a ) ,取极限就有 p = prox h ( p + a ) ,即 a ∈ ∂ h ( p ) 。现在对迭代中的两个关系
− y k j − ρ d k j ∈ ∂ f ( x k j ) , y k j ∈ ∂ g ( z k j ) 取极限,得到 − y ¯ ∈ ∂ f ( v ¯ ) 、y ¯ ∈ ∂ g ( v ¯ ) 。所以聚点本身就是鞍点,而不只是满足一致性约束的点。
最后,把 Fejér 不等式中的固定鞍点换成刚找到的 ( v ¯ , y ¯ ) 。相应的距离
E ¯ k = 1 ρ ‖ y k − y ¯ ‖ 2 + ρ ‖ z k − v ¯ ‖ 2 从 k = 1 起非增,又沿 k j 趋于零,因此整个 E ¯ k 都趋于零。这证明 z k → v ¯ 、y k → y ¯ ;再由 r k → 0 得 x k → v ¯ 。这里不需要最优点唯一,也没有用到函数在有效域边界的连续性。
计算结构与适用范围
对一般 Lasso,固定 ρ 时的矩阵 A T A + ρ I 在所有轮次中相同,可以预先分解后重复求解。若直接形成稠密的 n × n 系统,分解需要 O ( n 3 ) ,已有分解后的每轮求解为 O ( n 2 ) ,软阈值和乘子更新为 O ( n ) ;形成矩阵与计算 A T b 另有一次成本。与近端梯度法 理路 近端梯度法 Proximal gradient method 对复合目标的光滑项取显式梯度步、对非光滑凸项取隐式近端步的算法。 的矩阵向量乘法相比,是否划算取决于维度、稀疏性和能否复用分解。
本页证明依赖恒等约束 x − z = 0 、固定 ρ 、精确子问题和鞍点存在。一般形式 A x + B z = c 会引入矩阵核与子问题可解性等问题,不能由这里的点收敛论证直接推出所有原变量都收敛。非凸项、近似内层求解或调整惩罚参数也需要各自的假设与分析;对当前模型,两次 prox、两种残差和上述加权距离已经构成一条完整的算法与收敛链条。
另一个双预解方法是Douglas–Rachford分裂 理路 Douglas–Rachford 分裂 Douglas–Rachford splitting · Douglas Rachford method · DR splitting 分别计算两个极大单调算子的预解,通过反射平均恢复和算子的零点,证明状态与影子点的收敛,并用周期反例说明平均的作用。 ,它用反射平均更新内部状态,再输出两份趋于一致的影子。特定凸对偶重写可连接两类算法,但变量与缩放需要明确推导;不能只因都有两次prox,就将本页任意ADMM迭代与任意原问题上的Douglas–Rachford逐点等同。
参考资料