[拼音]:wuyueshu youhua fangfa [外文]:unconstrained optimization method 研究寻求多元函数ƒ(尣)=ƒ(x1,x2,…,xn)在整个实n维空间Rn中局部极小值点的数值方法。它在非线性规划的研究中占有很重要的位置,除了本身的意义与应用外,它也是许多带约束优化方法的基础。 大多数无约束优化方法都是迭代法,每一次迭代都从某一点尣 ƒ(尣 的点尣 往往以直观或以计算实践为基础而产生,这类算法的特点是只要求计算函数值本身,因而易于使用,但是与另一些要求计算偏导数值的方法相比,又收敛得慢。所以直接法常常用于变量极少而函数比较复杂且不易计算偏导数的情形。较为常用的直接法有鲍威尔法、单纯形调优法和模式搜索法。 最陡下降法和牛顿-拉弗森方法在要求计算偏导函数值的算法类中,一般取移动方向s
这里的T表示矩阵(或向量)的转置运算,墷ƒ(尣)表示ƒ(尣)在点尣上的梯度,即
式(2)保证了在以尣
上一定有点尣适合ƒ(尣)<ƒ(尣
式中Hk是一n阶的对称正定矩阵。 通常,步长λk的选取原则是取λk使尣
亦即点尣 只要墷ƒ(尣 可以证明,在由尣 牛顿-拉弗森法则以 ƒ(尣)的二次近似
但这样得到的 尣 在一些有关ƒ(尣)的假设下,对于这两个古老的方法,都可证明墷ƒ(尣
式中A对称正定,只要A不是数量矩阵αI,那么尣
所示。 与此相反,牛顿-拉弗森方法收敛得快。特别对于形如(6)的二次严格凸函数,只要一次迭代,就能达到最优解尣*,即使对于一般的函数ƒ(尣),在某些假设下,也可证明{尣 共轭梯度法与变尺度法是既有较快的收敛速度又无需计算二阶偏导函数的算法。 共轭梯度法由于在局部最小值点的邻近,函数的性状与二次凸函数 (6)十分相似,所以对于一个好的寻优方法,人们要求它在应用于二次凸函数时有较快的收敛速度,即使最小值点不能象牛顿-拉弗森方法那样一步达到,也应在有限步内达到。事实上,沿着y空间中n个两两正交的方向依次作线性搜索,一定可以达到函数1/2 (y-y*)T(y-y*) 的最小值点y*。于是通过变换y=A1/2尣,沿着尣空间中n个满足
的方向s(1),s(2),…,s(n)依次作线性搜索,就一定能达到函数(6)的最小值点尣*。满足式(7)的n个非零方向 s(1),s(2),…,s(n)称为关于矩阵A的共轭方向系。20世纪60年代R.弗莱彻和C.M.里夫斯用梯度向量构造出共轭方向系,提出了共轭梯度法。它从任意的初始点尣(1)开始,在第k次迭代时取移动方向 ![]() 然后沿着半直线(3)作线性搜索得到尣 ![]() 而若不采取周期性重开始的策略,其收敛阶仅为线性。共轭梯度法由于只需要存贮几个向量,特别适宜于解大型问题。当然,还需要采用条件予优的方法以加速收敛。 变尺度方法也有人称为拟牛顿方法。这是近二十多年来发展起来的一类很有成效的寻优方法。理论分析和计算实践都表明这类方法的收敛速度较快,同时又无需计算二阶偏导数矩阵。这类方法的共同特点是:移动方向s
步长λk和下一点尣 第一个变尺度法是W.D.戴维登于1959年首先提出的,而由 R.弗莱彻和 M.J.D.鲍威尔在理论上作了研究并于1963年公开发表,所以通常称为DFP方法,在这个方法中,Hk(k>1)的定义如下:
由于DFP方法的成功,在其后十多年间,又提出了许多变尺度方法,这些方法只在Hk(k>1)的定义方法上有所不同。在理论上,只要尣 无论是DFP方法或者 BFGS方法,都有以下一些性质: (1)只要初始的矩阵H1正定,那么以后的各个矩阵Hk(k≥1)也都正定; (2)将它们应用于二次严格凸函数(6)时,由算法所确定的移动方向序列s(1),s(2),…,s(n)是一组关于矩阵A的共轭方向系,所以最多经过n次迭代,一定能够达到二次严格凸目标函数的最小点尣*; (3)理论上可以证明这两个算法在一定的条件下都是超线性收敛并且都是n步二阶收敛的。 不精确线性搜索或可接受点准则前述各法都是建立在线性搜索的基础之上的,即取尣 一类具有特殊形式的无约束优化问题。在这类问题中,目标函数ƒ(尣)是一些函数的平方和,即
|