第7章--約束問(wèn)題的優(yōu)化方法(共26頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第7章 約束問(wèn)題的優(yōu)化方法7.1 可行方向法7.1.1 可行方向法的基本思想可行方向法是一類(lèi)算法,可看作無(wú)約束下降算法的自然推廣。典型策略是從可行點(diǎn)出發(fā)，沿著下降可行方向進(jìn)行搜索，求出使目標(biāo)函數(shù)值下降的新的可行點(diǎn)考慮只含線(xiàn)性約束的非線(xiàn)性規(guī)劃問(wèn)題： （1）為非線(xiàn)性函數(shù)，.注1：線(xiàn)性約束規(guī)格保證了優(yōu)化問(wèn)題（1）的可行方向集、線(xiàn)性化可行方向集以及序列化可行方向集是等同的。當(dāng)某個(gè)可行方向同時(shí)也是目標(biāo)函數(shù)的下降方向時(shí)，沿此方向移動(dòng)一定會(huì)在滿(mǎn)足可行性的情況下改進(jìn)迭代點(diǎn)的目標(biāo)函數(shù)值。目前已經(jīng)提出許多可行方向法，用來(lái)處理具有線(xiàn)性約束的非線(xiàn)性規(guī)劃問(wèn)題。搜索方向選擇方式不同形成不同的可行

2、方向法：（1）Zoutendijk可行方向法（2）Rosen梯度投影法（3）Wolfe既約梯度法可行方向的判定：定理1：設(shè)是問(wèn)題（1）的可行解，在點(diǎn)處有，其中，則非零向量為處的可行方向的充要條件是，證明：必要性：設(shè)非零向量是處的可行方向根據(jù)可行方向的定義，使得對(duì)每個(gè)有為可行點(diǎn)，即，.由于，由上式得到又由得到. 充分性：設(shè)，.由于，則，使得對(duì)于所有的,成立.根據(jù)假設(shè)及，得到.上述兩式組合起來(lái)就是.又由及可知表明是可行點(diǎn)，因此是處的可行方向7.1.2 Zoutendijk可行方向法Zoutendijk子問(wèn)題：根據(jù)定理1，如果非零向量同時(shí)滿(mǎn)足, ，,則是處的下降可行方向Zoutendijk可行方向法

3、把確定搜索方向歸結(jié)為求解線(xiàn)性規(guī)劃問(wèn)題 （2）在（2）式中，顯然是可行解，可推知目標(biāo)函數(shù)最優(yōu)值必定小于或等于零如果目標(biāo)函數(shù)最優(yōu)值小于零，則得到下降可行方向；否則，如果目標(biāo)函數(shù)最優(yōu)值為零，則x是K-T點(diǎn)定理2：考慮問(wèn)題（1），設(shè)是可行解，在點(diǎn)處有，其中，則為K-T點(diǎn)的充要條件是問(wèn)題（2）的目標(biāo)函數(shù)最優(yōu)值為零一維搜索步長(zhǎng)的確定：設(shè)為處一個(gè)下降可行方向后繼點(diǎn)迭代公式：的取值原則：(l)保持迭代點(diǎn)的可行性；(2)使目標(biāo)函數(shù)值盡可能減小根據(jù)上述原則，可以通過(guò)求解一維搜索問(wèn)題來(lái)確定步長(zhǎng)： （3）由于是可行方向，因此，(3)式中第2個(gè)約束是多余的在點(diǎn)處，把不等式約束區(qū)分為起作用約束和不起作用約束：，(3)式中

4、第1個(gè)約束可以寫(xiě)成 （4）由于為可行方向，以及，因此自然成立約束條件（4）簡(jiǎn)化為問(wèn)題（3）簡(jiǎn)化為 （5）根據(jù)（5）式的約束條件，容易求出的上限，令 由知. (5)式的約束條件寫(xiě)成：由此得到的上限：?jiǎn)栴}（3）最終簡(jiǎn)化成： （6）給定問(wèn)題（1）和一個(gè)可行點(diǎn)以后，可以通過(guò)求解問(wèn)題（2）得到下降可行方向，通過(guò)求解問(wèn)題（6）確定沿此方向進(jìn)行一維搜索的步長(zhǎng)初始可行點(diǎn)的確定：為求（1）式的一個(gè)可行點(diǎn)，引入人工變量（向量）和，解輔助線(xiàn)性規(guī)劃 （7）如果（7）式的最優(yōu)解，那么就是（1）式的一個(gè)可行解可行方向法的計(jì)算步驟：(l)給定初始可行點(diǎn)，置.(2)在點(diǎn)處把A和b分解成和，使得，計(jì)算 (3)求解線(xiàn)性規(guī)劃問(wèn)題得

5、到最優(yōu)解. (4)如果，則停止計(jì)算，為K-T點(diǎn)，否則，進(jìn)行步驟（5）. (5)計(jì)算的上限，在上作一維搜索：得到最優(yōu)解，令 (6)置，返回步驟（2）.例：用Zoutendijk可行方向法解下列問(wèn)題：取初始可行點(diǎn).第1次迭代：，在處，起作用約束和不起作用約束的系數(shù)矩陣及右端分別為，；，先求在處的下降可行方向： 即 由單純形方法求得最優(yōu)解：再求步長(zhǎng): 解一維搜索問(wèn)題得到：令 第2次迭代：，在處，起作用約束和不起作用約束的系數(shù)矩陣及右端分別為，；，求在處的下降可行方向：由單純形方法求得最優(yōu)解：沿搜索，求步長(zhǎng): 解一維搜索問(wèn)題得到：.令 第3次迭代：，；，求在處的下降可行方向：由單純形方法求得最優(yōu)解：根

6、據(jù)定理1，是K-T點(diǎn)。該例是凸規(guī)劃，是最優(yōu)解，目標(biāo)函數(shù)最優(yōu)值.將可行方向法推廣到非線(xiàn)性約束情形：考慮不等式約束問(wèn)題 （8）定理3：設(shè)x是問(wèn)題（8）的可行解，是在處起作用約束下標(biāo)集，又設(shè)函數(shù),在處可微，函數(shù)在處連續(xù)，如果，則d是下降可行方向根據(jù)定理3，求下降可行方向歸結(jié)為求解LP問(wèn)題 （9）設(shè)（9）式的最優(yōu)解為如果，則是在x處的下降可行方向；如果，相應(yīng)的x必為Fritz John點(diǎn)定理4：設(shè)x是問(wèn)題（9）的可行解，則x是Fritz John點(diǎn)的充要條件是問(wèn)題（9）的目標(biāo)函數(shù)最優(yōu)值等于零步長(zhǎng)的確定，仍然需要求解一維搜索問(wèn)題其中 （10）計(jì)算步驟：(l)給定初始可行點(diǎn)，置. (2)令，解線(xiàn)性規(guī)劃問(wèn)題

7、得最優(yōu)解，若，則停止計(jì)算，為Fritz John 點(diǎn)；否則，進(jìn)行步驟（3）. (3)求解一維搜索問(wèn)題其中由（10）式確定，得到最優(yōu)解（4）令，置，返回步驟（2）.Zoutendijk算法的收斂問(wèn)題：不能保證Zoutendijk方法迭代產(chǎn)生的序列收斂于K-T點(diǎn)Topkis-Veinott修正Topkis和Veinott把求方向的線(xiàn)性規(guī)劃改成緊約束和非緊約束在確定下降可行方向中均起作用，并且在接近非緊約束邊界時(shí)，不至發(fā)生方向突然改變修正方法計(jì)算步驟：(l)給定初始可行點(diǎn)，置. (2)解線(xiàn)性規(guī)劃問(wèn)題得最優(yōu)解.(3)若，則停止計(jì)算，為Fritz John 點(diǎn)；否則，進(jìn)行步驟（4）.(4)求解一維搜索問(wèn)

8、題其中由（10）式確定，得到最優(yōu)解（5）令，置，返回步驟（2）.Topkis-Veinott修正方法的收斂性:定理5: 考慮問(wèn)題（8），設(shè)函數(shù)連續(xù)可微，又設(shè)是Topkis-Veinott算法產(chǎn)生的序列，則的任一聚點(diǎn)是Fritz John點(diǎn)7.2 懲罰函數(shù)法7.2.1 懲罰函數(shù)法的基本思想懲罰函數(shù)法的基本思想：借助罰函數(shù)把約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題，進(jìn)而用無(wú)約束最優(yōu)化方法來(lái)求解考慮約束問(wèn)題 （1）求解的一種途徑是由目標(biāo)函數(shù)和約束函數(shù)組成輔助函數(shù)，把原來(lái)的約束問(wèn)題轉(zhuǎn)化為極小化輔助函數(shù)的無(wú)約束問(wèn)題對(duì)于等式約束問(wèn)題： （2）可定義輔助函數(shù)參數(shù)是很大的正數(shù)（2）式轉(zhuǎn)化為無(wú)約束問(wèn)題 （3）求解問(wèn)題（3）能夠

9、得到問(wèn)題(2)的近似解對(duì)于不等式約束問(wèn)題： （4）定義輔助函數(shù)（4）式轉(zhuǎn)化為無(wú)約束問(wèn)題 （5）通過(guò)（5）式求得（4）式的近似解一般情形（1）式）：可定義輔助函數(shù)其中連續(xù)函數(shù)和滿(mǎn)足條件：函數(shù)和的典型取法：為給定常數(shù)通常取作 . 約束問(wèn)題（1）轉(zhuǎn)化為無(wú)約束問(wèn)題 （6）稱(chēng)為罰項(xiàng)，稱(chēng)為罰因子，而稱(chēng)為罰函數(shù)。 當(dāng)x為可行點(diǎn)時(shí)，有；當(dāng)x不是可行點(diǎn)時(shí)，是很大的正數(shù)，它的存在是對(duì)點(diǎn)脫離可行域的一種懲罰，作用是在極小化過(guò)程中迫使迭代點(diǎn)靠近可行域求解問(wèn)題（6）能夠得到約束問(wèn)題（1）的近似解。越大，近似效果越好。7.2.2 乘子法1 乘子法的基本思想考慮只有等式約束問(wèn)題（2）.運(yùn)用乘子法事先需要定義增廣Lagran

10、ge函數(shù)（乘子罰函數(shù)）: (7)與Lagrange函數(shù)的區(qū)別在于增加罰項(xiàng);與罰函數(shù)的區(qū)別在于增加了乘子項(xiàng)注1：增廣Lagrange函數(shù)與Lagrange函數(shù)及罰函數(shù)具有不同的性態(tài)，即對(duì)于，只要取足夠大的罰因子，不必趨向無(wú)窮大，就可通過(guò)極小化，求得問(wèn)題（2）的局部最優(yōu)解為證明上述結(jié)論，先給出如下假設(shè)：設(shè)是等式約束問(wèn)題（2）的一個(gè)局部最優(yōu)解，且滿(mǎn)足二階充分條件，即存在乘子，使得且對(duì)每一個(gè)滿(mǎn)足的非零向量d ，有其中，定理1：設(shè)和滿(mǎn)足問(wèn)題（2）的局部最優(yōu)解的二階充分條件，則存在，使得對(duì)所有的，是的嚴(yán)格局部極小點(diǎn)反之，若存在點(diǎn)，使得且對(duì)于某個(gè)，是的無(wú)約束極小點(diǎn)，又滿(mǎn)足極小點(diǎn)的二階充分條件，則是問(wèn)題（2）

11、的嚴(yán)格局部最優(yōu)解證明：需要用到矩陣?yán)碚摰南嚓P(guān)知識(shí)和二階充分條件的定義。注2：根據(jù)定理1，如果知道最優(yōu)乘子 ，那么只要取充分大的罰因子，不需趨向無(wú)窮大，就能通過(guò)極小化求出問(wèn)題（2）的解注3：確定最優(yōu)乘子一般方法：先給定充分大的和Lagrange乘子的初始估計(jì)v，然后在迭代過(guò)程中修正v，力圖使v趨向.修正v的公式：設(shè)在第k次迭代中，Lagrange乘子向量的估計(jì)為，罰因子取，得到的極小點(diǎn)這時(shí)有對(duì)問(wèn)題（2）最優(yōu)解，當(dāng)線(xiàn)性無(wú)關(guān)，應(yīng)有假如，則必有一般來(lái)說(shuō)，并非是，因此該等式并不成立但由此可以給出修正乘子v的公式，令 （7）然后再進(jìn)行第k+1次迭代，求的極小點(diǎn)這樣做下去，可望, 從而如果不收斂，或者收斂太

12、慢，則增大參數(shù)，再進(jìn)行迭代收斂快慢一般用來(lái)衡量2 等式約束問(wèn)題乘子法計(jì)算步驟（1）給定初始點(diǎn)，乘子向量初始估計(jì)，參數(shù)，允許誤差，常數(shù), ，置. （2）以為初點(diǎn)，解無(wú)約束問(wèn)題得解. （3）若 ,則停止計(jì)算，得到點(diǎn)；否則，進(jìn)行步驟（4）. （4）若，則置，轉(zhuǎn)步驟（5）；否則，進(jìn)行步驟（5）.（5）用（7）式計(jì)算，置，轉(zhuǎn)步驟（2）. 例1：用乘子法求解下列問(wèn)題：增廣Lagrange函數(shù)取罰因子，令Lagrange乘子的初始估計(jì)，由此出發(fā)求最優(yōu)乘子及問(wèn)題的最優(yōu)解.以下用解析方法求函數(shù)的極小點(diǎn)第1次迭代：容易求得的極小點(diǎn)為第k次迭代：取乘子，增廣Lagrange函數(shù)的極小點(diǎn)為現(xiàn)在通過(guò)修正求，由（7）式，

13、有易證當(dāng)時(shí)，序列收斂，且同時(shí)，得到最優(yōu)乘子.問(wèn)題的最優(yōu)解注4：在實(shí)際計(jì)算中，應(yīng)注意的取值如果太大，則會(huì)給計(jì)算帶來(lái)困難；如果太小，則收斂減慢，甚至出現(xiàn)不收斂情形.3 不等式約束問(wèn)題的乘子法考慮只有不等式約束的問(wèn)題(4).為利用關(guān)于等式約束問(wèn)題得到的結(jié)果，引入變量，把問(wèn)題（4）化為等式約束問(wèn)題這樣可定義增廣Lagrange函數(shù)問(wèn)題（4）轉(zhuǎn)化為求解 (8)將關(guān)于y求極小，由此解出y，并代入（8）式，將其化為只關(guān)于x求極小的問(wèn)題為此求解用配方法將化為（9）為使關(guān)于取極小，取值如下：當(dāng)時(shí)，當(dāng)時(shí)，綜合以上兩種情形，即 將上式代入（9）式，由此定義增廣Lagrange函數(shù)將問(wèn)題（4）轉(zhuǎn)化為求解無(wú)約束問(wèn)題：

14、4 一般約束問(wèn)題的乘子法對(duì)于既含有不等式約束又含有等式約束的問(wèn)題（1），定義增廣Lagrange函數(shù) 在迭代中，與只有等式約束問(wèn)題類(lèi)似，取定充分大的參數(shù)，通過(guò)修正第k次迭代中的乘子和，得到第次迭代中的乘子和乘子和修正公式： (10)計(jì)算步驟與等式約束情形相同例2：用乘子法求解下列問(wèn)題：增廣Lagrange函數(shù)為令 得到的無(wú)約束極小點(diǎn) 取，得到的極小點(diǎn)： 修正，令求得的極小點(diǎn)以此類(lèi)推，設(shè)在第k次迭代取乘子，求得的極小點(diǎn)修正，得到顯然，按上式迭代得到的序列是收斂的.令，則 及 注5：在乘子法中，由于參數(shù)不必趨向無(wú)窮大就能求得約束問(wèn)題的最優(yōu)解，因此不出現(xiàn)罰函數(shù)法中的病態(tài)計(jì)算經(jīng)驗(yàn)表明，乘子法優(yōu)于罰函數(shù)

15、法，受到廣大使用者的歡迎7.3 序列二次規(guī)劃法7.3.1 序列二次規(guī)劃法的基本思想序列二次規(guī)劃法（SQP）的基本思想：在迭代點(diǎn)處構(gòu)造一個(gè)二次規(guī)劃（QP）子問(wèn)題，近似原來(lái)的約束優(yōu)化問(wèn)題；通過(guò)求解該QP子問(wèn)題，獲得約束優(yōu)化問(wèn)題的一個(gè)改進(jìn)迭代點(diǎn)；不斷重復(fù)這個(gè)過(guò)程，直到求出滿(mǎn)足一定要求的迭代點(diǎn)?？紤]一般的約束優(yōu)化問(wèn)題 （1）直覺(jué)：利用泰勒展開(kāi)在迭代點(diǎn)構(gòu)造QP子問(wèn)題： （2）令，則（2）等價(jià)于二次規(guī)劃：求出最優(yōu)解為，則新的迭代點(diǎn)為：7.3.2 Lagrange-Newton法等式約束的Lagrange-Newton法求解非線(xiàn)性方程組的Newton迭代公式為可以證明：解方程組的Newton法具有局部二次收

16、斂性?？紤]等式約束最優(yōu)化問(wèn)題： （3）問(wèn)題（3）的Lagrange函數(shù)為 令表示在處的Jacobi矩陣，即設(shè)為（3）的解且行滿(mǎn)秩，則存在使得是（3）的K-T點(diǎn)，即 （4）令，則函數(shù)的Jacobi矩陣為求解非線(xiàn)性方程組（4）的Newton迭代公式為： （5）是如下線(xiàn)性方程組的解： （6）稱(chēng)由（5）-（6）式建立的求解約束最優(yōu)化問(wèn)題（3）的算法為L(zhǎng)agrange-Newton法.Lagrange-Newton法不易于直接用于不等式約束最優(yōu)化問(wèn)題，需要導(dǎo)出Lagrange-Newton法的另一種形式.(與QP掛鉤)由約束最優(yōu)化問(wèn)題的K-T條件不難看出：Lagrange-Newton法迭代公式（5）-

17、（6）計(jì)算的是如下QP問(wèn)題的解： （7）且是相應(yīng)于等式約束的Lagrange乘子.求解等式約束問(wèn)題（3）的Newton法可等價(jià)地?cái)⑹鰹椋合惹蠖我?guī)劃（7）的K-T點(diǎn)，然后由（5）式確定.對(duì)問(wèn)題（7）的任何可行點(diǎn)，有問(wèn)題（7）等價(jià)于二次規(guī)劃 （8）二次規(guī)劃問(wèn)題（8）的K-T條件為： （9）比較（5）、（7）、（9）式，可看出：求解非線(xiàn)性方程組（4）的Lagrange-Newton法可等價(jià)地?cái)⑹鰹椋呵驫P問(wèn)題（8）的K-T點(diǎn)，令，由此產(chǎn)生迭代序列，稱(chēng)此Lagrange-Newton法為求解等式約束問(wèn)題（3）的SQP算法.一般約束優(yōu)化問(wèn)題的Lagrange-Newton法對(duì)一般約束優(yōu)化問(wèn)題，在當(dāng)前點(diǎn)

18、構(gòu)造如下QP子問(wèn)題： （10）解上述QP子問(wèn)題，得到解及對(duì)應(yīng)的乘子和，產(chǎn)生新的迭代點(diǎn)，其中.該算法稱(chēng)為求解約束問(wèn)題（1）的局部Newton-SQP算法.注1：子問(wèn)題（10）的目標(biāo)函數(shù)是問(wèn)題（1）的Lagrange函數(shù)的二次近似，而不是我們通常認(rèn)為的僅是問(wèn)題（1）的目標(biāo)函數(shù)的二次近似.基于Lagrange-Newton法的局部SQP算法步驟：（1）取初始點(diǎn)，置.（2）若滿(mǎn)足約束問(wèn)題（1）的K-T條件（從計(jì)算角度應(yīng)考察），則停止計(jì)算，得到；否則，轉(zhuǎn)步驟（3）.（3）解QP子問(wèn)題（10），得到解.（4）令，轉(zhuǎn)步驟（2）.注2：遺留問(wèn)題：（i）如何求解QP子問(wèn)題（后面再討論）？（ii）如果初始點(diǎn)取得不

19、恰當(dāng)，即使原問(wèn)題可行，也可導(dǎo)致QP子問(wèn)題不相容。QP子問(wèn)題不相容（可行域?yàn)榭眨┤绾翁幚?？?：對(duì)于約束，在點(diǎn)處，線(xiàn)性化近似約束為，不相容！7.3.3 Wilson-Han-Powell法在構(gòu)造QP子問(wèn)題（10）時(shí)，需要計(jì)算Lagrange函數(shù)在迭代點(diǎn)的Hesse矩陣，這種計(jì)算工作量比較大。借鑒無(wú)約束優(yōu)化的擬牛頓法在迭代過(guò)程中利用對(duì)稱(chēng)正定矩陣替代Hesse矩陣的思想，韓世平（S.P. Han）1976年基于Lagrange-Newton法提出了一種利用對(duì)稱(chēng)正定矩陣替代矩陣的序列二次規(guī)劃法（也稱(chēng)為約束擬牛頓法，約束變尺度法）.Wilson在1963年較早地考慮了Lagrange-Newton法.

20、后來(lái)Powell在1977年修正了Han的方法，故將這種序列二次規(guī)劃法稱(chēng)為Wilson-Han-Powell(WHP)方法對(duì)于一般的約束問(wèn)題（1），WHP方法需要構(gòu)造如下的QP子問(wèn)題： （11）利用子問(wèn)題（11）的解作為搜索方向。WHP方法除了用矩陣替代矩陣外，新的迭代點(diǎn)不直接按計(jì)算，而是由一維搜索確定步長(zhǎng)，新的迭代點(diǎn)為.由于這些改進(jìn)，WHP方法在一定條件下具有全局收斂性. 相對(duì)于Lagrange-Newton法（局部SQP算法），WHP方法稱(chēng)為全局SQP算法.（11）式確定的具有一個(gè)比較好的性質(zhì)：它是許多罰函數(shù)（價(jià)值函數(shù)，Merit Function）的下降方向.WHP方法中一種罰函數(shù)形式如

21、下(范數(shù)-1罰函數(shù))： （12）為罰因子.利用該罰函數(shù)作一維搜索確定步長(zhǎng).WHP方法的計(jì)算步驟：（1）初始化：給定初始點(diǎn)，對(duì)稱(chēng)正定矩陣，容許誤差和滿(mǎn)足的非負(fù)序列；取參數(shù)，置.(2)收斂性檢驗(yàn)：求解二次規(guī)劃子問(wèn)題（11），得到最優(yōu)解.若，則得到原來(lái)約束優(yōu)化問(wèn)題的一個(gè)近似K-T點(diǎn)，算法停止；否則，轉(zhuǎn)步驟（3）.（3）改進(jìn)迭代點(diǎn)：利用（12）式的罰函數(shù),按照某種線(xiàn)性搜索規(guī)則確定步長(zhǎng)，使得置.(4)修正矩陣：利用矩陣，在和點(diǎn)的其它信息，計(jì)算對(duì)稱(chēng)正定矩陣；令，轉(zhuǎn)步驟（2）.注3：遺留問(wèn)題：（1） 如何求解QP子問(wèn)題（11）？（后面討論）（2） 如何修正獲得？（3） 如何處理QP子問(wèn)題不相容？（1）的修正

22、方法：的修正有多種方法：（i）基于擬牛頓校正公式的方法（ii）基于增廣Lagrange函數(shù)的方法（iii）基于既約Hesse矩陣的方法只介紹基于擬牛頓校正公式的方法.對(duì)于的修正，一方面，應(yīng)為L(zhǎng)agrange函數(shù)的Hesse矩陣的近似；另一方面，要保持的對(duì)稱(chēng)正定性，使得相應(yīng)的QP子問(wèn)題是一個(gè)嚴(yán)格的凸二次規(guī)劃問(wèn)題.類(lèi)似于無(wú)約束問(wèn)題的擬牛頓法，令然后可利用BFGS等公式計(jì)算. (BFGS公式) 注4：與無(wú)約束問(wèn)題不同的是：這種修正不能保證條件（曲率條件）成立，因此，即使對(duì)稱(chēng)正定，也不能保證正定.為了克服此困難，1978年P(guān)owell利用和的一個(gè)凸組合代替，記為（13）修正后的BFGS公式（稱(chēng)為截?cái)郆

23、FGS修正） (14)（2）QP子問(wèn)題不相容的處理：Powell提出了一種處理方法：引進(jìn)輔助變量，解LP： （15）為該問(wèn)題的可行解，故（15）式的最優(yōu)解總是存在的，記為，顯然有.顯然原子問(wèn)題（11）（或（10）相容當(dāng)且僅當(dāng).（i）若或很小，則改變初始點(diǎn)重新開(kāi)始，此情況的發(fā)生常常因原問(wèn)題是不相容的；（ii）若，則將子問(wèn)題（11）中的約束條件用（15）中的約束條件代替，即子問(wèn)題取為（16）其中取為中的一個(gè)定值.例2：對(duì)于約束，在點(diǎn)處，求如下線(xiàn)性規(guī)劃最優(yōu)解為.若取，則對(duì)應(yīng)的QP子問(wèn)題（16）是相容的.7.3.4 二次規(guī)劃的求解方法二次規(guī)劃（QP）是非線(xiàn)性規(guī)劃中一種特殊情形，目標(biāo)函數(shù)是二次函數(shù)，約束

24、是線(xiàn)性函數(shù)。許多現(xiàn)實(shí)問(wèn)題本身可建模為二次規(guī)劃。QP是前面討論的SQP的基礎(chǔ)，在每一迭代步，均要求解一個(gè)QP子問(wèn)題。QP的算法較多，如：（1）Lagrange方法（2）起作用集方法（3）Lemke方法（4）路徑跟蹤法1Lagrange方法（求解等式約束QP問(wèn)題）考慮QP問(wèn)題 （17）為n階對(duì)稱(chēng)矩陣，為矩陣，秩為.該問(wèn)題的Lagrange函數(shù)為令，得到方程組將此方程組寫(xiě)成 （18）系數(shù)矩陣稱(chēng)為L(zhǎng)agrange矩陣.設(shè)Lagrange矩陣可逆，可表示為由式，推得假設(shè)逆矩陣存在，由上述關(guān)系可得的表達(dá)式 （19） （20） （21）（18）式兩端乘以L(fǎng)agrange矩陣的逆，得到問(wèn)題的解 （22） （2

25、3）的另一種表達(dá)式：設(shè)是問(wèn)題（17）的任一可行解，即滿(mǎn)足，在此點(diǎn)目標(biāo)函數(shù)的梯度利用和，可將（22）、（23）改寫(xiě)為 （24） （25）例3：用Lagrange法求解，可計(jì)算出 由（19）-（21）式算得，再根據(jù)（22）式，計(jì)算問(wèn)題的最優(yōu)解2起作用集方法（具有不等式約束的QP問(wèn)題）考慮具有不等式約束的QP問(wèn)題： （26）為n階對(duì)稱(chēng)正定矩陣，為矩陣，秩為. 該問(wèn)題不能直接用Lagrange方法求解，求解的策略之一，是用起作用集方法將它轉(zhuǎn)化為求解等式約束問(wèn)題.起作用集方法的基本思想：在每次迭代中，以已知的可行點(diǎn)為起點(diǎn)，把在該點(diǎn)起作用約束作為等式約束，在此約束下極小化目標(biāo)函數(shù)，而其余的約束暫且不管，求

26、得新的比較好的可行點(diǎn)后，再重復(fù)以上做法。設(shè)在第次迭代中，已知可行點(diǎn)，在該點(diǎn)起作用約束指標(biāo)集用表示.這時(shí)需求解等式約束問(wèn)題 （27）表示矩陣A的第i行，也是在處起作用約束函數(shù)的梯度.將坐標(biāo)原點(diǎn)移至，令，則 （28）問(wèn)題（27）等價(jià)于求校正量的問(wèn)題： （29）解此二次規(guī)劃問(wèn)題，求出最優(yōu)解，然后區(qū)別不同的情形，決定下面應(yīng)采取的步驟. （1）如果是可行點(diǎn)，且，則在第次迭代中，已知點(diǎn)取作 （2）如果不是可行點(diǎn)，則令方向，沿搜索. 令沿方向搜索步長(zhǎng)確定方法：基本要求：保持點(diǎn)的可行性.的取值應(yīng)使得對(duì)于每個(gè)，有 （30）已知是可行點(diǎn)，故.（1）當(dāng)時(shí)，對(duì)于任意非負(fù)數(shù)，（30）式總成立；（2）當(dāng)時(shí)，只要取正數(shù)對(duì)于每個(gè)，（30）式成立. 記 是問(wèn)題（29）的最優(yōu)解，為在第次迭代中得到較好的可行點(diǎn)，應(yīng)取 （31）并令 如