《第5章--一维搜索.doc》由会员分享,可在线阅读,更多相关《第5章--一维搜索.doc(32页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date第5章-一维搜索第2章 线性规划第5章 一维搜索5.1 最优化算法的简单介绍1算法概念在解非线性规划时,所用的计算方法,最常见的是迭代下降算法迭代:从一点出发,按照某种规则A求出后继点用代替,重复以上过程,产生点列。规则A是在某个空间X中点到点的映射,即对每一个,有点更一般地,把A定义为点到集的映射,即对每个点,经A作用,产生一个点集.任意选取一个点,作为的后继点定义
2、1: 算法A是定义在空间X上的点到集映射,即对每一个点,给定个子集.例1 考虑线性规划:最优解设计一个算法A求出这个最优解从一点出发,经A作用得到一个闭区间.从此区间中任取一点作为后继点,得到一个点列.在一定条件下,该点列收敛于问题的解利用算法A可以产生不同的点列,如以为起点可产生点列:其聚点是问题的最优解在许多情况下,要使算法产生的点列收敛于全局最优解是比较困难的因此,一般把满足某些条件的点集定义为解集合.当迭代点属于这个集合时,就停止迭代无约束最优化问题可以定义解集合为约束最优化问题可以定义解集合为2. 算法收敛问题设为解集合,是一个算法,集合.若以任一初点开始,算法产生的序列其任一收敛子
3、序列的极限属于,则称算法映射A在Y上收敛收敛速率:定义2: 设序列收敛于,定义满足的非负数p的上确界为序列的收敛级若序列的收敛级为p,就称序列是p级收敛的若且,则称序列是以收敛比 线性收敛的若或者且,则称序列是超线性收敛的例2 序列. 序列以收敛比a线性收敛于零例3 序列 序列是2 级收敛的注1:收敛级取决于当时该序列所具有的性质,它反映了序列收敛的快慢收敛级p越大,序列收敛得越快当收敛级p相同时,收敛比越小,序列收敛得越快。5.2 一维搜索基本概念5.2.1 基本概念在许多迭代下降算法中,得到点后,需要按某种规则确定一个方向,再从出发,沿方向在直线(或射线)上求目标函数的极小点,从而得后继点
4、求目标函数在直线上的极小点,称为一维搜索,或称为线搜索一维搜索可归结为单变量函数的极小化问题求目标函数在直线上极小点转化为求一元函数的极小点一维搜索大体可分成两类:试探法: 按某种方式找试探点通过一系列试探点来确定极小点函数逼近法,或插值法:用某种较简单的曲线逼近本来的函数曲线,通过求逼近函数的极小点来估计目标函数的极小点这两类方法一般只能求得极小点的近似值,称为非精确一维搜索5.2.2 搜索区间及其确定方法一维搜索需要事先给定一个包含极小点的区间,此区间称为搜索区间。搜索区间确定方法:进退法进退法是一种试探法:从一点出发,按一定的步长,试图确定出函数值呈现“高-低-高”的三点。一个方向不成功
5、,就退回来再沿相反方向寻找进退法的计算步骤:(l)给定初点,初始步长置,计算,并置.(2)令,计算,置.(3)若,则转步骤(4);否则,转步骤(5)(4)令, , , ,置,转步骤(2). (5) 若,则转步骤(6);否则,转步骤(7).(6) 置, ,转步骤(2).(7) 令,,停止计算得到含有极小点的区间或者注2:实际应用中,为了获得合适的,有时需要做多次试探才能成功5.2.3 单峰函数及其性质定义3: 设是定义在闭区间上的一元实函数, 是在上的极小点,并且对任意的,有当时,当时,则称是在闭区间上的单峰函数单峰函数的性质:通过计算区间内两个不同点处的函数值,就能确定一个包含极小点的子区间定
6、理1: 设f是区间上的单峰函数,,且.如果,则对每一个,有;如果,则对每一个,有.根据定理1,只需选择两个试探点,就可将包含极小点的区间缩短5.3 0.618法和Fibonacci法5.3.1 0.618法0.618 法(黄金分割法)适用于单峰函数基本思想:通过取试探点使包含极小点的区间(不确定区间)不断缩短,当区间长度小到一定程度时,区间上各点的函数值均接近极小值,因此任意一点都可作为极小点的近似 试探点计算公式:设在上单峰,极小点.设进行第 次迭代时,有为缩短包含极小点的区间,取两个试探点,并规定 (1) (2)计算步骤:(1)置初始区间及精度要求,计算试探点和,计算函数值和计算公式: 令
7、.(2)若,则停止计算否则,当时,转步骤(3);当时,转步骤(4).(3)置,, 计算函数值,转步骤(5).(4)置,, 计算函数值,转步骤(5).(5)置,返回步骤(2).例4:解下列问题:。初始区间,精度.1-11-0.2360.236-0.653-1.1252-0.23610.2360.528-1.1250.9703-0.2360.5280.0560.236-1.050-1.12540.0560.5280.2360.348-1.125-1.10650.0560.3480.1680.236-1.112-1.12560.1680.3480.2360.279-1.125-1.12370.168
8、0.279经6次迭代达到,极小点.该问题的最优解可取作为近似解5.3.2 Fibonacci法Fibonacci法与0.618法类似,也是用于单峰函数. Fibonacci法与0.618法的主要区别:(1)区间长度缩短比率不是常数,而是由Fibonacci数确定(2)需要事先知道计算函数值的次数.定义4:设有数列,满足条件:(1);(2)则称为Fibonacci数列012345678911235813213455Fibonacci法在迭代中计算试探点的公式: (3) (4)n是计算函数值的次数.利用(3)式和(4)式计算试探点时,第k次迭代区间长度的缩短比率恰为.给定初始区间长度及精度要求L,
9、可求出计算函数值的次数(不包括初始区间端点函数值的计算)由下式求出Fibonacci数,根据确定计算函数值的次数n .Fibonacci法与0.618 法的关系:(1)0.618法可作为Fibonacci法极限形式:(2)Fibonacci法精度高于0.618 法在计算函数值次数相同条件下,0.618法的最终区间大约比使用Fibonacci法长17%(3)Fibonacci法缺点是要事先知道计算函数值次数0.618 法不需要事先知道计算次数,且收敛速率与Fibonacci法比较接近.在解决实际问题时,一般采用0.618法5.4 插值法(二次)5.4.1 牛顿法(一点二次插值法)基本思想:在极小
10、点附近用二阶Taylor多项式近似目标函数,进而求出极小点的估计值考虑问题 (5)令 又令 得到的驻点,记作,则 (6)在点附近,因此可用函数的极小点作为目标函数极小点的估计如果是极小点的一个估计,那么利用(6)式可以得到极小点的一个进一步的估计.利用迭代公式(6)可以得到一个序列可以证明,在一定条件下,这个序列收敛于问题(5)的最优解,而且是2级收敛牛顿法的计算步骤:(1)给定初点,允许误差,置.(2)若,则停止迭代,得到点.(3)计算点,置,转步骤(2).注3:运用牛顿法时,如果初始点靠近极小点,则可能很快收敛;如果远离极小点,迭代产生的点列可能不收敛于极小点5.4.2 割线法(二点二次插
11、值法)基本思想:用割线逼近目标函数的导函数的曲线,把割线的零点作为目标函数的驻点的估计.迭代公式:得到序列可以证明,在一定的条件下,这个序列收敛于解(收敛级为1.618)注4:与牛顿法相比,收敛速率较慢,但不需要计算二阶导数注5:缺点与牛顿法类似,都不具有全局收敛性,如果初点选择得不好,可能不收敛5.4.3 抛物线法(三点二次插值法)基本思想:在极小点附近,用二次三项式逼近目标函数,令与在三点处有相同的函数值,并假设,.令 又令 (7) (8) (9)解方程组(7)-(9),求二次逼近函数的系数b和c为书写方便,记 由方程(7)-(9)得到 (10) (11)的极小点对应的驻点为.把驻点记作,则 (12)把作为的极小点的一个估计再从,中选择目标函数值最小的点及其左、右两点,给予相应的上标,代入(12)式,求出极小点的新的估计值.以此类推,产生点列.注6:在一定条件下,这个点列收敛于问题的解,其收敛级为1. 3-
限制150内