平邑网站建设,龙岩seo外包公司,网站设置怎么删除数据,张家港建设局网站最优化基础知识#xff08;2#xff09;
无约束优化问题#xff0c;一维搜索
一、一维搜索
一维搜索的意思是在一个方向上找到最小点。
用数学语言描述#xff0c;X*Xk tPk#xff0c;从Xk沿着Pk方向行走t到达最小点X*。
1、收敛速度#xff1a; 线性收敛#xff1…最优化基础知识2
无约束优化问题一维搜索
一、一维搜索
一维搜索的意思是在一个方向上找到最小点。
用数学语言描述X*Xk tPk从Xk沿着Pk方向行走t到达最小点X*。
1、收敛速度 线性收敛p1,0beta1超线性收敛: p1或者beta0次线性收敛p1beta1p阶收敛p1
2、二次终止性
能够在有限步内找到具有正定矩阵的二次函数的极小点。
f (X) 1/2 XTAX bTX c
3、终止准则
什么时候停机什么时候停止搜索。通常有以下五种 1、黄金分割法
给定每次迭代区间缩小比例如果做才能搜索次数最少
黄金分割法的python代码:
import mathdef golden_section_search(f, a, b, tol1e-6):golden_ratio (math.sqrt(5) - 1) / 2length b - ax1 a (1 - golden_ratio) * lengthx2 a golden_ratio * lengthwhile x2-x1tol:print(x1,x2)if f(x1) f(x2):b x2x2 x1x1 a (1 - golden_ratio) * (b - a)else:a x1x1 x2x2 a golden_ratio * (b - a)return (a b) / 2# 示例用法
def f(x):# 定义函数 f(x)return x*math.log(x)# 在区间 [0, 5] 中寻找函数的极小值点
result golden_section_search(f, 0, 5)
print(f极小值点的位置为: {result})
print(f函数极小值为: {f(result)})2、fibonacci搜索
给定迭代次数如何在迭代次数内达到最好的搜索效果最后一次迭代完成搜索区间最小
这个问题可以反过来理解假设最后一次迭代完成搜索区间长度为1那么最开始的搜索区间最大为多少
python代码
import mathdef fibonacci_search(f, a, b, n):# 计算Fibonacci数列fibonacci [0, 1]for i in range(n):fibonacci.append(fibonacci[-1] fibonacci[-2])# 计算初始区间长度length b - a# 计算初始比例ratio (fibonacci[-3] / fibonacci[-1]) if len(fibonacci) 2 else 0# 初始化区间端点x1 a ratio * lengthx2 a (1 - ratio) * length# 迭代搜索for _ in range(len(fibonacci) - 3):if f(x1) f(x2):b x2x2 x1x1 a ratio * (b - a)else:a x1x1 x2x2 a (1 - ratio) * (b - a)fibonacci.pop()ratio (fibonacci[-3] / fibonacci[-1])print(fibonacci[-3],fibonacci[-1],ration)# 返回最优解的位置return (a b) / 2# 示例用法
def f(x):# 定义函数 f(x)return x*math.log(x)# 在区间 [-5, 5] 中寻找函数的极小值点
result fibonacci_search(f, 0, 5, 30)
print(f极小值点的位置为: {result})
print(f函数极小值为: {f(result)})在有的地方直接给出的不是迭代次数而是最终的区间长度的上界Lb1-a1是初始区间。 b n − a n F n − 1 / F n ( b n − 1 − a n − 1 ) F n − 1 F n F n − 2 F n − 1 ⋯ F 1 F 2 ( b 1 − a 1 ) b_n-a_nF_{n-1}/F_{n}(b_{n-1}-a_{n-1}) \frac{F_{n-1}}{F_{n}}\frac{F_{n-2}}{F_{n-1}}\cdots\frac{F_{1}}{F_{2}}(b_1-a_1) bn−anFn−1/Fn(bn−1−an−1)FnFn−1Fn−1Fn−2⋯F2F1(b1−a1) 也就是说区间长度最小bn-anb1-a1/F_nLF_n是最大的fibonacci数。 关键F[n-2]F[n-1]F[n]F[n-2]/F[n]F[n-1]/F[n]1这样能保证每次删掉一侧的区间比例是一样的。 当F[6]/F[7]21/340.6176470588235294和黄金分割法近似相同。 黄金分割法是fibonacci法的极限形式。 3、三点二次插值法 4、两点三次插值法 5、牛顿法
牛顿法就是在极小点附近选择一个初始点x0在x0处二阶泰勒展开并求其驻点。牛顿法不具有全局收敛性因此初始点的选择很重要它只是向初始点附近的驻点靠近。 牛顿法的python代码
import sympy as sp
def newton_method(f, x0, tol1e-6, max_iter100):f_d1 f.diff()f_d2 f_d1.diff()# 迭代搜索for _ in range(max_iter):# 计算导数值fx f_d1.subs({x:x0})fxx f_d2.subs({x:x0})# 更新搜索位置x1 x0 - fx / fxx# 检查是否满足终止条件if abs(x1 - x0) tol:break# 更新当前点x0 x1# 返回搜索结果return x1# 示例用法
x sp.Symbol(x)
fx**3-4*x5# 选择初始点
x0 -10# 使用牛顿法搜索函数的极小值点
result newton_method(f, x0)
print(f极小值点的位置为: {result.n()})
print(f函数极小值为: {f.subs({x:result}).n()})二、非精确一维搜索
1、Goldstein准则 2、Wolfe准则 3、Armijo准则
