（应用数学专业论文）非凸优化问题的两个算法及其收敛性.pdf

摘要 对于带约束的非凸优化问题，逐步二次规划法( s q p ) 是十分有效的方法，但仍 有一些不足之处，例如要求h e s s e 矩阵正定等。信赖域方法可以避免这一缺陷。信 赖域方法的显著特点是它的可靠性和强适性，且具有很强的收敛性。本文研究求 解等式约束非凸优化问题的的信赖域方法。 内点法在求解大规模线性优化问题方面取得了很大成功，并已成功地应用于求 解半定规划( s d p ) ，在求解非线性规划方面也取得进展。 在第一章我们对信赖域方法的历史及结果作了简单回顾。 在第二章我们在b y r d - o m o j o k u n 算法的基础上，考虑到两个子问题的不同特 性和收敛速度，构造了两个有着相互独立的信赖域约束的子问题，证明了算法的 全局收敛性。由于效益函数是不可微的，在引进了二阶校正步后，证明了算法是 超线性收敛的。在新算法的基础上进行了进一步的讨论，给出新算法的一个改进 方案，并证明了算法的全局收敛性。 在第三章给出一个求解一般约束的非凸优化问题的原始- 对偶信赖域方法。( 分 析表明在靠近最优点时，算法的表现与n e w t o n 法类似，但算法的全局收敛性要优 于它。本章在不给出4 线性无关的条件下讨论了算法的全局收敛性。厂 关键词：非凸优化问题，信赖域法，原始对偶内点法，二阶校正步。 t w oa l g o r i t h m sa n d c o n v e r g 戴n c 嚣a n a l y s l sf o r n o n c o n v e xn o n l i n e a rp r o g r a m m i n g w e n - y a hy u a n ( a p p l i e dm a t h e m a t i c s ) s u p e r v i s e db yp r o f y a - x i a n gy u a n a 嚣s 墨l 醴e t f o rc o n s t r a i n e dn o n c o n v e x o p t i m i z a t i o np r o b l e m s ，s e q u e n t i a lq u a d r a t i c p r o g r a m m i n g ( s o p ) m e t h o d i sv e r ye f f e c t i v e b u ti ts t i l lc o n t a i n ss h o r t c o m i n g ，s u c ha s r e q u i r i n g h e s s i a nm a t r i x p o s i t i v ed e f i n i t e t r u s tr e g i o nm e t h o d sc a na v o i dt h e s e d r a w b a c k s t h e y 鹏r e l i a b l ea n dr o b u s t , a n dh a v es 行o n gc o n v e r g e n c ep r o p e r t y i n c h a p t e r2w ep r o p o s eat r u s tr e g i o nm e t h o df o re q u a l i t yc o n s t r a i n e do p t i m i z a t i o n p r o b l e m 。i nc h a p t e r4 锵g i v e am o d i f i e d a l g o d t h m 。 i n t e r i o rp o i n tm e t h o dw o r ep r o v e dt ob ee f f e c t i v ef o rs o l v i n gl a r g es c a l el i n e a r p r o g r a m m i n g ，a n dh a v eb e e ns u c c e s s f u l l ye x t e n d e d t os o l v es e m i d e f i n i t e p o s i t i v e p r o g r a m m i n g ( s d p ) p r o b l e m s 。p r o g r e s s h a sb e e nm a d eo l li n t e r i o rp o i n t sf o rn o n c o n v e x o p t i m i z a t i o np r o b l e n m i nc h a p t e r3w ep r e s e n tap r i m a l - d u a lt r u s tr e g i o nm e t h o df o r c o n s t r a i n e dn o n c o n v e x o p t i m i z a t i o np r o b l e m s i n c h a p t e r1w e r e v i e wt r u s tr e g i o nm e t h o d s ， i nc h a p t e r2at r u s tr e g i o nm e t h o db a s e do no m o j o k u na l g o r i t h m i s g i v e n c o n s i d e r i n gv e r t i c a ls u b p r o b l e ma n dh o r i z o n t a ls u b p r o b l e m sd i f f e r e n tp r o p e r t i e sa n d c o n v e r g e n tr a t e , w e r e d e f i n e dt h e s et w os u b p r o b l e m si nt w os e p a r a t et r u s tr e g i o n s t h e g l o b a lc o n v e r g e n c eo ft h ea l g o r i t h m i s p r o v e d 。t h ea l g o r i t h m w i t hs e c o n do r d e r c o r r e c t i o n si ss u p e r l i n e a r l yc o n v e r g e n t am o d i f i e da l g o r i t h mi sg i v e n t h eg l o b a l c o n v e r g e n c e i sp r o v e d 。 i n c h a p t e r 3w ed e s c r i b ea n da n a l y z ea l la l g o r i t h mt h a tu s e si d e a sf r o m i n t e r i o rp o i n t m e t h o da n ds e q u e n t i a lq u a d r a t i cp r o g r a m m i n g t h ea l g o r i t h ms o l v e so p t i m i z a t i o n s p r o b l e m sw i t h n o n l i n e a r e q u a l i t yc o n s t r a i n t , p l u s i n gt h ei m p l i c i tc o n s t r a i n t p 0 ，eu s e t h es t r a t e g yi nc h a p t e r2a n de n f o r c es 0b ym e a n s o ft h et r u s tr e g i o na n dt h eb a r r i e r t e r m t h eg l o b a lc o n v e r g e n c e i sg i v e n w h e nt h ei t e m t i v ep o i n ti sn e a r t h eo p t i m a l ，t h e m e t 1 0 di ss i m i l a rt on e w t o nm e t l l o d b u tt h ea l g o r i t h m g l o b a lc o n v e r g e n c ei sb e t t e r k e yw o r d s ：n o n c o n v e x o p t i m i z a t i o np r o b l e m s ，t r u s tr e g i o nm e t h o d ，p r i m a l d u a l i n t e r i o rm e t h o d ，s e c o n d - o r d e rc o r r e c t i o n 1 1 概述 第一章绪论 最优化问题可以追溯到十分古老的极值问题。早在n e w t o n 创立微积分之前的 十七世纪，d e s c a r t e s 和f e r m a t 就研究过如何寻找一个函数的极值点问题。但是 直到第二次世界大战以后，随着军事、工业、运输、经济等发展的需求，特别是 当计算机出现以后，最优化这门学科才得以蓬勃发展。 最优化问题是求一个定义在n 维空间的函数极值问题。函数的自变量可能受限 制于几个等式或不等式约束。通常有如下形式： m i n ，( 工)( 1 1 1 ) s t 岛( 力= 0 ，e ，( 1 1 2 ) q ( 力0 ， f ， ( 1 1 3 ) 其中f ( x ) 和c j ( x ) ，i e u x 都是定义在r ”上的函数，e = l ，2 ，m 。 ， ，= + 1 ，埘 。f ( x ) 是目标函数，c f o ) ( f = l ，m ) 是约束函数。( 1 1 2 ) 一( 1 1 3 ) 称为约束条件，满足约束条件的点称为可行点，可行点的集合 z = xl c i ( x ) = o ，i e ，c ，( x ) 0 ，i ， 称为可行域。当可行域是整个实数空间时，即m = o ，问题是无约束优化问题，否 则是约束优化问题。在约束优化问题中，如果只有等式，则称为等式约束优化问 题；如果只有不等式约束，则称为不等式优化问题。本文讨论求解等式约束优化 问题的信赖域方法及求解不等式约束优化问题的内点信赖域法。 定义1 1 1 设x x ，如果对某一占 0 有 ，( x ) ，( x ) ，x x n 丑( x ，艿) x + ) ， 则称工是问题( 1 1 1 ) 一( 1 1 3 ) 的局部极小值点。其中 曰( x ，占) ： 工l l k - x 1 1 2 蚰 如果( 1 1 4 ) 对严格不等号“ ”成立，则称x 是局部严格极小值点。 ( 1 1 4 ) ( 1 1 5 ) 第一章绪论 博t 毕业论文 通常情况下，集合x n b ( x + ，占) & 中有无穷多个点，通过验证( 1 1 4 ) 来判断 x 是否是优化问题( 1 1 1 卜_ ( 1 1 3 ) 的解显然是不可行的，因而代之以与之等价的 最优性条件。 定理1 1 2 ( f r i t z - j o h n 必要条件) 设工x 是问题( 1 1 1 ) - - ( 1 1 3 ) 的局部极小值 点，则存在不全为零的非负数毛，正( f = l ，m ) 使得 毛v 厂( x ) 一v c ( x + ) z = 0 ( 1 1 6 ) z o ，z c t ( 工+ ) = 0 ，i ， ( 1 1 7 ) 其中v c ( x ) = ( v c l ( x ) ，v c 。( x ) ) r 。 约束优化问题的局部极小点必满足f r i t z j o h n 条件。在f r i t z - j o h n 条件中，若 矗= 0 ，则f r i t z - j o h n 条件与目标函数无关，这对问题的解的描述没有多少价值。 要使疋0 ，则需要一些约束规格。在一定约束规格下，有如下k u h n - t u e k e r 定 理。 定理1 1 3 ( k u h n - t u c k e r 必要条件) 设x x 是问题( 1 1 1 卜_ ( 1 1 3 ) 的局部极小值 点，则在一定约束规格条件下，存在正o = l ，小) ，使得 w ( x ) 一v c ( x 。) z = 0 正o ，z c ，( x ) = 0 ，i j ( 1 1 8 ) ( 1 1 9 ) 条件( 1 1 8 卜_ ( 1 1 9 ) 称为k u h n - t u c k e r 条件，满足k u l m - t u c k e r 条件的点称为 k u h nt u c k e r 点( 简称为k - t 点) 。由于k a m s h ( 1 9 3 9 ) 也类似考虑了约束优化问题 的最优性条件，所以也有人将其称为k k - t 点。 求解问题( 1 i 1 卜 ( 1 2 - 3 ) s t c i ( x d + d 7 v c f ( x ) = 0 ，i e ， ( 1 2 4 ) 色( 故) + d r v c f ( ) 0 ，f 毫， ( 1 2 5 ) 夜( 囝是嚣标函数在警蓊迭代点墨熬邻城内熬二次遥逛，箕中g t = v f ( x , ) ，壤跫 3 羔! 蔓主一一 堕堡 堡圭兰些笙苎 l a g r a n g e 函数在处的h e s s e 矩阵或是h e s s e 矩阵的近似。( 1 2 4 ) ( 1 2 5 ) 是约束函 数在扎的线性展开。在一定条件下，s q p 法是收敛的。若严格互补条件成立，且b 。 满足一定条件下可证s q p 法是超线性收敛的。 n e w t o n 法和l a g r a n g e - n e w t o n 法都有其局限性，它们都要求初始点充分靠近 最优解才能保证算法的收敛性。这个条件在实际计算中很难得到满足。s q p 方法 通常要求l a g r a n g e 函数的h e s s e 矩阵或h e s s e 矩阵的近似阵一致正定，而许多实 际问题的l a g r a n g e 函数的h e s s e 矩阵不一定是正定的，也可能是坏条件的。毋不 正定可能使由( 1 2 3 卜- ( 1 2 5 ) 产生的搜索方向以是无界的，从而导致算法的失败。 信赖域的引入可以克服n e w t o n 法对初值的较高要求，从而保证从任一点出发， 算法都收敛到局部极小点。同时结合信赖域技巧的s q p 方法也放松了对毋的要求， 只需其有界即可。 信赖域方法是在二十世纪7 0 年代才发展起来的一类较新的方法。与线搜索方 法相比，信赖域方法还不够成熟，在实际应用中还没有线搜索方法那么广泛。但 是，信赖域方法具有两个性质，一是它的可靠性和强适性，即在一般的条件下算 法是全局收敛的：二是它的很强的收敛性，即算法是超线性收敛的。 信赖域方法的研究可以追溯到l e v e n b e r g ( 1 9 4 4 ) 的一篇研究非线性最小二乘法 的文章。在这篇文章中，他提出了信赖域的概念。当然这一概念与我们现在所使 用的信赖域概念有所不同。在1 9 6 0 年m o r r i s o n 在关于u - a j a c t o r yt r a c k i n g 的文章中 提出在一个固定半径的球内求解最小二乘问题的方法。1 9 6 3 年m a r q u a r d t 独立提 出了同样的观点。g r i t t i t h 和s t e w a r t ( 1 9 6 1 ) 提出在当前迭代点的邻域内求解模型 的极值点，但他们并没有提出校正信赖域的大小，而是在整个计算过程中保持不 变。g o l d f e l d t , q u a n d t 和f r o t t e r ( 1 9 6 6 ) 将此思想应用于无约束优化问题，用以防 止步长过大。p o w e l l ( 1 9 7 0 ) 进一步发展了信赖域的概念，利用信赖域这一技巧保 证了算法的全局收敛性。 现在我们回顾一下非线性最小二乘问题的著名的l e v e n b e r g - - m a r q u a r d t 方法。 对于非线性最小二乘问题： 恶净 ，( 工) 旺 ( 1 2 6 ) 其中f ( x ) = ( f d x ) ，l ( x ) ) 7 ，( 曲o = 1 ，m ) 是尺”中的连续可微的函数，求解此 问题的迭代公式是： h + l = 扎+ d k = 一a ( x ) + f ( x i ) ( 1 2 7 ) 其中a ( x k ) ：v f ( x r ：是f ( x ) y f f ：x k 点的j a c o b i 距阵。a + 表示一的广义逆a 不难看 4 第章 绪论 博_ 。毕业论文 出g a u s s - n e w t o n 步 是问题 d k = 一彳( z i ) + f ( x )( i _ 2 8 ) 卿i i f ( x * ) + 4 ( k ) d l l ； ( 1j 2 j 9 ) 的解。问题( 1 2 9 ) 是( 1 2 6 ) 在当前迭代点的近似。为了克服a ( x 。) 接近奇异时带来 的数值困难，l e v e n b e r g ( 1 9 4 4 ) 提出并由m a r q u a r d t ( 1 9 6 3 ) 重新发现的l e v e n b e r g - m a r q u a r d t 方法选取 d i = 一a ( x k ) 7 4 ( 工1 ) + ，) - 1 爿( x 女) f ( x 。) ( 1 2 1 0 ) 其中以0 是一个逐步修正的参数，它所起的作用是防止以过长。容易看到 l e v e n b e r g - m a r q u a r d t 步n 2 1 0 ) 是问题 r a 删i n i i v ( x k ) + 爿( 坼) r i l l ：+ 以： ( 1 2 1 1 ) 的解，丑i j 训i 可限制喀0 过大。 若令 = 0 ( 4 ( 以) 7 a ( x i ) + 以，) a ( x 。) 7 f ( x i ) 9 2 ， ( 1 2 1 2 ) 则不难发现( 1 2 1 0 ) 也是如下问题 m 。i l l i i y ( x - ) + 4 ( 以) r i l l ： ( 1 2 1 3 ) s t i i d l l ：i ( 1 2 1 4 ) 的解。而问题( 1 2 1 3 卜_ ( 1 2 1 4 ) 是信赖域子问题。在此意义下，l e v e n b e r g m a d q u a r d t 法是一特殊的信赖域方法。不过这一方法的不便之处在于以的确定。以的加入就 是为了调节步长破，使其不致过长，而调节。比调节以更直观、更容易、也更合 理。 信赖域方法的构造和逼近是密切相关的。它的基本思想是在每次迭代过程中， 在以当前迭代点为中心的邻域内，构造一个近似于原闯题的逼近模型，此邻域被 称为信赖域。例如，对无约束优化问题在信赖域内对逼近模型求极小，得到如下 子问题： m i n 纸t “t j i d 7 即= 丸( d ) ( 1 2 1 5 ) s 羔三j 三一一 堕笙 坚主望逃鎏兰 s t 恻2 a 女( 1 2 1 6 ) 其中g t 怒磺标函数酾梯度，b k 建蘸标函数静h e s s e 矩阵或遮戗阵，； o 楚信 赖域半径。 只有在小邻域内逼避效果才会好，因此限制步长的大小是念理的。求解- t - 闯题 ( i 2 t 5 1 2 。l 缮蘩试探步d k ，然藤穰趣菜浮徐蘧数确定怒孬接受或莠修莲信 赖域的大小a 对于无约柬问题来讲，评价函数就鼹其目标函数。对于约束问题来 讲，评价硒数通常是某罚函数。 在予翊题( 1 。2 。1 5 0 ，嚣o ，0 岛 c 4 0 ，使得 壤- 0 ，则 到b 1 1 = o ( 1 2 2 0 ) 定理1 2 5 假定算法1 2 2 产生的点列k 。x ，v 2 ，( x ) 在x 附近连续且 审2 f ( x + ) 聂定著籽t l ： e ，辩胼脊满足 a ( x ) 9 d = o ( 1 。3 。鳓 熬d 帮鸯 羹串 d 7 矿+ d - 撇i t 1 i ：。 渺+ = v 2 歹强。) 一髫审毡姆) ， 舔3 2 6 ) z 。嘏，毒楚游怒下式熬l a g r a n g e 黍子 v f ( x + ) 一蓑蔫秘* 密，l 、3 2 7 ) 彝鼗 糯弘m 螂a x 脚 懿哦 强 粼奴 越缝健收敛戮潜。 鼹鬻等式魏寨麴斑类予箨避嚣毙c d t 予鞠越： 掰融g ；霉+ 圭矗7 毽菇( 1 ，3 2 9 ) 姓辩蠢十l 基美， l 。3 ，3 0 ) 麟氛， l + 3 ，3 l c d t 予问题盼鼗忧憔簸件是y u a n ( 1 9 9 0 ) 娥鲰徐出。骞处c d t 乎潴题的最优性 暴搏袋全嚣鬓翡蘩爨涎蠛毒曩黪壤逸( 1 9 9 8 。 透嚣一类方港蹙剿溪零宝鬻技巧慕藜逡予瓣邀。o m o j o k , m j 弼挚黪袋簿攀 式约聚闻题的信赖蛾子问题转张为求解两个滗瓣聚信赖域予闯题，群求辩辫直孑 第一章 博士毕业论文 问题： m i n 恢+ “酬 f 1 3 3 2 ) s t 1v 忙弘女( 1 3 3 3 ) 产生一令法方囊毪，然聪求鼹窳乎予瓣蘧： m i n q + 圾u ) + 矗7 耳( 1 3 3 4 ) 8 t a ：h = 0 ，( 1 3 3 5 ) l k + 硝a # ， 0 ，则算法 毒鬏步终获，瑟 l 睃v ，圳+ 蔓 ( 1 3 3 8 ) 其孛l k = ， 椎) + 餐c ( ) 楚l a g r 强g e 避数。 另一炎方法是利用罚函数导出信赖域子问题，如基于非光滑精确罚函数的子 翅题： r a i n g ：矗+ 辞b k d + c q i ( c 。+ _ 参疗) 一l ( 1 3 3 9 ) s t 删a ( 1 3 4 0 ) f l e t c h e r ( 1 9 8 1 ) 彀1 - 舔数，y u a n ( 1 9 9 1 ) 考瘪了一蘧鼗，嚣曩绘爨了窝露逐步骖 改吼的技巧。 近年米内点法一直是研究的热点，并且在线性规划和半定规划方面都取得了很 大戆盛凌。翔 琴将内淼浚应弱裂 # 线性援划孛一鬟是入翻关心麴漾题，这方穗豹工 作集中在求解具有不簿式约束问磁上可见b y r d ，g i l b e r t 釉n o c e d a l ( 1 9 9 8 ) , 1 l 第一蕈 绪论 博士毕业论文 e l _ b a r k e y ，t a p i a ，t s u c h i y a 和y z h a n g ( 1 9 9 6 ) ，g a y ，o v e r t o n 和w r i g h t ( 1 9 9 6 ) ， v a n d e r b e i 和s h a n n o ( 19 9 7 ) ，y a m a s h i t a ( 19 9 4 ) ，c o r m ，g o u l d ，o r b a n 和t 0 i n t ( 1 9 9 9 ) ， c o l e m a n 和l i ( 1 9 9 6 ) 。 一部分方法利用罚函数，通过加入松弛变量将不等式约束转化为等式约束进行 求解，即考虑如下问题： m i n 八工) 一l n ( s 0 ) ( 1 3 4 1 ) j ；l s t c f ( x ) = 0 ， i e ， ( i 3 4 2 ) c ，( x ) + s = 0 ， i 1 ( 1 3 4 3 ) v a n d e r b e i 和s h a n n o ( 1 9 9 7 ) 利用n e w t o n 法对上述障碍子问题的k - k - t 系统进行求 解。b y r 0 ，g i l b e r t 和n o c e d a l ( 1 9 9 8 ) 利用信赖域法求解上述障碍子问题，在适当 条件下，证明了算法的全局收敛性。 w i c h t e r 和b i e g l e r ( 1 9 9 9 ) 构造例子说明一些求解非线性规划的内点法，特别是 使用线搜索的方法，可能收敛到一个不可行点。 对具有特殊结构的约束条件的闯题，信赖域予闯题可特别构造，可见b u r k e ， m o r 6 和t o r a l d o ( 1 9 9 0 ) ，c o r m ，g o u l d 和t o i n t ( 1 9 8 8 ) 以及g a y ( 1 9 8 4 ) 。 n o c e d a l 和y u a n ( 1 9 9 1 ) 还讨论了将信赖域方法与线搜索方法相结合的算法， 以减少计算量。 2 第一章 绪论 博士毕业论文 1 4 本文内容简介 通过近三十年来深入细致的研究，信赖域方法已发展得较为成熟，在理论和算 法上都取得了很多成果，它的显著特点是强适性和很快的收敛速度，这在1 3 中 给出了详细的介绍。 b y r d - o m o j o k u n 算法是求解等式约束的大规模优化问题的有效方法。在每一步 迭代，它求解的是两个比较容易求解的无约束子问题。本文在b y r d o m o j o k u n 算 法的基础上，在第二章中提出了一个新算法。考虑到垂直子问题和水平子问题各 自不同的收敛速度及不同的目标函数特性，将它们分开在两个相互独立的信赖域 内进行求解，即求解垂直子问题： r a i ni i c k + 彳f 咋8 s t m i s ： 和水平子问题： m i n 爵乙+ ( 互) 7 b ( 五) s t 9 乙忙砖 其中畿和缱是两个相互独立的信赖域半径，分别由a o 和砖迭代而来。我们将讨 论算法的全局收敛性和局部收敛性。 近十几年来，自从k a r m a r k a r 提出求解线性规划的内点法以后，内点法一直是 研究的热点，它在线性规划和半定规划( s e m i d e f i n i t ep r o g r a m m i n g ) 都取得了极 大成功，因此如何将其应用到非线性规划上来，如何与信赖域方法相结合都成为 人们所关注的课题，在这方面已经取得了一些可喜的结果。本文将内点法和信赖 域技巧相结合，在第三章中提出了一个求解一般约束的非凸的非线性规划的原始一 对偶信赖域法。由于信赖域方法的强适性，应用了信赖域技巧的方法都具有全局 收敛性，我们的方法与其它求解非线性规划的内点法的局部性质是类似的，但我 们的算法的全局收敛性要优于一般的内点法，在文中给出了算法的全局收敛性证 明。 本文如不特别说明，使用的范数都是2 - 范数。 1 3 第二章求解等式约束优化问题的信赖域法 2 1 弓i 言 本章考虑非线性等式约束优化问题： m i n ，( x )( 2 1 1 ) 采| 0 ( 砖= 0 ，i = l ，掰。( 2 1 2 ) 其中秘标函数，( ，等式约束岛( 曲= 0 ( i = l ，m ) - - 次连续可微，约束个数m 不超 过燮最个数n 。 s q p 方法是求解一般约束优优问题的一类十分重要的遮代法，将其奄信赖域技 巧穗缋合褥到求瓣约束税纯阉艨稳傣蔟域方法。这类算法缀多，在第一牵串给出 了简要介绍。这然方法利用信赖域技巧作为众局化方法，得到算法的全局收敛性。 求解等式约束间题的信赖域法大都具有如下步骤：在渴前迭代点收，五，通 遘求熬塞赣壤予麓嚣褥嚣凌爨步癍，瘸菜释方式售诗l a g r a n g e 黍子太在赣戆 迭代点稚。= 椎+ 以利用效益踊数对其进行泖0 试，以决定怒否接受它，鲻时修正信 赖域半径，得到新的逼近模型。 零章在b y r d - o m o j o k u n 雾法躯基穑上，绘密一个求嬲镣式约衷懿爨赣域法。 1 4 第二章 求解肄式约束优化问题的信赖域法博：1 - - 毕业论文 2 2 b y r d o m o j o k u n 算法 b y r d - o m o j o k t m 算法褥慧予早期工稼：v a r d i ( 1 9 8 5 ) ，c e l i s ，d e n n i s 和t a p i a ( 1 9 8 5 ) ，p o w e l l 和y u a n ( 1 9 9 1 ) ，b y r d , s c l m a b e l 和s c h u l t z ( 1 9 8 5 ) ，在每一步迭代， 它将信赖域予问蹶转化为两个易于求解的无约束信赖域予问题，因而怒求解大规 模耩蔬傀魏阉题豹一类骞效方法，楚l a l e e ，n o e e d a l 秘p l a n t e n g a ( 1 9 9 8 ) 。 在当前迭代点h ，b y r d o m o j o k u n 算法选择一个信赖域半径t 及l a g r a n g e 乘 子九，求解如下信赖域子问题： m i n g r d + 喜矗7 致矗 ( 2 ；2 1 ) s t a ：d + c ；0 ， ( 2 2 2 ) l i d l i a i ( 2 2 3 ) 其审毽是l a g r a n g e 涵数熬h e s s e 矩阵或冀= l 琏 娃阵。 然而由于信赖域约束q 2 ，3 ) 的雩l 入，可能导致( 2 2 2 ) 簌僖赖域蠢没有解，产堂 不棚容性。b y r d - o m o j o k u n 提出酋先在信赖城内计算尽可能满足线性约束的垂直 步，即预先给定一个参数孝( 0 , 1 ) ，求解垂纛予问题： m i n 瞅+ 硼 s t k l l - 孝a t 缮戮骧耋步毪。然器求解懿下子 蘧爨褥銎l 凌探多： l a t i n 姣d + 毛d t b k d s t c i + d = c i + 鬈v 女， k d l l - a t 。 令d = h + 南，劐上述问题转化为 r r f i n ( g k + b k v i ) 7 | h + 矗7 爆办 s 。t a l h 一0 ， 歉+ 确矗。 ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) ( 2 2 7 ) 往2 。8 ) ( 2 2 9 ) 陀2 1 0 ) ( 2 2 。1 ) 上述子问题称为水平子问麒。水平子问题总是有非空的可行域( h k = 0 即是一 个w 行解) 。垂巍予问题存在许多鳃，其中必商一解位于4 的值空间。水平子问题 茨赭满是矗：0 ，掰教燕京熬零空阉墨。设五震“”是鬈戆零窆阗黪 一组正交基，则稃在r ，有= 乙“。问题( 2 2 9 ) 一( 2 2 1 1 ) 转化为无约束的 1 5 第二章求解等式约束优化问题的信赖域法博_ ：毕业论文 信赖域子问题 m i n ( 反+ b h ) 7 五“+ “7 刃峨z 1 1 1 “ 胁忙压可可 求解上述子问题得到“。，此时有以= h + z k u ，令工= + 以， 判断x 。是否可被接受并修正信赖域半径。这里效益函数为 y o ，) = f ( x ) + l l c o , r e ( 0 ，1 ) ，孝( 0 , 1 ) ，k = 0 。 ( 1 ) 计算五，c i ，g ，a ，z i ，以： ( 2 ) 如果恬。- a 。以忆 占，i k 忆 占，则停止 ( 3 ) 修正毋； ( 4 ) 近似求解垂直子问题和水平子问题，得到v 。和h k ，d t = v t + ； ( 5 ) 计算实际下降量酊e 以，预测下降量p ，8 或和比值= 口” r e 矾 ( 6 ) 如果咋 。l + 氖l 麒，