王筱莉， 梁泽亮， 姚奕荣， 郑 权

(上海大学理学院，上海200444)

令X为一个拓扑空间，f：X→R是一个实值函数，D⊂X，考虑如下总极小值问题：

积分水平集方法［1］形成2个序列：

其中序列{ck}和{Hck}是趋于总极小值和总极小值点的集合.

Phu等［2］提出采用均值变差积分来研究可求和函数的基本下确界;邬冬华等［3］在此基础上讨论高阶矩的变差积分;姚奕荣等［4］给出了一般形式变差积分;文献［5］研究了变差积分的分析性质及总极值问题的全局最优性条件;文献［6-7］对变差积分方法进行了完善.而本研究在一般形式变差积分的基础上，构建了不同形式的变差积分并设计了算法，同时运用Monte-Carlo模拟技术，对具有100个变量的总极值问题进行了算法实现及数值试验结果的分析比较.数值试验结果表明，针对同一个问题利用不同类型的变差积分算法来计算，效果具有一定的差异性，但同时也有各自的优势.

1 丰满集、丰满函数和Q-测度空间

下面总结关于积分型总极值问题的一些基本概念和性质［8-10］.

1.1 丰满集和丰满函数

令X是一个拓扑空间，若X的一个子集D满足

则称D为丰满集，其中cl D表示D的闭包，int D表示D的内部.

一个丰满集合包含了这个集合的丰满点.若x∈D且对于 x的任意一个邻域 N(x)，有 N(x)∩int D≠Ø，则称x是D的丰满点.一个集合D是丰满的当且仅当D中每一点都是丰满点.x∈D是集合D的丰满点当且仅当存在一个序列{xλ}⊂int D，使得xλ→x.

非空丰满集合的内部是非空的，丰满集合的并集是丰满的，2个丰满集合的交可能是非丰满的，但是一个开集和一个丰满集合的交是丰满的.集合D是丰满的当且仅当∂D=∂int D，其中∂D=cl Dint D表示集合D的边界.

若集合

对于每个实数c都是丰满的，则称函数f：X→R是上丰满的.

2个上丰满函数的和或乘积可能不是上丰满的，但是一个上丰满函数和一个上半连续函数的和是上丰满的.一个函数f是上丰满的当且仅当f在每一点x都是上丰满的.若x∈Fc且f在x上是上丰满的，则x是f的一个丰满点.

1.2 Q-测度空间以及一些相关假设

为了利用积分途径研究总极值问题，需要引入一类特殊的测度空间，称为Q-测度空间.

令X是一个拓扑空间，Ω是X的子集的一个σ-域，μ是Ω上的测度，则称(X，Ω，μ)为Q-测度空间，且满足下列条件：①X中每个开集都是可测的;②X中非空开集G的测度μ(G)为正，即μ(G)＞0;③X中紧集K的测度μ(K)是有限的.

由于一个非空开集的内部是非空的，包含非空丰满集的可测集的Q-测度总是正的，这是在最小化的积分型途径中所必需的性质，因此，通常需要作以下假设.

(A)：f是下半连续的(l.s.c.)，并且X是下紧的.

(M)：(X，Ω，μ)是一个Q-测度空间.

(R)：f是一个可测的上丰满函数.

2 变差积分及其性质

定义1 令φ：R1→R1是一个严格递增的连续函数，而且φ(0)=0.f的变差积分形式为

式中，Vφ(c)是关于x在Hc∩D上的积分.

性质1 变差积分Vφ(c)有如下性质：

(1)Vφ(c)＞0，∀c＞c*;

(2)Vφ(c)=0，∀c＜c*;

(3)Vφ(c)在(－∞，+∞)上是非递减的，且在(c*，∞)上严格递增;

(4)Vφ(c)是连续的.

定理1 假定φ在(－∞，+∞)上是可微的，而且φ'(0)=0，那么积分Vφ(c)在(－∞，+∞)上是可微的，而且

Vφ(c)是凸的.

定理2 在(A)，(M)和(R)的假设下，c*为总极小值当且仅当cn↓c*，

以上性质和定理的具体证明可参见文献［8］.

3 3种变差积分的构造

3.1 双曲变差积分

3.2 分式变差积分

3.3 三角变差积分

令φ3(x)=x－arctan x是一个严格递增连续函数，而且φ3(0)=0.构造f的三角变差积分如下：

注：可验证上述3种类型的变差积分满足一般变差积分的性质定理.

4 算法的实现

下面介绍变差积分型总极值算法的实现过程.

4.1 Monte-Carlo实现

假设约束集D是在Rn上的一个投点区域，

f是一个下半连续且上丰满的目标函数，并且有唯一的总极小值点x*∈D.换言之，对于一个递减的收敛到总极值c*的数列{ck}，水平集的大小满足

有

式中，Dk是包含水平集Hck∩D的最小图投点区域.

这样，就是计算Vφ(ck;Dk)和V'φ(ck;Dk)而不是计算Vφ(ck;D)和V'φ(ck;D).

在每次迭代中，试图找到Dk来替代水平集Hck，其中

为了执行算法，需要计算积分Vφ(ck)和V'e(ck).下面用Monte-Carlo技术来具体实现.

(1)c0和Hc0的逼近.设ξ=(ξ1，ξ2，…，ξn)是一个均匀分布在区间［0，1］n上的n维随机数.设

则x=(x1，x2，…，xn)均匀分布在D上.

取km个子样本，并在样本点上计算函数值f(xj)，j=1，2，…，km.比较这些点上的函数值，得到一个样本点的集合W，其中包括对应的t个最小函数值点FV［j］，j=1，2，…，t.将其按函数值大小排序，即为

称集合W为接受集，并将其看作是水平集Hc0的逼近，其中c0=FV［1］是{FV［j］}中最大的一个，称正整数t为统计指标.可以看出，对于任意点 x∈W，f(x)≤c0.

此外，f在水平集Hc0上的Vφ(c0)和V'φ(c0)可以由以下方式来逼近，即

设

(2)由W产生一个新的投区域.用统计方法产生的投点n维区域为

假设在W中的随机样本为τ1，τ2，…，τt.令

其中

将

作为估计来产生ai和bi，i=1，2，…，n.

(3)继续迭代过程.从新的区域D1中去样本点.取一随机子样本x=(x1，x2，…，xn)∈D1，其中

计算f(x)，如果f(x)≥ck，则丢弃样本点;否则，更新集合FV［j］和W，最后使得FV［j］是最小的点.对接受集W作相应的更新.重复这个过程直到FV［1］≤c1，得到新的FV和W.

(4)迭代解.每次迭代，都可将集合FV［j］中的最小FV［t］及W中对应的点看作是迭代解.

(5)收敛辨别.每次迭代，用Monte-Carlo方法来计算变差积分Vk和V'k.令

如果λk小于给定的精度ε，则迭代终止.可将步骤(4)中的迭代解作为总极小值和总极小值点的逼近.

5 数值试验

下面主要考虑一类无约束或盒箱约束的总极小值问题.分别结合上述3类变差积分，运用Monte-Carlo技术可得以下数值结果.

当n=20，40，60，80，100时，采用分式变差积分算法和三角变差积分算法求解问题1得到的计算结果如表1和表2所示.采用双曲变差积分算法求解问题1的一些数值结果是数据溢出.

表1 分式变差积分算法求解问题1的一些数值结果Table 1 Numerical results of the problem 1 with fraction deviation integral method

表2 三角变差积分算法求解问题1的一些数值结果Table 2 Numerical results of the problem 1 with trigonometry deviation integral method

表1和表2的数据表明：①采用分式变差积分算法解决问题1时，迭代次数较少;② 采用双曲变差积分算法解决问题1时，一旦数值过大就会遇到指数数据溢出的情况，所以在选用时要慎重;③数据较多时，采用三角变差积分算法计算累积量较小.

问题2

D={(x1，x2，…，xn)∈Rn：－10.0≤xi≤10.0，i=1，2，…，n}.解x*=(0，…，0)，f*=0.

当n=20，40，60，80，100时，采用3种类型变差积分算法求解问题2得到的计算结果如表3～表5所示.

表3 双曲变差积分算法求解问题2的一些数值结果Table 3 Numerical results of the problem 2 with hyperbolic deviation integral method

表4 分式变差积分算法求解问题2的一些数值结果Table 4 Numerical results of the problem 2 with fraction deviation integral method

表5 三角变差积分算法求解问题2的一些数值结果Table 5 Numerical results of the problem 2 with trigonometry deviation integral method

表3～表5的数据表明：①采用双曲变差积分算法解决问题2时迭代次数最少，但计算结果的精度不高;②采用分式变差积分算法时迭代次数要少于三角变差积分算法;③ 数据较多时，采用三角变差积分算法计算累积量较少.

6 结束语

以上算例说明了本研究给出的3类变差积分算法是可行且有效的，但是各算法之间也存在差异.具体地说：①对于双曲变差积分算法，其计算的迭代次数较少，当数据量较大时，函数值的计算累积量并不大，但是当数据值比较大时可能容易造成数据溢出，且计算精度不够高;②对于分式变差积分算法，其计算的迭代次数较少，但是当数据量较大时，其函数计算累积量是三种算法中最大的，所以当计算数据规模较大时，其消耗时间也较多;③对于三角变差积分算法，其计算的迭代次数适中，当数据量较大时，函数值的计算累积量比分式变差积分算法要小，且计算耗时相对适中.

由于上述各类变差积分算法的差异性和优劣性，因此，在利用变差积分算法时应该注意针对不同的问题选择不同的算法.本研究就是通过设计变差积分算法来求解不连续、无约束总极值问题的.而对于约束的，特别是离散的总极值问题还需作进一步研究.

［1］ CHEWS H，ZHENGQ.Integral global optimization：theory，implementation and applications［M］.Berlin：Springer-Verlag，1988.

［2］ PHUH X，HOFFMANNA.Essential supremum and supremum of summable functions［J］.Numer Funct Anal and Optimiz，1996，17(1/2)：167-180.

［3］ WUD H，WUW Y，ZHENGQ.A sufficient and necessary condition for global optimization［J］.Applied Mathematics Letters，2010，23(1)：17-21.

［4］ YAOY R，CHENL，ZHENGQ.Optimality condition and algorithm with deviation integral for global optimization［J］.Journal Mathematical Analysis and Applications，2009，357：371-384.

［5］ PARDALOSP M，ROMEIJNH E，TUYH.Recent developments and trends in global optimization［J］.J Comp and Appl Maths，2000，124：209-228.

［6］ TIANW W，WUD H，ZHANGL S，et al.Modified integral-level set method forthe constrained global optimization［J］.Applied Mathematics and Mechanics，2004，25(2)：202-210.

［7］ 邬冬华，田蔚文，张连生，等.一种修正的求总极值的积分-水平集方法的实现算法收敛性［J］.应用数学学报，2001，24(1)：100-110.

［8］ SHIS Z，ZHENGQ，ZHUANGD M.Discontinuous robust mapping are approximatable［J］.Trans Amer Math Soc，1995，347：4943-4957.

［9］ ZHENGQ.Robust analysis and global minimization of a class of discontinuous functions(Ⅰ)and(Ⅱ)［J］.Acta Mathematicae Applicatae Sinica：English Ser，1990，6(3)：205-223，317-337.

［10］ ZHENGQ.Robust analysis and global optimization［J］.International J Computers and Mathematics with Applications，1991，21(6/7)：17-24.