Page 165 - 数学建模算法与应用

第六章 非线性规划的研究

Newton 法 法的优点是收敛速度快；缺点是有时不好用而需采取改进措施，
k
此外，当维数较高时，计算 -[ 2 f (x )] 的工作量很大。
-1
（三）变尺度法
变尺度法（Variable Metric Algorithm）是近 20 多年来发展起来的，它不仅
是求解有限极值问题的一种非常有效的算法，而且已经扩展到求解有限极值的问
题。在 1959 年威廉·C·戴维顿（William C. Davidon）首次提出了变尺度法的
思想。他在研究无约束优化问题时，发现可以通过迭代更新一个近似的 Hessian
矩阵来改善搜索方向，从而加快收敛速度。戴维顿的方法被称为 D 方法。1960

年代时罗杰·弗莱彻（Roger Fletcher）和迈克尔·J·D·鲍威尔（Michael J. D.
Powell）在戴维顿的基础上进行了改进，提出了 DFP 法（Davidon-Fletcher-Powell

Method）。DFP 法通过更新一个对称正定矩阵来近似 Hessian 矩阵，显著提高
了算法的效率和稳定性。1970 年代时伯特兰·弗莱彻（Broyden）、查尔斯·雷
比（Charles R. Broyden）、唐纳德·戈德法布（Donald Goldfarb）和汉斯·沙
诺（Hans Y. Shanno）分别提出了不同的变尺度法，这些方法统称为 BFGS 法
（Broyden-Fletcher-Goldfarb-Shanno Method）。在 1980 年代随着计算机技术的发

展，变尺度法在实际应用中的效果得到了验证和推广。研究人员开始探索变尺度
法在约束优化问题中的应用，提出了约束变尺度法（Constrained Variable Metric
Method）。1980 年代初时研究人员将变尺度法与罚函数法、拉格朗日乘子法等

结合，开发了多种求解约束优化问题的算法。
1990 年代至今，变尺度法在优化领域的应用越来越广泛，特别是在大规模
优化问题和非线性优化问题中表现突出。现代优化软件如 IPOPT、SNOPT 等，
集成了多种变尺度法和其他优化算法，能够高效地解决复杂问题。2000 年代至今，
随着机器学习和数据科学的兴起，变尺度法在训练神经网络、优化超参数等方面

得到了广泛应用。L-BFGS 等方法因其高效性和鲁棒性，成为许多机器学习框架
中的默认优化算法。
由于避免了二阶导数矩阵和逆过程计算，并且与梯度方法相比具有更快的收

敛速度，特别是对于高维问题，变尺度方法获得了很高的声誉。下面我们就来简
要地介绍一种变尺度法—DFP 法。这一方法首先由 Davidon 在 1959 年提出，后
经 Fletcher 和 Powell 加以改进。
k
k
我们已经知道，Newton 法的搜索方向是 -[ 2 f (x )] -1 f (x )，为了不计

155