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

第六章 非线性规划,第一节 基本概念第三节 无约束极值问题第四节 约束极值问题,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代替之。,4/110,还常写成 Min f(X)，XEn =X| gj(X)0，(j=1, 2, , l) 二、二维问题图解 Min f(X)=(x1-2)2+(x2-1)2 s.t. x1+x22-5x2=0 x1+x2-50 x10 x20,5/110,A(0,5),B,C,D(4,1),1,O,1,2,5,x1,x2,3,4,6/110,上图中B是f(X)部分可行域极小点，称为局部极小点， f(B)是部分可行域极小值，称为局部极小值， D是f(X)整个可行域上极小点，称为全局极小点， f(D)是整个可行域上极小值，称为全局极小值。全局极小点是局部极小点，局部极小点不应当是全局极小点。三、几个定义设f(X)是定义在n维欧式空间En中某一区域R上的n元实函数（可记为f(X)：En E1），对于X* ，如果存在某个0，使所有距离X*小于 的X ， (即X 即且|X- X*|)，都有,7/110,f(X)f(X*)，则称X*为f(X)在上的局部极小点， f(X*)为局部极小值。若XX*，X ，|X- X*|f(X*)，则称X*为f(X)在上的严格局部极小点， f(X*)为严格局部极小值。设f(X)是定义在En某一区域R上的n元实函数，若存在X* ，X ，都有f(X)f(X*)，则称X*为f(X)在上的全局极小点， f(X*)为全局极小值。若存在X* ，X X* ，都有f(X)f(X*)，则称X*为f(X)在上的严格全局极小点， f(X*)为严格全局极小值。若颠倒上述定义中的不等号方向，可得相应极大点和极大值的定义。,8/110,四、多元函数极值点存在条件1. 必要条件定理1 设R为n维欧式空间En上的某一开集，f(X)在R上有连续一阶偏导数，且在点X* 取得局部极值，则必有 () = () = () =0, 或f(X)=0f(X)= ( () , () , , () )T 是f(X)在X处的梯度。满足上述条件的点叫做“驻点”。,9/110,多元函数f(X)的梯度f(X)有如下性质：(1)某点X (0)处的f(X(0)与f(X)过此点的等值面正交（设f(X(0)非零）。(2)f(X)的方向是f(X)在该点处增加最快的方向；-f(X)的方向是f(X)在该点处减少最快的方向。2. 二次型 a11 a12 a1n x1f(X)=XTAX =(x1, x2, , xn ) a21 a22 a2n x2 . . . . . . . . . . . . an1 an2 ann xn= = = ,10/110,AT=A，即 aji =aij 。若aij均为实数，则称f(X)=XTAX为实二次型。A与二次型一一对应。(1)若对于非零X ，实二次型总有XTAX0，则称为正定的；(2)若对于非零X ，实二次型总有XTAX0，而对另一些非零X， XTAX0，则称为不定的；(4)若对任意非零X ，XTAX0 ，则称为半正定的。若对任意非零X ，XTAX0 ，则称为半负定的。(5)A相应地称正定、负定、不定、半定。,11/110,实二次型f(X)=XTAX为正定的充要条件是：0a110，|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|,12/110,实二次型f(X)=XTAX为负定的充要条件是：a110 |a21 a22 a23|0 |. . . | |. . . | |an1 an2 ann|,13/110,例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 | = -10 | 1 0 |矩阵B为不定。,14/110,3. 多元函数台劳展开式(Taylors expansion)回顾一元实函数的情况：设一元实函数f(x)在x0某邻域有连续二导数，则可写出f(x)在点x 0处台劳展开式f(x)= f(x0)+f(x0) (x-x0)+f () (x-x0)2/2是x和x0之间的一个点。,15/110,3. 多元函数台劳展开式设n元实函数f(X)在 X(0)某邻域有连续二阶偏导数，则可写出f(X)在点X(0)处台劳展开式f(X)= f(X(0)+f(X(0)T(X-X(0) +(X-X(0)Tf ( )(X-X(0)/2 =X(0)+(X-X(0)，01若以X=X(0)+P代入f(X(0)+P)= f(X(0)+f(X(0)TP+PTf ( )P/2也可以写成：f(X)= f(X(0)+f(X(0)T(X-X(0) +(X-X(0)Tf (X(0)(X-X(0)/2 +o(|X-X(0)|2),16/110,o(|X-X(0)|2)是当XX(0)时，|X-X(0)|2的高阶无穷小。即 XX(0) o(|XX(0)|2)/|XX(0)|2 =04. 充分条件定理2 设R为n维欧式空间En上的某一开集，f(X)在R上有连续二阶偏导数，若f(X)=0，且f(X)正定，则X* 为f(X)严格局部极小点。f(X)是f(X)在X处的Hesse矩阵。若f(X)负定，则X* 为f(X)的严格局部极大点。,17/110,() () () f(X)= () () () . . . . . . () () () 例2研究f(X)=x12-x22是否存在极值点。 () =2x1, () = -2x2, 令 () = () =0，得到 x1 =x2 =0, 得到一个驻点，X=(x1, x2)T =(0, 0)T,18/110,() () 2 0f(X)= () () = 0 -2f(X)是不定矩阵，所以， f(X)=x12-x22没有极值点。只有鞍点。,19/110,五、凸函数和凹函数1. 定义设f(X)为定义在n维欧式空间En中某凸集Rc上的函数，若对于任何实数(01)及Rc中任意两点X(1)和X(2) ，恒有f(X(1)+(1-)X(2)f(X(1)+(1-)f(X(2)则称 f(X)为定义在Rc上的凸函数。若对于任何实数(01)及Rc中任意两点X (1)和X (2) ，恒有f(X (1)+(1-)X (2)f(X (1)+(1-)f(X (2)则称 f(X)为定义在Rc上的严格凸函数。,20/110,颠倒上述定义中不等式方向，可得凹和严格凹函数的定义。若f(X)是（严格）凸函数，则g(X)=- f(X)是（严格）凹函数。（几何意义见下图）2. 凸函数性质性质1 设f(X)为定义在凸集Rc上凸函数，则对于任何实数0， f(X)也是定义在Rc上凸函数。性质2 设f1(X)和f2(X)均为定义在凸集Rc上凸函数，则 f(X)=f1(X)+f2(X)也是定义在Rc上凸函数。,21/110,x,f(x),f(x(2),f(x(1),f(x(1)+(1-) x(2),f(x(1) +(1-) f(x(2),x(1)+(1-) x(2),x(1),x (2),凸函数,22/110,x,f(x),f(x(2),f(x(1),f(x(1)+(1-) x(2),f(x(1) +(1-) f(x(2),x(1)+(1-) x(2),x(1),x (2),凹函数,23/110,x,f(x),f(x(2),f(x(1),f(x(1)+(1-) x(2),f(x(1) +(1-) f(x(2),x(1)+(1-) x(2),x(1),x (2),24/110,性质2 推论若干凸函数非负线性组合1f1(X)+2f2(X)+mfm(X)仍为凸集Rc上的凸函数。i0(i=1, 2, , m)性质3设f(X)为凸集Rc上的凸函数，则对于每一个实数0，集合（称为水平集） S=X|XRc，f(X)是凸集。3.凸函数的判定可直接从定义出发。但是，对于可微凸函数，也可利用如下两个条件：,25/110,（1）一阶条件设Rc是En上开凸集，f(X)在Rc上可微，则f(X)为Rc上凸函数的充要条件是，对于任意两点X (1) Rc和X (2)Rc ，恒有f(X(2)f(X(1)+f(X(1)T(X(2)-X(1)f(X)为Rc上严格凸函数的充要条件是，对于任意两点X(1)Rc和X(2)Rc ，恒有f(X(2)f(X(1)+f(X(1)T(X(2)-X(1)颠倒上述定义中不等式方向，可得凹和严格凹函数充要条件。,26/110,（2）二阶条件设Rc是En上开凸集，f(X)在Rc上二阶可微，则f(X)为Rc上凸（凹）函数的充要条件是，对于所有的X Rc，2 f(X )半正定（半负定）。例3证明f(X)=x12+x22是严格凸函数。先用一阶条件，任取不同的X (1)和X (2)，X (1) =(a1, b1)，X (2) =(a2, b2)，f(X (1)=a12+b12，f(X (2)=a22+b22，f(X (1)=(2a1, 2b1) T，看下式是否成立，a22+b22a12+b12+(2a1, 2b1) a2-a1 b2-b1,27/110,或a22+b22a12+b12+2a1a2-2a12 +2b1b2 -2b12或(a2-a1)2+(b2-b1)20，由于X (1)X (2)，所以上式成立。再用二阶条件 () =2x1， () =2x2， () =2， () =0， () =2，f(X)= () () = 2 0 () () 0 2f(X)是正定矩阵，所以， f(X)=x12+x22是严格凸函数。,28/110,4.凸函数极值要求目标函数最小（大）值，一般须找到所有极小（大）值和边界值，再确定最小（大）值。但对于凸集上的凸（凹）函数，任一极小（大）值就是最小（大）值。极小（大）点构成凸集。设f(X)是凸集Rc上可微凸函数，若有X *Rc，使得对于所有的X Rc，恒有f(X*)T(X-X *)0，则X *就是f(X)在Rc上最小点（全局极小点）。此结论可由一阶条件直接推出。,29/110,O,Rc,x1,x2,X*,X,XX*,f(X*),30/110,若X *是Rc的内点，向量X-X *在n维欧式空间En，中可取任何方向，这意味着，这时可用f(X*) =0代替f(X*)T(X-X *)0，可知，在这种情况下，f(X*) =0不仅是极值点存在的必要条件，也是充分条件。六、凸规划现在考虑非线性规划： Min f(X) s.t. gj(X)0， (j=1, 2, , l)若f(X)为凸函数，gj(X) (j=1, 2, , l)均为凹函数，（即-gj(X) (j=1, 2, , l)均为凸函数），就称该问题为凸规划。,31/110,凸规划性质(1) 可行解集为凸集。(2) 若有最优解，则最优解集为凸集。(3) 任何局部极值点也是全局极值点。(4) 若目标函数为严格凸函数，且有最优解，则该最优解唯一。以下验证上述四个性质：考虑凸规划 Min f(X) s.t. gj(X)0， (j=1, 2, , l)f(X)和-gj(X) (j=1, 2, , l)均为凸函数。,32/110,以Rc记可行解集。若任取X (1)Rc， X (2)Rc，则对任意(01)，有gj(X(1)+(1-)X(2)gj (X(1)+(1-)gj(X(2)0， (j=1, 2, , l)即X(1)+(1-)X(2) Rc，也就是说，可行解集（可行域）为凸集。既然可行域为凸集，f(X)为凸函数，则f(X)若有最优解，则最优解集为凸集，任何局部极值点也是全局极值点。下面验证性质(4)。,33/110,下面验证性质(4)。 反证法。设有多个最优解。例如X(1)Rc，X(2)Rc，X(1)X(2) ，但f(X(1)=f(X(2)，任取(01)，有X(1)+(1-)X(2) Rc，根据严格凸函数定义，应当说有f(X(1)+(1-)X(2)f(X(1)+(1-)f(X(2)=f(X(1)该式说明，还有比X(1)和X(2)更好的解， X(1)和X(2)不是最优解，矛盾。容易想到，线性规划是凸规划。,34/110,例4验证如下非线性规划为凸规划： Min f(X)=x12+x22-4x1+4 s.t. g1(X)=x1-x2+20， g2(X)= -x12+x2-10， g3(X)= x10， g4(X)= x20g1(X)、g3(X)和g4(X)是x1和x2的线性函数，也是凹函数。 对于g2(X)，有,35/110,g2(X)= g2() g2() = -2 0 g2() g2() 0 0g2(X)是半负定矩阵，所以，g2(X)是凹函数。f(X)= f() f() = 2 0 正定， f() f() 0 2f(X)是严格凸函数。该非线性规划为凸规划。唯一极小点是X=(0.58, 1.34)，f(X)=3.8在该点处，f(X) =(2x1-4, 2x2)T=(20.58-4, 2 1.34)T=(-2.84, 2.68)T,36/110,0,Rc,x1,x2,3.8,f(X),1.0,g1(X)=0,g2(X)=0,37/110,七、下降迭代算法对于一般的非线性规划目标函数，由f(X) =0，得到的是非线性方程组，很难解。此外，许多问题目标函数没有f(X)。所以，实际上用迭代法求解。基本思路，先找一个可行解，按照一定规则，再找一个更好的，判断是否是最好的？若是，停；若否，再找一个更好的，再判断是否是最好的。如此反复，一直满意为止。如此寻找，得到一个序列X(k)，该序列若有极限，用X*记之。 lim |X(k)X| =0,38/110,目标函数求最小的规划问题，应有f(X(0)f(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) +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)继续迭代。已有不少办法确定搜索方向P(k) 。多数按使目标函数下快最快的原则确定步长，即求解一维问题f(X(k) +kP(k)=minf(X(k) +P(k)，故称这一过程为（最优）一维搜索或线搜索。如此确定的步长，称为最优步长。,40/110,上述搜索有个重要性质：新点X(k+1)处的梯度f(X(k+1)和X(k)处搜索方向P(k)正交。定理3 设目标函数有连续一阶偏导数，按下列规则选择X(k+1) ，f(X(k) +kP(k)=minf(X(k) +P(k) X(k+1) =X(k) +kP(k)，则有f(X(k+1)TP(k) =0,41/110,证明：构造函数()=f(X(k) +P(k)，则 (k)=min() X(k+1) =X(k) +kP(k)，即k是()的极小点。另一方面， ()=f(X(k) +P(k)TP(k)由(k)=0，得(k)=f(X(k) +kP(k)TP(k) =0由于f(X)在某点处的梯度f(X)和该点等值面正交，从而一维最优搜索方向与其上最优点处函数等值面相切。,42/110,f(X)=f(X(k+1),f(X)=40,X(k+1),X(k),f(X(k+1),P(k),43/110,因事先不知道极值点X*，可根据相继两次结果之差，判断是否已到或接近极值点。有三种常用准则：(1) |X(k+1) -X(k)|1，|f(X(k+1) - f(X(k)|2(2) |X(k+1) -X(k)|/|X(k)|3，|f(X(k+1) - f(X(k)|/|f(X(k)|4(3)|f(X(k+)|51， 2， 3， 4， 5都是足够小的正数。,第三节 无约束极值问题,44/110,45/110,无约束极值问题表示Min f(X)，XRc前文已指出，须用迭代法求解。迭代法有解析法和直接法两类。解析法要用到目标函数一阶和二阶导数。直接法不用，只用目标函数值。有些目标函数没有导数，只能用直接法。,46/110,一、梯度法（最速下降法）Min f(X)，XRc是其他方法基础。设f(X)有连续一阶导数，有极小点X*。X(k)表示X*第k次近似，为求第k+1次近似X(k+1)，在X(k)处沿P(k)作射线 X=X(k)+P(k)， 0 将f(X)在X(k)处展开f(X)= f(X(k)+P(k)= f(X(k)+f(X(k)TP(k)+o()可假设f(X(k)0，o()是高阶无穷小。只要f(X(k)TP(k)0，即有 f(X(k)+P(k)f(X(k),47/110,现求满足这些要求的P(k)f(X(k)TP(k)=|f(X(k)|P(k)|cos是f(X(k)和P(k)的夹角。当f(X(k)和P(k)同向时， =0，cos =1，f(X(k)TP(k)最大。当f(X(k)和P(k)反向时， =1800，cos = -1，f(X(k)TP(k)0，最小，是负梯度方向，目标函数下降最快。梯度法沿负梯度方向搜索。再确定步长，为此，确定使下式成立的f(X(k)-f(X(k)f(X(k),48/110,另一种办法k: minf(X(k)-f(X(k)| 0这样的k叫做最优步长。用最优步长的梯度法叫做最速下降法。求minf(X)的梯度法步骤：(1)选取某一初始X(0)和，k:=0;(2)算f(X(k)和f(X(k)。若|f(X(k)|2，停，得近似极小点X(k)和近似f(X(k)；否则，转下一步。(3)确定步长。k: minf(X(k)-f(X(k)| 0算X(k+1)=X(k) -kf(X(k)，令k:=k+1，回第(2)步。,49/110,设f(X)在X(k)处有二阶连续偏导数，并将f(X(k)-f(X(k)在X(k)处展开：f(X(k)-f(X(k) f(X(k)- f(X(k)Tf(X(k) + 2f(X(k)Tf(X(k)f(X(k)/2对求导数，并令其等于零，得到k=f(X(k)Tf(X(k)/f(X(k)Tf(X(k)f(X(k)有时，将P(k)规一化，P(k) = -f(X(k)/|f(X(k)|这时，k=f(X(k)Tf(X(k) |f(X(k)|/f(X(k)Tf(X(k)f(X(k),50/110,例7用梯度法求f(X)=(x1-3)2+(x2+7)2的极小点，允许误差取=0.7。解 取X(0)=(2, 1)T，f(X()=(2x1-6, 2x2+14)T=(-2, 16)T 2 0f(X(0)= 0 2 0= (, ) (, ) =260/520=0.5X(1)=X(0)-0.5f(X()=(2, 1)T - 0.5(-2, 16)T=(3, -7)Tf(X()=(2x1-6, 2x2+14)T=(0, 0)T |f(X(1)|2=0 =0.7,51/110,例8用梯度法求f(X)=x12+5x22极小点，允许误差取=0.7。解 取X(0)=(2, 1)T，f(X()=(2x1, 10 x2)T=(4, 10)Tf(X(0)= 2 0 0 10 0= (, ) (, ) =116/1032=0.1124X(1)=X(0)-0.1124f(X()=(2, 1)T - 0.1124(4, 10)T =(1.5504, -0.124)Tf(X()=(2x1, 10 x2)T=(3.1008, -1.2400)T,52/110,|f(X(1)|2 =11.1524 =0.7 1= (., .) . . (., .) . . =0.3223X(2)=X(1)-0.3223f(X(1)=(1.5504, -0.124)T - 0.3223(3.1008, -1.24)T=(0.5510, 0.2757)Tf(X()=(2x1, 10 x2)T=(1.102, 2.757)T|f(X(2)|2 =8.815 =0.72= (., .) . . (., .) . . =0.1124X(3)=X(2)-0.1124f(X(2)=(0.551, 0.2757)T - 0.1124(1.102, 2.757)T=(0.4271, -0.03419)T,53/110,f(X()=(2x1, 10 x2)T=(0.8542, -0.3419)T|f(X(3)|2 =0.8466 =0.7 3= (., .) . . (., .) . . =0.3221X(4)=X(3)-0.3221f(X(3)=(0.4271, -0.03419)T - 0.3221(0.8542, -0.3419)T=(0.152, 0.0759)Tf(X()=(2x1, 10 x2)T=(0.304, 0.759)T|f(X(4)|2 =0.6685 =0.7故以X(4)= (0.152, 0.0759)T为近似极小点；f(X()= x12+5x22=0.0519为近似极小值。该题精确解是X= (0, 0)T，(X)=0。,梯度法缺点：现在回过头，看一看，f(X()Tf(X()=(4, 10)(3.1008, -1.2400)T=0f(X()Tf(X()=(3.1008, -1.2400)(1.102, 2.757)T =0f(X()Tf(X()=(1.102, 2.757)(0.8542, -0.3419)T =0f(X()Tf(X()=(0.8542, -0.3419)(0.304, 0.759)T =0,54/110,55/110,56/110,例9人工神经网络 模仿人脑神经网络，将具有识别、记忆功能的人工神经元以各种不同的方式连接成不同的网络。用于计算、分类、模式识别、评价、预测、控制、智能机器人、数据挖掘等领域。1. 人工神经元与感知机(1) 神经元感知功能 人工神经元 （感知机）,57/110,设该神经元有n个输入：x1, x2, ., xn；各自的连接权为：w1, w2, w3,., wn。激发值（强度）是a=w1x1+w2x2+.+ wnxn=wxT= =1 其中，w=(w1, w2, ., wn)，x =(x1, x2, ., xn)。激发结果是： f(wxT-)，是阈值， f(*)叫做激发函数。非对称Sigmoid激发函数,58/110,(2) 感知机学习与预测功能 对于时间序列xk= xn, xn-1, , x1，所谓预测 n+1就是用xk的线性组合 =1 n+1-i当作预测值。wi是第n+1-i个样本的权值。 感知机能够让wi逐渐适应xk的“模式”。一旦“适应”或“识别”了“模式”，就可以预测xk的未来。 感知机“识别” xk“模式”的过程，叫做“训练”，也是感知机的“学习”过程。 设xk=1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1，下面以预测x11为例，说明感知机的训练或学习过程。,59/110,要用感知机预测，先须确定连接权数目，这里用两项。预测前，先用上述样本训练。设感知机神经元输出是输入加权和的线性函数，即激发函数为f(x)=x，另外，设=0。 先用x1=0.1，x2=0.2预测x3，令w1=w2=0.5， 3= f(w1x2+w2x1)=w1x2+w2x1 =0.50.2+0.50.1=0.15， 误差e3= x3- 3=0.3-0.15=0.15，其中样本值x3是对预测的期望值，用来衡量 3是否准确。,60/110,误差是因为w1和w2初始值不合适，需调整。调整用下面的式子：w1=w1+2e3x2w2=w2+2e3x1叫做“学习系数”，暂取=0.9。于是，w1=0.5+20.90.150.2=0.554w2=0.5+20.90.150.1=0.527 调整之后，再利用x2=0.2，x3=0.3预测x4， 4=f(w1 x3+w2x2)=w1 x3+w2x2=0.5540.3+0.5270.2=0.2716误差是e4= x4- 4=0.4-0.2716=0.1284，,61/110,仍按下面的式子调整： w1=w1+2e4x3 = 0.554+20.90.12840.3=0.624w2=w2+2e4x2 = 0.527+20.90.12840.2=0.564 如此反复，一直到w1=2，w2= -1。 11=f(w1 x10+w2x9)=w1 x10+w2x9=21.0 -10.9=1.1 训练结束。下面说明上述调整公式的来源。,62/110,选择权值，应使预测误差最小。预测误差表示如下：en+1=xn+1- n+1=xn+1- =1 n+1-Ie2n+1=xn+1- =1 n+1-i2或f(w)= xn+1- =1 n+1-i2f(w)= (f(w)/w1, f(w)/w2 , , f(w)/wm)T,63/110,2xn+1- =1 n+1-ixn 2xn+1- =1 n+1-ixn-1f(w)= - . . 2xn+1- =1 n+1-ixn+1-m 2en+1xn 2en+1xn-1 = - . . 2en+1xn+1-m,先赋予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/110,65/110,预备知识：向量对向量的导数设u(X)是X的向量函数，即uT(X) =(u1(X), u2(X), , un(X)则定义矩阵 () () () () () () . . . . . . . . . () () () 是uT(X)对向量X的导数。 以duT(X)/dX表示。,66/110,若uT(X) =XT= (x1, x2, , xn) () = = I ,67/110,若vT(X) =(AX)T=( = , = , , = ) = = = () = = = = = AT = = = ( ) = v(X)+ u(X),68/110,二、牛顿法考虑二次正定函数：f(X)=XTAX/2+BTX+cA为nn二次对称正定矩阵，X En，BEn，c为常数。 () = () =f(X*)= (XTAX/2+BTX+c) = AX/2+ () X/2+ BT X+ XT B () =AX/2+ATX/2+B= AX+B,69/110,假定该函数极小点为X*， 必有f(X*)=AX* +B=0对于任意X(0)En，f(X(0)=AX(0) +B对于任意X(0)En，f(X(0)=AX(0) +B=AX(0) -AX*=AX(0) -AX* ，X*=X(0) -A-1f(X(0)该式说明，对于正定二次函数，从任意一点出发，沿任意-A-1f(X(0)方向搜索，以1为步长，迭代一步，就到达极小点。,70/110,例8用牛顿法求f(X)=x12+5x22的极小点，允许误差取=0.7。解 X(0)=(2, 1)T，f(X()=(2x1, 10 x2)T=(4, 10)TA= 2 0 A-1 = 1/2 0 0 10 0 1/10,71/110,X*=X(0) -A-1f(X(0)= 2 - 1/2 0 4 = 0 1 0 1/10 10 0f(X)=(2x1, 10 x2)T=(0, 0)T可见，牛顿法与梯度法搜索方向不同。考虑一般n元实函数f(X)，假定有二阶连续偏导数， X(k)为极小点近似，在该点附近展开，f(X) f(X(k)+f(X(k)TX + XTf(X(k)X/2其中X =X -X(k)上述近似表达式应当满足一阶必要条件：,72/110,f(X(k)+ f(X(k)X=0设f(X(k)有逆矩阵 X=X(k) f(X(k)-1f(X(k)这仍然是近似式。以 f(X(k)-1f(X(k)为搜索方向的牛顿法迭代步骤如下： P(k) = f(X(k)-1f(X(k) k: minf(X(k)+P(k)| 0 X(k+1)=X(k)+kP(k)这就是广义牛顿法，可用于求解非二次正定函数极小点。快，但有时需改进， f(X(k)-1计算费时。还有很多方法。,第四节 约束极值问题,73/110,74/110,一、最优性条件1. 可行下降方向(1)起作用约束设X(0)为 Min f(X)，XEn =X| gj(X)0，(j=1, 2, , l)的一个可行解。对于某个gj(X)0，可能有两种情况： gj(X(0)0和gj(X(0)=0。当gj(X(0)0时， X(0)不在由gj(X)=0确定的边界上，称该约束条件为不起作用或无效约束。当gj(X(0)=0时，X(0)在由gj(X)=0确定的边界上，,75/110,约束了X(0)移动，称为X(0)的起作用或有效约束。等式约束对于所有可行解都是有效约束。(2)可行方向设X(0)为任意可行点，对于某方向P，若存在实数00。使对任意0, 0，均有下式成立X(0)+P 就称P为X(0)点的可行方向。以J记X(0)点所有有效约束的编号，即J=j| gj(X(0)=0, j=1, 2, , l。,76/110,0,Rc,x1,x2,3.8,f(X),1.0,g1(X)=0,g2(X)=0,黑色方向不可行,77/110,如果P为X(0)点可行方向，则存在00，使对任意0, 0，均有gj(X(0)+P)gj(X(0)=0， jJ从而(dgj(X(0)+P)/d) =0 =gj(X(0)TP0， jJ另一方面， gj(X)在X(0)处的台劳展式为gj(X(0)+P)=gj(X(0)+gj(X(0)TP+o()对于X(0)点处任何有效约束，当足够小时，只要gj(X(0)TP0， jJ就有 gj(X(0)+P)0， jJ,78/110,对于X(0)点处任何无效约束， gj(X(0)0，由gj(X)的连续性，当足够小时，亦有gj(X(0)+P)0， j J从而，只要方向P满足gj(X(0)TP0，jJ，就可保证是X(0)点处可行方向。(3)下降方向设X(0)R，对于某方向P，若存在实数00，使对任意0, 0均有下式成立 f(X(0)+P)f(X(0)就称P 为X(0)点处一个下降方向。,79/110,由X(0)处台劳展式f(X(0)+P)=f(X(0)+f(X(0)TP+o()当足够小时，只要f(X(0)TP0 就有f(X(0)+P)f(X(0)，这说明，只要方向P 满足f(X(0)TP0，即可保证是X(0)处的下降方向。 (4)可行下降方向若X(0)处某方向P，既是该点可行方向，又是下降方向，就称X(0)点可行下降方向。设X(0)不是极小点，继续搜索时，应取该方向。,80/110,显然，对于某一点X*，若不存在可行下降方向，就可能是局部极小点，若存在可行下降方向，就不是极小点。定理4 设X*是局部极小点，f(X)在X*处可微，且gj(X)在X*处可微， jJgj(X)在X*处连续， j J则在X*处不存在可行下降方向，从而不存在P同时满足(X)TP0， jJP应与-(X)和gj(X*)都成锐角。,81/110,【例】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)Tg1(x)=(-1，-2)Tg2(x)=(1，0)Tg3(x)=(0，1)T,82/110,记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)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. 库恩塔克条件Kuhn-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, , 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,(2)Fritz John定理设X*为 Min f(X)，XEn =X| gj(X)0，(j=1, 2, , l)局部极小点， f(X)和gj(X) (j=1, 2, , l)在X*处具有一阶连续偏导数，则必存在不全为零的数0, 1, 2, , l，使0f(X*)-1g1(X*)-2g2(X*)-lgl(X*)=0 jgj(X*)=0 (j=1, 2, , l) j0 (j=1, 2, , l),90/110,证明：因为X*为 Min f(X)，XEn =X|gj(X)0，(j=1, 2, , l)局部极小点，根据定理4，在X*处不存在可行下降方向，满足 (X)TP0，-gj(X*)TP0， jJ将(X), -gj(X*)一起视为Gordan引理中的向量Aj，则必存在不全为零的00, j0(jJ)，使0f(X*)-jgj(X*) =0 对于 j J ，令j =0，从而有0f(X*)- = jgj(X) =0,91/110,且对所有的j，有 jgj(X*)=0 (j=1, 2, , l) j0 (j=1, 2, , l)该定理给出了Min f(X)，XEn =X| gj(X)0，(j=1, 2, , l)局部极小点应满足的必要