第一章非线性规划问题的基础概念
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 基本原理
由于()B AX X f +=?，故有
()()()()()()()
k k k k X X A X f X f -=?-?++11 但
()()()k k k k P X X λ+=+1 故
()()()()
()1,...,2,1,0,1-==?-?+n k AP X f X f k k k k λ （2-1） 任取初始近似点()0X ，并取初始搜索方向为此点的负梯度方向，即 ()()()
00X f P -?= 沿射线()()00P X λ+进行一维搜索，得 ()()()0001P X X λ+= ()()()000min :P X f λλλ
+
算出()()
1X f ?，因为
()()()()()()()
00101=?-?=?X f X f P X f T
T
从而可知()()1
X f ?和()()0
X f ?正交（这里假设()()1
X f ?和()()0
X f ?均不等于
零）。()()1X f ?和()()
0X f ?构成一正交系，我们可以在由它们生成的二维子空间中寻求()1P 。
为此，可令
式中为待定系数，欲使与与A 共轭，由式，必须 故 令
由此可得
以为搜索方向进行最优一维搜索，可得 算出，假定，因和为A 共轭，故 但 故 由于
所有
即和构成一正交系。现由它们生成的三维子空间中，寻求与和为A共轭的搜索方向。令
式中和均为待定系数。由于应与和为A共轭，故须
从而
解之得
令，则，于是
继续上述步骤，可得一般公式如下：
对于正定二次函数来说，由式
由于进行的是最优一维上述，故有
从而
如此，即可得共轭梯度法的一组计算公式如下：
其中为初始近似，
由于以及，故式也可以写成
2.3 共轭梯度法的算法
（1）选择初始近似，给出允许误差
（2）计算并用式和式算出。
（3）一般地，假定已得出和，则克计算其第k+1次近似：
（4）若，停止计算，即为要求的近似解。否则，若，则用式和式计算和，并转向第（3）步。
2.4 数值实验
求下述二次函数的极小点：
解将化成式的形式，得
现从开始，由于
故
于是
故
第三章 变尺度法 3.1 基本原理
假定无约束极值问题的目标函数()X f 具有二阶连续偏导数，X ()
k 为其极小点的某
一近似。在这个点附近取()X f 的二阶泰勒多项式逼近
()()
(
)()
()
()()
X
X H X X X f X
f X f k T T
k k ??+??+≈2
1
（3-1）
则其梯度为
()()()()()
X X H X f X f k k ?+?≈? （3-2） 这个近似函数的极小点满足 ()()()()
0=?+?X X H X f k k （3-3）
从而
()
()
(
)
()
()
k k k X f X
H X
X ?-=-1
（3-4）
其中()
()k X
H 为()X f 在()k
X 点的海赛矩阵。
如果()X f 是二次函数，则()X H 为常数阵。这时，逼近式（3-1）是准确的。在这种情况下，从任一点()
k X 出发，用（3-4）式只要一步即可求出()X f 的极小点（假定()
(
)
k X
H 正定）。
当()X f 不是二次函数时，（3-1）式仅是()X f 在()
k X
点附近的近似表达式。这时，按
（3-4）式求得的极小点，只是()X f 的极小点的近视。在这种情况下，人们常取
()()
()()
k k X f X H ?--1
为搜索方向，即
()
()
(
)
()
()
k k k X f X
H P
?-=-1
()()()k k k k P X X λ+=+1 （3-5）
()()()
k k k P X f λλλ
+min :
（3-5）式确定的搜索方向，为()X f 在点()
k X
的牛顿方向。
3.2 计算步骤 （1）给定初始点()
0X 及梯度允许误差0>ε。
（2）若
()
(
)
ε
≤?2
0X
f
则()
0X
即为近似极小点，停止迭代。否则，转向下一步。
（3）令
()I H
=-
0（单位阵）
()()()
()000X f P H ?-=-
在()
()00P
方向进行一维搜索，确定最佳步长0λ：
()()()
()()
)(min 00000P X f P X f λλλ
+=+ 如此可得下一个近似点
()()()0001P X X λ+=
（4）一般地，设已得到近似点()
k X ，算出()
(
)k X
f ?，若
()
(
)
ε≤?2
k X
f
则()
k X
即为所求的近似解，停止迭代；否则，按式计算()
k H
，并令
()()
()
()k k k X f H P ?-=
在()
k P
方向进行一维搜索，确定最佳步长k λ：
()()()
()())
(min k k k k k P X f P X f λλλ
+=+
其下一个近似点为
()()()k k k k P X X λ+=+1
（5）若()
1+k X 点满足精度要求，则()
1+k X
即为所求的近似解。否则，转回第四步，知道
求出某点满足要求为止。
3.3 数值实验
下面我们针对变尺度法进行数值实验： ()()()
2
22
1654min -+-=x x X f
解：
取 ()
()01
100=
H ，
())
(890=
X
由于
()()()[]
T
x x X f 62,5821--=?
()
(
)()
T
X
f 6.240=?
故
()
()
()
()
()
()
(
)[
]
00000001X f H X
P
X
X
?-+=+=λλ
)()()(()()(
)00
24869246
089
246
01
1008
9
λλλλ--=-=-=
()()
()[]()[]
2
02
0166952484--+--=λλX f
令
()
()
00
1=λd X df
可得
130
170=λ
()
()()[]()T T X 215.8,862.469,2480
01=--=λλ ()
()()
()T
X
X X
785.0,138.3010--=-=?
()()985.41=X f
()()()T
X f 431.4,108.11
-=? ()()
()()()
()T
X f X
f G 569.1,108.25010--=?-?=?
由此可得 ()
()
()
()
()()()()()
()()
()()()()()()
000000
00001G H G H
G G H X G X X
H
H
T
T
T ????-???+=
(
)()()()()()()()()()()()
T
T T
T
569.1,108.25569.1,108.25569.1,108.25569.1,108.25785.0,138.3569.1,108.25785.0,138.3785.0,138.301
10011001
100
1
10---------
--------+
=
()(
)(
)0622.00039
.09961.00622.00308.00077
.01231.00308.001
10-+=
(
)
0315.00038
.11270.00315.0--=
故
()
()
()
()
()11112X f H X
X ?-=λ
()(
)(
)
108.1431.40315.00038
.11270.00315.01862.4215
.8----=
λ
如上求最佳步长，可得 4942.01=λ
代入上式得
()
()
T X
6,52=
这就是极小点。
参考文献：
[1] 胡运权著. 运筹学教程【M 】. 北京：清华大学出版社，2003
[2] 王宜举、修乃华著. 非线性规划理论与算法【M 】. 西安：陕西科学技术出版社， 2008 [3] 袁亚湘著. 非线性规划数值方法【M 】. 上海：上海科学技术出版社，1993 [4] 袁亚湘、孙文瑜著. 最优化理论与方法【M 】. 北京：科学出版社，1997 [4] 王德人著. 非线性方程组解法与最优化方法. 北京：人民教育出版社，1979
[5] 中国科学院数学研究所运筹室编. 最优化方法. 北京：科学出版社，1980 [6] 席少霖、赵凤治著. 最优化计算方法. 上海：上海科学技术出版社，1983 [7] M.阿佛里耳著. 李元熹等译. 非线性规划——分析与方法. 上海：上海科 学技术出版社，1979
[8] 戴彧虹、袁亚湘著. 非线性共轭梯度法. 上海：上海科学技术出版社，1994
[9] 戚厚铎、韩继业、刘光辉著. 修正Hestenes—Stiefel共轭梯度算法. 数学年刊，1996，17A（3）；177—284
[10] 席少霖著. 约束变尺度法【J】. 运筹学学报，1985年01期
[11] 张慧生、王堂生著. 约束变尺度法应用探讨【J】. 新疆工学院学报，1994,15（A）；249—253
[12] 赵凤治、尉继英著. 约束最优化的计算方法【M】. 北京：科学出版社，1991