孫敏，田茂英

（1.棗莊學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，山東 棗莊 277160；2.山東煤炭衛(wèi)生學(xué)校 生理學(xué)教研室，山東 棗莊 277160）

最優(yōu)性條件是最優(yōu)化方法課程的教學(xué)重點(diǎn).一方面，最優(yōu)性條件給出了最優(yōu)解滿(mǎn)足的必要條件，因此，通過(guò)求解最優(yōu)性條件可以得到可能的最優(yōu)解，從而將搜索范圍從可行域縮小到有限個(gè)穩(wěn)定點(diǎn)或KKT點(diǎn)；另一方面，最優(yōu)性條件在最優(yōu)化問(wèn)題的算法設(shè)計(jì)中起著關(guān)鍵作用.實(shí)際上，很多最優(yōu)化算法的迭代格式、終止條件等的設(shè)計(jì)動(dòng)機(jī)來(lái)自于最優(yōu)性條件[1-5]，如增廣拉格朗日乘子法中乘子迭代格式的設(shè)計(jì)，可分裂凸規(guī)劃的交替方向法對(duì)偶變量迭代格式的設(shè)計(jì)等.最優(yōu)性條件在很多領(lǐng)域有著廣泛的應(yīng)用，是很多機(jī)器學(xué)習(xí)問(wèn)題分析的必要方法[6-7].

最優(yōu)性條件是最優(yōu)化方法課程的教學(xué)難點(diǎn).在學(xué)習(xí)高等數(shù)學(xué)多元函數(shù)約束極值問(wèn)題時(shí)，通過(guò)引入拉格朗日函數(shù)，將含等式約束的優(yōu)化問(wèn)題轉(zhuǎn)化成無(wú)約束優(yōu)化問(wèn)題，進(jìn)而借助無(wú)約束優(yōu)化問(wèn)題的最優(yōu)性條件給出了等式約束最優(yōu)化問(wèn)題的最優(yōu)性必要條件.但是由于不等式約束優(yōu)化問(wèn)題最優(yōu)性條件的證明需要引入更多的符號(hào)與概念，因此國(guó)內(nèi)常用的高等數(shù)學(xué)教材一般不對(duì)該問(wèn)題進(jìn)行研究.一般的最優(yōu)化教材往往按照下面的思路研究該問(wèn)題：為了給出不等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件，首先，引入3類(lèi)向量集合，即可行方向集合、線(xiàn)性化錐和下降方向集合；然后，給出前2個(gè)集合的等價(jià)條件，后2個(gè)交集是空集的等價(jià)代數(shù)形式，該等價(jià)形式即為最優(yōu)化問(wèn)題的最優(yōu)性一階必要條件.由于線(xiàn)性化錐與下降方向集合的交集可以表示成一個(gè)線(xiàn)性系統(tǒng)，因此通過(guò)Farkas 引理，該交集是空集等價(jià)于一個(gè)對(duì)應(yīng)的線(xiàn)性系統(tǒng)有解，而由線(xiàn)性系統(tǒng)有解可得到最優(yōu)性條件的代數(shù)形式[8-10].

具體分析過(guò)程見(jiàn)圖1.

圖1 不等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件

考慮一個(gè)簡(jiǎn)單的實(shí)例來(lái)說(shuō)明不等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件分析過(guò)程.

例1考慮不等式約束優(yōu)化問(wèn)題

分析類(lèi)似于數(shù)學(xué)分析課程所學(xué)的分析方法，為了求解該問(wèn)題的最優(yōu)解，需要找出可能的最優(yōu)解，即挖掘最優(yōu)解應(yīng)該具有的性質(zhì).顯然，最優(yōu)解應(yīng)該滿(mǎn)足：（1）可行性；（2）在最優(yōu)解處，沿著任意方向前進(jìn)任意小的步長(zhǎng)后，要么出了可行域，要么目標(biāo)值上升，這說(shuō)明在該點(diǎn)處不存在一個(gè)方向既是可行方向又是下降方向.由此分析得到最優(yōu)解應(yīng)該滿(mǎn)足條件

式中：I（x1,x2）為有效約束集合.于是必要條件可以松弛為

這樣處理產(chǎn)生了2個(gè)問(wèn)題：（1）在什么條件下，F(xiàn)D（x1,x2）=LD（x1,x2）；（2）LD（x1,x2）的定義是一種隱式的形式，即只有知道了（x1,x2），才能求出I（x1,x2），這樣才能將LD（x1,x2）表示成不等式組.我們的目的就是求（x1,x2），這與求二次規(guī)劃的積極集時(shí)遇到的問(wèn)題一樣，因此需要引入Farkas 引理，給出一個(gè)線(xiàn)性系統(tǒng)無(wú)解與另一個(gè)線(xiàn)性系統(tǒng)有界的結(jié)論，進(jìn)而導(dǎo)出約束優(yōu)化問(wèn)題的一階必要條件.

由分析過(guò)程可以看出，與無(wú)約束最優(yōu)化問(wèn)題或等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件不同，不等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件需要引入集合、線(xiàn)性系統(tǒng)、Farkas 引理等一系列新的概念或結(jié)論.與同樣類(lèi)型的問(wèn)題相比，其分析過(guò)程有些繁瑣，沒(méi)有充分利用已經(jīng)得到的結(jié)論.

課程教學(xué)內(nèi)容的起承轉(zhuǎn)合對(duì)于學(xué)生建構(gòu)一門(mén)課的內(nèi)容體系起著非常重要的作用.本文針對(duì)不等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件設(shè)計(jì)一套全新的教學(xué)過(guò)程，其充分利用了等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件，避免了集合、線(xiàn)性系統(tǒng)、Farkas 引理等元素，遵循了“如無(wú)必要，勿增實(shí)體”的奧卡姆剃刀原理.

1 等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件

回顧等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件.考慮等式約束最優(yōu)化問(wèn)題

2 不等式約束最優(yōu)化問(wèn)題最優(yōu)性條件的教學(xué)設(shè)計(jì)

基于等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件，給出不等式約束最優(yōu)化問(wèn)題最優(yōu)性條件的教學(xué)設(shè)計(jì).為了討論過(guò)程的簡(jiǎn)潔，考慮只含不等式約束的最優(yōu)化問(wèn)題

2.1 問(wèn)題（1）與問(wèn)題（2）的區(qū)別

問(wèn)題（2）與問(wèn)題（1）的區(qū)別只在于將等式約束換成了不等式約束.回顧在化線(xiàn)性規(guī)劃的一般形式為標(biāo)準(zhǔn)形式時(shí)，通過(guò)引入松弛變量可以將不等式約束轉(zhuǎn)化成等式約束.如對(duì)于約束x1+2x2≤ 1，引入松弛變量x3，得

為了保持約束的線(xiàn)性性，要求松弛變量x3非負(fù).

2.2 形式轉(zhuǎn)化

受線(xiàn)性規(guī)劃標(biāo)準(zhǔn)化（3）的啟發(fā)，通過(guò)引入松弛變量，將問(wèn)題（2）轉(zhuǎn)化成問(wèn)題（1）的形式，即

2.3 初步結(jié)果

根據(jù)定理1 可得到問(wèn)題（4）最優(yōu)解滿(mǎn)足的一階必要條件.為此引入向量ei?Rm表示單位向量，其第i個(gè)元素為1，其余元素全為0.

2.4 乘子非負(fù)性的討論

與KKT 條件相比，式（7）對(duì)乘子的符號(hào)沒(méi)有施加限制，需要再考慮二階必要條件.

2.5 線(xiàn)性無(wú)關(guān)的討論

例2直接利用等式約束優(yōu)化問(wèn)題的最優(yōu)性條件求解例1 中的不等式約束優(yōu)化問(wèn)題.

解引入松弛變量y1,y2，得

利用等式約束優(yōu)化問(wèn)題的必要條件得

取d=（0,0,λ1,0），則d顯然滿(mǎn)足 2d1x1+d2+2d3y1=0,d1+2d2x2+2d4y2=0，于是由等式約束的二階必要條件可知，2λ13≥0，即λ1≥0.類(lèi)似地，取d=（0,0,0,λ2），可得λ2≥0.將這些條件綜合到一起就得到了約束優(yōu)化問(wèn)題的K-T 條件.進(jìn)而利用該K-T 條件求出可能的極值點(diǎn)，再結(jié)合最優(yōu)性的二階必要與充分條件可以得到該問(wèn)題的最優(yōu)解.

比較例1 與例2 可以看出，直接利用等式約束優(yōu)化問(wèn)題的最優(yōu)性條件來(lái)推導(dǎo)不等式約束優(yōu)化問(wèn)題的最優(yōu)性條件是可行的，并且更便于學(xué)生理解這個(gè)知識(shí)點(diǎn)，同時(shí)便于構(gòu)建起這一部分的知識(shí)邏輯體系.

3 結(jié)語(yǔ)

最優(yōu)性條件是最優(yōu)化方法課程的基礎(chǔ)而重要的內(nèi)容.基于等式約束最優(yōu)化問(wèn)題的最優(yōu)性條件，本文給出了不等式約束最優(yōu)化問(wèn)題一階最優(yōu)性必要條件的一種新的教學(xué)設(shè)計(jì)思路.該思路沒(méi)有用到Farkas 引理，整個(gè)教學(xué)設(shè)計(jì)與已經(jīng)學(xué)過(guò)的知識(shí)緊密結(jié)合，可以使學(xué)生從整體上更好地理解與掌握相關(guān)知識(shí)點(diǎn)，進(jìn)而建構(gòu)起最優(yōu)化方法的結(jié)構(gòu)體系.今后，將基于等式約束最優(yōu)化問(wèn)題的二階條件給出不等式約束最優(yōu)化問(wèn)題二階條件的教學(xué)設(shè)計(jì).