无约束全局最优化的一种新的下降法*

刘呈军，卓春英

(重庆水利电力职业技术学院，重庆永川 402160)

已有许多文献对全局最优化问题中凸最优化问题进行了研究，并得到了一些很有效的解法.但是，在自然世界中大多数的最优化问题都是非凸的，目前已有文献对非凸全局优化问题进行凸化、凹化方面的研究［1］.如果一个通常的目标函数存在很多的局部最优解，这对求解全局最优是一个很大的挑战.

函数修正法［2］是一种针对一般全局最优化问题的求解方法，通过对目标函数作一些适当的修正来超越现有的局部最优解.函数修正法(隧道效应法)［3］是1985年由Levy和Montalvo提出的.1989年，在文献［4］中Yao将这种隧道效应算法用于求解约束全局最优化问题.在1983年两年一度的苏格兰敦提市第十届数值分析研讨会上，葛仁溥提出了填充函数法，并且他的文章［5］在1990年被发表.文献［6，7］又将填充函数法进行了推广.但是，现有的填充函数都具有以下的缺点:

(1)填充函数能够在原目标函数f的一个局部极小点x*处被构造出来，但在实际计算中局部最优化方法有时可能在一个不是局部极小点处终止，比如在函数f的一个平稳点处终止.

(2)在当前局部极小点x*处构造填充函数，则点x*一定是被构造出的填充函数的一个局部极大点.因为x*是这个填充函数的一个平稳点，所以不直接从点x*开始极小化这个填充函数，必须选取x*附近的点x来代替x*作为初始点去极小化填充函数.

针对以上的两个缺点，提出一种新的辅助函数法即全局下降法，这种全局下降法在函数修正法的第1，2阶段都有松弛的要求，用局部最优化方法产生的一个点x*可能不是一个局部极小点，比如是问题(P)的KKT点或平稳点，并且全局下降函数的极小化可能在一个平稳点处而不必是局部极小点处结束.

1 全局下降法

考虑无约束全局最优化问题:

其中，函数f在Rn上连续可微，并且对问题(P)作如下的假设.

注意到，如果f满足强制条件，即当‖x‖→+∞时f(x)→+∞，那么f(x)满足假设1.在假设1的条件下，问题(P)等价于下面的问题(PΩ)

此处提出一种新的辅助函数法(全局下降法)，使得它具有如下性质:

(1)在任意给出的一个可能不是问题(P)的一个局部极小点x*处能够构造出全局下降函数.

(2)满足f(x)≥f(x*)的任意点x(包含x*)不能是所构造的全局下降函数的一个平稳点.在Rn中用任何传统的局部搜索方法去极小化被构造的全局下降函数将会在全局下降函数的一个极小点或平稳点x＊＊(f(x＊＊)＜f(x*))处终止.

在后面的讨论中，假设x*是满足f(x*)≤f()的迭代算法中的当前点，其中满足假设1.

对一个给定的可变参数r＞0，定义下面两个函数

可以证明gr(t)和fr(t)在R上是可微的，且有

不失一般性，取点x0∈RnΩ为

显然，对任意的x∈Ω有x-x0≥1.取Ω中离x0最远的顶点为

注意到，x*不是函数(x)的平稳点.规定

定理1 如果假设1成立，那么对任意的r＞0(x)满足下面的条件:

(1)如果x∈Ω满足f(x)≥f(x*)，那么x不是函数(x)的平稳点，且满足‖▽(x)‖≥D.

①f()＜f(x*).

证明 1)由式(9)，有

因为f(x)≥f(x*)，即f(x)-f(x*)≥0，所以gr(f(x)-f(x*))=1，g'r(f(x)-f(x*))=0，f'r(f(x)-f(x*))=0.

设Y是问题(PΩ)的局部极小点的集合，并设

定理2 假设

1)假设1成立且F是一个有限集.

2)L(x*)≠φ，即x*不是问题(P)的全局极小点.

证明 因为x*不是问题(P)的全局极小点，且F是一个有限集，所以集合{f(x*)-f(x)|x∈L(x*)}既是非空的又是有限的，并且对任意∈L(x*)和r，满足0＜r≤时，β0(x*)＞0和≤-2r＜-r.因为f(x)连续，且是问题(PΩ)的一个局部极小点，所以存在的一个领域)∩Ω，有)＜-r和f(x)≥).因此对任意的0，fr(f(x)-f(x*))=f(x)-f(x*)+r和f(x)≥)，即有).因此∈L(x*)是)在Ω上的一个局部极小点.因∈L(x*)⊂int Ω，故=0.由式(12)可知)=0，并且对任意x∈∂Ω，f(x)≥f(x*)，有

定理3 对任意的x1，x2∈Ω，如果f(x1)≥f(x*)，f(x2)≥f(x*)，则‖x2-x0‖＞‖x1-x0‖当且仅当(x2)＜(x1).

证明 对任意的x1，x2∈Ω 满足f(x1)≥f(x*)，f(x2)≥f(x*)，则有(x2)=

+1，所以‖x2-x0‖＞‖x1-x0‖当且仅当

1)满足f(x)≥f(x*)的任意点x∈Ω(除点d外)既不是(x)在Ω上的局部极小点也不是平稳点.

2)当参数r充分小时，满足f)＜f(x*)的原问题(P)的任意局部极小点，或是在Ω上的一个局部极小点或是它的平稳点.

定义1 函数(x)称为问题(PΩ)在点x*的一个全局下降函数，如果(x)满足下面的条件:

2)函数(x)在Ω上的任意局部极小点，除Ω的(至多)一个顶点外都有f()＜f(x*)成立.

3)如果L(x*)≠Ø，即x*不是问题(P)的全局极小点，则任意的∈L(x*)是(x)在Ω上的一个局部极小点和平稳点，并且有)＜(x*);对任意的x∈∂Ω，有)＜(x).

①选取一个小的正数 μ＞0作为参数r的终止值，选取一个点x0∈RnΩ，使得对任意的x∈Ω满足‖x-x0‖≥1，选取一个初始点∈Ω，使得满足假设1.设r0是参数r的初始值，令k:=0.

注1 通常情况下，假设1的验证并不容易.但是，在许多情况下，不需要验证，因为很容易得到一个大的箱子集Ω.

2 数值计算

此处将利用全局下降算法来求解一些著名的检验函数的全局极小点.在后面的算例中，取 μ=10-10，r0=1.

例1 Six-Hump Camel-back(n=2).

例2 Rastrigin(n=2).

3 结论

介绍了无约束全局优化的一种全局下降法，只要调用现有的局部搜索方法就可以求得原问题的全局最优解，这是因为此处提出的全局下降函数具有非常好的性质.此处全局下降算法利用了MATLAB7.10最优化工具箱的最优化子程序，从文中例子的计算结果来看，这种全局下降法是非常有效的.

［1］刘呈军.非凸全局最优化的一种凸化、凹化方法［J］.重庆工商大学学报:自然科学版，2012，29(3):22-26

［2］GE R P.A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables［J］.Mathematics Program，1990(46):191-204

［3］LEVY A V，MONTALVO A.The Tunneling Algorithm for the Global Minimization of Functions［J］.SIAM J SciStat Comput，1985，6(1):15-29

［4］YAO Y.Dynamic Tunneling Algorithm for Global Optimization［J］.IEEE Trans SystMan Cybern，1989，19(5):1222-1230

［5］HANSEN E R.Global Optimization Using Interval Analysis［M］.New York:Dekker，1992

［6］WU Z Y，LEE H W J，ZHANG L S，et al.A Novel Villed Function Method and Quasi-filled Function Method for Global Optimization［J］.Comput Optim Appl，2006，34(2):249-272

［7］ZHANG L S，NG C K，LI D，et al.A New Filled Function Method for Global Optimization［J］.Glob Optim，2004(28):17-43