第三章一维优化方法

1、1 3.1 搜索区间的确定搜索区间的确定 进退法进退法 3.2一维搜索的最优化方法一维搜索的最优化方法3.2.1 格点法格点法3.2.2 黄金分割法黄金分割法3.2.3 二次插值法二次插值法2第三章第三章 一维优化方法一维优化方法 用数值迭代法求解一元函数的极小点和极小值方法称为一维搜用数值迭代法求解一元函数的极小点和极小值方法称为一维搜索优化方法。索优化方法。多维优化问题常常是通过一系列的一维优化方法来实现的。因当搜多维优化问题常常是通过一系列的一维优化方法来实现的。因当搜索方向索方向 确定后，新设计点确定后，新设计点 总是位于过点总是位于过点 的的 方向上。步长方向上。步长 不同不同, 得

2、到的设计点和相应的函数值得到的设计点和相应的函数值就不同，即只有一个就不同，即只有一个 变量。变量。)()()1(KKKSXX)(KS)(KS)(KX3ox1x2( )kX(1)kX*x( )kS(1)( )( )( )kkkkX= X+S由前基本迭代公式由前基本迭代公式:( )k待求待求已知已知(1)( )()minminkkkkF X=F X+Smin( )f这种在给定方向上确定最优步长的过程这种在给定方向上确定最优步长的过程, ,称一维优称一维优化。化。 称为最优步长称为最优步长 min( )f x( )k41x( )F x2x( )fo*X( )fO*n维问题维问题一系列一系列一维优化

3、问题一维优化问题53.1 3.1 搜索区间的确定搜索区间的确定x( )f xo单峰函数单峰函数 a*xb用尽量少的计算量用尽量少的计算量,尽快确尽快确定包含定包含x* 的区间的区间a, b 关键关键找三点找三点: :“高高- -低低- -高高”一维搜索最优化过程可分为两步一维搜索最优化过程可分为两步: :1 1、确定极小点所在的初始搜索区间、确定极小点所在的初始搜索区间aa，bb2 2、在区间、在区间aa，bb中搜索极小点。中搜索极小点。 采用某种方法将此区间逐步缩小，使其达到包含极小点采用某种方法将此区间逐步缩小，使其达到包含极小点x*在内在内 的很小邻域（的很小邻域（ ） 63.1 3.1

4、 搜索区间的确定（进退法）搜索区间的确定（进退法）ox( )f x1x2x3x1x3xa2xb函数为函数为yf(x), 给定初始点给定初始点x1,选定恰当的初始步长为选定恰当的初始步长为h0 一、试探搜索一、试探搜索由于最小点由于最小点x*的位置是未知的的位置是未知的，所以首先要试探最小点，所以首先要试探最小点x*位于初始点位于初始点x1的左方的左方或右方，然后再确定是前进还是后退或右方，然后再确定是前进还是后退111,( )xyf x21022,()xxhyf x比较比较y1、y2大小大小 21,yy前进前进21,yy后退后退二、前进搜索二、前进搜索0,2hhhh3233,( )xxhyf

5、x比较比较y y2 2、y y3 3大小：大小： 23,yya, b确定确定23,yy继续前进继续前进置换点号置换点号12122323,xxyyxxyy7由前：由前：ox( )f x1x2x3x1x3xa2xb三、后退搜索三、后退搜索比较比较y y1 1、y y2 2大小大小 21,yy前进前进21,yy后退后退0,2-hhhh3233,( )xxhyf x比较比较y y2 2、y y3 3大小：大小： 23,yya, b确定确定23,yy继续后退继续后退12122121,xxyyxxyy置换点号1x2x置换点号12122323,xxyyxxyy89例题例题3.1 试用进退法确定函数试用进退法

6、确定函数f(x)=x2- -6x+9的一维优化搜索区间的一维优化搜索区间a，b。设初始点。设初始点x10，初始步长，初始步长h0=1。解：按流程图解：按流程图3.4，计算过程如下：，计算过程如下： 由于由于y y2 2yyy3 3，再作前进搜索，再作前进搜索， x x1 1x x2 2=1=1，y y1 1y y2 2=4=4 x x2 2x x3 3=3=3，y y2 2y y3 3=0=0 h h2h=42h=4 x x3 3x x2 2+h=7+h=7，y y3 3f(xf(x3 3)=16)=16 再比较再比较y y2 2与与y y3 3，有，有y y2 2yy3 3，则取，则取 a

7、ax x1 1=1=1，b bx x3 3=7=7 103.2 3.2 一维搜索的最优化方法一维搜索的最优化方法 逐渐缩小搜索区间逐渐缩小搜索区间 3.2.1 格点法格点法x( )f xo在区间在区间a，b的内部取的内部取n个个内等分点：内等分点： x1，x2，xn区间区间a，b被分成被分成(n+1)等等分，各分点的坐标为分，各分点的坐标为: 1,2,.,1kb axakknn ab1xnx2x1mxmx1mx1mymy1my1212, ., .,nnxxxyyy计算计算找出找出minmin,1,2,.,kyknyab新区间新区间新区间新区间11,mmaxbx*11:?:mmmyesxxxxn

8、o再分格点再分格点区间缩短率: = 新区间长度老区间长度21n11格点法特点：格点法特点： 程序简单，但计算效率较低，即在一定精度要求下程序简单，但计算效率较低，即在一定精度要求下计算函数值的次数较多，因而不宜用于维数较高的计算函数值的次数较多，因而不宜用于维数较高的复杂问题中。复杂问题中。 12(1)(2)()()f af a与与(1)(2)aa与与(1)(2)()()f af a第一种情况：第一种情况：可丢掉可丢掉 部分部分(2)(, ab基本思想基本思想:逐步缩小搜索区间逐步缩小搜索区间,直至最小点存在的范围达到允许的直至最小点存在的范围达到允许的 误差范围为止误差范围为止.取中间点为极

9、小点取中间点为极小点.在在a,b内任取两点内任取两点 , 且且 计算函数值计算函数值: 进行比较可得进行比较可得:3.2.2 黄金分割法黄金分割法(1)(2),aaab13(1)(2)()()f af a(1)(2)()()f af a第二种情况：第二种情况：第三种情况：第三种情况：可丢掉可丢掉 部分部分(1) ,)a a问题问题1:= =?问题问题2:如何取点如何取点?14(1)(2),:.aa在在区区间间中中的的位位置置相相对对边边界界对对称称缩缩小小后后保保留留点点在在新新区区间间中中的的位位置置与与丢丢去去点点在在原原区区间间中中原原的的位位置置相相当当则则LlllL由此得由此得解此方

10、程得两个根取其正根为解此方程得两个根取其正根为 =0.6180339887=0.6180339887 0)(2lLLl01)()(2LlLl012215 15问题问题2:如何取点如何取点?0a0b1x2x1y2y1b2x1x1a2a2y1y2b取点规则取点规则:120.382()0.618()xab axab a 右图示右图示,第一次区间缩短第一次区间缩短:120.382()0.618()xab axab a 第二次区间缩短第二次区间缩短:100.618LL2110.382() xxxab a20100.3820.6180.618LLLL0L100.618LL00.382 L200.382LL

11、16终止准则终止准则: :( )( )kkba2a0a0b1x2x1y2y1b2x1x1a2y1y2b( )( )*2()kkabxff x17例题例题3.3试用黄金分割法求目标函数试用黄金分割法求目标函数f(x)=x2-6x+9的最优解。给定初始区间的最优解。给定初始区间1，7，收敛精度，收敛精度0.4。解：第一次区间缩短：解：第一次区间缩短： 计算两内点及对应函数值：计算两内点及对应函数值： x1=a+0.382(b-a)=3.292，y1=f(x1)=0.085264 x2=a+0.618(b-a)=4.708，y2=f(x2)=2.917264 作函数值比较，可见作函数值比较，可见y1

12、 第二次区间缩短第二次区间缩短: 置换置换： x2x1=3.292，y2y1=0.085 264 增补增补: x1=a(1)+0.382(b(1)- -a(1)2.416456， y1=f(x1)=0.340524 2a0a0b1x2x1y2y1b2x1x1a2y1y2b18各次缩短区间的计算数据见表各次缩短区间的计算数据见表3.2。第六次区间缩短的端点。第六次区间缩短的端点a(6)2.750 917，b(6)3.085 305，b(6)-a(6)0.334 388，满足精度要求，终止计算。，满足精度要求，终止计算。取最优解为取最优解为:19基本原理基本原理: :利用一个低次插值多项式来逼近原

13、目标函数利用一个低次插值多项式来逼近原目标函数, ,然然后求该多项式的极小点后求该多项式的极小点, ,并以此作为目标函数的近似极并以此作为目标函数的近似极小点小点, ,反复使用此法反复使用此法, ,逐次拟合逐次拟合, ,直到满足给定的精直到满足给定的精度为止度为止. . 常用的插值多项式为二次或三次多项式常用的插值多项式为二次或三次多项式, ,分别称为二分别称为二次插值法或三次插值法。次插值法或三次插值法。一、二次插值函数的构成一、二次插值函数的构成：p(x)=Axp(x)=Ax2 2+Bx+C +Bx+C 式中式中A A、B B、C C为待定系数，为待定系数，可由可由P P1 1、P P2

14、2、P P3 3三个插值结点三个插值结点的信息按下列线性方程组确定的信息按下列线性方程组确定3.2.3 二次插值法二次插值法20( )f x1P3P2Pa1xb3x 2x*xf(x)搜索区间为搜索区间为a，b取点取点x1、x2、x3，构成二次函数，构成二次函数2130.5xxx开始时开始时:计算计算112233(),(),()ff xff xff x得三点得三点:111122133(,),(,),(,)P xfP xfP xf作插值函数作插值函数p(x)2( )p xxAxBC211112111221113()()()p xxxfp xxxABCABCABCfp xxxf解方程组，得待定系数解

15、方程组，得待定系数A、B、C *Px( )p x*Pf求求p(x)的极小点的极小点x*P ，与，与x2比较比较区间缩短区间缩短1x3x2xx1=ax3=b21一、二次插值函数的构成一、二次插值函数的构成 2( )p xxAxBC解方程组，得待定系数解方程组，得待定系数A、B、C 231312123122331()()()()()()xxfxxfxxfxAxxxxx 222222231312123122331()()()()()()xxfxxfxxBfxxxxxx322311313221123122331()()()()()()xxx x fxxx x fxx xCx fxxxxxx22求二次插

16、值函数的极小点：求二次插值函数的极小点： 222222231312123231312123*1 ()()()22()()()PBxxfxxfxxfAxxfxxxfxxf 3113121211223()()() ()ffcxxffxxccxx令令1132*12Pcxxcx( )20p xxAB令令23二、二、区间区间的的缩短缩短*22ppxxff*22ppxxff*22ppxxff*22ppxxff24区间区间的的缩短程序框图缩短程序框图25三、终止准则三、终止准则 ( )f x1P3P2Pa1xb3x 2x*(1)Px( )p x*(1)Pf1x3x2x*(1)*(2)*(1)*(*), ., .kkPPPPxxxxx*( )*(1)kkPPxx*( )kPxx2627在流程图中有两个判别框的内容需稍加说明。其一是在流程图中有两个判别框的内容需稍加说明。其一是c2=0？若成？若成立，即：立，即：或写作或写作这说明三个插值结点这说明三个插值结点P1(x1，f1)、P2(x2，f2)、P3(x3，f3)在同一条直在同一条直线上