（運籌學(xué)與控制論專業(yè)論文）一類新的信賴域濾子sqp算法.pdf

上海大學(xué)碩士學(xué)位論文 摘要 約束非線性規(guī)劃問題是最優(yōu)化領(lǐng)域中重要的研究課題，許多實際問題都可 以化為約束非線性規(guī)劃問題。它有很多實際的應(yīng)用價值：在應(yīng)用數(shù)學(xué)方面，可 以應(yīng)用到約束擬合和優(yōu)化控制等領(lǐng)域；在物理學(xué)方面，可以應(yīng)用到光學(xué)和流體 力學(xué)等方面；此外還可以應(yīng)用到化學(xué)、工程學(xué)、計算機科學(xué)等學(xué)科。由此可見 它的重要性。 到了二十世紀七十年代后期，序列二次規(guī)劃( s q p ) 已成為解非線性最優(yōu) 化問題的一種最常見、最有效的方法。我們知道s o p 方法具有類似牛頓法的快 速收斂性。但傳統(tǒng)的s q p ( 無論是線搜索s q p 還是信賴域s q p ) 都存在價值函 數(shù)如何選取的問題，而大多數(shù)的價值函數(shù)都含有一個罰因子，該罰因子的選取 一直是s q p 問題的一個難點，選得過大或過小都會對算法產(chǎn)生不良的影響。為 了克服以上的困難，f l e t c h e r 在 8 中提出了一種新的思想，即把濾子( f i l t e r ) 和信賴域s q p 相結(jié)合，不需要選取罰因子。一個重要的概念就是如果試探點能 降低目標函數(shù)值或約束違反度的值，那么該點就被算法接受，而不像價值函數(shù) 將兩者結(jié)合。在1 9 9 8 年，針對濾子信賴域的s q p 方法，f l e t e r 等人給出的運 算結(jié)果也是很令人鼓舞的。緊隨其后，f l e t e r 等人又給出了相關(guān)算法的全局收 斂性的證明。1 9 9 9 年，f l e t e r , g o u l d ，l e f f e r 和t o i n t 在 9 對 8 中的算法有所 改進，給出兩種濾子s o p 算法并證明了他們的全局收斂性。在1 9 9 9 年g f l e t e r , s g o u l d ，和p t o i n t 在 4 1 中提出了一種濾子序列線性規(guī)劃( s l p ) 算法( 即帶 濾子的序列線性規(guī)劃) 并證明了其全局收斂性，該算法也避免使用罰函數(shù)。 本文主要提出了一類修改的帶n c p 函數(shù)的信賴域濾子s q p 算法，并給出 了它的全局收斂性證明，同時指出了其具有的超線性收斂性。主要的改進之處 是：用非線性互補函數(shù)替代了原來濾子中極小值函數(shù)構(gòu)成的約束違反度函數(shù)。濾 子s q p 與信賴域的結(jié)合最初由f l e t c h e r 在1 9 9 8 年提出，在本文中既沒有用罰 函數(shù)也沒有用可行性恢復(fù)階段。該算法基于多目標優(yōu)化的思想：一個迭代點被 接受當且僅當該點被濾子接受。而且如果搜索方向不斷用二階矯正步改進，算 法可以避免m a r a t o s 效應(yīng)，因此在每個局部解處可以獲得較快的局部收斂性。 數(shù)值結(jié)果顯示修改的算法是解決約束非線性規(guī)劃的一種有效算法。 v 上海大學(xué)碩士學(xué)位論文 本文結(jié)構(gòu)安排如下：第一章，我們將給出約束規(guī)劃中的重要理論，包括基 本的數(shù)學(xué)知識和最優(yōu)性條件，我們還給出了罰函數(shù)的研究概況及n c p 函數(shù)的定 義和簡單性質(zhì)；第二章給出兩類重要的算法：s q p 算法和信賴域算法；第三章 中給出了一類帶n c p 函數(shù)的n l p 濾子算法，該修改算法的收斂性證明及算例 在隨后的第四章給出：最后的第五章對這種算法進行了進一步的討論。 關(guān)鍵詞：非線性規(guī)劃，s q p ，n c p 函數(shù)，濾子，信賴域方法，全局收斂性。 v i 上海大學(xué)碩士學(xué)位論文 a b s t r a c t t h ec 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 gp r o b l e m ( n l p ) i sa ni m p o r t a n t r e s e a r c ht o p i ci no p t i m i z a t i o nf i e l d s m a n yp r a c t i c a lp r o b l e m sc a nb es u m m a r i z e d 嬲 t h ec 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 gp r o b l e m s i th a sm a n yp r a c t i c a la p p l i e d m e r i t s ：i na p p l i e dm a t h ，w ec a na p p l yi tt ot h ef i e l d so fc o n s t r a i n e ds i m u l a t i o na n d o p t i m i z a t i o nc o n t r o l ；i np h y s i c s ，i tc a nb ea p p l i e dt oo p t i c sa n dh y d r o d y n a m i c s ；i t a l s oc a nb ea p p l i e dt ot h ef i e l d so f c h e m i s t r y ，e n g i n e e r i n g ，c o m p u t e rs c i e n c ea n ds o o i l f r o mt h e s ew ec a ns e e t h ei m p o r t a n c eo fi t u pt ol a t e r1 9 7 0 s ，s e q u e n t i a lq u a d r a t i cp r o g r a m m i n g ( s q p ) i so n eo f t h e m o s t f a m i l i a ra n de r i e c t i v em e t h o d st os o l v en o n l i n e a rp r o g r a m m i n gp r o b l e m s w ek n o w s q pm e t h o d sh a v er a p i dc o n v e r g e n c el i k en e w t o nm e t h o d b u tt ot r a d i t i o n a ls q p m e t h o d s ( 1 i n es e a r c hs q p o rt r u s tr e g i o ns q p ) ，w ew o u l dm e e tap r o b l e mo f h o wt o c h o o s et h em e r i tf u n c t i o n s m o s tm e r i tf u n c t i o n sh a v ep e n a l t yf a c t o r s ，a n di t i sa d i f f i c u l tp o i n tt oc h o o s et h ef a c t o r s ，t o ob i g g e ro rt o os m a l l e rw i l ld oh a r mt ot h e a l g o r i t h m t og e to v e rt h i sd i f f i c u l t y , r f l e t c h e ra n ds l e y f f e rp r o p o s e dan e w t h o u g h ti n 8 】8 ，t h a ti st oc o m b i n et h ef i l t e ra n dt r u s tr e g i o ns q p , a n dn e e dn o tt o c h o o s et h ep e n a l t yf a c t o r s t h eu n d e r l y i n gc o n c e p ti st h a tt r i a lp o i n t sa r ea c c e p t e di f t h e yi m p r o v e t h eo b j e c t i v ef u n c t i o no rt h ec o n s t r a i n tv i o l a t i o ni ns t e a do f c o m b i n a t i o no f t h o s et w om e a s u r e sd e f i n e db yam e r i tf u n c t i o n t h ep r a c t i c a lr e s u l t s o ft h ef i l t e rt r u s tr e g i o ns q pm e t h o di n1 9 9 8w e r ee n c o u r a g i n g ，s u b s e q u e n t l yi n 1 9 9 9f l e t a r , g o u l d ，l e f f e ra n dt o i n ti m p r o v e dt h ea l g o r i t h mo f 【8 】i n 9 1 ，a n dg a v e t h ec o n v e r g e n c ep r o o f so f t w of i l t e rs q pm e t h o d s i n1 9 9 9 r f l e t e r ，s g o u l da n d e t o i n tp u tf o r w a r daf i l t e rs e q u e n t i a ll i n ep r o g r a m m i n ga l g o r i t h m ( s e q u e n t i a ll i n e p r o g r a m m i n gw i t hf i l t e r ) a n dp r o v e dt h eg l o b a lc o n v e r g e n c e ，i ta l s oa v o i d su s eo f m e r i tf u a c t i o n am o d i f i e dm e t h o do ft h en u s tr e g i o ns q p f i l t e rm e t h o dw i t hs o m en c p f u n c t i o ni sp r e s e n t e df o rc 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 gi nt h i sp a p e r , t h eg l o b a l c o n v e r g e n c eh a sb e e np r o v e da n dt h es u p e rl i n e a rc o n v e r g e n c eo ft h i sm e t h o dh a s 卜海大學(xué)碩士學(xué)位論文 b e e ng i v e n t h em a i nm o d i f i c a t i o nc o n s i s t so fu s i n gan e wf u n c t i o nn a m e dn c p f u n c t i o ni n s t e a do ft h ec o n s t r a i n tv i o l a t i o nf u n c t i o ni nt h ef i l t e r t h ef i l t e rs q p m e t h o d ，w h i c hi n c o r p o r a t e dw i t ht r u s tr e g i o nt e c h n i q u e ，w a si n h i a l l yp r o p o s e db y f l e t c h e ri n1 9 9 8 n e i t h e rp e n a l t yf u n c t i o nn o rr e s t o r a t i o np h a s e ( p r o p o s e di n1 9 9 8 f i r s t l y ) i su s e db yt h em e t h o di nt h i sp a p e r t h em e t h o di sb a s e do nt h ec o n c e p to f m u l t i o b j e c t i v eo p t i m i z a t i o nw h i c hm e a n st h a tat r i a lp o i n tc a l lb ea c c e p t e di fa n d o n l yi fe i t h e rt h eo b j e c tf u n c t i o nv a l u ed e c r e a s e so rt h em e a s u r eo fv i o l a t i o n c o n s t r a i n t sd e c r e a s e s f u r t h e r m o r e ，i ti ss h o w nt h a tt h ep r o p o s e dm e t h o dd o e sn o t s u f f e rf r o mt h em a r o t o se f f e c ti ft h es e a r c hd i r e c t i o n sa r ei m p r o v e db ys e c o n d o r d e rc o r r e c t i o n , s ot h a tt h ef a s tl o c a lc o n v e r g e n c et ot h el o c a ls o l u t i o n si sa c h i e v e d t h ea r r a n g e m e n to f t h i sp a p e ri s 勰f o l l o w s ：i nt h ef i r s tc h a p t e r , w ew i l lg i v et h e i m p o r t a n tt h e o r yo ft h ec o n s t r a i n e dp r o g r a m m i n gi n c l u d i n gb a s i cm a t h e m a t i c a l t h e o r ya n do p t i m i z a t i o nc o n d i t i o n a tt h es a m et i m ew ew i l lg i v et h es t u d yo f p e n a n yf u n c t i o n ，t h ed e f i n i t i o na n dt h ep r o p e r t yo fn c pf u n c t i o n i nt h es e c o n d c h a p t e r , w ew i l lg i v et w oi m p o r t a n ta l g o r i t h m s ：s q pa l g o r i t h ma n dt r u s tr e g i o n a l g o r i t h m am o d i f i e da l g o r i t h mo ft r u s tr e g i o ns q p f i l t e rw i t hn c pf u n c t i o ni s p r e s e n t e df o rc 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 gi nc h a p t e rt h r e e ，i t sg l o b a l c o n v e r g e n c ea n dt h en u m e r i c a lr e s u l t so ft h ea l g o r i t h mw i l lb eg i v e ni nt h en e x t c h a p t e r i nt h ef i f t hc h a p t e rw ew i l lg i v et h ef u r t h e rs t u d yo f t h i sa l g o r i t h m k e yw o r d s ：n o n l i n e a rp r o g r a m m i n g ，s q p ，n c pf u n c t i o n ，f i l t e r , t r u s tr e g i o n m e t h o d ，g l o b a lc o n v e r g e n c e t 海大學(xué)碩士學(xué)位論文 原創(chuàng)性聲明 本人聲明：所呈交的論文是本人在導(dǎo)師指導(dǎo)下進行的研究工作。 除了文中特別加以標注和致謝的地方外，論文中不包含其他人己發(fā) 表或撰寫過的研究成果。參與同一工作的其他同志對本研究所做的 任何貢獻均已在論文中作了明確的說明并表示了謝意。 簽名：揚多日 本論文使用授權(quán)說明 期：羋 本人完全了解上海大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即： 學(xué)校有權(quán)保留論文及送交論文復(fù)印件，允許論文被查閱和借閱；學(xué) ?？梢怨颊撐牡娜炕虿糠謨?nèi)容。 ( 保密的論文在解密后應(yīng)遵守此規(guī)定) 簽名： 遞壘 導(dǎo)師簽名：塑盔過日期：2 竺三z ! ! ：三 上海大學(xué)碩士學(xué)位論文 第一章最優(yōu)化的基礎(chǔ)知識 本章將介紹非線性規(guī)劃問題的一些基礎(chǔ)知識。由于濾子方法的提出是為了克 服罰函數(shù)的缺陷，本章還將介紹罰函數(shù)的發(fā)展概況及n c p 函數(shù)的定義和簡單性 質(zhì)。 1 1 數(shù)學(xué)預(yù)備知識 定義1 1 1 映射| | | l ：r “專r 稱為掣上的半范數(shù)，當且僅當它具有下列性質(zhì)： ( 1 ) o v x 掣 ( 2 ) 0 叫i - i 口| | i 硼，r ，溉掣 ( 3 ) l x + y l - j j x 9 + h ，v x , y r ” 此外，除了上述三條性質(zhì)外。如果映射還滿足： ( 4 ) = o 錚j = o ， 則稱刪為f 上的范數(shù)。 令石= ( _ ，而，x n ) 7 r ”，一些常用的向量范數(shù)有： 。= m 警m ，以) ； 1 1 4 1 。= z m ，“) ； = ( 窆# ) 必，( ，2 ) ； 一般地，7 時l _ p o 使得： “0 地- d x l l 。- d x l l v x r “ 則稱范數(shù)和范數(shù)心，是等價的。 上海大學(xué)碩士學(xué)位論文 特別地，有下列重要不等關(guān)系： i i x l l ：訓(xùn)x i i x 憶s i ：s 柝l i x 憶， i i x l l 。l l x ms 療0 工。， 0 zj i 。i i x0 ：s0 x i i 。 定義 1 1 3 設(shè)集合s t - r “， 如果對v 五，而s 有 口鼉+ ( 1 一口) 屯s ，r o t 【o ，1 1 ，稱s 是凸集。 定理1 1 1 彤中的凸子集具有以下性質(zhì)： 1 如果s 是一個凸集，b 是一個實數(shù)，那么集合b s = 缸i x = b y ，v 研也是凸集。 2 。如果墨和最是凸集，那么集合墨+ 島= 紅：x = v 1 + v 2 ，h e 墨，v 2 最) 也是凸集。 3 任意凸集的交集還是凸集。 定義1 1 4 設(shè)s c r 4 是非空凸集，口( 0 ，1 ) ，是定義在s 上的函數(shù)，如果 v 墨，屯s ，f ( a x t + ( 1 一口) 而) o n ， ) f ( x 。) ，x e d n b ( ，回、 x + ) ， ( 1 2 6 ) 則稱z 是問題( 1 2 1 ) ( 1 2 3 ) 的局部極小值，其中 占( x ，萬) = 跏b - - x * l ：j ) 。 ( 1 2 7 ) 如果( 1 2 6 ) 式對嚴格不等號“ ”成立，則稱z + 是局部嚴格極小值。 定義1 2 2 設(shè)r d ，如果 ，( 功f o ) ，x e d x ， ( 1 2 8 ) 則稱z 是問題( 1 2 1 ) ( 1 2 3 ) 的全局極小值。如果( 1 2 8 ) 式對嚴格不 上海大學(xué)碩士學(xué)位論文 等號“ ”成立，則稱x 是全局嚴格極小值。全局極小值也被稱為總體極小值。 從定義可知，全局( 嚴格) 極小值必定是局部( 嚴格) 極小值 定義1 2 3 對任何x e r 4 ，稱集合 彳( 功= e u l ( x ) ( 1 2 9 ) 是在x 點的積極集合，其中e = 1 , 2 ，p ，1 = l ，辨) 以及 l ( x ) = j l g ( x ) = o ，) 。 我們稱g j x ，4 0 ) ) 是在x 點的積極約束，稱g j ( x 燈芒爿( x ) ) 是在膏點的非積極 約束。對于給定的石d ，在一般情況下，集合d n b ( x ，o 3 ，) 中有無窮多個 點。所以，通過驗證( l2 6 ) 來判斷善是否是優(yōu)化問題( 1 2 1 ) ( 1 2 3 ) 的解幾乎是不可能的。最優(yōu)性條件就是在一定條件下和( 1 2 6 ) 等價的條件， 這些條件僅依賴于目標函數(shù)和約束函數(shù)在x 點的性質(zhì)。 1 3 最優(yōu)性條件 定義1 3 1 設(shè)，d ，稱集合 妒= d l 破一d ，石+ 五以d ，暖 o ，暖寸q ( 1 3 1 ) 為d 在x 處的序列可行方向集合；如果d 礦，則稱d 是d 在x 處的序列可行 方向。 定義1 3 2 設(shè)x d ，稱集合 甲= p 礦v ( ，) = o ，e ；d 7 ( x ) o ，_ ，“，) ( 1 3 2 ) 為d 在工+ 處的線性化可行方向集合：如果d l 壬，則稱d 是d 在工+ 處的線性化 可行方向。 引理1 3 1 如果所有的約束函數(shù)都在工d 處可微，則有礦l 王，。 但是反過來，一般不成立甲礦。因此，要使l 玉，。= ，需對約束附加條 4 上海大學(xué)碩士學(xué)位論文 件，稱任何一個保證甲= 緲成立的條件為約束規(guī)格( c o n s t r a i n t q u a l i f i c a t i o n ) 。 定義1 3 3f ( x 1 在x 處的下降方向集合為 d = 翮v f ( x ) 0 。 ( 1 3 3 ) 定理1 3 1 如果x + 為問題( 1 2 1 ) ( 1 2 3 ) 的局部極小點，則 礦n d + = 。 ( 1 3 4 ) 定理1 3 1 表示，在最優(yōu)解處不存在下降可行方向。這在直觀上是顯然的， 但極小點的這一特征是很難檢驗的。為了得到更好的最優(yōu)性條件，需要對問題作 一些假定。如果在x 點處 n d = 甲n d +( 1 3 5 ) 成立，則稱問題( 1 2 1 ) ( 1 2 3 ) 滿足正規(guī)性假定。顯然，在約束規(guī)范下正 規(guī)性假定( 1 3 5 ) 恒成立，但正規(guī)性假定比約束規(guī)格要弱一些。 定理1 3 2 ( k u h n - - t u c k e r 必要條件) 設(shè)x 為問題( 1 2 1 ) ( 1 2 3 ) 的一個局部最優(yōu)解， ) ，h , ( x x i e ) 和g j ( x e 1 ) 在x 的某個鄰域內(nèi)一階連續(xù) 可微，又設(shè)正規(guī)性假定( 1 3 5 ) 成立，則必存在向量 = ( 研，4 ) r , 2 = ( 石，以) 7 使得： v f ( x + ) + z o g v h , ( x ) + 一( 茗) = o ， ( 1 3 6 ) i * l - l 石o ，i j ( 1 - 3 7 ) 舛島( ，) = o f 1 ( 1 3 8 ) 成立。條件( 1 3 6 ) ( 1 3 8 ) 稱為k u h n - - t u c k e r 條件，滿足該條件的點x 稱為k u h n - - t u c k e r 點( 簡稱k t 條件與k t 點) ，而( x ，) 7 稱為k t 對，它 是一個n + p + m 維向量。 因此，在正規(guī)性假定下，最優(yōu)解必定為k t 點。若正規(guī)性假定不成立，則局 部極小點不一定是k t 點。 上海大學(xué)碩士學(xué)位論文 又因為k a r u s h ( 1 9 3 9 ) 也類似地考慮了約束優(yōu)化的最優(yōu)性條件，所以也有 人將上述定理稱為k a r u s h - - k u l m - - t u c k e r 定理，把k t 點稱為k k t 點。 與( 1 3 6 ) 式有密切關(guān)系的一個函數(shù)是 三( 石，彩，五) = ，( x ) + 國，h ，( 茗) + a j g ，( x ) ， ( 1 3 9 ) l ；1 i = 1 它被稱為問題( 1 2 1 ) ( 1 2 3 ) 的l a g r a n g e 函數(shù)，于是k k t 條件的第一式 可以寫成： v ，工( r ，國，刀) = 0 ， ( 1 3 1 0 ) 而向量， 稱為l a g r a n g e 乘子。 條件巧毋( x ) = 0 ( ，d 稱為互補松弛條件，它表明，巧與g j ( x ) 不能同時 不等于0 ，或者等價地，非積極約束的l a g r a n g e 乘子為0 。但是巧與毋( 工) 有可 能同時為0 ，即積極約束的l a g r a n g e 乘子可能為0 ，如果所有積極約束的l a g r a n g e 乘子均不為0 ，則稱嚴格互補松弛條件成立。在一些算法的理論分析中，常常需 要作這樣的假定。 m a n g a s a r i a n 和f r o m o w i t z ( 1 9 6 7 ) 提出另一個約束規(guī)格條件( 簡稱m f c q ) ： v p ) ( f d 線性無關(guān)， ( 1 3 1 1 ) s i s 7 v f ( 工) 0 ) ， 霞= c v e 。 6 ( 1 3 1 3 ) 上海大學(xué)碩士學(xué)位論文 定義1 3 4 設(shè)t = x + + 以d k 為一列滿足 毋( 以) 0 ，、c 和 g | q k 、= o ，j 哎 的可行點列，并且以_ o ，9 以4 = 盯，礬一d 。則稱 t ) 為可行方向點列，而稱d 為 工處的可行方向。用g + 表示z 處按上述定義的可行方向的全體的集合。 定義1 3 5 設(shè)x d ，稱集合 g = d i d 7 v g j ( x ) so ，_ ，i 、c ；d 7 v g ，( r ) = o ，e 或) ( 1 3 1 7 ) 為相應(yīng)約束函數(shù)線性化后的可行方向的集合。 注意：曠和g 均與l a g r a n g e 乘子z 的選取有關(guān)，因此，對于一個k k t 點 j ，可能有不止一個曠和g 。 引理1 3 2 如果所有的約束函數(shù)都在，d 處可微，則有g(shù) g 。 反之，g g 一般不成立。稱條件 g + = g ( 1 3 1 8 ) 及使它成立的任何條件為二階約束規(guī)范。 定理1 3 4 ( 二階必要性條件) 假定，( 功及 0 = l ，2 ，p ) g j ( x ) ( j = 1 ，朋) 都在善附近兩次連續(xù)可微，如果j 是問題( 1 2 1 ) ( 1 2 3 ) 的局部極小點， 且正規(guī)性條件( 1 3 5 ) 成立，從而存在l a g r a n g e 乘子礦，五使k k t 條件( 1 3 6 ) ( 1 3 8 ) 滿足，若對這組l a g r a n g e 乘子二階約束規(guī)范( 1 3 1 7 ) 式成立，則 有 d 7 v 曩( x ，兄) d 0 ，v d g 。 ( 1 3 1 9 ) 定理1 3 2 ( 二階充分條件) 設(shè)問題( 1 2 1 ) ( 1 2 3 ) 的可行點工為 一個k k t 點，是使( 1 3 6 ) ( 1 3 8 ) 式成立的一組l a g r a n g e 乘子， 若成立： 7 上海大學(xué)碩士學(xué)位論文 d 7 v 崩工( x + ，f - o + ，2 ) d 0 ，v d g + ， 則x 為問題( 1 2 1 ) ( 1 2 3 ) 的一個局部嚴格極小點。 1 4 罰函數(shù)的研究概況 求解約束最優(yōu)化問題的一個重要途徑是利用目標函數(shù)和約束函數(shù)構(gòu)造一個 新的函數(shù)，從而將有約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題。罰函數(shù)法就是這樣的 一類方法，構(gòu)造出來的新函數(shù)稱為罰函數(shù)。罰函數(shù)一般與某個罰參數(shù)有關(guān)。若在 罰參數(shù)取有限正數(shù)值時，罰函數(shù)的極小點和原約束函數(shù)的極小點之間存在某種精 確的關(guān)系，則稱該罰函數(shù)為精確罰函數(shù)；若該精確關(guān)系只在罰參數(shù)趨于無窮或零 的時候存在，則稱該罰函數(shù)為序列罰函數(shù)。 通常認為求解約束最優(yōu)化問題的罰函數(shù)方法的思想來源于c o u r a n t 2 5 1 。后 來c a m p 1 7 】和p i e l r z y k o w s k i 等討論了罰函數(shù)法在求解有約束非線性優(yōu)化問題 中的應(yīng)用。而f i a c c o 和m c c o r m i c k 在研究罰函數(shù)方法的理論和算法方面取得了 重大進展，他們提出了序列無約束極小化方法。此后，罰函數(shù)法在求解實際問題 中得到了廣泛應(yīng)用。 對( 1 2 1 ) 一( 1 2 3 ) 定義以下罰函數(shù)： ，c ) = ，( x ) + c ( 藝i 島( x ) | + m a ) 【 o ，旬o ) ) ，c 0 ，2 i，1 該罰函數(shù)就是一個經(jīng)典的序列罰函數(shù)。其本質(zhì)是在問題的不可行點處產(chǎn)生一個 正的懲罰，而在可行點處函數(shù)值不變。當罰參數(shù)c 充分大時，該罰函數(shù)的值可以 充分逼近原問題的整體最優(yōu)值。因此，通過求解一系列取遞增c 的罰問題，一般 都可以解得原約束優(yōu)化問題的最優(yōu)解。但是隨著c 的增大，罰函數(shù)可能會趨于病 態(tài)，從而導(dǎo)致計算上的困難。一般來說，這種方法求解約束規(guī)劃問題所需的工作 量都很大。 而精確罰函數(shù)在理論上只需取某有限正參c 就可以得到約束優(yōu)化問題的解， 從而避免了序列罰函數(shù)法在參數(shù)交大時產(chǎn)生病態(tài)的問題。精確罰函數(shù)的概念首先 由e r e m i n 和z a n g w i l l 于1 9 6 0 年代后期提出。精確罰函數(shù)包括不可微精確罰函 數(shù)和連續(xù)可微精確罰函數(shù)。z a n g w i l l 證明了具有精確性質(zhì)的罰函數(shù)是不可微精確 上海大學(xué)碩士學(xué)位論文 罰函數(shù)。 乞精確罰函數(shù)是一類最常見的不可微精確罰函數(shù)，其定義如下( c o ) ： ，c ) = ，o ) + c ( 圭阮( x ) 1 9 + 窆 m a x o 毋) ，彤，l g - o , b 0 ，a b = 0 本文將采用f i s c h e r - b u r m e i s t c rn c p 函數(shù)， 構(gòu)造出一系列與k k t 條件等價的條件。 f i s c h e r - b u r m e i s t e r n c p 函數(shù)有如下形式： ( 吼6 ) = ：萬一4 一b 。 該函數(shù)有以下性質(zhì)： 1 ：妒眩6 ) 的平方連續(xù)可微； 2 ：除原點外妒 6 ) 處處二階連續(xù)可微，但它在原點強半光滑；即 如果口2 + 6 2 0 ，則( 口，6 ) 在點( o ，o ) 連續(xù)可微，且 v ( 4 ，6 ) = ( 。4 南b 一1 了言舞b 1 ) ?？? 、f 口+ 如果口2 + 6 2 = 0 ，則妒( 口，6 ) 在點( o ，o ) 處的廣義梯度為 a ( o ，o ) = 占一l ，r 一l k 2 + r 2 = l 。 令力五，c ) = ( ( - c 0 ) ) ，a j ) , l 0 ，有g(shù) ，( x ) 0 ，以o 及乃毋( = 0 記 m ( x ，五，c ) = ( 旃( 薯五，c ) ，九( 毛五，c ) ) 7 。 顯然，k k t 條件等價于旯，c ) = o ，日( 工) i i = o 及v ，l ( x ，c o , 2 ) = 0 上海大學(xué)碩士學(xué)位論文 第二章s q p 算法與信賴域方法 我們下面要討論的算法以s q p 算法和信賴域算法作為基礎(chǔ)。s q p 算法是目 前具有較為成熟和易運算操作的特點；而信賴域算法又可以取代線搜索，來決定 搜索步的大小。 2 1s q p 算法 由于q p ( - - 次規(guī)劃) 問題的成功解決，就想到在當前迭代點x 。處，利用目 標函數(shù)的二次近似和約束函數(shù)的線性近似構(gòu)成一個二次規(guī)劃。通過求解這個二次 規(guī)劃得到下一個迭代點。這種將求解非線性規(guī)劃問題轉(zhuǎn)化為求解一系列q p 子問題的方法，稱為s q p ( s e q u e n t i a lq u a d r a t i cp r o g r a m m i n g ) 方法。s q p 最早 由h a r t 在1 9 7 6 年提出，隨后由p o w e l l 和w i l s o n 發(fā)展的w h p 算法，可謂是最早 的s q p 算法了。從此，s q p 方法就發(fā)展并流行了起來。s q p 發(fā)展至今已不再是 一個具體的算法，而是一個概念性的方法。 s q p 主要有兩類：基于線性搜索的l s q p 和基于信賴域框架的t s q p 。 l s q p 通過求解( 1 2 1 ) 一( 1 2 3 ) 的二次規(guī)劃子問題： m i i 】，盯( 以) 7 d + 曇d ，忍d ( 2 1 1 ) s t 囊( 耳) + v 吩( 屯) 7 d = o ( f = l ”，p ) ( 2 1 2 ) 毋( 以) + ( 坼) 7 d 0 ， j 0 ，且r 靠。，占l ，k # 1 。 s t e p 2 ：求解( 2 1 1 ) 一( 2 1 3 ) ，得出噍如果慨忙占則停止。否則求 a ke o ，0 7 ，使p ( x i + a k d k , o - ) 。m s 。i n 占p ( x i + a d k , 盯) + 占j s l e p 3 ：而+ l = 以+ q 噸，計算l ，k # k + l 轉(zhuǎn)s t y 2 a s q p 中的皿。一般用擬牛頓法修正，由于希望毋+ 。是l a g r a n g e 函數(shù)h e s s e 陣 的近似，?。?s t 2 x k + i x k ， 咒= v ( 。) - v f ( x d - 芝( c o a 吩瓴+ i ) 一v ( t ) 】一( 五) ， v g j ( x 。+ ，) - v g j ( x k ) j = l 1 = 1 與無約束優(yōu)化本質(zhì)不一樣的是：對于價值函數(shù)進行線搜索并不能保i f _ s ；y , 0 ， 從而不能直接利用b f g s 方法。p o w e i l 建議： 一f咒 n 2 1 嚷幾+ ( 1 一只) 犀& k 7 氏0 辭矚 其他 舯 幺= 摭 則 嘶等+ 再t t s q p 與l s q p 稍有不同，就是限制了d k 的范數(shù)不能超過其每步給定的信賴 域半徑，該子問題如下： m i nv f ( x a 7 d + d 7 最d ( 2 1 5 ) j 上h , ( x , ) + v h ( x k ) d = 0 ( f = l ，p ) ( 2 1 6 ) 毋阮) + v 衫( x a d a 0 u = l ，m ) ( 2 1 7 ) 0 d l 。s 咯 ( 2 1 8 ) 上海大學(xué)碩士學(xué)位論文 下面是s q p 的收斂性定理。 定理2 1 1 假定，( 力，吩( 工) 與g ，( x ) 連續(xù)可微，存在常數(shù)m ，m 0 使得 m u d l l ：- d 7 b , d m l l d l e 對一切七和d e r “都成立。如果i k k 盯對一切| i 都成 立，則算法1 產(chǎn)生的點列 x a 的任何聚點都是( n l p ) 的k k t 點。 利用二次規(guī)劃子問題的解t 作為搜索方向在一定條件下，比如 最) 正定， 乘子有界，q = 1 是一個超線性收斂步。需要注意的是：s q p 與線搜索或信賴域 結(jié)合在一定條件下才會全局收斂。 s q p 方法雖具有全局收斂性，但是不論l s q p 還是t s q p 都需要選擇某一合 適的罰函數(shù)作為價值函數(shù)。罰函數(shù)法的使用會因為罰因子的選取給運算帶來許多 困難，通常要求罰因子有界，這個界值很難確定。界太小會使得迭代點迭代至不 可行點；界太大會削弱目標函數(shù)f ( x ) 對迭代步的影響，從而導(dǎo)致當可行域邊界 是曲邊時，收斂的速度變得很慢。為了克服因罰因子的選取所帶來的困難， f l e t c h e r 和l e y f f e r 等人提出了濾子的概念，結(jié)合濾子的s q p 方法也應(yīng)運而生。 下一章將詳細介紹濾子的概念，并提出一種新的濾子s q p 算法并給出它的全局 收斂性證明。 在本節(jié)最后簡單討論與二次規(guī)劃子問題有關(guān)的m a r o t o s 效應(yīng)及二階校正步 ( s o c ) 問題。 所謂m a r a t o s 效應(yīng)是指：不管墨離x 多么接近，吼= 1 都不可能成立，從而 破壞了算法的超線性收斂性。目前已知m o r a t o s 效應(yīng)是由于價值函數(shù)的非光滑引 起的。 克服m a r a t o s 效應(yīng)的方法是引進一個二階校正步( s o c ) ，二階校正步是下述 問題 的解： m i n - - 9 1 7 d + 三d r b , d ( 2 1 9