单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,非线性规划,非线性规划,1,（优选）非线性规划,2,（优选）非线性规划2,2,、多元函数,y=f(X)=f(x,1,x,2,x,n,),：在,X,0,附近作泰勒展开，得,2、多元函数 y=f(X)=f(x1,x2,xn)：,3,极值点存在的必要条件：,f(x)=0,，此时求出的,x,0,为驻点。,极值点存在的充分条件：,极值点存在的必要条件：f(x)=0，此时求出的,4,四、,凸函数与凹函数,：,1,、定义：,y=f(x),是,E,n,中某凸集,R,上的函数,对,0,1,及,X,1,、,X,2,R,，且,X,1,X,2,若,fX,1,+(1-)X,2,f(X,1,)+(1-)f(X,2,),，则,f(x),为,R,上的凸函数。,若,fX,1,+(1-)X,2,f(X,1,)+(1-)f(X,2,),，则,f(x),为,R,上的严格凸函数。,对,0,1,及,X,1,、,X,2,R,，且,X,1,X,2,若,fX,1,+(1-)X,2,f(X,1,)+(1-)f(X,2,),，则,f(x),为,R,上的,凹,函数。,若,fX,1,+(1-)X,2,f(X,1,)+(1-)f(X,2,),，则,f(x),为,R,上的严格,凹,函数。,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),凹,函数,y,x,o,X,1,X,2,y=f(x),非凸、非,凹,函数,四、凸函数与凹函数：yxoX1X2X1+(1-)X2y=,5,2,、性质：,f,i,(X),为凸集,R,上的凸函数，则对,k,i,0,，,i=1,2,m,，有,k,1,f,1,(X)+k,2,f,2,(X)+,+k,m,f,m,(X),仍为,凸函数。,3,、凸函数的判定：,f(X),定义在凸集,R,上，若,f(X),有连续的二阶导数，,则,f(X),为凸函数,H,为半正定。,f(X),为严格凸函数,H,为正定。,4,、,凸函数的局部极值与全局极值的关系,若目标函数在可行域中为,凸函数，则其极值点为最优值点；,若目标函数在可行域中为,严格凸函数，则其极值点为唯一最优值点。,2、性质：fi(X)为凸集R上的凸函数，则对ki0,6,五、,凸规划,：,1,、定义：非线性规划,(p),Min f(X),g,i,(X)0,，,i=1,2,m,若,f(X),，,-g,i,(X),为凸函数，则,(p),称为凸规划。,2,、性质：,(p),的可行解集,R,是凸集；最优解集,R,*,也是凸集。,(p),的任何局部最优解均是全局最优解。,若,f(X),为严格凸函数时，其最优解必唯一。,特例,:,线性函数既是凸函数又是凹函数，故,L.P.,为凸规划。,六、,寻优方法概述,：,1,、,N.L.P.,问题分类,无约束条件的,NLP,问题。,有约束条件的,NLP,问题。,2,、,寻优方法,间接法,(,解析法,),：适应于目标函数有简单明确的数学表达式。,直接法,(,搜索法,),：目标函数复杂或无明确的数学表达式。,a.,消去法,(,对单变量函数有效,),：,不断消去部分搜索区间，逐步缩小极值点存在的范围。,b.,爬山法,(,对多变量函数有效,),：,根据已求得的目标值，判断前进方向，逐步改善目标值。,五、凸规划：(p)Min f(X)gi(X)0，i=,7,9.2,无约束条件下单变量函数寻优,一、消去法原理：,逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。,设要寻求,f(X),的极小值点为,X,*,，起始搜索区间为,a,0,b,0,。,x,1,、,x,2,a,0,b,0,，且,x,2,x,1,，计算,f(x,1,),和,f(x,2,),，并且比较结果：,f(x),x,o,a,0,b,0,X,*,x,1,x,2,在,x,*,的右侧,x,1,x,2,f(x),x,o,a,0,b,0,X,*,x,1,x,2,在,x,*,的左侧,x,1,x,2,f(x),x,o,a,0,b,0,X,*,x,1,x,2,在,x,*,的两侧,x,1,x,2,x,1,x,2,均在,x,*,的右侧，,f(x,2,),f(x,1,),，去掉,x,1,b,0,，此时,x,*,a,0,x,1,x,1,x,2,均在,x,*,的左侧，,f(x,2,),f(x,1,),，去掉,a,0,x,2,，此时,x,*,x,2,b,0,x,1,x,2,均在,x,*,的两侧，,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,9.2 无约束条件下单变量函数寻优f(x)xoa0b0X*x,8,二、黄金分割法,(0.618,法,),：是一种常用的消去法,与对分法、,Fibonacci,法比较，具有计算次数少，过程简单的特点。,1,、原理：,L,x,L-x,L,x,1,x,2,2,、取点法则：,L,x,1,x,2,a,0,b,0,L,f(x,2,)f(x,1,),，取,a,1,=a,0,b,1,=x,1,x,1,=x,2,x,2,=b,1,-,(,b,1,-a,1,),a,1,b,1,x,1,x,2,f(x,2,),f(x,1,),，取,a,1,=x,2,b,1,=b,0,x,1,=a,1,+,(,b,1,-a,1,),x,2,=x,1,a,1,b,1,x,1,x,2,计算,n,个点后，总缩短率为,E,n,=,n-1,，,可得试点数,n,。,二、黄金分割法(0.618法)：是一种常用的消去法 1、原理,9,3,、计算步骤：求函数,f(x),的极值点,第一步：取初始区间,a,0,b,0,x,1,x,2,a,0,b,0,若求,f(x),的极小值点，则,f(x,2,)f(x,1,),，取,a,1,=a,0,b,1,=x,1,x,1,=x,2,x,2,=b,1,-,(,b,1,-a,1,),f(x,2,),f(x,1,),，取,a,1,=x,2,b,1,=b,0,x,1,=a,1,+,(,b,1,-a,1,),x,2,=x,1,a,1,b,1,x,1,x,2,a,1,b,1,x,1,x,2,若求,f(x),的极大值点，则,f(x,2,)f(x,1,),，取,a,1,=a,0,b,1,=x,1,x,1,=x,2,x,2,=b,1,-,(,b,1,-a,1,),f(x,2,),f(x,1,),，取,a,1,=x,2,b,1,=b,0,x,1,=a,1,+,(,b,1,-a,1,),x,2,=x,1,第二步：求区间的缩短率,3、计算步骤：求函数f(x)的极值点 第一步：取初始区间,10,例 求解,f(x)=-18x,2,+72x+28,的极大值点，,0.1,，起始搜索区间为,0,3,解：用间接法：令,f,(x)=-36x+72=0,，得驻点,x=2,又因为,f,(x)=-36,0,，故,x=2,为,f(x),的极大值点，,f,max,=100,用直接法中的黄金分割法：令,n-1,=,，得,n=1+(lg,)/,(lg,)5.78442,约,6,步即可，计算结果见下表：,k,a,k,b,k,f(a,k,),f(b,k,),p,k,=,b,k,-a,k,p,k,/p,0,x,1,k,=,a,k,+,p,k,x,2,k,=,b,k,-,p,k,f(,x,2,k,),f(,x,1,k,),0,0,3,28,82,3,1,1.854,1.146,86.9,99.62,f(x),x,o,3,x,1,x,2,1,1.146,3,86.9,82,1.854,0.618,2.292,1.854,99.62,98.46,2,1.146,2.292,86.9,98.46,1.146,0.382,1.854,1.584,96.89,99.62,3,1.584,2.292,96.89,98.46,0.708,0.236,2.022,1.854,99.62,99.99,4,1.854,2.292,99.62,98.46,0.438,0.146,2.125,2.022,99.99,98.72,5,1.854,2.125,99.62,99.72,0.271,0.0903,例 求解 f(x)=-18x2+72x+28 的极大值点，,11,9.3,无约束条件下多变量函数寻优,一、爬山法原理：,通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。,由以下二部分组成：,选定搜索方向；,在选定的方向上爬山搜索。,二、变量轮换法,(,或降维法,):,选择与坐标轴平行的方向为搜索方向,设,S=f(X)=f(x,1,x,2,x,n,),，极值点存在的区间为,x,1,*,a,1,b,1,，,x,2,*,a,2,b,2,，,，,x,n,*,a,n,b,n,1,、原理：从起点,X,(0),出发，沿平行于,x,1,轴的方向,P,(1),进行一维搜索，,求得,f(X),在该方向,P(1),上近似极值点,X,(1),；,从点,X,(1),出发，沿平行于,x,2,轴的方向,P,(2),进行一维搜索，,求得,f(X),在该方向,P(2),上近似极值点,X,(2),；,从点,X,(2),出发，照此交替进行下去，直至满足给定的精度,为止,|f(X,(k),),-f(X,(k-1),)|,或,|S,(k),-S,(k-1),|,9.3 无约束条件下多变量函数寻优二、变量轮换法(或降维法),12,2,、算法步骤：,设,S=f(X)=f(x,1,x,2,),，极值点存在的区间为,x,1,*,a,1,b,1,，,x,2,*,a,2,b,2,第一步：从,X,(0),=(x,1,(0),x,2,(0),),T,出发,先固定,x,1,=x,1,(0),:,求以,x,2,为单变量的目标函数的极值点，,得,X,(1),=(x,1,(0),x,2,(1),),T,，,S,(1),=f(X,(1),),再固定,x,2,=x,2,(1),:,求以,x,1,为单变量的目标函数的极值点，,得,X,(2),=(x,1,(2),x,2,(1),),T,，,S,(2),=f(X,(2),),此时,S,(2),优于,S,(1),，且搜索区间缩短为,x,1,*,x,1,(2),b,1,，,x,2,*,x,2,(1),b,2,第二步：如此交替搜索，直至满足给定精度,为止,|f(X,(k),),-f(X,(k-1),)|,或,|S,(k),-S,(k-1),|,o,x,1,X,(0),X,(1),X,(2),X,(3),X,(4),x,2,2、算法步骤：ox1X(0)X(1)X(2)X,13,例 求,S=f(x)=x,1,2,+x,2,2,-x,1,x,2,-10 x,1,-4x,2,+60,的极小值点，,=0.01,解：设起始点,X,(0),=(0,0),T,，用变量轮换法,计算：,先固定,x,1,=x,1,(0),=0:,则,f(0,x,2,)=x,2,2,-4x,2,+60,，寻优得,x,2,(1),=2,于是,X,(1),=(x,1,(0),x,2,(1),),T,=(0,2),T,，,S,(1),=f(X,(1),)=56,再固定,x,2,=x,2,(1),=2:,则,f(x,1,2)=x,1,2,-12x,1,+56,，,寻优得,x,1,(2),=6,于是,X,(2),=(x,1,(2),x,2,(1),),T,=(6,2),T,，,S,(2),=f(X,(2),)=20,如此交替搜索，直至满足给定精度,=0.01,为止,|f(X,(k),),