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

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