填充函数法由葛仁溥教授在1990年提出, 是求解全局最优化问题的一种确定性算法.实践表明它是求解全局最优化问题的一种有效方法.在社会生产中遇到的许多实际问题都可以转化为全局最优化问题.因此, 对它的研究有着重要的理论和实际应用意义.
文献[1]中给出了一个带两个参数的填充函数
数值试验表明, 该填充函数和算法是有效的, 但存在如下的缺陷[2]:首先, 该算法的运算效率很大程度上依赖于两个参数$r$和$\rho $.如果参数$r$较大而$\rho ^{2}$与$r+f(x)$的比较小, 那么$f(x)$的全局极小点会在计算中被遗漏; 其次文献[3]中, 由于函数(1.1) 中存在指数项$\exp \left( {-\frac{\left\| {x-x_{1}^{\ast } } \right\|^{2}}{\rho^{2}}} \right)$, 在$\left\| {x-x_{1}^{\ast } } \right\|^{2}$过大或$\rho $过小时, $p(x_{1}^{\ast }, x, r, \rho )$和$\left\| {\nabla p(x_{1}^{\ast }, x, r, \rho )} \right\|$将变得很小, 从而产生假的平衡点.
为解决以上问题, 以后的学者构造了一些新的填充函数, 其中文献[3]给出了一个只含有一个参数的填充函数
其中参数$a$应充分大.该填充函数比$(1.1)$在效率上有了一定提高, 但仍存在参数的选取问题.文献[4]给出了一无参数填充函数
其中
数值试验表明填充函数$(1.3)$是有效的.由于不需要调整参数, 提高了运算效率.但$F(x, x_{1}^{\ast} )$不是关于目标函数$f(x)$的明确表达式.
本文研究了以上填充函数, 为克服其存在的缺陷, 构造了一个无参数的填充函数, 该填充函数具有关于目标函数$f(x)$的明确表达式.进行了数值试验.
关于填充函数的盆地和山头的定义详见参考文献[1].
本文考虑如下全局无约束最优化问题
其中$f(x)$是$R^{n}\to R^{1}$的目标函数, $x$是$n$维向量.
设目标函数$f(x)$满足一下假设[1]:
(1) 目标函数$f(x)$在$R^{n}$上连续可微;
(2) 当$\left\| x \right\|\to +\infty $时, $f(x)\to +\infty $.在该假设的条件下, 意味着存在一个有界闭区域$\Omega $, 使得在它的内部包含了$f(x)$的所有全局极小点;
(3) 目标函数$f(x)$在$\Omega $上只有有限个局部极小点.所以每个极小点都是孤立的, 而且对于$f(x)$的每一个极小点$x^{\ast }$处的盆地$B^{\ast }$内的任意点$x\ne x^{\ast }$, 都有$f(x)>f(x^{\ast })$.
定义1[1] 设$x^{\ast }$是$f(x)$的一个已知的局部极小点, 如果$P(x, x^{\ast })$满足一下条件:
(1) $x^{\ast }$是$P(x, x^{\ast })$的局部极大点, 并且$f(x)$的整个盆地$B^{\ast }$变成了$P(x, x^{\ast })$的山头的一部分;
(2) $P(x, x^{\ast })$在$f(x)$的任何比$B^{\ast }$高的盆地里没有极小点或者鞍点;
(3) 如果$f(x)$在$x_{0}^{\ast } $处有比$B^{\ast }$低的盆地$B_{0}^{\ast } $, 则$B_{0}^{\ast } $中存在一个点${x}'$, 它在$x^{\ast }$和$\overline {x_{0}^{\ast } } $的直线上且最小化$P(x, x^{\ast })$, 其中$\overline {x_{0}^{\ast } } $是$x_{0}^{\ast } $的某一邻域中的任意一点, 则$P(x, x^{\ast })$称为$f(x)$在点$x^{\ast }$处的一个填充函数.
构造填充函数:
其中$x^{\ast }$是$f(x)$的一个已知的局部极小点.
定理1 $W(x, x^{\ast })$是一个连续函数.
证 由假设条件(1) 易得$W(x, x^{\ast })$是一个连续函数.
定理2 设$x^{\ast }$是$f(x)$的一个已知的局部极小点, 则点$x^{\ast }$是$W(x, x^{\ast })$的一个严格局部极大点.
证 因为$x^{\ast }$是$f(x)$的一个局部极小点, 所以在$x^{\ast }$的盆地$B^{\ast }$内, 任意$x\in B^{\ast }$且$x\ne x^{\ast }$时, $f(x)>f(x^{\ast })$.所以对任意的$x\in B^{\ast }$且$x\ne x^{\ast }$,
又因为$W(x^{\ast }, x^{\ast })=0$, 所以$W(x, x^{\ast })< W(x^{\ast }, x^{\ast })$.所以点$x^{\ast }$是$W(x, x^{\ast })$的一个严格局部极大点.
定理3 设$f(x)>f(x^{\ast })$且$x\ne x^{\ast }$, 则$\nabla W(x, x^{\ast })\ne 0$.
证 因为$W(x, x^{\ast })=-[\arctan (e^{(f(x)-f(x^{\ast }))}-1)]\left\| {x-x^{\ast }} \right\|^{2}$, 则
由$x\ne x^{\ast }$且$f(x)>f(x^{\ast })$可知
因为$f(x)$在$R^{n}$上连续可微, 所以由泰勒公式展开得
所以$f(x^{\ast })-f(x)=(x^{\ast }-x)^{T}\nabla f(x)+o(\left\| {x^{\ast }-x} \right\|)$.因为$f(x)>f(x^{\ast })$得$f(x^{\ast })-f(x)<0$.所以
即$(x^{\ast }-x)^{T}\nabla f(x)<0$。所以, $(x-x^{\ast })^{T}\nabla f(x)=-(x^{\ast }-x)^{T}\nabla f(x)>0$, 所以
此定理证明了:当$f(x)>f(x^{\ast })$时, $\nabla W(x, x^{\ast })$没有鞍点, 且可得$d=x-x^{\ast }$为$W(x, x^{\ast })$的一个下降方向.
定理4 设$x^{\ast }$不是$f(x)$的一个全局极小点, 而$x_{0}^{\ast } $是$f(x)$邻近$x^{\ast }$的另一个局部极小点, 使得$f(x_{0}^{\ast } )<f(x)$, 则存在一个点${x}'\in B_{0}^{\ast } $, $\overline {x_{0}^{\ast } } $为$x_{0}^{\ast } $的某一领域内的任意一点, ${x}'$在$x^{\ast }$和$\overline {x_{0}^{\ast } } $的直线上并且使得$W(x, x^{\ast })$最小.
证 因为$x^{\ast }$是的一个局部极小点, 则对于$x^{\ast }$处的盆地$B^{\ast }$内的任意$x\ne x^{\ast }$点, 有$f(x)>f(x^{\ast })$, 则$W(x, x^{\ast })=-[\arctan (e^{(f(x)-f(x^{\ast }))}-1)]\left\| {x-x^{\ast }} \right\|^{2}<0$.
$x_{0}^{\ast } $是$f(x)$邻近$x^{\ast }$的另一个局部极小点, 则存在$x_{0}^{\ast } $的某一领域$O\left( {x_{0}^{\ast } , \delta_{0}^{\ast } } \right)$, 使得任意$\overline {x_{0}^{\ast } } \in O\left( {x_{0}^{\ast }, \delta_{0}^{\ast } } \right)$, 有$f(x^{\ast })>f(\overline {x_{0}^{\ast } } )>f(x_{0}^{\ast } )$, 则
易得$W(x^{\ast }, x^{\ast })=0$, 当$x$远离$x^{\ast }$时, $W(x, x^{\ast })<0$; 当$x$接近$\overline {x_{0}^{\ast } } $时, $W(x, x^{\ast })>0$, 可得, 当$f(x)>f(x^{\ast })$时, $W(x, x^{\ast })$递增; 当$f(x)<f(x^{\ast })$时, $W(x, x^{\ast })$递减.又因为$W(x, x^{\ast })$的连续性, 可得在$x_{0}^{\ast } $的某一领域内的点$\overline {x_{0}^{\ast } } $, 在$x^{\ast }$和$\overline {x_{0}^{\ast } } $的直线上有点${x}'$使得$W(x, x^{\ast })$最小.
定理5 若$x^{\ast }$是$f(x)$的一个全局极小点, 则对任意的$x\ne x^{\ast }$, 都有$W(x, x^{\ast })\leq 0$成立; 否则存在一个点$x_{0} $和它的一个邻域$O\left( {x_{0}, \delta_{0} } \right)$, 其中$\delta_{0} >0$, 并且$f(x_{0} )<f(x^{\ast })$, 使得对任意的$x\in O\left( {x_{0}, \delta _{0} } \right)$, 有$W(x, x^{\ast })>0$成立.
证 因为$x^{\ast }$是$f(x)$的一个全局极小点, 则对任意的$x\ne x^{\ast }$, 都有$f(x)\geq f(x^{\ast })$, 易得$W(x, x^{\ast })\leq 0$.
如果$x^{\ast }$不是$f(x)$的一个全局极小点, 则存在$x_{0} $使得$f(x_{0} )< f(x^{\ast })$, 由$f(x)$的连续性可知:存在$x_{0} $的一个领域$O\left( {x_{0}, \delta_{0} } \right)$, 其中$\delta_{0} >0$, 使得对于任意的$x\in O\left( {x_{0}, \delta_{0} } \right)$, 都有$f(x)<f(x^{\ast })$, 所以$W(x, x^{\ast })>0$.由以上证明可得$W(x, {x^ * })$满足填充函数的定义.
本文对文献[2]的算法加以改进.
步1 设定搜索步长$\delta > 0$, 选取任一初始点${x_0} \in \Omega $, 令$k = 1$, $i = 1$, $K = 2 \cdot \min ({3^n} - 1, 2n)$, 其中$n$为变量的个数.
步2 以${x_0}$为初始点, 用一局部极小化找到得目标函数$f(x)$的一个局部极小点${x^ * }$, 并计算出局部极小值$f({x^ * })$.
步3 如果$i < K$, 转到步4;否则${x^ * }$作为全局极小点, 停止运算.
步4 以${x^ * }$为初始点, 寻找到$W(x, {x^ * })$的局部极小点$x_1^ * $.
步5 令$x = x_1^ * $.
步6 如$W(x, {x^ * }) > 0$或者$f(x) < f({x^ * })$, 则令$k = k + 1$, ${x_0} = x$, 转步2;否则转步7.
步7 如果$j < {3^n} - 1$, 令$x = x + \delta {e_j}$, 转步6, 否则, $j = j + 1$; 若$x \notin X$, 则$i = i + 1$, 转步3;否则, 转步7.
用Matlab编程对此算法加以实现, 成功找到下列函数的全局极小点:
(1) $\begin{array}[t]{c} f(x) = \sin x + \sin (10x/3) + \ln x - 0.84x s.t.1 \le x \le 6 \end{array}$全局极小点${x^ * }$ =5.1998, 全局最小值${f^*} =-4.6013.$
(2) $ \begin{array}[t]{c} f(x) = \sin x + \sin (3x) s.t.0 \le x \le 4 \end{array}$全局极小点${x^ * } =3.7571, $全局最小值${f^*} =-1.5396.$
(3) 3-hump back camel function:
全局极小点${x^ * } = (0, 0), $全局最小值${f^ * } =0.$
(4) Simplified Rosenbrock's function:
全局极小点${x^ * } = (1.0000, 1.0000), $全局最小值${f^ * } =0.$
本文构造了一个连续的无参数填充函数$W(x, {x^ * })$, 它克服了含参数的填充函数在应用时调节参数的麻烦, 提高了实用性, 同时也使的算法的效率得到了提高.将新的填充函数用Matlab编程对一些目标函数进行数值试验, 结果表明该方法对求解全局最优化问题是有效的.
该填充函数算法仍存在缺点, 它要求目标函数只能有有限个局部极小点.其次, 算法的效率还需进一步提高, 下一步工作将在此基础上提高该算法对目标函数的适应性, 构造更高效率的填充函数.