资源预览内容
第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
第9页 / 共31页
第10页 / 共31页
亲,该文档总共31页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1,第 四 章,最优化搜索算法的结构与一维搜索,2,4.1 常用的搜索算法结构,一、收敛性概念: 考虑(fs) 设迭代算法产生点列x(k) S.1. 理想的收敛性:设x*S是g.opt.当x* x(k) 或 x(k) x*, k,满足 时,称算法收敛到最优解 x*。,3,4.1 常用的搜索算法结构,由于非线性规划问题的复杂性,实用中建立下列收敛性概念 :2. 实用收敛性:定义解集 S* = x | x 具有某种性质 例:S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (为给定的实数,称为阈值),4,4.1 常用的搜索算法结构,一、收敛性概念: 考虑(fs)2.实用收敛性(续)收敛性:设解集S* ,x(k)为算法产生的点列。下列情况之一成立时,称算法收敛: 1x(k) S*; 2x(k) S*, k,X(k)任意极限点S* 。 全局收敛:对任意初始点x(1),算法均收敛。 局部收敛:当x(1) 充分接近解x*时,算法才收敛。,5,4.1 常用的搜索算法结构,二、收敛速度 设算法产生点列x(k),收敛到解x*,且x(k)x*, k,1.线性收敛: 当k充分大时成立。2.超线性收敛: 3.二阶收敛: 0,是 使当k充分大时有,6,4.1 常用的搜索算法结构,二、收敛速度(续)定理:设算法点列x(k)超线性收敛于x*,且x(k)x*, k,那么证明只需注意| |x(k+1) x* | -| x(k) x* | | |x(k+1) x(k) | |x(k+1) x* | +| x(k) x* | ,除以| x(k) x* | 并令k,利用超线性收敛定义可得结果。,7,4.1 常用的搜索算法结构,三、二次终结性一个算法用于解正定二次函数的无约束极小时,有限步迭代可达最优解,则称该算法具有二次终结性。二次终结性=共轭方向+精确一维搜索。共轭方向 定义: 设 Ann 对称正定,d (1),d (2) Rn , d (1) 0,d(2) 0,满足d(1)TAd(2)=0, 称d(1),d(2) 关于矩阵A共轭。 共轭向量组:d(1),d(2), ,d(m) Rn 均非零,满足d(i)TAd(j)=0,(ij) .,8,4.1 常用的搜索算法结构,三、二次终结性(续) 当A=I(单位矩阵)时, d(1)TAd(2)= d(1)Td(2)=0,即正交关系。 当d(1),d(2), ,d(m) 关于正定矩阵A两两共轭时, d(1),d(2), ,d(m) 线性无关。 proof: 设d= 1 d(1)+ 2d(2)+ md(m) =0, j=1,2, ,m, d(j)TAd= jd(j)TAd(j)=0 d(j)TAd(j) 0,故j =0,即线性无关。 超线性收敛和二次终结性常用来讨论算法的优点。,9,4.1 常用的搜索算法结构,四、下降算法模型 考虑(fs) 常用一种线性搜索的方式来求解:迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。下降方向 : 设 S,d Rn,d0,若存在 ,使 ,称d 为 在 点的下降方向。,10,4.1 常用的搜索算法结构,四、下降算法模型(续)可行方向:设 S,dRn,d0,若存在 ,使 ,称d 为 点的可行方向。同时满足上述两个性质的方向称下降可行方向。,11,4.1 常用的搜索算法结构,模型算法,线性搜索求 ,新点使x(k+1)S,yes,no,12,4.2 一维搜索,一元函数求极小及线性搜索均为一维搜索。常用于求: min f(x(k)+ d(k)=() s.t. S S有3种情况(-,+)或(0, + )或a,b一、缩小区间的精确一维搜索:考虑问题(P) min () s.t. , ():RR1、不确定区间及单峰函数 不确定区间: , 含()的最小点,但不知其位置,13,4.2 一维搜索,一、缩小区间的精确一维搜索(续)定义:设: , R, * , 是在, 上的最小点 ,若对任意1 ,2, 1 (2); 2 若1 * ,则(1) (2).则称()在, 上强单峰。 若只有当(1) (* ), (2) (* )时,上述1, 2 式才成立,则称()在, 上单峰。,14,4.2 一维搜索,一、缩小区间的精确一维搜索(续)若对任意1 ,2, 1 (2); 2 若1 * ,则(1) (2).则称()在, 上强单峰。 若只有当(1) (* ), (2) (* )时,上述1, 2 式才成立,则称()在, 上单峰。,15,4.2 一维搜索,一、缩小区间的精确一维搜索(续)定理:设:RR 在, 上单峰, 。那么 1若() (),则() (), ,;如左下图 2若() (),则()(), , ;如右下图,16,4.2 一维搜索,一、缩小区间的精确一维搜索(续)Proof. 1反证:设* ,为最小点,,及*,使 () ( ) (),矛盾(假设); 若* ,),由定义及 *, ( ) (), 矛盾(条件); 于是结论成立。 2 的证明类似(略)。注:上述定理为缩短区间的算法提供了理论根据。,17,4.2 一维搜索,一、缩小区间的精确一维搜索(续)2、黄金分割法(0.618 法)通过上述定理,选二点0 时, 在上升段, * ,去掉, ; () ,去掉 , ;(自己画算法框图),21,4.2 一维搜索,4、进退法求初始不确定区间 找三点使两端点的函数值大于中间点的函数值。 思路:任取0,步长 0,取1=0 + , 1若(0 ) (1), 令=2 (步长加倍),2=0 - , 若(2 )(0),则停,= 2,= 1 (图1) 2若(0 )(1), 令=2 , 2=1 + , 若(2 )(1),则停,= 0 ,= 2 (图2),22,4.2 一维搜索,4、进退法求初始不确定区间(续)(自己画算法框图)注意:1 选择要适当。(太大含多个单峰区间,太小迭代次数增加); 2( )单调时无结果,(加迭代次数限制); 3可与中点法结合寻找单调区间(思考)。,23,4.2 一维搜索,二、牛顿法(Newton)和插值法1、Newton法: 对 在 k 点展开: ( )= (k )+ (k )(- k ) + (1/2) (k )(- k )2 + o (- k )2 取二次式(略去高阶项): qk() = (k) +(k)(-k) + (1/2)(k)(-k)2,24,4.2 一维搜索,二、牛顿法(Newton)和插值法1、Newton法:(续) 用qk()作为()的近似,当(k) 0时,其驻点为极小点: qk()= (k) +(k)(- k )=0 得 k +1=k (k) /(k) 取k +1为新的迭代点。以上过程即Newton法。特点:二阶、局部收敛。 (算法框图见下页),
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号