第51章

双上升法

本章介绍了目前已知的解决等式约束优化问题的最佳方法之一。实际上，这种方法还可以处理更一般的约束，即凸集的成员关系。它也可以用来解决套索最小化问题。为了更好地理解这种方法，称为乘法交替方向法，简称为ADMM，我们回顾了ADMM的两个前兆：双上升法和乘法方法。

ADMM不是一种新方法。事实上，它是在20世纪70年代发展起来的，由于它非常适合于分布（凸）优化，因此在处理非常大的数据的统计和机器学习问题上，它又重新成为一种非常有效的方法。Boyd、Parikh、Chu、Peleato和Eckstein的优秀论文[28]广泛介绍了ADMM及其变体及其应用。本文实质上是一本关于ADMM主题的书，我们的论述深受其启发。

在本章中，我们考虑在等式约束ax=b下最小化凸函数j（不一定可微）的问题。在第51.1节中，我们讨论了双上升法。它本质上是应用于对偶函数G的梯度下降，但由于G是最大的，梯度下降变成梯度上升。

为了使双上升法的最小化步骤更为稳健，可以使用在拉格朗日中加入惩罚项的技巧。我们得到了增强拉格朗日

，

用λ∈Rm，其中ρ>0称为惩罚参数。我们得到了最小化问题（pρ），

根据au=b最小化，

相当于原始问题。

一千七百一十七

加上惩罚项的好处（根据命题50.36，问题（pρ）在温和条件下有一个唯一的最优解。应用于（pρ）的对偶的对偶上升称为乘数法，并在第51.2节中讨论。

乘法交替方向法，简称ADMM，结合了双重上升的可分解性和乘法方法的优越收敛性。其思想是将函数j分解为两个独立的部分，即j（x，z）=f（x）+g（z），并考虑最小化问题（padmm）。

最小化f（x）+g（z），以ax+bz=c为准，

对于一些p×n矩阵a，一些p×m矩阵b，以及x∈rn，z∈rm，c∈rp，我们也假设f和g是凸的。稍后将添加其他条件。在乘子方法中，我们形成了增广拉格朗日

，

对于一些ρ>0，用λ∈rp。与乘法器方法的主要区别在于，ADMM不是在x和z上共同执行最小化步骤，而是先执行x最小化步骤，然后执行z最小化步骤。因此，x和z以交替或顺序的方式更新，这解释了术语交替方向。由于拉格朗日是增强的，因此A和B上的一些温和条件意味着这些最小化步骤将被保证终止。ADMM见第51.3节。

在第51.4节中，我们在以下假设下证明了ADMM的收敛性：（1）函数f:r→r+∞和g:r→r+∞是适当的闭凸函数（见第50.1节），这样relit（dom（f））relit（dom（g））=6∅。

(2) n×n矩阵a>a是可逆的，m×m矩阵b>b是可逆的。等价地，p×n矩阵a具有秩n，p×m矩阵具有秩m。

(3) 未经认可的拉格朗日l0（x，z，λ）=f（x）+g（z）+λ>（ax+bz−c）具有鞍点，这意味着存在x，z，λ（不一定是唯一的），因此

l0（x，z，λ）≤l0（x，z，λ）≤l0（x，z，λ）

对于所有x，z，λ。

根据定理50.40，假设（3）等价于KKT方程被一些三重方程（x，z，λ）满足的事实，即

ax+bz−c=0（）

和

0∈f（x）＋g（z）＋a>λ+b>λ，（†）

51.1。双上升

假设（3）也等价于定理50.40的条件（a）和（b）。特别是，我们的程序有一个最佳解决方案（x，z）。根据定理50.42，λ是对偶函数g（λ）=infx，z l0（x，z，λ）的最大值，强对偶性保持，即g（λ）=f（x）+g（z）（对偶间隙为零）。

在定理51.1的证明之后，我们将证明假设（2）实际上是由假设（3）所隐含的。这使得我们能够证明一个比Boyd等人所证明的收敛结果更强的收敛结果。【28】（在完全相同的假设（1）和（3）下）。特别地，我们证明了所有序列（xk）、（zk）和（λk）都收敛到最优解（x，）和λe。我们证明的核心在于Boyd等人。[28]但是有新的步骤，因为我们有更强有力的假设（2）。

在第51.5节中，我们讨论了停止标准。

在第51.6节中，我们介绍了ADMM的一些应用，特别是在RN中，在闭凸集C上最小化适当的闭凸函数f，以及二次规划。第二个例子提供了解决二次问题的最佳方法之一，特别是第54章讨论的SVM问题。

第51.7节给出了ADMM在“1-范数问题”中的应用，特别是在机器学习中起重要作用的lasso正则化。

51.1双升

我们的目标是解决最小化问题，问题（P）。

根据au=b，将j（u）最小化，

具有仿射等式约束（具有m×n矩阵和b∈rm）。问题（p）的拉格朗日L（u，λ）由下式给出：

l（u，λ）=j（u）+λ>（au-b）。

用λ∈Rm。从命题49.19出发，对偶函数g（λ）=infu∈rn l（u，λ）由下式给出：

（

−b>λ−j（−a>λ）如果−a>λ∈dom（j），

G（λ）=

−∞否则，

对于所有的λ∈rm，其中j是j的共轭。回想一下，根据定义49.11，在rn的子集u上定义的函数f:u→r的共轭f是由定义的部分函数f：rn→r。

.

如果定理49.18（1）的条件成立，在我们的例子中，这意味着对于每个λ∈Rm，都有一个唯一的uλ∈Rn，这样

g（λ）=l（uλ，λ）=infn l（u，λ），u∈r

函数λ7→uλ是连续的，那么g是可微的。此外，我们有

gλ=auλ−b，

对于双问题的任何解，μ=λ

最大化g（λ），服从于λ∈Rm，

向量u=u祄是原始问题（p）的一个解决方案。此外，j（u）=g（λ），即二元间隙为零。

双上升法本质上是应用于双功能G的梯度下降，但由于G最大化，梯度下降成为梯度上升。另外，我们不再担心上述问题的极小问题inf+一些极小值，namelyu∈rn l（u，λ）有一个唯一的解，因此我们用

U

u+=argminl（u，λ）。

U

给定初始双变量λ0，双上升法包括以下两个步骤：

UK+1=阿格明（u，λk）

，

其中αk>0是一个步长。第一步用于计算“新梯度”（实际上，如果Minimizer UK+1是唯一的，那么gλk=a uk+1−b），第二步是双变量更新。

例51.1。让我们来看一个非常简单的例子，即应用于我们在第41.1节中第一次遇到的问题的梯度上升法，即最小化j（x，y）=（1/2）（x2+y2），服从于2x−y=5。拉格朗日是

.

见图51.1。

拉格朗日对偶的方法是首先计算g（λ）=inf l（x，y，λ）。

（x，y）∈r2

51.1。双上升

图51.1:j（x，y）=（1/2）（x2+y2）为抛物面，2x−y=5为透明蓝色。实施例51.1的解是交叉曲线的顶点，即点（2，

自从

，

我们发现j（x，y）是由正定矩阵决定的二次函数。

，因此要计算g（λ），我们必须设置lx，y=0。通过计算=0和

=0，我们发现x=−2λ和y=λ。然后g（λ）=−5/2λ2−5λ，我们必须计算g（λ）相对于λ∈r的最大值。这意味着计算g0（λ）=0并获得（x，y，λ）=（−2λ，λ，λ）=（2、−1、−1）的解。

对偶同意法不是直接用（x，y）来求解λ，而是从λ的数值估计开始，即λ0，形成“数值”拉格朗日。

.

利用这个数值λ0，我们将l（x，y，λ0）与（x，y）的关系最小化。该计算将与上面形成g（λ）所用的计算相同，因此，我们得到迭代步骤（x1，y1）=（-2λ0，λ0）。因此，如果我们用λk替换λ0，我们就得到了双上升法的第一步，即

.

双上升法的第二步通过计算改进了λ的数值估计。

.

（回想一下，在我们最初的问题中，约束是2x−y=5或5，所以

通过简化上述方程，我们发现

λk+1=（1−β）λk−β，β=5αk。

用前面方程中的λk进行反代换，结果表明：

λk+1=（1−β）k+1λ0+（1−β）k+1−1。

如果0<β≤1，前一行意味着λk+1收敛于λ=−1，这与原拉格朗日对偶法提供的答案一致。观察β=1或，双升法一步结束。

选择适当的αk，我们得到了g（λk+1）>g（λk），该方法取得了进展。例如，在某些假设下，J是严格凸的，并且αk的某些条件下，可以证明双上升收敛到最优解（对于原解和对偶解）。然而，双重上升的主要缺陷是极小化步骤可能出现分歧。例如，发生这种情况的是j是它的一个分量的非零仿射函数。补救办法是给拉格朗日加上一个惩罚条款。

在积极方面，如果函数j是可分离的，则双重上升法将导致分散算法。假设u可以拆分为，使用ui∈rni和

，那

n

j（u）=xji（ui）

i＝1

A被分成n个块ai（ai是m×ni矩阵），作为a=[a1····an]，所以。那么拉格朗日可以写成

具有

.

由此可知，关于原变量u的l（u，λ）的最小化可以分解为n个单独的最小化问题，这些问题可以并行解决。然后算法执行n个更新

=阿格米利（Ui，λk）

用户界面

平行，然后是台阶

λk+1=λk+αk（auk+1−b）。

51.2增广拉格朗日和乘数法

为了使双上升法的最小化步骤更为稳健，可以使用在拉格朗日中加入惩罚项的技巧。

定义51.1.考虑到优化问题（p），

根据au=b，将j（u）最小化，

增广拉格朗日由下式给出

，

用λ∈Rm，其中ρ>0称为惩罚参数。

增广拉格朗日Lρ（u，λ）可以看作是极小问题（pρ）的普通拉格朗日。

根据au=b最小化。

上述问题相当于程序（p），因为对于（pρ）的任何可行解，我们必须有au-b=0。

加上惩罚项的好处（即根据命题50.36，问题（pρ）在a的温和条件下具有唯一的最优解。

对（pρ）的对偶应用的对偶上升产生乘数方法，该方法由以下步骤组成，给定一些初始λ0：

=argminlρ（u，λk）λk+1=λk+ρ（auk+1−b）。

观察第二步使用参数ρ。其原因是，选择αk=ρ可以保证（uk+1，λk+1）满足方程。

juk+1+a>λk+1=0，

这意味着（UK+1，λk+1）是双重可行的；见Boyd、Parikh、Chu、Peleato和Eckstein[28]第2.3节。

例51.2。考虑最小化问题

最小化Y2+2X，以2X−Y=0为准。

图51.2:Y2+2X图形与透明红色平面相交的两个视图

2x−y=0.例51.2的解是相交曲线的顶点，即点

1 1

见图51.2。

二次函数

是凸的，但不是严格凸的。由于y=2x，问题相当于最小化y2+2x=4x 2+2x，其最小值为x=−1/4（因为设置函数x→7 4x2+2的导数得到8x+2=0）。因此，我们的问题的唯一最小值为（x=−1/4，y=−1/2）。我们问题的最大值是l（x，y，λ）=y2+2x+λ（2x-y）。

如果我们采用双上升法，保持λ常数的l（x，y，λ）对x和y的最小化会产生方程。

2+2λ=0

2y-λ=0，

通过将L的梯度（相对于x和y）设置为零获得。如果λ=6−1，则问题没有解决方案。实际上，如果λ=6−1，将l（x，y，λ）=y2+2x+λ（2x−y）与x和y的关系最小化，则得出−∞。

增强拉格朗日是

，

矩阵形式是

.

上述矩阵的迹线为1+0，行列式为

，

因为ρ>0。因此，上述矩阵是对称正定的。将Lρ（x，y，λ）对x和y最小化，将Lρ（x，y，λ）（对x和y）的梯度设为零，得到方程：

解决办法是

.

因此，乘数法的步骤是

，

第二步简化为

λk+1=−1.

因此，我们发现对于任何初始值λ0，该方法在两步后收敛，我们得到

.

乘法的方法也收敛于非凸函数j，如下一个例子所示。

图51.3:2xy（β=1）鞍形图的两个视图与透明品红色平面2x−y=0相交。例51.3的解是相交曲线的顶点，即点（0,0,0）。

例51.3。考虑最小化问题

最小化2βxy，以2x−y=0为准，

β>0。见图51.3。二次函数

不是凸的，因为上面的矩阵不是正半定的（矩阵的特征值是−β和+β）。增强拉格朗日是

，

矩阵形式是

.

上述矩阵的迹线为20，行列式为

ρ2−（β−ρ）2=β（2ρ−β）。

如果ρ>β/2，这个行列式是正的，在这种情况下，矩阵是对称正定的。将Lρ（x，y，λ）对x和y最小化，将Lρ（x，y，λ）（对x和y）的梯度设为零，得到方程：

2ρx+（β-ρ）y+λ=0

2（β-ρ）x+ρy-λ=0。

因为我们假设ρ>β/2，所以解是

.

因此，乘数法的步骤是

，

第二步简化为

，

也就是说，

-

如果我们选取ρ>β>0，这意味着ρ>β/2，那么

，

该方法收敛于任何初值λ0的解。

x=0，y=0，λ=0.

实际上，由于约束2X−Y=0成立，2βx y=4βx2，并且函数x 7→4βx2的最小值在x=0时实现（因为β>0）。

作为练习，读者应该验证双上升（αk=ρ）产生的方程

，

因此，该方法有分歧，除了λ0=0，这是最优解。

乘法器的方法在比双提升更普遍的条件下收敛。然而，惩罚项的加成具有负效应，即J可分，拉格朗日Lρ也不可分。因此，乘法器的基本方法不能用于分解，也不可并行。下一种方法处理可分离性问题。

51.3 ADMM：乘法器的交替方向法

乘法交替方向法，简称ADMM，结合了双重上升的可分解性和乘法方法的优越收敛性。它可以被看作是乘法器方法的近似值，但一般来说它更优越。

其思想是将函数j分解为两个独立的部分，即j（x，z）=f（x）+g（z），并考虑最小化问题（padmm）。

最小化f（x）+g（z），以ax+bz=c为准，

对于一些p×n矩阵a，一些p×m矩阵b，以及x∈rn，z∈rm，c∈rp，我们也假设f和g是凸的。稍后将添加其他条件。在乘子方法中，我们形成了增广拉格朗日

-至-

对于一些ρ>0，用λ∈rp。

给定一些初始值（z0，λ0），admm方法包括以下迭代步骤：

xk+1=argminlρ（x，zk，λk）

X

zk+1=argminlρ（xk+1，z，λk）

.

51.3。ADMM：乘数交替方向法

而不是在x和z上共同执行最小化步骤，就像步骤中的乘数方法一样

（xk+1，zk+1）=argminlρ（x，z，λk），

x，z

ADMM首先执行X最小化步骤，然后执行Z最小化步骤。因此，x和z以交替或顺序的方式更新，这解释了术语交替方向。

ADMM中的算法状态为（zk，λk），从这个意义上说（zk+1，λk+1）是（zk，λk）的函数。变量xk+1是一个辅助变量，用于从（zk，λk）计算zk+1。X和Z的作用并不完全对称，因为X的更新是在λ的更新之前完成的。通过切换X和Z，F和G，A和B，我们得到了一个ADMM的变体，其中X-update步骤和Z-update步骤的顺序是相反的。

例51.4。让我们重新考虑一下示例51.2中的问题，用admm来解决它。我们把问题表述为

最小化2X+Z2，以2X−Z=0为准，

f（x）=2x，g（z）=z2。增广拉格朗日由下式给出

.

ADMM步骤如下。X-update是

xk+1=argmin，

X

由于这是x中的二次函数，当上述函数的导数（相对于x）为零时，即

（1）

z-update是

，

对于x阶跃，当上述函数的导数（相对于z）为零时，即达到最小值。

（2）

将（1）的右侧替换为（2）中的xk+1，得出

（4）

利用（2），我们得到

，（5）

然后用我们得到的

（6）

将（1）的右侧替换为（6）中的xk+1，我们得到

（7）

式（7）表明zk确定了λk+1，式（1）表明k+2，以及式（4）表明zk也确定了xk+2。特别是，我们发现

这样就足以找到该层序的界限（zk）。因为我们已经从例子中知道了

51.2该限值为−1/2，使用（4），我们写下

.

通过归纳，我们推断出

，

由于ρ>0，我们得到ρ/（ρ+2）<1，所以序列的极限（zk+1）确实是−1/2，因此（λk+1）的极限是−1，xk+2的极限是−1/4。

为了使ADMM实用，X-最小化步骤和Z-最小化步骤必须能够有效地实现。

根据标度双变量礹=（1/ρ）λ，编写ADMM更新通常很方便。如果我们将残差定义为

R=ax+bz−c，

然后我们有了

λ>r+（ρ/2）k r k22=（ρ/2）kr+（1/ρ）λk22−（1/（2ρ））kλk22=（ρ/2）kr+µk22−（ρ/2）kµk22。

按比例缩放的ADMM形式包括以下步骤：

xk+1=argmin

X

祄k+1=祄k+axk+1+bzk+1−c。

如果我们将步骤k的剩余Rk定义为

Rk=axk+bzk−c=祄k−祄k−1=（1/ρ）（λk−λk−1），

然后我们看到了

.

按比例排列的公式通常比未按比例排列的公式短。

我们现在讨论ADMM的收敛性。

51.4行政管理的衔接

让我们重复一下admm的步骤：给定一些初始值（z0，λ0），请执行以下操作：

xk+1=argminlρ（x，zk，λk）（x-更新）

X

zk+1=argminlρ（xk+1，z，λk）（z-更新）

（λ-更新）

可在以下三个假设下证明ADMM的收敛性：

(1) 函数f:r→r+∞和g:r→r+∞是适当的闭凸函数（见第50.1节），这样relit（dom（f））relit（dom（g））=6∅。

(2) n×n矩阵a>a是可逆的，m×m矩阵b>b是可逆的。等价地，p×n矩阵a具有秩n，p×m矩阵具有秩m。

(3) 未经认可的拉格朗日l0（x，z，λ）=f（x）+g（z）+λ>（ax+bz−c）具有鞍点，这意味着存在x，z，λ（不一定是唯一的），因此

l0（x，z，λ）≤l0（x，z，λ）≤l0（x，z，λ）

对于所有x，z，λ。

回想一下，增广拉格朗日由

.

对于z（和λ）固定，我们有

Lρ（x，z，λ）=f（x）+g（z）+λ>（ax+bz−c）+（ρ/2）（ax+bz−c）>（ax+bz−c）

=f（x）+（ρ/2）x>a>ax+（λ>+ρ（bz−c）>）ax

+G（Z）+λ>（BZ−C）+（ρ/2）（BZ−C）>（BZ−C）。

假设（1）和（2）保持不变。由于a>a是可逆的，那么它是对称正定的，并且根据命题50.36，x-最小化步骤有一个唯一的解（最小化问题用一个唯一的最小化器成功）。

同样，对于x（和λ）固定，我们有

由于b>b是可逆的，那么它是对称正定的，并且根据命题50.36，z-最小化步骤有一个唯一的解（最小化问题以一个唯一的最小化器成功）。

根据定理50.40，假设（3）等价于KKT方程被一些三重方程（x，z，λ）满足的事实，即

ax+bz−c=0（）

和

0∈f（x）＋g（z）＋a>λ+b>λ，（†）

假设（3）也等价于定理50.40的条件（a）和（b）。特别是，我们的程序有一个最佳解决方案（x，z）。根据定理50.42，λ是对偶函数g（λ）=infx，z l0（x，z，λ）的最大值，强对偶性保持，即g（λ）=f（x）+g（z）（对偶间隙为零）。

在定理51.1的证明之后，我们将看到假设（2）实际上是由假设（3）所隐含的。这使得我们能够证明一个比Boyd等人所证明的收敛结果更强的收敛结果。[28]在完全相同的假设（1）和（3）下。

设p为凸集上f+g的最小值（x，z）rm+p ax+bz−c=0，设（pk）为pk=f（xk）+g（zk）给出的序列，并回想Rk=axk+bzk−c。

我们的主要目标是证明以下结果。

定理51.1。假设以下假设成立：

(1) 函数f:r→r+∞和g:r→r+∞是适当的闭凸函数（见第50.1节），这样relit（dom（f））relit（dom（g））=6∅。

(2) n×n矩阵a>a是可逆的，m×m矩阵b>b是可逆的。同样地，p×n矩阵a有秩n，p×m矩阵有秩m（这个假设实际上是多余的，因为它是由假设（3）所隐含的）。

(3) 未经认可的拉格朗日l0（x，z，λ）=f（x）+g（z）+λ>（ax+bz−c）具有鞍点，这意味着存在x，z，λ（不一定是唯一的），因此

l0（x，z，λ）≤l0（x，z，λ）≤l0（x，z，λ）

对于所有x，z，λ。

然后，对于任何初始值（z0，λ0），以下属性保持不变：

(1) 序列（Rk）收敛到0（剩余收敛）。

(2) 序列（pk）收敛到p（目标收敛）。

(3) 序列（xk）和（zk）收敛到问题（padmm）的最优解（x，e ze），序列（λk）收敛到对偶问题（初等和对偶变量收敛）的最优解λe。

证据。证据的核心在于Boyd等人。[28]但是有新的步骤，因为我们有更强有力的假设（2），产生更强有力的结果（3）。

证据包括几个步骤。不能直接证明序列（xk）、（zk）和（λk）收敛，因此首先证明序列（rk+1）收敛到零，并且序列（axk+1）和（bzk+1）也收敛。

第1步。证明下面的不等式（a1）。

考虑reals（v k）的序列

.

可以看出，v k满足以下不等式：

（A1）

这相当困难。因为Boyd等人给出了完整的证据。[28]之后，我们将只提供一些关键步骤。

不等式（a1）表明序列（v k）是不递增的。如果我们为k，k−1，…，0写下这些不等式，我们有

通过把这些不等式相加，我们得到

，

这意味着

，（b）

因为v k+1≤v 0。

第2步。证明了序列（Rk）收敛于0，并且序列（axk+1）和（bzk+1）也收敛。

不等式（b）意味着级数绝对收敛。

特别是，序列（Rk）收敛到0。

系列的第n个部分和）是

，

由于序列）收敛，我们推断序列（bzk+1）收敛。由于axk+1+bzk+1−c=rk+1，（rk+1）和（bzk+1）的收敛意味着序列（axk+1）也收敛。

第3步。证明了序列（xk+1）和（zk+1）收敛。根据假设（2），矩阵a>a和b>b是可逆的，因此将每个向量a xk+1乘以（a>a）−1a>，如果序列（axk+1）收敛到u，那么序列（xk+1）收敛到（a>a）−1a>u。同样，如果序列（b zk+1）收敛到v，那么序列（zk+1）收敛到（b>b）−1B>

第4步。证明序列（λk）收敛。

回想一下

λk+1=λk+ρrk+1.

接下来是归纳法

λk+p=λk+ρ（Rk+1+···+ρk+p），p≥2.

结果，我们得到

.

由于级数收敛，部分和形成一个柯西序列，这立即意味着对于任何>0，我们都可以找到n>0，这样

对于所有k，p+k≥n，

因此序列（λk）也是柯西序列，因此它收敛。

第5步。证明了序列（pk）收敛于p。

为此，我们还需要两个不平等。遵循Boyd等人[28]我们需要证明

pk+1−p≤−（λk+1）>Rk+1−ρ（b（zk+1−zk））>（−Rk+1+b（zk+1−z））（a2）

和

P−pk+1≤（λ）>Rk+1.（A3）

因为我们证明了序列（Rk）和b（zk+1−zk）收敛于0，并且序列（λk+1）收敛于

（λk+1）>Rk+1+ρ（b（zk+1−zk））>（−Rk+1+b（zk+1−z））≤p−pk+1≤（λ）>Rk+1，我们推断在极限处，pk+1收敛于p。

第6步。证明（A3）。

因为（x，y，λ）是鞍点，我们有

l0（x，z，λ）≤l0（xk+1，zk+1，λ）。

由于ax+bz=c，我们得到l0（x，z，λ）=p，由于pk+1=f（xk+1）+g（zk+1），我们得到

l0（xk+1，zk+1，λ）=pk+1+（λ）>rk+1，

因此我们得到p≤pk+1+（λ）>Rk+1，

产生（a3）。

第7步。证明（A2）。

根据50.33号提案，zk+1最小化lρ（xk+1，z，λk）iff

0∈g（zk+1）+b>λk+ρb>（axk+1+bzk+1−c）

=g（zk+1）+b>λk+ρb>Rk+1

=g（zk+1）+b>λk+1，

因为Rk+1=axk+1+bzk+1−c和λk+1=λk+ρ（axk+1+bzk+1−c）。

总之，我们有

0 g（zk+1）+b>λk+1，（†1）

这表明zk+1最小化了函数

z 7→g（z）+（λk+1）>bz。

因此，我们

g（zk+1）+（λk+1）>bzk+1≤g（z）＋（λk+1）>bz（b1）

同样，xk+1最小化lρ（x，zk，λk）iff

0∈f（xk+1）+a>λk+ρa>（axk+1+bzk−c）

=f（xk+1）+a>（λk+ρrk+1+ρb（zk−zk+1））。

=f（xk+1）+a>λk+1+ρa>b（zk−zk+1）

因为Rk+1−Bzk+1=axk+1−c和λk+1=λk+ρ（axk+1+Bzk+1−c）=λk+ρRk+1。

同样，上述推导表明

0∈f（xk+1）+a>（λk+1−ρb（zk+1−zk）），（†2）

这表明XK+1最小化了功能

x 7→f（x）+（λk+1−ρb（zk+1−zk））>ax。

因此，我们得到f（xk+1）+（λk+1−ρb（zk+1−zk））>axk+1≤f（x））+（λk+1−ρb（zk+1−zk））>ax。（B2）

将不等式（b1）和（b2）相加，利用方程ax+bz=c，重新排列，得到不等式（a2）。

第8步。证明（xk）、（zk）和（λk）收敛于最优解。回想一下，（Rk）收敛到0，（Xk）、（zk）和（λk）收敛到极限x、z和

e e

λe.由于Rk=axk+bzk−c，在极限内，我们有

ax+bz−c=0.（1）e

但（）和（4）正是KKT方程，根据定理50.40，我们得出x、z和λ是最优解。EE

第9步。证明（A1）。这是证据中最冗长的一步。我们首先将（a2）和（a3）相加，然后执行相当多的操作或重写操作。完整的推导可在Boyd等人〔28〕。

评论：

(1) 根据定理50.41，我们可以用稍微强一些的假设来代替假设（3），即程序的最佳值是有限的，并且约束是合格的。由于约束是仿射的，这意味着在relit（dom（f））relit（dom（g））中存在一些可行的解决方案。这些假设比假设（3）更实际。

(2) 实际上，假设（3）意味着假设（2）。实际上，我们从定理50.40知道鞍点的存在意味着我们的程序有一个有限的最优解。但是，如果a>a或b>b不可逆，那么程序（p）可能没有有限的最优解，如下反例所示。

例51.5。让

f（x，y）=x，g（z）=0，y−z=0。

然后

Lρ（x，y，z，λ）=x+λ（y−z）+（ρ/2）（y−z）2，

但用Z保持不变的超（x，y）最小化得到−∞，这意味着上述程序没有有限的最优解。见图51.4。

问题是

，

但是

不可逆。

(3) 证明（a1）、（a2）、（a3）和（rk）到0和（pk）到p的收敛性不需要假设（2）。使用独创不等式（a1）（和（b））的证明是Boyd等人给出的证明。〔28〕。我们还能够证明（λk）、（axk）和（bzk）在没有假设（2）的情况下收敛，但为了证明（xk）、（yk）和（λk）收敛到最优解，我们必须使用假设（2）。

图51.4：示例51.5的图形表示。这是固定Z时X最小化步骤的图示。由于这两个平面的交叉点是一条无界线，我们“看到”最小化x的结果是−∞。

(4) Bertsekas在[17]第2.2和5.4节中讨论了ADMM。他对ADMM的表述略有不同，即

最小化f（x）+g（z），以ax=z为准。

Bertsekas在假设dom（f）是紧凑的或a>a是可逆的，并且存在鞍点的前提下陈述了该版本admm的收敛结果；见命题5.4.1。证据见Bertsekas[20]第3.4节，提案4.2。似乎证明利用了梯度，所以不清楚它适用于更一般的情况，其中f和g是不可微的。

(5) 在加贝[47]中讨论了ADMM的版本（第4节和第5节）。它们比这里讨论的版本更通用。给出了一些收敛性的证明，但由于加贝的框架更为一般，不清楚它们是否适用于我们的环境。同时，这些证据也依赖于狮和麦赛的早期结果，这使得比较变得困难。

（5）假设（2）并不意味着系统ax+bz=c有任何解决方案。例如，如果

，

系统

X−Z=1 X−Z=0

没有解决方案。然而，由于假设（3）意味着程序有一个矩阵优化解，它意味着。c属于p×（n+m）的列空间，这里有一个例子，其中admm对一个最优值为−∞的问题发散。

例51.6。考虑以下问题：

f（x）=x，g（z）=0，x−z=0。

由于f（x）+g（z）=x，x=z，变量x不受约束，当x变为−∞时，上述函数变为−∞。增强拉格朗日是

矩阵

-

是奇异的，当（x，z）=t（1,1），t变为−∞时，lρ（x，z，λ）变为−∞in。ADMM步骤如下：

，

这些方程适用于所有k≥0。从最后两个方程我们得出：

，对于所有k≥0，

所以

，对于所有k≥0。

结果我们发现

.

通过归纳，我们得到

，对于所有k≥0，

这表明，当k到无穷大时，xk+3变为−∞，由于xk+2=zk+2，同样地，当k到无穷大时，zk+3变为−∞。

51.5停车标准

回到不等式（a2），pk+1−p≤−（λk+1）>Rk+1−ρ（b（zk+1−zk））>（−Rk+1+b（zk+1−z）），（a2）利用ax+bz−c=0和Rk+1=axk+1+bzk+1−c的事实，我们得到

−Rk+1+b（zk+1−z）=−axk+1−bzk+1+c+b（zk+1−z）

=−axk+1+c−bz_

=−a xk+1+a x=−a（xk+1−x），

所以（a2）可以改写为

pk+1−p≤−（λk+1）>rk+1+ρ（b（zk+1−zk））>a（xk+1−x），

或等同于

pk+1−p≤−（λk+1）>rk+1+（xk+1−x）>ρa>b（zk+1−zk）。（s1）

我们将双重残差定义为

sk+1=ρa>b（zk+1−zk），

数量Rk+1=axk+1+bzk+1−c为主要残余物。那么（s1）可以写成

pk+1−p≤−（λk+1）>rk+1+（xk+1−x）>sk+1。（s）

不等式表明，当残差Rk和Sk较小时，Pk从下到下接近p。因为x是未知的，我们不能使用这个不等式，但是如果我们有一个猜测，那么使用柯西-施瓦兹，我们得到

.

51.6。ADMM的一些应用

上述建议，合理的终止标准是且应该是小的，即

Pri和Dual，

对于某些选定的可行性公差，pri和dual。选择这些参数的进一步讨论可在Boyd等人【28】（第3.3.1节）。

Boyd等人讨论了ADMM的各种扩展和变化。【28】（第3.4节）。为了加速该方法的收敛，可以在每个步骤中选择不同的ρ（例如，ρk），尽管证明这种方法的收敛可能很困难。如果我们假设ρk在多次迭代后变为常数，那么我们给出的证明仍然适用。一个简单的方案是：

K+1=__ρτkincr/τρdecrk ifif

π

_ρk，否则，

其中，τincr>1、τdecr>1和祄>1是一些选定的参数。我们再次将感兴趣的读者介绍给Boyd等人。【28】（第3.4节）。

51.6 ADMM的一些应用

F、G、A和B中的结构经常被用来产生更有效的方法来执行x-update和z-update。我们关注的是x-update，但讨论同样适用于z-update。由于z和λ在x的最小化过程中保持不变，因此使用比例形式的admm更为方便。回想一下

（这里我们使用u而不是μ），因此我们可以将x-update步骤表示为

，

带V=−BZ+C−U。

例51.7。当a=i时出现第一个简化，在这种情况下，x-update是

x+=argminproxf，ρ（v）。

X

map v 7→proxf，ρ（v）被称为f的邻近算子，惩罚为ρ。上述最小化通常称为近端最小化。

例51.8。当函数f足够简单时，可以用解析方法计算邻近算子。特别是当f=ic，非空闭凸集c的指示函数时，这种情况更为明显。

x+=argmin（最小值）

X

v对c的正交投影。在特殊情况下，其中（第一个或第二个），然后x+=（v）+，

将V的负分量设为零得到的向量。

例51.9。出现简化的第二种情况是f是形式的凸二次函数的情况。

其中p是一个n×n对称的半正定矩阵，q∈rn和r∈r。在这种情况下，图的梯度

由给出

（p+ρa>a）x+q−ρa>v，

由于a的秩为n，所以矩阵a>a是对称正定的，所以我们得到

x+=（p+ρa>a））−1（ρa>v−q）。

可以使用数值线性代数中的方法来相当有效地计算x+；见Boyd等人。【28】（第4节）。

例51.10。出现简化的第三种情况是前一种情况的变化，其中f是形式的凸二次函数。

除了f受到等式约束cx=b外，如第49.4节所述，这意味着dom（f）=x∈rn cx=b和a=i。x-最小化步骤包括

最小化函数

受约束的

cx=b，

51.6。ADMM的一些应用

因此，根据第49.4节的结果，x+是KKT系统解决方案的组成部分。

.

矩阵p+ρi是对称正定的，因此kkt矩阵是可逆的。

我们现在可以描述如何使用ADMM来解决凸优化的两个常见问题。

（1）在RN中的闭凸集C上，将适当的闭凸集F最小化。这是以下问题

最小化f（x）服从x∈c，

可以用aadm格式重写为

最小化f（x）+ic（z），以x−z=0为准。

使用标度双变量u=λ/ρ，增加的拉格朗日是

.

考虑到示例51.8，此问题的ADMM的缩放形式是

zk+1=_c（xk+1+uk）

UK+1=UK+XK+1−ZK+1。

X更新包括评估一个近端操作员。注意，函数f不必是可微的。当然，这些最小化依赖于对近端算子和投影算子进行有效的计算。（2）二次规划。问题在这里

减少

以ax=b，x≥0为准，

其中p是一个n×n对称的半正定矩阵，q∈rn，r∈r，a是秩m的m×n矩阵。

上述程序转换为以下ADMM格式：

最小化f（x）+g（z），以x−z=0为准，

当dom（f）=x∈rn ax=b，

和

，

正相关函数的指示函数。鉴于实施例51.8和51.10，按比例缩放的ADMM形式包括以下步骤：

zk+1=（xk+1+uk）+

UK+1=UK+XK+1−ZK+1。

X更新涉及求解KKT方程

.

这是一个重要的例子，因为它提供了解决二次问题的最佳方法之一，特别是第54章讨论的SVM问题。

51.7 ADMM在1-范数问题中的应用

ADMM的另一个重要应用是“1-范数最小化问题，特别是lasso最小化”，在下面和第52.2节中讨论。这涉及到admm的特殊情况，其中f（x）=τkxk1和a=i。特别是在一维情况下，我们需要解决最小化问题：查找

x=argmin（最小值）

X

x，v∈r，和ρ，τ>0。设c=τ/ρ并写

.

x上的f最小等于x上的f最小

g（x）=2c x+（x−v）2=2c x+x2−2xv+v2，

51.7。ADMM在1-范数问题中的应用

相当于最小化

h（x）=x2+2（c x−xv）

超过x。如果x≥0，则h（x）=x2+2（cx−x v）=x2+2（c−v）x=（x−（v−c））2−（v−c）2。

如果v−c>0，即v>c，因为x≥0，函数x 7→（x−（v−c））2的最小值为

=v c>0，否则如果v−c≤0，则函数x 7→（x−（v−c））2的最小值为

如果x≤0，则h（x）=x2+2（−cx−x v）=x2−2（c+v）x=（x−（v+c））2−（v+c）2。

如果v+c<0，即v<−c，因为x≤0，函数x 7→（x−（v+c））2对于x=v+c具有最小值，否则如果v+c≥0，则函数x 7→（x−（v+c））2对于x=0具有最小值。

总之，infx h（x）是v的函数，由

γ

−V C如果V>C

SC（V）=0，如果V≤C

V+C，如果V<−C。

函数sc被称为软阈值运算符。图中所示的sc图

51.5。

图51.5:sc图（当c=2时）。

你可以查一下

sc（v）=（v−c）+−（−v−c）+，

以及

sc（v）=（1−c/v）+v，v=06，

这表明sc是一个收缩操作符（它向零移动一个点）。

运算符sc扩展到以rn分量表示的向量，即，如果x=（x1，…，xn），则

sc（x）=（sc（x1），…，sc（xn））。

我们现在考虑几个1-范数问题。

(1) 最小绝对偏差。

这是最小化kax−bk1而不是kax−bk2的问题。最小绝对偏差比最小二乘拟合更具鲁棒性，因为它能更好地处理异常值。问题可以用ADMM形式表述如下：

最小化kzk1，以ax−z=b为准，

f=0，g=k1。和往常一样，我们假设a是n阶的m×n矩阵，因此a>a是可逆的。ADMM可以表示为

xk+1=（a>a）−1a>（b+zk−uk）zk+1=s1/ρ（axk+1−b+uk）uk+1=uk+axk+1−zk+1−b。

(2) 基础追求。

这是以下最小化问题：

最小化kxk1，以ax=b为准，

其中a是秩m<n的m×n矩阵，b∈rm，x∈rn。问题是找到一个欠定线性系统的稀疏解，这意味着有许多零坐标的解X。这个问题在压缩传感和统计信号处理中起着核心作用。

基础追求可以用ADMM形式表示为问题

最小化IC（x）+KZK1，以x−z=0为准，

51.7。ADMM在c=x∈rn ax=b 1-范数问题中的应用。很容易看出，ADMM过程是

xk+1=_c（zk−uk）

zk+1=s1/ρ（xk+1+uk）uk+1=uk+xk+1−zk+1，

其中_c是子空间c上的正交投影。实际上，不难证明xk+1=（i−a>（aa>）-1a）（zk−uk）+a>（aa>）-1b。

在某种意义上，“1-最小化问题”被简化为“2-范数问题”的序列。有一些方法可以提高方法的效率；参见Boyd等人。[28]（第6.2节）

(3) 一般1-规则化损失最小化。

这是以下最小化问题：

最小化l（x）+τkxk1，

式中，L是任何适当的闭和凸损失函数，τ>0。我们将问题转换为ADMM问题：

最小化L（x）+τkzk1，以x−z=0为准。

ADMM程序是

zk+1=sτ/ρ（xk+1+uk）

UK+1=UK+XK+1−ZK+1。

X-update是近端操作员评估。一般来说，我们需要应用一个数值程序来计算xk+1，例如，牛顿方法的一个版本。

特别的情况在哪里特别重要。

（4）套索的正规化。

这是以下最小化问题：

最小化（1.

这是一个线性回归，正则化项τkxk1而不是τkxk2，以鼓励稀疏解。这种方法最初是由Tibshirani arround于1996年提出的，其名称为lasso，代表“最小绝对选择和收缩运算符”。这种方法也被称为“1-正则回归”，但它不如主要使用的“lasso”那么可爱。这种方法在黑斯提、提比西拉尼和温赖特[88]中有广泛讨论。

Lasso最小化转换为以下ADMM形式的问题：

最小化以x−z=0为准。

那么ADMM程序是

xk+1=（a>a+ρi）−1（a>b+ρ（zk−uk））zk+1=sτ/ρ（xk+1+uk）uk+1=uk+xk+1−zk+1。

由于ρ>0，矩阵a>a+ρi是对称正定的。注意，x-update看起来像一个岭回归步骤（参见第52.1节）。

套索有各种各样的概括。

(5) 广义拉索正则化。

这是以下最小化问题：

最小化（1，

其中a是m×n矩阵，f是p×n矩阵，a有n秩或f有n秩，该问题转化为admm问题。

减少

以fx−z=0为准，

相应的ADMM程序是

xk+1=（a>a+ρf>f）−1（a>b+ρf>（zk−uk））zk+1=sτ/ρ（fxk+1+uk）uk+1=uk+fxk+1−zk+1。

(6) 集体套索。

这是（3）的概括。在这里，我们假设X是X=（x1，…，xn），用Xi＝RNI和N1+Fo.+Xn= n分裂，正则项KXK1被替换。

51.8。总结

. 当ni=1时，这减少到（3）。需要修改admm过程的z-update。我们定义了软阈值算子sc:rm→rm，由

当sc（0）=0时。然后z-update由n个更新组成

zik+1=sτ/ρ（xki+1+uk），i=1，…，n.

该方法可以扩展到处理重叠组；参见Boyd等人。【28】（第6.4节）。

在Boyd等人的研究中，还有许多关于ADMM的应用。[28]，包括共识和分享。另请参见Strang[166]了解简要概述。

51.8总结

本章的主要概念和结果如下：

• 双重提升。

• 增强拉格朗日。

• 惩罚参数。

• 乘数法。

• ADMM（乘法器交替方向法）。

• x-更新，z-更新，λ-更新。

• 按比例缩放的ADMM形式。

• 残余，双重残余。

• 停止标准。

• 近端操作员，近端最小化。

• 二次规划。

• KKT方程。

• 软阈值运算符。

• 收缩操作员。

• 最小绝对偏差。

• 基础追求。

• 一般1-规则化损失最小化。

• 套索正规化。

• 广义拉索正则化。

• 集体套索。