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

简介: 本文其实值属于:程序员的数学【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




目录
相关文章
|
存储 SQL 分布式计算
Cloudera Manager 术语和架构
本文介绍了Cloudera Manager 的常见术语和架构
Cloudera Manager 术语和架构
|
9月前
flutter开发中Use ‘const’ with the constructor to improve performance. Try adding the ‘const’ keyword to the constructor invocation.报错如何解决-优雅草卓伊凡
flutter开发中Use ‘const’ with the constructor to improve performance. Try adding the ‘const’ keyword to the constructor invocation.报错如何解决-优雅草卓伊凡
111 1
|
3月前
|
人工智能 安全 搜索推荐
合规风险、汇率损失、用户流失:跨境结算的“三座大山”怎么搬?
跨境电商代购系统面临跨境支付效率低、成本高、合规难和技术滞后等痛点。本文分析四大挑战,并探讨数字钱包、区块链、API与AI等技术解决方案,结合典型案例与未来趋势,助力企业构建高效、低成本、合规的跨境支付体系,推动行业迈向智能化、绿色化发展新阶段。
|
8月前
|
数据可视化
如何减少低效沟通?小型团队信息管理的实战方法
在小型团队中,信息过载常导致沟通混乱和任务执行低效。本文探讨了信息过载的根源,并提出优化策略:统一沟通渠道、结构化任务指令、设定消息优先级以及使用可视化工具如板栗看板,以减少信息碎片化、提高执行精准度、避免干扰专注工作并让任务状态透明,从而提升整体协作效率。
300 59
|
12月前
|
存储 移动开发 JavaScript
vuex的工作流程,模块化使用案例分享,及状态持久化
vuex的工作流程,模块化使用案例分享,及状态持久化
234 0
echarts 报错 —— Component series.map not exists. Load it first
echarts 报错 —— Component series.map not exists. Load it first
374 0
|
供应链 安全 物联网
深度剖析:区块链技术掌握必备知识,加密货币与智能合约应用解析
深度剖析:区块链技术掌握必备知识,加密货币与智能合约应用解析
501 0
|
应用服务中间件 nginx C语言
Nginx集成Lua实现根据POST请求报文内容自定义负载策略
上游服务调用下游服务的接口,部分接口业务高峰期请求量大,下游服务器压力很大,会影响到其它接口的访问。如果通过增加下游服务器横向扩容会增加成本,且在业务高峰期还是有可能影响其他接口。所以需要使用Lua配置一种可以根据报文内容进行负载的策略(调用接口的URL是固定的,下游服务通过解析报文调用对应接口)。
762 0
|
Web App开发 Rust 安全
|
SQL 存储 关系型数据库
OceanBase数据库开发和运维漫谈
本文是面向初次接触OceanBase数据库的开发和运维人员,介绍OceanBase数据库的直观特点(所以没有高大上的理论和复杂的技术细节)。然后再以一个实际问题为引子,逐步展现OceanBase数据库的独特魅力。
5442 0