罰函數(shù)法
求解約束優(yōu)化問(wèn)題：
\begin{align*}
\mathop{min}\limits_{x} & \quad f(x)\\
s.t. & \quad x \in S
\end{align*}
其中，$f$是連續(xù)函數(shù)。
可以采用罰函數(shù)法將約束優(yōu)化問(wèn)題轉(zhuǎn)變?yōu)闊o(wú)約束優(yōu)化問(wèn)題，具體方法是對(duì)目標(biāo)函數(shù)加上懲罰項(xiàng)：
$$q(c_k,x)=f(x)+c_kP(x)$$
其中:1)數(shù)列$\{c_k\}\subset \mathbb{R}$，且$c_k \uparrow,c_k\rightarrow +\infty$。2)$P$連續(xù)，$P \geq 0$，且$P(x)=0 \iff x \in S$。
對(duì)任意的$k$，求解$ min_{x} q(c_k,x)$得到的解記為$x_k$。

引理
$$q(c_k,x_k)\leq q(c_{k+1},x_{k+1})$$
proof：
\begin{align*}
q(c_k,x_k)=&f(x_k)+c_kP(x_k)\\
\leq & f(x_{k+1})+c_kP(x_{k+1})\\
\leq & f(x_{k+1})+c_{k+1}P(x_{k+1})=q(c_{k+1},x_{k+1})
\end{align*}

假設(shè)$x^*$為原問(wèn)題的解點(diǎn)，則有$$f(x^*)\geq q(x_k,x_k)\geq f(x_k)$$
proof：
\begin{align*}
f(x^*)=&f(x^*)+c_kP(x^*)\\
\geq& f(x_k)+c_kP(x_k)\\
\geq &f(x_k)
\end{align*}

收斂性
假設(shè)$\{x_k\}$是由罰函數(shù)法生成的序列，則其任意極限點(diǎn)都是原問(wèn)題的解點(diǎn)。
proof：\quad
取$\{x_k\}$的一個(gè)極限點(diǎn)為$\mathop{x}\limits^{-}$，為了書(shū)寫(xiě)方便記收斂子列依然為$\{x_k\}$。
由于函數(shù)$f$的連續(xù)性，有$$\lim\limits_{k\rightarrow +\infty}f(x_k)=f(\mathop{x}\limits^{-})$$
由上述兩個(gè)引理得到$q(c_k,x_k)$關(guān)于$k$單增，且以$f^*$為上界，于是得到:
$$\lim\limits_{k\rightarrow +\infty}q(c_k,x_k)=q^*\leq f^*$$
于是有$$\lim\limits_{k\rightarrow +\infty}q(c_k,x_k)-f(x_k)=\lim\limits_{k\rightarrow +\infty}=c_kP(x_k)\leq q^*-f(\mathop{x}\limits^{-})$$
再根據(jù)$c_k \rightarrow +\infty $，于是有$P(x_k)\rightarrow 0$，根據(jù)$P$的連續(xù)性得到:
$$\lim\limits_{k\rightarrow +\infty}P(x_k)=P(\mathop{x}\limits^{-})=0$$
于是極限點(diǎn)$\mathop{x}\limits^{-} \in S$。
由根據(jù)第二個(gè)引理得到:$$f(\mathop{x}\limits^{-})=\lim\limits_{k\rightarrow +\infty}f(x_k)\leq f^*$$
則$\mathop{x}\limits^{-}$是解點(diǎn)。
****************