第一章 Matlab概述 概述★搜索区间及其确定方法 ★对分法 ★Newton切线法 切线法 ★黄金分割法 ★抛物线插值法

第 四 章 一 维 搜 索由第一章关于求解优化问题的迭代法知道， 由第一章关于求解优化问题的迭代法知道，从已 知迭代点出发按照基本迭代公式 X k +1 = X k + t k Pk 来求解 最优化问题， 最优化问题，其关键在于如何构造一个搜索方向和确 定一个步长，使下一迭代点处的目标函数值下降， 定一个步长，使下一迭代点处的目标函数值下降， 即.现在我们来讨论，当搜索方向已经确定的情况下， 现在我们来讨论，当搜索方向已经确定的情况下， 如何来确定步长？步长因子的选取有多种方法， 如何来确定步长？步长因子的选取有多种方法，如取 步长为常数，但这样选取的步长并不最好， 步长为常数，但这样选取的步长并不最好，如何选取 最好步长呢？ 最好步长呢？实际计算通常采用一维搜索来确定最优 步长. 步长.

对无约束最优化问题min f ( X ) nX ∈R

第 四 章 一 维 搜 索

当已知迭代点 X k 和下降方向 Pk 时，要确定适当的步长 t k 使 f ( X k +1 ) = f ( X k + t k Pk ) 比 f ( X k ) 所下降，即相当于对于 所下降， 参变量 t 的函数 (t ) = f ( X k + tPk )

要在区间 [0, + ∞] 上选取 t = t k 使 f ( X k +1 ) <

f (X k )

,即

(t k ) = f ( X k + t k Pk ) < f ( X k ) = (0)

上面的分析， 上面的分析，实质上是单变量函数 (t ) 关于变量 t 的 一维搜索选取问题，故通常叫做一维搜索 一维搜索. 一维搜索选取问题，故通常叫做一维搜索.按这种方 最优步长， 又称为最优步长 这种方法的优点是， 法确定的步长 t k 又称为最优步长，这种方法的优点是， 它使目标函数值在搜索方向上下降得最多. 它使目标函数值在搜索方向上下降得最多.

为了简便起见， 为了简便起见，我们用记号X k +1 = ls ( X k,Pk ) (4.1) ) 表示从点 X k 出发沿 Pk 方向对目标函数 f (X ) 作直线搜索所 得到的极小点是 X k +1 .

第 四 章 一 维 搜 索

确定的条件下( )等价于如下两式： 在目标函数 f (X ) 确定的条件下(4.1)等价于如下两式： f ( X k + t k Pk ) = min f ( X k + tPk ) = min (t ) t t X k +1 = X k + t k Pk

若从 X k 出发，沿方向进行一维搜索得极小点 X k +1 = X k + t k Pk 出发， ,则该点处的梯度方向 f ( X k +1 )与搜索方向 Pk 之间应满足 f ( X k +1 ) T Pk = 0

(4.2)

原因：作直线搜索，搜 原因：作直线搜索， 索方向和梯度方向刚好 正交。 正交。

4.1 搜索区间及其确定方法 设一维最优化问题为

第 四 章 一 维 搜 索

0≤t ≤t max

min (t )

(4.3) )

下面引入如下的搜索区间概念.

下面引入如下的搜索区间概念 1 1 * * t + t 定义4.1 设 :R → R , ∈ [0, ∞)(t ∈ [0,max ]) ,并且 定义 (t * ) = min (t )0 ≤ t ≤ t max

b + b b 若存在闭区间 [a, ] [0, ∞)([a, ] [0,t max ]) 使 t * ∈ [a, ] ,则 b 是问题( 称 [ a, ]是问题(4.3)的搜索区间. ) 搜索区间.

简言之，一个一维最优化问题的搜索区间， 简言之，一个一维最优化问题的搜索区间，就是包含该 问题最优解的一个闭区间.通常，在进行一维搜索时， 问题最优解的一个闭区间.通常，在进行一维搜索时， 一般要先确定出问题的一个搜索区间， 一般要先确定出问题的一个搜索区间，然后在此区间中 进行搜索求解. 进行搜索求解.

下面介绍确定问题搜索区间的法—加步探索法 下面介绍确定问题搜索区间的法 加步探索法

第 四 章 一 维 搜 索

先选定一个初始点和初始步长.然后， 先选定一个初始点和初始步长.然后，沿着轴的正方 向探索前进一个步长，得到新点. 向探索前进一个步长，得到新点.若目标函数在新点 处的值是下降了， 处的值是下降了，即 (t0 + h0 ) < (t0 )

则下一步就从新点 t 0 + h0 出发加大步长，再向前探 出发加大步长， 函数值上升， 索.若目标函数在新点处的 函数值上升，即 (t 0 + h0 ) > (t 0 )

则下一步仍以 t 0 为出发点以原步长开始向轴的负方向 同样探索.当达到目标函数上升的点时，就停止探索， 同样探索.当达到目标函数上升的点时，就停止探索， 这时便得到一个搜索区间. 这时便得到一个搜索区间.

加步探索法算法的计算步骤： 加步探索法算法的计算步骤：

第 四 章 一 维 搜 索

+ (1) 选取初始数据.选取初始点 t 0 ∈ [0, ∞)(或t 0 ∈ [0,t max ]) , 选取初始数据. 计算 0 = (t0 ) .给出初始步长 h0 > 0 ,加步系数 α > 1 , 令k = 0 .

…… 此处隐藏2679字 ……

(t1, (t1 )),t 0, (t 0 )),t 2, (t 2 )) ( ( 作它的二次拟合曲线 P (t ) = a 0 + a1t + a 2 t 2

上的点， 由于上述三个点既是目标函数曲线 (t ) 上的点，又是 上的点， 二次拟合曲线 P(t ) 上的点，故有方程组

第 四 章 一 维 搜 索

P (t1 ) = a 0 + a1t1 + a 2 t12 = (t1 ), (4.5) ) 2 P (t 0 ) = a 0 + a1t 0 + a 2 t 0 = (t 0 ), 2 P (t 2 ) = a 0 + a1t 2 + a 2 t 2 = (t 2 ).

将方程组( ) 消去， 将方程组(4.5)中的 a 0 消去，得2 a1 (t1 t0 ) + a2 (t12 t0 ) = (t1 ) (t0 ), (4.6) ) 2 2 a1 (t0 t2 ) + a2 (t0 t2 ) = (t0 ) (t2 ).

从方程组( ) 从方程组(4.6)可解出待定系数 2 2 2 2 (t 0 t 2 ) (t1 ) + (t 2 t12 ) (t 0 ) + (t12 t 0 ) (t 2 ) (4.7) ) a1 =(t1 t 0 )(t 0 t 2 )(t 2 t1 )(t 0 t 2 ) (t1 ) + (t 2 t1 ) (t 0 ) + (t1 t 0 ) (t 2 ) a2 = (t1 t 0 )(t 0 t 2 )(t 2 t1 )

(4.8) )