《5-优化设计-2下降迭代原理和一维优化方法概要》由会员分享,可在线阅读,更多相关《5-优化设计-2下降迭代原理和一维优化方法概要(29页珍藏版)》请在金锄头文库上搜索。
1、1,一维求优的实现原理-数值迭代,一 维 优 化 方 法,、概念:针对一元函数进行求优的相关数值迭代方法的总称。,2,数值迭代实现求优的方法原理 -下降迭代算法复杂函数优化方法基本原理,) 特点用途:解决多变量、多约束的非线性极小化问题。 )下降迭代法基本思路 依优化目标,按照某一迭代格式,从一个初始点X(0)出发逐步构造一个点列 X(0)、 X(1)、 X(2)、 、X(k)、 X(k+1) X* 保证目标函数值依点列递减 f(X(0) f(X(1) f(X(k) f(X(k+1) min,3,k=k+1,) 下降迭代法基本流程,4,)下降迭代算法的关键问题 下一迭代点的构造方向 搜索方向不
2、同将构成不同的下降迭代算法 下一迭代点构造的距离步长因子 一般通过一维搜索法取得最优步长因子 何时停止构造下一迭代点收敛准则 用以判断迭代点是否能够作为最优点,) 下降迭代算法迭代算式的基本形式,5,5)下降迭代算法的基本步骤 1)给定一个初始点X(0)和收敛精度 2)选取搜索方向S(k) 3)确定步长因子a,沿搜索方向构造新迭 代点 4)基于新迭代点进行收敛性判断(若新点满足收敛精度,则其为最优点,终止计算;否则,以其为新起点,转步骤2进行下一轮迭代),6,、下降迭代算法收敛准则,(1)点距准则:用相邻两迭代点距离判断,(2)值差准则:用相邻两迭代点函数值差判断,7,(3)梯度准则:用相邻两
3、迭代点梯度模长判断,8,下降迭代算法小节,)本质和内涵: 下降优化的目标和依据 迭代优化的方法和手段 )作用价值: 迭代求优的理论依据、方法基础 )地位: 目前实际中所使用各种一维、多维优 化方法所共同遵循的基本方法。,9,一 维 优 化 方 法 一维搜索法,1.概念:基于下降迭代原理,通过数值迭代求解一元函数极小值的方法 最基本、简单的优化方法,.用途: 一元函数求优 多元函数优化问题搜索方向上求最优步长,10,、一维搜索法的实现步骤和方法,确定极值点的初始搜索区间,进 退 法,在极值区间搜索极值点,黄 金 分 割 法,二 次 插 值 法,11,、进退法,1)进退法确定初始搜索区间的原理 查
4、找目标函数上相邻三点函数值按“高低高”变化的单谷区间或按“低高低”变化的单峰区间。,12,函数在单谷区间中一定存在极小值,13,函数在单峰区间中一定存在极大值,a1,a2,a3,t0,t0,2t0,a,F(x),14,)进退法确定初始搜索区间的思路,单 谷 区 间,目标函数三个试算点,X1 X2 X3,f(x1)f(x2)? f(x3)f(x2)?,f(x1)f(x2)? f(x3)f(x2)?,计算比较三点函数值,单 峰 区 间,Y,Y,更新试算点,更新试算点,N,N,求极小值,求极大值,15,极小点在X3右侧,在X3右侧按一定步长构造两试算点继续比较 X1=x3 X2=x3+h X3=x3
5、+2h,)试算点更新方法(以求极小值为例),: 如果f(x1)f(x2), f(x2) f(X3),16,在X左侧按一定步长构造两试算点继续比较 X=x X2=xh X=x2h,2: 如果f(x1)f(x2), f(x2) f(X3),极小点在X1左侧,17,极小点在X1,X3之间,搜索结束 区间X1,X3 为极值搜索区间,3: 如果f(x1)f(x2), f(x2) f(X3),18,)进退法算法步骤 、针对目标函数,给定三个试算点 x1 ,x2,x3, (x1x2x3) 、计算比较x1,x2,x3三点函数值大小,并根据函数值大小更改试算点x1,x2,x3 、继续比较三试算点函数值大小直至:
6、 f(x1)f(x2),f(x2)f(X3) 或 f(x1)f(x2),f(x3)f(X2) 为止。,19,、黄金分割法、二次插值法原理,区间削去不断从极值区间一侧删除不含极值点的部分,使区间逐步缩短逼近极值点,20,1)方法特点:基于区间消去原理以0.618为缩小比例生成内点,进行区间削去。,、黄金分割法,)、黄金分割法内点迭代公式,X1=a+(1- )(b-a) X2=a +(b-a) =0.618,21,给定搜索区间a0, b0、收敛精度 a=a0;b=b0 x1=a+0.382(b-a),f1=f(x1) x2=a+0.618(b-a),f2=f(x2),是,否,是,停止 X*=(b+
7、a)/2,以a,x2为新搜索区间 a0=a;b0=x2,是,否,以x1,b为新搜索区间 a0=x1;b0=b,否,停止 X*=(b+a)/2,) 黄金分割法运算流程(以求极小值为例),f1f2,22,、 二次插值法,)二次插值法特点:以极值点搜索区间中三点所构造的目标函数的二次插值函数(目标函数二次近似多项式)的极值点作为内点,进行区间削去。,x1=x2 x2xp,fpx2,x3=x2 x2=xp,fpf2 xpx2,23,插值多项式基本形式:,) 二次插值法的插值多项式,f(x) =a0+a1x +a2x2,X1,X2,X3是依据进退法所确定极值搜索区间的两端点和一内点,插值多项式系数计算方
8、法:,24,f(x) =a0+a1x +a2x2,对于目标函数的二次插值法多项式,由f(x)=0可得其极小点为,)插值法多项式极值计算方法,代入系数a1, a2计算公式,25,4)二次插值法收敛条件和极值判定,收敛条件:以当前迭代区间两内点Xp,X2的距离充分小作为收敛准则,极值判定原则:根据收敛时点Xp,X2 处函数值大小,以小者或大者为极值点,)优势 基于目标函数近似插值多项式函数的极值点,可快速收敛到极值点,26,由于 ,应加大步长继续前探,例:用二次插值法求函数 的极小点,给定,解:1)进退法确定初始搜索区间,由于 可知初始区间已经找到,即,27,2)用二次插值法逼近极小点,给定初始区间内相邻三点及函数值为:,代入插值点计算公式可得,由于,故新区间为:,28,由于,故应继续作第二次插值计算,在新区间内给定相邻三点及其函数值依次为:,将它们代入插值点计算公式得新的插入点及其函数值为:,29,由于,故一维搜索结束,极小点和极小值为:,