拟牛顿法之DFP和BFGS.docx

拟牛顿法之DFP和BFGS 拟牛顿法是牛顿法的改进方法，旨在解决牛顿法中海塞矩阵的逆计算问题。牛顿法的算法思想是给定一个随机初始点，在该点附近对目标函数作二阶泰勒展开，找到下一个迭代点，重复上述方式直至找到极值点。其迭代公式为，式中为海塞矩阵，为梯度。然而，基本牛顿法迭代公式需要计算当前迭代点的一阶导数、海塞矩阵的逆，计算量大且复杂、有可能遇到海塞矩阵非正定而无法求逆的情况，从而导致原始牛顿迭代法失效。 为了克服上述缺点，拟牛顿法就被提出了。拟牛顿法的基本原理依然是牛顿法。不同的是：拟牛顿法不直接求二阶导数，而是采用近似的方式拟合海塞矩阵或海塞矩阵的逆，使其近似矩阵保证正定，从而进行优化迭代。 DFP拟牛顿法是第一个拟牛顿法，是有 Davidon 最早提出，后经Fletcher 和 Powell 解释和改进，在命名时以三个人名字的首字母命名。DFP 算法的迭代格式为： （5）初始化的 D0 为单位矩阵（对称正定），为保证的对称正定，需要保证的对称正定。设 （6）将公式（5）、（6）带入公式（4）可得：令，可将公式（7）化简为： （8）并求得 α 和 β 的值分别为，（9）令（10），则 α 和 β 的值分别为， （11）根据公式（6）、（10）、（11）可求得： （12）根据公式 DFP 算法（5）、（12）可得 DFP 算法的迭代格式为： 至此 DFP 算法的迭代公式推导完毕。 DFP 算法流程： 1 给定初始迭代点 x0 和迭代精确到阈值 tol，初始的海塞矩阵为单位矩阵（对称正定），迭代次数 K； 2 计算 gk 和 Dk 来确定搜索方向 dk= -gk*Dk； 3 利用 Wolfe 方法(步长搜索的方式)得到搜索步长 ak，更新迭代点位置 x(k+1)=xk+ak*dk ； 4 若满足，达到终止条件，结束； 5. 否则，进行迭代 ； 6 令 ，转至步骤 2 继续。 BFGS 算法是另一种拟牛顿法，和 DFP 算法相似，但采用公式（3）近似海塞矩阵，而不是近似海塞矩阵的逆。BFGS 算法的迭代格式也是根据公式（3）和（4）推导的。 拟牛顿法可以克服牛顿法中的计算困难，提高优化迭代的效率和稳定性。DFP 和 BFGS 算法是两种常用的拟牛顿法，广泛应用于 MATLAB 等编程语言中。