张叶安的小站

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 第七章 等式约束优化 ======

===== 本章导读 =====

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

===== 7.1 等式约束问题的一般形式 =====

**定义 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 拉格朗日乘子法 =====

==== 7.2.1 拉格朗日函数 ====

**定义 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.2.2 一阶必要条件 =====

**定理 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$$

==== 7.2.3 几何解释 ====

在最优解 $\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 二阶条件 =====

==== 7.3.1 切空间 ====

**定义 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.3.2 二阶必要条件 ====

**定理 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.3 二阶充分条件 ====

**定理 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}^*$ 是严格局部最优解。

===== 7.4 求解方法 =====

==== 7.4.1 直接求解KKT方程组 ====

求解非线性方程组：
$$\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.4.2 消元法（降维法） ====

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

===== 7.5 例题详解 =====

**例 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$

===== 7.6 习题 =====

**理论题**

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，验证与拉格朗日乘子法结果一致。

---

*本章完*