非线性规划课件-PPT.pptx

非线性规划课件非线性规划课件 2 2、多元函数、多元函数 y=f(X)=f(xy=f(X)=f(x1 1,x,x2 2,x,xn n):在在 X X0 0 附近作泰勒展开附近作泰勒展开,得得 极值点存在得必要条件极值点存在得必要条件:f(x)=0f(x)=0,此时求出得此时求出得 x x0 0 为驻点。为驻点。极值点存在得充分条件极值点存在得充分条件:四、四、凸函数与凹函数凸函数与凹函数:1 1、定义、定义:y=f(x)y=f(x)就是就是E En n中某凸集中某凸集R R上得函数上得函数 对对0,10,1及及 X X1 1、X X2 2 R R,且且 X X1 1XX2 2 若若ff X X1 1+(1-+(1-)X)X2 2 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2),则则f(x)f(x)为为R R上得凸函数。上得凸函数。若若ff X X1 1+(1-+(1-)X)X2 2 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2),则则f(x)f(x)为为R R上得严格凸函数。上得严格凸函数。对对0,10,1及及 X X1 1、X X2 2 R R,且且 X X1 1XX2 2 若若ff X X1 1+(1-+(1-)X)X2 2 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2),则则f(x)f(x)为为R R上得上得凹凹函数。函数。若若ff X X1 1+(1-+(1-)X)X2 2 f(Xf(X1 1)+(1-)+(1-)f(X)f(X2 2),则则f(x)f(x)为为R R上得严格上得严格凹凹函数。函数。y yx xo oX X1 1X X2 2 X X1 1+(1-+(1-)X)X2 2y=f(x)y=f(x)凸函数凸函数y yx xo oX X1 1X X2 2 X X1 1+(1-+(1-)X)X2 2y=f(x)y=f(x)凹凹函数函数y yx xo oX X1 1X X2 2y=f(x)y=f(x)非凸、非非凸、非凹凹函数函数 2 2、性质、性质:f fi i(X)(X)为凸集为凸集R R上得凸函数上得凸函数,则对则对 k ki i00,i=1,2,i=1,2,m,m,有有 k k1 1f f1 1(X)+k(X)+k2 2f f2 2(X)+(X)+k+km mf fm m(X)(X)仍为仍为凸函数。凸函数。3 3、凸函数得判定、凸函数得判定:f(X)f(X)定义在凸集定义在凸集R R上上,若若f(X)f(X)有连续得二阶导数有连续得二阶导数,则则f(X)f(X)为凸函数为凸函数 H H为半正定。为半正定。f(X)f(X)为严格凸函数为严格凸函数 H H为正定。为正定。4 4、凸函数得局部极值与全局极值得关系凸函数得局部极值与全局极值得关系 若目标函数在可行域中为若目标函数在可行域中为凸函数凸函数则其极值点为最优值点则其极值点为最优值点;若目标函数在可行域中为若目标函数在可行域中为严格凸函数严格凸函数,则其极值点为唯一最优值点。则其极值点为唯一最优值点。五、五、凸规划凸规划:1 1、定义、定义:非线性规划非线性规划(p)(p)Min f(X)Min f(X)g gi i(X)0(X)0 ，i=1,2,i=1,2,m,m 若若 f(X)f(X),-g-gi i(X)(X)为凸函数为凸函数,则则(p)(p)称为凸规划。称为凸规划。2 2、性质、性质:(p)(p)得可行解集得可行解集 R R 就是凸集就是凸集;最优解集最优解集 R R*也就是凸集。也就是凸集。(p)(p)得任何局部最优解均就是全局最优解。得任何局部最优解均就是全局最优解。若若f(X)f(X)为严格凸函数时为严格凸函数时,其最优解必唯一。其最优解必唯一。特例特例:线性函数既就是凸函数又就是凹函数线性函数既就是凸函数又就是凹函数,故故 L L、P P、为凸规划。为凸规划。六、六、寻优方法概述寻优方法概述:1 1、N N、L L、P P、问题分类问题分类 无约束条件得无约束条件得NLPNLP问题。问题。有约束条件得有约束条件得NLPNLP问题。问题。2 2、寻优方法寻优方法 间接法间接法(解析法解析法):适应于目标函数有简单明确得数学表达式。适应于目标函数有简单明确得数学表达式。直接法直接法(搜索法搜索法):目标函数复杂或无明确得数学表达式。目标函数复杂或无明确得数学表达式。a a、消去法消去法(对单变量函数有效对单变量函数有效):不断消去部分搜索区间不断消去部分搜索区间,逐步缩小极值点存在得范围。逐步缩小极值点存在得范围。b b、爬山法爬山法(对多变量函数有效对多变量函数有效):根据已求得得目标值根据已求得得目标值,判断前进方向判断前进方向,逐步改善目标值。逐步改善目标值。9 9、2 2 无约束条件下单变量函数寻优无约束条件下单变量函数寻优一、消去法原理一、消去法原理:逐步缩小搜索区间逐步缩小搜索区间,直至极值点存在得区间达到允许得误差范围为止。直至极值点存在得区间达到允许得误差范围为止。设要寻求设要寻求f(X)f(X)得极小值点为得极小值点为 X X*,起始搜索区间为起始搜索区间为aa0 0,b,b0 0。x x1 1、x x2 2 aa0 0,b,b0 0,且且x x2 2x x1 1,计算计算 f(xf(x1 1)与与f(xf(x2 2),并且比较结果并且比较结果:f(x)f(x)x xo oa a0 0b b0 0X X*x x1 1,x,x2 2 在在x x*的右侧的右侧x x1 1x x2 2f(x)f(x)x xo oa a0 0b b0 0X X*x x1 1,x,x2 2 在在x x*的左侧的左侧x x1 1x x2 2f(x)f(x)x xo oa a0 0b b0 0X X*x x1 1,x,x2 2 在在x x*的两侧的两侧x x1 1x x2 2 x x1 1,x,x2 2 均在均在x x*得右侧得右侧,f(xf(x2 2)f(xf(x1 1),去掉去掉xx1 1,b,b0 0,此时此时x x*aa0 0,x,x1 1 x x1 1,x,x2 2 均在均在x x*得左侧得左侧,f(xf(x2 2)f(xf(x1 1),去掉去掉aa0 0,x,x2 2,此时此时x x*xx2 2,b,b0 0 x x1 1,x,x2 2 均在均在x x*得两侧得两侧,f(xf(x2 2)f(xf(x1 1):a a、去掉去掉xx1 1,b,b0 0,此时此时x x*aa0 0,x,x1 1 b b、去掉去掉aa0 0,x,x2 2,此时此时x x*xx2 2,b,b0 0 二、黄金分割法二、黄金分割法(0(0、618618法法):就是一种常用得消去法就是一种常用得消去法 与对分法、与对分法、FibonacciFibonacci法比较法比较,具有计算次数少具有计算次数少,过程简单得特点。过程简单得特点。1 1、原理、原理:LxL-xLx1x2 2 2、取点法则、取点法则:Lx1x2a0b0L f(x f(x2 2)f(x)f(x1 1),取取aa1 1=a=a0 0,b,b1 1=x=x1 1 x x1 1=x=x2 2 x x2 2=b=b1 1-(b b1 1-a a1 1)a1b1x1x2 f(x f(x2 2)f(xf(x1 1),取取aa1 1=x=x2 2,b,b1 1=b=b0 0 x x1 1=a=a1 1+(b b1 1-a a1 1)x x2 2=x=x1 1 a1b1x1x2计算计算n n个点后个点后,总缩短率为总缩短率为 E En n=n-1n-1,可得试点数可得试点数n n。3 3、计算步骤、计算步骤:求函数求函数f(x)f(x)得极值点得极值点 第一步第一步:取初始区间取初始区间aa0 0,b,b0 0 x1x2a0b0 若求若求f(x)f(x)得极小值点得极小值点,则则 f(xf(x2 2)f(x)f(x1 1),取取aa1 1=a=a0 0,b,b1 1=x=x1 1 x x1 1=x=x2 2 x x2 2=b=b1 1-(b b1 1-a-a1 1)f(x f(x2 2)f(xf(x1 1),取取aa1 1=x=x2 2,b,b1 1=b=b0 0 x x1 1=a=a1 1+(b b1 1-a-a1 1)x x2 2=x=x1 1 a1b1x1x2a1b1x1x2 若求若求f(x)f(x)得极大值点得极大值点,则则 f(xf(x2 2)f(x)f(x1 1),取取aa1 1=a=a0 0,b,b1 1=x=x1 1 x x1 1=x=x2 2 x x2 2=b=b1 1-(b b1 1-a-a1 1)f(x f(x2 2)f(xf(x1 1),取取aa1 1=x=x2 2,b,b1 1=b=b0 0 x x1 1=a=a1 1+(b b1 1-a-a1 1)x x2 2=x=x1 1 第二步第二步:求区间得缩短率求区间得缩短率例例 求解求解 f(x)=-18xf(x)=-18x2 2+72x+28+72x+28 得极大值点得极大值点,0 0、1 1,起始搜索区间为起始搜索区间为0,30,3解解:用间接法用间接法:令令 f f(x)=-36x+72=0(x)=-36x+72=0,得驻点得驻点 x=2x=2 又因为又因为f f(x)=-36(x)=-360 0,故故 x=2 x=2 为为f(x)f(x)得极大值点得极大值点,f fmaxmax=100=100 用直接法中得黄金分割法用直接法中得黄金分割法:令令 n-1n-1=,得得n=1+(lgn=1+(lg)/)/(lg(lg)5)5、7844278442 约约6 6步即可步即可,计算结果见下表计算结果见下表:ka ak kb bk kf(ak)f(bk)pk=bk-akpk/p0 x x1 1k k=ak+pkx x2 2k k=bk-pkf(x x2 2k k)f(x x1 1k k)0032882311、8541、14686、999、62f(x)f(x)x xo o3 3x x1 1x x2 211、146386、9821、8540、6182、2921、85499、62 98、4621、1462、29286、998、461、1460、3821、8541、58496、8999、6231、5842、29296、8998、460、7080、2362、0221、85499、62 99、9941、8542、29299、6298、460、4380、1462、1252、02299、99 98、7251、8542、12599、6299、720、2710、09039 9、3 3 无约束条件下多变量函数寻优无约束条件下多变量函数寻优一、爬山法原理一、爬山法原理:通过点得直接移动通过点得直接移动,逐步改善目标函数取值逐步改善目标函数取值,直至达到极值点为止。直至达到极值点为止。由以下二部分组成由以下二部分组成:选定搜索方向选定搜索方向;在选定得方向上爬山搜索。在选定得方向上爬山搜索。二、变量轮换法二、变量轮换法(或降维法或降维法):):选择与坐标轴平行得方向为搜索方向选择与坐标轴平行得方向为搜索方向 设设 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n),极值点存在得区间为极值点存在得区间为 x x1 1*aa1 1,b,b1 1,x x2 2*aa2 2,b,b2 2,x xn n*aan n,b,bn n 1 1、原理、原理:从起点从起点 X X(0)(0)出发出发,沿平行于沿平行于 x x1 1 轴得方向轴得方向P P(1)(1)进行一维搜索进行一维搜索,求得求得 f(X)f(X)在该方向在该方向P(1)P(1)上近似极值点上近似极值点 X X(1)(1);从点从点 X X(1)(1)出发出发,沿平行于沿平行于 x x2 2 轴得方向轴得方向P P(2)(2)进行一维搜索进行一维搜索,求得求得 f(X)f(X)在该方向在该方向P(2)P(2)上近似极值点上近似极值点 X X(2)(2);从点从点 X X(2)(2)出发出发,照此交替进行下去照此交替进行下去,直至满足给定得精度直至满足给定得精度 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|大家学习辛苦了，还是要坚持继续保持安静继续保持安静继续保持安静继续保持安静 2 2、算法步骤、算法步骤:设设 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2),极值点存在得区间为极值点存在得区间为x x1 1*aa1 1,b,b1 1,x x2 2*aa2 2,b,b2 2 第一步第一步:从从 X X(0)(0)=(x=(x1 1(0)(0),x,x2 2(0)(0)T T出发出发 先固定先固定x x1 1=x=x1 1(0)(0):求以求以x x2 2为单变量得目标函数得极值点为单变量得目标函数得极值点,得得 X X(1)(1)=x=(x1 1(0)(0),x,x2 2(1)(1)T T ,S S(1)(1)=f(X=f(X(1)(1)再固定再固定x x2 2=x=x2 2(1)(1):求以求以x x1 1为单变量得目标函数得极值点为单变量得目标函数得极值点,得得 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(1)T T ,S S(2)(2)=f(X=f(X(2)(2)此时此时S S(2)(2)优于优于S S(1)(1),且搜索区间缩短为且搜索区间缩短为x x1 1*x x1 1(2)(2),b,b1 1,x x2 2*x x2 2(1)(1),b,b2 2 第二步第二步:如此交替搜索如此交替搜索,直至满足给定精度直至满足给定精度 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x-10 x1 1-4x-4x2 2+60+60 得极小值点得极小值点,=0=0、0101解解:设起始点设起始点 X X(0)(0)=(0,0)=(0,0)T T,用变量轮换法用变量轮换法计算计算:先固定先固定x x1 1=x=x1 1(0)(0)=0:=0:则则 f(0,x2)=x22-4x2+60,寻优得寻优得 x x2 2(1)(1)=2=2 于就是于就是 X X(1)(1)=(x=(x1 1(0)(0),x,x2 2(1)(1)T T=(0,2)=(0,2)T T ,S S(1)(1)=f(X=f(X(1)(1)=56)=56 再固定再固定x x2 2=x=x2 2(1)(1)=2:=2:则则 f(x1,2)=x12-12x1+56,寻优得寻优得 x x1 1(2)(2)=6=6 于就是于就是 X X(2)(2)=(x=(x1 1(2)(2),x,x2 2(1)(1)T T=(62)=(6,2)T T ,S S(2)(2)=f(X=f(X(2)(2)=20)=20 如此交替搜索如此交替搜索,直至满足给定精度直至满足给定精度 =0=0、01 01 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|0 0、01 01 或或|S|S(k)(k)-S-S(k-1)(k-1)|0 0、0101 最后得极小点最后得极小点 X X*=(8,6)=(8,6)T T,f(Xf(X*)=8)=8o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2计算结果见下表计算结果见下表:k固定得固定得x xi i单变量得目标函数单变量得目标函数f(xj)求得极点求得极点xj目标值目标值S S(k)(k)|S|S(k)(k)-S S(k-1)(k-1)|12345678x x1 1=x=x1 1(0)(0)=0=0 x x2 2=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=x=x1 1(4)(4)=7=7、5 5x x2 2=x=x2 2(5)(5)=5=5、7575x x1 1=x=x1 1(6)(6)=7=7、8888x x2 2=x=x2 2(7)(7)=5=5、9494f(0,x2)=x22-4x2+60f(x1,2)=x12-12x1+56f(6,x2)=x22-10 x2+36f(x1,5)=x12-15x1+65f(7、5,x2)=x22 11、5x2+41、25f(x1,5、75)=x12 15、75x1+70、06f(7、88,x2)=x22 11、88x2+43、27f(x1,5、94)=x12 15、94x1+71、50 x x2 2=x=x2 2(1)(1)=2=2x x1 1=x=x1 1(2)(2)=6=6x x2 2=x=x2 2(3)(3)=5=5x x1 1=x=x1 1(4)(4)=7=7、5 5x x2 2=x=x2 2(5)(5)=5=5、7575x x1 1=x=x1 1(6)(6)=7=7、875875x x2 2=x=x2 2(7)(7)=5=5、9494x x1 1=x=x1 1(8)(8)=7=7、97975620118、758、18758、04698、01178、00293692、250、56250、14060、03520、0088o ox x1 1X X(0)(0)X X(1)(1)X X(2)(2)X X(3)(3)X X(4)(4)x x2 2缺点缺点:很大程度上取决于目标函数性质。很大程度上取决于目标函数性质。目标函数等高线得性质很重要。目标函数等高线得性质很重要。道路迂回曲折道路迂回曲折,多次变换方向多次变换方向,在极点附近在极点附近,目标值改进更小目标值改进更小,收敛速度慢。故不就是一个有利方向。收敛速度慢。故不就是一个有利方向。三、一阶梯度法三、一阶梯度法(最速下降或上升法最速下降或上升法):):选择负梯度方向为搜索方向选择负梯度方向为搜索方向 设求设求 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)得极值点。得极值点。1 1、原理、原理:从起点从起点 X X(0)(0)出发出发,沿某个有利方向沿某个有利方向 P P(0)(0)进行一维搜索进行一维搜索,求得求得 f(X)f(X)在在 P P(0)(0)方向近似极小点方向近似极小点 X X(1)(1);从点从点 X X(1)(1)出发出发,沿某个新有利方向沿某个新有利方向 P P(1)(1)进行一维搜索进行一维搜索,求得求得 f(X)f(X)在在 P P(1)(1)方向近似极小点方向近似极小点 X X(2)(2);从点从点 X X(2)(2)出发出发,照此进行下去照此进行下去,直至满足给定得精度直至满足给定得精度 为止为止|f(X|f(X(k)(k)-f(X-f(X(k-1)(k-1)|)|或或|S|S(k)(k)-S-S(k-1)(k-1)|2 2、算法步骤、算法步骤:设求设求 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2)得极值点。得极值点。第一步第一步:从给定起点从给定起点 X X(0)(0)出发出发 第二步第二步:从点从点 X X(1)(1)出发出发,照此进行下去照此进行下去,直至满足给定得精度直至满足给定得精度 为止为止|f(X|f(X(k+1)(k+1)-f(X-f(X(k)(k)|)|或或|G|G(k)(k)|例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x-10 x1 1-4x-4x2 2+60+60 得极小值点得极小值点,=0=0、1 1解解:从点从点 X X(1)(1)出发出发,照此进行下去照此进行下去,直至满足给定得精度直至满足给定得精度 =0=0、1 1 为止为止|f(X|f(X(k+1)(k+1)-f(X-f(X(k)(k)|)|0 0、1 1 或或|G|G(k)(k)|0 0、1 1 计算结果见下表计算结果见下表:缺点缺点:搜索效果比变量轮换法快搜索效果比变量轮换法快,但愈接近极值但愈接近极值 点点,步长愈小步长愈小,目标值改进愈小。目标值改进愈小。当遇到强交互作用时当遇到强交互作用时,不就是有效得方法不就是有效得方法;当遇到山脊时当遇到山脊时,会慢慢爬行。会慢慢爬行。在远离极点时在远离极点时,收敛速度较快收敛速度较快;在极点附近在极点附近,收敛速度不快。收敛速度不快。k01234507、636、817、957、827、9903、055、115、565、875、93-102、21-1、490、33-0、220、05-4-5、53-0、60-0、82-0、09-0、1210、775、591、600、890、240、13-0、930、37-0、930、37-0、930、37-0、37-0、93-0、37-0、93-0、37-0、9288、222、211、220、330、180、056015、749、158、178、038、003744、266、590、980、140、026o ox x1 1x x(0)(0)x x(1)(1)x x(2)(2)X X(3)(3)x x2 2四、共轭梯度法四、共轭梯度法:选择共轭方向为搜索方向选择共轭方向为搜索方向 问题得提出问题得提出:在极值点附近在极值点附近,如何加快收敛速度如何加快收敛速度,须对函数在极值点附近得性质进行研究。须对函数在极值点附近得性质进行研究。设有设有n n维目标函数维目标函数 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n),),在极值点在极值点X X*附近展开成泰勒级数附近展开成泰勒级数:特别特别:对二元二次函数对二元二次函数,可证明可证明:在极值点附近在极值点附近,其等高线可近似视为同心其等高线可近似视为同心 椭园族椭园族,而同心椭园族得任意两根平行切线得切点连线必通过椭园中心。而同心椭园族得任意两根平行切线得切点连线必通过椭园中心。o ox x1 1X X(0)(0)P P(0)(0)X X(0)(0)X X(2)(2)X X(1)(1)x x2 2P P(0)(0)P P(1)(1)=X=X(2)(2)-X-X(1)(1)P P(1)(1)与与P P(0)(0)共轭共轭故故:在极值点附近在极值点附近,沿搜索方向沿搜索方向P P(0)(0)上巳得到一个上巳得到一个 切点切点X X(1)(1),则只要得出通过极值点得连线方向则只要得出通过极值点得连线方向 P P(1)(1),在此方向上寻优在此方向上寻优,可一步直达极值点。可一步直达极值点。而这个连线方向而这个连线方向P P(1)(1)就是上一次搜索方向就是上一次搜索方向P P(0)(0)得得 共轭方向。共轭方向共轭方向得定义共轭方向得定义:1 1、定义、定义:设设 X,Y X,Y 就是就是n n维向量空间维向量空间E En n中两个向量中两个向量,A A 为为nnnn对称正定矩阵对称正定矩阵,若若 X XT TAY=0 AY=0,则称向量则称向量X X与与Y Y对于矩阵对于矩阵A A共轭。共轭。特例特例:若若 A=IA=I,得得 X XT TY=0Y=0,则称向量则称向量X X与与Y Y正交。正交。2 2、几何意义、几何意义:共轭方向就是通过极值点得方向。共轭方向就是通过极值点得方向。寻优原理寻优原理:设设n n元函数元函数 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n),),在极值点在极值点X X*附近可用一个二次函数逼近附近可用一个二次函数逼近其中其中 H H 为为nnnn对称正定矩阵对称正定矩阵特别特别:对二元二次函数对二元二次函数 S=f(X)=f(xS=f(X)=f(x1 1,x x2 2)从某点从某点X X(0)(0)出发出发,以以P P(0)(0)方向搜索方向搜索,使使f(X)f(X)达到极小值点达到极小值点X X(1)(1),则则:X:X(1)(1)必为该点处等高线得切点必为该点处等高线得切点,P,P(0)(0)为切线方向为切线方向,且点且点X X(1)(1)得梯度方向得梯度方向 f(Xf(X(1)(1)为该等高线得法线方向为该等高线得法线方向,这两个方向正交。这两个方向正交。从另一点从另一点X X(0)(0)出发出发,仍以仍以P P(0)(0)方向搜索方向搜索,使使f(X)f(X)达到另一个极小值点达到另一个极小值点X X(2)(2),则则:X:X(2)(2)也必为该点处等高线得切点也必为该点处等高线得切点,P,P(0)(0)为切线方向为切线方向,且点且点X X(2)(2)得梯度方向得梯度方向 f(Xf(X(2)(2)为该等高线得法线方向为该等高线得法线方向,这两个方向正交。这两个方向正交。o ox x1 1X X(0)(0)P P(0)(0)X X(0)(0)X X(2)(2)X X(1)(1)x x2 2P P(0)(0)P P(1)(1)=X=X(2)(2)-X-X(1)(1)P P(1)(1)与与P P(0)(0)共轭共轭故故:对二元二次函数对二元二次函数,只须搜索两个方向只须搜索两个方向P P(0)(0)与与P P(1)(1)就就 可达到极值点可达到极值点 X X*。一般一般:对对n n元二次函数元二次函数,可用不超过可用不超过n n次搜索就可达到次搜索就可达到 极值点极值点 X X*。而而n n元非二次函数在极值点附近可用二次函数逼近。元非二次函数在极值点附近可用二次函数逼近。寻优步骤寻优步骤:例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x-10 x1 1-4x-4x2 2+60+60 得极小值点。得极小值点。解解 o ox x1 1X X(0)(0)P P(0)(0)X X(1)(1)x x2 2 即即o ox x1 1X X(0)(0)P P(0)(0)X X(1)(1)x x2 2P P(1)(1)与与P P(0)(0)共轭共轭X X(2)(2)对二元二次函数对二元二次函数,只须两次搜索就可达到极值点只须两次搜索就可达到极值点 X X*,一般一般:对对n n元二次函数元二次函数,可用不超过可用不超过n n次搜索就可达到极值点次搜索就可达到极值点 X X*。而而n n元非二次函数在极值点附近可用二次函数逼近。元非二次函数在极值点附近可用二次函数逼近。适用于一般目标函数得共轭梯度法适用于一般目标函数得共轭梯度法:1 1、共轭方向得计算问题、共轭方向得计算问题:须用到目标函数得海赛矩阵须用到目标函数得海赛矩阵H(H(二阶偏导数矩阵二阶偏导数矩阵),若目标函数为二次函数时若目标函数为二次函数时,H H 容易求出容易求出;若目标函数为高次或高维函数时若目标函数为高次或高维函数时,H H 难以求出难以求出,此时共轭方向难以求出。此时共轭方向难以求出。2 2、共轭方向得计算方法、共轭方向得计算方法:F-R F-R 法法,由由FletcherFletcher与与ReevesReeves提出提出,可避免海赛矩阵可避免海赛矩阵 H H 得计算得计算,方便地确定共轭方向方便地确定共轭方向,简单有效。简单有效。3 3、搜索过程、搜索过程:从从X X(0)(0)出发出发:从从X X(1)(1)出发出发:从从X X(2)(2)出发出发:4 4、搜索方法、搜索方法:若目标函数为若目标函数为n n元二次函数元二次函数,则理论上最多经则理论上最多经 n n 次迭代可达极小点次迭代可达极小点,实际由于舍入误差实际由于舍入误差,须须n n次以上得迭代。次以上得迭代。若目标函数为若目标函数为n n元非二次函数元非二次函数,但共轭方向只有但共轭方向只有n n个个,迭代迭代n n次以后应次以后应 重新开始迭代重新开始迭代,减少误差积累。减少误差积累。一般一般,在开始阶段在开始阶段(二次型较弱二次型较弱)用一阶梯度法用一阶梯度法,接近极点接近极点(二次型较强二次型较强)用共轭梯度法。用共轭梯度法。一般有一般有:例例 求求 S=f(x)=xS=f(x)=x1 12 2+x+x2 22 2-x-x1 1x x2 2-10 x-10 x1 1-4x-4x2 2+60+60 得极小值点得极小值点。解解:9 9、4 4 有约束条件下多变量函数寻优有约束条件下多变量函数寻优一、具有等式约束得极值问题一、具有等式约束得极值问题:1 1、消元法、消元法:n n元非线性规划元非线性规划 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)s s、t t、g gk k(X)=0,k=1,2,(X)=0,k=1,2,m,mn,m,mn 若可从若可从m m个个s s、t t、中解出中解出m m个变量个变量x xi i=h(x=h(xm+1m+1,x,xm+2m+2,x,xm m),i=1,2,),i=1,2,m,m,代入目标函数中消去代入目标函数中消去m m个变量个变量,则问题变为一个求则问题变为一个求n-mn-m个变量函数得个变量函数得 无约束条件得极值问题。无约束条件得极值问题。例：求解例：求解 MinMin s.t.s.t.2 2、拉格朗日、拉格朗日(Lagrangian)(Lagrangian)乘子法乘子法:n n元非线性规划元非线性规划 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)s s、t t、g gk k(X)=0,k=1,2,(X)=0,k=1,2,m,m 例：求解例：求解 MinMin s.t.s.t.则则 L(X,L(X,)有极值得必要条件为有极值得必要条件为:求出得解就就是求出得解就就是f(X)f(X)得驻点。得驻点。令令 其中其中,拉格朗日乘子拉格朗日乘子 k k得经济意义得经济意义:影子价格影子价格 -单位资源得目标增量单位资源得目标增量 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)s s、t t、g gk k(X)=b(X)=bk k,k=1,2,k=1,2,m,m 知知 k k 就是约束式就是约束式 g gk k 每变化一个单位每变化一个单位,引起目标引起目标 f f 值得变化率。值得变化率。若目标若目标 f f 为效用函数极大化为效用函数极大化,b b 为预算约束为预算约束,则则 *表示增加一元预算收入表示增加一元预算收入,可使最大效用增加得值。可使最大效用增加得值。若目标若目标 f f 为费用函数极小化为费用函数极小化,b b 为产出水平为产出水平,则则 *表示降低一元产出表示降低一元产出,可使最大费用增加得值可使最大费用增加得值 -影子费用。影子费用。3 3、罚函数、罚函数(代价函数代价函数)法法对对 n n 元非线性规划问题元非线性规划问题 S=f(X)=f(xS=f(X)=f(x1 1,x,x2 2,x,xn n)s s、t t、g gk k(X)=0,k=1,2,(X)=0,k=1,2,m,m R(X,p R(X,pk k)有极值得必要条件为有极值得必要条件为:求出得解就就是求出得解就就是f(X)f(X)得驻点。得驻点。当当s s、t t、不满足时不满足时,p,pk k越大越大,则则R R值越大值越大,此时罚项就是一种惩罚。此时罚项就是一种惩罚。当当s s、t t、满足时满足时,不论不论p pk k多大多大(一般取一般取),R(X,p),R(X,pk k)=f(X),)=f(X),此时罚项无效。此时罚项无效。例：求解例：求解 MinMin s.t.s.t.令令 得得 二、具有不等式约束得极值问题二、具有不等式约束得极值问题:1 1、拉格朗日乘子法、拉格朗日乘子法:引入松弛变量引入松弛变量,将不等式约束化为等式约束。将不等式约束化为等式约束。例：求解例：求解 MinMin s.t.s.t.s.t.s.t.令令 2 2、库恩塔克、库恩塔克(Kuhn(KuhnTuckers)Tuckers)条件法条件法:适用范围适用范围:含有等式与不等式约束及变量非负得一般非线性规划。含有等式与不等式约束及变量非负得一般非线性规划。库塔条件库塔条件:非线性规划非线性规划 s.t.s.t.MinMin注注:库塔条件就是确定库塔条件就是确定 X X*为极值点得为极值点得 必要条件必要条件,但不就是充分条件。但不就是充分条件。若为凸规划若为凸规划,则为充分必要条件。则为充分必要条件。B BA A局部极小局部极小全局极小全局极小x xL L例：求解例：求解 MinMins.t.s.t.由库由库塔条件有塔条件有:1 1、求出驻点求出驻点:则由则由得得 x1=1,x2=2,这与这与矛盾矛盾,舍去舍去;则由则由得得 x1=9/5,x2=4/5,代入代入得得 1=22/25,2=-24/250,矛盾矛盾,舍去舍去;则由则由,得得 x1=13/17,x2=18/17,1=0,2=4/17,用用校验正确校验正确,得得驻点驻点 X*=(13/17,18/17)T;则由则由,得得 x1=9/13,x2=20/13,1=2/13,2=0,用用校验不正确校验不正确,舍去。舍去。2 2、验证规划得凸性验证规划得凸性:所以原规划为凸规划所以原规划为凸规划,从而从而 X*=(13/17,18/17)T 为最小值点为最小值点,此时此时 Z*=-1173/578。