西北农林科技大学运筹学课件第六章非线性规划

第六章非线性规划 一 基本概念二 一维搜索三 无约束极值问题四 约束极值问题 一 基本概念 一般形式 1 非线性规划的数学模型 一 基本概念 2 二维问题的图解 考虑非线性规划问题 B A C D 0 5 x1 x2 一 基本概念 3 几个定义 定义1局部极小值 严格局部极小值 定义1全局极小值 严格全局极小值 一 基本概念 4 多元函数极值点存在的条件 1 必要条件梯度 2 充分条件海赛矩阵 函数在某点的梯度 垂直于过该点的等值面的切平面 梯度方向是函数值增加最快的方向 满足梯度为零的点称为驻点 若海赛矩阵是正定的 则驻点是极小点 若海赛矩阵是负定的 则驻点是极大点 若海赛矩阵是不定的 则驻点不是极值点 若海赛矩阵是半定的 须视高阶导数的性质而定 例利用极值条件求解下列问题 解 驻点处的海赛矩阵 一 基本概念 极小点 极大点 不定 不定 一 基本概念 5 下降迭代算法 选取某一初始点X 1 令k 0确定一个有利搜索方向d k 确定最优步长 K 得一新点X k 1 检验X k 1 是否为极小点 若是 停止计算 否则令k k 1返回第2步继续迭代 二 一维搜索 一维搜索方法的斐波那契法与黄金分割法的寻优途径不是直接找出最优点 而是不断缩小最优点所处区域 直到符合精度为止 这两种方法的主要特点为 适于单峰 谷 函数 压缩峰 谷 点所处的区域 二 一维搜索 1 0 618法 黄金分割法 在区间 a1 b1 上选取t 1和t1计算f t 1 f t1 比较函数值的大小 缩短区间 置换区间端点 判断精度 bk 1 ak 1 b1 a1 极值计算 t ak 1 bk 1 2 f x 为近似值 t1 a1 0 618 b1 a1 t 1 a1 0 382 b1 a1 t1 t 1 0 382 b1 t 1 a2 0 382 b2 a2 t 1 a1 0 618 t1 a1 a2 0 618 b2 a2 例黄金割法求下述问题的极小点 要求绝对误差不超过0 25 1 解 二 一维搜索 二 一维搜索 二 一维搜索 2 斐波那契法 根据缩短率 计算出Fn 确定试点个数n 选取前两个试点的位置 计算f t 1 f t1 比较函数值的大小 缩短区间 置换区间端点 当进行至k n 1时 计算tn 1及t n 1以函数值较小者为近似极小点 Fn 2 Fn 1 a0 t1 t 1 b0 Fn 3 给定初始点X 1 允许误差 0 k 1确定有利得搜索方向d k 为X k 点的负梯度方向判断精度确定最优步长求出新点 令k k 1返回第2步 三 无约束极值问题 1 梯度法 最速下降法 例给定初始条件 求下列问题的最小值 解 三 无约束极值问题 三 无约束极值问题 给定初始点X 1 允许误差 0 k 1确定搜索方向d k 判断精度确定最优步长求出新点 令k k 1返回第2步 三 无约束极值问题 2 牛顿法 三 无约束极值问题 例给定初始点求下列函数极值 三 无约束极值问题 库恩 塔克条件是确定能够非线性规划问题中某点为最优点的一阶必要条件 但对于凸规划 库恩 塔克条件是充要条件 对非线性规划数学模型minf x Hi X 0 i 1 2 m gj X 0 j 1 2 l 若X 是局部 或全局 极小点 则一定存在向量 1 2 m T及 1 2 l T 使得下述条件成立 四 约束极值问题 1 库恩 塔克条件 求下列非线性规划问题的库恩 塔克点 解 设K T点为X 四 约束极值问题 故根据K T点有 K T点的分析 四 约束极值问题 通过构造罚函数把约束问题转化为一系列的无约束问题 进而用无约束最优化方法求解 外点法 构造罚函数 四 约束极值问题 1 罚函数法 外点法 算法步骤给定初始点x 0 初始罚因子M1 0 放大系数C 1 允许误差 0 令k 1求解罚函数p X Mk 的无约束极小以X k 1 为始点 求解minp X Mk 得其极小点X k 判断精度在X k 点 若罚项 停止计算 否则 令Mk 1 CMk k k 1 四 约束极值问题 例用外点法求解非线性规划 四 约束极值问题 四 约束极值问题 通过构造罚函数把约束问题转化为一系列的无约束问题 进而用无约束最优化方法求解 外点法 构造罚函数 四 约束极值问题 2 障碍罚函数法 内点法 算法步骤给定初始点x 0 初始罚因子r1 0 允许误差 0 令k 1求解罚函数p X rk 的无约束极小以X k 1 为始点 求解