优化算法-从梯度下降到深度学习非凸优化

一、数学优化

1.1 定义

Mathematical Optimization（数学优化）问题，亦称最优化问题，是指在一定约束条件下，求解一个目标函数的最大值（或最小值）问题。

根据输入变量 ? 的值域是否为实数域，数学优化问题可以分为离散优化问题和连续优化问题．

在连续优化问题中，根据是否有变量的约束条件，可以将优化问题分为无约束优化问题和约束优化问题．

1.2 线性优化和非线性优化

如果目标函数和所有的约束函数都为线性函数，则该问题为线性规划（Linear Programming）问题。
相反，如果目标函数或任何一个约束函数为非线性函数，则该问题为非线性规划（Nonlinear Programming）问题。

在非线性优化问题中，有一类比较特殊的问题是凸优化（Convex Optimization）问题。

1.3 凸优化

1.3.1 凸集和凸函数

在凸优化问题中，变量 ? 的可行域为凸集（Convex Set），即对于集合中任意两点，它们的连线全部位于集合内部。

凸集的并集也是凸集。

目标函数 ? 也必须为凸函数，即满足
凸函数：给定任意两个点，函数的取值在两点之间的取值，总是小于此两点

1.3.2 其他性质

凸优化要求优化目标是凸函数，然而深度学习建模的往往是非凸的问题。因而，只在算法收敛性证明性上有用，但实际训练中用处不大。

1.4 深度学习优化

深度学习中大多数目标函数都很复杂，没有解析解，所以必须使用数值优化算法。

深度学习优化中最令人烦恼的是局部最小值、鞍点和梯度消失。

局部最小值

对于任何目标函数f(x)，如果在处x对应的值f(x)小于在x附近任意其他点的值，那么f(x)可能是局部最小值

鞍点（saddle point）

指函数的所有梯度都为0，但既不是全局最小值也不是局部最小值的任何位置。

假设函数输入是k维向量，其输出是标量，因此其Hessian矩阵将有k个特征值。函数的解可能是局部最小值、局部最大值或函数梯度为零位置处的鞍点：

当函数在零梯度位置处的Hessian矩阵的特征值全部为正值时(正定)，我们有该函数的局部最小值；
当函数在零梯度位置处的Hessian矩阵的特征值全部为负值时，我们有该函数的局部最大值；
当函数在零梯度位置处的Hessian矩阵的特征值为负值和正值时，我们有该函数的一个鞍点
这就是多变量微积分的结论。

二、梯度下降

2.1 方向导数推导GD

方向导数即，一个函数在给定方向的变化率（斜率，>0增加，<0减少），其实就是导数推广到单位方向：简而言之，给定函数点x，选择在任意一个单位方向都求一个斜率来看函数的变化程度Δf(x+Δx)/Δx。

方向导数相当于是算，在给定点和方向的变化率。

如果你要爬升（上山），那么可定选最陡的方向。给定点，通过求方向的极值得到最优方向（局部）。
梯度是方向导数取最大值的方向（负梯度，是衰减最厉害的方向）

2.2 泰勒级数启发式推导GD

总结：泰勒一阶展开，基于负梯度针对 \epsilon 构造递减序列

方向导数：梯度是方向导数最大的方向，而负梯度则是函数值下降最快的方向

梯度下降启发式

考虑一类连续可微实值函数 $ f: \mathbb{R} \rightarrow \mathbb{R} $。利用泰勒展开，可以得到

\[f(x + \epsilon) = f(x) + \epsilon f'(x) + \mathcal{O}(\epsilon^2)
\]

即在一阶近似中，$f(x + e)$可通过x处的函数值f(x)和及其一阶导数得出。

现在我们试图构造出一个让$f(x)$递减的序列：

\[f(x + \epsilon) f(x)
\]

\[f(x + \epsilon) - f(x) =\epsilon f'(x) + \mathcal{O}(\epsilon^2)
\]

可以试图将，$epsilon $设置为一个负的极小值 $\eta$ 乘以梯度：
$ \epsilon = -\eta f'(x) $ 那么有，$\eta$设为固定步长，将其代入泰勒展开式以得到：$$ f(x - \eta f'(x)) = f(x) - \eta f'^2(x) + \mathcal{O}(\eta^2 f'^2(x))
$$

如果$ f(x)$ 的导数没有消失，就能继续展开，这是因为：$ f'^2(x)$ 此外，总是可令 $\eta $小到足以使高阶项变得不相关。因此：

\[f(x - \eta f'(x)) - f(x)
\]

那么有, $x$为$f(x)$的参数，那么梯度下降则有：

\[x \leftarrow x - \eta f'(x)
\]

可假设$x$在负梯度方向上移动的会减少函数值。

学习率

在梯度下降中，我们首先选择初参数始值和学习率常数，然后使用它们连续迭代，直到停止条件达成。

学习率（learning rate）决定目标函数能否收敛到局部最小值，以及何时收敛到最小值。

若学习率太小，将导致的更新非常缓慢代

若学习率太大，将导致的更新震荡

import torch
import numpy as np

def f(x):  
    # 目标函数 
    f(x) = x^2   
    return x ** 2

def f_grad(x): 
    # 目标函数的梯度(导数)
    return 2 * x

def gd(eta, f_grad):
    x = 10.0  # 初始参数值
    results = [x]
    for i in range(10):
        x = x - eta * f_grad(x)
        results.append(float(x))
        print(f'epoch 10, x: {x:f}')
    return results

results = gd(0.2, f_grad)

2. 3多元梯度下降

多变量情况下的梯度下降。
考虑多元连续可微实值函数，输入为

\[\mathbf{x} = [x_1, x_2, \ldots, x_d]
\]

即目标函数将向量映射成标量 $f: \mathbb{R}^d \to \mathbb{R}$。相应地，它的梯度也是一个由个偏导数组成的向量：$$ \nabla f(\mathbf{x}) = \bigg[\frac{\partial f(\mathbf{x})}{\partial x_1}, \frac{\partial f(\mathbf{x})}{\partial x_2}, \ldots, \frac{\partial f(\mathbf{x})}{\partial x_d}\bigg]^\top.$$

对多变量函数使用相应的一阶泰勒近似来思考。具体来说

\[f(\mathbf{x} + \boldsymbol{\epsilon}) = f(\mathbf{x}) + \mathbf{\boldsymbol{\epsilon}}^\top \nabla f(\mathbf{x}) + \mathcal{O}(\|\boldsymbol{\epsilon}\|^2).
\]

在epsilon的二阶项中，函数下降最陡的方向由负梯度得出：$ -\nabla f(\mathbf{x})$ 。即在近似中，$ f(x + e)$ 可通过$x$处的函数值$f(x)$和一阶导数$f`(x)$得出。

现在试图，构造出一个让f(x)递减的序列：
可以试图将设置为一个负的极小值 $\eta$ 乘以梯度：