全局优化问题的最优性条件及其实现算法

丁 译， 程建强， 邬冬华

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

最优化问题存在于现实生活中的许多领域，而最优化方法是人们对实际问题进行建模和分析的重要手段.在分析问题的过程中所抽象出来的优化模型，许多都可以归结为求全局最优解的问题.现有的求解全局优化问题的方法依据收敛性质分为两大类［1］：确定型方法和随机型方法.确定型方法包括区间方法、分支定界方法、填充函数方法、积分水平集算法等;随机型方法包括纯粹随机搜索算法、纯粹更新搜索算法和现代启发式算法(如遗传算法、模拟退火算法)等.

一个全局优化问题可表述如下：

式中，G是Rn上的有界闭区域，f：Rn→R上的连续函数，f*为f(x)在G中的总极小值.20世纪七八十年代，郑权等［2-4］提出了求总极小值的积分水平集算法，并给出了相应的收敛准则.随后，邬冬华等［5-10］对此算法进行了多次修正.该算法的主要思想是在第k步构造一个均值函数

以及水平集

从而得到2个收敛序列{ck}和{Hk}，算法终止条件为水平集上的均方差趋近于0.

本研究受到求总极小值的积分水平集算法及权重思想的启发，考虑n维欧式空间Rn中区域D上的连续函数f(x)的总极大值，建立了一种新的求总极大值的积分水平集算法，并给出了相应的收敛性法则.

对于连续函数f(x)，若有一点x*∈D，对于一切x∈D，满足不等式

则称x*是函数在D上的总极大值点，f(x*)是总极大值.D中所有总极大值点的全体，构成了总极大值点集.

另外，假设对任意x∈D，f(x)≥0;若f(x)＜0，则认为可以通过给f(x)加上一个足够大的常数m＞0，使得f(x)+m≥0.那么，总极大值的问题可表示为

式中，D为Rn中的有界闭集，f：Rn→R上的连续函数，且对任意x∈D，f(x)≥0，f*为f(x)在D中的总极大值.

1 求总极大值的积分水平集算法

给定一个常数c0≥0，使水平集

非空，式(6)的右端表示在D中满足关系式f(x)≥c0的点的全体.设D是有界闭集，若H0是有界闭集，则H0是Rn中的紧集，f(x)在H0上达到极大值.由于对D－H0上的点x，f(x)＜c0，故这个极大值必是总极大值.于是，只需在H0上讨论f(x)在D中的总极大值问题.

引理1 若μ(H0)=0，且H0≠Ø，其中μ(H0)表示集合H0的勒贝格测度，则c0就是f(x)的总极大值，H0就是f(x)的总极大值点集.

于是，设μ(H0)＞0，依据求总极小值的积分水平集算法，构造f(x)在H0上的均值

则

并且

在本研究中，因为f(x)≥0，那么，若对任意点的函数值f(x)赋予权重fn－1(x)(n为不小于1的整数)，则函数值越大的f(x)，其权重也越大，函数值上升的速度越快.于是，对f(x)在H0上的均值函数进行如下修正：

则

一般地，由ck构造水平集

及均值

并且

k=1，2，….从而得到一个新的单调上升数列{ck}及一个单调的集序列{Hk}，它们的上升速度均比数列{}和序列{}快.由于ck≤f(x*)(设x*是f(x)在D上的总极大值点，k=1，2，…)，故{ck}有上界，设

定理1 若f(x)是区域D上的连续函数，则式(15)中数列{ck}的极限c*一定是f(x)在D上的总极大值，水平集序列{Hk}的极限H*是f(x)的总极大值点集.

再由引理3可知，

那么

则

由上述可知，在Hm－O(，δ)上，f(x)≥ck;在O，δ)上，f(x)＞c*+η，所以

又因为c*≥cm，(c*－cm)·μ(O(x—，δ))≥0，所以

移项可得

则

又由于0＜μ(Hm)＜μ(H0)，那么

是总极大值点集(非空).

证明 必要性.设c是总极大值，则

充分性.设方差序列条件成立时，c不是总极大值.令Hc={x|f(x)≥c，x∈D}，那么μ(Hc)＞0，且

已知Hk→Hc(k→∞)，故μ(Hk)→μ(Hc)(k→∞)(已假设H0有界)，那么上式右端被积函数一致有界.当k→∞时，2个积分→0，

设f(x)在D上的总极值为c*=f(x*)，那么c*＞c，故存在η＞0以及x*的邻域O(x*，δ)，对x∈O(x*，δ)，f(x)＞c+η，这时

矛盾.

定理3 若有某下标k，使得ck=ck+1或μ(Hk)= μ(Hk+1)，则f(x)≡常数.

由定义可知，ΔHk={x|ck－1≤f(x)＜ck，x∈D}，ΔHk必为空集，也就证明了μ(Hk－1)=μ(Hk).

再证，若μ(Hk)=μ(Hk+1)，则ck=ck+1，ck+1=ck+2，其中ck+1=ck+2显然成立.然后，证明ck=ck+1.设ck＜ck+1，由f(x)的连续性，存在测度为正的小邻域O(x，δ)⊂ΔHk={x|f(x)＞ck，f(x)≤ck+1}，这与μ(Hk)=μ(Hk+1)矛盾.

利用上面的结果，若ck=ck+1，可推得μ(Hk－1)= μ(Hk)，μ(Hk)=μ(Hk+1)，从而可得ck－1=ck，ck+1= ck+2.依此类推，可知 f(x)≡常数.若 μ(Hk)= μ(Hk+1)，则ck=ck+1，也可推得f(x)≡常数.

2 算法步骤

将上述迭代模型归结为计算数列{ck}和水平集序列{Hk}，概括算法步骤如下：

(1)取x0∈D，给定一个正数ε，令c0=f(x0)，H0={x|f(x)≥c0，x∈D}，k=0;

(2)若μ(Hk)=0，则ck为总极大值，Hk为总极大值点集，转步骤(6);

(5)若V≥ε，令k=k+1，转步骤(2)，否则，转步骤(6);

(6)令f*=ck+1，且H=Hk+1，H为f(x)在D中的近似总极大值点集，算法终止.

3 数值试验及算法讨论

本研究基于积分水平集算法，提出了对函数值恒大于0的函数求总极大值的概念性积分水平集算法;并根据权重的概念，修正了均值函数，理论上可使得函数值上升的速度更快，运算效率得到提高.

在实际计算过程中，本研究引入重要样本(important sample)和相对熵(cross entropy，CE)方法，在相对熵方法中，采用指数分布更新参数.

为了验证该算法的有效性，对具有代表性的全局最优化问题Rastrigin函数进行改进，分别运用一般的相对熵方法和改进的相对熵方法求其极大值，并进行了简单的比较.改进后的Rastrigin函数可表示为

试验结果如表1所示.

数值试验的结果显示，当全局最优化问题的维数较低(如d≤10)，n取到足够大(如n≥100)时，运算时间明显缩短，表明改进后的相对熵算法具有较好的收敛性和较高的效率，与理论推测结果一致，因此本算法有效.然而，当全局最优化问题的维数d越高时，n越大，运算时间越长，效率偏低，算法有待改进.

表1 CE算法与改进的CE算法的数值试验结果Table 1 Numerical results of CE method and modified CE method

另外，本研究赋予函数的权重是fn－1(x)，理论上也可以使用同样具有单调性的指数函数或者对数函数替代，那么对应的{ck}可以分别表示为

具体用这2种方法得到的2个序列是否收敛，以及用这2种方法求极值的最优性条件将另文给出.

［1］ PARDALOSP P，ROMEIJNH E，HOANGT.Recent developments and trends in global optimization［J］.Journal of Computational and Applied Mathematics，2000，124：209-228.

［2］ ZHENGQ，JIANGB C，ZHUANGS L.A method for finding globalextrema［J］. Acta Mathematicae Applicatae Sinica，1978，2(1)：161-174.

［3］ ZHENGQ.Optimality conditions of global optimization (Ⅰ) ［J］.Acta Mathematicae Applicatae Sinica：English Series，1985，1(2)：66-78.

［4］ ZHENGQ.Optimality conditions of global optimization (Ⅱ) ［J］.Acta Mathematicae Applicatae Sinica：English Series，1985，1(3)：118-132.

［5］ WUD H，TIANW W，ZHANGL S，et al.An algorithm of modified integral-level set method for solving global optimization［J］.Acta Mathematicae Applicatae Sinica，2001，24：100-110.

［6］ 俞武扬，邬冬华，吕瑜佩.一种求有约束总极值的新途径［J］.上海大学学报：自然科学版，2002，8(6)：590-597.

［7］ 田蔚文，邬冬华，张连生，等.一种修正的求约束总极值的积分水平集方法［J］.应用数学和力学，2004，25：202-209.

［8］ 邬冬华，俞武扬，田蔚文，等.一种求约束总极值的水平值估计方法［J］.应用数学和力学，2006(7)：165-178.

［9］ PENGZ，WUD H，TIANW W.A level-value estimation method for solving constrained global optimization［J］.Mathematica Numerica Sinica，2007，29(3)：271-282.

［10］ WUD H，YUW Y，ZHENGQ.A sufficient and necessary condition for global optimization［J］.Applied Mathematics Letters，2010，23：17-21.