1） 第一轮基本方向组取单位坐标矢量系e1、 e2、 e3 、… 、 en，沿这些方向依次作一维搜索，然后将始末两点相 连作为新生方向。
2）再沿新生方向作一维搜 索，完成第一轮的迭代。 以后每轮的基本方向组是 将上轮的第一个方向淘汰 ，上轮的新生方向补入本 轮的最后而构成： d2k , d3k , …… dnk , dk
0
以
x
1 1
为新起点，沿e2方向一维搜索
x1 2x1 12e25 021 0 52
以最优步长原则确定α2，即为极小化
m in F (x 1 1 )2 2 1 02 6 0 2 4.5
x
1 2
5
4
.
5
对于第一轮按终止条件检验
x1 2x0 1 524.526.7
计算5轮后，有 x25x05 0.0413
§4.5 坐标轮换法
计算步骤:
⑴任选初始点,确定搜索方向
x 第一轮的起点
1 0
，置n个坐标轴方向矢量为单位坐标矢量
1
0
e1
0
0
0
1
e2
0
0
0
0
en
0
1
§4.5 坐标轮换法
⑵迭代计算
xik xik1 ikei
k为迭代轮数的序号，取k=1，2，……； i为该轮中一维搜索的序号，取i=1，2，……n 步长α一般通过一维优化方法求出其最优步长。
结论：从不同的点出 发沿某一方向分别对 函数作两次一维搜索 ，得到两个极小点， 那么这两个极小点的 连线方向与该方向对 G共轭
二、鲍威尔基本算法
鲍 威 尔 基 本 算 法 的 搜 索 过 程 （ 二 维 ）
二、鲍威尔基本算法
维鲍 ）威
尔 基 本 算 法 的 搜 索 过 程 （ 三
鲍威尔基本算法的步骤：
故近似优化解为x* x257.9883 5.9981
f*f(x*)7.95025
§4.5 坐标轮换法
3. 方法评价：
• 方法简单，容易实现。 • 当维数增加时，效率明显下降。
收敛慢，以振荡方式逼近最优点。
• 受目标函数的性态影响很大。
如图 a) 所示，二次就收敛到极值点； 如图 b) 所示，多次迭代后逼近极值点； 如图 c) 所示，目标函数等值线出现山脊（或称陡 谷），若搜索到 A 点，再沿两个坐标轴以±t0步长测 试，目标函数值均上升，计算机判断 A 点为最优点。 事实上发生错误。
§4.6 鲍威尔方法
鲍威尔方法是直接搜索法中一个十分 有效的算法。该算法是沿着逐步产生的共 轭方向进行搜索的，因此本质上是一种共 轭方向法。
§4.6 鲍威尔方法
一、共轭方向的生成
x k , x k 1 为两个极小点
根据梯度与等值面之间关系可知
d j
T
gk
0
dj
T
gk1 0
dj
T
(gk1gk)0
§4.6 鲍威尔方法
一、共轭方向的生成
对于二次函数，x k , x k 1 两点处
的梯度可表示为
gk Gxk b gk1 Gxk1b
gk1gkG (xk1xk)
代入到公式：
dj
T
(gk1gk)0
§4.6 鲍威尔方法
一、共轭方向的生成
d jT (g k 1 g k ) d jT G (x k 1 x k ) 0
若在第k轮的优化搜索过程中出现1k=0，则方向dk表
示为d2k、 d3k 、 • • • 、 dnk的线性组合，以后的各次搜索 将在降维的空间进行，无法得到n维空间的函数极小值， 计算将失败。
如图所示为一个 三维优化问题的 示例，设第一轮
中1 =0 ，则新
生方向与e2 、e3 共面，随后的各 环方向组中，各 矢量必在该平面 内，使搜索局限 于二维空间，不 能得到最优解。
鲍威尔基本算法的缺陷：
可能在某一轮迭代中出现基本方向组为线性相关的矢 量系的情况。如第k轮中，产生新的方向：
dk=xnk-x0k=1kd1k+ 2kd2k + • • • + nkdnk
式中， d1k、d2k 、 • • • 、 dnk为第k轮基本方向组矢
量， 1k 、 2k、 • • • 、 nk为各方向的最优步长。
流
x xik f←f(x)
程
图
i←i+1
N i=n?
k←k+1
x* xnk Y
Y
xnk x0k ?
N
x0k 1 xnk
结束
例:用坐标轮换法求下列目标函数的无约束最优解。
F (x ) x 1 2 x 2 2 x 1 x 2 1x 1 0 4 x 2 60
给定初始点
x0
0
0
，精度要求ε=0.1
第四章 无约束优化方法
4.1 最速下降法 4.2 牛顿型方法 4.3 共轭梯度法 4.4 变尺度法 4.5 坐标轮换法 4.6 鲍威尔方法 4.7 单形替换法
§4.5 坐标轮换法
一. 坐标轮换法： 1. 基本思想：
每次搜索只允许一个变量 变化，其余变量保持不变， 即沿坐标方向轮流进行搜 索的寻优方法。它把多变 量的优化问题轮流地转化 成单变量（其余变量视为 常量）的优化问题，因此 又称这种方法为变量轮换 法。此种方法只需目标函 数的数值信息而不需要目 标函数的导数。
解：做第一轮迭代计算
沿e1方向进行一维搜索 x11 x01 1e1
式中，x
1 0
为第一轮的起始点，取
x
1 0
x0
x11 0011001
按最优步长原则确定最优步长α1，即极小化
m inF (x 1 1 )1 2 1 01 6 0
此问题可由某种一维优化方法求出α1:
21100
1 5
x
1 1
5
⑶判断是否中止迭代
应该是一轮迭代 的始点和终点， 不是某搜索方向 的前后迭代点。
xnk x0k ?
如满足，迭代中止， 并输出最优解
否则，令k←k+1 返回步骤（2）
最优解 x* x k F*F(x*)
开始
给定 x00 ,ε
坐
K←1
标
i←1
轮
换
法
沿ei方向一维搜索αi
的
xik xik1ikei
计算x0k 、 x1k、 • • • 、 xnk、xk、xn+1k 各点的函数值， 记作：
x3
x1 1=0
2e2
S1
e3
S1
e2
x2 3e3
鲍威尔基本算法的退化
三、鲍威尔修正算法
在某轮已经取得的n+1个方向中，选取n个线性无关的 并且共轭程度尽可能高的方向作为下一轮的基本方向组
鲍威尔修正算法的搜索方向的构造：在第k轮的搜索中
， x0k 为初始点，搜索方向为d1k、d2k 、 • • • 、 dnk，产生 的新方向为dk ，此方向的极小点为xk。沿dk方向移动得到点 xn+1k=2xnk-x0k ， 称之为x0k对xnk的映射点。