等式约束优化问题是最基本的约束优化问题形式。本章介绍求解等式约束问题的经典方法——拉格朗日乘子法，推导一阶必要条件（KKT条件的特例），并讨论二阶充分条件。

定义 7.1（等式约束优化问题）

等式约束优化问题的标准形式为： $$\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x})
\text{s.t.} \quad & h_j(\mathbf{x}) = 0, \quad j = 1, 2, \ldots, l \end{aligned}$$

其中 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是目标函数，$h_j: \mathbb{R}^n \rightarrow \mathbb{R}$ 是约束函数。

记约束向量 $\mathbf{h}(\mathbf{x}) = (h_1(\mathbf{x}), h_2(\mathbf{x}), \ldots, h_l(\mathbf{x}))^T$。

可行域：$\mathcal{F} = \{\mathbf{x} \in \mathbb{R}^n \mid h_j(\mathbf{x}) = 0, j = 1, \ldots, l\}$

定义 7.2（拉格朗日函数）

引入拉格朗日乘子 $\lambda_j \in \mathbb{R}$，定义拉格朗日函数： $$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^l \lambda_j h_j(\mathbf{x}) = f(\mathbf{x}) + \boldsymbol{\lambda}^T \mathbf{h}(\mathbf{x})$$

其中 $\boldsymbol{\lambda} = (\lambda_1, \ldots, \lambda_l)^T$。

定理 7.1（拉格朗日乘子定理/一阶必要条件）

设： 1. $f$ 和 $h_j$ 在 $\mathbf{x}^*$ 的邻域内连续可微 2. $\mathbf{x}^*$ 是局部最优解 3. 约束梯度 $\nabla h_1(\mathbf{x}^*), \ldots, \nabla h_l(\mathbf{x}^*)$ 线性无关（LICQ条件）

则存在拉格朗日乘子 $\boldsymbol{\lambda}^* \in \mathbb{R}^l$ 使得： $$\nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) = \nabla f(\mathbf{x}^*) + \sum_{j=1}^l \lambda_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}$$

即： $$\nabla f(\mathbf{x}^*) + \nabla \mathbf{h}(\mathbf{x}^*) \boldsymbol{\lambda}^* = \mathbf{0}$$

同时满足约束条件： $$h_j(\mathbf{x}^*) = 0, \quad j = 1, \ldots, l$$

在最优解 $\mathbf{x}^*$ 处，目标函数的梯度可以表示为约束函数梯度的线性组合： $$\nabla f(\mathbf{x}^*) = -\sum_{j=1}^l \lambda_j^* \nabla h_j(\mathbf{x}^*)$$

这意味着 $\nabla f(\mathbf{x}^*)$ 位于约束函数梯度张成的空间中，等价于 $\nabla f(\mathbf{x}^*)$ 与可行域在 $\mathbf{x}^*$ 处的切空间正交。

定义 7.3（切空间）

在可行点 $\mathbf{x}$ 处的切空间定义为： $$\mathcal{T}(\mathbf{x}) = \{\mathbf{d} \in \mathbb{R}^n \mid \nabla h_j(\mathbf{x})^T \mathbf{d} = 0, j = 1, \ldots, l\}$$

即与所有约束梯度正交的方向集合。

定理 7.2（二阶必要条件）

设： 1. $f$ 和 $h_j$ 在 $\mathbf{x}^*$ 处二阶连续可微 2. $\mathbf{x}^*$ 是局部最优解 3. LICQ条件成立

则对满足一阶条件的 $(\mathbf{x}^*, \boldsymbol{\lambda}^*)$，有： $$\mathbf{d}^T \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) \mathbf{d} \geq 0, \quad \forall \mathbf{d} \in \mathcal{T}(\mathbf{x}^*)$$

即拉格朗日函数的Hesse矩阵在切空间上半正定。

定理 7.3（二阶充分条件）

设： 1. $f$ 和 $h_j$ 在 $\mathbf{x}^*$ 处二阶连续可微 2. $(\mathbf{x}^*, \boldsymbol{\lambda}^*)$ 满足一阶必要条件 3. $$\mathbf{d}^T \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\lambda}^*) \mathbf{d} > 0, \quad \forall \mathbf{d} \in \mathcal{T}(\mathbf{x}^*) \setminus \{\mathbf{0}\}$$

则 $\mathbf{x}^*$ 是严格局部最优解。

求解非线性方程组： $$\begin{cases} \nabla f(\mathbf{x}) + \nabla \mathbf{h}(\mathbf{x}) \boldsymbol{\lambda} = \mathbf{0}
\mathbf{h}(\mathbf{x}) = \mathbf{0} \end{cases}$$

可用Newton法求解： $$\begin{bmatrix} \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L} & \nabla \mathbf{h}
\nabla \mathbf{h}^T & \mathbf{0} \end{bmatrix} \begin{bmatrix} \Delta \mathbf{x}
\Delta \boldsymbol{\lambda} \end{bmatrix} = -\begin{bmatrix} \nabla_{\mathbf{x}} \mathcal{L}
\mathbf{h} \end{bmatrix}$$

若约束函数简单，可从中解出某些变量，代入目标函数，转化为无约束问题。

例 7.1

求解： $$\begin{aligned} \min \quad & f(x, y) = x^2 + y^2
\text{s.t.} \quad & x + y - 1 = 0 \end{aligned}$$

解：

拉格朗日函数：$\mathcal{L}(x, y, \lambda) = x^2 + y^2 + \lambda(x + y - 1)$

KKT条件： $$\begin{cases} 2x + \lambda = 0
2y + \lambda = 0
x + y = 1 \end{cases}$$

由前两式：$x = y = -\frac{\lambda}{2}$

代入第三式：$-\lambda = 1$，即 $\lambda = -1$

解得：$x^* = y^* = \frac{1}{2}$，$f^* = \frac{1}{2}$

验证二阶条件：$\nabla^2 \mathcal{L} = \begin{bmatrix} 2 & 0
0 & 2 \end{bmatrix}$，切空间 $\mathbf{d} = (1, -1)^T$，$\mathbf{d}^T \nabla^2 \mathcal{L} \mathbf{d} = 4 > 0$。严格最优。

例 7.2

求解： $$\begin{aligned} \min \quad & f(x, y, z) = x^2 + 2y^2 + z^2
\text{s.t.} \quad & x + y + z = 3
& x - y = 0 \end{aligned}$$

解：

拉格朗日函数：$\mathcal{L} = x^2 + 2y^2 + z^2 + \lambda_1(x+y+z-3) + \lambda_2(x-y)$

KKT条件： $$\begin{cases} 2x + \lambda_1 + \lambda_2 = 0
4y + \lambda_1 - \lambda_2 = 0
2z + \lambda_1 = 0
x + y + z = 3
x - y = 0 \end{cases}$$

由 $x = y$，解得：$x = y = 1, z = 1, \lambda_1 = -2, \lambda_2 = 0$

理论题

1. 证明拉格朗日乘子定理的一阶必要条件。

2. 解释LICQ条件的几何意义。

3. 推导等式约束优化问题的KKT方程组的Newton迭代格式。

计算题

4. 用拉格朗日乘子法求解：

 $$\min x^2 + 2y^2 \quad \text{s.t.} \quad x + 2y = 2$$

5. 求解：

 $$\min (x-1)^2 + (y-2)^2 + (z-3)^2 \quad \text{s.t.} \quad x + y + z = 1, \quad 2x - y = 0$$

应用题

6. 用消元法求解例7.1，验证与拉格朗日乘子法结果一致。

—

*本章完*