====== 第九章 罚函数法 ======

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

罚函数法（Penalty Methods）是将约束优化问题转化为一系列无约束优化问题来求解的方法。通过在目标函数中添加惩罚项，使违反约束的解受到"惩罚"，从而引导迭代点向可行域靠近。本章介绍外点罚函数法、内点罚函数法和乘子法。

===== 9.1 外点罚函数法 =====

==== 9.1.1 基本思想 ====

外点罚函数法（Exterior Penalty Method）允许迭代点在可行域外，但随着惩罚因子的增大，违反约束的代价越来越大，迭代点被"推向"可行域。

==== 9.1.2 惩罚函数构造 ====

对于问题：
$$\min f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \leq 0, \quad h_j(\mathbf{x}) = 0$$

定义惩罚函数：
$$P(\mathbf{x}, \sigma) = f(\mathbf{x}) + \sigma \left[\sum_{i=1}^m [\max(0, g_i(\mathbf{x}))]^2 + \sum_{j=1}^l h_j^2(\mathbf{x})\right]$$

其中 $\sigma > 0$ 是惩罚因子。

==== 9.1.3 算法步骤 ====

**算法 9.1**（外点罚函数法）

  1. 选择初始点 $\mathbf{x}_0$，初始惩罚因子 $\sigma_0 > 0$，放大系数 $c > 1$，精度 $\varepsilon > 0$
  2. **for** $k = 0, 1, 2, \ldots$ **do**
     - 求解 $\mathbf{x}_{k+1} = \arg\min_{\mathbf{x}} P(\mathbf{x}, \sigma_k)$，以 $\mathbf{x}_k$ 为初始点
     - **if** $\sigma_k \cdot \left[\sum \max(0, g_i)^2 + \sum h_j^2\right] < \varepsilon$ **then** **break**
     - $\sigma_{k+1} = c \cdot \sigma_k$
  3. **return** $\mathbf{x}_{k+1}$

==== 9.1.4 收敛性 ====

**定理 9.1**

设 $f, g_i, h_j$ 连续，且约束优化问题的最优解存在。则外点罚函数法产生的序列满足：
1. $P(\mathbf{x}_k, \sigma_k) \leq P(\mathbf{x}_{k+1}, \sigma_{k+1})$
2. $\sum [\max(0, g_i)^2 + h_j^2]$ 关于 $k$ 单调递减趋于0
3. $f(\mathbf{x}_k) \rightarrow f(\mathbf{x}^*)$

===== 9.2 内点罚函数法 =====

==== 9.2.1 基本思想 ====

内点罚函数法（Interior Penalty Method/Barrier Method）要求迭代点始终保持在可行域内部，通过在可行域边界设置"障碍"来阻止迭代点越界。

==== 9.2.2 障碍函数 ====

常用对数障碍函数：
$$B(\mathbf{x}, \mu) = f(\mathbf{x}) - \mu \sum_{i=1}^m \ln(-g_i(\mathbf{x}))$$

或倒数障碍函数：
$$B(\mathbf{x}, \mu) = f(\mathbf{x}) + \mu \sum_{i=1}^m \frac{-1}{g_i(\mathbf{x})}$$

其中 $\mu > 0$ 是障碍参数。

==== 9.2.3 算法步骤 ====

**算法 9.2**（内点罚函数法）

  1. 选择严格可行初始点 $\mathbf{x}_0$（$g_i(\mathbf{x}_0) < 0$），初始参数 $\mu_0 > 0$，缩减系数 $\theta \in (0, 1)$
  2. **for** $k = 0, 1, 2, \ldots$ **do**
     - 求解 $\mathbf{x}_{k+1} = \arg\min_{\mathbf{x}} B(\mathbf{x}, \mu_k)$，以 $\mathbf{x}_k$ 为初始点
     - **if** $\mu_k \cdot m < \varepsilon$ **then** **break**
     - $\mu_{k+1} = \theta \cdot \mu_k$
  3. **return** $\mathbf{x}_{k+1}$

==== 9.2.4 收敛性 ====

**定理 9.2**

设 $f, g_i$ 连续，可行域内部非空且有界，最优解存在。则内点罚函数法产生的序列满足：
$$\lim_{k \rightarrow \infty} f(\mathbf{x}_k) = f(\mathbf{x}^*)$$

===== 9.3 乘子法（Augmented Lagrangian） =====

==== 9.3.1 基本思想 ====

乘子法（Augmented Lagrangian Method / 增广拉格朗日法）结合了拉格朗日函数和罚函数的优点，通过更新乘子来避免惩罚因子趋于无穷大。

==== 9.3.2 增广拉格朗日函数 ====

对于等式约束问题：
$$\mathcal{L}_A(\mathbf{x}, \boldsymbol{\lambda}, \sigma) = f(\mathbf{x}) + \boldsymbol{\lambda}^T \mathbf{h}(\mathbf{x}) + \frac{\sigma}{2} \|\mathbf{h}(\mathbf{x})\|^2$$

==== 9.3.3 算法步骤 ====

**算法 9.3**（乘子法——等式约束）

  1. 选择初始点 $\mathbf{x}_0$，初始乘子 $\boldsymbol{\lambda}_0$，初始惩罚因子 $\sigma_0$
  2. **for** $k = 0, 1, 2, \ldots$ **do**
     - 求解 $\mathbf{x}_{k+1} = \arg\min_{\mathbf{x}} \mathcal{L}_A(\mathbf{x}, \boldsymbol{\lambda}_k, \sigma_k)$
     - 更新乘子：$\boldsymbol{\lambda}_{k+1} = \boldsymbol{\lambda}_k + \sigma_k \mathbf{h}(\mathbf{x}_{k+1})$
     - 适当调整 $\sigma_{k+1}$
  3. **return** $\mathbf{x}_{k+1}, \boldsymbol{\lambda}_{k+1}$

==== 9.3.4 收敛性 ====

**定理 9.3**

在适当条件下，乘子法产生的序列满足：
$$\boldsymbol{\lambda}_k \rightarrow \boldsymbol{\lambda}^* \quad \text{且} \quad \mathbf{x}_k \rightarrow \mathbf{x}^*$$

且不需要 $\sigma_k \rightarrow \infty$。

===== 9.4 方法比较 =====

| 方法 | 可行点 | 惩罚因子 | 优点 | 缺点 |
|:---:|:---:|:---:|:---:|:---:|
| 外点法 | 不一定 | $\rightarrow \infty$ | 实现简单 | 病态问题 |
| 内点法 | 始终可行 | $\rightarrow 0$ | 始终可行 | 需要内点初始 |
| 乘子法 | 不一定 | 有限 | 收敛快 | 需要更新乘子 |

===== 9.5 习题 =====

**理论题**

1. 证明外点罚函数法中 $P(\mathbf{x}_k, \sigma_k) \leq f(\mathbf{x}^*)$。

2. 分析当 $\sigma \rightarrow \infty$ 时，Hesse矩阵的条件数变化。

3. 推导乘子法中乘子更新公式的合理性。

**计算题**

4. 用外点罚函数法求解：
   $$\min x^2 + y^2 \quad \text{s.t.} \quad x + y = 1$$
   取 $\sigma_0 = 1, c = 10$，进行2次迭代。

5. 用内点罚函数法求解：
   $$\min x \quad \text{s.t.} \quad x \geq 1$$

---

*本章完*