最优化方法-一维搜索法ppt课件.ppt

《最优化方法-一维搜索法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一维搜索法§搜索区间及其确定方法§对分法§Newton切线法§黄金分割法§抛物线插值法最优化问题的迭代解法（一）迭代方法最优化问题的迭代算法是指：从某一选定的初始点出发，根据目标函数、约束函数在该点的某些信息，确定本次迭代的一个搜索方向和适当的步长，从而到达一个新点，用式子表示即为式中,——前一次已取得的迭代点，在开始计算时为迭代初始点；——新的迭代点；——第k次迭代计算的搜索方向；——第k次迭代计算的步长因子．按照上式进行一系列迭代计算所根据的思想是所谓的“爬山法”，就是将寻求函数小点（无约束或约束极小点）的过程比喻为向“山”的顶峰攀登的过程

2、，始终保持向“高”的方向前进，直至达到“山顶”。当然“山顶”可以理目标函数的极大值，也可以理解为极小值，前者称为上升算法，后者称为下降算法。这两种算法都有一个共同的特点，就是每前进一步都应该使目标函数有所改善，同时还要为下一步移动的搜索方向提供有用的信息。如果是下降算法，则序列迭代点的目标函数值必须满足下列关系如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可行域内，即下图为迭代过程（二）收敛速度与计算终止准则（1）收敛速度作为一个算法A，能够收敛于问题的最优解当然是必要的，但光能收敛还不够，还必须能以较快的速度收敛，这才是好的算法．定

3、义3.2设由算法A产生的迭代点列在某种“

4、

5、·

6、

7、”的意义下收敛于点，即,若存在实数及一个与迭代次数无关的常数使得则算法A产生的迭代点列叫做具有阶收敛速度，或算法A叫做是阶收敛的，特别地：①当，迭代点列称为具有线性收敛速度或算法A称为线性收敛的．②当，或时，迭代点列叫做具有超线性收敛速度或称算法A是超线性收敛．③当时，迭代点列叫做具有二阶收敛速度或算法A是二阶收敛的．一般认为，具有超线性收敛或二阶收敛的算法是较快速的算法．(2)计算终止准则用迭代方法寻优时，其迭代过程总不能无限制地进行下去，那么什么时候截断这种迭代呢？这就是迭代什么时候终止的问

8、题。从理论上说，当然希望最终迭代点到达理论极小点，或者使最终迭代点与理论极小点之间的距离足够小时才终止迭代．但是这在实际上是办不到的．因为对于一个待求的优化问题，其理论极小点在哪里并不知道．所知道的只是通过迭代计算获得的迭代点列，因此只能从点列所提供的信息来判断是否应该终止迭代。对于无约束优化问题通常采用的迭代终止准则有以下几种：①点距准则相邻两迭代点之间的距离已达到充分小，即式中是一个充分小正数，代表计算精度．②函数下降量准则相邻两迭代点的函数值下降量已达到充分小．当时，可用函数绝对下降量准则当时，可用函数相对下降量准则③梯度准则目标函数在迭

9、代点的梯度已达到充分小，即这一准则对于定义域上的凸函数是完全正确的．若是非凸函数，有可能导致误把驻点作为最优点。对于约束优化问题，不同的优化方法有各自的终止准则．定义3.3当一个算法用于n元正定二次函数求最优解时，可以从任意初始点出发，至多经过n步迭代求出最优解，就称此算法具有二次终止性。如果算法具有二次终止性，则认为算法比较好。二次终止性仅仅是判断一个算法优劣的衡量标准之一。综上所述，优化算法的基本迭代过程如下：①选定初始点，置．②按照某种规则确定搜索方向．③按某种规则确定使得④计算⑤判定是否满足终止准则．若满足，则打印和,停机；否则置,转②

10、．NYX是否满足终止准则输出X，f(X)开始结束选定X0确定P确定t，使得f(X0+tP)

11、，而凸函数在所给区间上必然是单峰函数（如左图所示）．由定义3.3知，函数的单峰区间总是相应问题的一个搜索区间（如左图所示），但反之不然（如右图所示）．搜索区间及其确定方法定义3.5设是在上的最优解，如果存在,且,则称[t1t2]是函数的最优解的一个搜索区间。搜索区间及其确定方法单峰区间和单峰函数有如下有用的性质：定理3.1设是的单峰区间，任取并且．（1）若有，则是的单峰区间．（2）若有，则是的单峰区间．（2）若有，则是的单峰区间．定理3.1说明，经过函数值的比较可以把单峰区间缩短为一个较小的单峰区间．换句话说利用这个定理可以把搜索区间无限缩小，

12、从而求到极小点。搜索区间及其确定方法由前面关于求解最优化问题概述中我们知道，从已知迭代点出发按照基本迭代格式来求解最优化问题，其关键在于如何构造一个搜