求解約束優(yōu)化問(wèn)題的增廣拉格朗日函數(shù)法.pdf

1、約束優(yōu)化問(wèn)題廣泛見(jiàn)于工程、國(guó)防、經(jīng)濟(jì)、金融和社會(huì)科學(xué)等許多重要領(lǐng)域.求解約束優(yōu)化問(wèn)題的重要途徑之一是把它們轉(zhuǎn)化成無(wú)約束優(yōu)化問(wèn)題進(jìn)行求解.罰函數(shù)方法是將約束優(yōu)化問(wèn)題無(wú)約束化的一類主要方法，它們通過(guò)求解一個(gè)或一系列罰問(wèn)題來(lái)得到約束優(yōu)化問(wèn)題的解.我們稱罰問(wèn)題的目標(biāo)函數(shù)為一個(gè)罰函數(shù).罰函數(shù)一般與某個(gè)罰參數(shù)有關(guān).如果當(dāng)罰參數(shù)取大于某個(gè)較大正數(shù)的值(或者取大于零且小于某個(gè)小正數(shù)的值)時(shí)，對(duì)應(yīng)的罰問(wèn)題的極小點(diǎn)與原約束問(wèn)題的極小點(diǎn)之間存在某種精確的對(duì)應(yīng)

2、關(guān)系，則稱對(duì)應(yīng)的罰函數(shù)為精確罰函數(shù)；反之，如果對(duì)于罰參數(shù)的任何正的有限值，對(duì)應(yīng)的罰問(wèn)題的極小點(diǎn)與原約束問(wèn)題的極小點(diǎn)之間都不存在精確的對(duì)應(yīng)關(guān)系，而當(dāng)罰參數(shù)趨于它的極限值(無(wú)窮大或者零)時(shí)，對(duì)應(yīng)罰問(wèn)題的極小點(diǎn)的極限值與原約束問(wèn)題的極小點(diǎn)之間存在某種精確的對(duì)應(yīng)關(guān)系，則稱對(duì)應(yīng)的罰函數(shù)為序列罰函數(shù).序列罰函數(shù)方法在理論上需要求解無(wú)窮多個(gè)罰問(wèn)題來(lái)獲得約束優(yōu)化問(wèn)題的解.這種方法的主要缺點(diǎn)是，當(dāng)罰參數(shù)的值很大(或者很小)時(shí)，罰問(wèn)題成為壞條件問(wèn)題，從而使

3、這種方法產(chǎn)生數(shù)值不穩(wěn)定和收斂慢等缺點(diǎn).精確罰函數(shù)方法在理論上只需要求解一個(gè)(或有限多個(gè))罰問(wèn)題來(lái)獲得約束優(yōu)化問(wèn)題的解，從而避免了序列罰函數(shù)方法產(chǎn)生壞條件的缺點(diǎn).精確罰函數(shù)包括不可微精確罰函數(shù)和連續(xù)可微精確罰函數(shù).在實(shí)際計(jì)算時(shí)，不可微精確罰函數(shù)法由于罰函數(shù)的不可微性而使算法產(chǎn)生所謂的“Maratos效應(yīng)”，從而產(chǎn)生阻止快速局部收斂的現(xiàn)象.連續(xù)可微精確罰函數(shù)大體上又包括兩類：一類是定義在原約束問(wèn)題變量空間上的連續(xù)可微精確罰函數(shù)；另一類是定義

4、在原約束問(wèn)題變量空間和KKT乘子變量空間的積空間上的連續(xù)可微精確罰函數(shù).第一類連續(xù)可微精確罰函數(shù)通過(guò)使用乘子函數(shù)實(shí)現(xiàn)對(duì)不滿足KKT條件情形的“懲罰”.乘子函數(shù)是原問(wèn)題變量的函數(shù)，它產(chǎn)生KKT乘子的估計(jì).從計(jì)算的角度來(lái)看，當(dāng)約束的個(gè)數(shù)較多時(shí)，確定乘子函數(shù)值的代價(jià)是相當(dāng)大的，因?yàn)樗枰蟪雠c約束個(gè)數(shù)同階的一個(gè)矩陣的逆，而每一次計(jì)算罰函數(shù)值都需計(jì)算出乘子函數(shù)值.正是由于這一原因，使得這種連續(xù)可微精確罰函數(shù)的應(yīng)用在某種程度上受到了限制.第二類連

5、續(xù)可微精確罰函數(shù)又可以分為兩個(gè)子類：第一個(gè)子類是把考慮KKT條件的項(xiàng)加到約束問(wèn)題的目標(biāo)函數(shù)上；第二個(gè)子類是把考慮KKT條件的項(xiàng)加到通常的拉格朗日函數(shù)上，因此稱之為增廣拉格朗日函數(shù).大量的理論結(jié)果和數(shù)值試驗(yàn)均表明，增廣拉格朗日函數(shù)法(亦即使用增廣拉格朗日函數(shù)作為罰函數(shù)的連續(xù)可微精確罰函數(shù)法)比序列罰函數(shù)法和不可微精確罰函數(shù)法具有明顯的優(yōu)點(diǎn)，它們克服了序列罰函數(shù)法產(chǎn)生壞條件和不可微精確罰函數(shù)法產(chǎn)生“Maratos效應(yīng)”的缺點(diǎn).同時(shí)，增廣拉格

6、朗日函數(shù)法也具有比其它連續(xù)可微精確罰函數(shù)法優(yōu)越的性質(zhì). 本文主要考慮求解約束優(yōu)化問(wèn)題的增廣拉格朗日函數(shù)法.首先，我們進(jìn)一步研究了求解等式約束問(wèn)題和不等式約束問(wèn)題的Hestenes-Powell增廣拉格朗日函數(shù)法的理論性質(zhì)；然后，我們提出了求解等式約束問(wèn)題的一類增廣拉格朗日函數(shù)法，并研究了它們的精確性質(zhì)，然后把其中的一個(gè)增廣拉格朗日函數(shù)法的相關(guān)結(jié)果推廣到了不等式約束的情形；最后，我們提出了求解不等式約束問(wèn)題的一個(gè)新的增廣拉格朗日函

7、數(shù)法，并研究了它的精確性質(zhì). 本文具體內(nèi)容安排如下.第一章，我們陳述了本文所要用到的一些基本概念及有關(guān)結(jié)論，并簡(jiǎn)要介紹了目前國(guó)內(nèi)外關(guān)于增廣拉格朗日函數(shù)法和罰函數(shù)法的研究狀況.第二章，我們進(jìn)一步研究了求解等式約束問(wèn)題的Hestenes-Powell增廣拉格朗日函數(shù)法的理論性質(zhì).具體內(nèi)容包括：1.等式約束問(wèn)題的拉格朗日函數(shù)的穩(wěn)定點(diǎn)(或等式約束問(wèn)題的KKT對(duì))與Hestenes-Powell增廣拉格朗日函數(shù)的穩(wěn)定點(diǎn)之間的對(duì)應(yīng)關(guān)系；2.

8、等式約束問(wèn)題的局部極小點(diǎn)與Hestenes-Powell增廣拉格朗日函數(shù)的無(wú)約束局部極小點(diǎn)之間的對(duì)應(yīng)關(guān)系；3.等式約束問(wèn)題的全局極小點(diǎn)與HestenesPowell增廣拉格朗日函數(shù)的全局極小點(diǎn)之間的對(duì)應(yīng)關(guān)系；4.利用我們得到的理論結(jié)果，對(duì)求解等式約束問(wèn)題的一個(gè)用Hestenes-Powell增廣拉格朗日函數(shù)的算法模型作了一些解釋.第三章，我們進(jìn)一步研究了求解不等式約束問(wèn)題的Hestenes-Powell增廣拉格朗日函數(shù)法的理論性質(zhì).具體

9、內(nèi)容包括：1.不等式約束問(wèn)題的KKT對(duì)與Hestenes-Powell增廣拉格朗日函數(shù)的穩(wěn)定點(diǎn)之間的對(duì)應(yīng)關(guān)系；2.不等式約束問(wèn)題的局部極小點(diǎn)與Hestenes-Powell增廣拉格朗日函數(shù)的無(wú)約束局部極小點(diǎn)之間的對(duì)應(yīng)關(guān)系；3.不等式約束問(wèn)題的全局極小點(diǎn)與Hestenes-Powell增廣拉格朗日函數(shù)的全局極小點(diǎn)之間的對(duì)應(yīng)關(guān)系.第四章，我們提出了求解等式約束問(wèn)題的一類增廣拉格朗日函數(shù)法，并研究了它們的精確性質(zhì).這類增廣拉格朗日函數(shù)是對(duì)Di

10、Pillo和Grippo提出的一類增廣拉格朗日函數(shù)的補(bǔ)充和推廣.本章具體內(nèi)容包括：1.等式約束問(wèn)題的拉格朗日函數(shù)的穩(wěn)定點(diǎn)(或等式約束問(wèn)題的KKT對(duì))與我們給出的增廣拉格朗日函數(shù)的穩(wěn)定點(diǎn)之間的對(duì)應(yīng)關(guān)系；2.等式約束問(wèn)題的局部極小點(diǎn)與增廣拉格朗日函數(shù)的無(wú)約束局部極小點(diǎn)之間的對(duì)應(yīng)關(guān)系；3.增廣拉格朗日函數(shù)中加權(quán)矩陣的一些具體選擇.4.等式約束問(wèn)題的全局極小點(diǎn)與增廣拉格朗日函數(shù)的全局極小點(diǎn)之問(wèn)的對(duì)應(yīng)關(guān)系，以及關(guān)于等式約束二次規(guī)劃問(wèn)題的一個(gè)結(jié)果.

11、第五章，我們把第四章中的一個(gè)增廣拉格朗日函數(shù)法的相關(guān)結(jié)果推廣到了不等式約束的情形.第六章，我們提出了求解不等式約束問(wèn)題的一個(gè)新的增廣拉格朗日函數(shù)法，研究了它的精確性質(zhì).本章給出的增廣拉格朗日函數(shù)實(shí)際上是把DiPillo和Grippo給出的關(guān)于等式約束問(wèn)題的一個(gè)增廣拉格朗日函數(shù)推廣到了不等式約束的情形.具體內(nèi)容包括：1.不等式約束問(wèn)題的KKT對(duì)與新的增廣拉格朗日函數(shù)的穩(wěn)定點(diǎn)之間的對(duì)應(yīng)關(guān)系；2.不等式約束問(wèn)題的局部極小點(diǎn)與新的增廣拉格朗日函