清華大學(xué)運(yùn)籌學(xué)非線性規(guī)劃-課件

第六章非線性規(guī)劃第一節(jié)基本概念第三節(jié)無約束極值問題第四節(jié)約束極值問題1第六章非線性規(guī)劃第一節(jié)基本概念1第一節(jié)基本概念一、非線性規(guī)劃數(shù)學(xué)模型2第一節(jié)基本概念一、非線性規(guī)劃數(shù)學(xué)模型2非線性規(guī)劃數(shù)學(xué)模型一般形式：

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中的點(diǎn)，目標(biāo)函數(shù)f(X)，約束函數(shù)hi(X)和gj(X)是X實(shí)函數(shù)。有時(shí)，非線性規(guī)劃數(shù)學(xué)模型寫成：Minf(X)

s.t.

gj(X)≥0，(j=1,2,…,l)若某gj(X)=0，可以gj(X)≥0和-gj(X)≥0代替之。3非線性規(guī)劃數(shù)學(xué)模型一般形式：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均為實(shí)數(shù)，則稱f(X)=XTAX為實(shí)二次型。A與二次型一一對(duì)應(yīng)。(1)若對(duì)于非零X，實(shí)二次型總有XTAX>0，則稱為正定的；(2)若對(duì)于非零X，實(shí)二次型總有XTAX<0，則稱為負(fù)定的；(3)若對(duì)于某些非零X，XTAX>0，而對(duì)另一些非零X，XTAX<0，則稱為不定的；(4)若對(duì)任意非零X，XTAX≥0，則稱為半正定的。若對(duì)任意非零X，XTAX≤0，則稱為半負(fù)定的。(5)A相應(yīng)地稱正定、負(fù)定、不定、半定。10AT=A，即aji=aij。若aij均為實(shí)數(shù)，則稱f(實(shí)二次型f(X)=XTAX為正定的充要條件是：>0a11>0，|a11a12||a11a12a13||a21a22|>0

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

|...|>0|...||...||an1an2…ann|11實(shí)二次型f(X)=XTAX為正定的充要條件是：>011實(shí)二次型f(X)=XTAX為負(fù)定的充要條件是：a11<0，|a11a12||a11a12a13||a21a22|>0

|a21a22a23|<0…|a31a32a33||a11a12…a1n||a21a22…a2n|(-1)n|...|>0|...||...||an1an2…ann|12實(shí)二次型f(X)=XTAX為負(fù)定的充要條件是：12

[例1]判定如下二次型的性質(zhì)。

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

-5<0，|-5

2

|=26>0|-522||2-6||2-60|=-80<0|20-4|矩陣A為負(fù)定。矩陣B：b11=0，|0

1

|=-1<0|10|矩陣B為不定。

13[例1]判定如下二次型的性質(zhì)。13

14

14

15

15

16

16

17

17

18

18

19

19顛倒上述定義中不等式方向，可得凹和嚴(yán)格凹函數(shù)的定義。若f(X)是（嚴(yán)格）凸函數(shù)，則g(X)=-f(X)是（嚴(yán)格）凹函數(shù)。（幾何意義見下圖）2.凸函數(shù)性質(zhì)性質(zhì)1設(shè)f(X)為定義在凸集Rc上凸函數(shù)，則對(duì)于任何實(shí)數(shù)β≥0，βf(X)也是定義在Rc上凸函數(shù)。性質(zhì)2設(shè)f1(X)和f2(X)均為定義在凸集Rc上凸函數(shù)，則f(X)=f1(X)+f2(X)也是定義在Rc上凸函數(shù)。20顛倒上述定義中不等式方向，可得凹和嚴(yán)格凹函數(shù)的定義。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性質(zhì)2推論若干凸函數(shù)非負(fù)線性組合β1f1(X)+β2f2(X)+…+βmfm(X)仍為凸集Rc上的凸函數(shù)。βi≥0(i=1,2,…,m)性質(zhì)3設(shè)f(X)為凸集Rc上的凸函數(shù)，則對(duì)于每一個(gè)實(shí)數(shù)β≥0，集合（稱為水平集）

Sβ={X|X∈Rc，f(X)≤β}是凸集。3.凸函數(shù)的判定可直接從定義出發(fā)。但是，對(duì)于可微凸函數(shù)，也可利用如下兩個(gè)條件：24性質(zhì)2推論24

25

25

26

26

27

27

28

28ORcx1x2

29ORcx1x2

29

30

30凸規(guī)劃性質(zhì)(1)可行解集為凸集。(2)若有最優(yōu)解，則最優(yōu)解集為凸集。(3)任何局部極值點(diǎn)也是全局極值點(diǎn)。(4)若目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)，且有最優(yōu)解，則該最優(yōu)解唯一。以下驗(yàn)證上述四個(gè)性質(zhì)：考慮凸規(guī)劃Minf(X)

s.t.

gj(X)≥0，(j=1,2,…,l)f(X)和-gj(X)(j=1,2,…,l)均為凸函數(shù)。31凸規(guī)劃性質(zhì)31

32

32

33

33[例4]驗(yàn)證如下非線性規(guī)劃為凸規(guī)劃：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的線性函數(shù)，也是凹函數(shù)。

對(duì)于g2(X)，有34[例4]驗(yàn)證如下非線性規(guī)劃為凸規(guī)劃：34

35

350Rcx1x2

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

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

37

37目標(biāo)函數(shù)求最小的規(guī)劃問題，應(yīng)有f(X(0))>f(X(1))>f(X(2))>f(X(3))>…>f(X(k))>…這就是下降迭代算法。該算法一般格式與步驟：(1)選取初始X(0)，k:=0;(2)確定下降方向。若已到達(dá)的X(k)不是極小點(diǎn)，就確定一個(gè)方向P(k)，使目標(biāo)函數(shù)沿此方向能夠下降，但不要越出可行域。(3)確定步長(zhǎng)。沿P(k)前進(jìn)一定距離（步長(zhǎng)），到達(dá)新點(diǎn)X(k+1)。即在從X(k)出發(fā)的射線X=X(k)+λP(k)上(λ≥0)，選擇一個(gè)λk，到達(dá)新點(diǎn)X(k+1)=X(k)+λkP(k)，使得38目標(biāo)函數(shù)求最小的規(guī)劃問題，應(yīng)有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)檢查新點(diǎn)是否或接近極小點(diǎn)。若是，停。否則，k:=k+1，返回(2)繼續(xù)迭代。已有不少辦法確定搜索方向P(k)。多數(shù)按使目標(biāo)函數(shù)下快最快的原則確定步長(zhǎng)，即求解一維問題f(X(k)+λkP(k))=minf(X(k)+λP(k))，故稱這一過程為（最優(yōu)）一維搜索或線搜索。如此確定的步長(zhǎng)，稱為最優(yōu)步長(zhǎng)。39f(X(k))>f(X(k+1))=f(X(k)+λkP(

40

40

41

41

42

42

43

43第三節(jié)無約束極值問題44第三節(jié)無約束極值問題44無約束極值問題表示Minf(X)，X∈Rc前文已指出，須用迭代法求解。迭代法有解析法和直接法兩類。解析法要用到目標(biāo)函數(shù)一階和二階導(dǎo)數(shù)。直接法不用，只用目標(biāo)函數(shù)值。有些目標(biāo)函數(shù)沒有導(dǎo)數(shù)，只能用直接法。45無約束極值問題表示45

46

46

47

47

48

48

49

49

50

50

51

51

52

52

53

53

54

545555[例9]人工神經(jīng)網(wǎng)絡(luò)模仿人腦神經(jīng)網(wǎng)絡(luò)，將具有識(shí)別、記憶功能的人工神經(jīng)元以各種不同的方式連接成不同的網(wǎng)絡(luò)。用于計(jì)算、分類、模式識(shí)別、評(píng)價(jià)、預(yù)測(cè)、控制、智能機(jī)器人、數(shù)據(jù)挖掘等領(lǐng)域。1.人工神經(jīng)元與感知機(jī)(1)神經(jīng)元感知功能人工神經(jīng)元（感知機(jī)）56[例9]人工神經(jīng)網(wǎng)絡(luò)56

57

57

58

58

59

59

60

60

61

61

62

62

63

63

先賦予w=(w1,w2,…,wm)T一個(gè)初始值，然后逐步調(diào)整，使其逐步逼近極值點(diǎn)w*=(w*1,w*2,…,w*m)T，調(diào)整方向P=(p1,p2,…,pm)T，調(diào)整量是λP，步長(zhǎng)λ就是上面的“學(xué)習(xí)系數(shù)”。當(dāng)P=-▽f(w)時(shí)，總誤差f(w)下降最快。64先賦予w=(w1,w2,…,wm)T一

65

65

66

66

67

67

68

68

69

69

70

70

71

71

72

72第四節(jié)約束極值問題73第四節(jié)約束極值問題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))之間，可找到一個(gè)方向P，使得??f(x(0))TP<0，??g1(x(0))TP>0同時(shí)成立，即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先講幾個(gè)預(yù)備性定理。(1)Gordan引理設(shè)A1,A2,…,Al是l個(gè)n維向量，不存在n維向量P使AjTP<0(j=1,2,…,l)成立的充要條件是，存在不全為零的非負(fù)實(shí)數(shù)μ1,μ2,…,μl，使μ1A1+μ2A2+…+μlAl=0幾何意義明顯。852.庫恩塔克條件Kuhn-Tucker85Gordan引理設(shè)A1,A2,…,Al是l個(gè)n維向量，AjTP<0(j=1,2,…,l)成立的充要條件是，不存在μ=(μ1,μ2,…,μl)T≥0，使μ1A1+μ2A2+…+μlAl=0成立?；騁ordan引理

A1T方程組

A2TP<0有解的充要條件是...

AlT方程組(A1,A2,…,Al)μ=0，μ≥0無解。86Gordan引理設(shè)A1,A2,…,Al是l個(gè)n維向如果有n維向量P使AjTP<0(j=1,2,…,l)則對(duì)于μ=(μ1,μ2,…,μl)T≥0，有μ1A1TP+μ2A2TP+…+μlAlTP<0但μ1A1TP+μ2A2TP+…+μlAlTP=PT(μ1A1+μ2A2+…+μlAl)，這時(shí)要說存在μ=(μ1,μ2,…,μl)T≥0，有μ1A1+μ2A2+…+μlAl=0，則產(chǎn)生矛盾。87如果有n維向量P使AjTP<0(j=1,2,A1A2A3PHOA1A3A2PHO(a)(b)88A1A2A3PHOA1A3A2PHO(a)(b)88

89

89

90

90

91

91FritzJohn(1910~1994)1933在哥廷根大學(xué)學(xué)數(shù)學(xué)，當(dāng)年因希特勒得勢(shì)，被迫前往英國(guó)。1934年獲得哥廷根大學(xué)博士學(xué)位。1935年任肯塔基大學(xué)副教授，1941年入美國(guó)籍。1943～1945于馬里蘭阿伯丁試驗(yàn)場(chǎng)研究彈道學(xué)，1946年到紐約大學(xué)工作，一直到退休。92FritzJohn(1910~1994)1933在哥廷根大

93

93HaroldW.KuhnProfessorEmeritusMathematicsPrincetonUniversity94HaroldW.Kuhn94

95

95

96

96K-T條件是X*成為極小點(diǎn)的必要條件，但是對(duì)于凸規(guī)劃，也是充分條件。97K-T條件是X*成為極小點(diǎn)的必要條件，但是對(duì)于凸規(guī)劃，也是充

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點(diǎn)。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點(diǎn)。(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點(diǎn)。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解后兩個(gè)方程，得x1=-1,x2=2,代入前兩個(gè)方程μ1+2μ2=2μ1+3μ2=-5，得μ1=16,μ2=-7,不是K-T點(diǎn)。所以，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構(gòu)造如下線性規(guī)劃問題：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,不能同時(shí)為基變量。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-