运筹说第102期 | 非线性规划

运筹说第102期 | 非线性规划—制约函数法

通过上期学习，大家已经了解了非线性规划中约束极值问题的最优性条件。本期小编将为大家介绍约束极值问题的求解方法：制约函数法，包括概念以及最基本的两种制约函数法：罚函数法、障碍函数法等内容。

制约函数法是通过构造某种制约函数，并将它加到非线性规划的目标函数上，从而将原来的约束极值问题，转化为无约束极值问题来求解。此处介绍的方法用来求解一系列无约束问题，故称为序列无约束极小化技术。

一、罚函数法

对于非线性规划

构造函数

将 $g_{j}(X)$ 视为t，将约束条件的函数加到原目标函数中，构造新的目标函数：

新的目标函数转变为求解无约束问题，假定该问题极小点为X*，必有 $g_{j}(X)\geq 0$ ，X*是新构造无约束问题的极小点，同样也是原非线性规划问题的极小点。

但是，如上构造的函数ψ(t)在0处不连续，不可导，这就无法使用很多有效的无约束极值极小化方法进行求解。因此将其修改为

修改后的ψ(t)处处可导，ψ(t)和ψ′(t)处处连续。这时，修改后的函数的极小点不一定就是原非线性规划问题的极小点。于是，选取很大的实数M>0，作为惩罚因子，则得到

该式也可以写成另一种形式

在这个式子中，M称为惩罚因子， $M\sum_{j=1}^{l}\Psi (g_{j}(\mathbf{X}))$ 为惩罚项，P(X,M)为罚函数。

当X∈R时,P(X,M)=P(X)；当X∉R时, $M\sum_{j=1}^{l}\Psi (g_{j}(\mathbf{X)})$ 就会很大，离可行域越远，惩罚越大。当M足够大时，是新构造无约束问题的极小点，同样也是原非线性规划问题的极小点。

现引进阶跃函数

得到如下转变

随着罚因子M增大，惩罚项起到的作用就越大，minP(X,M)越趋近于可行域 $d_{0}$ ，当0<M1<M2<...Mk<...，趋于无穷大时，点列 $\left \{ \mathbf{X}(M_{k}) \right \}$ 会从可行域R的外部趋于原非线性规划的问题的极小点（此处假设点列 $\left \{ \mathbf{X}(M_{k}) \right \}$ 收敛）。

和不等式约束问题类似，对于等式约束问题，也可做如下变换：

对于既含有等式约束，又有不等式约束的一般非线性规划问题

其罚函数为

或

迭代步骤

(1)取第一个罚因子 $M_{1}>0$ ，允许ε>0，并令k:=1。

(2)求下述无约束极值问题的最优解： $minP(\mathbf{X},M_{k})$ ，设其极小点为 $\mathbf{X}^{(k)}$ 。

(3)若存在某一个j (1≤j≤l)，有 $-g_{j}(X)>\varepsilon$ ，或(和)存在某一个i (1≤i≤m)，有 $\left | h_{i} (X^{K})\right |> \varepsilon$ ，则取 $M_{k+1}>M_{k}$ （例如 $M_{k+1}=cM_{k}$ ,c=5），并令K:=k+1。然后，转回第(2)步；否则停止迭代，得到所要的点 $\mathbf{X}^{(k)}$ 。

例题

用罚函数法求解

解：

(1)构造罚函数

(2)对于固定的M，令

对于不满足约束条件的点x，有

(3)求得其极小点x(M)为

当M=0，x(M)=1/2

当M=1，x(M)=1/4

当M=10，x(M)=1/22

当M→∞，x(M)→0

因此，原约束问题的极小点x*=0

二、障碍函数法

对于罚函数而言，函数P(X,M)可在整个 $E_{n}$ 空间内进行优化，迭代过程往往在可行域外进行，不能以中间结果作为近似解使用。同时，目标函数在可行域外的性质比较复杂，甚至没有定义，就无法使用罚函数法。

障碍函数法与其不同，该方法要求迭代过程始终在可行域内进行。如果初始迭代点取在可行域内部（严格内点），在进行无约束极小化时，会阻止函数迭代到R的边界上，使迭代过程始终在可行域内部。此时的极小化是在不包括可行域边界的可行域开集上进行的，是一种具有无约束性质的极值问题，可用无约束极小化方法求解。

考虑非线性规划

当X点从可行域R内部趋于边界时，至少有某一个约束函数 $g_{j}(X)$ (j=1,2,...,l)趋于0，从而得到倒数函数 $\sum_{j=1}^{l}\frac{1}{g_{j}(\mathbf{X})}$ 以及（负）对数函数 $-\sum_{j=1}^{l}lg(g_{j}(\mathbf{X}))$ 都无限增大。

把倒数函数或对数函数加到目标函数上，则能构成新目标函数。取实数并构成一系列无约束性质的极小化问题如下：

其中

或

此处， $R_{0}$ 为严格内点的集合，即

上述式子中， $r_{k}\sum_{j=1}^{l}\frac{1}{g_{j}(\mathbf{X})}$ 和 $r_{k}\sum_{j=1}^{l}lg(g_{j}(\mathbf{X}))$ 被称为障碍项，此处 $r_{k}$ 为障碍因 $\left (r_{k}>0\right )$ ，函数 $\bar{P}(\mathbf{X},r_{k})$ 为障碍函数。