拉格朗日乘子法

flyfish

拉格朗日乘子法是一种用于求解带约束优化问题的强有力工具。它通过引入新的变量（拉格朗日乘子），将带约束的优化问题转换为无约束的优化问题，从而简化问题的求解过程。

假设我们有一个优化问题：
$$\min f(x)$$
$$\text{subject to }{g}_i(x)=0,i=1,\dots ,m$$其中，$f(x)$ 是目标函数，$g_i(x)$ 是等式约束条件。

“subject to”

在优化问题中，“subject to” 这部分用于引入约束条件。它表示在优化过程中，不仅需要找到使目标函数 $f(x)$ 达到最优值的 $x$ ，还需要确保这个 $x$ 满足特定的约束条件。约束条件可以是等式或不等式。
例如，考虑以下优化问题：
$\min f(x,y)=x^2+y^2$
$\text{subject to }x+y=1$这里，“subject to” 表示在优化目标函数 $x^2+y^2$ 的过程中，必须满足约束条件 $x+y=1$。

为了求解这个问题，我们引入拉格朗日乘子 ${\lambda }_i$，构造拉格朗日函数：$$L(x,\lambda )=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)$$
在这个函数中：

• $x$ 是原始问题的变量。

• ${\lambda }_i$ 是拉格朗日乘子，对应于每一个约束 $g_i(x)=0$。

• $L(x,\lambda )$ 是拉格朗日函数，它将目标函数 $f(x)$ 和约束条件 $g_i(x)$ 结合起来。
  通过对拉格朗日函数 $L(x,\lambda )$ 求偏导数并设为零，我们可以得到一组方程，这些方程包括目标函数的梯度和约束条件的梯度：
  $$\frac{\partial L}{\partial x}=\nabla f(x)+\sum _{i=1}^m{\lambda }_i\nabla g_i(x)=0$$
  $$\frac{\partial L}{\partial {\lambda }_i}=g_i(x)=0,i=1,\dots ,m$$解这些方程可以得到 $x$ 和 ${\lambda }_i$ 的值。

简单例子

假设我们有以下优化问题：
$$\min f(x,y)=x^2+y^2$$
$$\text{subject to }g(x,y)=x+y-1=0$$这个问题的目标是找到 $x$ 和 $y$ 的值，使得 $x^2+y^2$ 最小，并且满足约束条件 $x+y=1$。
我们构造拉格朗日函数：
$$L(x,y,\lambda )=x^2+y^2+\lambda (x+y-1)$$
对拉格朗日函数求偏导数并设为零：
$$\frac{\partial L}{\partial x}=2x+\lambda =0$$
$$\frac{\partial L}{\partial y}=2y+\lambda =0$$
$$\frac{\partial L}{\partial \lambda }=x+y-1=0$$
解这组方程，我们得到：
$$2x+\lambda =0$$
$$2y+\lambda =0$$
$x+y-1=0$从前两个方程，我们得到 $x=y$。将其代入第三个方程：$x+x-1=0$
$$2x=1$$
$$x=\frac{1}{2},y=\frac{1}{2}$$

代码解释

目标函数的等高线图和约束条件的直线

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize

# 目标函数
def objective(vars):
    x, y = vars
    return x**2 + y**2

# 约束条件
def constraint(vars):
    x, y = vars
    return x + y - 1

# 定义等高线图的网格范围
x = np.linspace(-1, 2, 400)
y = np.linspace(-1, 2, 400)
X, Y = np.meshgrid(x, y)
Z = X**2 + Y**2

# 绘制等高线图
plt.contour(X, Y, Z, levels=20, cmap='viridis')
plt.colorbar()

# 绘制约束条件的直线
x_line = np.linspace(-1, 2, 400)
y_line = 1 - x_line
plt.plot(x_line, y_line, 'r--', label='x + y = 1 (constraint)')

# 求解优化问题
x0 = [0, 0]
con = {'type': 'eq', 'fun': constraint}
solution = minimize(objective, x0, constraints=con)
x_opt, y_opt = solution.x

# 绘制最优解
plt.scatter([x_opt], [y_opt], color='red', zorder=5)
plt.text(x_opt, y_opt, f'Optimal: ({x_opt:.2f}, {y_opt:.2f})', color='red')

# 设置图例和标题
plt.legend()
plt.xlabel('x')
plt.ylabel('y')
plt.title('Optimization with Constraint: Minimize $x^2 + y^2$ subject to $x + y = 1$')
plt.grid(True)

plt.show()

几何解释

从几何上看，拉格朗日乘子法利用了目标函数的等高线与约束条件的曲线（或曲面）之间的关系。在最优解处，目标函数的等高线（或等值面）与约束条件的曲线（或曲面）相切。也就是说，在最优解处，目标函数的梯度 $\nabla f(x)$ 与约束条件的梯度 $\nabla g_i(x)$ 之间是线性相关的。这意味着存在一组拉格朗日乘子 ${\lambda }_i$，使得：$$\nabla f(x)+\sum _{i=1}^m{\lambda }_i\nabla g_i(x)=0$$