运筹学课件-非线性规划

第六章非线性规划第一节基本概念第三节无约束极值问题第四节约束极值问题1/91第一节基本概念一、非线性规划数学模型2/913/91非线性规划数学模型一般形式：

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/91

5/91A(0,5)BCD(4,1)1O125x1x2346/91

7/91

8/91

9/91

10/91AT=A，即aji

=aij

。若aij均为实数，则称f(X)=XTAX为实二次型。A与二次型一一对应。(1)若对于非零X，实二次型总有XTAX>0，则称为正定的；(2)若对于非零X，实二次型总有XTAX<0，则称为负定的；(3)若对于某些非零X

，XTAX>0，而对另一些非零X，

XTAX<0，则称为不定的；(4)若对任意非零X，XTAX≥0，则称为半正定的。若对任意非零X，XTAX≤0，则称为半负定的。(5)A相应地称正定、负定、不定、半定。11/91实二次型f(X)=XTAX为正定的充要条件是：>0a11>0，|a11a12||a11a12a13|

|a21a22|>0

|a21a22a23|>0…|a31a32a33||a11a12…a1n||a21a22…a2n|

|...

|>0|...

||...

|

|an1an2…ann|12/91实二次型f(X)=XTAX为负定的充要条件是：a11<0，|a11a12||a11a12a13|

|a21a22|>0

|a21a22a23|<0…|a31a32a33||a11a12…a1n||a21a22…a2n|(-1)n|...

|>0|...

||...

|

|an1an2…ann|13/91

[例1]判定如下二次型的性质。

-522011A=2-60B=10-320-41-30矩阵A：

-5<0，|-5

2

|=26>0|-522|

|2-6||2-60|=-80<0

|20-4|矩阵A为负定。矩阵B：b11=0，|0

1

|=-1<0

|10|矩阵B为不定。

14/91

15/91

16/91

17/91

18/91

19/91

20/91颠倒上述定义中不等式方向，可得凹和严格凹函数的定义。若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/91xf(x)f(x(2))f(x(1))

x(1)x(2)

22/91xf(x)f(x(2))f(x(1))

x(1)x(2)

23/91xf(x)f(x(2))f(x(1))

x(1)x(2)24/91性质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/91

26/91

27/91

28/91

29/91ORcx1x2

30/91

31/91凸规划性质(1)可行解集为凸集。(2)若有最优解，则最优解集为凸集。(3)任何局部极值点也是全局极值点。(4)若目标函数为严格凸函数，且有最优解，则该最优解唯一。以下验证上述四个性质：考虑凸规划

Minf(X)

s.t.

gj(X)≥0，(j=1,2,…,l)f(X)和-gj(X)(j=1,2,…,l)均为凸函数。32/91

33/91

34/91[例4]验证如下非线性规划为凸规划：Minf(X)=x12+x22-4x1+4

s.t.

g1(X)=x1-x2+2≥0，

g2(X)=-x12+x2-1≥0，g3(X)=x1≥0，g4(X)=x2≥0g1(X)、g3(X)和g4(X)是x1和x2的线性函数，也是凹函数。

对于g2(X)，有35/91

36/910Rcx1x2

●1.0g1(X)=0g2(X)=037/91

38/91目标函数求最小的规划问题，应有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)+λkP(k)，使得39/91f(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/91

41/91

42/91

43/91

第三节无约束极值问题44/9145/91无约束极值问题表示Minf(X)，X∈Rc前文已指出，须用迭代法求解。迭代法有解析法和直接法两类。解析法要用到目标函数一阶和二阶导数。直接法不用，只用目标函数值。有些目标函数没有导数，只能用直接法。46/91

47/91

48/91

49/91

50/91

51/91

52/91

53/91

54/91梯度法缺点：55/91

56/91

57/91

58/91

59/91

60/91

61/91

62/91

第四节约束极值问题63/9164/91

65/91

66/910Rcx1x2

●1.0g1(X)=0g2(X)=0黑色方向不可行67/91

68/91

69/91

70/91

71/912.库恩塔克条件Kuhn-Tucker先讲几个预备性定理。(1)Gordan引理设A1,A2,…,Al是l个n维向量，不存在n维向量P使AjTP<0(j=1,2,…,l)成立的充要条件是，存在不全为零的非负实数μ1,μ2,…,μl，使μ1A1+μ2A2+…+μlAl=0不证明，只看几何意义。72/91Gordan引理设A1,A2,…,Al是l个n维向量，AjTP<0(j=1,2,…,l)成立的充要条件是，不存在μ=(μ1,μ2,…,μl)T≥0，使μ1A1+μ2A2+…+μlAl=0成立。或Gordan引理

A1T方程组

A2TP<0有解的充要条件是

...

AlT方程组(A1,A2,…,Al)

μ=0，

μ≥0无解。73/91如果有n维向量P使AjTP<0(j=1,2,…,l)则对于μ=(μ1,μ2,…,μl)T≥0，有μ1A1TP+μ2A2TP+…+μlAlTP<0但μ1A1TP+μ2A2TP+…+μlAlTP=PT(μ1A1+μ2A2+…+μlAl)，这时要说存在μ=(μ1,μ2,…,μl)T≥0，有μ1A1+μ2A2+…+μlAl=0，则产生矛盾。74/91A1A2A3PHOA1A3A2PHO(a)(b)75/91

76/91

77/91

78/91FritzJohn(1910~1994)1933在哥廷根大学学数学，当年因希特勒得势，被迫前往英国。1934年获得哥廷根大学博士学位。1935年任肯塔基大学副教授，1941年入美国籍。1943～1945于马里兰阿伯丁试验场研究弹道学，1946年到纽约大学工作，一直到退休。79/91

80/91HaroldW.KuhnProfessorEmeritusMathematicsPrincetonUniversitykuhn@math.Princeton.EDU81/91

82/91

83/91K-T条件是X*成为极小点的必要条件，但是对于凸规划，也是充分条件。84/91

85/91

86/91

87/914x1+4x2+μ1+2μ2=64x1+6x2

+μ1+3μ2=3μ1(1-x1-x2)=0μ2(4-2x1-3x2)=0μ1,μ2≥0分成几种情况：(i)μ1=μ2=0x1=3,x2=-1.5,g1(X)=1-x1-x2=1-3+1.5=-0.5<0不是K-T点。88/91(ii)μ1=0,μ2≠04x1+4x2+2μ2=64x1+6x2

+3μ2=34-2x1-3x2=0→x1

=2-1.5x2代入前两式，得μ2=-5/3<0，x1=3,x2=-2/3,不是K-T点。(iii)

μ1≠0,μ2=04x1+4x2

+μ1=64x1+6x2

+μ1=31-x1-x2=0→x1

=1-x2代入前两式，得μ1=2，x1=5/2,x2=-3/2,g2(X)=4-2x1-3x2=4-10/2+9/2=7/2>0，是K-T点。89/91(iv)μ1≠0,μ2≠04x1+4x2+μ1+2μ2=64x1+6x2

+μ1+3μ2=34-2x1-3x2=01-x1-x2=0解后两个方程，得x1=-1,x2=2,代入前两个方程μ1+2μ2=2μ1+3μ2=-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/290/91

91/914x1+4x2+μ1+2μ2-μ3=64x1+6x2

+μ1+3μ2-μ4=3μ1(1-x1-x2)=0μ2(4-2x1-3x2)=0μ3x1=0μ4x2=0μ1,μ2,μ3,μ4≥0构造如下线性规划问题：92/91Minφ(z)=z1+z24x1+4x2+

μ1+2μ2-μ3+z1=64x1+6x2+

μ1+3μ2-μ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,不能同时为基变量。93/66cj0000000011θicBxBbx1x2x3x4μ1μ2μ3μ4z1z21z16440012-10103/21z234[6]00130-1011/20x31111000000010x4423010000004/3φ(z)9-8-1000-2-51100σj1z144/30001/30-12/31-2/30x21/2[2/3]1001/61/20-1/601/60x31/21/3010-1/6-1/201/60-1/60x45/20001-1/2-3/201/20-1/2φ(z)4-4/3000-1/301-2/305/394/66cj0000000011cBxBbx1x2x3x4μ1μ2μ3μ4z1z21z130-2000-1-111-10x13/413/2001/43/40-1/401/40x31/40-1/210-1/4-3/40[1/4]0-1/40x45/20001-1/2-3/201/20-1/2φ(z)30200011-1021z1200-40[1]2-101020x111110000000-0μ410-24