第四章 无约束优化方法

(k 0,1, 2, )
第四章 无约束优化方法
第三节 牛顿型法
阻尼牛顿法的迭代步骤：
1）给定初始点x 0 , 收敛精度，置k 0; 2）计算f ( x k )、G ( x k )和G ( x k ) 1， 得到d k G ( x k ) 1 f x k ； 3）求x k 1 x k k d k，其中， k 是沿着 d k 进行一维搜索的最佳步长； 4）检查收敛精度。若 | x k 1 x k | ， 则停止迭代，得最优解x* x k 1 ; 否则，k k 1, 转到第二步继续进行 搜索。
第四章 无约束优化方法
第三节 牛顿型法 牛顿型法的基本思想：
利用二次曲线来逐点近似原目标函数，以二次曲线的极
， 小点来近似原目标函数的极小点并逐渐逼近该点。
基本牛顿法的迭代公式：
x k 1 x k d k (k 0,1, 2 )
d k G ( x k )1 f x k
1
( y1 ) 0
经变换后，只需一次迭代，就可找到最优解。 ， 这是因为经过尺度变换：
y1 x1 y2 5 x2
等值线由椭圆变成圆。
第四章 无约束优化方法
第二节 最速下法 最速下降法的特点：
1）对初始搜索点无严格要求；
， 2）收敛速度不快；
3）相邻两次迭代搜索方向互相垂直，在远离极值点处 收敛快，在靠近极值点处收敛慢； 4）收敛速度与目标函数值的性质有关，对等值线是同 心圆的目标函数来说，经过一次迭代就可以达到极值点。
x
k 1
x k f ( x )(k 0,1, )
k k
第四章 无约束优化方法
解 取初始点 x 0 [2,2]T 则初始点处函数值及梯 度分别为
，
f ( x 0 ) 104 2 x1 4 f ( x ) 50 x2 x0 100
，
代入x k 1 x k ak d k 得到新的迭代点； 4）若 | x k 1 x k | ，则停止迭代， 得最优解x* x k 1 ; 否则，k k 1, 转到第二步。
第四章 无约束优化方法
第二节 最速下降法
2 2 例：用最速下降法求目标函数 f ( x ) x 25 x 1 2 的极小点。 ，
第四章 无约束优化方法
第一节 概
在x k 1 x k k d k中，d k 是第k 1次 搜索或迭代方向，称为搜索或迭代方向 ，它是根据数学原理由目标函数和约束
， 条件的局部信息状态形成的。确定 d k的
述
方法很多，相应地，确定使f(x k k d k ) 取极值的 k = *的方法也是不同的，具 体方法已在第三章“一维搜索方法”中 进行了讨论。 d k 和 k的形成和确定方法不同就派 生出不同的n维无约束优化问题的数值解 法。
第四章 无约束优化方法
第三节 牛顿型法
基本牛顿法的迭代公式：
，
x k 1 x k d k (k 0,1, 2 )
d k G ( x k )1 f x k
例：用基本牛顿法求解下列无约束优化问题， 已知x 0 [1,1]T , 0.1。
2 min f ( x) x12 2 x2 2 x1 x2 4 x1
第四章 无约束优化方法
第一节 概 述
无约束优化方法可以分成两类：
• • 一类是利用目标函数的一阶或二阶导数的无约束优化方
，
法（如最速下降法、共轭梯度法、牛顿法及变尺度法）； 另一类只利用目标函数的无约束优化方法（如坐标轮换 法、单形替换法及鲍威尔法等）。
第四章 无约束优化方法
第二节 最速下降法
定义：
x x a1d
* 1
1
d
0 T
Gd 1 0
第四章 无约束优化方法
第四节 共轭方向及共轭方向法 •共轭方向
设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）对于多维无约束问题来说，古典极值理论中令一阶 导数为零，但要求二阶可微，且要判断海赛矩阵为正定 才能求得极小点，这种方法有理论意义，但无实用价值。 和一维问题一样，若多元函数 F(X)不可微，亦无法求解。 ， 但古典极值理论是无约束优化方法发展的基础。
第四章 无约束优化方法
最速下降法就是采用使目标函数值下降得最快的负梯 k ) 作为探索方向，来求目标函数的极小值的 度方向 f ( x， 方法，又称为梯度法。
最速下降法 的迭代公式
xk 1 xk k f ( xk )(k 0,1, )
第四章 无约束优化方法
第二节 最速下降法
为了使目标函数值沿搜索方向 f ( x ) 能够获得最大的 下降值，其步长因子 k应取一维搜索的最佳步长。即有
第四章 无约束优化方法
第四节 共轭方向及共轭方向法 •共轭方向
以二元函数为例： f x
1 T x Gx bT x c 2 我们任意选择一个初始点 x0点， ，
沿着某个下降方向d0作一维搜索
x1 x0 a0d 0 [f ( x1 )]T d 0 0
在下一次迭代时，选择搜索方d1指向极小点x*，
第四章 无约束优化方法
第二节 最速下降法 最速下降法的迭代步骤：
1）给定初始点x 0和收敛精度，置k 0； 2）计算梯度，并构造搜索方向d k f ( x k ); 3）用一维搜索的方法求解
k k min f x a d 得最佳步长ak， k min
k
k k f ( x k 1 ) f [ x k ak f ( x k )] min f [ x a f ( x )] a
min ( ) a
，
根据一元函数极值的必要条件和多元复合函数求导公式，得
'( ) f [ x k f ( x )] f ( x ) 0
第四章 无约束优化方法
第三节 牛顿型法
基本牛顿法的迭代公式：
，
x k 1 x k d k (k 0,1, 2 )
d k G ( x k )1 f x k
阻尼牛顿法的迭代公式： d k G ( x k ) 1 f x k
x k 1 x k k d k
k k T k
[f ( x )] f ( x ) 0
k 1 T k
(d ) d 0
k 1 T k
第四章 无约束优化方法
第二节 最速下降法
在最速下降法中，相邻两个
迭代点上的函数梯度相互垂直。 ， 而搜索方向就是负梯度方向，因 此相邻两个搜索方向互相垂直。 这就是说在迭代点向函数极小点 靠近的过程，走的是曲折的路线。 形成“之”字形的锯齿现象，而 且越接近极小点锯齿越细。 图4-2 最速下降法的搜索路径
，
第四章 无约束优化方法
第三节 牛顿型法
阻尼牛顿法的迭代公式： d k G ( x k ) 1 f x k
，
x k 1 x k k d k
(k 0,1, 2, )
例：用阻尼牛顿法求解下列无约束优化问题， 已知x 0 [1,1]T , 0.1。
2 min f ( x) x12 2 x2 2 x1 x2 4 x1
第一节 概 述
xn ]T
无约束优化问题是： 求n维设计变量
x [ x1 x2 使目标函数 f ( x ) min min f ( x) x Rn
，
对于无约束优化问题的求解，可以直接应用第二章的 极值条件来确定极值点位置。这就是把求函数极值的问 题变成求解方程 f 0
这是一个含有n个未知量，n个方程的方程组，并且一般是非线性的。对于 非线性方程组，一般是很难用解析方法求解的，需要采用数值计算方法逐 步求出非线性联立方程组的解。
y1=x1,
则函数f(X)变为：
0
，
y2=5x2
( y1 , y2 ) y y
2 1
T
2 2
其等值线由椭圆变成一簇同心圆。
T
仍从 x [2,2] 即 y [2,10] 出发进行最速下降法寻优。 此时：
0
( y 0 ) 104
2 y1 4 ( y ) 2 y2 y0 20
第四章 无约束优化方法
第一节 概 述
第1章所列举的机械优化设计问题，都是在一定的限制条件下追 求某一指标为最小，它们都属于约束优化问题。工程问题大都如此。
为什么要研究无约束优化问题?
， （1）有些实际问题，其数学模型本身就是一个无约束优化问题。
（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也是 优化方法的基础。
第四章 无约束优化方法
第一节 概 述
数值解法：是从给定的初始点x0出发，沿某一搜索方向d0
进行搜索。确定最佳步长α，使函数值沿d0方向下降最大。 依此方式按下述公式不断进行，形成迭代的下降算法。
xk 1 xk k d k (k 0,1, )
，
1）选择迭代方向即探索方向； 2）在确定的方向上选择适当步长迈步进行探索。 各种无约束优化方法的区别就在于确定其搜索方向 dk 的方 法不同。所以搜索方向的构成问题是无约束优化方法的关键。
•正交
当G=I（单位矩阵）时，有(d i )T d j 0 (i j )， 即向量d0、d1、 、d m1互相正交。