1、機(jī)械優(yōu)化設(shè)計(jì)報(bào)告（2）關(guān)于拉格朗日乘子法及KKT條件的探究姓名：xxx學(xué)號(hào)：xxx0（北京理工大學(xué)機(jī)械與車輛學(xué)院車輛工程，北京 100081）摘要：拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)條件是求解約束優(yōu)化問題的重要方法，在有等式約束時(shí)使用拉格朗日乘子法，在有不等約束時(shí)使用KKT條件。當(dāng)然，這兩個(gè)方法求得的結(jié)果只是必要條件，只有當(dāng)目標(biāo)函數(shù)是凸函數(shù)的情況下，才能保證是充分必要條件。本文將首先描述拉格朗日乘子法和KKT條件，然后對其進(jìn)行推導(dǎo)，最后談?wù)劄槭裁匆@樣求最優(yōu)值。1. 拉格朗日乘子法及KKT條件概述通常我們需要求解的最優(yōu)化問題

2、有如下幾類：(i) 無約束優(yōu)化問題，可以寫為:;(ii) 有等式約束的優(yōu)化問題，可以寫為:;s.t. ; ;(iii) 有不等式約束的優(yōu)化問題，可以寫為：;s.t. 對于第(i)類的優(yōu)化問題，常常使用的方法就是Fermat定理，即求取的導(dǎo)數(shù)，然后令其為零，可以求得候選最優(yōu)值，再在這些候選值中驗(yàn)證；如果是凸函數(shù)，可以保證是最優(yōu)解。對于第(ii)類的優(yōu)化問題，常常使用的方法就是拉格朗日乘子法，即把等式約束用一個(gè)系數(shù)與寫為一個(gè)式子，稱為拉格朗日函數(shù)，而系數(shù)稱為拉格朗日乘子。通過拉格朗日函數(shù)對各個(gè)變量求導(dǎo)，令其為零，可以求得候選值集合，然后驗(yàn)證求得最優(yōu)值。對于第(iii)類的優(yōu)化問題，常常使用的方法就

3、是KKT條件。同樣地，我們把所有的等式、不等式約束與寫為一個(gè)式子，也叫拉格朗日函數(shù)，系數(shù)也稱拉格朗日乘子，通過一些條件，可以求出最優(yōu)值的必要條件，這個(gè)條件稱為KKT條件。1.1拉格朗日乘子法通過引入拉格朗日乘子把等式約束和目標(biāo)函數(shù)組合成為一個(gè)新的目標(biāo)函數(shù)：把作為一個(gè)新的無約束條件的目標(biāo)函數(shù)來求解它的極值點(diǎn)，所得結(jié)果就是滿足約束條件的原目標(biāo)函數(shù)的極值點(diǎn)。其中稱為拉格朗日函數(shù)。函數(shù)具有極值的必要條件為： 可得個(gè)方程，從而解得和共個(gè)未知變量的值。由上述方程組求得的是函數(shù)極值點(diǎn)的坐標(biāo)值。1.2 KKT條件工程上大多數(shù)優(yōu)化問題都可表示為具有不等式約束條件的優(yōu)化問題，求解此類問題的目標(biāo)函數(shù)極值點(diǎn)一般用KK

4、T條件。首先，設(shè)計(jì)變量為n維變量，它受有q個(gè)不等式約束，p個(gè)等式約束。然后把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫為一個(gè)函數(shù)：對求導(dǎo)，得以下極值條件：其中，是對應(yīng)于不等式約束的拉格朗日乘子向量，并有非負(fù)的要求。對于僅有等式約束的優(yōu)化問題，上式 中省去，即變?yōu)榈仁郊s束的拉格朗日乘子法。所以說KKT條件是拉格朗日乘子法的泛化。KKT最優(yōu)化條件是Karush1939以及Kuhn和Tucker1951先后獨(dú)立發(fā)表出來的。這組最優(yōu)化條件在Kuhn和Tucker發(fā)表之后才逐漸受到重視, 因此許多書只記載成Kuhn-Tucker 最優(yōu)化條件 (Kuhn-Tucker conditions)。2. 拉格朗

5、日乘子法及KKT條件的推導(dǎo)2.1拉格朗日乘子法的推導(dǎo)為推導(dǎo)簡便起見，考慮兩變量目標(biāo)函數(shù)在單個(gè)等式約束條件下的最優(yōu)化問題。一方面，在極值點(diǎn)處必滿足：（2.1.1）故有：（2.1.2）另一方面，由于，故有：（2.1.3）由以上兩式可得：（2.1.4）不妨令（2.1.5）則有（2.1.6）令，那么下面兩個(gè)問題是互相等價(jià)的：（2.1.7）這是因?yàn)楹瘮?shù)H存在極值的必要條件為（2.1.8）而上式的結(jié)果恰與式（2.1.6）及是等價(jià)的。這樣就將原約束問題轉(zhuǎn)為一個(gè)無約束的最優(yōu)化問題，通過求解函數(shù)的極小值完成對極小值的求取。以上推導(dǎo)對于一般的多變量目標(biāo)函數(shù)和多個(gè)等式約束情形推導(dǎo)過程類似，其結(jié)論也是不變的。此時(shí)引入

6、的拉格朗日乘子向量中乘子的個(gè)數(shù)等于等式約束的個(gè)數(shù)。2.2 KKT條件的推導(dǎo)2.2.1一元函數(shù)在給定區(qū)間上的極值條件對于一元函數(shù)在給定區(qū)間上的極值問題，可以寫成具有不等式約束條件的優(yōu)化問題：s.t. 為了能應(yīng)用拉格朗日乘子法來討論此問題的極值條件，需引入松弛變量使不等式約束變成等式約束。設(shè)和為兩個(gè)松弛變量，則上述兩個(gè)不等式約束可寫成如下的兩個(gè)相應(yīng)的等式約束這樣則得該問題的拉格朗日函數(shù)其中的和是對應(yīng)于不等式約束條件的拉格朗日乘子，應(yīng)滿足非負(fù)的要求，即根據(jù)拉格朗日乘子法，此問題的極值條件是分析可知，此時(shí)不是，就是。當(dāng)時(shí)，約束起作用，即為的情況。當(dāng)時(shí)，約束不起作用，即為的情況。通過以上分析可得這說明對

7、于和，二者至少必有一個(gè)需要取零值，因此可將的條件寫成。同樣，對于的分析結(jié)果也可表示為因此，可將的條件寫成。這樣，對于一元函數(shù)在給定區(qū)間上的極值條件，就可完整地表示為從以上分析可以看出來，對于不起作用約束的拉格朗日乘子取零值，因此可以用約束的下標(biāo)集合。當(dāng)時(shí)，兩個(gè)約束均不起作用，。當(dāng),第一個(gè)約束起作用，故有，。當(dāng)，第二個(gè)約束起作用，。這樣可將式2-17改寫為如下形式即在極值條件中只考慮起作用的約束及其相應(yīng)的拉格朗日乘子。2.2.2 KKT條件對于多元函數(shù)不等式約束優(yōu)化問題：s.t. 其中設(shè)計(jì)變量向量為n維向量，它受有m個(gè)不等式的約束的限制。在用拉格朗日乘子法推導(dǎo)出相應(yīng)的極值條件時(shí)，需要引入m個(gè)松弛

8、變量，使不等式約束變成等式約束 ，從而組成相應(yīng)的拉格朗日函數(shù)。其中是對應(yīng)于不等式約束的拉格朗日乘子向量，并有非負(fù)的要求。根據(jù)無約束極值條件，在極值點(diǎn)處有 仿照對一元函數(shù)在給定區(qū)間上極值條件的推導(dǎo)過程，同樣可以得到具有不等式約束多余函數(shù)極值條件上式即為庫恩-塔克條件。若引入起作用約束的下標(biāo)集合KKT條件又可寫成如下形式（2.2.2.1）將式（2.2.2.1）的偏微分形式表示為梯度形式，得或 這表明KKT條件的幾何意義是：在約束極小值點(diǎn)處，函數(shù)的負(fù)梯度一定能表示成所有起作用約束在該點(diǎn)梯度的非負(fù)線性組合。3. 拉格朗日乘子法的合理性設(shè)想我們的目標(biāo)函數(shù)，是向量, z取不同的值，相當(dāng)于可以投影在構(gòu)成的平

9、面（曲面）上，即成為等高線。如圖3.1，目標(biāo)函數(shù)是，這里x,y是標(biāo)量，虛線是等高線，現(xiàn)在假設(shè)我們的約束，是向量，在構(gòu)成的平面或者曲面上是一條曲線，假設(shè)與等高線相交，交點(diǎn)就是同時(shí)滿足等式約束條件和目標(biāo)函數(shù)的可行域的值，但肯定不是最優(yōu)值，因?yàn)橄嘟灰馕吨隙ㄟ€存在其它的等高線在該條等高線的內(nèi)部或者外部，使得新的等高線與目標(biāo)函數(shù)的交點(diǎn)的值更大或者更小，只有到等高線與目標(biāo)函數(shù)的曲線相切(或曲面和曲線在面垂直延伸面的交線)的時(shí)候，可能取得最優(yōu)值，如圖3.1所示，即等高線和目標(biāo)函數(shù)的曲線在該點(diǎn)的法向量必須有相同方向（等高線與目標(biāo)函數(shù)的曲線相切，即斜率相等），所以最優(yōu)值必須滿足：，是常數(shù)，表示左右兩邊同向。這個(gè)等式就是對參數(shù)求導(dǎo)的結(jié)果。圖3.1 綠線： g(x,y) = c點(diǎn)的軌跡；藍(lán)線是f的等高線；箭頭表示斜率，和等高線的法線平行。4.總結(jié)本文首先對常見的三類優(yōu)化問題進(jìn)行簡單敘述，并引出拉格朗日乘子法和KKT條件的概念以及其在相應(yīng)的優(yōu)化問題中的使用方法。其次對拉格朗日乘子法及KKT條件進(jìn)行數(shù)學(xué)上的推導(dǎo)。最后通過對拉格朗日乘子法幾何意義的描述，說明其在求解等式約束極值問題時(shí)的合理性。參考文獻(xiàn)1 李志鋒。機(jī)械優(yōu)化設(shè)計(jì)。高等教育出版社。2