当前位置:
文档之家› 4 无约束最优化方法-直接搜索法
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 ,