在 X(k) 和 X(k+1)两点处的梯度可以表示为 ▽f (X(k) ) = H X(k) + B （1）
▽f (X(k+1) ) = H X(k+1） + B （2） （2）－ （1）得 ▽f (X(k+1) ) － ▽f (X(k) ) = H ( X(k+1) － X(k) )（3） （3）式两边同时左乘[S(j) ]T得
机械优化设计
太原科技大学 张学良
.
1
第四章 无约束优化的直接搜索法
X (k+1)=X (k) + (k) S(k) (k =0 , 1 , 2 , …)
各种无约束优化方法的区别就在于确定其
搜索方向S(k)的方法不同，所以搜索方向的构成
问题是无约束优化方法的关键。根据构造搜索
方向所使用的信息性质的不同，无约束优化方
轴方向ei (i=1, 2, … , n)的一维优化问题来求解， 并记完成n次一维搜索为一轮。若一轮搜索后
未得到满足精度要求的最优点，则继续下一
轮迭代搜索。如此反复，直至得到满足精度
要求的最优点为止。在每一轮搜索中，每次
迭代仅对n元函数的一个变量沿其坐标轴方向
进行一维搜索，其余n-1个变量均保持不变，

4）判断是否满足迭代收敛准则
|| Xn(k) – X0(k) ||≤ ？
若满足，则输出最优解: X * = Xn(k) ，f * = f (X * )
否则，令X0(k+1) = Xn(k) ，k k+1，返回3）。
.
7
举例： 用坐标轮换法求目标函数
f (X) = x12 + x22 – x1x2 – 4x1 – 10x2+ 60 的无约束最优解。初始点X(0)= [ 0 0 ]T ，迭代 收敛精度=0.1。 • 坐标轮换法搜索过程和收敛情况讨论
这说明：
沿 S(j) 方 向 分 别 对 函 数 做 两 次 一 维 搜 索 ， 得到两个极小点X(k) 和 X(k+1)，该两点的连 线方向S(k)与S(j)是关于H 共轭的方向。
.
14
x2 S(k) X*
X(k+1) S(j)
X(k)
x1
.
15
上述生成共轭方向的方法完全可以推广
到n维优化问题中，即在n维空间中，按上述
方法可以生成n个相互共轭的搜索方向。
• 鲍威尔法的基本原理和迭代过程
1）采用坐标轮换法顺次沿n个坐标轴方
向 进 行 一 维 搜 索 ， 然 后 以 初 始 点 X(0) 和 终 点
Xn(1)构成一个新的方向 S(1) ，并以次方向搜索 方向再作一维搜索得到极小点Xn+1(1)。
设是X(k) 和 X(k+1)为从不同点出发，沿同 一方向进行一维搜索而得到的两个极小点。。
▽f (X(k) )
S(j)
S(j)
▽f (X(k+1) )
X(k)
X(k+1) S(k)
[S(j) ]T ▽f (X(k) ) = 0
[S(j) ]T ▽.f (X(k+1) ) = 0
12
具有正定对称矩阵H的二次函数 f (X) = 0.5 XT H X + BT X + C
[S(j) ]T[▽f (X(k+1) )－▽f (X(k) .)]= [S(j) ]TH (X(k+1)－X(k) )13=0
即
[ S(j) ]T H ( X(k+1) － X(k) ) = 0
若取
S(k) = X(k+1) － X(k)
那么， S(k) 和 S(j) 关于H 共轭，即
[ S(j) ]T H S(k) = 0
再依次轮换进行一维搜索的坐标轴，直至完
成沿n个沿坐标轴方向的n次一维搜索。
.
3
x2
X2(1)
X0(1)
X1(1)
x1
取初始点X(0)=X0(1)， x1坐标轴方向的单位向 量S1(1)=e1=[1 0]T， x2坐标轴方向的单位向量 S2(1)= e2=[0 1]T。
X1(1) =X0(1)+α1(1)S1(1)， X2(1) =X1(1)+α2(1)S2(1)
法可以分为两类：
一类是只利用目标函数值信息的无约束优化
方法，如坐标轮换法、鲍威尔法，称为直接搜
索法；另一类是利用目标函数的一阶或二阶导
数信息的无约束优化方法，如梯度法、牛顿法、
共轭梯度法、变尺度法，称为间接搜索法。
.
2
§4.1 坐标轮换法（变量轮换法、交替法、降维法）
• 基本思想
将n维无约束优化问题转化为n个沿坐标
若满足，则输出最优解，否则，继续下一
轮迭代搜索。
.
5
Xi(k) =Xi-1(k)+αi(k)ei(k) ( k—迭代轮次，i— k轮迭代的第i次一维搜索
αi(k) — 一维搜索求得的最优步长） || Xn(k) – X0(k) ||≤ ？
• 计算步骤与算法框图
1）任选初始点X(0)=X0(1) = [x1(0) x2(0) … xn(0) ]T ，给定迭代收敛精度，i = 1，k = 1。
X*
X0(1)
. X1(1)
8
X0(1)
X* X1(1)
.
9
x2
X* X2(1)
X0(1)
X1(1)
x1
等值线出现脊线的情况（4M14图）
.
10
§4.2 鲍威尔（Powell）法
• 基本思想
它是直接利用函数值来构造共轭搜索方
向的一种共轭搜索方向法，又称鲍威尔共轭
方向法或方向加速法。由于对于n维正定二次
函数，共轭搜索方向具有n次收敛的特性，所
以鲍威尔法是直接搜索法中十分有效的一种
算法，一般认为对于维数n ≤20的目标函数它
是成功的。鲍威尔法是在研究具有正定对称
矩阵H的二次函数的极小化问题时形成的，其
基本思想是在不用函数导数信息的前提下，
在迭代过程中逐次构造关于H的共轭方向。
.
11
• 共轭方向的生成
.
4
第一轮迭代搜索：
X1(1) =X0(1)+α1(1)e1(1) = [x1(0) x2(0)]T + α1(1)[1 0]T
X2(1) =X1(1)+α2(1)e2(1) = [x1(1) x2(1)]T + α2(1)[0 1]T
判断是否满足迭代收敛准则：
|| X2(1) – X0(1) ||≤ ？
2）置n个坐标轴方向向量为单位向量，即
e1=[1 0 … 0 ]T， e2=[0 1 0 … 0 ]T ，… ，
en=[0 … 0 1]T。
.
6
3）按如下迭代计算公式进行迭代计算
Xi(k) =Xi-1(k)+αi(k)ei(k) ( k—迭代轮次，i— k轮迭代的第i次一维搜索 i =1，2， … ，n）