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

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

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

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

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

5、續(xù)可微精確罰函數(shù)又可以分為兩個子類：第一個子類是把考慮KKT條件的項(xiàng)加到約束問題的目標(biāo)函數(shù)上；第二個子類是把考慮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).同時，增廣拉格

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

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

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

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

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

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