最优化方法全部PPT课件

最优化方法
（最优化课件研制组）
编辑课件
1
最优化方法
为了使系统达到最优的目标所提出的各种求解方法
称为最优化方法。最优化方法是在第二次世界大战前后，
在军事领域中对导弹、雷达控制的研究中逐渐发展起来
的。
最优化方法解决问题一般步骤：
（1）提出需要进行最优化的问题，开始收集有关资 料和数据；
（2）建立求解最优化问题的有关数学模型，确定变
向量内积的性质：
ⅰ) ,,（对称性）；
ⅱ) , , , k,k,（线性性）；
ⅲ) , 0 ,当且仅当 0 时，, 0（正定性）；
编辑课件
13
向量的长 ,
单位向量 1
向量的夹角
，
,
arccos
,
0 ,
向量的正交 , ,0（正交性）
2
1.可微
定义1.7 设 f:D R n R 1,x0 D .如果存在 n
sx 0
sx 0
x* x*
f f x*
编辑课件
9
1.4 二维问题图解法
二维极值问题有时可以用图解的方式进行求解，有 明显的几何解释。
例 求解 m infx ,y x 2 2 y 1 2
编辑课件
10
图解法的步骤：
①令 fx,yx22y 1 2c，显然 c 0 ；
②取 c0,1,4,9, 并画出相应的曲线（称之为等值线）.
解法：Lagrange乘子法
1.2 实例
数据拟合问题 原料切割问题 运输问题 营养配餐问题 分配问题
1.3 基本概念
1. 最优化问题的向量表示法
设 xx1,x2, ,xnT 则
m i n fx 1 ,x 2 , ,x n 编辑课m 件 i n fx （1）
4
以向量为变量的实值函数 定义向量间的序关系(定义1.1)：
设 f : Rn R1 具有二阶连续偏导数，且 gxfx,
则矩阵
2 f x
x12
2
f
x
f x x1x2
2 f x
x1xn
2 f x
x2x1
2 f x
x22
2 f x
x2xn
2 f x
xnx1

称为函数 f x 关于变量 x 的二阶导数，简记为 2 f x 。
容许解（点）
容许集 D xhx 0 ,sx 0
编辑课件
6
求解问题（3）是指：在容许集 D 中找一点 x *，使得
目标函数 f x 在该点取极小值，即对于容许集中的任 意一点 x ，总有
f x*f x
最优点（极小点）x * 最优值 f x * 最优解 x*, f x*
局部
严格极小点 非严格极小点
g1x,gx2, , gm x 在点 x 0 都可微，则称向量值函数
g x 在点 x 0 处可微。 编辑课件
23
定义表明，g x 在点 x 0 处可微，则
lim g ix 0 p g ix 0 g ix 0 Tp 0 , i 1 ,2 , ,m
p 0
p
成立，其用向量形式可简单地表示为
fx p fx fx Tp 1 p T 2 fx p （1.29） 或 fx p fx fx T p 1 p T 2 2 fx p o p （1.31）
2
这个公式与一元函数展开到三项的Taylor公式是相对应的。
多元函数的Taylor展开式在最优化方法中十分重要，
许多方法及其收敛性的证明编辑都课件是从它出发的。
26
1.6 凸函数与凸规划 1. 凸集
直观上，凸集就是空间中内部无“洞”，边界又不向 内凹的一些点的集合，其基本特征是该集合中任意两点 间的线段仍然属于这个集合。
向量的内积 设 a a 1 ,a 2 ,,a n T ,b b 1 ,b 2 ,,b n T ,
则 a1b1a2b2 anbn 称为向量 a 与 b 的内积，
记作 a , b 。
其实，a,b aTb a1,a2,
b1
,
an
b2
。
bn
向量也常用希腊字母 ,,,,,等表示。
的圆周上，哪一个点具有最大的或最小的目标函数值。
编辑课件
17
为了一般地描述函数 f x 在点 x 0 处沿 p 方向的变化
情况及变化速度，须引入上升方向和下降方向及方向导数 的概念。
函数 f x 在点 x 0 处沿 p 方向的变化反映的是函数 f x 在一条直线上的变化，空间中由一点 x 0 和一方向 p
22
几个常用函数的梯度公式
（1）若 f x C ，则 f x0 ，即 C0 ；
（2） bTxb ；
（3） xTQx2Qx；
（4） xTx2x .
2. Hesse矩阵
问：函数 f x 关于变量 x 的二阶导数又是什么？
先来看什么是向量值函数的可微。
定义1.11 设 g :D R n R m ,x 0 D 若 g x 。的所有分量
m infx1,x2, ,xn或 m axfx1,x2, ,xn
解法：解方程组
第二，仅含等式约束的极值问题
m infx1,x2, ,xn
s.t.hix1,x2, ,xn 0,编辑课i件1,2, ,l(ln)
3
或 m axfx1,x2, ,xn s.t.hix1,x2, ,xn0, i1,2, ,l(ln)
定义1.9 设 f : Rn R1在点 x 0 处可微， e 是非
零向量 p 方向上的单位向量。如果极限
limfx0tefx0
t 0
t
存在，则称其为函数 f x 在点 x 0 处沿 p 方向的方向导数，
记作
f x0
p
。
思考： f x 与
fx fx
,,
fx
,
的异同。
p
x1编辑课件x2
xn
19
全局
严格极小点 非严格极小点
编辑课件
7
全局极小点一定是局部极小点。 到目前为止，大多数最优化算法求到的都是局部极小点。 为了求得全局极小点，一种解决办法是，先求出所有的 局部极小点，然后再从中找出全局极小点。
4. 极大值问题与极小值问题的关系
编辑课件
8
max f x
min f x
s.t. h x 0 s.t. h x 0
⑶等值面稠密的地方，目标函数值变化得比较快；等值 面稀疏的地方，目标函数值变化得比较慢；
⑷在极值点附近，等值面（等值线）一般近似地呈现为 同心椭球面族（椭圆线族）。
1.5 梯度和Hesse矩阵
本段讨论都基于对函数 f x 可微的假定。
以下及今后的讨论中还经常要用到以下一些向量的知识。
编辑课件
12
定理1.2又表明：只要 f x0T p0，则 p 方向是 f x
在点 x 0 处的上升方向；只要 f x0T p0，则 p 方向是
f x 在点 x 0 处的下降方向。
编辑课件
20
函数值升降的快慢则是由方向导数绝对值的大小决 定的。绝对值越大，升或降的速度就越快；绝对值越小， 升或降的速度就越慢。这是因为
量，列出目标函数和有关约束条件；
（3）分析模型，选择合适的最优化方法； （4）求解方程。一般通过编制程序在电子计算机上 求得最优解；
（5）最优解的验证和实施。 随着系统科学的发展和各个领域的需求，最优化方
法不断地应用于经济、自然、军事和社会研究的各个领
域。
编辑课件
2
第1章 预备知识
1.1 经典极值问题 1. 例子， 2. 数学模型 第一，无约束极值问题
2 f x 也称为多元实值函数 f x 的Hesse矩阵。
例1.9 P21
编辑课件
25
几个特殊的向量值函数的导数公式：
（1）cO ； （2）xI ；
（3）AxAT ； （4）设 tfx0tp，其中 f:Rn R 1,:R 1 R 1 。则
tf x0 tpT p,
tpT2f x0 tpp.
利用（4），可得多元函数展开到三项的Taylor公式
fx 0 p fx 0 fx 0 T p o p
这个公式与一元函数展开到两项的Taylor公式是相对的。
梯度的性质：当梯度 f x 连续时，
第一，若 f x0，则 f x 必垂直于 f x 过点
x 处的等值面；
编辑课件
16
第二，梯度方向是函数具有最大变化率的方向。
下面以 fx1,x2x1 2x2 21为例来解释这个性质。
等于＝，小于 ，严格小于 。由此
min f x1, x2, , xn s.t. hi x1, x2, , xn 0,
min f x s.t. h x 0
i 1,2, ,l(l n)
（2）
以向量为变量的实向量值函数最优化问题的一般形式
minfx1,x2, ,xn
m in f x
③确定极值点位置，并用以往所学方法求之。
易知本题的极小值点 x* 2,1T。
再复杂点的情形见P13上的例1.7。 虽然三维及以上的问题不便于在平面上画图，图解 法失效，但仍有相应的等值面的概念，且等值面具有以 下性质： ①有不同函数值的等值面互不相交（因目标函数是单值 函数的缘故）；
②等值面不会在区域的内部中断，除了极值点所在的等 值面以外。这是由于目标函编辑课数件 是连续函数的缘故； 11
p
f x0
编辑课件
21
ⅱ) 若 f x0, p
是钝角，则 f x0 0
是锐角，则 f x0 0
p
。
;若
f x0, p
p
因此，方向导数又可以称为函数 f x 在点 x 0 处沿 p
方向的变化率。
使函数值下降最快的方向称为最速下降方向。