华中科技大学工程优化设计-一维搜索

工程优化设计内容提要工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统一维搜索方法一.问题的提出子优化问题:FindMinimize()=f(x(k)+s(k))子优化问题的一阶必要条件:’()=0[f(x(k)+s(k))]Ts(k)=0fs(k)一维搜索方法二.确定搜索区间的进退法区间搜索的终止条件:找到三点a,c,b,满足

(a)(c)

(b),输出[a,b].acb(1)算法思想先在初始点的左右方向中确定一个下降方向.沿着下降方向向前搜索,直到遇到上升点.搜索的前一点与上升点构成所求区间.另外,用到步长加倍,提高搜索效率.一维搜索方法(2)算法

初始化.k=0,k=0,hk=h0,t=t0>1.计算0=(0).2.比较目标值.k+1=k+hk,计算k+1=(k+1).若k+1<k,转步3;否则,转步4.3.加大步长.hk+1=thk,=k,k=k+1,k=k+1,k=k+1,转步2.4.反向搜索.若k=0,转换搜索方向,hk=-hk,=k+1,转步2;

否则,停止.输出a=min{,k+1},b=max{,k+1}.k-迭代变量;k-当前点;-前一点;k+1-后一点;hk-步长t-步长加倍系数

一维搜索方法(2)举例

k-迭代变量;k-当前点;-前一点;k+1-后一点;hk-步长t-步长加倍系数

()014235t=1.5

a=3

b=5

一维搜索方法三.黄金分割法(0.618法)acb(1)算法思想逐步缩小区间[a,b].一般来说,在[a,b]中只增加计算一个点,难以确定极点所在的较小区间.可是,0.618法通过合理选择加计算点,能够达到增一点来缩小区间.aµbacb一维搜索方法a1µ1b11a2µ2b22目标:希望只计算一个新点就能将区间缩小倍.bk+1-ak+1=(bk-ak)另外,设,µ在[a,b]中对称

bk-µk=k-ak1=a1+(1-)(b1-a1)µ1=a1+(b1-a1)µ2=a2+(b2-a2)=a1+(µ1-a1)=a1+(a1+(b1-a1)-a1)=a1+2(b1-a1)由1=µ2,1-=2,=5-1/2=0.618

一维搜索方法(2)算法

初始化.a1,b1,1=a1+0.382(b1-a1),µ1=a1+0.618(b1-a1),k=1.计算(1),(µ1).取>0.2.比较目标值.若(k)>(µk)转步3;否则,转步4.3.若bk-k<,停止,输出µk.否则,ak+1=k,bk+1=bk,k+1=µk.

µk+1=ak+1+0.618(bk+1-ak+1),

计算(µk+1),转步2.4.若µk-ak<,停止,输出k.否则,ak+1=ak,bk+1=µk,µk+1=k.

k+1=ak+1+0.382(bk+1-ak+1),

计算(k+1),转步2.一维搜索方法四.Fibonacci法(1)算法思想逐步缩小区间[a,b].一般来说,在[a,b]中只增加计算一个点,难以确定极点所在的较小区间.可是,Fibonacci法通过Fibonacci数列选择新计算点,能够达到增一点来缩小区间目的.Fibonacci数列F0=F1=1,Fk+1=Fk+Fk-1,k=1,2,…1,1,2,3,5,8,13,….k=ak+(1-k)(bk-ak)µk=ak+k(bk-ak),k=Fn-k/Fn-k+1,每次缩小k倍.一维搜索方法四.Fibonacci法k=ak+(1-k)(bk-ak)µk=ak+k(bk-ak),k=Fn-k/Fn-k+1µk+1=ak+1+k+1(bk+1-ak+1)=ak+k+1(µk-ak)=ak+k+1[(ak+k(bk-ak))-ak]=ak+k+1[k(bk-ak)]=ak+k+1k(bk-ak)k+1=Fn-k-1/Fn-k=(Fn-k+1-Fn-k)/Fn-k

=(Fn-k+1/Fn-k-1)k+1k=(Fn-k+1/Fn-k-1)(Fn-k/Fn-k+1)=1-k所以每次也只需计算一个新点akµkbkkak+1µk+1bk+1k+1kk+1一维搜索方法四.Fibonacci法k=ak+(1-k)(bk-ak)µk=ak+k(bk-ak),k=Fn-k/Fn-k+1µn=bn+1,an+1=anbn+1=an+1+n(bn-an),

bn+1-an+1=n(bn-an),=nn-1n-2…1(b1-a1)=(F0/F1)(F1/F2)…(Fn-1/Fn)(b1-a1)=(1/Fn)(b1-a1),所以,取n使Fn>(b1-a1)/,即可得逼近精度为.另外,Fk-1/Fk->=0.618a1µ1b11a2µ2b22一维搜索方法四.Fibonacci法算法与黄金分割法类似.(2)算法(3)算法分析收敛速度与黄金分割法同为线性收敛,实际速度比黄金分割法稍快,但黄金分割法更容易实现.一维搜索方法bn+1-an+1=(bn-an)=n(b1-a1)bn+1-an+1=n(bn-an),=

nn-1n-2…1(b1-a1)=(1/Fn)(b1-a1)一维搜索方法五.逐次插值方法(三点二次插值)123二次极值点下一循环以23为插值点收敛阶