机械优化设计_第四章无约束优化方法

X
k
T
f
X 0
K
f
x
k 1
f
T
x
k

0
或 d
k 1

T
d
k
0
机械优化设计 由此可知，在最速下降 法中，相邻两个迭代点上 的函数梯度相互垂直。而 搜索方向就是负梯度方向， 因此相邻两个搜索方向互 相垂直。这就是说在迭代 点向函数极小点靠近的过 程，走的是曲折的路线， 形成“之”字形的锯齿现 最速下降法的搜索路径 象，而且越接近极小点锯 齿越细。
机械优化设计 最 速 下 降 法 的 程 序 框 图
机械优化设计 例：求目标函数 f X x 解法1：取初始点
f
2 1
T
25 x2
2
的极小点
X
0
2, 2
，则初始点处的函数值
X
2 0 2 4 2 4 0 1 0 0 2 1 0 0 0
4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计 算量和存储量大。此外对于二阶不可微函数也不适用。 虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收 敛最快的优点，可为其他算法提供思路和理论依据。
不同等值线的迭代过程
机械优化设计
讨论
f
x1 , x 2
x1 2 5 x 2
2 2
1 2
x1
2 x2 0
0 50
x1 x2

y1 , y 2
y1 y 2
2 2
1 2
y1
2 y2 0
0 2
1 0
y1 y 2
2
2
Y
0
104
Y
0

2 y1 4 20 2 y2 Y 0
2 4 2 4 0 Y Y 0 Y 0 10 20 10 20 0
机械优化设计 （2）阻尼牛顿法的计算步骤
1）给定初始点 X 0，收敛精度 ，置 k 0 2）计算
d
f
k
X 、
k
2
f
k
X 、
k
2
f
X
k
1
f
2
X
1
f
X
k
3）求 X
k 1
X
k
kd
X
k
4）检查收敛精度。若
X
k 1
f
X ，使函
X
k
kf
X
k

( k 0,1, 2 )
机械优化设计 2、最速下降法的原理
（1）使 d
f
X ，按此规律不断走步，形成迭代算法：
k
X
k 1
X
kf
X
k

( k 0,1, 2 )
k f x akf
k

T
f
2
x
k
x x
k

设 X k 1 为 X 的极小点，它作为 f X 极小点 X 的下一个近似点，根据极值必要条件：
X
k 1
0 即 f X
k
2
2
f
X X
k
k 1
X
k
0
X
k 1
X
k
k
f
1）有些实际问题，其数学模型本身就是一个无约束问题；
2）通过熟悉它的解法可以为研究约束优化问题打下良好的 基础；
3）约束优化问题的求解可用通过一系列无约束优化方法来 达到。
所以无约束优化问题的解法是优化设计方法的基本 组成部分，也是优化方法的基础。
机械优化设计
一、概述
1、无约束优化问题 T , xn 求 n 维设计变量 X x1 , x使目标函数 2 f X m in ，而对 X 没有任何限制条件。 2、求解方法 （1）利用极值条件来确定极值点的位置。 （2）数值计算方法——搜索方法 基本思想：从给定的初始点 x 0 出发，沿某一搜索方向 0 0 d 进行搜索，确定最佳步长 0 使函数值沿 d 下降
f
X
1
3 .6 8 6 1 6 4
经过10次迭代后，得到最优解：
X

0, 0
T
f
X

0
该问题的目标函数的等值线为一族椭圆，迭代 点走的是一段锯齿形路线。
机械优化设计 解法2：引入变化

y 1 x1 y2 5 x2
，则目标函数 f x , x 变为
1 2
y1 , y 2
k 1
X
k

，则 X X k 1 ，停机；
否则置 k k 1 返回到2），继续进行搜索。
机械优化设计 （3）阻尼牛顿法的 程序框图
机械优化设计 方法特点：
1）初始点应选在极小点附近，有一定难度；
2）尽管每次迭代都不会是函数上升，但不能保证每次 都下降；
3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不 能构造牛顿法方向；
函数梯度为局部性质，因此并非“最快”。
机械优化设计
梯度法的迭代历程
机械优化设计
方法特点
1）初始点可任选，每次迭代计算量小，存储量少， 程序简短。即使从一个不好的初始点出发，开始 的几步迭代，目标函数值下降很快，然后慢慢逼 近局部极小点；
2）任意相邻两点的搜索方向是正交的，它的迭代 路径为绕道逼近极小点。当迭代点接近极小点时， 步长变得很小，越走越慢。
最大。依此方式不断进行，形成迭代的下降算法：
X
k 1
X
k
kd
k
( k 0,1, 2 )
机械优化设计 3、算法框图
机械优化设计 4、无约束优化方法的分类 搜索方向的构成问题是无约束优化方法的关键。 k 根据确定其搜索方向 d 方法不同，可分为：
（1）只利用目标函数值的无约束优化方法（或称直接法， 即不使用导数信息），如：坐标轮换法、单形替换法及鲍威 （Powell）法。 直接法不必求函数导数，只计算目标函数值。适用于求 解变量个数较少（小于20）的问题，一般情况下效率较低。
y1 y2
可以看出二者的对角形矩阵不同，前者的 等值线为一族椭圆，后者的等值线为一族同 心圆，这说明对角形矩阵是表示度量的矩阵 或者是表示尺度的矩阵，最速下降法的收敛 速度和变量的尺度有很大关系。
机械优化设计 3、最速下降法收敛速度的估计式
X
M
k 1
X

2 m 1 X 2 M
0
0
26 52
0 .5
2 4 0 0 Y 0 1 0 2 0， 0 0
1
Y1 0
经过坐标（尺度）变化后，只需要经过一次迭代，就可找到 最优解：
X

0, 0
T
f
X 0

机械优化设计
2
的极小值
解：取初始点
f
X
0
2, 2
T
，则
f
2
X
0
2 x1 4 50 x2 X 0 100
X
0
2 0
0 50
f
2
X
0
0
1
1 2 0
1 50 0
''
'
( k 0 ,1, 2 , )
机械优化设计 1、牛顿法
对于多元函数 f X ，设 X k 为 f X 极小点 X 的第一 个近似点， f X 泰勒展开，保留到二次项，得:
f
x x
f
x
k
f
x
k

T
x x
k

1 2
x x
机械优化设计
第四章
无约束优化方法
一、概述 二、最速下降法（梯度法） 三、牛顿型方法（牛顿法和阻尼牛顿法） 四、共轭方向和共轭方向法 五、共轭梯度法 六、变尺度法 七、坐标轮换法
机械优化设计 实际中的工程问题大都是在一定限制条件下追 求某一指标为最小，属于约束优化问题。 为什么要研究无约束优化问题？
及梯度分别为：
X 104
0
f
X
0
2 x1 4 5 0 x 2 1 0 0
X
1
X
0
0 f
0
0 为一维搜索最佳步长，应满足极值必要条件
f X
1
m in

0 f X f X
0
m in (2 4 )
0
代入牛顿法迭代公式可得:
1 2 2 2 0 1 50 0
X
1
X
2 f
X

1
f
X
0
4 0 1 0 0 0
从而经过一次迭代即求得极小点和函数极小值。
机械优化设计
（2）利用目标函数的一阶或二阶导数的无约束优化方法 （或称间接法）如：最速下降法（梯度法）、共轭梯度法、 牛顿法及变尺度法； 间接法除了要计算目标函数值外，还要计算目标函数的 梯度，有的还要计算其海赛矩阵；
机械优化设计
二、最速下降法（梯度法）