凸优化（B）——再看交替方向乘子法（ADMM），Frank-Wolfe方法

学弱猹

发布于 2021-08-09 17:33:51

1.7K0

发布于 2021-08-09 17:33:51

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

上一节笔记：凸优化（A）——坐标下降法，对偶上升法，再看增强拉格朗日法

————————————————————————————————————

大家好！

这一节我们会介绍目前非常流行的交替方向乘子法（Alternating Direction Method of Multipliers，ADMM），这个方法的应用非常广泛，所以课件上举了非常多的例子来说明它的应用，我们这里自然也不会吝啬于此。如果有空的话，我们还会继续介绍Frank-Wolfe算法，这也是一个设计上比较有意思的优化算法。

那么我们开始吧。

Source

CMU 10-725: Convex Optimization
Boyd, Vandenberghe, Convex Optimization
S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein (2010), Distributed optimization and statistical learning via the alternating direction method of multipliers
M. Hong, Z. Luo (2012), On the linear convergence of the alternating direction method of multipliers
F. Lutzeler, P. Bianchi, Ph. Ciblat, W. Hachem (2014), Linear convergence rate for distributed optimization with the alternating direciton method of multipliers
R. Nishihara, L. Lessard, B. Recht, A. Packard, M. Jordan (2015), A general analysis of the convergence of ADMM
W. Deng, W. Yin (2012), On the global and linear convergence of the generalized alternating direction method of multipliers
V. Vu, J. Cho, J. Lei, K. Rohe (2013), Fantope projection and selection: a near-optimal convex relaxation of sparse PCA
Fan (1949), On a theorem of Weyl conerning eigenvalues of linear transformations

交替方向乘子法

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）的核心自然在于“交替方向”和“乘子”。即一方面有坐标下降法的意思，又借鉴了上一节所说的增强拉格朗日法的思想。通过这个介绍，相信读者可以看出，这个方法希望解决的是当问题可分解的时候，有没有比较好的优化算法。

具体来说，它所关注的问题就是

\min_{x, z} f(x) + g(z)

s.t. \quad Ax + Bz = c

即优化问题可以被拆成

f,g

两部分。那么通过增强拉格朗日法的变换，再利用上一节所说对偶上升法的迭代公式，我们可以得到拉格朗日函数

L_\rho (x, z , u) = f(x) + g(z) + u^T(Ax + Bz - c) + \frac \rho 2 \|A x + Bz - c\|_2^2

“乘子”这个词就体现出来了。它的更新公式就可以体现出“交替方向”的意思，因为交替方向乘子法的更新公式是

x^{(k)} = \arg\min_x L_\rho(x, z^{(k - 1)}, u^{(k - 1)})

z^{(k)} = \arg\min_z L_\rho(x^{(k)}, z, u^{(k - 1)})

u^{(k)} = u^{(k - 1)} + \rho(Ax^{(k)} + Bz^{(k)} - c)

前两行就是先以

为变量优化，再以

为变量优化的意思（注意在给

做优化的时候，

的信息已经是最新的了），而第三行和增强拉格朗日法的更新公式几乎是一脉相承。

另外一种更新方法叫作标准化形式的ADMM（Scaled Form ADMM），如果我们设

w =\frac u\rho

，那么这个时候，拉格朗日函数会发生一些改动（我们给它起一个名字叫增强拉格朗日函数），即

L_\rho(x, z, w) = f(x) + g(z) + \frac \rho 2 \|Ax + Bz - c + w \|_2^2 - \frac \rho 2 \|w \|_2^2

事实上这就是一个经典的平方展开的逆运算，不难验证这种写法其实和上面的拉格朗日函数是等价的。

一个关键的地方在于，这么写好之后，其实公式就会变成下面这样

x^{(k)} = \arg\min_x f(x) + \frac \rho 2 \| A x + Bz^{(k-1)} - c + w^{(k - 1)} \|_2^2

z^{(k)} = \arg\min_z g(z) + \frac \rho 2 \|Ax^{(k)} + Bz - c + w^{(k - 1)} \|_2^2

w^{(k)} = w^{(k - 1)} + Ax^{(k)} + Bz^{(k)} - c

这么修改的好处也有一些，一是可以提出一个与

x, z

都无关的项

\frac \rho 2 \|w \|_2^2

，所以优化的时候就可以直接无视它。二是在对

作更新的时候，其实等价于之前的

的更新式子再两边除以一个

\rho

。因此我们会发现在更新

的时候其实没有所谓的步长的说法了（回顾一下，在对偶上升法中，这个系数的意义就是步长），这也是“标准化形式”这个说法的由来。

当然不管是什么形式，其实这个方法几乎没什么大的改动。但是它具备很好的几个特性。

Theorem 1: 在合理的对

f, g

的假设下，对任意的

\rho > 0

，ADMM算法都能做到

r^{(k)} = A x^{(k)} + B z^{(k)} - c \to 0

f(x^{(k)}) + g(z^{(k)}) \to f(x^*) + g(z^*)

，即最优值。

u^{(k)} \to u^*

这三个式子代表三个意思：原问题的解

x^{(k)}, z^{(k)}

在极限状态下是可行解，最优值在极限状态下可达到，且对偶变量极限状态下可以达到极值点。当然有的人可能会问什么是“合理的假设”，这个要讨论起来有点复杂，大家可以见Source中的Boyd (2010)中对这个方法的讨论。

注意这三个式子并没有说明这个方法可以使得原问题的解逼近原问题的极值点，尽管函数本身的极值是可以达到的。不过在应用层面上这个问题一般是不大的，大家也并不care太多这个细节，尤其是很多时候只希望知道问题最优解是多少的时候2333……

关于这个方法的收敛性分析，理论也不是很完备，不过Source中的Hong (2012), Deng (2012), lutzeler (2014), Nishihara (2015)等都可以作为参考。但有一个经验法则是它的速度近似于一阶方法，因此可以认为它具备次线性收敛速度。

与其他方法不太一样的是，ADMM具有非常多的相关应用，所以我们会举一些实操的例子再继续介绍下一个算法。

Example 1: Connection to Proximal Operators （Source：CMU）考虑近端优化解决的问题形式

\min_x f(x) + g(x)

，使用ADMM求解。

很显然，这是一个天然的给ADMM求解的格式，我们可以通过转换，得到等价的优化问题

\min_{x, z} f(x) + g(z)

s.t. \quad x = z

那么我们自然可以写出它的增强拉格朗日函数

L_\rho(x, z, w) = f(x) + g(z) + \frac \rho 2 \|x - z + w \|_2^2 - \frac \rho 2 \|w \|_2^2

如果要针对

优化，那么其实就是对式子

f(x) + \frac \rho 2 \|x - z + w\|_2^2

优化。根据近端梯度的公式

\operatorname{prox}_{h, t}(x) = \arg\min_{z} \frac 1 {2t} \|x - z \|^2 + h(z)

我们自然可以给出它的更新公式

x^{(k)} = \operatorname{prox}_{f, 1/\rho}(z^{(k - 1)} - w^{(k - 1)})

z^{(k)} = \operatorname{prox}_{g, 1/\rho}(x^{(k)}+ w^{(k - 1)})

w^{(k)} = w^{(k - 1)} + x^{(k)} - z^{(k)}

所以我们可以看出，ADMM做的其实就是两步近端算子的计算而已。不过这里有一个细节，就是如果我们把自变量

x, z

前面的系数改一下，也即考虑对于一般的

Ax + By = c

这样的约束。在这种情况下对应的更新公式就不一定等价于求解近端算子了。假如说我们希望

x^{(k)}

的更新等价于求解近端算子，那么就必须要求

A = I

是一个单位阵。

另一个方面，可以看出ADMM可以认为是近端梯度法的一个延伸，因为近端梯度法可以解决的问题其实局限于对

凸且光滑，

凸的情况。但是如果函数不具备光滑性，或者说不清楚函数的光滑性，那么这个时候其实对于这样的问题，ADMM会被优先考虑。

Example 2: LASSO（Source：CMU）设

y \in \mathbb R^n

X \in \mathbb R^{n \times p}

，考虑LASSO目标函数

\min_\beta \frac 12 \| y - X \beta \|_2^2 + \lambda \| \beta \|_1

的ADMM解法。

可以说大部分算法我们都拿LASSO举了例子，因此相信大家也不太会对这个方法陌生了。如果陌生，那就把前几节刷一刷233。

这个问题是一个无约束优化问题，因此我们可以把问题写成下面的形式。

\min _{\beta, \alpha} \frac 12 \|y - X \beta \|_2^2 + \lambda \|\alpha \|_1

s.t. \quad \beta - \alpha = 0

写成这样，我们就可以把问题转换成

f(x) + g(z)

的形式。那么这个问题的增强拉格朗日函数形式是

当然了看到这个形式你就知道它是标准化形式的ADMM，它与一般的ADMM是等价的，只是写出来的形式不同。

那么这样的话，我们按照先

\beta

，后

\alpha

的形式，来看看如何推出这个问题的ADMM算法。

先优化

\beta

，那么其实就是要求解问题

\min _\beta \frac 12 \|y - X \beta \|_2^2 + \frac \rho 2 \| \beta - \alpha + w\|_2^2

= \min_\beta \frac 12 \beta^T X^T X \beta - y^T X \beta + \frac \rho 2 \beta ^T \beta - \rho (\alpha - w )^T \beta

让式子对

\beta

求梯度可以得到

(X^T X + \rho I) \beta - X^T y - \rho (\alpha - w) = 0

（见《数值优化》第1节（数值优化（1）——引入，线搜索：步长选取条件））因此不难得到

\beta^{(k)}

的更新公式，只需要代入

\alpha^{(k - 1)}, w^{(k - 1)}

即可。

得到

\beta

的更新公式之后，我们可以针对

\alpha

优化，也就是考虑问题

\min _\alpha \frac \lambda \rho \|\alpha \|_1 + \frac 1 2 \| \beta - \alpha + w\|_2^2

这个其实就是近端梯度法（《凸优化》第4节（凸优化（4）——次梯度案例，加速梯度法，随机梯度下降法，近端梯度法引入）Example 2）中的软阈值算子。因此对比一下公式也可以很轻松得到结论。

两个式子都得到了，那么我们看一下最终的迭代公式，其实就是

\beta^{(k)} = (X^TX + \rho I)^{-1} (X^T y + \rho (\alpha^{(k - 1)} - w^{(k - 1)}))

\alpha^{(k)} = S_{\frac \lambda \rho}(\beta^{(k)} + w^{(k - 1)})

w^{(k)} = w^{(k - 1)} + \beta^{(k )} - \alpha^{(k)}

还是要强调一下，第二步迭代的时候，

\beta

最新的迭代值就要用上了。

下一张图是ADMM对于不同的

\rho

，针对LASSO问题所做的数值实验。可以看出ADMM的速度其实并不是特别快的。不过考虑到它所适用的场景比较多，因此速度稍微慢一些倒也不是不能忍受。

接下来来看一些更加偏线性代数的一些例子。

Example 3: Sparse Subspace Estimation （Source：CMU）考虑问题

\max _Y \operatorname{tr}(SY) - \lambda \|Y \|_1, s.t. \quad Y \in \mathcal {F}_k

，其中

\mathcal F_k = \{Y \in \mathbb S^p: 0 \preceq Y \preceq I, \operatorname{tr}(Y) = k\}

，

是原数据矩阵的相关阵

X^TX

。

这个问题就是Source中的Vu et al. (2013)那篇论文中重点研究的问题，但我们要说的是它其实非常像稀疏PCA，因为当

\lambda = 0

的时候，这个问题的解和PCA降维后的解是等价的。这个可以见Source的Fan (1949)，我们这里就不详谈了。

对于这个问题，转换的思路也是很相似的，首先把问题的形式写成

\min_{Y, Z} - \operatorname{tr}(SY) + I_{\mathcal F_{k}}(Y) + \lambda \|Z \|_1

s.t. \quad Y = Z

可以看出其实就是把原问题的符号换了一下，然后再把两项中其中一个的

换成了

。

那么这样的话，我们可以写出这个问题的增强拉格朗日函数，得到

L_\rho = - \operatorname{tr}(SY) + I_{\mathcal F_{k}}(Y) + \lambda \|Z \|_1+ \frac \rho 2 \| Y - Z + W\|_2^2 - \frac \rho 2 \| W \|_2^2

这是一个关于

Y, Z

的函数，我们先看

。其实求解

，对应的就是优化问题

\min_Y -tr(SY) + I_{\mathcal F _k}(Y) + \frac \rho 2 \|Y - Z + W \|_2^2

考虑求解它的次梯度，可以得到

0 \in -S + N_{\mathcal {F}_k}(Y) + \rho(Y - Z + W)

（注意

是对称的）也就是

Y \in \frac S \rho + Z - W - N_\mathcal{F_k}(Y)

。这里回忆一下正规锥的定义是

\mathcal{N}_C(x) = \{g \in \mathbb {R}^n: g^T(x - y) \ge 0 , \forall y \in C\}

但是在这里

是一个矩阵（而且是一个对称阵），所以条件就会变成

\operatorname{tr}(G^T (X - Y)) \ge 0, \forall Y \in \mathcal{F}_k

。这是因为在向量情况下，我们有这是因为在向量情况下，我们有，但是在矩阵的情况下，式子会变成。至于具体的这个次梯度的，可以查看《凸优化》的第3节。

凸优化（3）——梯度与次梯度：方法，性质与比较

这个问题要求解，对矩阵论的知识要求就很高了。我尝试着手推了一下并没有成功的在去游珠江之前得到一个完整的思路……所以我们这里会直接给出答案，就不给过程了。

对于

的求解就简单得多，因为我们已经碰到过多次这种问题的求解，所以综合一下就可以得到

Y^{(k)} = P_{\mathcal F_k}(Z^{(k - 1)} - W^{(k - 1)} + \frac S \rho)

Z^{(k)} = S_{\frac \lambda \rho}(Y^{(k)} + W^{(k - 1)})

W^{(k)} = W^{(k - 1)} + Y^{(k)} - Z^{(k)}

这里的

P_{\mathcal F_k}

被称作Fantope投影算子，如果

A = U \Sigma U^T

是对称矩阵的奇异值分解，并且

\Sigma = \operatorname{diag}(\sigma_1, \ldots, \sigma_p)

，那么我们有

P_\mathcal{F_k}(A) = U \Sigma_\theta U^T, \Sigma_\theta = \operatorname{diag}(\sigma_1(\theta), \ldots, \sigma_p(\theta))

其中

\sigma_i(\theta) = \min \{\max \{\sigma_i - \theta , 0\}, 1\}

，并且

\sum_{i = 1}^p \sigma_i (\theta) = k

。如果有会求解这个问题的人，欢迎在评论区留下你的足迹！

Example 4: Sparse + Low Rank Decomposition （Source：CMU）设

M \in \mathbb R^{n \times m}

，考虑问题

\min_{L, S} \|L \|_{\operatorname{tr}} + \lambda \|S \|_1

，

s.t. \quad L + S = M

对于这个问题，我们可以写出它的增强拉格朗日函数，也就是

\mathcal L_\rho = \|L \|_{\operatorname{tr}} + \lambda \|S \|_1 + \frac \rho 2 \| L + S - M + W\|_2^2 - \frac \rho 2 \| W \|_2^2

这里因为符号的冲突，我们临时把拉格朗日函数的符号从

L_\rho

改成了

\mathcal{L}_\rho

。

那么这个时候，我们可以通过类似的方法来求得ADMM的更新公式

L^{(k)} = S_{1/\rho}^{\operatorname{tr}} (M - S^{(k - 1)} + W^{(k - 1)})

S^{(k)} = S_{\lambda/ \rho}^{l_1}(M - L^{(k)} + W^{(k - 1)})

W^{(k)} = W^{(k - 1)} + M - L^{(k)} - S^{(k)}

那么这里其实有两个算子，它们俩的本质当然都是软阈值算子，但是一个是针对矩阵的，一个是针对向量的，因此作用的方式有些不同。至于为什么是这两个算子，可以认为矩阵的迹算子和向量的1-范数的作用其实是等价的。所以它们俩对应的结果也具有很大的相似性。

Example 5: 2d-fused LASSO 考虑

Y \in \mathbb R^{d \times d}

，考虑问题

\min_\Theta \frac12 \|Y - \Theta \|_F^2 + \lambda \sum_{i, j} (|\Theta_{i,j} - \Theta_{i+1, j} | + |\Theta_{i,j} - \Theta_{i, j + 1 }|)

，可以等价将其写成

y \in \mathbb R ^n

，问题也可以转换成

\min_\theta \frac12 \|y - \theta \|_2^2 + \lambda \|D \theta \|_1

，考虑对此问题的ADMM解决方案。

我们在《凸优化》的第1节（凸优化（1）——引入，优化实例分析，凸集举例与相关性质）有举过这个例子。这个问题的应用就是图像处理，也就相当于考虑一个

d \times d

的一个像素矩阵。而我们这个问题其实很明显，就是做一个降噪的过程。就像LASSO中，不重要的特征会被筛掉一样，在这里我们加了两项1-范数，表示是其实也是一样的作用——把图像中不重要的像素点抹掉。比方说一张拍的比较好的照片，可能会被污染，或者可能因为镜片太脏导致相片比较难看，模糊等等，都可以通过降噪来复原原始的相片，或提高相片的质量。当然这里的1-范数的形式是有讲究的，我们取的是相邻像素点的差，因此如果

\lambda

很大，那么对应的得到的

\Theta

就会显得比较粗糙一些（因为不允许值发生太大的变化）。这里的2-d的含义也很明显，注意到两个罚项分别是针对

坐标和

坐标来做的。

当然了，大家都比较容易发现这是一个无约束优化问题。因此如果要使用ADMM，必然是需要把它转换成带约束优化问题的。但如何转换呢？这里有两种思路。第一，可以考虑设

\theta = Dz

，把问题变为

\min_{\theta, z} \frac 12 \| y - \theta \|_2^2 + \lambda \|z \|_1

s.t. \quad \theta = D z

这样的话可以把ADMM的迭代公式写成

\theta^{(k)} = (I + \rho D^T D)^{-1}(y+ \rho D^T (z^{(k - 1)} + w^{(k - 1)}))

z^{(k)} = S_{\lambda / \rho}(D \theta^{(k)} - w^{(k - 1)})

w^{(k)} = w^{(k - 1)} + z^{(k - 1)} - D \theta^{(k)}

但是其实我们还可以把

\Theta

拆成两份，变为

H, V

两个。也就是说问题也可以写成

\min_{H, V} \frac 12 \|Y - H \|_F^2 + \lambda \sum_{i, j} (|H_{i,j } - H_{i + 1, j}| + |V_{i, j} - V_{i, j+ 1}|)

s.t. \quad H = V

这也可以得到一个ADMM的更新公式

H_{\cdot, j}^{(k)} = \operatorname{FL}_{\lambda / (1 + \rho)}^{1d} \left(\frac {Y + \rho (V_{\cdot, j}^{(k - 1)} - W_{\cdot, j}^{(k - 1)})}{1 + \rho}\right), j = 1, \ldots, d

V_{i, \cdot}^{(k)} = \operatorname{FL}_{\lambda / \rho}^{1d}(H_{i, \cdot}^{(k)} + W_{i, \cdot}^{(k - 1)}), i = 1, \ldots, d

W^{(k)} = W^{(k - 1)} + H^{(k)}-V^{(k)}

这里要注意的是

是一列一列更新，而

是一行一行更新的。这里的算子的含义是

\operatorname{FL}_\tau^{1d}(a) = \arg\min_x \frac 12 \|a - x \|_2^2 + \tau \sum_{i = 1}^{d- 1} |x_i - x_{i + 1}|

可以看出其实就是一维情况下的降噪。当然为什么跑出这个结果，我们就不推了，感兴趣的可以自己试试233。

这里的两种方法对应跑出来的结果怎么样呢？我们可以看一下下面的图以及实际的效果

这里的Standard就是第一种，Specialized就是第二种，可以看出总体上，第二种是占优的（这里要强调的是，两种方法的每一步的迭代速度其实是接近的，但这个推导不是很容易，我们这里不详谈）。为什么呢？我们可以看到，第一种方法就是把所有的关于罚项的信息都聚合成一个矩阵

。但是第二种方法它的处理方法相当于把一个2d问题拆成了2个1d问题。这样的话，从直觉上来说，它在两个方向分别做了好的优化，有点像之前提到的坐标下降法（见《凸优化》第A节（凸优化（A）——坐标下降法，对偶上升法，再看增强拉格朗日法））。所以这个问题也说明了，对于问题的不同处理方式，会导致不同效率的算法，至于什么样的算法才是最好的，恐怕也是很多科研人员需要解决的问题。

好的，关于ADMM，我们就说这么多。

Frank-Wolfe方法

这应该是我们这一个系列要介绍的最后几个算法之一了，也是一个比较新的，我自己之前都没听过的一个算法。这个算法因为是Frank和Wolfe两个人设计的，所以起名叫这个算法，我们后面会用FW算法作为简称。但其实它还有个说法叫作条件梯度方法（Conditional Gradient Method），但因为起这个名字的动机不明确，所以我们没有采用这个名字。

这个算法设计出来是为了解决梯度投影法的一个问题，梯度投影法的介绍可以见《数值优化》的第8节（数值优化（8）——带约束优化：引入，梯度投影法），也就是说我们考虑的问题是

\min_x f(x)

s.t. \quad x \in C

我们回忆一下，梯度投影法的迭代公式为

x^{(k)} = P_C(x^{(k - 1)} - t_k \nabla f(x^{(k - 1)}))

它是近端梯度法的一个特例，而内部的更新公式其实就是梯度下降法，所以我们可以把它等价的写成这样

x^{(k)} = P_C(\arg\min_y \nabla f(x^{(k - 1)})^T (y - x^{(k - 1)}) + \frac 1 {2t} \|y - x^{(k - 1)}\|_2^2)

这里就会遇到一个问题，就是投影算子一般情况下都是不好求的。那怎么办呢？FW算法做的事情，概括一下有两点

改成线性近似
去掉投影算子，改成带约束优化问题求解。

去掉投影算子大概是最大胆的一步：既然算不出来，那就不算了。那么改成线性近似，其实就是去掉

\frac 1 {2t} \|y - x^{(k - 1)}\|_2^2

这一项，而改成带约束优化问题，其实就是把内部的优化问题加上约束

y \in C

，因此如果我们再去掉与优化变量

无关的项，我们就可以得到最终的FW方法所考虑的核心步骤

y^{(k -1)} \in \arg\min_{y \in C} \nabla f(x^{(k - 1)})^T y

但是这么改又出问题了，步长的元素因为在二阶近似中，所以被抹掉了。所以我们实际上是得到了一个“可能的下一步迭代点”，所以还需要再更新一下，也就是说

x^{(k)} = x^{(k - 1)} + \gamma_k (y^{(k - 1)} - x^{(k - 1)})

这个

\gamma_k

就是步长，一个常见的取法是

\gamma_k = \frac 2 {k + 1}

也就是说，迭代越往后，走的步伐就越小。

这里要注意的是，对于凸问题而言，新的点一定是在

内的，因为我们可以把这个迭代公式写成

x^{(k)} = (1 - \gamma_k) x^{(k - 1)} + \gamma_k y^{(k - 1)}

所以根据凸集的定义就可以得到这个结论。这个结论直接告诉我们说，FW方法是不需要额外的投影算子的。因为投影算子的目的就是把可能“出界”的点给“拉”回来，但是这里每一步的迭代点都一定是在可行域

内的，那自然不需要这一步了。

好的，我们来看几个这个方法应用的例子。

Example 1: 考虑约束

C = \{x: \|x \| \le t\}

对应的FW方法的更新公式。

对于这个问题，最关键的便是怎么去取那个

。也就是要求解问题

y \in \arg\min_{\|s \| \le t}\nabla f(x^{(k - 1)})^T s = -t (\arg\max_{\|s \| \le 1}\nabla f(x^{(k - 1)})^T s)

这里我们要用一个结论。当然这个结论的证明还是有点复杂的，我们以后找个时间可以单独说一下，但这里就不详谈了。

Lemma 1: 设

f(x) = \|x \| = \max_{\|z \|_* \le 1} z^T x

，那么

\partial f(x) = \arg\max_{\|z\|_* \le 1} z^T x

是它的次微分。

把这个结论代进去，我们就可以得到

y \in -t \partial \| \nabla f(x^{(k - 1)}) \|_*

换句话说，对于范数球的约束，求解迭代的“可能的下一个点”其实就等价于求解对偶范数。这一般来说都是比求投影算子要容易很多的。

比方说如果是

\|x \|_1 \le t

，那么这个时候方向就是

y \in -t \partial \|\nabla f(x^{(k - 1)})\|_\infty

，一个向量的无穷大范数其实就是向量的最大的取过绝对值后的元素，所以我们自然可以得到下面的更新公式

i_{k - 1} \in \arg\max_{i = 1, \ldots, p} | \nabla _i f(x^{(k - 1)})|

x^{(k)} = (1 - \gamma _k) x^{(k - 1)} - \gamma_k t \cdot \operatorname{sign} (\nabla _{i_{k - 1}} f(x^{(k - 1)})) \cdot e_{i_{k - 1}}

FW方法比较多的会和近端梯度方法联系到一起。这主要是因为，在一般的

t > 0

的情况下，问题

\min_x f(x)

s.t. \quad \|x \| \le t

和拉格朗日函数问题

\min_x f(x) + \lambda \|x \|

其实是等价的。第一个带约束优化问题就是FW方法解决的问题，第二个问题就是近端梯度方法可以解决的问题。对于

l_1

范数的这个问题，我们在这一节也多次提到过，它最终就是归于一个软阈值算子。对于它的计算，其实复杂度和FW方法得到的更新公式是差不多的。但是对于一般的

l_p

范数，或者说迹范数，一般来说计算的复杂度都会比近端梯度方法要容易不少。

下面是一个

n = 100, p = 500

的一个LASSO问题的数值实验，可以看出，相比较一般的梯度投影法，其实条件梯度法（也就是FW方法）的效果会差一些。这一点也比较好理解，因为FW算法相比较梯度投影法而言，做了两步比较大的计算的简化，使得问题的应用范围得到了拓宽，也就一定程度上牺牲了效率。

按照道理来说这个时候我们应该谈一谈收敛性分析，但在这之前，我们希望说一下这个方法的一个独特的优势，就是它有一个比较好的对偶间隔。这也就是下一个性质。

Proposition 1: 证明

\nabla f(x^{(k)})^T (x^{(k)} - y^{(k)})

是一个合适的对偶间隔。

回顾一下，使用对偶间隔的目的就是为了好估计函数的收敛，具体的可以见《凸优化》第6节

凸优化（6）——对偶性：案例分析，强弱对偶性及理解，再看KKT条件

麻烦你给我翻译翻译，什么叫“合适的”对偶间隔？自然的，需要它能够比较好的估计函数的迭代值。那么在这之前，我们先解释说，为什么这和对偶间隔有关系？因为注意到问题其实等价于

\min_x f(x) + I_C(x)

那么利用我们在《凸优化》第7节（凸优化（7）——对偶性延伸：对偶范数，共轭函数，双对偶；再看牛顿法）讲到的共轭函数求解对偶问题的相关的知识，我们可以得到它的对偶问题

\max_u -f^*(u)- I_C^*(-u)

所以我们可以给出它的一般的对偶间隔，也即

f(x) + f^*(u) + I_C^*(-u)

，那么根据Fenchel不等式（《凸优化》第7节的Proposition 2），可以得到

f(x) + f^*(u) + I_C^*(-u) \ge x^T u + I_C^*(-u)

代入

x = x^{(k)}

，

u = \nabla f(x^{(k)})

，我们可以得到右边的式子其实就是

\nabla f(x^{(k)})^T x^{(k)} + \max_{y \in C} -\nabla f(x^{(k)})^T y = \nabla f(x^{(k)}) (x^{(k)} - y^{(k)})

这就是我们之前说的式子。换句话说，这个对偶范数的提出并不是空穴来风，当然发现它确实是一个挺难的事情……

那么我们现在给出说明它“合适”的证明吧。这个证明不难，注意到函数

是凸函数（毕竟要解决凸问题嘛），所以有一阶条件

f(y) \ge f(x^{(k)}) + \nabla f(x^{(k)})^T (y - x^{(k)})

两边取

s \in C

的最小值，可以得到

f(x^*) \ge f(x^{(k)}) + \min_{y \in C} \nabla f(x^{(k)})^T (y - x^{(k)}) = f(x^{(k)}) + \nabla f(x^{(k)})^T(y^{(k)} - x^{(k)})

移项就可以了。

还差一些关于FW的方法的内容，考虑到字数的API到了，我们就放到下一节再说吧。

小结

这一节我们主要在介绍ADMM和FW方法的应用，对于理论性质介绍的不是很多。这也是因为这两个方法也是目前较流行，也较新的方法，还是有很多的研究的可能。当然了碍于字数，我们没有在这一节说完FW方法的所有内容。在下一节我们会补充完，并介绍一些其它的新的算法。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-10-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度