罰函數(shù)法
本部分考慮約束優(yōu)化問題：
min
?
f
(
x
)
s
.
t
.
x
∈
χ
(1)
\begin{aligned} \min f(x) \\ s.t. x\in\chi \end{aligned} \tag{1}
minf(x)s.t.x∈χ?(1)
這里
χ
?
R
n
\chi\subset\mathbb{R}^n
χ?Rn為問題的可行域。與無約束問題不同，約束優(yōu)化問題中自變量
x
x
x不能任意取值，這導(dǎo)致無約束優(yōu)化算法不能使用。例如梯度法中沿著梯度負(fù)方向下降所得的點(diǎn)未必是可行點(diǎn)，要尋找最優(yōu)解處目標(biāo)函數(shù)的梯度也不是零向量。這使得約束優(yōu)化問題比無約束優(yōu)化問題要復(fù)雜許多。本部分要介紹的罰函數(shù)法將約束作為懲罰項(xiàng)加到目標(biāo)函數(shù)中，從而轉(zhuǎn)化為我們熟悉的無約束優(yōu)化問題求解。
一、等式約束的二次罰函數(shù)法
面對約束優(yōu)化問題，我們試圖通過變形將問題（1）轉(zhuǎn)化為無約束問題來求解。一種簡單的情況是，假設(shè)問題約束中僅含燈飾約束，即考慮問題
min
?
x
f
(
x
)
s
.
t
.
c
i
(
x
)
=
0
,
i
∈
E
(2)
\begin{aligned} &\min_{x}f(x) \\ &s.t.\quad c_i(x)=0, i\in\mathcal{E} \end{aligned}\tag{2}
?xmin?f(x)s.t.ci?(x)=0,i∈E?(2)
其中變量
x
∈
R
n
,
E
x\in\mathbb{R}^n,\mathcal{E}
x∈Rn,E為等式約束的指標(biāo)集，
c
i
(
x
)
c_i(x)
ci?(x)為連續(xù)函數(shù)。在某些特殊場合下，可以通過直接求解（非線性方程組）
c
i
(
x
)
=
0
c_i(x)=0
ci?(x)=0消去部分變量，將其轉(zhuǎn)化為無約束優(yōu)化問題。但是對于一般函數(shù)來說，變量消去這一操作很難實(shí)現(xiàn)，我們必須采用其他方法來處理這種問題。
罰函數(shù)法的思想是將約束優(yōu)化問題（1）轉(zhuǎn)化為無約束優(yōu)化問題來進(jìn)行求解。為了保證解的逼近質(zhì)量，無約束優(yōu)化問題的目標(biāo)函數(shù)為原約束優(yōu)化問題的目標(biāo)函數(shù)加上與約束函數(shù)有關(guān)的懲罰項(xiàng)。對于可行域外的點(diǎn)，懲罰項(xiàng)為正，即對該點(diǎn)進(jìn)行懲罰；對于可行域內(nèi)的點(diǎn)，懲罰項(xiàng)為0，即不做任何懲罰。因此懲罰項(xiàng)會促使無約束優(yōu)化問題的解落在可行域內(nèi)。
對于燈飾約束問題，懲罰項(xiàng)的選取方式有很多，結(jié)構(gòu)最簡單的是二次函數(shù)，這里給出二次罰函數(shù)的定義，
對于等式約束最優(yōu)化問題（1），定義二次罰函數(shù)
P
E
(
x
,
σ
)
=
f
(
x
)
+
1
2
∑
i
∈
E
c
i
2
(
x
)
P_E(x,\sigma)=f(x)+\frac{1}{2}\sum_{i\in\mathcal{E}}c_i^2(x)
PE?(x,σ)=f(x)+21?i∈E∑?ci2?(x)
其中燈飾右端第二項(xiàng)稱為懲罰項(xiàng)，
σ
>
0
\sigma>0
σ>0稱為懲罰因子。
由于這種罰函數(shù)對不滿足約束的點(diǎn)進(jìn)行懲罰，在迭代過程中點(diǎn)列一般處于可行域外，因此它也被稱為外點(diǎn)罰函數(shù)。二次罰函數(shù)的特點(diǎn)如下：對于非可行點(diǎn)而言，當(dāng)
σ
\sigma
σ變大時(shí)，懲罰項(xiàng)在發(fā)函數(shù)中的權(quán)重加大，對罰函數(shù)求績效，相當(dāng)于迫使其極小點(diǎn)向可行域靠近；在可行域中，
P
E
(
x
,
σ
)
P_E(x,\sigma)
PE?(x,σ)的全局極小點(diǎn)于約束問題（1）的最優(yōu)解相同。
舉例1
考慮優(yōu)化問題
min
?
x
+
3
y
s
.
t
.
x
2
+
y
2
=
1
\begin{aligned} &\min\quad x + \sqrt{3}y \\ &s.t. \quad x^2 + y^2 = 1 \end{aligned}
?minx+3?ys.t.x2+y2=1?
容易求出改問題的最優(yōu)解為
(
?
1
2
,
?
3
2
)
(-\frac{1}{2},-\frac{\sqrt{3}}{2})
(?21?,?23??)?？紤]二次罰函數(shù)
P
E
(
x
,
y
,
σ
)
=
x
+
3
y
+
σ
2
(
x
2
+
y
2
?
1
)
2
,
P_E(x,y,\sigma)=x+\sqrt{3}y+\frac{\sigma}{2}(x^2+y^2-1)^2,
PE?(x,y,σ)=x+3?y+2σ?(x2+y2?1)2,
在下圖中繪制出
σ
=
1
\sigma=1
σ=1和
σ
=
8
\sigma=8
σ=8對應(yīng)的罰函數(shù)的等高線?？梢钥闯?，隨著
σ
\sigma
σ增大，二次罰函數(shù)
P
E
(
x
,
y
,
σ
)
P_E(x,y,\sigma)
PE?(x,y,σ)的最小值和原問題最小值越來越接近，但最優(yōu)點(diǎn)附近的等高線越來越趨于扁平，這導(dǎo)致求解無約束優(yōu)化問題的難度變大。此外，當(dāng)
σ
=
8
\sigma=8
σ=8時(shí)函數(shù)出現(xiàn)了一個(gè)極大值，罰函數(shù)圖形在
(
?
1
2
,
?
3
2
)
T
(-\frac{1}{2},-\frac{\sqrt{3}}{2})^T
(?21?,?23??)T附近出現(xiàn)一個(gè)鞍點(diǎn)。
sigma = 1;
x = -2:0.01:2;
y = -2:0.01:1.5;
[X, Y] = meshgrid(x, y);
%X = X;
%Y = Y;
P_E = X + sqrt(3) * Y + sigma/2 * (X.^2+Y.^2-1).^2;
figure
subplot(121)
contour(X, Y, P_E, 80)
sigma = 8;
x = -2:0.01:2;
y = -2:0.01:1.5;
[X, Y] = meshgrid(x, y);
%X = X;
%Y = Y;
P_E = X + sqrt(3) * Y + sigma/2 * (X.^2+Y.^2-1).^2;
subplot(122)
contour(X, Y, P_E, 180)
從以上例子知道，給定罰因子 σ \sigma σ，我們可通過求解 P E ( x , σ ) P_E(x,\sigma) PE?(x,σ)的最小值點(diǎn)作為原問題的近似解。當(dāng)實(shí)際情況并不總是這樣，當(dāng) σ \sigma σ選取過小時(shí)罰函數(shù)可能無下屆。
舉例2
考慮優(yōu)化問題
min
?
?
x
2
+
2
y
2
s
.
t
x
=
1
\begin{aligned} &\min\quad -x^2+2y^2 \\ &s.t \quad x = 1 \end{aligned}
?min?x2+2y2s.tx=1?
通過消去變量容易得知最優(yōu)解就是
(
1
,
0
)
T
(1,0)^T
(1,0)T。但考慮罰函數(shù)
P
E
(
x
,
y
,
σ
)
=
?
x
2
+
2
y
2
+
σ
2
(
x
?
1
)
2
,
P_E(x,y,\sigma)=-x^2+2y^2+\frac{\sigma}{2}(x-1)^2,
PE?(x,y,σ)=?x2+2y2+2σ?(x?1)2,
對任意的
σ
≤
2
\sigma\le 2
σ≤2，該罰函數(shù)是無界的。
出現(xiàn)以上現(xiàn)象的原因時(shí)當(dāng)罰因子過小時(shí)，不可行點(diǎn)處的函數(shù)下降抵消了罰函數(shù)對約束違反的懲罰。實(shí)際上所有外點(diǎn)罰函數(shù)法均存在這個(gè)問題，因此
σ
\sigma
σ的初值選取不應(yīng)該太小。
我們在這里給出等式約束罰函數(shù)法的算法，之后再對每一步進(jìn)行具體解釋。
二次罰函數(shù)法
- 給定 σ 1 > 0 , x 0 , k ← 1 \sigma_1>0,x^0,k\leftarrow 1 σ1?>0,x0,k←1，罰因子增長系數(shù) ρ > 0 \rho > 0 ρ>0
- while 未達(dá)到收斂準(zhǔn)則 do
- 以 x k x^k xk為初始點(diǎn)，求解 x k + 1 = a r g min ? x P E ( x , σ k ) x^{k+1}=arg\min_{x}P_E(x,\sigma_k) xk+1=argminx?PE?(x,σk?)
- 選取 σ k + 1 = ρ σ k \sigma_{k+1}=\rho\sigma_k σk+1?=ρσk?
- k ← k + 1 k\leftarrow k+1 k←k+1
- end while
算法的執(zhí)行過程比較直觀：即先選取一系列指數(shù)增長的罰因子 σ k \sigma_k σk?，然后針對每個(gè)罰因子求解二次罰函數(shù)文章來源：http://www.zghlxwxcb.cn/news/detail-417909.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-417909.html
到了這里，關(guān)于約束優(yōu)化求解之罰函數(shù)法的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
