清华大学运筹学5非线性规划.ppt

第六章第六章非线性规划非线性规划第一节第一节基本概念基本概念第三节第三节无约束极值问题无约束极值问题第四节第四节约束极值问题约束极值问题1.第一节第一节基本概念基本概念一、非线性规划数学模型一、非线性规划数学模型2.非线性规划数学模型一般形式：非线性规划数学模型一般形式：Minf(X)s.t.hi(X)=0 (i=1,2,m)gj(X)0，(j=1,2,l)X=(x1,x2,xn)T是是n维欧式空间维欧式空间En中的点，目中的点，目标函数标函数f(X)，约束函数，约束函数hi(X)和和gj(X)是是X实函数。实函数。有时，非线性规划数学模型写成：有时，非线性规划数学模型写成：Minf(X)s.t.gj(X)0，(j=1,2,l)若某若某gj(X)=0，可以，可以gj(X)0和和-gj(X)0代替之。代替之。3.n4.A(0,5)BCD(4,1)1O125x1x2345.n6.n7.n8.n9.AT=A，即，即aji=aij。若。若aij均为实数，则称均为实数，则称f(X)=XTAX为实二次型。为实二次型。A与二次型一一对应。与二次型一一对应。(1)若对于非零若对于非零X，实二次型总有，实二次型总有XTAX0，则称，则称为正定的；为正定的；(2)若对于非零若对于非零X，实二次型总有，实二次型总有XTAX0，而对另一些非，而对另一些非零零X，XTAX0a110，|a11 a12|a11 a12 a13|a21 a22|0|a21 a22 a23|0|a31 a32 a33|a11 a12 a1n|a21 a22 a2n|.|0|.|.|an1 an2 ann|11.实二次型实二次型f(X)=XTAX为负定的充要条件是：为负定的充要条件是：a110|a21 a22 a23|0|.|.|an1 an2 ann|12.例例1判定如下二次型的性质。判定如下二次型的性质。-5 2 2 0 1 1A=2 -6 0 B=1 0 -3 2 0 -4 1 -3 0 矩阵矩阵A：-50|-5 2 2|2 -6|2-6 0|=-800|2 0-4|矩阵矩阵A为负定。为负定。矩阵矩阵B：b11=0，|0 1|=-1f(X(1)f(X(2)f(X(3)f(X(k)这就是下降迭代算法。这就是下降迭代算法。该算法一般格式与步骤：该算法一般格式与步骤：(1)选取初始选取初始X(0)，k:=0;(2)确定下降方向。若已到达的确定下降方向。若已到达的X(k)不是极小点，不是极小点，就确定一个方向就确定一个方向P(k)，使目标函数沿此方向能够，使目标函数沿此方向能够下降，但不要越出可行域。下降，但不要越出可行域。(3)确定步长。沿确定步长。沿P(k)前进一定距离（步长），到前进一定距离（步长），到达新点达新点X(k+1)。即在从。即在从X(k)出发的射线出发的射线X=X(k)+P(k)上上(0)，选择一个，选择一个k，到达新点，到达新点X(k+1)=X(k)+kP(k)，使得，使得38.f(X(k)f(X(k+1)=f(X(k)+kP(k)k是使是使f(X(k)+kP(k)=minf(X(k)+P(k)成立的成立的。(4)检查新点是否或接近极小点。若是，停。否则，检查新点是否或接近极小点。若是，停。否则，k:=k+1，返回，返回(2)继续迭代。继续迭代。已有不少办法确定搜索方向已有不少办法确定搜索方向P(k)。多数按使目标函数下快最快的原则确定步长，即多数按使目标函数下快最快的原则确定步长，即求解一维问题求解一维问题f(X(k)+kP(k)=minf(X(k)+P(k)，故，故称这一过程为（最优）一维搜索或线搜索。如此称这一过程为（最优）一维搜索或线搜索。如此确定的步长，称为最优步长。确定的步长，称为最优步长。39.n40.n41.42.n43.第三节第三节无约束极值问题无约束极值问题44.无约束极值问题表示无约束极值问题表示Minf(X)，XRc前文已指出，须用迭代法求解。迭代法有解析法前文已指出，须用迭代法求解。迭代法有解析法和直接法两类。和直接法两类。解析法要用到目标函数一阶和二阶导数。解析法要用到目标函数一阶和二阶导数。直接法不用，只用目标函数值。有些目标函数没直接法不用，只用目标函数值。有些目标函数没有导数，只能用直接法。有导数，只能用直接法。45.n46.n47.n48.n49.n50.n51.n52.n53.n54.55.例例9人工神经网络人工神经网络 模仿人脑神经网络，将具有识别、记忆功能模仿人脑神经网络，将具有识别、记忆功能的人工神经元以各种不同的方式连接成不同的网的人工神经元以各种不同的方式连接成不同的网络。用于计算、分类、模式识别、评价、预测、络。用于计算、分类、模式识别、评价、预测、控制、智能机器人、数据挖掘等领域。控制、智能机器人、数据挖掘等领域。1.人工神经元与感知机人工神经元与感知机(1)神经元感知功能神经元感知功能 人工神经元人工神经元 （感知机）（感知机）56.n57.n58.n59.n60.n61.n62.n63.先赋予先赋予w=(w1,w2,wm)T一个初始值，然一个初始值，然后逐步调整，使其逐步逼近极值点后逐步调整，使其逐步逼近极值点w*=(w*1,w*2,w*m)T，调整方向调整方向P=(p1,p2,pm)T，调整量，调整量是是P，步长，步长就是上面的就是上面的“学习系数学习系数”。当当P=-f(w)时，总误差时，总误差f(w)下降最快。下降最快。64.n65.n66.n67.n68.n69.n70.n71.n72.第四节第四节约束极值问题约束极值问题73.n74.n75.0Rcx1x21.0g1(X)=0g2(X)=0黑色方向不可行黑色方向不可行76.n77.n78.n79.n80.【例例】Min f(x)=-4x1-6x2+2x12+2x1x2+2x22 s.t.-x1-2x2+20，1x10，x20 x=(x1,x2)T=(1/2,3/4)T是否为是否为上上面问题的解？面问题的解？【解解】f(x)=(4x1+2x2-4，2x1+4x2-6)T g1(x)=(-1，-2)T g2(x)=(1，0)T g3(x)=(0，1)T81.记记x(0)=(1/2,3/4)Tg1(x(0)=-1/2-2(3/4)+2=0g2(x(0)=1-1/2=1/20g3(x(0)=3/40所以，在所以，在x(0)处，处，g1(x)是有效约束。是有效约束。f(x(0)=(-1/2，-2)T，g1(x(0)=(-1，-2)T，g2(x(0)=(1，0)T，g3(x(0)=(0，1)T82.x1x2x(0)不是解。不是解。因在因在 f(x(0)和和 g1(x(0)之间，可找到一个方向之间，可找到一个方向P，使得使得 f(x(0)TP0同时成立，即同时成立，即P同同 f(x(0)成钝角，而同成钝角，而同 g1(x(0)成锐角。成锐角。121P P f(x(0)g1(x(0)x(0)83.或者，令或者，令P=(p1，p2)T，下列不等式组有解：下列不等式组有解：f(x(0)TP=-p1/2-2p20只须令只须令p1=-1，p2=3/8即可，所以，即可，所以，x(0)=(1/2,3/4)T不是问题的解。不是问题的解。84.2.库恩塔克条件库恩塔克条件Kuhn-Tucker先讲几个预备性定理。先讲几个预备性定理。(1)Gordan引理引理 设设A1,A2,Al是是l个个n维向量，不维向量，不存在存在n维向量维向量P使使AjTP0 (j=1,2,l)成立的充要条件是，存在不全为零的非负实数成立的充要条件是，存在不全为零的非负实数1,2,l，使，使1A1+2A2+lAl=0几何意义明显。几何意义明显。85.Gordan引理引理 设设A1,A2,Al是是l个个n维向量，维向量，AjTP0 (j=1,2,l)成立的充要条件是，不存在成立的充要条件是，不存在=(1,2,l)T0，使，使 1A1+2A2+lAl=0成立。成立。或或Gordan引理引理 A1T方程组方程组 A2TP0有解的充要条件是有解的充要条件是.AlT方程组方程组 (A1,A2,Al)=0，0无解。无解。86.如果有如果有n维向量维向量P使使 AjTP0 (j=1,2,l)则对于则对于=(1,2,l)T0，有，有1A1TP+2A2TP+lAlTP0但但1A1TP+2A2TP+lAlTP=PT(1A1+2A2+lAl)，这时要说存在，这时要说存在=(1,2,l)T0，有，有1A1+2A2+lAl=0，则产生矛盾。则产生矛盾。87.A1A2A3PHOA1A3A2PHO(a)(b)88.n89.n90.n91.FritzJohn(19101994)1933在哥廷根大学学数学，在哥廷根大学学数学，当当年年因因希特勒得势，被迫前往英国。希特勒得势，被迫前往英国。1934年获得哥廷根大学博士年获得哥廷根大学博士学位。学位。1935年任肯塔基大学副教授，年任肯塔基大学副教授，1941年入美国籍。年入美国籍。19431945于马里兰阿伯丁试验场研究弹道学，于马里兰阿伯丁试验场研究弹道学，1946年年到到纽约大学工作，一直到退休。纽约大学工作，一直到退休。92.n93.Harold W.KuhnProfessor EmeritusMathematicsPrinceton Universitykuhnmath.Princeton.EDU94.n95.n96.K-T条件是条件是X*成为极小点的必要条件，但是对于成为极小点的必要条件，但是对于凸规划，也是充分条件。凸规划，也是充分条件。97.98.99.n100.4x1+4x2+1+22=64x1+6x2+1+32=31(1-x1-x2)=02(4-2x1-3x2)=01,20分成几种情况：分成几种情况：(i)1=2=0 x1=3,x2=-1.5,g1(X)=1-x1-x2=1-3+1.5=-0.50不是不是K-T点。点。101.(ii)1=0,204x1+4x2+22=64x1+6x2+32=34-2x1-3x2=0 x1=2-1.5x2代入前两式，得代入前两式，得2=-5/30，是，是K-T点。点。102.(iv)10,204x1+4x2+1+22=64x1+6x2+1+32=34-2x1-3x2=01-x1-x2=0解后两个方程，得解后两个方程，得x1=-1,x2=2,代入前两个方程代入前两个方程1+22=21+32=-5，得，得1=16,2=-7,不是不是K-T点。点。所以，所以，X*=(x1,x2)T=(5/2,-3/2)T，f(X*)=2x12+4x1x2+3x22-6x1-3x2=25/2-15+27/4-15+9/2=95/4-30=-25/2103.n104.4x1+4x2+1+22-3=64x1+6x2+1+32-4=31(1-x1-x2)=02(4-2x1-3x2)=03x1=04x2=01,2,3,4 0构造如下线性规划问题：构造如下线性规划问题：105.Min(z)=z1+z24x1+4x2 +1+22-3 +z1 =64x1+6x2 +1+32 -4 +z2=3x1+x2+x3 =12x1+3x2 +x4 =4x1,x2,x3,x4,1,2,3,4,z1,z2 0可利用单纯形表求解，但注意可利用单纯形表求解，但注意x1和和3,x2和和4,x3和和1,x4和和2,不能同时为基变量。不能同时为基变量。106.cj0000000011icBxBbx1x2x3x41234z1z21 z16440012-10103/21 z234600130-1011/20 x31111000000010 x4423010000004/3(z)9-8-1000-2-51100j1 z144/30001/30-1 2/31-2/30 x21/2 2/31001/6 1/20-1/601/60 x31/21/3010-1/6-1/201/60-1/60 x45/20001-1/2-3/201/20-1/2(z)4-4/3000-1/301-2/305/3107.cj0000000011cBxBbx1x2x3x41234z1z21 z130-2000-1-111-10 x13/413/2001/4 3/40-1/401/40 x31/40-1/210-1/4-3/40 1/40-1/40 x45/20001-1/2-3/201/20-1/2(z)30200011-1021 z1200-4012-101020 x111110000000-0 410-240-1-3010-1-0 x4201-21000000-(z)30040-1-21001x4和和2不能同时为基变量，所以，不能同时为基变量，所以，2不能换入，不能换入，1换入。换入。108.cj0000000011cBxBbx1x2x3x41234z1z20 1200-4012-101020 x111110000000-0 430-2000-1-111-1-0 x4201-21000000-(z)00000000011X*=(x1,x2,x3,x4,1,2,3,4)T=(1,0,0,2,2,0,0,3)T，f(X*)=2x12+4x1x2+3x22-6x1-3x2=2-6=-4109.x1=1,x2=0,x3=0,x4=2,1=2,2=0,3=0,4=3,z1=0,z2=0代入约束条件，检查代入约束条件，检查4x1+4x2 +1+22-3 +z1 =64x1+6x2 +1+32 -4 +z2=3x1+x2+x3 =12x1+3x2 +x4 =4均成立。均成立。110.