1、1第六章第六章 非线性规划非线性规划第一节第一节 基本概念基本概念第三节第三节 无约束极值问题无约束极值问题第四节第四节 约束极值问题约束极值问题2第一节第一节 基本概念基本概念一、非线性规划数学模型一、非线性规划数学模型3非线性规划数学模型一般形式：非线性规划数学模型一般形式：Min f(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实函数。实函数。有时，非线性规划数学模型写成：有时，非线性规划数学模型写成：Min
2、 f(X)s.t.gj(X)0，(j=1,2,l)若某若某gj(X)=0，可以，可以gj(X)0和和-gj(X)0代替之。代替之。4n 5A(0,5)BCD(4,1)1O125x1x2346n 7n 8n 9n 10AT=A，即，即 aji=aij。若。若aij均为实数，则称均为实数，则称f(X)=XTAX为实二次型。为实二次型。A与二次型一一对应。与二次型一一对应。(1)若对于非零若对于非零X，实二次型总有，实二次型总有XTAX0，则称，则称为正定的；为正定的；(2)若对于非零若对于非零X，实二次型总有，实二次型总有XTAX0，而对另一些非，而对另一些非零零X，XTAX0a110，|a11
3、a12|a11 a12 a13|a21 a22|0|a21 a22 a23|0|a31 a32 a33|a11 a12 a1n|a21 a22 a2n|.|0|.|.|an1 an2 ann|12实二次型实二次型f(X)=XTAX为负定的充要条件是：为负定的充要条件是：a110|a21 a22 a23|0|.|.|an1 an2 ann|13 例例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
4、：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)上
5、上(0)，选择一个，选择一个k，到达新点，到达新点X(k+1)=X(k)+k P(k)，使得，使得39f(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)，故，
6、故称这一过程为（最优）一维搜索或线搜索。如此称这一过程为（最优）一维搜索或线搜索。如此确定的步长，称为最优步长。确定的步长，称为最优步长。40n 41n 4243n 44第三节第三节 无约束极值问题无约束极值问题45无约束极值问题表示无约束极值问题表示Min f(X)，XRc前文已指出，须用迭代法求解。迭代法有解析法前文已指出，须用迭代法求解。迭代法有解析法和直接法两类。和直接法两类。解析法要用到目标函数一阶和二阶导数。解析法要用到目标函数一阶和二阶导数。直接法不用，只用目标函数值。有些目标函数没直接法不用，只用目标函数值。有些目标函数没有导数，只能用直接法。有导数，只能用直接法。46n 47
7、n 48n 49n 50n 51n 52n 53n 54n 5556例例9人工神经网络人工神经网络 模仿人脑神经网络，将具有识别、记忆功能模仿人脑神经网络，将具有识别、记忆功能的人工神经元以各种不同的方式连接成不同的网的人工神经元以各种不同的方式连接成不同的网络。用于计算、分类、模式识别、评价、预测、络。用于计算、分类、模式识别、评价、预测、控制、智能机器人、数据挖掘等领域。控制、智能机器人、数据挖掘等领域。1.人工神经元与感知机人工神经元与感知机(1)神经元感知功能神经元感知功能 人工神经元人工神经元 （感知机）（感知机）57n 58n 59n 60n 61n 62n 63n 64 先赋予先
8、赋予w=(w1,w2,wm)T一个初始值，然一个初始值，然后逐步调整，使其逐步逼近极值点后逐步调整，使其逐步逼近极值点w*=(w*1,w*2,w*m)T，调整方向调整方向P=(p1,p2,pm)T，调整量，调整量是是P，步长，步长就是上面的就是上面的“学习系数学习系数”。当当P=-f(w)时，总误差时，总误差f(w)下降最快。下降最快。65n 66n 67n 68n 69n 70n 71n 72n 73第四节第四节 约束极值问题约束极值问题74n 75n 760Rcx1x21.0g1(X)=0g2(X)=0黑色方向不可行黑色方向不可行77n 78n 79n 80n 81【例例】Min f(x)
9、=-4x1-6x2+2x12+2 x1x2+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)Tg1(x)=(-1，-2)Tg2(x)=(1，0)Tg3(x)=(0，1)T82记记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
10、，g2(x(0)=(1，0)T，g3(x(0)=(0，1)T 83x1x2x(0)不是解。不是解。因在因在f(x(0)和和g1(x(0)之间，可找到一个方向之间，可找到一个方向P，使得，使得f(x(0)TP0同时成立，同时成立，即即P同同f(x(0)成钝角，而同成钝角，而同g1(x(0)成锐角。成锐角。121P Pf(x(0)g1(x(0)x(0)84或者，令或者，令P=(p1，p2)T，下列不等式组有解：下列不等式组有解：f(x(0)TP=-p1/2-2p20只须令只须令p1=-1，p2=3/8即可，所以，即可，所以，x(0)=(1/2,3/4)T不是问题的解。不是问题的解。852.库恩塔克
11、条件库恩塔克条件Kuhn-Tucker先讲几个预备性定理。先讲几个预备性定理。(1)Gordan引理引理 设设A1,A2,Al是是l个个n维向量，不维向量，不存在存在n维向量维向量P使使AjTP0 (j=1,2,l)成立的充要条件是，存在不全为零的非负实数成立的充要条件是，存在不全为零的非负实数1,2,l，使，使1A1+2A2+lAl=0几何意义明显。几何意义明显。86Gordan引理引理 设设A1,A2,Al是是l个个n维向量，维向量，AjTP0 (j=1,2,l)成立的充要条件是，不存在成立的充要条件是，不存在=(1,2,l)T0，使，使 1A1+2A2+lAl=0成立。成立。或或Gord
12、an引理引理 A1T方程组方程组 A2T P0有解的充要条件是有解的充要条件是 .AlT方程组方程组 (A1,A2,Al)=0，0无解。无解。87如果有如果有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，则产生矛盾。则产生矛盾。88A1A2A3PHOA1A3A2PHO(a)(b)89n 90n 91n 92Fritz John(19101994)1933在哥廷根
13、大学学数学，在哥廷根大学学数学，当当年年因因希特勒得势，被迫前往英国。希特勒得势，被迫前往英国。1934年获得哥廷根大学博年获得哥廷根大学博士学位。士学位。1935年任肯塔基大学副教授，年任肯塔基大学副教授，1941年入美国籍。年入美国籍。19431945于马里兰阿伯丁试验场研究弹道学，于马里兰阿伯丁试验场研究弹道学，1946年年到到纽约大学工作，一直到退休。纽约大学工作，一直到退休。93n 94Harold W.KuhnProfessor EmeritusMathematicsPrinceton University95n 96n 97K-T条件是条件是X*成为极小点的必要条件，但是对于成为
14、极小点的必要条件，但是对于凸规划，也是充分条件。凸规划，也是充分条件。9899100n 1014x1+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点。点。102(ii)1=0,204x1+4x2+22=64x1+6x2+32=34-2x1-3x2=0 x1=2-1.5x2代入前两式，得代入前两式，得2=-5/30，是，是K-T点。点。103(iv)10,204x1+4x2+1+22=64x1+
15、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/2104n 1054x1+4x2+1+22-3=64x1+6x2+1+32-4=31(1-x1-x2)=02(4-2x1-3x2)=03x1=04x2=01,2,3,4 0构造如下线性规划问题：构造
16、如下线性规划问题：106Min(z)=z1+z24x1+4x2 +1+22-3 +z1 =64x1+6x2 +1+32 -4 +z2=3 x1+x2+x3 =12x1+3x2 +x4 =4x1,x2,x3,x4,1,2,3,4,z1,z2 0可利用单纯形表求解，但注意可利用单纯形表求解，但注意x1和和3,x2和和4,x3和和1,x4和和2,不能同时为基变量。不能同时为基变量。107cj0000000011icBxBbx1x2x3x41234z1z21 z16440012-10103/21 z234600130-1011/20 x31111000000010 x4423010000004/3(z
17、)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/3108cj0000000011cBxBbx1x2x3x41234z1z21 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/
18、2(z)30200011-1021 z1200-4012-101020 x111110000000-0 410-240-1-3010-1-0 x4201-21000000-(z)30040-1-21001x4和和2不能同时为基变量，所以，不能同时为基变量，所以，2不能换入，不能换入，1换入。换入。109cj0000000011cBxBbx1x2x3x41234z1z20 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=-4
