山东大学软件学院：非线性规划（PPT讲稿）一维搜索方法

第4章非线性规划 维搜索方法 2011年11月

2011年11月 第4章 非线性规划 一维搜索方法

维搜索方法 目标函数为单变量的非线性规划问题称为一维搜索问题 (又称为线性搜索问题)。 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 法。 一维搜索方法

0618法 2011年11月 山东大学软件学院

2011年11月 山东大学 软件学院 3 0.618法

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作为最后求到的最小值估计

例43.1 用0618法解m叭)=-2+1,搜索区间宽度到=05 14 2011年11月 山东大学软件学院 10

2011年11月 山东大学 软件学院 10 例4.3.1 用 0.618 法解 min ( ) 2 1 3 0 = − +  t t t t  ，搜索区间宽度到 = 0.5