工程优化设计-无约束间接法

《工程优化设计-无约束间接法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、工程优化设计黄正东二0一一年九月内容提要工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统无约束间接搜索方法一.梯度法(最速下降法)间接法:利用函数的性态,通过函数微分或变分求优。梯度法,牛顿法,共轭梯度法,变尺度法(拟牛顿法)(1)算法思想梯度的负方向代表目标函数下降最快的方向,以负梯度方向作为一维搜索方向。f(x)=f(x0)+(x-x0)Tf(x0)+O((x-x0)2)f(x0)+(x-x0)Tf(x0

2、)设x=x0+d,

3、d

4、=1f(x)f(x0)+dTf(x0)由于

5、dTf(x0)

6、

7、d

8、*

9、f(x0)

10、,或

11、ab

12、=

13、a

14、

15、b

16、cos()

17、a

18、

19、b

20、所以d=f(x0)/

21、f(x0)

22、时,

23、dTf(x0)

24、最大.即:如果一定,在d=-f(x0)/

25、f(x0)

26、时,f(x)下降最快f(x0)df(x)=2f(x)=1x0f(x)=0无约束间接搜索方法一.梯度法(最速下降法)(2)算法无约束间接搜索方法一.梯度法(最速下降法)(3)算法分析1.开始下降较快,当接近最优点时,下降速度变慢,呈锯齿路线.2.优

27、点是算法简单.局部下降最快不等于整体下降最快!!无约束间接搜索方法二.牛顿法(1)算法思想梯度法基于一次逼近,牛顿法基于二次逼近,可以提高收敛速度.=(X)==0牛顿法迭代公式广义牛顿法中一维搜索无约束间接搜索方法二.牛顿法(2)算法(广义牛顿法)无约束间接搜索方法二.牛顿法(3)算法分析收敛阶定义:1-牛顿方向,2-梯度方向牛顿法在现有算法中收敛速度最快;但要求二阶可微,计算逆矩阵,计算量大,另外收敛与否依赖于初始点的选择.无约束间接搜索方法三.共轭梯度法(1)算法思想结合共轭方向法和梯度法的优点,将相互共轭的搜索方向,同时取为与当前

28、点梯度方向相关方向.一般共轭梯度法:初始化.g0=f(x0),选择d0使d0Tg0<0.如果

29、gk

30、

31、Tdi=0;实际上当di之间共扼时，有：gi+1Tdi=0，gi+1Tdi-1=0，…即，gi+1垂直di,di-1,…，d1张成的子空间（或平面）。xi-1di-1无约束间接搜索方法三.共轭梯度法性质1:设x0,x1,x2,…,xk,gi=f(xi),di为共轭搜索方向,即xi+1=xi+aidi,则gi+1Tdj=0,j=0,1,…,i.证明:f(x)=0.5xTHx-bTx,gi=f(xi)=Hxi-b,使ri=gi=Hxi-bgk+1-gk=H(xk+1-xk)=aHdk在一维精确搜索时,当j

32、dj+gi+1Tdj=gj+1Tdj+(gj+2Tdj-gj+1Tdj)+(gj+3Tdj-gj+2Tdj)+…+(gi+1Tdj-giTdj)d1d2d3g1g2g3无约束间接搜索方法三.共轭梯度法性质2:设x0,x1,x2,…,xk是一维精确搜索产生的点列,gi=f(xi),di为共轭搜索方向,即xi+1=xi+aidi,如果令则βi=0,i=0,1,…,k-2.即：dk=-gk+βk-1dk-1,d0=-g0.f(x)=0.5xTHx-bTx,gi=f(xi)=Hxi-b,d1d2d3g1g2g3性质2证明:设d0=-g0,d1

33、=-g1+β11d0,d2=-g2+β21d0+β22d1,要证明β21=0。由d0THd2=0,得β21=-d0THg2/d0THd0.设xi+1=xi+aidi,则：g1-g0=(Hx1+b)-(Hx0+b)=H(x1-x0)=a0Hd0d0THg2=g2THd0=g2T(g1-g0)/a0.[归结为证明g2Tg1=0,g2Tg0=0]由g2-g1=a1Hd1->g2Tg1=g1Tg1+a1g1THd1=g1Tg1-a1(-g1T+β11d0)Hd1=g1Tg1-a1d1THd1由g2Td1=0,得(g1+a1Hd1)Td1=0,a1

34、=-g1Td1/d1THd1由g1Td0=0,得g1Td1=g1T(-g1+β11d0)=-g1Tg1,a1=g1Tg1/d1THd1,所以，g2Tg1=0。g2Tg0=(g1+a1Hd1)g