精确一维搜索
试探法
精确一维搜索就是通过迭代取减少搜索区间
对于搜索区间[a, b]
在这个区间中找连个互不相同的试探点p1 p2获取f(p1), f(p2), 设p1 < p2
若f(p1) < f(p2) 则丢弃区间 [p2, b]
若f(p1) >= f(p2) 则丢弃区间 [a, p1]
这样就达到了通过一次迭代减小搜索区间的目的
当搜索区间长度< 给定的误差e时，终止迭代
不同的试探法，其实不同的是选取p1, p2的方法
0.618法
0.618法就是
p1 = a * 0.618 + b * (1-0,618)
p2 = a * (1-0,618) + b * 0.618
斐波那契法:
对与第i次迭代
p1 = Fi+1 / (Fi + Fi+1) * a + Fi / (Fi + Fi+1) * b
p2 = Fi / (Fi + Fi+1) * a + Fi+1 / (Fi + Fi+1) * b
插值法
通过已有的条件构造插值函数
通过求插值函数的极小值点去近似已有函数的极小值点
三点二次插值
已有三个点（p1,f(p1))，（p2,f(p2))，（p3,f(p3))
通过拉格朗日插值法获取插值函数
求得插值函数的倒数为0获取插值函数的极小值点（p0,f(p0))
现在我们有四个点了，通过这种方法得到四个点后，通过试探法的迭代方法去缩小区间即可
终止准则也同迭代法的终止准则
二点二次插值
给定初始步长alaph和步长缩减因子
我可以获得x的函数值和他的导数
获取第一个点x0,f(x0), f'(x0)
给定步长alaph，往函数下降的方法走alaph得到x1
若f(x1) > f(x0) + f'(x0) * abs(x0 - x1) 则步长不断以alaph = 2*alaph增加直到不满足条件
通过f(x1), f(x0), f'(x0)计算插值函数，并求得最优点u
若f‘(u) < e 终止迭代
否则将u作为初始点，继续迭代步长alaph = p * alaph
一般来说 alaph = 2 p = 1/10
二点三次插值
给定初始步长alaph和步长缩减因子
我可以获得x的函数值和他的导数
获取第一个点x0,f(x0), f'(x0)
给定步长alaph，往函数下降的方法走alaph得到x1
计算得到f(x1), f'(x1)
若f'(x1) * f'(x0) > 0 则将x1做为x0 alaph = 2 * alaph的方式迭代直到不满足条件
通过f(x1),f'(x1), f(x0), f'(x0)计算插值函数，并求得最优点u
若f‘(u) < e 终止迭代
否则将u作为初始点，继续迭代步长alaph = p * alaph
一般来说 alaph = 2 p = 1/10
非精确一维搜索
Goldstein方法
对于函数Φ(x) 我能知道在任意一点的函数值与倒数
对于区间[umin, umax]，置精度要求0<β1<β2<1
一般来说umin= 0 umax = +∞
取初始点u0
若Φ(u) > Φ(0) + β1 * Φ(0)’ * u
umax = u
若Φ(0) + β2 * Φ(0)‘ * u <= Φ(u) <= Φ(0) + β1 * Φ(0)’ * u
达到精度要求，停止计算
若Φ(u) < Φ(0) + β2 * Φ(0)‘ * u
umin = u
当 umax = +∞时，置下一步的试探点为u = 2 * umin
否则u = (umin+umax) / 2
Armijo方法
取一大于0的数M，0<β1<1
Φ(u) <= Φ(0) + β1 * Φ(0)‘ * u
且Φ(u*M) >= Φ(0) + β1 * Φ(0) ’* u
条件终止
Wolfe-Powell方法
置精度要求0<β1<β2<1
Φ(u) <= Φ(0) + β1 * Φ(0)‘ * u
Φ’(u) <= β2 * Φ(0)'