约束优化问题的单参数填充函数算法

马素霞 ,高岳林 ,杨丽丽 ,柳迎春

(1.宁夏大学数学统计学院,宁夏 银川 750021;2.北方民族大学数学与信息科学学院,宁夏 银川 750021;3.宁夏科学计算与智能信息处理协同创新中心,宁夏 银川 750021)

1.引言

科学和工程中的大量决策问题都可归结为求解全局优化问题,而这类问题的求解方法是当今社会的一个重要研究热点.现有的全局优化算法大体可分为两大类,即,确定性算法[1-4]和随机性算法[5-7].其中,填充函数法是一种经典的全局优化确定性方法,由西安交通大学的葛仁溥教授[2]最早提出,该方法主要通过循环迭代不断跳出当前已知的最好局部极小点以便找到另一个更好的局部极小点,直到找到全局极小点为止,从而能够克服一般优化算法容易陷入“早熟”的缺陷.在文[1]中,葛仁溥教授率先给出了填充函数的初步概念,并将其应用于无约束全局优化问题的求解,该方法因内部只需要调用现有的局部优化方法而深受广大学者的欢迎.然而,文[1]中的第一代填充函数包含指数项和两个参数,由于参数调节上的困难使得实际应用中的计算量变大以及指数项的存在容易遗失问题的最优点,从而导致了该填充函数的不适用性.因此,诸多国内外学者都对葛教授的填充函数的不足之处做出了相关改进并提出了各种能够被应用到实际问题中的填充函数.例如,文[8-11]中所出现的四种双参数填充函数、文[12-16]中所提出的五个单参数填充函数以及文[17-22]中所给出的六种无参数填充函数等等,这些填充函数的提出使得全局优化理论更为丰富.值得一提的是,文[16]中的填充函数仅在部分可行域内有定义,使得该填充函数的填充效率大为降低;文[21]中是一个很有前景的无参数填充函数,它具有连续可微的性质,但仍然包含指数项从而降低了填充效果,文[22]的填充函数却避免了这一缺点,但其函数图像在某些情况下是平坦的,使得填充函数在跳出局部极小点时的效率降低,该填充函数中也包含不连续可微的符号函数,这大大限制了极小化填充函数所需下降方法的选取范围.上述填充函数方法仅能被用于求解无约束全局优化问题或盒子约束全局优化问题.目前,只有少数填充函数可以解决约束全局优化问题,如文[23-27]中的方法.此外,现有的填充函数虽然各有优点,但也存在一些缺点,如填充函数包含多个参数,导致调整困难,降低了算法的效率,若某些填充函数是非光滑函数,这也是传统局部优化方法无法实现的.

为了求解有约束的全局优化问题,本文提出了一种新的填充函数,它是一个连续可微的单参数函数.如果参数的取值尽可能小且大于0,那么该填充函数将保证不可行区域不存在驻点.另外，如果某个可行点的目标函数值大于当前局部极小值,则该点也不是所提填充函数的驻点.如果存在另一个优于目标函数当前极小值的局部极小点,那么此填充函数的极小点就会落在目标函数值较优的极小点附近.

本文的其余部分组织如下.第二节中给出了填充函数方法的相关预备知识.第三节提出了一种连续可微的单参数填充函数.并对其解析性质做出了分析.第四节是所设计的填充函数全局优化算法的具体步骤.第五节给出一些测试问题的数值实验结果.第六节是结论.

2.预备知识

本文研究以下约束全局优化问题:

其中f:R,gi(x) :R,i1,2,···,m,均为二次连续可微函数,Ω是一个盒子,S{x|gi(x)≤0,i1,2,···,m}是有界集且满足cl(int(S))S,这里int(A)表示集合A的内部,cl(A)表示集合A的闭包.在S的限制上,存在Ω满足S ⊂Ω和∂Ω∩S∅(∂Ω表示集合Ω的界).

为确保问题(OP)的全局最优解存在以及所提出的填充函数方法能够顺利实现,预先给出关于该问题的一些假设条件和定义是有必要的.

假设2.1问题(OP)中的目标函数是连续可微的.

假设2.2集合τ是由问题(OP)在S中的所有局部极小点组成的,且L∗{F(x)|是有限的.

注2.1假设2.2表明问题(OP)可能有无限个局部极小点,但是局部极小值的数量总是有限的.

定义2.1如果存在ε>0,使得(x0,ε)∩S,有F(x)≥(≤)F(x0),则x0被称为F(x)在集合S上的一个局部极小点(极大点).如果等式不成立,则x0被称为F(x)在集合S上的一个严格局部极小点(极大点);如果,有F(x)≥(≤)F(x0)成立,则x0被称为F(x)在集合S上的一个全局极小点(极大点).如果等式不成立,则x0被称为F(x)在集合S上的一个严格全局极小点(极大点).

注2.2B(x0,ε)表示x0的以ε为半径的邻域.

注2.3 定义2.2的前两个填充性质保证了填充过程得以实现,而第三个填充性质则确保了填充函数极小点x′的存在性.另外定义2.2也可概括为: 1)填充函数在上是一个减函数并且没有驻点;2) 填充函数的极小点在上.

3.新的填充函数及其解析性质

基于定义2.2所要求的三个填充性质并且考虑到多参数填充函数的不足之处,提出了下面的单参数填充函数:

式中r>0为参数,∥·∥表示是·的欧氏范数,F(x)是目标函数,是问题(OP)的一个局部极小点,h(t),g(t)和fr(t)是R上连续可微的一元函数.m是问题(OP)中不等式约束的个数.容易验证,填充函数(3.1)是连续可微的.

下面验证,当r>0且r足够小时,MF(x,,r)满足第二部分所定义的填充函数.

再利用函数fr(t)的定义不难断定

4.填充函数算法

本节将利用构造的填充函数设计出相应的单参数填充函数算法(PFFA: Parameter Filled Function Algorithm).填充函数算法总是涉及到极小化过程,包括极小化目标函数或者极小化填充函数本身.本文将采用SQP方法极小化目标函数,采用BFGS方法极小化填充函数.

步0 选择参数r的一个下界Lr(例如,取Lr10-9)和一个常数ρ<1(例如,取ρ10-3);给出r的初始值(例如,取r1);选择一个初始点x0;令方向集D{eiRn|i1,2,···,2n}(其中ei(0,···,1,···,0)T,i1,2,···,n,ei的第i个元素取1,ei−ei-n,in+1,···,2n,n是函数F(x)的变量个数);σ0>0(本文取σ00.01);ε>0(本文取ε10-6);置k1.

步1 以x0作为初始点极小化F(x)得到,置i1.

步2 构造函数

5.数值实验

本文使用Matlab(2016a)对PFFA算法进行编码并执行.通过使用6种测试函数对该算法进行测试,所有这些计算过程均在Intel(R) Core(TM)i5-8500 3.00 GHz power处理器8.00 GB内存,Win10操作系统的台式电脑上进行.

下面给出6种测试函数,其中F(x)表示目标函数,x0表示初始点,x∗和F(x∗)分别表示全局极小点和全局极小值.

例1[28]

例1的全局最优解为x∗(2.3295,3.1783)T,F(x∗)−5.5079.实验中,采用初始点x0(0,0)T和x0(0.6,0.8)T,其计算结果见表5.2.

例2[29]

在例2中,x∗(0.7255,0.3993)T,F(x∗)−1.8376.本文使用初始点x0(1,1)T,x0(0.5,0.5)T,x0(1.5,1.5)T,x0(2,2)T和x0(2,1)T对该问题进行数值测试,其计算结果见表5.2.

例3[29]

例3在可行域内的全局最优解为x∗(5,1,5,0,5,10)T,F(x∗)−310.本文使用初始点x0(3,3,3,3,3,3)T,x0(4,4,4,4,4,4)T,x0(3,3,4,4,3,5)T,x0(4,4,4,4,4,4)T和x0(2,2,3,2,3,2)T对该问题进行数值测试,其数值计算结果见表5.2.

例4[28]

例4在可行域内的全局最优解为x∗(78,33,29.9953,45,36.7758)T,F(x∗)−30665.5387.本文使用了初始点x0(90,33,35,35,40)T来测试这个问题,其计算结果见表5.2.

例5[10]

在例5中,x∗(0.1093,−0.6234)T,F(x∗)−0.9711.本文使用初始点x0(−1,−1)T,x0(0,0)T和x0(1,1)T对该问题进行数值测试,其计算结果见表5.2.

例6[26]

例6的全局最优解为x∗(0,0)T,F(x∗)−2.7183.实验中,采用初始点x0(30,30)T,其计算结果见表5.2.

后面这部分对PFFA算法进行了数值实验测试.为了证明该算法的有效性,我们对PFFA算法计算所得到的迭代次数和填充函数的评估次数的数值结果与文[10,23,26]中相应的数值结果进行了比较.在此之前,对这部分所使用的一些符号约定如表5.1所示.

表5.1 符号说明

从表5.2的数值结果可以看出,本文算法能够在有限的迭代内对这6种类型共19个测试例子进行全局寻优,且算法的每一步都是下降的,这说明该算法是可行的.

表5.2 例1-4的计算结果

表5.3-5.5分别是本文算与文[23]、[10]和[26]中算法对这6种类型的测试问题的数值计算结果对比.从表5.3-5.5可以观测到,算法PFFA与三个对比文献中算法的迭代次数相当.而在函数评估次数上,表5.3表明了算法PFFA在13个测试例子中有11个测试例子均优于文[23]中算法,表5.4表明了算法PFFA在10个测试例子中有7个测试例子均优于文[10]中算法.表5.5中算法PFFA与[26]中算法所得全局最优解相一致.因此,本文算法也是有效的,并且比文[23]和[10]中的算法计算能力更强.

表5.3 本文与文[23]的数值计算结果对比

表5.4 本文与文[10]的数值计算结果对比

表5.5 本文与文[26]的数值计算结果对比

综上所述,本文所设计的填充函数算法是有效可行的,适合求解约束全局优化问题.

6.结论

为更好地求解约束全局优化问题,本文提出了一个具有连续可微性质且无指数项和对数项的新型填充函数,并证明了该填充函数满足填充性质.最后利用6种共19个测试例子将本文算法分别与文[23]、[10]和[26]中的算法进行了数值计算结果对比,验证了本文算法的可行性和有效性.未来的研究中,将着重为约束优化问题构造无约束填充函数及其对应的全局优化算法,以避免参数调节上的限制.