资源描述：
《工程优化设计-无约束直接法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、工程优化设计黄正东二0一0年九月内容提要工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统无约束直接搜索方法一.坐标轮换法直接法:利用迭代过程已有信息和再生信息进行试探和求优,不需要用到函数导数和分析性质。(1)算法思想轮换地以每一个坐标轴作为一维搜索方向的优化搜索方法。无约束直接搜索方法一.坐标轮换法(2)算法1.初始化，>0，M，n,k=1,x=x(0).2.对于i=1,2,…,n，进
2、行2.1Si=ei;2.2i=minf(x+Si)2.3x=x+iSi,f=f(x).3.如果
3、iSi
4、<,或者k>M,转步4;否则，k=k+1,转步2。4.输出x,f.结束。无约束直接搜索方法一.坐标轮换法(3)算法分析对于维数较高的优化问题，搜索时间过长，一般当n>10时，则不应采用此方法。2.算法效率与f(x)形态有关。无约束直接搜索方法二.单纯形方法(1)算法思想单纯形（Simplex）概念:n维空间中的n+1面体f(xh)=max{f(x0),f(x1),…,f(xn)}---高点f(xl)=
5、min{f(x0),f(x1),…,f(xn)}---低点x=---除最高点外的所有点的形心xhx2x1xxrxr=x+a(x-xh)---反射点，a反射系数，一般取a=1.无约束直接搜索方法二.单纯形方法分三种情况选择新点:xe=x+y(xr-x)若f(xr)>f(xe),则xe->xh否则，xr->xh1。如果f(xl)>f(xr),进一步扩展扩展系数y>1,一般y=2.xhx2xlxxrxef(xr)比所有单纯形点上值小不进一步扩展,避免狭窄单纯形无约束直接搜索方法二.单纯形方法分三种情况选择新点:xe=x
6、+y(xr-x)若f(xr)>f(xe),则xe->xh否则，xr->xh1。如果f(xl)>f(xr),进一步扩展扩展系数y>1,一般y=2.xhx2xlxxrxef(xr)比所有单纯形点上值小无约束直接搜索方法二.单纯形方法分三种情况选择新点:2。如果max{f(xi),ih}f(xr)f(xl),则xr->xhxhx2x1xxrxef(xr)在单纯形点上值之间,但最少比第二最大值小.分三种情况选择新点:3。如果f(xr)>max{f(xi),ih},则f(xh’)=min{f(xh),f(xr)}压
7、缩xc=x+b(xh’-x),0xh否则，以xl为中心压缩整个单纯形：xi=xi+0.5(xl-xi),i=0,1,2,…,nxhx2xlx2xhxhx2x1xxrxcxhx2xxrxcx1f(xr)可以在单纯形点上值之上,但最少比第二最大值大.试探顺序无约束直接搜索方法二.单纯形方法终止条件:初始单纯形:x0=(a1,a2,…,an)x1=(a1+p,a2+q,…,an+q)x2=(a1+q,a2+p,…,an+q)……xn=(a1+q,
8、a2+q,…,an+p)p=a为单纯形边长无约束直接搜索方法(2)算法（略）初始单纯形所选的尺度与方向对结果有大的影响。单纯形可能退化到低维空间情况。有人指出，对于变量很多的情况，如n>10时，效率不高。二.单纯形方法(3)算法分析无约束直接搜索方法(1)算法思想三.模式搜索法(Hooke-Jeeves方法)通过在坐标轴方向进行探测性移动,确定下降方向,然后,沿着下降方向进行一次模式性移动.第1次探测第2次探测模式移动第1次探测第2次探测模式移动22成功失败下一步,步长减小下一步,步长不变无约束直接搜索方法三.模
9、式搜索法(Hooke-Jeeves方法)探测性移动:X0(k)-ae1X0(k)+ae1X0(k)移动X0(k)-ae1,X0(k),X0(k)+ae1的f(X)最小点,记为X1(k).a为探测移动步长.也可以用一维搜索确定最优位置,但每一步计算量增大.无约束直接搜索方法三.模式搜索法(Hooke-Jeeves方法)模式移动:X0(k)Xn+1(k)Xn(k)Xn+1(k)=Xn(k)+[Xn(k)-X0(k)]模式移动没进行优化比较!(2)算法无约束直接搜索方法效率比坐标轮换法高。算法比单纯形法稳定,没有退化情
10、况。但也只适用于变量较少的优化问题，不过,可作为其他搜索方法的初始点生成。三.模式搜索法(3)算法分析无约束直接搜索方法四.共轭方向法及其改进后的Powell法(1)概念与性质无约束直接搜索方法四.共轭方向法及其改进后的Powell法(1)概念与性质A对称正定,所以,A=UTDU=UTD1/2D1/2U=(D1/2U)T(D1/2U)=QTQS1TAS2=S1TQTQS2
