运筹学非线性规划ppt课件

第三章非线性规划 请回顾线性规划 其目标与约束函数均为线性的 线性规划具有相对完美的理论与方法 应用也很广泛 但它终究不能穷尽各种优化问题 因为世界是非线性的 非线性规划 NonlinearProgramming 研究具有非线性构成函数的优化问题 是运筹学中相对活跃的重要研究分支 第一节基本概念 一 非线性规划问题与模型 投资决策问题 2 模型 二 模型的解及相关概念 1 可行解与最优解 可行解 约束集D中的X 最优解 如果有 对于任意的 都有 则称为 NLP 的最优解 也称为全局最小值点 局部最优解 如果对于 使得在的邻域中的任意都有 则称为 NLP 的局部最优解 也称为局部最小值点 例1 考虑非线性问题 如果约束改为呢 2 梯度 海塞阵与泰勒公式 梯度 海塞阵 泰勒公式 例2 写出在点的二阶泰勒展开式 解 3 极值的条件 对于无约束极值问题 可以利用微积分的知识给出局部极值点的条件 将n n 1 元函数与一元函数的极值条件加以对比并归纳如下 例3 求的极小值点 解 4 凸规划 注 判断一个可导函数f X 是否是凸函数的方法一元函数f x 二阶导大于等于零 多元函数f X 海塞阵半正定 凸规划 性质 约束集是凸集 最优解集是凸集 任何局部最优解也是全局最优解 若目标函数是严格凸函数 且最优解存在 则其最优解是唯一的 在非线性规划模型 NLP 中 若目标函数f X 是凸函数 不等式约束函数为凹函数 等式约束函数为仿射函数 则称 NLP 是一个凸规划 例4 判断下面的非线性规划是否为凸规划 标准化 计算 第二节无约束极值问题 一般模型 求解 f X 可微 应用极值条件求解 往往得到一个非线性的方程组 求解十分困难 因此 求解无约束问题一般采用迭代法 称为下降类算法 一 下降类算法的基本步骤与算法收敛性 1 基本思想 2 基本步骤 1 2 3 4 注 不同的搜索方向 就形成了不同的算法 不同的算法所产生的点列收敛于最优解的速度也不一样 3 收敛性 衡量标准 二阶收敛 超线性收敛 线性收敛 二 一维搜索 1 分数法 斐波那契法 基本思想 怎样在区间中取点最好 基本概念 步骤 例5 2 0 618法 区别 每次取点得比例是定值0 168 即每次区间内两点得位置均在区间相对长度得0 328和0 168处 特点 简单 更易于应用 效果也比较好 3 近似最佳步长公式 例6 三 梯度法和共轭梯度法 1 梯度法 一般步骤 1 2 3 4 例7 上例中 目标函数是同心圆族 无论初始点选在何处 在该点的负梯度方向总是指向圆心 而圆心就是极小点 故沿负梯度方向搜索一步便可得极小点 但对于一般的函数 若每次迭代均采用负梯度方向 则由于这些方向是彼此正交的 很可能形成开头几步下降较快 但后来便产生直角锯齿状的 拉锯 现象 收敛速度很慢 可以证明 梯度法是线性收敛的 注 2 共轭梯度法 基本概念 这一性质说明采用共轭方向作为搜索方向 对二次函数求极小可以有限步终止 由此可构造二次函数的共轭方向算法 共轭方向算法用于二次函数时均具有二次终止性 由于一般函数在一点附近的性质往往与二次函数很相似 因此共轭方向算法一般也可用于其他非线性函数 并且至少是线性收敛的 一般步骤 例8 四 牛顿法与拟牛顿法 1 牛顿法 牛顿方向 一般步骤 当一维搜索是精确的 牛顿法为二阶收敛 缺点 2 拟牛顿法 DFP方法的一般步骤 例9 第三节约束极值问题 一般模型 1 基本概念和性质 起作用约束 可行下降方向 可行下降方向的条件 2 最优性条件 K T条件 定理 K T条件 例10 利用K T条件求解下面的非线性规划 为解此方程组 可分几种情况考虑 例11 考虑非线性规划并验证它为凸规划 用K T条件求解 计算目标和约束函数的海赛阵 3 二次规划 一般模型 思考 能否在此基础上构想基于线性规划求解的方法 例12 求解二次规划 解 求得的结果是 4 罚函数 外点法的关键是基于 NLP 构造一个新的目标函数P X M 称为罚函数 当X是可行点时 罚项为0 当X不是可行点时