维搜索方法 目标函数为单变量的非线性规划问题称为一维搜索问题 (又称为线性搜索问题)。 mn t20 (0≤ t<t) ,其中t∈R。 解决一维搜索MP问题的方法统称为一维搜索方法。主 要有: ●精确一维搜索方法:(1)0.618法,(2) Newton法。 ●非精确一维搜索方法:(1) Goldstein法,() Armijo 法。 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 2 目标函数为单变量的非线性规划问题称为一维搜索问题 (又称为线性搜索问题)。 min (t) (0 ) 0 max t t t ,其中 t R。 解决一维搜索 MP 问题的方法统称为一维搜索方法。主 要有: ⚫精确一维搜索方法:(1)0.618 法,(2)Newton 法。 ⚫非精确一维搜索方法:(1)Goldstein 法,(2)Armijo 法。 一维搜索方法
0.618法的基本思想 )是一个函数。如果存在一个r∈[ab,使得q(O)在, r上严格递减,在r,矶上严格递增,则称函数p(0)在|a,b 上是单谷的,区间|a,b称为g(的单谷区间。 ●以单谷区间{a,b为初始搜索空间。首先按照某种方法确 定[a,b内两个探索点t,t ●观测:若q(t1)≤q(1),则∈{t]l。 若φ()≥qp(),则∈团,b]。 ●然后以a,t(或[t,b)为新的搜索区间,确定新的探索 点,继续进行搜索。 ●如何使搜索区间宽度逐次递减? 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 4 ⚫(t)是一个函数。如果存在一个 t* [a, b],使得(t)在[a, t*]上严格递减,在[t*, b]上严格递增,则称函数(t)在[a, b] 上是单谷的,区间[a, b]称为(t)的单谷区间。 ⚫以单谷区间[a, b]为初始搜索空间。首先按照某种方法确 定[a, b]内两个探索点 t1, t2。 ⚫观测:若(t1) (t2),则 t* [a, t2]。 若(t1) (t2),则 t* [t1, b]。 ⚫然后以[a, t2](或[t1, b])为新的搜索区间,确定新的探索 点,继续进行搜索。 ⚫如何使搜索区间宽度逐次递减? 0.618法的基本思想
使搜索区间宽度逐次递减 在搜索过程中,既有可能以|a,为新的搜索区间,也有 可能以[t,b为新的搜索区间。因此令二者宽度相等,即 a=b-t ●希望搜索区间宽度能按比例递减。于是,令 -a b b-a b-a 因此,41=a+(-o)b-a),2=a+o(b-a)。(2) tu t2 b ●假设以|a,l为新的搜索区间([4,b的情形与此对称) 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 5 ⚫在搜索过程中,既有可能以[a, t2]为新的搜索区间,也有 可能以[t1, b]为新的搜索区间。因此令二者宽度相等,即 t2 – a = b – t1。 ⚫希望搜索区间宽度能按比例递减。于是,令 b a b t b a t a − − = − − = 2 1 , (1) 因此,t = a +(1−)(b−a) 1 ,t = a +(b−a) 2 。 (2) a t1 t2 b ⚫假设以[a, t2]为新的搜索区间([t1, b]的情形与此对称)。 使搜索区间宽度逐次递减
使搜索区间宽度逐次递减 ●设,中的新的探索点为和2。 ●由于搜索区间宽度要按相同比例递减,因此 (3) ●并且,希望在新一轮的搜索中,上次的探索点能够被重复利 用(以减少计算)。不妨设重复利用t为新的探索点,而 2重新选择(1<t2)。 因此,12-1=12-1=0(2-d)=0(b-a)。(由(1) ●由(2,12-1=(20-1%b-a) 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 6 ⚫设[a, t2]中的新的探索点为 1 t 和 2 t 。 ⚫由于搜索区间宽度要按相同比例递减,因此 = − − = − − t a t t t a t a 2 2 1 2 2 。 (3) ⚫并且,希望在新一轮的搜索中,上次的探索点能够被重复利 用(以减少计算)。不妨设重复利用 t1为新的探索点 1 t ,而 2 t 重新选择( 1 2 t t )。 ⚫因此, t −t = t −t = (t −a) = (b − a) 2 2 1 2 1 2 。(由(1)) ⚫由(2),t −t = (2 −1)(b−a) 2 1 。 使搜索区间宽度逐次递减
使搜索区间宽度逐次递减 于是,2=20-1。但这将得到O=1,搜索区间不能递减。 这表明将t用作不合适。 ●将t用作2。 (3,(1)→4-a=0(2-a)=o(b-a)。 (2)→1-a=(-0)(b-a ●于是,02+0-1=0。解三次方程,得s3 ≈0.618 (另一个根舍弃)。 ●这就是0618法的由来。 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 7 ⚫于是, 2 1 2 = − 。但这将得到 =1 ,搜索区间不能递减。 这表明将 t1用作 1 t不合适。 ⚫将 t1用作 2 t 。 ⚫(3), (1) t − a = (t − a) = (b − a) 2 1 2 。 ⚫(2) t −a = (1−)(b−a) 1 。 ⚫于是, 1 0 2 + − = 。解二次方程,得 0.618 2 5 1 − = (另一个根舍弃)。 ⚫这就是 0.618 法的由来。 使搜索区间宽度逐次递减
0.618法 (E>0为输入参数,表示最后区间精度。) 1确定单谷区间a,b为初始搜索区间。 2探索点th2赋初值:←-a+0.382(b-a),q1←-q(1); ta+0.618(-a),φ2φ(t2) 2011年11月 山东大学软件学院 8
2011年11月 山东大学 软件学院 8 ( > 0 为输入参数,表示最后区间精度。) 1 确定单谷区间[a, b]为初始搜索区间。 2 探索点 t1, t2赋初值:t1 a + 0.382(b – a),1 (t1); t2 a + 0.618(b – a),2 (t2)。 0.618法
0.618法 3 while b-a>edo 4 if (p1 <(P2 then 5b←t2,t2←t1,q2←q1 6←a+0.382(b-a),q1←φ(t) else 8 a(t1,t<t2,q1←q2 ←a+0.618(b-a),q2<φ(t2)。 10 endif endwise l2 return t,qp1作为最后求到的最小值估计。 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 9 0.618法 3 while b – a > do 4 if 1 < 2 then 5 b t2, t2 t1, 2 1。 6 t1 a + 0.382(b – a),1 (t1)。 7 else 8 a t1, t1 t2, 1 2。 9 t2 a + 0.618(b – a),2 (t2)。 10 endif 11 endwhile 12 return t1, 1作为最后求到的最小值估计