基于黄金分割的夹逼一维寻优法

　　 论文 关键词：夹逼一维寻优　黄金分割法　单峰函数　算法　优化设计

　　论文摘要：本文在黄金分割法的基础上，提出了一种夹逼一维寻优法。该方法利用对分法选取给定搜索区间中点的原理，将区间对分为两个等分区间，在这两个区间内用黄金分割法同时进行搜索，然后再对这两个区间内所求得的函数值进行比较，运用“去劣存优”的原则，保留含优的搜索区间而摒弃含劣的搜索区间以同时从区间的两侧夹逼来逐步缩小搜索寻优区间，最终求得最优解。本文给出了具体的算法实施过程和算法证明，结合算法给出算例并进行了理论分析和比较,结果表明本算法思路清晰、编程简单、 计算 简化，可以有效地求得函数的最优解。

　　1 引言

　　从数学的观点看，工程中的各种优化问题都可以归结为求极大值或极小值问题。所谓优化设计[1]就是借助最优化数值计算方法和计算机技术求取工程问题的最优设计方案。在优化设计的寻优过程中，首先要根据实际设计问题的物理模型建立相应的数学模型，即用数学形式来描述实际设计问题。其次就是应用数学规划方法的理论[2]，以计算机作为工具，根据数学模型的特点选择最优化方法来求解数学模型，以确定最佳设计参数。在优化设计过程中，求一元函数的极小点和极小值问题就是一维优化问题。求解一维优化问题的方法称为一维优化方法[3]。一维优化法是优化问题中最简单、最基本的方法。因为它不仅可以解决单变量目标函数的最优化问题，而且在求多变最目标函数的最大值时，大多数方法都要反复多次地进行一维搜索，用到一维优化方法。

　　一维优化法中的黄金分割法[4]是使用最广泛、操作简单的一维寻优方法，这种方法是在一元单峰函数所定义的区间上按黄金分割率对称取得一系列的黄金分割点，然后对分割点所对应的函数值进行计算和比较，利用区间缩小的序列消去原理[5]，最终确定函数的最优解和对应的最优值。黄金分割法具有均匀的收敛速度，但每次迭代时只能使给定的搜索区间从单侧进行收缩，使得其收敛速度较慢，区间缩短率偏低。因此，本文利用黄金分割法具有均匀的区间缩小率的序列消去特性，提出一种可以使给定的搜索区间从双侧同时进行收缩的基于黄金分割的夹逼一维寻优法。　

　　2 黄金分割法的基本原理　

　　黄金分割法是用于一元函数 在给定的初始区间 内搜索极小点 的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数[6]，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间[7]。具体步骤是：在区间 内取点： ， ， 和 把 分为三段。如果 ，令 ；如果 ，令 ，重新开始。因为 为单峰区间，这样每次可将搜索区间缩小 倍或 倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区 逐步缩小，直到满足预先给定的精度时，即获得一维优化问题的近似最优解。黄金分割法原理如图１所示，其中k＝ ，区间长度为l，该算法为收敛速度均匀的一维搜索方法。

图1 黄金分割法原理图

fig.1 the principle of golden-section

　　3 算法及其基本原理　

　　3．1 夹副一维寻优法的基本原理

　　夹逼一维寻优方法是在黄金分割法的基础上，利用对分法[8]选取给定搜索区间中点的原理，将区间对分为两个等分区间，在这两个区间内用黄金分割法同时进行搜索，然后再对这两个区间内所求得的函数值进行比较，运用“去劣存优”的原则，保留含优的搜索区间而摒弃含劣的搜索区间以同时从区间的两侧夹逼来逐步缩小搜索寻优区间，最终求得最优解。这种方法和黄金分割法一样，具有算法简单、收敛速度均匀的特点，此外还具有可以使给定的搜索区间以相等的速率从双侧同时进行夹逼收缩，收敛速度快、区间缩短率更高等优点，因而可以更大程度的发挥黄金分割法的优点来进行一维寻优。其基本思想是：在给定的初始区间 上取得区间中点 ，用 将区间 对分为两个等分区间 和 ，记 为ⅰ区间， 为ⅱ区间，在ⅰ和ⅱ区间上分别用黄金分割法进行一维寻优，对这两个区间内所求得的函数值进行比较。两个区间内所求得的函数值进行比较后有如下4种情况，具体比较如图2所示。

图2 区间ⅰ和ⅱ内函数值的比较情况

fig.2 situation of comparing the function value in region ⅰand ⅱ

　　（1）若为第①种情况，则保留ⅰ区间，舍弃ⅱ区间，然后将在ⅰ区间内用黄金分割法求得的新的区间作为下一步寻优搜索区间；

　　（2）若为第②种情况，则保留ⅱ区间，舍弃ⅰ区间，然后将在ⅱ区间内用黄金分割法求得的新的区间作为下一步寻优搜索区间；

　　（3）若为第③和第④种情况，则保留ⅰ和ⅱ区间，然后将用黄金分割法在ⅰ区间内求得的新的区间的左端点和在ⅱ区间内求得的新的区间的右端点所组成的新的整合区间作为下一步寻优搜索区间；

　　通过上述夹逼收缩的寻优搜索后，得到新的搜索区间，如此循环下去，直至搜索区间小于事先给定的精度时，即可得到一维极小点的近似解 ，进一步可以求得最优解 。

　　3．2 算法

　　设目标函数 为单峰函数， ，区间缩小的相对精度为 ，则优化求解的模型可以表述为：　

　　求一元函数 在单峰区间为 上的最优解。

具体算法如下：

　　step1：给定初始区间 ，收敛精度 ；

　　step2：取 ，用 将区间 对分为两个等分区间 和 ，记 为ⅰ区间， 为ⅱ区间，在ⅰ和ⅱ区间上分别按夹逼一维寻优法执行搜索；

　　step3：在ⅰ和ⅱ区间上分别计算黄金分割点 、 ：

　　ⅰ区间上： ；

　　ⅱ区间上： ；

　　并分别计算出ⅰ和ⅱ区间上各黄金分割点处的函数值 和 ；

　　step4：判断是否ⅰ ⅱ ， ：

　　若是，则保留ⅰ区间，舍弃ⅱ区间；

　　否则，转step8；

　　step5：在保留区间ⅰ内比较 与 的大小：

　　若 ，则将原搜索区间替换为 ，并将其赋予新的搜索区间 ，同时取 ；

　　否则，转step7；

　　step6：比较 与 的大小：

　　若 ，则令 ，计算 ，print ；

　　否则，转step2；

　　step7： ，将原搜索区间替换为 ，并将其赋予新的搜索区间 ，同时取 ，并转step6；

　　step8：判断是否ⅱ ⅰ ， ：

　　若是，则保留ⅱ区间，舍弃ⅰ区间；

　　否则，转step11；

　　step9：在保留区间ⅱ内比较 与 的大小：

　　若 ，则将原搜索区间替换为 ，并将其赋予新的搜索区间 ，同时取 ，并转step6；

　　否则，转step10；

　　step10： ，将原搜索区间替换为 ，并将其赋予新的搜索区间 ，同时取 ，并转step6；

　　step11：保留ⅰ和ⅱ区间，然后将在保留ⅰ区间内和ⅱ区间内分别进行step5和step9，只调用ⅰ区间内和ⅱ区间内所赋予的新的搜索区间 ；

　　step12：取ⅰ区间内新的搜索区间 的左端点和ⅱ区间内新的搜索区间 的右端点整合得到下一步寻优的新的搜索区间 ，同时取 ，并转step6；

　　设目标函数 为单峰函数， ，区间缩小的相对精度为 ，则优化求解的模型可以表述为：　

　　定义1：设 为目标函数 的单峰区间， 为 中点，用 将区间 对分为两个等分区间 和 ，记 为ⅰ区间， 为ⅱ区间，按夹逼一维寻优法分别在ⅰ、ⅱ区间内进行搜索，运用“去劣存优”的原则所得到的新的搜索区间 仍然为目标函数 的单峰区间。

　　定义2:夹逼一维寻优法是按黄金分割率对称取点的取点规则[9],以序列消去原理缩小区间,利用对分法提高区间收缩的效率,能够满足单峰函数的极小点在“两头大,中间小”的区间内[10],保证极小点不丢失,从而确保夹逼的收敛性。

　　定理1：设目标函数 为单峰函数， ，区间缩小的相对精度为 ， 为 中点，在用 将区间 对分的ⅰ、ⅱ区间内进行夹逼一维寻优，设第 次所得到的新的搜索区间为 ，记 ，则有 。

　　证明：设给定的初始区间为 ，取 ，用 将区间 对分为两个等分区间 和 ，记 为ⅰ区间， 为ⅱ区间，第1次将该区间对分为2个小区间，再在ⅰ、ⅱ区间内进行黄金分割，依照这样的分法，每个区间的间距不变，且它们的间距分别为：ⅰ ，ⅱ ，且有ⅰ =ⅱ ，经过“去劣存优”后所得到的新的搜索区间的间距为 ，为方便统一记为 ， ，则在对分后新的搜索区间的间距满足 ；第2次，在前面得到的新的搜索区间 内，依照与前面同样的方法再分成更小的区间，由黄金分割的收缩率易知：在由“去劣存优”原则所优选后的区间上继续进行黄金分割所得到的新的区间的间距记为 ， ，则在对分后新的搜索区间的间距满足 ；设第ｎ次分割后在由“去劣存优”原则所优选后的区间上继续进行黄金分割所得到的新的区间的间距记为 ， ，对分后新的搜索区间的间距满足 ；则第（ｎ＋１）次分割后得到的新的搜索区间的间距为 ，对分后新的搜索区间的间距满足 ，由等比数例的收敛性知：存在任意小的数 ，能够使得 成立，故有 成立，即本算法能够满足间距收敛准则[11]。

　　定理２：设目标函数 为单峰函数，且连续有下界， 为给定的初始区间，区间缩小的相对精度为 ，如果将 区间按夹逼一维寻优法逐级分割，第n次分割后所得到的搜索区间为 ，在该搜索区间上能够取得一点 ，使得新的搜索区间的最小函数值 收敛，且 为初始区间最优解。　

　　证明：设给定的初始区间为 ，取 ，用 将区间 对分为两个等分区间 和 ，记 为ⅰ区间， 为ⅱ区间，如果将 区间按夹逼一维寻优法逐级分割，第i次分割后所得到的搜索区间为 ，并将 与 比较，若 ，则可以取得区间的最优值点： ， 计算 求得一元函数 的最优解，若 ,则继续进行夹逼一维寻优。第n次分割后所得到的搜索区间为 ，这样的搜索区间能够满足 ，则可以取得区间的最优值点： ，又依据 为单峰函数，且有下界，且由定义2知 的极小点在“两头大,中间小”的区间 内，则由最优值点计算得新的搜索区间的最小函数值 ，这样的 满足 ，故必收敛。

　　利用反证法来证明 为初始区间最优解。如果有某一点 处的函数值小于 ，则由函数的连续性知必存在该点的一个小邻域 ，其中所有点的函数值都小于 ，由定理１知，经过夹逼一维寻优后得到的新的搜索区间 的间距 ，由定义1可知新的搜索区间 仍然为目标函数 的单峰区间，所以在夹逼一维寻优后必有一个小区间的中点值完全落入 ，从而该区间中点处的函数值小于 ，这与 始终是所有新的搜索区间的中点处函数值的最小值矛盾。所以 必为初始区间最优解。

　　5 算例

　　以下给出利用本文算法计算的算例：

（1） ,已知初始区间为 ，区间缩小的相对精度为 ；

　　（2） ，已知初始区间为 ，区间缩小的相对精度为 。

表1 算例计算结果比较

tab 1 comparison in calculating results of examples

　对于上述算例，分别运用本算法和黄金分割法进行了计算，并对计算结果进行了分析和比较，结果比较见表1。从计算结果来看，在算例1中，本算法按精度要求共只需要迭代3次，黄金分割法则需要迭代6次，且本算法得到的计算精度比要求的精度要高，计算时间仅为黄金分割法的1/3左右，并且所得到的计算结果比用黄金分割法计算得到的结果更加逼近真实值。进一步研究其区间收缩率，按照给定的相对收敛精度 和区间收缩率 可知迭代过程中区间缩短次数n必须满足：

　　算例1中用本算法的迭代次数为n=3，将其代入上式可计算得本算法在算例1中的区间收缩率 ，对比可知比黄金分割法的区间收缩 要高，并且经过算例可以证明：本算法在相对收敛精度 更高的情况下其区间收缩率 更大。

　　究其原因，主要是由于黄金分割法每次都只能以相等的收缩率从区间的单侧来缩短搜索区间，其收敛速度较慢，区间缩短率偏低。而本算法是在黄金分割法具有均匀的区间缩小率的序列消去特性的基础上，利用对分法的原理，使给定的搜索区间从双侧同时进行夹逼收缩，加速了搜索区间的缩短效率，因而可以更有效、更精确地寻求到区间的最优解。

　　6 结论

　　本文在黄金分割法的基础上，提出了一种夹逼一维寻优法。该方法利用对分法选取给定搜索区间中点的原理，将区间对分为两个等分区间，在这两个区间内用黄金分割法同时进行搜索，然后再对这两个区间内所求得的函数值进行比较，运用“去劣存优”的原则，保留含优的搜索区间而摒弃含劣的搜索区间以同时从区间的两侧夹逼来逐步缩小搜索寻优区间，最终求得最优解。文中算法和算例表明本算法思路清晰、编程简单、计算简化，可以有效地求得函数的最优解，求解精度令人满意，具有一定的实用价值。与一维优化方法中的现有算法相比，本算法具有3个方面的特点：

　　（1）可以使给定的搜索区间以相等的速率从双侧同时进行夹逼收缩，收敛速度更快、区间缩短率更高；

　　（2）本算法兼容黄金分割法和对分法的优点，具有算法简单、收敛速度均匀的特点，可以较为精确、快速地求得区间最优解，在理论上讲可以达到任意精度要求；

　　（3）本算法用计算机编程原理简单，所需内存很少，对硬件要求很低，运算时间少，运算速度快，因而可应用的范围较广。

参考 文献

　　[1]王凤岐． 现代 设计方法及其应用[m]．天津大学出版社，2008，81-160．

　　[2]陈树勋．工程结构系统的分析、综合与优化设计：理论、方法及其工程应用案例[m]． 中国 科学 文化出版社，2008，45-80．

　　[3]宋巨龙，钱富才．基于黄金分割的全局最优化方法[j]．计算机工程与应用.2005，4：94—95．

　　[4]韩林山．机械优化设计[m]．郑州：黄河水利出版社，2003 ，40-55．

　　[5]张鄂．机械与工程优化设计[m]．科学出版社，2008 ，105-125．

　　[6]商敏儿，卫成业．确定单峰搜索区间的新算法——前进法[j]．基础自动化，2002，9(1)：1-3．

　　[7]stakhov a．the golden section secrets of the egyptian eivilization and harmony mathematics[j]．chaos，solitons and fractals，2006，30(2)：490-505．

　　[8]panos m pardalos，edwin romeijn h，hoang toy．recent developments and trends in global optimization[j]．journal of computational and applied mathematics，2ooo，124：209～228．

　　[9]刘艳．关于黄金分割法的几点讨论[j]．机电技术,2006,1:13-14．

　　[10]宋巨龙，钱富才．利用平面上的黄金分割求全局最优解[j]．数学的实践与认识，2004，11：113-117．

　　[11]王婷，刘勇，杨秀峰．平面上全局最优解的一种新方法[j]．纺织高校基础科学学报，2007，20（2）：169-171．