最优化基础知识（2）
无约束优化问题，一维搜索
一、一维搜索
一维搜索的意思是在一个方向上找到最小点。
用数学语言描述，X*=Xk +tPk，从Xk沿着Pk方向行走t到达最小点X*。
1、收敛速度：
- 线性收敛：p=1,0<beta<1
- 超线性收敛: p>1或者beta=0
- 次线性收敛：p=1，beta=1
- p阶收敛：p>1
2、二次终止性：
能够在有限步内找到具有正定矩阵的二次函数的极小点。
f (X) = 1/2 XTAX + bTX + c
3、终止准则
什么时候停机，什么时候停止搜索。通常有以下五种：
1、黄金分割法
给定每次迭代区间缩小比例，如果做才能搜索次数最少？
黄金分割法的python代码:
import math
def golden_section_search(f, a, b, tol=1e-6):
golden_ratio = (math.sqrt(5) - 1) / 2
length = b - a
x1 = a + (1 - golden_ratio) * length
x2 = a + golden_ratio * length
while x2-x1>tol:
print(x1,x2)
if f(x1) < f(x2):
b = x2
x2 = x1
x1 = a + (1 - golden_ratio) * (b - a)
else:
a = x1
x1 = x2
x2 = 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 math
def 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 * length
x2 = a + (1 - ratio) * length
# 迭代搜索
for _ in range(len(fibonacci) - 3):
if f(x1) < f(x2):
b = x2
x2 = x1
x1 = a + ratio * (b - a)
else:
a = x1
x1 = x2
x2 = 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)}")
在有的地方，直接给出的不是迭代次数，而是最终的区间长度的上界L，b1-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_n=F_{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−an=Fn−1/Fn(bn−1−an−1)=FnFn−1Fn−1Fn−2⋯F2F1(b1−a1)
也就是说区间长度最小bn-an=（b1-a1）/F_n<=L，F_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/34=0.6176470588235294，和黄金分割法近似相同。
黄金分割法是fibonacci法的极限形式。
3、三点二次插值法
4、两点三次插值法
5、牛顿法
牛顿法就是在极小点附近选择一个初始点x0，在x0处二阶泰勒展开，并求其驻点。牛顿法不具有全局收敛性，因此初始点的选择很重要，它只是向初始点附近的驻点靠近。
牛顿法的python代码：
import sympy as sp
def newton_method(f, x0, tol=1e-6, max_iter=100):
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')
f=x**3-4*x+5
# 选择初始点
x0 = -10
# 使用牛顿法搜索函数的极小值点
result = newton_method(f, x0)
print(f"极小值点的位置为: {result.n()}")
print(f"函数极小值为: {f.subs({x:result}).n()}")
二、非精确一维搜索
1、Goldstein准则
2、Wolfe准则
3、Armijo准则
