09非线性规划：无约束极值问题.ppt

第四章 非线性规划 一 什么是非线性规划 目标函数和约束条件中有非线性函数的规划问题 例1某企业生产一种产品y需要生产资料x1和x2 用经济计量学方法根据统计资料可写出生产函数为 但是投入的资源有限 能源总共1O个单位 而每单位生产资料x1要消耗1单位能源 每单位生产资料x2要消耗2单位能源 问 应如何安排生产资料使产出最大 解 Max 例2某厂生产两种产品 第一种产品每件售价30元 第二种产品每件售价450元 设x1与x2分别为第一 二种产品的数量 据统计 生产第一种产品所需工作时间平均为0 5小时 生产第二种产品所需工作时间平均为 2 0 25x2 小时 已知该工厂在这段时间内允许的总工作时间为800小时 试确定使总收入最大的生产计划 解 max 二 非线性规划问题的特点局部最优点不是全局最优点 三 极值问题1 一元函数y f x 局部极值点存在的必要条件 f x0 0 此时求出的x0为驻点 局部极值点存在的充分条件 a 若f x0 0 则该点x0为局部极小值点 2 多元函数y f X f x1 x2 xn 在X0附近作泰勒展开 得 极值点存在的必要条件 f x 0 此时求出的x0为驻点 极值点存在的充分条件 二次型ZTHZ称为半正定 如果对任意Z 0 有ZTHZ 0二次型ZTHZ称为正定 如果对任意Z 0 有ZTHZ 0 四 凸函数与凹函数 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上的严格凹函数 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 凸函数的局部极值与全局极值的关系若目标函数在可行域中为凸函数 则其极值点为最优值点 若目标函数在可行域中为严格凸函数 则其极值点为唯一最优值点 五 凸规划 1 定义 非线性规划 若f X gi X 为凸函数 则 p 称为凸规划 2 性质 p 的可行解集R是凸集 最优解集R 也是凸集 p 的任何局部最优解均是全局最优解 若f X 为严格凸函数时 其最优解必唯一 特例 线性函数既是凸函数又是凹函数 故L P 为凸规划 六 寻优方法概述 1 非线性规划问题分类 无约束条件的非线性规划 有约束条件的非线性规划 2 寻优方法 间接法 解析法 适应于目标函数有简单明确的数学表达式 直接法 搜索法 目标函数复杂或无明确的数学表达式 a 消去法 对单变量函数有效 不断消去部分搜索区间 逐步缩小极值点存在的范围 b 爬山法 对多变量函数有效 根据已求得的目标值 判断前进方向 逐步改善目标值 迭代法 无约束极值问题的解法 一 梯度法 最速下降法 选择负梯度方向为搜索方向 2 算法步骤 设求S f X f x1 x2 xn 的极值点 第一步 从给定起点X 0 出发 第二步 从点X 1 出发 照此进行下去 直至满足给定的精度 为止 f X k 1 f X k or f X k 例求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 计算结果见下表 缺点 愈接近极值点 步长愈小 目标值改进愈小 当遇到山脊时 会慢慢爬行 在远离极点时 收敛速度较快 在极点附近 收敛速度不快 二 共轭梯度法 选择共轭方向为搜索方向 问题的提出 在极值点附近 如何加快收敛速度 须对函数在极值点附近的性质进行研究 设有n维目标函数S f X f x1 x2 xn 在极值点X 附近展开成泰勒级数 特别 对二元正定二次函数 可证明 在极值点附近 其等高线可近似视为同心椭园族 而同心椭园族的任意两根平行切线的切点连线必通过椭园中心 故 在极值点附近 沿搜索方向P 0 上巳得到一个切点X 1 则只要得出通过极值点的连线方向P 1 在此方向上寻优 可一步直达极值点 而这个连线方向P 1 是上一次搜索方向P 0 的共轭方向 共轭方向的定义 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对称正定矩阵 特别 对二元正定二次函数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元非二次函数在极值点附近可用二次函数逼近 寻优步骤 例求S f x x12 x22 x1x2 10 x1 4x2 60的极小值点 解 对二元二次函数 只须两次搜索就可达到极值点X 一般 对n元二次函数 可用不超过n次搜索就可达到极值点X 而n元非二次函数在极值点附近可用二次函数逼近 适用于一般目标函数的共轭梯度法 f x 为严格凸函数 且具有二阶连续偏导数 4 搜索