基于降维的填充函数方法

王 薇, 袁 琪, 李 民, 胡 铨

(华东理工大学数学系,上海 200237)

基于降维的填充函数方法

王 薇, 袁 琪, 李 民, 胡 铨

(华东理工大学数学系,上海 200237)

提出了一个基于降维技术的填充函数方法,用以求解箱约束非线性全局优化问题。首先利用降维变换将n维问题转化为一维问题,其次对一维问题运用填充函数方法求解,证明了降维填充函数的理论性质,并给出了算法和数值实验结果。

全局最优化; 填充函数; 降维变换;α-致密

填充函数方法是求解非线性多极值优化问题的有效方法之一,由西安交通大学葛仁傅教授在1987年提出[1-2]。在以后的发展过程中,很多学者对此方法又作了许多改进[3-6],提出了单参数填充函数、无参数填充函数法等。降维方法由CHERRUAULT,ZIADI等学者提出并应用在求解全局优化问题上[7-12]。该方法通过构造降维变换,利用变换将原n维问题转化为一维全局最优化问题。本文将降维技术与填充函数方法结合,构造了新的算法求解最优化问题,最终利用数值实验验证了该方法的可行性。

1 降维变换和填充函数

1.1 降维变换

考虑箱式约束的全局最优化问题P:

假设1 f(x)在E上偏导数存在且连续。

假设2 f(x)在E上有有限个极小值。

引理1 f(x)在E上偏导数存在且连续,则f(x)在E上Lipschitz连续。

对问题P的稳定点做出一点说明:若x*是问题P的稳定点,则x*满足:

构造降维变换:xi=hi(θ),i=1,2,…,n,将n维问题转化为只与θ有关的一维问题f*(θ)。其中,hi(θ),i=1,2,…,n构成空间S={(x1,x2,…,xn)|xi=hi(θ),i=1,2,…,n}。

此时,空间S要满足以下定义:

定义1 S是Rn空间的子空间,如果对任意一点Q∈Rn,存在Q′∈S,使得d(Q,Q′)≤α,那么称S是α致密的。 其中d是欧氏距离,α>0充分小。

由文献[11]定理2推论1知,hi(θ)构成的子空间S是α致密的。

降维之后,为了保证变换后问题的最优解是原问题的最优解,参考文献[13]给出以下定理:

定理1 如果变换xi=hi(θ),i=1,2,…,n是α致密的,那么f*(θ)的全局极小值近似接近f(x)的全局极小值。

证明 文献[13]中已证。

转换之后最优化问题P*为:

其中,f*(θ)=f(h1(θ),h2(θ),…,hn(θ)),D=[0,π]。根据f(x)的性质和变换函数T,可知f*(θ)在D上连续且可导。

1.2 填充函数

应用填充函数方法,在目标函数满足两个假设的前提下,构造填充函数。该方法由两个阶段构成,第1阶段极小化阶段,找原函数的局部极小点,构造填充函数;第2阶段填充阶段,利用填充函数找比上一个极小点更低盆谷,然后重复第1阶段。这两个阶段交替进行,直到找不到更优的解。在填充函数方法的发展过程中,其定义也在不断变化,下面给出n维填充函数定义。

定义2 函数p(x,x*)称为函数f(x)在局部极小点x*处的填充函数,如果满足:

(1)x*是p(x,x*)的一个严格局部极大点;

(2)p(x,x*)在高水平集S1={x|f(x)≥f(x*),x∈E{x*}}上没有稳定点;

(3) 如果x*不是全局极小点,那么p(x,x*)在低水平集S2={x|f(x)

2 一维填充函数及性质

令θ*是f*(θ)的一个局部极小值点,在θ*处构造一维填充函数P(θ,θ*,r)

其中,r>0充分小,r为参数。

一维填充函数P(θ,θ*,r)的高水平集和低水平集分别为

下面证明P(θ,θ*,r)满足填充函数条件。

定理2 在[0,π]上,θ*是P(θ,θ*,r)的一个局部极大点。

证明 已知θ*是f*(θ)在[0,π]的局部极小值点,θ*的取值有3种情况:θ*=0,θ*=π,θ*∈(0,π)。

(1)当θ*=0时,对∀θ∈(0,δ),δ>0充分小,有f*(θ)-f*(0)>0。因此,

θ*=0是P(θ,θ*,r)的一个局部极大点。

(3)当θ*∈(0,π)时,对∀θ∈(θ*-δ″,θ*)∪(θ*,θ*+δ″),δ″>0充分小,有f*(θ)-f*(θ*)>0。因此,

所以,θ*是P(θ,θ*,r)的一个局部极大点。

证明 因为θ∈[0,π],θ*的取值有3种情况:θ*=0,θ*=π,θ*∈(0,π)。

即得证。

3 算 法

初始步:

(1)选择参数r>0,r=10-3

(2)选取初始点θ1∈D

(3)令k=1

循环:

Step1 利用转换T,将f(x)转换为f*(θ);

Step3 i=1;

4 数值实验

在本节中利用数学软件MATLAB R2012a对以上算法进行了编程,并给出了实例的数值实验及其结果,结果见表1。

列表中的θ0:算法初始点

min:最优解

Global min:标准算例最优解

-5≤xi≤5,i=1,2。

算例2[11]:minG2(x1,x2)=

-1≤xi≤1,i=1,2。

-2≤xi≤2,i=1,2,3,4。

算例4[11]:minG2(x1,…,x6)=

从表1可以看出,本文提出的基于降维的填充函数算法是可行的。从数值效果上看,对于维数较低的函数,数值结果的精确度较高。

表1 函数的数值实验结果Table 1 Numerical results of function

5 结 论

本文给出了解决问题P的一种新方法。这种方法将降维与填充函数结合,用一维问题解决n维箱约束问题,并找到原问题ε-近似解。且原在箱约束上的n维函数转化到[0,π]的一元函数上求解,提高了算法的运行速度,更快地找出最优解。从数值效果上看,求解维数较低的问题,在初始点较好的情况下,可以求出标准的最优解;当维数较高时,由于转化到一维函数值波动较大,求出的最优值精确度与低维相比略差。

[1] GE Renpu.The theory of filled function method for finding global minimizers of nonlinearly constrained minimization problems[J].Journal Of Computation Mathematics,1987,5(1):1-9.

[2] GE Renpu,QIN Yongfeng.A class of filled functions for finding global minimizers of a function of several variables[J].Journal of Optimization Theory and Applications,1987,54,(2):241-252.

[3] LUCIDI S,PICCIALLI V.New classes of globally convexized filled functions for global optimization[J].Journal of Global Optimization,2002,24(2):219-236.

[4] 梁玉梅,李铭明,迟东璇,等.全局优化问题的一个单参数填充函数方法[J].运筹学学报,2009,13(4):101-108.

[5] 茅嘉,杨永建.一个无参数的填充函数算法[J].应用数学与计算数学学报,2010,24(1):35-44.

[6] 李铭明,张连生,王薇,等.一个新的填充函数[J].系统与科学,2007,27(5):703-710.

[7] CHERRUAULT Y.A new method for global optimisation (Alienor)[J].Kybernetes,1990,19(3):19-32.

[8] AMMAR H,CHERRUAULT Y.Approximation of a several variables function by a one variable function and application to global optimization[J].Mathmatics & Computer Modelling,1993,18(2):17-21.

[9] BENDIAB O,CHERRUAULT Y.A new method for global optimization in two dimiensions[J].International Journal of Biomedical Computing,1995,38:71-73.

[10] CHERRUAULT Y.α-Dense curves and global optimization[J].Kybernetes,2003,32(3):369-375.

[11] ZIADI A,GUETTAL D,CHERRUAULT Y.Global optimization:The alienor mixed method with piyavskii-shubert technique[J].Kybernetes,2005,34(7):1049-1058.

[12] ZIADI A,CHERRUAULT Y,MORA G.Global optimization:A new variant of the alienor method[J].Computers and Mathematics With Applications,2001,41 (1):63-71.

[13] BALIRA O.K,CHERRUAULT Y,BENNEOUALA T.A global optimization method for a large number of variables (variant of Alienor method)[J].Kybernetes,2005,34(7):1070-1083.

A Filled Function Method Based on Dimensionality Reduction

WANG Wei, YUAN Qi, LI min, HU Quan

(Department of Mathematics,East China University of Science and Technology,Shanghai 200237,China)

This paper presents a filled function method based on reducing dimension technology.The method will be used for the nonlinear global optimization problems with box constraints.Firstly,a reducing transformation is used to convert ann-variable problem into a one-variable problem.Secondly,the one-variable problem is solved by filled function method.The paper proves the theoretical characteristic of filled function,gives the algorithm and lists the experimental results at last.

global optimization problem; filled function; dimensionality reduction;α-dense

1006-3080(2016)06-0877-04

10.14135/j.cnki.1006-3080.2016.06.020

2015-06-08

国家自然科学基金(11271128，71372113)

王 薇(1956-)，女，安徽金寨人，教授，研究方向为全局最优化。E-mail：wangwei@ecust.edu.cn

O221.2

A