开山运筹

运筹学

拉格朗日

海瑟矩阵

库恩塔克KKT

拉格朗日乘数法（Lagrange multipliers）是一种用于求解带有约束条件的优化问题的方法。该方法适用于在某个约束条件下寻找函数的极值（最小值或最大值）。以下是拉格朗日乘数法求解最小值的一般步骤：

步骤

1. 定义目标函数和约束条件：
   • 假设我们要最小化目标函数 f(x,y)f(x,y)，并且有一个约束条件 g(x,y)=0g(x,y)=0。
2. 构造拉格朗日函数：
   • 引入拉格朗日乘数 λλ，构造拉格朗日函数：

L(x,y,λ)=f(x,y)+λg(x,y)L(x,y,λ)=f(x,y)+λg(x,y)

3. 求偏导数：
   • 对拉格朗日函数 LL 关于 xx、yy 和 λλ 分别求偏导数，并设置为零：

∂L∂x=0∂x∂L​=0

∂L∂y=0∂y∂L​=0

∂L∂λ=0∂λ∂L​=0

• 这将产生一个方程组。

4. 求解方程组：
   • 解这个方程组，找到 xx、yy 和 λλ 的值。
5. 验证极值：
   • 计算目标函数 f(x,y)f(x,y) 在找到的点的值，以确定是否为最小值。

示例

假设我们要最小化函数 f(x,y)=x2+y2f(x,y)=x2+y2，在约束条件 g(x,y)=x+y−1=0g(x,y)=x+y−1=0 下。

1. 定义目标函数和约束条件：
   • 目标函数： f(x,y)=x2+y2f(x,y)=x2+y2
   • 约束条件： g(x,y)=x+y−1=0g(x,y)=x+y−1=0
2. 构造拉格朗日函数：

L(x,y,λ)=x2+y2+λ(x+y−1)L(x,y,λ)=x2+y2+λ(x+y−1)

3. 求偏导数并设置为零：

∂L∂x=2x+λ=0(1)∂x∂L​=2x+λ=0(1)

∂L∂y=2y+λ=0(2)∂y∂L​=2y+λ=0(2)

∂L∂λ=x+y−1=0(3)∂λ∂L​=x+y−1=0(3)

4. 解方程组：
   • 从方程 (1) 和 (2) 中可以得到 λ=−2xλ=−2x 和 λ=−2yλ=−2y，因此有 −2x=−2y−2x=−2y 或 x=yx=y。
   • 将 x=yx=y 代入方程 (3)：

x+x−1=0  ⟹  2x−1=0  ⟹  x=12x+x−1=0⟹2x−1=0⟹x=21​

• 因此，y=12y=21​。

5. 验证极值：
   • 计算目标函数在这个点的值：

f(12,12)=(12)2+(12)2=14+14=12f(21​,21​)=(21​)2+(21​)2=41​+41​=21​

因此，在约束条件 x+y=1x+y=1 下，函数 f(x,y)=x2+y2f(x,y)=x2+y2 的最小值为 1221​，发生在点 (12,12)(21​,21​)。

单纯型法3x_1​

对偶单纯形法