运筹学之非线性规划培训讲座

第六章非线性规划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

*

)