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

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

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

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

　　0 引言

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

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

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

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

　　考慮等式約束的極值問題

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

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

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

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

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

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

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

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

　　3 數值實驗

　　例 3. 1( 非退化情況) 考慮線性規劃[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 其中，最優解是 X4，最優基是 B = [P1，P2]，拉格朗日乘子是 λ = [25，250]. 另一方面最優基 B 對應的單純形乘子 π = cB B-1 = [25，250]. 于是 λ = π.例 3. 2( 退化情況) 考慮線性規劃[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 是自由參數. 而該線性規劃有唯一的最優解 X = [4，0，0]T . 顯然該最優解是退化的基可行解，其對應的基有兩個，一個是 B1 = [P1，P2]，另一個是 B2 = [P1，P3]. 經簡單計算，兩個基對應的單純形乘子分別是 π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 時分別得到上面的兩個單純形乘子.