数学杂志  2014, Vol. 34 Issue (4): 773-778   PDF    
扩展功能
加入收藏夹
复制引文信息
加入引用管理器
Email Alert
RSS
本文作者相关文章
李博
鲁殿军
全局最优化问题的一个无参数的填充函数算法
李博, 鲁殿军    
青岛科技大学数理学院, 山东 青岛 266061
摘要:本文研究了全局最优化问题.利用构造填充函数的方法, 提出了一个新的无参数填充函数, 它是目标函数的一个明确表达式.得到了一个新的无参数填充函数算法, 数值试验结果表明该填充函数算法是有效的, 从而推广了填充函数算法在求解全局最优化问题方面的应用.
关键词非线性规划    全局最优化    确定性算法    填充函数    
A PARAMETER-FREE FILLED FUNCTION METHOD FOR GLOBAL OPTIMIZATION
LI Bo, LU Dian-jun    
College of Math. and Physics, Qingdao University of Science and Technology, Shandong 266061, China
Abstract: In this article, we study the global optimization problem.By using the method of constructing filled function, we propose a new parameter-free filled function that is a clear expression of the objective function, and get a new non-parameter filled function algorithm.Numerical experiments show that the filled function algorithm is effective, which generalizes filled function algorithm in solving global optimization problems in the application.
Key words: nonlinear programming     global optimization     deterministic method     filled function    
1 引言

填充函数法由葛仁溥教授在1990年提出, 是求解全局最优化问题的一种确定性算法.实践表明它是求解全局最优化问题的一种有效方法.在社会生产中遇到的许多实际问题都可以转化为全局最优化问题.因此, 对它的研究有着重要的理论和实际应用意义.

文献[1]中给出了一个带两个参数的填充函数

$ \begin{equation} p(x_{1}^{\ast }, x, r, \rho )=\frac{1}{r+f(x)}\exp \left( {-\frac{\left\| {x-x_{1}^{\ast } } \right\|^{2}}{\rho^{2}}} \right). \end{equation} $ (1.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]给出了一个只含有一个参数的填充函数

$ \begin{equation} H(x, x_{1}^{\ast }, a)=\frac{1}{\ln [1+f(x)-f(x_{1}^{\ast } )]}-a\left\| {x-x_{1}^{\ast } } \right\|^{2}, \end{equation} $ (1.2)

其中参数$a$应充分大.该填充函数比$(1.1)$在效率上有了一定提高, 但仍存在参数的选取问题.文献[4]给出了一无参数填充函数

$ \begin{equation} F(x, x_{1}^{\ast } )=\frac{1}{(\left\| {x-x_{1}^{\ast } } \right\|+1)}\psi (f(x)-f(x_{1}^{\ast } )), \end{equation} $ (1.3)

其中

$ \psi (t)=\left\{ {{\begin{array}{*{20}c} {1, } \hfill&{t\geq 0.} \hfill \\ {0, } \hfill&{t<0.} \hfill \\ \end{array} }} \right. $

数值试验表明填充函数$(1.3)$是有效的.由于不需要调整参数, 提高了运算效率.但$F(x, x_{1}^{\ast} )$不是关于目标函数$f(x)$的明确表达式.

本文研究了以上填充函数, 为克服其存在的缺陷, 构造了一个无参数的填充函数, 该填充函数具有关于目标函数$f(x)$的明确表达式.进行了数值试验.

2 全局优化模型和填充函数定义

关于填充函数的盆地和山头的定义详见参考文献[1].

本文考虑如下全局无约束最优化问题

$ \begin{equation} \min \limits_{x\in R^{n}} f(x), \end{equation} $ (2.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 }$处的一个填充函数.

3 无参数填充函数

构造填充函数:

$ W(x, x^{\ast })=-[\arctan (e^{(f(x)-f(x^{\ast }))}-1)]\left\| {x-x^{\ast }} \right\|^{2}, $

其中$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, x^{\ast })=-[\arctan (e^{(f(x)-f(x^{\ast }))}-1)]\left\| {x-x^{\ast }} \right\|^{2}<0, $

又因为$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}$, 则

$ \nabla W(x, x^{\ast })=-\frac{e^{f(x)-f(x^{\ast })}}{1+[e^{f(x)-f(x^{\ast })}-1]^{2}}\left\| {x-x^{\ast }} \right\|^{2}\nabla f(x)-2[\arctan (e^{(f(x)-f(x^{\ast }))}-1)](x-x^{\ast }). $

$x\ne x^{\ast }$$f(x)>f(x^{\ast })$可知

$ \frac{e^{f(x)-f(x^{\ast })}}{1+[e^{f(x)-f(x^{\ast })}-1]^{2}}\left\| {x-x^{\ast }} \right\|^{2}>0$,$\arctan (e^{(f(x)-f(x^{\ast }))}-1)>0. $

因为$f(x)$$R^{n}$上连续可微, 所以由泰勒公式展开得

$ f(x^{\ast })=f(x)+(x^{\ast }-x)^{T}\nabla f(x)+o(\left\| {x^{\ast }-x} \right\|), $

所以$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)+o(\left\| {x^{\ast }-x} \right\|)<0. $

$(x^{\ast }-x)^{T}\nabla f(x)<0$。所以, $(x-x^{\ast })^{T}\nabla f(x)=-(x^{\ast }-x)^{T}\nabla f(x)>0$, 所以

$ (x-x^{\ast })^{T}\nabla W(x, x^{\ast })=-\frac{e^{f(x)-f(x^{\ast })}}{1+[e^{f(x)-f(x^{\ast })}-1]^{2}}\left\| {x-x^{\ast }} \right\|^{2}(x-x^{\ast })^{T}\nabla f(x)\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;- 2[\arctan (e^{(f(x)-f(x^{\ast }))}-1)]\left\| {x-x^{\ast }} \right\|^{2}. $

此定理证明了:当$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(\overline {x_{0}^{\ast } }, x^{\ast })=-[\arctan (e^{(f(\overline {x_{0}^{\ast } } )-f(x^{\ast }))}-1)]\left\| {\overline {x_{0}^{\ast } } -x^{\ast }} \right\|^{2}>0. $

易得$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^ * })$满足填充函数的定义.

4 算法和数值试验

本文对文献[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.$

表 1 计算结果

(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.$

表 2 计算结果

(3) 3-hump back camel function:

$ \begin{array}[t]{c} f(x) = 2x_1^2 - 1.05x_1^4 + x_1^6/6 - {x_1}{x_2} + x_2^2, \\ s.t. - 3 \le {x_1}, {x_2} \le 3 \end{array} $

全局极小点${x^ * } = (0, 0), $全局最小值${f^ * } =0.$

表 3 计算结果

(4) Simplified Rosenbrock's function:

$ \begin{array}[t]{c} f(x) = 0.5{(x_1^2 - {x_2})^2} + {({x_1} - 1)^2}, \\ s.t. - 3 \le {x_1}, {x_2} \le 3 \end{array} $

全局极小点${x^ * } = (1.0000, 1.0000), $全局最小值${f^ * } =0.$

表 4 计算结果
5 结语

本文构造了一个连续的无参数填充函数$W(x, {x^ * })$, 它克服了含参数的填充函数在应用时调节参数的麻烦, 提高了实用性, 同时也使的算法的效率得到了提高.将新的填充函数用Matlab编程对一些目标函数进行数值试验, 结果表明该方法对求解全局最优化问题是有效的.

该填充函数算法仍存在缺点, 它要求目标函数只能有有限个局部极小点.其次, 算法的效率还需进一步提高, 下一步工作将在此基础上提高该算法对目标函数的适应性, 构造更高效率的填充函数.

参考文献
[1] Ge R P. A filled function method for finding a global minimizer of a function of several variables[J]. Math. Prog., 1990, 46: 191–204. DOI:10.1007/BF01585737
[2] 王鹏, 李博, 王攀. 全局最优化问题的无参数填充函数法[J]. 青岛科技大学学报(自然科学版), 2008, 29(6): 553–556.
[3] Liu Xian. Finding global minima with a computable filled function[J]. J. Global Optimization, 2001, 19: 151–161. DOI:10.1023/A:1008330632677
[4] 茅嘉, 杨勇建. 一个无参数的填充函数算法[J]. 应用数学与计算数学学报, 2010, 24(1): 35–44.
[5] Yang Yongjian, Shang Youlin. A new filled function method for unconstrained global optimization[J]. Appl. Math. Comput., 2006, 173: 501–512.
[6] Yang Yongjian, Liang Yumei. A new discrete filled function algorithm for discrete global optimization[J]. J. Comput. Appl. Math., 2007, 202: 280–291. DOI:10.1016/j.cam.2006.02.032