1、基于黄金分割的夹逼一维寻优法论文关键词：夹逼一维寻优 黄金分割法 单峰函数 算法 优化设计论文摘要：本文在黄金分割法的基础上，提出了一种夹逼一维寻优法。该方法利用对分法选取给定搜索区间中点的原理，将区间对分为两个等分区间，在这两个区间内用黄金分割法同时进行搜索，然后再对这两个区间内所求得的函数值进行比较，运用“去劣存优”的原则，保留含优的搜索区间而摒弃含劣的搜索区间以同时从区间的两侧夹逼来逐步缩小搜索寻优区间，最终求得最优解。本文给出了具体的算法实施过程和算法证明，结合算法给出算例并进行了理论分析和比较,结果表明本算法思路清晰、编程简单、计算简化，可以有效地求得函数的最优解。1 引言从数学的观
2、点看，工程中的各种优化问题都可以归结为求极大值或极小值问题。所谓优化设计1就是借助最优化数值计算方法和计算机技术求取工程问题的最优设计方案。在优化设计的寻优过程中，首先要根据实际设计问题的物理模型建立相应的数学模型，即用数学形式来描述实际设计问题。其次就是应用数学规划方法的理论2，以计算机作为工具，根据数学模型的特点选择最优化方法来求解数学模型，以确定最佳设计参数。在优化设计过程中，求一元函数的极小点和极小值问题就是一维优化问题。求解一维优化问题的方法称为一维优化方法3。一维优化法是优化问题中最简单、最基本的方法。因为它不仅可以解决单变量目标函数的最优化问题，而且在求多变最目标函数的最大值时，
3、大多数方法都要反复多次地进行一维搜索，用到一维优化方法。一维优化法中的黄金分割法4是使用最广泛、操作简单的一维寻优方法，这种方法是在一元单峰函数所定义的区间上按黄金分割率对称取得一系列的黄金分割点，然后对分割点所对应的函数值进行计算和比较，利用区间缩小的序列消去原理5，最终确定函数的最优解和对应的最优值。黄金分割法具有均匀的收敛速度，但每次迭代时只能使给定的搜索区间从单侧进行收缩，使得其收敛速度较慢，区间缩短率偏低。因此，本文利用黄金分割法具有均匀的区间缩小率的序列消去特性，提出一种可以使给定的搜索区间从双侧同时进行收缩的基于黄金分割的夹逼一维寻优法。 2 黄金分割法的基本原理 黄金分割法是用
4、于一元函数在给定的初始区间 内搜索极小点 的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数6，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间7。具体步骤是：在区间内取点：， ，和把分为三段。如果，令；如果，令，重新开始。因为为单峰区间，这样每次可将搜索区间缩小倍或倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区逐步缩小，直到满足预先给定的精度时，即获得一维优化问题的近似最优解
5、。黄金分割法原理如图所示，其中 K，区间长度为 L，该算法为收敛速度均匀的一维搜索方法。图 1 黄金分割法原理图Fig.1 the principle of golden-section3 算法及其基本原理 31 夹副一维寻优法的基本原理夹逼一维寻优方法是在黄金分割法的基础上，利用对分法8选取给定搜索区间中点的原理，将区间对分为两个等分区间，在这两个区间内用黄金分割法同时进行搜索，然后再对这两个区间内所求得的函数值进行比较，运用“去劣存优”的原则，保留含优的搜索区间而摒弃含劣的搜索区间以同时从区间的两侧夹逼来逐步缩小搜索寻优区间，最终求得最优解。这种方法和黄金分割法一样，具有算法简单、收敛速度
6、均匀的特点，此外还具有可以使给定的搜索区间以相等的速率从双侧同时进行夹逼收缩，收敛速度快、区间缩短率更高等优点，因而可以更大程度的发挥黄金分割法的优点来进行一维寻优。其基本思想是：在给定的初始区间 上取得区间中点 ，用 将区间 对分为两个等分区间 和 ，记 为区间， 为区间，在和区间上分别用黄金分割法进行一维寻优，对这两个区间内所求得的函数值进行比较。两个区间内所求得的函数值进行比较后有如下 4 种情况，具体比较如图 2 所示。图 2 区间和内函数值的比较情况Fig.2 situation of comparing the function value in region and （1）若为第
7、种情况，则保留区间，舍弃区间，然后将在区间内用黄金分割法求得的新的区间作为下一步寻优搜索区间；（2）若为第种情况，则保留区间，舍弃区间，然后将在区间内用黄金分割法求得的新的区间作为下一步寻优搜索区间；（3）若为第和第种情况，则保留和区间，然后将用黄金分割法在区间内求得的新的区间的左端点和在区间内求得的新的区间的右端点所组成的新的整合区间作为下一步寻优搜索区间；通过上述夹逼收缩的寻优搜索后，得到新的搜索区间，如此循环下去，直至搜索区间小于事先给定的精度时，即可得到一维极小点的近似解，进一步可以求得最优解。32 算法设目标函数为单峰函数， ，区间缩小的相对精度为，则优化求解的模型可以表述为： 求一
8、元函数在单峰区间为上的最优解。具体算法如下：Step1：给定初始区间，收敛精度；Step2：取，用将区间对分为两个等分区间 和，记为区间，为区间，在和区间上分别按夹逼一维寻优法执行搜索；Step3：在和区间上分别计算黄金分割点 、：区间上：；区间上：；并分别计算出和区间上各黄金分割点处的函数值 和 ；Step4：判断是否 ，：若是，则保留区间，舍弃区间；否则，转 Step8；Step5：在保留区间内比较与的大小：若，则将原搜索区间替换为，并将其赋予新的搜索区间，同时取；否则，转 Step7；Step6：比较与的大小：若，则令，计算 ，print；否则，转 Step2；Step7：，将原搜索区间
9、替换为，并将其赋予新的搜索区间，同时取 ，并转 Step6；Step8：判断是否 ，：若是，则保留区间，舍弃区间；否则，转 Step11；Step9：在保留区间内比较与的大小：若，则将原搜索区间替换为，并将其赋予新的搜索区间，同时取，并转 Step6；否则，转 Step10；Step10：，将原搜索区间替换为，并将其赋予新的搜索区间，同时取，并转 Step6；Step11：保留和区间，然后将在保留区间内和区间内分别进行 Step5 和 Step9，只调用区间内和区间内所赋予的新的搜索区间；Step12：取区间内新的搜索区间的左端点和区间内新的搜索区间的右端点整合得到下一步寻优的新的搜索区间 ，
10、同时取，并转Step6；4 收敛性证明 设目标函数为单峰函数， ，区间缩小的相对精度为，则优化求解的模型可以表述为： 定义 1：设为目标函数的单峰区间，为中点，用将区间对分为两个等分区间和，记为区间，为区间，按夹逼一维寻优法分别在、区间内进行搜索，运用“去劣存优”的原则所得到的新的搜索区间仍然为目标函数的单峰区间。定义 2:夹逼一维寻优法是按黄金分割率对称取点的取点规则9,以序列消去原理缩小区间,利用对分法提高区间收缩的效率,能够满足单峰函数的极小点在“两头大,中间小”的区间内10,保证极小点不丢失,从而确保夹逼的收敛性。定理 1：设目标函数为单峰函数， ，区间缩小的相对精度为，为中点，在用将
11、区间 对分的、区间内进行夹逼一维寻优，设第次所得到的新的搜索区间为，记，则有。证明：设给定的初始区间为，取，用将区间对分为两个等分区间和，记为区间，为区间，第 1 次将该区间对分为 2 个小区间，再在、区间内进行黄金分割，依照这样的分法，每个区间的间距不变，且它们的间距分别为：，且有 =，经过“去劣存优”后所得到的新的搜索区间的间距为，为方便统一记为 ， ，则在对分后新的搜索区间的间距满足；第 2 次，在前面得到的新的搜索区间内，依照与前面同样的方法再分成更小的区间，由黄金分割的收缩率易知：在由“去劣存优”原则所优选后的区间上继续进行黄金分割所得到的新的区间的间距记为 ， ，则在对分后新的搜索
12、区间的间距满足；设第次分割后在由“去劣存优”原则所优选后的区间上继续进行黄金分割所得到的新的区间的间距记为 ， ，对分后新的搜索区间的间距满足；则第（）次分割后得到的新的搜索区间的间距为，对分后新的搜索区间的间距满足，由等比数例的收敛性知：存在任意小的数，能够使得成立，故有成立，即本算法能够满足间距收敛准则11。定理：设目标函数为单峰函数，且连续有下界，为给定的初始区间，区间缩小的相对精度为 ，如果将区间按夹逼一维寻优法逐级分割，第 n 次分割后所得到的搜索区间为，在该搜索区间上能够取得一点，使得新的搜索区间的最小函数值收敛，且为初始区间最优解。 证明：设给定的初始区间为，取，用 将区间对分为
13、两个等分区间 和，记为区间，为区间，如果将区间按夹逼一维寻优法逐级分割，第 i 次分割后所得到的搜索区间为，并将与 比较，若，则可以取得区间的最优值点：，计算求得一元函数的最优解，若,则继续进行夹逼一维寻优。第 n 次分割后所得到的搜索区间为，这样的搜索区间能够满足，则可以取得区间的最优值点：，又依据为单峰函数，且有下界，且由定义2 知的极小点在“两头大,中间小”的区间内，则由最优值点计算得新的搜索区间的最小函数值，这样的满足 ，故必收敛。利用反证法来证明 为初始区间最优解。如果有某一点 处的函数值小于，则由函数的连续性知必存在该点的一个小邻域，其中所有点的函数值都小于，由定理知，经过夹逼一维
14、寻优后得到的新的搜索区间的间距，由定义 1 可知新的搜索区间仍然为目标函数的单峰区间，所以在夹逼一维寻优后必有一个小区间的中点值完全落入，从而该区间中点处的函数值小于，这与始终是所有新的搜索区间的中点处函数值的最小值矛盾。所以必为初始区间最优解。5 算例以下给出利用本文算法计算的算例：（1）,已知初始区间为，区间缩小的相对精度为；（2） ，已知初始区间为，区间缩小的相对精度为。表 1 算例计算结果比较Tab 1 comparison in calculating results of examples对于上述算例，分别运用本算法和黄金分割法进行了计算，并对计算结果进行了分析和比较，结果比较见表
15、 1。从计算结果来看，在算例 1中，本算法按精度要求共只需要迭代 3 次，黄金分割法则需要迭代 6 次，且本算法得到的计算精度比要求的精度要高，计算时间仅为黄金分割法的 1/3 左右，并且所得到的计算结果比用黄金分割法计算得到的结果更加逼近真实值。进一步研究其区间收缩率，按照给定的相对收敛精度 和区间收缩率 可知迭代过程中区间缩短次数 N 必须满足：算例 1 中用本算法的迭代次数为 N=3，将其代入上式可计算得本算法在算例 1 中的区间收缩率 ，对比可知比黄金分割法的区间收缩 要高，并且经过算例可以证明：本算法在相对收敛精度 更高的情况下其区间收缩率 更大。究其原因，主要是由于黄金分割法每次都
16、只能以相等的收缩率从区间的单侧来缩短搜索区间，其收敛速度较慢，区间缩短率偏低。而本算法是在黄金分割法具有均匀的区间缩小率的序列消去特性的基础上，利用对分法的原理，使给定的搜索区间从双侧同时进行夹逼收缩，加速了搜索区间的缩短效率，因而可以更有效、更精确地寻求到区间的最优解。6 结论本文在黄金分割法的基础上，提出了一种夹逼一维寻优法。该方法利用对分法选取给定搜索区间中点的原理，将区间对分为两个等分区间，在这两个区间内用黄金分割法同时进行搜索，然后再对这两个区间内所求得的函数值进行比较，运用“去劣存优”的原则，保留含优的搜索区间而摒弃含劣的搜索区间以同时从区间的两侧夹逼来逐步缩小搜索寻优区间，最终求
17、得最优解。文中算法和算例表明本算法思路清晰、编程简单、计算简化，可以有效地求得函数的最优解，求解精度令人满意，具有一定的实用价值。与一维优化方法中的现有算法相比，本算法具有3 个方面的特点：（1）可以使给定的搜索区间以相等的速率从双侧同时进行夹逼收缩，收敛速度更快、区间缩短率更高；（2）本算法兼容黄金分割法和对分法的优点，具有算法简单、收敛速度均匀的特点，可以较为精确、快速地求得区间最优解，在理论上讲可以达到任意精度要求；（3）本算法用计算机编程原理简单，所需内存很少，对硬件要求很低，运算时间少，运算速度快，因而可应用的范围较广。参考文献1王凤岐现代设计方法及其应用M天津大学出版社，2008，81-1602陈树勋工程结构系统的分析、综合与优化设计：理论、方法及其工程应用案例M中国科学文化出版社，2008，45-803宋巨龙，钱富才基于黄金分割的全局最优化方法J计算机工程与应用.2005，4：94954韩林山机械优化设计M郑州：黄河水利出版社，2003 ，40-555张鄂机械与工程优化设计M科学出版社，2008 ，105-125
