鲍威尔法

第1章最优化问题的基本概念

§1.1最优化的概念

最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率

求得工程问题最优解决方案的过程。

§1.2最优化问题的数学模型

1.最优化问题的一般形式



















qvxxxh

puxxxgts

xxxf

xxxfind

nv

nu

n

n

,,2,10),,,(

,,2,10),,,(..

),,,(min

,,,

21

21

21

21









2.最优化问题的向量表达式



















0)(

0)(..

)(min

XH

XGts

Xf

Xfind

式中：T

n

xxxX],,,[

21



T

p

XgXgXgXG)](,),(),([)(

21



T

p

XhXhXhXH)](,),(),([)(

21



3.优化模型的三要素

设计变量、约束条件、目标函数称为优化设计的三要素！

设计空间：由设计变量所确定的空间。设计空间中的每一个点都代表一个设计方案。

§1.3优化问题的分类

按照优化模型中三要素的不同表现形式，优化问题有多种分类方法：

1按照模型中是否存在约束条件，分为约束优化和无约束优化问题

2按照目标函数和约束条件的性质分为线性优化和非线性优化问题

3按照目标函数个数分为单目标优化和多目标优化问题

4按照设计变量的性质不同分为连续变量优化和离散变量优化问题

第2章最优化问题的数学基础

§2.1n元函数的可微性与梯度

一、可微与梯度的定义

1.可微的定义

设

)(Xf

是定义在n维空间nR

的子集D上的n元实值函数，且

DX0。若存在n维

向量L，对于任意n维向量P，都有

0

)()(

lim

00

0





P

PLXfPXfT

P

则称

)(Xf

在0X处可微。

2.梯度

设有函数

)(XF

，T

n

xxxX],,,[

21

，在其定义域内连续可导。我们把

)(XF

在定

义域内某点X处的所有一阶偏导数构成的列向量，定义为

)(XF

在点X处的梯度。记为：

T

n

k

x

F

x

F

x

F

XF

























,,,)(

21



梯度有3个性质：

⑴函数在某点的梯度方向为函数过该点的等值线的法线方向；

⑵函数值沿梯度方向增加最快，沿负梯度方向下降最快；

⑶梯度描述的只是函数某点邻域内的局部信息。

§2.2极小点及其判别条件

一、相关概念

1.极小点与最优解

设)(Xf是定义在n维空间nR的子集D上的n元实值函数，若存在DX*及实数

0，使得)(),(**XXDXNX

都有)()(*XfXf，则称*X为

)(Xf

的局部

极小点；若)()(*XfXf，则称*X为

)(Xf

的严格局部极小点。

若DX，都有)()(*XfXf，则称*X为)(Xf的全局极小点，若)()(*XfXf，

则称*X为

)(Xf

的全局严格极小点。

对最优化问题



















0)(

0)(..

)(min

XH

XGts

Xf

Xfind

而言

满足所有约束条件的向量T

n

xxxX],,,[

21

称为上述最优化问题的一个可行解，全

体可行解组成的集合称为可行解集。在可行解集中，满足：

)(min)(*XfXf的解称为优化问题的最优解。

2.凸集和凸函数

凸集：设nRD

，若对所有的DXX21、，及

]1,0[，都有DXX21)1(

，

则称D为凸集。

凸函数：设1:RRDfn，D是凸集，如果对于所有的DXX21、，及

]1,0[，

都有)()1()(])1([2121XfXfXXf，则称

)(Xf

为D上的凸函数。

二、局部极小点的判别条件

驻点：设

)(Xf

是定义在n维空间nR的子集D上的n元实值函数，*X是D的内点，

若0)(*Xf，则称*X

为

)(Xf

的驻点。

局部极小点的判别：设

)(Xf

是定义在n维空间nR的子集D上的n元实值函数，具

有连续的二阶偏导数。若*X是

)(Xf

的驻点，且)(*2Xf是正定矩阵，则*X是

)(Xf

的

严格局部极小点。

三、全局极小点的判别

1.凸规划

对于优化问题：







piXgts

Xf

i

,,2,10)(..

)(min



若

)(Xf

、)(Xg

i

都是凸函数，则称该优化问题为凸规划。

2.全局极小点的判别

若优化问题为凸规划，则该优化问题的可行集为凸集，其任何局部最优解都是全局

最优解。（能否证明）

第3章无约束优化方法

§3.1下降迭代算法及终止准则

一、数值优化方法的基本思想

基本思想就是在设计空间内选定一个初始点kX，从该点出发，按照某一方向kS



（该

方向的确定原则是使函数值下降）前进一定的步长k，得到一个使目标函数值有所下

降的新设计点1kX，然后以该点为新的初始点，重复上面过程，直至得到满足精度要求

的最优点*X。

该思想可用下式表示：kkkkSXX1

二、迭代计算的终止准则

工程中常用的迭代终止准则有3种：

⑴点距准则

相邻两次迭代点之间的距离充分小时，迭代终止。

数学表达为：kkXX1

⑵函数下降量准则（值差准则）

相邻两次迭代点的函数值之差充分小，迭代终止。

数学表达为：)()(1kkXfXf

⑶梯度准则

目标函数在迭代点处的梯度模充分小时，迭代终止。

数学表达为：)(1kXf

三、算法的收敛速度

对于某一确定的下降算法，其优劣如何评价？人们通常采用收敛速度来评价。

下面给出度量收敛速度的几个概念。

1.P阶收敛

设序列kX收敛于解*X，若存在常数0P及L、

0

k，使当

0

kk时下式：

p

kkXXLXX**1

成立，则称kX为P阶收敛。

2.线性收敛

设序列kX收敛于解*X，若存在常数

0

k、L及

)1,0(，使当

0

kk时下式：

kkLXX*1

成立，则称kX为线性收敛。

3.超线性收敛

设序列kX收敛于解*X，若任给

0都存在0

0

k，使当

0

kk时下式：

**1XXXXkk

成立，则称kX为超线性收敛。

§3.2一维最优化方法

一、确定初始区间的进退法

任选一个初始点

0

x和初始步长h，由此可确定两点

01

xx和hxx

12

，通过比较

这两点函数值)(

1

xf、)(

2

xf的大小，来决定第三点

3

x的位置。比较这三点函数值是否

呈“高——低——高”排列特征，若是则找到了单峰区间，否则向前或后退继续寻求下

一点。

进退法依据的基本公式：

01

xx

hxx

12

hxx

23

具体步骤为：

⑴任意选取初始点

0

x和恰当的初始步长

h

；

⑵令

01

xx，取hxx

12

，计算)(

1

xf、)(

2

xf；

⑶若)()(

21

xfxf，说明极小点在

2

x右侧，应加大步长向前搜索。转⑷；

若)()(

21

xfxf，说明极小点在

1

x左侧，应以

1

x点为基准反向小步搜索。转⑹；

⑷大步向前搜索：令hh2，取hxx

23

，计算)(

3

xf；

⑸若)()(

32

xfxf，则)(

1

xf、)(

2

xf、)(

3

xf呈“高——低——高”排列，说明],[

31

xx

即为所求的单峰区间；

若)()(

32

xfxf，说明极小点在

3

x右侧，应加大步长向前搜索。此时要注意做变

换：舍弃原

1

x点，以原

2

x点为新的

1

x点，原

3

x点为新的

2

x点。转⑷，直至出现“高—

—低——高”排列，则单峰区间可得；

⑹反向小步搜索（要注意做变换）：为了保证

3

x点计算公式的一致性，做变换：将

原

2

x点记为新

1

x点，原

1

x点记为新

2

x点，令

hh

4

1



，取hxx

23

，转⑸

例：用进退法确定函数96)(2xxxf的单峰区间[a，b]，设初始点0

0

x，

1h

。

解：①10

0

hx

②4)(9)(10

211201

xfxfhxxxx

③)()(

21

xfxf

说明极小点在

2

x点右侧，应加大步长向前搜索

④令2122hh，取321

23

hxx则0)(

3

xf

⑤)()(

32

xfxf

说明极小点在

3

x点右侧，应加大步长向前搜索

舍弃原

0

1

x的点，令31

21

xx，则0)(4)(

21

xfxf

令4222hh，取743

23

hxx则0)(16)(

23

xfxf

、)(

2

xf、)(

3

xf呈“高——低——高”排列

],[

31

xx为单峰区间，即区间[1，7]即为所求

二、黄金分割法

黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原

则：

⑴对称取点的原则：即所插入的两点在区间内位置对称；

⑵插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点；

⑶等比收缩的原则：即每一次区间消去后，单峰区间的收缩率保持不变。

设初始区间为[a，b]，则插入点的计算公式为：

)(382.0

1

abax

)(618.0

2

abax

黄金分割法的计算步骤如下：

①给定初始区间[a，b]和收敛精度



；

②给出中间插值点并计算其函数值：

)(382.0

1

abax)(

1

xf

)(618.0

2

abax)(

2

xf

；

③比较)(

1

xf、)(

2

xf，确定保留区间得到新的单峰区间[a，b]；

④收敛性判别：计算区间[a，b]长度并与



比较，若ab，输出

)(

2

1

*bax

否则转⑤；

⑤在保留区间内继承一点、插入一点，转②。

例：使用黄金分割法求解优化问题：2.0532)(min2xxxxf，。

解：①115.0)(056.0)35(382.03)(382.0

11

xfabax

②667.7)(944.1)35(618.03)(618.0

22

xfabax

③∵)()(

12

xfxf∴舍弃（1.944，5]，保留[-3，1.944])3(944.1；

④继承原

1

x点，即115.0)(056.0

22

xfx

插入987.0)(111.1)3944.1(382.03)(382.0

11

xfabax

∵)()(

12

xfxf∴舍弃（0.056，1.944]，保留[-3，0.056])3(056.0；

继承原

1

x点，即987.0)(111.1

22

xfx

插入306.0)(832.1)3056.0(382.03)(382.0

11

xfabax

∵)()(

12

xfxf∴保留[-1.832，0.056])832.1(056.0

；

继承原

2

x点，即987.0)(111.1

11

xfx

插入888.0)(665.0)832.1056.0(618.0832.1

22

xfx

∵)()(

12

xfxf∴保留[-1.832，-0.665]

如此迭代，到第8次，保留区为[-1.111,-0.940]171.0)111.1(940.0

∴

999.0)(0255.1)940.0111.1(

2

1

**xfx

§3.3梯度法

一、基本思想

对于迭代式kkkkSXX1，当取搜索方向)(kkXfS



时构成的寻优算法，称

为求解无约束优化问题的梯度法。

二、迭代步骤

⑴给定出发点kX和收敛精度



；

⑵计算kX点的梯度)(kXF，并构造搜索方向)(kkXFS；

⑶令kkkkSXX1，通过一维搜索确定步长k，即：

)(minkkkSXF

求得新点1kX

⑷收敛判断：若)(1kXF

成立，输出1*kXX、)()(1*kXFXF，寻优结

束；否则令1kk转⑵继续迭代，直到满足收敛精度要求。

三、梯度法的特点

梯度法寻优效率受目标函数性态影响较大。若目标函数等值线为圆，则一轮搜索就

可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。

梯度法中相邻两轮搜索方向相互垂直。（是否会证明）

§3.4牛顿法

牛顿法分为基本牛顿法和阻尼牛顿法两种。

对于迭代式kkkkSXX1，当取

1k且搜索方向)()]([12kkkXfXfS



时

构成的寻优算法，称为求解无约束优化问题的基本牛顿法；

对于迭代式kkkkSXX1，取搜索方向)()]([12kkkXfXfS



，k为从kX

出发、沿牛顿方向做一维搜索获得的最优步长，所构成的寻优算法，称为求解无约束优

化问题的阻尼牛顿法。

搜索方向)()]([12kkkXfXfS



称为牛顿方向。

这里需要注意的是会求海塞阵的逆矩阵。

§3.5变尺度法

我们把具有)(1kkkkkXfAXX

迭代模式的寻优算法称为变尺度法。

其搜索方向表达式为：)(kkkXfAS，称为拟牛顿方向，其中kA称为变尺度矩

阵。

在迭代开始的时候，IA0；随着迭代过程的继续，)()]([12kkkXfXfA。

因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。

§3.6共轭梯度法

一、共轭方向的概念

设H为对称正定矩阵，若有两个n维向量

1

S和

2

S，满足0

21

SHST，则称向量

1

S

与

2

S关于矩阵H共轭，共轭向量的方向称为共轭方向。

若有一组非零向量

1

S，

2

S，…，

n

S满足)(0jiSHS

j

T

i

，则称这组向量关于

矩阵H共轭。

对于n元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多n次即可得到

极值点。

二、共轭方向的形成

对于函数

CXBHXXxxxfXfTT

n



2

1

),,,()(

21



沿任意方向0S在设计空间上任意做两条平行线，分别与目标函数等值线切于点1X、

2X，令121XXS，则0S、1S关于矩阵H共轭。（能否给出证明）

三、共轭梯度法

对于迭代式kkkkSXX1，取搜索方向k

k

kkSXfS)(11

其中：)(00XfS，

2

2

1

)(

)(

k

k

k

Xf

Xf











共轭梯度法相邻两轮搜索方向是一对共轭方向。

§3.7鲍威尔法

基本迭代公式仍旧是：kkkkSXX1

基本鲍威尔法每轮搜索分为两步：一环的搜索+在该环搜索完毕后生成的新方向上

的一维搜索。

对于基本鲍威尔法，相邻两轮搜索生成的搜索方向是共轭的。

修正鲍威尔法与基本鲍威尔法类似，所不同的是每环搜索后生成的新方向要利用鲍

威尔条件判别其可用性。

注意掌握鲍威尔条件的表达式和应用！

每环搜索方向组的生成：

1．第一环的搜索方向组就是各坐标轴方向

2．下一环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定，方法是：

若本环的搜索结果满足鲍威尔条件，则将本环搜索方向组中使目标函数下降量最大的方

向去掉，并将本环生成的新方向递补进去，就形成下一环的搜索方向组；若本环的搜索

结果不满足鲍威尔条件，则下一环的搜索方向组仍旧沿用本环搜索方向组不变。

下一环搜索起点的确定：

下一环搜索起点由本环搜索结果确定，方法是：若本环的搜索结果满足鲍威尔条件，

则以本环搜索终点为起点，沿新生成的方向作一维搜索，得到的新点作为本轮的搜索终

点，也是下一轮的搜索起点；若本环的搜索结果不满足鲍威尔条件，则取本环搜索终点

和反射点中目标函数值小的点作为本轮的搜索终点，也是下一轮的搜索起点。

这里需要注意的是反射点的计算：kk

n

k

n

XXX

02

2



式中：k

n

X

2

是本环起点kX

0

相对于本环终点k

n

X沿新生成方向的反射点。

例：对于无约束目标函数

211

2

2

2

1

242)(minxxxxxXf，利用修正Powell法从















1

1

0X出发求最优解。

解：令















1

1

01

0

XX),(

21

01eePP































1

1

0

1

1

0

1

1



XX

令0)(1

1





Xf得：2则：















1

3

1

1

X



































1

3

1

0

1

1

1

2

XX

令0)(1

2





Xf得：

5.0则：















5.1

3

1

2

X

该环生成的新搜索方向为：











































5.0

2

1

1

5.1

3

1

0

1

2

1XXS

对1S

进行有效性判别：

反射点











































2

5

1

1

5.1

3

221

0

1

2

1

4

XXX

3)(1

01

Xff5.7)(1

22

Xff7)(1

43

Xff

4)7(3)()(1

1

1

01

XfXf，5.0)5.7(7)()(1

2

1

12

XfXf

故最大下降量4

1



m

故：

13

ff和2

31

2

21321

)(

2

1

))(2(fffffff

mm



均成立

方向1S

可用

以1

2

X为起点，沿1S方向作一维搜索：





















































5.05.1

23

5.0

2

5.1

3

11

2

1

3

SXX

由)()(min11

2

1

3

SXfXf得4.05/2

故，本轮寻优的终点为：















7.1

8.3

1

3

1XX

做收敛性判别：

22017.08.2XX

，应继续搜索

下一轮寻优过程的起点为：















7.1

8.3

1

3

2

0

XX

下一轮寻优过程的搜索方向组为：),(1

2

Se

继续依样搜索直至满足收敛精度

第4章约束优化方法

约束优化方法要求大家重点掌握惩罚函数法，包括内点法、外点法、混合法。

一、外点法

构造惩罚函数：







q

v

v

k

p

u

u

kkXhrXgrXfrX

1

2

1

2)]([]0),(max[)(),(min

外点法既可以处理不等式约束优化问题，又可以处理等式约束优化问题。

需要注意的是：惩罚因子kr

随迭代次数的增加是递增的，当kr时得到的解就

是原问题的最优解。

例：用外点法求解

03..

12)(min

2

1

2

2

2

1





xts

xxxXf

解：构造惩罚函数2

21

2

2

2

1

]0,3max[12),(xrxxxrXkk

















时当

时当

0312

03)3(12

),(

21

2

2

2

1

2

2

21

2

2

2

1

xxxx

xxrxxx

rX

k

k

令022

1

1







x

x



0)3(22

22

1







xrx

x

k



X为内点时无约束最优解

故得：

k

k

r

r

xx





1

3

1

21

9)(3lim1*

2

*

2

*

1





xfxxx

k

二、内点法

构造惩罚函数：







p

u

u

kk

Xg

rXfrX

1

)(

1

)(),(或：





p

u

u

kkXgrXfrX

1

)](ln[)(),(

内点法只能处理不等式约束优化问题，不能处理等式约束优化问题。

需要注意的是：惩罚因子kr随迭代次数的增加是递减的，当

0kr

时得到的解就

是原问题的最优解。

例：用内点法求解约束优化问题

21

)(minxxXf

0

0..

1

2

2

1





x

xxts

解：构造惩罚函数

1

2

1221

ln]ln[),(xrxxrxxrXkkk

令

0

1

2

1

1

2

12

1

1













x

r

xx

x

r

x

kk



0

1

1

2

12

2











xx

r

x

k



得

4

181

1





kr

x

，k

k

r

r

x





16

)181(2

2

当0kr时，得















0

0

*x0)(*xf

三、混合法

构造惩罚函数：







q

v

v

k

p

u

u

kkXhr

Xg

rXfrX

1

2

2

1

1

)]([

)(

1

)(),(

或：





q

v

v

k

p

u

u

kkXhrXgrXfrX

1

2

2

1

1

)]([)](ln[)(),(

混合法的特点是：对于不等式约束按照内点法构造惩罚项，对于等式约束按照外点

法构造惩罚项。混合法既可以处理不等式约束优化问题，也可以处理等式约束优化问题。

例：用混合惩罚函数法求解约束优化问题

2

22

2

1

3)(minxxxXf

0

01..

2

1





x

xts

解：构造惩罚函数2

21

2

22

2

1

1

]1ln[3),(x

r

xrxxxrX

k

kk

令

0

2

23

1

1

2

),(

2

2

1

1



































k

k

k

r

x

x

x

rx

rX

得：

2

211

1

kr

x





，

)1

1

(2

3

2





kr

x

当0kr时，得















0

1

*x1)(*xf

第5章遗传算法

本章要求重点掌握遗传算法的5个要素、遗传算法的寻优机制。

一、遗传算法的5个要素

1.编码

将优化问题的解编码，用以模拟生物个体的基因组成；

2.初始种群生成

将优化问题多个随机可行解汇成集合，用以模拟进化的生物种群；

3.个体适应度评估

将优化问题目标函数加以变换，生成适应度函数来评价种群个体的适应度，用以模

拟生物个体对环境的适应能力；

4.遗传操作

包含选择、交叉、变异

选择：一种使适应度函数值大的个体有更大的存活机会的机制，用以模拟环境对生

物个体的自然选择；

交叉：不同个体间相互交换信息，用以模拟高级生物有性繁殖过程中的基因重组过

程；

变异：模拟生物在遗传过程中基

因复制差错而产生新个体的现象。

5.控制参数的设定

种群规模：160~30M；

交叉概率：99.0~4.0

c

p

变异概率：1.0~0001.0

m

p

最大进化代数：1000~100T

二、遗传算法的寻优机制

寻优机制见右侧的基本遗传算

法流程图。

仔细看看遗传算法人工模拟进

化的例题。

遗

传

操

作

否

是

编码

初始群体的生

群体中个体适应度函数的评

选择

交叉

变异

收敛？

结束

基本遗传算法流程图

作业练习：

1.确定下列函数的初始区间。

⑴xxxf6)(min3取2.2

0

x，

8.0h

答案：[0.8，2]

⑵

xxxf2

4

1

)(min

取5.0

0

x，

3.0h

答案：[0.8，2.6]

2.用黄金分割法求解xxxf6)(min3，取3.0、初始搜索区间[0.8，2]。

4.1)5416.12584.1(

2

1

)(

2

1

*bax256.4)(*xf

3.用梯度法求解2

2

2

1

4)(minxxXf，TX]4,4[0（做两轮迭代）

答案：















4531.0

4723.0

2*XX0443.1)()(2*XfXf

4.用阻尼牛顿法求解

21

2

221

2

1

25.12)(minxxxxxxXf，TX]2,1[0

答案：















1

2/1

1*XX4/3)()(1*XfXf

5.用共轭梯度法求解

2121

2

2

2

1

410)(minxxxxxxXf，TX]1,1[0

答案：















6

8

*X52)(*Xf

6.用Powell法求解

2121

2

2

2

1

410)(minxxxxxxXf，TX]1,1[0（迭代2轮，计算

过程中小数点后面保留3位）

答案：





























6

8

999.5

998.7

*x52)()(2*XfXf

7.用外点法求解：

01..

2)(min

21

2

2

2

1





xxts

xxxf

答案：



























3

1

3

2

*x

，

3

2

)(*xf

8.用混合罚函数法求解：

01

0ln..

)(min

21

1

21







xx

xts

xxxf

答案：















0

1

*x1)(*xf