《非线性规划无约束问题课件.pptx》由会员分享，可在线阅读，更多相关《非线性规划无约束问题课件.pptx（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性规划无约束问题第1页，此课件共82页哦当要求容器的容积一定，求表面积最小，以使用料最省。第三节 非线性规划 x1x2s.tx10，x20第2页，此课件共82页哦一连续反应器如图所示，进行如下反应第3页，此课件共82页哦已知单位体积的液相反应速率为原料A的单位成本折旧、公用工程和其他费用第4页，此课件共82页哦根据预测，市场只能提供物料A 600单位/h，产品B的市场需求量FB不超过50 单位/h，产品B的价格为C3=2000 元/单位。试确定物料A的进料速度FA0、初始浓度CA0、反应器体积V和转化率各取多大，才能使得该反应器在单位时间内的经济效益是最好的？第5页，此课件共82页哦第6页
2、，此课件共82页哦目目标标函函数数或或约约束束条条件件中中有有非非线线性性函函数数的规划问题的规划问题非线性规划第7页，此课件共82页哦非线性规划的最优解可能在其可行域中的任意一点达到不一定是全局最优解第8页，此课件共82页哦背景理论计算相对于计算要求，计算能力仍十分有限第9页，此课件共82页哦第10页，此课件共82页哦背景为加快计算速度，必须明确各种方法的特点，以针对不同问题选择最合适的方法第11页，此课件共82页哦求解思路：迭代从一个选定的初始点x0出发，按照某种特定的迭代规则产生一个点列xkxk有穷点列：最后一个点为最优解xk无穷点列：其中一个点为最优解第12页，此课件共82页哦基本迭代
3、格式 ：第k轮迭代点 ：第k+1轮迭代点tk：搜索步长pk：迭代方向第13页，此课件共82页哦对于存在0，使则称x*为R上的局部极小点，f(x*)称为局部极小值严格局部极小点、严格局部极小值基本概念第14页，此课件共82页哦若对于任意x，有则x*为R上的全局极小点，f(x*)为全局极小值严格全局极小点、严格全局极小值基本概念第15页，此课件共82页哦Hessian矩阵凸性和凹性的判定（二阶条件）H为对称矩阵第16页，此课件共82页哦多元函数，如何判断H是否正定？特征值第17页，此课件共82页哦f(x)H特征值严格凸函数正定0凸函数半正定0凹函数半负定0严格凹函数负定0,0f”(x)0第22页，
4、此课件共82页哦对n维函数必要条件：f(x)在x*处一阶可导充分条件H(x*)正定，则x*为极小值，反之为极大值第23页，此课件共82页哦例 求函数的所有稳定点解第24页，此课件共82页哦解方程组得第25页，此课件共82页哦试判断所得的稳定点是否为最优解第26页，此课件共82页哦求得各点的H特征值和稳定点类型如下：稳定点f(x)特征值1.941，3.8540.985537.030.97局部极小点-1.053，1.028-0.513410.503.50（全局）极小点0.6117，1.49292.83007.0-2.56鞍点第27页，此课件共82页哦第28页，此课件共82页哦一维搜索法多项式近似求
5、导数方法主要方法Fibonacci法0.618法二次插值法三次插值法一阶导数二阶导数最速下降法共轭梯度法牛顿法拟牛顿法*第29页，此课件共82页哦一维搜索法步长tk的选定是由使目标函数值沿搜索方向下降最多为依据的，因此这一工作变成了求解以tk为变量的一元函数，故得名一维搜索法。无约束问题第30页，此课件共82页哦适用于某些不能求得一阶导数解析解的问题如求最小回流比其中 ij：组分i对组分j的相对挥发度 xDi：塔顶产品中i组分的组成 ：由Underwood公式确定用经典的微分方法很难求解第31页，此课件共82页哦斐波那契（Fibonacci）法（分数法）0.618法无需求导，根据函数值判断搜索
6、方向适用于求解已知极值区间的单峰函数一维搜索法（消去法）第32页，此课件共82页哦f(x2)f(x1)，去掉x1,b0，此时x*a0,x1一维搜索法（消去法）f(x)xoa0b0 x*x1,x2 在x*的右侧x1x2第33页，此课件共82页哦f(x2)f(x1)，去掉a0,x2，此时x*x2,b0一维搜索法（消去法）f(x)xoa0b0 x*x1,x2 在x*的左侧x1x2第34页，此课件共82页哦f(x2)f(x1)：a.去掉x1,b0，此时x*a0,x1 b.去掉a0,x2，此时x*x2,b0 f(x)xoa0b0 x*x1,x2 在x*的两侧x1x2第35页，此课件共82页哦斐波那契数列
7、数列Fn为斐波那契数列 斐波那契分数斐波那契（Fibonacci）法第36页，此课件共82页哦n012345Fn112358n67891011Fn1321345589144第37页，此课件共82页哦计算步骤选取初始数据，确定单峰区间a0,b0根据缩短率计算Fn，再确定最小n值计算初值t1和t2，计算f(t1)、f(t2)第38页，此课件共82页哦当区间变为a0,t2第39页，此课件共82页哦反之区间变为t1,b0第40页，此课件共82页哦确定n个搜索点以后，每次的区间缩短率为第41页，此课件共82页哦n次计算能得到的区间长度比为要使精度够大，即：区间缩短的相对精度第42页，此课件共82页哦如果
8、至某一步则可令第43页，此课件共82页哦可以证明对于斐波那契数列，其奇数项和偶数项都各自收敛于同一极限，该极限值等于0.618法第44页，此课件共82页哦以0.618作为固定的区间缩短率代替斐波那契法不同的缩短率，就得到了0.618法实施更为容易第45页，此课件共82页哦第46页，此课件共82页哦计算步骤选取初始区间a0,b0第47页，此课件共82页哦 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 Lt2t1a0b0La1b1t2t1a1b1t2t1
9、第48页，此课件共82页哦搜索n个点后的 区间长度缩短为或者说，迭代k次以后的区间长度变为即 已知搜索的相对精度，迭代次数满足第49页，此课件共82页哦例 用0.618法求设初始区间为a0=-1.0，b0=3.0，要求剩余区间长度不大于0.1解 本例可以通过解析法求得精确解第50页，此课件共82页哦第一次搜索选取两个初始试算点比较得，第51页，此课件共82页哦可以得到下一次搜索区间第52页，此课件共82页哦第二次搜索计算试算点第53页，此课件共82页哦确定下一轮搜索区间第54页，此课件共82页哦迭代次数kak-1bk-1x(k,1)x(k,2)(x(k,1)(x(k,2)剩余区间长度1-130
10、.5281.4721.75078 2.694782.4722-11.472-0.0556960.5282.05879 1.75078 1.5276963-0.0556961.4720.5280.888421.75078 1.90087 0.9441164-0.0556960.888420.3049560.5281.78804 1.75078 0.58346450.3049560.888420.5280.6655361.75078 1.77740 0.3605860.3049560.6655360.44270.5281.75321.750780.228101.75002 1.750060.032
11、5第55页，此课件共82页哦不断用低次（不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近最优解多项式近似（插值法、抛物线法）第56页，此课件共82页哦最速下降法共轭梯度法牛顿法拟牛顿法使用导数的方法第57页，此课件共82页哦对于迭代格式使目标函数f下降最快的方向是点xk的负梯度方向称为f在xk的最速下降方向每一轮都从点xk出发沿最速下降方向进行搜索的方法，称为最速下降法最速下降法第58页，此课件共82页哦具体步骤选取初始点x0，给定终止误差 求梯度向量。计算 ，若 ，停止迭代，输出xk构造负梯度方向进行搜索。求tk，使得令 ，重新求梯度向量最速下降法第59页，此课件共82页哦
12、例 求解 令x(0)=(1,2)T,1，2为任意实数假设x(0)不是最优点则令第60页，此课件共82页哦代入目标函数，求最优步长t0有令第61页，此课件共82页哦因故x(1)为最优解，最优值f(x*)=0对于目标函数的等值线为圆的问题，最速下降法总能一步得到最优解第62页，此课件共82页哦例 用最速下降法求解 取x(0)=(2,2)T第63页，此课件共82页哦令代入目标函数，得t(0)=2.005第64页，此课件共82页哦继续迭代，得kt(k)x1x202.0052.0002100.0810411.8501.920-0.0033.8433.68720.0710.0710.0713.5470.1
13、3130.0650.0680.0000.1360.46310-240.0030.0030.0030.1260.16410-2第65页，此课件共82页哦可能在任何类型的稳定点终止。通过分析Hessian矩阵来检验是否是极小点。对f(x)的尺度太灵敏，收敛缓慢，容易产生大量摆动（局部最速下降，相邻搜索方向彼此正交）。最速下降法第66页，此课件共82页哦f(x)为二阶可导函数，且在每个搜索方向上能准确最小化，则较少次迭代即可收敛计算量略大，收敛速度大幅提高搜索方向结合当前梯度方向和前一次梯度方向，搜索方向共轭解大型线性或非线性方程组最有效的方法之一存储空间小，稳定性高共轭梯度法第67页，此课件共82
14、页哦牛顿法（Newtons method）（Newton-Raphson method）若H正定，则Q(x)的稳定点xk+1为最小点，该点可表示为解得对照第68页，此课件共82页哦可得由此，可反复利用方程直到满足收敛条件牛顿法第69页，此课件共82页哦例 用牛顿法求解 该函数的一阶、二阶导数分别为一维函数的牛顿法第70页，此课件共82页哦若取初始点x(0)=3，则故第71页，此课件共82页哦迭代次数kx(k)(x(k)(x(k)|(x(k)|03-52245215.167153.352184.33153.35224.33532.302109.44632.30234.0403.38386.870
15、3.38344.0010.005584.0470.0055|(x(k)|0.01第72页，此课件共82页哦例 求解解，取x(0)=(0,0)T有第73页，此课件共82页哦得为检验x(1)是否为最优点，即x(1)为最优点第74页，此课件共82页哦几何意义牛顿法第75页，此课件共82页哦收敛速度很快，对于严格凸函数，只需一步即可得到极小值对纯牛顿法模型，如果初始值与局部极小值不是足够接近，通常不收敛需要计算一阶、二阶导数，计算量大，存储空间大对于一阶导数非单调变化的函数，往往会失败牛顿法第76页，此课件共82页哦为避免计算二阶导数矩阵H及其逆阵，我们设法构造另一个矩阵，用它来逼近二阶导数矩阵的逆阵，称拟牛顿法拟牛顿法（Quasi-Newton Method）第77页，此课件共82页哦构造近似矩阵当f(x)为二阶函数，H为常数矩阵即对于非二阶函数拟牛顿法（Quasi-Newton Method）第78页，此课件共82页哦BFGS校正：近似Hessian矩阵：拟牛顿法（Quasi-Newton Method）第79页，此课件共82页哦用有限差分代替一阶、二阶导数一维函数的拟牛顿法h：步长第80页，此课件共82页哦例 用拟牛顿法求解 令取x(0)=3，h=10-3第81页，此课件共82页哦最优解析解第82页，此课件共82页哦