（基础数学专业论文）无约束最优化问题牛顿型算法的若干研究.pdf

a b s t r a c t n e w t o nm e t h o d sa r et h eo l d e s ta n dm o s te f f i c i e n to n e sf o rs o l v i n gu n c o n s t r a i n e d o p t i m i z a t i o np r o b l e m sb yn o w i n t h i sp a p e r ，w ep r o p o s ean e wm o d i f i e dd a m p e dn e w t o n a l g o r i t h mf o rs o l v i n gt h eo b j e c t i v ef u n c t i o nm i n i m i z a t i o np r o b l e m s t h ea l g o r i t h mi ss h o w n t oc o n v e r g eg l o b a l l y q u a s i n e w t o nm e t h o d sa r ea l s ot h em o s te f f i c i e n to n e sf o rs o l v i n g u n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s t r a d i t i o n a ld f pa l g o r i t h mn e e d ss t r o n gc o n d i t i o n st o k e e pt h ea p p r o x i m a t ei n v e r s em a t r i xh to ft h eh e s s i a nm a t r i xp o s i t i v ed e f i n i t e w ep r o p o s e an e wd f pa l g o r i t h m i th e l p s h t t om a i n t a i np o s i t i v ed e f i n i t eb yav e r yg o o dq u a l i t a t i v e r e s u l t a n di t p r o v e s t h a tt h em e t h o dw i t ha c c u r a t el i n es e a r c hc o n v e r g e sg l o b a l l y q u a s i - n e w t o n e q u a t i o n sp l a y ak e yr o l ei nq u a s i - n e w t o nm e t h o d sf o ro p t i m i z a t i o n p r o b l e m s t h eo r i g i n a lq u a s i - n e w t o ne q u a t i o n so n l ye m p l o yt h eg r a d i e n to ft h eo b j e c t i v e f u n c t i o n ，b u ti g n o r et h ev a l u ei n f o r m a t i o no ft h ea v a i l a b l eo b j e c t i v ef u n c t i o n i no r d e rt ou s e m o r ev a l u ei n f o r m a t i o n ，m a n yp e o p l es t u d yt h eq u a s i n e w t o nc o r r e c t i o nf o r m u l aa n dh a v e m a d eg o o dp r o g r e s si nt h ef i e l d i nt h i sp a p e r ， c o n v e xu n c o n s t r a i n e do p t i m i z a t i o np r o b l e m s t y p el i n es e a r c hc o n v e r g e sg l o b a l l y w ep r o p o s ean e wb f g sa l g o r i t h mf o rt h en o ， a n di t p r o v et h a tt h em e t h 。dw i t hg 。l d s t e i n 卜， k e y w o r d s ：n e w t o n t y p em e t h o d s ，c o n v e r g e n c e ，n u m e r i c a lr e s u l t s 4舢9肿7 删447niii删y 0 0 中文文摘 非线性规划的最优化理论与算法是- - f q 新兴的学科，它是在电子计算机出现以后， 由于大量的社会实践的需要而迅速发展起来的。它是- f 3 在复杂的实际环境中遇到的许 多可能的决策中挑选最佳决策的科学，因而在许多方面均有广泛应用。非线性规划的最 优化理论与算法主要包括一些传统的理论与算法，如无约束和带约束优化问题的最优性 条件，无约束优化问题的下降算法、牛顿法、共轭梯度法、拟牛顿算法等。【1 l 牛顿法是求解无约束最优化问题最古老的算法之一，但目前为止它的改进形式仍不 失为最有效的算法之一。修正牛顿法是对目标函数的h e s s i a n 矩阵进行修正。本文提出 一类新的修正阻尼牛顿法如下： 1 ) 当h e s s i a n 矩阵g 。正定时，假如目标函数梯度g 0 ，那么取牛顿方向为下降方 向，a ( ) = 一g f lg ( ，于是小) 7 9 ( ) = 一) g ka ( ) 0 时，一a 便为下降方向， 此时改取= g k dg 3 ) 如果) t g 。= 0 ，或者g t 奇异，此时采用负梯方向，即取a 一g 得到此修正算法的全局收敛性质如下： 定理1 ：如果目标函数厂o ) 二阶连续可微有下界，此修正阻尼牛顿算法满足铀g 。时有 界且风的条件数有界时，那么! i m g = o 。 此修正阻尼牛顿算法能保证目标函数h e s s i a n 矩阵的正定性，并证明了对一般的非 凸目标函数，该算法是全局收敛的。 拟牛顿算法是求解非线性无约束优化问题的最有效、理论上也是最成熟的算法之 一。传统的d f p 算法对保持目标函数的h e s s i a n 矩阵的近似矩阵风的逆矩阵h 。的正定 性需要较强的条件，本文对d f p 算法提出新的校正公式为 。， 日，7 切。日i 风“f f ih t + 磊赢祷一举毒尹 此d f p 算法有如下性质包括其全局收敛性： 定理1 ：设h t 正定，则日m 正定的充分必要条件是亭。叼0 假设l 1 ) ，：r 4 _ 尺二阶连续可微 y 2 ) 目标函数f ( x ) 满足，存在胁，m 0 ，对任意x 工 o ) m 俐2 z t a ( x ) z m 2 ，v zer “ 定理2 ：设目标函数f ( x ) 满足假设1 ，则精确线搜索步长规则下的d f p 方法产生的 点列缸件) 收敛到极小点x 。 最初的拟牛顿校正公式仅仅利用了目标函数的一阶导数，而忽略了可利用的目标函 数值。为了利用更多的可利用的信息，很多人对拟牛顿校正公式进行了研究，取得很好 的进展。本文研究一般非凸目标函数的极小f , - j 题的拟牛顿算法及其收敛性，对无约束优 化问题提出一类改进的b f g s 算法，校正公式为 曰t + = 吼一嚣+ i ；罟务舅哿叼。) 刁仲) t ， 其中u k ( p ) 一p s 印皓) 7 ，7 ( ) 亭) 1 r + 2 ( 1 一p 少t ， 其中k 一 + l 一厂七一g ( ) 7 亭， v p s o ，1 】 此算法有如下性质包括其全局收敛性： 定理1 - 设色正定，则此校正公式使b + ，保持正定 假设l ：设目标函数f ( x ) 在尺“上是二阶连续可微函数且有下界，其水平集 上o o ) = x l f ( x ) s ，o o ) ) 有界 定理2 ：在假设1 下，本文中改进的b f g s 拟牛顿算法或者对某个k 有g = o ，或者有 避i n f l l = 0 定理3 ：在假设1 下，且当尼一时，亭呻0 ，如果存在缸) 的一个聚点工。满足 g ( x 。) 一o _ r g ( x 。) 正定，那么忸。) 整个序列收敛于z 数值实验说明了算法的有效性，且当p 取适当的值时，会提高算法的计算效率。 i v 目录 中文摘要i a b s t r a c t ii 中文文摘i i i 序言1 第一章概论3 一、问题的提出3 二、最优化问题的分类5 三、非线性规划基本概念5 四、算法的衡量标准6 第二章修正阻尼牛顿算法8 一、前f 言8一、刖舌秽 二、具体算法9 三、此修正算法的全局收敛性1 0 四、数值实验1 1 五、小结1 2 第三章一般无约束优化问题的拟牛顿算法1 4 一、算法描述1 4 二、算法的全局收敛性1 4 三、小结2 0 第四章一类改进的b f g s 算法2 2 一、具体算法o ooilo t0 00 0 0000 2 2 二、算法的全局收敛性2 4 三、数值实验2 5 四、小结2 7 结论2 9 注释3 0 参考文献3 l 福建师范大学学位论文使用授权声明3 4 序言 最优化理论与算法是一门新兴的学科，它是在电子计算机出现以后，由于大量的社 会实践的需要而迅速发展起来的。它是一门在复杂的实际环境中遇到的许多可能的决策 中挑选最佳决策的科学，因而在许多方面均有广泛应用，如在空间科学、化工、电子、 建筑工程等工程设计方面，在资源的利用、生产管理、企业的投资等方面得到日益广泛 的应用j， 最优化理论与算法至今已出现线性规划、整数规划、非线性规划、几何规划、动态 规划、随机规划、网络流等许多分支 2 - 3 。非线性规划作为运筹学一个重要分支在近二 十年得到了快速发展，新的理论和算法不断出现。非线性规划的最优化理论与算法主要 包括一些传统的理论与算法，如无约束和带约束优化问题的最优性条件，无约束优化问 题的下降算法、牛顿法、共轭梯度法、拟牛顿算法，约束优化问题的可行方向法、罚函 数法和s q p 方法等 i 1 。 牛顿法是求解无约束优化问题最古老的算法之一，但目前为止它的改进形式仍不 失为最有效的算法之一。修正牛顿法是对目标函数的h e s s i a n 矩阵进行修正。1 9 6 6 年 g o l d f e l d 等人提出了g o l d f e l d 算法【l 】，1 9 6 7 年g o l d s t e i n 和p r i c e 提出了g o l d s t e i np r i c e 修正算法【1 1 ，这两个算法在一定的条件下有全局收敛性。1 9 8 8 年冯慈璜提出非线性方程 f ( x ) ；0 的一类修正牛顿法，其中f ：尺4 一只是f r 6 c h e t 可导算子【4 1 1 9 9 6 年何良德对 非线性方程的迭代式进行改进，得到一种加速的修正牛顿法 5 1 2 0 0 3 年陈元媛对 s h a m a n s k i i 修正牛顿法的全局收敛性定理进行了改进和推广，使其应用范围更广【6 1 同 年，郑权在合理的条件下，证明了求解非线性方程组精确牛顿法和非精确修正牛顿法的 线性收敛性【7 1 2 0 0 5 年陈以平以解非线性方程的常微分方程方法和传统牛顿法为基础， 提出方程求根的一种具有参数的修正牛顿迭代法，并证明了这种迭代法具有三阶收敛速 度【钔2 0 0 6 年李欣林提出一种新的修正c h o l e s k y 分解算法【9 1 ，得到较好的收敛性2 0 0 8 年苗慧提出了一个改进的求解多项式方程的修正牛顿法1 1 0 1 ，其收敛速度大大提高 本文提出一类新的修正阻尼牛顿法。若h e s s i a n 矩阵正定且目标函数的梯度不为零， 则搜索方向取牛顿方向；若h e s s i a n 矩阵不正定且非奇异，且目标函数的梯度的转置和 牛顿方向的数量积大于零时，搜索方向采用负牛顿方向；若h e s s i a n 矩阵奇异或者目标 函数的梯度的转置和牛顿方向的数量积等于零时，搜索方向则采用负梯度方向。因此该 算法能保证搜索方向始终为下降方向，此算法能保证目标函数h e s s i a n 矩阵的正定性， 并证明了对一般的非凸目标函数，如果目标函数二阶连续可微有下界，此修正阻尼牛顿 算法满足h e s s i a n 阵有界且其条件数有界时，该算法是全局收敛的。 拟牛顿算法是求解非线性无约束优化问题的最有效、理论上也是最成熟的算法之一 1 9 5 9 年d a v i d o n 提出第一个秩2 校正法拟牛顿法d f p 法，1 9 6 3 年f l e t c h e r 和p o w e l 把这个方法重新改写并证明之后，拟牛顿算法的研究倍受关注。在精确线搜索之下，拟 牛顿算法具有二次终止性 1 1 。1 9 7 1 年p o w e l 【l l 】证明了一般的非线性目标函数为一致凸的 二阶连续可微函数且采用精确线搜索时d f p 算法具有全局收敛性，且当h e s s i a n 矩阵满 足l i p s c h i t z 条件时，收敛速度是超线性的。1 9 7 2 年，p o w e l 【1 2 】证明了目标函数为凸函 数时d f p 算法的收敛性；对于一般的非凸目标函数，p o w e l l 证明了n = 2 时d f p 算法全局 收敛性，当n 2 时一般的非凸目标函数的拟牛顿法全局收敛性，至今仍是一个没有解 决的问题。1 9 7 6 年，p o w e l 1 3 1 证明了当采用非精确搜索时拟牛顿法的全局收敛性，他证 明了当目标函数为凸函数且二阶连续可微有下界，当采用w o l f e 线搜索原则时b f g s 算 法产生的迭代序列的任何聚点必为极小点；而当目标函数为一致凸函数且h e s s i a n 矩阵 满足l i p s c h i t z 条件时，收敛速率是超线性的。1 9 8 7 年，b y r d ，n o c e d a l 与y u a n i “i 将 p o w e l l 的结果推广，证明了b r o y d e n 族中的所有算法( d f p 算法除外) ，在目标函数为凸 函数的条件下，采用w o l f e 线搜索原则，这些算法具有全局收敛性；在目标函数为一致 凸函数且h a s s i a n 矩阵为h s l d e r 连续的假设条件下，这些算法有局部超线性收敛性【1 5 1 。 y u a n y 1 6 , 1 1 7 1 ，b y r d r f l 8 1 提出了一类非拟牛顿法，以新的思路和方法解决一般目标 函数的极小化问题。2 0 0 1 年，l i ，f u k u s h i m a ”i 提出一种新的b f g s 校正公式，证明了假 设目标函数具有l i p s c h i t z 连续梯度条件，且当采用w o l f e 原则或a r m i j o 原则，该b f g s 算法是全局收敛的。文献 1 5 提出的广义校正公式，采用非精确线搜索来研究一般非 凸目标函数极小化问题，得到了其全局收敛性，推进了 1 9 - 2 1 的结果。 本文研究目标函数的极小化问题的拟牛顿算法及其收敛性。提出一类新的d f p 拟 牛顿算法，证明了新的校正公式对保持目标函数h c s s i a n 矩阵的逆的近似矩阵日。的正定 性有很好的效果，并证明了若目标函数二阶连续可微且满足存在m ，m o ，对任意 x o 。) ，m z2 z t g ( x ) z m0 z nvze r “时，精确线搜索下该算法是全局收敛 的。最后对无约束优化问题还提出一类改进的b f g s 算法。此算法具有矩阵的正定传递 性，并证明了对一般非凸目标函数极小化问题，采用g o l d s t e i n 线搜索，若目标函数二 阶连续可微有下界，且水平集有界，那么此算法收敛。此结果推进了文献【1 5 】的结果。 数值试验表明了算法的有效性。 2 第一章概论 一、问题的提出 为建立优化问题模型，我们下面给出一个具体例子 例1 ( 曲线拟合问题) 设有某三个物理量工。，z ：，x 。，根据某一物理定律知道它们满 足下列函数关系 r ( t ) = 五+ 工2 e 。印 用实验测得t t ；时的r 的值为r ，i 一1 ，2 ，朋现在要确定参数z 。，工：，x ，这里，参数满 足x l + z 2 1 , x 3 芑0 。 对上述问题，我们可以用最小二乘原理来解决，即选择z ，z ：，x ，的组值，使偏差 的平方和最小。建立如下的非线性问题模型： 幽厂o ) 2 群r 一瓴+ 掣。西) 】2 ， s t 。而+ 屯一1 ， x 3 0 这里s t 是s u b j e c tt o 的缩写。 例2 投资决策问题。某一公司有资金a 元，可供投资的项目有万个，至少投资一个 项目。已知第f 个项目需投资a i 元，预计效益为么元，试选择最佳投资方案。 解：设投资决策量为 金额必须满足 又已知毛g = l 2 ，厅) 只取1 或0 。所以置还应满足 玉( 1 - x h = o , i = 1 , 2 ，n 最佳投资方案应为投资额最小，而总效益最大。因此该问题的数学模型为 m 吣= 弘弘， s t ：j o 善口；工ts 么，( f 。1 ，2 ，以) k ( 1 - - x ；) = 0 ， 例3 运输问题。设某物资有所个产地4 ，么：，a ，产量分别为a l , q ：，口。，有万个 销地且，b ：，色，销量分别为轨，6 ：，吮，c 表示将货物从4 运到丑的单位货物运费， 试求最佳运输方案。 解：设勤为确定由4 到曰j 的运输量。要求最佳运输方案即求使其满足运输要求且 总的运输费用最小。 为便于形成数学问题，列出矩阵如下： 五1 ，2 ，h 屯1 ，石2 2 ，, x t n 1 ，2 ， 于是得到问题的数学形式为。 m i n 勺嘞， s t 善嘞屯( i - - 纷：，小) ， ， 嘞。6 ( j 2 1 ，2 ，1 ) ， 嘞o ( i 一1 2 ，m ；j = 1 ，2 ，厅) 如果考虑产销平衡的情形，那么要求满足 卅 2 6 广 l - l j - i 4 它说明约束条件中第一和第二组是相容的，运输问题一个特殊的线性规划问题。 对于最大化的问题，只要在目标函数前加个负号，就转化成最小化问题。 基于此，我们给出最优化问题的数学模型 r a i n ( x ) s t 工q ( 1 1 ) 其中，函数，：r “_ 尺称为目标函数。q 尺”称为可行域。它是在对目标函数求极值过 程中对所涉及变量的取值范围的界定。也就是说，可行域是由满足某种条件的点组成的 集合。它有多种表述形式，一般用等式和不等式来定义，如 q ；仁r “b ) ；0 , i e ；c f o ) 苫o ，i e i 对i e e ，c 。 ) = 0 称为等式约束，称为等式约束指标集；g i j i e i ，c 。0 ) 之0 称为不等式约 束，i 称为不等式约束指标集。 二、最优化问题的分类 最优化问题形形色色，具体的数学模型多种多样。从不同的角度出发，可以对最优 化问题进行分类。一般地，主要是按其中的约束条件、目标函数以及变量的确定性进行 分类的。 1 根据有无约束来划分若q = 尺4 ，即x 是自由变量，则称( 1 1 ) 为无约束问题；若 q 尺“，称( 1 1 ) 为约束最优化问题。这两类问题并不是严格对立的，它们之间可以进 行转化。 2 根据约束函数和目标函数的线性与否来划分若目标函数及约束函数都是线性 的，则称( 1 1 ) 为线性规划问题；若目标函数与约束函数中至少有一个函数是非线性的， 那么称( 1 1 ) 为非线性规划问题。 三、非线性规划的基本概念 对非线性规划( 1 1 ) ，我们给出解的定义。 1 称x 。q 为( i 1 ) 的可行解，若x q 。 2 称z 。q 为( 1 1 ) 的整体最优解( 整体最小值点) ，若对任意z q 有 f ( x ) s 厂0 ) ，其对应的目标函数值称为最优值( 最小值) ；称z 。q 为( 1 1 ) 的严格整 体最优解，若对任意x e f 2 ，x x 。有厂o ) 0 ，使得对 5 任意x e n ( x , 6 ) nq ，有f ( x ) s 厂o ) ：称x 。q 是( 1 1 ) 的严格局部最优解，若存在z 点的一个邻域 。，6 ) ，使得对任意石0 。，6 ) nq ，工x 。，有f ( x 。) 厂o ) 。 由于求目标函数的最大值可以通过给目标函数前面加负号而转化为求目标函数的 最小值，因此，除非特别说明，最优化问题的( 整体或局部) 最优解就是指其( 整体或局部) 最 小值解。 四、算法的衡量标准 。 对于一般的非线性规划问题，一个求解方法要被认可，既要经过理论上的证明，又 要有满意的数值效果；既要要求计算精度相对较高，又希望收敛速度快。具体地，一个 好的求解算法应在如下几个指标上具有好的特性。 1 全局收敛与局部收敛对于算法许可范围内的一类问题，选择合理的初始点后， 一个好的算法应能在计算法运行时许可的范围内得到满足一定精度要求的问题最优解 或理论上保证产生的序列收敛到一满足某最优性条件的点，称该算法具有全局收敛性。 若算法只有在初始点和最优点具有某种程度的接近时才能保证算法产生的迭代点列的 收敛性，则称该算法具有局部收敛性。 在算法分析中，我们还经常碰到如下的收敛定义，即存在算法产生的迭代点列的一 个聚点，其满足某最优性条件，我们也称这种算法具有收敛性。 2 收敛速度与二次终止性一个算法具有收敛性还不够，还必须有好的收敛速度。 设点列缸) 收敛到x ，且存在q o 满足 i 罂p 锱郇 若0 q 占：肛g ( t | l 那么转步8 ，否则 步5 ：沿方向a ( 作线搜索，求口t = a r g m i nf ( x t + at ) ，令工m = x + 吒a 步6 ：若i l g “1 0 s ，则停止计算z z “n 否则k ：2 k + 1 ，返回步1 步7 ：令a ( ) = 一g n ，转步5 步8 ：令a ( ) - - - a ( ，转步5 在这个算法中，当牛顿方向不是下降方向时，则用风取一g 。或i 来代替g 。，使之 产生的a ( 始终为下降方向 三、此修正算法全局收敛性 引理it l l ：设目标函数，二阶连续可微且在r 4 上有下界，精确下降算法产生的迭代 w - 列k ( i ) ，若存在常数m 0 ，使得对任意k 及l 恢0 m ， 则 驴。i | 2 c o s 2 一州 0 ，由假设条件，存在f ( z 七1 ，z + 口ia ) ，使得 厂+ 甜) ) | + 槲厂+ 三口2 g w ” s + 锨7 9 + j 1 口2 m ”1 1 2 甜知旷卜崭卜1m ”j 1 2 蹴当口一崭时，不等式右边唰粤拥步嬲燃u 得到 ”，1 1 2c o s 2 ，一g ) s2 m ( a 一 + ，) 不等式两边对k 求级数，利用数列单调不增有下界，得 扣卜2 一州 定理1 ：如果，o ) 二阶连续可微有下界，此修正阻尼牛顿算法满足 i g 。咛有界且b ? 的条件数有界时，那么! 鲤g 卜0 证明：由引理1 ，、 渺卜2 一州 啦 b 。的条件数记作c d 以d ( 风) ，c o 蒯( b ) = b b , i ii i b ；1 1 1 - o ，d o ，c o ) ，那么 o o s a r k ) , _ g t k ) ) = c o s ( b f l g k ) , g t k ) ) = 篇错一嘲1 帑1 从而l i m g t ) = 0 四、数值实验 本节提供几个数值例子，以验证修正算法的有效性 算例1r o s e n b r o c k 函数： f ( x ) = 1 0 0 ( x z 一# ) 2 + ( 1 一五) 2 这个极小化问题的最优解是工+ 一q 矿，f ( x ) ；0 在实验中，终止准则值为 i f ( x ) 1 0 9 1 对不同的初始点，数值结果如下： 初始点迭代次数 f ( x ) 的值绝对误差( i l z ( ) 一x i i ) ( 0 ，0 ) 2 55 9 8 1 4 e 一0 1 05 4 6 8 7 e - 0 0 5 ( 0 ，1 ) 1 66 9 7 1 3 e 一0 1 01 6 0 7 4 e - 0 0 5 ( 1 ，0 ) 21 9 7 2 2 e 一0 2 9 4 4 4 0 9 e - 0 1 6 ( 一1 2 ，1 ) 3 69 9 6 3 l e - o l o4 0 9 3 6 e - 0 0 5 ( 1 2 ，1 ) 3 89 9 6 5 8 e 一0 1 04 0 2 0 8 e - 0 0 5 ( 2 ，3 ) 1 7 6 7 6 0 7 e - 0 1 0 5 4 7 7l e - 0 0 5 ( 1 0 ，1 0 ) 5 22 9 6 1 7 e - 0 111 1 7 1 2 e - 0 0 5 表1 算例l 对不同初始点的数值结果 算例2 立方体函数： 、 f ( x ) - - 1 0 0 ( x 2 一# ) 2 + ( 1 一五) 2 这个极小化问题的最优解是z = g 1 ) r ，f ( x ) ；0 在实验中，在实验中，终止准则值 为l ， ) f 1 0 一对不同的初始点，数值结果如下： 初始点迭代次数 f ( x ) 的值 绝对误差( 1 l x ( ) 一z 1 1 ) ( 0 ，0 ) 2 51 3 3 8 2 e - 0 1 11 1 0 7 6 e - 0 0 5 ( 2 ，1 ) 4 44 6 2 9 0 e - 0 1 05 2 5 4 6 e - 0 0 5 ( 1 2 ，1 2 ) 1 6 1 6 2 3 9 e - 0 1 02 9 0 6 1 e - 0 0 5 ( 1 2 ，1 ) 2 78 9 0 7 3 e - 0 1 09 2 4 6 6 e 一0 0 6 ( 一1 2 ，- 1 ) 3 4 2 8 9 9 8 e - 01 05 3 8 5 0 e - 0 0 5 ( 3 ，一3 ) 5 31 7 4 9 1 e - 0 1 03 0 5 8 6 e - 0 0 5 ( 一6 ，6 ) 9 85 8 4 7 9 e - 0 1 07 6 2 6 7 e - 0 0 5 表2 算例2 对不同初始点的数值结果 算例3p o w e l l 奇异函数： f ( x ) = “+ 1 0 x 2 ) 2 + 5 化一) 2 + 如一弛) 4 + 1 0 “一x 4 ) 4 这个极小化问题的最优解是x 一( 0 ，o , o ，0 ) r ，f ( x ) 一0 在实验中，终止准则值为 f ( x ) l 0 ，ns g n ( 宇( ) t ，7 ( ) 扩纠1 2 s g l l ( 宇) 7 r ( ) 亭) 1 ，7 ( ) 一1 ，s 印( 亭) t ，7 ( ) 亭) 7 ，7 ( ：亭忙) r ( k ) 0 ， 1 0 若口t 与钆线性无关，由c a u c h y s c h w a r z 不等式得到， 忙。阢0 2 ( 瓯，瓯) 2 ，所以肛。 若a 。与以线性相关，即存在 同样得到 2 咚# o 因而 ：v 纠l | u 2 。 ) ，t h i + 1 y 0 0 ie r l ，使得口t 一场t ，贝u 亭) 7 y = 亭) 1 ( 1 7 7 ) 一1 u ：y = z 宇厂( u ? ) 1 u 丁，7 ( ) = z 亭矿，7 ( o ， ) ，t h t + l y 0 假设亭) 7 ，7 ( ) 0 ，有 t 纠1 2 s g n ( 亭) 7 r ( ) 耋) t ，7 ( ) 假设1 0 ，同上讨论得到 1 ) ，：r “_ r 二阶连续可微 y t h “l y 0 2 ) 目标函数f ( x ) 满足，存在m ，m o ，对任意x l ( x o ) m z2 z t a ( x ) z ml j z | | 2 ，vz er “ 引理l ：设，：r 4 一r 满足假设1 ，则精确线搜索方法产生的迭代歹l j x ) 对应的 下述数列 一似 一叩 一厂 胪i 一争”一0掣一矿 y 一，0一仲 一，手一咿 + 都是有界的 亭) 7 r l ( ) 渺，0 2 7 叼( ”0 2 垆0 2 1 叼( 缈，1 1 2 7 ，7 ( 定理2 ：设f ( x ) 满足假设l ，则精确线搜索步长规则下的d f p 方法产生的点列缸 收敛到极小点工。 证明：先给出关于日。的d f p 校正公式， 。 亭亭。) 1 h k r r 1h h k + l = h k + ；吾巧西一了蒂 当亭) t ，7 ( ) 0 时，d f p 校正公式 z r 宇) i h i r 1 日h k + l 划一齐一带 圾+ - 2 i r ( - - f ， i ，7 ( ) t 7 ，7 ( + 筹亭) 。，7 ( ) 当孝) ，7 ( ) 0 ，仍有( 3 1 ) 和( 3 2 ) 成立 显然仇+ ，h m = ，对+ 。的表达式两边求迹， t r 0 气+ 。) = t r ( 风) 一+ 躞 由工“1 ；x + a 女小，小= 一日t g 卵( ) t r ( ) 亭) t 叩( ) ( 3 1 ) ( 3 2 ) ( 3 3 ) b t 宇七= b ig “一x 。) 一口t b t 小= 一a k g 忙， g ( “1 ) t 亭) = g ( “1 ) t “1 ) 一z ( 七)= a k g ( “1 ) t a ( ) = 一a k a t + 1 ) t 反+ 1 硝) ；0 ，以及 叼) = g “n g ，( 3 3 ) 右端的中间两项可以写成 ， 宇1b k r 一2 三= 一 亭) ，7 ， 吨( 带+ 吨( 努+ ( g ( + 1 ) t 亭) 一g ( ) t 亭) ( ，7 ( 七) 7 叩( ) ( 事) ，7 ( ) 2 ( ，7 ( 七) t 亭) ( ，7 仕) 7 ，7 ( ) ( 亭) ，7 ( ) 2 两 p一陟 ” 一” 争一矿 矿丽 争广纺 一，叩一似 仇一 ，一仲 一亭 2 、，一 一 叩一 ”一广 仞一 0 一叩 仲一，宇一仲 反皓 t 一 一 芋一 i 一 + ， 因为 吨一 吨掣善瓮鬻 ( g ( 七+ 1 ) t + g ( ) t ) ( g ( “n g ( ) g ( ) 7 以g ( 。) g ( + 1 ) g ( “1 1 一g ( ) t g ( ) + g ( ) t g ( + n g ( + 1 ) t g ( ) 渺哪妒0 2 g ( ) t 巩g ( ) g ( ) 7 以g ( ) ；( 七+ 1 ) t j f 七+ t t ，( 七+ 1 ) = ，( 七+ 1 ) t ( f ，七 日t ，7 ( ) ，7 ( ) t h h 。 矿巾 叫妒c 即甓努 l 妒+ 1 h 女r ( ) 叩( 7 日t r ( ：，7仲)th。叩tt，一翌!三二璺二至三；翌掣。o r 2 巩r ( ) 协簪挚 ( 3 4 ) ( 3 5 ) p “勺 慨6 ， z g忙)t日。叩仲)一墨!竺二墨号手铲一。 ，( i ) 7c - 7 。一嚣，g ( i =刁作)t。g)一!：二专篡铲=。 由( 3 6 ) 一( 3 9 ) 得 ( 3 7 ) ( 3 8 ) ( 3 9 ) 广 ” g ( t ) 7 f ，t + - 舌：i + 1 ) 2s r j ( 上，t g ( 川h t l h i r ( ，h 7 h t r ( p g(tj7-了。g(i)一!：i!：!；铲 叫矿蹦协筹 划矿蹦坐铲 g ( r h t g ( ( g ( “矿h i g ( “1 ) ( g + 1 一g ) t h t ( g + 1 一g ) ( g ( ) t 日t g ( ) ( g ( m ) t 日t g ( + d ) g ( ) 7 h i g ( ) + g ( + 1 ) 7h t g ( 2 + 1 ) 其中( 3 4 ) ，( 3 1 0 ) ，( 3 1 1 ) 对( 3 1 1 ) 求倒数得 1 禾0 用了g ( “1 ) t 日女g ( ) = 0 g ( 2 ) h t g ( ) 1 g ( + 1 ) 7 h t g ( + 1 ) 把( 3 5 ) ，(