青科大化工-最优化方法

第三部第九章无约束条件的最优§9.1单变量最优化方§9.2多变量最优化方模式逐向寻优建模、仿真与优 第三部分优什么是最优化所谓最优化是指如何用最小的代价获得最大的优化理论和方法奠基于0世纪0年代（二战期间），但作为一门新兴学科，则是在.B.Dantzig提出单纯形法（1947）、.W.Kuhn和.W.uck提出非线性基本定理（191、.Blan提出动态规划的最优化原理（197）之后，借助于计算机的发展，优化理论才得到飞速的发展。至今已形成具有多分支的综合学科，主要有线性规划、非线性规划、动态规划、图论和网络、对策论、决策论等。建模、仿真与优 化工领域中1、研究开发和设包括工艺条件的最优设计、过程最佳参数的确定、技术经济分析决策的最优化、最优总体设计等2、过程运行、管最优化分析和决策、过程最优化操作参数的分析和确定、最优制等3、化工发 方如区域资源综合利用的最优规划、区域性化工与环境治理的最优规划等建模、仿真与优 优化涉及多门学科知识 计算机：硬件、软建模、仿真与优 按优化目标分为单目标优多目标优化（往往可以转化为单目标优化问题按对象是否确定分为：确定型优化：所有变量都有一确定 有约束优化：线性规非线性规 建模、仿真与优 求解优化问题的步骤提出问题、分析问建立目标函确定约束条选择优化算建模、仿真与优 几个概念化工生产过程优

f(X

----目标函数objective

hi(X)

i1~

----约束条件gj(X)

j1~

常见的有：不等式约束条若f(X)、hi(X)、gj(X)均为线 线性规

等式约束条若f(X)、hi(X)、gj(X)中含有非线性函 非线性规其中，若f(X)为二次函数，hi(X)、gj(X)为线性函 二次规建模、仿真与优 几个概念x8x 约束条件64 约束条件约条件

约束条件

----可行域valid满足约束条件的点的全体集----闭域与开 2

1建模、仿真与优 函数的极值只是局部的最优值，但却是全局最优值的侯选者。极值条件对一元连续函

Y

(X存在极值点的必要条件是：

(X)充分条件是

f(X)

(极小点f(X)

(极大点建模、仿真与优 对多元连续函

Yf(X1,X1 ,Xn

2n存在极值点的必2n充分条件是

fX22212X2XnX1

,

X1X

...22H X22

...

（汉森矩阵XnX

...2X1Xn2X2Xn22n2X1Xn2X2Xn22n若H为负定时（所有偶数行列式为正，所有奇数行列式为负X*为极大点否则，X*为鞍点建模、仿真与优 12例1：判断下列12y

2x2xx1

8

9x2x1 1x1xx22xx2

4x2

1212

Hx 10H2

41

xx122建模、仿真与优 xx122第九章无约束条件的最优

单变量最优化方多变量最优化方§9.1单变量最优化方

解析法：要求一阶导数存在且连数值 一维搜索近似

y

x通过反复迭代，不断缩小搜索区间，最终求取函数近极值点下面以具有一个极值点的问题为例说明建模、仿真与优 §9.1单变量最优化方在原始搜索区间（a0,b0）内任选两点x1、计算f(x1)、f(x2)，并比较两者的大小120 fxfx,则最小点必在120

,x2112 fxfx,则最小点必在112

,x2112 fxfx,则最小点必在112

,b0在新区间内重复进行以上两步，直到区间小于预定的精度要求为止2fx12fx12 Nx

fx1ffx1f21

fx

一个好的搜索法应满足一个好的搜索法应满足区间缩短率大选点方式简便对函数形式无特殊要求对初始点的选择要求不高§9.1单变量最优化方从原始搜索区间（a0,b0）的每一端距离0.382处选两点x1、除开始需选两点外，以后每次选一个即

x1

a0

x2

a0

区间缩短率

5 50.618具有如下性质

2 20.6180.618

0.3820.3820.618

建模、仿真与优 §9.1单变量最优化方二、近似搜索到最后阶段基本思想：用一多项式P(x)拟合目标函数由于多项式具有连续可微等较好的解析性可求得多项式的极小点的解析解，并作为的搜索点，重复此法，直到满足精度为止收敛速度较快多项式的方次越算量和难度也越大下面以常用的二次多项式近似法法）为例

f

fxxxm

Px建模、仿真与优 §9.1单变量最优化方

x1

fx;x

fx;x

fx 0Px 0

axax2

fx

a11

a2 xxff22xxff2 Px

aa

a2 xf2fxf2 xxm

x1x112 x1建模、仿真与优 §9.1单变量最优化方Px

fx

x

mfxm

fx Px xxm 建模、仿真与优 单变量寻优举例1：冷却器最优某炼油厂需将煤油从1C冷却到40ºC，煤油处理量为314g/r，冷却介质为水，初始温度为t130C。要求设计一冷却器（逆流），并使该冷却器的年度总费用J最小。已知数据如下：JA

200元/m

----冷却器总材料费和制作费/m2（投资费

----年折旧率（包括维修费K

/m

hr 总传热系数8000小时

冷却器每年运行时间Jw

0.04元

冷却水单价CwCh

/kg/kg

冷却水比热 煤油比热建模、仿真与优 A单变量寻优举A

200元mhmh

K836.8kJ/m2hrT1

8000小时Jw0.04元t t

Cw4.184kJ/kgKCh2.092kJ/kgt1 解

总费投资①进行最优化分②建模：目标函

操作年度投资费

JA

A年度操作费

Jw

冷却水用量建模、仿真与优 单变量寻优举J

JA

Jwmw

年

T1

目标函

t1AQmhC

T2

mwCw

t1

12TtTt12tm

ln

t2A 200元mA

T2K836.8kJ/m2hr8000小时Jw0.04元Cw4.184kJ/kgKCh2.092kJ/kg

建模、仿真与优 单变量寻优举3

2.092 t t 3104A836.83104mw

建模、仿真与优 单变量寻优举J20015% 130

无约束条件的目标函初始区间0

T1

T2t At2

3.406万建模、仿真与优 §9.2多变量最优化

模式逐向寻优解析法很难或不可能处理多变量最优化方法一、模式法Pattern

单纯形改进的单纯形单纯形法（simplexmethod）最常用由Spendley,Hext和Himsworth于1962年创立 四面 n+1个顶点构成建模、仿真与优 单纯形法

§9.2多变量最优化方下面以二个变量的最优化（最大值）问题为例单纯形选为正三角形寻优步骤计算单纯形各顶点的函数值比较各函数值，舍 者（即最小者）

y y y y 点的相对点（映像）为新点并与其余的两点构成新的 纯形重复上面的过程，直至达到精度要求若产生振荡不前进时，舍去第二 的点搜索到最后，单纯形会跨着最优点或距其一定距离（不超过单纯本身的大小，此时再搜索也无甚进展，应缩小单纯形的尺寸建模、仿真与优 §9.2多变量最优化方改进的单纯形法上述单纯形法简单，但搜索不能加速若在搜索中改变单纯形的形状，如用延伸、收缩、扩张等操作，则可大大提高搜索效率，即方向对时，就用扩张操作，方向不对时，就用收缩操作。一般扩张系数取为1.2~1.5，收缩系数取为0.5建模、仿真与优 多变量最优化方例2：换热器序优化设

冷流体进入温度

t5 冷流体离开温度K1、K2、 第1、2、台换热器的总传热系数

T1、T2、 热流体1、2、3进入温度t3、t4、 热流体1、2、3离开温度

1000C,

5000C,T

3000C,T

4000C,T

6000C,123fK1120,123f

80,

40,

pphpp

105热容流率c问如何设计该换热器序列方能使换热面积之和最小建模、仿真与优 多变量最优化

tAA1

f t3t3p

php

c

tt4A

tt5Q

t

1

A1250t2in

tin

40022A12500AA1

22500t11002

t112500 无约束条件的目标函

400建模、仿真与优 A2500t13A2500t13 t125001 400t2

t0t1确定初始点

t

100t1

t1t2确定有关参数，建立初始单纯形取扩张系数=2，压缩系数=0.75，步长h=10，按如下建立初始单纯tj

j

0 1

2

150

160

tt21tl1th

0

150

150

代入式1中，得

t

t2

tg建模、仿真与优 2500t tA 12500

3精度判别

300

400t2xh

xg

差点

t21

tl令 l

h 好点

精度判别：

h

2 g

t1th

（舍去

t2tg

1

最大值

7361.1111t

tl

0.01394

建模、仿真与优

23t21tl

t22t1t构造新的单纯形

重心点：剔 点后剩余点的重心，

t

tgt22

gtl点：一般取为对称反射，公式

tn3

th

155

7250

A2A2A21建模、仿真与优 扩张

t

tl

t24扩张点：一般公式

t23xxxxn4 n2 n3 xxxx

tt22取扩张系数

2

t1th

t2tg 165

7202.16

由ltgt24组成新的单纯建模、仿真与优

165

150

t

tl

t24tl

24

tg

t21

t23160

t22t

t2 250

Al

Ag

t

th

t

tg2

7359.1429Al

0.0215

A1A1A2A21A23A24建模、仿真与优 l

181.2504

l

g

182.3438

g

h

182.9688

h

9

7049.8881

t1t2t1t2t2

A

建模、仿真与优

A

单纯形法优点：计算工作量小，计算速度快；缺点：收敛速度慢；只要单纯形边长选得足够小，仍能得到意的结果建模、仿真与优 §9.2多变量最优化方二、逐向寻优坐标轮换法：最

法共轭梯度 共轭方向Powell每次只改变一个变量，保持其余变量不变该法搜索速度慢，可能发散 建模、仿真与优 xx22例2：求下列函xx22f60

4x2

10

x2

4

x11x1

fminx2坐标轮换x2x2取初始迭代x2x1(0)x1

(0)

f

建模、仿真与优 xx22例2：求下列函xx22xxf60xx

4x2

fmin12坐标轮换12沿x1轴搜xx1

)60

x2

42x2

2x2xx22x211

(1)f

建模、仿真与优 xx22例2：求下列函xx22xxf60xx

4x2

fmin12坐标轮换121沿x2轴搜1xx2

f

,2)56

x2

122x1

xx11下一个迭代点x(2)1

(2)

f

x12如此反复，最后有：x12

x2x

f建模、仿真与优 梯度法：将函数

xn附近

展开，并取一次f

fx

f

xnnnnfxnnn

fx

xn

n当＝180（或0）时，函数值下降（或上升）最大，即负（正）（上升最快，故取负）梯度方向为搜索方向。n步骤•取初始迭代负梯度方求取步确定下一个迭代……如此反

建模、仿真与优 仍以例2为例xx22例2：求下列函xx22xx12f60xx12

4x2

梯度

fminx取初始迭xx1 (0)x1

(0)

2负梯度方2

x10x

10

x10x

4

建模、仿真与优 仍以例2为例例2：求下列函x1f6010x14x2x1梯度求取步

x2x2

x(0)

fxx(0)x x1

x1x

xx xx

4x(0)

x(0)60116x(模、仿真与优 求极值

10016

80x(0)得：

确定下一个迭代xx1

xx2

负梯度方

x1

x2

建模、仿真与优 求取步xx1

x1x

3.7179xx2

x2x

1.48716确定下一个迭代如此反复……（略建模、仿真与优 法因为最优解存在的必要条件

x上式为 线性方程组，求解这一方程可得最优解。 迭代式为xk

f

xk汉森建模、仿真与优 仍以例2为例xx22例2：求下列函xx22xx12f60xx12

4x2

fmin求取一阶导数、二阶导数取初

(0) (0)xx12 xx12

,x(0)

4

12

x

fx(0),x(0) 1

0,0建模、仿真与优 仍以例2为例xx22例2：求下列函xx22xx12f60xx12

4x2

fmin2

1

1 212

2

3

x(1)

1

3

fx(1),x(1)102x

4

x

1建模、仿真与优 法用尺度矩阵（MetricMatrix）代替汉森矩阵，以避免计算二构建尺度矩阵的方法有多种，但均要保证对称、正定。较好有2种：DFP法、BFGS法xk

fx

fx汉森矩建模、仿真与优 共轭梯度法什么是共轭DTAQ

则称D、Q以A共轭若A为单位矩阵，则D、Q正交什么是共轭梯度法负梯度方向（Fletcher和 D0g0建模、仿真与优

该次的负梯度方向与上次索方向的线性组将D0、D1作为D、Q代入式AgT0

D00TD00建模、仿真与优 §9.2多变量最优化方Powell法：最有效的方法之1964年由Powell提出，不用计算函数的梯度此法是将二次型目标函数的收敛原理用于非二次型的最优化。

极小x最小极小

二次型收敛原理建模、仿真与优 §9.2多变量最优化方Powell法对于非二次型（n维）最优化问 极小x

骤如下X由一个基点X0

尽可能接近最解）出发，并取一系列线性独立的最小i 极小i

索方

k,

i

并依次沿一系列方向搜索最优，得到一 建模、仿真与优 设有一组矢量：X1X2

x2nTXnxT

xn2

xnn若存在有一组不全部为零的标量：

t

tn能使：

t1X

t2X2

tjXj

tnXn则X1

X2,

Xj,,X

为线性相关，或线性不独立；其中00如果只有当

t2 t

0t1X

t2X2

tjXj

tnXn才成立，则

X1

X2,

Xj,,X

为线性独立，或线性不相关。建模、仿真与优 从几何角度看，线性不独立的两个矢量X 和X 互平行，而线性独立的两个矢量X

X

XX3X1X2 2-

建模、仿真与优 （2）由Xk

点构造新的搜索方k

Xk

Xk，并判断此方向是否可行， 此，需

yXk

kmtyXkmt

y2Xk

Xk

ykyt求最小值时，

k0yt0y

kny0ny

y0nk y0nk

yy yy

yk

ykand/

k2y

求最大值时，

kyty

ky0yy y

yk

ykkk

/

2y

yt

y0ny建模、仿真与优 y0ny则k不是可取方向，接着，应从最后一

kX0X

kXnX

开始，重复步骤若式1（或式2）不满足，则

k

方向搜索可行，并按下式找极小点XkXn

kXnX

k

为最优步长建模、仿真与优 例3：Powell1 1

x2x1

x2

（1）选基点、确定2个线性独立的搜索方向、依次寻X2 X20

01

02

由X0开始0方向找最小值，即

0代入目标函数0 (4.545,0)

1y1

x152 x11212建模、仿真与优

0

x1y

1

0X1X

y01

再由