運(yùn)籌學(xué)之非線性規(guī)劃培訓(xùn)講座

第六章非線性規(guī)劃1

引言非線性規(guī)劃是運(yùn)籌學(xué)中包含內(nèi)容最多，應(yīng)用最廣泛的一個(gè)分支，計(jì)算遠(yuǎn)比線性規(guī)劃復(fù)雜，由于時(shí)間的限制，只能作簡(jiǎn)單的介紹。

例

6-1

電廠投資分配問(wèn)題水電部門打算將一筆資金分配去建設(shè)

n個(gè)水電廠，其庫(kù)容量為

k

i

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

F

i

(Q)

，發(fā)電量隨庫(kù)容與徑流量而變化，以E

i

(k

i

,Q)

表示。計(jì)劃部門構(gòu)造一個(gè)模型，即在一定條件下，使總發(fā)電量年平均值最大，用數(shù)學(xué)語(yǔ)言來(lái)說(shuō)，使其期望值最大。對(duì)每個(gè)電廠

i

，其年發(fā)電量的期望值為

E

i

(k

i

,Q)

dF

i

(Q)設(shè)

V

為總投資額，

V

i

為各水電廠的投資，都是

k

i

的非線性函數(shù)，構(gòu)造非線性規(guī)劃模型如下：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利用一定的算法，可求出最優(yōu)分配

k

i*

和V

i

*

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

主要內(nèi)容非線性規(guī)劃理論方面算法方面應(yīng)用方面

對(duì)偶問(wèn)題互補(bǔ)穩(wěn)定靈敏最優(yōu)性條件無(wú)

約束問(wèn)題直接法有約束問(wè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

上的實(shí)函數(shù)。

幾個(gè)概念定義

1如果

X

滿足（

P

）的約束條件

h

i

(X)=0

(i=1,2,….m)

g

j

(X)

0

(j=1,2….l)

則稱

X

E

n

為（

P

）的一個(gè)可行解。記（

P

）的所有可行解的集合為

D

，D

稱為（

P

）可行域。

幾個(gè)概念定義

2

X

*

稱為（

P

）的一個(gè)（整體）最優(yōu)解，如果

X

*

D

，滿足f(X)

f(X

*

)

，

X

D

。

幾個(gè)概念定義

3

X

*

稱為（

P

）的一個(gè)（局部）最優(yōu)解，如果

X

*

D

，且存在一個(gè)

X

*的鄰域N(X

*

,

)=

X

E

n

X-

X

*

<

>0滿足f(X)

f(X

*

)

，

X

D

N(X

*

,

)f(X)局部最優(yōu)解整體最優(yōu)解

模型分類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

上的實(shí)函數(shù)。

模型分類

1如果

f(X)

h

i

(X)

g

j

(X)

中至少有一個(gè)函數(shù)不是線性（仿射）函數(shù)，則稱（

P

）為非線性問(wèn)題。如果

f(X)

h

i

(X)

g

j

(X)

都是線性（仿射）函數(shù)，則稱（

P

）為線性問(wèn)題。

模型分類

2o

若

m=l=0

，則稱（

P

）為無(wú)約束問(wèn)題。（

P

1

）

Min

f(X)X

E

n

模型分類

2o

若

m

0

，

l=0

，則稱（

P

）為帶等式約束問(wèn)題。（

P

2

）

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

h

i

(X)=0X

E

n

模型分類

2o

若

m=0

，

l

0

，則稱（

P

）為帶不等式約束問(wèn)題。（

P

3

）Min

f(X)

s.t.

g

j

(X)

0

(j=1,2….l)

X

E

n

模型分類

2o

若

m

0

，

l

0

，則稱（

P

）為一般問(wèn)題。（

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

凸函數(shù)的概念凸集概念：

設(shè)

D

是

n

維線性空間

E

n

的一個(gè)點(diǎn)集，若

D

中的任意兩點(diǎn)

x

(1)

,x

(2)

的連線上的一切點(diǎn)

x

仍在

D

中，則稱

D

為凸集。即：若

D

中的任意兩點(diǎn)

x

(1)

,x

(2)

∈

D

，存在

0<

<1

使得x=

x

(1)

+(1-

)x

(2)

∈

D,

則稱

D

為凸

凸函數(shù)的概念定義：定義在凸集

D

E

n

上的函數(shù)

f(X)如果對(duì)任意兩點(diǎn)

x

(1)

,x

(2)

∈

D

，均有0<

<1

使得f(

x

(1)

+(1-

)x

(2)

)

f(

x

(1)

)

+(1-

)

f(x

(2)

)則稱函數(shù)

f(X)

為

D

上的凸函數(shù)

.

凸函數(shù)的概念若嚴(yán)格不等式成立

,

則稱函數(shù)

f(X)

為

D

上的嚴(yán)格凸函數(shù)

.如果

-

g(X)

為

D

上的

(

嚴(yán)格

)

凸函數(shù)

,

則g(X)

為

D

上的

(

嚴(yán)格

)

凹函數(shù)

.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)

任意兩點(diǎn)的函數(shù)值的連線上的點(diǎn)都在曲線的上方線性函數(shù)既是凸函數(shù)

,

又是凹函數(shù)

,反之也然

.

梯度向量

f(X)=grad

f(X)=(

f/

x

1

,

f/

x

2

,…..,

f/

x

n

)

正定矩陣如果對(duì)矩陣

H(X),

對(duì)任意

X

N(X

*

,

)Z

E

n

均有

Z

T

H(X)Z

>

0(

0

)則稱

H(X)

在

X

*

點(diǎn)正定

(

半正定

).

海賽

(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

最優(yōu)性條件

最優(yōu)性條件的研究是非線性規(guī)劃理論研究的一個(gè)中心問(wèn)題。

為什么要研究最優(yōu)性條件？o

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

它是許多算法設(shè)計(jì)的基礎(chǔ)。

無(wú)約束問(wèn)題的最優(yōu)性條件（

P

1

）Min

f(X)

X

E

n定理

1

（一階必要條件）

設(shè)

f(X)

在

X

*

點(diǎn)可微，則

X

*

為（

P

1

）

的一個(gè)局部最優(yōu)解，一定有

f(X

*

)=grad

f(X

*

)=0

（

X

*

稱為駐點(diǎn)

）

無(wú)約束問(wèn)題的最優(yōu)性條件（

P

1

）Min

f(X)

X

E

n定理

2

（二階必要條件）

設(shè)

f(X)

在

X

*

點(diǎn)二階可微，如果

X

*

為（

P

1

）

的一個(gè)局部最優(yōu)解，則有

f(X

*

)

=0

和

H

（

X

*

）為半正定。

無(wú)約束問(wèn)題的最優(yōu)性條件（

P

1

）Min

f(X)

X

E

n定理

3

（二階充分條件）

設(shè)

f(X)

在

X

*

點(diǎn)二階可微，如果

f(X

*

)

=0

和

H(X

*

)

為正定，則

X

*

為(P

1

)

的一個(gè)局部最優(yōu)解。（

H(X)

在

X

*的鄰域內(nèi)為半正定。

無(wú)約束問(wèn)題的最優(yōu)性條件（

P

1

）Min

f(X)

X

E

n定理

4

（一階充分條件）

設(shè)

f(X)

為

E

n

上的凸函數(shù)，又設(shè)

f(X)在

X

*

點(diǎn)可微，如果

f(X

*

)

=0

，則

X

*

為(P

1

)

的一個(gè)整體最優(yōu)解。例

6-2

Min

f(X)=

（

x

2

-1)

3X

E

1解：

利用一階必要條件求出有可能成為最優(yōu)解的那些點(diǎn)

:

f(X)

=

6x(x

2

-1)

2

=0

得到：x

1

=0,x

2

=1,x

3

=

-1進(jìn)一步考慮二階必要條件，縮小范圍：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

點(diǎn)正定，依二階必要條件，x

1

=0

為（

P

1

）的局部最優(yōu)解。而

x

2

=1

，x

3

=

-1

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

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駐點(diǎn)

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)

為最優(yōu)解。f(X*)=0解無(wú)約束問(wèn)題的算法：

求

f(X)

的駐點(diǎn)

X*

，若是凸函數(shù)，得到最優(yōu)解。否則，轉(zhuǎn)下一步。

在駐點(diǎn)

X*

處，計(jì)算

H(x)

。

根據(jù)

H(x)

來(lái)判斷該駐點(diǎn)

X*

是否是極值點(diǎn)。o

若

H(x)

為正定，該駐點(diǎn)

X*

是嚴(yán)格局部極小值點(diǎn)；o

若

H(x)

為負(fù)定，該駐點(diǎn)

X*

是嚴(yán)格局部極大值點(diǎn)；o

若

H(x)

為半正定（半負(fù)定）則進(jìn)一步觀察它在該點(diǎn)某鄰域內(nèi)的情況，如果保持半正定（半負(fù)定），那它們是嚴(yán)格局部極小值點(diǎn)（極大值點(diǎn)）；o

如果

H(x)

不定的，該駐點(diǎn)

X*

就不是f(X)

極值點(diǎn)。例

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駐點(diǎn)

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ù)定，

f(X)

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

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

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

帶不等式約束問(wèn)題的最優(yōu)性條件（

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

必要條件）

設(shè)

f(X)

和每個(gè)

g

j

(X)

在

X

*

D

點(diǎn)可微，又設(shè)

g

j

(X)

(

j

J

（

X*

）

)

線性無(wú)關(guān)，如果

X

*

為（

P

3

）的局部最優(yōu)解，則存在（

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

（一階充分條件）

設(shè)

f(X)

和每個(gè)

g

j

(X)

都是

E

n

中的凸函數(shù)，且在

X

*

D

點(diǎn)可微，如果存在（

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

）的一個(gè)最優(yōu)解。

一般問(wèn)題的最優(yōu)性條件（

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

必要條件）

設(shè)

f(X)

和每個(gè)

g

j

(X)

在

X

*

D

點(diǎn)可微，每個(gè)h

i

(X)

在

X

*

D

點(diǎn)連續(xù)可微

,

又設(shè)

g

j

(X)(

j

J(X*))

和

h

i

(X)

線性無(wú)關(guān)

,

如果

X

*

為

(P)

的局部最優(yōu)解

,

一定存在

(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

充分條件）

設(shè)

f(X)

和每個(gè)

g

j

(X)

都是

E

n

中的凸函數(shù)，每個(gè)

g

j

(X)

都是線性函數(shù)，如果存在（

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

*

)