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

学弱猹

发布于 2021-08-09 17:32:57

1.2K0

发布于 2021-08-09 17:32:57

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

上一节笔记：凸优化（8）——内点法中的屏障法与原始-对偶方法，近端牛顿方法

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

大家好！熟悉我的写作风格的人都知道，这里A就是10的意思。

这一节我们会开始介绍一些比较高端的算法，这里的“高端”也即在当今用的多，流行，但理论不完备的一些算法，这些算法多出现在统计，人工智能等当今大火的领域，但对于传统的应用数学与计算数学来说，说它们是“新方法”是很确切的。比方说这一节我们会先介绍坐标下降法（Coordinate Descent），如果有空则还会介绍一下对偶上升法（Dual Ascent）。

那么我们开始吧。

Source

A. Beck and L. Tetruashvili (2013), On the convergence of block coordinate descent type methods
X. Li, T. Zhao, R. Arora, H. Liu, M. Hong (2016), An improved convergence analysis of cyclic block coordinate descent-type methdos for strongly convex minimization
R. Sun, M. Hong (2015), Improved iteration complexity bounds of cyclic block coordinate descent for convex problems
S. Wright (2015), Coordinate Descent Algorithms
CMU 10-725, Convex Optimization
Boyd, Vandenberghe, Convex Optimization

坐标下降法

坐标下降法（Coordinate Descent）是一个非常容易让人顾名思义的方法。没有错，它考虑的就是这么一个问题：如果函数在每一个维度上都达到了极小值，能否保证函数已经找到了极小值点？如果写成数学式子，就是

\forall \delta, f(x + \delta e_i) \ge f(x) \to f(x) = \min_z f(z)

这里

e_i

是一个仅仅只有第

维为1，其余维度均为0的一个列向量。

要解决这个问题，很显然需要对函数做一些限制，如果我们函数是凸并且光滑的，那么很好办了。假如说第

维上达到了极小值，并且对应的自变量值为

x^*

，这就说明

\frac {\partial f}{\partial x_i}(x^*) = 0

，那么每一个维度都满足这个要求，就说明

\nabla f(x) = 0

，在函数凸的情况下这当然是一个极小值点，也就是说这个推断是没问题的。

但是如果说函数没有光滑性，但是有凸性，这可不可以呢？答案是否定的。这确实挺难想的，不过如果我们考虑二维的简单情况，并且简单的画画图，我们能看出这一点。

可以看出当我们画出指定点对应的函数等高线时，让它往左右走一点，或者往上下走一点，都会导致函数值的增大（红线所画定的方向），而这就覆盖了所能走的所有方向，也就是说它确确实实满足“任意一个维度上都达到了极小值”这个条件。但是很明显它并不是一个极小值点，蓝色点对应的才是极小值点。

凸性如果没有，就变成了一个非凸优化问题，那自然不可能是我们“凸”优化讨论的范围。但是目前的讨论看来，难道光滑性是一个必要条件？当然也不是，事实上，对于一种特殊的情况

f(x) = g(x) + \sum_{i = 1}^n h_i(x_i)

也即

可以拆分成两个函数

g, h

，其中

是凸函数并且光滑，

可以继续拆分为

h_1, \ldots, h_n

（

是

的维数），并且每一个

h_i

都是凸函数（有的地方会说

是可分的）。在这种情况下，我们是可以导出这个结论的，但稍微需要一些技巧。

注意到根据条件，我们有

f(y) - f(x) \ge \nabla g(x)^T (y - x) + \sum_{i = 1}^n [h_i (y_i) - h_i (x_i)]

= \sum_{i = 1}^n [\nabla_i g(x) (y_i - x_i) + h_i(y_i) - h_i(x_i)] \ge 0

最后一个不等式是为什么？根据条件，在每一个维度上可以取到极小值，所以其实只需要根据次梯度的一阶最优性条件，就可以得到

0 \in \nabla _i g(x) + \partial h_i (x_i)

也就是说

-\nabla_i g(x)

是

h_i(x_i)

的一个次梯度，那么根据次梯度定义，自然会有

h_i(y_i) \ge h_i(x_i) - \nabla_i g(x)^T (y_i - x_i)

移项一下就可以得到结论。

上面这几个例子事实上就说明了，如果我们在每一个维度下都优化到最好，对于某些情况是可以认为优化问题已经解决的，这也就是坐标下降法可被应用的理论基础。而对于坐标下降法，一般来说采用的迭代方式是

x_i^{(k)} = \arg\min_{x_i} f(x_1^{(k)} , \ldots, x_{i - 1}^{(k)}, x_i, x_{i + 1}^{(k - 1)} , \ldots, x_n^{(k - 1)})

这里

按照

1, 2, \ldots, n

这样的顺序枚举下去，当然也可以乱序，不过一定要保证一轮不重复的遍历完每一个维度。这个迭代公式的意思也即每一轮迭代，都在每一个维度下优化到最好。

这里要注意的一个关键的地方在于：无论采用什么方式枚举维度，都要采用最新的信息。比方说这里我们会发现，在对第

个维度进行迭代的时候，前

i - 1

个维度都已经更新完毕了，所以可以发现在进行迭代的时候，前

i-1

个维度采用的都是最新的值，也即第

步的迭代值。

至于为什么要使用这样的方式，只能说实操中，如果我们不立刻更新，而是先把每一个维度迭代完，再一起更新，那样的话很多时候算法是不收敛的。这个想法可以和数值分析中，解线性方程组的Jacobi方法与Gauss-Seidel方法作类比。不过不知道的话也没关系，就当我在说废话就好233。

下面这一张图给出了解一个

n = 100, p = 20

（

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

为数据矩阵）的线性回归问题时，不同方法对应的迭代步数（注意坐标下降法必须把所有的维度都更新完，才算是一次迭代完成）。总体来说坐标下降法相比较其它方法而言，还是有一定优势的。

当然了这个问题可以用坐标下降法求解，也是因为它本身就是一个凸且光滑的问题。

说到这里有的人可能要问一个比较刁钻的问题，即坐标下降法这种需要对每一个维度进行迭代的方式，在计算迭代次数的时候会不会吃亏，因为看上去，要完成一步迭代，正常的算法做一次更新就可以了，但是对于坐标下降法，则需要很多次，如果数据的维度很大的话。但事实上是不会的，如果运算都比较得当的话。解释这个正好可以用上上一节所说的知识，我们不妨用线性回归的例子来看下。

线性回归问题一般可以写成

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

现在考虑一下坐标下降法。既然要在每一个维度都取到极小值，其实就是要求

\nabla_i f(\beta) = 0

，而这很简单，就是

X_i^T (X \beta - y) = 0

（可以通过《数值优化》第1节（数值优化（1）——引入，线搜索：步长选取条件）来计算出完整的梯度，再根据线性代数的知识得到某一个维度的表达式）。那么因为需要知道

\beta_i

（这里表示**

\beta

的第

个分量**）的更新公式，我们自然需要把

\beta_i

拆出来，也即

X \beta = X_i \beta_i + X_{-i} \beta_{-i}

这里

X_{-i}

即把

的第

列去掉，保证其它列的相对顺序不变的新的矩阵，

\beta_{-i}

也可以类似的理解。所以得到这个之后，就可以得到更新公式

\beta_i = \frac{X_i^T (y - X_{-i} \beta_{-i})}{X_i^T X_i} = \frac{X^T r}{\|X_i \|_2^2} + \beta_i

这里

r - y - X \beta

。对于一般的迭代方法，我们不妨用梯度下降法来看看。梯度下降法的更新公式是

\beta^{k + 1} = \beta^k + t X^T ( y - X \beta)

当然要提醒一下，这里的

\beta^k

表示第

步的迭代结果，不是求次幂的运算。

既然要分析两种迭代方案的运算时间，自然需要看一下运算顺序。对于梯度下降法，我们可以先计算

X \beta

，再计算

y - X \beta

，再计算

X^T (y - X \beta)

，这样的话是一个

O(np)

的复杂度（我算出来大概是

4np

）。那么再看一下坐标下降法的更新公式，可以看出需要先更新

，再计算

X_i^T r

，是一个

O(n)

的复杂度，而且差不多也是

的浮点数运算次数。

这里有两个要注意的地方，一是有的人会问这一项为什么不计算，这是因为这是数据矩阵的信息，是不变的，因此是可以事先计算好存储在计算机里的。二是为什么更新

只需要

O(n)

的时间复杂度，这是因为下一步相对上一步来说，对于

的更新只会影响

X_i

和

\beta_i

，因此可以推导出一个更新公式，使得更新的步骤在

O(n)

的时间内完成，而不需要每一次都重新计算

r= y- X\beta

。

所以既然坐标下降法每一个维度只需要约

次运算，那么一共

个维度的话，就是

4np

次运算。可以看出它和梯度下降法的运算次数其实是一样的，如果不考虑非常细微的小量的话。

接下来我们再看一个机器学习的例子。

Example 1: SVM dual（Source：CMU）给定

y \in \{-1, 1\}^n, X \in \mathbb{R}^ {n \times p}

，那么考虑SVM问题 \min_{\beta, \beta_0, \xi} \frac 12 |\beta|2^2 + C \sum{i = 1}^ n \xi_i

s.t. \quad \xi_i \ge 0, i = 1, \ldots, n

y_i(x_i^T \beta + \beta_0) \ge 1 - \xi_i, i = 1, \ldots, n

那么如果说

\tilde X = \operatorname{diag}(y) X

，那么它的对偶问题可以写成

\min_{\alpha} \frac 12 \alpha^T \tilde X \tilde X^T \alpha - 1^T \alpha

s.t. \quad 0 \le \alpha \le C, \alpha^T y = 0

考虑求解此对偶问题的算法。

关于如何求对偶问题，我们这里不详谈，大家可以用之前教的技巧，也可以考虑b站上我录的《手把手教会机器学习与数据挖掘理论》上面的内容。

https://www.bilibili.com/video/BV1ZK4y1b7Xt/

这里所采用的是序列最小化算法（Sequential Minimal Optimization, SMO），这个算法主要用在对偶问题这种二次问题上，它的本质就是坐标下降法。

注意到这个问题的互补松弛条件为

\alpha_i ( 1 - \xi_i - (\tilde X \beta)_i - y_i \beta_0) = 0, i = 1, \ldots, n

(C - \alpha_i) \xi_i = 0, i =1 , \ldots, n

同时这个问题满足强对偶性，所以只要约束条件满足这些等式，就可以认为找到了极小值和对应的极小值点，因为

\beta = \tilde X^T \alpha

。

那么如何优化呢？这里的思路很有趣，即每一次挑选不满足互补松弛条件的两个变量

\alpha_i, \alpha_j

，然后固定其它变量为常数，这样的话可以把问题变成一个在一条线段上求解一个二次函数的极小值问题。这个具体可以参考Source中的Platt (1998)。所以它其实对应的这种“每一次只优化部分变量”的思想，就恰好对应上了坐标下降法的核心思想。

当然了，这个东西的收敛性其实是不保证的，毕竟对偶问题并不是我们之前说的形式。因此很多时候，其实还需要做一些其它的处理。因此我们这里也只是简单的介绍一下SMO算法的本质，更多的细节还是要看一下其它相关的paper。

当然了，我们在《数值优化》第B节（数值优化（B）——二次规划（上）：Schur补方法，零空间法，激活集方法）提到过二次规划中的激活集法，这个方法的本质其实也是坐标下降法，感兴趣的可以把两个方法的思想对比一下，相信也不难看出来。

最后对于这个算法，我们简单提一下它的收敛性分析。但是其实对于这个算法，它的具体的理论依然是不完备的。Source里列了几篇关于它的收敛性分析的一些paper，例如Beck (2013)，Wright (2015)，Sun, Hong (2015)和Li et al. （2016），感兴趣的可以去看一看。

最后总结一下，对于坐标下降法，它实操比较方便，同时在某些情况下，优化的效果也都还不错。一个例子是，这个算法对于诸如二次函数+可分凸函数的形式（比如二次规划的问题），是可以得到比较好的收敛速度的。当然了很多时候的问题虽然不是二次问题，但是可以通过一些变换来把它转成二次问题。不过这就是非常精细的，需要具体问题具体分析的内容，我们这里也就不详谈了。

这个算法其实还有一些其它的延伸。比方说我们可以考虑下面的迭代公式

x_i^{(k)} = x_i^{(k - 1)} - t_{ki} \nabla_i f(x_1^{(k)}, \ldots, x_{i - 1}^{(k)}, x_i , x_{i + 1}^{(k - 1)}, \ldots, x_n^{(k -1)})

可以看出它结合了坐标下降法和梯度下降法，所以它就是坐标梯度下降法（Coordinate Gradient Descent），这个算法只要

是光滑的时候就可以使用。

同样的，我们也可以写出这样的迭代公式

x_i^{(k)} = \operatorname{prox}_{h_i, t_{ki}}(x_i^{(k - 1)} - t_{ki} \nabla_i f(x_1^{(k)}, \ldots, x_{i - 1}^{(k)}, x_i , x_{i + 1}^{(k - 1)}, \ldots, x_n^{(k -1)}))

类似的思路，我们可以称它为坐标近端梯度下降法（Coordinate Proximal Gradient Descent）。只要

f = g + h

满足近端梯度法的要求，并且

是可分的，那么这个方法就是可以使用的。

好的，那么关于坐标下降法，我们就说这么多。

对偶上升法

对偶上升法（Dual Ascent）也是一个比较现代化的优化算法。它的重点在于两个词：对偶和上升。一般的优化问题都是解一个极小值的问题，为了得到极小值我们会希望每一次迭代得到的函数值都要比上一次迭代得到的要更小。但是注意到，如果对原问题求它的对偶问题，这个问题就变成了一个极大值问题，因此如果我们求解对偶问题，我们就希望迭代中，每一步的函数值都要比上一步要大，这就是“对偶上升”的含义。

回顾一下，假如说我们的问题是

\min_x f(x)

s.t. \quad Ax = b

那么它的对偶问题就是

\max_u -f^* (-A^T u) - b^T u

这里的

就是对偶变量，当然了它也是一个向量。回顾一下，

f^*

就是

的共轭函数，这可以把一个带约束优化问题转变为无约束的优化问题，我们在《凸优化》第7节（凸优化（7）——对偶性延伸：对偶范数，共轭函数，双对偶；再看牛顿法）有说过这个转换。

如果我们采用梯度下降法的设置，那么这个时候，设

g(u) = - f^*(-A^T u) - b^T u

，我们自然是需要求解

\partial g(u)

，然后以正次梯度，而不是负次梯度作为迭代的搜索方向。那么注意到我们有

\partial g(u) = A \partial f^* (-A^T u) - b

（这里涉及到次梯度运算的一个线性变换法则，即如何计算

f(Ax)

关于

的次梯度。走定义很容易验证结果）所以实际上，我们的关键就是在于

\partial f^*(-A^T u)

怎么求解。

注意到，根据

f^*(-A^T u) = \min_z f(z) - z^T (-A^T u)

，就可以得到，如果

x \in \partial f^*(-A^T u)

，就会有

x \in \arg \min_z f(z) + u^T Az

（想想为什么？）所以给定

，我们如果能够找到一个符合条件的

，那么

\partial g(u) = Ax - b

就是一个合适的上升方向，因此对于一般的对偶上升问题，它的更新公式就是

x^{(k)} \in \arg\min_x f(x) + (u^{(k - 1)})^T A x

u^{(k)} = u^{(k - 1)} + t_k (Ax^{(k)} - b)

这里的

t_k

为步长。

可以看出，虽然我们的对偶问题本身是依赖于共轭函数的，但是最终的更新公式告诉我们，其实我们并不需要知道对偶问题的形式，也可以使用对偶上升法。

当然了，如果对偶问题具备了光滑性，那么就不再需要依赖一般的次梯度了，直接算梯度就好。体现在更新公式中，就是把第一个式子的

\in

改成

就对了。

接下来我们来看一下它的收敛性分析，我们先给出它们的结果，再来回头分析这个方法的利弊。

Theorem 1: 如果

强凸，且凸性量度为

，那么取

t_k = m

可以让方法以次线性收敛速度（

O(\frac 1\epsilon)

）收敛。 Theorem 2: 如果

强凸，且

\nabla f(x)

Lipschitz连续，且对应常数为

。那么如果取

t_k = \frac {2}{\frac 1m + \frac 1L}

，可以让方法以线性收敛速度（

O(\log \frac 1 \epsilon)

）收敛。

虽然给出了两个结果，但也可以看出这两个结果所要求的条件都不低。这也便是对偶上升法的一个麻烦：收敛所需要的条件往往很难满足。出现这个情况倒也不难理解，毕竟对偶问题能够给原问题的性质带来多大变化，其实是一个还没摸清楚的东西。

但回到这两个定理来说，其实它们的支柱在于下面的这个性质。

Proposition 1: 设

是一个闭且凸的函数，那么

强凸且凸性量度为

等价于

\nabla f^*

Lipschitz连续且常数为

\frac 1 m

。

我们证明一下这个结论。现在假如说

是强凸函数，那么首先的话我们要使用一个强凸性的结论，也即

\forall y, g(y) \ge g(x) + \frac m 2 \|y - x\|_2^2

这个结论可以参考《凸优化》第2节（凸优化（2）——凸函数，强凸函数及相关拓展）最后关于强凸性的一系列等价条件中的最后一条。

那么现在既然我们希望得到

\nabla f^*(x)

的结论，我们自然需要考虑

g_u(x) = f(x) - u^T x

这个函数，这个函数保持了强凸性，并且它是共轭函数的源头。

如果我们希望求它的极小值，那么自然需要梯度为0，也就是

\nabla f(x) = u

。所以如果说

x_u

是它的一个极小值点，那么

\nabla f(x_u) = u

。

关键的一步来了，注意到

凸且闭，所以根据《凸优化》第7节（链接见前）的Proposition 4，我们可以得到

\nabla f^*(u) = x_u

这里理解的关键是性质中的

y \in \partial f(x) \Leftrightarrow x \in \partial f^*(y)

如果说函数是光滑的，那么其实从左到右，就是作用了一个算子

\nabla f^*

，潜在的意思就是

\nabla f^* = \nabla f^{-1}

。

所以类似的我们可以设

x_v = \nabla f^*(v)

，这样的话就可以得到下面两个不等式

f(x_v) - u^T x_v \ge f(x_u) - u^T x_u + \frac m 2 \|x _u - x_v \|_2^2

f(x_u) - v^T x_u \ge f(x_v) - v^T x_v + \frac m 2 \|x _u - x_v \|_2^2

两个式子加在一起，就可以得到

(u - v)^T(x_u - x_v) \ge m\|x_u - x_v\|_2^2

再利用Cauchy不等式放缩一下左边即可。

另一方面，如果设

\nabla f^*

是Lipschitz连续的，且常数为

\frac 1 m

，那么设

g = f^*, L = \frac 1m

。我们的思路就是就是把上面的思路再反过来用。既然我们构造了一个共轭函数又得到了

x_u = \nabla f^*(u)

的结论，那么这里我们就设

g_x(z) = g(z) - \nabla g(x)^T z

。那么它依然保持了连续性，所以有

g_x(z) \le g_x(y) + \nabla g_x(y)^T (z - y) + \frac L 2 \|z - y \|_2^2

注意这是对

\forall z

都成立的一个式子，所以可以左边右边分别求式子的极小值，这个不等式依然是成立的（想想为什么？）。因此这样的话可以通过化简得到

\frac 1 {2L} \| \nabla g(x) - \nabla g(y) \|_2^2 \le g(y) - g(x) + \nabla g(x)^T ( x -y)

不过这个转换也是需要一些功夫的，留给读者当个小练习题吧。

再交换

x, y

，把两个式子加在一起，就可以得到

\frac 1 {L} \| \nabla g(x) - \nabla g(y) \|_2^2 \le (\nabla g(x) - \nabla g(y))^T ( x -y)

到这里似乎还看不出什么关联，但是要注意，如果我们设

u= \nabla g(x)

，可以得到

x \in \partial f(u)

（这是因为

f^{**} = f

，也是《凸优化》第7节的内容，如果看的不太清楚的话，拿

x = \nabla f(u)

代进去看看？）。那么实际上就可以得到一个结论为

(x - y)^T (u - v) \ge \frac{\|u - v \|_2^2 }{L} = m \|u - v \|_2^2

根据《凸优化》第2节的Proposition 4的第二个等价结论，就可以说明我们的结论成立。

我们花了一段篇幅来说明这个性质，也是为了解释强凸性，光滑性在原问题中所起到的作用。也就是说，

强凸对应的就是

\nabla f^*

光滑，因此对偶上升法的性态就对应梯度下降法中，梯度只有光滑性但函数没有强凸性的情况。如果

\nabla f

具备光滑性，那么对应的就是

f^*

具备强凸性的情况，所以这个时候对应了梯度下降法中，梯度有光滑性也有强凸性的情况，因此它们的收敛速度就很容易得到了。

对偶上升法的一个最重要的应用就是对偶分解法（Dual Decomposition），还是考虑一样的问题，但是这里

是可分的，也就是说问题可以写成

\min_x \sum_{i = 1}^B f_i(x_i)

s.t. \quad Ax = b

但是这里

x = (x_1, \ldots, x_B)

被划分成了

块，

x_i \in \mathbb R^{n_i}

，所以在这种情况下，约束

也可以对应的划分为

块，得到

A = [A_1, \ldots, A_B]

且

A_i \in \mathbb R^{m \times n_i}

，这里的

对应

的行数，意思就是约束问题具有

个约束。

这个时候，重要的是对偶上升法可以转化为

x^+ \in \arg\min_x \sum_{i = 1}^B f_i(x_i) + u^T A x \Leftrightarrow x_i^+ \in \arg\min_{x_i} f_i(x_i) + u^T A_i x_i, i = 1, \ldots, B

而我们的对偶上升法就可以改为

u^{(k)} = u^{(k -1)} + t_k (\sum_{i = 1}^B A_i x_i^{(k)} - b)

也就是说，首先把每一块都更新完，然后再加在一起，把数传送给

进行更新。所以如果说问题是可分的，那么实际上是可以把问题拆解为一些更小的问题的，这样的话至少在计算复杂度上会好很多。

最后关于对偶上升法，我们再简单提一下它在线性不等式约束下的应用。如果说约束变为

Ax \le b

，那么对偶上升法怎么用呢？这并不困难，因为相比较等式约束来说，对偶问题只是多了一个对偶可行性条件

u \ge 0

，因此其实只需要在

的更新时加一个保险就好，也即

u^{(k)} = [u^{(k - 1)} + t_k (Ax^{(k)} - b)]_+

也即时刻保证它的非负性。

好的，关于对偶上升法，我们就说到这里。

再看增强拉格朗日法

我们在《数值优化》第C节（数值优化（C）——二次规划（下）：内点法；现代优化：罚项法，ALM，ADMM；习题课）已经提到过增强拉格朗日法（Augmented Lagrange Method，ALM），但是在这里，我们的思路则不同，我们不再是通过罚项的思路来解释，而更多的是通过这种“对偶问题”的思路来重新看这些方法，相信也会有不一样的收获。

对偶上升法的劣势很明显，就是它的收敛性要有很强的条件保证。而增强拉格朗日法其实可以解决这个问题。我们在之前提过，增强拉格朗日法就是在求解这样的问题

\min_x f(x) + \frac \rho 2 \| A x - b \|_2^2

s.t \quad Ax = b

其中

\rho > 0

，这个出发点和《数值优化》里面提到的其实是不一样的，但是核心思想相同，都是多加一个类似罚项的东西。可以看出它这个问题是与原问题的解等价的，并且加了这一项之后，如果

是列满秩的，就可以发现这个目标函数是具备强凸性的，如果

本身就是凸函数的话。

那么对于这个问题，我们考虑使用对偶上升法求解，不难得到公式为

x^{(k)} = \arg\min_x f(x) + (u^{(k - 1)})^T A x + \frac \rho 2 \|A x - b \|_2^2

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

如果第二行的

\rho

是一般的

t_k

的话，那它和对偶上升法并没什么区别。但是这里的关键在于步长我们取定为了

\rho

，这是为什么？这是因为，如果固定了步长为

\rho

，我们实际上可以推出来

0 \in \partial f(x^{(k)}) + A^T u^{(k)}

注意这个就是原问题KKT条件中的稳定性条件。因此只需要再让

Ax^{(k)} - b \to 0

，就可以验证这个迭代会收敛到最优解。也即我们令

k \to \infty

，可以证明KKT条件成立，结合问题具备强对偶性自然可以得到这个结论。

不过这个方法也有不好的地方，就是这样的话就不能够使用分解法了，因为即使原问题可以使用对偶分解法，新的问题也做不到了。

总结一下就是说，增强拉格朗日法是可以解决对偶上升法中收敛困难的问题的。但是它的思想和作用自然不可能只有这个。具体的它的延伸方法，我们到下一节再说。

小结

本节主要介绍了两种现代优化的方法——坐标下降法和对偶上升法，同时也简单提了一下增强拉格朗日法。坐标下降法其实非常多的被用到机器学习，深度学习等相关算法中，也是因为它相对比较好理解，好用。对偶上升法则不是那么有名，可能也和它收敛困难有关系。

下一节我们会接着增强拉格朗日法这条线，继续介绍一些比较有名的算法，并给出一些实际的例子。

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

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

编程算法

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

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

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

编程算法

登录后参与评论

0 条评论

热度