05-非线性规划-无约束问题培训课件.pptx

,单击此处编辑母版标题样式,2012/5/17,#,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 最优化方法 运筹学,施鹏,当要求容器的容积一定，求表面积最小，以使用料最省。,第三节 非线性规划,x,1,x,2,s.t,x,1,0,，,x,2,0,一连续反应器如图所示，进行如下反应,根据预测，市场只能提供物料,A 600,单位,/h,，产品,B,的市场需求量,F,B,不超过,50,单位,/h,，产品,B,的价格为,C,3,=2000,元,/,单位。试确定物料,A,的进料速度,F,A0,、初始浓度,C,A0,、反应器体积,V,和转化率各取多大，才能使得该反应器在单位时间内的经济效益是最好的？,目标函数或约束条件中有,非线性函数,的规划问题,非线性规划,非线性规划的最优解可能在其可行域中的任意一点达到,不一定是全局最优解,背景,理论计算,相对于计算要求，计算能力仍十分有限,背景,为加快计算速度，必须明确各种方法的特点，以针对不同问题选择最合适的方法,求解思路：,迭代,从一个选定的初始点,x,0,出发，按照某种特定的迭代规则产生一个点列,x,k,x,k,有穷点列：最后一个点为最优解,x,k,无穷点列：其中一个点为最优解,基本迭代格式,：第,k,轮迭代点,：第,k,+1,轮迭代点,t,k,：搜索步长,p,k,：迭代方向,对于,存在,0,，使,则称,x,*,为,R,上的,局部极小点,，,f,(,x,*,),称为,局部极小值,严格局部极小点,、,严格局部极小值,基本概念,若对于任意,x,，有,则,x,*,为,R,上的,全局极小点,，,f,(,x,*,),为,全局极小值,严格全局极小点、严格全局极小值,基本概念,凸集：,对于在集合中的每一对点,x,1,和,x,2,，连接两点所形成的直线段上任一点,都在此集合内，则该集合为凸集,凸函数 凸规划,凸函数,如果函数 满足,则称,f,(,x,),为,F,上的,凸函数,若,则称,f,(,x,),为,严格凸函数,凸函数 凸规划,凸函数 凸规划,y,x,o,x,1,x,2,x,1,+(,1-,),x,2,y,=,f,(,x,),凸函数,凸函数 凸规划,y,x,o,x,1,x,2,x,1,+(,1-,),x,2,y,=,f,(,x,),非线性规划,如,f,(,x,),和,g,i,(,x,),都为凸函数，则称该规划问题为,凸规划,可以证明：,f,(,x,),的局部极小值也是全局最小值,理想情况,凸函数 凸规划,若,f,(,x,),有连续的一阶导数，则,f,(,x,),为凸函数,对,x,1,、,x,2,R,，有,f,(,x,2,),f,(,x,1,)+,f,(,x,1,),T,(,x,2,-,x,1,),f,(,x,),为严格凸函数,对,x,1,、,x,2,R,，有,f,(,x,2,),f,(,x,1,)+,f,(,x,1,),T,(,x,2,-,x,1,),凸性和凹性的判定（一阶条件）,Hessian,矩阵,凸性和凹性的判定（二阶条件）,H,为对称矩阵,例 判断下列函数的凹凸性（,x,R,）,(a),f,(,x,)=3,x,2,(b),f,(,x,)=2,x,(c),f,(,x,)=-5,x,2,(d),f,(,x,)=2,x,2,-,x,3,解,(a),f,”,=6,，故,f,(,x,),为（严格）凸函数。,(b),f,”,=0,，故,f,(,x,),既凸又凹,(c),f,”,=-10,，故,f,(,x,),为（严格）凹函数,(d),f,”,=4-6,x,，故,f,(,x,),既不为凸也不为凹,对于多元函数，如何判断,H,是否正定？,特征值,f,(,x,),H,特征值,严格凸函数,正定,0,凸函数,半正定,0,凹函数,半负定,0,严格凹函数,负定,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,法,二次插值法,三次插值法,一阶导数,二阶导数,最速下降法,共轭梯度法,牛顿法,拟牛顿法,*,一维搜索法,步长,t,k,的选定是由使目标函数值沿搜索方向下降最多为依据的，因此这一工作变成了求解以,t,k,为变量的一元函数，故得名,一维搜索法,。,无约束问题,适用于某些不能求得一阶导数解析解的问题,如求最小回流比,其中,ij,：组分,i,对组分,j,的相对挥发度,x,Di,：塔顶产品中,i,组分的组成,：由,Underwood,公式确定,用经典的微分,方法很难求解,斐波那契（,Fibonacci,）法（分数法）,0.618,法,无需求导，根据函数值判断搜索方向,适用于求解已知极值区间的单峰函数,一维搜索法（消去法）,f,(,x,2,),f,(,x,1,),，去掉,x,1,b,0,，此时,x,*,a,0,x,1,一维搜索法（消去法）,f,(,x,),x,o,a,0,b,0,x,*,x,1,x,2,在,x,*,的右侧,x,1,x,2,f,(,x,2,),f,(,x,1,),，去掉,a,0,x,2,，此时,x,*,x,2,b,0,一维搜索法（消去法）,f(x),x,o,a,0,b,0,x,*,x,1,x,2,在,x,*,的左侧,x,1,x,2,f,(,x,2,),f,(,x,1,),：,a.,去掉,x,1,b,0,，此时,x,*,a,0,x,1,b.,去掉,a,0,x,2,，此时,x,*,x,2,b,0,f,(,x,),x,o,a,0,b,0,x,*,x,1,x,2,在,x,*,的两侧,x,1,x,2,斐波那契数列,数列,F,n,为斐波那契数列,斐波那契分数,斐波那契（,Fibonacci,）法,n,0,1,2,3,4,5,F,n,1,1,2,3,5,8,n,6,7,8,9,10,11,F,n,13,21,34,55,89,144,计算步骤,选取初始数据，确定单峰区间,a,0,b,0,根据缩短率计算,F,n,，再确定最小,n,值,计算,初值,t,1,和,t,2,，计算,f,(,t,1,),、,f,(,t,2,),当,区间变为,a,0,t,2,反之,区间变为,t,1,b,0,确定,n,个搜索点以后，每次的区间缩短率为,n,次计算能得到的区间长度比为,要使精度够大，即,：区间缩短的,相对精度,如果至某一步,则可令,可以证明对于斐波那契数列，其奇数项和偶数项都各自收敛于同一极限，该极限值等于,0.618,法,以,0.618,作为固定的区间缩短率代替斐波那契法不同的缩短率，就得到了,0.618,法,实施更为容易,计算步骤,选取初始区间,a,0,b,0,f,(,t,1,),f,(,t,2,),，取,a,1,=,a,0,b,1,=,t,2,t,2,=,t,1,t,1,=,a,1,+,0.382(,b,1,-,a,1,),f,(,t,1,),f,(,t,2,),，取,a,1,=,t,1,b,1,=,b,0,t,2,=,a,1,+,0.618(,b,1,-,a,1,),t,1,=,t,2,L,t,2,t,1,a,0,b,0,L,a,1,b,1,t,2,t,1,a,1,b,1,t,2,t,1,搜索,n,个点后的 区间长度缩短为,或者说，迭代,k,次以后的区间长度变为,即 已知搜索的相对精度,，迭代次数满足,例,用,0.618,法求,设初始区间为,a,0,=-1.0,，,b,0,=3.0,，要求剩余区间长度不大于,0.1,解 本例可以通过解析法求得精确解,第一次搜索,选取两个初始试算点,比较得，,可以得到下一次搜索区间,第二次搜索,计算试算点,确定下一轮搜索区间,迭代次数,k,a,k,-1,b,k,-1,x,(,k,1),x,(,k,2),(,x,(,k,1),),(,x,(,k,2),),剩余区间长度,1,-1,3,0.528,1.472,1.75078,2.69478,2.472,2,-1,1.472,-0.055696,0.528,2.05879,1.75078,1.527696,3,-0.055696,1.472,0.528,0.88842,1.75078,1.90087,0.944116,4,-0.055696,0.88842,0.304956,0.528,1.78804,1.75078,0.583464,5,0.304956,0.88842,0.528,0.665536,1.75078,1.77740,0.36058,6,0.304956,0.665536,0.4427,0.528,1.7532,1.75078,0.228,10,1.75002,1.75006,0.0325,不断用低次（不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近,最优解,多项式近似（,插值法,、抛物线法）,最速下降法,共轭梯度法,牛顿法,拟牛顿法,割线法,使用导数的方法,对于迭代格式,使目标函数,f,下降最快的方向是点,x,k,的负梯度方向,称为,f,在,x,k,的,最速下降方向,每一轮都从点,x,k,出发沿最速下降方向进行搜索的方法，称为最速下降法,最速下降法,具体步骤,选取初始点,x,0,，给定终止误差,求梯度向量。计算,，若,，停止迭代，输出,x,k,构造负梯度方向,进行搜索。求,t,k,，使得,令,，重新求梯度向量,最速下降法,例,求,解,令,x,(0),=(,1,2,),T,1,，,2,为任意实数,假设,x,(0),不是最优点,则令,代入目标函数，求最优步长,t,0,有,令,因,故,x,(1),为最优解，最优值,f,(,x,*,)=0,对于目标函数的等值线为圆的问题，,最速下降法总能一步得到最优解,例 用最速下降法求,解,取,x,(0),=(2,2),T,令,代入目标函数，得,t,(0),=2.005,继续迭代，得,k,t,(,k,),x,1,x,2,0,2.005,2.000,2,100.08,104,1,1.850,1.920,-0.003,3.843,3.687,2,0.071,0.071,0.071,3.547,0.131,3,0.065,0.068,0.000,0.136,0.46310,-2,4,0.003,0.003,0.003,0.126,0.16410,-2,可能在任何类型的稳定点终止。,通过分析,Hessian,矩阵,来检验是否是极小点,。,对,f,(,x,),的尺度太灵敏，收敛缓慢，容易产生大量摆动（局部最速下降，相邻搜索方向彼此正交）。,最速下降法,f,(,x,),为二阶可导函数，且在每个搜索方向上能准确最小化，则较少次迭代即可收敛,计算量略大，收敛速度大幅提高,搜索方向结合当前梯度方向和前一次梯度方向，搜索方向共轭,解大型线性或非线性方程组,最有效,的方法之一,存储空间小，稳定性高,共轭梯度法,牛顿法（,Newtons method,）,（,Newton-Raphson method,）,若,H,正定，则,Q,(,x,),的稳定点,x,k,+1,为最小点，该点可表示为,解得,对照,可得,由此，可反复利用方程,直到满足收敛条件,牛顿法,例,求解,解，取,x,(0),=(0,0),T,有,得,为检验,x,(1),是否为最优点，,即,x,(1),为最优点,几何意义,牛顿法,例,用牛顿法求,解 该函数的一阶、二阶导数分别为,一维函数的牛顿法,若取初始点,x,(0),=3,，则,故,迭代次数,k,x,(,k,),(,x,(,k,),),(,x,(,k,),),|,(,x,(,k,),)|,0,3,-52,24,52,1,5.167,153.352,184.33,153.352,2,4.335,32.302,109.446,32.302,3,4.040,3.383,86.870,3.383,4,4.001,0.0055,84.047,0.0055,|,(,x,(,k,),)|,0.01,收敛速度很快，对于严格凸函数，只需一步即可得到极小值,对纯牛顿法模型，每一步步长为,1,，但如果初始值与局部极小值不是足够接近，,通常不收敛,需要计算一阶、二阶导数，,计算量大，存储空间大,对于一阶导数非单调变化的函数，往往会,失败,牛顿法,为避免计算,二阶导数矩阵,H,及其逆阵，我们设法构造另一个矩阵，用它来逼近二阶导数矩阵的逆阵,，称,拟牛顿法,拟牛顿法（,Quasi-Newton Method,）,Quasi-Bush=Monkey,构造近似矩阵,当,f,(,x,),为二阶函数，,H,为常数矩阵,即,对于非二阶函数,拟牛顿法（,Quasi-Newton Method,）,BFGS,校正：,近似,Hessian,矩阵：,拟牛顿法（,Quasi-Newton Method,）,用有限差分代替一阶、二阶导数,一维函数的拟牛顿法,h,：步长,例 用拟牛顿法求,解 令,取,x,(0),=3,，,h,=10,-3,最优解析解,适用于写不出目标函数的明确解析式，或导数的解析式,对于多参数问题，,计算时间和存储空间大,拟牛顿法（,Quasi-Newton Method,）,函数二阶可导,初值,割线法,几种,计算收敛方法的比较,方法,预测搜索方向,预测搜索距离,是否要求导数,是否能,保证总是,局部下降,由基准点预测新方向时要算多少次函数值,相对收敛速度,直接迭代法,是,是,否,否,1,后期搜索慢,牛顿拉夫森法,是,是,是,是,n,快,割线法,是,是,否,是,n,相当,快,拟牛顿法,是,是,否,否,1,相当快,