等式约束优化问题是最基本的约束优化问题形式。本章介绍求解等式约束问题的经典方法——拉格朗日乘子法，推导一阶必要条件（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，验证与拉格朗日乘子法结果一致。
—
*本章完*