一、变尺度法的基本思想
变尺度法是在牛顿法的基础上发展起来的，它和梯度法亦有密切关系。
我们观察一下梯度法和阻尼牛顿法的迭代公式，即：
式——（1）
和——（2）
分析比较这两种方法可知:梯度法的搜索方向为，只需计算函数的一阶偏导数，计算工作量小，当迭代点远离最优点时对突破函数的非二次性极为有利，函数值下降很快，但是当迭代点接近最优点时收敛速度很慢。
牛顿法的搜索方向为，
不仅需要计算一阶偏导数而且要计算二阶偏导数矩阵及其逆矩阵.计算工作璧很大，但牛顿法具有二次收敛性，当迭代点接近最优点时收敛速度很快。
对这两种方法取其优，去其劣，迭代过程先用梯度法，后用牛顿法并避开牛顿法的赫森矩阵的逆矩阵的繁琐计算，这就是萌生建立“变尺度法”的基本构想。
下面对变尺度法的基本思想进行阐述。
变尺度法所构成的迭代公式为：
——（3）
式中为最优步长因子，由一维搜索
而得;对照无约束优化迭代通式。
变尺度法的搜索方向应为；
是根据需要人为构造的一个n×n阶对称矩阵，它在迭代过程中随迭代点的位置变化而变化。
若在初始点取为单位矩阵取I,则式(3}就成为式(1)表示的梯度法迭代公式，搜索方向为负梯度方向。
以后随着迭代过程不断地修正构造矩阵，使它在整个迭代过程中
逐步地逼近目标函数在极小点处的赫森矩阵的逆矩阵。
当时。
式(3)就成为式(2)表示的阻尼牛顿法迭代公式。
这样，当迭代点逼近最优点时，搜索方向就趋于牛
顿方向。
如能实现这种构想，那就综合了梯度法和牛顿法的优点，不直接计算，而是用变化的构造矩阵去逼近它，使算法更为有效。
构造矩阵在迭代过程中是变
化的，称为变尺度矩阵。
由于变尺度法的迭代形式与牛倾法类似，不同的是在迭代公式中用
来逼近，所以又称为“拟牛顿法”，变尺度法的搜索方向
，最终要逼近牛顿方向，故又称为拟牛顿方向。
实现上述变尺度法的基本思想，关键在于如何产生这一合乎要求的变尺度矩阵，下面对此进行重点讨论。
二、构造变尺度矩阵的基本要求
1.为了使拟牛顿搜索方向朝着目标函
数值下降的方向，必须为对称正定矩阵。
证明如下：
若有目标函数f(X}由点沿方向具有下降的性质，即，根
据梯度的性质，可知搜索方向与负梯度方向之间的夹角应成锐角，即两者的点积应大于零
将代入上式，则有
用矩阵表示为或
这表明变尺度矩阵必须是对称正定矩阵才能保证变尺度算法拟牛顿搜索方向是函数值下降方向。
2.要求构造的变尺度矩阵具有简单的迭代形式，能利用本次迭代信息以固定的格式构造下一次迭代的变尺度矩阵，可以写成
——（4）
式中称为校正短阵。
从上式可知，若确定了初始变尺度矩阵(通常取为单位矩阵I，若再确定，则可得；确定，又可得…，式（4）就是产生变尺度矩阵序列{(k=0，1，2，…)}的基本迭代公式。
3.为使逐次构造的变尺度矩阵最终能遇近赫森矩阵的逆矩阵，必须满足拟牛顿条件。
所谓拟牛顿条件，可由下面导出。
设f (X)为具有连续的一、二阶偏导数的一般形式的目标函数，为使构造的变尺度矩阵仅使用梯度和其他一些易于获得的信息而最终逼近计算繁琐的赫森矩阵之逆矩阵，可先分析一下赫森矩阵H(X)与函数梯度g=▽f (X)之间的关系。
f (X)展开成泰勒级数并仅取到二次项时
该近似二次函数的梯度是
如果取为极值点附近第k+1次迭代点，则有
即
若矩阵为可逆矩阵，则用左乘上式两边，得
——（5）
上式表明与前后两个迭代点的向量差以及梯度向量差
之间的基本关系。
设迭代过程早己进行到第k+1步，、和、均已在此之前求得，根据期望能借助前一次迭代的某些结果来构造下一次的变尺度矩阵以及最终逼近赫森矩阵的逆矩阵，则应迫使第k+1次变尺度矩阵代替式(4)中，即满足
——（6）
式（6）是构造变尺度矩阵应满足的一个重要条件，通常称为拟牛顿条件或拟牛顿方程。
为简便起见，记，，则拟牛顿条件可写成
——（7）
三、DFP法变尺度矩阵递推公式
前已述及，产生变尺度矩阵序列{ (k=0，1，2，…)}采用式（4）的形式，即
可见，在前一次变尺度矩阵给定后，若能确定校正矩阵，则下一个变尺度矩阵就可以确定，而建立校正矩阵的计算公式时又必须使满足式（7）的拟牛顿条件
联立式（4）和式(7)，则有
亦即——（8）
在上式中要直接求解还有困难，因满足上式的矛有无穷多个，实际上建立
的计算公式构成一族算法，校正矩阵取不同的计算公式，就形成各自的变尺度法。
这里介绍W. C. Davidon提出并经过R. Fletcher和M. J. D. Powell修改的求校正矩阵的公式，即所谓DFP公式。
由于和都是n×n阶对称矩阵，所以
也一定是n×n阶对称矩阵。
DFP算法取为如下形式：
——（9）
式中，，为待定常数；，为n维待定向量，将上式代入式（8），则有
即——（10）
满足上式的待定向量，有多种取法，现令
——（11）
——（12）
注意到和都是数量，故可取
由式（11）及（12）可以定出
——（13）
——（14）
将式（11）到式（14）代回到（9）式，得DFP法校正矩阵的计算公式，
——（15）将式（15）代入（4）式，得
——（16）此式通常称为DFP法变尺度矩阵递推公式
四、DFP法迭代过程及算法框图
DFP法的具体迭代步骤如下：
（1）给定初始点，迭代精度，维数n
（2）置0→k，单位矩阵I→，计算。
（3）计算搜索方向
（4）进行一维搜索求，使
得迭代新点
（5）检验是否满足迭代终止条件‖‖≤？若满足，停止迭代，输出最优解：
,；否则进行下一步。
（6）检查迭代次数，若k=n，则置，转向步骤(2)；若k<n，则进行下一步。
（7）计算：。
然后，置k+1→k，转向步骤（3）。
五、DFP变尺度法的算法框图如下所示：
六、DFP法的效能特点
DFP变尺度法综合了梯度法、牛顿法的优点而又避弃它们各自的缺点，只需计算一阶偏导数，无需计算二阶偏导数及其逆矩阵，对目标函数的初始点选择均无严格要求，收敛速度快，这些良好的性能已作阐述。
.对于高维（维数大于50）问题被认为是无约束极值问题最好的优化方法之一。
下面对其效能特点再作一些补充说明。
1.DFP公式恒有确切解
分析DFP公式
为使变尺度矩阵恒有确定的解，必须保证该式右端第二项和第三项的分母为异于零的数，南京大学编的《最优化方法》已证明了这两项的分母均为正数。
2.LIFP法搜索方向的共扼性
南京大学编的《最优化方法》可以确认：对于n维二次目标函数f(X)，由DFP法所产生的搜索方向，，…，为一组关于常量赫森矩阵相共扼的向量。
因此DFP变尺度法也是共扼方向法之一，它具有有限步收敛的性质。
在任何情况下，DFP法对于n维二次目标函数在理论上都将在n步内搜索到目标函数的最优点，而且第n+1次变尺度矩阵
A(n)必等于常量赫森矩阵的逆矩阵。
3.DFP算法的稳定性
优化算法的稳定性是指每次迭代都能使目标函数值逐次下降。
在阐述构造变尺度矩阵
的基本要求中。
已经证明为保证拟牛顿方向目标函数值下降，必须是对称正定矩
阵。
南京大学编的《最优化方法》证明了对于f(X)的一切非极小点处，只要矩阵对称正定，则按DFP公式产生的矩阵亦为对称正定。
通常我们取初始变尺度矩阵为
对称正定的单位矩阵I，因此随后构造的变尺度矩阵序列{(k=1,2, …)}必为对称正定
矩阵序列，这就从理论上保证DFP法使目标函数值稳定地下降。
但实际上由于一维最优搜索不可能绝对准确，而且计算机也不可避免地有舍入误差，仍有可能使变尺度矩阵的正定性遭到破坏或导致奇异。
为提高实际计算的稳定性，除提高一维搜索的精度外，通常还将进行n次(n为目标函数的维数)迭代作为一个循环，将变尺度矩阵重置为单位矩阵I,并以上一循环的终点作为起点继续进行循环迭代，这己反映在迭代过程和算法框图之中。
七、BFGS变尺度法
为进一步改善DFP变尺度法在实际计算中存在的算法稳定性问题，在70年代初
C.G.Broyden，R.Fletcher，
D.Goldfarb和D.F.Shanno提出改进的算法——BFGS变尺度法。
BFGS变尺度法的基本思想和迭代步骤均与DFP法完全相同，也是通过式（4）由校正矩阵求下一次迭代的变尺度矩阵，即，只是式中的校正矩阵△A(k)的计算公式不同于式（14）所示的DFP法。
BFGS法导得的校正矩阵公式为
式中符号的涵义与式（14）相同、虽然构造复杂了一些，但其构造的变尺度矩阵不易变为奇异，因而它比DFP法在实际计算中有更好的数值下降稳定性。
