（應(yīng)用數(shù)學(xué)專業(yè)論文）線性約束優(yōu)化問題的仿射信賴域子空間算法.pdf

中交摘要 摘要 最優(yōu)化理論與方法是決策科學(xué)和系統(tǒng)分析中的一個重要工具，在很多領(lǐng)域都有著非 常廣泛的應(yīng)用。本文主要研究線性等式和不等式約束的非線性優(yōu)化問題，提出了結(jié)合內(nèi) 點回代線搜索技術(shù)的仿射信賴域子空間算法 信賴域策略是求解非線性規(guī)劃問題的兩種基本逼近方法之一，它能保證算法的 整體收斂性對于無約束優(yōu)化問題，信賴域方法的思想非常簡單與直觀。但是， 對于約束優(yōu)化問題，由于約束的存在，通常很難構(gòu)造一個類似的信賴域子問題。 最近，c o l e m a n 和l i 針對僅帶有線性不等式約束的優(yōu)化問題，提出了“雙信賴域方 法”( t r a m ) ，通過仿射變換，成功地構(gòu)建了一個近似二次模型函數(shù)和信賴域子問題，同 時證明了算法的整體收斂性，然而文中并未具體給出求解信賴域子問題的方法，且在每 次迭代過程中，往往要重復(fù)多次求解該子問題，才能獲得可接受的嚴格內(nèi)點可行步，因 此，每得到一新的迭代步，必帶來較大的計算量。為克服在求解信賴域子問題時所面臨 的一系列困難，本文將借助于子空間技術(shù)，信賴域算法及內(nèi)點回代線搜索技術(shù)來搜索得 到一個嚴格內(nèi)點可行步。信賴域子空間技術(shù)的應(yīng)用使得本算法適用于求解大型的約束優(yōu) 化問題。 本文先對一些相關(guān)概念、理論及方法進行簡單的回顧，作為進一步研究的基礎(chǔ)接 著引進一個仿射變換矩陣，同時構(gòu)建一個近似二次模型函數(shù)和信賴域子問題。受到子空 間技術(shù)的啟發(fā)，我們給出二維子空間的具體形式，并結(jié)合子空間求解信賴域子問題，從 而獲得模型的一個候選的迭代方向，然后沿此方向通過線搜索獲得步長因子，既能保證 迭代點嚴格可行，又能使目標(biāo)函數(shù)在迭代點處單調(diào)下降。最后基于信賴域子空問算法的 良好性質(zhì)，在合理的假設(shè)條件下，證明了該算法不僅具有整體收斂性，而且保持局部超 線性收斂速率數(shù)值計算結(jié)果表明了算法的有效性 關(guān)鍵詞：非線性約束優(yōu)化；不等式約束：信賴域算法：子空間技術(shù)；仿射變換；內(nèi)點 法；整體收斂性；局部收斂速率 第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 范數(shù) o o 一范數(shù) p r o b e n i u s 一范數(shù) 竹維決策變量 向量z 的第j 個分量 目標(biāo)函數(shù)的局部極小值點 目標(biāo)函數(shù) ，在當(dāng)前迭代點z i 處的函數(shù)值 約束函數(shù) 可行集 嚴格可行集 ，在。處的梯度 l a g r a n g e 乘子 約束優(yōu)化問題的ia g 髓n g e 函數(shù) ，在z 處的投影梯度 ，在z 處的增廣梯度 ，在處的h e s s e 陣 第k 次迭代步 譏( 以；五) 目標(biāo)函數(shù)在孤處的局部二次近似 信賴域半徑 c ( o ) = p 9 妒i ，0 ) ，( 跏) ) 水平集 翻線性約束優(yōu)化問題的子空間 第頁 論文獨創(chuàng)性聲明 本論文是我個人在導(dǎo)師指導(dǎo)下進行的研究工作及取得的研究 成果。論文中除了特別加以標(biāo)注和致謝的地方外，不包含其他人 或機構(gòu)已經(jīng)發(fā)表或撰寫過的研究成果其他同志對本研究的啟發(fā) 和所做的貢獻均已在論文中做了明確的聲明并表示了謝意 作者簽名：日期： 論文使用授權(quán)聲明 本人完全了解上海師范大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定， 即：學(xué)校有權(quán)保留送交論文的復(fù)印件，允許論文被查閱和借閱； 學(xué)?？梢怨颊撐牡娜炕虿糠謨?nèi)容，可以采用影印、縮印或其 它手段保存論文保密的論文在解密后遵守此規(guī)定。 作者簽名：導(dǎo)師簽名； 日期： 第一章最饒化同趣基本概念 第一章最優(yōu)化問題基本概念 1 1 最優(yōu)化問題簡介 最優(yōu)化理論與方法是一門應(yīng)用相當(dāng)廣泛的學(xué)科，它討論決策問題的最佳選擇之特 性，構(gòu)造尋求最佳解的計算方法，研究這些計算方法的理論性質(zhì)及實際表現(xiàn)因為最優(yōu) 化問題廣泛應(yīng)用于經(jīng)濟計劃、工程設(shè)計、生產(chǎn)管理，交通運輸，國防等重要領(lǐng)域，已受 到政府部門的高度重視。伴隨著電子計算機的普及和優(yōu)化計算方法的迅速發(fā)展，規(guī)模越 來越大的優(yōu)化問題得到解決通常，為應(yīng)用最優(yōu)化技術(shù)確定最優(yōu)方案，需要針對具體的 實際問題建立相應(yīng)的最優(yōu)化模型，再根據(jù)模型的具體形式和特征選擇適當(dāng)?shù)淖顑?yōu)化方法 求解。 最優(yōu)化問題的數(shù)學(xué)模型通常寫為： m i n ，( s t c ( 扛) = 0 ，i = 1 ，2 ，鞏 ( 1 1 1 ) c i ( ) 0 ，t = k 十l ，m 其中。一p l ，現(xiàn)，) r 艫為決策變量，( ：艫耕為目標(biāo)函數(shù)，c c ( z ) ： 艫一跪1 0 = 1 ，2 ，m ) 為約束向量函數(shù)。m m 。是兩個非負整數(shù)如果約束條 件m = m 。= 0 ，則稱優(yōu)化目題( 1 1 1 ) 為無約束最優(yōu)化問題。為方便數(shù)值計算，這里我們定 義的且標(biāo)函致，0 ) 與約柬函數(shù)q 扛) ， = 1 ，2 ，m ，均為實值連續(xù)可微函數(shù) 為便于下文敘述，定義 = 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 ) 的嚴格內(nèi)點可行域 一般情況下，可借助于在z 處的目標(biāo)函數(shù)和約束函數(shù)信息獲得一階必要性條件和二階 必要性條件，至于充分必要性條件只對一些特殊的最優(yōu)化問題存在，最優(yōu)化條件不僅對 最優(yōu)化理論的研究具有重要意義。兩且對最優(yōu)化算法的設(shè)計和終止條件的確定起著重要 的作用。 第l 頁 1 2 最優(yōu)化方法的結(jié)構(gòu) 1 2 最優(yōu)化方法的結(jié)構(gòu) 最優(yōu)化方法通常采用迭代方法求它的最優(yōu)解，其基本思想是：給定一個初始點跏 g p ，按照某一迭代規(guī)則產(chǎn)生一個點列 z ) ，使得當(dāng) 取) 是有窮點列時，其最后一個點是 最優(yōu)化模型問題的最優(yōu)解，當(dāng) 瓢) 是無窮點列時，它有極限點，且其極限點是最優(yōu)化問 題的最優(yōu)解 設(shè) z 為第k 次迭代點，氏為第k 次搜索方向，訊為第k 次步長因子，則第k 次迭代格 式為： z k + 1 = 蕾k + o t k 氐( 1 2 1 ) 從這個迭代格式可以看出，不同的步長因子覦和不同的搜索方向以構(gòu)成了不同的方法 一個好的算法應(yīng)具備的典型特征是：迭代點茁k 能穩(wěn)定地接近于局部極小值點z 。的鄰 域，然后迅速收斂于z 當(dāng)給定的某個收斂準(zhǔn)則滿足時，迭代即終止如果對任意的初 始點z o q ，由算法產(chǎn)生的點列都收斂于最優(yōu)點z 。，則稱該算法具有整體收斂性一個 算法是否可行，分析其是否具有整體收斂性，一般地，可以通過證明迭代點列 z k ，的聚 點( 即子序列的極限點) 為一局部極小值點。 速度是衡量一個算法有效性的重要方向如果點列 瓢 雖收斂到z 。，但收斂地太 慢，以至在允許的時間內(nèi)不可能達到滿意的迭代結(jié)果，則算法可能沒有實際的應(yīng)用價 值 最優(yōu)化方法中，牛頓步和擬牛頓步都具有很好的局部超線性收斂速率牛頓法對非 二次函數(shù)不能保證整體收斂性。但當(dāng)初始點靠近極小值點時，收斂速率一般是快的。 算法的另一個重要特征為終止迭代所需要的終止準(zhǔn)則。最有用的也許是要求i i 瓤一 z 0 f 或i ，) 一，0 ) i e 其中參數(shù)e 由使用者提供。但由于上述準(zhǔn)則需要預(yù)先知道解 的信息，因而是不實用的事實上，由于0 l 一鞏是誤差i j 鞏一文0 的一個估計，因此 我們有時采用 或 0 i + 1 一鞏0 f i ( z l k 一( 鞏) d 日， ( 1 2 3 ) 其中( z ) t 表示向量觀的第t 個分量另一個可以采用的終止準(zhǔn)則是 f ( x k ) 一，( ?！? ) 毛 值得注意的是，以上的終止準(zhǔn)則并不是萬能的在不同的最優(yōu)化方法中往往采用不同的 終止準(zhǔn)則，有時甚至是同時采用不同的終止準(zhǔn)則。具體可以參考【”】等文獻中有關(guān)最優(yōu) 化方法的實際應(yīng)用。 第2 頁 第一童最僥化問題基本概念 1 3 兩類常用的最優(yōu)化的整體收斂性方法簡介 從( 1 2 1 ) 式可以看出，不同的步長因子弧和不同的搜索方向缸將構(gòu)成不同的迭代方 法其中。線搜索方法與信賴域策略是保證最優(yōu)化方法總體收斂的兩類技術(shù)。下面我們 分別作一下簡單的介紹 1 3 1 線搜索方法 從當(dāng)前迭代點瓢出發(fā)，設(shè)搜索方向矗已知且為下降方向，確定步長因子硯使 ，( “+ n 鞏) o 為信賴域半 徑，0 為某一范數(shù)，通常采用1 2 范數(shù)。 信賴域子問題的求解方法，一般情況下，當(dāng)取正定且0 且1 v ( x h ) 0sa k 時，子 問題( 1 3 2 ) 的解可以簡單地通過求解二次模型似p ) 在無信賴域約束下的最優(yōu)解= 一p f l v ，( o i ) 得到，被稱為牛頓( 或擬牛頓) 步。 n o c e d a l 和y u a n 在 1 7 0 提出了一種結(jié)合信賴域和線搜索的方法，這種方法被稱為回 代( b a c k t r a c k i n g ) 法。它自然地利用了內(nèi)計算出的試探步如，在乳方向上采用一維搜索 以使產(chǎn)生合理的下降量，這種方法每次迭代只需計算一次信賴域子問題 第3 頁 1 4 信賴域予空婀算法簡介 另外文獻 8 - - 1 6 中給出了信賴域予問題的構(gòu)造及求解方法，書 2 1 - 2 3 q a 相關(guān)章節(jié)也都 有該方法的具體說明。 1 4 信賴域子空間算法簡介 在文獻【2 _ 4 】中獲得利用子空間技術(shù)近似求解信賴域子問題思想，且對反正定的情況 下說明的比較清晰。本文將以此為基礎(chǔ)，進一步討論反負定和不定的情況，并給出子空 間的具體形式和信賴域子空間算法的描述及必要的理論證明在子空間的構(gòu)造上，將結(jié) 合梯度方向，牛頓步( 擬牛頓步) 方向及負曲率方向，信賴域子空問算法明顯可降低原 問題的維數(shù)，進而一定程度上減輕了求解信賴域子問題的復(fù)雜性。另外子空間算法其實 質(zhì)是折線法的延伸。 下文中將給出算法的具體描述及相關(guān)的證明過程，概述如下：第一章中已對一些相 關(guān)的基本概念、理論和方法進行簡單的回顧第二章中，給出了子空間的具體形式，并 在子空間中求解信賴域的子問題；第三章中，結(jié)合回代步、內(nèi)點仿射變換、信賴域子空 間策略與線搜索技術(shù)，描述了仿射內(nèi)點信賴域子空間算法；第四章中，證明了在合理的 假設(shè)條件下算法具有弱整體收斂性；第五章中，結(jié)合合理的假設(shè)條件，進一步證明了算 法不僅具有強整體收斂性，而且具有超線性收斂速率；第六章中，通過具體的數(shù)值試驗 結(jié)果，說明了該算法的實際可行性和有效性最后，第七章對本文工作進行總結(jié)，同時 提出進一步的研究方向。 第4 頁 第二章線性約束問題的仿射內(nèi)點信賴城子空聞劈法 第二章線性約束問題的仿射內(nèi)點信賴域 子空間算法 2 1 引言 本文主要考慮求解帶有線性等式和不等式約束的非線性優(yōu)化問題： m i l l ，【z ) s t a 1 z = 6 1 ( 2 1 1 ) a 2 x 6 2 舯，滯一鏟是連續(xù)可繃非線性醮，矩附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 幻，并 假設(shè)不等式約束的嚴格內(nèi)點可行集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 】中提出了雙信賴域仿射變換內(nèi)點法求解僅帶有線性不等式約束的 最優(yōu)化問題，即 m i n f ( x ) ( 2 1 2 ) s t a 2 2 26 2 。 該算法由( 2 1 2 ) 的一階必要性條件得到牛頓步，并基于牛頓步建立其信賴域子問題。簡述 如下：假設(shè)z 是當(dāng)前的嚴格可行迭代內(nèi)點，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 信籟域子空聞問題的近似最優(yōu)解 叫磊卜”，即 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 】中證明它使得原始目標(biāo)函數(shù)單調(diào)下降，并利用增廣 二次型作為模型的目標(biāo)函數(shù)，給出了下面的信賴域子問題： ( 2 1 6 ) 其中甌= 仇或者鼠= 西k ，晚是文章i l 】中給出的另一仿射校正矩陣。甌取d i 時可以 得到類似的結(jié)果，本文只考慮& = 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 & 雙信賴域仿射變換內(nèi)點法保證了每次迭代即滿足信賴域約束又滿足內(nèi)點可行性約 柬。c o l e m a n 和“在f 1 沖給出的充分下降條件保證了互補松弛性對偶可行性廈二階必 要性條件的成立，并最終證明了信賴域仿射變換內(nèi)點法的整體與局部收斂性最近，朱 德通在文【”】中提出了一個新的具有非單調(diào)內(nèi)點回代技巧的仿射變換信賴域方法求解帶有 線性等式與不等式約束的最優(yōu)化問題，并證明了該算法的整體收斂性和局部超線性收斂 速率 由于上述問題的不等式約束使得保持內(nèi)點可行有一定的困難，并且在計算每一步新 的迭代點時需要在擴展等式約束的零子空間中極小化一個具有仿射變換橢球約束的二次 函數(shù)，所以當(dāng)零子空問的維數(shù)較大時，計算工作量比較大受到文【2 】，【3 】和【4 】中利用子空 間技巧近似求麓信賴域子問題思想啟發(fā)，本文首先構(gòu)建合適的二維子空間，在子空問中 求解得到模型的迭代方向，然后沿此方向通過線搜索獲得步長因子，既能保證迭代點嚴 格可行，又能保證迭代點使目標(biāo)函數(shù)單調(diào)下降子空間技術(shù)的應(yīng)用使得我們的方法適用 于求解大規(guī)模的優(yōu)化問題?；谛刨囉蜃涌臻g算法的良好性質(zhì)，在合理的假設(shè)條件下， 證明了該算法不僅具有整體收斂性，而且保持局部超線性收斂速率。 2 2 信賴域子空間問題的近似最優(yōu)解 本節(jié)中，考慮用具有非單調(diào)內(nèi)點回代技巧的仿射變換信賴域子空間算法求解問 第6 頁 如q 筇巧 擴亂篇叨懶 魯蚍 第z - 章線性約柬問題的仿射內(nèi)點信賴坡子空問算法 題( 2 1 1 ) 。這包括選取一個仿射變換矩陣玩和一個二次模型函數(shù)極( 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 ) 的一個穩(wěn)定點進一步，此時若對任意的i = 1 ，2 ，f ，都有l(wèi) 定i 0 。并且不等式啄 矗一鉀 o 與i 應(yīng)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 當(dāng)遠離解的時候，牛頓步。女不一定就是，( z ) 的一個下降方 向。為獲得整體收斂性，我們采取【l 】中的建議，用qd = e fd i a g l 綹i 來代替d i a g 觸) ，可 得下面的修正牛頓步方程，即 暖一舊阱一r a 豢t x - 嘞 一： 可以證明，修正牛頓步是漸進充分接近于精確牛頓步的，因此具有較快的收斂 速率。利用增廣二次函數(shù)作為模型的目標(biāo)函數(shù)，可得在a ，的零子空間中與修正牛頓 步喇相關(guān)的信賴域子問題如下： 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 露饑的下降量度量的譏池面的一個充分下降將 導(dǎo)致滿足互補性條件： 溉l l v 矗一鐘k + 1 一霹弘“1 8 2 = o ，和熙或脅1 l | 2 z o 髂2 i 1 ) 2 2 1負曲率方向的構(gòu)造 類似于文獻 2 8 ，2 9 1 中對對稱矩陣晚的分解可知，存在單位正交矩陣q 和對角矩 陣札，使得反= q i a q ：，其中札的對角元素以s 醒s 榷構(gòu)成風(fēng)的n 個特征值， 第8 頁 由于a 是對角矩陣，赦可以擴充單位正交矩陣仉和對角陣，使得慨：i 仇rl 必t j l 曼j = 三：= 黼= 衙= 特征值，且相應(yīng)的n + m 個標(biāo)準(zhǔn)正交特征向量分別為鼠= l ：l ，露= i ：i ，口1 = ”= 虢m - c - m , 其鴨妒踴個禳齜其毓耥的靴向 假設(shè)矩陣 2 一是 是行滿秩i 、的t j l = ， a + 那j , 么：- - 它i 的o 零空問g _ _ ( i 2 一麓 ) c 以下簡記 值，程= m 定義 甌磐一s g n ( 鰭程) 程 ( 2 2 1 2 ) 其中s 印暈符號函數(shù)，早由畢定義的礬滿足霹 靠瓴= 嘏 0 ，以使0 缸+ e d l ls 忱對任意的成立，我們在下文中假設(shè)0 肘硼k 1 成立 第9 頁 未籠竺篙三：巍毫嫉0 磊。二簍三篇篇圣 摹熟淼每t 顯k 篙鼯關(guān)，諾鰳莽0 在 子空間中求解信賴域子問題( ) 所得到的解1 7i 必屬于m ，即j r 、 llzl 2 2 3 子問題的近似最優(yōu)解的確定 令砟表示由二維予空間s r 的標(biāo)準(zhǔn)i e 交基所張成的矩陣顯然可得k 筑一+ 哪“，硭妖= 如。由于本文考慮在二維子空間中求解信賴域子問題( t k ) t 則必存 在弧刪糠娟如g 滿g l l c d e o 1 陬州i = 蚓| p 結(jié)厶子空問觀可 得( n ) 的一階必要性條件： 埒( 觚+ 仃k i ) k 弧= 一蹬弧 靠( 一0 弧0 2 ) = 0 ， o k 0 ( 2 2 1 3 ) ( 2 2 ，1 4 ) 下面分別考慮求解不同情況下子嘲n ，的近似最優(yōu)解圖輒鯽鯽乘為 方便起見，以下求解過程將統(tǒng)一省略下標(biāo)七 1 當(dāng)m 在 ，上是正定矩陣時，由子空同的定義可褥 由( 2 2 1 3 ) 式，可得 ( y 丁肘y + 叮，挎= 一y 勺 正交分解上式中的對稱矩陣p m y ，可知存在單位正交矩陣u 和對角矩陣y ， 使y r m y ；( ，y 曠，其中硯2 也構(gòu)成礦m l ，的兩個特征值，正交矩陣u 的 列玨1 ，晚分別為相應(yīng)的標(biāo)準(zhǔn)正交特征向量，因此問題( 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 ， 第二章線性約束問題的仿射內(nèi)點信賴域子空聞算法 由上式可知，如果口= 。且怕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 一 成立。將其展開、整理后可得一個關(guān)于盯的四次方程： 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 結(jié)合c 2 2 - ，式和c 2 2 ，9 ) 式求解a 和 ： 2 當(dāng)m 在 廠上是不定矩陣時， 若i i c m 。+ o o - 1 引i 成立，那么由子空間的定義得 y = 贏贏器耩器躲 ( z 2 2 0 ) 于是類似于1 中的求解過程可知，必存在口 口使i l u l i = 成立，再結(jié)合( 2 2 1 7 ) 式 和c 2 2 - 式求解盯和 習(xí) 若8 ( m + 口j ) - i 酬 o 使m l = 成立，再結(jié)合( 2 2 1 7 ) 式 和c z 2 t 叻式求解盯和 ： 注釋3 ：為便于下文的證明，相對于上述情況2 中的“困難情況”，稱其他情況為“一般 情況”。 第1 2 頁 第三章算法 第三章算法弟二早畀) 玄 本章我們給出求解問題( 2 1 1 ) 的仿射內(nèi)點信賴域子空圊算法。 初始步：選取參數(shù)口( 0 ， ) ，i ( 0 ，1 ) ，o 7 l 啦 1 ，0 饑 仇 l 0 ， 選取一個對稱矩陣風(fēng)，給定初始信賴域半徑a o 和初始嚴格可行內(nèi)點z o i n