清华大学运筹学非线性规划-课件

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

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代替之。3非线性规划数学模型一般形式：3

4

4A(0,5)BCD(4,1)1O125x1x2345A(0,5)BCD(4,1)1O125x1x2345

6

6

7

7

8

8

9

9AT=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相应地称正定、负定、不定、半定。10AT=A，即aji=aij。若aij均为实数，则称f(实二次型f(X)=XTAX为正定的充要条件是：>0a11>0，|a11a12||a11a12a13||a21a22|>0

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

|...|>0|...||...||an1an2…ann|11实二次型f(X)=XTAX为正定的充要条件是：>011实二次型f(X)=XTAX为负定的充要条件是：a11<0，|a11a12||a11a12a13||a21a22|>0

|a21a22a23|<0…|a31a32a33||a11a12…a1n||a21a22…a2n|(-1)n|...|>0|...||...||an1an2…ann|12实二次型f(X)=XTAX为负定的充要条件是：12

[例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为不定。

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

14

14

15

15

16

16

17

17

18

18

19

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

x(1)x(2)

21xf(x)f(x(2))f(x(1))

x(1)x(2xf(x)f(x(2))f(x(1))

x(1)x(2)

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

x(1)x(2xf(x)f(x(2))f(x(1))

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

x(1)x(2性质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.凸函数的判定可直接从定义出发。但是，对于可微凸函数，也可利用如下两个条件：24性质2推论24

25

25

26

26

27

27

28

28ORcx1x2

29ORcx1x2

29

30

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

s.t.

gj(X)≥0，(j=1,2,…,l)f(X)和-gj(X)(j=1,2,…,l)均为凸函数。31凸规划性质31

32

32

33

33[例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)，有34[例4]验证如下非线性规划为凸规划：34

35

350Rcx1x2

●1.0g1(X)=0g2(X)=0360Rcx1x2

●1.0g1(X)=0g2(X)=036

37

37目标函数求最小的规划问题，应有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)，使得38目标函数求最小的规划问题，应有f(X(0))>f(X(1))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))，故称这一过程为（最优）一维搜索或线搜索。如此确定的步长，称为最优步长。39f(X(k))>f(X(k+1))=f(X(k)+λkP(

40

40

41

41

42

42

43

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

46

46

47

47

48

48

49

49

50

50

51

51

52

52

53

53

54

545555[例9]人工神经网络模仿人脑神经网络，将具有识别、记忆功能的人工神经元以各种不同的方式连接成不同的网络。用于计算、分类、模式识别、评价、预测、控制、智能机器人、数据挖掘等领域。1.人工神经元与感知机(1)神经元感知功能人工神经元（感知机）56[例9]人工神经网络56

57

57

58

58

59

59

60

60

61

61

62

62

63

63

先赋予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先赋予w=(w1,w2,…,wm)T一

65

65

66

66

67

67

68

68

69

69

70

70

71

71

72

72第四节约束极值问题73第四节约束极值问题73

74

74

75

750Rcx1x2

●1.0g1(X)=0g2(X)=0黑色方向不可行760Rcx1x2

●1.0g1(X)=0g2(X)=0黑色方

77

77

78

78

79

79

80

80【例】Min

f(x)=-4x1-6x2+2x12+2x1x2+2x22

s.t.-x1-2x2+2≥0，1≥x1≥0，x2≥0x=(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)T81【例】81记x(0)=(1/2,3/4)Tg1(x(0))=-1/2-2(3/4)+2=0g2(x(0))=1-1/2=1/2>0g3(x(0))=3/4>0所以，在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

82记x(0)=(1/2,3/4)T82x1x2x(0)不是解。因在𝛁f(x(0))和𝛁g1(x(0))之间，可找到一个方向P，使得𝛁f(x(0))TP<0，𝛁g1(x(0))TP>0同时成立，即P同𝛁f(x(0))成钝角，而同𝛁g1(x(0))成锐角。121P𝛁f(x(0))𝛁g1(x(0))x(0)83x1x2x(0)不是解。121P𝛁f(x(0))𝛁g1(或者，令P=(p1，p2)T，下列不等式组有解：𝛁f(x(0))TP=-p1/2-2p2<0𝛁g1(x(0))TP=-p1-2p2>0只须令p1=-1，p2=3/8即可，所以，x(0)=(1/2,3/4)T不是问题的解。84或者，令P=(p1，p2)T，842.库恩塔克条件Kuhn-Tucker先讲几个预备性定理。(1)Gordan引理设A1,A2,…,Al是l个n维向量，不存在n维向量P使AjTP<0(j=1,2,…,l)成立的充要条件是，存在不全为零的非负实数μ1,μ2,…,μl，使μ1A1+μ2A2+…+μlAl=0几何意义明显。852.库恩塔克条件Kuhn-Tucker85Gordan引理设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无解。86Gordan引理设A1,A2,…,Al是l个n维向如果有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，则产生矛盾。87如果有n维向量P使AjTP<0(j=1,2,A1A2A3PHOA1A3A2PHO(a)(b)88A1A2A3PHOA1A3A2PHO(a)(b)88

89

89

90

90

91

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

93

93HaroldW.KuhnProfessorEmeritusMathematicsPrincetonUniversity94HaroldW.Kuhn94

95

95

96

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

98

98

99

99

100

1004x1+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点。1014x1+4x2+μ1+2μ2=6101(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点。102(ii)μ1=0,μ2≠0102(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/2103(iv)μ1≠0,μ2≠0103

104

1044x1+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构造如下线性规划问题：1054x1+4x2+μ1+2μ2-μ3=6105Minφ(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,不能同时为基变量。106Minφ(z)=z1+z2106cj0000000011θicBxBbx1x2x3x4μ1μ2μ3μ4z1z21z16440012-10103/21z234[6]00130-1011/20x31111000000010x4423010000004/3φ(z)9-8-1000-2-51100σj1z144/30001/30-