第四章 无约束优化方法

第四章
第四章
无约束优化问题标准形式：
无约束优化问题标准形式：
§
§
§
§
§
§
图最速下降法的收敛过程
αα
2
2
例4－1 求目标函数
取初始点
[2,2]
=
x
例4－2 求目标函数解取初始点[2,2]
=x
算出一维搜索最佳步长
§
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
例4－3 用梯度法求下面无约束优化问题：
梯度法的特点
x
给定0,ε
一般迭代式：
§4.3
§4.3
§4.3
§4.3
α0
d 0
x
x 1
x*
1
α1d 1
1()
f −∇x d 1
4-4 共轭方向法
假设目标函数f (x ) 在极值点附近的二次近似函数为
沿某个下降方向
如果能够选定这样的搜索方向，那么对于二
α
0d0
x0x1x*
1
α
1
d1
1
()
f
−∇x d
1。

教学重点
1．鲍威尔法 2．梯度法 3．牛顿法
2
机械优化设计
概述
一、无约束优化方法的数学模型 有约束优化问题模型
L min F ( X * ) = F ( x1，x2， ，xn ), X ∈ R n D : g j ( X ) ≥ 0 j = 1,2,L, m hk ( X ) = 0 k = 1, 2,L, l
12
机械优化设计
一、Powell基本算法 Powell基本算法 1）开始采用坐标轴方向； 开始采用坐标轴方向； 2）每轮迭代产生一个新方向取代原来的第一 方向， 轮迭代后可产生n个彼此共轭的方向； 方向，n轮迭代后可产生n个彼此共轭的方向； 若目标函数为正定二次函数， 3）若目标函数为正定二次函数，n轮结束后 即可到达最优点。 即可到达最优点。
r (k ) r (k ) r (k ) r (k ) r (k ) r (k ) S 1 , S 2 , . . . , S m -1 , S m + 1 , . . . , S n , S n + 1 ,
22
第k+1环的方向组为：
机械优化设计
给定X 给定 0,Si=ei i=1,2,…n, ε
Powell 修正算法
K=0 i=1 方向搜索得一维最优点X 自Xi-1始，沿Si方向搜索得一维最优点 i
N
若powell法中不 需要换向，则 是否仍为共轭 方向法？ 检查两次前后 sn+1是否对函数 的海塞矩阵共 轭即可。
Y
i< n Xn-X0 ≤ε
i=i+1
Y
输出X*=Xn 输出 F*=F（X*） （ ）
x2
x2
o
x1
(2)等值线为如图脊线时--无效 (2)等值线为如图脊线时--无效 -o

X (k)=X*是准确的，由X (k)出发只要迭代一次可得到极小点。 6
2.特点 (1).收敛的速度快，即使到了
x2
最优点邻域时也很快收敛于函数 的局部最优点。
(2).采用定步长迭代，因而 就不能保证每次迭代中目标函
5
X2
4
X1
D
3
数是下降的。 原因：φ (X)仅为目标函数
E2 B
f(X)在X (k)点附近的近似表达 式。 X(k+1)点是φ (X)在牛顿方
X(2) X(1)2S(2)
③ S(3)X(2)X(0)
fX ( 2 ) 3 S ( 3 ) m fX 2 i n S ( 3 )
④
XX (3()3)XX ((02))S (2) 3 S(S3 )(1)
S (3)
(2)
S
S 3
X0 1S 1
Sˆ2 S3
Xˆ 1
Xˆ 2 Sˆ 3
Sˆ1 S2X22ຫໍສະໝຸດ 2X3 X ˆ0X1
⑤ (3) (2) (0)
S X X
[S3]THX(2)X(3)0
23
三、Powell法存在的问题 (1)、对于非二次函数，用Taylor展开只有接近中心处是椭 圆，故收敛就不是二次收敛，即n次不一定达到最优点。 (2)、共轭方向一定是线性无关的。出现线性相关或近似线 性相关，使一些方向漏掉，降维，称为退化，故对Powell法进 行修改，即不一定固定每次去掉的都是第一个方向，而是“哪 个方向好就朝哪个方向走”，从而避免出现线性相关的“退 化”现象。 (3)、修正方法 增加模式移动：
迭代一轮，求出下一轮的初始点和迭代方向。
六、编程实现Powell算法
28
无约束优化方法

，
它表示沿着方向dk做一维搜索， 它的终点xk+1与始点xk的梯度之差
与dk的共轭方向dj正交。
4.5 共轭梯度法
共轭梯度法递推公式：
2 || g || d k 1 g k 1 k 1 2 d k || g k ||
，
(k 0,1, 2,
, n 1)
4.5 共轭梯度法
共轭梯度法步骤：
4.5 共轭方向及共轭方向法
2 1 0 例：求G= 1 2 1的一组共轭向量系d 0、d 1、d 2。 0 1 2
，
d
i 1
vi 1 i 1,r d
r 0
i
r
i 1, j
(d j )T Gvi 1 j T (d ) Gd j
d
0 T
Gd 1 0
4.5 共轭方向及共轭方向法
•共轭方向
设G是n n对称正定矩阵，若n维空间中有m个非零向量d 0、d1、 、d m 1 满足 (d i )T Gd j 0
，
(i, j 0,1,
, m 1) (i j )
则称d 0、d1、 、d m 1对G共轭，或称它们是G的共轭方向。
第四章
4.1 4.2 4.3 4.4 4.5 4.6 4.7
无约束优化方法
概述 最速下降法 牛顿型方法 变尺度法 共轭方向及共轭方向法
共轭梯度法
鲍威尔方法
4.1 概述
数值解法：是利用已有的信息，通过计算点一步
一步地直接移动，逐步逼近最后达到最优点。
xk 1 xk k d k (k 0,1, )
4）收敛速度与目标函数值的性质有关，对等值 线是同心圆的目标函数来说，经过一次迭代就可 以达到极值点。