《清华大学运筹学5非线性规划》由会员分享，可在线阅读，更多相关《清华大学运筹学5非线性规划（110页珍藏版）》请在金锄头文库上搜索。
1、第六章 非线性规划 第一节 基本概念 第三节 无约束极值问题 第四节 约束极值问题 1/110 第一节 基本概念 一、非线性规划数学模型 2/110 3/110 非线性规划数学模型一般形式： 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 f(X) s.t. gj(X)0， (j=1, 2, , l) 若某gj(X) =0，可以gj(X)0和 -gj(X)0代
2、替之。 4/110 n 5/110 A(0,5 ) B C D(4,1 ) 1 O125 x1 x2 34 6/110 n 7/110 n 8/110 n 9/110 n 10/110 AT=A，即 aji =aij 。若aij均为实数，则称 f(X)=XTAX为实二次型。A与二次型一一对应。 (1)若对于非零X ，实二次型总有XTAX0，则称 为正定的； (2)若对于非零X ，实二次型总有XTAX0，而对另一些非 零X， XTAX0 a110，|a11 a12 | |a11 a12 a13| |a21 a22 |0 |a21 a22 a23|0 |a31 a32 a33| |a11 a12
3、a1n | |a21 a22 a2n | |. . . |0 |. . . | |. . . | |an1 an2 ann| 12/110 实二次型f(X)=XTAX为负定的充要条件是： a110 |a21 a22 a23|0 |. . . | |. . . | |an1 an2 ann| 13/110 例1判定如下二次型的性质。 -5 2 2 0 1 1 A= 2 -6 0 B= 1 0 -3 2 0 -4 1 -3 0 矩阵A： -50 |-5 2 2| | 2 -6 | | 2 -6 0|= -80f(X(2)f(X(3)f(X(k) 这就是下降迭代算法。 该算法一般格式与步骤： (1)
4、选取初始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) +k P(k)，使得 39/110 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)继续迭代。 已有不少办
5、法确定搜索方向P(k) 。 多数按使目标函数下快最快的原则确定步长，即 求解一维问题f(X(k) +kP(k)=minf(X(k) +P(k)，故 称这一过程为（最优）一维搜索或线搜索。如此 确定的步长，称为最优步长。 40/110 n 41/110 n 42/110 43/110 n 第三节 无约束极值问题 44/110 45/110 无约束极值问题表示 Min f(X)，XRc 前文已指出，须用迭代法求解。迭代法有解析法 和直接法两类。 解析法要用到目标函数一阶和二阶导数。 直接法不用，只用目标函数值。有些目标函数没 有导数，只能用直接法。 46/110 n 47/110 n 48/110
6、 n 49/110 n 50/110 n 51/110 n 52/110 n 53/110 n n 54/110 55/110 56/110 例9人工神经网络 模仿人脑神经网络，将具有识别、记忆功能 的人工神经元以各种不同的方式连接成不同的网 络。用于计算、分类、模式识别、评价、预测、 控制、智能机器人、数据挖掘等领域。 1. 人工神经元与感知机 (1) 神经元感知功能 人工神经元 （感知机） 57/110 n 58/110 n 59/110 n 60/110 n 61/110 n 62/110 n 63/110 n 先赋予w=(w1,w2 , , wm)T一个初始值，然后 逐步调整，使其逐步
7、逼近极值点w*=(w*1,w*2 , , w*m)T，调整方向P=(p1, p2 , , pm)T，调整量 是P，步长就是上面的“学习系数”。 当P= -f(w)时，总误差f(w)下降最快。 64/110 65/110 n 66/110 n 67/110 n 68/110 n 69/110 n 70/110 n 71/110 n 72/110 n 第四节 约束极值问题 73/110 74/110 n 75/110 n 76/110 0 Rc x1 x2 1.0 g1(X)=0 g2(X)=0 黑色方向不可行 77/110 n 78/110 n 79/110 n 80/110 n 81/110
8、【例】 Min f (x)= - 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)T g1(x)=(-1，-2)T g2(x)=(1，0)T g3(x)=(0，1)T 82/110 记x(0)=(1/2, 3/4)T g1(x(0)= -1/2 -2(3/4) +2=0 g2(x(0)= 1 -1/2=1/20 g3(x(0)= 3/40 所以，在x(0)处，g1(x)是有效约束。 f(x(0)=(-1/2
9、，-2)T，g1(x(0)=(-1，-2)T， g2(x(0)=(1，0)T，g3(x(0)=(0，1)T x1 x2 83/110 x(0)不是解。 因在f(x(0)和g1(x(0)之间，可找到一个方向 P，使得f(x(0)TP0同时成立 ，即P同f(x(0)成钝角，而同g1(x(0)成锐角 。 1 2 1 P f(x( 0) g1(x(0) x(0) 84/110 或者，令P=(p1，p2)T， 下列不等式组有解： f(x(0)TP= -p1/2-2p20 只须令p1= -1，p2= 3/8即可，所以，x(0)= (1/2, 3/4)T不是问题的解。 85/110 2. 库恩塔克条件Kuh
10、n-Tucker 先讲几个预备性定理。 (1)Gordan引理 设A1, A2, , Al是l个n维向量，不 存在n维向量P使 AjTP0 (j=1, 2, , l) 成立的充要条件是，存在不全为零的非负实数1, 2, , l，使 1A1+ 2A2+lAl=0 几何意义明显。 86/110 Gordan引理 设A1, A2, , Al是l个n维向量， AjTP0 (j=1, 2, , l) 成立的充要条件是，不存在=(1, 2, , l)T0 ，使 1A1+ 2A2+lAl=0成立。 或Gordan引理 A1T 方程组 A2T P0有解的充要条件是 . . . AlT 方程组 (A1, A2,
11、 , Al) =0， 0无解。 87/110 如果有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， 则产生矛盾。 88/110 A1 A2 A3 P H O A1 A3 A2 P H O (a) (b) 89/110 n 90/110 n 91/110 n 92/110 Fritz John(19101994)1933在哥廷根大学学数学，当年因 希特勒得势，被
12、迫前往英国。1934年获得哥廷根大学博士 学位。1935年任肯塔基大学副教授，1941年入美国籍。 19431945于马里兰阿伯丁试验场研究弹道学，1946年到 纽约大学工作，一直到退休。 93/110 n 94/110 Harold W. Kuhn Professor Emeritus Mathematics Princeton University kuhnmath.Princeton.EDU 95/110 n 96/110 n 97/110 K-T条件是X*成为极小点的必要条件，但是对于 凸规划，也是充分条件。 98/110 99/110 100/110 n 101/110 4x1+4x
13、2 + 1 +22=6 4x1+6x2 + 1 +32=3 1(1-x1-x2)=0 2(4-2x1-3x2)=0 1, 20 分成几种情况： (i) 1=2=0 x1=3, x2= -1.5, g1(X)=1-x1-x2=1-3+1.5= -0.50 不是K-T点。 102/110 (ii) 1=0, 20 4x1+4x2 +22=6 4x1+6x2 +32=3 4-2x1-3x2=0x1 =2-1.5x2代入前两式，得 2= -5/30，是K-T点。 103/110 (iv) 10, 20 4x1+4x2 +1+22=6 4x1+6x2 +1+32=3 4-2x1-3x2=0 1-x1-x2=0 解后两个方程，得x1= -1, x2= 2, 代入前两个方程 1+22=2 1+32= -5，得
