二次規(guī)劃問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) MACROBUTTON MTEditEquationSection2 SEQ MTEqn r h * MERGEFORMAT SEQ MTSec r 1 h * MERGEFORMAT SEQ MTChap r 1 h * MERGEFORMAT 序列二次規(guī)劃法求解一般線性優(yōu)化問題: MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTSec c * Arabic * MERGE

2、FORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 1)基本思想：在每次迭代中通過求解一個(gè)二次規(guī)劃子問題來確定一個(gè)下降方向，通過減少價(jià)值函數(shù)來獲取當(dāng)前迭代點(diǎn)的移動(dòng)步長，重復(fù)這些步驟直到得到原問題的解。1.1等式約束優(yōu)化問題的Lagrange-Newton法考慮等式約束優(yōu)化問題 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 2)其中

3、都為二階連續(xù)可微的實(shí)函數(shù).記.則 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 2)的Lagrange函數(shù)為： （1.3）其中為拉格朗日乘子向量。約束函數(shù)的Jacobi矩陣為：.對（1.3）求導(dǎo)數(shù)，可以得到下列方程組： （1.4）現(xiàn)在考慮用牛頓法求解非線性方程（1.4）.的Jacobi矩陣為： （1.5）其中是拉格朗日函數(shù)關(guān)于的Hessen矩陣.也稱為K-T矩陣。對于

4、給定的點(diǎn)，牛頓法的迭代格式為：.其中是線性方程組 （1.6）的解。注意：只要行滿秩且是正定的，那么（1.6）的系數(shù)矩陣非奇異，且方程組有唯一解。引理1：已知矩陣，則對任意滿足的非零向量都有的充要條件是存在常數(shù)，使得對任意的都有.證明略。鑒于方程組（1.6）的求解數(shù)值不穩(wěn)定，故考慮將它轉(zhuǎn)化成一個(gè)嚴(yán)格凸二次規(guī)劃問題.轉(zhuǎn)化的條件是 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMA

5、T 2)的解點(diǎn)處的最優(yōu)性二階充分條件成立，即對滿足的任一向量，成立。再由引理1知：當(dāng)充分小時(shí)，正定。考慮（1.6）中的用一個(gè)正定矩陣來代替，記則當(dāng)時(shí)，矩陣正定。（1.6）的第一個(gè)展開式為將上式變形為：令后得：.因此，（1.6）等價(jià)于 （1.7）進(jìn)一步，可以把方程（1.7）轉(zhuǎn)換成如下嚴(yán)格凸二次規(guī)劃： （1.8）方程（1.7）和（1.8）具有同解的。1.2一般形式的約束優(yōu)化問題將1.1節(jié)中構(gòu)造二次規(guī)劃子問題求解等式約束優(yōu)化問題的思想推廣到一般形式的約束優(yōu)化問題 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ

6、MTSec c * Arabic * MERGEFORMAT 1. SEQ MTEqn c * Arabic * MERGEFORMAT 1)。在給定點(diǎn)后，將約束函數(shù)線性化，并對拉格朗日函數(shù)進(jìn)行二次多項(xiàng)式近似，得到下列二次規(guī)劃子問題： （1.9）其中，拉格朗日函數(shù)為.于是，迭代點(diǎn)的校正步以及新的拉格朗日乘子估計(jì)量可以分別定義為問題的一個(gè)K-T點(diǎn)和相應(yīng)的拉格朗日乘子向量。定理1：給定約束優(yōu)化問題（1.1）的最優(yōu)解 和相應(yīng)的拉格朗日乘子.假定在處，下面的條件成立：有效約束的Jacobi矩陣行滿秩，其中;嚴(yán)格互補(bǔ)松弛條件成立，即 二階最優(yōu)性充分條件成立，即對滿足的任一向量，成立.那么若充分靠近，則二

7、次規(guī)劃問題(1.9)存在一個(gè)局部極小點(diǎn)，使得其對應(yīng)的有效約束指標(biāo)集與原問題在處的有效指標(biāo)集是相同的。注意：在構(gòu)造二次規(guī)劃子問題時(shí)，需要計(jì)算拉格朗日函數(shù)在迭代點(diǎn)處的Hessen矩陣，計(jì)算量過大。為了克服這個(gè)缺陷，韓世平基于牛頓-拉格朗日法提出了一種利用對稱正定矩陣來代替拉格朗日矩陣的序列二次規(guī)劃法。對于一般約束優(yōu)化問題（1.1），在迭代點(diǎn)，構(gòu)造下列形式的二次規(guī)劃子問題：（1.10）并且用（1.10）的解作為原問題變量在第次迭代過程中的搜索方向。其中有一個(gè)好的性質(zhì)是它許多罰函數(shù)（價(jià)值函數(shù)）的下降方向。例如，對于L1精確罰函數(shù)：其中為罰參數(shù)，。為了保證SQR方法的全局收斂性，通常借助價(jià)值函數(shù)來確定搜

8、索步長。用來衡量一維搜索的好壞。算法（一般約束優(yōu)化問題的SQP方法）Step 0:給定初始點(diǎn)對稱正定矩陣.計(jì)算，.選擇參數(shù)容許誤差令Step 1:求解子問題（1.10）得最優(yōu)解.Step 2:若且,stop,得到(1.1)的一個(gè)近似KT點(diǎn).Step 3:對于某種價(jià)值函數(shù)，選擇罰參數(shù)，使得是該函數(shù)在處的下降方向。Step 4:Armijo搜索. 令是使下列不等式成立的最小非負(fù)整數(shù): 令 Step 5:計(jì)算 以及最小二乘乘子 Step 6:校正矩陣為.令 其中參數(shù)定義為Step 7:令轉(zhuǎn)1.注意：（step 1）利用K-T條件，問題(1.10)等價(jià)于（1.11）第三式是維互補(bǔ)問題，定義光滑函數(shù) 其中為光滑參數(shù).令，其中其中表示的第行.記，那么（1.11）問題等價(jià)于 則的Jacobi矩陣為 其中,由下式確定： 而，其中由下式確定：給定參數(shù)，定義非負(fù)