（计算数学专业论文）解锥信赖域子问题的一类数值方法.pdf

南京航空航天大学硕士学位论文 摘要 信赖域方法是现代优化方法中一类重要的数值计算方法，其中基于锥模型 的信赖域方法是当今优化界研究的热点。在锥模型信赖域方法中，解锥模型信 赖域子问题是关键，因此本文主要研究锥模型信赖域子问题及求解方法。 本文共分五章。第一章主要简介了信赖域方法的基本思想、二次模型和锥 模型的研究状况。本文主要研究锥模型信赖域子问题的第二神情形。通过对第 二种情形进行细化和变换，把原锥信赖域子问题转化为凸规划问题。第二章把 原规划转化为一个对偶问题即无约束极大化问题，推广和证明了这个对偶问 题的一些性质和基本定理。第三章用广义牛顿法迭代求解由锥信赖域子问题转 化成的对偶问题，对迭代过程中产生的各种情况进行理论分析并提出解决方案， 从而给出了详细的算法。最后还在理论上讨论了锥信赖域子问题非凸的情形。 第四章证明了对偶算法的全局收敛性和局部收敛速率。最后一章给出了具体的 数值算例，证明了该算法的有效性。 关键词：锥模型、信赖域方法、锥模型信赖域子问题、对偶规划、广义牛顿法 解锥信赖域子问题的一类数值方法 a b s t r a c t t r u s tr e g i o nm e t h o disac l a s so f i m p o r t a n to p t i m i z a t i o nm e t h o d s t h i sp a p e rm a i n l yd i s c u s s e st h ec o n i ct r u s tr e g i o ns u b p r o b l e mw h i c hi s a k e yp r o b l e mi nc o n i ct r u s tr e g i o nm e t h o d t h e r ea r ef i v ec h a p t e r si nt h i sp a p e r t h ef i r s tc h a p t e ri n t r 。d u c e s t h et r u s tr e g i o nm e t h o d ，q u a d r a t i cm o d e la n dc o n i cm o d e l t h i sd a d e r m a i n l ys t u d i e st h es e c o n dc a s eo fac l a s so ft r u s t r e g i o ns u b p r o b l e m s i n v o l v i n gc o n i cm o d e _ a n dt h r o u g ht h et r a n s f o r m a t i o n ，t h ec o n i ct r u s t r e g i o ns u b p r o b l e mi sc o n v e r t e di n t ot h ep r o b l e mo f m i n i m i z i n g aq u a d r a t i c f u n c t i o nw i t ht w oc o n v e xc o n s t r a i n t s i nt h es e c o n d c h a p t e r ，t h i sp r o b l e m i s c o n v e r t e di n t oa d u a l p r o b l e m ，i e u n c o n s t r a i n e dm a x i m i z a t i o n p r o b l e m w ed e v e l o pa n dp r o v es o m eb a s i ct h e o r e m s a n d p r o p e r t i e so f th i sd u a l p r o b l e m i nt h et h i r dc h a p t e r ，am o d i f i e dn e w t 。nm e t h 。d is p r o p o s e df o rs o l v i n gt h ed u a lp r o b l e m w ep r o v eg e n e r a lc o n v e r g e n c ea n d 1 0 c a lc o n v e r g e n c eo ft h i sa l g o r i t h m a tl a s tw es h o wt h ev a l i d i t yo ft h e a l g o r i t h i nb yu s i n gs e v e r a ln u m e r ic a lt e s t s k e yw o r d s ：c o n i c m o d e l ，t r u s t r e g i o nm e t h o d ，c o n i c t r u s t r e g i o n s u b p r o b l e m d u a lp r o b l e m 。n e w t o nm e t h o d 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的 研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出 贡献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被 查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其他复制手段保存论文。 作者签名：召9 纲 日期：p f 7 ；i 南京航空航天大学顾士学位论文 绪论 信赖域方法是现代优化方法中一类重要的数值计算方法，由于其良好的可 靠性和很强的收敛性使其受到了非线性优化研究界的重视。 信赖域方法一般采用二次模型来逼近原问题。对于信赖域子问题( t s p ) 已 经有很多学者对其进行了深入的研究，参见文献 1 1 1 2 1 1 3 1 1 4 5 】。而基于二次模型 的信赖域方法的理论和算法也基本成熟。求解光滑无约束优化问题的信赖域方 法可参见文献 6 7 】【8 】 9 等；而求解约束优化问题的此类方法可参见文献 1 0 1 1 1 2 】【1 3 等；它们的收敛性结果可参见文献 1 4 】：非光滑优化问题的信赖 域方法可参见文献 1 5 】 1 6 】 1 7 】 18 】等。 d a v i d o n 【1 9 】于1 9 8 0 年首次提出了解无约柬优化问题的锥模型方法。锥模型 是二次模型的推广可以包含以前迭代过程中的函数信息。对于一些非二次性 态强、曲率变化剧烈的函数，用二次函数模型去逼近的效果并不好，而锥模型 去逼近的效果可能好于二次模型。文献【2 0 2 l 】 2 2 】等研究了锥模型共线调比拟 牛顿方法。近十多年来由于其良好性质，锥模型吸引了越来越多的重视和研究， 参见文献 2 3 卜 3 0 。锥模型信赖域方法也因此蓬勃发展，已经发展成为具有了 一定的理论基础并且实际计算中具有某方面优势的方法。 锥模型信赖域方法的关键步骤是构造锥模型信赖域子问题及求解，锥模型 信赖域子问题的最优性条件开始由文献 2 3 给出，文献 3 1 对锥信赖域子问题 进行了进一步的分类，给出了更为一般的最优性条件。除了把有些锥信赖域子 问题化戍7 z 次模型子问题来求解( 见文献 2 4 1 1 2 5 1 ) t - ，目前解一般锥模型信赖域 子问题还没有完善的方法。基于二次函数模型的优化方法经过多年的研究，理 论和算法都已经比较成熟，而锥模型方法还有很多的研究工作要做。 本文主要研究锥模型信赖域子问题的理论和方法。先通过变换把锥模型信 赖域子问题的一类情形转化为目标和约束函数均为二次的优化问题，再把原问 题转化为对偶问题，即无约束极大化问题，然后用修正的广义牛顿法来求解， 最后编制了算法，数值实验结果表明了算法的有效性。下面我们先介绍基本台勺 锥模型信赖域方法。 鳖堡垒塑堕三塑塾塑二鲞墼堡查堡一 第一章锥模型信赖域方法简介 在这章我们先介绍通常的二次模型与信赖域方法，接着介绍锥模型信赖 域子问题的各种形式，并将有些子问题转换成两个二次函数约柬子问题a 1 1 二次模型与信赖域方法 常用的解无约束最优化问题的信赖域方法3 2 1 是以拟牛顿型方法为基础。信 赖域法的基本思想是要求试探步d 。在信赖域之内，即在每次迭代时有一正数 乱，并要求试探步d 。满足 jj d 女j | 茎女， 其中l 是婀”中的某一向量范数。信赖域法的试探步d 。在某种意义下( 如对于暹 近子问题) 使得坼+ d 是在以h 为中心的广义球 ( x 。+ d ，i l i d i | s ， 上“最好的”点。由于试探步的这一性质以及要求变量之增量+ 。一曩也满足 i 卜 + i 一工女0 s 女- 因此信赖域法不进行搜索，而是令。= 以+ d 或者砟+ 。= 。 对于非线性优化问题信赖域法的一般形式如下 基本信赖域算法 步1给出初始值葺婀n ， 0 ，七等l ： 步2 计算一个满足i k + 以硎。 的试探步吐： 步3 如果d 。满足某种下降条件。则_ = 坼+ 4 。；否则t 札。= 。 步4以某种方式给出；七芦t + l ；转步2 。 在信赖域法中，试探步的计算一般是在信赖域 dl s 。 上求解一个原优 化问题的逼近问题，称这为信赖域子问题。一股的，对于无约柬优化问题 r a 。w i n 。f ( x ) 的信赖域子问题( 二次模型) 为 南京航空航天大学硕上学位论文 翟瓣g ；d + 圭d 7 b 。d = 妒。( d ) 趴t 由于二次模型形式简单，计算方便，因此基于二次模型的信赖域方法理论发展 较成熟。 1 2 锥模型与信赖域方法 锥模型信赖域方法以锥模型为基础，锥模型的形式如下 帅，= 矗+ 亲舞 其中a ，g 吼”，a 贸“”1 ，s 婀”。要求解的锥模型信赖域子问题如下： r a i n 甲( j )f 1 2 1 盯 s ( 1 3 ) i l 一口7s l 占o( 1 ，4 ) 【l u 、- 。， 其中t 岛为一个在0 和l 之间的正数。这里是用约束( 1 4 ) 来代替一般所用的约 束： 1 1 一口。5 i 0 。 那么，如上问题可以分成如下三种情况考虑推导可以参见文献 3 1 ： ( 1 ) 当】一占o 9 口时： m i n 甲( j ) n 删o ( 2 ) 当1 1 0 并且占对称。 我们先引用文献 2 4 中的引理2 ，】为了本文结构的完整性，我们给出证明 过程。 引理1 1 在条件1 一岛下情况( 1 ) 可化为二次模型信赖域子问题。 证明：首先，我们令 s w = 。 1 一口。s 由s h e r m a n - m o r r i s o n 定理“o 得 7 忙而 j l l j 问题情况( 1 ) 可以表示成： 展开( 1 9 ) 得 m i n g r w + 三爿w 旺8 剖玉 w 7 w ( 1 + 口7 w ) 2 2 。 设q 是正交旋转矩阵使得 跏= 0 - , l i e ， 其中，e ，= ( 1 , 0 ，o ) 7 ，并且令： 访= q w 那么( 1 ，1 0 ) 化为： 订7 订( 1 + l l o l l 瓦) 2 2 。 这罩，矿为向量订的第i 个元素。经过简单计算， 分( 啊一) 2 + 面；+ + e ；西， ( 18 、 ( 19 ) f 1 1 0 ) ) ) u 心 n r n 价等 (然显 南束航空航天大学硕士学位论文 黼删二， 蚴= 警西舍。 令： 五= 万一o g e 、，矿= d i a g ( 8 1 、1 ) ，那么，( 1 1 2 ) 就可以化筒为： c i r 昭蛩 再令：d = 矿j j ，那么： 归 1 2s 密， 再令：季= v - i - q g b = 矿一j 鲫q 7 y 一，那么情况( i ) 化为： m i n 亭7 d + 昙d 7 b d ( 1 1 3 ) 托t 陋五。 ( 1 1 4 ) 显然，问题( 1 1 3 ) 一( 1 1 4 ) 即为二次模型信赖域子问题。命题得证。 需要指出的是，在过去求解锥模型信赖域子问题的方法中，都需要对a 做 特殊的要求，即l - 1 4 ：叠 0 因此在锥模型插值过程中般都要求j 比较小。 这实际上就把锥模型子问题变成了近化- 次模型，这样做也容易使锥模型信赖 域方法矢去了其自身臼勺特点，文献 3 1 的初衰就是在不对口做任何约束的情形 下( 保持锥函数的特性) 。建立锥模型信赖域方法。现在我们讨论情况( 2 ) ，即 条件l l 一娅m 5 。满足。这时情况( z ) 变换成 1 m i n o ( d ) = g7 d + d 7 彪 ( 1 1 5 ) 而f 1 1 7 ) 等价于 j t d r d 一2 a - a 7 d 一尔( d r d ) 2 一0( i 1 6 1 錾 i - 矗。 1 。a d “ ( 1 + a r d ) 2 嵩s ( 1 + a r d 九l 刮， ( 11 7 ) 解锥信赖域于问题的一类数值方法 甚| j ( 口7 d ) 2 占o + ( 2 e o 1 ) 口7 d ( 1 一占。) 。( 1 1 8 ) 因此解情况( 2 ) 即解如下问题： r a i n 中( d ) = g r d + 妻d 7 b d z s r d r d 一2 岔口7 d 一6 - f a r d l2 一a ! 0 ( 口7 d ) 2 晶+ ( 2 ( 1 一1 ) a 7 d s ( 1 一e o ) ， 这就是问题( 1 5 ) - ( 1 7 ) 。 情况( 3 ) 的前一种情形完全同情况( 2 ) ，而在后一种情形下通过推导可以变 换成 m i n 由( d ) = 9 7 d + 昙d 7 8 d j f d r d 一2 a 2 a 7 d a 2 ( a 7 d 1 2 一? 0 ( d 7 d ) 二g o + ( 2 s 。+ 1 ) 口7 d 一( 1 - 占n ) 。 ( 1 1 9 ) ( 1 2 0 ) ( 1 2 1 ) 显然t 如果能解问题( 1 5 ) - ( 1 7 ) ，那么问题( 1 i 9 ) ( 1 2 1 ) 也同样能解决，从而锥模 型信赖域子问题也就迎刃而解了。下面我们主要探讨一种解问题( 1 5 ) ( 1 7 ) 的算 第二章对偶理论 在本章，我们运用对偶理论，把凸二次约束优化问题转化成为一个无约束 极大化问题，并推导了几个重要的定理。 2 1 凸对偶理论 首先，为了方便讨论，令 g ( d ) = ( 口7 d ) 2 占。+ ( 2 s o 1 ) a7 d 一( 1 一g o ) ， p ( d ) = d r d 一2 ：口7 d 一j ( 口7 d ) 2 一a 2 。 我们有如下引理。 引理2 1 g ( d ) 为凸函数。j d ( d ) 在0 s 1 一钏口i f 。满足时为凸函数，在 6 南京航空航天大学硕士学位论文 一 1 一a l l a l i i o ”表示正半定。显然q ( d ) 为凸函数。当0 1 一a t l a l i 氏时 i 一! 忙i i ：= ( i 一1 1 口忱l + i i 口| | ) 。，那么夏0 2 f p 。， p ( d ) 为凸函数。而当 一氏s 1 - a l l a l i o 时，l - 1 l l a l l 2 s 0 即p ( d ) 非凸函数。证毕。 因此本文把文献【3 l 】中信赖域子问题的第二种情况进一步分为 0 s l - 占。和一氏 1 一1 1 0 t i 0 来讨论。而本文主要研究o 1 一a l l a l | 即约 束函数为凸的这种情形的算法，同时给出一s 。 1 一a l l a l l 南京航空航天大学硕士学位论文 令蜀( 五- o ) = d ( 五o ) 2 a 7 ( 五期“，那么即需要证：鱼铲s o 。直接计算得 型：一日一l 望日一- a a 五 = 一6 o h 一醐7h 一 掣：2 岱o a ( a ，o ) a r h ( o ) 口+ 岱 d le 2a ( a 7 何( ，i ，o ) 1 口) a 五 = - 2 口( 2 o ) 二s 。日。h ( 2 o ) 一l 船7h ( 2 ，o ) 口一口( ，o ) 2g 。口7 h ( 2 ，0 ) 一a a 7 h ( a o ) 。 = 一3 c e ( a o ) ：n 口。h ( 2 o ) 口口h ( 2 o ) 一d 0 。 这洋就证明了，：( 五0 ) 在五0 上是凸的。 下面证明以( o ，) 在p 0 上是凸的。同理得 掣：一2 工( o ) 7h ( o ，声) - ix ( o f ) 。 u 令 苫：( o ，卢) ；x ( o ) 7h ( 0 ) x ( o ) ，因为掣：( ，一二口口7 ) 所以0 h ( i 0 , _ a ) 一- ：一h ( 0 ，) 一，( 一岔删7 ) h ( 0 ，) 一- ， 0 “ 证毕。 下a g ：( 0 1 ) ：2 圳，h ( o 川_ a x ( o f , h ) 掣掣州o ，) o p e d 己u 7o h ( o ，芦) 一 乩 = 一3 ( h ( 0 ，) x ( o ，) ) 7 ( ，一a - a a 7 ) ( 何( o ，) x ( o ，) ) s0 。 下面再证明两个有用的引理。 引理2 5 集合n ； ( 卫，掣) i 甲( 2 ，1 ) 中( o ，o ) ，( a ，) 有界。 证明： 因为可行域包含0 ，所以问题( 1 5 ) ( 1 7 ) 有解。设存在0 r ， ( d7 0 ) 二。+ ( 2 s 。一l ) a7 ( i 一( 1 一譬。) 0 使 x ( o ，) 解锥信赖域于问题的一类觳值方法 归8 2 2 岔口7c i 一2 。7 c ) 2 一2 o 成立，并且参照文献 4 1 】引理2 3 的证明有 掣i 五一) 。( & ) + 圭 ( ( 口7 c i ) 2 9 。+ ( 2 e o - i ) a 1 毒一( 1 - 6 0 ) ) 十 告( 峥 1 2 一岔一2 2 口7 0 ( 五，) 一岔7 0 ) 2 ) 而假若i 】一，则甲( 五，) 呻一，矛盾。因此定理得证。 引理2 6 设d ( 2 ) j l t l ( 2 1 0 ) 定义，( 五，) 正定，那么 。m 。a x 砖i l a ( a - ) | 1 ： 有界，由此，v 甲( a ，) 和v 2 掣( 五，m 在旯：上也有界。 证明：在这罩r 我们设：0 o j ，i 五f s m 。，f j 0 ， 则右式第二项： 卜船。一扣一口：+ 坂 。；i t i l + n o 岔i t 地 因此慨五h ) | i ：有界而v 甲( 兄卢) 和v - 甲( 五) 均只有d ( 五，p ) 一个变量，因此 j | v 甲( 丘) l f 和j f v3 甲( 五，) | f 也有界。 引理得证。 南京航空航天大学硕卜学位论文 第三章对偶问题求解 在这一章用广义牛顿法迭代求解对偶问题即无约束优化问题，对迭代过程中 产生的各种特殊情况予以分析，对一些性质进行了证明，并给出了详细的算法， 最后还在理论上讨论了原问题中约束函数非凸的情形。 3 ，t 基本思想 在这罩，我们参照了文献 4 1 中解c d t 子问题【4 2 】的思想，给出算法的基本 思想如下。设( 以肌) 7 为迭代点，用牛顿法求得迭代方向，并保证魄段) 半 正定，直到找到以，) 满足最优性条件为止。下面给出算法的基本步骤。 算法3 1 步1 ：绘定初始迭代点( 厶。鳓) 7 ， 步2 ：判断最优性条件若满足，则停：否则转步3 ， 步3 ：用牛顿法计算求得可行的并是可以接受的( 懿。，审。y ，或者用可以接受的 最速上方向， 步4 ：若试探步o 。+ 撕。，卢。+ 审。) 7 满足h ( + 阮，肌+ 酗。) 半正定，则 令( 以。以+ ) 7 = ( 五+ 3 2 。，阪+ 审。) 7 并由( 2 1 0 ) 计算d 。，转步2 ；否则 通过( 五，段) 7 和( 甄，呶) 7 构造出满足条件的轨。研+ ir ，转步2 。 3 2 算法实现 在算法3 1 步1 中t 我们取初始迭代点( 矗，硒) 7 为o ，o ) 7 。此时，条件 h ( 九，。) = b 0 满足。 在讨论算法最优性条件时，我们先引用文献f 3 1 的定理5 2 如下。 定理3 , 2 设a 婀“”且对称t 并假设一e o , , l l a l l 一1 0 “ 0 ( 3 2 ) ( 3 3 ) 算法3 1 步3 是非常重要的一步，也是较为复杂的。 在每次迭代中，己 知( 屯f 。) ，计算出( 巍。，酗。) 后令 ( 嚣) = 盼阱 ( 戳。审。) 由下列牛顿法的公式 4 南京航空航天大学硕士学位论文 v 掣e z ，p ，+ v 2 掣t 厶芦) ( = ( ：) t ，4 ， 求出。为方便记p = ( ) ，则当v 二甲( a ，卢) 菲奇异的时候， p = 一( v2 平( 五p ) ) 一v ￥( a ，一)( 3 5 ) 若v ! 甲( 五) 奇异，由广义逆的基本理论( 参见文献 3 7 】【3 8 】( 3 9 】) 知 声= 一( v2 甲( 五，) ) + v 甲( 五，) 。( 3 6 ) 我们称芦为广义牛顿步。出引理2 4 ，我们知道v2 甲( 五p ) 是一个二阶负半定矩 阵，因此广义逆是容易计算的。 当v ：甲( 五、) 非奇异时。由( 3 4 ) 可以推出p 是如下二次函数q ( s ) 的最大 值： q ( s ) = 5 7 可甲( 矗，芦) + 去s 7 v 2 甲( 兄， s 豫： ( 3 7 ) 但当v 二。t 1 2 ) 奇异时芦是问题( 3 7 ) 在v2 甲( 五，) 象空间阜的一个最大值。 引理3 3对十任惹涌足如f 条件的币数 以 m 一t r a c e v 2 甲( 五，) 】= 口2 口7 h 一口+ 工7h xf 3 8 ) 如果能满足： 芦7v 叫( 枷) q ( 声) ( 3 1 0 ) 而且只有当v 2 甲( 五，) 奇异的时候，( 3 9 ) 才可能成立。 证明：首先 q ( 击v 甲( 2 , a ) ) = 万1v 甲( a , 2 ) ，v 州卅+ 嘉v 哪川7 v 2 州川v 州川 g ( 芦) = 万7 v t i - , ( 2 ，) + 妄v 甲( 五，) 7 v2 、王，( 五，) + v 甲( 五，) 解锥佑赖域子何堰的一荚数值方法 出条件( 3 9 ) t 凼此 9 ( 击v v ( 五，) ) 一q ( 声) j ! j 矿1 v 甲( 丑f ) 7 v 3 甲( a , a ) v 甲( a , a ) 一昙v 甲( 五，一) 7 v 2 l 壬，( 工，卢) + 可l 壬，( 五，) 、 。 、 ， 由实对称矩阵的谱分解定理，存在正交阵q ，使 v 2 叫0 如，且c v 2 脚矿叫一乒一抄 这罩我们设v 二甲( 五，) 的两个特征值为：一 一如s 。才：1 1 五。， 1 0 = 0 靴：嘉( 一0 三：) ( 乒一如半嗽阮 下面，我们柬证明 苜一专 狐 出( 3 8 ) 我仍得到： m + 。 若 = 。，墨一击 = o 。若 。，彳一专 = 面b ( m 2 一番) 。因此 冒一嘉 o ，同理：五一未了t 。 现在证后一个结论。要使( 3 9 ) 式成立，只需： v 甲7 ( v 2 甲) + v 甲+ 击v 甲7 v 甲2 o 。 由上面的假设得 帅矿划陋辂 南京航空航天大学硕士学位论文 v _ ( 五，) 7 ( v 2 甲( 五，p ) ) + v 掣( 丑，) + 石i v 掣( 五，) 7 v v f ( a ，) = ( q v 甲( 1 ，) ) 。 一”+ 上0 膨 0 一+ 二 。 m ( q v 甲( 2 ，) ) 叫( 吖+ 击) + 业( 一巧+ 寺 这罩令 卿舻 显然当v ：q j ( 2 , a ) 非奇异时，一苜+ 上m 和一一+ 击都小于o ，则( 3 t 9 ) 式不成立， 因此只有当v 2 甲( 五一) 奇异时，( 3 9 ) 式才可能成立。命题得证。 在每步迭代中t 如果满足( 3 ，8 ) 的m 使( 3 9 ) 成立，则由如上的定理结论，我 们可用最速上升方向 p 2 玄w ( 却) ( 3 1 1 ) 束代替广义牛顿步石。 由引理2 5 ，我们知道对偶问题( 2 1 1 ) 的解有界。因此，如果广义牛顿步太大 时，我们也可用最速上升法，即用声代替万作为实验步。我们用下式： 2 5( 3 1 2 ) 来判断广义牛顿步是否过大，其中j 是在每次迭代中产生的一个正参数。 下面讨论( 五0 ) 7 ，( 0 。) 7 这些边界的处理方法。 在边界点( 0 ) 7 处，如果似7 d ) 2 + ( 2 氏一1 ) a 7 d 一( 1 一占。) o ，这说明原问 题的约束条件( 1 6 ) 是不起作用的，则我们用投影最速上升方向 r 觑、f 0 、 l 审j 2 k 卜2 a - a ，d 一岔( 口。) 二一a - ) 2 x r h - t x j ： b 1 3 ) 解锥信赖域于问题的一类数值方往 而如果迭代步万或者多中第一项是负的时候，显然迭代步是不可行的，圊样我 们用( 3 1 3 ) 来作为迭代步。这里d = d ( 2 ，“) ，= ( ，“) 。 在边界点( 且。o ) 7 处，我们用同样的方法来处理，即如果 2 - 2 & - a 7 d - 2 ( a 7 d ) 二_ a 2 0 或者迭代步的第二项是负的，那我们用投影最速上升方向 ：p 们2 ( 2 铲1 ) a r d - ( 1 - - o c _ 0 ) ) 2 扩口7 k ( 3 1 4 ) l 审j - 1 0 j p ” 在非边界处，同样会出现迭代步不可行的情况，即五+ 况 0 或者 芦+ 牵 o ，k = 1 ， 步1 ：计算h ( 2 。，“) ，并对h ( 2 。“i ) 迸行c h o l e s k y 分解，由( 2 1 0 ) 计算矾： 步2 ：根据( 3 2 3 ) ，( 3 2 4 ) 计算w 1w ：，若收敛，则停：否则， 令 加= m a x i m 一i ，口：口7 j 可。a + x 7 h “砖， & = m a x s 女一l ，l i v 、壬，f | 2 m 。 ； 如果 t = o 。w ，o ，转步4 ；如果凤= o ，_ ，2s o ，转步s ； 步3 ：计算广义牛顿步，并且令( 6 2 。，印。) 7 = 万，如果( 3 t 2 ) 成立则令 ( 6 2 。舡。) 7 = 声，如果 = o ，吼 0 ，且 挺i m 。m 2 。 ( 3 2 7 ) 因此存在i f 整数五。，使得当t k o 时。满足( 3 t 8 ) ，那么声是可以接受的迭代步。 由算法3 1 步7 知对所有的k 2 x o - m 。= m h ，这与( 3 2 7 ) 矛盾。因此，结论为 真。 3 ，3 非凸情形 在条件- - 6 。 0 ，若 h ( 2 女+ 巍d 十印。) 不j 下定，我们可以适当选取r ( o ，1 ) 使得 胃( 五+ 嗽“+ 却。) 为正定。 ， 南京航空航天大学硕士学位论文 第四章收敛性分析 本章主要证明了算法3 4 的全局收敛性和局部收敛性。 4 1 全局收敛性 为了进行收敛性分析，我们定义向量 广( 五) = e a e r , v - p ( a ，) 若五= 0 且( 口7 d ) 2 9 。+ ( 2 s o 一1 ) a7 d 一( 1 一占。) s 0 ， q 8 i v 甲( 五芦) 若= o g l l e l t ；一2 - a 7 d 一，( 口7 d ) 2 一岔s d ， ( o o ) 7 若五= a = o ，；一2 a 2 a r d a 2 ( a r d ) ! 一a 2 o 且( 4 1 ) ( 口7 d ) 3 o + ( 2 9 0 - 1 ) a 7 d 一( 1 一s o ) 蔓0 ， v p ( 2 ，)其他情况 其中( 五) 峨：e l = f 1o ) 7 ，岛= f o1 ) 7 ，并定义 乏= 肛( ，。) 虬 ( 4 2 ) 我们知道( 五，) 是问题( 2 1 1 ) 的最优解，n g l 2 n ，( 五，) = 0 。因此我们需要证 明毛_ 0 。为此，我们首先证明如下引理。 引理4 1 设( 甄，审。) 。是第k 步迭代点则我们有如下结论 吼= w ；v ，舨删v k r a i n 1 ，毛m 。) ， ( 4 3 ) 其中l u 。( 懿。舡。) 7 v 敝= 审甲( ，以) ，坂，& 由算法3 ，4 步2 中确定。 证明! 若w 。：声( 见( 3 1 1 ) ) 则显然嘶= 1 ，结论成立。 若是广义牛顿步w k =