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

摘要 本文主要研究非線性優(yōu)化中的一類對偶算法，包括無約束極大極小問 題的對偶算法和約束非線性規(guī)劃問題的一類對偶算法的理論與相應的數(shù)值 實現(xiàn)本文取得的主要結果可概括如下t 1 第2 章建立求解不等式約束優(yōu)化問題的一類對偶算法的理論框架在 適當?shù)募僭O條件下，證明了該類算法的局部收斂性質，并給出近似解 的誤差界驗證了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ù)型勢函數(shù)建立了相應的對偶算法，它也屬于這類對偶算法對這一對 偶算法，給出了精細的收斂性結果，同時估計了勢函數(shù)的h e s s e 陣的條 件數(shù)，它依賴于罰參數(shù) 2 第3 章給出無約束極大極小問題的一個對偶算法的收斂理論給出一 個基于b e r t s e k a s ( 1 9 8 2 ) 罰函數(shù)的求解無約束極大極小問題的對偶算 法證明罰參數(shù)存在一個閥值，當罰參數(shù)小于這一閥值時，該對偶算法 產生的序列局部收斂到問題的k u h n t u k e r 點，并建立了參數(shù)解的誤差 估計式同樣估計了罰函數(shù)的h e s s e 陣的條件數(shù)。它也依賴于罰參數(shù) 3 第4 章考慮算法的實現(xiàn)技術與算法的推廣首先針對前兩章的對偶算 法由于需要精確求解一系列無約束極小化問題，因而實際計算中很難 實現(xiàn)這一缺點，構造修正的對偶算法，即，關于勢函數(shù)的無約束極小化 問題無需精確求解的對偶算法證明這些修正的對偶算法仍具有同前 兩章的概念性對偶算法相同的收斂性結果我們還進一步構造了般 約束非線性規(guī)劃問題的對偶算法，建立了相應的局部收斂理論最后估 計了修正l a g r a n g e 函數(shù)的h e s s e 陣的條件數(shù)，它同樣依較于罰參數(shù) 4 第5 章對第2 章，第3 章及第4 章的對偶算法進行了數(shù)值實驗用這 些算法計算大量的規(guī)模不是很大的不等式約束優(yōu)化問題，無約束極大 極小同題，一般約束優(yōu)化問題，數(shù)值結果表明它們是有效的同時給出 的各種關于數(shù)值結果的表格驗證了取得的某些理論結果的正確性 關鍵詢：對偶算法，無約束極大極小問題，約束非線性規(guī)劃問題，修正l a g r a n g e 函數(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 緒論 綜述對偶方法中的原始一對偶方法及修正l a g r a n g e 函數(shù)方法的研究歷史及現(xiàn) 狀；介紹本文研究的非線性優(yōu)化中的一類對偶算法的研究背景，并列出取得的主要 結果 1 1 原始對偶方法與修正l a g r a n g e 函數(shù)方法 原始對偶方法是求解線性規(guī)劃及非線性規(guī)劃的重要方法這一方法在線性規(guī)射領 域中的理論已發(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é)僅對原始對偶方法及修正l a g r a n g e 函數(shù)方法在非線性優(yōu)化領域中的研究 現(xiàn)狀進行綜述 首先以下述非線性規(guī)劃問題為例說明對偶方法的含義 其中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ù)問題( 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ù)若某一算法 中的每一迭代點均近似地滿足( 1 2 b ) 且使，( z ) 或其效益函數(shù)下降。則這一算法屬于原 始算法，因為只要求原始變量( 近似) 可行；若某一算法中的每一迭代點均滿足( 1 2 a ) 與 ( 1 2 d ) ，逐步迭代到( 1 2 b ) 與( 1 2 c ) 最終被滿足，則這一算法為對偶算法，因為它要求對 偶變量u ， 是可行的；若某一算法中的每一迭代點均滿足( 1 2 a ) ，( 1 2 b ) 與( 1 2 d ) ，最終 迭代到( 1 2 c ) 被滿足或對偶間隙消失，則這一算法是原始對偶算法，因為算法要求原 始變量及對偶變量均可行 最成功的對偶算法當屬求解線性規(guī)劃的對偶單純形法( 見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 求解嚴格凸二次規(guī)劃的對偶算法基于w b l f e ( 1 9 6 3 ) 1 5 j 對偶理 論，凸規(guī)劃的對偶算法往往是從對偶問題出發(fā)而構造的。其算法理論也比較成熟，見 r o c k a f e u a r ( 1 9 7 1 ) 憫 1 大連理工大學博士學位論文：非線性優(yōu)化中的一類對偶算法的理論研究 隨著線性規(guī)劃內點法理論與計算發(fā)展的日趨完善，人們把線性規(guī)劃原始一對偶內點 法的思想用于求解更為廣泛的問題，如互補問題，非凸非線性規(guī)劃問題，等等 m h w r i g h t ( 1 9 9 1 ) 構造了單調非線性互補問題的原始一對偶算法；在此基礎上，m o n t e i r o ， p a n g w a n g ( i 9 9 2 ) 進一步考慮了非單調非線性問題的原始一對偶算法；s j w r i g h t ( 1 9 9 2 ) 對線性約束的非線性規(guī)劃問題進行了探討，并給出了相應的原始一對偶算法； l a s d o n ，y u & p l u m m e r ( 1 9 9 2 ) 建立了多種求解一般約束非線性規(guī)劃問題的原始- 對偶 算法；y a m a s h i t a ( 1 9 9 2 ) 建立了一種求解一般約束問題的原始對偶算法，并且進行了 相應的收斂性分析九十年代初期，在非線性優(yōu)化領域中有關原始對偶方法的研究工 作還有m c c o r m i c k ( 1 9 9 1 ) 建立的非線性原始一對偶算法及其相應的超線性收斂理論； k o j i m a ，m e g i d d o & n o m a ( 1 9 9 1 ) 建立的求解非線性互補問題的同倫方法，等等參見 7 一【1 4 】 九十年代后期，人們對非線性優(yōu)化中的原始一對偶方法的研究更加深入，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ī)劃問題他們建立了兩 種稍有差異但收斂性結果截然不同的原始一對偶算法第一種算法的思想基于問題( 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 ) ，建立了相應的原始對偶算法，詳細分析了算 法具體實施時會遇到的各種問題，如當求解( 1 5 ) 時某些重要矩陣可能會出現(xiàn)非正定情 況。擾動參數(shù)_ “如何選取等，并且給出了相應的處理策略g a y 等( 1 9 9 8 ) 進行了大量 的數(shù)值實驗，取得了數(shù)據(jù)詳盡的實驗結果，這些結果充分說明了原始一對偶方法具有很 大的潛力，值得進一步研究 修正l a g - r a n g e 函數(shù)往往是根據(jù)所解決問題的特點及相應的經典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ù)( 包括其在內) 性質的函 數(shù)，它可以用來建立對偶算法給定可行的初始對偶變量，迭代過程中保證對偶變量的可 行性對于給定的對偶變量，求解修正l a g r a n g e 函數(shù)的極小化問題，得到原始近似解， 然后根據(jù)所求得的原始近似解對對偶變量進行修正，然后進行循環(huán)，最終得到原始最優(yōu) 解與對偶最優(yōu)解可見修正l a g r a n g e 函數(shù)方法是一種對偶方法 早期的求解約束非線性規(guī)劃問題的方法都是罰函數(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 ) 等，見 17 】一 2 0 】它的基本思想是將約束問題非約束化但是由于 這些罰函數(shù)法一般要求罰因子趨于無窮大( 或0 ) 或者需要求解非光滑最優(yōu)化問題，所以 無約束優(yōu)化的算法在數(shù)值上常遇到困難，而且收斂速度也不快針對這些問題，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 ) 分別提出了著名的乘子法，用來解決 等式約束非線性規(guī)劃問題，見 2 1 - 【2 3 】最初的乘子法是基于二次增廣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ù)之后， 利用前一次求得的解的信息對乘子進行修正，如此重復上述過程，直到滿足一定的終止條 件二次增廣l a g r a n g e 函數(shù)法，即，最早的修正l a g r a n g e 函數(shù)方法這一方法的優(yōu)點在于 它克服了早期罰函數(shù)的病態(tài)問題以及收斂速度較慢這些弱點但是，這幾位學者都沒有對 此方法進行收斂性分析，參見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ù)的閥值，并且當罰參數(shù)小于( 或大于) 這一閥值時，這一方法以幾何收斂率收斂到原始一對偶最優(yōu)解，同時給出了依賴于罰參數(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 盔壟望三盔堂璺圭堂垡堡塞：韭垡絲垡垡塑二鲞塑堡墨鯊箜里堡堡塞一一 思想又進一步推廣應用于不等式約束優(yōu)化問題，得到般約束優(yōu)化問題的乘子法理論有 關乘子法的詳細研究工作可參閱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ī)劃非二次懲罰函數(shù)法也屬于修正l a g r a n g e 函數(shù)方法 隨著人們對修正l a g r a n g e 函數(shù)方法的深入研究，該方法的優(yōu)越性逐漸顯示出來，尤 其是函數(shù)的形式也由復雜趨向于簡單c h a r a l a r a b o u s ( 1 9 7 7 ) 建立了求解不等式約束非 線性規(guī)劃問題的最小p 階函數(shù)，于1 9 7 9 年又建立了該函數(shù)的修正形式用來解決無約束 極大極小問題，見【2 s 一 2 9 最小p 階函數(shù)確實有相當好的性質，并且由此建立的算法有 很好的收斂結果，計算上也有效，但函數(shù)形式較復雜，不利于計算p o l y a k ( 1 9 s s ) 3 0 】建 立了形式簡單的求解無約束極大極小問題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 點處具有光滑增廣l a g r a n g e 函數(shù)的性質，并且證明了在適當條件下，罰參 數(shù)存在閥值 0 ，當k o 時，基于這兩種函數(shù)建立的算法均局部收斂于原始最優(yōu)解 與對偶最優(yōu)解，同時也給出了近似解的界值估計式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)化問題的n r ( n o n l i n e a rr e s a & h n 曲算| 法，其中p 0 為罰參數(shù)，妒 為滿足一定條件的二次連續(xù)可微函數(shù)，g 均為凸函數(shù)在一些凸性條件下以及一些適 當?shù)募僭O條件下，證明了n f t 算法產生的對偶序列解全局收斂于最優(yōu)l a g r a n g e 乘子，而 相應的原始序列解在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 ) 嘲對不等式約柬優(yōu)化同題進行變形： m i n f ( x ) l g i ( x ) 6 j ) ， 4 塑! 童墮絲 其中，( z ) ，b j0 = 1 ，m ) 均太于0 ，g j ( x ) 0 = 1 ，m ) 為非負的，由此建立了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ù)由他們對這兩個函數(shù)性質的分析結果知道這兩個函數(shù)也是修正 l a g r a n g e 函數(shù)由此可見，對于不同類型的優(yōu)化問題可以建立不同形式的修正l a g r a n g e 函數(shù)，而且對于同一類優(yōu)化問題，也存在不同形式的修正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ù)形式來解決不同類型的優(yōu)化問題，例如。可以應用修正l a g r a n g e 函 數(shù)形式( 1 6 ) 來解決無約束極大極小問題，應用修正l a g r a n g e 函數(shù)形式( 1 7 ) 或( 1 8 ) 來 解決不等式優(yōu)化問題等等 1 2 本文的研究背景及取得的主要結果 正如第1 1 節(jié)所介紹的，原始對偶方法目前已成為眾多學者的研究熱點，并且它的 數(shù)值表現(xiàn)也頗吸引人但我們容易發(fā)現(xiàn)各種原始一對偶算法形式在具體實施時不可避免 地都會遇到許多復雜問題，如它們要求原始變量與對偶變量均嚴格初始可行，而這一問 題的解決就需要耗費相當大的工作量；尋找搜索方向時，要涉及原始對偶線性系統(tǒng)方 程的形式確定及其求解技巧問題；確定搜索步長時，不僅要考慮到原始變量與對偶變量 均可行而且還要使迭代點滿足勢函數(shù)下降的條件，而勢函數(shù)又是一個值得研究的問題； 原始一對偶方法還要求在選取障礙參數(shù)時不僅需要考慮到使迭代朝障礙軌道進行而且還 需要考慮到盡可能地使解的誤差最小，等等而諸如第1 1 節(jié)所介紹的修正l a g r a n g e 函 數(shù)的形式較簡單，而且相應的算法也具有很好的收斂性質鑒于這樣一些原因，本文的 研究對象是非線性優(yōu)化中的一類對偶方法，即。修正l a g r a n g e 函數(shù)方法本文取得的結 果如下： 第2 章構造了一類求解不等式約束非線性規(guī)劃問題的對偶算法在適當?shù)臈l件下， 論證了這類對偶算法的局部收斂性理論，并給出了原始一對偶序列解的誤差上界經過 仔細推證，發(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 ) 求解極大極小問題的光滑函數(shù)方法，第 2 章還構造了一個求解不等式約束非線性規(guī)劃問題的對偶算法這個對偶算法的形式比 較簡單并且不需要考慮初始點的可行性第2 章對這一對偶算法的收斂性進行了精細證 盔重型王盔堂堡圭堂垡絲窒：韭垡堡垡垡主塑二耋塑苧婆塑望堡受塞 明，對它所基于的勢函數(shù)的h e s s e 陣的條件數(shù)作出了估計而且這一個對偶算法也屬于 我們建立的這一類對偶算法 求解無約束極大極小問題的光滑化方法是一類頗受青睞的方法，如 l i ( 1 9 9 2 ，1 9 9 7 ) 1 3 4 】，刪建立的凝聚函數(shù)法在工程計算中就很有效 z h a n g & t a n g ( 1 9 9 7 ) 例 對l i 的方法進行變形，基于b e r t s e k a s ( 1 9 8 2 ) 的罰函數(shù)構造了一個對偶算法它既是一 種光滑化方法，也是一種修正l a g r a n g e 函數(shù)方法雖然z h a “g & t a n g ( 1 9 9 7 ) 討論了這 一方法的性質，但沒有給出該方法的收斂性證明，也沒有進行有效的數(shù)值實驗第3 章給 出了這一對偶算法的精細的收斂性結果在j a c o b i 唯一性條件下，證明了罰參數(shù)存在一 閥值，當罰參數(shù)小于這一閩值時，對偶算法產生的序列局部收斂到問題的k u h n t u c k e r 解，并且給出了參數(shù)解的估計公式還分析了含參數(shù)的勢函數(shù)的h e s s e 陣的條件數(shù)與罰 參數(shù)之間的關系，這有助于我們在進行效值實驗時選取適當?shù)牧P參數(shù) 第2 ，3 章討論的對偶算法的第2 步都需要精確地求解一無約束極小化同題，這在實 際計算中是很費時并且是很難實現(xiàn)的為此，第4 章建立了不需精確求解勢函數(shù)的無約 束極小化問題的對偶算法，即，在實際計算中對該步進行修正的對偶算法我們證明了這 些修正的對偶算法仍然具有很好的收斂性質，即同前兩章的對偶算法的收斂結果相同 第4 章還進一步構造了求解般約束非線性規(guī)劃問題的對偶算法給出了這個對偶算法 的局部收斂性結果，并且估計了所構造的修正l a g r a n g e 函數(shù)的h e s s e 陣的條件數(shù)，表明 它是依賴于罰參數(shù)的 前三章建立的對偶算法的收斂性結果在理論上是很完善的。但在實際問題的計算中 它們是否有效，需要數(shù)值實驗來證實第5 章分別對這些算法進行了大量的數(shù)值實驗 數(shù)值實驗表明了這些對偶算法是有效的，同時也驗證了取得的某些理論結果是正確的 6 苧! 窒至箜壅塑塞垡些墮塑塑二壅型堡蔓鱉 一 2 不等式約束優(yōu)化問題的一類對偶算法 這一章首先給出了一類求解不等式約束優(yōu)化問題的對偶算法的理論框架；在 某些適當?shù)臈l件下，建立了該類方法的局部收斂性定理然后基于個指數(shù)型修正 l a g r a a g e 函數(shù)建立了個具體的對偶算法，并目發(fā)現(xiàn)它是這類對偶方法的特例進一 步對這一對偶算法的收斂性進行了精細分析，并且又分析了該指數(shù)型修正l a g t a n g e 函數(shù)的h e s s e 陣的條件數(shù)與罰參數(shù)之間的關系 2 1 一類構造性對偶算法 在這一節(jié)，我們構造了一類求解不等式約束優(yōu)化問題的對偶算法證明了在適當?shù)臈l 件下，勢函數(shù)的罰參數(shù)存在一個閥值，當罰參數(shù)小于這個闊值時，由這一類方法所產生的 序列局部收斂到問題的k u h n - t u c k e r 解，并且我們也建立了解的依賴于罰參數(shù)的誤差上 界驗證了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ù)算法都是這類算法的特例，同時也驗證了第2 2 節(jié)將要介紹的對偶算法也是這類算 法的特例 2 1 1 引言 考慮如下的不等式約束優(yōu)化問題 血“弛! 。、m 1 ) s t z q = $ | 9 ( z ) so ) ， 、7 其中f ：四h 廚，g ：聹1 - 一刀“均是二次連續(xù)可微函數(shù)求解這一問題的傳統(tǒng)數(shù) 值方法有很多，如，f i a c c o m c c o r m i c k ( 1 9 6 8 ) 建立的序列無約束極小化方法，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 ) 建立的乘子法，等等近年來 對求解這一問題的原始一對偶算法的研究已成為非線性規(guī)劃領域的新的研究熱點，有代 表性的如緒論所述，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 ) ，等等 通過對p o l y a k ( 1 9 9 2 ) 建立的修正障礙函數(shù)的研究，我們構造如下一類修正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é)將要討論的對偶 算法的主要特點是它不需尋找問題( 2 1 1 ) 的初始可行點而這一點使得它在實際計算中 7 大連理工大學博士學位論文t 非線性優(yōu)化中的一類對偶算法的理論研究 比可行方向法及其他需要初始可行點的方法具有更大的吸引力，這主要是因為尋找問題 ( 2 1 1 ) 的初始可行點在后者中往往占有很大的工作量第2 1 2 節(jié)給出后面章節(jié)中所需的 預備知識在第2 1 3 節(jié)中我們建立些適當?shù)臈l件，并且發(fā)現(xiàn)在這些條件下，h ( x ，t ) 具有很好的性質第2 1 。4 節(jié)建立一類對偶算法及其相應的的局部收斂性理論第2 1 。5 節(jié)驗證了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ù)法 都是這類對偶算法的特例，并且發(fā)現(xiàn)將在第2 2 節(jié)中介紹的求解問題( 2 1 1 ) 的基于指數(shù) 型修正l a g r a n g e 函數(shù)而建立的對偶算法也是這類對偶算法的個特例， 2 1 2 預備知識 我們主要考慮問題( 2 1 1 ) 的局部極小點令三( z ，牡) = f ( x ) + 蘭lu l g i ( x ) 表示這 一問題的l a g r a n g e 函數(shù)，b ( z ) = 矧肌( z ) = 0 ，i = 1 ，m ) 表示約柬函數(shù)在髫處的緊 指標集，礦= ( 礦，4 ) 表示問題( 2 。1 1 ) 的k u h n t u c k e r 對，并且礦滿足如下條件t ( a ) 為方便起見，記日( ) = 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 ) 嚴格互補松弛條件成立，邵： 玨； 0 ，i b ( x ) ； ( d ) v 鯫( 。+ ) l i b ( x + ) ) 是組線性無關的向量； ( e ) 對于任意滿足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 ) ，該引理在以后耍建立的對偶算法中起著熏要作 用 引理2 1 1 令a 是皿叩上的對稱矩陣，q 是四”上的半正定矩陣假如對任意滿 足。t 日茁= 0 的。0 ，總有x t a x 0 成立，則存在常數(shù)e 0 與p 0 ，使得對任意的 c i ，成立著 戶( a + c q ) z 1 i z f l 2 ，v z 四。 下面引入一些以后論述中要用到的符號： v 亙( z ) = ( v 9 ，( 。) ，v 辦( 。) ) ，珊( z ) = ( v 褂z ( 。) ，v 孫) 8 第2 章 丕堇壅塑塞垡些堅墮墮二耋型堡苧鱉一 礦 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 ，使得對任意的o 0 ，使得當i t l ( 0 ，旬時，v ：日( 礦，t + ，t ) 是嚴格正定矩陣 證明：計算得 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 ，使得當 t i ( o ，旬時，v ：胃( 礦，u + ，t ) 是嚴格 正定的口 注2 1 1 由日( z ，u ，t ) 的性質。我們可知當i t 充分小時，。是日( z ，u ，t ) 的