（運(yùn)籌學(xué)與控制論專業(yè)論文）非線性優(yōu)化中的一類對(duì)偶算法的理論研究.pdf

摘要 本文主要研究非線性優(yōu)化中的一類對(duì)偶算法，包括無(wú)約束極大極小問(wèn) 題的對(duì)偶算法和約束非線性規(guī)劃問(wèn)題的一類對(duì)偶算法的理論與相應(yīng)的數(shù)值 實(shí)現(xiàn)本文取得的主要結(jié)果可概括如下t 1 第2 章建立求解不等式約束優(yōu)化問(wèn)題的一類對(duì)偶算法的理論框架在 適當(dāng)?shù)募僭O(shè)條件下，證明了該類算法的局部收斂性質(zhì)，并給出近似解 的誤差界驗(yàn)證了p o l y a k ( 1 9 9 2 ) 的修正障礙函數(shù)算法以及b e r t s e k a s ( 1 9 8 2 ) 的增廣l a g r a n g e 函數(shù)算法都是這類算法的特例還基于個(gè)指 數(shù)型勢(shì)函數(shù)建立了相應(yīng)的對(duì)偶算法，它也屬于這類對(duì)偶算法對(duì)這一對(duì) 偶算法，給出了精細(xì)的收斂性結(jié)果，同時(shí)估計(jì)了勢(shì)函數(shù)的h e s s e 陣的條 件數(shù)，它依賴于罰參數(shù) 2 第3 章給出無(wú)約束極大極小問(wèn)題的一個(gè)對(duì)偶算法的收斂理論給出一 個(gè)基于b e r t s e k a s ( 1 9 8 2 ) 罰函數(shù)的求解無(wú)約束極大極小問(wèn)題的對(duì)偶算 法證明罰參數(shù)存在一個(gè)閥值，當(dāng)罰參數(shù)小于這一閥值時(shí)，該對(duì)偶算法 產(chǎn)生的序列局部收斂到問(wèn)題的k u h n t u k e r 點(diǎn)，并建立了參數(shù)解的誤差 估計(jì)式同樣估計(jì)了罰函數(shù)的h e s s e 陣的條件數(shù)。它也依賴于罰參數(shù) 3 第4 章考慮算法的實(shí)現(xiàn)技術(shù)與算法的推廣首先針對(duì)前兩章的對(duì)偶算 法由于需要精確求解一系列無(wú)約束極小化問(wèn)題，因而實(shí)際計(jì)算中很難 實(shí)現(xiàn)這一缺點(diǎn)，構(gòu)造修正的對(duì)偶算法，即，關(guān)于勢(shì)函數(shù)的無(wú)約束極小化 問(wèn)題無(wú)需精確求解的對(duì)偶算法證明這些修正的對(duì)偶算法仍具有同前 兩章的概念性對(duì)偶算法相同的收斂性結(jié)果我們還進(jìn)一步構(gòu)造了般 約束非線性規(guī)劃問(wèn)題的對(duì)偶算法，建立了相應(yīng)的局部收斂理論最后估 計(jì)了修正l a g r a n g e 函數(shù)的h e s s e 陣的條件數(shù)，它同樣依較于罰參數(shù) 4 第5 章對(duì)第2 章，第3 章及第4 章的對(duì)偶算法進(jìn)行了數(shù)值實(shí)驗(yàn)用這 些算法計(jì)算大量的規(guī)模不是很大的不等式約束優(yōu)化問(wèn)題，無(wú)約束極大 極小同題，一般約束優(yōu)化問(wèn)題，數(shù)值結(jié)果表明它們是有效的同時(shí)給出 的各種關(guān)于數(shù)值結(jié)果的表格驗(yàn)證了取得的某些理論結(jié)果的正確性 關(guān)鍵詢：對(duì)偶算法，無(wú)約束極大極小問(wèn)題，約束非線性規(guī)劃問(wèn)題，修正l a g r a n g e 函數(shù)，勢(shì)函數(shù)，罰參數(shù)，條件數(shù)，局部收斂性，誤差界 a b s t r a c t t h i sd i s s e r t a t i o ns t u d i e sm a i n l yt h e o r i e sa n da c c o r d i n gn u m e r i c a li r a - p l e m e n t a t i o no fac l a s so f d u a la l g o r i t h m sf o rn o n l i n e a ro p t i m i z a t i o np r o b - l e m s ，i n c l u d i n gu n c o n s t r a i n e dm i n i m a xp r o b l e m sa n dc o n s t r a i n e dn o n l i n e a r p r o g r a m m i n gp r o b l e m s t h em a i nr e s u l t s ，o b t a i n e di nt h i sd i s s e r t a t i o n ， m a yb es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r2e s t a b l i s h e st h et h e o r e t i c a lf r a m e w o r ko fac l a s so fd u a la l g o r i t h m sf o rs o l v i n gn o n l i n e a ro p t i m i z a t i o np r o b l e m sw i t hi n e q u a l i t y c o n s t r a i n t s w ep r o v e ，u n d e rs o m em i l da s s u m p t i o n s ，t h el o c a lc o n v e r - g e n c et h e o r e mf o rt h i sc l a s so fd u a la l g o r i t h m sa n dp r e s e n tt h ee r r o r b o u n df o ra p p r o x i m a t es o l u t i o n s t h em o d i f i e db a r r i e rf u n c t i o nm e t h o d so fp o l y a k ( 1 9 9 2 ) a n dt h ea u g m e n t e dl a g r a n g ef u n c t i o nm e t h o do f b e r t s e k a s ( 1 9 8 2 ) a r ev e r i f i e dt ob et h es p e c i a lc a s e so ft h ec l a s so fd u a l a l g o r i t h m s ad u a la l g o r i t h m ，b a s e do na l le x p o n e n t i a lp o t e n t i a lf u n c - t i o n ，i sp r o v e nt ob ei n c l u d e di nt h i sc l a s so fd t l a la l g o r i t h m s d e t a i l e d c o n v e r g e n c er e s u l t sf o rt h ed u a la l g o r i t h ma x eg i v e na n dt h ee s t i m a t eo f t h ec o n d i t i o nn u m b e ro ft h ep o t e n t i a lf u n c t i o n sh e s s i a ni se s t a b l i s h e d ， w h i c hd e p e n d so nt h ep e n a l t y p a r a m e t e r 2 c h a p t e r3i sd e v o t e dt ot h es t u d yo ft h ec o n v e r g e n c et h e o r yo fad u a l a l g o r i t h mf o ru n c o n s t r a i n e dm i n i m a xp r o b l e m s ad u a la l g o r i t h mf o r s o l v i n gu n c o n s t r a i n e dm i n i m a xp r o b l e m s ib a s e do i lt h ep e n a l t yf u n c t i o n o f b e r t s e k a s ( 1 9 8 2 ) ，i sp r e s e n t e d w ep r o v et h a tt h e r ee x i t sat h r e s h o l d o ft h ep e n a l t yp a r a m e t e rs a t i s f y i n gt h a tt h es e q u e n c e s g e n e r a t e db y t h ed u a la l g o r i t h mc o n v e r g el o c a l l yt ot h ek u h n - t u k e rp o i n to ft h e u n c o n s t r a i n e dm i n i m a xp r o b l e m sw h e nt h ep e n a l t yp a r a m e t e ri sl e s s t h a nt h et h r e s h o l d a n dw ee s t a b l i s ht h ee r r o rb o u n d o ft h es o l u t i o 璐 w i t ht h ep e n a l t yp a r a m e t e r f u r t h e r m o r e ，t h ec o n d i t i o nn u m b e ro f p o t e n t i a l f u n c t i o n sh e s s i a ni se s t i m a t e d ，w h i c hd e p e n d so nt h ep e n a l t y p a r a m e t e r 3 c h a p t e r4s t u d i e st h et e c h n i q u e sf o rn u m e r i c a lr e a l i z a t i o no f t h ed u a l a l g o r i t h m sa n dg e n e r a l i z a t i o no ft h ed u a la l g o r i t h m s t og e n e r a lu s c o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g a tf i r s t ，w ec o n s t r u c tm o d i f i e d d u a la l g o r i t h m st oo v e r c o m et h ed r a w b a c kt h a ti tn e e d st or e s o l v ea s e q u e n t i a lu n c o n s t r a i n e dm i n i m i z a t i o np r o b l e m se x a c t l yi n t h es t e p2 o ft h ed u a la l g o r i t h m si nc h a p t e r2a n dc h a p t e r3 i ti sp r o v e nt h a t t h e s em o d i f i e dd u a la l g o r i t h m ss t i l lh a v et h es a m ec o n v e r g e n c er e s u l t s a st h o s eo ft h ec o n c e p t i o n a ld u a la l g o r i t h m si nc h a p t e r2a n dc h a p t e r 3 s e c o n d l y , ad u a la l g o r i t h mi sc o n s t r u c t e df o rg e n e r a lc o n s t r a i n e d n o n l i n e a rp r o g r a m m i n g p r o b l e m sa n dt h el o c a lc o n v e r g e n c et h e o r e m i s e s t a b l i s h e da c c o r d i n g l y t h ec o n d i t i o nn u m b e ro fm o d i f i e dl a g r a n g e f u n c t i o n sh e s s i a ni se s t i m a t e d ，w h i c ha l s od e p e n d so nt h ep e n a l t yp a _ r a m e t e r 4 c h a p t e r5r e p o r t sn u m e r i c a le x p e r i m e n t sf o rt h ed u a la l g o r i t h m si n c h a p t e r2 c h a p t e r3a n dc h a p t e r4 w ea p p l yt h e s ed u a la l g o r i t h m s t os o l v eal a r g en u m b e ro fn o n l i n e a ro p t i m i z a t i o np r o b l e m sw i t hr e l a - t i v es m a l l s c a l e ，i n c l u d i n gi n e q u a l i t y c 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 s ， u n c o n s t r a i n e dm i n i m a x p r o b l e m sa n dg e n e r a lc 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 s t h en u m e r i c a lr e s u l t sd e m o n s t r a t et h a tt h ed u a la l g o r i t h m s a r ee f f e c t i v ea n dt h e1 i s t e dt a b l e so nt h en u m e r i c a lr e s u l t sc o n f i r mt h e c o r r e c t n e s so fs o m et h e o r e t i c a lr e s u l t so b t a i n e di nt h e p r e v i o u sc h a p t e r s k e y w o r d s ：d u a l a l g o r i t h m ，u n c o n s t r a i n e dm i n i m a xp r o b l e m ，c o n s t r a i n e d n o n l i n e a r p r o g r a m m i n gp r o b l e m ，m o d i f i e dl a g r a n g ef u n c t i o n ，p o t e n t i a l f u n c - t i o n ，p e n a l t yp a r a m e t e r ，c o n d i t i o nn u m b e r ，l o c a lc o n v e r g e n c e ，e r r o rb o u n d 蔓! 童 墮絲l 一 1 緒論 綜述對(duì)偶方法中的原始一對(duì)偶方法及修正l a g r a n g e 函數(shù)方法的研究歷史及現(xiàn) 狀；介紹本文研究的非線性優(yōu)化中的一類對(duì)偶算法的研究背景，并列出取得的主要 結(jié)果 1 1 原始對(duì)偶方法與修正l a g r a n g e 函數(shù)方法 原始對(duì)偶方法是求解線性規(guī)劃及非線性規(guī)劃的重要方法這一方法在線性規(guī)射領(lǐng) 域中的理論已發(fā)展得較為完善，參閱s j w r i g h t ( 1 9 9 7 ) t 1 1 與y y y e ( 1 9 9 7 ) 【2 】，這里不 再贅述本節(jié)僅對(duì)原始對(duì)偶方法及修正l a g r a n g e 函數(shù)方法在非線性優(yōu)化領(lǐng)域中的研究 現(xiàn)狀進(jìn)行綜述 首先以下述非線性規(guī)劃問(wèn)題為例說(shuō)明對(duì)偶方法的含義 其中f ：研h 礬，h ： k u h n t u c k e r 條件是 v ；l ( x ，u ， ) = 0 ， ( z ) = 0 ，g ( x ) 0 ， v i g i ( x ) = 0 ，i ；l ，m ， 挑0 ，i = 1 ，m ， s t h ( x ) = 0 ，( 1 1 ) g ( z ) 0 ， 盈ph 刪，g ：刪。r _ 胛“是光滑函數(shù)問(wèn)題( 1 1 ) 的 ( 1 2 口) ( 1 2 6 ) ( 1 2 c ) ( 1 2 d ) 其中l(wèi) ( 。，u ， ) = ，( 。) + 7 1 , t ( 茹) + v t g ( 。) 是( 1 1 ) 的( 線性) l a g r a n g e 函數(shù)若某一算法 中的每一迭代點(diǎn)均近似地滿足( 1 2 b ) 且使，( z ) 或其效益函數(shù)下降。則這一算法屬于原 始算法，因?yàn)橹灰笤甲兞? 近似) 可行；若某一算法中的每一迭代點(diǎn)均滿足( 1 2 a ) 與 ( 1 2 d ) ，逐步迭代到( 1 2 b ) 與( 1 2 c ) 最終被滿足，則這一算法為對(duì)偶算法，因?yàn)樗髮?duì) 偶變量u ， 是可行的；若某一算法中的每一迭代點(diǎn)均滿足( 1 2 a ) ，( 1 2 b ) 與( 1 2 d ) ，最終 迭代到( 1 2 c ) 被滿足或?qū)ε奸g隙消失，則這一算法是原始對(duì)偶算法，因?yàn)樗惴ㄒ笤?始變量及對(duì)偶變量均可行 最成功的對(duì)偶算法當(dāng)屬求解線性規(guī)劃的對(duì)偶單純形法( 見(jiàn)d a n t z i g ( 1 9 6 3 ) 1 a 1 ) 及g o l d - f a r b i d n a n i ( 1 9 8 3 ) a 求解嚴(yán)格凸二次規(guī)劃的對(duì)偶算法基于w b l f e ( 1 9 6 3 ) 1 5 j 對(duì)偶理 論，凸規(guī)劃的對(duì)偶算法往往是從對(duì)偶問(wèn)題出發(fā)而構(gòu)造的。其算法理論也比較成熟，見(jiàn) r o c k a f e u a r ( 1 9 7 1 ) 憫 1 大連理工大學(xué)博士學(xué)位論文：非線性優(yōu)化中的一類對(duì)偶算法的理論研究 隨著線性規(guī)劃內(nèi)點(diǎn)法理論與計(jì)算發(fā)展的日趨完善，人們把線性規(guī)劃原始一對(duì)偶內(nèi)點(diǎn) 法的思想用于求解更為廣泛的問(wèn)題，如互補(bǔ)問(wèn)題，非凸非線性規(guī)劃問(wèn)題，等等 m h w r i g h t ( 1 9 9 1 ) 構(gòu)造了單調(diào)非線性互補(bǔ)問(wèn)題的原始一對(duì)偶算法；在此基礎(chǔ)上，m o n t e i r o ， p a n g w a n g ( i 9 9 2 ) 進(jìn)一步考慮了非單調(diào)非線性問(wèn)題的原始一對(duì)偶算法；s j w r i g h t ( 1 9 9 2 ) 對(duì)線性約束的非線性規(guī)劃問(wèn)題進(jìn)行了探討，并給出了相應(yīng)的原始一對(duì)偶算法； l a s d o n ，y u & p l u m m e r ( 1 9 9 2 ) 建立了多種求解一般約束非線性規(guī)劃問(wèn)題的原始- 對(duì)偶 算法；y a m a s h i t a ( 1 9 9 2 ) 建立了一種求解一般約束問(wèn)題的原始對(duì)偶算法，并且進(jìn)行了 相應(yīng)的收斂性分析九十年代初期，在非線性優(yōu)化領(lǐng)域中有關(guān)原始對(duì)偶方法的研究工 作還有m c c o r m i c k ( 1 9 9 1 ) 建立的非線性原始一對(duì)偶算法及其相應(yīng)的超線性收斂理論； k o j i m a ，m e g i d d o & n o m a ( 1 9 9 1 ) 建立的求解非線性互補(bǔ)問(wèn)題的同倫方法，等等參見(jiàn) 7 一【1 4 】 九十年代后期，人們對(duì)非線性優(yōu)化中的原始一對(duì)偶方法的研究更加深入，e 1 一b a k r y , t a p i a ，t s u c h i y a & z h a n g ( 1 9 9 6 ) 【1 5 】及g a y , o v e r t o n w r i g h t ( 1 9 9 8 ) 1 6 的工作具有代 表性 e 1 一b a k r y 等( 1 9 9 6 ) 考慮了形式為( 1 1 1 ) 的一般約束非線性規(guī)劃問(wèn)題他們建立了兩 種稍有差異但收斂性結(jié)果截然不同的原始一對(duì)偶算法第一種算法的思想基于問(wèn)題( 1 _ 1 ) 的k k t 條件，即( 1 2 a ) 一( 1 2 d ) 的松弛變量形式亦即， x ，y ，s ，z ) = v ；l ( x ，y ，z ) h ( x ) g ( 。) + 8 z s e 一“8 = 0 ，( 5 ，z ) 0 ，( 1 3 ) 其中p 0 為障礙參數(shù)， v 。l ( x ，y ，z ) = v f ( x ) + v ( 。) + v 口( z ) z ，z = d i a g l i 。億) ， s = d i a g ，! i 0 令乃= 一番裔，j = 1 ，m ，則同題 ( 1 4 ) 的k k t 條件為 ，v 捌則瑚、 g p ( $ ，y ，z ) = l ( 茹)l = o ， ( 1 5 ) 勛( 。) + p e 其中z = d i a g 。 。) 基于方程( 1 5 ) ，建立了相應(yīng)的原始對(duì)偶算法，詳細(xì)分析了算 法具體實(shí)施時(shí)會(huì)遇到的各種問(wèn)題，如當(dāng)求解( 1 5 ) 時(shí)某些重要矩陣可能會(huì)出現(xiàn)非正定情 況。擾動(dòng)參數(shù)_ “如何選取等，并且給出了相應(yīng)的處理策略g a y 等( 1 9 9 8 ) 進(jìn)行了大量 的數(shù)值實(shí)驗(yàn)，取得了數(shù)據(jù)詳盡的實(shí)驗(yàn)結(jié)果，這些結(jié)果充分說(shuō)明了原始一對(duì)偶方法具有很 大的潛力，值得進(jìn)一步研究 修正l a g - r a n g e 函數(shù)往往是根據(jù)所解決問(wèn)題的特點(diǎn)及相應(yīng)的經(jīng)典l a g r a n g e 函數(shù)( 即 線性l a g r a n g e 函數(shù)) 形式而建立的具有光滑增廣l a g r a n g e 函數(shù)( 包括其在內(nèi)) 性質(zhì)的函 數(shù)，它可以用來(lái)建立對(duì)偶算法給定可行的初始對(duì)偶變量，迭代過(guò)程中保證對(duì)偶變量的可 行性對(duì)于給定的對(duì)偶變量，求解修正l a g r a n g e 函數(shù)的極小化問(wèn)題，得到原始近似解， 然后根據(jù)所求得的原始近似解對(duì)對(duì)偶變量進(jìn)行修正，然后進(jìn)行循環(huán)，最終得到原始最優(yōu) 解與對(duì)偶最優(yōu)解可見(jiàn)修正l a g r a n g e 函數(shù)方法是一種對(duì)偶方法 早期的求解約束非線性規(guī)劃問(wèn)題的方法都是罰函數(shù)法，如c o u r a n t ( 1 9 4 3 ) ，f d s c h ( 1 9 5 5 ) ，c a r r o l l ( 1 9 6 1 ) 等，見(jiàn) 17 】一 2 0 】它的基本思想是將約束問(wèn)題非約束化但是由于 這些罰函數(shù)法一般要求罰因子趨于無(wú)窮大( 或0 ) 或者需要求解非光滑最優(yōu)化問(wèn)題，所以 無(wú)約束優(yōu)化的算法在數(shù)值上常遇到困難，而且收斂速度也不快針對(duì)這些問(wèn)題，h e s t e n e s ( 1 9 6 9 ) ，p o w e l l ( 1 9 6 9 ) 以及h a a r h o f f b u y s ( 1 9 7 0 ) 分別提出了著名的乘子法，用來(lái)解決 等式約束非線性規(guī)劃問(wèn)題，見(jiàn) 2 1 - 【2 3 】最初的乘子法是基于二次增廣l a g r a n g e 函數(shù)( 形 式最簡(jiǎn)單的修正l a g r a n g e 函數(shù)) 建立的，每一次無(wú)約柬極小化增廣l a g r a n g e 函數(shù)之后， 利用前一次求得的解的信息對(duì)乘子進(jìn)行修正，如此重復(fù)上述過(guò)程，直到滿足一定的終止條 件二次增廣l a g r a n g e 函數(shù)法，即，最早的修正l a g r a n g e 函數(shù)方法這一方法的優(yōu)點(diǎn)在于 它克服了早期罰函數(shù)的病態(tài)問(wèn)題以及收斂速度較慢這些弱點(diǎn)但是，這幾位學(xué)者都沒(méi)有對(duì) 此方法進(jìn)行收斂性分析，參見(jiàn)v t p o l y a k n v 2 y e t ，y a k o v ( 1 9 7 3 ) 2 4 在一定的條件 下，p 0 1 y a k & t r e t y a k o v ( 1 9 7 3 ) 證明了存在罰參數(shù)的閥值，并且當(dāng)罰參數(shù)小于( 或大于) 這一閥值時(shí)，這一方法以幾何收斂率收斂到原始一對(duì)偶最優(yōu)解，同時(shí)給出了依賴于罰參數(shù) 的解的誤差上界r o c k a f e l l a x ( 1 9 7 3 ，1 9 7 4 ) 剛，嗍把h a a r h o f f & b u y s h e s t e n e s p o w e l l 的 3 盔壟望三盔堂璺圭堂垡堡塞：韭垡絲垡垡塑二鲞塑堡墨鯊箜里堡堡塞一一 思想又進(jìn)一步推廣應(yīng)用于不等式約束優(yōu)化問(wèn)題，得到般約束優(yōu)化問(wèn)題的乘子法理論有 關(guān)乘子法的詳細(xì)研究工作可參閱b e r t s e k a s ( 1 9 8 2 ) 2 7 的專著值得一提的是，b e r t s e k a s ( 1 9 s 2 ) 中關(guān)于凸規(guī)劃非二次懲罰函數(shù)法也屬于修正l a g r a n g e 函數(shù)方法 隨著人們對(duì)修正l a g r a n g e 函數(shù)方法的深入研究，該方法的優(yōu)越性逐漸顯示出來(lái)，尤 其是函數(shù)的形式也由復(fù)雜趨向于簡(jiǎn)單c h a r a l a r a b o u s ( 1 9 7 7 ) 建立了求解不等式約束非 線性規(guī)劃問(wèn)題的最小p 階函數(shù)，于1 9 7 9 年又建立了該函數(shù)的修正形式用來(lái)解決無(wú)約束 極大極小問(wèn)題，見(jiàn)【2 s 一 2 9 最小p 階函數(shù)確實(shí)有相當(dāng)好的性質(zhì)，并且由此建立的算法有 很好的收斂結(jié)果，計(jì)算上也有效，但函數(shù)形式較復(fù)雜，不利于計(jì)算p o l y a k ( 1 9 s s ) 3 0 】建 立了形式簡(jiǎn)單的求解無(wú)約束極大極小問(wèn)題1 2 1 i n $ m a x i 0 為罰參數(shù)，q = 如l k m ( x ) + 1 0 ，i = 1 ，m ) ，分析了這兩種函數(shù)在 k u t m - t n c h e r 點(diǎn)處具有光滑增廣l a g r a n g e 函數(shù)的性質(zhì)，并且證明了在適當(dāng)條件下，罰參 數(shù)存在閥值 0 ，當(dāng)k o 時(shí)，基于這兩種函數(shù)建立的算法均局部收斂于原始最優(yōu)解 與對(duì)偶最優(yōu)解，同時(shí)也給出了近似解的界值估計(jì)式p o l y a k & t e b o u l l e ( 1 9 9 7 ) a 2 曾基 于如下一類函數(shù) 1 旦 g ( 。，”，曲= ，( o ) + 二 ：銘i 妒( 鰳( 茹) ) ， p 西 建立了求解凸約束優(yōu)化問(wèn)題的n r ( n o n l i n e a rr e s a & h n 曲算| 法，其中p 0 為罰參數(shù)，妒 為滿足一定條件的二次連續(xù)可微函數(shù)，g 均為凸函數(shù)在一些凸性條件下以及一些適 當(dāng)?shù)募僭O(shè)條件下，證明了n f t 算法產(chǎn)生的對(duì)偶序列解全局收斂于最優(yōu)l a g r a n g e 乘子，而 相應(yīng)的原始序列解在e r g o d i c 意義下近似原始最優(yōu)解而這類算法也屬于修正l a g r a n g e 函數(shù)方法l i & s u n ( 2 0 0 0 ) 嘲對(duì)不等式約柬優(yōu)化同題進(jìn)行變形： m i n f ( x ) l g i ( x ) 6 j ) ， 4 塑! 童墮絲 其中，( z ) ，b j0 = 1 ，m ) 均太于0 ，g j ( x ) 0 = 1 ，m ) 為非負(fù)的，由此建立了p 一冪 l a g r a n g e 函數(shù) i l v ( x ，札) = m ) 他( z ) 】p _ 鴛) j = l 和部分p 一冪l a g r a n g e 函數(shù) ，n 島( 掣) = m ) + 嘶 脅( 茹) 一圬) j = l 其中p 0 為罰參數(shù)由他們對(duì)這兩個(gè)函數(shù)性質(zhì)的分析結(jié)果知道這兩個(gè)函數(shù)也是修正 l a g r a n g e 函數(shù)由此可見(jiàn)，對(duì)于不同類型的優(yōu)化問(wèn)題可以建立不同形式的修正l a g r a n g e 函數(shù)，而且對(duì)于同一類優(yōu)化問(wèn)題，也存在不同形式的修正l a g r a n g e 函數(shù)，并且可以由此 建立相應(yīng)的算法另一方面，對(duì)于同一類修正l a g r a n g e 函數(shù)方法，可以通過(guò)應(yīng)用不同的 修正l a g r a n g e 函數(shù)形式來(lái)解決不同類型的優(yōu)化問(wèn)題，例如?？梢詰?yīng)用修正l a g r a n g e 函 數(shù)形式( 1 6 ) 來(lái)解決無(wú)約束極大極小問(wèn)題，應(yīng)用修正l a g r a n g e 函數(shù)形式( 1 7 ) 或( 1 8 ) 來(lái) 解決不等式優(yōu)化問(wèn)題等等 1 2 本文的研究背景及取得的主要結(jié)果 正如第1 1 節(jié)所介紹的，原始對(duì)偶方法目前已成為眾多學(xué)者的研究熱點(diǎn)，并且它的 數(shù)值表現(xiàn)也頗吸引人但我們?nèi)菀装l(fā)現(xiàn)各種原始一對(duì)偶算法形式在具體實(shí)施時(shí)不可避免 地都會(huì)遇到許多復(fù)雜問(wèn)題，如它們要求原始變量與對(duì)偶變量均嚴(yán)格初始可行，而這一問(wèn) 題的解決就需要耗費(fèi)相當(dāng)大的工作量；尋找搜索方向時(shí)，要涉及原始對(duì)偶線性系統(tǒng)方 程的形式確定及其求解技巧問(wèn)題；確定搜索步長(zhǎng)時(shí)，不僅要考慮到原始變量與對(duì)偶變量 均可行而且還要使迭代點(diǎn)滿足勢(shì)函數(shù)下降的條件，而勢(shì)函數(shù)又是一個(gè)值得研究的問(wèn)題； 原始一對(duì)偶方法還要求在選取障礙參數(shù)時(shí)不僅需要考慮到使迭代朝障礙軌道進(jìn)行而且還 需要考慮到盡可能地使解的誤差最小，等等而諸如第1 1 節(jié)所介紹的修正l a g r a n g e 函 數(shù)的形式較簡(jiǎn)單，而且相應(yīng)的算法也具有很好的收斂性質(zhì)鑒于這樣一些原因，本文的 研究對(duì)象是非線性優(yōu)化中的一類對(duì)偶方法，即。修正l a g r a n g e 函數(shù)方法本文取得的結(jié) 果如下： 第2 章構(gòu)造了一類求解不等式約束非線性規(guī)劃問(wèn)題的對(duì)偶算法在適當(dāng)?shù)臈l件下， 論證了這類對(duì)偶算法的局部收斂性理論，并給出了原始一對(duì)偶序列解的誤差上界經(jīng)過(guò) 仔細(xì)推證，發(fā)現(xiàn)p o l y a k ( 1 9 9 2 ) 的修正障礙函數(shù)算法及b e r t s e k a s ( 1 9 8 2 ) 的增廣l a g r a n g e 函數(shù)算法是這類算法的特例基于p o l y a k ( 1 9 8 8 ) 求解極大極小問(wèn)題的光滑函數(shù)方法，第 2 章還構(gòu)造了一個(gè)求解不等式約束非線性規(guī)劃問(wèn)題的對(duì)偶算法這個(gè)對(duì)偶算法的形式比 較簡(jiǎn)單并且不需要考慮初始點(diǎn)的可行性第2 章對(duì)這一對(duì)偶算法的收斂性進(jìn)行了精細(xì)證 盔重型王盔堂堡圭堂垡絲窒：韭垡堡垡垡主塑二耋塑苧婆塑望堡受塞 明，對(duì)它所基于的勢(shì)函數(shù)的h e s s e 陣的條件數(shù)作出了估計(jì)而且這一個(gè)對(duì)偶算法也屬于 我們建立的這一類對(duì)偶算法 求解無(wú)約束極大極小問(wèn)題的光滑化方法是一類頗受青睞的方法，如 l i ( 1 9 9 2 ，1 9 9 7 ) 1 3 4 】，刪建立的凝聚函數(shù)法在工程計(jì)算中就很有效 z h a n g & t a n g ( 1 9 9 7 ) 例 對(duì)l i 的方法進(jìn)行變形，基于b e r t s e k a s ( 1 9 8 2 ) 的罰函數(shù)構(gòu)造了一個(gè)對(duì)偶算法它既是一 種光滑化方法，也是一種修正l a g r a n g e 函數(shù)方法雖然z h a “g & t a n g ( 1 9 9 7 ) 討論了這 一方法的性質(zhì)，但沒(méi)有給出該方法的收斂性證明，也沒(méi)有進(jìn)行有效的數(shù)值實(shí)驗(yàn)第3 章給 出了這一對(duì)偶算法的精細(xì)的收斂性結(jié)果在j a c o b i 唯一性條件下，證明了罰參數(shù)存在一 閥值，當(dāng)罰參數(shù)小于這一閩值時(shí)，對(duì)偶算法產(chǎn)生的序列局部收斂到問(wèn)題的k u h n t u c k e r 解，并且給出了參數(shù)解的估計(jì)公式還分析了含參數(shù)的勢(shì)函數(shù)的h e s s e 陣的條件數(shù)與罰 參數(shù)之間的關(guān)系，這有助于我們?cè)谶M(jìn)行效值實(shí)驗(yàn)時(shí)選取適當(dāng)?shù)牧P參數(shù) 第2 ，3 章討論的對(duì)偶算法的第2 步都需要精確地求解一無(wú)約束極小化同題，這在實(shí) 際計(jì)算中是很費(fèi)時(shí)并且是很難實(shí)現(xiàn)的為此，第4 章建立了不需精確求解勢(shì)函數(shù)的無(wú)約 束極小化問(wèn)題的對(duì)偶算法，即，在實(shí)際計(jì)算中對(duì)該步進(jìn)行修正的對(duì)偶算法我們證明了這 些修正的對(duì)偶算法仍然具有很好的收斂性質(zhì)，即同前兩章的對(duì)偶算法的收斂結(jié)果相同 第4 章還進(jìn)一步構(gòu)造了求解般約束非線性規(guī)劃問(wèn)題的對(duì)偶算法給出了這個(gè)對(duì)偶算法 的局部收斂性結(jié)果，并且估計(jì)了所構(gòu)造的修正l a g r a n g e 函數(shù)的h e s s e 陣的條件數(shù)，表明 它是依賴于罰參數(shù)的 前三章建立的對(duì)偶算法的收斂性結(jié)果在理論上是很完善的。但在實(shí)際問(wèn)題的計(jì)算中 它們是否有效，需要數(shù)值實(shí)驗(yàn)來(lái)證實(shí)第5 章分別對(duì)這些算法進(jìn)行了大量的數(shù)值實(shí)驗(yàn) 數(shù)值實(shí)驗(yàn)表明了這些對(duì)偶算法是有效的，同時(shí)也驗(yàn)證了取得的某些理論結(jié)果是正確的 6 苧! 窒至箜壅塑塞垡些墮塑塑二壅型堡蔓鱉 一 2 不等式約束優(yōu)化問(wèn)題的一類對(duì)偶算法 這一章首先給出了一類求解不等式約束優(yōu)化問(wèn)題的對(duì)偶算法的理論框架；在 某些適當(dāng)?shù)臈l件下，建立了該類方法的局部收斂性定理然后基于個(gè)指數(shù)型修正 l a g r a a g e 函數(shù)建立了個(gè)具體的對(duì)偶算法，并目發(fā)現(xiàn)它是這類對(duì)偶方法的特例進(jìn)一 步對(duì)這一對(duì)偶算法的收斂性進(jìn)行了精細(xì)分析，并且又分析了該指數(shù)型修正l a g t a n g e 函數(shù)的h e s s e 陣的條件數(shù)與罰參數(shù)之間的關(guān)系 2 1 一類構(gòu)造性對(duì)偶算法 在這一節(jié)，我們構(gòu)造了一類求解不等式約束優(yōu)化問(wèn)題的對(duì)偶算法證明了在適當(dāng)?shù)臈l 件下，勢(shì)函數(shù)的罰參數(shù)存在一個(gè)閥值，當(dāng)罰參數(shù)小于這個(gè)闊值時(shí)，由這一類方法所產(chǎn)生的 序列局部收斂到問(wèn)題的k u h n - t u c k e r 解，并且我們也建立了解的依賴于罰參數(shù)的誤差上 界驗(yàn)證了p o l y a k ( 1 9 9 2 ) 的兩種修正障礙函數(shù)算法與b e r t s e k a s ( 1 9 8 2 ) 的增廣l a g r a n g e 函數(shù)算法都是這類算法的特例，同時(shí)也驗(yàn)證了第2 2 節(jié)將要介紹的對(duì)偶算法也是這類算 法的特例 2 1 1 引言 考慮如下的不等式約束優(yōu)化問(wèn)題 血“弛! 。、m 1 ) s t z q = $ | 9 ( z ) so ) ， 、7 其中f ：四h 廚，g ：聹1 - 一刀“均是二次連續(xù)可微函數(shù)求解這一問(wèn)題的傳統(tǒng)數(shù) 值方法有很多，如，f i a c c o m c c o r m i c k ( 1 9 6 8 ) 建立的序列無(wú)約束極小化方法，h a n ( 1 9 7 6 ，1 9 7 7 ) ) 建立的序列二次規(guī)劃方法，b e r t s e k a s ( 1 9 8 2 ) 建立的乘子法，等等近年來(lái) 對(duì)求解這一問(wèn)題的原始一對(duì)偶算法的研究已成為非線性規(guī)劃領(lǐng)域的新的研究熱點(diǎn)，有代 表性的如緒論所述，e 1 - b a k r y , t a p i a ，t s u c h i y a z h a n g ( 1 9 9 6 ) ，y a m a s h i t a ( 1 9 9 2 ，1 9 9 6 ， 1 9 9 z ) ，g a y , o v e r t o n w r i g h t ( 1 9 9 8 ) ，等等 通過(guò)對(duì)p o l y a k ( 1 9 9 2 ) 建立的修正障礙函數(shù)的研究，我們構(gòu)造如下一類修正l a g r a n g e 函數(shù) m 日( z ，”，t ) = ，( z ) + ：( 或( 囂) ，讓，t ) ，( 2 1 2 ) i = 1 其中t 0 是罰參數(shù)，西：皿皿皿 o ) - _ 肥是光滑函數(shù)本節(jié)將要討論的對(duì)偶 算法的主要特點(diǎn)是它不需尋找問(wèn)題( 2 1 1 ) 的初始可行點(diǎn)而這一點(diǎn)使得它在實(shí)際計(jì)算中 7 大連理工大學(xué)博士學(xué)位論文t 非線性優(yōu)化中的一類對(duì)偶算法的理論研究 比可行方向法及其他需要初始可行點(diǎn)的方法具有更大的吸引力，這主要是因?yàn)閷ふ覇?wèn)題 ( 2 1 1 ) 的初始可行點(diǎn)在后者中往往占有很大的工作量第2 1 2 節(jié)給出后面章節(jié)中所需的 預(yù)備知識(shí)在第2 1 3 節(jié)中我們建立些適當(dāng)?shù)臈l件，并且發(fā)現(xiàn)在這些條件下，h ( x ，t ) 具有很好的性質(zhì)第2 1 。4 節(jié)建立一類對(duì)偶算法及其相應(yīng)的的局部收斂性理論第2 1 。5 節(jié)驗(yàn)證了p o l y a k ( 1 9 9 2 ) 的修正障礙函數(shù)法與b e r t s e l m s ( 1 9 8 2 ) 的增廣l a g r a n g e 函數(shù)法 都是這類對(duì)偶算法的特例，并且發(fā)現(xiàn)將在第2 2 節(jié)中介紹的求解問(wèn)題( 2 1 1 ) 的基于指數(shù) 型修正l a g r a n g e 函數(shù)而建立的對(duì)偶算法也是這類對(duì)偶算法的個(gè)特例， 2 1 2 預(yù)備知識(shí) 我們主要考慮問(wèn)題( 2 1 1 ) 的局部極小點(diǎn)令三( z ，牡) = f ( x ) + 蘭lu l g i ( x ) 表示這 一問(wèn)題的l a g r a n g e 函數(shù)，b ( z ) = 矧肌( z ) = 0 ，i = 1 ，m ) 表示約柬函數(shù)在髫處的緊 指標(biāo)集，礦= ( 礦，4 ) 表示問(wèn)題( 2 。1 1 ) 的k u h n t u c k e r 對(duì)，并且礦滿足如下條件t ( a ) 為方便起見(jiàn)，記日( ) = 1 ，r ( r m ) ； ( b ) k u h n - t u c k e r 條件在礦成立，即t v 。i ( x + ，牡) = 0 ，礦0 ， 讓孫( 礦) = 0 ，g i ( x ) 0 ，i = 1 ，m ( c ) 嚴(yán)格互補(bǔ)松弛條件成立，邵： 玨； 0 ，i b ( x ) ； ( d ) v 鯫( 。+ ) l i b ( x + ) ) 是組線性無(wú)關(guān)的向量； ( e ) 對(duì)于任意滿足v g ( x 4 ) t y = 0 ，i b ( x + ) 的y 0 ，存在常數(shù)a o 0 ，使得 y t v ：l ( x + ，u ) a o ir y l l 2 成立 下面的引理出自b e r t s e k a s ( 1 9 8 2 ) ，該引理在以后耍建立的對(duì)偶算法中起著熏要作 用 引理2 1 1 令a 是皿叩上的對(duì)稱矩陣，q 是四”上的半正定矩陣假如對(duì)任意滿 足。t 日茁= 0 的。0 ，總有x t a x 0 成立，則存在常數(shù)e 0 與p 0 ，使得對(duì)任意的 c i ，成立著 戶( a + c q ) z 1 i z f l 2 ，v z 四。 下面引入一些以后論述中要用到的符號(hào)： v 亙( z ) = ( v 9 ，( 。) ，v 辦( 。) ) ，珊( z ) = ( v 褂z ( 。) ，v 孫) 8 第2 章 丕堇壅塑塞垡些堅(jiān)墮墮二耋型堡苧鱉一 礦 a i ( 口，u ，t ) a ( z ，讓，t ) s ( x + ，e ) 四2 盥m + ( ：，：) t 艫，面= ( 釷i ，牡：) r 皿7 ， 蒜( 蹴現(xiàn)待h - j m ，t 0 ( a 1 ( 茹，u ，t ) ，a 。( 。，u ，t ) ) t 況“，u + = d i a g l _ 0 ，t o ； ( a 6 ) l 象( o ，b ，t ) i m ( 其中m 0 是常數(shù)) ，b 0 ，t o ； ( a 7 ) 存在t o 0 ，使得對(duì)任意的o 0 ，使得當(dāng)i t l ( 0 ，旬時(shí)，v ：日( 礦，t + ，t ) 是嚴(yán)格正定矩陣 證明：計(jì)算得 m 7 v ：酢，u 一= v 2 m ) + 善嵩湎川) 鏟咖) + + c g g , ( 坐x ) o g 一, ( x ) ( m ( z ) m ，t ) v 璣( 茁) v g , ( z ) t 、，、山，仙l ，。，l 、山，、山， 于是 v ：。日( 衛(wèi)+ ，u + ，t ) = v ：工( 茹。，牡+ ) + ，7 ( f t l ) v 口( z + ) v g ( x + ) r 根據(jù)條件( e ) 與引理2 1 1 ，易知存在 0 ，使得當(dāng) t i ( o ，旬時(shí)，v ：胃( 礦，u + ，t ) 是嚴(yán)格 正定的口 注2 1 1 由日( z ，u ，t ) 的性質(zhì)。我們可知當(dāng)i t 充分小時(shí)，。是日( z ，u ，t ) 的