《数值最优化方法》PPT课件

x(k)是函数在{x(0) +1p1+2p2+···+kpk,1,2···,k∈R}中的
极小点.
最终x(n)= u1 p1+u2 p2+···+un pn =x* 即迭代过程同样在n步之后找到最优点.
因此,对二次函数
f ( x) 1 xTGx bT x c 2
我们可以找到n个方向(向量),对其依次进行一维搜索,最
8
共轭方向法的思路
|| (s1 1 u1) p1 (s2 u2 ) p2 L (sn un ) pn ||G2
(s1 1 u1) p1 (s2 u2 ) p2 L (sn un ) pn ,
( s1
1
u1 )
p1
( s2
n
u2
)
p2
L
(sn un ) pn
(s1 1 u1)2 || p1 ||G2 (si ui )2 || pi ||G2
即p1,p2,···,pn线性无关,且 pi , pj 0(i j)
设问题的最优解x*= -G-1b在这组基底下的表示为x*= u1 p1+u2 p2+···+un pn
任取初始点x(0) =s1 p1+s2 p2+···+sn pn, 在方向p1上进行 一维搜索,即求解问题
min || (s1 1 u1) p1 (s2 u2 ) p2 L (sn un ) pn ||G2
z
x(1) O
x(3) =x* x(2) y
x(0)
x
5
共轭方向法的思路
上面的方法对一般的二次函数是否适用呢?
考虑问题
其中
G
1 2

f ( X 0 ) f ( X1) f ( X k ) f ( X k 1)
一 最优化问题总论
如果是求一个约束的极小点，则每一次迭代的新点都应该在约束可 行域内，即 X k D，k 0，1，2，
下图为迭代过程
一 最优化问题总论
（二）收敛速度与计算终止准则
（1）收敛速度
作为一个算法A，能够收敛于问题的最优解当然
x1 x2
即求
2x，1 5x2 40
x1 0 ， x2 0
max f (x1, x2 ) x1 x2
2x1 5x2 40，
x1
0，x2
0．
一 最优化问题总论
最优化问题的数学模型包含有三个要求：即变
量（又称设计变量）、目标函数、约束条件．
一、变量 二、目标函数 三、约束条件 四、带约束条件的优化问题数学模型表示形式
t f (x1，x2 )
t c
L
L在 三维空间中曲面
与[平x1， 面x2 ]T 有一条交
线 ．交线在平面上的投影曲线是 ，可见曲线上的点到平
面
的高度都等于常数C，也即曲线上的的函数值都
具有相同的值．
一 最优化问题总论
当常数取不同的值时，重复 上面的讨论，在平面上得到一族 曲线——等高线.
等高线的形状完全由曲面的 形状所决定；反之，由等高线的 形状也可以推测出曲面的形状．
线（如图），不等式约束把坐标平面分成两部分当中的一部分 （如图）．
一 最优化问题总论
综上所述，当把约束条件中的每一个 等式所确定的曲线，以及每一个不等式所 确定的部分在坐标平面上画出之后，它 们相交的公共部分即为约束集合D．
一 最优化问题总论
例1.4 在坐标平面上画出约束集合

最优化方法
（最优化课件研制组）
编辑课件
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）

f x0
据此有
ⅰ) 等号成立当且仅当 p 与f x0 同方向或与 f x0
同方向。且当
p与
f x0
同方向时，f x0
p
取到最大值
f x0 。当 p 与 f x0 同方向时，f x0 取到最小值 p
f x0
第1章 预备知识
1.1 经典极值问题 1. 例子， 2. 数学模型 第一，无约束极值问题
min f x1, x2, , xn 或 max f x1, x2, , xn
解法：解方程组 第二，仅含等式约束的极值问题
min f x1, x2, , xn s.t. hi x1, x2, , xn 0, i 1, 2, ,l(l n)
p
思考：f x 与
f x f x f x
,
,,
的异同。
p
x1 x2
xn
根据极限理论，易见
若
f x0
p

0，则p方向是 f
x
在点
x0 处的上升方向；
若 f x0 0，则 p方向是 f x在点 p
x0
处的下降方向。
因此，方向导数的正负决定了函数值的升降。
例1.8 P19
几个常用函数的梯度公式
（1）若 f x C ，则 f x 0
（2） bT x b ；
（3） xTQx 2Qx ；
（4） xT x 2x .
，即 C 0 ；
2. Hesse矩阵
问：函数 f x 关于变量 x 的二阶导数又是什么？
1.5 梯度和Hesse矩阵
本段讨论都基于对函数 f x 可微的假定。

数值积分与微分
数值积分
通过数值方法近似计算定积 分，如梯形法则、辛普森法 则等。
数值微分
通过数值方法近似计算函数 的导数，如差分法、中心差 分法等。
常微分方程的数值解法
通过数值方法求解常微分方 程，如欧拉方法、龙格-库塔 方法等。
03
数值分析的稳定性与误差分析
误差的来源与分类
模型误差
由于数学模型本身的近 似性和简化，与真实系
非线性代数方法
非线性方程组的求解
通过迭代法、直接法等求解非线性方程组，如牛顿法、拟牛顿法 等。
非线性最小二乘问题
通过迭代法、直接法等求解非线性最小二乘问题，如GaussNewton方法、Levenberg-Marquardt方法等。
多项式插值与逼近
通过多项式插值与逼近方法对函数进行近似，如拉格朗日插值、 样条插值等。
机器学习与数值分析的交叉研究
机器学习算法
利用数值分析方法优化和改进机器学 习模型的训练和预测过程，提高模型 的准确性和效率。
数据驱动的模型
通过数值分析方法处理大规模数据集 ，提取有用的特征和模式，为机器学 习模型提供更好的输入和输出。
大数据与数值分析的结合
大数据处理
利用数值分析方法处理和分析大规模数 据集，挖掘其中的规律、趋势和关联信 息。
数值分析PPT课件
contents
目录
• 引言 • 数值分析的基本方法 • 数值分析的稳定性与误差分析 • 数值分析的优化方法 • 数值分析的未来发展与挑战
01
引言
数值分析的定义
数值分析
数值分析是一门研究数值计算方法及 其应用的学科，旨在解决各种数学问 题，如微积分、线性代数、微分方程 等。

1 ' 2 ' 3 ' 1 17
1 x 3 2 x1 x5 2 x 4 16 4 x1 1 x2 3 x5 4
1 ' 2 ' 3 ' 1 17
令非基变量
x1 x 5 0
得到另一基可行解
例9.2.3
试以下例来讨论如何用单纯形法求
（生产计划安排问题）某工厂在计划期内要安排生产Ⅰ、 Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B 两种原材料的消耗，如表1-1所示。
资源 产品
设
备
原材料 A 原材料 B
Ⅰ 1 4 0
Ⅱ 2 0 4
拥有量
8台时 16 kg 12 kg
该工厂
• 每生产一件产品Ⅰ可获利2元， • 每生产一件产品Ⅱ可获利3元， • 问应如何安排计划使该工厂获利最多?
x1 x2 a 1 , m 1 x m 1 a 1 n x n b1 a 2 , m 1 x m 1 a 2 n x n b 2
1 22
x m a m , m 1 x m 1 a m x n b m x
x
(1)
(0,3,2,16,
0) , 且 z 9
T
z 9 2 x1
3 4
x5
• 从目标函数的表达式可以看到，非基变量x1的系数 是正的，说明目标函数值还可以增大，X(1) 还不是 最优解。 • 于是再用上述方法，确定换入、换出变量，继续迭 代，再得到另一个基可行解X(2) X(2)=(2,3,0,8,0)T • 再经过一次迭代，再得到一个基可行解X(3) X(3)=(4,2,0,0,4)T • 而这时得到目标函数的表达式是： z=14-1.5x3-0.125x4 (1-19)

其实，a,b aTb a1, a2,
b1
,
an
b2
。
bn
向量也常用希腊字母 , , , ,, 等表示。
向量内积的性质：
ⅰ) , ,（对称性）；
ⅱ) , , , k, k , （线性性）；
ⅲ) , 0 ,当且仅当 0 时，, 0（正定性）；
向量的长 ,
这个公式与一元函数展开到两项的Taylor公式是相对的。
梯度的性质：当梯度 f x 连续时，
第一，若 f x 0 ，则 f x 必垂直于 f x 过点
x 处的等值面；
第二，梯度方向是函数具有最大变化率的方向。
下面以 f x1, x2 x12 x22 1 为例来解释这个性质。
上图是该函数的等值线图。
的异同。
p
x1 x2
xn
根据极限理论，易见
若
f x0
p
0，则p方向是 f
x
在点
x0 处的上升方向；
若 f x0 0，则 p方向是 f x在点 p
x0
处的下降方向。
因此，方向导数的正负决定了函数值的升降。
定理1.2
设 f : Rn R1 在点 x0 处可微，则
f x0
p
f
x0
T
e
其中 e 是非零向量 p 方向上的单位，向量。
f x0
p
f
x0
e
cos
f
x0 , p
f x0
p
f
x0
cos
f
x0 , p
f x0
据此有
ⅰ) 等号成立当且仅当 p 与f x0 同方向或与 f x0
同方向。且当
p与

x4 a5
例3：两杆桁架的最优设计问题。由两根空心圆杆组成的对称两
杆桁架，其顶点承受负载为2p，两支座之间的水平距离为2L，圆
杆的壁厚为B，杆的比重为ρ，弹性横量为E，屈服强度为δ。求在
桁架不被破坏的情况下使桁架重量最轻的桁架高度h及圆杆平均
直径d。
B
2p
p1
p
2
h
h
d
2p
2L
受力分析图
圆杆截面图
问题追求的目标是圆柱体表面积最小。即
min 2 r h 2 r2
则得原问题的数学模型：
min2rh 2r2
s.t.
r2h40 3
利用在微积分学中所学的Lagrange乘子法可求解本问题
L r.h .2 rh2 r2 r2h4
3
分别对r、h、λ求偏导数，并令其等于零，有:
L r
最优化技术工作被分成两个方面，一是由实际生产或科
技问题形成最优化的数学模型，二是对所形成的数学问题进
行数学加工和求解。
对于第二方面的工作，目前已有一些较系统成熟的资料， 但对于第一方面工作即如何由实际问题抽象出数学模型，目 前很少有系统的资料，而这一工作在应用最优化技术解决实 际问题时是十分关键的基础，没有这一工作，最优化技术将 成为无水之源，难以健康发展。
因此，我们在学习本课程时要尽可能了解如何由实际问 题形成最优化的数学模型。
为了便于大家今后在处理实际问题时建立最优化数学模 型，下面我们先把有关数学模型的一些事项作一些说明。
所谓数学模型就是对现实事物或问题的数学抽象或描述。 建立数学模型时要尽可能简单，而且要能完整地描述所研究 的系统，但要注意到过于简单的数学模型所得到的结果可能 不符合实际情况，而过于详细复杂的模型又给分析计算带来 困难。因此，具体建立怎样的数学模型需要丰富的经验和熟 练的技巧。

0.91
0.91
3 (x 5)2 ( y 3)2 18 (x 1)2 ( y 1)2
0.91
0.91
8 (x 3)2 ( y 1)2 6 (x 5)2 ( y 1)2 ] / 84
▪ 问题为在区域0=<x=<6, 0=<y=<6上求z=f(x,y)的 最小值。
•15
绘制目标函数图形
xnew=a+(b-a)*rand(1); ynew=c+(d-c)*rand(1); znew=subs(z,[x,y],[xnew,ynew]); if znew<zmin
xmin=xnew; ymin=ynew; zmin=znew; fprintf('%4.0f %1.6f %1.6f %1.6f\n', n, xmin, ymin, zmin); end end
•16
16/5+...+17/140 (x2-10 x+26+y2-2 y)91/200
20
15
10
5
5 0
5 0
-5
-5
y
x
•17
绘制等值线图
ezcontourf(z,[0 6 0 6])
colorbar, grid on
16/5+...+17/140 (x2-10 x+26+y2-2 y)91/200 6
据的统计分析给出：对离救火站r英里打来
的求救电话，需要的响应时间估计
为
。下图给出了从消3.防21管.7r0员.91 处得到
的从城区不同区域打来的求救电话频率的
估计数据。求新的消防站的最佳位置。
•13

回想最优解的定义，可行的概念对 于不等式约束是怎么样的概念？
min s .t . f (x) c(x) 0
可行域为
Q { x | c ( x ) 0 }。
0
可行方向： 设 x Q ， 为一个向量。如果存在 d 使得对任意的 一个可行方向。
0
实数 0 ，
0
[ 0 , ] 有 x d Q , 则称 d 为 x 处的
有缺点吗？
14
例题
15
例题
16
收敛性
17
18
优缺点
优点：
19
作业
• P129 习题：3.7 （1），（2）
20
最优化方法补充内容7
共轭梯度法
共轭方向
怎么解释？
实际意义是什么？
共轭方向法的框架
共轭梯度法的构造
翻译成文字语言
算法的下降性质
如果初始方向不是负梯度方向
x 2 1 3 x2 2 0 2 x2 0 1 2 3
这与 2 0 矛盾。 (3) 若 x1 0 , x 2 0 :
2 0
x1 1 3 x1 3 0 3 x1 0 1 3 3 x1 1 2 3 这与 3 0 矛盾。 x2 1 3 3 (4) 若 x1 0 , x 2 0 : 1 (4 x1 x 2 ) 0 2 x1 0 2 3 0 3 x2 0 x1 1 3 x1 x 2 4 x1 x 2 x 2 1 3 1 , 2 , 3 , x1 , x 2 0
*
故 x ( 1 ,1 ,1 ) 为 KT 点。

可以用一个 x 的函数
N(x)=max|xi|来度量 x 的“大小”, 而且这种度量 x 的 “大小”的方法计算起来比欧氏范数方便. 在许多应用 中 , 对度量 x的“大小”的函数 N(x) 都要求是正定的、 齐次的且满足三角不等式 . 下面我们给出向量范数的
一般定义.
定义2.(向量的范数) 如果向量xRn(或Cn)的某个实值函 数f(x)=||x||，满足条件: (1) ||x||0(||x||=0当且仅当x=0) (正定性), (2) ||αx||=|α| ||x||, 对任何αR(或αC)(齐次性), (3) ||x+y|| ||x||+||y|| (三角不等式). 则称f(x)=||x||是Rn(或Cn)上的一个向量范数(或模).
例 1.1.2 （ 数 据 拟 合 问 题 ） 设 有 观 测 数 据 (xk, yk), k=1,…,5,其值由表1.1给出： k 1 2 3 4 5
xk yk
2 2.01
4 2.98
5 3.50
8 5.02
9 5.47
试用一个简单的函数关系拟合这些数据。
2. 最优化问题的数学模型
min f ( x), x D Rn ,
定义1.9
都有 f x0 tp f x0 ，则称
x0
f x tp f x 0 ，则称 都有 0
处的上升方向；若存在
p
0,
方向是 是非
方向上的单位向量。如果极限 f x0 te f x0 lim t 0 t f x 在点 x0 处沿 p 方向的方向导数， 存在，则称其为函数 f x0 记作 。 p f x f x f x 思考： f x 与 , , , 的异同。 x1 x2 xn p 零向量

由上面的引理， P ( xk , k ) 单调上升，并且根据上面的 P( xk , k ) p0 。 式子 P ( x , ) 有上界，所以，
k k
根据引理，我们还知道 f ( xk ) 单调增加，并且
f ( x k ) P ( x k , k ) f ( x * )
（4.1.3）
惩罚项所具有的性质应该怎么样呢？ 怎么取呢？
想一想 有没有其他形式的惩罚项。
6
一般约束优化问题
min f ( x ) s.t. ci ( x) 0
ci ( x) 0 i I l 1,2,, m
i E 1,2, , l
怎么构造罚函数？
~ P x, f ( x) P x l m ~ P x ci ( x ) min0, ci ( x )
得到 以 xk 为 近 似 最 优 解 ， 停 止 。 否 则 ， 令
~ minP x, k f ( x) k P x
k 1 c k , k k 1 ，转 Step 2。
那么这类方法是否能收敛呢？？
13
~ minP x, k f ( x) k P x
2 2 min f x1 , x2 x1 x2 s.t. x1 x 2 2 0
其中的 表示很大的正数。
2 2 P x1 , x 2 , x1 x 2 x1 x 2 2


2
2 x1 x 2 2 1
当 时， x1 x 2 1 即无约束优化问题最优解的极限为原问题的解。
14
证明 (1)因为 xk 是 P ( x , k ) 的极小点，且 k 1 k ，故