最优化方法第一次基础知识
一. 引言 1. 最优化定义
最优化是从所有可行方案中选择最合理方案以达到最优目标 的一门学科。 (1) 达到最优目标的方案:最优方案(最优解) (2) 搜寻最优方案的方法:最优化方法
最优化问题:寻求某些变量的取值使其符合某些限制条件, 并使某个目标函数达到最大值或最小值的问题。
一般的数学形式为: min f ( x) , s.t. x D 其中 f ( x)为定义在集合D 上的函数
四. 极值问题的经典方法
1.求驻点的方法
min f ( x) f ( x) 0
xRn
grange 乘子法
f x1
0
f
x
n
0
min f ( x1 , x2 , xn )
s.t
.
h1
(
x1
,
x
2
,
xn )
0
hl ( x1 , x2 , xn ) 0
min L( x, )
产品
1 2…
1 a11 a12 …
资 2 a21 a22 … 源… … … …
m am1 am2 …
单位 利润
c1
c2 …
拥有 n量
a1n b1 a2n b2
……
amn bm
cn
令 x j 表示第 j 种产品的产量。
模型:
n
max f ( x) c j x j
j 1
n
aij x j bi
s.t. j1
x1 x2 xn
性质1:函数在某点的梯度若不为0, 则必与过该点的等值线
(面)垂直。
▽f(X0)
X0x0
LL
f(X)=f(X0)
性质2:梯度方向是函数值具有最大变化率的方向,即函数值 上升最快的方向。
2. 方向导数和下降(上升)方向
(1)方向导数: f ( x0 ) lim f ( x0 t p) f ( x0 )
法。
3.应用领域
工程设计、军事科学、自动控制、空间技术、资源 分配、计算机科学等等。例如:
①桥梁结构设计; ②运输问题;
③参数拟合;
④多波形信号发生仪中正弦波形逼近的优化设计,
在
0 ,
2
中找
n
个分点,使过这些分点的折线和
正弦函数曲线的误差最小。
4.包含内容: 最优化又称数学规划: LP、NLP、DP、IP
2. 发展简况
经典最优化理论的研究已有很久,最早可追溯到 Fermat时代。 1940年前,对多变量函数的数值最优化方法知之 甚少,但当时已发现了若干最小二乘法和在物理上 应用的最速下降法,多变量的牛顿法也很著名。 40年代与50年代:线性规划(LP)的发展。 二战以后,爬山法得到发展与应用(实用,粗糙)。 1959年,W-C.Davidon的一个报告引入了变尺度方
ti
Ri
1
50
34780
2
55
28610
3
60
23650
。。。
。。。
。。。
15
120
3307
利用最小二乘思想,可将其化为三维空间的无约束最优化
问题,即:
min f ( x1 ,
x2 ,
x3 )
i151
Ri
x1 exp
ti
x2 x3
2
例2. 生产安排问题
现有 m 种资源的数量为 b1 , b2 , , bm 。计划生产 n 种产 品1,2,…,n。有关数据如下,试问:怎样安排生产可以使利 润达大?
x
j
0
i 1,2,...,m j 1,2,...,n
例3. 运输问题(TP)
已知有m个生产点Bi,可供应某种物质量分别为 bi ( i 1, 2 , , m ) n个销地 C j ,需求量为 c j ( j 1, 2 , , n ) . 从 Bi 到 C j 的单
位运价为aij 。问:应如何安排运输方案才能使总运费最小?
min f ( x)
g( x) 0
min f ( x)
s.t. h( x) 0
s.t. x D
2.解法分类 ➢ 解析方法:利用函数的解析性质去构造迭代公式使之收敛 到最优解(如牛顿法)。 ➢ 直接方法:它对函数的解析性质如可微性没有要求,而是 根据一定的数学原理来确定(如0.618法)。
3.全局最优解与局部最优解
xRn Rl
f
(
x)
l
i 1
i
h(i x)
L
x L
f ( x) h( x)
0
h(
x)
0
ቤተ መጻሕፍቲ ባይዱ
五. 图解法
等值线(面)的特点:
1.不同值的等值线不相交 ; 2.除极值点外,等值线是连续曲线 ; 3.等值线稠密处导数变化快,稀疏处变化慢 ;
六. 梯度与Hesse阵
1. 梯度 f ( X ) ( f , f ,..., f )T
5.分类:
无约束问题
单 目 标 静 态 问 题有 约 束 问 题线 非性 线规 性划 规 划
最优化问题
动态问题
多目标
二. 最优化问题实例
例1:多参数曲线拟合问题
已知热电阻
R
依赖于温度
t
的函数关系为:R
x1
exp
t
x2 x3
其中
x1
,
x
2
和x
是待定参数。通过试验,得到
3
t和R的15组数
i
运费
销
12
1
a11
a12
产2
a21
a22
地… … …
m am1 am2
销量
c1
c2
地 …n
… a1n … a2n …… … amn … cn
产量
b1 b2
…
bm
在产销平衡条件下,要求得总运费最小的调运方案,可得如下 模型:
设 xij 表示从第i个产地向第j个销地的运量,则有
mn
min z aij xij
最优化方法
1.教 材:最优化理论与方法 陈宝林,清华大学出版社
2.参考书:最优化原理与方法 薛嘉庆,冶金工业出版社
基本知识
一.引言
二.最优化问题实例 三.最优化问题及基本概念
四.极值最优化问题的经典方法 五.图解法 六.梯度与Hesse阵 七.Taylor展开式 八.凸集与凸函数 九.极小点的判定条件 十.算法及相关概念 十一.中止条件 十二.收敛速度
i 1 j 1
n
xij bi
i 1,2,...,m
j1
s.t .
m
xij c j
j 1,2,...,n
i 1
x
ij
0
i j
1,...,m 1,...,n
1.模型
三. 最优化问题及基本概念
min f ( x)
s.t .
gi (x) 0 h j ( x) 0
i 1, ,m j 1, ,p
最 优 点 :x* 最 优 值 :f ( x* ) 最 优 解 : ( x* , f ( x* ))T 邻 域N ( x0 , ) { x | x x0 } 局 部 最 优 解x* : f ( x* ) f ( x),x N ( x0 , ) D 全 局 最 优 解x* : f ( x* ) f ( x),x D