最優(yōu)化方法課程研究性教學(xué)之初探
——拉格朗日乘子法*

孫 敏，葛 靜

(棗莊學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，山東 棗莊 277160)

引言

最優(yōu)化理論與方法是運(yùn)籌學(xué)的一個重要分支，其包含了線性規(guī)劃、非線性規(guī)劃、組合優(yōu)化、動態(tài)規(guī)劃以及最優(yōu)控制等最優(yōu)化模型.學(xué)者們對這些最優(yōu)化分支進(jìn)行了深入的研究，針對每個分支，相應(yīng)的最優(yōu)化理論與求解算法都已經(jīng)相當(dāng)完善[1].在求解約束優(yōu)化問題的方法中，拉格朗日乘子法因?yàn)槠淞己玫臄?shù)值表現(xiàn)以及在實(shí)際生活中的廣泛應(yīng)用而獲得了學(xué)者們更多的關(guān)注.

拉格朗日乘子法是《最優(yōu)化理論與方法》的重點(diǎn)，也是一個教學(xué)難點(diǎn).本文中，擬對拉格朗日乘子法的教學(xué)進(jìn)行探討，對這塊內(nèi)容采用層次化教學(xué)模式：動機(jī)→目標(biāo)→算法→擴(kuò)展→應(yīng)用，層層遞進(jìn)，由淺入深，以一種立體的形式將這個知識點(diǎn)慢慢展示給學(xué)生，進(jìn)而達(dá)到分散難點(diǎn)的目的.

1 拉格朗日乘子法的設(shè)計動機(jī)

考慮等式約束優(yōu)化問題

minf(x)
s.t.h(x)=0

(1)

其中f(x):Rn→R,h(x):Rn→Rl.外罰函數(shù)法通過引入罰因子，對不滿足約束的點(diǎn)實(shí)施懲罰，將約束優(yōu)化問題(1)轉(zhuǎn)化為一系列的無約束優(yōu)化問題.為了讓這些無約束優(yōu)化問題的最優(yōu)解向(1)的可行域靠近，需要讓罰因子趨于正無窮，而這會給求解無約束優(yōu)化問題帶來困難.下面通過一個例子來說明當(dāng)罰因子趨于無窮大時，無約束優(yōu)化問題會發(fā)生什么變化.

例1 考慮約束最優(yōu)化問題

minf(x)=(x1-1)2+2(x2-1)2

s.t.x1+x2=1

解 引入增廣目標(biāo)函數(shù)Pσ(x)=(x1-1)2+2(x2-1)2+σ(x1+x2-1)2,

取[0,0]T作為初始迭代點(diǎn)，罰因子取為σk=k，利用最速下降法求解第k個子問題(k=0,1,2,…)

minPσk(x)=(x1-1)2+2(x2-1)2+σk(x1+x2-1)2.

計算過程的信息見表1.

表1 利用最速下降法求解子問題的信息

由表1可以得到，隨著子問題目標(biāo)函數(shù)條件數(shù)的增大，子問題的迭代次數(shù)變得越來越大，到了第100 000次迭代，子問題沒有求解成功.可以從幾何上解釋如下：目標(biāo)函數(shù)的條件數(shù)越大，其等高線越來越密集，因此使用梯度類算法求解將會變得非常困難[2].于是為了提高算法的計算效果，需要設(shè)計一種罰因子不需要趨于無窮的罰函數(shù)法，而拉格朗日乘子法就是這樣一類算法.

2 拉格朗日乘子法的設(shè)計思路

問題(1)的拉格朗日函數(shù)是L(x,λ)=f(x)-λTh(x)，KKT條件是

(2)

其中λ∈Rm為拉格朗日乘子.下面將系統(tǒng)(2)視為求解目標(biāo).問題(1)的外罰法的子問題是

其最優(yōu)性條件是

▽Pσk(x)=▽f(x)+σk(▽h(x))h(x)=0

(3)

這說明每次求解外罰法的子問題時，實(shí)際得到了方程(3).對比系統(tǒng)(2)，方程(3)中缺少了拉格朗日乘子項(xiàng)，因此補(bǔ)充這一項(xiàng)得

▽f(x)-(▽h(x))λ+σk(▽h(x))h(x)=0

(4)

容易看出這是無約束優(yōu)化問題(λ視為參數(shù))

(5)

的最優(yōu)性條件，其中Lσk(x,λ)被稱為增廣的拉格朗日函數(shù)[1].最優(yōu)化問題(5)有如下性質(zhì).

定理1[3]給定參數(shù)λ，假設(shè)x*是最優(yōu)化問題(5)的最優(yōu)解，則(x*,λ)是問題(1)的KKT對的充要條件是h(x*)=0.

對比方程(4)與系統(tǒng)(2)可以看出，只有當(dāng)h(x)=0時，由方程(4)才能得到系統(tǒng)(2).而在實(shí)際問題中，問題(5)的最優(yōu)解同時滿足h(x)=0的概率往往是很低的.下面這四個方法可以解決這個問題.

方法二：同時求解關(guān)于x與λ的如下無約束優(yōu)化問題

(6)

該問題的最優(yōu)性條件是

(7)

這與系統(tǒng)(2)是等價的.優(yōu)化問題(6)的維度是m+l，比問題(1)的維度n增大了，因此對于約束比較多的等式約束優(yōu)化問題，無約束優(yōu)化問題(6)往往并不比原問題容易求解，尤其是當(dāng)所求問題的維度比較大時.

對比系統(tǒng)(2)的第一個式子，可以利用λk+1=λk-σkh(xk)更新對偶變量λ.于是，得到拉格朗日乘子法

(8)

與(7)相比，拉格朗日乘子法(8)的優(yōu)點(diǎn)是其交替的在原始空間Rn與對偶空間Rl中更新兩個變量.這體現(xiàn)了分而治之的思想，將一個Rn+l維的問題分解為兩個低維的子問題，這個優(yōu)點(diǎn)隨著問題維度的增加愈加明顯.同時拉格朗日乘子法(8)在求解一些凸優(yōu)化問題時有比較好的收斂結(jié)果[4].

方法四：如果約束條件是線性的，即h(x)=Ax-b，文獻(xiàn)[5]提出了如下的定制拉格朗日乘子法

(9)

其中r>0,s>0,rs>‖ATA‖.關(guān)于迭代格式(9)，有如下收斂結(jié)果[5].

定理3[5]如果參數(shù)r,s滿足r>0,s>0,rs>‖ATA‖，且f(x)是凸函數(shù)，則迭代格式(9)產(chǎn)生的點(diǎn)列{xk}全局收斂于問題(1)的一個最優(yōu)解.

3 應(yīng)用

例2 考慮約束最優(yōu)化問題

下面利用第2部分中的4種方法來求解該約束優(yōu)化問題.

方法一：取一個充分大的罰因子，本例中取σk=106，并且給定λ=1.求解

根據(jù)無約束優(yōu)化問題的一階必要條件得

根據(jù)無約束優(yōu)化問題的一階必要條件得

方法三：給定λk，則由拉格朗日乘子法的迭代格式得

由無約束優(yōu)化問題的一階必要條件得

即

(10)

方法四：由迭代格式(9)得

由無約束優(yōu)化問題的一階必要條件得

(11)

下面給出一個例子來說明拉格朗日乘子法可能失效.

例3 考慮約束最優(yōu)化問題

解 類似于例2的求解過程，用拉格朗日乘子法求解上面的問題時得到如下迭代格式

(12)

顯然當(dāng)σ>0時，有|2/(2-σ)|>1，因此序列{λk}發(fā)散.由此可見，帶固定罰因子的拉格朗日乘子法可能失效.

4 結(jié)語

本文討論了拉格朗日乘子法的層次化教學(xué)模式：從引入拉格朗日乘子的必要性入手，給出了由目標(biāo)到算法的反向設(shè)計思路，進(jìn)而提出了四種基于增廣目標(biāo)函數(shù)的算法，并對算法的優(yōu)缺點(diǎn)進(jìn)行了分析.最后給出了實(shí)例詳細(xì)說明了如何使用這些算法，舉例說明了帶固定罰因子的拉格朗日乘子法在求解非凸優(yōu)化問題時可能失效.