智能理论与技术PPT学习教案

1、会计学1 智能理论与技术智能理论与技术 第1页/共67页 2优化问题求 的极小值 |34|)( 2 xxxf 034)( 2 xxxf 1求解问题求 的根 13 2 x f(x) 132 x f(x) 一个求解可以问题转变为一个优化问题 第2页/共67页 优化模型的一般形式优化模型的一般形式 第3页/共67页 非梯度搜索非梯度搜索 x2 x 1 o (k)S(k) S(k) x(k+1) x(k) x* F(x(k) F(x(k+1) x(k+1)=x(k)+ (k)s(k)迭代公式迭代公式 在优化设计的在优化设计的 迭代运算中，迭代运算中， 在搜索方向在搜索方向s(k) 上寻求最优步上寻求最

2、优步 长长 (k) 的方法的方法 称一维搜索法。称一维搜索法。 第4页/共67页 直接搜索直接搜索 第5页/共67页 黄金分割法适用于黄金分割法适用于a,b区间上的任何单峰函数区间上的任何单峰函数 求极小值问题。对函数除要求单峰外不作其它要求，求极小值问题。对函数除要求单峰外不作其它要求， 甚至可以不连续。因此，这种方法的适应面相当广。甚至可以不连续。因此，这种方法的适应面相当广。 一、黄金分割法的原理一、黄金分割法的原理 在搜索区间在搜索区间a,b内适当插入两点内适当插入两点x1,x2 ，并计，并计 算其函数值。算其函数值。 x1,x2 将区间分为三段，通过比较函将区间分为三段，通过比较函

3、数值的大小，删除其中的一段，使搜索区间缩短。数值的大小，删除其中的一段，使搜索区间缩短。 然后再在保留下来的区间上作同样处理，如此迭代然后再在保留下来的区间上作同样处理，如此迭代 下去，使搜索区间无限缩小，从而得到极小点的近下去，使搜索区间无限缩小，从而得到极小点的近 似值。似值。 第6页/共67页 第7页/共67页 第8页/共67页 第9页/共67页 x1=a+ 0.382(b-a) x2=a+ 0.618(b-a) b-x2=x1-a x2-x1= (b-a) 第10页/共67页 kakbk kukf( k)f( uk) 1-11-0.236 0.236-0.653 -1.125 2 -0

4、.23610.2360.528-1.125 -0.970 3 -0.236 0.5280.0560.236-1.050 -1.125 4 0.0560.5280.2360.348-1.125 -1.106 5 0.0560.3480.1680.236-1.112 -1.125 6 0.1680.3480.2360.279-1.125 -1.123 7 0.1680.279 第11页/共67页 第12页/共67页 第13页/共67页 逼近原目标函数的极小点的近似逼近原目标函数的极小点的近似 求解方法，称为插值方法或函数求解方法，称为插值方法或函数 逼近法。逼近法。 第14页/共67页 第15页/

5、共67页 第16页/共67页 第17页/共67页 p1 p(x) p3 f(x) f1 x1=a p2 f2 x2x*xP* f3 x3=b 第18页/共67页 3333 第19页/共67页 )()( )()()( 133221 321213132 xxxxxx fxxfxxfxx A )()( )()()( 133221 3 2 2 2 12 2 1 2 31 2 3 2 2 xxxxxx fxxfxxfxx B )()( )()()( 133221 321122313113223 xxxxxx fxxxxfxxxxfxxxx C 第20页/共67页 321213132 3 2 2 2 12

6、 2 1 2 31 2 3 2 2* )()()( )()()( 2 1 fxxfxxfxx fxxfxxfxx xp 第21页/共67页 13 13 1 xx ff c 32 11212 2 )/()( xx cxxff c ) 2 1 31( 2 1 * c c xxxP 第22页/共67页 0 )/()( 32 11212 2 xx cxxff c 13 13 1 12 12 xx ff c xx ff 第23页/共67页 第24页/共67页 xP*x2 f2 f3 x*x1=a x3=b 第25页/共67页 xP* xP* xP* xP* x2 x2 x2x2 x3=b x3=b x1

7、=a x1=a 第26页/共67页 入口入口 xp*x2? f2*fP*?f2fH? XS=XF-b(XF-XH), fS fsfH? 单纯 形为 HFL SGL fRfG? XS=XF+b(XF-XH) SGL fRfL? RGL XE=XF+a(XF-XH), fE fEfR?GLE RGL N N N N Y Y Y Y Y N 图5.3.2 单纯形算法框图 第40页/共67页 梯度搜索梯度搜索 第41页/共67页 称为f在点x处的梯度 第42页/共67页 第43页/共67页 第44页/共67页 第45页/共67页 入口入口 给定：给定： x(0)， k=0 |g(k)| ？ x*=x(

8、k) f*=f(x(k) 出口出口 x(k)= x(0 计算：计算：g(k)k=k+1 沿沿g(k)方向一维搜索，方向一维搜索， 求最优步长求最优步长 (k)。 N Y 第46页/共67页 l先求出函数的梯度：g(k) = 4x1 2x2 l第一次迭代:求出-g(1),并运算是否满足终止条 件 l不满足终止条件后,沿-g(1)做一维搜索，求出 (1) l利用x( )=x()- ()g()，得-g()后跳到第一步 第47页/共67页 xk x* xk+1 - f(xk+1) Sk+1 Sk 第48页/共67页 2 1 )( )( k k k xf xf 第49页/共67页 2 1 )( )( k

9、 k k xf xf 第50页/共67页 入口入口 k=0，计算计算：- f(x0) | f(xk+1) | ？ 出口出口 求求 (k) ，x(k+1)= x(k) + (k)S(k) 计算计算： f(xk+1) x*=xk+1 f(x*)=f(xk+1) Y N 给定：给定： x(0)， k n ？ x0=xk+1 N Y Sk+1 = - f(xk+1) + kSk K=K+1 第51页/共67页 第52页/共67页 F(x) 1(x) 0(x) x0 x1x2 x* 第53页/共67页 xxGxxxfxfxf k TT kk )( 2 1 )()()( xxGxxxfxfx k TT k

10、k )( 2 1 )()()( 第54页/共67页 第55页/共67页 第56页/共67页 2 221 4 1 )1 ()(xxxxxf 2 0 )( ) 1 ( xf 2 0 )( ) 1 ( xf 第57页/共67页 0 2 )()( )1(1)1(2)1( xfxfd 从x(1)出发,沿d(1)作一维搜索.得 116)()( 4) 1 () 1 ( dxf 第58页/共67页 从x(1)出发,沿d(1)作一维搜索.得 116)()( 4)1()1( dxf 0 064)( 1 3 显然,用阻尼牛顿法不能产生新点.原因在 于Hessian矩阵非正定. 第59页/共67页 第60页/共67页 第61页/共67页 )( )1( k xf )()( )()( )()( )()( 1 k k Tk K Tkk k kTk Tkk kk qHq HqqH qp pp HH 第62页/共67页 242 1 2 2 2 1 xxx 1 2 )1( x 10 01 1 H 2 1 2