拉格朗日乘子與單純形乘子關系探討

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

　　孫敏， 棗莊學院學報 發(fā)表時間：2021-09-01

　　[關鍵詞] 等式約束極值問題; 拉格朗日乘子; 一般約束極值問題; 單純形乘子

　　0 引言

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

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

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

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

　　考慮等式約束的極值問題

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

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

　　考慮線性規(guī)劃的標準形式 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].單純形乘子是其矩陣描述中的一個重要的參數(shù)，其定義如下: 假設 B 是線性規(guī)劃( 2) 的一個可行基，不妨假設 B 是 A 的前 m 列，將 A 寫成分塊矩陣 A = [B，N]，根據(jù) A 的分塊結(jié)構(gòu)將 c 寫成分塊形式 c = [cB， cN]，于是得單純形乘子的定義 π = cB B-1 . 單純形乘子的意義在于，( a) 簡化單純形的矩陣描述，如非基變量的檢驗數(shù) λN = cN - πN，目標函數(shù) Z = πb; ( b) 如果問題( 2) 是由生產(chǎn)計劃問題添加松弛變量得到的，則當 B 為最優(yōu)基時，π = cB B-1 表示原材料的影子價格.

　　2 拉格朗日乘子與單純形乘子關系

　　由于線性規(guī)劃( 2) 中含有不等式約束 x ≥ 0，拉格朗日乘子法不能直接用來求解( 2) .下面我們引入約束 x = y°y = [y 2 1，y 2 2，…，y 2 n]T ，其中 ° 表示 Hadamard 乘積. 于是問題( 2) 可以轉(zhuǎn)化成 max Z = cx s. t. Ax = b x = y°y ( 3) 注 2. 1: 將問題( 2) 轉(zhuǎ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ù)都可以將不等式約束轉(zhuǎn)化成等式約束.

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

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

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

　　3 數(shù)值實驗

　　例 3. 1( 非退化情況) 考慮線性規(guī)劃[3] max Z = 300x1 + 400x2 s. t. 2x1 + x2 ≤ 40 x1 + 1. 5x2 ≤ 30 x1，x2 ≥ 0 利用拉格朗日乘子法求得 4 個可能的最值點，即可行域的 4 個頂點: 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 對應的單純形乘子 π = 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 個可能的最值點: X = [4，0，0]T . 對應的拉格朗日乘子是 λ = [5 - 2a，a /2 - 3 /2]T ，其中 a ∈ R 是自由參數(shù). 而該線性規(guī)劃有唯一的最優(yōu)解 X = [4，0，0]T . 顯然該最優(yōu)解是退化的基可行解，其對應的基有兩個，一個是 B1 = [P1，P2]，另一個是 B2 = [P1，P3]. 經(jīng)簡單計算，兩個基對應的單純形乘子分別是 π1 = cB1 B-1 1 = [- 17，4]與 π2 = cB2 B-1 2 = [5，- 1. 5]. 當拉格朗日乘子 λ = [5 - 2a，a /2 - 3 /2]T 中的 a = 11 或 0 時分別得到上面的兩個單純形乘子.