第五次模式搜索法

最优化方法

无约束最优化问题的直接方法1. 模式搜索法 2. Powell 算法 3. 单纯形替换法

最优化方法

无约束最优化问题的直接方法无约束最优化问题 min f ( x );

直接方法： 不用计算导数，只需计 算函数值的方法。 算函数值的方法。 直接方法： 不用计算导数，

最优化方法

方法， 1961 一. 模式搜索法 (Hooke Jeeves 方法， 年)

1. 基本思想： 算法从初始基点开始， 交替实施两种搜索：轴 向 基本思想： 算法从初始基点开始， 交替实施两种搜索：搜索和模式搜索。 个坐标轴的方向进行， 搜索和模式搜索。轴向 搜索依次沿 n 个坐标轴的方向进行，

用来确定新的基点和有 利于函数值下降的方向 。模式搜索则线方向进行， 数值下降更快。 沿着相邻两个基点的连 线方向进行，试图使函 数值下降更快。 2. 算法分析 问题 min f ( x);

个坐标轴方向。 令 e j = ( 0 ,L , 0 , 1 , 0 ,L , 0 )T , j = 1 , 2 ,L , n 表示 n 个坐标轴方向。作为第一个基点。 给定初始步长 δ ,加速因子 α 。任取初始点 x 1作为第一个基点。 个基点。 以下用 x j 表示第 j 个基点。

最优化方法

在每一轮轴向搜索中， 在每一轮轴向搜索中， 用 y i 表示沿第 i 个坐标轴 e i 方向搜索时

的出发点。 的出发点。 轴向搜索： 轴向搜索：令 y1 = x1 。

e2

x (1 ) = y (1 )

y ( 2) y ( 3)

方向搜索： 沿 e1方向搜索：如果 f ( y 1 + δ e1 ) < f ( y 1 ),则令

y 2 = y 1 + δ e1 ;否则， 否则，如果 f ( y 1 δ e1 ) < f ( y 1 ), 则令 y 2 = y 1 δ e1 ;否则， 令 否则， y 2 = y 1 。

O

e1

出发， 再从 y 2 出发，仿上沿 e 2 进行搜索得到 y 3 ,

最优化方法

一轮轴向搜索结束。 依次进行搜索， 依次进行搜索，直到得 到点 y n + 1 。 ( 一轮轴向搜索结束。 )如果 f ( y n + 1 ) ≥ f ( x 1 ) , 则缩小步长 δ ,仍以 x 1为起点进行新的

轴向搜索。 否则，进行模式搜索。 轴向搜索。 否则，进行模式搜索。 e 2

模式搜索： 模式搜索：如果 f ( y n + 1 ) < f ( x 1 ) , 则令 x 2 = y n + 1 。x 2 x 1方向可能有利于函数

x (1 ) = y (1 )

y ( 2) y ( 3) = x ( 2)

y ( 1) Oe1

值下降， 值下降，因此下一步沿 x 2 x 1

方向进行模式搜索。 方向进行模式搜索。即令 y 1 = x 2 + α ( x 2 x 1 )。

最优化方法

有效？ 如何判断模式搜索是否 有效？搜索， 以 y 1 为起点进行下一轮轴向 搜索，所得的点仍记为 y n + 1 。 如果 f ( y n + 1 ) < f ( x 2 ) , 表明此次模式搜索成功 ，令 e2 x 3 = y n + 1 。 仿上继续进行迭代。 仿上继续进行迭代。 x ( 1) = y (1 ) y ( 2) 如果 f ( y n + 1 ) ≥ f ( x 2 ) , 表明此次 模式搜索失败， 模式搜索失败，返回基 点 x 2 ,

y ( 3) = x ( 2)y ( 2) = y ( 3)e1

进行下一轮轴向搜索。 进行下一轮轴向搜索。

y (1 ) O

最优化方法

x3 x x12

x x4

5

x6 x

最优化方法

模式搜索法： 模式

搜索法：(1) 给定初始点 x 1 ∈ R n , 初始步长 δ ,加速因子 α ≥ 1,缩减率

β ∈ ( 0 , 1 ) , 精度 ε > 0。 令 y 1 = x 1 , k = 1 , j = 1。( 2) 轴向搜索： 轴向搜索：如果 f ( y j + δ e j ) < f ( y j ) , 则令 y j +1 = y j + δ e j , 转 3); ( 如果 f ( y j δ e j ) < f ( y j ) , 则令 y j + 1 = y j δ e j , 转 3); ( 否则， 否则，令 y j +1 = y j 。

( 3) 若 j < n , 则令 j : = j + 1 , 转( 2)。否则， 如果 f ( y n +1 ) < f ( x k ) , 转(4); ,转(5)。 否则 (4) 模式搜索： x k + 1 = y n + 1 , y 1 = x k + 1 + α ( x k + 1 x k )。 模式搜索： 令

令 k : = k + 1 , j = 1 , 转(2)。 否则， 否则，令 δ : = βδ , (5) 如果 δ ≤ ε , 停止，得到点 x ( k ) ; 停止，

y 1 = x k , x k +1 = x k 。令 k : = k + 1 , j = 1 , 转(2)。

最优化方法

注 将轴向搜索和模式搜索 中的固定步长改为用一 维搜索确定步长， 维搜索确定步长，算法仍然收敛。 算法仍然收敛。 例 1 . 用模式搜索法求解问题

min率 β = 0.2。 轮迭代： 解 : 第 1 轮迭代：

2 2 f ( x ) = x1 + x 2 。

取初始点 x 1 = ( 1 , 1 )T , 初始步长 δ = 0.25, 加速因子 α = 1 ,

缩减

令 y 1 = x 1 = ( 1 , 1 )T , 则 f ( y 1 ) = 2。

Q f ( y 1 + δ e1 ) = 2.5625 > f ( y 1 ) , f ( y 1 δ e1 ) = 1.5625 < f ( y 1 ) , ∴ y 2 = y 1 δ e1 = ( 0.75 , 1 )T 。

最优化方法

Q f ( y 2 + δ e 2 ) = 2.125 > f ( y 2 ) , f ( y 2 δ e 2 ) = 1.125 < f ( y 2 ) , ∴ y 3 = y 2 δ e 2 = ( 0.75 , 0.75 )T 。Q f ( y 3 ) < f ( x1 ) ,

∴ 令 x 2 = y 3。 取加速方向 d 1 = x 2 x 1 = ( 0.25 , 0.25 )T 。

模式搜索： 模式搜索：y 1 = x 2 + α d 1 = ( 0.5 , 0.5 )T 。

最优化方法

二. Powell 方法基本思想： 基本思想： Powell 方法主要由 基本搜索、加速搜索和 调整搜索方向三个 基本搜索、 部分组成。 部分组成。基本搜索包 括从基点出发沿着已知 的 n 个搜索方向

进行一维搜索， 个新基点。 进行一维搜索，确定一 个新基点。 加速搜索是指沿着相邻 的两 一维搜索， 降更快。 个基点的连线方向进行 一维搜索，使函数值下 降更快。 最后用基点个搜索方向之一， 新的搜索方向组， 连线方向代替已知的 n 个搜索方向之一，构成 新的搜索方向组， 进行下一轮迭代。 进行下一轮迭代。

最优化方法

原始 Powell 法步骤：(1) 给定初始点 x 0 , n 个线性无关的方向： 个线性无关的方向：

d ( 1 , 1) , d ( 1 , 2 ) , L , d ( 1 , n ) 。

允许误差 ε > 0,令 k = 1。( 2 ) 令 x ( k , 0 ) = x k 1 , 从 x ( k , 0 ) 出发，依次沿方向 出发，

进行搜索， d ( k , 1) , d ( k , 2 ) ,L , d ( k , n ) 进行搜索， 即令 x ( k , j ) = x ( k , j 1 ) + t j d ( k , j ) t : f ( x ( k , j 1 ) + t d ( k , j ) ) = min f ( x ( k , j 1 ) + t d ( k , j ) ) j j t( k , 1) , x ( k , 2 ) ,L , x ( k , n ) 。 得到点 x

令 d ( k , n +1 ) = x ( k , n ) x ( k , 0 ) ,

从 x ( k , n ) 出发沿 d ( k , n +1 ) 进行一维搜索得到点 x k 。

( 3) 若 || x k x k 1 || < ε ,停止，得到点 x k ; 否则，令 停止， 否则， d ( k + 1 , j ) = d ( k , j + 1 ) , j = 1 , 2 ,L , n 。

返回( 令 k : = k + 1 , 返回(2)。

最优化方法

例 2. 用原始 Powell 方法求解下述问题： 方法求解下述问题：

min

f ( x ) = ( x1 + x2 ) 2 + ( x1 1) 2

初始点为 x 0 = ( 2 , 1 )T , 初始搜索方向为 d (1,1) = ( 1 , 0 )T , d (1, 2 ) = ( 0 , 1 )T 。

第一轮迭代： 解： 第一轮迭代： 作一维搜索， 令 x (1, 0 ) = x 0。 从 x ( 1, 0 )出发沿着方向 d ( 1,1 )作一维搜索，即求解mint

f ( x ( 1 , 0 ) + t d ( 1 ,1 ) ) …… 此处隐藏：3504字，全部文档内容请下载后查看。喜欢就下载吧 ……