-非线性规划-无约束问题.pptxVIP

第三章 最优化方法 运筹学 施鹏 当要求容器的容积一定，求表面积最小，以使用料最省。 第三节 非线性规划 s.t x1≥0，x2≥0 一连续反应器如图所示，进行如下反应 已知单位体积的液相反应速率为 原料A的单位成本 折旧、公用工程和其他费用 根据预测，市场只能提供物料A 600单位/h，产品B的市场需求量FB不超过50 单位/h，产品B的价格为C3=2000 元/单位。试确定物料A的进料速度FA0、初始浓度CA0、反应器体积V和转化率各取多大，才能使得该反应器在单位时间内的经济效益是最好的？ 目标函数或约束条件中有非线性函数的规划问题 非线性规划 非线性规划的最优解可能在其可行域中的任意一点达到 不一定是全局最优解 背景 理论计算 相对于计算要求，计算能力仍十分有限 背景 为加快计算速度，必须明确各种方法的特点，以针对不同问题选择最合适的方法 求解思路： 迭代 从一个选定的初始点x0出发，按照某种特定的迭代规则产生一个点列{xk} xk有穷点列：最后一个点为最优解 xk无穷点列：其中一个点为最优解 基本迭代格式 ：第k轮迭代点 ：第k+1轮迭代点 tk：有哪些信誉好的足球投注网站步长 pk：迭代方向 对于 存在ε0，使 则称x*为R上的局部极小点，f(x*)称为局部极小值 →严格局部极小点、严格局部极小值 基本概念 若对于任意x，有 则x*为R上的全局极小点， f(x*)为全局极小值 →严格全局极小点、严格全局极小值 基本概念 凸集： 对于在集合中的每一对点x1和x2，连接两点所形成的直线段上任一点 都在此集合内，则该集合为凸集 凸函数 凸规划 凸函数 如果函数 满足 则称f(x)为F上的凸函数 若 则称f(x)为严格凸函数 凸函数 凸规划 凸函数 凸规划 凸函数 凸函数 凸规划 非线性规划 如f(x)和gi(x)都为凸函数，则称该规划问题为凸规划 可以证明：f(x)的局部极小值也是全局最小值 理想情况 凸函数 凸规划 若f(x)有连续的一阶导数，则 f(x)为凸函数 ? 对?x1、x2 ?R，有f(x2)≥f(x1)+?f(x1)T (x2-x1) f(x)为严格凸函数 ? 对?x1、x2 ?R，有f(x2)＞f(x1)+ ?f(x1)T (x2-x1) 凸性和凹性的判定（一阶条件） Hessian矩阵 凸性和凹性的判定（二阶条件） H为对称矩阵 例 判断下列函数的凹凸性（ x ?R） (a) f(x)=3x2 (b) f(x)=2x (c) f(x)=-5x2 (d) f(x)=2x2-x3 解 (a) f”=6， 故f(x)为（严格）凸函数。 (b) f”=0，故f(x)既凸又凹 (c) f”=-10，故f(x)为（严格）凹函数 (d) f”=4-6x，故f(x)既不为凸也不为凹 对于多元函数，如何判断H是否正定？ 特征值 f(x) H 特征值 严格凸函数 正定 0 凸函数 半正定 ≥0 凹函数 半负定 ≤0 严格凹函数 负定 0 例 分析函数 指出此函数属于哪种类型 H正定，f(x)为严格凸函数 极值存在的必要条件和充分条件 对于一元函数f(x) 极值存在 必要条件→f’(x)=0（稳定点） 充分条件→ f’(x)=0且 无约束问题 f”(x)0 f”(x)0 对n维函数 必要条件： f(x)在x*处一阶可导 充分条件 H(x*)正定，则x*为极小值，反之为极大值 例 求函数 的所有稳定点 解 解方程组得 试判断所得的稳定点是否为最优解 求得各点的H特征值和稳定点类型如下： 稳定点 f(x) 特征值 1.941，3.854 0.9855 37.03 0.97 局部极小点 -1.053，1.028 -0.5134 10.50 3.50 （全局）极小点 0.6117，1.4929 2.8300 7.0 -2.56 鞍点 一维有哪些信誉好的足球投注网站法 多项式近似 求导数方法 主要方法 Fibonacci法 0.618法 二次插值法 三次插值法 一阶导数 二阶导数 最速下降法 共轭梯度法 牛顿法 拟牛顿法* 一维有哪些信誉好的足球投注网站法 步长tk的选定是由使目标函数值沿有哪些信誉好的足球投注网站方向下降最多为依据的，因此这一工作变成了求解以tk为变量的一元函数，故得名一维有哪些信誉好的足球投注网站法。 无约束问题 适用于某些不能求得一阶导数解析解的问题 如求最小回流比 其中?ij：组分i对组分j的相对挥发度 xDi：塔顶产品中i组分的组成 ?：由Underwood公式确定 用经典的微分 方法很难求解 斐波那契（Fibonacci）法（分数法） 0.618法 无需求导，根据函数值判断有哪些信誉好的足球投注网站方向 适用于求解已知极值区间的单峰函数 一维有哪些信誉好的足球投注网站法（消去法） f(x2)＜f(x1)，去掉[x1,b0]，此时x*?[a0,x1