非线性规划问题的两种方法

由天下分享时间：2025/1/2 22:30:52 加入收藏我要投稿点赞

第一章非线性规划问题的基础概念

1.1非线性规划问题的简介

非线性规划问题时形成于二十世纪五十年代的新兴学科，是运筹学的一个重要分支[1]。库恩和塔克于1951年发表的关于最优性条件(后来称为库恩－塔克条件，又称为K-T条件)的论文是非线性规划正式诞生的一个重要标志。非线性规划问题主要研究的是在线性或非线性的约束函数条件下线性或非线性的目标函数的最优化问题，典型的应用领域包括预报、生产流程的安排、库存控制、质量控制、过程设计等诸多方面。特别是在最近三十多年，非线性规划的发展很快，不断有研究者提出各种新的算法，并其的应用范围也越来越广泛，例如在各种预报、管理方面、最优设计、质量控制、系统控制等领域。 1.2 共轭梯度法简介

共轭梯度法一开始是1908年由Schmidt引入梯度类方法计算效率高,特别是Hestenes和Stiefel在大约1951年经过不断的改进,并且和统计类反演方法结合形成了统计加迭代的组合反演方法,消除了依赖于初始猜测的缺点,成了一种广受欢迎的反演方案。共扼梯度法具有结构简单,计算量小,存储量少且构造搜索方向不需要求解线性方程组以及算法具有二次终止性等优点,因此该算法是最优化方法中相对较好的一种方法,特别是在求解大规模无约束最优化间题时更是得到了广泛的应用\ 1.3 变尺度法简介

变尺度法是近30多年来发展起来的，它是求解无约束极值问题的一种有效方法。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著地优越性，因而使变尺度法获得了更高的声誉，至今仍被公认为求解无约束极值问题最有效的算法之一。

第二章共轭梯度法

2.1 引言

共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一.

（1）最初是由计算数学家Hestenes和几何学家Stiefel于1952年为求正定系数矩阵线性方程组而独立提出的.他们合作的著名文章Method of conjugate gradients for solving linear systems 被认为是共轭梯度法的奠基性文章。

（2）1964年，Fletcher和Reeves将此方法推广到非线性最优化，得到了求解一般函数极小值的共轭梯度法.

（3）共轭梯度法的收敛性分析的早期工作主要由Fletcher、Powell、Beale等学者给出.

（4） Nocedal、Gilbert、Nazareth、Al-Baali、Storey、 Dai、Yuan和Han等学者在收敛性方面得到了不少新成果. 共轭梯度法（conjugate gradient method, CG）是以共轭方向（conjugate direction）作为搜索方向的一类算法。CG法是由Hesteness和Stiefel于1952

年为求解线性方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。这种方法具有二次终止性。 2.2 基本原理

由于?f?X??AX?B，故有

?fX?k?1???fX?k??AX?k?1??X?k? 但

X?k?1??X?k???kP?k? 故

?fX?k?1???fX?k???kAP?k?,k?0,1,2,...,n?1 （2-1）任取初始近似点X?0?，并取初始搜索方向为此点的负梯度方向，即 P?0????fX?0? 沿射线X?0???P?0?进行一维搜索，得 X?1??X?0???0P?0? ?0:minf?X?0???P?0??

?????????????算出?fX?1?，因为

????????从而可知?f?X???和?f?X???正交（这里假设?f?X???和?f?X???均不等于

?fX?1?P?0????fX?1??fX?0??0

101TT0零）。?fX?1?和?fX?0?构成一正交系，我们可以在由它们生成的二维子空间中寻求P?1?。

为此，可令

式中为待定系数，欲使与与A共轭，由式，必须故令

由此可得