鲍威尔法

简介

鲍威尔法，严格来说是鲍威尔共轭方向法，是迈克尔J.D.鲍威尔提出的一种求解函数局部最小值的算法。该函数不能是可微分的，并且不会导出衍生函数。

该函数必须是固定数量的实值输入的实值函数。通过传入一组初始搜索向量，通常会传入N个搜索向量（譬如)这是与每个轴对齐的法线。

计算过程

鲍威尔法依次通过沿着每个搜索向量的双向搜索使功能最小化。沿着每个搜索向量的双向线搜索可以通过黄金分割搜索或黑雁的方法来完成。让每个双向线搜索中找到的最小值为

其中是起始点，是沿着的双向搜索确定的标量。然后可以将新位置（）表示为搜索向量的线性组合，即

新的位移矢量

成为新的搜索向量，并被添加到搜索向量列表的末尾。

同时，对新方向贡献最大的搜索向量，即最成功的搜索向量（）搜索向量列表。新的N个搜索向量集合是

该算法迭代任意次数，直到没有明显的改善。

该方法对于计算连续但复杂函数的局部最小值是有用的，特别是没有基础数学定义的函数，因为不需要导数。基本算法简单；复杂度在沿着搜索向量的线性搜索中，这可以通过布伦特法来实现。

布伦特法

定义

布伦特方法(the method of Brent)是在二分法或试位法的基础上，借助二次插值方法进行加速，有利用反插值方法来简化计算而形成的一种方法。

内容

假如知道f(x)的零点x’在一个不太大的区间内，而且已知f(x)在区间的端点处的函数值

以及在内的近似解和，接下来利用这已知的三个点以及它们所对应的函数值作插值抛物线。与Muller方法不同的是，把与的对应关系反过来用，相当于用 替代方程组

**************** (1)

**************** (2)

**************** (3)

中的，而方程组的常数项 则用这里的替换。所以对应的插值抛物线的一般形式为

**************** (4)

**************** (5)

**************** (6)

**************** (7)

由（5）（6）（7）式可以得利用Muller方法，可以写成a,b 的表达式。

在（4）中令,可以得到下一个近似点为

**************** (8)

其中相当于校正项。

Brent方法的下一个规则是，如果得到的x仍然在区间内，则用根据

的符号替换或，用x替换；如果所得到的x不在区间内，则暂时放弃反抛物线插值法，继续用二分法或试位法。

实际上，我们可以利用二分法所得到函数顺便采用反插值方法试探一下。