前言

本文其实值属于：程序员的数学【AIoT阶段二】的一部分内容，本篇把这部分内容单独截取出来，方便大家的观看，本文介绍最优化，本文涵盖了一些计算的问题并使用代码进行了实现，安装代码运行环境见博客：最详细的Anaconda Installers 的安装【numpy，jupyter】（图+文），如果你只是想要简单的了解有关线代的内容，那么只需要学习一下博文：NumPy从入门到高级，如果你是跟着博主学习的小伙伴，建议先看博文：数据分析三剑客【AIoT阶段一（下）】（十万字博文 保姆级讲解），如果你没有基础，那么还需先修博文：Python的进阶之道【AIoT阶段一（上）】（十五万字博文 保姆级讲解）

优化的概念

1.1 最大值最小值

🚩优化问题是找到的最大值或最小值

我们经常求最小值，其中为优化变量，即自变量，称为目标函数，也可能有约束。一些优化问题同时具有等式约束和不等式约束。

满足该约束且仍在域内的那些的集合称为可行域。

1.2 局部极小值

🚩函数存在于的域，而，则是局部极小点

1.3 全局最小值

🚩其实在初中的时候，我们就学会了寻找极值的问题。例如，二次函数抛物线的顶点是最大值或最小值。在高中，我们也会遇到寻找极值的问题。计算一个非常复杂的函数的极值。完成初等数学技能。真正的飞跃发生在大学。微积分课程提供了求解极值的统一方法，即求导数等于的点。如果是多元函数，我们说它的梯度等于，我们只要解方程组。我们在机器学习中遇到的几乎所有函数都是可导出的。平滑引导

局部极小值，通过大量实践发现，在高维优化问题中，局部极小值和全局极小值通常没有太大区别，甚至在某些情况下局部极小值具有更好的归纳能力（泛化能力）。

2. 推导和迭代求解

2.1 求导遇到的问题

🚩 前面我们说找到极值就是等于的导数或者梯度，找到疑似极值就是停滞点：

用微积分这样的方法，只要能导出函数，能解吗？

因为很多时候要找到等于的方程或等于的方程组的根并不容易，例如：

分别求关于的偏导数：

设上述导数为仍不能解。对于次及以上的代数方程，没有求根的公式，所以这个想法看起来很美，但实际上行不通，我们只好另想办法了。

2.2 近似迭代求解

🚩近似解，我们先给一个初值看是否为极值点。当然，它必须满足等式或不等式约束。如果不是，我们会想办法更​​进一步，只要我们有就越来越接近我们的极点，这个问题不就解决了吗！

因此，构造一个满足这样一个极限的序列，当接近，的梯度值极限接近，我们就找到了函数的驻点

由此，我们要解决的核心问题就变成了，如何从当前点移动到下一个点，即如何从到，迭代法是我们在计算数学中经常使用的一种方法，它它不仅可以求极值，还可以用来求方程的解，包括线性方程、非线性方程、矩阵的特征值等等。

在优化中，这种迭代思想也称为梯度下降！

3.梯度下降

3.1 公式推导

🚩数值优化算法是求近似解，而不是理论之上的精确解

我们推导出这个公式，我们需要使用多元函数泰勒展开公式（函数在的邻域），最后加上一个高阶无穷小

如果忽略高阶无穷小，即属于的邻域，则等号变为近似相等，则将置于等号左侧：

这时候如果想减少得更快，就必须让等式右边取最小值，即时，减少的幅度最大！

单位向量表示方向，长度为的向量，即模为的向量称为单位向量。

将向量乘以标量不会改变它的方向，只会改变它的大小。这是缩放矢量的方法。

因此，向量可以表示为标量乘以单位向量。

为了最大化下降，那么向量[这里的向量用表示]的方向与梯度的方向相反：

分母是一个标量，可以并入，简化为：

需要注意的是，当和足够接近时，即在其邻域内，泰勒展开式中不止一项可以忽略，否则不能忽略，不是高阶无穷小，条件约等于不成立，所以的步长不能太大，所以我们得到梯度下降法的公式。

实施细节：

• 初始值的设置，随机或设置满足约束
  
• 步长设置，比较小，也可以动态调整
  
• 循环终止的判断，达到（最大迭代次数）；当上一次更新减去下一次更新差值基本不变时
  

3.2 代码演示

3.2.1 创建模拟数据

import numpy as np
import matplotlib.pyplot as plt
# 构建方程
f = lambda x : (x - 3.5) ** 2 - 4.5 * x + 10
# 导函数
g = lambda x : 2 * (x - 3.5) - 4.5
# 创建模拟数据并可视化
x = np.linspace(0, 11.5, 100)
y = f(x)
plt.plot(x, y)
_ = plt.scatter(5.75, f(5.75), color = 'red', s = 30)

3.2.2 迭代法求解（梯度下降）

eta = 0.3 # 学习率
# 随机（瞎蒙）,初始值x0
x = np.random.randint(0, 12, size = 1)[0]

# 多次while 循环，每次梯度下降，更新，记录一下上一次的值
# 比较精确度
# 一开始故意设置差异，目的为了有区分，不能一上来就停止
last_x = x + 0.1

# 精确度，人为设定
precision = 0.0001
print('-----------------随机x是：', x)

# 每次梯度下降，求解出来的x值，一开始随机给的
x_ = [x] # Python中列表

count = 0
while True:
    if np.abs(x - last_x) < precision: # 更新时，变化甚微，满足精确度，终止
        break
    # 更新，梯度下降
    # x是当前数值，赋值给上一个值
    last_x = x
    count += 1
    x = x - eta * g(x) # 梯度下降公式
    x_.append(x)
    print('+++++++++++++++更新之后的x是：%0.5f' % (x))
print('+++++++++++++++梯度下降次数：', count)

# x1是NumPy数组
x1 = np.linspace(0, 11.5, 100)
y1 = f(x1)
plt.figure(figsize = (9, 6))
plt.plot(x1, y1)

# 散点图
x_ = np.array(x_)
_ = plt.scatter(x_, f(x_), color = 'red', s = 30)

3.2.3 迭代法求解（退出条件最大迭代次数）

eta = 0.2 # 学习率
# 随机（瞎蒙）,初始值
x = np.random.randint(0, 12, size = 1)[0]
# 多次while 循环，每次梯度下降，更新，记录一下上一次的值
# 一开始故意设置差异，目的为了有区分，不能一上来就停止
last_x = x + 0.1
# 最大迭代次数，人为设定
count = 30
print('-----------------随机x是：', x)
# 每次梯度下降，求解出来的x值，一开始随机给的
x_ = [x] # Python中列表
for i in range(count):
    # 更新，梯度下降
    # x是当前数值，赋值给上一个值
    last_x = x
    x = x - eta * g(x) # 梯度下降公式
    x_.append(x)
    print('+++++++++++++++更新之后的x是：%0.5f' % (x))

# x1是NumPy数组
x1 = np.linspace(0, 11.5, 100)
y1 = f(x1)
plt.figure(figsize = (9, 6))
plt.plot(x1, y1)

# 散点图
x_ = np.array(x_)
plt.scatter(x_, f(x_), color = 'red', s = 30)

4.牛顿法

4.1 牛顿法原理

🚩牛顿法的原理是利用函数的泰勒级数的前几项求方程的根。

将处的函数展开为泰勒级数：

取线性部分作为的逼近，的解可以逼近的解，解为：

由于的近似只是一阶展开，因此并非的解，只能说比更接近 0 。于是，考虑迭代求解：

迭代过程如下：

4.2 牛顿法代码演示

def f(x):
    return (x - 3) ** 3        # 定义函数

def fd(x):
    return 3 * ((x - 3) ** 2)    # 定义一阶导数

y = [0] # 初始值
def newtonMethod(n, assum):
    count = n
    x = assum
    next_x = 0
    A = f(x) # 函数值
    B = fd(x) # 导数值
    print('A = %0.4f' % (A) + ', B = %0.4f' % (B) + ', time = %d' % (count))
    if f(x) == 0.0: # 是不是f(x) = 0的解
        return count, x
    else: # 不是方程 = 0的解，迭代更新
        next_x = x - A / B
        y.append(next_x)
        print('next_x = %0.4f' % (next_x))
        
    if abs(A - f(next_x)) < 1e-6: # 满足精确值，退出，什么都没做，只是打印
        # 设置迭代跳出条件，同时输出满足f(x) = 0的x值
        print('方程的解为： f(x) = 0, x = %0.4f'% (next_x))  
    else: # 不满足精确度，再次调用这个方法，递归
        return newtonMethod(n + 1, next_x)
    
# 设置从0开始计数，x0 = 4
newtonMethod(0, 0)

x = np.linspace(0, 6, 100)
plt.plot(x, f(x)) # 原图
_ = plt.scatter(y, f(np.array(y)), color = 'red') # 更新过程点

4.3 求解最优化问题

🚩牛顿法的优化公式如下：

在：

假设函数迭代次后的值为，则上的二阶泰勒展开式可近似如下公式：

我们要求的最小值，必要条件是在极值点的一阶导数是，因为我们把每次迭代得到的满足目标函数最小值的作为下一次迭代的值，所以我们可以假设round 的值是最优解：

代入二阶泰勒展开式并推导出：

制作：

其中代表矩阵

最终的优化公式可以得到：

将复杂问题简化，将多元函数降级为一元函数，则优化牛顿法的二阶泰勒展开式的更新公式为：

梯度下降法只使用一阶导数的信息，牛顿法使用一阶导数的信息以及二阶导数的信息。梯度下降法用线性函数代替目标函数，牛顿法用二次函数代替目标函数，所以牛顿法的收敛速度更快。

4.4 求解最优化代码演示

4.4.1 使用牛顿法求最优化（11步得到答案，2.0062）

import numpy as np
import matplotlib.pyplot as plt
# 构建方程
f = lambda x : (x - 2) ** 4 + 10

# 导函数
g1 = lambda x : 4 * (x - 2) ** 3
g2 = lambda x : 12 * (x - 2) ** 2

# 创建模拟数据并可视化
x = np.linspace(1, 3, 100)
y = f(x)
plt.plot(x, y)

y = [2.8]
def newtonMethod(n, assum):
    count = n
    x = assum
    next_x = 0
    A = g1(x)
    B = g2(x)
    print('A = %0.4f' % (A) + ',B = %0.4f' % (B) + ',次数 = %d' % (count))
    if f(x) == 0.0:
        return count, x
    else:
        next_x = x - A / B
        y.append(next_x)
        print('next_x = %0.4f' % (next_x),)
    if abs(f(x) - f(next_x)) < 1e-8:
        # 设置迭代跳出条件，同时输出满足f(x) = 0的x值
        print('方程的解为： f(x) = 0, x = %0.4f'% (next_x))  
    else:
        return newtonMethod(n + 1, next_x)
    
# 设置从0开始计数，x0 = 4
newtonMethod(0, 2.8)
_ = plt.scatter(y,f(np.array(y)), color = 'red')

4.4.2 使用梯度下降求最优解（207步得到答案，2.04349）

import numpy as np
import matplotlib.pyplot as plt
# 构建方程
f = lambda x : (x - 2) ** 4 + 10
# 导函数
g1 = lambda x : 4 * (x - 2) ** 3

eta = 0.3 # 学习率
# 随机（瞎蒙）,初始值
x = 2.8
# 多次while 循环，每次梯度下降，更新，记录一下上一次的值
# 比较精确度
# 一开始故意设置差异，目的为了有区分，不能一上来就停止
last_x = x + 0.1
# 精确度，人为设定
precision = 1e-8
print('-----------------随机x是：', x)
# 每次梯度下降，求解出来的x值，一开始随机给的
x_ = [x] # Python中列表
count = 0
while True:
    if np.abs(f(x) - f(last_x)) < precision: # 更新时，变化甚微，满足精确度，终止
        break
    # 更新，梯度下降
    # x是当前数值，赋值给上一个值
    last_x = x
    count += 1
    x = x - eta * g1(x) # 梯度下降公式
    x_.append(x)
    print('+++++++++++++++更新之后的x是：%0.5f' % (x))
print('+++++++++++++++梯度下降次数：', count)

# x1是NumPy数组
x1 = np.linspace(0, 11.5, 100)
y1 = f(x1)
plt.figure(figsize = (9, 6))
plt.plot(x1, y1)

# 散点图
x_ = np.array(x_)
_ = plt.scatter(x_, f(x_), color = 'red', s = 30)

4.5 拟牛顿法

🚩 上节提到，牛顿法虽然收敛速度快，但是需要计算Hessian矩阵的逆矩阵，有时目标函数的Hessian矩阵不能保持正定（多元函数微分） ，这使得牛顿法无效。为了克服这两个问题，提出了拟牛顿法。该方法的基本思想是构造一个正定对称矩阵，可以在不使用二阶偏导数的情况下逼近Hessian矩阵（或Hessian矩阵的逆）。不同的构造方法产生不同的拟牛顿法。

我们先推导出拟牛顿条件，它为“逼近Hessian矩阵（或Hessian矩阵的逆）”提供了理论指导，并指出了用于逼近的矩阵应满足的条件。

对进行二阶泰勒展开，我们得到以下近似值：

制作：

所以：

取，我们得到：

让，然后：

以上是准牛顿条件！

在拟牛顿法中，选择作为的近似值或选择作为的近似值，使它们满足上述牛顿条件。不同的拟牛顿法，区别在于如何确定或

常用的拟牛顿算法有：、、算法。这里不展开！

5.坐标下降法

🚩坐标下降法是分而治之的思想。

它的思想是保持其他不变，只优化其中一个，比如，那么多元函数求极值的问题就变成了单变量函数求极值的问题，这样难度就大了优化的小很多，然后我们把剩下的按住不放，然后优化直到，一轮结束后再回来优化。至于如何求解一个变量，可以通过梯度下降或牛顿法等优化算法求解，具体问题可以详细分析。

中的算法是优化其中两个，其他固定； 库也使用了大量的坐标下降法来解决。直观上看起来像：

我们优化所有变量一次，就像梯度下降迭代一次一样，这种方法也有很大的优势，就是计算量要小得多。

六、优化算法瓶颈

🚩前面的梯度下降法和牛顿法都是以为基础的，我们前面也说过，函数在某一点的导数或梯度等于是驻点，只是函数达到的必要条件求极值，不是充分条件，即不能推导出来

我们前面介绍的所有数值优化算法都面临两个问题。

6.1 局部极值问题

🚩这个问题是局部极值，但不是全局极值。理论上，如果我们需要一个全局最优解，我们必须找出所有的极值。您可能必须反复设置不同的初始迭代点。解决方案让它收敛到不同的局部最小值，然后比较谁最小找到全局最小值。

6.2 鞍点问题

🚩 前面我们说一元函数函数，它是坐标处的驻点，但它甚至不是局部最小值，对应的多元函数，我们称之为鞍点（既不是极大点也不是极点） ) 小值点的临界点称为鞍点)。严格的定义是，此时它的矩阵是不确定的，既不是正定也不是负定，因此它既不是最小值也不是最大值。

它在物理上更广泛，指的是一个方向上的最大值和另一个方向上的最小值的点。

七、凸优化问题

🚩 前面我们说过数值优化面临两个问题，一个是局部极值问题和鞍点问题。我们能避免这两个问题吗？

只要我们限制优化问题，这种问题有两个限制

1、优化变量的可行域必须是凸集
2、优化函数必须是个凸函数

同时满足这两个约束的问题称为凸优化问题，即先有局部最小值，再有全局最小值。

八、凸集

🚩凸集的定义：对于点的集合，有属于中的两点，连接两点的连线上的任意一点也属于集合。例如，立方体是一个凸集。


欧式空间

它的意义在于很多情况下，可行域是欧几里得空间，它一定是凸集。只有在凸集的前提下才能解决优化问题。

9.凸函数

🚩凸函数在函数上找到任意两个点。它们的连续性意味着割线上的值大于的对应值

函数的二阶导数与函数的凹凸性有关。凹凸是怎么定义的？

我们先做一个简单的介绍。请记住，凸函数是向下凸的。反正就是凹的。无论是凸函数，都可以通过二阶导数。如果二阶导数大于，则为凸函数。
如果函数是一元的，那么是凸函数。多元函数矩阵是半正定的，它是一个凸函数；多元函数矩阵是正定的，是一个严格凸函数。

如果每个函数都是凸的，那么它们的非负线性组合也是凸的。

10. 凸优化表达式形式

🚩凸优化的​​定义是目标函数是一个凸函数，可行域是一个凸集。如果存在这两个约束，则局部最优解必然是全局最优解。

凸优化一般表达式：

，其中是凸集

具有等式约束的表达式：

带有不等式约束的表达式：

往往我们需要证明一些机器学习算法是凸优化问题，比如逻辑回归、、线性回归等，来证明它的可行域是凸集，目标函数是凸函数，凸优化避免了局部最小值问题，也避免了鞍点问题，是凸函数，它的矩阵是半正定的，是半正定的，也避免了鞍点问题。

十一、拉格朗日乘子法

🚩高等数学和微积分，相信大家都学过，用来求解方程约束下的极值问题

拉格朗日乘子法将上有约束的优化问题转化为无约束的优化问题

称为函数（拉格朗日函数），称为拉格朗日乘数（实际上是系数）。求对的偏导，求对的偏导，令导数为，求出的值，则是函数在附加条件下的极值点。

以上是拉格朗日乘数法。拉格朗日乘子法通俗的理解是将有等式条件的约束优化问题转化为无约束优化问题来构造拉格朗日函数

十二、KKT条件

🚩 假设我们面临一个不等式条件约束优化问题，如下：

对于上式，显然是不等式约束的优化问题，不能再使用拉格朗日乘子法，因为拉格朗日乘子法是有等式约束的优化问题。

拉格朗日乘子法的扩展，用于求解具有不等式约束的理论结果：

约束是：

上述条件称为条件。

13. 拉格朗日对偶

🚩凸优化、非线性规划问题，甚至运筹学中的线性规划问题都会涉及到这个概念。其含义是将原问题转化为另一个问题来解决，但转化后的问题更容易解决，Lager Longian multiplier method 的一种扩展，用于同时解决等式约束和不等式约束的方法，通过将原问题转化为对偶问题，通常比原始问题更容易解决。

约束如下：

构造一个广义的拉格朗日函数，所谓的泛化还包括不等式约束。在下面的等式中，你会发现上的约束消失了，尽管上有一个约束：

原始问题

我们将对偶问题定义为（上式的解等价于解下式）：

其实和是互换的，当然相应的变量也要换。

双重问题有什么好处？对于原题，要先求内，再求外。对于对偶问题，我们可以先在其中找到。有时，先确定上函数的最小值，再求解上的最大值，比原问题更容易解决问题。

但是原始问题和对偶问题并不等价。有强对偶和弱对偶的概念。弱对偶是所有对偶问题都具有的属性。

所有向下凸函数都满足强对偶。如果两个问题是强对偶的，那么这两个问题实际上是等价的：

下面是弱对偶的推导过程：

其中，是函数取最大值和最小值时的最优解，即原问题总是大于等于对偶问题：