拉格朗日乘子法

1. 简介

拉格朗日乘子法是一种寻找多元函数在其变量受到一个或多个条件的约束时的局部极值的方法。这种方法可以将一个有 nn 个变量与 kk 个约束条件的最优化问题转换为一个解有 n+kn+k 个变量的方程组的解的问题。

2. 方法

2.1 拉格朗日乘法定理

设 f:Rn→Rf: \mathbb{R}^n \rightarrow \mathbb{R} 为目标函数，g:Rn→Rcg: \mathbb{R}^n \rightarrow \mathbb{R}^c 为约束函数，二者有连续的一阶导数。令 x∗x_* 为下列问题的一个最优解，使得 rank(Dg(x∗))=c<n\mathrm{rank}(D g(x_*)) = c < n，其中 Dg(x∗)D g(x_*) 表示偏导矩阵 [Dg(x∗)]j,k=[∂gj∂xk][Dg(x_*)]_{j, k} = \left[\frac{\partial g_j}{\partial x_k}\right]：

maximizef(x)subject tog(x)=0\begin{aligned} \mathrm{maximize} &\quad f(x) \\ \mathrm{subject\ to} &\quad g(x) = 0 \end{aligned}

则一定存在一个唯一的拉格朗日乘子 λ∗∈Rc\lambda_* \in \mathbb{R}^c，使得 Df(x∗)=λ∗TDg(x∗)Df(x_*) = \lambda_*^T D g(x_*)。

2.2 拉格朗日乘子法

为了找到函数 f(x)f(x) 在约束条件 g(x)=0g(x) = 0 下的极值，可以构造以下的拉格朗日函数：

L(x,λ)=f(x)+λ⋅g(x)L(x, \lambda) = f(x) + \lambda \cdot g(x)

则拉格朗日函数的鞍点中，一定包含原始问题的极值点。所以我们需要求出 L(x,λ)L(x, \lambda) 的所有鞍点，也即需满足：

{∂L(x,λ)∂x=0∂L(x,λ)∂λ=0\begin{cases} \frac{\partial L(x, \lambda)}{\partial x} = 0 \\ \frac{\partial L(x, \lambda)}{\partial \lambda} = 0 \end{cases}

2.3 拉格朗日对偶性

在约束最优化问题时，常常会利用拉格朗日对偶性将原始问题转换为对偶问题，通过解对偶问题而得到原始问题的解。

原始问题

假设 f(x),ci(x),hj(x)f(x), c_i(x), h_j(x) 是定义在 Rn\mathbb{R}^n 上的连续可微函数。考虑约束以下最优问题

min⁡x∈Rnf(x)s.t.ci(x)≤0,i=1,2,⋯ ,khj(x)=0,j=1,2,⋯ ,l\begin{aligned} \min_{x \in \mathbb{R}^n} &\quad f(x) \\ \mathrm{s.t.} &\quad c_i(x) \leq 0, i = 1, 2, \cdots, k \\ &\quad h_j(x) = 0, j = 1, 2, \cdots, l \end{aligned}

称此约束最优化问题为原始最优化问题或原始问题。

首先引入广义拉格朗日函数：

L(x,α,β)=f(x)+∑i=1kαici(x)+∑j=1lβjhj(x)L(x, \alpha, \beta) = f(x) + \sum_{i=1}^k \alpha_i c_i(x) + \sum_{j=1}^l \beta_j h_j(x)

其中，x∈Rnx \in \mathbb{R}^n，αi,βj\alpha_i, \beta_j 是拉格朗日乘子，αi≥0\alpha_i \geq 0。考虑 xx 的函数：

θP(x)=max⁡α,β:αi≥0L(x,α,β)\begin{aligned} \theta_P(x) = \max_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta) \end{aligned}

则有

θP(x)={f(x)x 满足原始问题约束 +∞ 其他 \theta_P(x) = \begin{cases} f(x) & x\text{ 满足原始问题约束 } \\ +\infty & \text{ 其他 } \end{cases}

因此，以下极小化问题

min⁡xθP(x)=min⁡xmax⁡α,β:αi≥0L(x,α,β)\min_{x} \theta_P(x) = \min_{x} \max_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta)

其与原始最优化问题等价。问题 min⁡xmax⁡α,β:αi≥0L(x,α,β)\min_{x} \max_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta) 称为广义拉格朗日函数的极小极大问题。定义原始问题的最优值：

p∗=min⁡xθP(x)p^* = \min_{x} \theta_P(x)

对偶问题

定义

θD(α,β)=min⁡xL(x,α,β)\theta_D(\alpha, \beta) = \min_{x} L(x, \alpha, \beta)

再考虑极大化 θD(α,β)\theta_D (\alpha, \beta)，即：

max⁡α,β:αi≥0θD(α,β)=max⁡α,β:αi≥0min⁡xL(x,α,β)\max_{\alpha,\beta: \alpha_i \geq 0} \theta_D(\alpha, \beta) = \max_{\alpha,\beta: \alpha_i \geq 0} \min_{x} L(x, \alpha, \beta)

可以将上述广义拉格朗日函数的极大极小问题表示为约束最优化问题：

max⁡α,βθD(α,β)=min⁡xL(x,α,β)s.t.αi≥0,i=1,2,⋯ ,k\begin{aligned} \max_{\alpha,\beta} &\quad \theta_D(\alpha,\beta) = \min_{x} L(x, \alpha, \beta) \\ \mathrm{s.t.} &\quad \alpha_i \geq 0, i = 1, 2, \cdots, k \end{aligned}

称为原始问题的对偶问题。定义对偶问题的最优值：

d∗=max⁡α,β:αi≥0θD(α,β)d^* = \max_{\alpha,\beta:\alpha_i \geq 0} \theta_D(\alpha, \beta)

  • 定理一：若原始问题和对偶问题都有最优值，则

    d∗=max⁡α,β:αi≥0min⁡xL(x,α,β)≤min⁡xmax⁡α,β:αi≥0L(x,α,β)=p∗d^* = \max_{\alpha,\beta:\alpha_i \geq 0} \min_{x} L(x, \alpha, \beta) \leq \min_{x} \max_{\alpha,\beta:\alpha_i \geq 0} L(x, \alpha, \beta) = p^*

  • 定理二（KKT 条件）：对于原始问题和对偶问题，假设函数 f(x)f(x) 和 ci(x)c_i(x) 是凸函数，hj(x)h_j(x) 是仿射函数，并且不等式约束 ci(x)c_i(x) 是严格可行的，则 x∗x^* 和 α∗,β∗\alpha^*, \beta^* 分别是原始问题和对偶问题的解的充分必要条件是 x∗,α∗,β∗x^*, \alpha^*, \beta^* 满足下面的 KKT 条件：

    ∇xL(x∗,α∗,β∗)=0αi∗ci(x∗)=0,i=1,2,⋯ ,kci(x∗)≤0,i=1,2,⋯ ,kαi∗≥0,i=1,2,⋯ ,khj(x∗)=0,j=1,2,⋯ ,l\nabla_x L(x^*, \alpha^*, \beta^*) = 0 \\ \alpha_i^* c_i(x^*) = 0, i = 1, 2, \cdots, k \\ c_i(x^*) \leq 0, i = 1, 2, \cdots, k \\ \alpha_i^* \geq 0, i = 1, 2, \cdots, k \\ h_j(x^*) = 0, j = 1, 2, \cdots, l

附录

Technique Math Theory
Technique Math Theory

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！