文档详情

(运筹学——非线性规划.ppt

发布:2016-11-03约4.04千字共76页下载文档
文本预览下载声明
Goldstein算法 搜索法求解: 或 基本过程: 给出[a,b],使得t*在[a,b]中。[a,b]称为搜索区间。 迭代缩短[a,b]的长度。 当[a,b]的长度小于某个预设的值,或者导数的绝对值小于某个预设的正数,则迭代终止。 退 出 前一页 后一页 假定:已经确定了单谷区间[a,b] t1 t2 a b a b t1 t2 新搜索区间为[a,t2] 新搜索区间为[t1,b] 退 出 前一页 后一页 区间缩小比例的确定: 区间缩短比例为(t2-a)/(b-a) 缩短比例为(b-t1)/(b-a) 缩短比例满足: 每次插入搜索点使得两个区间[a,t2]和[t1,b]相等; 每次迭代都以相等的比例缩小区间。 0.618法 t1 t2 a b a b t1 t2 退 出 前一页 后一页 确定[a,b],计算探索点 t1=a+0.382(b-a) t2=a+0.618(b-a) 0.618法解题步骤: 是 否 是 停止,输出t1 否 以[a,t2]为新的搜索区间 是 停止,输出t2 否 以[t1,b]为新的搜索区间 退 出 前一页 后一页 例: 解: t1 t2 3 0 t 1、第一轮: t1=1.146, t2=1.854 t2-00.5 退 出 前一页 后一页 2、第二轮: t2=1.146, t1=0.708 t2-0=1.1460.5 3、第三轮: t1=0.438, t2=0.708 b-t1=1.146-0.4380.5 1.854 0 t t2 t1 1.416 0 t t2 t1 退 出 前一页 后一页 4、第四轮: t2=0.876, t1=0.708 b-t1=1.146-0.7080.5 输出:t*=t2=0.876为最优解,最优值为-0.0798 课下练习:仔细分析上述迭代过程,体会0.618法的实质。 0 1.416 t t1 t2 退 出 前一页 后一页 2、Newton法 Newton法基本思想: 用探索点tk处的二阶Taylor展开式近似代替目标函数,以展开式的最小点为新的探索点。 课下练习:画图理解Newton法的几何意义 退 出 前一页 后一页 解题步骤: 给定初始点t1和精度 是 是 停止,输出t1 是 否 停止,解题失败 否 停止,输出t2 否 退 出 前一页 后一页 例: 解: 取t1=1,计算: 迭代过程如下表: 1.137 0.1163 0.1169 3 -0.001061 4 1.3258 -0.5178 -0.5708 2 2 0.7854 1 1 退 出 前一页 后一页 非精确一维搜索法 数值方法的关键是从一个点迭代到下一个点。 确定下一个点的关键是确定搜索方向和步长 如果已经确定了搜索方向pk,则只要确定一个最佳的步长即可。 所谓的最佳步长即是在pk方向上走一个最好的长度使得目标函数下降的最多,即下述的最优化问题: 这样的最优化问题不需要太高的精度,只要满足某些更宽松的精度要求即可。 这样的搜索方法称之为非精确一维搜索方法 退 出 前一页 后一页 Goldstein法原理: y t 0 b c d a Y=?(0)+ ?′(0)t Y=?(0)+ m2?′(0)t Y=?(0)+ m1?′(0)t 退 出 前一页 后一页 是 确定m1,m2,α,t0, a=0,b=+∞ ?(t0)≤ ?(0)+m1 ?’(0)t0 ?(t0) ≥?(0)+m2?’(0)t0 是 停止,输出t0 否 a=a, b=t0, t1=(a+b)/2 否 a=t0,b=b, t1=(a+b)/2 (若b=+∞,则t1= αa) 退 出 前一页 后一页 Armijo法原理: y t 0 tk Mtk 退 出 前一页 后一页 第四节 无约束最优化方法 本节课讨论n元函数的无约束非线性规划问题: 求解此类模型(UMP)的方法称为无约束最优化方法。 无约束最优化方法通常有两类: 解析法:要使用导数的方法; 直接法:无须考虑函数是否可导,直接使用函数值。 退 出 前一页 后一页 本节课内容: 无约束问题的最优性条件 最速下降法(一种解析法) 退 出 前一页 后一页 1、无约束问题的最优性条件 定理1 定理2 梯度为0的点称为函数的驻点。 驻点可能是极小点,也可能是极大点,也可能即不是极大也不是极小,这时称为函数的鞍点。 定理2说明:UMP问题的局部最优解必是目标函数的驻点。 注: 退 出 前一页 后一页 定理3 定理4 课下练习:画图理解定理1、2、4的几何意义。 退 出 前一页 后一页 例 解: 1、先求出目标函数的全部驻点; 2、利用充分条件判断驻点是不是最优点。 退 出 前一页 后一页 关于梯度的复习: 梯度是一个向量。n元函数f(x1 ,x2 ,…xn)在某点
显示全部
相似文档