程序员的数学【最优化】(二)

简介: 本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 最优化

四、牛顿法

4.1 牛顿法原理

🚩牛顿法的原理是使用函数f(x)的泰勒级数的前面几项来寻找方程f(x)=0的根。

image.png

迭代过程如下:

44.png

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') # 更新过程点

45.png

4.3 求解最优化问题

🚩牛顿法最优化公式如下:

image.png

其中:

image.png

image.png

image.png

image.png

可得最终的优化公式为:

image.png

复杂问题简单化,多元函数降级为一元函数,那么最优化牛顿法泰勒二阶展开的更新公式为:

image.png

梯度下降法只用到了一阶导数的信息,牛顿法既用到了一阶导数的信息,也用到了二阶导数的信息。梯度下降法是用线性函数来代替目标函数,牛顿法是用二次函数来代替目标函数,所以说牛顿法的收敛速度是更快的。

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')

46.png

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)

47.png

4.5 拟牛顿法

🚩如上节所说,牛顿法虽然收敛速度快,但是需要计算海塞矩阵的逆矩阵H-1,而且有时目标函数的海塞矩阵无法保持正定(多元函数微分学),从而使得牛顿法失效。为了克服这两个问题,人们提出了拟牛顿法。这个方法的基本思想是:不用二阶偏导数而构造出可以近似海塞矩阵(或海塞矩阵的逆)的正定对称阵。不同的构造方法就产生了不同的拟牛顿法。


下面我们先推导一下拟牛顿条件,它给“对海塞矩阵(或海塞矩阵的逆)做近似”提供了理论指导,指出了用来近似的矩阵应该满足的条件。


对 ᐁf(x) 做二阶泰勒展开我们得到了以下近似:

image.png

令:

image.png

所以:

image.png

以上即为拟牛顿条件!

image.png




目录
相关文章
|
人工智能 决策智能
数学基础之博弈论
数学基础之博弈论
95 0
|
2月前
|
算法
第七章 回溯算法理论基础
第七章 回溯算法理论基础
22 0
|
算法 决策智能
运筹优化学习06:拉格朗日松弛算法(一)
运筹优化学习06:拉格朗日松弛算法(一)
运筹优化学习06:拉格朗日松弛算法(一)
|
算法 程序员
程序员的数学【最优化】(三)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 最优化
215 0
程序员的数学【最优化】(三)
|
机器学习/深度学习 算法 数据挖掘
程序员的数学【最优化】(一)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 最优化
222 0
程序员的数学【最优化】(一)
|
机器学习/深度学习 程序员
程序员的数学【微积分基础】(一)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 微积分基础,微积分是公式推导的基础,如果你也关注我的专栏:西瓜书读书笔记,里面对公式进行详细推导的过程中,运用到了大量的 导数,积分,身为一名程序员,我们务必掌握一些必备的数学知识。
319 0
程序员的数学【微积分基础】(一)
|
机器学习/深度学习 程序员
程序员的数学【微积分基础】(二)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 微积分基础,微积分是公式推导的基础,如果你也关注我的专栏:西瓜书读书笔记,里面对公式进行详细推导的过程中,运用到了大量的 导数,积分,身为一名程序员,我们务必掌握一些必备的数学知识。
252 0
程序员的数学【微积分基础】(二)
|
机器学习/深度学习 程序员
程序员的数学【概率论】(三)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 概率论
158 0
程序员的数学【概率论】(三)
|
程序员
程序员的数学【概率论】(二)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 概率论
247 0
程序员的数学【概率论】(二)
|
机器学习/深度学习 算法 数据挖掘
程序员的数学【概率论】(一)
本文其实值属于:程序员的数学【AIoT阶段二】 的一部分内容,本篇把这部分内容单独截取出来,方便大家的观看,本文介绍 概率论
298 0
程序员的数学【概率论】(一)