罚函数是一类重要的最优化算法
处理有约束的优化问题时，一种常见的处理方法是: 将约束条件作为惩罚项加到目标函数中。"惩罚"是一个很形象的称呼，意思是优化过程迭代到约束条件之外时给与惩罚，或者说负反馈。例如，我们在处理最小化函数值\(f\)时，在f中增加一些项，这些项会使得迭代点在可行域之外时，增大函数f的值，这些项就起到了惩罚的作用
这些约束条件可以是等式，也可以是不等式，又或者是两者都有。
在处理等式约束时，常常使用外点罚函数法，意思是迭代点允许在可行域之外(其实非常自然，因为等式约束是一种"很严格"的约束，迭代不要限制地太紧了，不然都不好迭代优化);对于不等式约束，常使用内点罚函数法，意思是不让迭代点到可行域之外。内点法适用于只有不等式约束的问题。在对函数添加罚函数后，就将有约束的优化问题转换为了无约束优化问题。
外点罚函数法
等式约束外点罚函数法
考虑问题 \[ \min_x f(x) \quad x\in \mathbb{R^n}\\ s.t. \ \ c_i(x)=0 \ \ i \in \mathcal E \] 最自然的想法，把约束条件的平方作为罚函数，即
\[ P_E(x, \sigma)=f(x)+\frac{1}{2}\sigma \sum_i c_i^{2}(x) \] 其中第二项为惩罚项，sigma称为罚因子。这种方法称为等式约束的二次外点罚函数法。其迭代过程与收敛性的证明参考文在文的《最优化计算方法》P186
上面我们说，外点罚函数法常用于处理等式约束，但如果通过巧妙的设计，也可以用于不等式约束，例如对于如下问题
不等式约束外点罚函数法
\[ \min_x f(x) \quad x\in \mathbb{R^n}\\ s.t. \ \ c_i(x)\le0 \ \ i \in \mathcal I \] 将二次罚函数设定为如下样式
\[ \tilde c_i(x)=\max (x_i(x),0) \] 那么有
\[ P_I(x, \sigma)=f(x)+\frac{1}{2}\sigma \sum_i \tilde c_i^{2}(x) \] 可见，此时也允许迭代点在可行域之外迭代。值得注意的是，\(P_I\)仍然是可导函数，进而可以用梯度类算法求解。
同时含有等式约束与不等式约束的外点罚函数法
对于如下问题 \[ \min_x f(x) \quad x\in \mathbb{R^n}\\ s.t. \ \ c_i(x)\le0 \ \ \ i\in \mathcal I \\ \tilde c_i(x)= 0 \ \ \ i\in \mathcal E \]
把两个罚函数相加即可
\[ P(x, \sigma)=f(x)+\frac{1}{2}\sigma (\sum_i c_i^{2}(x) + \sum_i \tilde c_i^{2}(x)) \]
内点罚函数法
内点法使用于只有不等式约束的优化问题。其思想是: 为了使得迭代过程始终在可行域范围内，如果迭代点迭代到可行域的边界，那么给它一个极大的惩罚。这个惩罚函数的形状就像一睹墙，或者说示性函数。这个惩罚项可以用对数函数、倒数函数构造
例如对于如下问题:
\[ \min_x f(x) \quad x\in \mathbb{R^n}\\ s.t. \ \ c_i(x)\le0 \ \ i \in \mathcal I \] 保持迭代点含于可行域内部的方法是 定义障碍函数 \[ G(x, r)=f(x) 十 r B(x) \] 其中 \(\mathbf{B}(\mathbf{x})\) 是连续函数, 当点 \(\mathbf{x}\) 趋向可行域 边界时, \(B(x) \rightarrow+\infty\) 两种最重要的形式 \[ \begin{aligned} &B(x)=\sum_{i=1}^{m} \frac{1}{g_{i}(x)} \\ &B(x)=-\sum_{i=1}^{m} \log g_{i}(x) \end{aligned} \] r是很小的正数。这样, 当x趋向边界时, 函数 \(G(\mathbf{x}, \mathbf{r}) \rightarrow +\infty\) ； 否则, 由于 \(\mathbf{r}\) 很小, 则函数 \(\mathbf{G}(\mathbf{x}, \mathbf{r})\) 的取值近似 \(\mathbf{f}(\mathbf{x})\) 。因此, 可通过求解 下列问题得到的近似解: \[ \min G(x, r) \\ s.t. \ \ x \in intS \] 由于 \(\mathrm{B}(\mathrm{x})\) 的存在，在可行域边界形成“围墙”, 因此的解x必含于可行域的内部 B(x)的阻挡作用是自动实现的, 因此从计算的观点看,可当作无约束问题来处理
参考
- 《最优化计算方法》文再文
- 《凸优化》Stephen Boyd