求解非线性无约束优化问题的两种方法的分析.pdf

￡望叁兰堑圭兰垒篁塞１

第一章预备知识

§１．１共轭梯度方法
§１．１．１引言
共轭梯度法足最优化中最常用的方法之一。它具有算法简便，存储需求小等优点，
十分适合于大规模优化问题．在石油勘探，大气模拟，航天航空等领域出现的特大规模
的优化问题是常常利用共轭梯度法求解。在所有需要计算导数的优化方法中，最速下降
是最简单的，但它速度太慢。拟牛顿方法收敛速度很快，被广泛认为是非线性规划的最
有效的方法。但拟牛顿法需要存储矩阵以及通过求解线性方程组来计算搜索方向，这对
于求解诸如上述问题等一些大规模问题几乎是不太可能办到的，共轭梯度法在算法的简
便性，所需存储量等方面均与最速下降法差别不大，而收敛速度比最速下降法要快。非
线性共轭梯度法的收敛性分析的早期工作主要由Ｆｌｅｔｃｈｅｒ，Ｐｏｗｅｌｌ，Ｂｅａｌｅ等学者给出的，
近年来，Ｎｏｃｅｄａｌ，Ｇｉｌｂｅｒｔ，Ｎａｚａｒｅｔｈ等学者在收敛性方面得到了不少的结果，使得共轭梯
度法的研究由又热了起来．我国的学者也在共轭梯度法的理论研究中也取得了一定的成
绩。例如中科院应用数学所的韩继业，戴口等．
§１．１．２共轭方向法
共轭梯度法最本质的是共轭性质，共轭性是正交的一种推广。
定义１．１．２．１：设Ｗ∈咿×ｎ对称正定，ｄｌ，ｄ２，…，ｄ。是咿中的一组非零向量，如果

盯Ａｄｊ＝０，（ｉ≠Ｊ）．（１．１）

则称ｄ１，ｄ２，…，ｄ。是相互Ａ一共轭。
显然可见，如果ｄｌ，ｄ２，…，ｄ。相互Ａ一共轭，则它们是线性无关的。设Ｊ是单位阵
则知，一共轭就是正交。一般共轭方向法步骤如下：
算法１．１．２．１：（一般共轭方向法）
给出∞＋的初始点Ｘｌ，
步ｌ：计算ｇｌ＝ｇ（Ｘ１）．
步２：计算ｄｌ，使（ｆ｛’９ｌ＜０．
步３：令女＝１．
步４：计算口ｋ和Ｘｋ＋１，使得
ｆ（ｘｋ－Ｆ‘１ｋｄｋ）。Ｉ。ｊ１１，‰十“呶），

Ｘｋ＋１＝Ｘｋ＋ｖ。ｋｄｋ．
步５：计算以＋ｌ使得ｄ矗１Ｇｄｊ＝０，Ｊ＝１，２，…ｋ．
步６：令ｋ：＝ｋ＋１，转步４．
共轭方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性，这
就足下面的共轭方向法基本定理。
定理１．１．２．１：（共轭方向法基本定理【１１）对于正定二次函数，共轭方向法至多经ｎ步精
确线性搜索终止；且每一ｘ｛＋１都是，（ｚ）在Ｘｌ和方向ｄｌ，…，ｄｉ所张成的线性流行驯ｚ＝
￥ｌ＋∑：：ｔｌｊｄｊ１，Ｖｑ）中的极小点。
证明：因为Ｇ正定且共轭方向ｄ１，ｄ２，…线性无关，故只要证明对所有ｉ≤ｎ一１，有

９§１ｄｊ＝０，Ｊ＝１，…，｛，（１２）

（既沿流行中的任何直线的斜率为零），就可得出定理中的两个结论．事实上，由于

珊＝ｇｋ＋ｌ一９≈＝Ｇ（ｚｋ＋ｌ一￡＾）＝ａｋＧｄｋ
２００４年广西大学硕士学位论文２

故有当ｊ＜ｉ时

｜｜考由＋Ⅳ由
，＋；∑卅Ｔ≈
≈

南＋＆ｄＧ白３
。∑卅≈ｒ女
再ｍ々

在（１．３）中两项为零分别由精确线性搜索和共轭性得到。当ｊ＝ｉ时，直接由线性搜索可
知
９‘１吨＝０

从而有（１．２）成立。
§１．１．３非线性共轭梯度法与Ｚｏｕｔｅｎｄｉｊｋ条件
§非线性共轭梯度法：
考虑无约束优化问题
ｍｉｎ｛ｆ（ｘ）Ｉｚ∈舻），（１．４）
给出一初始值ｚ。，算法迭代产生ｚ２，ｚ３，…。希望某一ｚ≈是（１．４）的解或点列收敛于解。
在第＆次迭代，当前迭代点为。≈，线搜索型的方法将产生一搜索方向ｄｋ∈乳“。然后下一
个迭代点
茁≈＋ｌ＝茁七＋ｏ≈ｄ≈，（１．５）
其中ＯＺｋ＞０是步长因子。它满足某些线性搜索条件．信赖域型的方法在当前迭悠枣周国
下的一邻域一中！荤袋寝杀求得一试探点。ｋ＋ｓ型的方法的ｋ，然后通过某种判断，在ｚｋ与每步迭代Ｘｋ＋ｓ主要ｋ之间挑选其由两一为部分组成：第一部分是搜索方向的寻找；
一个线搜索型的方法的每步迭代主要由两部分组成：第一部分是搜索方向的寻找；
第二部分是步长因子ａ＾的计算。搜索方向如通常要求是下降方向，即
露Ｖｆ（ｘｋ）＜０．

上式保证一定存在ａ＞０，使得

ｆ（ｘｋ＋ｏ以）＜，（。ｔ）．
也就是说，沿着ｄ≈方向搜索，一定可找到比ｚ＾更好的点。记９（。）＝Ｖｆ（ｘ）以及鲰一９（。ｋ）。
最简单的下降方向是负梯度方向：
ｔ。ｏｄｋ＝一９＆＋——一一ｉｆ五丽∑１‘
ｆ（ｘ）连续时，只要鲰≠。０，ｌ则对任何ｉｒａｌ向量ｄ∈咿且俐ｉ１２＝１，有ｒａ＋ｊｆ（。ｃｋ）盟－－ｆ丛（ｘｋ－－堕ｇｇｋ／生ｌｌｇｋｌｌ２）＝一淼＜１

正因如此，我们称负梯度方向为最速下降方向，利用最速下降方向作为搜索方向的方法
称为最速下降法。牛顿法的搜索方向为：

ｄ＾＝一（Ｖ２，（。々））～ｇｋ．（１．６）

它需要计算ｎ×ｎ的Ｈｅｓｓｅ矩阵Ｖ２，（ｚ＾）。如果Ｖ２，（ｚｋ）非正定，则牛顿法的搜索方向
（１．６１可能不是下降方向