一个求解无约束优化的单参数填充函数算法

张玉琴，冯向东，张建亮

(成都理工大学 工程技术学院，四川 乐山 614000)

0 引 言

全局优化问题是解决实际问题的重要理论之一，在日常生活中，有着非常广泛的应用，尤其在管理决策、工程计算和控制理论等领域。从算法的结构分类，全局最优化算法被分为两类：确定性算法和随机性算法。然而填充函数法被称为确定性算法。

西安交通大学葛仁溥教授最初提出填充函数法[1]。此方法是求解非线性全局优化问题的方法之一；填充函数法是解决怎样从原问题的一个局部极小解开始，找到更小的局部极小解的方法。填充函数法主要有两个过程：极小化过程与填充过程。这两个过程循环使用直到找不到更好的局部极小解。为了消除已有的经典极小化算法存在早熟的弊端，找到更好的局部极小解，众多理论和实际工作者更加热衷于研究填充函数法[2-7]。

填充函数法的核心工作是填充函数，其性质与形式决定它的算法效率；填充函数应构建为目标函数的复合函数，且含有一个参数[4，8-10]或两个参数[1，3，5，11]，由于参数的选取比较困难，或由于填充函数是分段函数[3，5，11]，使得填充函数算法的效率降低。为此，科研工作者竭力地构建参数尽量少、形式足够简单及呈现优良性质的填充函数。仔细研究文献[4，8]，笔者构建了一个形式简易、容易计算的连续的单参数的填充函数。

1 基本知识

文中仅研究无约束最优化问题

(1)

对于无约束最优化问题(P0)，目标函数f(x)满足以下假设：

假设Ⅰ：(P0)的函数f(x)是强制的。即当‖x‖→时，f(x)→。

由假设Ⅰ可以得出，必定存在一个有界闭集X⊂Rn，使得f(x)的全局极小解都包含在X内；也可以这样解释f(x)的极小值在X的内部取得。因此，问题(P0)就转化为求解如下问题：

(P1) minf(x) s.t.x∈X

(2)

假设Ⅱ：在Rn上，函数f(x)连续而且可微。

假设Ⅲ：问题中可有无穷个相异的局部极小解，但只有可数个相异的局部极小值。

文中填充函数的定义参考文献[4]。

(2)对所有x∈S1,有这里即在S1上没有极小解或鞍点；

2 填充函数与性质

鉴于问题(P0)，假若(P0)的局部极小解为x*，单参数填充函数构建如下：

P(x,x*,ρ)=-ρ[f(x)-f(x*)]2-arctan(‖x-x*‖2)

(3)

其中，ρ>0为参数，以下定理说明函数P(x,x*,ρ)满足填充函数定义，而且有一些较好的性质。

定理1：若x*是函数f(x)的局部极小解，则x*是P(x,x*,ρ)的一个严格的局部极大解。

证明：因为在Rn上，目标函数f(x)连续；又因为x*为函数f(x)的局部极小解，所以存在点x*的某个邻域U(x*)，使得对于每个x∈U(x*)，且x≠x*，满足f(x)≥f(x*)且

P(x,x*,ρ)=-ρ[f(x)-f(x*)]2-arctan(‖x-x*‖2)<0=P(x*,x*,ρ)

即证：x*是P(x,x*,ρ)的一个严格的局部极大解。

定理2：假若x*是函数f(x)的局部极小解，对每个x∈S1，则P(x,x*,ρ)≠0。

证明：因为f(x)连续可微，因此

对任意x∈S1，满足

下面证明对任意x∈Y,都有P(x,x*,ρ)>P(x1*,x*,ρ)。

P(x,x*,ρ)-P(x1*,x*,ρ)=

ρ{[f(x1*)-f(x*)]2-[f(x)-f(x*)]2}+

ρ{[f(x*)-f(x1*)]2-[f(x*)-f(x1*)-

arctan(‖x-x*‖2)

因为ε>0，因此

ρ{[f(x*)-f(x1*)]2-[f(x*)-f(x1*)-ε]2}>0

因此，对任意x∈Y，当ρ充分大时，P(x,x*,ρ)>P(x1*,x*,ρ)。(*)

由上述证明可得，当取足够大的ρ时，使得在S2上存在P(x,x*,ρ)的一个局部极小解x0*。

定理4：如果x*是函数f(x)的全局极小解，则对于任意的x∈X,x≠x*，有P(x,x*,ρ)<0。

证明：因为x*是目标函数f(x)的全局极小解，因此对任意x∈X，f(x)≥f(x*)。

由定理1知：对于任意x∈X,x≠x*，有P(x,x*,ρ)<0。

定理5：如果x*是目标函数f(x)的局部极小解，对于任意x∈S1，且当ρ充分大时，则方向d=f(x)T是P(x,x*,ρ)在x处的下降方向；其中f(x)T≠0。

-2ρ[f(x)-f(x*)]所以f(x)TP(x,x*,ρ)=-2ρ[f(x)-f(x*)]f(x)Tf(x)-

对于任意x∈S1，当ρ充分大时，f(x)TP(x,x*,ρ)<0。因此结论成立。

3 填充函数算法与算例实验

3.1 填充函数算法

假设调节步长δ>0，ε>1，参数k是外循环的运算次数，且存在一个足够大的正整数N，使得k≤N；参数i是内循环迭代次数，且存在一个足够大的正整数M，使得i≤M;一般选取M>2n，其中n是决策变量的维数。参数ρ≤ρ0

Step1：令k:=1，i:=1，ρ:=1。

Step2：选择初始点x0∈X,从x0开始，利用成熟的最优化方法，解出局部极小解x1*和对应的局部极小值f(x1*)。

Step3：在极小解x1*处构建填充函数：

P(x,x*,ρ)=-ρ[f(x)-f(x*)]2-

arctan(‖x-x*‖2)

Step4：如果i≤M，选取x1=x1*+δdi∈X,其中di是随机方向，‖di‖∞≤1，δ>0；从点x1开始，用成熟的优化算法求解P(x,x*,ρ)的局部极小解x2，转为Step5；否则，令k:=k+1，转为Step6。

Step5：假若x2∈X,转为Step6；否则令i:=i+1，转为Step4。

Step7：如果k≤N,令ρ:=ρε，i:=1，如果ρ>ρ0，则取ρ=ρ0，转为Step4。否则，结束计算；输出x1*与函数值f(x1*)，把f(x1*)作为近似的全局极小值。

3.2 算例实验

算例都在Matlab2014a运行环境下实现。

算例1：Rastrigin

s.t.x∈{(x1,x2)|-1≤x1,x2≤1}

文中迭代次数是1次，得到的全局极小解是x*=(-0.679 5e-9,0.555 2e-9)T，全局极小值f(x*)=-2；而文献[4]的数值结果中迭代次数是4次，全局最小解是x*=(-0.200 0e-7,-0.200 0e-7)T，全局极小值是f(x*)=-1.999 999 99。

算例2：Three-hump camel-back Function

s.t.x∈{(x1,x2)|-3≤x1,x2≤3}

文中的迭代次数是2次，全局极小解是x*=(0.076 5e-6,0.161 8e-6)T，全局极小值是f(x*)=2.551 4e-14。文献[4]的迭代次数是3次，全局极小解是x*=(-1.356e-5,0.492 0e-5)T，全局极小值是f(x*)=4.585e-10。

算例3：Treccani Function

s.t.x∈{(x1,x2)|-3≤x1,x2≤3}

文中的迭代次数是1，全局极小解是x*=(0.061 0×1.0e-6,-0.156 9×1.0e-6)T全局极小值是f(x*)=3.951 4e-14；文献[4]的迭代次数是2，全局极小解是x*=(4.66e-6,0.000 0)T,全局极小值是f(x*)=8.677 1e-11。

算例4：Six-hump camel-back Function

s.t.x∈{(x1,x2)|-3≤x1,x2≤3}

文中迭代次数是2次。全局极小解是(0.089 8,0.712 7)T，全局极小值是f(x*)=-1.031 6。文献[4]的迭代次数是3，全局极小解是x*=(0.089 837 22,0.712 694 68)T,全局极小值是f(x*)=-1.031 628 44。

算例5：Two-dimensional Function

minf(x)=[1-2x2+0.5sin(4πx2)-x1]2+[x2-0.5sin(2πx1)]2

s.t.x∈{(x1,x2)|0≤x1≤10,-10≤x2≤0}文中迭代次数是4次；全局极小解是x*=(0.934 2,-0.174 6)T，全局极小值是f(x*)=7.669 3e-14。文献[4]的迭代次数是3，全局极小解是

x*=(0.999 999 99,0.000 000 17)T，全局极小值是f(x*)=5.907 849 04e-13。

小结：对比文献[4，8]的数值结果，算法迭代次数较少，而且精度较高。

4 结束语

文中构建的无约束的优化问题的单参数填充函数，具有较好的性质，而且形式简单，便于计算。算例结果证明了该算法的可行性。在此基础上，还可以构建无参数填充函数，或引入滤子方法等[12-15]，研究求解优化问题的填充函数仍是一个研究方向。