（应用数学专业论文）线性约束优化问题的仿射信赖域子空间算法.pdf

中交摘要 摘要 最优化理论与方法是决策科学和系统分析中的一个重要工具，在很多领域都有着非 常广泛的应用。本文主要研究线性等式和不等式约束的非线性优化问题，提出了结合内 点回代线搜索技术的仿射信赖域子空间算法 信赖域策略是求解非线性规划问题的两种基本逼近方法之一，它能保证算法的 整体收敛性对于无约束优化问题，信赖域方法的思想非常简单与直观。但是， 对于约束优化问题，由于约束的存在，通常很难构造一个类似的信赖域子问题。 最近，c o l e m a n 和l i 针对仅带有线性不等式约束的优化问题，提出了“双信赖域方 法”( t r a m ) ，通过仿射变换，成功地构建了一个近似二次模型函数和信赖域子问题，同 时证明了算法的整体收敛性，然而文中并未具体给出求解信赖域子问题的方法，且在每 次迭代过程中，往往要重复多次求解该子问题，才能获得可接受的严格内点可行步，因 此，每得到一新的迭代步，必带来较大的计算量。为克服在求解信赖域子问题时所面临 的一系列困难，本文将借助于子空间技术，信赖域算法及内点回代线搜索技术来搜索得 到一个严格内点可行步。信赖域子空间技术的应用使得本算法适用于求解大型的约束优 化问题。 本文先对一些相关概念、理论及方法进行简单的回顾，作为进一步研究的基础接 着引进一个仿射变换矩阵，同时构建一个近似二次模型函数和信赖域子问题。受到子空 间技术的启发，我们给出二维子空间的具体形式，并结合子空间求解信赖域子问题，从 而获得模型的一个候选的迭代方向，然后沿此方向通过线搜索获得步长因子，既能保证 迭代点严格可行，又能使目标函数在迭代点处单调下降。最后基于信赖域子空问算法的 良好性质，在合理的假设条件下，证明了该算法不仅具有整体收敛性，而且保持局部超 线性收敛速率数值计算结果表明了算法的有效性 关键词：非线性约束优化；不等式约束：信赖域算法：子空间技术；仿射变换；内点 法；整体收敛性；局部收敛速率 第1 页 英文摘要 a b s t r a c t o p t i m i z a t i o ni sa ni m p o r t a n tt o o li nd e c i s i o ns c i e n c ea n ds y s e ma n a l y s i s a n dc 珏b ew i d e l y u s e di nm a n yd o m a i n s i nt h i st h e s i s ，w ew o p o s ea na f f i n es c a l i n gs u b s p a c et r u s tr e g i o na p p r o a c h i na s s o c i a t i o nw i t hi n t e r i o rb a c k t r a c k i n gf i n es e a r c ht e c h n i q u ef o rn o n l i n e a ro p t i m i z a t i o ns u b j e c t t ol i n e a re q u a l i 竹a n di n e q u a l i t yc o n s t r a i n t s t r u s tr e g i o ns 廿a m g yi saw e l l a c c e p t e dm e t h o di nt h en o n l i n e a rp r o g r a m m i n gt oa s s u r e g l o b a lc o n v e r g e n c e t h ei d e ab e h i n dat r o tr e g i o nm e t h o df o ru n c o n s t r a i n e dm i n i m i z a t i o ni s i n t n i t i v ea n ds i m p l e b u tf o rc o n s t r a i n e dm i n i m i z a t i o n ，c o n s t r a i n t sw i l lm a k ei td i f f i c u l tt of o r m u - i n mas i m i l a rs u b p r o b l e m r e c e n t l y , c o l e m a na n dl ip r e s e n tat x u t s tr e g i o na f f i n es c a l i n gi n t e r i o r p o i n ta l g o r i t h mf o rt h em i n i m i z a t i o np r o b l e ms u b j e c to n l yt ol i n e a ri n e q u a l i t yc o n s t r a i n t s b y u s i n ga f f i n es c a l i n gt of o r m u l a ma na p p r o p r i a t eq u a d r a t i cf u n c t i o na n d t r u s tr e g i o ns u b p r o b l e m ， d i f f i c u l t i e si m p o s e db yc o n s t r a i n t sa r eo v e r c o m e a n df u r t h e r m o r e t h ea u t h o r sa n a l ) 7 z e da n d p r o v e d c o n v e r g e n c e p r o p e r t i e s o f t h e p r o p o s e d m e t h o d ，b u t i n t h a t a r t i c l e ，t h e a u t h o r s d i d n t g i v e a n ym a t e r i a lm e t h o dt os o l v et h es u b p r o b l e m i nf a c t , i ti so b v i o u st h et r u s tr e g i o ns u b p m b l e m w i t hs t r i c t l yf e a s i b l ec o n s t r a i n bn e e d st ob er e s o l v e dm a n yt i m e sb e f o r eo b t a i n i n ga l la c c e p t a b l e s t r i c ti n t e r i o rf e a s i b l es t e p ，a n dh e n c et h et o t a lc o m p u t a t i o nf o r c o m p l e t i n go n ei t e r a t i o nm i g h tb e e x p e n s i v ea n dd i f f i c u l li no r d e rt oo v e t c o m ea s e r i e so fd i f f i c u l t i e sb r o u g h tb ys o l v i n gt h et m s t r e g i o ns u b p r o b l e m , w em a yr e s o r tt ou s es u b s p a c em e t h o d ，l r a s tr e g i o na l g o r i t h ma n di n t e r i o r b a c k - t r a c k i n gl i n es e a r c ht e c h n i q u et os e a r c hf o ra c c e p t a b l es t r i c ti n t e r i o rf e a s i b l es t e p s d u et o t h es p e c i a ls u u c t t t r e so ft h es u b s p a c et e c h n o l o g y , t h em e t h o dc a nb ea p p l i e dt os o l v ev e r yl a r g e s c a l ep r o b l e m s i nt h i sp a p e r , w ef i r s t l yr e v i e ws o m er e l a t i v ec o n c e p t s ，t h e o r i e sa n dt e c h n i q u e sa st h eb a - s i ck n o w l e d g ef b rf u i t l l e fs t u d y , t h e ni n t r o d u c ear e l e v a n ta f r i n es c a l i n gm a t r i x ，a n df o r m u l a t ea n a p p r o 脚q u a d r a t i cf u n c t i o na n da l n l s tr e g i o ns u b p r o b l e n xu p o nu b es u b s p a c et e c h a i q u e w e s o l v e t h e t r u s t r e g i o n s u b p r o b l e m i n t h e p r o p o s c c i s u b s p a c e t o o b t a i n t r i a l s t e p s f u r t h e r , c o m - b i n et h ei n t e r i o rb a c k - t r a c k i n gl i n es e a r c hs t r a t e g yt of i n a l l yg e ta na c c e p t a b l es t e pl e n g t hw h i c h i ss t r i c t l yf e a s i b l ea n dm a k e st h eo b j e c t i v ef o l l c t i o nm o n o t o n i c a l l yd e c r e a s e f o l l o wt h a t , b a s e d g o o dp f 叩酬髂o ft h es u b s p a c em e t h o d , w e a kg i o b a ! c o n v e c g a n c ea n ds t r o n gg l o b a lc o t g a - g e n c ea n dl o c a lc o n v e r g e n c er a t eo ft h ep r o p o s e dm e t h o da i 宅e s t a b u s h e du n d e rs o l r i er e a s o n a b l e c o n d i t i o n s n u m e r i c a lr e s o l si n d i c a t et h a tt h ea l g o r i t h mi su s e f u la n de f f e c t i v ei np r a c t i c e ， k e yw o r d s ： n o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n ；i n e q u a l i t yc o n s t r a i n t s ；t r a s tr e g i o nm e t h o d ； 第1 i 页 英文攮要 s u b s p a c em e t l l o d ；a l f l i n es c a l i n g ；i n t e r i o rp o i n tm e t i l o d ；g l o b a lc o n v e r g e n c e ；l o c a lc o n v e r g e n c e r a t e 第页 主要符号对照表 主要符号对照表 掰。” 0i i ，” | 1 i l ， | | k c ( z ) q i n t ( q ) v ，0 ) a 缸 己仕，) 1 ) 9 ( 。) = v ，扛) 一a a a 如 鼬，= 出 v 2 ，( ) 岗 靠维实向量空间 n m 维实矩阵 e u c l i d 范数 o o 一范数 p r o b e n i u s 一范数 竹维决策变量 向量z 的第j 个分量 目标函数的局部极小值点 目标函数 ，在当前迭代点z i 处的函数值 约束函数 可行集 严格可行集 ，在。处的梯度 l a g r a n g e 乘子 约束优化问题的ia g 髓n g e 函数 ，在z 处的投影梯度 ，在z 处的增广梯度 ，在处的h e s s e 阵 第k 次迭代步 讥( 以；五) 目标函数在孤处的局部二次近似 信赖域半径 c ( o ) = p 9 妒i ，0 ) ，( 跏) ) 水平集 翻线性约束优化问题的子空间 第页 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究 成果。论文中除了特别加以标注和致谢的地方外，不包含其他人 或机构已经发表或撰写过的研究成果其他同志对本研究的启发 和所做的贡献均已在论文中做了明确的声明并表示了谢意 作者签名：日期： 论文使用授权声明 本人完全了解上海师范大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其 它手段保存论文保密的论文在解密后遵守此规定。 作者签名：导师签名； 日期： 第一章最饶化同趣基本概念 第一章最优化问题基本概念 1 1 最优化问题简介 最优化理论与方法是一门应用相当广泛的学科，它讨论决策问题的最佳选择之特 性，构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际表现因为最优 化问题广泛应用于经济计划、工程设计、生产管理，交通运输，国防等重要领域，已受 到政府部门的高度重视。伴随着电子计算机的普及和优化计算方法的迅速发展，规模越 来越大的优化问题得到解决通常，为应用最优化技术确定最优方案，需要针对具体的 实际问题建立相应的最优化模型，再根据模型的具体形式和特征选择适当的最优化方法 求解。 最优化问题的数学模型通常写为： m i n ，( s t c ( 扛) = 0 ，i = 1 ，2 ，巩 ( 1 1 1 ) c i ( ) 0 ，t = k 十l ，m 其中。一p l ，现，) r 舻为决策变量，( ：舻耕为目标函数，c c ( z ) ： 舻一跪1 0 = 1 ，2 ，m ) 为约束向量函数。m m 。是两个非负整数如果约束条 件m = m 。= 0 ，则称优化目题( 1 1 1 ) 为无约束最优化问题。为方便数值计算，这里我们定 义的且标函致，0 ) 与约柬函数q 扛) ， = 1 ，2 ，m ，均为实值连续可微函数 为便于下文叙述，定义 = 0 l i = 1 ，2 ，仉k 工= a i l = m + 1 ，m 集合 q 些 互i q ( = o ，i ；c i ( z ) o i z 1 1 2 ) 称为问题( 1 i i ) 的可行域迸一步集合 m r ( n ) 磐 2 lc i ( 互) = 0 ，l ；c i ( 霉) o d ( 1 1 3 ) 称为问题( 1 ，1 1 ) 的严格内点可行域 一般情况下，可借助于在z 处的目标函数和约束函数信息获得一阶必要性条件和二阶 必要性条件，至于充分必要性条件只对一些特殊的最优化问题存在，最优化条件不仅对 最优化理论的研究具有重要意义。两且对最优化算法的设计和终止条件的确定起着重要 的作用。 第l 页 1 2 最优化方法的结构 1 2 最优化方法的结构 最优化方法通常采用迭代方法求它的最优解，其基本思想是：给定一个初始点跏 g p ，按照某一迭代规则产生一个点列 z ) ，使得当 取) 是有穷点列时，其最后一个点是 最优化模型问题的最优解，当 瓢) 是无穷点列时，它有极限点，且其极限点是最优化问 题的最优解 设 z 为第k 次迭代点，氏为第k 次搜索方向，讯为第k 次步长因子，则第k 次迭代格 式为： z k + 1 = 蕾k + o t k 氐( 1 2 1 ) 从这个迭代格式可以看出，不同的步长因子觎和不同的搜索方向以构成了不同的方法 一个好的算法应具备的典型特征是：迭代点茁k 能稳定地接近于局部极小值点z 。的邻 域，然后迅速收敛于z 当给定的某个收敛准则满足时，迭代即终止如果对任意的初 始点z o q ，由算法产生的点列都收敛于最优点z 。，则称该算法具有整体收敛性一个 算法是否可行，分析其是否具有整体收敛性，一般地，可以通过证明迭代点列 z k ，的聚 点( 即子序列的极限点) 为一局部极小值点。 速度是衡量一个算法有效性的重要方向如果点列 瓢 虽收敛到z 。，但收敛地太 慢，以至在允许的时间内不可能达到满意的迭代结果，则算法可能没有实际的应用价 值 最优化方法中，牛顿步和拟牛顿步都具有很好的局部超线性收敛速率牛顿法对非 二次函数不能保证整体收敛性。但当初始点靠近极小值点时，收敛速率一般是快的。 算法的另一个重要特征为终止迭代所需要的终止准则。最有用的也许是要求i i 瓤一 z 0 f 或i ，) 一，0 ) i e 其中参数e 由使用者提供。但由于上述准则需要预先知道解 的信息，因而是不实用的事实上，由于0 l 一巩是误差i j 巩一文0 的一个估计，因此 我们有时采用 或 0 i + 1 一巩0 f i ( z l k 一( 巩) d 日， ( 1 2 3 ) 其中( z ) t 表示向量观的第t 个分量另一个可以采用的终止准则是 f ( x k ) 一，( 。“1 ) 毛 值得注意的是，以上的终止准则并不是万能的在不同的最优化方法中往往采用不同的 终止准则，有时甚至是同时采用不同的终止准则。具体可以参考【”】等文献中有关最优 化方法的实际应用。 第2 页 第一童最侥化问题基本概念 1 3 两类常用的最优化的整体收敛性方法简介 从( 1 2 1 ) 式可以看出，不同的步长因子弧和不同的搜索方向缸将构成不同的迭代方 法其中。线搜索方法与信赖域策略是保证最优化方法总体收敛的两类技术。下面我们 分别作一下简单的介绍 1 3 1 线搜索方法 从当前迭代点瓢出发，设搜索方向矗已知且为下降方向，确定步长因子砚使 ，( “+ n 巩) o 为信赖域半 径，0 为某一范数，通常采用1 2 范数。 信赖域子问题的求解方法，一般情况下，当取正定且0 且1 v ( x h ) 0sa k 时，子 问题( 1 3 2 ) 的解可以简单地通过求解二次模型似p ) 在无信赖域约束下的最优解= 一p f l v ，( o i ) 得到，被称为牛顿( 或拟牛顿) 步。 n o c e d a l 和y u a n 在 1 7 0 提出了一种结合信赖域和线搜索的方法，这种方法被称为回 代( b a c k t r a c k i n g ) 法。它自然地利用了内计算出的试探步如，在乳方向上采用一维搜索 以使产生合理的下降量，这种方法每次迭代只需计算一次信赖域子问题 第3 页 1 4 信赖域予空婀算法简介 另外文献 8 - - 1 6 中给出了信赖域予问题的构造及求解方法，书 2 1 - 2 3 q a 相关章节也都 有该方法的具体说明。 1 4 信赖域子空间算法简介 在文献【2 _ 4 】中获得利用子空间技术近似求解信赖域子问题思想，且对反正定的情况 下说明的比较清晰。本文将以此为基础，进一步讨论反负定和不定的情况，并给出子空 间的具体形式和信赖域子空间算法的描述及必要的理论证明在子空间的构造上，将结 合梯度方向，牛顿步( 拟牛顿步) 方向及负曲率方向，信赖域子空问算法明显可降低原 问题的维数，进而一定程度上减轻了求解信赖域子问题的复杂性。另外子空间算法其实 质是折线法的延伸。 下文中将给出算法的具体描述及相关的证明过程，概述如下：第一章中已对一些相 关的基本概念、理论和方法进行简单的回顾第二章中，给出了子空间的具体形式，并 在子空间中求解信赖域的子问题；第三章中，结合回代步、内点仿射变换、信赖域子空 间策略与线搜索技术，描述了仿射内点信赖域子空间算法；第四章中，证明了在合理的 假设条件下算法具有弱整体收敛性；第五章中，结合合理的假设条件，进一步证明了算 法不仅具有强整体收敛性，而且具有超线性收敛速率；第六章中，通过具体的数值试验 结果，说明了该算法的实际可行性和有效性最后，第七章对本文工作进行总结，同时 提出进一步的研究方向。 第4 页 第二章线性约束问题的仿射内点信赖城子空闻劈法 第二章线性约束问题的仿射内点信赖域 子空间算法 2 1 引言 本文主要考虑求解带有线性等式和不等式约束的非线性优化问题： m i l l ，【z ) s t a 1 z = 6 1 ( 2 1 1 ) a 2 x 6 2 舯，滞一铲是连续可绷非线性醮，矩附d = d 蚓a l 舻”一卜 f d i ，d 2 ，m 】，妒。和蟹= 【m + 1 ，m + 2 ，a m j g p 。( ”一( m j ) ，向量6 d = d 【6 1 ，i , 扩1 ，护尸，p 文中可行解集记为qc l = e f z l a l x = b l ，a u x2 幻，并 假设不等式约束的严格内点可行集i a t ( q ) d = e f x l a l 。= b l ，a 2 x 6 2 非空 c o l e m a n ：和l i 在文【1 】中提出了双信赖域仿射变换内点法求解仅带有线性不等式约束的 最优化问题，即 m i n f ( x ) ( 2 1 2 ) s t a 2 2 26 2 。 该算法由( 2 1 2 ) 的一阶必要性条件得到牛顿步，并基于牛顿步建立其信赖域子问题。简述 如下：假设z 是当前的严格可行迭代内点，m 是问题( 2 1 2 ) 的l a g r a n g i a n 乘子的近似，仿 射变换矩阵仇和对角矩阵& 分别定义为： d 扛) 些d i a g a 2 z 一6 2 ) ，与d kd = t f d ( 砌 c 0 ) c = l e f ( 1 i a g l p i ) ，与仉d = dg ( ) ( 2 1 3 ) ( 2 1 4 ) 忽略原始与对偶可行性约束，问题( 2 - 1 2 ) 的一阶必要性条件可以表示为( m + n ) ( m + n ) 的 非线性方程组： d i n g a 2 $ 一6 2 ) p = 0 ，和v ，一a 弘= 0 记 ： 护”表示一个前价分量为z 舻，后祈分量为p 妒的列向量为获得整 体收敛性。c o l 锄姐和l i 用仉d = * qd i a g l 纵仔来代替d i a g 鲰，由上面的方程组得到修正牛 第5 页 2 2 信籁域子空闻问题的近似最优解 叫磊卜”，即 c 啾k a 2 警 爱 = 一 v 1仇i f 如il d i 胀 l ( 2 1 5 ) 可以证明修正牛顿步是渐进充分接近于精确牛顿步的，因此具有很快的收敛速率。 基于此修正牛顿步，c o l e m a n 和l i 在【l 】中证明它使得原始目标函数单调下降，并利用增广 二次型作为模型的目标函数，给出了下面的信赖域子问题： ( 2 1 6 ) 其中瓯= 仇或者鼠= 西k ，晚是文章i l 】中给出的另一仿射校正矩阵。瓯取d i 时可以 得到类似的结果，本文只考虑& = d h 时的情况。v = v ( x k ) ，d = z - - x k ，玩是v 2 氏或 其近似，v 露d + ；矿b d 是，在z 处的一个局部二次近似，a k 是信赖域半径。作变换蠢= d i 5 a 2 d ，信赖域的子问题( 2 1 6 ) 等价于下面这个原始变量空间中的问题： fr a i n 仇 旬d = e fv 班+ ；d r b k d + ；, f c , d c 氏) s ，t a 2 d = d 扫 i i i c d ；d ) 1 1 2 & 双信赖域仿射变换内点法保证了每次迭代即满足信赖域约束又满足内点可行性约 柬。c o l e m a n 和“在f 1 冲给出的充分下降条件保证了互补松弛性对偶可行性厦二阶必 要性条件的成立，并最终证明了信赖域仿射变换内点法的整体与局部收敛性最近，朱 德通在文【”】中提出了一个新的具有非单调内点回代技巧的仿射变换信赖域方法求解带有 线性等式与不等式约束的最优化问题，并证明了该算法的整体收敛性和局部超线性收敛 速率 由于上述问题的不等式约束使得保持内点可行有一定的困难，并且在计算每一步新 的迭代点时需要在扩展等式约束的零子空间中极小化一个具有仿射变换椭球约束的二次 函数，所以当零子空问的维数较大时，计算工作量比较大受到文【2 】，【3 】和【4 】中利用子空 间技巧近似求麓信赖域子问题思想启发，本文首先构建合适的二维子空间，在子空问中 求解得到模型的迭代方向，然后沿此方向通过线搜索获得步长因子，既能保证迭代点严 格可行，又能保证迭代点使目标函数单调下降子空间技术的应用使得我们的方法适用 于求解大规模的优化问题。基于信赖域子空间算法的良好性质，在合理的假设条件下， 证明了该算法不仅具有整体收敛性，而且保持局部超线性收敛速率。 2 2 信赖域子空间问题的近似最优解 本节中，考虑用具有非单调内点回代技巧的仿射变换信赖域子空间算法求解问 第6 页 如q 筇巧 扩乱篇叨懒 鲁蚍 第z - 章线性约柬问题的仿射内点信赖坡子空问算法 题( 2 1 1 ) 。这包括选取一个仿射变换矩阵玩和一个二次模型函数极( d ；两以及一个二维子 空间, 5 p k 。通过检验( 2 1 1 ) 的一阶必要性条件，可选取仿射变换矩阵。 问题( 2 1 1 ) 的一阶必要性条件很容易建立对于可行点氟q ，问题( 2 1 1 ) 的一阶必 要性条件为存在乘子向量儿掰和0 地3 p 一，使得 d i a g a 2 x 一6 2 ) j k = 0 ，和v ( x ) 一a r a 一a d , 。= 0 ( 2 2 1 ) 成立，称z 。为( 2 1 1 ) 的一个稳定点进一步，此时若对任意的i = 1 ，2 ，f ，都有l 定i 0 。并且不等式啄 矗一钾 o 与i 应l o g = l ，2 ，价一f ) 中至少有一个不等式成立。 即l 麓i 0 ，i = 1 ，2 ，m l 且i 吸f 矗一护旬l + l 厦i o ，j = 1 ，2 ，m z ，则称在z 。处 严格互补性条件成立，其中砖表示k 的第i 个分量，疋，扩钾表示m ，b 的第j 个分量。 忽略不等式约束的原始与对偶可行性，( 2 1 1 ) 的一阶必要性条件可以表示为下面 的( m + n ) + n ) 的非线性方程组： f 瓢1 梯陟龇艘帆蚣旆躺物步引敝 e v 2 f ( x k 如) 一嘲0 褂a a k 一隅- a t a 二k - 玩钒 一捌 其中d t 磐d i a g a 2 一b 当远离解的时候，牛顿步。女不一定就是，( z ) 的一个下降方 向。为获得整体收敛性，我们采取【l 】中的建议，用qd = e fd i a g l 绺i 来代替d i a g 触) ，可 得下面的修正牛顿步方程，即 暖一旧阱一r a 豢t x - 嘞 一： 可以证明，修正牛顿步是渐进充分接近于精确牛顿步的，因此具有较快的收敛 速率。利用增广二次函数作为模型的目标函数，可得在a ，的零子空间中与修正牛顿 步喇相关的信赖域子问题如下： n f i nv 露d + ；取d + 以；巩_ 。t g 巩5 1 如d 8 t a l d = 0 ( 2 2 5 ) 1 忡；班a 2 d 1 1 2s 趣 第7 页 作变换c i = 口i o 如d t 可褥本文主要考虑的信赖域子目题： f m i no k ( d ；d ) = v 跖d + ；d r b k d + ；护q c ( t k ) r 倒a i d = d = 0c i i i i ( d ；a ) 1 1 2 s 乱 令l 塞i 为子问题( t t ) 的解，此时定义慨箩l 言c 三 kl ，则子问题( 凡) 的一阶必要性 lmii u l 条件为? 存在l a 舒a n 西飘乘子a + 1 和p m 以及靠b ，使莓 c 地州，阱一一i f h 一脚) ， ( 2 2 6 ) 叽c t 一0 【麦 0 。，= 。， c 2 2 力 “20 【z 2 却 其中ia g 跚g i 彻乘子a e + 1 和p 1 ，可利用最小二乘法求解，即 言丢凇州巩 磐例一阶一眦= 盎，卜删矩 阵匕叫0 1 卜锊蚋撇嬲曩则 一审舨；跏 ：( t l v a 一砰k ，一a 和+ 。l 暖+ l i 建p k + ，惦) ：o 蠡眩 2 2 i o ) 显然从( 2 2 1 0 ) 式可知，由既约值一v 露饥的下降量度量的讥池面的一个充分下降将 导致满足互补性条件： 溉l l v 矗一钟k + 1 一霹弘“1 8 2 = o ，和熙或胁1 l | 2 z o 髂2 i 1 ) 2 2 1负曲率方向的构造 类似于文献 2 8 ，2 9 1 中对对称矩阵晚的分解可知，存在单位正交矩阵q 和对角矩 阵札，使得反= q i a q ：，其中札的对角元素以s 醒s 榷构成风的n 个特征值， 第8 页 由于a 是对角矩阵，赦可以扩充单位正交矩阵仉和对角阵，使得慨：i 仇rl 必t j l 曼j = 三：= 黼= 衙= 特征值，且相应的n + m 个标准正交特征向量分别为鼠= l ：l ，露= i ：i ，口1 = ”= 虢m - c - m , 其鸭妒踊个禳龇其毓耥的靴向 假设矩阵 2 一是 是行满秩i 、的t j l = ， a + 那j , 么：- - 它i 的o 零空问g _ _ ( i 2 一麓 ) c 以下简记 值，程= m 定义 瓯磐一s g n ( 鳍程) 程 ( 2 2 1 2 ) 其中s 印晕符号函数，早由毕定义的矾满足霹 靠瓴= 嘏 0 ，以使0 缸+ e d l ls 忱对任意的成立，我们在下文中假设0 肘硼k 1 成立 第9 页 未笼竺篙三：巍毫嫉0 磊。二篓三篇篇圣 摹熟淼每t 显k 篙鼯关，诺鳓莽0 在 子空间中求解信赖域子问题( ) 所得到的解1 7i 必属于m ，即j r 、 llzl 2 2 3 子问题的近似最优解的确定 令砟表示由二维予空间s r 的标准i e 交基所张成的矩阵显然可得k 筑一+ 哪“，硭妖= 如。由于本文考虑在二维子空间中求解信赖域子问题( t k ) t 则必存 在弧删糠娟如g 满g l l c d e o 1 陬州i = 蚓| p 结厶子空问观可 得( n ) 的一阶必要性条件： 埒( 觚+ 仃k i ) k 弧= 一蹬弧 靠( 一0 弧0 2 ) = 0 ， o k 0 ( 2 2 1 3 ) ( 2 2 ，1 4 ) 下面分别考虑求解不同情况下子嘲n ，的近似最优解图辄鲫鲫乘为 方便起见，以下求解过程将统一省略下标七 1 当m 在 ，上是正定矩阵时，由子空同的定义可褥 由( 2 2 1 3 ) 式，可得 ( y 丁肘y + 叮，挎= 一y 勺 正交分解上式中的对称矩阵p m y ，可知存在单位正交矩阵u 和对角矩阵y ， 使y r m y ；( ，y 旷，其中砚2 也构成矿m l ，的两个特征值，正交矩阵u 的 列珏1 ，晚分别为相应的标准正交特征向量，因此问题( t k ) 的近似解为： f ；i = y g = - y v ( y + 盯如) 一1 r r y r # ：一晔 0 1y 旷噤y 地，叫。 十盯他十仃 且满足 5 2 ：1 例卜器+ 一1 1 0 1 1 2 一 叫s ， 第二章线性约束问题的仿射内点信赖域子空闻算法 由上式可知，如果口= 。且怕ns 成立，那么 ： = 一m - 1 参；否则必存在一 o 使l l y lj = 成立( 因为i 随口的增大而减小) ，即存在盯 o 以使 丽1 1 0 1 1 2 + 丽i i 。1 1 2 , 4 - = 2( 秽l + 口) 2 ( 也盯) 2 一 成立。将其展开、整理后可得一个关于盯的四次方程： a 4 0 4 + a 3 矿+ a 2 0 2 + a l 盯+ a o _ 0( 2 2 1 9 ) 其中 山= a 2 ，a 3 = 2 a 2 ( 地+ t j 2 ) ，a 2 = 2 【( 口1 + t 1 2 ) 2 + 2 ( v l 也) 】一2 1 1 蚕1 1 2 ， a l = 2 ( v l + 地) 【2 ( 1 也) 一l l 引1 2 】，a o = 2 ( 地也) 2 一f i i 1 1 2 f ( 铆+ t j 2 ) 2 2 v l t l 2 j 这里口l + 抛= t r ( y 7 m y ) ， 1 抛= i y 个艇y 1 结合c 2 2 - ，式和c 2 2 ，9 ) 式求解a 和 ： 2 当m 在 厂上是不定矩阵时， 若i i c m 。+ o o - 1 引i 成立，那么由子空间的定义得 y = 赢赢器耩器躲 ( z 2 2 0 ) 于是类似于1 中的求解过程可知，必存在口 口使i l u l i = 成立，再结合( 2 2 1 7 ) 式 和c 2 2 - 式求解盯和 习 若8 ( m + 口j ) - i 酬 o 使m l = 成立，再结合( 2 2 1 7 ) 式 和c z 2 t 叻式求解盯和 ： 注释3 ：为便于下文的证明，相对于上述情况2 中的“困难情况”，称其他情况为“一般 情况”。 第1 2 页 第三章算法 第三章算法弟二早畀) 玄 本章我们给出求解问题( 2 1 1 ) 的仿射内点信赖域子空圊算法。 初始步：选取参数口( 0 ， ) ，i ( 0 ，1 ) ，o 7 l 啦 1 ，0 饥 仇 l 0 ， 选取一个对称矩阵风，给定初始信赖域半径a o 和初始严格可行内点z o i n