非线性规划教学PPT.ppt

non linearprogramming nlp 非线性规划主要内容 基本概念一维搜索方法无约束最优化方法约束最优化方法 1 基本概念 非线性规划问题非线性规划方法概述 非线性规划问题 例 曲线的最优拟合问题 非线性规划模型的一般形式 其中 x x1 x2 xn t f x gi x hj x 为x的实值函数 f x 局部最优解 整体最优解 非线性规划问题的解 x 例 三角形表示的是可行域 同心圆表示的是目标函数的等值线 最优解为 1 2 1 2 最优值为1 2 1 2 1 2 设f x 为定义在n维欧氏空间en某一区域上r上的n元实函数 其中 x x1 x2 xn t对于x r 如果存在某个 0 使所有与x 的距离小于 的x r 即x r且 x x 均满足f x f x 则称 x 为f x 在r上的局部极小点 f x 为局部极小值 极值问题 若对于所有x x 且与x 的距离小于 的x r 都有f x f x 则称x 为f x 在r上的严格局部极小点 f x 为严格局部极小值 若x r 而对所有x r都有f x f x 则称x 为f x 在r上的全局极小点 f x 为全局极小值 若对于所有x r且x x 都有f x f x 则称x 为f x 在r上的严格全局极小点 f x 为严格全局极小值 如将以上不等式反向 即可得到相应的极大点和极大值的定义 凸函数和凹函数 凸函数 凹函数 非凸非凹函数 非线性规划方法概述 微分学方法的局限性 实际的问题中 函数可能是不连续或者不可微的 需要解复杂的方程组 而方程组到目前仍没有有效的算法 实际的问题可能含有不等式约束 微分学方法不易处理 往往需要数值解法 迭代 数值方法的基本思路 迭代 给定初始点x0 根据x0 依次迭代产生点列 xk xk 的最后一点为最优解 xk 有限 xk 无限 xk 收敛于最优解 无约束最优化方法 n元函数的无约束非线性规划问题 无约束最优化方法通常有两类 解析法 要使用导数的方法 直接法 无须考虑函数是否可导 直接使用函数值 1 无约束问题的最优性条件 定理 梯度为0的点称为函数的驻点 驻点可能是极小点 也可能是极大点 也可能既不是极大也不是极小 这时称为函数的鞍点 定理说明 ump问题的局部最优解必是目标函数的驻点 注 例 解 1 先求出目标函数的全部驻点 2 利用充分条件判断驻点是不是最优点 2 下降迭代算法 迭代步骤 注 选步长有多种方法 最常用的方法是用以上确定最佳步长的方法 一维搜索的性质 一维搜索方法 0 618法 近似黄金分割法 1 求解下降迭代法中 要求搜索方向pk为下降方向 显然 可能有多个下降方向 那么哪个方向下降最快呢 是否有下降最快的方向呢 2 梯度法的基本原理 梯度方向是函数在这一点附近上升最快的方向 负梯度方向是函数在这一点附近下降最快的方向于是在下降迭代中 在每一迭代 都采用前轮迭代点处的负梯度方向为搜索方向 梯度法 最速下降法 多维问题 3 计算步骤 坐标轮换法 步长加速法 4 约束最优化方法 一 等式约束条件下得nlp 拉格朗日乘子法 罚函数法 二 不等式约束下得nlp 最优性条件 罚函数法 1 拉格朗日乘子法2 罚函数法 一 等式约束条件下得nlp 二 不等式约束下得nlp 1 最优性条件2 罚函数法 外点法 3 罚函数法 内点法 1 约束性的分析 可行解 满足所有约束的解 即 可行解x0的约束形式 a当 这个不等式在x0的一个邻域仍成立 因此 这个约束对局部极值问题而言不起作用 即为无效约束 b当 这时x0处于该约束条件形成的可行域边界上 称这个约束称为起作用约束 有效约束 一 最优性条件 2 k t条件 对于无约束问题 f x 0对于有约束问题 复杂多了引入一个向量 让不等式约束变为等式约束 即 jgj x 0 j 0 k t条件 f x j gj x 0 jgj x 0 j 0 f x i gi x j hj x 0 igi x 0 i 0 举例 minf x1 x2 3x1 x