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

1、工程优化设计内容提要 工程优化问题建模工程优化问题建模 优化数学理论优化数学理论 一维搜索方法一维搜索方法 无约束问题直接搜索方法无约束问题直接搜索方法 无约束问题间接接搜索方法无约束问题间接接搜索方法 约束问题直接搜索方法约束问题直接搜索方法 线性规划与二次规划问题求解线性规划与二次规划问题求解 约束问题间接搜索方法约束问题间接搜索方法 启发式算法启发式算法 优化软件系统优化软件系统一维搜索方法一一. .问题的提出问题的提出子优化问题子优化问题: :Find Find Minimize Minimize ( ( )=f(x)=f(x(k)(k)+ + s s(k)(k) )子优化问题的一阶必

2、要条件子优化问题的一阶必要条件: : ( )=0 )=0 f(xf(x(k)(k)+ + s s(k)(k)T Ts s(k)(k)=0=0 f fs s(k)(k)一维搜索方法二二. .确定搜索区间的进退法确定搜索区间的进退法区间搜索的终止条件区间搜索的终止条件: : 找到三点找到三点a,c,b, a,c,b, 满足满足 (a) (a) (c)(c) (b), (b), 输出输出 a,b.a,b.acb(1) (1) 算法思想算法思想先在初始点的左右方向中确定一个下降方向先在初始点的左右方向中确定一个下降方向.沿着下降方向向前搜索沿着下降方向向前搜索,直到遇到上升点直到遇到上升点.搜索的前一

3、点与上升点构成所求区间搜索的前一点与上升点构成所求区间.另外另外,用到步长加倍用到步长加倍,提高搜索效率提高搜索效率.一维搜索方法(2) (2) 算法算法 初始化初始化. . k=0, k=0, k k= = 0 0, h, hk k=h=h0 0, t=t, t=t0 01. 1. 计算计算 0 0= = ( ( 0 0).).2. 2. 比较目标值比较目标值. . k+1k+1= = k k+h+hk k, ,计算计算 k+1k+1= = ( ( k+1k+1).). 若若 k+1k+1 0.0.2. 2. 比较目标值比较目标值. . 若若 ( ( k k) ( ( k k) ) 转步转步

4、3; 3; 否则否则, ,转步转步4.4.3. 3. 若若b bk k- - k k , ,停止停止, ,输出输出 k k. . 否则否则, , a ak+1k+1= = k k, b, bk+1k+1=b=bk k, , k+1k+1= = k k. . k+1k+1=a=ak+1k+1+ +0.6180.618(b(bk+1k+1-a-ak+1k+1),), 计算计算 ( ( k+1k+1), ), 转步转步2.2.4. 4. 若若 k k-a-ak k (b(b1 1-a-a1 1)/)/ , ,即可得逼近精度为即可得逼近精度为 . .另外另外, , F Fk-1k-1/F/Fk k-

5、=0.618=0.618a11b1 1a22b2 2一维搜索方法四四. .FibonacciFibonacci法法算法与黄金分割法类似算法与黄金分割法类似. .(2) (2) 算法算法(3) (3) 算法分析算法分析收敛速度与黄金分割法同为线性收敛收敛速度与黄金分割法同为线性收敛, ,实际速度比黄金分割法稍快实际速度比黄金分割法稍快, ,但黄金分割法但黄金分割法更容易实现更容易实现. .一维搜索方法bn+1-an+1= ( (bn-an) )= = n(b1-a1) b bn+1n+1-a-an+1n+1= = n n(b(bn n-a-an n), ), = = n n n-1 n-1 n-

6、2n-2 1 1(b(b1 1-a-a1 1)=(1/F)=(1/Fn n)(b)(b1 1-a-a1 1) ) 一维搜索方法五五. .逐次插值方法逐次插值方法( (三点二次插值三点二次插值) ) 1 1 2 2 3 3 二次极值点二次极值点下一循环以下一循环以 2 2 3 3为插值点为插值点收敛阶为收敛阶为1.32,1.32,比比0.6180.618方法与方法与FibonacciFibonacci速度快速度快. .|xk+1-x*|C|xk-x*|aa为收敛阶为收敛阶一维搜索方法总结总结一维搜索是多维优化的基础一维搜索是多维优化的基础. .这里给出的算法都是直接法这里给出的算法都是直接法, ,没有利用导数信息没有利用导数信息, ,具有较广的具有较广的适用性适用性. .实际上实际上, ,还可以用导数信息确定搜索步长还可以用导数信息确定搜索