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

第六章非线性规划第一节基本概念第三节无约束极值问题第四节约束极值问题1/110第一节基本概念一、非线性规划数学模型2/1103/110非线性规划数学模型一般形式：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代替之。4/110还常写成Minf(X)，X∈𝑹⊂En𝑹={X|gj(X)≥0，(j=1,2,…,l)}二、二维问题图解Minf(X)=(x1-2)2+(x2-1)2s.t.x1+x22-5x2=0x1+x2-5≥0x1≥0x2≥05/110A(0,5)BCD(4,1)1O125x1x2346/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/110f(X)≥f(X*)，则称X*为f(X)在𝑹上的局部极小点，f(X*)为局部极小值。若∀X≠X*，X∈𝑹，||X-X*||ε，都有f(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∗)=0𝛁f(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.二次型a11a12…a1nx1f(X)=XTAX=(x1,x2,…,xn)a21a22…a2nx2............an1an2…annxn=𝒂𝒊𝒋𝒙𝒊𝒙𝒋𝒏𝒋=𝟏𝒏𝒊=𝟏10/110AT=A，即aji=aij。若aij均为实数，则称f(X)=XTAX为实二次型。A与二次型一一对应。(1)若对于非零X，实二次型总有XTAX0，则称为正定的；(2)若对于非零X，实二次型总有XTAX0，则称为负定的；(3)若对于某些非零X，XTAX0，而对另一些非零X，XTAX0，则称为不定的；(4)若对任意非零X，XTAX≥0，则称为半正定的。若对任意非零X，XTAX≤0，则称为半负定的。(5)A相应地称正定、负定、不定、半定。11/110实二次型f(X)=XTAX为正定的充要条件是：0a110，|a11a12||a11a12a13||a21a22|0|a21a22a23|0…|a31a32a33||a11a12…a1n||a21a22…a2n||...|0|...||...||an1an2…ann|12/110实二次型f(X)=XTAX为负定的充要条件是：a110，|a11a12||a11a12a13||a21a22|0|a21a22a23|0…|a31a32a33||a11a12…a1n||a21a22…a2n|(-1)n|...|0|...||...||an1an2…ann|13/110[例1]判定如下二次型的性质。-522011A=2-60B=10-320-41-30矩阵A：-50，|-52|=260|-522||2-6||2-60|=-800|20-4|矩阵A为负定。矩阵B：b11=0，|01|=-10|10|矩阵B为不定。14/1103.多元函数台劳展开式(Taylor’sexpansion)回顾一元实函数的情况：设一元实函数f(x)在x0某邻域有连续二导数，则可写出f(x)在点x0处台劳展开式f(x)=f(x0)+f’(x0)(x-x0)+f‘’(ξ)(x-x0)2/2ξ是x和x0之间的一个点。15/1103.多元函数台劳展开式设n元实函数f(X)在X(0)某邻域有连续二阶偏导数，则可写出f(X)在点X(0)处台劳展开式f(X)=f(X(0))+𝛁f(X(0))T(X-X(0))+(X-X(0))T𝛁𝟐f(𝑿)(X-X(0))/2𝑿=X(0)+θ(X-X(0))，0θ1若以X=X(0)+P代入f(X(0)+P)=f(X(0))+𝛁f(X(0))TP+PT𝛁𝟐f(𝑿)P/2也可以写成：f(X)=f(X(0))+𝛁f(X(0))T(X-X(0))+(X-X(0))T𝛁𝟐f(X(0))(X-X(0))/2+o(||X-X(0)||2)16/110o(||X-X(0)||2)是当X→X(0)时，||X-X(0)||2的高阶无穷小。即𝑙𝑖𝑚X→X(0)o(||X−X(0)||2)/||X−X(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)T18/110𝜕𝟐𝒇(𝑿)𝜕𝑥𝟏𝟐𝜕𝟐𝒇(𝑿)𝜕𝑥𝟏𝜕𝑥𝟐20𝛁𝟐f(X)=𝜕𝟐𝒇(𝑿)𝜕𝑥𝟐𝜕𝑥𝟏𝜕𝟐𝒇(𝑿)𝜕𝑥𝟐𝟐=0-2𝛁𝟐f(X)是不定矩阵，所以，f(X)=x12-x22没有极值点。只有鞍点。19/110五、凸函数和凹函数1.定义设f(X)为定义在n维欧式空间En中某凸集Rc上的函数，若对于任何实数α(0α1)及Rc中任意两点X(1)和X(2)，恒有f(αX(1)+(1-α)X(2))≤αf(X(1))+(1-α)f(X(2))则称f(X)为定义在Rc上的凸函数。若对于任何实数α(0α1)及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/110xf(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/110xf(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/110xf(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上的凸函数。βi≥0(i=1,2,…,m)性质3设f(X)为凸集Rc上的凸函数，则对于每一个实数β≥0，集合（称为水平集）Sβ={X|X∈Rc，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，𝛁2f(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-a1b2-b127/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)=𝜕𝟐𝒇(𝑿)𝜕𝑥𝟏𝟐𝜕𝟐𝒇(𝑿)𝜕𝑥𝟏𝜕𝑥𝟐=20𝜕𝟐𝒇(𝑿)𝜕𝑥𝟐𝜕𝑥𝟏𝜕𝟐𝒇(𝑿)𝜕𝑥𝟐𝟐02𝛁𝟐f(X)是正定矩阵，所以，f(X)=x12+x22是严格凸函数。28/1104.凸函数极值要求目标函数最小（大）值，一般须找到所有极小（大）值和边界值，再确定最小（大）值。但对于凸集上的凸（凹）函数，任一极小（大）值就是最小（大）值。极小（大）点构成凸集。设f(X)是凸集Rc上可微凸函数