（应用数学专业论文）一个新锥模型信赖域算法的研究.pdf

硕十论文一个新锥模型信赖域算法的研究 摘要 本文主要目的是对一类新锥模型信赖域算法进行研究，主要是对求解信赖域子问题 的方法做出了讨论和补充，给出了求解子问题的算法，并以此为基础建立了一个新锥模 型信赖域算法。最后对讨论和补充后的算法进行收敛性分析、编程和数值验证。 首先，本文介绍了q i nn i 提出的一个新锥模型信赖域算法建立的理论依据和思想实 质。这类算法实际上是根据信赖域球心分别到超平面厶= y ：1 一口7 y = 一氏 和 厶= y ：1 一，y = 岛 的距离是否大于当前的信赖域半径来确定锥模型的可行域。在讨论 和分析中发现，岛的不同选取会导致信赖域和超平面厶，厶的相对位置发生变化。进而 导致锥模型的可行域产生三种不同的选择，最终将信赖域子问题转化为三种不同的情 形。 其次，就本文提出的划分锥模型可行域的两种猜想进行了具体的研究和分析，给出 了求解信赖域子问题的新方法和新思路，给出了子问题的修正形式，并在求解子问题的 算法基础上建立了一类新锥模型信赖域算法，最后证明该算法是具有全局收敛性的。 最后部分进行算法编程和数值验证。结果表明本文提出的这类改进和拓展的新锥模 型信赖域算法是可行的并且是有效的。 关键词：锥模型，信赖域法，二次型，全局收敛性 a b s t r t a c t i nt h i sd i s s e r t a t i o n ，an e wt r u s t r e g i o na l g o r i t h mw i t hc o n i cm o d e li sr e s e a r c h e d ，a d i s c u s sa n ds u p p l e m e n to ft h en e wt r u s t - r e g i o na l g o r i t h mw i t ht h ee o n c im o d e li sp r o p o s e d ， p r i m a r i l ya b o ms o l v i n gt h et r u s t - r e g i o ns u b p r o b l e mw i t ht h ec o n i cm o d e l t h ec o n v e r g e n c e a n a l y s i sa n ds o m en u m e r i c a lr e s u l t sa r eg i v e n a tl a s tt oe n s u r et h ea l g o r i t h mi sf e a s i b l ea n d e 伍c i e n t f i r s t , an e wt r u s t r e g i o na l g o r i t h mw i t hc o n i cm o d e lw h i c hi sp r o p o s e db yq i nn ii s i i l 仃o d u c e d t h et h e o r e t i cf o u n d a t i o na n dt h es u b s t a n c ea r ep r e s e n t e da f t e r t h a t t h ea l g o r i t h m d e t e r m i n e st h ef e a s i b l er e g i o no ft h ec o n i cm o d e lb yc o m p a r i n gw h e a t h e rt h e d i s t a n c e b e t w e e nt h ec e n t r eo ft h et r s u t r e g i o na n dt h eh y p e r p l a n e 厶= y ：l 一口7y = 毛 a n d 厶= j ，：1 一a r y = e o i sm o r et h a nt h ec u r r e n tt r u s t - r e g i o nr a d i u s o rn o t t r o u g ht h ed i s c u s sa n dt h e a n a l y s i s ，w ec a nf i n dt h a tt h ed i f f e r e n ts e l e c to fc 0 c a nl e a dt ot h ec h a n g eo ft h er e l a t i v ep o s i t i o nb e t w e e n t h eh y p e r p l a n ea n dt h et r u s t - r e g i o n h e n c et h et r u s t - r e g i o ns u b p r o b l e mi s t r a n s l a t e di n t ot h r e ed i f f e r e n t s e c o n d l y ad e t a i l e ds t a t ea n da n a l y s i sa o b u tt h es e n c o do n eo ft h et h r e ec a s e sm e n t i o n e da b o v ei s p r e s e n t e df o l l o w i n g a n dt h en e wt h o u g h to fs o l v i n gt h et r u s t - r e g i o ns u b p r o b l e mw i t hc o n i cm o d e l i sg i v e n o u t t h en e wt r u s t - r e g i o na l g o r i t h mw i t hc o n i cm o d e lb a s e do nt h a ti sc o n s t r u c t e d ，t h ef e a s i b i l i t ya n dt h e c o n v e r g e n c e a r e p r o v e dr e s p e c t i v e l y t h ec o n v e r g e n t r e s l u t ss h o wt h a tt h ea l g o r i t h mh a sg l o b a l o d n v e 唱e n c e f i n a l l y , t h ea l g o r i t h mp r o g r a ma n dt h en u m e r i c a lt e s t a r ep e r f o r m e d t h er e s u l t si l l u s t r a t et h a tt h e n e wt r u s t - r e g i o na l o g r i t h mw i t hc o n i cm o d e li sf e a s i b l ea n de f f i c i e n t k e yw o r d ：c o n i cm o d e l ，t r u s t r e g i o nm e t h o d ，q u a d r a t i cm o d e l ，t h eg l o b a lc o n v e r g e n c e h 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 劢j p 年多月；日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 j 口年6 月) 日 硕 ：论文一个新锥模型信赖域算法的研究 l 绪论 1 1 引言 本文主要考虑的是无约束优化问题 m i n 厂( x ) 其中厂( x ) 是连续可微函数，x r ”。 信赖域方法是解无约束优化问题的一个很有效的方法。与线搜索方法相比，信赖域 方法有其独特的优势：即当目标函数的非线性程度较高时，增加信赖区域限制的信赖域 方法通常会得到比线搜索方法更好的迭代方向。这是因为在这个时候，信赖域外部的二 次模型对目标函数的逼近精度已经大大失真，故以它的全局最优解作为迭代方向往往已 不是目标函数的最佳下降方向。 1 9 7 0 年p o w e l l t l 4 】，【1 5 1 第一次提出了信赖域方法，并建立了算法的一个详细的求解框 架。他证明了信赖域算法具有一阶梯度的全局收敛性，并且具有很好的稳定性和收敛速 度。他提出的算法被称为经典信赖域方法。 一般的信赖域法是在信赖域中使用一个二次型去逼近目标函数，即 一 1 m i n 依( d ) = 或d + z ，、d 24 d ( 1 2 ) z s j i i d l l - 0 是信赖域半径。 1 9 8 0 年，d a v i d o n l 4 】提出了锥模型的概念，这种函数模型拥有足够多的自由度因此 能够结合足够丰富的函数值和梯度值的信息。锥模型是二次模型的推广，因此，它比二 次模型更普遍，期望能够更充分地逼近原函数。对于一些在极小点附近很不对称，或曲 率变化剧烈的函数，或在某个区域内变化较大的函数，全部或部分用锥模型去逼近的效 果可能好于用二次模型去逼近。运用这种锥模型的新算法也被称作锥模型算法。在同一 年，s o r e n s e n l 2 1 1 建立了锥模型共线调比方法的详细内容，并且证明了他所提出的方法在 一种特殊情形下拥有q 阶超线性收敛性。a r i y a w a n s a 和l a u 【2 】提出了布鲁丹族共线调比 算法并且得到了超线性收敛性的结果。在这些方法中，他们都使用线性搜索来一步一步 前进。s h e n g l l 9 】进一步研究了锥模型方法的插值性质。 一个典型的锥模型函数可以写成下面的形式： l 绪论 硕士论文 嘶m + 高t 尚 4 ) 其中( s ) 是对f ( x k + s ) 一( 投) 的逼近，4 r “”是厂( 力在吒点的f f e s s i a n 矩阵的逼 近，= g ( 吒) = 夥( ) r ”，a t er ”是一个满足1 一口7 s o 的水平向量，ser ”。注意 到当口= o 时，依( s ) 就是一个二次型函数。 1 9 9 6 年，s i m o nd i 和w e n y us u n 5 1 提出了求解无约束优化问题的锥模型信赖域方法， 其d e 的信赖域子问题如下所示： 幽) = 丧t 尚 她 i i 协忙赴 其d ed 是一个调比矩阵，色是信赖域半径。 w e n y us u n , j i n y u ny u a n 矛iy a - x i a n gy u a n 2 3 1 在19 9 6 年提出了解决线性有约束优化问 题的锥模型信赖域法。记要解决的线性有约束优化问题为 础，( 川。 ( 1 5 ) 【s j a 。x 2 b 假设当前迭代点黾是可行的，也就是说么7 1 坼= 6 。如果我们令x = 砟+ s ，那么约束条件 就等价于a r s = 0 ，那么式( 1 5 ) 就可以转化为 = 矶矧弛 6 ， 使用零空间技巧，我们可知线性有约束形式下的锥模型信赖域子问题( 1 6 ) 可以转化成 一个无约束形式下的二次型信赖域子问题 m i n 鼓z + 妥z t 螽k z g j k z + ：b k z 眈五i ， 其中磊，豆，五。，z 等变量的定义可以参考文献 2 3 】。最后，他们给出了算法的全局收敛性。 q h an i l 9 1 在2 0 0 5 年提出了一个新锥模型信赖域算法。对于一般锥模型，缈( s ) 的可行 域定义为 s r ”，l 一口7 s 0 或者 s 掣，l a r s 0 。这样的话可能会导致锥模型信赖域 子问题在这些可行域上并没有一个有限解，因为缈( s ) 在b = s r ”。1s l l a 和上述的可 行域上可能是无界的。为了避免这种情况，0 i nn i 定义了缈( s ) 的一个新的可行域 s = se 雎1 1 - - a r s l ， ( 1 7 ) 其中氏( o ，1 1 。因此，将这个新的可行域与传统的锥模型信赖域子问题结合起来，可以 2 硕上论文一个新锥模型信赖域算法的研究 得到一个新的锥模型信赖域子问题 豳缈( s ) ， s 六s q ， ( 1 8 ) ( 1 9 ) 其中q = b n s 。因为伊( s ) 在q 上是有界的，所以式( 1 8 ) 一( 1 9 ) 的解是存在的。 令 s = s r ”，口r s 1 8 0 ，岛= s r ”，口7 s 1 + ， ( 1 1 0 ) 那么q = ( b n s ) u ( s n s , ) ，i e i _ q 有下面三种不同的表示： f b f l - 占o - a l i b i i q = b n s , f l l - a i i d l e o ， ( 1 1 1 ) 【( s n s , ) u ( s n s ：) c aa i i 1 + 氏 分别对应锥模型信赖域子问题的三种不同的形式。接下来，q i n n i 还分别就这三种信赖 域子问题分别给出了它们的最优化性质。 q i nn i 和h a i p i n gw u 2 6 1 在2 0 0 8 年给出了具体求解这三种锥模型信赖域子问题的方 法。首先，他们讨论了子问题的修正，指出了子问题的修正动机和合理性，将文献 9 】 中给出的三个锥模型信赖域子问题p 1 ，p 2 ，p 3 分别转化为三个二次模型信赖域子问题，并 提出了一个新锥模型信赖域算法。最后，他们给出了算法的全局收敛性证明。 1 2 本文的主要内容 本文的主要内容是提出求解锥模型信赖域子问题的新思路，并给出一类新锥模型信 赖域算法的改进。本文主要是在q i nn i 9 提出的新锥模型信赖域算法的基础上进行改进 和拓展，将岛( o ，1 ) 的情形延伸到6 0 ( 1 ，2 ) 和e o = 1 的情形上去，使得这类新锥模型信 赖域算法的应用范围更为广阔。本文首先分析了q i nn i 给出的新锥模型信赖域算法的思 想实质和理论基础，接着给出了本文作者提出的新的想法，并就该思路进行了可行性分 析和证明，给出了修正动机和证明，并就最优化性质进行了讨论，证明了该算法的全局 收敛性。最后对本文提出的新锥模型信赖域算法进行数值验证，说明了算法的可行性和 有效性。 2 准备工作硕上论文 2 准备工作 首先我们将先为我们后面所要进行的算法的改进做一些所必须的准各工作，包括锥 模型信赖域法的背景介绍，原算法的理解和分析，算法改进的猜测和理论依据以及一些 必要的引理和定理等等。 2 1 锥模型信赖域法的背景介绍 信赖域法是求解无约束优化问题时很有效很强大的方法。最初的信赖域法是基于在 信赖域中用一个二次型函数来逼近目标函数。这是因为二次函数模型很容易求解，而且 一般的二次函数的轨迹都可以逼近一族在最小值点x 附近的同心圆。然而，如果目标函 数具有很强的非二次性态或者它的曲率变化得非常剧烈，二次模型法对函数最小值的预 测则通常产生一个不好的结果。除此之外，二次模型并没有充分考虑到之前迭代步骤中 所产生的对算法有用的函数值和梯度值的信息。因此，在迭代过程中混合了更多插值信 息并且改进了优化算法性态的非二次模型就此建立了。 锥模型法最早可以追溯到d a v i d o n 4 】于1 9 8 0 年提出的锥函数概念。之后的 s o r e n s e n f 2 1 1 、a r i y a w a n s a l l l 、s h e n g 1 9 】等人均对锥模型法做出了发展和贡献。至此，锥模 型已经得到较为广泛的认可，在各个领域也得到较为广泛的应用。 锥模型法是二次型法的推广，拥有很多优点。第一，如果目标函数具有强非二次性 态或者它的曲率变化得很剧烈，那么二次型法经常会产生一个对于目标函数最小值的不 好的估计。而在这种情况下，锥模型则能比二次型更好地逼近目标函数，因为它具有更 多的自由度；第二，二次型并没有考虑到在之前迭代过程中产生的对于算法很有用的与 函数值和梯度值密切相关的信息。然而，锥模型拥有更丰富的插值信息，并且满足一定 的插值条件，使用这些丰富的插值信息可能提高算法的效果；第三，锥模型法拥有与二 次型法基本类似的全局和局部收敛性。 因此，将信赖域法与锥模型法结合起来得到锥模型信赖域法可以弥补传统意义上的 二次型信赖域法的很多不足，使得信赖域算法的效果更为理想和精确。 s i m o nd i 和w e n y us u n 5 】于1 9 9 6 年提出了一种求解无约束优化问题的锥模型信赖域 法，证明了算法的全局收敛性和超线性收敛性。w e n y us u n ，j i n y u ny u a n 和y a - x i a n g y u a n t 冽在1 9 9 6 年提出了解决线性有约束优化问题的锥模型信赖域法，给出了算法的全 局收敛性。 q i n n i 9 1 于2 0 0 5 年提出了一个新锥模型信赖域法。为了克服锥函数可能出现的无界 性，在算法中，他建立了锥模型的一个新的可行域s = s 尺”，l l 一口7 s l ，并将在此 ， 基础上建立的新的锥模型信赖域子问题转化为 4 硕1 ：论文一个新锥模型信赖域算法的研究 眺出，毪+ 尚， s s q ， 其中n = b n s ，b = 5 r ”：i l sl - - 1 1 4 l 时，子问题( 2 1 ) 一( 2 4 ) 转化为 f m i n 妒( j ) l - 旺 ( 2 ) 当i l 一| l 口 岛时，子问题( 2 1 ) 一( 2 2 ) 转化为 ( 2 1 ) ( 2 2 ) 我们可以将子 ( p 1 ) = 忙忙筌s z + o 时，子问题( 2 1 ) 一( 2 2 ) 转化为 絮t s l ，口。 l + e o 。 ( p 3 ) l s i ，口7 j 7 s 。、1 。7 当给出任意一个锥模型信赖域子问题时，它可以随着a 和a 的不同从而转变成( p 1 ) ， ( p 2 ) ，( p 3 ) 中的一个。这样，我们在后面的求解过程中就可以有分别的对待。 q i n n i 和h a i p i n gw u 2 6 】随后给出了将锥模型信赖域子问题( p 1 ) 一( p 3 ) 转化成 二次型信赖域子问题的修正动机和合理性，并且给出了三个修正子问题的求解方法和相 应的锥模型信赖域算法。最后证明了该算法的全局收敛性。 2 2 提出算法改进的猜测 0 i nn i 在文献 9 和文献 2 6 中提出了一个新锥模型信赖域算法。他提出了一个锥 模型的新的可行域，记为s = s 尺”，1 1 一口r j l ，其中( o ，1 ) 。 我们接下来从空间几何的思维角度来具体分析这个新锥模型信赖域算法的实质。我 们来考虑上面所描述的信赖域子问题( p 1 ) 一( p 3 ) 。对于超平面厶= y ：l 一口7 y = 和 厶= y l - a 7 y = 一毛 ，经过简单的计算可知信赖域球心到厶和厶的距离分别是 1_ = 孚和乞= 苦孚。当岛( o ，1 ) 时，超平面厶，厶和信赖域在空间中的相对位置是 孵00 厶，厶! 均位于信赖域的同侧，且信赖域球心到厶的距离比厶要大。再结合( 1 1 0 ) 中可 行域s t 和墨的定义可知，信赖域的半径在变化过程中可能会导致信赖域与超平面厶，厶1 5 2 准备t 作硕j ：论文 产生三种相对情况： ( 1 ) 信赖域球心到厶的距离大于等于信赖域半径，巳pt a “v a ，也就是说l 一岛a i i a i | 。 这时信赖域球心到厶的距离显然是大于信赖域半径的。此时snb = b ，sn 口= a ， q = ( sns ) u ( s 2nb ) = b ，也就是说a ，即对应着子问题( p 1 ) 的情形； ( 2 ) 信赖域球心到厶的距离小于信赖域半径，到厶的距离大于信赖域半径。也就是说 莆 首即川 s o ( 2 3 ) 其中( 1 ，2 ) 。 同时相应的锥模型信赖域子问题可以写成如下的形式 硕上论文一个新锥模型信赖域算法的研究 其中 肌n 伊( 5 ) s t s g q + ( 2 4 ) ( 2 5 ) ( 2 6 ) 【2 = b n s ，b = s e r ”：l l s l l - 0 ，那么则有 q = 。b n 茹吾函n 是， 矿氏- i | i 口| | ， 矿岛- i - e o + 1 证明：经过简单的计算我们可知，信赖域球心到超平面厶= y ：l - a 7 y = s o 的距离 为寄，至超平面岛2y 1 - a r y = - g o 的距离为苷。由【9 】中弓i 理2 1 的证明过程 和此处对岛的定义即可得证。 利用之前对于岛( 0 , 1 ) 时的分析我们可知： ( 1 ) 当信赖域的球心到超平面厶= y l - a 7 y = 岛) 的距离大于等于信赖域半径时，显然 到岛2y 1 - a r y = - g o 的躏也大于信赖域半径。也即是说可o p 0 - 1 ，即岛一1 怵i i 此时snb = 囝，n 召= a ，那么q = ( snb ) u ( 是nb ) = a ； ( 2 ) 当信赖域的球心到超平面厶的距离小于信赖域半径，到岛的距离大于信赖域半径 时，有寄 - - a l l a i i 时，选取( o ，1 ) i 吏得1 - r o 岛一l al a i ，这时子问题( 2 4 ) 一 ( 2 5 ) 可采用子问题( p 1 ) 的解法，我们将这个子问题记为e ； ( 2 ) 当s o - 1 a l l a l i 氏+ 1 时，子问题( 2 4 ) 一( 2 5 ) 可转化为 我们将这个子问题记为b 。 m l n 驴( s ) ， 豇 0 s l _ 0 。 证明：考虑下面这个二次函数 g ( s ) = ( 1 - a t s ) 2 ( 缈( s ) 一缈( ) ) ( 2 1 1 ) 由式( 2 6 ) ，式( 2 1 0 ) ，经过计算，我们可以得到 g ( s ) = ( 1 - a r s ) 9 7 s + 丢s 7 彳s 一缈( & ) ( 1 - a r s ) 2 ：1 s r s + 季7 s 一伊( 最) ， ( 2 1 2 ) 其中 季= g + 2 缈( ) 口，j = v 2 9 ( s ) = 彳一g 口7 一昭r - 2 ( o ( s , ) a a ， ( 2 1 3 ) 由式( 2 9 ) 和式( 2 1 0 ) ，我们有 v q ( s 。) = 五& + 季 = ( 彳一g 口r 一昭7 ) - 2 6 p ( s ) a r s a + g + 2 q g ( s ) a = - g 7 s , a + 2 a p ( s , ) ( 1 - a 气) 口= o 9 2 准备工作 硕1 ：论文 和 其中 j ：与4 9 ， 谨 ( 2 1 4 ) 9 = u ，+ 文口7 ，u = 1 一a 丁文 ( 2 1 5 ) 因此， g ( s ) ：g ( ) + v g ( & ) ( s 一& ) + i i ( s 一& ) 7 匀( s 一鼠) ：昙( s 一文) r 彳( s 一& ) ， 这告诉我们 伊( s ) 一伊( & ) 2 三石二笔t 了s 一鼠) r 彳( s 一& ) 。 ( 2 1 6 ) 因为l a 7 墨0 ，我f i j , - - i 知q 是非奇异的。因此由式( 2 1 4 ) 和式( 2 1 6 ) 即可得证。 接下来，我们将介绍一个关于二次型信赖域子问题的非常有名的结论，g a y l 6 1 和 s o r e n s c n 2 0 l 都分别对这个结论作出过证明。 定理2 4 一个向量s 是优化问题 m i n ，s + l s t h s( 2 1 7 ) 2 s t s b( 2 1 8 ) 的解，当且仅当存在着允0 使得h + 见，是半正定的， ( 日+ 元，) & - - - - c ，a ( i i s , i i - a ) = o ，牲i i _ o ，a e r ”，且满足1 一氏i l 以| l o 那么则有矗是日的 解当且仅当存在0 使得 ( 4 - g a r + 力，) = - g + 2 2 口 ( 3 1 ) 旯+ ( 0 8 一) = o ，0 s i l ( 3 2 ) f 1 ：f i a + , t i - a 2 a a7 ) 是半正定的。如果彳+ i - a 2 a a r ) 是正定的，那么& 就是日的唯 一解。 证明：令& 是子问题只的全局解。我们定义一个二次型信赖域子问题如下 m l n g ( s ) = ( 1 一口7 s ) 2 ( 缈( s ) 一缈( ) ) 妣 a ( 3 3 ) ( 3 4 ) 很容易发现& 也同样是子问题( 3 3 ) 一( 3 4 ) 的一个全局解。假设j 是子问题( 3 3 ) 一( 3 4 ) 的另一个全局解，那么则有g ( j ) = g ( & ) = 0 ，且有 口r ；i i 口l i l 一，且 l l - a 7 ；岛 又岛( o ，1 ) ，可知妒( ；) 一缈( ) = 0 ，也就是说j 同样是子问题名的一个全局解。这就说 明了& 是子问题日的一个全局解当且仅当& 是子问题( 3 3 ) 一( 3 4 ) 的一个全局解。 将定理2 4 应用到子问题( 3 3 ) 一( 3 4 ) 上，我们可以得到品是子问题日的一个全 局解当且仅当存在r 0 使得j + j 是半正定的，并且 3 锥模型信赖域了问题的最优化性质硕 ：论文 其中 ( j + 力，) = 一季， 旯( i s , l i - a ) - - o ， ( 3 5 ) ( 3 6 ) 雪= g + 2 缈( ) 口，j = v 2 9 ( s ) = 彳一g a 7 - a g r - 2 q ，( s , ) a a 7 。 ( 3 7 ) 如果j + r ，是正定的，那么& 就是子问题置的唯一全局解。 由式( 3 5 ) 我们可得 ( 4 一矿+ r j ) & = 一g + ( - 2 妒( & ) v + 9 7 瓯) 口 其中v = 1 一，& 。在上式左右两端各乘以彭，我们可得 ( - 2 q g ( s , ) v , + g r s , ) 口= 彭彳+ s r s , + v 9 7 & 由缈( s ) 的定义，我们有 2 v , 2 q ( s , ) = 2 v , g r + s t , a s 将式( 3 9 ) 和式( 3 1 0 ) 结合起来，我们可以得到 一2 缈( s ) u + g 7 & = 兄a 2 ， 由式( 3 8 ) 和上式，我们可以推出 记 ( a - g a 7 + 旯，) & = - g + 2 2 口 2 = a + a i - a 2 a a 7 1 ，9 = u ，+ 册r 那么由谚口= 口可以得到 1 2 吉谚彳9 ：吉( 么q + 记，+ 旯+ u ( 口7 + 耐) ) k、 、 叫 专一+ 彭彳最绷r “记，+ u ( ( 彳& “& ) a t + a ( 彳“文) 7 ) ) “门+ 警绷r + 击( ( w “如) 口- v , g + 2 * a 2 a ) 7 ) = 彳+ 五，一朋r 一昭7 + ( 兰三半 鲫r ( 3 。8 ) ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) ( 3 1 2 ) ( 3 1 3 ) 硕_ ：论文一个新锥模型信赖域算法的研究 = a + 尤i g a t - a g t - 2 q ，( s , ) a a t ：j + 名i( 3 1 4 ) 因为q 是非奇异的，因此彳是半正定的( 正定的) 当且仅当j + ，是半正定的( 正定 的) 。因此，由式( 3 6 ) ，式( 3 1 2 ) 和式( 3 1 4 ) 即可得证。 3 2 信赖域子问题只的最优化条件 接下来我们讨论子问题最的充分和必要条件。 定理3 2 假设岛- 1 i | 口l i 岛+ 1 。如果& 是子问题昱的解，那么存在、正o 使 得 ( a - g a 7 + ，) & = - g 一庇， ( 3 1 5 ) o ，1 2 t & = 1 - o 。如 3 锥模型信赖域了问题的最优化性质 硕士论文 果v 刁( & ) 和耻 ) 是线性相关的，那么就有l 口7 文i _ 忙u u u = u 口i i a e o - 1 ，与a r 瓯= 1 一岛 矛盾。因此，v 刁( ) 和耻( ) 是线性无关的。 其中 因此，e hk k t 一阶最优化必要条件可知存在彳，正o 使得 v q ( & ) + 正& + 正口= o ， 砌最1 1 2 - 2 ) = 0 ，( 口气一1 + ) = 0 ， ( 3 2 0 ) ( 3 2 1 ) v g ( & ) = 彳+ 季，季= g + 2 缈( & ) 口，7 4 = a - g a r - a g r 一2 a p ( s , ) a a r ( 3 2 2 ) 由式( 3 2 0 ) 可知 ( a - g a r + 彳，) 文= 一g + ( 一2 妒( 文) u + g7 一正) 口 ( 3 2 3 ) 在上式左右两端各乘以0 ，我们可以得到 k - 2 c p ( s ) v , + g ts 。一墨、羹n = 羹a s + 墨史s + v 季s 由式( 3 1 0 ) ，式( 3 2 3 ) 和式( 3 2 4 ) 我们有 和 - 2 r p ( s ) v , + g7 文= 彳2 + 正0 口 ( 么一g 口7 + 石，) 矗= - g + ( z a 2 一正氏) 口 ( 3 2 4 ) ( 3 2 5 ) = - g - 2 a ( 3 2 6 ) 因此，式( 3 1 5 ) 和式( 3 1 6 ) 可由式( 3 2 1 ) 和式( 3 2 6 ) 得到。 如果我们记 三( s ，彳，z ) = g ( s ) + 0 刁( s ) + 正( j ) ， 那么由式( 3 2 0 ) ，式( 3 2 2 ) 和q , t a = 口我们可以得到 因此我们有 1 4 v l ( s ，石，l j ) = v q ( s 。) + 公文+ 正d = o ， v 2 l ( s , ，彳，正) = v 2 q ( s ) + r ? i = f 4 + g i ( 3 2 7 ) = 彳一g a r - a g r - 2 o ( s , ) a a 7 + 彳， ( 3 2 8 ) 硕十论文 一个新锥模型信赖域算法的研究 吉谚五9 = 吉( 彳q + 彳谚，+ c o a a7 + 彳u ( 口r + 耐) ) = 吉( 记彳+ a s a a t + & v 2 i + , 砭* c o a a 7 + u ( ( 彳& + 彳a r + a ( a s + 彳) 7 1 ) = 彳+ 彳，+ 学船，一击( ( u g + 庇) 口r + 口( u g + 庇) 7 ) = 彳+ 彳，一弘，一昭，+ ( 兰主l 学 口口r 靠机( 叠幽半卜 ：五十彳，+ 尘鍪一丝册r 】；u = v 2 ( 只，正) 一三z 伽r 。 ( 3 2 9 ) 、 7 为了证明上式的非负性，我们需要考虑下面三种情况。 ( 1 ) 假设口r 文 l 一岛。那么则有正= o ，且& 是子问题( 3 3 ) 一( 3 4 ) 的解。通过与 定理3 1 证明过程的一个类似的推导，又由式( 3 1 7 ) ，我们可以知道 i i 够t 彳 9 = 吉谚( 彳+ 彳( ，一2 口口r ) ) 9 皎v ： 。、 j 一 是半正定的。因此d7 谚jq d o 对于所有满足d r 口：o 的d 成立。 ( 2 ) 假设l 0 a 且a 7 ：i 一岛。那么则有彳：0 ，且岛是 m l n q ( s ) s ，( s ) = 口r s - l + s o = o 的局部极小值点。 根据等式约束优化问题的二阶必要条件，我们可以得到d 7 v 2 三( 民，0 ，z ) d o 对于所 有满足d 0 = 0 的j 都是成立的。因此由式( 3 2 9 ) 我们有 1 5 3 锥模型信赖域了问题的最优化性质硕士论文 谚五9 d = 记d r v 2 l ( 文，。，正) d 一记正三t o ( 口7 d ) 2 。 对于所有满足d 7 a = 0 的d 都是成立的。 ( 3 ) 假设性0 = a r a7 = l 一岛。根据等式约束优化问题的二阶必要条件，我们有 d 7 v 2 三( ，彳，正) d o 对于所有满足d r a = o ，d r & = 0 的d r ”都成立。因此 d r 谚五9 d = v ；d 7 v 2 三( 岛，彳，正) d v 正( 口r d ) 2 d 0 = 记d 7 v 2 ( & ，彳，z ) d o 对于所有满足d 7 a = 0 ，d 7 文= 0 的d r ”都成立。 对于北斛忙叫b o 的情况，捌门批一静。那么则有 r ( s + t a r ) = 0 ，( + 耐) = ( & + 掰) 7 口一l + t o = o 且有 o q ( s 。+ t d ) - q ( s 。) = 三( 鼠+ t a r ，彳，) 一三( 文，石，正) ：，v ( ，彳，正) 7 d + i 1f 2 d r v ：l ( ，并，疋) d = 丢力v ( ，彳，) d 因此， d r 谚五9 d = 谚d 7 v 2 三( s ，彳，正) d v 2 。, 1 。、a r d ) 2 o 0 0 对于所有满足d r a = 0 ，d 7 矗0 的d r ”都成立。 定理3 3a r 脓”是对称矩阵，侣判2t o - 1 a la l i t o + l 。如果存在彳，正o ，& r ” 使得 ( 彳一朋7 + 彳) & = 一g 一厄， ( 3 3 0 ) 硕 ：i k 文一个新锥模型信赖域算法的研究 g ( i i * i i - a ) = 0 ，正( 口7 s o - 1 + s o ) = 0 ，口7 c o ，都成立。因此，文是子问题芝的全局最小值点。 3 3 信赖域子问题b 的最优化条件 并且 最后我们讨论子问题b 的最优化充分和必要条件。 定理3 4 假设a l a l i 氏+ 1 。如果是子问题只的解，那么就存在彳，正o 使得 ( 彳一朋r + 彳，) & = - g - 互a ， 彳( 一) = o ， 且有d7 谚jq d o 对于所有满足口r d = o 的d ，其中彳和j 由式( 3 1 7 ) 式定义。 如果i i 口i i = 1 + o 且& 是子问题只的解_ 纠埽那么& 2 龠口。 ( 3 3 7 ) ( 3 3 8 ) ( 3 3 9 ) 证明：如果满足口7 1 一，那么本定理的证明就和定理3 2 的证明过程相同。 如果& 满足口r & 1 + 岛并且j j 口0 1 + 岛，那么我们需要证明当两个约束域函数在文点都 是活跃时口和文是线性无关的，也就是说= 且口7 = l + e o 。假设这不为真。那么就 1 8 + 一 1 且 聪蒯 矿 托纩h印以 岛矿 h 仉 一 i i 以 正o & - 墨 ，l 硕l 论文 一个新锥模型信赖域算法的研究 存在一个常数c 使得口= 强。由口7 文= 1 + 岛和民= a 可以得到 c ：蜂：蚴。c = = _ 。 。