一种新的无约束优化问题的混合算法

宋巨龙,钱富才,梁锦锦

(1.西安石油大学 理学院, 陕西 西安 710065;2.西安理工大学 自动化与信息工程学院, 陕西 西安 710048)

一种新的无约束优化问题的混合算法

宋巨龙1,钱富才2,梁锦锦1

(1.西安石油大学 理学院, 陕西 西安 710065;2.西安理工大学 自动化与信息工程学院, 陕西 西安 710048)

将传统的一维搜索方法——成功-失败法与新的Apollonius填充算法相结合,给出一种新的平面上的无约束优化方法。该方法既将成功-失败法推广到了平面上,又将Apollonius填充算法的适用对象由约束问题推广到了无约束问题。数值实验表明,该方法适用于较为复杂的非线性可微凸函数,如果对计算时间要求不高的话,该方法可以适用于具有较高复杂度的非线性可微凸函数,具有一定的实际应用价值。

Apollonius填充; 成功-失败法; 非线性最优化; 算法

非线性函数寻优问题由于其在非线性分析[1]、函数逼近[2]、系统控制[3]、模式识别[4]等领域的广泛应用,一直受到科学研究人员与工程技术人员的高度关注。关于这方面的研究,成果众多,诸如经典共轭梯度算法[5]、遗传算法[6]、模拟退火算法、蚁群算法等等[7],各有其独到的优点,当然也都有其局限性,比如共轭梯度法要求目标函数为凸函数,否则会陷入局部最优,遗传算法尽管以概率1收敛到目标函数的最优解,但由于用不确定性的方法搜索确定性问题,使得搜索效率大大下降。因此,探索新的更为有效的算法成为本文研究的出发点。

目前,被理论界和工程界广为接受的众多算法中,成功-失败法[8]是一个经典的一维搜索算法。该方法用于寻找一维凸函数的搜索区间,即包含目标函数最优解的区间,同时该方法也可以直接用来求一维凸函数的最优解,只是效率比黄金分割法等经典算法稍低些。此外,该方法的适用范围仅仅局限于一维凸函数。

在古老的初等几何问题中,有一个被命名为Apollonius的问题,就是求任意三个已知圆的公切圆,该问题已经圆满解决。以此为基础,一些关于该问题的应用被提出,文献[9]利用Apollonius问题的结论,给出了一个用无限多个圆将一个圆填满的具体方法,这就是著名的Apollonius填充。文献[10]在文献[9]的基础上对Apollonius填充的构造进行了深入研究,得到了一些可以在工程设计中应用的结果,在那里仅就分形的构造进行了研究。而文献[11]则进一步将Apollonius填充应用到有着广泛应用前景、并且是目前的一个研究难点的非线性全局最优化问题中去。在那里将Apollonius填充和分形的思想相结合,得到了一种特殊区域——圆域约束下的全局最优化计算方法。该方法可以很好的解决定义在特殊区域——圆域上的非线性函数的全局最优解,不过在那里,该方法只适用于圆域约束下的非线性函数最优解的求解。

基于对成功-失败法和Apollonius问题的了解,本文尝试将两者相结合,提出了一种新的优化算法。本文的主要方法和目的是:将经典的成功-失败法和Apollonius填充算法相结合,得到一种基于Apollonius填充的成功-失败法。其特点是:一方面将成功-失败法的适用范围由只适用于一维非线性凸函数推广到也适用于二维非线性凸函数,另一方面又可将只适用于圆域约束优化问题的Apollonius填充算法推广到了适用于无约束非线性凸函数的优化问题。数值实验表明,该方法可以有效地求得二维非线性凸函数的无约束最优解,除此之外,新方法对搜索路径通过图形给出了形象清晰的描述。总的来说,新方法是对无约束非线性优化问题的一种新的探索,给出了一种新的二维无约束优化算法,对非线性优化研究人员以及工程技术人员都有一定的参考和实用价值。

1 成功-失败法

成功-失败法是一种传统的一维搜索方法,其主要功能在于求一维函数的搜索区间,也可以用来直接求一维函数的最优解,该方法只适用于单峰函数,具体步骤如下:

为求函数的最小值点,通常分两步走,首先确定函数的搜索区间,然后不断收缩搜索区间,直至区间收缩为一点为止。成功-失败法正是基于这一理念而产生的。

为方便起见,设函数f(x)是R1上的凸函数。∀x0∈R1,步长h>0。

1) 若f(x0)>f(x0+h), 则当f(x0+h)>f(x0+3h)时,步长加倍,向前推进,即令x0=x0+h,h=2h,重新开始搜索;否则得搜索区间[a,b]=[x0,x0+3h]。

2) 若f(x0)=f(x0+h),则得搜索区间[a,b]=[x0,x0+h]。

通过这样的步骤,可以得到凸函数f(x)的最优解所在的区间。如果还不满足于此,想进一步直接求得函数的最优解,则可采取如下步骤:

Step1 ∀x0∈R1,步长h>0,计算精度ε>0。

Step2 计算f0=f(x0),f1=f(x0+h)。

Step3 如果|h|<ε,则停止计算,可取x0为近似最优解。

Step4 如果f0>f1,则令x0=x0+h,f0=f1,h=2h,转Step3。

否则，令h=-0.25h,转Step3。

这样即可获得目标函数的近似最优解。该方法简单有效,是一种很实用的一维搜索方法。

2 Apollonius填充及其算法

2.1 Apollonius填充

所谓Apollonius填充,指的是将任意一个圆,用位于其内部的无限多个相互外切的圆将该圆完全填满,使得该圆中的任意一点都可以落入某个填充圆中。至于其中具体的填充方式是可以选择的。图1所示是一个填充结果,无数个半径不等的小圆将一个大圆完全填满。当然，这里所谓的填满其实是理论上的,由于计算时间、计算机计算功能及显示功能的限制,实际上只能做到近似填满，不过,如果需要,是可以使填充的满足程度达到任意精度的。构造该填充的关键方法在于求任意三个相切圆的公切圆,也就是所谓的Apollonius问题的求解,对于如何求解Apollonius问题以及如何实现Apollonius填充,在文献[10]中有着详细的论述,所以具体实现方法请参阅文献[10]。

2.2 Apollonius填充算法

Apollonius填充算法是由文献[11]提出的,该算法的主要功能在于求解约束区域为圆域的非线性约束问题的全局最优解。其主要特点有两个:①不要求目标函数为凸函数,任意可微非线性函数都可以,即对目标函数的要求很低;②求得的非线性函数的最优解是圆形约束区域内的全局最优解。具体实现方法如下:

1) 首先任选可行圆域中的一点,将其作为当前近似最优解,对应的函数值作为当前近似最优值。

2) 对圆形约束区域进行Apollonius填充,也可以看成是对圆域进行Apollonius分割,将目标函数的函数值在每一个圆上的下界进行估计,将那些圆域中目标函数值的下界大于当前近似最优值(即该圆域中必不含有目标函数最优解)的圆放弃掉,不对该圆进行进一步的分割，否则转到下一步。

3) 对那些圆域中目标函数值的下界小于当前近似最优值,即该圆域中有可能含有目标函数最优解的圆,进行进一步的Apollonius分割。在分割之前,计算一下该圆圆心的坐标以及目标函数在该圆心上的函数值,如果该函数值小于当前近似最优值,则用圆心替代当前近似最优解,同时用该圆心处的函数值替代当前近似最优值。如此不断进行下去,直到满足事先规定的精度为止,比如所论圆的直径小于某精度,或者迭代次数达到事先规定的次数。

对于上述算法,可能有人会提出这样的疑问:填充已经是无限的了,还要对其中的每个圆再进行无限填充,如此大的数据量,可以实现吗?会不会发生数据爆炸?其实对此大可不必过于担心,由于在计算过程中要不断的对目标函数进行估计,一旦目标函数在该圆上的下界大于当前近似最优值,就不再对该圆进行进一步分割了,所以大多数圆都很快被放弃掉了,只有少部分圆需要分割,故不会发生数据爆炸。文献[11]中对大量复杂的例子进行了数值实验,并没有发生数据爆炸。

3 新算法的基本原理

下面就新算法的基本原理进行论述。

本法求解的优化问题为非线性无约束最优化问题,优化问题的目标函数应是非线性可微凸函数。

本法的基本原理:从任意一点出发,以该点为圆心,取适当长度为半径,用Apollonius填充算法求目标函数在该圆上的全局最优解,若该最优解落在圆域内部,则终止计算,由于目标函数为凸函数,故该点即为所求目标函数的无约束最优解,若该最优解落在该圆边界上,或者非常靠近边界,则以该最优解为新的圆心,仍以上述给定的半径为半径,再次用Apollonius填充算法求目标函数在该圆域上的全局最优解,直到某最优解落入圆的内部且远离边界的时候终止,此时,当前的近似最优解即为所求无约束问题的近似最优解。

本法的具体方法如下:

前两年，有关方面组织编写出版的《中国当代杂文家》和《走近杂文家》两书，让我忝列其中，还鼓励我参评“首届全国鲁迅杂文奖”，并获得金奖，这是对我这个“创作劳模”的一种奖赏，对此我心存感激。

Step1 从任意一点x0出发,将该点作为当前近似最优解,相应的函数值作为当前的近似最优值,给定一个半径r0。

Step2 以x0为圆心,r0为半径作圆,用Apollonius填充算法求目标函数在该圆上的全局最优解。

Step3 判断该最优解是否落在该圆域的边界上,若没有落在边界上,则由于目标函数为凸函数,所以该最优解必为目标函数的无约束最优解,因而停止计算;若落在边界上(若非常靠近边界,也认为是落在边界上了),则以该最优解为新的圆心x0,仍以r0为半径,转Step2。

关于本算法的收敛性说明如下。

首先,本文所涉及的目标函数应该是连续可微凸函数,该函数的最优解应该是存在的,也就是说函数在整个区域上是有下界的,而在算法中每次迭代所得到的近似最优解xn处的最优值f(xn)是单调递减的,即满足:

故依单调有界原理知其必收敛。

其次,由于本算法求得的最终的最优解必位于某圆域内部,且是该圆域内部的全局最优解,而所论目标函数是凸函数,从而在圆域外部必没有目标函数的最优解,因此该近似最优解点列的极限点必为目标函数的最优解。

4 数值算例

下面是利用本法求解的非线性优化问题的数值实验结果。

解:显然这是一个单峰函数,搜索过程见图2。搜索过程中,从左下角第一个圆开始,逐步经过若干个圆域的搜索,最终落到坐标系第一象限,在精确解的周围又进行了更为密集的,也就是更为精确的搜索。最后一个黑点即为精确最优解的位置,可以看出,真正搜过的区域并不是很大。

本例精确解为(x*,y*)=(8,12), 最优值为f*=0。经本法搜索的结果为:(x*,y*)=(8.001 9,11.999 6),最小值为f*=3.883 3×10-6。

例2 圆函数：

minf(x,y)=x2+2y2+4x+4

解:本例精确解为(x*,y*)=(-2,0),最小值为f*=0。经本法搜索的结果为: (x*,y*)=(-1.999 025,3.527 198×10-4),最小值为f*=1.198 969×10-6。图3为本例搜索过程图。通过图3可看出,本例大面积的区域被迅速地删除,只搜索了很少一部分区域就找到了最优解。搜索路径为一弧线。

例3 香蕉函数：

minf(x,y)=(x-y)2+100(y-1)2

解:本例函数是一个具有槽状平底的单峰函数,一般优化方法不容易得到精度较高的最优解。图4为本例搜索过程图。从图4可看出：只搜索了很少一部分区域就得到了精度相当高的最优解；在奔向槽底时搜索速度较快,而在槽底时则搜索的速度较慢,搜索区域较大,但总体上搜索过的区域并不是很大。本例精确解为(x*,y*)=(1,1),最小值为f*=0。经本法搜索的结果为(x*,y*)=(1.008 48,0.997 65),最小值为f*=6.690 235×10-4。

5 结 论

本文将经典的成功-失败法与新的Apollonius填充算法相结合,获得一种新的无约束最优化方法,该方法将成功-失败法的应用范围由仅适用于一维无约束非线性凸函数的优化问题推广到二维无约束非线性凸函数的优化问题。同时也使Apollonius填充算法在无约束非线性凸函数优化问题中得到应用。数值实验表明,本法对较为复杂的非线性凸函数是有效的;搜索路径是清晰可见的。本法的局限性在于这种方法只能应用于二维问题,无法进一步推广到更高维数的优化问题。

[1]钱富才, 黄姣茹, 秦新强. 基于鲁棒优化的系统辨识算法研究 [J].自动化学报, 2013, 40(5): 988-993. Qian Fucai, Huang Jiaoru, Qin Xinqiang. Research on algorithm for system identification based on robust optimization [J].Acta Automatic Sinica, 2013, 40(5): 988 -993.

[2]钱富才, 朱少平, 刘丁. 噪声未知的LQG控制问题与研究 [J].控制理论与应用, 2010, 27(8): 1017-1022. Qian Fucai, Zhu Shaoping, Liu Ding. On LOG problems with unknown noises [J].Control Theory & Applications, 2010, 27(8): 1017-1022.

[3]莫国端, 刘开第. 函数逼近论方法 [M].北京: 科学出版社, 2003.

[4]陈予恕, 唐云, 陆启超，等.非线性动力学中的现代分析方法 [M].北京: 科学出版社, 2000.

[5]张光澄, 王文娟, 韩慧磊, 等. 非线性最优化计算方法 [M].北京: 高等教育出版社, 2005.

[6]王竹荣，杨波，吕兴朝，等. 一种改进的量子遗传算法研究[J].西安理工大学学报，2012，28(2)：145-151. Wang Zhurong, Yang Bo, Lü Xingchao, et al. An inproved quantum genetic algorithm[J].Journal of Xi’an University of Technology, 2012,28(2):145-151.

[7]Dorigo M, Stutzle T. Ant colony optimization [M].London: MIT Press, 2004.

[8]陈开周. 最优化计算方法 [M].西安: 西安电子科技大学出版社, 1985.

[9]肯尼思·法尔科内. 分形几何——数学基础及其应用 [M]. 曾文曲，刘世耀，戴连贵，等，译. 沈阳: 东北大学出版社, 1991.

[10]宋巨龙, 林椹尠, 宋国乡. Apollonius填充在CAD中的应用 [J].计算机应用, 2005, 25(5): 1108-1109. Song Julong, Lin Zhenxian, Song Guoxiang. Application of Apollonius fill in CAD [J].Computation Application, 2005, 25(5): 1108-1109.

[11]Song Julong, He Xiangjian, Lin Zhenxian. Global optimization under nonlinear constraints based on Apollonius fill [C]∥Third International Conference on Natural Cpmputation V5, Los Almitos, 2007: 39-45.

(责任编辑 周蓓)

An innovation hybrid algorithm on unconstrained optimization problems

SONG Julong1,QIAN Fucai2,LIANG Jinjin1

(1.Faculty of Science, Xi’an Shiyou University, Xi’an 710065, China; 2.Faculty of Automatization and Information Engineering, Xi’an University of Technology, Xi’an 710048, China)

Combing one dimensional research method—Success-Failure method with novel Apollonius fill algorithm, gives a new kind of algorithm of unconstrained optimization method on the plane. The new algorithm has extended Success-Failure method to the plane. At the same time, the scope of application of Apollonius fill algorithm is extended from constrained optimization problems to unconstrained problems. Numerical experiment results show that this algorithm is suitable for complicated nonlinear differentiable convex function. If the calculation time is not highly required, the algorithm can be applied to any complicated nonlinear differentiable convex function. Whereby indicating that this algorithm is of the highly practical application value.

Apollonius fill; Success-Failure method; nonlinear optimization; algorithm

1006-4710(2015)04-0460-04

2015-03-10

国家自然科学基金资助项目(61273127,61304204);高等学校博士学科点专项科研基金资助项目(2011611 8110008)。

宋巨龙,男,教授,研究方向为最优化、数值计算。E-mail:sjlong@xsyu.edu.cn。

O151.21

A