修正积分水平集方法的随机实现算法.pdfVIP

维普资讯 2006年 12月 应用数学与计算数学学报 第20卷第2期 Dec．．2006 COMM．ON APPL。MATH。AND COMPUT Vo】．20 NO．2 修正积分水平集方法的随机实现算法 余泓 楼烨 。 凌和 良。 沈菁华 1．苏州科技学院应用数学系，苏州， 215009 2．上海科学技术职业学院，上海， 201800 3．南昌工程学院理学系，南昌，330099 摘要：本文提出了一个从随机到确定性的变测度算法，通过对不同的箱子采用不同的 测度，将 Monte-Carlo随机投点与确定性数论方法相结合的策略，使水平值充分地下降． 最后，给出了实现算法收敛性并通过数值实验验证了其有效性． 关键词：积分 一水平集，变测度，一致分布佳点集，随机到确定性 1．引 言 通常一个全局最优化问题可表述为：对于给定的一个 n维空间的紧集DCR ， 和一个连续函数 f：R 一R 上，寻找某一点 ∈D，使得对于一切的 ∈D，满足 f(x) ．厂()．即求下列问题的解： ra i nf() (-1) ∈∈UD 郑权教授于 1978年首次提出求总极值的积分 一水平集算法 1【】【，其思想简明直 观，对 目标函数和约束函数的限制较小，有判别总极值的收敛准则，但其概念算法与 Monte—Carlo随机投点的实现算法不匹配，易失总极值，然后，张连生教授等也提出了 求总极值的离散均值 一水平集算法，并证明了其算法的收敛性．接着邬冬华等人提出 了修正算法，浚算法的构造与概念算法较为吻合，弥补了易失总极值的缺点，并用数 论方法进行数值计算，得到了实现算法的收敛性 ． 在上述研究工作的基础上，本文提出了一种从随机到确定性的变测度积分 ～ 水 平集算法，该算法的优点主要有如下两个方面： 1．由于在实现算法中，每一步迭代都把区域 D分划成 2n+1个箱子，分别在这 2礼+1个子箱里进行投点来构造近似水平集，在每次划分出的2礼+1个子箱中含有不 同程度的最优化信息，我们利用对不同的箱子采用不同的测度方法，使水平值充分下 降． 2．同时在实现算法中调用了Monte—Carlo随机函数选取随机点，使用随机方法避 免了在修正算法中初值由构造佳点集进行数值计算的繁杂性，将初值 co尽量优化， f(x)充分下降后，再使用数论一致分布的确定性方法求解计算并实现终止． 上述两种方法的结合会使修正算法的收敛速度更快，计算效率更高． 本文按如下结构组织：首先定义算法最优性条件；接着给出变测度的概念性算法 及其从随机到确定性的实现算法；最后，给出了实现算法收敛性并通过数值实验验证 了其有效性． 文中我们始终作如下假设： 本文 2006年 1月 12 日收到． 维普资讯 46 应用数学与计算数学学报 20卷 假设 1：，在D上连续． 假设 2：存在一个实数 c，使得水平集 = x∈RnIf(x) c}和D的交集非空而 且紧． 定理 1．1在假设 1和假设2下，如果地(矾)=0，且 ≠ ，其中 = x∈D[f(x) c} m(：1，2，… ，)为Lesbesgue测度，其中L为任意给定的正整数，那么c为 ，在D上 的总极值， 为总极值点集． 证明假设 c不是 ，在 D上的总极值，而 a是总极值．那厶／， C一6=2rl0，令 K=(xlx∈D，y(x)c一叼)，显然K是非空的开集。因为f是连续函数，而且c一叼a 所以有 ≠风 cKc 由测度的性质可知， {( ) ()0这