強(qiáng)次可行方法與序列二次約束二次規(guī)劃算法的研究.pdf

1、最優(yōu)化在工程設(shè)計、生產(chǎn)管理、交通運(yùn)輸、政府決策等重要領(lǐng)域日益得到廣泛的應(yīng)用，因此更加快速有效的最優(yōu)化算法成為迫切需求.序列二次規(guī)劃(SQP)算法是求解非線性約束優(yōu)化最有效的算法之一，而可行SQP算法又是其中一類重要的算法，因?yàn)樗墚a(chǎn)生可行迭代點(diǎn)序列，故在工程設(shè)計和實(shí)時控制等方面有著十分重要的實(shí)際應(yīng)用.然而可行SQP算法的較大缺陷就是需要一個可行初始迭代點(diǎn)，而通常計算一個可行點(diǎn)不是一個容易的工作.為此，簡金寶教授近年提出了一個強(qiáng)次可行方向

2、法，并成功應(yīng)用于可行SQP算法.該方法能從任意初始點(diǎn)開始，能保證迭代的可行性單調(diào)增加，且一旦迭代點(diǎn)落入可行域即變成可行方向法.然而，強(qiáng)次可行方向法中仍然有一些問題亟待解決，如：能否在理論上保證在經(jīng)過有限次迭代之后迭代點(diǎn)落入可行域；在理論分析當(dāng)中一些較強(qiáng)的假設(shè)條件能否去掉或者減弱；數(shù)值計算量能否進(jìn)一步減少等. 在過去三四十年里SQP方法的研究得到了極大的完善，然而當(dāng)要求解的問題非線性程度比較高時，如人造衛(wèi)星軌道問題，SQP方法可能

3、進(jìn)程較為緩慢，甚至?xí)?于是近年來一些學(xué)者專門針對該類問題提出了一種有效的方法，稱為序列二次約束二次規(guī)劃(SQCQP)方法.與SQP方法相比，SQCQP方法每步迭代只需求解一個二次約束二次規(guī)劃(QCQP)子問題，并且在不需要任何方向修正的情況下可以克服Maratos效應(yīng)，達(dá)到超線性收斂性.由于QCQP子問題是原問題的二次近似，因此相對于SQP方法中的二次規(guī)劃(QP)子問題而言，QCQP子問題對原問題的近似程度要好，從而SQCQP方法預(yù)

4、期的數(shù)值效果要比SQP方法好. 本學(xué)位論文首先結(jié)合強(qiáng)次可行方向法，SQP方法和SQCQP方法的思想，分別給了一個強(qiáng)次可行SQP算法和一個強(qiáng)次可行SQCQP算法.然后專門針對目前SQCQP方法中存在的缺陷，提出了兩個新的SQCQP算法.本論文共分為六章，各章內(nèi)容簡要介紹如下. 第一章主要介紹了強(qiáng)次可行方向法的思想，可行SQP方法和SQCQP方法的研究進(jìn)展，以及QCQP子問題的求解方法. 第二章結(jié)合強(qiáng)次可行方向法和可

5、行SQP方法的思想，提出了一個新的強(qiáng)次可行SQP算法.通過構(gòu)造新的修正方向和設(shè)計新的Armijio型曲線搜索，提出的算法彌補(bǔ)了傳統(tǒng)強(qiáng)次可行SQP算法的多個缺陷.首先能在理論上保證算法經(jīng)過有限次迭代之后，迭代點(diǎn)落入可行域，之后自動變?yōu)榭尚蠸QP算法，并由此克服了一個較強(qiáng)的假設(shè)條件(即最大約束違背函數(shù)是QP子問題解的高階).其次，去掉了嚴(yán)格互補(bǔ)條件.最后，由于兩個修正方向均由簡單的顯式產(chǎn)生，而且包含的逆矩陣是一樣的，從而極大減少了計算量.算

6、法具備全局和超線性收斂性.初步的數(shù)值試驗(yàn)說明該算法是穩(wěn)定有效的. 第三章結(jié)合強(qiáng)次可行方向法和可行模松弛SQCQP方法的思想，提出了一個強(qiáng)次可行模松弛SQCQP算法.通過對線搜索和QCQP子問題精心的構(gòu)造，算法能從任意初始點(diǎn)開始，并保證有限步之后迭代點(diǎn)落入可行域.算法每次迭代只需求解一個凸QCQP子問題，且無需任何修正方向就能得到算法的全局、超線性及擬二次收斂性.數(shù)值試驗(yàn)說明算法的數(shù)值效果與測試的SQP算法相比有一定的優(yōu)越性.

7、 第四章提出了一個新的罰函數(shù)型SQCQP算法.算法引入了一個簡單的非單調(diào)罰參數(shù)調(diào)整技術(shù)，該技術(shù)僅利用QCQP子問題中有界約束的KKT乘子來更新罰參數(shù)，因?yàn)楫?dāng)把QCQP轉(zhuǎn)化為二階錐規(guī)劃求解時，對應(yīng)于二次約束的乘子往往比較難獲取.該技術(shù)還允許罰參數(shù)在早期迭代減小，從而緩解了因罰參數(shù)增大過快而導(dǎo)致罰函數(shù)及子問題性態(tài)變差的問題.此外，我們利用了工作集技術(shù)剔除了QCQP子問題中局部不相關(guān)的約束，從而極大地減少了計算量.在不需要假設(shè)目標(biāo)和約束函

8、數(shù)為凸的情況下，算法是全局、超線性及二次收斂性的.初步的數(shù)值試驗(yàn)表明算法對測試的算例要比SQP方法優(yōu)越. 第五章結(jié)合增廣Lagrange函數(shù)線搜索技術(shù)和SQCQP方法的思想，提出了一個增廣Lagrange函數(shù)型SQCQP算法.算法中構(gòu)造了一個新型的凸QCQP子問題，該子問題不僅始終有可行解，而且通過應(yīng)用積極約束集技術(shù)避免了那些局部不相關(guān)的梯度和(近似)Hesse陣的計算，從而減少了計算量.步長由Armijio型線搜索產(chǎn)生，罰參數(shù)

9、允許減小.在適當(dāng)?shù)募僭O(shè)下，算法不需要任何修正方向就具有全局、超線性及二次收斂性.此外，與以往SQCQP算法不同的是，該算法還能簡單地推廣到求解混合等式與不等式的一般約束優(yōu)化，以及推廣到非單調(diào)線搜索. 第六章總結(jié)了本文的主要工作，并引出了一些需要進(jìn)一步研究的問題. 最后，值得指出的是，我們對本文中提出的兩個SQCQP算法做了比較充分和完整的數(shù)值試驗(yàn)，而以往給出的SQCQP算法中，除了一個局部收斂的算法給出了一些初步的數(shù)值試