《一非线性规划-无约束问题教学幻灯片》由会员分享，可在线阅读，更多相关《一非线性规划-无约束问题教学幻灯片（96页珍藏版）》请在金锄头文库上搜索。
1、第三章 最优化方法 运筹学,施鹏, system,第三节 非线性规划,当要求容器的容积一定，求表面积最小，以使用料最省。,s.t,x10，x20,已知单位体积的液相反应速率为 原料A的单位成本 折旧、公用工程和其他费用,根据预测，市场只能提供物料A 600单位/h，产品B的市场需求量FB不超过50 单位/h，产品B的价格为C3=2000 元/单位。试确定物料A的进料速度FA0、初始浓度CA0、反应器体积V和转化率各取多大，才能使得该反应器在单位时间内的经济效益是最好的？,非线性规划,目标函数或约束条件中有非线性函数的规划问题,非线性规划的最优解可能在其可行域中的任意一点达到 不一定是全局最优解
2、,背景 理论计算 相对于计算要求，计算能力仍十分有限,背景 为加快计算速度，必须明确各种方法的特点，以针对不同问题选择最合适的方法,求解思路： 迭代 从一个选定的初始点x0出发，按照某种特定的迭代规则产生一个点列xk,xk有穷点列：最后一个点为最优解 xk无穷点列：其中一个点为最优解,基本迭代格式 ：第k轮迭代点 ：第k+1轮迭代点 tk：搜索步长 pk：迭代方向,基本概念,对于 存在0，使 则称x*为R上的局部极小点，f(x*)称为局部极小值 严格局部极小点、严格局部极小值,基本概念,若对于任意x，有 则x*为R上的全局极小点， f(x*)为全局极小值 严格全局极小点、严格全局极小值,凸函数
3、 凸规划,凸集： 对于在集合中的每一对点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
4、(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”=6-3x，故f(x)既不为凸也不为凹,对于多元函数，如何判断H是否正定？,特征值,例 分析函数 指出此函数属于哪种类型,H正定，f(x)为严格凸函数,无约束问题,极值存在的必要条件和充分条件
5、对于一元函数f(x) 极值存在 必要条件f(x)=0（稳定点） 充分条件 f(x)=0且 f”(x)0 f(x)0,对n维函数 必要条件： f(x)在x*处一阶可导 充分条件 H(x*)正定，则x*为极小值，反之为极大值,例 求函数 的所有稳定点 解,解方程组得,试判断所得的稳定点是否为最优解,求得各点的H特征值和稳定点类型如下：,主要方法,一维搜索法 多项式近似 求导数方法,Fibonacci法,0.618法,二次插值法,三次插值法,一阶导数,二阶导数,最速下降法,共轭梯度法,牛顿法,拟牛顿法,无约束问题,一维搜索法 步长tk的选定是由使目标函数值沿搜索方向下降最多为依据的，因此这一工作变成
6、了求解以tk为变量的一元函数，故得名一维搜索法。,适用于某些不能求得一阶导数解析解的问题 如求最小回流比 其中ij：组分i对组分j的相对挥发度 xDi：塔顶产品中i组分的组成 ：由Underwood公式确定,用经典的微分 方法很难求解,一维搜索法（消去法）,斐波那契（Fibonacci）法（分数法） 0.618法 无需求导，根据函数值判断搜索方向 适用于求解已知极值区间的单峰函数,一维搜索法（消去法）,f(x2)f(x1)，去掉x1,b0，此时x*a0,x1,一维搜索法（消去法）,f(x2)f(x1)，去掉a0,x2，此时x*x2,b0,f(x2)f(x1)： a.去掉x1,b0，此时x*a0
7、,x1 b.去掉a0,x2，此时x*x2,b0,斐波那契（Fibonacci）法,斐波那契数列 数列Fn为斐波那契数列 斐波那契分数,计算步骤 选取初始数据，确定单峰区间a0, b0 根据缩短率计算Fn，再确定最小n值 计算初值t1和t2，计算f(t1)、f(t2),当 区间变为a0, t2,反之 区间变为t1, b0,确定n个搜索点以后，每次的区间缩短率为,n次计算能得到的区间长度比为 要使精度够大，即 ：区间缩短的相对精度,如果至某一步 则可令,0.618法,可以证明对于斐波那契数列，其奇数项和偶数项都各自收敛于同一极限，该极限值等于,以0.618作为固定的区间缩短率代替斐波那契法不同的缩
8、短率，就得到了0.618法 实施更为容易,计算步骤 选取初始区间a0, b0,f(t1)f(t2)，取a1=a0, b1=t2 t2=t1 t1=a1+0.382(b1-a1) f(t1)f(t2)，取a1=t1, b1=b0 t2=a1+ 0.618(b1-a1) t1=t2,搜索n个点后的 区间长度缩短为 或者说，迭代k次以后的区间长度变为 即 已知搜索的相对精度，迭代次数满足,例 用0.618法求 设初始区间为a0=-1.0，b0=3.0，要求剩余区间长度不大于0.1 解 本例可以通过解析法求得精确解,第一次搜索 选取两个初始试算点 比较得，,可以得到下一次搜索区间,第二次搜索 计算试算
9、点,确定下一轮搜索区间,多项式近似（插值法、抛物线法）,不断用低次（不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近最优解,直接迭代法,使用一阶导数的方法,最速下降法 共轭梯度法 牛顿法 拟牛顿法 割线法,最速下降法,对于迭代格式 使目标函数f下降最快的方向是点xk的负梯度方向 称为f在xk的最速下降方向 每一轮都从点xk出发沿最速下降方向进行搜索的方法，称为最速下降法,最速下降法,具体步骤 选取初始点x0，给定终止误差 求梯度向量。计算 ， 若 ，停止迭代，输出xk 构造负梯度方向 进行搜索。求tk，使得 令 ，重新求梯度向量,例 求 解 令x(0)=(1, 2)T, 1，
10、2为任意实数 假设x(0)不是最优点 则令,代入目标函数，求最优步长t0 有 令,因 故x(1)为最优解，最优值f(x*)=0,对于目标函数的等值线为圆的问题， 最速下降法总能一步得到最优解,例 用最速下降法求 解 取x(0)=(2, 2)T,令 代入目标函数，得t(0)=2.003,继续迭代，得,最速下降法,可能在任何类型的稳定点终止。 通过分析Hessian矩阵来检验是否是极小点。 对f(x)的尺度太灵敏，收敛缓慢，容易产生大量摆动（局部最速下降，相邻搜索方向彼此正交）。,共轭梯度法,f(x)为二阶可导函数，且在每个搜索方向上能准确最小化，则较少次迭代即可收敛 计算量略大，收敛速度大幅提高
11、 搜索方向结合当前梯度方向和前一次梯度方向，搜索方向共轭 解大型线性或非线性方程组最有效的方法之一 存储空间小，稳定性高,牛顿法（Newtons method）（Newton-Raphson method）,若H正定，则Q(x)的稳定点xk+1为最小点，该点可表示为,解得,对照,牛顿法,可得 由此，可反复利用方程 直到满足收敛条件,例 求解 解，取x(0)=(0, 0)T 有,得 为检验x(1)是否为最优点，,即x(1)为最优点,牛顿法,几何意义,一维函数的牛顿法,例 用牛顿法求 解 该函数的一阶、二阶导数分别为,若取初始点x(0)=3，则 故,|(x(k)| 0.01,牛顿法,收敛速度很快，
12、对于严格凸函数，只需一步即可得到极小值 对纯牛顿法模型，每一步步长为1，但如果初始值与局部极小值不是足够接近，通常不收敛 需要计算一阶、二阶导数，计算量大，存储空间大 对于一阶导数非单调变化的函数，往往会失败,拟牛顿法（Quasi-Newton Method）,为避免计算二阶导数矩阵H及其逆阵，我们设法构造另一个矩阵，用它来逼近二阶导数矩阵的逆阵 ，称拟牛顿法,Quasi-Bush=Monkey,拟牛顿法（Quasi-Newton Method）,构造近似矩阵 当f(x)为二阶函数，H为常数矩阵 即 对于非二阶函数,拟牛顿法（Quasi-Newton Method）,BFGS校正： 近似Hessian矩阵：,一维函数的拟牛顿法,用有限差分代替一阶、二阶导数,h：步长,例 用拟牛顿法求 解 令 取x(0)=3，h=10-3,最优解析解,拟牛顿法（Quasi-Newton Method）,比牛顿法迭代速度更快 适用于写不出目标函数的明确解析式，或导数的解析式 对于多参数问题，计算时间和存储空间大,割线法,函数二阶可导 初值,几种计算收敛方法的比较,
