（计算数学专业论文）二阶非单调线搜索方法及其收敛性分析.pdf

摘要 摘要 本文通过使用h e s s e 矩阵的负曲率信息和强制函数的概念，提 出了二阶非单调w o l f e 线搜索方法和二阶非单调线搜索方法的一 般形式，即所定义的二阶非单调f 准则证明了w o l f e 线搜索准则 所产生的迭代序列收敛于稳定点，该稳定点满足二阶最优性条 件，并得出了二阶非单调a r m i j o 准则，g o l d s t e i n 准则，w o l f e 准则都 是f 一准则的特殊情况最后通过数值试验说明了本文所提出的新 方法的可行性和有效性 关键词：非单调，二阶线线索，下降对，w o l f e 准则，f 一准则，强制函 数，无约束优化 a b s t r a c t a b s t r a c t i nt h i sp a p e r , b yu s i n gt h en e g a t i v ec u r v a t u r ei n f o r m a t i o nf r o m t h eh e s s i a na n dt h ec o n c e p t i o no ff l e x i b l ef o r c i n gf u n c t i o n ，w ep r e s e n ta n e w a l g o r i t h mc a l l e dt h en o n m o n o t o n e s e c o n do r d e rw b l f e sl i n es e a r c h m e t h o da n dt h eg e n e r a lf o r mo fn o n m o n o t o n es e c o n do r d e rl i n es e a r c h m e t h o d s ，w h i c hw ec a l lt h en o n m o n o t o n es e c o n do r d e rf r u l e w ep r o v e t h a tt h es e q u e n c eg e n e r a t e dc o n v e r g e st ot h es t a t i o n a r yp o i n t st h a ts a t - i s f yt h es e c o n do r d e ro p t i m a l i t yc o n d i t i o n s w 色a l s op r o v et h a tt h ep o p - u l a r1 i n es e a r c hm e t h o d s w h i c hi n c l u d et h en o n m o n o t o n es e c o n do r d e r a r m i j or u l e ，t h en o n m o n o t o n es e c o n do r d e rg o l d s t e i nr u l ea n d t h en o n m o n o t o n es e c o n do r d e rw 6 1 f er u l ea r ea l lt h es p e c i a lc a s e so ft h ef - r u l e i na d d i t i o n ，t h en u m e r i c a lr e s u l t ss h o wt h a tt h ea b o v et w on e wm e t h o d s a r ee f f e c t i v ea n dr o b u s ti np r a c t i c a lc o m p u t a t i o n k e y w o r d s ：n o n m o n o t o n e ；s e c o n do r d e rl i n es e a r c h ；d e s c e n tp a i r s ； w o l f e sl i n es e a r c h ；f r u l e ；f o r c i n gf u n c t i o n ；u n c o n s t r a i n e do p t i m i z a - t i o n 一v 一 本文创新点 本文主要研究的是求解无约束优化问题的二阶非单调线搜索 方法主要有两个创新之处： 首先，本文在s u na n dz h o u 【s c i e n c ei nc h i n as e r i e sa ：m a t h e m a t - i c s ，5 0 ( 1 0 ) ，p p 1 3 8 9 1 4 0 0 ( 2 0 0 7 ) 提出的方法的基础上，提出了二阶 非单调w o l f e 线搜索方法，这种新的线搜索准则可以避免a r m i j o 准 则步长太小，也可以防止出现g o l d s t e i n 准则排除掉最优解的情形， 从而使算法更加有效和实用我们通过两组数值试验，分别说明二 阶非单调w o l f e 线搜索方法l l - - 阶单调w o l f e 线搜索方法和二阶非 单调g o l d s t e i n 线搜索方法更加有效 其次，本文在s u na n dh a n j o u r n a lo fc o m p u t a t i o n a la n da p p l i e d m a t h e m a t i c s1 4 6 ，p p 8 9 9 8 ( 2 0 0 2 ) 1 提出的一阶非单调f 一准则的基 础上，通过引入负曲率方向，建立了二阶非单调f 一准则的一般 形式，并且证明了常用的二阶非单调a r m i j o 准则、g o l d s t e i n 准 则、w o l f e 准则都是其特殊形式这一重要的性质最后，分别用二 阶单调和非单调线搜索方法进行了数值试验，结果表明二阶非单 调线搜索方法的效率更高一些 第l 章引言 第1 章引言 本文考虑求解下面的无约束优化问题 m i ni ( z ) z r n 。7 ( 1 0 1 ) 并且假设f ：r n _ r 是一个二次连续可微的函数，它的梯度g 矛1 h e s s e 矩阵h 存 在且连续，并记作g ( x ) = v f ( x ) ，h ( x ) = v 2 厂( z ) 为了方便，我们将把f ( x k ) ， g ( x k ) ，和h ( x k ) 分别记作 ，鲰和风此外，符号i l 代表兄”空间上的欧几里 德范数，符号m i n ( ) 代表矩阵的最小特征值 我们可以通过信赖域方法和线搜索方法求解问题( 1 0 1 ) 上面的两类方法 都可以得到算法的全局收敛性( 见【1 5 】) 现在，我们着重分析线搜索方法假设 当( 1 0 1 ) 的近似解为z k ，通常取以下形式 x k + l = x k + a k d k ， k = 1 ，2 ( 1 0 2 ) 其中d 七是下降方向，o 知是沿着方向如的步长，则下一步的近似迭代点z 七+ 1 就 采用( 1 0 2 ) 的形式这一类方法在求解大规模无约束优化问题时是非常有效 的( 见【1 5 ，3 2 ，3 4 1 ) 算法的关键是收敛到稳定点z + ，此时h e s s e 阵h ( x 4 ) 是一个 半正定矩阵然而，当初始点远离局部极小点时，h e s s e 矩阵或它的近似不是半 正定，这类方法就失效了幸运的是，在参考文献【8 ，1 8 ，1 9 】中，通过使用负曲 率方向( 即方向d 满足d t h ( x ) d 0( 1 0 3 ) 其中( s 惫，毗) 是下降对，s 如是下降方向( 即s 蚕9 o ) ，以保证更快地达到全局收 敛，如是负曲率方向( 即g k 0 ，d 善k h k d k 0 ( 1 0 4 ) 本文所讨论的内容均是采用( 1 0 4 ) 的迭代格式产生迭代序列的 传统的二阶线搜索方法要求目标函数值单调下降，以保证全局收敛性然 而，文献 1 1 ，2 6 ，3 4 】表明单调线搜索技术有许多缺点例如，强制单调可能会 放慢收敛速度，特别当迭代到很窄的弯谷时因而，我们允许目标函数值在迭 代过程中带有非单调性g r i p p oe ta 1 【9 】首次提出了牛顿法的非单调线搜索方 法由于非单调方法的高效性，这项技术已被广泛应用到线搜索方法【1 5 ，3 l 】 和信赖域方法 4 ，6 ，2 8 】中最近，非单调方法又与曲率搜索和二阶线搜索方法 相结合【5 ，3 5 】数值结果说明了这种方法解决无约束优化问题的有效性 常用的线搜索方法有a r m i j o 准则，g o l d s t e i n 准则和w o l f e 准则g o l d s t e i n 准 则和a r m i j o 准则的不同之处在于，它允许步长偶尔增加，而且g o l d s t e i n 准则能 够保证目标函数充分下降，同时防止步长太小但是，g o l d s t e i n 准则也有缺点， 它可能会将问题的最优解排除掉，这一问题已在文献【3 0 】中指出因此，我们 这篇文章的目的就是利用非单调二阶w o l f e 准则来克服上述缺点 文献【3 4 】中提到的强制函数是一族非常重要的函数，常常用来证明充分 下降和收敛性文献 1 7 】中提出的一阶非单调f 准则来解无约束优化问题， 这一方法将强制函数和非单调线搜索方法结合产生的一般的搜索准则( f 准 则) 本文中我们也将上述两种技术结合，又加入了负曲率方向，产生二阶非单 调f - 准则，并证明了常用的二阶非单调a r m i j o 准则、g o l d s t e i n 准则、w b l f e 准则 都是其特殊形式这一重要的性质 这篇文章的其余部分安排如下：第二章分析解无约束优化问题的二阶非 单调w o l f e 线搜索方法，得出非单调二阶w o l f e 线搜索算法，建立收敛性分析，给 出数值结果；第三章分析解无约束优化问题的二阶非单调线搜索方法的一般 形式，i 司样给出了收敛性分析和数值结果，说明该方法的可行性和有效性；第 四章总结与展望 一2 一 第2 章解无约束优化问题的阶：m 单调w o l f e 线搜索方法 第2 章解无约束优化问题的二阶非单调w o l f e 线 搜索方法 2 1 引言 这一章，我们主要分析解无约束优化问题的二阶非单调w o l f e 线搜索方法， 本章内容安排如下：2 2 节给出一些准备工作，给出最优解存在性引理的证明； 2 3 节给出解无约束优化问题的二阶非单调w o l f e 线搜索方法的算法；2 4 节进 行收敛性分析：2 5 节将本文的新算法的数值结果与二阶w o l f e 线搜索方法进行 比较，通过数值试验说明该方法的可行性和有效性：2 6 节给出本章的总结 2 2 准备工作 假设f ：r 几一r 是一个二次连续可微的函数，它的梯度9 $ l i h e s s e 矩阵日存 在且连续，并记作a ( x ) = v f ( x ) ，h ( x ) = v 2 t 厂( z ) 为了方便，我们将把，( z 七) ， 9 ( x k ) ，幂1 h ( x k ) 分别记作厶，9 k 和风此外，符号”i i 代表舻空间上的欧几里 德范数，符号入m i 札( ) 代表矩阵的最小特征值 定义2 21 ( 1 ) 若h e s s e 矩阵h ( z ) 至少有一个负特征值，则z 称为不定点 ( 2 ) 如果z 是一个不定点，若方向d 满足d r h ( z ) d 0 ，则称d 为日( z ) 在z 处的 负曲率方向 定义2 2 2 如果s t g ( x ) 0 ，d r g ( z ) 0 ，d t h ( x ) d 0 ，则向量对( s ，d ) 称为 不定点z 处的下降对；若z 不是一个不定点，则满足s t 夕( z ) 0 ，d t g ( x ) 0 ， , t r h ( z ) a = o 的向量对( s ，d ) 称为在点z 处的下降对， 定义2 2 3 令( 1 l s k l l 和 l l a k l l 是有界数列，若 纸t 8 缸= 0 意味着g k = 0 且8 k = 0 ， 9 t s 七一0 意味着g a on8 k 一0 ， 第2 章解无约束优化问题的_ 阶怍单i 目w o l f e 线搜索方法 d t k kh ( x ) d k 一0 意味着a 七_ 0 且呶_ 0 ， 其中入j c = m i n i 0 ，入m 伽( 巩) 】，另g z , ( s k ，d k ) y 口 - i 接受下降对 首先，我们描述w o l f e 线搜索准则当步长o t 七满足下面的条件， f ( x k + a k d u ) f ( x k ) + p o e k g t d k ， 玉1 d k 8 9 t d k ( 2 2 1 ) ( 2 2 2 ) 其中p ，6 ( 0 p 6 1 ) 是给定的常数，则令x k + 1 - x k + o t k d k 下面，我们将回顾 非单调w o l f e 线搜索准则令 m 2 。器七) m 七一j ) m 是非负整数且m ( k ) 满足m ( o ) = 0 $ n o m ( k ) m i n m ( k 一1 ) + 1 ，m ) ( 七 1 ) 对应于( 2 2 1 ) ( 2 2 2 ) 式，非单调w o l f e 准则描述如下( 见 2 6 】) ： y ( x k + a k d k ) _ 。g m 鲫a x z 南圳+ p q 七露毗， g ( x k + a k d k ) t d k i s g d k ， 其中0 p 6 1 当乳是不定点时，我们可以提出二阶w o l f e 准则令 x k ( o e k ) = x k + a 2 s 七十a k d k ， 其中( s 詹，d k ) 是x k 处的下降对要求o l k 满足： f ( x k ( a 凫) ) m 七) + p q 獬鲰+ 三耀风d 七 ， ( 2 2 3 ) 9 ( z 惫( q 惫) ) t z ：( q 惫) 6 f 夕蚕d 彪+ 2 a k g t s k + a k d r h k d k ，( 2 2 4 ) 其中0 p 6 1 对应于二阶准则，我t l , - - i 以提出二阶非单调准则： m 女( q ) ) m + p 口2 s + 弘1t 风吼 ( 2 2 5 ) 一4 一 第2 章解无约束优化题的_ 阶怍单凋w o l f e 线搜索方法 夕( z 七( a 七) ) r z ：( 岛) 6 b 丢d 七+ 2 a k ：鳍s 知+ q 知蛭h k d 七】 ( 2 2 6 ) 那么，我们只需要使口后满足( 2 2 5 ) 一( 2 2 6 ) ，然后令z 忌( 0 1 知) = z k + a 2 s + a k d k 当m = o 时，( 2 2 5 ) ( 2 2 6 ) 简化为( 2 2 3 ) 一( 2 2 4 ) 二阶非单调w o l f e 线搜索方法的几何解释女n f i g u r e1 所示 f i g u r e r1 g e o m e t r i c a li n t e r p r e t a t i o no f ( 2 2 3 ) 一( 2 2 4 ) a n d ( 2 2 5 ) 一( 2 2 6 ) 在f i g u r el 中，d a t a l 代表f ( x k + 0 1 2 8 k t - q 毗) ，d a t a 2 代表f ( x k ) - t - p a 2 g t s k - t - h k d k ，d a t a 3 代表c + 6 口鲧也+ 0 1 2 ( 鲰t 乳+ g k d k ) ，d a t a 4 代表，( 戤( 。) ) - t - p q 2 g s k - t - ；h k d k 我们观察到不等式( 2 2 3 ) 和( 2 2 5 ) 给出了函数的充分下 降不等式( 2 2 4 ) 或( 2 2 6 ) 排除了极小值，此外，使n ( 2 2 5 ) 和( 2 2 6 ) ，可接受 区间【n ，c 】比区间【o ，6 】大，它们都满足( 2 2 3 ) ( 2 2 4 ) 令 机( q ) = f ( x 七十a 2 8 七十a d k ) ， ( 2 2 7 ) 一5 一 第2 章解无约束优化 q 题的阶非单调w o l f e 线搜索方法 其中( s 七，d k ) 是z 忌处的下降对，那么吼( o ) = g t d k ，( o ) = 2 9 r s k + d 蚕k h k d k 非 单调二阶w o l f e 线搜索准则( 2 2 5 ) ( 2 2 6 ) 等价于 和 妒忌( a 知) f ( 七) ( o ) + 三p 乜k 2 妒忌i i ( o ) ：( q 南) 6 【咖：( o ) + q 知咖：( o ) ( 2 2 8 ) ( 2 2 9 ) 从定义2 2 2 ，可得嗾( o ) 0 或嗾( o ) 0 且( o ) 0 下面的引理证明了在 条件( 2 2 1 0 ) ( 2 2 11 ) 下满足( 2 2 5 ) ( 2 2 6 ) 的q 七存在， 且 s 七t g 詹 0 ，g k 0 ， 耀h d k 0 ，g k = 0 一旦找不到下降对( s k ，d k ) ，则迭代终止 ( 2 2 1 0 ) ( 2 2 11 ) 引理2 2 4 令机：r _ r 是一个二次连续可微函数，且l = q 【o ，+ o o ) ：机( q ) s c k ( o ) ) 是紧集若嗽( o ) 0 ，或瓯( o ) 0 且( o ) 0 ，那么存在一个满足下列 条件的步长区间 咖岛( q 七) 咖j ( 南) ( 0 ) + 互1p a 七2 9 i 七p l j u ) ， ：( q 南) j 【：( o ) + q 七咖；：( o ) 】 ( 2 2 1 2 ) ( 2 2 1 3 ) 证明：令卢= s u p o r 【0 ，+ o o ) ：机( 口) 机( o ) ) ，因为要么嗾( o ) o 又因为 1 的连续性，从而存在p l ( 0 ，纠，使得 且 另一方面， 即 且 1 ( 卢1 ) = 0 ，九j ( p 1 ) 0 h l ( a ) 0 ，v a ( 0 ，卢1 ) 2 ( o ) = 咖：( o ) 一6 ：( o ) = ( 1 6 ) ：( o ) 0 九：( q ) = ：( a ) 一6 妒：( o ) ， 即 ：( o ) = ；：( o ) 一6 ：( o ) = ( 1 6 ) 咖；：( o ) 0 ，使得 h 2 ( a ) 0 ，v a ( 倪，卢1 ) ( 2 2 1 4 ) ( 2 2 1 5 ) 因为机( o ) 咖( 七) ( o ) ，通过不等式( 2 2 1 4 ) 和( 2 2 1 5 ) ，可得九3 ( a ) 愚1 ( 乜) 一7 一 第2 章解无约束优化n u 题的阶非单调w o l f e 线搜索方法 0 ，( 2 2 1 2 ) 和( 2 2 1 3 ) 成立，当口( 侥，卢1 ) 时 口 2 3 解无约束优化问题的二阶非单调w o l f e 线搜索方法的算法 算法2 3 1 d a t a ：x o ，整数m 0 ，0 p 5 0 s 1 令k = o ，m ( o ) = 0 ，计算，( z o ) s 2 计算g k ，凰若终止条件满足，则停止迭代 s 3 计算下降对( s 知，d k ) 和- 厂( 。f ( 知) ) s 4 计算步长o l k o l m n z ，使得下列条件成立： ，( z 忌( q 砖) ) f ( x z ( 惫) ) + j d q 2 s 吾夕惫+ 三d t h k d 惫】， 9 ( z 七( a 七) ) t z ：( q 七) 6 【9 吾d = + 2 q k g t ks k + o e k d t 巩d 屉】 s 5 令z 七+ 1 = z 七+ q 2 s 七+ q 七毗，同时计算f ( x k + 1 ) ，然后令m ( k + 1 ) = m i n m ( k ) + 1 ，m ) ，七：= 尼+ 1 ，转s 2 口 2 4 收敛性分析 假设2 4 1 ( 1 ) 水平集g t = x l f ( x ) f ( x o ) ，x o r n 是紧集j t f ( x ) ：r n r 是 q 上的二次连续可微函数 ( 2 ) 序列 ( s 七，也) ) 在算法2 3 1 中是可接受的 引理2 4 2 若假设2 4 1 成立且 z 恳) 由算法2 3 1 产生，那么序列( z 庇 i 仍在q 中， 且 ，( 舰( 纠) - 是非增收敛序列： 证明：证明类似于【3 0 】中的l e m m a3 2 口 一8 一 第2 章解无约束优化问题的_ 阶。怍单凋w o l f e 线搜索方浊 引理2 4 3 若假设2 4 1 成立，且算法2 3 1 产生了一个无限序列 z 七】，那么 ，l i mf ( x k ) = 3 i m 厂( z z ( 知) ) ， 七0 0 ，o o 1 i mq 则s 七| i = 0 ，1 i ma k l l d k t i = 0 ， c - - - , o 。k _ 0 0 且 1 i mi i x 七+ l z 七| i = 0 证明：证明类似于【3 0 中的l e m m a3 3 口 定理2 4 4 若假设2 4 1 成立，序列 z 七) 由算法2 3 1 产生，那么 证明：令 如前所述，得到 且 ( 2 4 1 ) ( 2 4 2 ) ( 2 4 3 ) ，l i m “8 k = 0 ，l i m 凰如= 0 ( 2 4 4 ) r o 。尤o 。 饥( a ) = f ( x k + 0 1 2 8 k + a d k ) 蜈( o ) = 鲧d k 0 咖七( o ) = 2 9 t ks k + 耀巩比 o ， ：。( o ) 昙e o ， 二 这与( o ) o ， 一伽) 耋e 0 ( 2 4 8 ) 从而( 2 4 8 ) 隐含了o t 不能收敛到零事实上，若o l k ；一o ，那z , o 愚；_ 0 ( k i c o ) ， 且西；：；( p ) 一；：。( o ) 一o ，则有一( 1 6 ) ( o ) 0 ，这与( 2 。4 9 ) 式矛盾另一方面， 若q 觑声0 ( k i _ ) ，r l i m k - o o g t s k 0 和l i m k o 。h k d k 0 ，可得( 2 4 6 ) 和 ( 2 4 7 ) 不收敛到零，从而产生矛盾最终定理得证 口 注释2 4 5 由定理2 4 4 ，可得要么存在某个k ，使得g k = 0 且a 七= 0 ，要么由算 法产生的序列使得鳜_ 0 且九一o ( k _ o o ) 引理2 4 6 设厂：r n r 是紧集q 上的连续可微函数若厂( z ) 在q 中有有限个 极限点，那么 z 惫 cq 满足 1 i m | | x k + 1 一z 七| l = 0 ，j i mi i 夕七i i = 0 ， ( 2 , 4 9 ) 托o o，o 。 筇2 章解无约束优化0 , - j 题的二阶非单凋w o l f e 线搜索方法 且 1 i r ax k = z 4 ，a n dg ( x + ) = 0 ( 2 4 1 0 ) 拧o o 证明：证明类似于【2 9 】中的定理3 5 1 3 口 定理2 4 7 若假设2 4 1 成立，且f ( x ) 在q 中有有限个迭代点，算法2 3 1 产生的 序列 z 七 是无限序列，那么 z 七 收敛到z + qk g ( z + ) = 0 ，入m 饥( 日( z + ) ) 0 因为这个证明类似于 3 0 1 中的t h e o r e m3 7 ，这里就将它省略了 2 5 数值结果 这一部分主要分析算法2 3 1 的数值结果，我们采用b u n c h p a r l e t t 分解产生 算法中的下降对，榆测函数取自文献 2 0 1 在表1 中，我们列出了所使用的检测 函数本文的试验结果是使用m a t l a b 语言编写的 表l ：检测函数 pf u n c t i o nn a m epf u n c t i o nn a m e lh e l i c a lv a l l e y 1 1 b i g g se x p 6 2b e a l e1 2 p e n a l t yi 3b r o w na n dd e n n i s1 3 p e n a l t yi i 4e x t e n d e dr o s e n b r o c k1 4c u b e 5e x t e n d e dp o w e l ls i n g u l a r1 5 t r i g o n o m e t r i c 6g u l fr e s a n dd e v1 6 v a r i a b l yd i m e n s i o n e d 7g a u s s i a n1 7肋t s o n 8b o x3 d i m e s i o n a l 1 8w o o d 9s c r o s e n b r o c k1 9s c c u b e 1 0b r o b a d s c 2 0 c h e b y q u a d 首先令参数p 1 - - - 0 1 ，6 = 0 2 ，o l m a x = 1 0 停机准则是i i l 1 0 一数值结果 列在表2 中在表2 中“n f - n g n i ”和“f v a l ”分别代表函数值迭代次数，梯 度运算次数，不定的h e s s e 矩阵风的出现次数和目标函数值，把问题的维数记 作n 初始点是i o l x o ，其中z o 是标准初始点符号代表n f 大于1 0 0 0 ，这种情 况下我们认为算法失败 在表2 中，比较了单调和非单调的数值结果在算法2 3 1 中比较了m = 0 ( 二 阶单调w o l f e 线搜索方法) $ i m = 6 ( 二阶非单调w o l f e 线搜索方法) 比较结果列 第2 章解无约束优化00 题的_ 阶。 | ：单渊w b l f e 线搜索方法 在表2 中在f i g u r e3 中，比较了使用( 2 2 8 ) 一( 2 2 9 ) 式的二阶非单调w o l f e 线搜索 方法和g o l d s t e i n 线搜索方法( 见 3 0 1 ) ，即 和 f ( x k ( 七) ) ，( z z ( 。) ) + j 9 1 q 2 s 吾9 知+ 互1u t 惫日知d 七 f ( x k ( q 七) ) m 七) + 肿獬鲰+ 三砌凫】， 其中p 1 = 0 1 ，p 2 = 1 一p 1 比较结果是在相同的函数和相同的初始点基础上进 行的 表2 ：二阶单调和非单调w o l f e 线搜索方法的比较 m = 0m = 6 pnln f n g n if v a ln f n g n if v a l 1302 7 1 4 31 9 3 4 9 e 0 2 33 6 2 3 78 4 4 9 l e 0 1 9 2201 5 一1 0 31 9 51 4 e 0 2 31 3 一1 0 32 1 5 8 0 e 一0 1 6 409 9 08 5 8 2 2 e + 0 0 49 9 o8 5 8 2 2 e + 0 0 4 3411 5 1 5 08 5 8 2 2 e + 0 0 41 5 1 5 o8 5 8 2 2 e + 0 0 4 422 4 2 2 08 58 2 2 e + 0 0 42 1 2 1 08 5 8 2 2 e + 0 0 4 1 002 6 1 8 02 1 6 7 7 e 0 1 31 8 1 4 07 6 7 8 2 e 0 2 0 41 0110 7 5 2 一o8 4 9 7 3 e 0l39 8 01 0 3 0 9 e 0 2 2 1 027 4 0 3 6 7 03 4 3 1 0 e 一0 1 79 8 08 0 8 5 8 e 一0 3 0 4o1 6 1 6 04 3 7 8 8 e 0 0 91 6 1 6 04 3 7 8 8 e 一0 0 9 5 4l2 2 2 2 02 6 0 l l e 0 0 92 2 2 2 o2 6 01l e 0 0 9 4 2 2 7 2 7 07 8 2 2 3 e 0 0 92 7 2 7 o7 8 2 2 3 e 0 0 9 6302 7 2 1 54 9 8 6 0 e 一0 2l2 4 1 9 59 0 2 5 2 e 0l5 302 2 o1 1 2 9 3 e 0 0 82 2 o1 1 2 9 3 e 0 0 8 7315 6 1 8 1 21 1 2 8 0 e 0 0 82 2 8 71 1 2 8 0 e 0 0 8 8301 3 1 1 29 9 2 7 9 e 0 111 3 1 1 29 9 2 7 9 e 01l 2018 3 9 7 01 8 6 7 4 e 0 1 64 3 3 1 01 9 0 4 4 e 0 2 3 9 ( c = 1 0 4 ) 21 7 4 2 3 5 8 04 9 7 4 5 e 0199 8 01 2 3 3 7 e 0 2 8 229 8 00 第2 章解无约束优化问题的阶仆单渊w o l f e 线搜索方法 m = 0m = 6 pnln f n g n if v a ln f n g n if v a l 20 4 3 3 1 01 9 0 5 6 e 0 2 3 9 ( c = 1 0 6 ) 2 l 9 8 01 2 3 2 6 e 一0 2 6 229 8 一o0 1 02l4 2 2 1 1 31 9 7 2 2 e 一0 314 2 2 1 1 31 9 7 2 2 e 0 3l 1 1 6o7 1 3 6 3 50 0 0 5 7 1 15 9 4 9 3 0 0 0 5 7 404 4 2 3 。02 2 6 0le 0 0 51 7 1 7 o2 2 5l3 e 一0 0 5 1 2416 l 一3 6 一o2 2 5 0 0 e 0 0 52 4 2 4 o2 2 5l8 e 0 0 5 1 008 1 2 9 o7 0 8 7 7 e 0 0 5 2 2 2 1 07 0 8 8 4 e 0 0 5 1 3 1 00 4 0 2 2 0 7 08 7 8 8 0 e 一0 0 61 9 1 9 08 81 4 7 e 一0 0 6 206 0 2 2 02 0 6 8 8 e 0 1 43 1 1 3 o1 8 1 8 8 e 0 2 7 1 4212 1 1 2 14 7 5 0 9 e 一015 2 001 6 9 21 9 7 9 l e 0 1 21 6 9 21 9 7 9 l e 0 1 2 6 007 1 2 0 1 01 4 8 9 3 e 0 0 74 8 2 71 4 8 9 3 e 0 0 7 1 58 009 4 2 1 1 47 3 7 61e - 0 0 73 6 1 6 51 4 6 9 6 e 一0 0 6 1 0 001 0 0 2 4 一1 31 8 41 0 e 0 0 64 8 2 0 一66 9 0 6 2 e 一0 0 7 1 61 0l1 7 1 7 01 6 81 9 e 一0 1 4 1 7 1 7 01 6 8 1 9 e 0 1 4 1 022 4 2 4 07 0 6 2 5 e 0 2 22 4 2 4 07 0 6 2 5 e 一0 2 2 1 71 201 3 1 3 04 7 2 2 4 e 一0101 3 1 3 04 7 2 2 4 e 0 1 0 4010 0 5 7 22 0 1 6 4 e 0 1 33 4 2 9 12 7 319 e 0 2 0 1 84l5 8 4 3 16 4 7 5 7 e 。0l94 3 3 6 25 0 8 6 8 e 一0 1 6 4 25 3 一1 4 一l 1 1 9 6 3 e 0 1 44 9 4 1 13 4 2 7 4 e 一0 16 1 9403 1 1 3 05 5 3 6 4 e 一0 21 ( c = 1 0 6 ) 4l3 5 1 9 一l2 0 4 4 4 e 011 2 0601 0 2 2 4 1 61 1 8 4 2 e 一0 1 46 4 1 7 93 4 5 2 7 e 一0 1 5 从表2 中可以看到，新方法是高效的和稳定的，特别是针对一些病态的问 题对大多数检测函数，它的“n f n g n i ”数比单调的情形是减少的，或者至 少是和二阶单调w o l f e 线搜索方法的结果一样的 在f i g u r e3f i g u r e4 ，z 轴分别对应于表l 中的检测函数l - 1 0 和11 - 2 0 可轴 是g o l d s t e i n 方法与w o l f e 方法的迭代次数比值，即 0 nf 七n g j rn i 、g r = 二一 ( f + n g + n 1 ) i v 第2 章解无约束优化问题的_ 阶非单调w o l f e 线搜索方法 f i g u r e3 如果g o l d s t e i n 方法失败了，我们将比值记作3 ，这是最大比值另一方面，如 果w o l f e 方法失败了，我们将比值记作0 可以看出所有的柱状都大过1 ，除 - j f i g u r e4 中的第4 个问题( 即表1 中的第1 4 个问题) ，说明了对大多数检测函数 使用二阶非单调w o l f e 线搜索方法比使用二阶非单调g o l d s t e i n 线搜索方法需要 更少的迭代次数就可以收敛例如，f i g u r e4 q b 的第1 0 个问题( 即表l 中的第2 0 个 问题) ，使用g o l d s t e i n 方法的迭代次数是使用w o l f e 方法的迭代次数的2 5 倍 2 6 总结 在这一章中，我们提出了解无约束优化问题的二阶非单调w o l f e 线搜索方 第2 章解无约束优化问题的阶怍单调w o l f e 线搜索方法 法，这一方法是将传统的单调w o l f e 线搜索方法拓展成二阶非单调形式，我们证 明了新方法产生的序列收敛n - 阶稳定点最后，我们给出了详细的数值试验 和数值结果的比较，说明了新方法的有效性 第3 章解无约束优化问题的二阶非单调线搜索方法的收敛性分析 第3 章解无约束优化问题的二阶非单调线搜索方 法的收敛性分析 3 1 引言 这一章，我们主要引入强制函数的概念，定义了f 准则以求解问题 ( 1 0 1 ) ，并证明了常用的二阶非单调线搜索方法都是f 准则的特例本章内 容安排如下：3 2 节给出一些准备工作和相关定义；3 3 节提出二阶非单调f 一准 则和相关引例：3 4 节建立二阶非单调线搜索方法解无约束优化问题的全局收 敛性；3 5 节通过数值试验说明该方法的可行性和有效性；3 6 节给出本章的总 结 3 2 准备工作 下面的假设贯穿于本章全部过程： 假设3 2 0 设函数，：舻一r 是二次连续可微函数，水平集 q = z i 厂( z ) s ，( z o ) ) 是紧集 在这一假设下，函数厂是下有界的且梯度9 ( x ) 在q 上是一致连续的 线搜索方法是解无约束优化问题的重要方法，线搜索方法的每步迭代通 常分为以下两步： ( 1 ) 选择一个下降方向呶； ( 2 ) 沿这个下降方向选择一个步长口七 一般地，d 七的选择要满足下降条件，即 纸t 如 0 ， 第3 章解无约束优化问题的_ 阶m 单调线搜索方法的收敛性分析 或者d j c 满足充分下降条件，即 菇d k 一r i o i i g 膏一 最后，可以选择适当的d k ，使其满足夹角性质，即 一蹁狐 其中r o 是一个正常数且伽 0 ，步长q 七满足： ，( z 七十q 七d k ) = ：m 【0 i n o tu ，8 】，( z 七+ q d ) t 1 1 下面的线搜索方法都是从当前迭代点2 7 屉出发沿着某个方向毗去选择步 长。彪，其中。七满足不同的不等式 ( c ) 不精确线搜索步长n 南满足： ( 1 ) a r m i j o 准则 y ( x k + o z k d 南) f ( x k ) + p a 忌g d k ， 其中o p 1 ( 2 ) g o l d s t e i n 准则 且 其中0 p 互1 ，( z 忌+ o 惫d 南) f ( z 七) + p a 9 吾d 知， ，( z + a k d 七) f ( x k ) + ( 1 一p ) a k g 吾d k ， 第3 章解无约束优化问题的阶非单凋线搜索方法的收敛性分析 ( 3 ) w o l f e 准则 且 其中0 p 口 1 ( 4 ) 强w o l f e 准则 且 其中0 p 盯 1 f ( x k + a k d k ) f ( x k ) + p o l k g t d k ， g ( x k + a k d k ) t d k a g t d k ， f ( x k + o t k d k ) sf ( x k ) + p o e k g f d k ， g ( x k + a k d k ) t d k i o r l g t d k l ， ( d ) 非单调线搜索方法 令m 是非负整数对任意的