摘要 約束非線性規(guī)劃在經(jīng)濟(jì)金融、工程控制、技術(shù)物理、物流配送、 計算機(jī)科學(xué)及生物工程等各個領(lǐng)域有著廣泛的應(yīng)用。近年來，隨著理 論研究的深入和計算機(jī)技術(shù)的普及和發(fā)展，人們開始嘗試把一些計 算復(fù)雜度小、穩(wěn)定性好、收斂性強(qiáng)的算法拓展到求解非線性規(guī)劃問 題。其中，內(nèi)點算法的研究尤為引入注目。內(nèi)點算法的基本思想是從 問題可行域中的某一點出發(fā)，沿著中心路徑進(jìn)行搜索，直達(dá)問題的最 優(yōu)解。不過，內(nèi)點算法在非線性規(guī)劃中的實際研究、證明和測試中還 是遇到了許多的障礙。 首先，對于具有大規(guī)模約束的問題，如何尋找一個初始的可行點 是內(nèi)點法中研究的課題。在線性規(guī)劃問題中，我們可以采用一些非 可行內(nèi)點算法的技巧，例如在某一步迭代過程中選取全牛頓步長等 等。研究表明，在錐優(yōu)化模型中，可以通過引入自對偶嵌入模型來克 服初始點選取的困難。但這些技巧不適用于一般的非線性規(guī)劃問題。 其次，在路徑跟蹤內(nèi)點算法中，由于正交性條件的不滿足，如何證明 算法的收斂性，也是要進(jìn)行探索的問題。 本文主要的工作是結(jié)合內(nèi)外罰函數(shù)給出了求解約束非線性規(guī)劃 的內(nèi)點方法。針對上的問題，我們作了以下二方面的工作，一、通過 引入輔助變量來構(gòu)造原問題的等價問題，從而克服了初始點選取的 難題。然后，給出相應(yīng)的k k t 條件和罰內(nèi)點算法，并采用w o l f 條件設(shè) 計了一個可調(diào)的內(nèi)嵌算法，進(jìn)一步證明了算法的收斂性，數(shù)值試驗也 說明了新給出的算法是可行的、有效的。二、在前工作的基礎(chǔ)上，構(gòu) 造修正的k k t 條件，給出了大步長路徑跟蹤內(nèi)點算法，通過添加關(guān)系 不等式條件，給出并證明路徑跟蹤算法的收斂性定理，相應(yīng)的數(shù)值算 飼也說明了新給出的算法是可行的、有效的。 本文結(jié)構(gòu)共分為四章，在第一及第二章，我們簡單介紹了內(nèi)點算 法基本概念、發(fā)展歷史及分類，并對對數(shù)障礙函數(shù)法和原對偶一路徑 跟蹤法的思想作了較詳細(xì)的介紹。第三章，給出了線搜索下的罰內(nèi)點 算法，并證明了算法的收斂性，第四章，給出了大步長路徑跟蹤內(nèi)點 算法，并證明了算法的全局收斂性。相應(yīng)的數(shù)值算例也說明了新給出 的算法是可行的、有效的。 關(guān)鍵詞：約束非線性規(guī)劃；罰函數(shù)方法；內(nèi)點法；牛頓方程；k k t 條- 件 a b s tr a c t i i i 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 gh a sb e e nw i d e l yu s e di n e c o n o m y & f i n a n c e ，e n g i n e e r i n gc o n t r o l ，t e c h n i c a lp a y s i c s ，l o g i s t i c s t r a n s s h i p m e n t ， c o m p u t e rs c i e n c e ，b i o c h e m i c a lc o n s t r u c t i o na n dm a n yo t h e rf i e l d s r e c e n t l y , w i t hd e v e l o p m e n to ft h e o r yr e s e a r c ha n dc o m p u t e rt e c h n o l o g y , s o m ee f f e c t i v e a l g o r i t h m sw i t hl e s st i m ec o m p l e x i t y , g o o ds t a b i l i t ya n dc o n v e r g e n c eh a v e b e e n t r i e dt os o l v en o n l i n e a r p r o g r a m m i n g a m o n gt h e m ，i n t e r i o rp o i n tm e t h o dw o n m o s ta t t e n t i o n s t h eb a s i ci d e ao fi n t e r i o rp o i n tm e t h o di st os e l e c ta ni n i t i a l p o i n ti nf e a s i b l er e g i o na n dt h e ni t e r a t ea l o n gt h ec e n t r a lp a t ht i l lr e a c h i n g t h eo p t i m a lp o i n t h o w e v e r ，m a n yd i f f i c u l t i e so c c u rw h i l er e s e a r c h i n g ，t e s t i n g ， c o n v e r g e n tp r o o f i n gt h ea l g o r i t h mf o rs o l v i n gn o n l i n e a rp r o g r a m m i n g f i r s t l y , f o rp r o b l e mw i t hm a n yc o n s t r a i n t s ，h o wt of i n da ni n i t i a lf e a s i b l e p o i n ti sar e s e a r c ht o p i c i nl i n e a rp r o g r a m m i n g ，r e s e a r c h e r sp r e s e n ts e v e r a l s t r a t e g i e st oo v c r c o n l et h i s ( 1 i t f i ( 。u l t y ，s c ci n f l 、 l s i t ) l c - i n t c r i o r - i ) o i n tm e t h o d ，s i r h a s ，t a k eaf u l ln e w t o ns t e pa ta n yi t e r a t i o n w i t h i nt h ef r a m e w o r ko fc o n i c o p t i m i z a t i o n ，ap o s s i b l er e m e d yo ft h ep r o b l e mi st oe m b e dt h ep r i m a la n d d u a lf o r m u l a t i o n so ft h ep r o b l e mi n t oa s i n g l es e l f - d u a lm o d e l ，w h i c ht h e n h a sa ne a s ya v a i l a b l ei n i t i a lf e a s i b l es o l u t i o n h o w e v e rt h e s es t r a t e g i e sa r e n o te f f e c t i v ef o rn o n l i n e a rp r o g r a m m i n g s e c o n d l y , d u et o u n s a t i s f a c t o r yo f o r t h o g o n a l i t yc o n d i t i o n ，h o wt op r o o fc o n v e r g e n c eo fp a t h f o l l o w i n ga l g o r i t h m i ss t i l la t o p i c t h em a j o rw o r ki st oi n t e g r a t ei n t e r i o rp o i n tm e t h o dw i t hi n n e r - o u t e r p e n a l t yf u n c t i o n sf o rs o l v 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 g i nl i g h to f d i f f i c u l t i e sm e n t i o n e da b o v e ，o u rw o r ki n c l u d e st w o p a r t s f i r s t l y , i n c o r p o r a t e a na u x i l i a r yv a r i a b l ew h i c hi sd r i v e nt oz e r ob yp e n a l i z a t i o na n d t h e nc o n s t r u c t an e wp r o b l e me q u a lt oo r i g i n a lo n e d u et ot h i sa u x i l i a r yv a r i a b l e ，t h ep r o b l e m o fi n i t i a l i z a t i o ni sc i r c u m v e n t e d t h e c o r r e s p o n d i n gk k tc o n d i t i o n sa sw e l la s p e n a l i z e di n t e r i o rp o i n ta l g o r i t h ma r eg i v e ns u b s e q u e n t l y w ed e s i g na ni n n e r 上海大學(xué)碩士學(xué)位論文 a l g o r i t h mb a s e do nw o l fc o n d i t i o n sa n dp r o o fc o n v e r g e n c eo fo u t e ra n di n n e r a l g o r i t h m sr e s p e c t i v e l y r e s u l t so ft h en u m e r i c a le x p e r i m e n ta r er e p o r t e dt o s h o wt h ea l g o r i t h mi sp r a c t i c a la n de f f e c t i v e s e c o n d l y ，b a s e do nt h ew o r k d o n e1 ) e h ) r e w ei ) r o p o s em o d i f i e dk k tc o n d i t i o n s 嬲w e l la sl o n g s t e pp a t h f o l l o w i n ga l g o r i t h m f o r m u l aa s s u m p t i o ni sd e s c r i b e da n dt h e nt h ea l g o r i t h m i sp r o v e dt ob ec o n v e r g e n t r e s u l t so ft h en u m e r i c a le x p e r i m e n ta r er e p o r t e d t os h o wt h ea l g o r i t h mi sp r a c t i c a la n de f f e c t i v e t h e p a p e rc o n s i s t so ff o u rc h a p t e r s i nc h a p t e ro n ea n dt w o ，w ed e s c r i b e t h eb a s i cc o n c e p ta n dd e v e l o p m e n th i s t o r yo fi n t e r i o rp o i n tm e t h o d s o m e c l a s s i ci n t e r i o rp o i n tm e t h o d sa r ep r e s e n t e dt h e r e ，w h e r el o g a r i t h mb a r r i e r f u n c t i o nm e t h o da n dp r i m a l d u a lp a t hf o l l o w i n gm e t h o da r ei n t r o d u c e di n d e t a i l s i nc h a p t e rt h r e e ，w ed e s i g nap e n a l i z e di n t e r i o rp o i n ta l g o r i t h mb a s e d o nl i n es e a r c hc o n d i t i o n sa n dp r e s e n tc o n v e r g e n tt h e o r e m s ap e n a l i z e di n t e r i o r p o i n ta l g o r i t h mb a s e do np a t hf o l l o w i n gm e t h o di sg i v e ni nc h a p t e rf o u rw h i l e s e v e r a lc o n v e r g e n tt h e o r e m sa r ep r o v e dt h e r e n u m e r i c a lr e s u l t sa r er e p o r t e d t os h o wa l g o r i t h m sa r ep r a c t i c a la n de f f e c t i v er e s p e c t i v e l y k e yw o r d 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 ；p e n a l t yf u n c t i o n m e t h o d ；i n t e r i o rp o i n tm e t h o d ；n e w t o ne q u a t i o n ；k k tc o n d i t i o n s i v 原創(chuàng)性聲明 3 本人聲明：所呈交的論文是本人在導(dǎo)師指導(dǎo)下 進(jìn)行的研究工作。除了文中特別加以標(biāo)注和致謝的 地方外，論文中不包含其他人已發(fā)表和撰寫過的研究 成果。參與同一工作的其他同志對本研究所做的任 何貢獻(xiàn)均已在論文中作了說明并表示了謝意。 簽名：一日期：一 本論文使用授權(quán)說明 本人完全了解上海大學(xué)有關(guān)保留、使用學(xué)位論 文的規(guī)定，即：學(xué)校有權(quán)保留論文及送交論文復(fù)印 件，允許論文被查閱和借閱；學(xué)?？梢怨颊撐牡?全部或部分內(nèi)容。 簽名：畔導(dǎo)師簽名嫗日期：業(yè) 上海大學(xué)碩士學(xué)位論文 第一章緒論 非線性規(guī)劃是2 0 世紀(jì)5 0 年代才開始形成的一門新興學(xué)科，現(xiàn)已成 為運(yùn)籌學(xué)的一個重要分支，它在工程、管理、經(jīng)濟(jì)、科研、軍事等方 面都有廣泛的應(yīng)用，為最優(yōu)設(shè)計提供了有力的工具。1 9 5 1 年h w 庫恩 和a w 塔克發(fā)表的關(guān)于最優(yōu)性條件( 后來稱為庫恩一塔克條件) 的論文 是非線性規(guī)劃正式誕生的一個重要標(biāo)志。在2 0 世紀(jì)5 0 年代還得出了可 分離規(guī)劃和二次規(guī)劃的多種解法，它們大都是以g b 丹齊克提出的解 線性規(guī)劃的單純形法為基礎(chǔ)的。5 0 年代末n 6 0 年代末出現(xiàn)了許多解非 線性規(guī)劃問題的有效的算法，7 0 年代、8 0 年代又得到進(jìn)一步的發(fā)展。 隨著研究的深入，人們開始嘗試把一些成熟的、有效的線性規(guī)劃 算法拓展到求解非線性規(guī)劃問題。其中內(nèi)點算法的研究最引入注目。 內(nèi)點算法的提出最初是為了克服單純性算法的缺陷。單純性算法的 時間復(fù)雜度是指數(shù)形式的，在運(yùn)用計算機(jī)編程調(diào)試時，每一步迭代必 然導(dǎo)致內(nèi)存需要存貯大量的數(shù)據(jù)，因此在求解一些大規(guī)模的問題時 就顯得效率不高。這個缺陷促使人們迫切尋找到一種新的、更行之有 效的算法，對此人們作了很多的嘗試也得到了一些結(jié)果。 1 9 7 9 年，蘇聯(lián)學(xué)者哈奇揚(yáng)提出了第一個多項式算法一橢球算法1 1 】， 并證明了計算復(fù)雜性是0 ( n 4 l ) ，這引起了人們極大的熱情，對算法復(fù) 雜度理論產(chǎn)生了巨大的影響。但是該法在實際上并沒有如期所希望 的那樣在計算速度上超過單純形法。原因主要有二：一是迭代次數(shù)仍 然很多；二是不便應(yīng)用稀疏矩陣技術(shù)，每次迭代的計算比單純形法慢 很多。 1 9 8 4 年，n k a r m a r k a r 提出了線性規(guī)劃的一種新的多項式算法 2 】，k a r m 上海大學(xué)碩士學(xué)位論文 a r k a r 算法不僅比橢球算法具有更優(yōu)越的計算復(fù)雜度，而且在實際計 算中也可以與單純形法相媲美，尤其對大規(guī)模問題更顯其高效性。與 單純形算法沿著可行區(qū)域的邊界尋優(yōu)不同，k a r m a r k a r 算法是建立在 單純形結(jié)構(gòu)之上的，它是從初始內(nèi)點出發(fā)，沿著最速下降方向，從可 行區(qū)域內(nèi)部逐漸走向最優(yōu)解，因此k a r m a r k a r 算法又被稱為內(nèi)點算法。 自從k a r m a r k a r 劃時代的論文發(fā)表以來，內(nèi)點算法一直是數(shù)學(xué)規(guī) 劃領(lǐng)域一個非?；钴S的研究方向。很多研究者在k a r m a r k a r 法的基礎(chǔ) 上對算法作了各種修正或改進(jìn)。首先的改進(jìn)包括各種問題形式的列 出；起始可行解的計算；近似最速下降投影方向的計算以及的帶稀疏 性矩陣的方程組的解算；每步跌代的目標(biāo)函數(shù)下界的計算；以及每步 跌代時為加快收斂的參數(shù)a 的選擇等。這方面已發(fā)表的文章很多，典 型的可舉出5 ，6 1 等等。 另一方面，從理論上的不同方面發(fā)展了作為k a r m a r k a r 法的變種 的其他內(nèi)點法。在這些方法中，值得提出的有【7 】和 8 】等人發(fā)展的原 仿射比例調(diào)節(jié)法和a d l e r 9 ，1 0 1 等人提出的對偶仿射比例調(diào)節(jié)法等。此 外，1 9 8 6 年g i l l 1 l i 等人第一次把原來用于非線性規(guī)劃的對數(shù)障礙函數(shù) 法應(yīng)用于線性規(guī)劃，并且證明了對數(shù)障礙函數(shù)法和k a r m a r k a r 投影法是 等價的，以后的研究進(jìn)一步表明了k a r m a r k a r 法實際上是廣義對數(shù)障礙 函數(shù)法的一個特殊情形。此后m e g i d d o ，k o j i m a ，l u s t i g 和m e h r o t r a 等人 又提出了原對偶路徑跟蹤對數(shù)障礙函數(shù)法，以及”極限可行方向 原一對 偶路徑跟蹤法，全面收斂不可行內(nèi)點算法和m e h r o t r a 預(yù)計改正等改進(jìn) 方法 1 2 1 一 1 5 1 ，這些方法都是很有效的，計算復(fù)雜性達(dá)到0 ( 佗3 ) 。類似 的方法還有g(shù) o n z a g a 和y e 等提出勢函數(shù)下降法 4 ，1 6 ，17 】。他們方法優(yōu)點 是采用大步長，并且也證明了計算復(fù)雜性也達(dá)到0 ( n 3 己) 。 在k a r m a r k a r 法提出后，在對內(nèi)點法的實際編程并與單純形法的 2 上海大學(xué)碩士學(xué)位論文 優(yōu)秀商用軟件對比方面，開始直接按k a r m a r k a r 法編程的測試并未表明 他的明顯優(yōu)越性。1 9 8 6 年a d l e r 等人應(yīng)用k a r m a r k a r 法變種的所謂對偶仿 射法編程，并對d a v i d g a y 所收集的約5 0 個問題的n e t l i b 問題集與單純 形法商用軟件m i n o s 4 0 進(jìn)行了對比測試。對比表明，對較大型問題來 說，內(nèi)點法要明顯的優(yōu)于單純形法【9 ，1 1 】。1 9 9 2 年l u s t i g 1 8 1 等人用原一對 偶路徑跟蹤法并采用一系列的改進(jìn)技術(shù)進(jìn)行了編程，并與比m i n o s 系 統(tǒng)快2 1 0 倍的最新單純形法商用軟件i b mo s l r e l e a s e 2 1 9 進(jìn)行了對比測 試，對比的問題是比n e t l i b 問題大得多的8 個( 幾千幾萬行和幾萬幾 十萬列) 的大問題。結(jié)果表明，除了一個問題特殊之外，對其他問題 內(nèi)點法比單純形法快2 5 - 2 0 倍。更為壯觀的是，用原一對偶有效地解決 了大至9 9 5 3 3 ( 行) 1 1 7 1 1 7 ( 列) 和2 7 0 7 9 6 x 3 0 3 9 6 的兩個大問題，而這種 大問題單純形法是從未涉足過的。 內(nèi)點算法區(qū)別其他算法的一個特性是由算法產(chǎn)生的迭代點都是 向最優(yōu)點”邁進(jìn)了一大步，從不走任何彎路”。它不是圍繞著可行區(qū)域 的邊界尋找最優(yōu)點，而是在可行域內(nèi)部迭代，因此當(dāng)他到達(dá)可行域的 邊界時就說明已經(jīng)到達(dá)了最優(yōu)點。 內(nèi)點算法的諸多優(yōu)點都吸引著人們把它拓展到求解其他的問 題，包括非線性規(guī)劃問題。1 9 9 4 年，n e s t e r o v 和n e m i r o v s k i 提出了s e l f - c o n c o r d a n t 障礙理論 3 7 】，它是把內(nèi)點算法思想拓展到求解一般凸最 優(yōu)化問題的理論基礎(chǔ)。在此理論基礎(chǔ)上，內(nèi)點算法被應(yīng)用于有效地解 決一類的凸優(yōu)化問題?，F(xiàn)在，內(nèi)點算法的思想已被廣泛的應(yīng)用于研究 和求解非線性規(guī)劃問題 4 8 1 一 5 6 】，不過，內(nèi)點算法在非線性規(guī)劃中的實 際研究、證明和測試中還是遇到了許多的障礙。 由于內(nèi)點算法的特性保證由一個初始可行點產(chǎn)生的一系列迭代點 都是嚴(yán)格可行的，因此選擇一個初始的可行點就顯得尤為重要。但對于 3 上海大學(xué)碩士學(xué)位論文 一般的大規(guī)模問題，一個可行的初始點并不是容易得到的。為此人們也 作了大量的研究工作，希望來克服這一難題。1 9 9 4 年，y e ，y ，t o d d ，m i z u n o 提 出了求解線性規(guī)劃的自對偶嵌入方法 3 3 】，解決了尋找初始可行點的 困難且保證嵌入問題有最優(yōu)解，并可利用任何內(nèi)點算法來求解，從 而也得到了原問題的最優(yōu)解。對一般的線性規(guī)劃問題也可采用一些 非可行內(nèi)點算法的技巧，例如在某一步迭代過程中選取全牛頓步長 等等。到了2 0 0 0 年，l u o ，z q ，s t u r m ，。i f 和z h a n g ，s 提出了把自對偶嵌 入技術(shù)推廣到s d p 及更一般錐優(yōu)化問題 3 6 】，從而使初始化難題得到解 決。2 0 0 4 年，z h a n g ，s 提出了解決凸規(guī)劃的一個新自對偶嵌入技術(shù) 3 9 】。 該方法的思想是先把凸規(guī)劃轉(zhuǎn)化為等價的錐優(yōu)化問題，然后運(yùn)用自 對偶嵌入技術(shù)來解決由此產(chǎn)生的錐優(yōu)化模型。其優(yōu)點是初始化難題 得到了克服。不過這些方法并不適用于一般的非線性規(guī)劃問題，因 此，關(guān)于求解非線性規(guī)劃問題的初始化難題也成為了一個重要的研 究課題。 作為內(nèi)點算法獨有的特征，中心路徑在算法中扮演著重要的角 色，因而路經(jīng)跟蹤算法也就成為了內(nèi)點算法中一個重要的組成部分。 路經(jīng)跟蹤算法的思想是使每一步產(chǎn)生的迭代點均落在中心路徑周圍 的一個帶狀區(qū)域，直至問題的最優(yōu)解。在該算法的收斂性證明中，要 求迭代方向相互正交。這一條件在一般的線性規(guī)劃問題中自然成立。 但對于非線性的問題，就不一定滿足了。這也成為了該算法能普遍有 效地應(yīng)用于求解非線性規(guī)劃問題的一大障礙。 本文主要是結(jié)合內(nèi)外罰函數(shù)給出了求解約束非線性規(guī)劃的內(nèi)點 方法。針對上述提到的兩個問題，作了以下二方面的工作，一、通 過引入輔助變量，構(gòu)造原問題的等價問題，并在罰內(nèi)點算法的設(shè)計 中，使輔助變量逐步被”罰”為零，從而克服了初始點選取的困難。然 4 上海大學(xué)碩士學(xué)位論文 后，給出了相應(yīng)的k k t 條件、在牛頓法的基礎(chǔ)上，設(shè)計了一個罰內(nèi)點 算法，并證明了所給算法是收斂的。同時結(jié)合線搜索在w o l f 條件下設(shè) 計了可調(diào)的內(nèi)嵌算法，來修正牛頓步。進(jìn)一步證明了該算法的全局收 斂性，數(shù)值試驗說明了所給算法是可行的、有效的。二、在前工作的 基礎(chǔ)上，構(gòu)造修正的k k t 條件，然后通過調(diào)節(jié)迭代參數(shù)，控制每一步 的迭代都落在中心路徑的一個較寬泛的帶狀區(qū)域內(nèi)，從而設(shè)計出大 步長路徑跟蹤內(nèi)點算法。通過添加關(guān)系不等式條件，證明了算法的收 斂性。相應(yīng)的數(shù)值算例也說明了新給出的算法是可行的、有效的。 5 上海大學(xué)碩士學(xué)位論文 第二章幾類經(jīng)典的內(nèi)點算法 在本章中，我們將主要介紹幾類經(jīng)典的內(nèi)點算法，它們分別是 k a r m a r k a r 算法 仿射比例調(diào)節(jié)法 對數(shù)障礙函數(shù)法 原一對偶路徑跟蹤法 勢函數(shù)下降法 這些算法都是用以求解線性規(guī)劃問題。通過對這些算法的研究和分 析，掌握各類算法的思想和優(yōu)缺點，從而為后面兩章中運(yùn)用內(nèi)點算法 求解非線性規(guī)劃問題的研究打下基礎(chǔ)。 2 1內(nèi)點算法簡介 在非線規(guī)劃問題中，對數(shù)障礙函數(shù)法和原一對偶路徑跟蹤法應(yīng)用 得最為廣泛 4 1 】- 4 7 】，因此，會后面的幾節(jié)中作詳細(xì)的介紹，這里就對 剩下的三個算法作一個簡單的介紹。 k a r m a r k a r 算法：1 9 8 4 年，在美國貝爾實驗室工作的數(shù)學(xué)家k a r m a r k a r 提 出了一個多項式算法一- - k a r m a r k a r 算法，他的時間復(fù)雜度是o ( n 3 5 l ) ， 而且聲稱他比單純刑法更為有效。在當(dāng)時，k a r m a r k a r 的名字和k a r m a r k a r 的 算法被刊登在紐約時代雜志的頭版，盡管當(dāng)時他的主張受到同行許 多專家學(xué)者的質(zhì)疑。今天看來，k a r m a r k a r 顯然開創(chuàng)了線性規(guī)劃的一個 6 上海大學(xué)碩士學(xué)位論文 新領(lǐng)域一一內(nèi)點算法。在此之后，k a r m a r k a r 算法得到不斷地改進(jìn)。線 性規(guī)劃、凸二次規(guī)劃的內(nèi)點算法相繼問世。已經(jīng)證實，如果通過好的 程序來實現(xiàn)內(nèi)點算法，包括最初的k a r m a r k a r 算法，的確可以得到比單 純形法更好的效果。特別是對于含幾千個以上變量的大規(guī)模問題，他 的收斂性態(tài)完全優(yōu)越于單純形法。更令人吃驚的是，在實際計算中發(fā) 現(xiàn)內(nèi)點算法的迭代次數(shù)幾乎與問題的規(guī)模無關(guān)，這一事實也是內(nèi)點 算法在理論尤其是實踐中引人注目的重要因素。 仿射比例調(diào)節(jié)法：是k a r m a r k a r 法中變換方法。它是用一個仿射變 換d i l x 代替投影變換，以投影目標(biāo)函數(shù)替代勢函數(shù)，把坐標(biāo)系的正掛 限( 而不是單純形) 映射到自身，把每次跌代的變量值z 七變換成與各 坐標(biāo)面等距的e 。 早在1 9 6 7 年蘇聯(lián)學(xué)者d i k i n 7 ，2 0 就首先提出了這種方法，并于1 9 7 4 年 給出了收斂性的證明。但他的這些工作直s j b a r n e s 等人再次研究該法 后被人們所發(fā)現(xiàn)。1 9 8 5 年，b a r n e s 8 】和v a n d e r r e i 2 1 等人詳細(xì)研究稱為 原仿射法，到了1 9 8 7 年a d l e r 9 等提出另一種仿射比例調(diào)節(jié)法，由于它 實際上是從原問題的對偶問題出發(fā)，因而被稱之為對偶放射比例調(diào) 節(jié)法。 勢函數(shù)下降法：是g o n z a g a 4 ，2 s 和y e 與t o d d 2 7 ，2 9 1 等提出的基于 勢函數(shù)下降的原勢函數(shù)下降法和原一對偶勢函數(shù)下降法，其迭代次數(shù) 為o ( 何l ) 。在這方面作出貢獻(xiàn)的還有t a n a b e 3 0 、g 2 1 e r 3 1 和k o j i m a 等 3 2 。 從歷史的角度，最早k a r m a r k a r 原算法就是用勢函數(shù)進(jìn)行推導(dǎo)的 2 】。 這種早期的方法對隨后發(fā)展的路徑跟蹤方法提供了有用的理論上的 透視，因此很自然的激起人們繼續(xù)研究這類方法。另一方面，就路徑 跟蹤法來說，實際所用的方法已消除了很多對路徑跟蹤的限制，因此 導(dǎo)致了理論與實踐之間的變樣。而勢函數(shù)法正好能把理論與實踐更 7 上海大學(xué)碩士學(xué)位論文 緊密地聯(lián)系起來，因為諸如搜索方向的選擇，步長的確定以及它們的 分析都可依據(jù)一個確定的勢函數(shù)( 或優(yōu)勢函數(shù)) 來進(jìn)行。這個勢函數(shù) 可作為測度來衡量一個點的質(zhì)量以及指示怎樣對他進(jìn)行改進(jìn)。采用 一個適當(dāng)?shù)乃惴ㄔ诿看蔚际乖搫莺瘮?shù)盡可能減少，因而導(dǎo)致相 應(yīng)算法的計算復(fù)雜性。 2 2 對數(shù)障礙函數(shù)法 對數(shù)障礙函數(shù)法首先是引進(jìn)解非線性規(guī)劃問題，即 m i nm ) ( 2 2 1 ) 2 s t g i ( x ) 0 ， i = 1 ，2 ，仇 式中，z = ( z 1 ，z 2 ，z n ) 丁。引用對數(shù)障礙函數(shù)把上面問題轉(zhuǎn)換為如下 形式的非約束條件問題： m i n f ( x ) 一肌l n g i ( x ) ( 2 2 2 2 ) i = 1 式中，肌是一個障礙參數(shù)，且有，南 o 和 1 i m ，= 0 算法是從一嚴(yán)格可行點出發(fā)，以一迭代形式選取，z 南和使( 2 2 2 ) 式 為最小的礦，產(chǎn)生的一系列可行點z 南收斂于( 2 2 2 ) 的解，而 _ j c l 。i m 。仇# ( z k 酉- a i ( 2 2 3 ) _ j c o o 肌( z 擰j 、 這里九是關(guān)于吼( z 七) 的最優(yōu)拉格朗日乘數(shù)。 對數(shù)障礙函數(shù)法應(yīng)用于線性規(guī)劃問題，可從原問題形式或?qū)ε?問題形式出發(fā)。前者稱為原對數(shù)障礙函數(shù)法，后者稱為對偶對數(shù)障礙 函數(shù)法。下面分別論述。 8 上海大學(xué)碩士學(xué)位論文 g i l l 等 1 l 】( 1 9 8 6 ) 把原對數(shù)障礙函數(shù)法應(yīng)用于線性規(guī)劃，且考慮如 下標(biāo)準(zhǔn)形式的線性規(guī)劃問題： 式中，a 艫跏( m 扎) 。 把上面問題轉(zhuǎn)換成 m i nc t x s t a x = b x 0 ( 2 2 4 ) m i n f ( x ) = c r x p l n j = l ( 2 2 5 ) s t a x = b 這里是對非負(fù)約束引用了障礙參數(shù)p ，而對等式約束，由于不能用障 礙交換處理，因此仍以約束條件形式直接處理。對這些等式約束條件 引進(jìn)相應(yīng)的拉格朗日乘數(shù)列向量丌，則( 2 2 5 ) 的拉格朗日武為 求其最小值，條件為其對x 和丌的偏導(dǎo)數(shù)為零，即 ( 2 2 6 ) v = l = c p d 一1 e a t 丌= o ( 2 2 7 ) v 丌l = 一a x + b = 0 注意，式中用d 代表其對角線元素分別# 7 x j ( j = 1 ，2 ，禮) 的對角方 陣，e 為n 個元素都為1 的幾維列向量。 非線性規(guī)劃中f 均n e w t o n 法，是把函數(shù)f ( z ) 按如下的泰勒級數(shù)展 開： f ( z 七十1 ) = f ( z 七) + v t f ( z 七) a x 七- f 去( z 七) t v 2 f ( z 七) a x 七 9 一z a r 丌一 巧 n 。蘆 p z， = 肛 丌 z 乙 上海大學(xué)碩士學(xué)位論文 其中略去高于二次的近似，增量為a x 七= x k + 1 一x 七。求該函數(shù)在a x 七方 向上的最小值，是該函數(shù)a x 七的每個分量求導(dǎo)數(shù)后并令其為零，因而 得出下7 1 關(guān)系： 一v 2 f ( x 七) a x 七= v t f ( x 七)( 2 2 8 ) 注意，這里取a x 血為n e w t o n 方向( 最速下降方向) 。 對問題( 2 2 5 ) 應(yīng)用n e w t o n 法( 即可行點最速下降法) 。如當(dāng)前的迭 代點礦滿足a 擴(kuò)= 6 的條件，下一次估計的最優(yōu)解為 z 七+ 1 = z 七+ q p b( 2 2 9 ) 即處于n e w t o n 搜索方向上，這里a 是某個適當(dāng)?shù)拇笥诹愕牟介L參數(shù)， 且p b 和q 的計算必須保證a 礦+ 1 = 6 和f ( x 七+ 1 ) o 的起始可行解 b e g i n k ：= 0 x ：= x 0 ，l ：= ，0 w h i l el i r l i o rp e “ d o p ：= p 肛 d ：= d i a g ( x l ，x 2 ，z ，1 ) g ：= d c 一弘e 丌：= ( a d 2 a 丁) 一1 a d g 7 7 ：= c a 丁7 r r ：= d q p e 1 1 ( 2 2 1 1 ) ( 2 2 1 2 ) ( 2 2 1 3 ) ( 2 2 1 4 ) 上海大學(xué)碩士學(xué)位論文 p ：= 一p id r 一1 ，噻 字i 功 0 和a x o = b 。這個假定可通 過在原問題( 2 2 4 ) 中引進(jìn)入x - 交量列，并用。兩階段”法或“大m 。法 來處理。如果用后者方法，則問題變?yōu)?( p ) m i n c t x + m x 幾+ 1 s t a x + ( b a x o ) z 幾+ 1 = b ( 2 2 1 5 ) x 0 ，x 幾+ 1 0 式中，m 是一大數(shù)。該問題的起始可行解為z = x o ，z n + 1 = 1 ，其中z o 為 任意值，由于m 足夠大，因此假定i ；1 題具有可行解，則必有x n + 1 = 0 ， 即問題( 2 2 1 5 ) 的最優(yōu)解就是( 2 2 4 ) 的最優(yōu)解。 2 ) 步長參數(shù)q 的選擇 為加快收斂，可以在保證不破壞可行性的條件下適當(dāng)加大每步 迭代的步長。這可在每步迭代時按下式找到口： q = 7 瑰 字i 殤 0 時有惟一的 最優(yōu)解，這個惟一的最優(yōu)解所構(gòu)成的曲線 z ( ，z ) i p o ) 稱為一條路徑或 中心軌跡( c e n t r a lt r a j e c t o r y ) ，當(dāng)肛_ 0 時z ( p ) 的極限即為原問題的最優(yōu) 解。 k o j i m a 等最早( 1 9 8 7 ) 1 3 ，2 3 】提出收斂的算法。之后m o n t e i r o 和a d l e r 2 4 ， 2 5 】以及其他研究者【1 4 ，2 6 】對算法都作了進(jìn)一步的改進(jìn)，使計算復(fù)雜性 達(dá)到0 ( 禮l ) 迭代和全部o ( n 3 三) 次算術(shù)運(yùn)算的水平。 1 4 上海大學(xué)碩士學(xué)位論文 為討論其算法，考慮如下標(biāo)準(zhǔn)形式的原問題和對偶問題對： ( p ) m i nc r z s t a x = b ( 2 3 。2 2 ) x 0 ( d ) m a x b t y s t a 丁y + z = c ( 2 3 2 3 ) z 0 這里a 是t i t n 矩陣，6 和c 分別是為m 和n 維向量，z 是對偶問題中加入的 松弛變量( n 維向量) 。 對對偶問題( d ) 引進(jìn)對數(shù)障礙函數(shù)，則問題轉(zhuǎn)換為 n b t y + p i nz y j = 1 ( 2 3 2 4 ) a 丁y 一- z = c 式中，p 為障礙參數(shù)( p o ) 。顯然z 為( 2 3 2 4 ) 的約束條件的拉格朗日乘 數(shù)，因此相應(yīng)的拉格朗日函數(shù)為 l ( 礎(chǔ)石，z ) = 6 t 可+ ，暑1 n 勿一z 丁( a t 可+ 名一c ) ( 2 3 2 5 ) 第一階最優(yōu)性條件，即其分別對z 、秒和z 的一階導(dǎo)數(shù)為零，導(dǎo)致下列方 程組： d g e 一弘e = 0 a x b = 0 ( 2 3 2 6 ) a t y + z c = 0 式中，d 牙v c , 分別為對角元x j 和乃的三角矩陣，因此下面的計算式 中d g - 1 與g - 1 d 的結(jié)果一致。注意上式的后兩式，分別是通常的原問 1 5 一 疏 0 上海大學(xué)碩士學(xué)位論文 三；一蘭r - d a x = r 。g ip e g a x + d a z = 肛e d g e a a x ：= 0 a t a y 士a z = 0 解該方程組得出按如下計算步驟地式子： a y = 一( a d g _ 1 a 丁) - 1 a g - 1 v o l ) a z = 一a 丁a y a x = g _ 1 u ( p ) 一d g - 1 z 式中，u ( p ) = r e d g e ( 2 3 2 8 ) 的全顯示表示式則為 z = 【g 一d g - 1 a 丁( a d g - 1 a 丁) _ 1 a g - 1 】 p e d g e 】 a y = - ( a d g 1 a 丁) - 1 a g - 1 弘e d g e 】 a z = a t ( a d g - 1 a t ) _ 1 a g _ 1 】【p e d g e 】 ( 2 3 2 7 ) ( 2 3 2 8 ) ( 2 3 2 9 ) 式中，u ( p ) = t i e d g e 根據(jù)計算的方向，考慮適當(dāng)?shù)牟介L參數(shù)q ，則可寫出迭代公式。 m o n t e i r o 和a d l e r 2 4 出的算法中每步取步長參數(shù)a