第六章非線性規劃1

引言非線性規劃是運籌學中包含內容最多，應用最廣泛的一個分支，計算遠比線性規劃復雜，由于時間的限制，只能作簡單的介紹。

例

6-1

電廠投資分配問題水電部門打算將一筆資金分配去建設

n個水電廠，其庫容量為

k

i

,i=1,2….n,各電廠水庫徑流輸入量分布為

F

i

(Q)

，發電量隨庫容與徑流量而變化，以E

i

(k

i

,Q)

表示。計劃部門構造一個模型，即在一定條件下，使總發電量年平均值最大，用數學語言來說，使其期望值最大。對每個電廠

i

，其年發電量的期望值為

E

i

(k

i

,Q)

dF

i

(Q)設

V

為總投資額，

V

i

為各水電廠的投資，都是

k

i

的非線性函數，構造非線性規劃模型如下：Max

E

i

(k

i

,Q)

dF

i

(Q)

1

(k

1

)+

V

2

(k

2

)+……

+

V

n

(k

n

)=VV

1

(k

1

),

V

2

(k

2

),……,V

n

(k

n

)

0利用一定的算法，可求出最優分配

k

i*

和V

i

*

(i=1,2,….n).

主要內容非線性規劃理論方面算法方面應用方面

對偶問題互補穩定靈敏最優性條件無

約束問題直接法有約束問題間接法

一般模型Min

f(X)s.t.

h

i

(X)

=

0(i=1,2,….m)（

P

）

g

j

(X)

0

(j=1,2….l)

X

E

n

f(X)

h

i

(X)

g

j

(X)

為

E

n

上的實函數。

幾個概念定義

1如果

X

滿足（

P

）的約束條件

h

i

(X)=0

(i=1,2,….m)

g

j

(X)

0

(j=1,2….l)

則稱

X

E

n

為（

P

）的一個可行解。記（

P

）的所有可行解的集合為

D

，D

稱為（

P

）可行域。

幾個概念定義

2

X

*

稱為（

P

）的一個（整體）最優解，如果

X

*

D

，滿足f(X)

f(X

*

)

，

X

D

。

幾個概念定義

3

X

*

稱為（

P

）的一個（局部）最優解，如果

X

*

D

，且存在一個

X

*的鄰域N(X

*

,

)=

X

E

n

X-

X

*

<

>0滿足f(X)

f(X

*

)

，

X

D

N(X

*

,

)f(X)局部最優解整體最優解

模型分類Min

f(X)s.t.

h

i

(X)=0

(i=1,2,….m)（

P

）

g

j

(X)

0

(j=1,2….l)

X

E

n

f(X)

h

i

(X)

g

j

(X)

為

E

n

上的實函數。

模型分類

1如果

f(X)

h

i

(X)

g

j

(X)

中至少有一個函數不是線性（仿射）函數，則稱（

P

）為非線性問題。如果

f(X)

h

i

(X)

g

j

(X)

都是線性（仿射）函數，則稱（

P

）為線性問題。

模型分類

2o

若

m=l=0

，則稱（

P

）為無約束問題。（

P

1

）

Min

f(X)X

E

n

模型分類

2o

若

m

0

，

l=0

，則稱（

P

）為帶等式約束問題。（

P

2

）

Minf(X)(i=1,2,….m)s.t.

h

i

(X)=0X

E

n

模型分類

2o

若

m=0

，

l

0

，則稱（

P

）為帶不等式約束問題。（

P

3

）Min

f(X)

s.t.

g

j

(X)

0

(j=1,2….l)

X

E

n

模型分類

2o

若

m

0

，

l

0

，則稱（

P

）為一般問題。（

P

）Min

f(X)s.t.

h

i

(X)=0(i=1,2,….m)

g

j

(X)

0

(j=1,2….l)X

E

n

凸函數的概念凸集概念：

設

D

是

n

維線性空間

E

n

的一個點集，若

D

中的任意兩點

x

(1)

,x

(2)

的連線上的一切點

x

仍在

D

中，則稱

D

為凸集。即：若

D

中的任意兩點

x

(1)

,x

(2)

∈

D

，存在

0<

<1

使得x=

x

(1)

+(1-

)x

(2)

∈

D,

則稱

D

為凸

凸函數的概念定義：定義在凸集

D

E

n

上的函數

f(X)如果對任意兩點

x

(1)

,x

(2)

∈

D

，均有0<

<1

使得f(

x

(1)

+(1-

)x

(2)

)

f(

x

(1)

)

+(1-

)

f(x

(2)

)則稱函數

f(X)

為

D

上的凸函數

.

凸函數的概念若嚴格不等式成立

,

則稱函數

f(X)

為

D

上的嚴格凸函數

.如果

-

g(X)

為

D

上的

(

嚴格

)

凸函數

,

則g(X)

為

D

上的

(

嚴格

)

凹函數

.f(X)Xf(X

1

)f(X

2

)X

1X

2f(X)Xf(X

1

)f(X

2

)X

1X

2

x

1

+(1-

)x

2f(

x

1

+(1-

)x

2

)f(X)X

f(

x

1

)

+(1-

)

f(

x

2

)f(X

1

)f(X

2

)X

1X

2

x

1

+(1-

)x

2f(

x

1

+(1-

)x

2

)X

f(

x

1

)

+(1-

)

f(

x

2

)f(X

1

)f(X

2

)X

1X

2

x

1

+(1-

)x

2f(

x

1

+(1-

)x

2

)f(X)

任意兩點的函數值的連線上的點都在曲線的上方線性函數既是凸函數

,

又是凹函數

,反之也然

.

梯度向量

f(X)=grad

f(X)=(

f/

x

1

,

f/

x

2

,…..,

f/

x

n

)

正定矩陣如果對矩陣

H(X),

對任意

X

N(X

*

,

)Z

E

n

均有

Z

T

H(X)Z

>

0(

0

)則稱

H(X)

在

X

*

點正定

(

半正定

).

海賽

(Hesse)

矩陣

xx

f(X)

=

H(X)

2

f/

x

12

2

f/

x

1

x

2

…..

2

f/

x

1

x

n

2

f/

x

22…..

2

f/

x

2

x

1

2

f/

x

2

x

n……..

2

f/

x

n

x

1

2

f/

x

n

x

2

…..=2

最優性條件

最優性條件的研究是非線性規劃理論研究的一個中心問題。

為什么要研究最優性條件？o

本質上把可行解集合的范圍縮小。o

它是許多算法設計的基礎。

無約束問題的最優性條件（

P

1

）Min

f(X)

X

E

n定理

1

（一階必要條件）

設

f(X)

在

X

*

點可微，則

X

*

為（

P

1

）

的一個局部最優解，一定有

f(X

*

)=grad

f(X

*

)=0

（

X

*

稱為駐點

）

無約束問題的最優性條件（

P

1

）Min

f(X)

X

E

n定理

2

（二階必要條件）

設

f(X)

在

X

*

點二階可微，如果

X

*

為（

P

1

）

的一個局部最優解，則有

f(X

*

)

=0

和

H

（

X

*

）為半正定。

無約束問題的最優性條件（

P

1

）Min

f(X)

X

E

n定理

3

（二階充分條件）

設

f(X)

在

X

*

點二階可微，如果

f(X

*

)

=0

和

H(X

*

)

為正定，則

X

*

為(P

1

)

的一個局部最優解。（

H(X)

在

X

*的鄰域內為半正定。

無約束問題的最優性條件（

P

1

）Min

f(X)

X

E

n定理

4

（一階充分條件）

設

f(X)

為

E

n

上的凸函數，又設

f(X)在

X

*

點可微，如果

f(X

*

)

=0

，則

X

*

為(P

1

)

的一個整體最優解。例

6-2

Min

f(X)=

（

x

2

-1)

3X

E

1解：

利用一階必要條件求出有可能成為最優解的那些點

:

f(X)

=

6x(x

2

-1)

2

=0

得到：x

1

=0,x

2

=1,x

3

=

-1進一步考慮二階必要條件，縮小范圍：H(X)

=

xx

f(X)

=

6(x

2

-1)

2

+24

x

2

(x

2

-1)H(x

1

)

=

xx

f(x

1

)

=

xx

f(0)

=6>0H(x

2

)

=

xx

f(x

2

)

=

xx

f(1)

=

0H(x

3

)

=

xx

f(x

3

)

=

xx

f(-1)

=0

f(X)

在

x

1

=0

點正定，依二階必要條件，x

1

=0

為（

P

1

）的局部最優解。而

x

2

=1

，x

3

=

-1

滿足二階必要條件和一階必要條件，但它們顯然都不是最優解。例

6-3

Min

f(X)=

2x

12

+5x

22

+x

32

+

2x

2

x

3+

2x

1

x

3

-

6x

2

+3X

E

3解：

f(X)

=

（

4x

1

+

2x

3

,

10x

2

+

2x

3

–

6,

2x

1

+

2x

2

+

2x

3

）

=0駐點

x*=(1,1,-2)H(X)

=

xx

f(X)=0245

0102

26

2

2H(X)=

xx

f(X)=4025

0

26

210

204

2010=40>0各階主子式：

4>0,

4

0

2105

0

2=24>0H(X)

正定，

X*=(1,1,-2)

為最優解。f(X*)=0解無約束問題的算法：

求

f(X)

的駐點

X*

，若是凸函數，得到最優解。否則，轉下一步。

在駐點

X*

處，計算

H(x)

。

根據

H(x)

來判斷該駐點

X*

是否是極值點。o

若

H(x)

為正定，該駐點

X*

是嚴格局部極小值點；o

若

H(x)

為負定，該駐點

X*

是嚴格局部極大值點；o

若

H(x)

為半正定（半負定）則進一步觀察它在該點某鄰域內的情況，如果保持半正定（半負定），那它們是嚴格局部極小值點（極大值點）；o

如果

H(x)

不定的，該駐點

X*

就不是f(X)

極值點。例

6-4

求極值

f(X)=

x

1

+

2x

3

+x

2

x

3

-x

12

-x

22

-x

32

X

E

3解：

f(X)

=

(1-2x

1

,x

3

-2x

2

,

2+x

2

-

2x

3

)

=

0駐點

x*=(1/2,2/3,4/3)H(X)

=

xx

f(X)=-20000-2

1

1-2H(X)=

xx

f(X)=0-20-2=4>0=

-

6<0-20000-2

1

1-2各階主子式：

-2<0,

-2

000-21H(X)

負定，

f(X)

是凹函數X*=(1/2,2/3,4/3)

為極大值點。f(X*)=

f(1/2,2/3,4/3)=19/12

帶不等式約束問題的最優性條件（

P

3

）

Min

f(X)s.t.

g

j

(X)

0

(j=1,2….l)X

E

nj

g

j

(

X*

)

=0令

X*

D

，

記

J

（

X*

）

=緊約束集合。定理

5

（

Kuhn-Tucker

必要條件）

設

f(X)

和每個

g

j

(X)

在

X

*

D

點可微，又設

g

j

(X)

(

j

J

（

X*

）

)

線性無關，如果

X

*

為（

P

3

）的局部最優解，則存在（

u

1

,u

2

,…u

l

)

0,

使得?

f(X

*

)+

u

j

g

j

(X

*

)

=0g

j

(X

*

)

0u

j

g

j

(X

*

)

=0j=1,2….l

j=1,2….l定理

6

（一階充分條件）

設

f(X)

和每個

g

j

(X)

都是

E

n

中的凸函數，且在

X

*

D

點可微，如果存在（

u

1

,u

2

,…u

l

)

0,

使得?

f(X

*

)+

u

j

g

j

(X

*

)

=0g

j

(X

*

)

0u

j

g

j

(X

*

)

=0j=1,2….l

j=1,2….l則

X

*

為（

P

3

）的一個最優解。

一般問題的最優性條件（

P

）Min

f(X)s.t.

h

i

(X)=0(i=1,2,….m)

g

j

(X)

0

(j=1,2….l)X

E

n定理

7

（

Kuhn-Tucker

必要條件）

設

f(X)

和每個

g

j

(X)

在

X

*

D

點可微，每個h

i

(X)

在

X

*

D

點連續可微

,

又設

g

j

(X)(

j

J(X*))

和

h

i

(X)

線性無關

,

如果

X

*

為

(P)

的局部最優解

,

一定存在

(u

1

,u

2

,…u

l

)

0

和(v

1

,v

2

,…v

m

),

使得?

f(X

*

)+

u

j

g

j

(X

*

)

+

v

i

h

i

(X

*

)

=0j=1,2….lg

j

(X

*

)

0h

i

(X

*

)

=0u

j

g

j

(X

*

)

=0

i=1,2….m定理

8

（

Kuhn-Tucker

充分條件）

設

f(X)

和每個

g

j

(X)

都是

E

n

中的凸函數，每個

g

j

(X)

都是線性函數，如果存在（

u

1

,u

2

,…u

l

)

0,

和

(v

1

,v

2

,…v

m

),

使得?

f(X

*

)+

u

j

g

j

(X

*

)

+

v

i

h

i

(X

*

)

=0j=1,2….lg

j

(X

*

)