18.2.8 罚函数法和障碍函数法

这些方法的基本原理是通过修正目标函数将约束优化问题转换成一列无约束优化问题. 修正后的问题, 例如, 可以通过 18.2.5 给出的方法求解. 通过适当构造修正的目标函数, 这一修正问题解点列的每个聚点都是原问题的一个解.

18.2.8.1 罚函数法

问题

$$\begin{array}{}\text{(18.107)}& f\left(\underset{―}{\mathbf{x}}\right)=min!,\text{ 约束条件为 }{g}_i\left(\underset{―}{\mathbf{x}}\right)\le 0\left(i=1,\cdots ,m\right)\end{array}$$

用如下一列无约束问题代替:

$$\begin{array}{}\text{(18.108)}& H\left(\underset{―}{\mathbf{x}},p_k\right)=f\left(\underset{―}{\mathbf{x}}\right)+p_{k}S\left(\underset{―}{\mathbf{x}}\right)=min!,\text{ 其中 }\underset{―}{\mathbf{x}}\in {\mathbb{R}}^n,p_k>0\left(k=1,2,\cdots \right)\end{array}$$

这里 $p_k$ 是正参数,而 $S\left(\underset{―}{\mathbf{x}}\right)$ 满足

$$\begin{array}{}\text{(18.109)}& S\left(\underset{―}{\mathbf{x}}\right)=\{\begin{array}{ll}=0,& \underset{―}{\mathbf{x}}\in M,\\ >0,& \underset{―}{\mathbf{x}}\notin M,\end{array}\end{array}$$

即让可行集 $M$ 用一 “补偿” 项 $p_{k}S\left(\underset{―}{x}\right)$ 进行惩罚. 问题 (18.108) 通过一列趋于无穷的罚参数 $p_k$ 来求解. 于是

$$\begin{array}{}\text{(18.110)}& \underset{k\to \mathrm{\infty }}{lim}H\left(\underset{―}{\mathbf{x}},p_k\right)=f\left(\underset{―}{\mathbf{x}}\right),\underset{―}{\mathbf{x}}\in M.\end{array}$$

如果 ${\underset{―}{\mathbf{x}}}^k$ 是第 $k$ 个罚问题的解,则

$$\begin{array}{}\text{(18.111)}& H\left(\underset{―}{\mathbf{x}},p_k\right)\ge H\left({\underset{―}{\mathbf{x}}}^{k-1},p_{k-1}\right),f\left({\underset{―}{\mathbf{x}}}^k\right)\ge f\left({\underset{―}{\mathbf{x}}}^{k-1}\right),\end{array}$$

并且序列 $\left\{{\underset{―}{x}}^k\right\}$ 的每个聚点 ${\underset{―}{x}}^{\ast }$ 都是 (18.107) 的解. 如果 ${\underset{―}{x}}^k\in M$ ,则 ${\underset{―}{x}}^k$ 是原问题的解.

例如,如下函数是 $S\left(\underset{―}{\mathbf{x}}\right)$ 的合适的选择:

$$\begin{array}{}\text{(18.112a)}& S\left(\underset{―}{\mathbf{x}}\right)=\stackrel{r}{max}\left\{0,g_1\left(\underset{―}{\mathbf{x}}\right),\cdots ,g_m\left(\underset{―}{\mathbf{x}}\right)\right\}\left(r=1,2,\cdots \right)\end{array}$$

或

$$\begin{array}{}\text{(18.112b)}& S\left(\underset{―}{\mathbf{x}}\right)=\sum _{i=1}^m\stackrel{r}{max}\left\{0,g_i\left(\underset{―}{\mathbf{x}}\right)\right\}\left(r=1,2,\cdots \right).\end{array}$$

如果函数 $f\left(\underset{―}{\mathbf{x}}\right)$ 和 $g_i\left(\underset{―}{\mathbf{x}}\right)$ 可微,那么当 $r>1$ 时,罚函数 $H\left(\underset{―}{\mathbf{x}},p_k\right)$ 在 $M$ 的边界上也可微, 从而可以使用解析解求解辅助问题 (18.108).

图 18.11 为罚函数方法的示意图.

$f\left(\underset{―}{\mathbf{x}}\right)=x_1^2+x_2^2=min!,x_1+x_2\ge 1,H\left(\underset{―}{\mathbf{x}},p_k\right)=x_1^2+x_2^2+p_k\stackrel{2}{max}\{0,1-$$x_1-x_2\}$ . 最优性必要条件是

$$\mathrm{\nabla }H\left(\underset{―}{\mathbf{x}},p_k\right)=\left(\begin{array}{l}2x_1-2p_{k}max\left\{0,1-x_1-x_2\right\}\\ 2x_2-2p_{k}max\left\{0,1-x_1-x_2\right\}\end{array}\right)=\left(\begin{array}{l}0\\ 0\end{array}\right).$$

这里 $H$ 的梯度是相对于 $\underset{―}{x}$ 计算的. 两个方程相减得到 $x_1=x_2$ . 方程 $2x_1-$ $2p_{k}max\left\{0,1-2x_1\right\}=0$ 有唯一解 $x_1^k=x_2^k=\frac{p_k}{1+2p_k}$ . 由此让 $k\in \mathrm{\infty }$ 得到解$x_1^{\ast }=x_2^{\ast }=\underset{k\to \mathrm{\infty }}{lim}\frac{p_k}{1+2p_k}=\frac{1}{2}.$

18.2.8.2 障碍函数法

在障碍函数法中, 考虑如下一列修正问题:

$$\begin{array}{}\text{(18.113)}& H\left(\underset{―}{\mathbf{x}},q_k\right)=f\left(\underset{―}{\mathbf{x}}\right)+q_{k}B\left(\underset{―}{\mathbf{x}}\right)=min!,q_k>0.\end{array}$$

这里的项 $q_{k}B\left(\underset{―}{x}\right)$ 是为了避免解偏离可行集 $M$ ,因为目标函数在接近 $M$ 的边界时会无限增长. 正则性条件

$$\begin{array}{}\text{(18.114)}& M^0=\left\{\underset{―}{\mathbf{x}}\in M:g_i\left(\underset{―}{\mathbf{x}}\right)<0,i=1,\cdots ,m\right\}\ne \varnothing ,\overline{M^0}=M\end{array}$$

必须满足,即 $M$ 的内点必须非空,并且要求从内部可以逼近到任意边界点,即 $M^0$ 的闭包是 $M$ . 函数 $B\left(\underset{―}{x}\right)$ 要求在 $M^0$ 上连续,而在边界上增加到无穷大. 修正问题 (18.113) 通过一列趋于零的障碍参数 $q_k$ 来求解. 设 ${\underset{―}{x}}^k$ 是第 $k$ 个问题 (18.113) 的解, 则

$$\begin{array}{}\text{(18.115)}& f\left({\underset{―}{\mathbf{x}}}^k\right)\le f\left({\underset{―}{\mathbf{x}}}^{k-1}\right),\end{array}$$

并且序列 $\left\{{\underset{―}{\mathbf{x}}}^k\right\}$ 的每个聚点都是 (18.107) 的解. 图 18.12 为障碍函数法的示意图. 例如, 函数

$$\begin{array}{}\text{(18.116a)}& B\left(\underset{―}{\mathbf{x}}\right)=-\sum _{i=1}^m-\ln \left(-g_i\left(\underset{―}{\mathbf{x}}\right)\right),\underset{―}{\mathbf{x}}\in M^0\end{array}$$

或

$$\begin{array}{}\text{(18.116b)}& B\left(\underset{―}{\mathbf{x}}\right)=-\sum _{i=1}^m\frac{1}{{[-g_i\left(\underset{―}{\mathbf{x}}\right)]}^r}\left(r=1,2,\cdots \right),\underset{―}{\mathbf{x}}\in M^0\end{array}$$

是 $B\left(\underset{―}{x}\right)$ 的合适的选择.

$f\left(\underset{―}{\mathbf{x}}\right)=x_1^2+x_2^2=min!,x_1+x_2\ge 1,H\left(\underset{―}{\mathbf{x}},q_k\right)=x_1^2+x_2^2+q_k\left(-\ln \left(x_1+x_2-1\right)\right),$$x_1+x_2>1,\mathrm{\nabla }H\left(\underset{―}{\mathbf{x}},q_k\right)=\left(\begin{array}{c}2x_1-q_k\frac{1}{x_1-x_2-1}\\ 2x_2-q_k\frac{1}{x_1+x_2-1}\end{array}\right)=\left(\begin{array}{l}0\\ 0\end{array}\right),x_1+x_2>1$ . 这里 $H$ 的梯度是相对于 $\underset{―}{x}$ 的. 两个方程相减得到 $x_1=x_2,2x_1-q_k\frac{1}{2x_1-1}=0,x_1>\frac{1}{2}\Rightarrow x_1^2-\frac{x_1}{2}-\frac{q_k}{4}=$$0,x_1>\frac{1}{2},x_1^k=x_2^k=\frac{1}{4}+\sqrt{\frac{1}{16}+\frac{q_k}{4}},k\to \mathrm{\infty },q_k\to 0:x_1^{\ast }=x_2^{\ast }=\frac{1}{2}.$

问题 (18.108) 和 (18.113) 第 $k$ 步的解并不依赖于前几步的解. 应用高阶罚函数和较小的障碍参数往往会引起 (18.108) 和 (18.113) 的数值解的收敛性问题, 例如,特别是在 (18.2.4) 的方法中,如果没有好的初始近似的话. 使用第 $k$ 个问题的解作为第 $k+1$ 个问题的初始解,收敛行为有可能得到改善.