---

[toc]

罚函数

罚函数法定义：将约束最优化问题转化为无约束最优化问题去求解

等式约束问题

对于约束问题

$$\large{ \begin{align} min\ & f(x)\\ s.t.\ & g_i(x) = 0 \end{align} }$$

定义罚函数为

$$\large{\begin{align} min\ F(x,\sigma) &= f(x)+\sigma{P(x)}\\ P(x) &= g_i(x)^Tg_i(x) \end{align}}$$

其中$\large{\sigma}$是惩罚因子，$\large{F(x,\sigma)}$是罚函数，$\large{\sigma{P(x)}}$是惩罚项

该罚函数的特点：对非可行点，当$\large\sigma$变大时，惩罚项在罚函数的比重加大，对罚函数求极小相当于使极小值点向可行域靠近。简单的说就是只要你没得到可行解，惩罚项就会越来越大，对罚函数求极小就会迫使所求的x点向极小值点靠近来让惩罚项下降

不等式约束问题

对于约束问题

$$\begin{align} min\ & f(x) \\ s.t.\ &h_i(x) \geq 0 \end{align}$$

当$\large h_i(x)\geq0$时，惩罚项为0；当x不在可行域时，$\large h_i(x)<0$，所以我们用$\large{min\{h_i(x),0\}}$来分辨x是否在可行域。如果不在，我们还需要加大惩罚因子

所以我们定义惩罚项为$\large P(x)=\sigma{\sum_{i\in{I}}[min\{h_i(x),0\}]}^2$,

一般形式约束问题

对于约束问题

$$\large{\begin{align} min\ & f(x)\\ s.t.\ & g_i(x)=0\\ & h_j(x)\ge 0 \end{align}}$$

则罚函数为$\large{P(x)=\sum_i[g_i(x)]^2 + \sum_j[min\{0,h_j(x)\}]^2}$

特别注意：惩罚因子是充分大的数，拉格朗日乘子是一个确定的参数，意义不一样

增广拉格朗日

定义：增广拉格朗日就是在拉格朗日函数上增加一个惩罚项

等式约束

$$\large{\begin{align} min\ & f(x)\\ s.t.\ & g_i(x)=0 \end{align}}$$

其增广拉格朗日函数为：$\large{\phi(x,\lambda,\sigma)=f(x)+\lambda^T{g(x)}+\frac{1}{2}\sigma{g^T(x)g(x)}}$，其中惩罚因子前的1/2只是为了求导方便

令$\large{\nabla_x\phi(x_k,\lambda_k,\sigma_k)}=0$

得到

$$\large{\begin{align} &\nabla_xf(x_k)+\lambda_k\nabla_xg^T(x_k)+\sigma_k\nabla_kg^T(x_k)g(x_k)\\ =&\nabla_kf(x_k)+\nabla_xg^T(x_k)(\lambda_k+\sigma_kg(x_k)) \\ =& 0 \end{align}}$$

其中对惩罚项的导数为

$$\large{\begin{align} 原式&= \frac{\partial\frac{1}{2}\sigma{g^T(x)g(x)}}{\partial{x}} \\ &= \frac{1}{2}\sigma*\frac{\part{g^T(x)g(x)}}{\part{g(x)}} * \frac{\part{g(x)}}{\part{x}}\\ &= \frac{1}{2}\sigma*2g(x)*\nabla_xg(x)\\ &= \sigma{g(x)*\nabla_xg(x)} \\ &= \sigma{g(x)^T\nabla_xg(x)} \\ &= \sigma{\nabla_xg^T(x)g(x)} \end{align}}$$

令$\large{\lambda_{k+1}=\lambda_k+\sigma_kg(x_k)}$，得到$\large{\nabla_xf(x_k)+\lambda_{k+1}\nabla_x{g^T(x_k)}=0}$

不等式约束

$$\large{\begin{align} min\ & f(x) \\ s.t.\ & h_i(x)\ge0 \end{align}}$$

引入松弛变量a，使得$\large{h_i(x)-a=0}(a\ge0)$

则原问题化为

$$\large{\begin{align} min\ \phi(x,\lambda,\sigma)&=f(x)+\lambda^T(h_i(x)-a)+\frac{1}{2}\sigma{(h_i(x)-a)^T(h_i(x)-a)} (1) \end{align}}$$

消除松弛变量a，得到

$$\large{\begin{align} min\ \phi(x,\lambda,\sigma,a)&= f(x) + \frac{\sigma}{2}(\frac{2}{\sigma}\lambda^T(h_i(x)-a)+||(h_i(x)-a)||^2)\\ &= f(x) + \frac{\sigma}{2}((h_i(x)-a+\frac{\lambda}{\sigma})^2-(\frac{\lambda}{\sigma})^2)(2)\\ \end{align}}$$

当x确定时，求a的最小值，此时与a无关的因为不会影响可以忽略掉

$$\large{\begin{align} min_a\ \phi(x,\lambda,\sigma) &= (h_i(x)-a+\frac{\lambda}{\sigma})^2\\ s.t. a&\ge0 \\ \therefore a_i &= \frac{1}{\sigma}max\{0,\sigma{h_i(x)}+\lambda\} \end{align}}$$

当$\large{\sigma{h_i(x)}+\lambda\ge0}$时，也就是$\large{a={h_i(x)}+\frac{\lambda}{\sigma}}$，带入(2)式得到

$$\large{\begin{align} \phi(x,\lambda,\sigma) &= f(x)-\frac{\sigma}{2}(\frac{\lambda}{\sigma})^2\\ &=f(x) - \frac{\lambda^2}{2\sigma}\\ \therefore\nabla_x\phi(x,\lambda,\sigma)&=\nabla_xf(x) \end{align}}$$

当$\large{\sigma{h_i(x)}+\lambda<0}$时，$\large{a=0}$,带入(2)式，得到

$$\large{\begin{align} \phi(x,\lambda,\sigma)&=f(x)+\frac{\sigma}{2}(h_i(x)+\frac{\lambda}{\sigma})^2-\frac{\sigma}{2}(\frac{\lambda}{\sigma})^2\\ &=f(x)-\frac{\lambda^2}{2\sigma} + \frac{1}{2\sigma}(\sigma{h_i(x)}+\lambda)^2\\ \therefore \nabla_x\phi(x,\lambda,\sigma) &= \nabla_xf(x) + (\sigma{h_i(x)}+\lambda)\nabla_xh_i(x) \end{align}}$$

综上所述：

$$\large{ \nabla_x\phi(x,\lambda,\sigma) = \left\{\begin{align} &\nabla_xf(x),&\sigma{h_i(x)}+\lambda\ge0 \\ &\nabla_xf(x) + (\sigma{h_i(x)}+\lambda)\nabla_xh_i(x),&\sigma{h_i(x)}+\lambda<0 \end{align}\right.}$$

最后令梯度为0就能求得最优解