（運(yùn)籌學(xué)與控制論專業(yè)論文）非線性規(guī)劃中的罰函數(shù)及填充函數(shù)方法.pdf

摘要 最優(yōu)化理論和方法的出現(xiàn)可以追溯到十分古老的極值問(wèn)題，然而，它成為一 門獨(dú)立的學(xué)科還是在上世紀(jì)4 0 年代末d a n t z i n g 在1 9 4 7 年提出求解一般線性規(guī) 劃問(wèn)題的單純形算法之后，隨著工業(yè)革命、信息革命的不斷深化，以及計(jì)算機(jī)技術(shù) 的巨大發(fā)展，至今短短的幾十年，它得到了迅猛的發(fā)展現(xiàn)在，解線性規(guī)劃、非線 性規(guī)劃以及隨機(jī)規(guī)劃、非光滑規(guī)劃、多目標(biāo)規(guī)劃、幾何規(guī)劃、整數(shù)規(guī)劃等各種最 優(yōu)化問(wèn)題的理論研究發(fā)展迅速，新方法不斷涌現(xiàn)，在經(jīng)濟(jì)、軍事、科學(xué)技術(shù)等方 面得到了廣泛的應(yīng)用，成為一門十分活躍的學(xué)科 約束非線性規(guī)劃問(wèn)題廣泛見于工程、國(guó)防、經(jīng)濟(jì)等許多重要領(lǐng)域求解約束 非線性規(guī)劃問(wèn)題的主要方法之一是把它化成無(wú)約束非線性規(guī)劃問(wèn)題，而罰函數(shù)方 法和拉格朗日對(duì)偶方法是將約束規(guī)劃問(wèn)題無(wú)約束化的兩種主要方法罰函數(shù)方法 通過(guò)求解一個(gè)或多個(gè)罰問(wèn)題來(lái)得到約束規(guī)劃問(wèn)題的解，如果當(dāng)罰參數(shù)充分大時(shí)， 求單個(gè)罰問(wèn)題的極小點(diǎn)是原約束規(guī)劃問(wèn)題的極小點(diǎn)，則稱此罰問(wèn)題中的罰函數(shù)為 精確罰函數(shù)，否則稱為序列罰函數(shù)針對(duì)傳統(tǒng)罰函數(shù)的定義而言，若罰函數(shù)是簡(jiǎn) 單的、光滑的，則它一定是不精確的；若罰函數(shù)是簡(jiǎn)單的、精確的，則它一定是不 光滑的：若罰函數(shù)是精確的、光滑的，則它一定是復(fù)雜的因此我們的工作是對(duì)傳 統(tǒng)罰函數(shù)進(jìn)行了改造，主要是引入了指數(shù)型罰函數(shù)和對(duì)數(shù)型罰函數(shù)，并在改造后 的罰函數(shù)中增添了乘子參數(shù)，使之成為既是簡(jiǎn)單的、光滑的，又是精確的結(jié)果我 們把這類罰函數(shù)稱為簡(jiǎn)單光滑乘子精確罰函數(shù)所謂簡(jiǎn)單的，即罰函數(shù)中包含原 問(wèn)題中的目標(biāo)函數(shù)和約束函數(shù)而不包含它們的梯度，若罰函數(shù)中包含有原問(wèn)題中 目標(biāo)函數(shù)和約束函數(shù)的梯度，則稱為是復(fù)雜的 全局最優(yōu)化是最優(yōu)化一個(gè)重要分支全局最優(yōu)化算法，從算法的構(gòu)造上大體 可以分為確定型算法和隨機(jī)型算法，例如，填充函數(shù)法、打洞函數(shù)法屬于確定型 算法；模擬退火法、遺傳算法屬于隨機(jī)型算法，我們?cè)谶@篇文章中也考慮非線性 規(guī)劃的全局最優(yōu)化確定型算法這篇文章的另一個(gè)主要且的就是，在研究已有確 定型算法的基礎(chǔ)上，嘗試提出一些改進(jìn)和創(chuàng)新，力圖在算法效果方面有所提高， i 在理論方面有所深化其詳細(xì)內(nèi)容如下： 本論文共五章：在第一章中，簡(jiǎn)要介紹了目前國(guó)內(nèi)外關(guān)于罰函數(shù)、精確罰函 數(shù)、乘子精確罰函數(shù)的研究工作；第二章提出一種帶有指數(shù)、對(duì)數(shù)性質(zhì)的乘子罰 函數(shù)，并進(jìn)行了一定的數(shù)值試驗(yàn)，取得了較好的計(jì)算效果；第三章介紹一種光滑 的近似精確罰函數(shù)，從理論上證明它的近似精確性，為進(jìn)一步研究打下了基礎(chǔ)；第 四章介紹了一種全局精確罰函數(shù)，在一定的假設(shè)下該函數(shù)具有全局的精確性；在 第五章介紹了常見的填充函數(shù)法及給出一個(gè)新的填充修正打洞函數(shù)算法對(duì)于一 般無(wú)約束全局最優(yōu)化問(wèn)題，我們給出一個(gè)填充修正打洞函數(shù)的定義，它不同于傳 統(tǒng)的填充函數(shù)定義在此基礎(chǔ)上，提出了一個(gè)填充修正打洞函數(shù)和相應(yīng)的算法， 該算法降低了對(duì)參數(shù)的依賴，具有較好的可操作性數(shù)值試驗(yàn)顯示，該算法是有 效和可靠的 關(guān)鍵詞：罰函數(shù)，非線性規(guī)劃，全局最優(yōu)解，填充函數(shù)，精確光滑罰函數(shù) a b s t r a c t 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 gp r o b l e m sa b o u n di nm a n yi m p o r t a n tf i e l d s s u c ha se n g i n e e r i n g ，n a t i o n a ld e f e n c e ，f i n a n c ee t c o n eo ft h em a i na p p r o a c h e s f o rs o l 、，i n gc 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 si st ot r a n s f o r mi ti n t o u n 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 gp r o b l e m p e n a l t yf u n c t i o nm e t h o d sa n d l a g r a n g i a nd u a i i t ym e t h o d sa r et h et w op r e v a i l i n ga p p r o a c h e st oi m p l e m e n tt h e t r a n s f o r m a t i o n p e n a l t yf u n c t i o nm e t h o d ss e e kt oo b t a i nt h es o l u t i o n so fc o n s t r a i n e dp r o g r a m m i n gp r o b l e mb ys o l v i n go n eo rm o r ep e n a l t yp r o b l e m s i f e a c hm i n i m u mo ft h ep e n a l t yp r o b l e mi sam i n i m u mo ft h ep r i m a lc o n s t r a i n e d p r o g r a m m i n gp r o b l e m ，t h e nt h ec o r r e s p o n d i n gp e n a l t yf u n c t i o ni sc a l l e de x a c t p e n a l t yf u n c t i o n i nt h i st h e s i s ，w ef i r s tg i v es o m ep e n a l t yf u n c t i o n ，a n dt h e n w ed i s c u s st h eg l o b a le x a c ta n da p p r o x i m a t i v e l ye x a c tp e n a l t yp r o p e r t yo fe x a c t p e n a l t yf u n c t i o n s ，w ea l s od i s c u s ss m o o t h i n go fe x a c tp e n a l t yf u n c t i o n s g l o b a lo p t i m i z a t i o np r o b l e m sa b o u n di ne c o n o m i cm o d e l l i n g ，f i n a n c e ，n e t - w o r k sa n dt r a n s p o r t a t i o n ，d a t a b a s e s ，c h i pd e s i g n ，i m a g ep r o c e s s i n g ，c h e m i c a le n - g i n e e r i n gd e s i g na n dc o n t r o l ，m o l e c u l a rb i o l o g y ，a n de n v i r o n m e n t a le n g i n e e r i n g s i n c et h e r ee x i s tm u l t i p l el o c a lo p t i m at h a td i f f e rf r o mt h eg i o b a ls o l u t i o n ，a n d t h et r a d i t i o n a lm i n i m i z a t i o nt e c h n i q u e sf o rn o n l i n e a rp r o g r a m m i n ga r ed e v i s e d f o ro b t a i n i n gl o c a lo p t i m a ls o l u t i o n ，h o wt oo b t a i nt h eg l o b a l l yo p t i m a ls o l u t i o n s i sv e r yi m p o r t a n tt o p i c i nt h i st h e s i s ，w ea l s od i s c u s st h ef i l l e df u n c t i o nm e t h o d s f o rg l o b a lo p t i m i z a t i o na n dg i v ean e wf i l l e df u n c t i o n t h i sp a p e rm a i n l yc o n s i s t so ff i v ec h a p t e r s i nt h ef i r s tc h a p t e r ，w eg i v eab r i e fi n t r o d u c t i o nt ot h ee x i s t i n gr e s e a r c hw o r k o np e n a l t yf u n c t i o n s i nt h es e c o n dc h a p t e r ，w eg i v ea nm u l t i p l i e rp e n a l t yf u n c t i o na n dd i s c u s si t s p r o p e r t i e s b a s e d0 nt h ep e n a l t yf u n c t i o n a na l g o r i t h mi sg i v e n 1 nc h a p t e rt h r e e ak i n do fs m o o t h i n ga n da p p r o x i m a t i v e l ye x a c tp e n a l t yf u n c - t i o n si sg i v e n ，a n di t sa p p r o x j m a t i v e l ye x a c tp r o p e r t yi sp r o v e d f i n a l l ya na l g o - r i t h mi sg i v e n i nc h a p t e rf o u r ，t h eg l o b a le x a c tp e n a l t yf u n c t i o ni sg i v e n ，w ef i r s tp r o v ei t s p r o p e r t i e s ，t h e na na l g o r i t h mi sg i v e n i nt h el a s tc h a p t e r ，f o rg l o b a lo p t i m i z a t i o np r o b l e m s ，w eg i v ean e wa l g o r i t h m c a l l e d 矗l l e dm o d i f i e dt u n n e l l i n gf u n c t i o nm e t h o d s a l la u x i l i a r yf u n c t i o nc a i l e d f i l l e dm o d i f i e dt u n n e l l i n gf u n c t i o ni sf i r s tg i v e n ，i th a sg o o dp r o p e r t i e so ff i l l e d f u n c t i o na n dt u n n e l l i n gf u n c t i o n t h e n ，b a s e do nt h ef u n c t i o n ，卸a l g o r i t h mi s g i v e n t h ei m p l e m e n t a t i o no ft h ea l g o r i t h m so ns e v e r a lt e s tp r o b l e m si sr e p o r t e d w i t hs a t i s f a c t o r yn u m e r i c a lr e s u l t s i i i 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 ；p e n a l t yf u n c t i o n ；t u n n e l l i n gf u n c t i o n ； g l o b a lo p t i m i z a t i o n ；f i l l e df u n c t i o n i v 原創(chuàng)性聲明 本人聲明：所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作。 除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已發(fā) 表或撰寫過(guò)的研究成果。參與同一工作的其他同志對(duì)本研究所做的 任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示了謝意。 簽名：牡日期：型叢 本論文使用授權(quán)說(shuō)明 本人完全了解上海大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即： 學(xué)校有權(quán)保留論文及送交論文復(fù)印件，允許論文被查閱和借閱；學(xué) ?？梢怨颊撐牡娜炕虿糠謨?nèi)容。 ( 保密的論文在解密后應(yīng)遵守此規(guī)定) 上海大學(xué)博士學(xué)位論文 第一章基礎(chǔ)知識(shí)及相關(guān)結(jié)論 1 1 基礎(chǔ)知識(shí) 考慮如下約束非線性規(guī)劃問(wèn)題 ( p ) m i n ，( z ) s t 壤( z ) 0 “= 1 ，2 ，m ) ( 1 1 1 ) o x 其中，9 i ，i = 1 ，2 ，m 是定義在艫上的非線性連續(xù)可微函數(shù)，x 是毋的 一個(gè)子集，。= ( z l ，z 2 ，x n ) r 是n 維向量集合 s = z xj 肌( z ) s0 ，i = 1 ，2 ，m ) 表示為問(wèn)題( p ) 的可行域，s 中的點(diǎn)稱為問(wèn)題( 尸) 的可行點(diǎn) 設(shè)礦s ，若存在礦的領(lǐng)域 d ( 。，6 ) = z l0z z i f 6 ) ， 使對(duì)任意s n d ( 礦，6 ) 成立 f ( x ) s ( 0 ) ，= t j ( z ) la ：= o ) l ( z ，a ) 在的h e s s i a n 陣為 v 2 l ( 礦，”) = v 2 ，( 礦) + n v 2 吼( 礦) i e l ( z ) 其中v 2 ，扛) ，v 2 9 i ( z ) ( i ，( 礦) ) 分別是，孽t ( i = 1 ，2 ，m ) 在礦i 臼h e s s i a a 陣 定義錐 c = pjv g i ( z ) = 0 ，l ，+ ，v g i ( z ) s0 ，i ，0 ) ， 于是，坳c ，都有 ，v 2 l ( z + ，a ) p 0 ， 則礦為嚴(yán)格的局部極小點(diǎn) 定理1 1 4 ( - - 階必要條件，見f 1 1 j 定理4 4 3 ) 設(shè)在問(wèn)題( 尸) 中，g i ( i = 1 ，2 ，m ) ，在j p 上二次可微，礦為局部極小點(diǎn)，l a g r a n g e 函數(shù)在r 的h e s s i a n 陣 為 v 2 l ( z ，a 。) = v 2 ( z + ) + 礙v 2 9 i ( 礦) i e l ( = ) 3 上海大學(xué)博士學(xué)位論文 其中v 2 ，忙) ，v 2 9 i ( z + ) ， j ) 分別是f ，毋i ，( r ) 在礦的h e s s i a n 陣 假定v g i ( x ) ，i j ( 礦) 線性無(wú)關(guān)，則礦為k k t 點(diǎn)，且對(duì)印c = 仞0i v 9 t ( 士) r p oi ，( z ) 成立，v 2 r ( z ，a ) p 0 通常對(duì)于求解非線性規(guī)劃問(wèn)題方法，應(yīng)當(dāng)要求它具有有關(guān)的收斂性，而要判 斷其有效性，除了可以看它是否具有收斂性之外，重要的衡量標(biāo)準(zhǔn)是它的收斂速 度。下面我們將介紹有關(guān)的收斂性和斂速的一些定義 定義1 1 1 ( 局部收斂性) 設(shè)礦為問(wèn)題解，存在礦的某領(lǐng)域d ( 礦，盯) ，盯 0 ，對(duì)任意初始點(diǎn)a ；o 0 ( 礦，口) ，由算法產(chǎn)生的點(diǎn)列 瓢) ，總成立。l i r az = ， - - | o o 定義1 1 2 ( 全局收斂性) 設(shè)礦為問(wèn)題解，對(duì)任x o 艫，由算法產(chǎn)生的 點(diǎn)列 孤) ，總成立) i m 以= 礦 g - - o o 定義1 1 3 ( 局部線性斂速) 為由算法產(chǎn)生的點(diǎn)列，礦為問(wèn)題的解，若 成立l iz + 1 一rf | se0 ：k - - a 7 i | ，或 f ( z k + 1 ) 一，( 礦) l sgif ( x k ) - f ( x ) i ，這 里k ， 0 為某正整數(shù)，o c 1 ，則稱點(diǎn)列 鞏) 具局部線性斂速 定義1 1 4 ( 一致線性斂速) z t ) 為由算法產(chǎn)生的點(diǎn)列，礦為問(wèn)題的解，若 成立l ix k - t - 1 一礦l | ci | x k - - a 7 或if ( z k + 1 ) 一，( 礦) i scif ( z c k ) - f ( z 。) l ，對(duì) 所有k = 1 ，2 ，o 0 為常數(shù)， 4 上海大學(xué)博士學(xué)位論文 1 2 罰函數(shù)方法 考慮問(wèn)題 m i n f ( x 1 ( 戶) 8 刪0 ，江1 m ，m( 1 馴 吩0 ) = 0 ，j = 1 ，2 ，r ， z x 其中x c 妒 罰函數(shù)方法的基本思想就是把上述約束問(wèn)題變換成無(wú)約束問(wèn)題來(lái)求解，采用 的方法是在目標(biāo)函數(shù)上加上一個(gè)或多個(gè)與約束函數(shù)有關(guān)的函數(shù)，而刪去約束條 件，在形式上把問(wèn)題( p ) 交換成如下形式： q ( 文丸，觸) = f ( x ) f a k 咖h ( z ) 】+ 縱妒【吻( z ) 】 ( 1 2 2 ) j = lj = l 其中，咖( 暑，) ，妒( 耖) 為連續(xù)函數(shù)，且滿足( s ，) = 0 ，ys0 且妒( ! ) 0 ，耋 0 ； 妒( 可) = 0 ，s f = 0 且妒( f ) 0 ，y 0 ，而k ，肌，為罰因子tq ( 。，札，p k ) 稱為罰 函數(shù) 若a t = a ，腳= 地則是一個(gè)無(wú)約束問(wèn)題；若出現(xiàn)一列兒，m ，k = 1 ，2 ，a 女， mt + o 。則是一系列無(wú)約束問(wèn)題 罰函數(shù)法主要分s u m t ( 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 nt e c h n i q u e s ) 法， 增廣l a g r a n g e 罰數(shù)法和精確罰函數(shù)法三類它們有一點(diǎn)共同點(diǎn)就是對(duì)不可行點(diǎn) 要予以懲罰其懲罰大小體現(xiàn)在罰參數(shù)h ，觸及( 暑，) ，妒( ) 上 用罰函數(shù)方法來(lái)解約束最優(yōu)化問(wèn)題通常認(rèn)為最早由c o u r a n t 在求解線性規(guī) 劃時(shí)提出。后來(lái)，c a m p 4 8 和p i e t r g y k o w s k i 4 7 討論了罰函數(shù)方法在解非線性規(guī) 劃問(wèn)題中的應(yīng)用。f i a c c o 和m c c o r m i c k 1 一【6 在利用罰函數(shù)方法，即序列無(wú)約束極 小化方法上作了不少工作，并總結(jié)為s u m t 方法 s u m t 法是用形如m i n 【，( z ) + 即( z ) 】的序列無(wú)約束問(wèn)題來(lái)替代問(wèn)題( 戶) ， 其中p 0 稱為罰參數(shù)，p ( x ) 稱為r “上的罰函數(shù)它滿足： 1 p ( z ) 在尼。上連續(xù)； 2 p ( x ) 0 ，比舒； 5 上海大學(xué)博士學(xué)位論文 3 p 仁) = 0 充要條件是 zes = z ig i ( x ) 0 ，i = 1 ，2 ，一，m ，h j ( x ) = o ，j = 1 ，2 ，r ) 例如對(duì)問(wèn)題( 即，下述兩函數(shù)均是罰函數(shù) mr p ( z ) = 妒( 甄( z ) ) + 妒( b ( 。) ) ( 1 2 3 ) i = 1 j = l 仇r p ( z ) = m a x ( o ，吼( z ) ) p + ih a z ) l ， ( 1 2 4 ) i - - - - - 1 j - - - - - i 這里p 為正整數(shù) 一般來(lái)說(shuō)，無(wú)約束問(wèn)題 ( q p ) ： m 州i n 地) + 爐( 。) 0 2 5 ) 隨著p 的增加，其解必落在p ( z ) 之值很小的一個(gè)區(qū)域內(nèi)，亦b 口s 附近，因而可 設(shè)想，當(dāng)p _ o o 時(shí)，問(wèn)題( q 。) 的解趨于可行域 設(shè)q ( u ) = i , f f ( z ) + p p 0 ) iz x ) ，我們有如下結(jié)論： 引理1 2 1 ( 見【1 1 】定理9 2 1 ) 設(shè)f ，蟲i = 1 ，2 ，m ，h j ，j = 1 ，2 ，r 為j p 上的連續(xù)函效，x 為j p 中一個(gè)非空閉箱，設(shè)p ( z ) 由( 1 2 3 ) 定義的連續(xù)函 數(shù)，如果對(duì)任何p 0 ，存在點(diǎn)釓x ，使得 q ( 蘆) = ，扛p ) + 弘p ( ) = i a f f ( x ) + 伊( z ) ：善x ) 那么下述結(jié)論成立： 1 i n f ，( i 戤p ) 0 ，i = 1 ，m ，h j i z ) = 0 ，j = 1 ，t ，t 。ex ， 之s u p q ( p ) p 三0 2 ，( 卻) 是關(guān)于肛的單調(diào)不減函數(shù)，q ( p ) 關(guān)于p 的單調(diào)不減函數(shù)，p ( z ，) 是 關(guān)于p 的單調(diào)不增函數(shù)。 6 上海大學(xué)博士學(xué)位論文 定理1 2 1 ( 見【1 1 定理6 2 4 ) 設(shè)f ，璣i = 1 ，2 ，仇，j = 1 ，2 ，r 為t p 上的連續(xù)函數(shù)，x 為p - 中的非空閉箱，設(shè)問(wèn)題( p ) 至少有一個(gè)可行解， p ( 士) 為由( 1 2 3 ) 定義的連續(xù)函數(shù)，如果對(duì)任何p 0 ，存在一點(diǎn)x ，使得 q ( p ) = ，( q 。) + l z p ( z ，) = i n f f ( z ) + 巾仁) ：z x ) ， 而且 ) 也包含于x 中的一個(gè)緊子集，那么成立 1 i n f f ( x ) lg i ( x ) 0 ，i = 1 ，m ，h j ( x ) = 0 ，= 1 ，r z x ) = s u p q o , ) p 2 0 = l i mq ( p ) ； 一w 2 卻) 的任何收斂子列的極限點(diǎn)是原問(wèn)題( 戶) 的一個(gè)最優(yōu)解； 3 1 i m 肛尸( 工“) = 0 - f o o 顯然，如果對(duì)某個(gè)p 成立p 0 ，) = 0 ，那么是原問(wèn)題戶的最優(yōu)解。 從定理1 2 1 得知，當(dāng)取罰函數(shù)p 充分大時(shí)，問(wèn)題( q ，) 的最優(yōu)解可以任 意逼近原問(wèn)題( 戶) 的最優(yōu)解，但是，如當(dāng)p 很大時(shí)，( $ p ) + p 尸( z 。) 的h e s s i a l l 陣 趨于病態(tài)而導(dǎo)致計(jì)算困難，因此當(dāng)用無(wú)約束優(yōu)化方法來(lái)解r a i n ，( z ) + 肛p ( z ) 時(shí)， 運(yùn)用有些算法如n e w t o n 法，其收斂速度很慢，引用s u m t 方法來(lái)解原問(wèn)題所需的 計(jì)算量是比較大的。因此產(chǎn)生了求解約束非線性規(guī)劃的一些改進(jìn)的罰函數(shù)方法 與傳統(tǒng)的罰函數(shù)( 1 2 3 ) 不同，在文f 9 7 】中亦討論了不等式約束非線性規(guī)劃問(wèn) 題( p ) 的指數(shù)型罰函數(shù)，其形式如下； 躲，r ( z 凈他) + 7 善麟p r o 稱釹為二( z ) 的取極小解，若滿足下述不等式： 九( 釓坯。m i nf r ( 孑) + “， 7 上海大學(xué)博士學(xué)位論文 其中“ 0 ，而7 k 0 為罰參數(shù) 它得至下述“近似解的結(jié)論 定理1 2 2 ( 見文1 9 7 命題2 1 ) 假定函數(shù)f ( z ) ，乳( z ) ，i = 1 ，2 ，m 是連續(xù) 的且f 下有界。令j p 是允的e k - - 極小解，這里缸0 ， 0 都趨 于o ，則點(diǎn)列 扛女) ) 的任一極限點(diǎn)礦皆為原問(wèn)題的全局解此外著存在對(duì) 0 ， 成立 。息，0 ) 2 + o o l i 忙) s q 貝4 點(diǎn)列 0 t ) ) 的極限點(diǎn)一定存在 t n 很顯然，對(duì)于上述指數(shù)型罰函數(shù)二0 ) = f ( x ) + r e x pf 魚( z ) 】= i = 1 f ( x ) - i r p ( x ，r ) ，其中p ( x ，r ) o ，對(duì)所有z ，而當(dāng)z 乏s , r 0 時(shí)，p ( z ，r ) 隨 著r 0 減小而增大，且對(duì)同樣r 0 ，z 乏s 的不可行程度越嚴(yán)重，則p ( x ，r ) 值 越大，這一指數(shù)型罰函數(shù) ( z ) 是簡(jiǎn)單的、光滑的，但仍然不是精確的因?yàn)閮H 當(dāng)“上o 時(shí)，若工女收斂于礦，則礦為原問(wèn)題的全局解洇此仍是序列的 定理l 2 3 ( 見文【9 7 】定理3 1 ) 設(shè)f ( x ) ，歷( z ) 在問(wèn)題( p ) 的最優(yōu)解r 的某個(gè) 鄰域內(nèi)二次連續(xù)可微，如果在礦處滿足嚴(yán)格互補(bǔ)和二階最優(yōu)性條件，則方程組 m v f ( z ) + e x p 【g i ( x ) r 】v 仇( 罩) = f l = i e ( o ，o ) 附近關(guān)于( r f ) 定義了一個(gè)連續(xù)可微隱函數(shù)x ( r ，) ，其中r 0 ，并滿足 船工( r ，f ) = 礦 r j o 此外，k ( r ，) = e x p 【島( z ( r ，q ) r1 是連續(xù)可微函數(shù)，并滿足 i m ，扣協(xié)，) = 礙 并且當(dāng)( r ，f ) 趨于( o ，o ) 時(shí)，x ( r ，) 和a ( r ，) 的導(dǎo)數(shù)有極限，還對(duì)所有充分小r ，點(diǎn)研= z ( r ，0 ) 是，r 的嚴(yán)格局部極小點(diǎn) 8 上海大學(xué)博士學(xué)位論文 在介紹了一個(gè)外插算法后，文章又給出了如下結(jié)論 定理1 2 4 ( 見文 9 7 1 定理5 1 ) 設(shè)岔 + 1 是經(jīng)第“次迭代后得到的外插點(diǎn)，對(duì) 罰參數(shù)r 七+ 1 首次迭代的牛頓方向e _ 滿足 e j i d ( ) 此外，如果x 。n + 1 表示首次牛頓迭代后得到的點(diǎn)，則有 ov f ( x k 盤。) + e x p 【g i ( x n + 。) “+ t 】v m ( 。魯，) j | o ( r t 4 ，r 2 + ，) i = 1 1 3 精確罰函數(shù)方法 考慮問(wèn)題 m i n f ( z ) ( p )s t g i ( x ) 0 ，i = 1 ，2 ，。仇 z x c 艫 精確罰函數(shù)是用形如m 。；i x n 【，扛) + p e 扛) 】的無(wú)約束問(wèn)題( b ) 來(lái)替代問(wèn)題( p ) ， 其中p 為參數(shù)，e ( x ) 為x - r 上的函數(shù)且滿足： 1 e ( z ) 0 ，比x 2 e ( z ) = 0 的充要條件是z s ， 這里 s = oig i ( z ) 0 ，t = 1 ，2 ，m ，z x ) 定義1 3 1 若存在, i , o 0 ，當(dāng)p 腳時(shí)使得問(wèn)題( 只) 的解是問(wèn)題( _ p ) 的 解，或問(wèn)題( p ) 的解是( 丘) 的解， 則稱 f ( z p ) + , u e ( x p ) 為問(wèn)題( p ) 的精確罰函數(shù)。這里解可以是局部最優(yōu)解，也可以是全局最優(yōu)解。 精確罰函數(shù)概念首先i 芻e r e m i nf 4 2 $ 1 z a n g w i l l 【1 2 8 】于上世紀(jì)六十年代后期 提出。這是線性規(guī)劃中大m 法在非線性規(guī)劃中的自然推廣。從那時(shí)起，精確罰函 9 上海大學(xué)博士學(xué)位論文 數(shù)一直在數(shù)學(xué)規(guī)劃理論與方法中扮演很重要的角色。下面我們介紹發(fā)展最為成熟 的2 l 精確罰函數(shù)方法的主要理論結(jié)果： 設(shè)原問(wèn)題( p ) 中集合x 為開集，令( 1 2 4 ) 中p = 1 ，得罰問(wèn)題 ( 茸) m m f ( x ) 州若m a x m z ) ) + j = l ib ( 圳) 稱 只扛，p ) = ，( 姊+ p ( m a x o ，吼( z ) - p i 磚( z ) i ) = 1 j = 1 為l l 精確罰函數(shù)，f 1 精確罰函數(shù)又稱為經(jīng)典精確罰函數(shù) 定理1 3 1 ( 見文f 1 1 】定理9 3 1 ) 設(shè)礦為問(wèn)題( p ) 的k - k t 點(diǎn)，( u + ，口+ ) 為與礦相 應(yīng)的k - k t 乘子，進(jìn)一步，設(shè)f ( z ) ，g i ( x ) ，eei o ( x ) = l 吼( 礦) = 0 ，i = l ，2 ，m ) 是凸函數(shù)，而且h j ( z ) ，j = 1 ，2 ，r 是仿射函數(shù)，則對(duì)弘芝 懈 成，i 1 0 ( x ) ，1 哼l ，j = 1 ，2 ，r ) ，礦也是問(wèn)題( 冠) 的解 定理1 3 2 ( 見文 1 0 9 定理4 4 ) 設(shè)z 為問(wèn)題( p ) 的一個(gè)嚴(yán)格局部極小點(diǎn)， ，( ) ， n ( 工) ，i = 1 ，m ，h i c k ) ，j = 1 ，r 在礦的一個(gè)領(lǐng)域內(nèi)連續(xù)可微，進(jìn)一步， 設(shè)礦滿足m a n g a s a r i a n f r o m o v i t z 約束品性，那么存在礦，使得弘礦，礦 是問(wèn)題( q ) 的局部極小點(diǎn) 定理1 3 3 ( 見文f 1 0 9 7 定理4 6 ) 設(shè)命題1 2 ，3 的條件成立，則對(duì)任何滿足p2 m a x 店，ie 厶( 礦) ，i 口；i ，j = 1 ，2 ，r ) ，的罰參數(shù)蘆，礦是罰問(wèn)題( 爿1 ) 的 嚴(yán)格局部極小點(diǎn)。 在算法方面，盡管使用精確罰函數(shù)的歷史已經(jīng)很長(zhǎng)，由于已經(jīng)證明在傳統(tǒng)罰 函數(shù)定義下，若罰函數(shù)是簡(jiǎn)單的、光滑的，則一定是不精確的，這里所謂簡(jiǎn)單的 表示罰函數(shù)表達(dá)式中只含目標(biāo)函數(shù)和約束函數(shù)?？紤]問(wèn)題 ( p ) m i n m ) = 一z s t 夕( z ) = z 一1 0 1 0 上海大學(xué)博士學(xué)位論文 相應(yīng)的罰問(wèn)題 ( 兄)m i n q ( x ，弘) = 一+ pm a x ( o ，扛一1 ) ) 2 當(dāng)z 乏s 時(shí)，令q ( z ，p ) = 0 ，得z = 去+ 1 從而可知p - 0 0 ，礦= 1 為問(wèn) 題( p ) 是最優(yōu)解，顯然所給出的罰函數(shù)是可微的，但不是精確的。長(zhǎng)期來(lái)一直存 在著爭(zhēng)論，爭(zhēng)論的根源在于精確罰函數(shù)的不可微性從算法的角度來(lái)看，這種不 可微性能夠引起所謂的“m a r a t o s 效應(yīng)”，即引起阻止快速局部收斂的現(xiàn)象，為了克 服這一效應(yīng)，人們發(fā)展了所謂 w a t c h i n gd o gt e c h n i q u e ” 1 0 0 1 和“s e c o n d o r d e r c o r r e c t i o nt e c h n i q u e s ”【1 0 1 i 0 3 另外，一些學(xué)者引入了與上述精確罰函數(shù)完全不同類的可微精確罰函數(shù) 2 1 1 【2 8 】這類可微精確罰函數(shù)由于其表達(dá)式包含有目標(biāo)函數(shù)及約束函數(shù)的梯度，方 法大大地限制了其實(shí)際應(yīng)用，從上世紀(jì)九十年代后期開始非線性精確罰函數(shù)1 2 9 1 f 3 4 】得到了較廣泛的研究，同時(shí)對(duì)精確罰函數(shù)進(jìn)行了修正，非線性精確罰函數(shù) 2 9 1 f 3 4 】和低次罰函數(shù) 3 5 1 【3 6 】開辟了關(guān)于精確罰函數(shù)的新的研究領(lǐng)域，至今不斷有 新的研究成果問(wèn)世。 而對(duì)于傳統(tǒng)罰函數(shù)，若罰問(wèn)題是簡(jiǎn)單的、精確的，則一定的非光滑的。如 q o ，a ，肛) = ， ) + a m a x ( o ，吼 ) ) + p i 幻 ) i ，a 0 i = l j = 1 若罰問(wèn)題是精確的、光滑的，則罰問(wèn)題的表達(dá)式一定包含有f ( x ) ，g i ( x ) ，h j ( z ) 的 梯度。如對(duì)只含不等式約束問(wèn)題( p ) ，其罰函數(shù)為 q ( x ，a ，盯) = f ( x ) + a ( x ) t g ( x )( 1 3 1 ) = ，( z ) + a ( z ) + v f ( x ) g ( z ) + 曇( a + ( z ) 9 ( z ) r ) ( a + ( z ) 9 ( z ) ) ，( 1 3 2 ) 其中仃 0 ，a ( x ) a ( x ) = v f ( z ) ，a ( x ) = v g ( z ) ，a + ( z ) 表示矩陣a ( x ) 的廣義 逆這里q ( z ，a ，盯) 的表達(dá)式中包有，( z ) ，g i ( x ) 的梯度，這種表達(dá)式就變得復(fù)雜了 鑒于上述情況，我們考慮對(duì)傳統(tǒng)罰函數(shù)的定義進(jìn)行改變，改變后的罰函數(shù) 定義為z s 兮p ( z ) 0 ，甚至于p ( z ) 0 且遠(yuǎn)大于 當(dāng)z s 時(shí)，p ( x ) 的值按照這種改變，下節(jié)我們將介紹和討論簡(jiǎn)單光滑乘子 精確罰函數(shù)的現(xiàn)狀及我們所得到的某些結(jié)果 】1 上海大學(xué)博士學(xué)位論文 1 4 乘子精確罰函數(shù)方法 文f 3 7 】構(gòu)造一個(gè)改進(jìn)的指數(shù)型乘子罰函數(shù)，從而分析了極小化凸規(guī)劃問(wèn)題的 乘子指數(shù)型方法以及對(duì)偶情況，并給出了一種熵極小化算法，而且強(qiáng)化了方法的 有效收斂結(jié)果，在應(yīng)用到線性問(wèn)題時(shí)，給出了其收斂速度，以下對(duì)這一途徑作一 簡(jiǎn)單介紹，參文【3 7 】， 考慮非線性規(guī)劃問(wèn)題： 假使( 1 4 1 ) 的最優(yōu)解集非空且有界， 仁if ( x ) 0 其算法由下兩式給出 詁：1 m 。i 礦0 r 9 種r a i n + 萋篝妒( 弓北) ) ) ( 1 4 2 ) 瞄+ 1 = 磚e 哆g j ( z k ) ，j = l ，2 ，m ( 1 4 3 ) 其中腳 0 是相當(dāng)于第j 個(gè)約束的乘子，白 0 是罰參數(shù)。此外當(dāng)i ，鯫為凸 函數(shù)時(shí)，而相應(yīng)的對(duì)偶問(wèn)題為 嘶d ( p ) ( 1 4 4 ) 其中 = 蚴悱) + 腳鯽( z ) ) ( 1 叫 由此給出了熵極小化算法 黼似小霎爭(zhēng)c 鈔 a q 仇 2 = 0 0 ，vk ，則 礦) 收斂于對(duì)偶問(wèn)題( 1 4 4 ) 的最優(yōu)解，此 外，序列f 礦) 有界且其每一個(gè)聚點(diǎn)是原問(wèn)題( 1 4 1 ) 的最優(yōu)解 性質(zhì)1 4 5 ：( 見文【3 7 】命題4 2 ) 設(shè) 礦) 是f h ( 1 4 2 ) 和( 1 4 3 ) 產(chǎn)生的序列，罰參 數(shù)由磚= c 磁，vk ，這里常數(shù)c 0 ，假定 礦 收斂于m 。中的點(diǎn)，則 礦) 至 少是二次收斂的 f l 精確罰函數(shù)在那些使得對(duì)某個(gè)ie l ，2 ，m ) 成立蟲( z ) = 0 的z 處 不可徽，兩非線性規(guī)劃中大部分效果較好的算法都要求目標(biāo)函數(shù)具有可微性， 從而促使人們?nèi)ニ伎剂P函數(shù)的光滑化f 3 8 j ，【3 9 j ，f 4 0 j 文1 4 0 lp i n a r 和z e n i o s 針對(duì) 凸規(guī)劃問(wèn)題提出了對(duì)z l 精確罰函數(shù)的二次函數(shù)光滑逼近，并證明了通過(guò)解光滑 后的罰問(wèn)題，可以得到可行和艮近似全局極小點(diǎn)，這里多是常數(shù)。此外， 在1 9 9 9 年，d g o l d f a r b 和r p o l y a k 等在文【4 1 】“am o d i f i e db a r r i e r - a u g m e n t e d l a g r a n g i a nm e t h o df o rc o n s t r a i n e dm i n i m i z a t i o n ”中針對(duì)問(wèn)題( 1 2 1 ) 給m , - f 述形 式的修正障礙一增廣l a g r a n g i a n 函數(shù)。 lm ) 一 地i n ( 1 ( z ) ) 聊a 螄) = 一壹啪) + ；壹蜘) ，工刪q 。 f ”1 剃觚 1 4 上海大學(xué)博士學(xué)位論文 其中q = 扛i 吼( z ) ，l = 1 ，2 ，m ) 記 ”lr 工扛，u ，口) = ， ) + 牡t 皿( z ) + , j h a z ) ， i = 1 j = l i = il 皿( 礦) = o ) = 1 ，2 ，z ) ， 礦是問(wèn)題( 1 2 1 ) 的嚴(yán)格局部極小點(diǎn)，則有下述主要收斂結(jié)果： 定理1 4 1 ( 見【4 1 】定理5 1 ) 假定對(duì)問(wèn)題( 1 2 1 ) 在嚴(yán)格局部極小點(diǎn)礦處滿足 第二階最優(yōu)性充分條件，則存在b 0 ，6 0 ) 使得對(duì)任何 ( “，。，k ) = ( u ，k ) d ( u ，正k o ) = ( u ，k ) = ( t ，t ，k ) ii iu 一叫+ ij s6 k ，t “) 0 ，讓( m 1 ) 20 ，k 七o ) ， 0u0 有界，有： ( 1 ) f ( z ，t ，t ，k ) 在礦的某一開球內(nèi)有唯一極小點(diǎn)量= 圣( u ，口，k ) ( 2 ) 對(duì)p ，砬，：哦= u ( 1 一鏹 ) ) ，i = 1 ，2 ，m ，吩= 巧一七乃( 圣) ，歹= 1 ，2 ，r 成立 ”童一孑f f s ；l f 。一。+ | | ，f | 。塒f j s ；”。一。f | 其中 d = ( 豇，o ) 和c 0 與k 無(wú)關(guān) 定理1 4 2 ( 見【4 1 定理5 2 ) 假定對(duì)問(wèn)題( 1 2 1 ) 在全局最優(yōu)解礦滿足第二階 充分條件并假定存在k o 0 使得對(duì)所有固定仳0 和口及所有有限數(shù)。冰平 集k ( 釷， ，) = z j pif ( z ，u ， ，) sd ) 為有界集，則當(dāng) 0 充分大 使得對(duì)任何( t ，。，k ) d p ，j ，k o ) 定理1 5 1 中的點(diǎn)童是f ( z ，u ， ，k ) 的全局最 優(yōu)解。 下面我們將給出關(guān)于指數(shù)型及對(duì)數(shù)型兩類乘子精確罰函數(shù)的新形式，并討 論某些相關(guān)的結(jié)論。若在問(wèn)題( p ) 中，xcj p 為有界閉箱，( z ) ，吼( z ) ， = 1 ，2 ，m 為光滑函數(shù)，則相應(yīng)的指數(shù)型及對(duì)數(shù)型乘子精確罰函數(shù)分別表示為： 】5 上海大學(xué)博士學(xué)位論文 1 指數(shù)型 m i n q ( z ，a ，肛) 舊訓(xùn)一訓(xùn)卅去喜e 棚 其中p 0 為罰參數(shù)，而九20 ，i = 1 ，m ，與原問(wèn)題乘子有關(guān)的參數(shù) 2 對(duì)數(shù)型 m i n q ( o ，a ，p ) q 馴x x ：m n 妻i n ( 1 - , x i z g i ( z ) ) r i = 1 或 m i n q ( z ，a ，肛) q m x x ：m ) 一：勘n ( 1 - # g l ( z ) ) 嚴(yán)t = l 其中p 0 為罰參數(shù)，而九20 ，i = 1 ，m ，為與原問(wèn)題乘子有關(guān)的參數(shù) 我們討論7 c ( p ) 、l ( p ) 與g ( q 盧) 、l ( q p ) 之間的關(guān)系，發(fā)現(xiàn)九0 ，i = 1 ，2 ，m 與原問(wèn)題( p ) 的乘子有著密切的聯(lián)系，從而我們稱它們?yōu)楹?jiǎn)單光滑乘 予精確罰函數(shù)。 特別需要指出的是在求解某類凸規(guī)劃時(shí)，我們運(yùn)用上述形式的乘子精確罰函 數(shù)，用牛頓法求解時(shí)，效果很好，具一致全局線性收斂性和局部二次收斂性 1 6 上海大學(xué)博士學(xué)位論文 第二章乘子精確罰函數(shù)法 2 1引言 考慮約束非線性規(guī)劃問(wèn)題 ( p )m i n ，( 。) ，z s 其中s = 伽x i 蟲0 ，i = l ，m ) ，這里j i mf ( z ) = + o 。，( 。) ，蟲( z )