4 无约束最优化方法-直接搜索法

2）置n个坐标轴方向向量为单位向量，即e1=[1 0 … 0 ]T， e2=[0 1 0 … 0 ]T ，… ， en=[0 … 0 1]T。
3）按如下迭代计算公式进行迭代计算 Xi(k) =Xi-1(k)+αi(k)ei(k) ( k—迭代轮次，i— k轮迭代的第i次一维搜索
i =1，2， … ，n） 4）判断是否满足迭代收敛准则
fL = f (XL) =min{ fi : i = 0, 1, 2, … , n }
fH = f (XH) =max{ fi : i = 0, 1, 2, … , n }
fG = f (XG) =max{ fi : i = 0, 1, 2, … , n; i ≠H }
4）检验是否满足迭代收敛条件 |( fH – fL) / fL | ≤ ?
7）收缩：当 fn+2≥ f
G
时，则需收缩。 （ =0.5）
若 fn+2 < fH，则取收缩点Xn+4 ： Xn+4 = Xn+1 + (Xn+2 – Xn+1)
fn+4 = f (Xn+4 )
否则，以XH代替上式中的Xn+2 ， 计算收敛点Xn+4 ： Xn+4 = Xn+1 + (XH – Xn+1) fn+4 = f (Xn+4 )
形成新的单纯形，然后返回到 2）。
鲍威尔（Powell）法
• 基本思想
它是直接利用函数值来构造共轭搜索方向的一种共轭 搜索方向法，又称鲍威尔共轭方向法或方向加速法。由于对 于n维正定二次函数，共轭搜索方向具有n次收敛的特性，所 以鲍威尔法是直接搜索法中十分有效的一种算法，一般认为 对于维数n ≤20的目标函数它是成功的。鲍威尔法是在研究 具有正定对称矩阵 H的二次函数的极小化问题时形成的，其 基本思想是在不用函数导数信息的前提下，在迭代过程中逐 次构造关于H的共轭方向。
S(k) = Xn(k) -X0(k)
鲍威尔条件： 若 f
3
<f
1
,
且
( f1 - 2f2 + f3) (f1 - f2 - △m(k))2 < 0.5 △m(k) (f1 - f3 )2 同时成立，则用S(k) 替代Sm(k) ；否则，仍用原搜索方向组。这 就是鲍威尔修正算法，通常所说的鲍威尔算法就是指这一修正算 法。
无约束优化的直接搜索法 X (k+1)=X (k) + (k) S(k)
(k =0 , 1 , 2 , …)
各种无约束优化方法的区别就在于确定其搜索方向 S(k) 的方法不同，所以搜索方向的构成问题是无约束优化方法的关 键。根据构造搜索方向所使用的信息性质的不同，无约束优化 方法可以分为两类： 一类是只利用目标函数值信息的无约束优化方法，如坐标 轮换法、鲍威尔法，称为直接搜索法；另一类是利用目标函数的 一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共 轭梯度法、变尺度法，称为间接搜索法。
2）取始点X0(2) = Xn+1(1)，并去掉原搜索方向组中 的第一个方向S1(1)=e1，而将第一轮构成的新搜索方向 S(1) 作为最末一个方向，以此组成第二轮迭代的n个方向。
依此进行下去，直到获得满足迭代收敛精度要求的近似极小 点为止。 根据这一原理构造的迭代算法称为鲍威尔基本算法。
x2 S2(1) X3 X2 X0
坐标轮换法（变量轮换法、交替法、降维法）
• 基本思想
将 n 维 无 约 束 优 化 问 题 转 化 为 n 个 沿 坐 标 轴 方 向 ei (i=1, 2, … , n)的一维优化问题来求解，并记完成n次一 维搜索为一轮。若一轮搜索后未得到满足精度要求的最优点， 则继续下一轮迭代搜索。如此反复，直至得到满足精度要求 的最优点为止。在每一轮搜索中，每次迭代仅对 n元函数的 一个变量沿其坐标轴方向进行一维搜索，其余 n-1个变量均 保持不变，再依次轮换进行一维搜索的坐标轴，直至完成沿 n个坐标轴方向的n次一维搜索。
|| Xn(k) – X0(k) ||≤ ？ 若满足，则输出最优解: X * = Xn(k) ，f
*
= f (X * )
否则，令X0(k+1) = Xn(k) ，k k思想
通过计算出若干点处的函数值，对其大小进行比较，可 以看出函数值变化的大致趋势，从而可以寻求使函数值下降的 搜索方向。在n维空间中，由n+1个不同点顺序相连，就可以 构成一个具有n+1个顶点的多面体——称之为单纯形。计算函 数在这n+1个顶点的函数值，并进行比较，据此来确定有利的 搜索方向和步长，找到一个比较好的点来取代单纯形中较差的 那个顶点，从而组成了一个新的单纯形，并用之取代原来的单 纯形。如此下去，新单纯形不断地向目标函数的极小点靠近， 直到搜索到极小点为止。
那么，为什么会产生这种情况呢？又该如何去改进呢？
•
鲍威尔条件及鲍威尔修正算法
鲍威尔基本算法中，每一轮迭代都是用连接始点和终 点所产生的新搜索方向去机械地替换原方向组中的第一个搜 索方向，而不做任何的“好坏”判断，这正是产生向量线性 相关而发生“退化”的根本原因所在。为了避免这种“退化” 现象的发生，鲍威尔对这一基本算法进行了修正。即在每一 轮产生新的搜索方向 S(k) 后，首先判断原搜索方向组是否可 以直接用作下一轮迭代的搜索方向组，若可以，则仍用之， 否则，还要进一步判断原搜索方向组中哪个方向上函数值下 降量最大或贡献最大，然后再用新搜索方向替换这个贡献最 大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的 搜索方向组线性无关。
x2
XL X 2 Xn+1 X0 XH
Xn+2
Xn+3
X1
XG
x1
6）扩张：当 fn+2< f
L
时，取扩张点Xn+3，即 (=1.2～2.0 )
Xn+3 = Xn+1 + (Xn+2 – Xn+1)
并计算 fn+3 = f (Xn+3 ) 。 若 fn+3 < fn+2，则以Xn+3 代替 XH ， fn+3代替fH ，构造一个新的单纯形；否则，以Xn+2 代 替XH ， fn+2 代替fH，构造新的单纯形；然后返回到 3）。
x2 Xn+4
XL X 2
Xn+2 Xn+1
Xn+3
Xn+4 XG
X0
XH
X1
x1
若 fn+4 < fH，则以Xn+4 代替XH ， fn+4代替fH ，形 成新的单纯形，然后返回到 3）；否则转下一步8）。
8）缩边：将单纯形向XL缩边，可以将各向量
( Xi – XL ) 的长度都缩小一半，即 Xi = XL + 0.5 (Xi – XL) = 0.5 (Xi + XL) ( i = 0, 1, 2, …, n ) ( i = 0, 1, 2, …, n )
对第 k 轮迭代，记 f 1 = f (X0(k) ) X0(k) ) f
2
= f (Xn(k) )
f
3
= f (2Xn(k) -
及 △m(k) = max { f (Xi-1(k) ) - f (Xi (k) ) , i=1,2,…, n }， 并记 S
m ( k )
为与△
m
( k )
相对应的搜索方向，
• 共轭方向的生成 设是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
• 计算步骤 1）构造初始单纯形 选初始点X0 ，和步长h。从X0出发沿各坐标轴方向分别 走步长h，得到n个顶点Xi (i=1, 2, … , n)，与X0构成初始 单纯形。 x2 X2
X0
X1
x1
2）计算各顶点的函数值 fi = f (Xi) (i=0, 1, 2, … , n)
3）比较函数值大小，确定最好点XL 、最差点 XH 和次差点 XG ，即:
具有正定对称矩阵H的二次函数
f (X) = 0.5 XT H X + BT X + C 在 X(k) 和 X(k+1)两点处的梯度可以表示为 ▽f (X(k) ) = H X(k) + B ▽f (X(k+1) ) = H X(k+1） + B （2）－ （1）得 ▽f (X(k+1) ) － ▽f (X(k) ) = H ( X(k+1) － X(k) )（3） （3）式两边同时左乘[S(j) ]T得 [S(j) ]T[▽f (X(k+1) )－▽f (X(k) )]= [S(j) ]TH (X(k+1)－ X(k) )=0 （1） （2）
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)
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) 给定迭代收敛精度，i = 1，k = 1。 x2(0) … xn(0) ]T ，