高级运筹学-第9章：非线性规划.ppt

1 第九章 非线性规划模型 9 1基本概念和基本原理一 什么是非线性规划 目标函数和约束条件中有非线性函数的规划问题 例9 1某企业生产一种产品y需要生产资料x1和x2 用经济计量学方法根据统计资料可写出生产函数为 但是投入的资源有限 能源总共1O个单位 而每单位生产资料x1要消耗1单位能源 每单位生产资料x2要消耗2单位能源 问 应如何安排生产资料使产出最大 解 Max 2 例9 2某厂生产两种产品 第一种产品每件售价30元 第二种产品每件售价450元 设x1与x2分别为第一 二种产品的数量 据统计 生产第一种产品所需工作时间平均为0 5小时 生产第二种产品所需工作时间平均为 2 0 25x2 小时 已知该工厂在这段时间内允许的总工作时间为800小时 试确定使总收入最大的生产计划 解 Max 二 非线性规划问题的特点局部最优点不是全局最优点 三 极值问题1 一元函数y f x 极值点存在的必要条件 f x 0 此时求出的x0为驻点 极值点存在的充分条件 a 若在驻点x0附近f x0 0 则该点x0为极小值点 3 2 多元函数y f X f x1 x2 xn 在X0附近作泰勒展开 得 4 极值点存在的必要条件 f x 0 此时求出的x0为驻点 极值点存在的充分条件 5 四 凸函数与凹函数 1 定义 y f x 是En中某凸集R上的函数 对 0 1 及 X1 X2 R 且X1 X2若f X1 1 X2 f X1 1 f X2 则f x 为R上的凸函数 若f X1 1 X2 f X1 1 f X2 则f x 为R上的严格凸函数 对 0 1 及 X1 X2 R 且X1 X2若f X1 1 X2 f X1 1 f X2 则f x 为R上的凹函数 若f X1 1 X2 f X1 1 f X2 则f x 为R上的严格凹函数 6 2 性质 fi X 为凸集R上的凸函数 则对 ki 0 i 1 2 m 有k1f1 X k2f2 X kmfm X 仍为凸函数 3 凸函数的判定 f X 定义在凸集R上 若f X 有连续的二阶导数 则f X 为凸函数 H为半正定 f X 为严格凸函数 H为正定 4 凸函数的局部极值与全局极值的关系若目标函数在可行域中为凸函数 则其极值点为最优值点 若目标函数在可行域中为严格凸函数 则其极值点为唯一最优值点 7 五 凸规划 1 定义 非线性规划 若f X gi X 为凸函数 则 p 称为凸规划 2 性质 p 的可行解集R是凸集 最优解集R 也是凸集 p 的任何局部最优解均是全局最优解 若f X 为严格凸函数时 其最优解必唯一 特例 线性函数既是凸函数又是凹函数 故L P 为凸规划 六 寻优方法概述 1 N L P 问题分类 无约束条件的NLP问题 有约束条件的NLP问题 2 寻优方法 间接法 解析法 适应于目标函数有简单明确的数学表达式 直接法 搜索法 目标函数复杂或无明确的数学表达式 a 消去法 对单变量函数有效 不断消去部分搜索区间 逐步缩小极值点存在的范围 b 爬山法 对多变量函数有效 根据已求得的目标值 判断前进方向 逐步改善目标值 8 9 2无约束条件下单变量函数寻优一 消去法原理 逐步缩小搜索区间 直至极值点存在的区间达到允许的误差范围为止 设要寻求f X 的极小值点为X 起始搜索区间为 a0 b0 x1 x2 a0 b0 且x2 x1 计算f x1 和f x2 并且比较结果 x1 x2均在x 的右侧 f x2 f x1 去掉 x1 b0 此时x a0 x1 x1 x2均在x 的左侧 f x2 f x1 去掉 a0 x2 此时x x2 b0 x1 x2均在x 的两侧 f x2 f x1 a 去掉 x1 b0 此时x a0 x1 b 去掉 a0 x2 此时x x2 b0 9 二 黄金分割法 0 618法 是一种常用的消去法与对分法 Fibonacci法比较 具有计算次数少 过程简单的特点 1 原理 2 取点法则 f x2 f x1 取 a1 a0 b1 x1 x 1 x2x 2 b1 b1 a1 f x2 f x1 取 a1 x2 b1 b0 x 1 a1 b1 a1 x 2 x1 计算n个点后 总缩短率为En n 1 可得试点数n 10 3 计算步骤 求函数f x 的极值点 第一步 取初始区间 a0 b0 若求f x 的极小值点 则 f x2 f x1 取 a1 a0 b1 x1 x 1 x2x 2 b1 b1 a1 f x2 f x1 取 a1 x2 b1 b0 x 1 a1 b1 a1 x 2 x1 若求f x 的极大值点 则 f x2 f x1 取 a1 a0 b1 x1 x 1 x2x 2 b1 b1 a1 f x2 f x1 取 a1 x2 b1 b0 x 1 a1 b1 a1 x 2 x1 第二步 求区间的缩短率 11 例求解f x 18x2 72x 28的极大值点 0 1 起始搜索区间为 0 3 解 用间接法 令f x 36x 72 0 得驻点x 2又因为f x 36 0 故x 2为f x 的极大值点 fmax 100 用直接法中的黄金分割法 令 n 1 得n 1 lg lg 5 78442约6步即可 计算结果见下表 12 9 3无约束条件下多变量函数寻优一 爬山法原理 通过点的直接移动 逐步改善目标函数取值 直至达到极值点为止 由以下二部分组成 选定搜索方向 在选定的方向上爬山搜索 二 变量轮换法 或降维法 选择与坐标轴平行的方向为搜索方向设S f X f x1 x2 xn 极值点存在的区间为x1 a1 b1 x2 a2 b2 xn an bn 1 原理 从起点X 0 出发 沿平行于x1轴的方向P 1 进行一维搜索 求得f X 在该方向P 1 上近似极值点X 1 从点X 1 出发 沿平行于x2轴的方向P 2 进行一维搜索 求得f X 在该方向P 2 上近似极值点X 2 从点X 2 出发 照此交替进行下去 直至满足给定的精度 为止 f X k f X k 1 或 S k S k 1 13 2 算法步骤 设S f X f x1 x2 极值点存在的区间为x1 a1 b1 x2 a2 b2 第一步 从X 0 x1 0 x2 0 T出发 先固定x1 x1 0 求以x2为单变量的目标函数的极值点 得X 1 x1 0 x2 1 T S 1 f X 1 再固定x2 x2 1 求以x1为单变量的目标函数的极值点 得X 2 x1 2 x2 1 T S 2 f X 2 此时S 2 优于S 1 且搜索区间缩短为x1 x1 2 b1 x2 x2 1 b2 第二步 如此交替搜索 直至满足给定精度 为止 f X k f X k 1 或 S k S k 1 14 例求S f x x12 x22 x1x2 10 x1 4x2 60的极小值点 0 01 解 设起始点X 0 0 0 T 用变量轮换法计算 先固定x1 x1 0 0 则f 0 x2 x22 4x2 60 寻优得x2 1 2于是X 1 x1 0 x2 1 T 0 2 T S 1 f X 1 56 再固定x2 x2 1 2 则f x1 2 x12 12x1 56 寻优得x1 2 6于是X 2 x1 2 x2 1 T 6 2 T S 2 f X 2 20如此交替搜索 直至满足给定精度 0 01为止 f X k f X k 1 0 01或 S k S k 1 0 01最后得极小点X 8 6 T f X 8 计算结果见下表 15 缺点 很大程度上取决于目标函数性质 目标函数等高线的性质很重要 道路迂回曲折 多次变换方向 在极点附近 目标值改进更小 收敛速度慢 故不是一个有利方向 16 三 一阶梯度法 最速下降或上升法 选择负梯度方向为搜索方向设求S f X f x1 x2 xn 的极值点 1 原理 从起点X 0 出发 沿某个有利方向P 0 进行一维搜索 求得f X 在P 0 方向近似极小点X 1 从点X 1 出发 沿某个新有利方向P 1 进行一维搜索 求得f X 在P 1 方向近似极小点X 2 从点X 2 出发 照此进行下去 直至满足给定的精度 为止 f X k f X k 1 或 S k S k 1 2 算法步骤 设求S f X f x1 x2 的极值点 第一步 从给定起点X 0 出发 第二步 从点X 1 出发 照此进行下去 直至满足给定的精度 为止 f X k 1 f X k 或 G k 17 例求S f x x12 x22 x1x2 10 x1 4x2 60的极小值点 0 1 解 从点X 1 出发 照此进行下去 直至满足给定的精度 0 1为止 f X k 1 f X k 0 1或 G k 0 1 18 计算结果见下表 缺点 搜索效果比变量轮换法快 但愈接近极值点 步长愈小 目标值改进愈小 当遇到强交互作用时 不是有效的方法 当遇到山脊时 会慢慢爬行 在远离极点时 收敛速度较快 在极点附近 收敛速度不快 19 四 共轭梯度法 选择共轭方向为搜索方向 问题的提出 在极值点附近 如何加快收敛速度 须对函数在极值点附近的性质进行研究 设有n维目标函数S f X f x1 x2 xn 在极值点X 附近展开成泰勒级数 特别 对二元二次函数 可证明 在极值点附近 其等高线可近似视为同心椭园族 而同心椭园族的任意两根平行切线的切点连线必通过椭园中心 故 在极值点附近 沿搜索方向P 0 上巳得到一个切点X 1 则只要得出通过极值点的连线方向P 1 在此方向上寻优 可一步直达极值点 而这个连线方向P 1 是上一次搜索方向P 0 的共轭方向 20 共轭方向的定义 1 定义 设X Y是n维向量空间En中两个向量 A为n n对称正定矩阵 若XTAY 0 则称向量X与Y对于矩阵A共轭 特例 若A I 得XTY 0 则称向量X与Y正交 2 几何意义 共轭方向是通过极值点的方向 寻优原理 设n元函数S f X f x1 x2 xn 在极值点X 附近可用一个二次函数逼近 其中H为n n对称正定矩阵 21 特别 对二元二次函数S f X f x1 x2 从某点X 0 出发 以P 0 方向搜索 使f X 达到极小值点X 1 则 X 1 必为该点处等高线的切点 P 0 为切线方向 且点X 1 的梯度方向 f X 1 为该等高线的法线方向 这两个方向正交 从另一点X 0 出发 仍以P 0 方向搜索 使f X 达到另一个极小值点X 2 则 X 2 也必为该点处等高线的切点 P 0 为切线方向 且点X 2 的梯度方向 f X 2 为该等高线的法线方向 这两个方向正交 故 对二元二次函数 只须搜索两个方向P 0 和P 1 就可达到极值点X 一般 对n元二次函数 可用不超过n次搜索就可达到极值点X 而n元非二次函数在极值点附近可用二次函数逼近 22 寻优步骤 例求S f x x12 x22 x1x2 10 x1 4x2 60的极小值点 解 23 对二元二次函数 只须两次搜索就可达到极值点X 一般 对n元二次函数 可用不超过n次搜索就可达到极值点X 而n元非二次函数在极值点附近可用二次函数逼近 24 适用于一般目标函数的共轭梯度法 1 共轭方向的计算问题 须用到目标函数的海赛矩阵H 二阶偏导数矩阵 若目标函数为二次函数时 H容易求出 若目标函数为高次或高维函数时 H难以求出 此时共轭方向难以求出 2 共轭方向的计算方法 F R法 由Fletcher和Reeves提出 可避免海赛矩阵H的计算 方便地确定共轭方向 简单有效 25 3 搜索过程 从X 0 出发 从X 1 出发 26 从X 2 出发 4 搜索方法 若目标函数为n元二次函数 则理论上最多经n次迭代可达极小点 实际由于舍入误差 须n次以上的迭代 若目标函数为n元非二次函数 但共轭方向只有n个 迭代n次以后应重新开始迭代 减少误差积累 一般 在开始阶段 二次型较弱 用一阶梯度法 接近极点 二次型较强 用共轭梯度法 一般有 27 例求S f x x12 x22 x1x2 10 x1 4x2 60的极小值点 解 28 9 4有约束条件下多变量函数寻优一 具有等式约束的极值问题 1 消元法 n元非线性规划S f X f x1 x2 xn s t gk X 0 k 1 2 m m n若可从m个s t 中解出m个变量xi h xm 1 xm 2 xm i 1 2 m 代入目标函数中消去m个变量 则问题变为一个求n m个变量函数的无约束条件的极值问题 29 2 拉格朗日 Lagrangian 乘子法 n元非线性规划S f X f x1 x2 xn s t gk X 0 k 1 2 m 则L X 有极值的必要条件为 求出的解就是f X 的驻点 30 其中 拉格朗日乘子 k的经济意义 影子价格 单位资源的目标增量S f X f x1 x2 xn s t gk X bk k 1 2 m 知 k是约束式gk每变化一个单位 引起目标f值的变化率 若目标f为效用函数极大化 b为预算约束 则 表示增加一元预算收入 可使最大效用增加的值 若目标f为费用函数极小化 b为产出水平 则 表示降低一元产出 可使最大费用增加的值 影子费用 31 3 罚函数 代价函数 法 对n元非线性规划问题S f X f x1 x2 xn s t gk X 0 k 1 2 m R X pk 有极值的必要条件为 求出的解就是f X 的驻点 当s t 不满足时 pk越大 则R值越大 此时罚项是一种惩罚 当s t 满足时 不论pk多大 一般取 R X pk f X 此时罚项无效 32 33 二 具有不等式约束的极值问题 1 拉格朗日乘子法 引入松弛变量 将不等式约束化为等式约束 34 2 库恩 塔克 Kuhn Tuckers 条件法 适用范围 含有等式和不等式约束及变量非负的一般非线性规划 库 塔