最优化理论

作者: legendgh | 来源:发表于2020-02-17 19:22 被阅读0次

凸函数

若函数 $f(x)$ 满足
$f(\alpha x + (1-\alpha)y) \le \alpha f(x) + (1-\alpha)f(y)$
其中， $0 \le \alpha \le 1$ ，则称 $f(x)$ 是凸函数。 $f(x)$ 可以是多元函数。

Jensen不等式

若 $f(x)$ 为凸函数，则对于任意点集 $\{ x_1, \cdots, x_n\}$ ，若 $\lambda_i \le 0, \sum_{i=1}^n \lambda_i = 1$ ，
$f(\sum_{i=1}^{n} \lambda_i x_i) \le \sum_{i=1}^{n}\lambda_i f(x_i)$

【证明】利用数学归纳法证明

首先，当 $n=1$ ， $f(x_1)= f(x_1)$

当 $n=2$ 时， $f(\lambda x_1 + (1-\lambda)x_2) \le \lambda f(x_1) + (1-\lambda)f(x_2)$

假定当n=k时，满足
$f(\sum_{i=1}^{k} \lambda_i x_i) \le \sum_{i=1}^{k}\lambda_i f(x_i)$
当 $n=k+1$ 时，
$\begin{align} f(\sum_{i=1}^{k+1}\lambda_i x_i) &= f(\lambda_{k+1}x_{k+1} + \sum_{i=1}^{k}\lambda_ix_i) \\\\ &= f(\lambda_{k+1}x_{k+1} + (1-\lambda_{k+1})\sum_{i=1}^{k}\frac{\lambda_i}{1-\lambda_{k+1}}x_i) \\\\ &\le \lambda_{k+1}f(x_{k+1}) + (1-\lambda_{k+1})f(\sum_{i=1}^{k}\frac{\lambda_i}{1-\lambda_{k+1}}x_i) \end{align} \\\\ 因为 \sum_{i=1}^{k+1} \lambda_i = 1, 所以\sum_{i=1}^{k} \lambda_i = 1 - \lambda_{k+1} \\\\ 原式 \le \lambda_{k+1}f(x_{k+1}) + (1-\lambda_{k+1})\sum_{i=1}^{k}\frac{\lambda_i}{1-\lambda_{k+1}}f(x_i) \\\\ \le \sum_{i=1}^{k+1}\lambda_i f(x_i)$
故得证。

牛顿法

简述

牛顿法是求 $f(x)$ 的极值，一般是最小化。牛顿法的思路是：随机（或者根据某种规则）选择一个起始点 $x_0$ ，用quadratic form来逼近 $x_0$ 附近的图形。此时，获得了一个二次逼近函数。对该二次逼近函数求极值点（通过偏导数等于0），将该极值点作为新的起始点，重复以上流程（即在新起始点附近用二次函数逼近原函数），直至收敛。

算法

用二次函数逼近 $f(x)$ ，
$f_{appro}(x) = f(x^{(t)}) + (\nabla f(x^{(t)}))^{T} (x-x^{(t)}) + \frac{1}{2}(x-x^{(t)})^{T}H(x^{(t)})(x-x^{(t)}) \tag{1.1}$
其中Hessian矩阵为函数 $f(x)$ 的二阶偏导数矩阵，
$H(x) = \begin{bmatrix} \frac{\partial ^2 f}{\partial x_i \partial x_j}\end{bmatrix}_{n\times n} \tag{1.2}$

为求该逼近函数的极值点，我们对其求偏导数，并令其等于0
$\nabla f_{appro}(x) = \nabla f(x^{(t)}) + H(x^{(t)})(x-x^{(t)}) = 0 \tag{1.3}$

求得新的起始点
$x^{(t+1)} = x^{(t)} - (H(x^{(t)}))^{-1} \nabla f(x^{(t)}) \tag{1.4}$
令 $H_t = H(x^{(t)}), g_t = \nabla f(x^{(t)})$ ，上式可化为
$x^{(t+1)} = x^{(t)} - H_t^{-1}g_t \tag{1.5}$

详述

引导：首先，让我们从导数的定义开始。已知 $f(x)$ 和点 $a$ ，
$\begin{equation} f^{\prime}(a) = \lim _{x\to a} \frac{f(x) -f(a)}{x-a} \tag{2.1} \end{equation}$
以上当 $x$ 趋近于a的时候取等号。我们将条件放宽一点，如果x不趋近a，将等号改成约等号
$f^{\prime}(a) \approx \frac{f(x) -f(a)}{x-a} \tag{2.2}$
将上式移项得
$f(x) \approx f(a) + f^{\prime}(a)(x-a) \tag{2.3}$
等式（3）可以用来求 $f(x)$ 在 $x$ 处的近似值。 $a$ 的取值越趋近 $x$ ，求出来的近似值越趋近真实值。此处我们无法通过迭代，使得我们求得的 $f(x)$ 越来越趋近于真实值。同时，我们不难发现，其实（3）就是泰勒展开的前两项。

那牛顿法的精髓迭代什么时候出现呢？让我们试图寻找 $f(x) = 0$ 的解吧。条件允许的话，我们可以求得 $f(x)=0$ 的解析解。如果条件不允许呢（什么时候不允许？）？将 $f(x)=0$ 代入等式（3），得
$x = a - \frac{f(a)}{f^{\prime}(a)} \tag{2.4}$
由（4）可以求出 $x$ 的近似解，但如果a取值离真实解差太多，近似解误差较大。不用慌，我们可以重复过程（4），每次都用上次求得的 $x$ 作为a的取值，最终x会收敛于x的真实值（为什么会收敛？）。

同样的道理，如果我们想求 $f(x)$ 的最优解呢？我们可以通过求解函数的导数，令导数等于0，求得的x便是最优解处的变量x。但同样我们可能无法获取解析解，因此，我们采用牛顿法求解 $f^{\prime}(x)=0$ ，只不过原函数变成了原函数求导
$x = a - \frac{f^{\prime}(a)}{f^{\prime\prime}(a)} \tag{2.5}$
通过迭代求解（5），可以求解 $f^{\prime}(x)=0$ 的近似值了。

多元函数的逼近（local approximation)

拟牛顿法

简述

牛顿法需要计算Hessian矩阵的逆矩阵，首先我们不一定能保证Hessian存在逆矩阵，其次逆矩阵的运算复杂度比较高 $O(n^3)$ ，消耗计算资源。为解决这个问题，拟牛顿法的思想就是用一个近似的矩阵 $U$ 来代替Hessian矩阵的逆矩阵，在迭代过程中，矩阵 $U$ 也通过迭代的方式进行更新。 $U = H_t^{-1}$

如何更新矩阵U呢？先看一下，在迭代过程中，我们需要的求解的变量和更新的变量

变量	描述	更新条件
$x^{(t)}$	每次迭代的起始点	$U_t, g_t$
$g_t$	原函数在 $x^{(t)}$ 点处的梯度向量	$x^{(t)}$
$U_t$	代替Hessian矩阵的逆矩阵	$\Delta x$

根据算法中等式(3)，将 $x^{(t+1)}$ 代入其中，得
$\nabla f(x^{(t+1)}) - \nabla f(x^{(t)}) = H(x^{(t)})(x^{(t+1)} - x^{(t)}) \tag{3.1} \\\\ \Delta g_t = H_t \Delta x_t \\\\ \Delta x_t = H_t^{-1}\Delta g_t$

此处如果疑惑为何将 $x^{(t+1)}$ 代入等到的式子与牛顿法求解的公式不一样的话，仔细分析（3.1）和（1.5）不难发现， $H_t^{-1} \Delta g_t = -H_t^{-1}g_t$ 等式成立，是因为在求二次逼近函数的最小值时，取 $g_{t+1} =0$ ，因此有 $g_{t+1} - g_t = \Delta g_t = -g_t$

由等式(3.1)可知，如果知道 $x^{(t+1)}, x^{(t)}, g_{t+1}, g_t$ ，我们可以求得

在牛顿法中，我们通过 $x^{(t)}$ 来求得 $H(x^{(t)}), g_t$ ，从而求出 $x^{(t+1)}$ ；在拟牛顿法中，我们通过 $x^{(t)}$ ，求得

疑惑的地方：为什么拟牛顿条件由 $H_t^{-1} \Delta g_t = \Delta x_t$ 可以转换为 $U_{t+1}\Delta g_t = \Delta x_t$ 。原本等式满足的是对于t而言，为何对 $t+1$ 也成立？？？

拟牛顿条件

先看牛顿法：取值（或来自上一次迭代） $x_t$ ，二次逼近函数，求导并求出Hessian矩阵，获取极值点，得到 $x_{t+1}$ ；

拟牛顿法：取值（或来自上一次迭代） $x_t$ ，上次迭代得到 $H_t$ 的近似矩阵 $U_t$ ，求 $x_{t+1}$ ，根据拟牛顿条件求解 $U_{t+1}$ 。

分别将 $f(x)$ 在 $x_t$ 和 $x_{t+1}$ 展开：
$f_{approxi}(x)= f(x^{(t)}) + \nabla f(x^{(t)})(x-x^{(t)}) + (x-x^{(t)})^TH(x^{(t)})(x-x^{(t)}) \tag{a}$

$f_{approxi}(x) = f(x^{(t+1)}) + \nabla f(x^{(t+1)})(x-x^{(t+1)}) + (x-x^{(t+1)})^TH(x^{(t+1)})(x-x^{(t+1)}) \tag{b}$

逼近图

对上式分别求梯度：
$\nabla f_{approxi}(x) = \nabla f(x^{(t)}) + H(x^{(t)})(x-x^{(t)})$

$\nabla f_{approxi}(x) = \nabla f(x^{(t+1)}) + H(x^{(t+1)})(x-x^{(t+1)})$

对(a)将 $x=x^{(t+1)}$ 代入，对(b)将 $x=x^{(t)}$ 代入，分别得以下：
$\nabla f_{approxi}(x^{(t+1)}) - \nabla f(x^{(t)}) = H(x^{(t)})(x^{(t+1)} - x^{(t)}) \tag{c}$

$\nabla f(x^{(t+1)}) - \nabla_{approxi}f(x^{(t)}) = H(x^{(t+1)})(x^{(t+1)} - x^{(t)}) \tag{d}$

对于拟牛顿法，在已知 $x^{(t)}, U_t, x^{(t+1)}$ 的时候，我们要求的是 $U_{t+1}$ ，也即 $H(x^{(t+1)})$ ，但如果根据(d)来求解，得到的Hessian矩阵不能保证是正定的。因此，我们需要采用迭代的方式来求解 $U_{t+1}$ 。(d)作为拟牛顿条件。

《统计学习方法》中，用的是(c)来推出拟牛顿条件，给我带来了很大的困扰。因为(c)求出的是 $H(x^{(t)})$ 的逆矩阵的approximation矩阵 $U_t$ ，但 $U_t$ 是用来求 $x^{(t+1)}$ ，而 $x^{(t+1)}$ 是已知的，我们想求的是 $x^{(t+2)}$

总结一下，拟牛顿的思想是，假设在 $x^{(t+1)}$ 处的二次逼近函数在 $x^{(t)}$ 处的梯度等于原函数在 $x^{(t)}$ 处的梯度，然后通过这个条件（限制）来求解Hessian矩阵的逆矩阵的趋近矩阵。虽然这个趋近不一定吻合，但随着不断的迭代， $x^{(t)}$ 越来越趋近目标值。

那么接下来我们的工作就是，根据拟牛顿条件（d）来定义 $U_t$ 。

DFP算法

该算法定义
$U_{t+1} = U_t + \Delta U_t$
因为 $D_{t+1}$ 需要满足正定矩阵的要求，我们令 $\Delta D_t = \alpha w w^t + \beta v v^t$

我们希望找到合适的 $\alpha, \beta, w, v$

加入拟牛顿条件，可得
$y_t = \nabla f(x^{(t+1)}) - \nabla f(x^{(t)}) \\\\ \delta_t = x_{t+1} - x_t \\\\ U_{t+1} = H(x_{t+1})^{-1} \\\\ U_{t+1} y_t = \delta_t$

$\delta_t = (U_t + \alpha ww^t + \beta v v^t)y_t \\\\ = U_ty_t + aww^ty_t + \beta vv^ty_t$

因为 $\alpha ww^Ty_t = \alpha w^Ty_t w$ （结合律）,
$\delta_t = U_ty_t + (\alpha w^ty_t)w + (\beta v^ty_t)v$
此时，我们令 $(\alpha w^ty_t)=1, (\beta v^ty_t) =-1$ ，则
$\delta_t = U_ty_t + w - v \\\\ \delta _t - U_ty_t = w -v \\\\$
此时，我们令 $w = \delta_t, v = U_ty_t$ ，则拟牛顿条件满足了，根据 $(\alpha w^Ty_t)=1, (\beta v^Ty_t) =-1$ ，求出
$\alpha = \frac{1}{\delta_t^Ty_t} \\\\ \beta = \frac{1}{y_t^TU_t^Ty_t}$
因此
$\Delta U_t = \frac{\delta_t \delta_t^T}{\delta_t^Ty_t} + \frac{U_ty_ty_t^TU_t}{y_t^TU_t^Ty_t}$
其中，正定矩阵 $U_t^T = U_t$