基于降維的填充函數(shù)方法

王 薇, 袁 琪, 李 民, 胡 銓

(華東理工大學(xué)數(shù)學(xué)系,上海 200237)

基于降維的填充函數(shù)方法

王 薇, 袁 琪, 李 民, 胡 銓

(華東理工大學(xué)數(shù)學(xué)系,上海 200237)

提出了一個(gè)基于降維技術(shù)的填充函數(shù)方法,用以求解箱約束非線性全局優(yōu)化問題。首先利用降維變換將n維問題轉(zhuǎn)化為一維問題,其次對(duì)一維問題運(yùn)用填充函數(shù)方法求解,證明了降維填充函數(shù)的理論性質(zhì),并給出了算法和數(shù)值實(shí)驗(yàn)結(jié)果。

全局最優(yōu)化; 填充函數(shù); 降維變換;α-致密

填充函數(shù)方法是求解非線性多極值優(yōu)化問題的有效方法之一,由西安交通大學(xué)葛仁傅教授在1987年提出[1-2]。在以后的發(fā)展過程中,很多學(xué)者對(duì)此方法又作了許多改進(jìn)[3-6],提出了單參數(shù)填充函數(shù)、無參數(shù)填充函數(shù)法等。降維方法由CHERRUAULT,ZIADI等學(xué)者提出并應(yīng)用在求解全局優(yōu)化問題上[7-12]。該方法通過構(gòu)造降維變換,利用變換將原n維問題轉(zhuǎn)化為一維全局最優(yōu)化問題。本文將降維技術(shù)與填充函數(shù)方法結(jié)合,構(gòu)造了新的算法求解最優(yōu)化問題,最終利用數(shù)值實(shí)驗(yàn)驗(yàn)證了該方法的可行性。

1 降維變換和填充函數(shù)

1.1 降維變換

考慮箱式約束的全局最優(yōu)化問題P:

假設(shè)1 f(x)在E上偏導(dǎo)數(shù)存在且連續(xù)。

假設(shè)2 f(x)在E上有有限個(gè)極小值。

引理1 f(x)在E上偏導(dǎo)數(shù)存在且連續(xù),則f(x)在E上Lipschitz連續(xù)。

對(duì)問題P的穩(wěn)定點(diǎn)做出一點(diǎn)說明:若x*是問題P的穩(wěn)定點(diǎn),則x*滿足:

構(gòu)造降維變換:xi=hi(θ),i=1,2,…,n,將n維問題轉(zhuǎn)化為只與θ有關(guān)的一維問題f*(θ)。其中,hi(θ),i=1,2,…,n構(gòu)成空間S={(x1,x2,…,xn)|xi=hi(θ),i=1,2,…,n}。

此時(shí),空間S要滿足以下定義:

定義1 S是Rn空間的子空間,如果對(duì)任意一點(diǎn)Q∈Rn,存在Q′∈S,使得d(Q,Q′)≤α,那么稱S是α致密的。 其中d是歐氏距離,α>0充分小。

由文獻(xiàn)[11]定理2推論1知,hi(θ)構(gòu)成的子空間S是α致密的。

降維之后,為了保證變換后問題的最優(yōu)解是原問題的最優(yōu)解,參考文獻(xiàn)[13]給出以下定理:

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

證明 文獻(xiàn)[13]中已證。

轉(zhuǎn)換之后最優(yōu)化問題P*為:

其中,f*(θ)=f(h1(θ),h2(θ),…,hn(θ)),D=[0,π]。根據(jù)f(x)的性質(zhì)和變換函數(shù)T,可知f*(θ)在D上連續(xù)且可導(dǎo)。

1.2 填充函數(shù)

應(yīng)用填充函數(shù)方法,在目標(biāo)函數(shù)滿足兩個(gè)假設(shè)的前提下,構(gòu)造填充函數(shù)。該方法由兩個(gè)階段構(gòu)成,第1階段極小化階段,找原函數(shù)的局部極小點(diǎn),構(gòu)造填充函數(shù);第2階段填充階段,利用填充函數(shù)找比上一個(gè)極小點(diǎn)更低盆谷,然后重復(fù)第1階段。這兩個(gè)階段交替進(jìn)行,直到找不到更優(yōu)的解。在填充函數(shù)方法的發(fā)展過程中,其定義也在不斷變化,下面給出n維填充函數(shù)定義。

定義2 函數(shù)p(x,x*)稱為函數(shù)f(x)在局部極小點(diǎn)x*處的填充函數(shù),如果滿足:

(1)x*是p(x,x*)的一個(gè)嚴(yán)格局部極大點(diǎn);

(2)p(x,x*)在高水平集S1={x|f(x)≥f(x*),x∈E{x*}}上沒有穩(wěn)定點(diǎn);

(3) 如果x*不是全局極小點(diǎn),那么p(x,x*)在低水平集S2={x|f(x)

2 一維填充函數(shù)及性質(zhì)

令θ*是f*(θ)的一個(gè)局部極小值點(diǎn),在θ*處構(gòu)造一維填充函數(shù)P(θ,θ*,r)

其中,r>0充分小,r為參數(shù)。

一維填充函數(shù)P(θ,θ*,r)的高水平集和低水平集分別為

下面證明P(θ,θ*,r)滿足填充函數(shù)條件。

定理2 在[0,π]上,θ*是P(θ,θ*,r)的一個(gè)局部極大點(diǎn)。

證明 已知θ*是f*(θ)在[0,π]的局部極小值點(diǎn),θ*的取值有3種情況:θ*=0,θ*=π,θ*∈(0,π)。

(1)當(dāng)θ*=0時(shí),對(duì)?θ∈(0,δ),δ>0充分小,有f*(θ)-f*(0)>0。因此,

θ*=0是P(θ,θ*,r)的一個(gè)局部極大點(diǎn)。

(3)當(dāng)θ*∈(0,π)時(shí),對(duì)?θ∈(θ*-δ″,θ*)∪(θ*,θ*+δ″),δ″>0充分小,有f*(θ)-f*(θ*)>0。因此,

所以,θ*是P(θ,θ*,r)的一個(gè)局部極大點(diǎn)。

證明 因?yàn)棣取蔥0,π],θ*的取值有3種情況:θ*=0,θ*=π,θ*∈(0,π)。

即得證。

3 算 法

初始步:

(1)選擇參數(shù)r>0,r=10-3

(2)選取初始點(diǎn)θ1∈D

(3)令k=1

循環(huán):

Step1 利用轉(zhuǎn)換T,將f(x)轉(zhuǎn)換為f*(θ);

Step3 i=1;

4 數(shù)值實(shí)驗(yàn)

在本節(jié)中利用數(shù)學(xué)軟件MATLAB R2012a對(duì)以上算法進(jìn)行了編程,并給出了實(shí)例的數(shù)值實(shí)驗(yàn)及其結(jié)果,結(jié)果見表1。

列表中的θ0:算法初始點(diǎn)

min:最優(yōu)解

Global min:標(biāo)準(zhǔn)算例最優(yōu)解

-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可以看出,本文提出的基于降維的填充函數(shù)算法是可行的。從數(shù)值效果上看,對(duì)于維數(shù)較低的函數(shù),數(shù)值結(jié)果的精確度較高。

表1 函數(shù)的數(shù)值實(shí)驗(yàn)結(jié)果Table 1 Numerical results of function

5 結(jié) 論

本文給出了解決問題P的一種新方法。這種方法將降維與填充函數(shù)結(jié)合,用一維問題解決n維箱約束問題,并找到原問題ε-近似解。且原在箱約束上的n維函數(shù)轉(zhuǎn)化到[0,π]的一元函數(shù)上求解,提高了算法的運(yùn)行速度,更快地找出最優(yōu)解。從數(shù)值效果上看,求解維數(shù)較低的問題,在初始點(diǎn)較好的情況下,可以求出標(biāo)準(zhǔn)的最優(yōu)解;當(dāng)維數(shù)較高時(shí),由于轉(zhuǎn)化到一維函數(shù)值波動(dòng)較大,求出的最優(yōu)值精確度與低維相比略差。

[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] 梁玉梅,李銘明,遲東璇,等.全局優(yōu)化問題的一個(gè)單參數(shù)填充函數(shù)方法[J].運(yùn)籌學(xué)學(xué)報(bào),2009,13(4):101-108.

[5] 茅嘉,楊永建.一個(gè)無參數(shù)的填充函數(shù)算法[J].應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào),2010,24(1):35-44.

[6] 李銘明,張連生,王薇,等.一個(gè)新的填充函數(shù)[J].系統(tǒng)與科學(xué),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

國(guó)家自然科學(xué)基金(11271128，71372113)

王 薇(1956-)，女，安徽金寨人，教授，研究方向?yàn)槿肿顑?yōu)化。E-mail：wangwei@ecust.edu.cn

O221.2

A