罚函数法（Penalty Methods）是将约束优化问题转化为一系列无约束优化问题来求解的方法。通过在目标函数中添加惩罚项，使违反约束的解受到“惩罚”，从而引导迭代点向可行域靠近。本章介绍外点罚函数法、内点罚函数法和乘子法。
外点罚函数法（Exterior Penalty Method）允许迭代点在可行域外，但随着惩罚因子的增大，违反约束的代价越来越大，迭代点被“推向”可行域。
对于问题： $$\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（外点罚函数法）
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
设 $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}^*)$
内点罚函数法（Interior Penalty Method/Barrier Method）要求迭代点始终保持在可行域内部，通过在可行域边界设置“障碍”来阻止迭代点越界。
常用对数障碍函数： $$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（内点罚函数法）
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
设 $f, g_i$ 连续，可行域内部非空且有界，最优解存在。则内点罚函数法产生的序列满足： $$\lim_{k \rightarrow \infty} f(\mathbf{x}_k) = f(\mathbf{x}^*)$$
乘子法（Augmented Lagrangian Method / 增广拉格朗日法）结合了拉格朗日函数和罚函数的优点，通过更新乘子来避免惩罚因子趋于无穷大。
对于等式约束问题： $$\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（乘子法——等式约束）
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
在适当条件下，乘子法产生的序列满足： $$\boldsymbol{\lambda}_k \rightarrow \boldsymbol{\lambda}^* \quad \text{且} \quad \mathbf{x}_k \rightarrow \mathbf{x}^*$$
且不需要 $\sigma_k \rightarrow \infty$。
| 方法 | 可行点 | 惩罚因子 | 优点 | 缺点 |
| :—: | :—: | :—: | :—: | :—: |
| 外点法 | 不一定 | $\rightarrow \infty$ | 实现简单 | 病态问题 |
| 内点法 | 始终可行 | $\rightarrow 0$ | 始终可行 | 需要内点初始 |
| 乘子法 | 不一定 | 有限 | 收敛快 | 需要更新乘子 |
理论题
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$$
—
*本章完*