拉格朗日乘子與單純形乘子關(guān)系探討

　　[摘 要] 拉格朗日乘子法是求解含等式約束極值問(wèn)題的有效方法，其核心思想是通過(guò)引入拉格朗日乘子將條件極值問(wèn)題轉(zhuǎn)化為無(wú)條件極值問(wèn)題，而單純形方法是求解帶不等式約束的線性規(guī)劃問(wèn)題的經(jīng)典方法，其矩陣描述中含有單純形乘子參數(shù)，即影子價(jià)格. 在線性規(guī)劃的基本可行解非退化的假設(shè)下，證明了單純形乘子就是拉格朗日乘子.通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了理論分析，特別地，通過(guò)實(shí)際例子說(shuō)明了當(dāng)最優(yōu)解是退化基可行解時(shí)，拉格朗日乘子可能包含了單純形乘子.

　　孫敏， 棗莊學(xué)院學(xué)報(bào) 發(fā)表時(shí)間：2021-09-01

　　[關(guān)鍵詞] 等式約束極值問(wèn)題; 拉格朗日乘子; 一般約束極值問(wèn)題; 單純形乘子

　　0 引言

　　最優(yōu)化是運(yùn)籌學(xué)的一個(gè)重要分支，其在經(jīng)濟(jì)、管理、軍事、工業(yè)設(shè)計(jì)等領(lǐng)域有著廣泛的應(yīng)用[1 - 2]. 例如，旅行售貨員問(wèn)題、中國(guó)郵路問(wèn)題、指派問(wèn)題、運(yùn)輸問(wèn)題等都可以轉(zhuǎn)化成最優(yōu)化問(wèn)題，進(jìn)而借助于最優(yōu)化算法求解.

　　從約束類型上看，最優(yōu)化問(wèn)題包括等式約束優(yōu)化問(wèn)題和一般約束優(yōu)化問(wèn)題. 求解等式約束優(yōu)化問(wèn)題的最基礎(chǔ)、最簡(jiǎn)單的方法是拉格朗日乘子法[3]，該方法通過(guò)對(duì)約束引入拉格朗日乘子構(gòu)造一個(gè)增廣的目標(biāo)函數(shù)，然后求解這個(gè)增廣的目標(biāo)函數(shù)的無(wú)約束極值，進(jìn)而得到條件極值問(wèn)題的最優(yōu)解的可能解，最后通過(guò)一些輔助準(zhǔn)則判斷這些可能解哪些是原問(wèn)題的極值點(diǎn). 線性規(guī)劃是一個(gè)最簡(jiǎn)單的約束優(yōu)化問(wèn)題，該問(wèn)題的標(biāo)準(zhǔn)形式既含等式約束，又含決策變量的非負(fù)約束，因此其屬于一般約束優(yōu)化問(wèn)題. 許多求解一般約束優(yōu)化問(wèn)題的迭代算法可以用來(lái)求解線性規(guī)劃，比如罰函數(shù)法、SQP 法、投影梯度法、簡(jiǎn)約梯度法等[4]. 求解線性規(guī)劃的定制方法包括單純形法、橢球法、內(nèi)點(diǎn)法等，其中單純形法是求解線性規(guī)劃最經(jīng)典的方法之一，該方法充分利用線性規(guī)劃的一系列特殊性質(zhì)[2]，在基本可行解集合中通過(guò)若干次的旋轉(zhuǎn)變換，可以在有限步內(nèi)求出線性規(guī)劃的最優(yōu)解或判斷最優(yōu)解不存在. 在單純形法的矩陣描述中，單純形乘子是一個(gè)重要的參數(shù)，其出現(xiàn)在檢驗(yàn)數(shù)及目標(biāo)函數(shù)值的表達(dá)式中，同時(shí)在最優(yōu)基的假設(shè)下，其表示資源的影子價(jià)格[2].

　　拉格朗日乘子和單純形乘子分別是描述拉格朗日乘子法和單純形法中的兩個(gè)重要參數(shù). 通過(guò)簡(jiǎn)單的變形，將線性規(guī)劃的決策變量非負(fù)約束轉(zhuǎn)化成等式約束，進(jìn)而利用拉格朗日乘子法求解線性規(guī)劃. 在線性規(guī)劃的基本可行解非退化的假設(shè)下，證明了單純形乘子就是拉格朗日乘子. 同時(shí)我們通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了理論分析.

　　1 拉格朗日乘子與單純形乘子

　　考慮等式約束的極值問(wèn)題

　　max Z = f( x) s. t. h( x) = 0 ( 1) 其中，f( x) : Rn → R 的光滑函數(shù)，h( x) : Rn → Rm 的光滑映射. 拉格朗日乘子法求解問(wèn)題( 1) 的步驟如下[3].首先引入拉格朗日乘子 λ ∈ R1 ×m 得到增廣的目標(biāo)函數(shù) L( x，λ) = f( x) - λh( x) 然后求 L( x，λ) 最值點(diǎn)的候選點(diǎn)，即解方程組 L( x，λ)  x = f( x) - h( x) λT = 0  L( x，λ)  λ = - h( x) T { = 0

　　最后根據(jù)問(wèn)題的其他信息判斷在最值點(diǎn)的候選點(diǎn)中哪些是最值點(diǎn)，也可以借助二階最優(yōu)性的充分條件來(lái)輔助判斷[4].

　　考慮線性規(guī)劃的標(biāo)準(zhǔn)形式 max Z = cx s. t. Ax = b x ≥ 0 ( 2) 其中，c ∈ R1 ×n ，x ∈ Rn ，A ∈ Rm×n ，b ∈ Rm，并且 r( A) = m. 單純形法是求解( 2) 的最有效方法之一[1 -2].單純形乘子是其矩陣描述中的一個(gè)重要的參數(shù)，其定義如下: 假設(shè) B 是線性規(guī)劃( 2) 的一個(gè)可行基，不妨假設(shè) B 是 A 的前 m 列，將 A 寫成分塊矩陣 A = [B，N]，根據(jù) A 的分塊結(jié)構(gòu)將 c 寫成分塊形式 c = [cB， cN]，于是得單純形乘子的定義 π = cB B-1 . 單純形乘子的意義在于，( a) 簡(jiǎn)化單純形的矩陣描述，如非基變量的檢驗(yàn)數(shù) λN = cN - πN，目標(biāo)函數(shù) Z = πb; ( b) 如果問(wèn)題( 2) 是由生產(chǎn)計(jì)劃問(wèn)題添加松弛變量得到的，則當(dāng) B 為最優(yōu)基時(shí)，π = cB B-1 表示原材料的影子價(jià)格.

　　2 拉格朗日乘子與單純形乘子關(guān)系

　　由于線性規(guī)劃( 2) 中含有不等式約束 x ≥ 0，拉格朗日乘子法不能直接用來(lái)求解( 2) .下面我們引入約束 x = y°y = [y 2 1，y 2 2，…，y 2 n]T ，其中 ° 表示 Hadamard 乘積. 于是問(wèn)題( 2) 可以轉(zhuǎn)化成 max Z = cx s. t. Ax = b x = y°y ( 3) 注 2. 1: 將問(wèn)題( 2) 轉(zhuǎn)化成問(wèn)題( 1) 的方法不唯一. 基于指數(shù)函數(shù)的 x = [e y1，e y2，…，e yn ]T 或基于雙曲余弦函數(shù)的 x = e y1 + e -y1 2 - 1， e y2 + e -y2 2 - 1，…， e yn + e -yn 2 [ ] - 1 T 也可以將不等式約束轉(zhuǎn)化成等式約束. 實(shí)際上任何定義域是實(shí)數(shù)集，值域是非負(fù)集的函數(shù)都可以將不等式約束轉(zhuǎn)化成等式約束.

　　定理 2. 1 假設(shè) B 是線性規(guī)劃( 2) 的非退化最優(yōu)基，則利用拉格朗日乘子法求解問(wèn)題( 2) 的等價(jià)問(wèn)題( 3) 時(shí)，最優(yōu)基 B 對(duì)應(yīng)最優(yōu)解的拉格朗日乘子等于 B 對(duì)應(yīng)的單純形乘子 π = cB B-1 .

　　證明 利用拉格朗日乘子法求解問(wèn)題( 3) . 首先構(gòu)造增廣的拉格朗日函數(shù) L( x，y，λ，μ) = cx - λ( Ax - b) - μ( x - y°y) 其中，λ ∈ R1 ×m，μ ∈ R1 ×n 是對(duì)應(yīng)于兩個(gè)等式約束的拉格朗日乘子. 然后求解方程組 ·不妨假設(shè) B 是 A 的前 m 列，按照第二節(jié)的分塊方式，將 y，μ 寫成分塊形式 y = [yT B，yT N]T ，μ = [μT B， μT N]T . 根據(jù)( 4) 的第4 個(gè)等式得 xB = yB °yB，于是結(jié)合 xB ≠0，得 yB ≠0. 再結(jié)合( 4) 的第2 個(gè)等式得 μB = 0. 整理( 4) 的第 1 個(gè)等式得

　　不妨假設(shè) B 是 A 的前 m 列，按照第二節(jié)的分塊方式，將 y，μ 寫成分塊形式 y = [yT B，yT N]T ，μ = [μT B， μT N]T . 根據(jù)( 4) 的第4 個(gè)等式得 xB = yB °yB，于是結(jié)合 xB ≠0，得 yB ≠0. 再結(jié)合( 4) 的第2 個(gè)等式得 μB = 0. 整理( 4) 的第 1 個(gè)等式得[cB，cN]- λ[B，N]- [μB，μN] = 0 于是，得 cB - λB - μB = 0 cN - λN - μN = { 0 . 將 μB = 0 代入第 1 個(gè)等式得 λ = cB B-1 = π. 證畢定理2. 2 假設(shè) B 是線性規(guī)劃( 2) 的退化最優(yōu)基，x 是相應(yīng)的最優(yōu)解，則利用拉格朗日乘子法求解問(wèn)題( 2) 的等價(jià)問(wèn)題( 3) 時(shí)，最優(yōu)基 B 對(duì)應(yīng)的單純形乘子 π = cB B-1 可以作為與 x 對(duì)應(yīng)的拉格朗日乘子.證明 只需要驗(yàn)證 π = cB B-1 滿足方程組( 4) . 顯然只需要取 μ = 0 即可. 證畢

　　3 數(shù)值實(shí)驗(yàn)

　　例 3. 1( 非退化情況) 考慮線性規(guī)劃[3] max Z = 300x1 + 400x2 s. t. 2x1 + x2 ≤ 40 x1 + 1. 5x2 ≤ 30 x1，x2 ≥ 0 利用拉格朗日乘子法求得 4 個(gè)可能的最值點(diǎn)，即可行域的 4 個(gè)頂點(diǎn): X1 = [0，0]T ，X2 = [20，0]T ，X3 = [0，20]T ，X4 = [15，10]T 其中，最優(yōu)解是 X4，最優(yōu)基是 B = [P1，P2]，拉格朗日乘子是 λ = [25，250]. 另一方面最優(yōu)基 B 對(duì)應(yīng)的單純形乘子 π = cB B-1 = [25，250]. 于是 λ = π.例 3. 2( 退化情況) 考慮線性規(guī)劃[3] min Z = x1 + 2x2 + x3 s. t. x1 - 2x2 + 4x3 = 4 4x1 - 9x2 + 14x3 = 16 x1，x2，x3 ≥ 0 利用拉格朗日乘子法求得1 個(gè)可能的最值點(diǎn): X = [4，0，0]T . 對(duì)應(yīng)的拉格朗日乘子是 λ = [5 - 2a，a /2 - 3 /2]T ，其中 a ∈ R 是自由參數(shù). 而該線性規(guī)劃有唯一的最優(yōu)解 X = [4，0，0]T . 顯然該最優(yōu)解是退化的基可行解，其對(duì)應(yīng)的基有兩個(gè)，一個(gè)是 B1 = [P1，P2]，另一個(gè)是 B2 = [P1，P3]. 經(jīng)簡(jiǎn)單計(jì)算，兩個(gè)基對(duì)應(yīng)的單純形乘子分別是 π1 = cB1 B-1 1 = [- 17，4]與 π2 = cB2 B-1 2 = [5，- 1. 5]. 當(dāng)拉格朗日乘子 λ = [5 - 2a，a /2 - 3 /2]T 中的 a = 11 或 0 時(shí)分別得到上面的兩個(gè)單純形乘子.