最優(yōu)化理論與算法(第九章)

第九章二次規(guī)劃§9.1二次規(guī)劃問題稱形如（9.1）的非線性規(guī)劃問題為二次規(guī)劃問題。對二次規(guī)劃問題，有如下的最優(yōu)性條件。定理9.1設(shè)是（9.1）的局部極小點，則必存在乘子，使得（9.2）且對于一切滿足于：的，都有。注：1）上述定理的前后兩部分分別對應(yīng)于一、二階的必要條件；2）滿足上述條件的，都有；3）當(dāng)約束條件均為線性函數(shù)時，容易證明：及上面給出的是二次規(guī)劃的必要性條件，下面給出充分性條件。定理9.2設(shè)是K-T點，是相應(yīng)的Lagrange乘子，如果對滿足（9.3）的一切非零向量，都有，則是（9.1）的局部嚴(yán)格極小點。注：條件組（9.3）表示的正好是的條件，因此這個定理實際上是上一節(jié)二階充分性條件在二次規(guī)劃情形的特殊表述。對二次規(guī)劃問題還有如下充分必要條件定理9.3設(shè)是（9.1）的可行解，則是一局部最小點的充要條件是：存在乘子，使得（9.2）滿足，且對一切滿足（9.3）的都有注：這個定理的證明可參見韓繼業(yè)《二次規(guī)劃理論與算法》，曲阜師范學(xué)院學(xué)報，1985年第一期1~8。特別地，當(dāng)為正定或半正定時，目標(biāo)函數(shù)為凸函數(shù)，二次規(guī)劃為凸規(guī)劃。因此任何K-T點必為二次規(guī)劃的全局極小點，此時求解（9.1）等價于求解（9.4）其中，，，§9.2對偶性質(zhì)二次規(guī)劃問題：（9.5）的Wolfe對偶為：(9.6)在正定時，若令，則（9.6）可改寫為：（9.7）假定是（9.5）的可行解，而是對偶問題（9.7）的可行解，則有：由于時，，及，并且正定，即得：等式成立當(dāng)且僅當(dāng)：同時。定理9.4（對偶定理）設(shè)是原問題（9.5）的可行解，而是對偶問題（9.7）的可行解，則總有：；若存在（9.5）的可行點，（9.7）的可行點，使得：，則，分別為原問題與對偶問題的最優(yōu)解。由于當(dāng)且僅當(dāng)：且時，。從而有下面定理：定理9.5設(shè)正定，則（9.5）的可行點是最優(yōu)解的充要條件是存在對偶問題（9.7）的可行解滿足：，及。定理9.6設(shè)正定，則原問題不可行當(dāng)且僅當(dāng)對偶問題無界。證明：1）若原問題可行，則由知對偶問題有界；2）若原問題不可行，利用Farkas引理，可構(gòu)造一無界的對偶可行解，故對偶問題無界。我們已經(jīng)看到，原問題的Lagrange函數(shù)與對偶問題有密切聯(lián)系，實際上它正是對偶形式（9.6）的目標(biāo)函數(shù)。求解問題（9.5）求解上節(jié)的K-T問題（9.4）求Lagrange函數(shù)在區(qū)域上的穩(wěn)定點。由的Hessian矩陣為利用可知恰為個正特征值，而且它的負(fù)特征值的個數(shù)正好為的秩。因而，的穩(wěn)定點一般是一個鞍點，下面證明的確是的鞍點。事實上，我們有這里是對偶問題（9.7）的可行域。而對任何，若令則是（9.7）的可行點，而且（由于對給定的，是的凸函數(shù)，的最優(yōu)解可由解出得，同時注意到即可得到上式。）設(shè)是K-T問題（9.4）的解，令，則知是對偶問題（9.7）的可行點。于是和都有：即：故是的鞍點。反之，我們還可以證明，若是的鞍點，則必為原始問題（9.1）的極小點。上面討論給出了鞍點問題解與原極小化問題解之間的關(guān)系：定理9.7設(shè)正定，則是原始問題極小點的充要條件是：存在，使得對一切，和一切，都有。§9.3等式約束問題問題形式：（假定）（9.8）一、消去法記，則可改寫為解出得將其代人目標(biāo)函數(shù)得無約束問題：（9.9）最優(yōu)性條件：1）若正定，2）若半正定，借助廣義逆，有（任意，解不唯一）3）若有負(fù)特征值，則問題無界。注：問題（9.9）可利用無約束優(yōu)化問題的各種算法求解。二、廣義消去法設(shè)是域空間的一組線性無關(guān)的向量（即的一組基），是的一組線性無關(guān)向量，顯然與互為正交補。若記，則有：非奇異，而。事實上，由于與的列向量組均為的基，故有：(為兩組基之間的過渡矩陣)進(jìn)一步有：由列滿秩知是正定矩陣，再由可逆，故有非奇異。而由于中列向量均在中，故有。顯然，，可表示為。特別地，對滿足的有得因此將此代入目標(biāo)函數(shù)并略去常數(shù)項，得到：（9.10）稱為既約Hessian矩陣，而為既約梯度。三、Lagrange乘子法直接求Lagrange函數(shù)的穩(wěn)定點：（9.11）§9.4積極集法（有效集法）一、算法的理論基礎(chǔ)積極集法是通過求解有限多個等式約束二次規(guī)劃問題，來求解一般約束二次規(guī)劃問題，下面引理是其理論基礎(chǔ)。定理9.8設(shè)是二次規(guī)劃問題（9.1）的局部極小點，則也必是問題（9.12）的局部極小點；反之，若是（9.12）的K-T點，且還是原問題（9.1）的可行點。相應(yīng)Lagrange乘子滿足：，。則也是原問題的K-T點。證明：設(shè)是原問題的解，若它不是（9.12）的極小點，那么必有充分靠近的點使得，而當(dāng)充分靠近時，也必是原問題的可行點，這與是最優(yōu)點矛盾。另一方面，設(shè)是原問題的可行點，且滿足（9.12）的K-T條件，則存在，使得且還有，。進(jìn)一步地，當(dāng)時，令，則有且滿足，，由可行，即知是原問題的K-T點。積極集法是一個可行點法，在迭代過程中，始終保持迭代點可行。而每次迭代求解一個只含等式約束的二次規(guī)劃。如果等式約束問題的解是原約束問題的可行解，則進(jìn)一步檢驗，是否滿足。若滿足，則停止計算，否則，可去掉一約束重新求解約束問題。若等式約束二次規(guī)劃之解不是原問題的可行解，則需要增加約束，然后重新求解等式約束問題。二、算法的迭代步驟1．給出初始可行點，令。2．求解等式約束問題得，若，則轉(zhuǎn)3.若（），算法停止；令，置，，轉(zhuǎn)4.3.令，；若，轉(zhuǎn)4；否則，找到使得，令。4．轉(zhuǎn)2.三、算法的有限終止性定理9.8設(shè)是由積極集法產(chǎn)生的點列，若對任何都有線性無關(guān)，則算法必有限終止于問題的K-T