凸优化（7）——对偶性延伸：对偶范数，共轭函数，双对偶；再看牛顿法

学弱猹

发布于 2021-08-09 17:31:17

1.7K0

发布于 2021-08-09 17:31:17

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

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

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

大家好！

在这一节，我们会进一步探讨对偶性的应用。我们会说一些更加深层次的内容，并将它们与其他学科联系起来。将这一部分说完之后，我们将回到算法的部分，开始介绍以牛顿法作为先锋的一些常见的二阶方法。当然了因为在《数值优化》第5节（数值优化（5）——信赖域子问题的求解，牛顿法及其拓展）中已经介绍了牛顿法，所以这一节关于牛顿法的部分，更多的像是一个补充。

那么我们开始吧。

Source

CMU 10-725, Convex Optimization
Boyd, Vandenberghe, Convex Optimization
Amir Beck (2017), FIrst-order Methods in Optimization
R. T. Rockafellar (1970), Convex Analysis
Y. Nesterov, A. Nemirovskii (1994), Interior-point polynomial methods in convex programming, Chapter 2
J. Nocedal, S. Wright (2006), Numerical Optimization
L. Vandenberghe, Lecture notes for EE 236C, UCLA, Spring 2011-2012

对偶性的应用

对偶性应用1：对偶范数定义与性质

在矩阵论（或者说数值线性代数）里有一个对偶范数（dual norm）的概念，它的定义如下

Definition 1: Dual Norm 定义对偶范数为

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

比方说对于一般的

l_p (p \ge 1)

范数

\|x\|_p = (\sum_{i = 1}^n |x_i|^p)^{1 / p}

，它的对偶范数就是

l_q

范数。这个性质的证明其实利用的就是赫尔德（Holder）不等式，是数学分析的一道经典习题。但证明它不是我们这一节要关注的内容，所以我们就不提这个证明了。

与对偶性有关系的其实是下面这个性质。

Proposition 1

\|x\|_{**} = \|x\|

，也即对偶范数的对偶范数是原范数。

我们证明一下这个结论。要利用上对偶性，我们自然需要一个优化问题。所以我们把范数改成了下面这个优化问题

\min _y \|y \| \quad s.t. y = x

这只是一个形式的变换而已，这个解就是

\|x\|

。但是它已经有了一个优化问题的形式了，所以可以推导对偶问题，也即

L(y, u) = |y | + u^T (x - y) = |y | - y^T u + x^T u

然后我们考虑

\min_y L(y, u)

，注意到如果说

\|u \|_* > 1

，那么说明

\max_{\|z\| \le 1}z^T u > 1

，这就说明了

可以取到一个方向，使得

\|y\| < y^T u

。这就说明了

\min_y \{\|y\| - y^T u\} = -\infty

，因为可以让

的量度尽可能地大。但这种情况就没意思了，因为对偶问题本质上是希望得到一个原极小值问题的好的上界，

-\infty

显然不是一个好的候选。

如果说

\|u \|_* \le 1

，那么这个时候，

\|y\| \ge y^T u

，那么最好的方法就是让

\|y \| = 0

，所以这个时候

\min_y \{\|y\| - y^T u\} = 0

。

总结一下，对偶问题就是

\max_u u^T x \quad s.t. \|u \|_* \le 1

这个解其实就是

\|x\|_{**}

。而我们会发现原问题是满足强对偶性的，所以解是相同的，这就是结论。

需要多说一句的是，这个结论从语言上来看似乎非常显然（毕竟没有人会怀疑“对面的对面就是自己”），但是对偶问题的对偶问题不一定是原问题，很多用到对偶概念的内容也没有很完美的对称性。我们到后面还会提到这个现象，但不管如何，提到对偶性都要非常小心。在对偶性的相关章节里，从来没有提到”互为对偶“这样的言辞，也是因为这个。

对偶性应用2：共轭函数与优化问题的形式转化

我们在上一节最后其实举了一个这样的例子，即一个带约束优化问题可以通过对偶性转化为无约束优化问题。这个技巧其实可以更一般化一些。比如我们考虑下面这个例子

Example 1: 求解

\min_x \sum_{i = 1}^n f_i(x_i) \quad s.t. a^T x = b

的对偶问题。

也算是一个一般性的问题了。那么根据正常的流程，写出拉格朗日函数，就可以得到

g(v) = \min_x \sum_{i = 1}^n f_i(x_i) + v(b - a^T x) \\ = bv + \sum_{ i = 1}^n \min_{x_i} \{f_i(x_i) - a_i v x_i\}

所以我们的对偶问题其实就是

\max _ v g(v)

。虽然这个形式看起来还挺复杂，但至少它是一个无约束优化问题了。如果目标函数有一个比较好的形式的话，求解这个问题会比原问题要简单得多。

细心的同学会观察到，对偶问题还是有些复杂，所以有一个叫作共轭函数（Conjugate Function）的概念被提了出来。

Definition 2: Conjugate Function 给定函数

f: \mathbb R^n \to \mathbb R

，定义其共轭为

f^*: \mathbb R^n \to \mathbb R

，且

f^*(y) = \max_x y^T x - f(x)

有了这个定义之后，我们就可以进一步把式子简化，得到

\min_{x_i}\{f_i(x_i) - a_i v x_i\} = -f_i^*(a_i v)

这样写起来就会更方便，虽然它的作用远不止此哈哈。

这里要注意到共轭函数一定是凸函数。因为它是一个关于

的函数，所以只需要看

y^T x

这一部分。所以这个函数相当于是一系列仿射函数的最大值，那自然是凸函数。下面这张图是一个共轭函数的几何解释，简单来说就是线性函数

y^T x

与

f(x)

的距离的最大值。

关于共轭函数有一些有用的结论，我们这里列举一些但不会全部证明，毕竟有的东西太分析了……

Proposition 2: Fenchel's Inequality 对任意的

x, y

都有

f(x) + f^*(y) \ge x^T y

这个没什么好说的，走定义一步结束。

Proposition 3:

f^{**} \le f

，如果

是闭的且凸，那么

f^{**} = f

我们只证明第一个结论，第二个结论的证明比较分析，大家可以去参考Source中，Amir (2017)的Theorem 4.8。

对于第一个结论，我们取定一个

，那么注意到

f^*(y) = \max_x y^T x - f(x) = y^T x^* - f(x^*)

也即假设这个最大值在

x^*

处取到。那么这样的话，我们有

f^{**}(x) = \max_y y^T x - f^*(y) = \max_y y^T x - y^T x^* + f(x^*)

我们希望说明的是

f^{**}(x) \le f(x), \forall x

，那么我们已经取了一个

，那么根据

\max

，只需要证明

\forall y, y^T(x - x^*) + f(x^*) \le f(x)

这等价于

\forall y, y^Tx - f(x) \le y^T x^* - f(x^*)

，这是显然的结论，因为我们的

x^*

就是最大值对应的点。最后再根据

是任意的，就可以得到第一个结论。

有了Proposition 3，我们可以证明下面这个很有意思的结论。

Proposition 4: 如果

是闭的且凸，那么

\forall x,y

，下面结论相互等价 (1)

y \in \partial f(x)

(2)

x \in \partial f^*(y)

(3)

f(x) + f^*(y) = x^T y

我们简单的证明一下。假如说

y \in \partial f(x)

，那么这就说明

\forall z, f(z) \ge f(x) + y^T (z -x)

通过变换，根据共轭函数的定义，我们可以得到

y^T x - f(x) \ge f^*(y)

，那么这个不等号一定会取等，因为我们根据Fenchel不等式（Proposition 2），可以得到一个相反方向的不等式，而这就是我们的第三个结论。

注意到因为我们有

的一些性质，所以根据Proposition 3有

f^{**} = f

。所以换句话说，我嗯耶自然会有

f^*(y) + f^{**}(x) = y^T x

仔细看一下形式，我们只不过在第三个结论的基础上，把

改成了

f^*

，把

x, y

的位置相互交换了一下而已，所以我们其实可以完全复用上面的结论，得到

x \in \partial f^*(y)

，因为这个相比较

y \in \partial f(x)

而言，也只是交换了一些顺序，做了个相同的替换而已，而这就是第2个结论。最后注意到两个小结论都是等价结论，所以逻辑闭环已经做好，也就说明了证明的完结。

通过这些小的分析性质和证明（当然了，大的分析是不敢拿出来的），我们可以看出，一是对称的对称不一定是本身，二是对于这个结论而言，其实

1 \Leftrightarrow 3

是不需要

有闭，凸的条件的，但是

3 \Leftrightarrow 2

是需要的。

好的，我们来看一些小而精的例子吧。

Example 2: 证明

f(x) = \|x\|

的共轭函数为

f^*(y) = I_{\{z: \|z \|_* \le 1\}} (y)

为示性函数。

那么我们看一下如何解这个问题。要解它首先要观察示性函数的一些性质。注意到如果我们设

h(x) = I_C(x)

，那么通过定义很容易得到

h^*(y) = \max_{x \in C}y^T x

为它的共轭函数，并且在

是凸集的时候，

h^{**}(x) = h(x)

，也就是说示性函数的共轭的共轭是其本身。但是另一方面，又注意到我们上面推导过对偶范数的一个性质（Proposition 1），所以有

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

是一个示性函数的共轭。那么再对这个示性函数的共轭再共轭一次，就可以得到它自己，而

其实就是对应这个问题的约束

\|z\|_* \le 1

，这就证明了结论。

提共轭函数的一个很重要的原因是我们用它可以更方便的描述一些对偶问题。

Example 3: LASSO Dual（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

的对偶问题。

注意到这个问题是一个无约束问题，所以乍一眼看似乎很难求解对偶问题。但我们可以通过变量替换来人工的添加约束。也就是把问题转为

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

s.t. \quad z = X \beta

这样我们就可以写出它的对偶函数

g(u) = \min_{\beta, z} \frac 12 \|y - z \|_2^2 + \lambda \|\beta\|_1 + u^T (z - X \beta)

注意到没有

\beta, z

的交叉项，所以拆开来优化，可以得到

g(u) = \min_{\beta} \lambda \|\beta\|_1 - u^T X \beta + \min_z \frac 12 \|y - z\|_2^2 + u^T z

关于

的那一部分不是很困难，梯度求导然后根据函数是凸就可以得到极小值。但是另外的那一个部分可能有点难求，事实上我们可以根据变换

\min _\beta \lambda \|\beta\|_1 - u^T X \beta = - \lambda \max_{\beta} (\frac {u^T X}{\lambda} \beta - \| \beta\|_1) = -\lambda g^*(\frac {X^T u} \lambda)

发现可以构造出一个共轭函数的形式（这里

g^*(x) = \max_\beta x^T \beta - \|\beta\|_1

），也就是说我们只需要知道

g^*

是什么形式就可以了。这只需要根据Example 2，就可以得到

\min _\beta \lambda \|\beta\|_1 - u^T X \beta = -\lambda I_{\{v: \|v \|_\infty \le 1\}} (\frac {X^T u}{\lambda})

两个结合到一起，就可以得到

g(u)

，然后我们极大化它，就可以得到我们的对偶问题为

\max_u \frac 12 (\|y\|_2^2 - \|y - u \|_2^2)

s.t. \quad \|X^T u \|_\infty \le \lambda

这个就是它的对偶问题，当然了因为

\frac 12 \|y\|_2^2

是与

无关的，所以我们可以把问题再做一些变换，得到

\min_u \frac 12 \|y - u \|_2^2

s.t. \quad \|X^T u \|_\infty \le \lambda

这个虽然不再是对偶问题，但是它的解是不变的（当然了对应的极值肯定变了，毕竟你丢掉了一项2333）。

因为我们构造出的问题没有不等式约束，所以强对偶性满足，而这个对偶问题的解其实就是投影算子，具体的可以见下面这一张图。

我们可以看到，在这个区域外取两个点往下投影，就是它的一个对偶问题的解，那怎么理解它呢？首先根据KKT条件，可以发现

u = y - X \beta

。也就是说对偶解其实就是残差。那么根据投影算子的结论，我们可以证明，对于不同的两个点

y, y'

，它投影到的两个点

u, u'

满足

\|u - u'\| \le \|y - y' \|

（这个可以看《数值优化》第8节（数值优化（8）——带约束优化：引入，梯度投影法）与投影算子相关的性质的部分），所以如果我们的数据有一些扰动，这不会对结果的残差产生太多的影响，一定程度上说明了LASSO方法具备的稳健性。事实上这个结论如果不通过对偶原理，是很难发现的，或者说只能根据1-范数本身的特性去“猜”，却很难得到一个让人信服的解释。

最后我们来把这个思路再推广到更为一般的优化问题上。考虑近端梯度方法解决的问题形式

\min_x f(x) + g(x)

那么我们可以把它转为带约束的形式

\min_{x, z} f(x) + g(z) \quad s.t. x = z

那么同样的我们可以得到它的对偶问题

g(u) = \min_{x , z} f(x) + g(z) + u^T(z - x) = \min_x f(x) -u^T x + \min_z g(z) + u^T z

=-f^*(u) - g^*(-u)

所以可以看出对偶问题就是

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

。这个形式在很多问题中都可以去使用，只需要把函数的共轭函数求出来就可以了。比方说如果原问题是

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

那么对偶问题就是

\max_u -f^*(u) \quad s.t. \|u \|_* \le 1

你看，现在你一眼就可以看出来结果了，这肯定方便多了吧。

进一段广告！

广告结束！

对偶性应用3：二次对偶

虽然感觉严格来说应该翻译成双对偶（Double Dual），但我翻译成“二次对偶”，就是想强调“对偶的对偶”的意思。也就是说这一部分我们会给出一个结论，说明有哪些情况可以导出“对偶问题的对偶问题是原问题”这样的结论。但严格的定理证明其实还是分析的内容，大家可以参考Source中Rockafellar (1970)中的Chapter 29和30。

Theorem 1: 对于一般的优化问题

\min_x f(x) \\ s.t. \quad h_i(x) \le 0 , i = 1, \ldots, m \\ l_j (x) = 0 , j = 1 ,\ldots, r

如果

f, h_1, h_2, \ldots, h_m

都是闭且凸的，

l_1, \ldots, l_r

是仿射函数，那么对偶函数的对偶函数依然是原函数。

那么关于对偶性，我们就说到这里。我们整整跨了三节（虽然其实也就不到两节吧……）来提对偶问题，也足够说明它的重要性了。

再看牛顿法

欢迎回到优化算法的世界！

从这一部分开始，我们将先关注一些经典的二阶方法（Second-order Method），也就是会用到二阶信息（海塞矩阵）的优化算法。再关注一些更加现代的，更加深入的流行的方法。牛顿法（Newton Method）作为二阶方法的经典中的经典，自然不能被错过。不过因为我们在《数值优化》第5节（数值优化（5）——信赖域子问题的求解，牛顿法及其拓展）中已经非常详细的介绍了牛顿法的原理和一些性质。因此这里只是对那里没有提到的部分做一些补充。

再看牛顿法的设计理念与操作方法

在《数值优化》中，我们提到过牛顿法是根据一个估计

0 = \nabla f(x + v) \simeq \nabla f(x) + \nabla^2 f(x) v

来得到的结果，但如果我们把它与《凸优化》第3节（凸优化（3）——梯度与次梯度：方法，性质与比较）所提到的梯度下降法对比，我们会发现，其实牛顿法是要求我们的优化公式满足

x^+ = \arg\min_y f(x) + \nabla f(x)^T (y - x) + \frac 12 (y - x)^T \nabla^2 f(x) ( y - x)

把右边看成一个

的函数，然后令梯度为0，就可以得到更新公式。相比较一下梯度方法的目标

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

我们会发现更改的地方其实就是二次项。很显然牛顿法是对二次项的一个更加精确的估计。而梯度法只是把Taylor展开之后得到的二次项的那个海塞矩阵改成了

\frac 1t I

而已。事实上，如果函数是一个二次函数，那么牛顿法可以做到一步收敛，因为海塞矩阵其实变成了一个数量矩阵，所以估计是完全精确的，那么自然就可以直接得到极小值。

下面这一张图是使用数值方法解Logistic回归的目标函数，其中

n = 500, p = 100

为数据矩阵的行和列。这告诉我们，因为用到了二阶信息，所以在迭代步数上，牛顿法的优势是明显的。

接下来要介绍的就是它的步长选取和收敛性分析了。请注意，这里所说的和我们在《数值优化》里提到的策略并不相同。我们在这里所提到的策略其实和梯度下降法相同，都是回溯法。

Definition 3: Backtracking for Newton Method 设

0 < \alpha \le \frac 12

，

0 < \beta < 1

，那么牛顿法的回溯法步长选取方案就是：从

t = 1

开始，只要不等式

f(x + tv) > f(x) + \alpha t \nabla f(x)^T v

满足，那么就修改

t = \beta t

，否则就说明步长合适，执行牛顿迭代过程

x^+ = x - t v

，其中

v = (\nabla^2 f(x))^{-1} \nabla f(x)

。

这里要注意的是，我们这里的迭代公式严格来说不是牛顿法，而是弱牛顿法（damped Newton Method），但一般来说我们不区分，还是称呼这种迭代方式叫做牛顿法。

那么它的收敛性分析是什么样的呢？

Theorem 2: 设函数

是二阶可微的凸函数，

\nabla f(x)

是Lipschitz连续的，且对应Lipschitz常数为

，

f(x)

强凸，且凸性量度为

，

\nabla^2 f(x)

是Lipschitz连续的，且对应常数为

，那么对于牛顿法而言，我们有

f(x^{(k)}) - f(x^*) \le \begin{cases}(f(x^{(0)}) - f(x^*)) - \gamma k & k \le k_0 \\ \frac {2 m^3}{M^2} (\frac 12 )^{2^{k - k_0 + 1}} & k > k_0\end{cases}

，其中

\gamma =\frac{ \alpha \beta^2 \eta^2 m }{L^2}

，

\eta = \frac{\min \{1, 3(1- 2\alpha)\}m^2}{M}

，

k_0

是使得

\| \nabla f(x^{(k_0 + 1)})\|_2 < \eta

的步数。

忘记强凸的话，回《凸优化》第2节（凸优化（2）——凸函数，强凸函数及相关拓展）复习一下hhh。

这个定理我们不给出完整的证明过程（但我们会给出辅助证明二次收敛速度的一些小的工具），也没啥有意思的其他结论，大家看《数值优化》那里面的证明就足够理解牛顿法的这个特性了。

懵逼了？不要着急，我们忽略这些乱七八糟的系数，看看它告诉我们什么有趣的事实。一是我们发现，对于强凸的函数而言，牛顿法是一定收敛的，这也不是什么奇怪的事实。第二就是对于牛顿法而言，在比较靠近极小值点的时候，它的收敛速度是二次的收敛速度。虽然之前提过这个概念，不过有一个更直接的解释：如果希望满足

f(x^{(k)}) - f(x^*) \le \epsilon

，那么迭代步数的量级大约为

O(\log \log \frac 1\epsilon)

，而线性收敛速度是

O(\log \frac 1 \epsilon)

，因此这是一个非常快的速度，并且如果观察一下式子，可以发现对它取两次以2为底对数，确实会得到

k - k _0 + 1

这样的迭代步数。

说到这里，我们列一个小的结论。它是这个证明的一部分，但是我们主要是希望用它来解释一些其他的现象。

Proposition 5: 在二次收敛阶段，步长固定为1时，会有

\frac M {2m^2} \|\nabla f(x^{(k + 1)})\|_2 \le (\frac {M}{2m^2} \|\nabla f(x^{(k)}) \|_2)^2

我们证明一下这个结论，这里我们设

就是当前迭代点，而

x^+

是下一步的迭代点。

事实上注意到

x^+ = x + v

，其中

v = -(\nabla^2 f(x))^{-1} \nabla f(x)

，那么一定会有

\|\nabla f(x + v)\|_2 = \| \nabla f(x+ v) - \nabla f(x) + \nabla ^2 f(x) v \|_2

= |\int_0^1 \nabla ^2 f(x + tv) v d t - \nabla ^2 f(x) v|_2\le M |v |_2^2 \int_0^1 t dt

最后一个不等号用的是海塞矩阵的Lipschitz连续性。那么到此，把

的表达式代入，其实就可以得到一个中间结论

\|\nabla f(x + v) \|_2 \le \frac 12 M \| (\nabla^2 f(x))^{-1} \nabla f(x) \|_2^2

，因此可以考虑再使用范数的不等式

\| (\nabla^2 f(x))^{-1} \nabla f(x) \|_2^2 \le \| \nabla^2 f(x)^{-1}\|_{2}^2 \| \nabla f(x) \|_2^2 \le \frac 1 {m^2} \| \nabla f(x) \|_2^2

这里要注意矩阵的2-范数

\|X\|_2 = \sigma_1(X)

为它的最大奇异值，有的地方会写成算子范数（Operator Norm）

\|X\|_{op}

。把这两个结论拼起来，就算证明最终的结论了。

通过这个结论可以发现，如果我们有

\| \nabla f(x) \|_2 \le \eta

，那么我们会有

|\nabla f(x^{(k + 1)})|_2 \le \frac{2m^2}{M}(\frac {M}{2m^2} \eta)^2 \le \eta

这是因为根据条件可以推出

\eta \le \frac{m^2}{M}

。也就是说一旦模型进入了二次收敛速度的阶段，它的梯度就不再有可能回到

> \eta

的水平，只会一直收敛下去。

事实上通过这个你也能大致的看出来梯度的变化水平，也就是说通过不停的迭代，可以得到一个梯度的变化趋势。所以找到梯度与函数值差的一个桥梁就可以证明二阶收敛速度了。这个桥梁其实就是强凸性，注意到

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

因此两边对

取最小值，就可以得到

f(x) - f(x^*) \le \frac 1 {2m} \|\nabla f(x) \|_2^2

这是一个关于强凸的小结论，但这也是完成证明所必须要的工具，如果读者希望自己证明出这个定理的话。

那么如果放到总的过程来看，我们会发现迭代大约需要

\frac{f(x^{(0)}) - f(x^*)}{\gamma} + \log \log(\frac{\epsilon_0}{\epsilon})

步，其中

\epsilon_0 = \frac{2m^3}{M^2}

。也就是说之前需要经过一段时间的积累，使得迭代点的梯度逐渐缩小了之后，才会进入二阶收敛速度的阶段。

#牛顿法的其他性质

回头看这个收敛性分析，我们会发现它的收敛速度是依赖于三个指标的，也即

L, m, M

，它们也彰显了问题本身的一些性质。但在实际中会出现的情况是算法的运行效率并不受海塞矩阵条件数等的影响。因此实际上上面的收敛性分析结果是不全面的。不过也有一些references给出了一些修补，即说明了在某些情况下，可以证明出来它们的收敛性结果是与问题的性质好坏无关的。这就牵涉到自和谐（self-concordance）的概念。

Definition 4: self-concordance 若凸函数

满足

|f'''(x)| \le 2 f''(x) ^{3 /2}, \forall x

，那么称其为一个自和谐的函数。

比方说

f(x) = -\sum_{i = 1}^n \log(x_i), x \in \mathbb R_{++}^n

就是一个自和谐的函数。

根据这个性质，Nesterov和Nemirovskii得到了下面这个定理。

Theorem 3: 如果函数满足自和谐性，那么它最多经过

C(\alpha, \beta)f(x^{(0)} - f(x^*)) + \log \log(\frac 1 \epsilon)

步就可以收敛，其中

C(\alpha, \beta)

是一个仅仅与

\alpha, \beta

有关的常数。

当然这一块其实还是挺不完备的，我也说不清楚，因此这一块大家有个印象就好啦。

第二个关于牛顿法的拓展的性质是仿射不变性（affine invariance）。

Proposition 6: 对函数

和可逆矩阵

A \in \mathbb {R}^{n \times n}

，设

x = Ay

，

g(y) = f(Ay)

，则更新公式仍然不变。

我们证明一下这个结论。注意到对于

，牛顿法的更新公式为

y^+ = y - (\nabla^2 g(y))^{-1} \nabla g(y)

这里的一个困难点就是在于如何根据

的梯度的海塞矩阵，来求解

的。这个技巧自然还是使用《数值优化》第1节（数值优化（1）——引入，线搜索：步长选取条件）介绍的向量求导。注意到

\forall v, v^T \nabla f(x) = \lim_{t \to 0} \frac{f(x + tv) - f(x)}{t}

\forall v, \nabla^2 f(x) v = \lim_{t \to 0}\frac{\nabla f(x + tv) - \nabla f(x)}{t}

所以我们有

\forall v, v^T \nabla g(y) = \lim_{t \to 0} \frac{g(y + tv) - g(y)}{t} = \lim_{t \to 0} \frac{f(Ay + tA v) - f(Ay)}{t}

\forall v, \nabla^2 g(y) v = \lim_{t \to 0}\frac{\nabla g(y + tv) - \nabla g(y)}{t} = \lim_{t \to 0}\frac{\nabla f(Ay + tA v) - \nabla f(Ay)}{t}

但是通过变量代换，我们又可以发现

\forall v, \lim_{t \to 0} \frac{f(Ay + tA v) - f(Ay)}{t} = (Av)^T \nabla f(Ay) = v^T A^T \nabla f(Ay)

这就得到了

\nabla g(y) = A^T \nabla f(Ay)

。使用这个结果，又可以得到

\forall v, \nabla^2 g(y) v = \lim_{t \to 0}\frac{\nabla g(y + tv) - \nabla g(y)}{t} = A^T \lim_{t \to 0}\frac{\nabla f(Ay + tA v) - \nabla f(Ay)}{t}

= A^T \nabla^2 f(Ay)(Av)

这就得到了

\nabla^2 g(y) = A^T \nabla^2 f(Ay) A

。

把这两个小结论用起来，可以得到

y - (\nabla^2 g(y))^{-1} \nabla g(y) = y - A^{-1} (\nabla^2 f(Ay))^{-1} \nabla f(Ay)

这就说明我们可以得到更新公式为

Ay^+ = Ay - (\nabla^2 f(Ay))^{-1} \nabla f(Ay)

根据

x = Ay, x^+ = A y^+

，我们自然就发现了，虽然我们把式子的自变量做了一个更改，但这完全不影响最终的更新公式。潜在的含义就是，无论这个问题的解怎么变换，都不会改变牛顿法的更新过程。这也许可以解释为什么牛顿法在实际运行的过程中，其实一般看不出来问题性质（比如梯度的条件数）对迭代效果的影响，但毕竟没有严格的theory，这也只能算是一个个人意义上的瞎猜罢了。

一个好的拿来对比的例子就是梯度下降法。在实际的算法工程问题中，经常会遇到标准化（Standardization），归一化（Normalization）的需求，其实本质上就是因为梯度下降法会受到问题条件数的影响。具体的可以见下面的这张图。

可以看出，上边的图对应的椭圆就比较均匀，这对应着数据的两个维度的量级接近的情况。所以梯度下降法相对比较容易在很少的步骤内找到最优解（这里画的干脆就是一个圆，所以梯度下降法直接找到最优解，也就是这里的坐标轴原点）。但是对于下边的图，这个椭圆就比较扁平，对应着数据的两个维度的量级差距很大的情况。那么梯度下降法就会遇到麻烦。事实上，把二维的优化问题抽象成为一个二次型，或求解问题的条件数，我们会发现椭圆越扁平，其实对应的问题的条件数就越差。这个现象在吴恩达（Andrew Ng）放在Coursera上的机器学习课程上有比较形象的解释，这里也贴上b站对应的链接。

https://www.bilibili.com/video/BV164411b7dx?from=search&seid=15378095232710462984

那么到此，我们对于牛顿法，其实就说的差不多了。

小结

我们这一节主要探讨了对偶原理的一些应用，并利用共轭函数进一步方便了我们构造和理解一些对偶问题和原问题所揭示的现象。之后我们介绍了牛顿法的一些《数值优化》中所没有提到的一些出发点与性质，结合之前所说的内容再看牛顿法，相信会有一些不同的理解。

当然了，二阶方法还有很多其他的变种，它们多多少少都在《数值优化》中有被提及过，因此后面的文章还是会有很多补充穿插介绍的内容。结合起来看会有更棒的体验～

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

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

definition

optimization

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

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

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

definition

optimization