一类求全局最小点的填充函数及其算法

收稿日期:2011-12-04;修回日期:2012-03-09 作者简介:姚桂霞(1988-) ,女,甘肃庆阳人,硕士研究生,研究方向 为全局优化理论与算法;叶仲泉,教授,博士,研究方向为最优化理 论与算法、控制论、人工神经网络。 一类求全局最小点的填充函数及其算法 姚桂霞,叶仲泉,马　 雪 (重庆大学 数学与统计学院,重庆 401331) 摘　 要:填充函数法是求解全局最优化问题的一种重要的方法,其关键之一在于构造一类性质良好的填充函数。 文中基 于填充函数的严格定义,针对全局优化问题 (P0):minx∈Rn f(x),在目标函数 f(x) 满足一定条件的基础上,提出了一类求其全 局最小解的填充函数,并在适当的假设条件下,研究证明了该函数的填充性质和其他的分析性质,并按照这些相关性质设 计了相应的填充函数算法。 该函数形式简单,便于计算。 最后,还进行了数值试验测试,结果 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明,该函数是可行的,算法 是有效的。 关键词:填充函数;全局优化;全局最小点;局部极小点 中图分类号:TP301. 6　 　 　 　 　 　 文献标识码:A　 　 　 　 　 　 　 文章编号:1673-629X(2012)08-0096-04 A Class of Filled Function for Solving Global Minimum Point and Its Algorithm YAO Gui-xia,YE Zhong-quan,MA Xue (College of Mathematics and Statistics,Chongqing University,Chongqing 401331,China) Abstract:Filled function method is a kind of important method for solving global optimization problem and the key of the method is to construct a filled function with good properties. Based on the strict definition of filled function and certain conditions the objective func- tion f(x) meets,construct a class of novel filled function with simple form and easy to calculate for global optimization problem (P0)： min x∈Rn f(x) ,study and prove filled properties and other analysis properties of the function in the appropriate assumptions. Besides,according to the related properties,design the corresponding algorithm for filled function. Finally,the numerical experiment shows that the function is feasible and the algorithm is effective. Key words:filled function;global optimization;global minimum;local minimum 0　 引　 言 在现实生活中,全局优化问题具有广泛的应用,尤 其是在科学计算、经济工程、生物科学等方面。 最近几 年,全局优化在理论和实践方面做出了很多进展,对于 求解全局优化的算法也是有很多。 这些算法大致可以 分为两类,即确定性算法和随机性算法,其中填充函数 法属于确定性算法。 填充函数法最早是由 Ge 提出的为了解决多变量 函数的极小解问题,它的基本思想是构造一个辅助函 数,即填充函数(有些学者也在此基础上提出了类似 的另一些辅助函数,例如文献[1]的 F-C 函数),这个 函数在目标函数 f(x) 的初始极小点 x1 * 处取得极大 值,在比 f(x)的极小点高的任何盆域[2] 里没有极小点 或鞍点;但在比 f(x) 的极小点低的盆域里一定存在极 小点或鞍点,最早由很多学者[2 ~ 12]提出的许多填充函 数有含有两个参数的、一个参数的,很多由于参数的选 择比较困难和麻烦,比如 Ge[2,3]给出的填充函数由于 有两个参数需要调整使得填充函数的算法效率降低, 又由于因子 e - ‖x-x*‖2 ρ2 的存在,当‖x - x*‖2很大而 ρ2 很小时, P(x,x*,r,p) 和 ÑP(x,x*,r,p) 接近于 0 和 零向量,可能找到假的平稳点或者丢失目标函数的极 值点,求得填充函数的极小点的算法也难以实现。 在 此,文中给出了一种比较简单的填充函数,函数中只包 含因子 arctan(·),由于它良好的性质,使其算法的效 果较好,效率比较高。 1　 基本概念 文中主要考虑无约束优化问题。 (P0):min x∈Rn f(x) (1) 假设条件如下: 第 22 卷　 第 8 期 2012 年 8 月 　 　 　 　 　 　 　 　 　 　 计 算 机 技 术 与 发 展 COMPUTER TECHNOLOGY AND DEVELOPMENT 　 　 　 　 　 　 　 　 　 　 Vol. 22　 No. 8Aug. 　 2012 (H1) f(x) 在 R n 上是连续可微的; (H2) f(x) 的极小点的个数可以有无穷多个,但 是它的极小值应该是有限个;记 Y为问题(P0) 的所有 极小点的集合,则 F = f(x) | x ∈{ }Y 是有限集。 (H3) f(x) 是强制性函数,即 lim‖x‖→¥f(x) = + ¥则问 题 (P0) 等价于 (P):min x∈Ω f(x) (2) 其中 Ω ⊆ Rn 是有界闭域。 定义 1[5] 　 域 B* ⊂Ω称为问题(P0) 的关于一个 局部极小点 x* 的 G-盆谷,具有如下性质: (1) x* ∈ B* ,且对于任意的 x ∈ B* , f(x) ≥ f(x*) 成立; (2) x - ∈ B* 是问题(P0) 的局部极小点当且仅当 f(x - ) = f(x*) 。 定义 2[4] 　 设 x1 和 x2 是 f(x) 的两个局部极小 点。 如果 f(x2) ≥ f(x1),则称局部极小点 x2 高于局部 极小点 x1,或局部极小点 x1 低于局部极小点 x2。 如果 f(x2) = f(x1),则称局部极小点 x1 和 x2 是同样高度的。 设 x*是问题(P0)的一个局部极小点,B *是 x*的 一个 G-盆谷, L是问题(P0) 的低于 x * 所有局部极小 点的集合,即 L(x*) = {x ∈ Y f(x) < f(x* }) (3) 定义 3[5] 　 函数 P(x,x*) 称为问题(P0) 在极小 点 x* 处的填充函数,函数满足如下性质: (1) x* 是 P(x,x*) 的一个严格局部极大点; (2)对于任意 x满足 f(x) ≥ f(x*),且 x≠ x*,x不 是函数 P(x,x*) 极值点或鞍点,即ÑP(x,x*) ≠ 0; (3)如果 x* 不是问题 (P0) 的全局极小点,即 L(x*) ≠∅,则对任意的 x - ∈ L(x*),x - 是 P(x,x*) 的 局部极小点,而且进一步满足 P(x - ,x*) < P(x*,x*), 且对于任意的 x ∈ ∂Ω,都有 P(x - ,x*) < P(x,x*),其 中 ∂Ω是 Ω的边界; (4)对任意的 x1,x2 ∈ Ω ,满足 f(x1) ≥ f(x *), f(x2) ≥ f(x *) ,则‖x2 - x *‖ > (≥)‖x1 - x *‖当 且仅当 P(x2,x *) < (≤)P(x1,x *) 。 2　 一类填充函数 针对问题 (P0), 设 x * 是当前局部极小点, 构造 填充函数如下: H(x,x*) = - q{arctan ‖x - x*‖2 · φr( f(x) - f(x*)) - arctan[min(1,1 + f(x) - f(x *) q )]} (4) 其中 φr( f(x) - f(x *)) = 1 f(x) - f(x*) ≥ 0 1 r [ f(x) - f(x *)] + 1 - r < f(x) - f(x*) < 0 0 f(x) - f(x*) ≤- r ì î í ï ï ï ï 　 (5) q > 0,r > 0是参数,设 S1 = {x | f(x) > f(x *)}, S2 = {x | f(x) < f(x *)} 且 β0 = miny1,y2∈F y1≠y2 y1 - y2 。 下面用几个定理说明 H(x,x*) 是满足定义 3 的 一类填充函数。 定理 1　 对∀q > 0,r > 0,若 x*是 f(x)的局部极 小点,则 x* 是 H(x,x*) 的一个严格的极大值点。 证:因为 H(x*,x*) = qarctan1 = π4 q ,又∃δ > 0, 对∀x ∈ N0(x*,δ) ∩ S1,有 f(x) > f(x *) ,则 H(x,x*) = - q[arctan ‖x - x*‖2 - π4 ] = π 4 q - qarctan ‖x - x*‖2 < H(x*,x*) 所以,对∀x ∈ N0(x*,δ) ∩ S1,当 x ≠ x * 时, x* 是 H(x,x*) 的一个严格极大值点, ∀q > 0,r > 0。 证毕 对∀x ∈ Ω ,定义 d(x) = x - x* 。 定理 2　 f(x) 是 Rn 上的连续可微函数,对∀x ∈ S1 且 x≠ x *,x不是 H(x,x*)的稳定点,且对∀q > 0, r > 0,ÑΤH(x,x*)·d(x) < 0。 证 明: H(x,x*) = - q{arctan ‖x - x*‖2 · φr( f(x) - f(x *)) - arctan[min(1,1 + f(x) - f(x*) q )]} 因为 x∈ S1,即 f(x) > f(x *) ,所以 H(x,x*) = - q[arctan ‖x - x*‖2 - π4 ], Ñ H(x,x *) = - q · 2(x - x*) 1 + ‖x - x*‖4 因为 x≠ x*,q > 0,所以ÑH(x,x*) ≠0,即 x*不 是 H(x,x*) 的稳定点,且 ÑΤH(x,x*)·d(x) = - q· 2 ‖x - x *‖2 1 + ‖x - x*‖4 < 0 定理 3　 若 f(x) 是连续可微的,且满足强制性条 件,即当‖x‖→ ¥时,f(x) →+ ¥。 若 x*不是原问题 的最小点,即 L(x*) ≠ ∅,则对 ∀x - ∈ L(x*),∀q > 0,x - 是 H(x,x*) 的一个局部极小点,且满足 H(x - ,x*) < H(x*,x*),H(x - ,x*) < H(x,x*),∀x∈∂Ω,当 r≤ β0 2 时。 证明:因为 β0 = miny1,y2∈F y1≠y2 y1 - y2 且 L(x *) ≠ ∅,则 ·79·　 第 8 期　 　 　 　 　 　 　 　 　 　 　 姚桂霞等:一类求全局最小点的填充函数及其算法 对∀x - ∈ L(x*),有 f(x*) - f(x - ) ≥ β0,则 f(x - ) - f(x*) ≤- β0 ≤- 2r < - r,因为 f(x)连续,则∃x - 的邻 域 N(x - ,δ0) = {x ∈ R n | ‖x - x - ‖ < δ0},对于 ∀x ∈ N(x - ,δ0),有 f(x) - f(x *) < - r,因此有 φr( f(x) - f(x*)) = 0,∀x∈ N(x - ,δ0);又因为 x - 是 f(x)的局部极 小点,则∃x - 的邻域 N(x - ,δ1) = {x ∈ R n | ‖x - x - ‖ < δ1},则对 ∀x ∈ N(x - ,δ1), 有 f(x) > f(x - ), 取 δ = min{δ0,δ1},则对于∀x ∈ N(x - ,δ) ,有 H(x,x*) = q·arctan(1 + f(x) - f(x *) q ) ≥ q· arctan(1 + f(x - ) - f(x*) q ) = H(x - ,x*) 则 x - 是 H(x,x*) 的一个局部极小点,且 H(x - ,x*) = q·arctan(1 + f(x - ) - f(x*) q ) < q· arctan1 = π4 q = H(x *,x*) 定理 4 　 对∀ x1,x2 ∈ Ω,满足 f(x1) ≥ f(x *), f(x2) ≥ f(x *);‖x2 - x *‖ > (≥)‖x1 - x *‖,当且 仅当 H(x2,x *) < (≤)H(x1,x *),∀q > 0,r > 0。 证明:对∀ x1,x2 ∈ Ω,因为 f(x1) ≥ f(x *),f(x2) ≥ f(x*) ,则有 H(x1,x *) = - q[arctan ‖x1 - x *‖2 - π4 ] = π4 q - q·arctan ‖x1 - x *‖2 H(x2,x *) = - q[arctan ‖x2 - x *‖2 - π4 ] = π4 q - q·arctan ‖x2 - x *‖2 又因为‖x2 - x *‖ > (≥)‖x1 - x *‖⇔ arctan ‖x2 - x *‖2 > (≥)arctan‖x1 - x *‖2⇔ H(x2,x *) < (≤)H(x1,x *) 。 由以上这几个定理可以得知,式(4)满足填充函 数的定义 3,所以是填充函数。 3　 填充函数的算法 步 1,选取充分小的正数 μ > 0,ε > 0(ε < μ) 作 为最小化问题的终止参数,选择 M > 0 为参数 q 的上 界,取 k0 ≥2n,其中 n为变量的维数;取单位向量{ei}, i = 1,…,k0,使得 ei在单位球 B = {x∈ R n | ‖x‖ = 1} 上,给定初始点 x01 ∈Ω,初始值 q0 ≥1且 r0 ≤1,k: = 1; 步 2,从 x0k 处开始用某一搜索方法寻找原问题 min x∈Ω f(x) 的局部极小点 x*k ,取一个正数 δ0 > 0,让 δ: = δ0, i: = 1; 步 3,令 x*k = x * k + δei ,若 f(x * k ) < f(x * k ) ,则 x 0 k+1: = x*k , k: = k + 1,转步 2;否则,转步 4; 步 4, 构 造 填 充 函 数 H(x,x*) = - q{arctan ‖x - x*‖2·φr( f(x) - f(x *)) - arctan[min(1,1 + f(x) - f(x*) q )]} 从初始点 x*k 开始用局部搜索方法解问题 min x∈Ω H(x,x*) 。 若此问题的解在 ∂Ω上得到,则转步 5; 否则,若以下条件之一在某一点 y*k ∈ Ω上成立: (1) (y*k - x * k ) Τ ÑH(y*k ,x * k ) ≥ 0; (2) f(y*k ) < f(x * k ) ; (3) ‖ ÑH(y*k ,x * k )‖ ≤ ε 。 则令 x0k+1: = y * k , k: = k + 1,转步 2;否则,在 Ω上 继续极小化 H(x,x*) ; 步 5,若 q < M ,则增加 q (例:让 q: = 10q ),转步 3,否则让 q: = q0,转步 6; 步 6,若 δ > μ ,则减少 δ (例:让 δ: = δ2 ),让 q: = q0,转步 3;否则,让 q: = q0, δ: = δ0,转步 7; 步 7,若 i < k0,则 i: = i + 1,转步 2;否则,转步 8; 步 8,若 r > μ ,则减少 r (例:让 r: = r10 ),让 i: = 1,q: = q0,δ: = δ0,转步 3;否则停止, x * k 就是问题的全 局极小解。 4　 算　 例 使用 Matlab(R2009a)软件进行计算, 使用 Fmin- con函数求 f(x) 的极值, 使用 Fminunc 函数求 H(x, x*) 的极值。 算例 1　 6-Hump back camel( n = 2)函数: f(x) = 4x21 - 2. 1x 4 1 + 1 3 x 6 1 - x1x2 - 4x 2 2 + 4x 4 2 - 3 ≤ x1,x2 ≤3 文献[2]中 Ge 给出的全局最优解为 x* = (0. 0898,0. 7127) 或( - 0. 0898, - 0. 7127) ,全局最优值 为 f(x*) = - 1. 0316,但是在利用文中的算法下通过一 次迭代得到的全局最优解为 x* = ( - 0. 0898, - 0. 7129) ,目标函数值为 f(x*) = - 1. 0316, 与 Ge 的一 致。 算例 2　 Rastrigin( n = 2)函数: f(x) = x21 + x 2 2 - cos(18x1) - cos(18x2) - 1 ≤ x1,x2 ≤1 Yang 等给出的全局最优解为 x* = (0． 0000, 0． 0000) ,最优值为 f(x*)= - 2. 0000,而利用文中算法 ·89·　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 计算机技术与发展　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 　 第 22 卷 得到的全局最优解为 x* = (1. 0e - 005*0. 9583,1. 0e - 005*0. 9583),最优值为 f(x*) = - 2. 0000,与 Yang 等的一致, 算法是有效的。 算例 3　 Treccanifunction ( n =2): f(x) = x41 + 4x 3 1 + 4x 2 1 + x 2 2 　 - 3 ≤ x1,x2 ≤3 文献[6]给出的全局最小解为 x* =(0. 00000466, 0. 00000000) T, 全局最小值为 f(x*) = 8. 67710185 e-11,而利用文中算法得到的全局最小解为 x* =1. 0e- 004*(0. 0960, 0. 4020),全局最小值 f(x*) = 1. 9857e -009,与文献中的结果一致。 5　 结束语 文中基于全局优化问题的 (P0)： min x∈Rn f(x) ,提出 了一类求解其最小值的填充函数法,讨论并证明了该 函数的填充性质和其他一些分析性质,并在其理论基 础上为其设计了算法。 理论分析和数值试验表明,该 函数是可行的,算法是有效的,收敛速度比较快,精度 相对比较高。 参考文献: [1]　 杨军君,叶仲泉. 一类求解全局优化问题的 F-C 函数法 [J].计算机技术与发展,2009,19(7):124-126. [2]　 Ge R P,Qin Y F. A class of filled functions for finding a glob- al minimizers of a function of several variables[J]. Journal of Optimization Theory and Applications,1987,54 (2 ):241 - 252. [3]　 Ge R. A filled function method for finding a global minimizer of a function of several variables[J]. Math. Program,1990,46 (1-3):191-204. [4]　 Zhang L S,Ng C K,Li Duan,et al. A new filed function meth- od for global optimization[ J]. Global Optimization,2004,28 (1):17-43. [5]　 Wu Z Y,Lee H W J,Zhang L S,et al. A novel filled function method and quasi-filled function method for global optimiza- tion[J]. Comput. Optim. Appl. ,2005,34(2):249-272. [6] 　 Wang C J,Yang Y J,Li J. A new filled function method for unconstrained global optimization[J]. Journal of Computation- al and Applied Mathematics,2009,225(1):68-79. [7]　 Lin Youjiang,Yang Yongjian. Filled function method for non- linear equations [ J]. Journal of Computational and Applied Mathematics,2010,234(3):695-702. [8]　 刘　 津,叶仲泉. 一类新的寻求全局最优解的填充函数 [J].计算机技术与发展,2010,20(6):36-38. [9]　 杨军君,叶仲泉.求解全局优化问题的填充函数算法[ J]. 运筹与管理,2011,20(1):8-11. [10] 贺素香,陈未来.一个求解无约束优化问题的填充函数算 法[J].浙江大学学报(理学版),2011,38(2):144-149. [11] 张玉芬,张群峰,王永军,等.用于全局优化的一种新辅助 函数及其性质[J].河北大学学报(自然科学版),2011,31 (1):7-11. [12] 梁玉梅,李铭明,迟东璇.全局优化问题的一个单参数填充 函数方法[J].运筹学学报,2009,13(4): 췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍췍 102-108. (上接第 95 页) 参考文献: [1]　 尹　 璐,何晓光,毋立芳,等.多用途人脸识别系统的设计 与实现[J].计算机工程与应用,2007,43(20):225-228. [2]　 梁路宏,艾海舟,徐光佑,等. 人脸检测研究综述[ J]. 计算 机学报,2002,23(5):449-458. [3]　 Yang Jie,Lu Weier,Waibel A. Skin color modeling and adap- tation[C] / / Proc of the 3rd Asian Conference on Computer Vision. London:Spring-Verlag,1998:687-694. [4]　 Craw I,Ellis H,Lishman J. Automatic Extraction of Face Fea- tures[J]. Pattern Recognition Letters,1987,5(2):183-187. [5]　 廖学锋,陈雷霆,阂　 帆,等.基于粗糙集与肤色模型的人 眼定位算法[J].计算机应用,2007,27(S1):125-126. [6]　 梁路宏,艾海舟,何克忠. 基于多模板匹配的单人脸检测 [J].中国图象图形学报,1999,4(10):825-830. [7]　 陈茂林,戚飞虎. 自组织的隐马尔可夫模型的人脸检测研 究[J].计算机学报,2002,25 (11):1165-1169. [8]　 Li J,Najmi A,Gray R M. Image classification by a two dimen- sional hidden Markov model[J]. IEEE Transactions on Signal Processing,2000,48(2):517-533. [9]　 Karungaru S,Fukumi M,Akamatsu N. Human Face Detection in Visual Scenes Using Neural Networks[ J]. Transaction of Institute of Electrical Engineers of Japan (IEEJ),2002,122c: 995-1000. [10] Cauwenberghs G,Poggio T. Incremental and decremental sup- port vector machine learning[C] / / Advances in Neural Infor- mation Processing Systems. Cambridge MA:MIT Press,2000: 409-415. [11] 武　 勃,黄　 畅,艾海舟,等.基于连续 Adaboost 的多视角 人脸检测[ J]. 计算机研究与发展,2005,42 (9):1612 - 1621. [12] 王　 晶,杨　 煜.基于边缘方向直方图的 Adaboost 人脸检 测[J].计算机技术与发展,2007,17(12):5-7. [13] 尹　 飞,冯大政.基于 PCA算法的人脸识别[J].计算机技 术与发展,2008,18(10):22-24. [14] Jain A K. Face Detection in Color Image[ J]. IEEE Trans on PAML,2002,23(5):696-786. [15] Meynet J. Fast face detection using adaboost pattern recogni- tion[EB / OL]. 2003-07-16. http: / / ftp. ut-cluj. ro / pub / us- ers / nedevschi / AV / References / B3. Face% 20 detection / Mey- net 2003-923. pdf. [16] Vezhnevets V,Sazonov V,Andreeva A. A Survey on Pixel - based Skin Color Detection Techniques[C] / / Proceedings of Graphicon-2003. [s. l. ]:[s. n. ],2003:85-92. ·99·　 第 8 期　 　 　 　 　 　 　 　 　 　 　 姚桂霞等:一类求全局最小点的填充函数及其算法 一类求全局最小点的填充函数及其算法 作者： 姚桂霞， 叶仲泉， 马雪 作者单位： 重庆大学数学与统计学院,重庆401331 刊名： 计算机技术与发展 英文刊名： Computer Technology and Development 年，卷(期)： 2012(8) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_wjfz201208027.aspx