====== 第八章 不等式约束优化 ======

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

不等式约束优化问题比等式约束问题更复杂，因为需要判断哪些约束在最优解处是起作用的（active）。本章介绍不等式约束优化的KKT条件、约束规范（Constraint Qualifications）以及最优性条件的几何解释。

===== 8.1 不等式约束问题的一般形式 =====

**定义 8.1**（不等式约束优化问题）

$$\begin{aligned}
\min_{\mathbf{x}} \quad & f(\mathbf{x}) \\
\text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, 2, \ldots, m
\end{aligned}$$

记 $\mathbf{g}(\mathbf{x}) = (g_1(\mathbf{x}), \ldots, g_m(\mathbf{x}))^T$。

===== 8.2 起作用约束与指标集 =====

**定义 8.2**（起作用约束/Active Constraint）

对于可行点 $\mathbf{x}$，若 $g_i(\mathbf{x}) = 0$，则称约束 $g_i$ 在 $\mathbf{x}$ 处**起作用**（active）；若 $g_i(\mathbf{x}) < 0$，则称约束**不起作用**（inactive）。

**定义 8.3**（起作用约束指标集）

$$\mathcal{A}(\mathbf{x}) = \{i \mid g_i(\mathbf{x}) = 0\}$$

===== 8.3 KKT条件 =====

==== 8.3.1 拉格朗日函数 ====

**定义 8.4**

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}) = f(\mathbf{x}) + \sum_{i=1}^m \mu_i g_i(\mathbf{x}) = f(\mathbf{x}) + \boldsymbol{\mu}^T \mathbf{g}(\mathbf{x})$$

其中 $\mu_i \geq 0$ 是不等式约束的拉格朗日乘子。

==== 8.3.2 KKT一阶必要条件 ====

**定理 8.1**（KKT条件，Karush-Kuhn-Tucker，1939/1951）

设：
1. $f$ 和 $g_i$ 在 $\mathbf{x}^*$ 的邻域内连续可微
2. $\mathbf{x}^*$ 是局部最优解
3. 某约束规范条件成立（如LICQ）

则存在 $\boldsymbol{\mu}^* \in \mathbb{R}^m$ 使得：

**平稳性**：$\nabla f(\mathbf{x}^*) + \sum_{i=1}^m \mu_i^* \nabla g_i(\mathbf{x}^*) = \mathbf{0}$

**原始可行性**：$g_i(\mathbf{x}^*) \leq 0$，$i = 1, \ldots, m$

**对偶可行性**：$\mu_i^* \geq 0$，$i = 1, \ldots, m$

**互补松弛性**：$\mu_i^* g_i(\mathbf{x}^*) = 0$，$i = 1, \ldots, m$

==== 8.3.3 KKT条件的解释 ====

**互补松弛性**的含义：
  - 若 $g_i(\mathbf{x}^*) < 0$（约束不起作用），则 $\mu_i^* = 0$
  - 若 $\mu_i^* > 0$，则 $g_i(\mathbf{x}^*) = 0$（约束起作用）

即不起作用的约束对应的乘子必为零。

===== 8.4 约束规范 =====

约束规范保证KKT条件的必要性。

**定义 8.5**（LICQ - Linear Independence CQ）

在 $\mathbf{x}^*$ 处，起作用约束的梯度线性无关：
$$\{\nabla g_i(\mathbf{x}^*) \mid i \in \mathcal{A}(\mathbf{x}^*)\} \text{ 线性无关}$$

**定义 8.6**（Slater条件）

对于凸优化问题，若存在严格可行点：
$$\exists \mathbf{x}: g_i(\mathbf{x}) < 0, \quad i = 1, \ldots, m$$

则Slater条件成立。

**定理 8.2**

对于凸优化问题，Slater条件保证KKT条件是充分必要的。

===== 8.5 一般约束优化问题 =====

==== 8.5.1 问题形式 ====

$$\begin{aligned}
\min \quad & f(\mathbf{x}) \\
\text{s.t.} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \\
& h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, l
\end{aligned}$$

==== 8.5.2 完整的KKT条件 ====

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \mu_i g_i(\mathbf{x}) + \sum_{j=1}^l \lambda_j h_j(\mathbf{x})$$

**KKT条件**：
1. $\nabla_{\mathbf{x}} \mathcal{L} = \mathbf{0}$
2. $g_i(\mathbf{x}^*) \leq 0$，$h_j(\mathbf{x}^*) = 0$
3. $\mu_i^* \geq 0$
4. $\mu_i^* g_i(\mathbf{x}^*) = 0$

===== 8.6 例题详解 =====

**例 8.1**

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

**解**：

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

KKT条件：
$$\begin{cases}
2(x-2) + 2\mu x = 0 \\
2(y-1) + 2\mu y = 0 \\
x^2 + y^2 \leq 1 \\
\mu \geq 0 \\
\mu(x^2 + y^2 - 1) = 0
\end{cases}$$

**情况1**：$\mu = 0$，则 $x = 2, y = 1$，但 $x^2 + y^2 = 5 > 1$，不可行。

**情况2**：$\mu > 0$，则 $x^2 + y^2 = 1$。

由前两式：$x = \frac{2}{1+\mu}, y = \frac{1}{1+\mu}$

代入约束：$\frac{4}{(1+\mu)^2} + \frac{1}{(1+\mu)^2} = 1$

$(1+\mu)^2 = 5$，$\mu = \sqrt{5} - 1 > 0$ ✓

解得：$x^* = \frac{2}{\sqrt{5}}, y^* = \frac{1}{\sqrt{5}}$

===== 8.7 习题 =====

**理论题**

1. 解释互补松弛条件 $\mu_i g_i(\mathbf{x}) = 0$ 的几何意义。

2. 证明：对于凸优化问题，KKT条件是充分条件。

3. 比较LICQ和Slater条件的异同。

**计算题**

4. 用KKT条件求解：
   $$\min x^2 + y^2 \quad \text{s.t.} \quad x + y \geq 1$$

5. 求解：
   $$\min (x-1)^2 + y^2 \quad \text{s.t.} \quad x^2 + y^2 \leq 4, \quad x \geq 0$$

---

*本章完*