5_郭科_常用无约束最优化方法

第五章 常用无约束最优化方法本章开始讨论多维无约束最优化问题

min f ( X )都有

(5.1)

其中 f:R n R1 .这个问题的求解是指，在 点 X * ,使得对于任意的 X R n

Rn

中找一

f (X *) f (X )

(5.2)

成立，则点 X * 就是问题(5.1)的全局最优点.但是，大 多数最优化方法只能求到局部最优点，即在 R n 中找到一 点 X * ,使得式(5.2)在 X * 的某个领域中成立.这个 矛盾对于实际问题一般容易解决.根据问题的实际意义多 半可以判定用优化方法求出的局部最优解是否为全局最优 解.而在理论上这是个比较复杂的问题，本书不涉及.

无约束优化方法是优化技术中极为重要和基本的内容之 一.它不仅可以直接用来求解无约束优化问题，而且很多约束 优化问题也常将其转化为无约束优化问题，然后用无约束优化 方法来求解.另外，有些无约束优化方法只需略加处理，即可 用于求解约束优化问题. 无约束优化理论发展较早，比较成熟，方法也很多，新的 方法还在陆续出现.把这些方法归纳起来可以分成两大类：一 类是仅用计算函数值所得到的信息来确定搜索方向，通常称它 为直接搜索法，简称为直接法，另一类需要计算函数的一阶或 二阶导数值所得到的信息来确定搜索方向，这一类方法称为间 接法(解析法).直接法不涉及导数、Hesse矩阵，适应性强， 但收敛速度较慢；间接法收敛速度快，但需计算梯度，甚至需 要计算Hesse矩阵.一般的经验是，在可能求得目标函数导数 的情况下还是尽可能使用间接方法；相反，在不可能求得目标 函数的导数或根本不存在导数的情况下，当然就应该使用直接 法.

§5.1 最速下降法对于问题(5.1)为了求其最优解，按最优化算法的基本思 想是从一个给定的初始点 X 0出发，通过基本迭代格 式 X k 1 X k t k Pk ,按照特定的算法 A产生一串点列 { X k } ,如果 点列收敛，则该点列的极限点为问题(5.1)的最优解. 在基本迭代格式 X k 1 X k t k Pk 中，每次迭代搜索方向 Pk 取为目标函数 f (X )的负梯度方向，即 Pk f ( X k ) ,而每次迭 代的步长 t k取为最优步长，由此所确定的算法 A称为最速下 降法.

为了求解问题(5.1),如图5.1所示，假定我们 已经迭代 了 k 次，获得了第 k个迭代点 X k .现在从 X k 出发，可选择的 下降方向很多，一个非常自然的想法是沿最速下降方向(即负 梯度方向)进行搜索应该是有利的，至少在 X k 邻近的范围内 是这样。因此，取搜索方向为 Pk f ( X k ) 。

为了使目标函数在搜索方向上获得最多的下降，沿 Pk 进行 一维搜索，由此得到第 k 1 个迭代

点，即 ， tk 其中步长因子 t k按下式确定 X k 1 X k f ( X k )f ( X k t k f ( X k )) min f ( X k t f ( X k )) 也可记为

X k 1 ls ( X k , f ( X k ))

t

(5.3)

显然，令 k 0, 1, 2, 就可以得到一个点列 X 0 , X 1 , X 2 , 其中 X 0 是初始点，由计算者任意选定.当 f (X ) 满足一定的 条件时，由式(5.3)所产生的点列 { X k }必收敛于的极小点.g 以后为书写方便，记 g ( X ) f ( X ) 因此，( X k ) f ( X k ) .

在不发生混淆时，再记 g k g ( X k ) f ( X k ).

二、最速下降法迭代步骤

已知目标函数f (X ) 及其梯度 g (X ) ,终止限 1 、 2 和 3 . (1)选定初始点 X 0 ,计算 0 f ( X 0 ), 0 g ( X 0 );置 k 0 . g f (2)作直线搜索：k 1 ls( X k , g k );计算 f k 1 f ( X k 1 ), g k 1 g ( X k 1 ) . X (3)用终止准则检测是否满足：若满足，则打印最优解 X k 1 , ( X k 1 )停 f 机；否则，置 k k 1 转(2). 最速下降法算法流程如图5.2所示. 将最速下降法应用于正定二次函数 1 T (5.4) Tf (X ) 2 X QX b X c可以推出显式迭代公式. 设第 k 次迭代点为 X k ,我们来求 X k 1 的表达 式. 对式(5.4)关于 X 求梯度，有

g ( X ) QX b因此，

(5.5)

g k g ( X k ) QX k b

(5.6)

现在从 X k 出发沿 g k 作直线搜索以确定 X k 1,于 是， (5.7) X k 1 X k t k g k 其中 t k 是最优步长因子. 又因式(4.2),有 g ( X k 1 )T g k 0 ,再利用 (5.5),(5.6)和(5.7)可得： [Q( X k t k g k ) b]T g k 0 或 [ g k t k Qg k ]T g k 0 , T gk gk 由此解出：tk

代入(5.7)中得到，

T g k Qg k

X k 1

T gk gk Xk T gk g k Qg k

(5.8).

这就是最速下降法用于二次函数的显式迭代公式

2 2 例5.1试用最速下降法求函数f ( x1 , x2 ) x1 4 x2 的 极小点.迭代两次，计算各迭代点的函数值，梯度及 其模，并验证相邻两个搜索方向是正交的.设初始点 为 X 0 [1, 1]T. 2 0 解 与(5.4)比较，得 Q 0 8 梯度表达式是

由f ( x0 )

1 X0 1

2 x1 f ( X ) f ( x1 , x 2 ) 8x2

,计算出

12

4 12

2 5 g 0 f ( X 0 ) 8

|| g 0 || 8.24621

因为目标函数是二次的，可以使用式(5.8),所以 有T 1 2 0.73846 g0 g0 X1 X 0 T g 0 0.13077 g 0 Qg 0 1 8 0.04616

计算f ( X 1 ) 0.73846 2 4 0.04616 2 0.55385, 1.47692 g1 f ( X 1 ) , 0.36923 || g1 || 1.52237.T 0.73846 1

.47692 g1 g1 X 2 X1 T g1 0.42500 0.36923 g1 Qg1 0.04616 0.11076 , 0.11076 0.22152 f ( X 2 ) 0.06134, g 2 f ( X 2 ) , 0.88008 || g 2 || 0.91335.

T T 因为 g1 g0 0.0000,g2 g1 0.0000,

由此说明相邻两个搜索方向 P

P1 g1 是正交的.

1 g1

与P