拉格朗日乘子与单纯形乘子关系探讨

　　[摘 要] 拉格朗日乘子法是求解含等式约束极值问题的有效方法，其核心思想是通过引入拉格朗日乘子将条件极值问题转化为无条件极值问题，而单纯形方法是求解带不等式约束的线性规划问题的经典方法，其矩阵描述中含有单纯形乘子参数，即影子价格. 在线性规划的基本可行解非退化的假设下，证明了单纯形乘子就是拉格朗日乘子.通过数值实验验证了理论分析，特别地，通过实际例子说明了当最优解是退化基可行解时，拉格朗日乘子可能包含了单纯形乘子.

　　孙敏， 枣庄学院学报 发表时间：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 时分别得到上面的两个单纯形乘子.