第二次一维最优化ppt课件

1、一一 维最优化一维搜索维最优化一维搜索q 进退法进退法q 二次逼近法二次逼近法q 黄金分割法黄金分割法一一. . 一维最优化问题一维最优化问题下降迭代算法中最优步长确实定下降迭代算法中最优步长确实定)(min)(kkkkkdxfdxf 一维最优化问题：一维最优化问题：)(minxfRxts .极值点的必要条件：极值点的必要条件：0)( xf.kxkd.k 二进退法二进退法思想思想从一点出发从一点出发, ,按一定的步长按一定的步长, , 试图确定出函数值呈现试图确定出函数值呈现“高高- -低低- -高高的三点。一个方向不胜利，就退回来，再沿相反方向寻觅。的三点。一个方向不胜利，就退回来，再沿相反

2、方向寻觅。进退法的计算步骤进退法的计算步骤,. 1)1(x给给定定初初始始点点, 0 h初初始始步步长长),()1(xf计计算算. 0 k并并令令,. 2) 1 () 3(hxx 令令),()3(xf计计算算.1: kk令令),()(. 3) 1 () 3(xfxf 若若，则则转转 45.否否则则，转转,. 4)1()2(xx 令令,)3()1(xx . 2,2:转转令令hh 如何确定一个包含极小点的区间？如何确定一个包含极小点的区间？,1.5 k若若.否否则则，停停止止计计算算,:hh 令令,)3()2(xx .2转转。即即为为包包含含极极小小点点的的区区间间或或区区间间,)2()3()3(

3、)2(xxxx例：例：)1(xhxx ) 1 () 3()2(x)1(x)3(x)1(x)3(xhh :)1(x)2(x)3(x,)3()2(xx,)2()3(xx三三. . 二次逼近法抛物线插值二次逼近法抛物线插值思想思想在极小点附近，用二次三项式在极小点附近，用二次三项式),()(xfx 逼近目标函数逼近目标函数 处有相同的函数值，处有相同的函数值，在三点在三点与与令令)3()2()1()()(xxxxfx 并并假假设设).()(),()()3()2()2()1(xfxfxfxf )1(x)2(x)3(x)(xf)(x x*x,)(2cxbxax 设设)()()1(2)1()1()1(xf

4、cxbxax )()()2(2)2()2()2(xfcxbxax )()()3(2)3()3()3(xfcxbxax .)(cbx和和的的系系数数近近函函数数解解上上述述方方程程组组，可可得得逼逼 的的极极小小点点，再再求求函函数数)(x 令令cxbx2)( , 0 解得解得.2cbx 如何计算函数如何计算函数?)(x 。的的极极小小点点的的估估计计值值作作为为以以)(xfx抛物线插值算法步骤：抛物线插值算法步骤：, ,)1()3()1(xx给定初始区间给定初始区间).()(),()()3()2()2()1(xfxfxfxf 设设。给给定定精精度度。令令 )2()0(1:xxk 。令令。设设3

5、,2,1, )()()()2()()(2 ixfxcxbxaxii 解出解出。的的极极小小点点解解出出。系系数数cbxxcbak2)(,)( 及及其其的的函函数数值值最最小小的的点点中中选选择择和和从从)(,)3()()3()2()1(xfxxxxk。）转转（。令令。重重新新标标记记为为左左、右右两两点点，21:,)3()2()1( kkxxx）。否否则则转转（，则则算算法法停停止止若若3,| )()(|)1()( kkxfxf其它插值算法：其它插值算法：1. 1. 三次插值算法；三次插值算法；2. 2. 有理插值。有理插值。四四. . 黄金分割法黄金分割法0.6180.618法法1. 1.

6、单谷函数单谷函数定义：设定义：设)(xf是区间是区间,ba上的一元函数，上的一元函数，x是是)(xf在在,ba上的极小点，且对恣意的上的极小点，且对恣意的, ,2121xxbaxx 有有a a当当xx 2时，时，; )()(21xfxf b b当当时时，xx 1. )()(21xfxf a. . .b. .x. . . .1x2x那么称那么称 是单谷函数。是单谷函数。)(xf. . .性质：经过计算区间性质：经过计算区间,ba内两个不同点的函数值，就可以内两个不同点的函数值，就可以确定一个包含极小点的子区间。确定一个包含极小点的子区间。定理定理 设设是区间是区间,ba上的一元函数，上的一元函数

7、，x是是)(xf在在,ba上的极小点。任取点上的极小点。任取点)(xf, ,badc 那么那么有有1 1假设假设)()(dfcf ，那，那么么; ,bcx 2 2假设假设, )()(dfcf 那那么么。,dax a. . .b. .x. . .cd2. 2. 黄金分割法黄金分割法思想经过选取试探点使包含极小点的区间不断缩短，经过选取试探点使包含极小点的区间不断缩短，直到区间长度小到一定程度，此时区间上各点的函数直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。值均接近极小值。下面推导黄金分割法的计算公式。下面推导黄金分割法的计算公式。上上单单谷谷，在在设设,)(11baxf.,11

8、bax 极极小小点点假设进行假设进行次迭代前次迭代前第第 k,kkbax ,kkkkba 取取规规定定.kk , )()(kkff 和和计算计算分分两两种种情情况况：, )()(. 1kkff 若若,1kka 则则令令;1kkbb , )()(. 2kkff 若若,1kkaa 则则令令.1kkb ？与与如何确定如何确定kk kkkkab . 1比率相同，即比率相同，即每次迭代区间长度缩短每次迭代区间长度缩短. 2)0()(11 kkkkabab)1()2(）可可得得：）与与（由由式式（21 )()(1(kkkkkkkkabaaba )3()4(件：件：要求其满足以下两个条要求其满足以下两个条k

9、akbk ku？取取值值的的确确定定 经过确定经过确定 的取值，使上一次迭代剩余的迭代点恰与下一次的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。迭代的一个迭代点重合，从而减少算法的计算量。 , )()()1(kkuffk 次次迭迭代代时时有有设设在在第第则则有有。,11kkkkuaba ,111k kuk 次次迭迭代代时时选选取取在在第第）有）有则由（则由（4)(1111 kkkkabau )(2kkkaba 。不不必必重重新新计计算算因因此此则则，如如果果令令112,1 kkkuu 618. 021512 。次次迭迭代代时时有有若若在在第第)()()2

10、(kkuffk 同理可得同理可得618.0 时时,.1kk 算法步骤：算法步骤：0.,. 111 精精度度要要求求给给定定初初始始区区间间ba. 1: k令令),(382. 01111aba 令令),(618. 01111aba ).()(11 ff与与并并计计算算,. 2 kkab若若停止，停止，.2kkabx 且且否则，否则，；时，转时，转当当3)()(kkff . 4)()(时，转时，转当当kkff ,. 31kka 令令,1kkbb ,1kk ),(618. 01111 kkkkaba ),(1 kf 计计算算。转转 2,. 41kkaa 令令,1kkb ,1kk ),(382. 01

11、111 kkkkaba ),(1 kf 计计算算, 1: kk令令。转转 2, 1: kk令令例例. . 用用 0.618 0.618 法计算法计算 f (t) = (t -1)2 f (t) = (t -1)2 在在 0 , 3 0 , 3 上的极小点。上的极小点。854. 1)03(618. 00146. 1)03(382. 0011 第第一一次次迭迭代代解解. .7293. 0854. 0)(,0213. 0146. 0)(2121 ff854. 10,)()(11，新新的的搜搜索索区区间间 ff 708. 0)0854. 1(382. 000213. 0)(,146. 12212 f第第二二次次迭迭代代)(0851. 0)1708. 0()(222 ff 854. 1708. 0，新新的的搜搜索索区区间间416.