鲍威尔法是搜索方法基本模式的扩展,它是使用最广泛的直接搜索法并且可以证明是一种共轭方向法[6.7]。一个共轭方向法将减少二次函数有限的步骤。由于一般的非线性函数可以近似合理的接近二次函数的最小值,共轭方向法有望加快,甚至一般非线性目标函数的收敛。本节将给出产生共轭方向法和二次收敛性质的定义。49607
共轭方向
定义:共轭方向 设:A=[A]是一个n×n的对称矩阵,若一组n个向量(或方向){Si}被说成共轭(更准确地说一个共轭)满足S AS =0 对于所有i≠j, i=1,2, …,n,j=1,2, …,n (6.27)
可以看出,正交方向是共轭方向的特殊情况(从方程式(6.27)中获得[A]=[I])
定义:二次收敛法 如果一个最小化的方法,使用精确算法,可以找到n个步骤中的最低点,同时最小化n个变量的二次函数,这个方法就称为二次收敛法。
定理6.1 给定一个二次n维函数变量和两个相互平行的第1和第2维度k<n,让在超论文网平面上二次函数的约束驻点分别为X 和X ,此时加入的线X 和X 是平行于超平面的任意共轭线。
证明:让二次函数表示为:Q(X)= X AX+B X+C
给定Q的梯度 Q(X)=AX+B
因此 Q(X )- Q(X )=A(X -X )
如果S是与任何向量平行的超平面,那么它必须是正交梯度▽Q(X )和▽Q(X )。因此
S Q(X )= S A X + S B=0 (6.28)
S Q(X )= S A X + S B=0 (6.29)
方程式(6.28)减去(6.29),得到
S A (X - X )=0 (6.30)
因此S和(X - X )称为一对共轭。
这个定理的含义如二维空间图6.8所示,如果X 和X 是从两个不同的出发点X 、X ,分别沿单向S搜索得到Q的极小值,将形成沿搜索方向的共轭线(X - X )。
共轭方向
定理6.2 如果一个二次函数
Q(X)= X AX+B X+C (6.31)
按顺序被最小化,一旦沿着每个方向的一组n个相互共轭方向,函数Q的最小值将会在不论起点之前的第n个步骤中被发现。
证明:设X*最小化二次函数Q(X),那么
Q(X )=B+AX =0 (6.32)
给定一个点X 和一组线性独立方向S ,S ,…,S ,总是可以找到这样的常量
X =X + (6.33)
向量S ,S ,…,S 被用作基本向量,如果方向S 是共轭的且它们都不为零,可以很容易的显示S 是线性无关的并且 可以如下确定,将方程式(6.33) 带入(6.32)得到
B+AX +A( )=0 (6.34)
整个方程式乘以S ,得到
S (B+AX )+ S A( )=0 (6.35)
方程式(6.35)可以改写为
(B+A X ) S + S A S =0 (6.36)