（运筹学与控制论专业论文）求解约束优化与半定互补问题的信赖域方法.pdf

大连理工大学博士学位论文 摘要 信赖域方法是求解非线性最优化问题的一类重要数值计算方法，由于它具有 较好的可靠性和很强的收敛性，因而在近三十年来受到了最优化研究界的重视 特别是近几年来，一直是最优化领域的一个研究重点目前，信赖域方法已经和 传统的线搜索方法并列为非线性规划的两类主要数值方法在变分不等式与互补 问题及平衡约束优化问题中也有信赖域算法可见，在最近兴起的f i l t e r 方法中， 信赖域方法也起着重要的作用 本文主要研究非线性优化中的信赖域方法其中包括信赖域予问题的构造、 求解以及在约束优化及半定互补问题中的应用全文共分六章 第一章：简单介绍信赖域方法的起源及发展现状 第二章：给出了带记忆的信赖域子问题模型该模型不仅包含当前点的信息 而且包含着过去迭代点的信息，从而使我们可以从更全局的角度来求得信赖域试 探步，避免了传统信赖域方法中试探步的求取完全依赖于当前点的信息而过于局 部化的困难将此模型应用到凸约束优化及等式约束优化问题，在几种不同的非 单调信赖域技术下，获得了方法的全局收敛性 第三章：利用谱投影梯度方法与一个新的非单调线搜索技术给出了求解信赖 域子问题的一个方法，在一般的假设条件下获得了方法的全局收敛性 第四章；分析了求解一般非线性方程组的有效集信赖域一c c 方法的全局收 敛性将一般非线性方程组问题转化为带非负约束的极小化问题，并利用有效集 信赖域对其进行求解，其中信赖域子问题是利用截断共轭梯度方法求解的在不 需要聚点存在的条件下获得了算法的全局收敛性 第五章：将n o e e d a l 与y u a n 的组合信赖域与线搜索技术应用到等式约束优 化问题通过求解某一信赖域子问题及对罚因子的矫正，证明了信赖域步为价值 函数提供了一个下降方向为允许负曲率方向及克服m a r a t o s 效应，我们在信赖 域试探步中加入二阶校正步，线搜索时采用非单调技术在一般信赖域方法的假 摘要 设条件下，我们证明了该方法的全局收敛性及局部收敛速度数值试验表明了该 方法的有效性 第六章；给出了求解非线性半定互补问题的一个新的光滑效益函数，在不需 要单调及l i p s c h i t z 连续的条件下，证明了效益函数的水平集有界且稳定点即为 全局极小点进一步地，给出了求解带半定约束极小化问题的信赖域算法，其中 信赖域子问题是利用截断共轭梯度法近似求解的 关键词：约束优化，信赖域方法，半定互补问题，记忆模型，非单调技术，有效 集策略，截断共轭梯度法，稳定点，全局收敛性 大连理工大学博士学位论文 a b s t r a c t t r u s tr e g i o nm e t h o di sac l a n 8o f i m p o r t a n tn u m e r i c a lm e t h o df o rn o n l i n e a r o p t i m i z a t i o np r o b l e m s b e c a u s eo fi t sr e m a r k a b l en u m e r i c a lr e l i a b i f i t yi nc o n j u n c t i o nw i t has o u n da n dc o m p l e t ec o n v e r g e n c et h e o r y , r e s e a r c h e r si nn o n l i n e a r o p t i m i z a t i o na r e ah a v ep a i dg r e a ta t t e n t i o nt oi ts i n c e8 0 s ，e s p e c i a l l yd u r i n g 9 0 sa tp r e s e n t ，t r u s tr e g i o nm e t h o da n dl i n es e a r c hm e t h o da r et w om a i n l y t y p e sn u m e r i c a la l g o r i t h m sf o rn o n l i n e a rp r o g r a m m i n g f o rv a r i a t i o n a li n e q u a f i t y p r o b l e m sa n dc o m p l e m e n t a r i t yp r o b l e m s ，o n ec a na l s od e s i g nt h ec o r r e s p o n d i n e t r u s tr e g i o na l g o r i t h m s m o r e o v e r ，i ta l s o p l a ya l li m p o r t a n tr o l ei nar e c e n t l v d e v e l o p e df i l t e rm e t h o d t h ea i mo ft h i st h e s i s i st os t u d yt h et r u s t r e g i o nm e t h o di nn o n l i n e a r o p t i m i z a t i o n ，w h i c hi n c l u d i n gt h ef o r m i n ga n dt h es o l v i n go ft h et r u s tr e g i o n s u b p r o b l e ma n da p p l i c a t i o n sf o rc o n s t r a i n e do p t i m i z a t i o na n ds e i i l i d e f i n i t ec o r n p l e m e n t a r i t yp r o b l e m s t h i st h e s i si n c l u d e ss i xc h a p t e r s c h a p t e rl ：i n t r o d u c t i o n c h a p t e r2 = at r u s tr e g i o ns u b p r o b l e mm o d e lw i t h m e m o r y i sp r o p o s e dt h e “o 醢e li n c l u d e sm e m o r yo ft h ep a s ti t e r a t i o n ，w h i c hm a k e s t h ea l g o r i t h mm o t e f a r s i g h t e di nt h es e n s et h a ti t sb e h a v i o ri sn o tc o m p l e t e l yd o m i n a t e d b yt h el o c a l n a t u r eo ft h eo b j e c t i v ef u n c t i o n ，b u tr a t h e r b y am o r e g l o b a lv i e w w e a p p l vt l l i s m o d e it oc o n v e xc o n s t r a i n e da n d e 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 np r o b l e m sa n d e s t a b l i s ht h eg l o b a lc o n v e r g e n c ew i t ht h e h e l po fn o n m o n o t o n et e i h n i 口u e s c h a p t e r3 ：u s i n gs p e c t r a lp r o j e c t e dg r a d i e n tm e t h o da n dan e w n o n m o n o t o n el i n 88 e a r c ht e c h n i q u e w ep r o p o s ea a l g o r i t h mf o rs o l v i n gt h et r u s tr e g i 0 1 1 s u b p r o b l e m - u n d e rw e a kc o n d i t i o n s ，t h eg l o b a lc o n v e r g e n c ei se s t a b l i s h e d c h a p t e r4 ：w ea n a l y z ea na c t i v es e tt r u s tr e g i o n - c gm e t h o d f o rt h es o l u t i o n o fn o n l i n e a r s y s t e mw i t he q u a l i t i e sa n d i n e q u a l i t i e s b yr e f o r m u l a t i n gt h es y s t e m i “t oan o a l i n e a rm i n i n d z a t i o n p r o b l e mw i t hd o n n e g a t i v e c o n s t r a i n t ，w ep r o p o s e d 8 “8 。t i ”88 8 tt r u s t r e g i o na l g o r i t h mw i t hw h i c ht h es u b p r o b l e mi s s o l v e db y 塑垦 一一 t h et r u n c a t e dc o n j u g a t eg r a d i e n tm e t h o d t h eg l o b a lc o n v e r g e n c ei se s t a b l i s h e d w i t h o u tr e q u i r i n gt h ee x i s t e n c eo fa na c c u m u l a t i o np o i n t c h a p t e r5 ：w ea p p l yt h ec o m b i n i n g t r u s tr e g i o na n dl i n es e a r c ha l g o r i t h m t os o l v ee 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 b yu s i n gl le x a c tp e n a l t yf u n c t i o n a st h em e r i tf u n c t i o na n ds o l v i n gat r u s tr e g i o ns u b p r o b l e m ，w ep r o v et h a tt h e t r u s tr e g i o nt r i a ls t e pp r o v i d ead e s c e n td i r e c t i o nf o rt h em e r i tf u n c t i o n t oa l l o w t h en e g a t i v ec u r v a t u r ed i r e c t i o na n da v o i dt h em a r a t o se f f e c t ，w ea d ds e c o n d c o r r e c t i o ns t e pt ot r o tr e g i o nt r i a ls t e pa n dm a p l o yn o l l l l l o n o t o n et e c h n i q u ei n l i n es e a r c h t h eg l o b a lc o n v e r g e n c ea i dl o c a ls u p e r l i n e a rr a t ea r eo b t a i n e du n d e r c e r t a i nc o n d i t i o n s s o m en u m e r i c a lt e s t sa r ea l s op r e s e n t e d c h a p t e r6 ：i nt h i sc h a p t e r ，w ep r e s e n tan e w m e r i tf u n c t i o nf o rt h es e m i - d e f i n i t ec o m p l e m e n t a r i t yp r o b l e m ( s d c p ) b ye x t e n d i n gt h eb o u n d e ds m o o t h r e f o r m u l a t i o nf o rv a r i a t i o n a li n e q u a l i t yp r o b l e m s v v ep r o v et h a tt h em e r i tr u n e t i o nh a sab o u n d e dl e v e ls e ta n da n ys t a t i o n a r yp o i n to fi ti sa g l o b a lm i n i m i z e r w i t h o u tt h ea s s u m p t i o no fm o n o t o n i c i t y m o r e o v e r ，w ep r e s e n tat r u s tr e g i o na l g o r i t h mf o rs o l v i n gt h em i n i m i z a t i o np r o b l e m w i t hs e m i d e f i n i t ec o n s t r a i n t s t h e t r u s tr e g i o ns u b p r o b l e mi ss o l v e db yt h et r u n c a t e dc o n j u g a t eg r a d i e n tm e t h o d a n dt h eg l o b a lc o n v e r g e n c ei se s t a b l i s h e de v e nw i t h o u tr e q u i r i n gt h ee x i s t e n c eo f a na c c u m u l a t i o np o i n to ft h eg e n e r a t e ds e q u e n c e k e yw o r d s ：c o n s t r a i n e do p t i m i z a t i o n ，t r u s tr e g i o na l g o r i t h m ，s e m i d e f i n i t e c o m p l e m e n t a r i t yp r o b l e m s ，m e m o r ym o d e l ，n o n m o n o t o n et e c h n i q u e ，a c t i v e - s e t s t r a t e g y , t r u n c a t e dc o n j u g a t e dg r a d i e n tm e t h o d ，s t a t i o n a r yp o i n t ，g l o b a lc o i l - v e r g e n c e 盔连里王盔堂堕主兰垡迨塞一 第一章绪论 1 1弓l 言 最优化问题是在多种( 有限或无限种) 决策中挑选最好决策的问题它广泛 应用予农业、国防、交通、金融、笼源、通信等许多领域，如在资源利用、结构 优化、调度管理、后勤供应等许多问题中产生了巨大的经济效益和社会效应优 化在结构力学、生命科学、环境科学等其他科学研究领域和方向也有广泛应用 如果说，“模拟”深刻地改变着人们认识世界的能力，那么“优化”则深刻 地改变着人们改造世界的方法和途径美国工程科学院院士，啥佛大学何毓琦教 授在国际自控联合会1 9 9 9 年世界大会上以“优化一光彩夺目的领域”为题的报 告中提到“优化是人类文明发展的柱石” 许多急需解决的对国民经济有重大影响的大规模复杂科学和工程问题本质 上都是优化问题它们有的规模十分巨大( 维数达上百万，如大气科学中的四维 同化问题) ，有的规模并不十分巨大但却是非常复杂的优化问题( 如化工工业中的 多相流计算问题) 因此，研究高效的优化计算方法不仅具有重要的科学意义，而 且有着很大的应用前景它对促进优化方法在国民生产等方面的应用将起到重大 作用 在本文中，我们主要考虑优化方法中的信赖域方法全文共分六章，第一章 是绪论，简单介绍了信赖域方法的起源与发展第二章到第六章主要对约束优化 的信赖域方法进行了讨论，其中包括信赖域子问题的构造与求解方法及其在约束 优化与半定互补问题中的应用， 5 1 2 信赖域方法的起源及发展现状 信赖域方法是求解非线性优化的一类重要数值方法，由于它具有很好的稳 健性和较强的收敛性，因此它在近三十年来受到了最优化研究界的重视特别是 近几年来，一直是非线性最优化的研究热点目前，信赖域方法已经和传统的线 搜索方法并列为非线性规划的两类主要数值方法在最近由f l e t c h e r 等提出的 f i l t e r 方法( 或称为无罚函数法) 中，信赖域方法也起着十分重要的作用 信赖域方法的研究起始于p o w e l l 1 】，他首先证明了信赖域方法是全局收敛 的 m o r e 2 】为保证信赖域方法全局收敛提供了一些一般的条件s h u l t z ， 第一章绪论 s c t m a b e l 和b y r df 3 1 则得出了既保证信赖域方法全局收敛又收敛到一满足二阶 必要条件的点的一般条件但是，人们发现信赖域方法的基本技巧在一定意义下 等价于十分著名的求解非线性最小二乘的l e v e n b e r g - m a r q u a r d t 方法 4 i 5 对 于非线性最小二乘问题： r 呶l i y ( x ) 悒 ( 1 1 ) 其中f ( x ) = ( ( z ) ， ( z ) ，厶( z ) ) 了1 ， ( z ) 0 = 1 ，2 ，m ) 是舻中的连续 可微函数，求解( 1 1 ) 的g u a s s - n e w m n 方法是 x k + 1 = 。k + d k = z e a ( z k ) + f ( x k ) 其中且( z ) = v f ( x ) 7 是j a c o b i 矩阵，j 4 + 表示a 的广义逆矩阵 g u a s s - n e w t o n 步也= 一以( ) + f ( x k ) 是问题 ( 12 ) 不难看出， 础m i n 。z k ) + a ( x k ) d l l 2 ( 1 3 ) 的解而问题( 1 3 ) 则是问题( 1 1 ) 在当前迭代点z 的近似，当j a c o b i 矩阵a ( x ) 几乎奇异时。g u a s s - n e w t o n 步d k = - - a ( z k ) + f ( x k ) 很可能会非常长，从而使 g u a s s - n e w t o n 方法出现数值困难为了克服这一困难，由l e v e n b e r g 提出并由 m a r q u a r d t 重新发现的l e v e n b e r g - m a r q u a r d t 方法利用如下步： d = 一( a ( z ) 7 a ( x k ) + a 女，) 一1 a ( 。k ) 7 y ( x ) ，( 1 4 ) 其中h 0 是一参数，它每次迭代修正l e v e n b e r g m a r q u a r d t 方法的思想就 是通过引进参数儿来克服a ( z t ) 的奇异所带来的困难利用恰当的参数丸可 保证矩阵( a ( x k ) 7 a ( x k ) + a ，) 可逆而且能避免出现过大的l i 血忆容易看出， l e v e n b e r g - m a r q u a r d t 步( 1 4 ) 是问题 d m 。印i n l i e ( z ) + a ( 。k ) d f 2 + a i l d l l ；( 1 5 ) 的解问题( 1 5 ) 是问题( 1 3 ) 的修改，所加的一项a k l l d l l ! 可看作罚项，从而可 阻止i f 靠| | 过大 定义 鼠= i i ( a ( x k ) 7 a ( x 女) + k ，) a ( x k ) 7 f ( z 女) 1 1 则不难证明l e v e n b e r g m a r q u a r d t 步也是如下问题： m i n d 肿i i f ( x k ) + a ( x k ) d l l 2 ， s u b j e c t t o i i d l l 2 k 2 ( 1 6 ) ( 1 7 ) 大连理工大学博士学位论文 的解约束条件l i d l l 。正是一信赖域约束，故显然可见，问题( 1 7 ) 是一信 赖域子问题因此，从这个意义下传统的l e v e n b e r g m a r q u a r d t 方法也是一特殊 的信赖方法也正由于此，信赖域方法的历史可以追溯到l e v e n b e r g - m a r q u a r d t 方法 信赖域方法的关键组成部分是如何求得信赖域试探步以及怎样决定试探步 是否可被接受试探步一般是一子问题的解，所以如何求得信赖域试探步实质上 归结于子f 可题的结构，决定试探步是否可被接受通常是利用某一价值函数，看试 探步是否能使价值函数下降对于无约束优化问题，价值函数自然是目标函数， 对于约束优化问题，在传统的信赖域方法中价值函数通常是一罚函数在最近由 f l e t c h e r 等人提出的f i l t e r 方法中 6 】 7 】 8 【9 ，则利用f i l t e r 代替了罚函数在文 1 0 】中，由u l b r i c h 给出的一个非单调信赖域方法中，也不需要利用罚函数 现在考虑无约束最优化问题 m i n ，( z ) s tz r “ ( 1 8 ) 其中，( z ) 是定义在舒上的连续可微函数利用二次逼近构造的信赖域子问题 如下： m i n9 吾d4 - j d 7 b k d s t i i d t a k ， 妣( d ) ( 1 9 ) 其中g k = v f ( x k ) ，b k 是一n n 实对称矩阵，。是信赖域半径 信赖域子问题还可以利用锥模型构造，其形式如下 1 1 1 2 ： m i “静尊绷嘞( d ) ( 1 1 0 ) s t l i d l l 趣， ” 其中d 舻为一向量使得1 4 - 0 7 d 0 解子问题( 1 9 ) 或( 1 1 0 ) 得到实验步d k ， 然后令 p r e d k = c k ( d ) 一机( 血) 为预测下降令 a r e d k = f ( x k ) 一，( z 4 - d k ) 为实际下降再定义预测下降和实际下降的比率为 a r e d 2 两瓦+ 3 ( 1 1 1 ) ( 1 1 2 ) ( 1 1 3 ) 第一章绪论 根据这一比率来决定是否接受试验步以及如何调节信赖域半径 下面给出利用子问题( 1 9 ) 获得的无约束最优化信赖域方法的一般形式1 3 1 算法1 步1给出z l 舻，i 0 ，e 0 ， 0 c 3 c 4 1 c i ，05c osc 2 0 ，= 0 ， 0 c 3 c 4 c t ，0s 岛sc 2 0 ， 厶( x ) 2 曼癸( ( f ( x ) ，g ( x ) 一y ) 一去| | g ( x ) 一y | | 2 ) ( 1 3 7 ) 投影残差函数 7 3 f ( x ) = i i g ( x ) 一 g ( x ) 一f ( x ) + f f 2 ，( 1 3 8 ) 其中i x 表示x 在尼上的正交投影，即， i x + = n r g m i n y 。( i i x y i i f i s c h e r - b u r m e i s t e r 函数 7 4 ，( x ) = ；f j 妒( f ( x ) ，g ( x ) ) 叭 ( 1 3 9 ) 其中函数咖：5 5 一s 定义为 庐( 。，6 ) = ( n 2 + 6 2 ) 1 2 一( o + 6 ) f 1 4 0 ) l u oa n d t s e n g 函数 7 5 ，( x ) = 讥( ( f ( x ) ，g ( x ) ) ) + 妒( f ( x ) ，g ( x ) ) ， ( 1 4 1 ) 苎19 ：r 。( o ，。) 满足条件咖( t ) = o 当且仅当t s o ，矽：s s 一 o ，。) 满 足条件 妒( n ，6 ) = 0 ，( 。，6 ) 0 当且仅当( n ，6 ) 咒厄，( 。，6 ) ：0 掌_ 步警，p a t l lt s e n g 分析了上述价值函数的一些性质，包括可微性，稳定点 为全局点的条件及误差界成立的条件 9 第一章绪论 在p a u lt s e n g 给出关于s d c p 的价值函数中，并没有设计相应的求解方 法1 9 9 8 年，f u k u s h i m a 等人在文 7 6 中给出了s d c p 的如下价值函数 f ( x ) = 妒( ( f ( x ) ，g ( x ) ) ) 4 - 妒( f ( x ) ，g ( x ) ) ， ( 1 4 2 ) 在这里f u k u s h i m a 等人取a ( x ) = x ，妒：r r ，：8 xs 只分别定义为 1 妒( t ) = m a x 0 ， 4 ( 1 4 3 ) t 1 咖( 。，b ) = i 3 - l | ( 驴+ b 2 ) 1 2 一( 口+ b ) 1 2 ( 14 4 ) 和用( 1 4 2 ) 一( 1 4 4 ) 所定义的价值函数，f u k u s h i m a 等人给出了求解s d c p 的 一个全局收敛性下降方法在文 7 7 1 中，张立平，高自友，赖炎连则利用p a u l t s e n g 所给出的正则价值函数( 1 3 7 ) ，给出了求解s d c p 的一个全局收敛性下降 算法x c h e n 与p a u lt s e n g 在文 7 8 中将求解n c p 的非内连续化方法推广 到s d c p ，利用牛顿方法给出了求解s d c p 的具有全局收敛及局部超线性收敛的 方法h u a n g 与h a n 在文 7 9 】中又对这一方法进行了改进而j i es u n ，d e f e n g s u n 与l i q u nq i 在文 8 0 中对非光滑矩阵函数给出了一个具有二次收敛的光滑 牛顿方法，并将其应用到s d c p 在2 0 0 8 年由c k a n z o w 8 1 1 利用f b 函数给出 的求解s d l p 的光滑化方法中，也可以扩展来求解s d c p 但到目前为止，求解 s d c p 的信赖域方法还几乎没有 1 4本文的主要工作 本文研究的主要内容为优化问题中的信赖域方法包括信赖域子问题的构 造、求解及在约束优化与半定互补问题中的应用 信赖域子问题的构造是信赖域方法的重要组成部分之一，本文我们注意到在 传统的信赖域方法中信赖域子问题是仅仅依靠当前迭代点的信息而构造的，换句 话说，传统信赖域子问题的构造完全依赖当前点的梯度及h e s s i a n 信息，雨当前 点之前所得到的点的信息完全被抛弃了，我们称这样的信赖域子闻题为无记忆子 问题但我们发现，当目标函数的非线性程度很高，也就是说，目标函数的二阶 泰勒项作为x 的函数变化很快时，无记忆的信赖域迭代是有缺陷的例如，如果 目标函数具有局部的波纹从而对目标函数的外形几乎没有全局的影响时，无记忆 的信赖域迭代可能会被目标函数的局部信息所蒙蔽，从而容易失去更全局性的轨 迹，尽管后者在确定搜索方向时是极其关键的，而这些方向将会使算法有更为可 1 0 盔整堡三盔堂堡主堂焦堡壅 一 一 观的改进在这种情况下，我们希望结合过去得到点的信息与当前点的信息而建 立新的信赖域- 于j n n ，从而有望获得更好的信赖域试探步我们称这样的信赖域 子问题为带记忆的信赖域子问题 在本文中，我们首先给出了求解凸约束优化的带记忆信赖域子问题，提出了 一个新的信赖域算法，并在非单调技术的帮助下，获得了方法的全局收敛性进 一步地，我们将此方法推广到等式约束优化问题 在信赖域算法中主要的计算量是对信赖域子问题的求解，目前在无约束信粮 域子问题的求解方面已有许多成熟的方法而对于大规模问题的求解更是计算学 者们所关注的，由b a r z i l a ia n db o r w e i ni s 2 最早提出并由r a y d a n 8 3 给出了理 论分析的谱方法的优点是需要的计算量很少，因而特别适合于对大规模问题的求 解另外，由于该方法在每次迭代中不要求目标函数单调下降，从而可以在一定 程度上加快收敛的速度，由于方法的这些优点，它已经被广泛应用于求解大规模 无约束及约束优化问题最近，e g b i r g i n ，jm m a r t i n e za n dm r a y d a n 8 4 1 提 出了具有凸约束的优化问题的非单调谱投影梯度方法，该方法可以用来求解大规 模问题的信赖域子问题在本文中，我们给出了个新的非单调线搜索技术并与 谱投影梯度法结合，给出了可以求解大规模信赖域子问题的一个非单调谱投影梯 度方法，并在一般条件下获得了算法的全局收敛性 到目前为止，求解约束信赖域子问题的有效方法是相对较少的对于等式约 束优化问题，人们一般可将其转化为一个或两个无约束信赖域子问题来求得信赖 域试探步而对于一般约束优化问题，在多数情况下则被转化为带边界约束的信 赖域子问题来求得信赖域试探步，因此人们自然希望寻求有效地求解带边界约柬 的信赖域子问题的方法与无约束信赖域子问题一样，精确求解此类问题的解是 很困难的，因此有必要研究非精确求解的方法，丽求解的思路之是将求解无约 束信赖域子问题的非精确方法推广到此类问题，最近，q ih o u d u o 8 5 等人将由 t i o n t 与s t e i h a u g 提出并由y u a n 给出理论分析的截断共轭法推广到此类问题取 得了良好的理论与数值效果在本文中，我们利用q i 的方法来求解非线性等式 与不等式方程组，并在较弱的条件下获得了更为一般的收敛结果 另一方面，为了克服在一次信赖域迭代中多次求解信赖域子问题的困难， n o c e d a l 与y u a n 8 6 】提出了求解无约束优化的组合信赖域与线搜索技术在本文 中，我们将这一技术应用到等式约束优化问题利用上，精确罚函数作为价值函 数，通过求解一相应的信赖域子问题及对罚参数的适当调整，证明了信赖域试探 步为价值函数提供了一个下降方向而为了允许负曲率方向及克服m a r a t o s 效 第一章绪论 应，我们在信赖域步中力d j x - - 阶矫正步，在线搜索中采用非单调技术在一定条 件下获得了方法的全局收敛性与局部收敛性，并给出数值测试说明了方法的有效 性 价值函数法是目前求解半定互补问题的主要方法，相应地，求解等价的半定 优化问题的一些下降算法也被提出。在以往所给出的半定互补问题的价值函数 中，为获得水平集有界及目标函数的稳定点是极小点的结果，一般都需要单调性 假设，有的甚至需要强单调假设，在本文中，我们给出了半定互补问题的一个新 的价值函数，在不需要单调假设的条件下，获得了上述结果进一步地，我们提 出了求解带半定约束优化问题的信赖域算法并利用内点策略将求解无约束信赖 域子问题的截断共轭梯度法用来求解带半定约束的信赖域子问题，在较弱条件下 获得了一个一般性的收敛结果 1 2 盔重堡三盔兰竖主兰焦堡茎 1 5 一些预备知识 从前面的讨论我们知道，最优化问题的模型一般可表示为 兰t 竖 a s ， s z s 2 ， 其中，函数，( z ) ：彤一r 称为目标函数，nc 印称为可行域下面我们给出 问题( 1 4 5 ) 的解的定义 ( 1 ) 称矿q 为( 1 4 5 ) 的可行解，若矿q ( 2 ) 称矿n 为( 1 4 5 ) 的整体最优解，若对v x q ，有f ( x ) ，( 矿) ；称矿n 为( 1 4 5 ) 的严格整体最优解，若对v x q ，z 一，有f ( x ) 0 ， 使得对v x n ( x + ，d ) nn 有，( o ) 5f ( 2 7 + ) ；称矿n 为( 1 4 5 ) 的严格局部最优 解，若对v z n ，z 矿，有，( z ) ，( 矿) 对于一个最优化问题，求解和验证整体最优解是一件十分棘手的事情，因此 人们寄希望于求得局部最优解对于局部最优解，人们又常借助下面的最优性条 件来讨论 最优性条件： ( 1 ) 稳定点：矿en 称为( 1 4 5 ) 的稳定点，若满足 ( v f ( x + ) ，z z + ) o ，v z n 其中( ，) 表示欧几里德内积，显然，若q = 舻，则稳定点条件退化为v ，( 一) = 0 对于( 1 4 5 ) 的具体表述形式( 1 1 6 ) 一( 1 1 8 ) ，其最优性条件的具体形式为 ( 2 ) f j 条件：若矿为( 1 1 6 ) 一( 1 1 8 ) 的最优解，则当其满足一定条件时，存在 a o r 和a r i 。u z l ，使得下式成立 fa o v f ( z + ) = 九v c ；( x + ) ， li e g u i ? q ( 矿) = 0 ，i ， i q ( z + ) 0 ，九0 ，九如( z + ) = 0 ，i 工 【( o ， ) 0 上述系统称为f j 条件，它最早由f r i t zj o h n 提出对于f j 条件，若= 0 ，那 么这个条件变得没有意义；若a o 0 ，f j 条件就是下面的k k t 条件 1 3 箜二童堡堡 ( 3 ) k k t 条件：若矿为( 11 6 ) 一( 1 1 8 ) 的最优解，则当其满足一定条件时 存在非零向量a ，使得下式成立 fv m + ) = 丸v 岛( 矿) ， li c e 皿 1c i ( x + ) = 0 ，i ， ic t ( z + ) 0 ，九20 ，九q ( 矿) = 0 ，i 工 上述系统称为k k t 条件，有时也简记为k t 条件它最早由k a r u s h 和k u h n ，k u c k e r 分别独立提出 对于非线性优化问题( 1 1 6 ) 一( 1 1 8 ) ，一般没有有效的方法直接求得最优解， 人们普遍采用迭代的方法求解；从初始点z o 出发，利用当前迭代点或已产生的 迭代点的信息产生下一个迭代点，一步步地逼近最优点从而得到一个迭代点列 t k ) 这样便构成了求解( 1 1 6 ) 一( 11 8 ) 的迭代算法那么，我们如何来判断一个 算法的好与坏呢? 通常人们要借助下面几个指标来衡量 ( 1 ) 收敛性；对于算法许可范围内的一类问题，选择合理的任意初始点后， 算法都能较快地给出问题的最优解，或产生的迭代点列的聚点满足一定的最优性 条件如果整个序列收敛到一满足最优性条件的点，称该算法具有全局收敛性 ( 2 ) 收敛速度：设某算法产生的迭代点列 ) 收敛到问题的最优解z + 并设 l i r as u p 1 1 1 2 e ： k + 一l k o 。l l z 女鼎。 若0 0 为信赖域半径 从子问题( 2 1 2 ) 一( 2 1 4 ) 可以看出，信赖域试探步是完全依靠当前点的信息 而获得的换句话说，信赖域子问题模型( 2 1 2 ) 一( 2 1 4 ) 中的目标函数仅利用了 当前点x k 的一阶与二阶信息，而在当前点之前所有点的信息完全被抛弃了 我们将模型( 2 1 2 ) 一( 2 1 4 ) 称为无记忆信赖域子问题模型但是，当目标函数的 1 6 大连理工大学博士学位论文 非线性程度很高时，无记忆的信赖域迭代是有缺陷的例如，当目标函数具有一 些局部的波纹从而对其整体图形有很小的影响时，无记忆的信赖域迭代有可能被 函数的局部性质所欺骗，从而容易失去更为全局性的轨迹，尽管后者在确定搜索 方向上是极其关键的，而这些方向将会使算法有可观的改进在这种情况下，如 果我们利用过去已得到点的信息建立新的信赖域子问题模型将会有助于确定更 好的试探步我们称此类模型为带记忆的信赖域子问题模型 事实上，带记忆的算法已经由n i m g o u l d 等人在文【9 1 中提出，但他们 是以牛顿方向作为搜索方向，以线搜索技术来确定迭代点列的本文中，我们利 用信赖域方法代替线搜索技术，从而不必要求目标函数的h e s i a n 阵是正定的 另外，n _ i mg o u l d 等人考虑的是无约束优化问题，丽这里我们则考虑约束优化 问题 2 1 2 算法模型 设呶为( 2 1 2 ) 一( 2 1 4 ) 的解，等价地，我们可以将氏看做是在约束域。 q ，忙一z l ls k 上使得孤+ d k 为下面的模型达到极小的点 1 m k ( ) 2 f ( x k ) + ( 吼z z b ) + 击( z z k ，h k ( x 一。) ) ( 2 15 ) 由此可知，信赣域迭代的“短浅”性质来自于此模型的纯局部性如果我们想使 得算法更长远一些，自然要考虑具有更全局性质的模型为此，我们考虑如下的 模型； m ( z ) = ，m ( ) + ( 群，z z e ) + j 1 ( x - - x k l 础( z z 。) ) 其中，m ( z ) ，日分别为，( z k ) ，船，日女的近似具体地，我们考虑m ( z ) 为当前的纯局部模型m t ( z ) 与过去点的模型的组合，即， m r ( z ) = ( 1 一脚) m k ( z ) + p m 芒。扛) ，( 21 6 ) 其中，肌 o ，- ，可 0 ，1 ) ，过去模型的量就是由此参数来控制的那么我们如