无约束优化的改进变尺度算法【文献综述】

《无约束优化的改进变尺度算法【文献综述】》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业设计文献综述信息与计算科学无约束优化的改进变尺度算法最优化,现在已作为分析许多复杂决策或分配问题所依据的一个原则而牢固地确立起来.利用这种最优化的原理,人们只要把注意力集中于一个使性能数量化并能度量决策特性的单一目标上,就能解决涉及到需要对很多有内在联系的变量进行选值的复杂决策问题.在限制决策变量取值范围的约束下,我们就能使这样一个目标函数取得极大值(或极小值).最代化计算方法是计算数学中的一个十分活跃的分支.随着电子计算机的普及,它已广泛应用于化工、航空、机械、建筑、无线电技术等许多工程技术部门.另外在生产组织、资源分配等管理科学方面,最优化方法也已成为一种重要的决策手段.无约束最

2、优化论述函数在无任何约束之下的极小或极大问题.设是一个定义在维欧氏空间上的函数.把寻找的极小点的问题称为一个无约束最优化问题.可用下列形式表示：其中称为目标函数.虽然,许多实际的最优化间题必须满足一些次要的约束.然而,由于种种理由,对无约束最优化方法的研究仍然是根重要的.虽然实用规划问题大多是有约束的,但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解.事实上,解约束问题的许多算法是经过Lagrange乘子把约束问题转化为一系列的无约束问题.或经过惩罚函数和障碍因数把约束问题转化为一系列的无约束问题.　　解无约束最优化方法大致可以分成两类：一类在求解过程中无需计算目标函数的导数

3、,称为直接法；一类在求解过程中要计算目标函数的导数,称为解沂法.直接法一般用在目标函数的导数难以求得的情况,解析法一般用在目标函数的导数较易求得的情况.使用导数的解沂法中最古老的算法大概应是最速下降法了.早在1847年,Cauchy就提出了最速下降法,即梯度法.对于变量不多的某些问题,这些方法是可行的.但对于变量较多的一般问题,就常常不适用了,其原因是最速下降法收敛速度较慢.1964年,R．Fletcher,C．M.．Reeves给出了一个共轭梯度法,避免了最速下降法产生的锯齿形现象,并且具有二次终止性.还有一类收敛性能较好的算法就是牛顿法和变尺度法.牛顿法要计算目标函数的二阶导数,一般

4、计算量较大,也正因为如此,牛顿法的收敛速度很快,是二阶收敛的,但不稳定.变尺度法是既保持了牛顿法收敛速度快的特点,是超线性收敛的,又克服了牛顿法计算量大的缺点.最早的变尺度法是W．C．Davidon于1959年提出,且经R．Fletcher和M．J．D．Powell于1963年加以简化得到的,即DFP法.C．G．Broyden于1967年又根据求解非线性方程组的方法推导出了—类变尺度法.后来,1970年C．G．Broyden,R．Fletcher,D．Goldfarb和D．F．Shanno提出了一个秩2的校正公式,通常称为BFGS公式.而本论文,主要便是对变尺度算法作介绍和进一步的研究.

5、在文献[5],[6]中给出了极值点极其存在条件的定义,在此基础上对算法做研究.变尺度法是对牛顿法的修正,它不再是计算二阶偏导数的矩阵和它的逆矩阵,而是设法构造一个对称正定矩阵H来代替Hesse矩阵的逆矩阵,使其逐渐逼近.从而在"拟牛顿"的条件下优化目标函数.由于对称正定矩阵H在迭代过程中是不断修正改变的,它对于一般尺度的梯度起到改变尺度的作用,因此H又称变尺度矩阵.由于这类方法相当于每一轮的度量是变化的最速下降法,通常又叫做变尺度法.假定无约束极值问题的目标函数具有二阶连续偏导数,为对其极小点第k次迭代之后得到点.在该点将目标函数展成Taylor级数,取二阶近似,得到可推出上式即为（1）

6、容易推证,若是带有正定系数矩阵A的二次函数：则（1）将成为等式,即,且此时,只需计算目标函数的一阶导数,就可以依据方程估计该处的Hesse矩阵的逆.为了用不包含二阶导数的矩阵近似牛顿法中的Hesse矩阵的逆矩阵,必须满足,即拟牛顿条件而矩阵是随迭代步骤的变动而变化的,假定每一个这样的矩阵由迭代格式产生,称为修正矩降.代入拟牛顿条件,有或（2）为了构造出每一轮的搜索方向,在开始时可以简单地取为单位矩阵.然后,在每一第k轮利用拟牛顿条件按基本关系式（2）产生修正短阵,并利用其使得到下一个迭代矩阵.如此反复迭代,可以产生一系列迭代矩阵从而相应地确定出一系列搜索方向.其中,DFP法利用DFP公式

7、,而BFGS法利用BFGS公式来产生迭代矩阵.总体来说,DFP法与BFGS法具有类似的收敛性定理及部分性质,但BFGS法具有更好的数值稳定性.1997年,Liaoaiping对BFGS法作了改进,提出了一种双参数修正的拟牛顿法,具有更好的适应性，其形式为（3）其中,2003年,Xiaoyunhai等人基于Weizengxin提出的改进方法中的,将BFGS公式中的第三项分子中的改为,从而给出了另一种改进形式,.2006年,Weizen