工程优化设计-一维搜索

工程优化设计黄正东二0一0年九月内容提要•工程优化问题建模•优化数学理论•一维搜索方法•无约束问题直接搜索方法•无约束问题间接接搜索方法•约束问题直接搜索方法•线性规划与二次规划问题求解•约束问题间接搜索方法•启发式算法•优化软件系统一维搜索方法一.问题的提出子优化问题:FindMinimize()=f(x(k)+s(k))子优化问题的一阶必要条件:’()=0[f(x(k)+s(k))]Ts(k)=0fs(k)一维搜索方法二.确定搜索区间的进退法区间搜索的终止条件:找到三点a,c,b,满足(a)(c)(b),输出[a,b].acb(1)算法思想先在初始点的左右方向中确定一个下降方向.沿着下降方向向前搜索,直到遇到上升点.搜索的前一点与上升点构成所求区间.另外,用到步长加倍,提高搜索效率.一维搜索方法(2)算法1.初始化.k=0,k=0,hk=h0,t=t01.计算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-步长加倍系数()014235t=1.5a=3b=5一维搜索方法三.黄金分割法(0.618法)acb(1)算法思想逐步缩小区间[a,b].一般来说,在[a,b]中只增加计算一个点,难以确定极点所在的较小区间.可是,0.618法通过合理选择加计算点,能够达到增一点来缩小区间.aµbacb一维搜索方法a1µ1b11a2µ2b22目标:希望只计算一个新点就能将区间缩小倍.bk+1-ak+1=(bk-ak)另外,设,µ在[a,b]中对称bk-µk=k-ak对称为了保持固定缩小比例,避免较大区间成为缩小结果1=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)算法1.初始化.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)(1)µk=ak+k(bk-ak),从右图知保证缩小k倍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+1k(bk-ak)(2)k+1=Fn-k-1/Fn-k=(Fn-k+1-Fn-k)/Fn-k=(Fn-k+1/Fn-k-1)k+1k=(Fn-k+1/Fn-k-1)(Fn-k/Fn-k+1)=1-k这样,由(1)(2)式保证k=µk+1,从而下一步可少计算一个点所以每次也只需计算一个新点akµkbkkak+1µk+1bk+1k+1kk+1一维搜索方法四.Fibonacci法k=ak+(1-k)(bk-ak)µk=ak+k(bk-ak),此式保证缩小k倍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),=nn-1n-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µ1b11a2µ2b22一维搜索方法四.Fibonacci法算法与黄金分割法类似.(2)算法(3)算法分析收敛速度与黄金分割法同为线性收敛,实际速度比黄金分割法稍快,但黄金分割法更容易实现.一维搜索方法bn+1-an+1=(bn-an)=n(b1-a1)bn+1-an+1=n(bn-an),=nn-1n-2…1(b1-a1)=(1/Fn)(b1-a1)一维搜索方法五.逐次插值方法(三点二次插值)123二次极值点下一循环以23为插值点收敛阶为1.32,比0.618方法与Fibonacci速度快.|xk+1-x*|C|xk-x*|aa为收敛阶一维搜索方法总结一维搜索是多维优化的基础.这里给出的算法都是直接法,没有利用导数信息,具有较广的适用性.实际上,还可以用导数信息确定搜索步长.另外,这里没有考虑约束问题.实际上,在一维搜索区间上,有可能存在一些子区间属于可行域外.