凸优化（C）——FW方法的分析与应用，镜面下降方法，深度学习与运筹中的优化简介

学弱猹

发布于 2021-08-09 17:35:44

1.3K0

发布于 2021-08-09 17:35:44

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

上一节笔记：凸优化（B）——再看交替方向乘子法（ADMM），Frank-Wolfe方法

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

大家好！

这一节我们接着介绍之前的Frank-Wolfe方法（以下简称FW方法），并介绍一下一阶方法中具有浓厚分析意味的一种方法：镜面下降法（Mirror Descent）。在这两种方法介绍完之后，CMU的对应课程的正课内容就告一段落，但中科大的《最优化原理》中还有对它在运筹学中的应用做一些简单的拓展。因此，这一部分内容会单独作为一个章节进行补充。

那么我们开始吧。

Source

CMU 10-725: Convex Optimization
USTC: 最优化原理
Boyd, Vandenberghe, Convex Optimization
K. Clarkson (2010), Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
J. Giesen, M. Jaggi and S. Laue, S. (2012), Approximating parametrized convex optimization problems
M. Jaggi (2011), Sparse convex optimization methods for machine learning
M. Jaggi (2011), Revisiting Frank-Wolfe: projection-free sparse convex optimization
M. Frank and P. Wolfe (2011), An algorithm for quadratic programming
R. J. Tibshirani (2015), A general framework for fast stagewise algorithms

Frank-Wolfe方法的收敛性分析

回顾一下上一届提到的FW方法，它是在梯度投影法下的一个变种。通过去掉约束中的二次项和避免计算投影算子，FW方法就应运而生。它的迭代公式是

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

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

这里的

\gamma_k

就是步长，一般取成

\frac 2 {k + 1}

，具体的设计原理和细节参考上一节的笔记。

在上一节的最后，我们介绍到了它有一个比较合适的“对偶间隔”（我们加了个双引号，因为它不是严格意义上的对偶间隔），这一节我们接着这个来说一下它的收敛性分析。它的收敛性分析也是一个相当新的结果，属于Source中的Jaggi (2011)，具体可以阐述如下

Theorem 1: 如果设步长为

\gamma_k = \frac 2 {k + 1}

，那么有

f(x^{(k)}) - f(x^*) \le \frac {2M}{k + 2}

，其中

M = \max_{\gamma \in [0, 1], x, y, z \in C, z = (1- \gamma) x + \gamma y} \frac {2}{\gamma^2}(f(z)- f(x)-\nabla f(x)^T (z- x))

弄出这么一个常数来也是挺不容易的……

虽然这个方法是一个很新的方法，但是它的证明倒也不是无迹可寻。在证明它之前我们先给出一些背景和推论。

这个性质最直接的推论就是它的收敛速度是

O(\frac 1k )

这样的级别的。这里防止大家忘记之前的内容多说两句，它的意思就是如果需要达到

\epsilon

这样的误差精度，需要

O(\frac 1 \epsilon)

这么多迭代步数。计算方法可以参考《凸优化》的第3节，有关收敛性分析的部分。

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

为了给出它的一个证明思路，我们先看一下，当我们回到梯度投影法，设

\nabla f

Lipschitz连续且常数为

的时候，会有什么效果。

事实上，在这个时候，根据《凸优化》第2节（凸优化（2）——凸函数，强凸函数及相关拓展）最后的结果，我们有

f(z) - f(x) - \nabla f(x)^T (z - x) \le \frac L 2 \|z - x \|_2^2

那么两边按照

的那个要求取极大值，可以得到

M \le \max_{\gamma \in [0, 1], x, y, z \in C, z = (1- \gamma)x + \gamma y} \frac 2 {\gamma^2} \frac L 2 \| z - x \|_2^2

把

z = (1 - \gamma) x + \gamma y

代入就可以得到

M \le \max_{x , y \in C}L \|x - y \|_2^2 = L \operatorname{diam}^2(C)

这代表什么意思呢？说明

和

的量级可以认为差不多，因为

\operatorname{diam}^2(C)

实在不是一个可以有什么影响力的常数因子。这一点也就说明，其实这个方法的收敛性结果，和梯度投影法很类似，也就是说和近端梯度法是比较接近的。

拿之前学过的方法和这个方法做类比是很好的找灵感的方法。我们来看一下，要证明FW方法的这个收敛性结果，可以怎么利用这个类比。

Proposition 1: 证明在迭代过程中，

f(x^{(k)}) \le f(x^{(k - 1)}) - \gamma_k g(x^{(k - 1)}) + \frac {\gamma_k^2}{2}M

，

的定义同上，

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

这个证明并不是很困难，只需要注意到

f(x^{(k)}) \le f(x^{(k - 1)} + \gamma_k (y^{(k - 1)} - x^{(k - 1)})) \le f(x^{(k - 1)}) + \gamma_k \nabla f(x^{(k - 1)})(y^{(k - 1)} - x^{(k - 1)}) + \frac {\gamma_k^2}2 M

\le f(x^{(k)}) - \gamma_k g(x^{(k)}) + \frac{\gamma_k^2}{2} M

第二个和第三个不等号分别用到了

M, g

的定义，所以这样就可以了。

很明显，这个公式和我们之前退回到梯度投影法所利用到的那个不等式，在形式上是一模一样的。所以如果我们不先讨论梯度投影法，这个结论就显得有些突兀了。

好的，现在我们开始证明这个结论。根据这个不等式，两边同时减掉一个

f(x^*)

，我们就有

h(x^{(k)}) \le h(x^{(k - 1)}) - \gamma_k g(x^{(k - 1)}) + \frac {\gamma_k^2}{2}M

这里

h(x) = f(x) - f(x^*)

。写到这里，我们希望利用到递推的思路，将

h(x^{(k)})

和

h(x^{(k - 1)})

的关系推出来。而恰好我们发现

g(x^{(k - 1)}) \ge h(x^{(k - 1)})

（这可以参考上一节最后提对偶间隔的部分，想想为什么？），所以可以得到

h(x^{(k)}) \le h(x^{(k - 1)}) - \gamma_k h(x^{(k - 1)}) + \frac {\gamma_k^2}{2}M = (1- \gamma_k)h(x^{(k - 1)}) + \frac {\gamma_k^2}2 M

有了递推公式，归纳法就自然逃不掉了。注意到如果我们设

h(x^{(k - 1)}) \le \frac{2M}{k + 1}

，那么根据归纳法，有

h(x^{(k)}) \le (1 - \frac 2 {k + 1})\frac{2M}{k + 1} + (\frac 2 {k + 1})^2 \frac M 2 \le \frac {2M}{k + 2}

所以相当于说，假设定理对于

的情况成立，我们证明出了对于

k+ 1

时的情况也成立。这就足够证明结论了。

在Jaggi (2011)这篇paper中，还针对计算不准确的情况做了分析。具体来说就是下面这个定理。

Theorem 2: 如果“可能的”迭代点

y^{(k - 1)}

满足

\nabla f(x^{(k - 1)})^T y^{(k - 1)} \le \min_{y \in C} \nabla f(x^{(k - 1)})^T y + \frac {M \gamma_k} 2 \delta

，且

\delta \ge 0

，

\gamma_k = \frac 2 {k + 1}

保持不变，那么有

f(x^{(k)}) - f(x^*) \le \frac {2M}{k + 1} ( 1 + \delta)

这个定理是说，我们对于

的计算的结果并不是严格意义上的极小值，有一定的误差

\frac{M \gamma_k} 2 \delta

，但是在这种情况，可以看出迭代的收敛速度依然是

O (\frac 1k )

，只是这个常数变大了一些。当然了要注意的是，

\gamma_k \to 0

，因此随着迭代的进行，这个误差是要求最终收敛于0的。

最后我们提一下FW方法的一些变种。一方面，我们可以修改它的步长，比方说我们可以考虑更新公式

\gamma_k = \arg\min_{\gamma \in [0, 1]}f(x^{(k - 1)} + \gamma (y^{(k - 1)} - x^{(k - 1)}))

也就是说不额外规定步长的选取公式，而是使用求最小值的方法。这个思路比较像线搜索方法中的精确线搜索（exact line search）的思路。同样的，你也可以考虑使用非精确线搜索，利用回溯法的思路。这一方面我们不多言，感兴趣的可以看一下《数值优化》第1节至第3节，与线搜索有关的部分。

数值优化（1）——引入，线搜索：步长选取条件

数值优化（2）——线搜索：步长选取条件的收敛性

数值优化（3）——线搜索中的步长选取方法，线性共轭梯度法

还有一种变种是下面这样

x^{(k)} = \arg\min_z f(z)

s.t. \quad y \in \operatorname{conv}\{x^{(0)}, y^{(0)}, \ldots, y^{(k - 1)}\}

要理解这个算法，需要注意到

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

本质上就是一个

x^{(k -1)}

与

y^{(k - 1)}

的凸组合。既然如此，为什么我不干脆一点考虑之前迭代中所有出现的可能的迭代点

y^{(i)}

呢？所以这也可以认为是原始FW方法的一个拓展。

应用：轨迹跟踪方法

轨迹跟踪方法（Path Following）在这里的意思并不是大家所想的车辆跟踪，而是在解决带范数罚项问题的一种通用的解决方案。这里说的“带范数罚项问题”就是

\min_x f(x)

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

轨迹跟踪方法的思路就是：每隔一段距离，就重新使用FW方法更新一个新的迭代点并保持下去。下面这一张图大概可以描述这个意思。

可以看出，在一段空间内，

都是不变的。然后到了一个节点之后，就会再做一次FW方法，将最优解

变一下。所以可以看出，它的作用是可以给出一系列的变化值。虽然这些变化值并不连续，但是有定理保证它们离实际的最小值的差距不会太远。

我们先给出这个方法，再解释这个结论。

设

t_0 = 0

，

x^*(0) = 0

，设

m > 0

，

k = 1

计算

t_k = t_{k - 1} + \frac{(1 - 1/m)\epsilon}{\|\nabla f(\hat x(t_{k - 1}))\|_*}

，并设

\hat x(t) = \hat x(t_{k - 1}), \forall t \in (t_{k - 1}, t_k)

在

t = t_k

的时候，用FW方法计算

\hat x(t_k)

，当对偶间隔不大于

\frac \epsilon m

的时候停止。

k = k + 1

这里要多说一句，对偶间隔并不是我们上一节提到的那个"对偶间隔"

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

而是

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

具体为什么这个是合理的，可以看上一节Proposition 1证明的最后一部分。

这个设计还是很讨巧的，我们来看看它能够得到什么好的结果。

Proposition 1:

\forall t \ge 0, f(\hat x(t)) - f(x^* (t)) \le \epsilon

我们证明一下这个结论。首先上一节我们有提到过一个对偶间隔的公式。为了方便，我们假设

\|y \| \le 1

（这个思路有点巧妙，可以参考上一节笔记的Example 1找一些关联）利用它，我们有

\nabla f(x^{(k)})^T (x^{(k)} - y^{(k)}) \le \max_{\|y \| \le 1} \nabla f(x)^T ( x -y) = \nabla f(x)^T x + t \|\nabla f(x) \|_*

（这里用到的就是对偶范数的定义，可以参考《凸优化》第7节（https://zhuanlan.zhihu.com/p/260819137））也就是说，我们的对偶范数不会超过

\nabla f(x)^T x + t \|\nabla f(x) \|_*

。这个数如果比较小，那么就有理由相信真正的对偶间隔会比较小，也就可以认为结论成立。

注意到这个是一个与

有关的线性函数，而且是单增的。注意到算法是每隔一段距离

，就更新一次FW方法。但这个结论暗示着，如果我们的

不断增加，总会使得这个值超过我们的阈值

\epsilon

（因为线性函数在全实数空间是没有最大最小值的）。所以我们自然想到在

增长到某一个

t^+

的时候，做下一步的优化操作。那么只要在

t^+

的时候，对偶间隔的上界依然没有超过

\epsilon

，那么下一个阶段自然也不会超出上限，也就能够保证最终，不管

的值是多少，我们的误差都会是可控的。

那么我们看一下，如果以

t^+ = t +\frac{ (1 - \frac 1 m)\epsilon }{\| \nabla f(x) \|_*}

代替一开始的

，我们会有

\nabla f(x)^T x + t \|\nabla f(x) \|_* + \epsilon - \frac \epsilon m \le \epsilon

这是因为我们之前要求对偶间隔低于

\frac \epsilon m

。总结一下，这个结论说明，对于每一个

[t, t^+]

的阶段，因为在

t^+

这个点处我们的对偶间隔

\le \epsilon

，结合线性函数单调性，就可以知道，每一个

[t, t^+]

的对偶间隔都在范围内，那么自然结论就成立了。

这个方法对应的就是我们LASSO中的warm-up，也即不立刻计算某一个

下的优化问题最小值，而是设置一系列的

t_i

来逼近这个

。具体的思路可以参考《凸优化》的第5节，对于warm-up的讨论。

凸优化（5）——近端梯度法：性质，延伸与案例分析；对偶性：引入与理解

只是相比较之前利用近端梯度方法来求解，这个方法可以保证误差可控，还算是挺好的一个性质。

好的，那么关于FW方法，我们就说这么多。

镜面下降方法简介

镜面下降方法（Mirror Descent）应该是《凸优化》系列所涉及到的最后一个先进的方法，也是覃含章学长所认为的统一一阶方法的一种工具，这里把他对于这个方法的介绍文贴在这里

https://zhuanlan.zhihu.com/p/34299990

在这一节中我们更多的会介绍一些思路和原理性的设计，不会涉及到过多理论的推导，如果希望了解一些更加理论的东西，可以看上面的那篇文章。

要介绍镜面下降方法，我们要先介绍布雷格曼散度（Bregman Divergence）这个概念。

Definition 1: Bregman Divergence 定义

D_\psi (x, y) = \psi(x) - [\psi(y) + \nabla \psi(y)^T (x - y)]

是布雷格曼散度，其中

\psi(x)

要求关于范数

\|\cdot \|

是强凸可微的，且凸性量度为

\lambda

。

这里

\| \cdot \|

是可以任意选的，并不一定是2-范数。这个概念比较类似统计机器学习中的K-L散度（K-L Divergence），都是描述一种“距离”的概念。而且对于函数强凸的要求，我们可以得到

D_\psi(x, y) \ge \frac \lambda 2 \|x - y \|^2

因此说它是“距离”也无可厚非。

比方说我们设范数是2-范数，并且设

\psi (x) = \frac12 \|x \|^2

，那么这个时候就可以得到

D_\psi(x, y) = \frac 12 \|x - y \|^2

。

这个概念介绍完了之后，一定会有人说，既然多设计了一个距离，自然是希望将这个距离用一些方式去“嫁接”到一些老的方法上。而和FW方法一样，镜面下降方法也是在近端梯度方法基础上做的改造。要看到这一点，我们要先回顾一下梯度下降法做的更新公式。

回顾一下梯度下降方法，其实就是下面这样的更新公式

x_{t + 1} = \arg\min_{x \in C} f(x_t) + \nabla f(x_t)^T (x - x_t) + \frac 1 {2 \eta_t} \|x - x_t\|_2^2

这里的

x_{t + 1}

就是第

t +1

步迭代点，

\eta_t

是梯度下降法的步长。这些和之前的写法不太一样，注意区分。

那么我们这里采用的方案就是**把最后的一项中的

\frac 12 \|x - x_t \|_2^2

改掉，改成

D_\psi(x, x_t)

。**这样改就是改了一个距离的函数，并且我们上面说了，在2-范数和特定的

\psi(x)

的情况下，

D_\psi(x, x_t)

和

\frac 12 \|x - x_t \|_2^2

两个是相等的。

那么我们看看，这么修改之后会发生什么。如果替换之后，我们考虑修改一下这个优化目标，考虑把它变成

x_{t + 1} = \arg\min_{x \in C} x^T (\nabla f(x_t) - \frac 1 {\eta_t} \nabla \psi(x_t)) + \frac{\psi (x)}{\eta_t}

这是因为这么替换之后，我们把与

无关的项去掉了。

这虽然是一个带约束的优化问题，但因为我们有可微做保证，所以求极小值还是可以先通过梯度为0来看看，所以我们对右边求极小值的式子求一个梯度，做一些整理，我们就有

\nabla \psi(x_{t + 1}) = \nabla \psi(x_t) - \eta_t \nabla f(x_t)

如果写成算子的形式，就可以变成

x_{t + 1} = (\nabla \psi)^{-1}(\nabla \psi(x_t) - \eta_t \nabla f(x_t))

但是这个

x_{t + 1}

只是一个“可能的”下一步迭代点，因为不像FW方法，你没有办法保证这样得到的迭代点满足约束的要求。因此我们最后加一个投影算子。所以最终，我们就可以得到镜面下降方法的更新公式

x_{t + 1} = P_C((\nabla \psi)^{-1}(\nabla \psi(x_t) - \eta_t \nabla f(x_t)))

虽然到此，我们算是介绍完了镜面下降法的迭代公式的来源，但问题是，为什么把它叫作镜面下降法？我们说了半天，似乎也没看到这个方法和Mirror有什么关联之处。要说明这一点需要用一些泛函的知识，但我尽量用通俗的语言去说，不涉及泛函内的专属名词。

在泛函的视角下，

所属于的空间，和

\nabla f

所属于的空间并不是一个空间。而因为在函数凸且闭的情况下，我们可以得到一个结论

(\nabla \psi)^{-1} = (\nabla \psi)^*

这可以认为说

\nabla \psi

这个算子的作用，相当于作用到了函数的对偶空间上。记住这句话之后，我们再回头看一下原方法。大概可以概括为：先在

\nabla \psi

这样的空间下做了一步梯度下降，

\eta_t

是步长。然后再利用

(\nabla \psi)^{-1}

这个算子映射回去。下面这一张图描述了一般的梯度下降和镜面下降的区别。

我们可以看到，对偶空间和原空间相比，就好像一面镜子，原空间经过一个梯度投射到了对偶空间，在对偶空间做了相同的操作之后，再投射回来。因此从泛函的角度来说，镜面下降的核心，就是不依赖原空间的函数与空间性质，而依赖对偶空间的迭代和映射完成同样的任务。因此在实际的数值实验中，有时候我们会发现镜面下降法相比较一般的近端梯度法，具有更好的收敛性。这一般说明对偶空间的性质是优于原空间的。

好的，关于它的内容我们就说这么多。

深度学习中的优化器是什么？

介绍完这些内容之后，很多人自然会对优化的最为广泛的应用——深度学习（deep learning）感兴趣。的确，无论是处理计算机视觉（Computer Vision，CV）相关问题的卷积神经网络（Convolutional Neural Network，CNN），还是处理自然语言处理（Natural Language Processing，NLP）相关问题的循环神经网络（Recurrent Neural Network，RNN），它们的背景都是计算图，都是人工神经网络（Artificial Neural Network，ANN），而人工神经网络的正向计算过程和反向传播过程，本质上就是层层迭代计算函数值，和通过一种神奇的方法计算函数的梯度，最后得以使用一些梯度方法来完成任务。因此我们甚至可以说

深度学习就是在一个大号的神经网络上用梯度下降法。

当然了，这话并不准确，但明白大概的意思就行了。

因此我们会发现，深度学习的优化其实是AI中的一个非常热门的话题。也因此涌现出了相当多的优化器，也就是我们之前提到的优化算法。但比较邪门的事情是，无论是《数值优化》还是《凸优化》，我们都鲜有提到过深度学习的优化器。出现这种现象的原因可以归结为两个。一是这种优化器的设计原理多半是实验性的，缺少理论依据，即使是完全不懂神经网络的人，基本上一个Adam或者SGD就可以解决很多问题了。二则是因为神经网络的本质是函数的不断的复合，而神经网络的节点就比较像是增强函数非线性特征的工具，这都会大大加深理论分析的难度。比方说ANN中常用的sigmoid，tanh，relu，或者是RNN中的LSTM，GRU等等。

关于深度学习的优化器的介绍，多半是一些经验性的内容，这里我们也不会多提。但除了CMU的10-725有简单的提到这些以外，台大李宏毅的《机器学习》课程也有详细介绍这些内容。大家可以在b站视频中找到optimization这一部分的内容。另外，如果有人对于反向传播求梯度的方式也不是很了解，那么也可以看这一个课程的相关部分。就我看来，李宏毅老师对反向传播的解释，是我见过的最通俗易懂也最透彻的。

https://www.bilibili.com/video/BV1JE411g7XF?from=search&seid=4234153071728209301

那么关于深度学习的优化器，我们就说这么多。也恭喜大家，跟到这里，就说明你已经看完了CMU 10-725的主要内容。

优化中的运筹学：敏感性分析

接下来，我们会引用一些中科大《最优化原理》的，与传统运筹优化相关的一些内容。

运筹学中经常涉及到敏感性分析（sensitivity analysis）的概念。顾名思义，即对问题施加一个扰动之后，对于问题的性态会产生多大的影响。在传统运筹优化中，这种情况可以被更加精细的刻画。

我们考虑一般的凸优化问题

\min f_0(x)

s.t. \quad f_i(x) \le 0, i = 1, \ldots, m

h_i(x) = 0 , i =1 ,\ldots, p

因为我们有凸的要求，所以除了目标函数是一个凸函数，还需要

f_i

都是凸函数，

h_i

都是仿射函数。

对于优化问题的敏感性分析就是，改变约束条件之后，对问题会有多大的影响。所以我们也可以定义一个对应的干扰问题

\min f_0(x)

s.t. \quad f_i(x) \le u_i, i = 1, \ldots, m

h_i(x) = w_i , i =1 ,\ldots, p

很明显，改变不同的

u_i, w_i

，都会得到不同的优化问题，自然也会有不同的最优值和最优解。所以我们可以设最优值为一个关于

u, v

的一个函数

f^*(u, w)

，其中

u = (u_1, \cdots, u_m)^T

，

w = (w_1, \cdots, w_p)^T

。那么很明显，

f^*(0,0)

就是原问题的最优值。所以归根到底，我们就是希望研究函数

f^*(u, w)

的性质，这也就是敏感性分析的本质。

首先就是关于它的凸性。

Proposition 2:

f^*(u, w)

是一个凸函数。

简单证明一下，我们注意到这个函数可以写成

f^*(u, w) = \inf_x \{f_0(x) \mid f_i(x) \le u_i, i = 1 ,\ldots, m ; h_i(x) \le w_i, i = 1, \ldots, p\}

一层一层解剖，首先，内层的函数可以写成

g(x, u, w) = f_0(x)

，但是因为有一系列的约束，所以定义域为

\operatorname{dom} g = \operatorname{dom} f_0 \cap D

，这里的

就是一系列约束所划分成的区域，而

\operatorname{dom}f_0

就是函数

f_0(x)

在没有约束情况下的定义域。

要说明函数是一个凸函数，第一步要确认的就是定义域是一个凸集。但这个不难，因为如果

f_i(x)

都是凸函数，

h_i(x)

都是仿射函数，那么它们交在一起形成的约束

自然是一个凸集。而因为目标函数是一个凸函数，所以

\operatorname{dom}f_0

自然是一个凸集，因此

\operatorname{dom}g

就是一个凸集。

说完这个，我们再说明

g(x, u, w) = f_0(x)

是一个凸函数，但这个没什么好说的。

g(x,u,w)

函数本身是与

u, w

无关的，而

f_0(x)

又是一个凸函数，所以走定义很容易看出来这一点。事实上，通过走定义，也可以证明如果

g(x, u, w)

是一个凸函数，那么

f^*(u, w)

也是一个凸函数（想想为什么？），因此综合起来，这个性质就得到了证明。

下面这一个性质就是敏感性分析的核心内容。

Proposition 3: 如果问题具备强对偶性，且

\lambda^*, v^*

分别为对应

f_i

和

h_i

的对偶变量的最优值，那么有

p^*(u, w) \ge p^*(0, 0) - \lambda^{*^T} u - v^{*^T} w

如果已经忘记了对偶变量的书写和用法，可以去看一下《凸优化》的第5，6节

凸优化（5）——近端梯度法：性质，延伸与案例分析；对偶性：引入与理解

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

这个性质也不难，如果我们设

x^*

为干扰问题的最优解，那么不难得到

p^*(0, 0) = g(\lambda^*, v^*) \le f_0(x^*) + \sum_{i = 1}^m \lambda_i^* f_i(x^*) + \sum_{i = 1}^p v_i^* h_i(x^*)

\le f_0(x^*) + \lambda^{*^T}u + v^{*^T} w = p^*(u, w) + \lambda^{*^T}u + v^{*^T} w

第一个不等号利用的是对偶问题的定义，而第二个不等号就是利用了干扰问题的约束条件。移项就可以得到结论。

现在，我们回头再看一下这个性质在说什么。我们会发现，对于

p^*(u, w)

来说，它其实是受

\lambda^{*^T} u + v^{*^T} w

这么一个东西所制约的。假如说有某一个

\lambda_i^*

非常大，那么其对应的约束

u_i

稍微变化一点，都会对极值产生非常大的影响，这也就是不稳定，敏感的含义。

当然了，事实上如果

p^*(u, w)

的性质再好一些，那么还有一个局部敏感性的说法。

Proposition 4: Local Sensitivity 若

p^*(u, w)

在

(0, 0)

处可微，那么有

\lambda_i^* = -\frac{\partial p^*(0, 0)}{\partial u_i}

，

v_i^* = -\frac{\partial p^*(0, 0)}{\partial v_i}

。

这个性质用的倒不是特别多，毕竟验证这个函数的可微性，也不算是一件特别容易的事情。

好的，这一节我们就到这里。剩下的内容以及习题课，我们都集合在下一节再说。

小结

本节主要是对Frank-Wolfe方法做了一个总结，并给出了镜面下降法的大概思路。除此之外，对于深度学习中的优化器，运筹学中的敏感性分析，我们也在这里做了一些解释，它本质上就是对偶性的一个应用。事实上到这一节为止，基本的凸优化的内容算是介绍完了，对于入门绝对算是足够了。下一节我们结束所有的内容，并会给出一些习题用于对相关概念的巩固。

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

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

深度学习

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

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

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

深度学习

登录后参与评论

0 条评论

热度