二次規(guī)劃問題

1、序列二次規(guī)劃法求解一般線性優(yōu)化問題: 基本思想：在每次迭代中通過求解一個二次規(guī)劃子問題來確定一個下降方向，通過減少價值函數(shù)來獲取當(dāng)前迭代點的移動步長，重復(fù)這些步驟直到得到原問題的解。1.1等式約束優(yōu)化問題的Lagrange-Newton法考慮等式約束優(yōu)化問題 其中都為二階連續(xù)可微的實函數(shù).記.則的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矩陣。對于給定的點，牛頓法的

2、迭代格式為：.其中是線性方程組 （1.6）的解。注意：只要行滿秩且是正定的，那么（1.6）的系數(shù)矩陣非奇異，且方程組有唯一解。引理1：已知矩陣，則對任意滿足的非零向量都有的充要條件是存在常數(shù)，使得對任意的都有.證明略。鑒于方程組（1.6）的求解數(shù)值不穩(wěn)定，故考慮將它轉(zhuǎn)化成一個嚴(yán)格凸二次規(guī)劃問題.轉(zhuǎn)化的條件是的解點處的最優(yōu)性二階充分條件成立，即對滿足的任一向量，成立。再由引理1知：當(dāng)充分小時，正定?？紤]（1.6）中的用一個正定矩陣來代替，記則當(dāng)時，矩陣正定。（1.6）的第一個展開式為將上式變形為：令后得：.因此，（1.6）等價于 （1.7）進一步，可以把方程（1.7）轉(zhuǎn)換成如下嚴(yán)格凸二次規(guī)劃：

3、（1.8）方程（1.7）和（1.8）具有同解的。1.2一般形式的約束優(yōu)化問題將1.1節(jié)中構(gòu)造二次規(guī)劃子問題求解等式約束優(yōu)化問題的思想推廣到一般形式的約束優(yōu)化問題。在給定點后，將約束函數(shù)線性化，并對拉格朗日函數(shù)進行二次多項式近似，得到下列二次規(guī)劃子問題： （1.9）其中，拉格朗日函數(shù)為.于是，迭代點的校正步以及新的拉格朗日乘子估計量可以分別定義為問題的一個K-T點和相應(yīng)的拉格朗日乘子向量。定理1：給定約束優(yōu)化問題（1.1）的最優(yōu)解 和相應(yīng)的拉格朗日乘子.假定在處，下面的條件成立：（1） 有效約束的Jacobi矩陣行滿秩，其中;（2） 嚴(yán)格互補松弛條件成立，即 （3） 二階最優(yōu)性充分條件成立，即對

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

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