非线性及动态规划.ppt

2017-2-23 1 优化问题三要素: 决策变量 decision bariable ;目标函数 objective function ;约束条件 constraints 约束条件决策变量优化问题的一般形式 n j iDx ljxg m ixhts xf opt???????,..., 1,0)( ,..., 1,0)(.. )(目标函数等约束 equality constraint 不等约束 inequality constraint 一般优化问题概述?要解决的问题的目标可以用数值指标反映?对于要实现的目标有多种方案可选择?有影响决策的若干约束条件特点一般优化问题概述?可行解 feasible solution (满足约束)与可行域 feasible region (可行解的集合) ?最优解 optimal solution (取到最小 minimum /大值 maximum 的可行解,对应最优值 optimal value ) 局部最优解或相对最优解 local/relative optimizer 全局或整体最优解 global optimizaer 优化模型的基本类型无约束优化 unconstrained optimization 约束优化 constrained optimization 特殊:等式(不等式)方程组 system of equations(inequations ) 一般优化问题概述约束优化 constrained optimization 的简单分类数学规划 mathematical programming 或连续优化 continuous optmization ?线性规划(LP) 目标和约束均为线性函数 Linear programming ?非线性规划(NLP) 目标或约束中存在非线性函数 Nonlinear programming 二次规划(QP) 目标为二次函数、约束为线性 Quadratic programming 一般优化问题概述整数规划(IP) 决策变量(全部或部分)为整数 Integer programming ?整数线性规划(ILP) ,整数非线性规划(INLP) ?纯整数规划(PIP), 混合整数规划(MIP) Pure (mixed) Integer programming 一般整数规划, 0-1 (整数)规划 Zero-one programming 离散优化 discrete optimization binatorial optimization 一般优化问题概述求解 y = f (x)极小值的数值迭代算法:一维搜索算法中的黄金分割法( 法). 分割法原理:设函数 f (x ) 在闭区间[a, b ] 上是下单峰函数, 即在(a, b ) 内 f (x ) 由唯一的极小点 x *, 在x *的左边 f (x ) 严格单调下降, 在 x *的右边 f (x)严格单调上升. 那么对于(a, b)内任意两点 x 1<x 2, 如果 f (x 1)< f (x 2 ), 则x *∈[a, x 2];否则 x *∈[x 1, b ]. 如右图非线性规划-无约束问题给定下单峰区间[a, b ] 及控制误差?>0, 黄金分割法( 法)的迭代步骤: ①取x 2 = a + ( b - a ), f 2 = f (x 2 ), 转向②. ②取x 1 = a + ( b - a ), f 1 = f (x 1 ), 转向③. ③若| b - a |<?, 则取 x * = ( a + b )/2, 停. 否则转向④. ④若f 1<f 2, 则取 b = x 2 , x 2 = x 1, f 2 = f 1 , 转向②; 若f 1=f 2 , 则取 a = x 1, b = x 2, 转向①; 若f 1>f 2 , 则取 a = x 1, x 1= x 2, f 1 = f 2 , 转向⑤. ⑤取x 2 = a + ( b - a ), f 2 = f (x 2 ), 转向③. 非线性规划-无约束问题下面我们再给出一个求初始区间的进退算法, 在所求出的区间上 f (x)是下单峰函数. 给定初始点x 0和初始步长?>0, 进退算法的迭代步骤: ①取x 1 = x 0 +?, 计算 f (x 0 ), f (x 1 ). 若 f (x 0 ) ≥ f (x 1 ), 则转向②;否则转向④. ②取?= 2 ?, x 2 = x 1 +?, 计算 f (x 2 ). 若 f (x 2)≥ f (x 1 ), 则得到区间[x 0 , x 2 ] 为