文档介绍：求解无约束优化问题的新填充函数算法
摘要:填充函数法是求解全局优化问题的一种重要的方法,本文构造一个新的形式简单且便于计算的单参数填充函数,编写算法,并通过数值计算验证了该算法的有效性和可行性。
关键词:填充函数;全局优化;单参数;数值计算
abstract:the filled function method is an important way to solve global optimization problem. a novel single parameter filled function with simple form and easy to calculate is constructed in the paper. and also its validity and feasibility is validated by numerical calculation.
keywords:filled function;global optimization;single parameter;numerical calculation
1引言
填充函数法由两个阶段组成:极小化阶段和填充阶段,两个阶段交替循环着进行,直到找到问题的全局极小点。其中极小化阶段就是用我们学过的无约束极小化算法极小化问题,得到局部极小点,当该点不是全局极小点时,就进入填充阶段,构造填充函数,回到极小化阶段,找到更小的极小点,重复这个过程,就可以找到全局极小点。填充函数法的核心就是构造填充函数,填充函数的形式与性质决定着相应算法的效率,因此本文力求构造出形式简单,含参数尽量少,且性质良好的填充函数。
2基本概念
考虑无约束极小化问题
■f(■) (p)
对问题(p)作如下假设:
●函数f(■)是强制性质的,即■f(■)=+∞;
该假设的目的是保证存在一个紧集x?奂rn,x包含了f(■)的所有全局极小点和函数值较小的局部极小点,于是,问题(p)等价于■f(■)。
●函数f(■)在x上是连续可微的,问题(p)的局部极小点可以是无限多个,但不同的局部极小值是有限的。
下面给出问题(p)所满足的填充函数的定义:
函数p(■,■,a)称为f(■)在局部极小点处■的填充函数,如果它满足以下条件:
(1)在x上■是p(■,■,a)的严格局部极大点;
(2)对任意■∈s1有,?塄p(■,■,a)≠■,其中s1={■|f(■)≥f(■),■∈x\{■}},即p(■,■,a)在s1上没有极小点或鞍点;
(3)若■不是全局极小点,那么p(■,■,a)一定在s2={■|f(■)0是参数。
当a>0充分大时,下面几个定理表明函数p(■,■,a)是满足定义的一个填充函数。
定理1:■是f(■)的局部极小解,则■是p(■,■,a)的一个严格局部极大解。
证明:由■是f(■)的局部极小解及f(■)的连续性,可知,?埚n(■,?啄),?啄>0,?坌■∈n(■,?啄),且■≠■,有f(■)≥f(■),则?坌■∈n(■,?啄),且■≠■有p(■,■,a)=-aexp[f(■)-f(■)]-||■-■||2≤0=p(■,■,a)。
定理2:若■是f(■)的局部极小解,则?坌■∈s1={■|f(■)≥f(■),■∈x\{■}}都有?塄p(■,■,a)≠■。