罚函数法总结

处理有约束的优化问题时，一种常见的处理方法是: 将约束条件作为惩罚项加到目标函数中。"惩罚"是一个很形象的称呼，意思是优化过程迭代到约束条件之外时给与惩罚，或者说负反馈。例如，我们在处理最小化函数值

f

f

f时，在f中增加一些项，这些项会使得迭代点在可行域之外时，增大函数f的值，这些项就起到了惩罚的作用

这些约束条件可以是等式，也可以是不等式，又或者是两者都有。

在处理等式约束时，常常使用外点罚函数法，意思是迭代点允许在可行域之外(其实非常自然，因为等式约束是一种"很严格"的约束，迭代不要限制地太紧了，不然都不好迭代优化);对于不等式约束，常使用内点罚函数法，意思是不让迭代点到可行域之外。内点法适用于只有不等式约束的问题。在对函数添加罚函数后，就将有约束的优化问题转换为了无约束优化问题。

外点罚函数法

等式约束外点罚函数法

考虑问题

min

⁡

x

f

(

x

)

∈

R

n

s

.

t

c

i

=

i

E

\min_x f(x) \quad x\in \mathbb{R^n}\\ s.t. \ \ c_i(x)=0 \ \ i \in \mathcal E

xmin​f(x)x∈Rns.t.  ci​(x)=0  i∈E

最自然的想法，把约束条件的平方作为罚函数，即

P

E

,

σ

+

1

2

∑

P_E(x, \sigma)=f(x)+\frac{1}{2}\sigma \sum_i c_i^{2}(x)

PE​(x,σ)=f(x)+21​σi∑​ci2​(x)

其中第二项为惩罚项，sigma称为罚因子。这种方法称为等式约束的二次外点罚函数法。其迭代过程与收敛性的证明参考文在文的《最优化计算方法》P186

上面我们说，外点罚函数法常用于处理等式约束，但如果通过巧妙的设计，也可以用于不等式约束，例如对于如下问题

不等式约束外点罚函数法

min

≤

I

\min_x f(x) \quad x\in \mathbb{R^n}\\ s.t. \ \ c_i(x)\le0 \ \ i \in \mathcal I

xmin​f(x)x∈Rns.t.  ci​(x)≤0  i∈I

将二次罚函数设定为如下样式

c

~

max

⁡

\tilde c_i(x)=\max (x_i(x),0)

c~i​(x)=max(xi​(x),0)

那么有

I

P_I(x, \sigma)=f(x)+\frac{1}{2}\sigma \sum_i \tilde c_i^{2}(x)

PI​(x,σ)=f(x)+21​σi∑​c~i2​(x)

可见，此时也允许迭代点在可行域之外迭代。值得注意的是，

P

P_I

PI​仍然是可导函数，进而可以用梯度类算法求解。

同时含有等式约束与不等式约束的外点罚函数法

对于如下问题

\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

xmin​f(x)x∈Rns.t.  ci​(x)≤0   i∈Ic~i​(x)=0   i∈E

把两个罚函数相加即可

P(x, \sigma)=f(x)+\frac{1}{2}\sigma (\sum_i c_i^{2}(x) + \sum_i \tilde c_i^{2}(x))

P(x,σ)=f(x)+21​σ(i∑​ci2​(x)+i∑​c~i2​(x))

内点罚函数法

参考

• 《最优化计算方法》文再文
• 《凸优化》Stephen Boyd