清華大學(xué)運籌學(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中的點，目標(biāo)函數(shù)f(X)，約束函數(shù)hi(X)和gj(X)是X實函數(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ù)，則稱f(X)=XTAX為實二次型。A與二次型一一對應(yīng)。(1)若對于非零X，實二次型總有XTAX>0，則稱為正定的；(2)若對于非零X，實二次型總有XTAX<0，則稱為負(fù)定的；(3)若對于某些非零X，XTAX>0，而對另一些非零X，XTAX<0，則稱為不定的；(4)若對任意非零X，XTAX≥0，則稱為半正定的。若對任意非零X，XTAX≤0，則稱為半負(fù)定的。(5)A相應(yīng)地稱正定、負(fù)定、不定、半定。10AT=A，即aji=aij。若aij均為實數(shù)，則稱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為負(fù)定的充要條件是：a11<0，|a11a12||a11a12a13||a21a22|>0

|a21a22a23|<0…|a31a32a33||a11a12…a1n||a21a22…a2n|(-1)n|...|>0|...||...||an1an2…ann|12實二次型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ù)，則對于任何實數(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ù)，則對于每一個實數(shù)β≥0，集合（稱為水平集）

Sβ={X|X∈Rc，f(X)≤β}是凸集。3.凸函數(shù)的判定可直接從定義出發(fā)。但是，對于可微凸函數(shù)，也可利用如下兩個條件：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)任何局部極值點也是全局極值點。(4)若目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)，且有最優(yōu)解，則該最優(yōu)解唯一。以下驗證上述四個性質(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]驗證如下非線性規(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ù)。

對于g2(X)，有34[例4]驗證如下非線性規(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)不是極小點，就確定一個方向P(k)，使目標(biāo)函數(shù)沿此方向能夠下降，但不要越出可行域。(3)確定步長。沿P(k)前進(jìn)一定距離（步長），到達(dá)新點X(k+1)。即在從X(k)出發(fā)的射線X=X(k)+λP(k)上(λ≥0)，選擇一個λk，到達(dá)新點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)檢查新點是否或接近極小點。若是，停。否則，k:=k+1，返回(2)繼續(xù)迭代。已有不少辦法確定搜索方向P(k)。多數(shù)按使目標(biāo)函數(shù)下快最快的原則確定步長，即求解一維問題f(X(k)+λkP(k))=minf(X(k)+λP(k))，故稱這一過程為（最優(yōu)）一維搜索或線搜索。如此確定的步長，稱為最優(yōu)步長。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ò)，將具有識別、記憶功能的人工神經(jīng)元以各種不同的方式連接成不同的網(wǎng)絡(luò)。用于計算、分類、模式識別、評價、預(yù)測、控制、智能機(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一個初始值，然后逐步調(diào)整，使其逐步逼近極值點w*=(w*1,w*2,…,w*m)T，調(diào)整方向P=(p1,p2,…,pm)T，調(diào)整量是λP，步長λ就是上面的“學(xué)習(xí)系數(shù)”。當(dāng)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第四節(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))之間，可找到一個方向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先講幾個預(yù)備性定理。(1)Gordan引理設(shè)A1,A2,…,Al是l個n維向量，不存在n維向量P使AjTP<0(j=1,2,…,l)成立的充要條件是，存在不全為零的非負(fù)實數(shù)μ1,μ2,…,μl，使μ1A1+μ2A2+…+μlAl=0幾何意義明顯。852.庫恩塔克條件Kuhn-Tucker85Gordan引理設(shè)A1,A2,…,Al是l個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個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，則產(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)年因希特勒得勢，被迫前往英國。1934年獲得哥廷根大學(xué)博士學(xué)位。1935年任肯塔基大學(xué)副教授，1941年入美國籍。1943～1945于馬里蘭阿伯丁試驗場研究彈道學(xué)，1946年到紐約大學(xué)工作，一直到退休。92FritzJohn(1910~1994)1933在哥廷根大

93

93HaroldW.KuhnProfessorEmeritusMathematicsPrincetonUniversity94HaroldW.Kuhn94

95

95

96

96K-T條件是X*成為極小點的必要條件，但是對于凸規(guī)劃，也是充分條件。97K-T條件是X*成為極小點的必要條件，但是對于凸規(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點。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構(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,不能同時為基變量。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-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/3107cj0000000011cBxBbx1x2x3x4μ1μ2μcj0000000011cBxBbx1x2x3x4μ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-240-1-3010-1-0x4201-21000000-φ(z)30040-1-21001x4和μ2不能同時為基變量，所以，μ2不能換入，μ1換入。108cj0000000011cBxBbx1x2x3x4μ1μ2μcj0000000011cBxBbx1x2x3x4μ1μ2μ3μ4z1z20μ1200-40[1]2-101020x111110000000-0μ430-2000-1-111-1-0x4201-21000000-φ(z)00000000011X*=(x1,x2,x3,

x4,

μ1,μ2,μ3,μ4)T

=(1,0,0,2,

2,0,0,3)T，

f(X*)=2x12+4x1x2+3x22-6x1-3x2=2-6=-4109cj0000000011cBxBbx1x2x3x4μ1μ2μ第六章非線性規(guī)劃第一節(jié)基本概念第三節(jié)無約束極值問題第四節(jié)約束極值問題110第六章非線性規(guī)劃第一節(jié)基本概念1第一節(jié)基本概念一、非線性規(guī)劃數(shù)學(xué)模型111第一節(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中的點，目標(biāo)函數(shù)f(X)，約束函數(shù)hi(X)和gj(X)是X實函數(shù)。有時，非線性規(guī)劃數(shù)學(xué)模型寫成：Minf(X)

s.t.

gj(X)≥0，(j=1,2,…,l)若某gj(X)=0，可以gj(X)≥0和-gj(X)≥0代替之。112非線性規(guī)劃數(shù)學(xué)模型一般形式：3

113

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

115

6

116

7

117

8

118

9AT=A，即aji

=aij。若aij均為實數(shù)，則稱f(X)=XTAX為實二次型。A與二次型一一對應(yīng)。(1)若對于非零X，實二次型總有XTAX>0，則稱為正定的；(2)若對于非零X，實二次型總有XTAX<0，則稱為負(fù)定的；(3)若對于某些非零X，XTAX>0，而對另一些非零X，XTAX<0，則稱為不定的；(4)若對任意非零X，XTAX≥0，則稱為半正定的。若對任意非零X，XTAX≤0，則稱為半負(fù)定的。(5)A相應(yīng)地稱正定、負(fù)定、不定、半定。119AT=A，即aji=aij。若aij均為實數(shù)，則稱f(實二次型f(X)=XTAX為正定的充要條件是：>0a11>0，|a11a12||a11a12a13||a21a22|>0

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

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

|a21a22a23|<0…|a31a32a33||a11a12…a1n||a21a22…a2n|(-1)n|...|>0|...||...||an1an2…ann|121實二次型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為不定。

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

123

14

124

15

125

16

126

17

127

18

128

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ù)，則對于任何實數(shù)β≥0，βf(X)也是定義在Rc上凸函數(shù)。性質(zhì)2設(shè)f1(X)和f2(X)均為定義在凸集Rc上凸函數(shù)，則f(X)=f1(X)+f2(X)也是定義在Rc上凸函數(shù)。129顛倒上述定義中不等式方向，可得凹和嚴(yán)格凹函數(shù)的定義。20xf(x)f(x(2))f(x(1))

x(1)x(2)

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

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

x(1)x(2)

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

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

x(1)x(2)132xf(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ù)，則對于每一個實數(shù)β≥0，集合（稱為水平集）

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

134

25

135

26

136

27

137

28ORcx1x2

138ORcx1x2

29

139

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

s.t.

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

141

32

142

33[例4]驗證如下非線性規(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ù)。

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

144

350Rcx1x2

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

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

146

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

149

40

150

41

151

42

152

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

155

46

156

47

157

48

158

49

159

50

160

51

161

52

162

53

163

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

166

57

167

58

168

59

169

60

170

61

171

62

172

63

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

174

65

175

66

176

67

177

68

178

69

179

70

180

71

181

72第四節(jié)約束極值問題182第四節(jié)約束極值問題73

183

74

184

750Rcx1x2

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

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

186

77

187

78

188

79

189

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)T190【例】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

191記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)192x1x2x(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不是問題的解。193或者，令P=(p1，p2)T，842.庫恩塔克條件Kuhn-Tucker先講幾個預(yù)備性定理。(1)Gordan引理設(shè)A1,A2,…,Al是l個n維向量，不存在n維向量P使AjTP<0(j=1,2,…,l)成立的充要條件是，存在不全為零的非負(fù)實數(shù)μ1,μ2,…,μl，使μ1A1+μ2A2+…+μlAl=0幾何意義明顯。1942.庫恩塔克條件Kuhn-Tucker85Gordan引理設(shè)A1,A2,…,Al是l個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無解。195Gordan引理設(shè)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，則產(chǎn)生矛盾。196如果有n維向量P使AjTP<0(j=1,2,A1A2A3PHOA1A3A2PHO(a)(b)197A1A2A3PHOA1A3A2PHO(a)(b)88

198

89

199

90

200

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

202

93HaroldW.KuhnProfessorEmeritusMathematicsPrincetonUniversity203HaroldW.Kuhn94

204

95

205

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

207

98

208

99

209

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點。2104x1+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點。211(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點。所以