1、第四章 一维搜索法由第一章关于求解最优化问题概述中我们知道，从已知迭代点 nkRX出发按照基本迭代公式 kkPtX1来求解最优化问题，其关键在于如何构造一个搜索方向nkRP和确定一个步长 1R，使下一迭代点 1kX处的目标函数值下降，即)()(kff现在我们来讨论，当搜索方向 P已经确定的情况下，如何来确定步长kt？步长因子的选取有多种方法，如取步长为常数，但这样选取的步长并不最好，如何选取最好步长呢？实际计算通常采用一维搜索来确定最优步长对无约束最优化问题 )(minXfR，当已知迭代点 kX和下降方向 kP时，要确定适当的步长 kt使 )(1kf)(kPtf比 )(f有所下降，即相当于对于
2、参变量 的函数)()ktPft要在区间 ,0上选取 kt使 (1kXf，即 0() kkft由于这种从已知点 kX出发，沿某一下降的探索方向 来确定步长 kt的问题，实质上是单变量函数 ()t关于变量 t的一维搜索选取问题，故通常叫做一维搜索按这种方法确定的步长 kt又称为最优步长，这种方法的优点是，它使目标函数值在搜索方向上下降得最多今后为了简便起见，我们用记号 )(1kkPXls，（4.1）表示从点 kX出发沿 kP方向对目标函数 )f作直线搜索所得到的极小点是 1kX其中l和 s分别是 Linear search（直线搜索）两词的词首在目标函数 )(f已确定的条件下（4.1）等价于如下两
3、式： kk tktkPXtftf1 min)(in)( ，下面进一步解释迭代点 t的空间位置容易证明，若从 kX出发，沿kP方向进行一维搜索得极小点 kk，则该点 1kX处的梯度方向)(1Xf与搜索方向 kP之间应满足 0)(1Tf (4.2)事实上，设 )(tXft，对 t求导有kTkPtXft)()令 0)(t，即 0kf，所以 0)(1kTPXf式（4.2）的几何意义是明显的从某一点 出发沿 方向对目标函数 )(Xf作直线搜索，所得到的极小点为 1k式（4.2）指出，梯度 )(1kf必与搜索方向 kP正交又因为 )(1kXf与目标函数过点 X的等值面 )(f正交，所以进一步看到，搜索方向
4、 P与这个等值面在点 k处相切（如图 4.1 所示） 4.1 搜索区间及其确定方法一、搜索区间设一维最优化问题为 )(minax0tt （4.3）为了求解问题（4.3） ，我们引入如下的搜索区间概念定义 4.1 设 )(*1tR，： ，并且imax0tt，若存在闭区间 )(0baba， 使 *b， ，则称 a， 是问题（4.3）的搜索区间简言之，一个一维最优化问题的搜索区间，就是包含该问题最优解的一个闭区间通常，在进行一维搜索时，一般要先确定出问题的一个搜索区间，然后在此区间中进行搜索求解二、加步探索法下面，介绍一个确定问题(4.3)的搜索区间的简单方法这个方法的思想是：先选定一个初始点 )0
5、)(0maxttt ，或， 和初始步长 0h然后，沿着 t轴的正方向探索前进一个步长，得到新点 h若目标函数在新点处的值是下降了，即 )(00tt，则下一步就从新点 0t出发加大步长，再向前探索若目标函数在新点处的 函数值上升，即 )(00tht，则下一步仍以 0t为出发点以原步长开始向 轴的负方向同样探索当达到目标函数上升的点时，就停止探索，这时便得到问题（4.3）的一个搜索区间这种以加大步长进行探索来寻找探索区间的方法叫做加步探索法加步探索法算法的计算步骤：(1) 选取初始数据选取初始点 )0)(0maxttt ，或， ，计算 )(0t给出初始步长 0h，加步系数 1，令 k(2) 比较目
6、标函数值令 kkht1，计算 11kt，若 k1，转(3)否则转(4)(3)加大探索步长令 kk1，同时，令 kt， kt， 1k， ，转(2)（4） 反向探索若 0，转换探索方向，令 ,kkth，转（2） 否则，停止迭代，令图 4.111minaxkkatbt， ， ，输出 ba， 加步探索法算法的流程图如图 4.2 所示。在加步探索法中，一般建议 2若能估计问题（4.3）的最优解的大体位置的话，初始点 0t要尽量取接近于问题（ 4.3）的最优解在具体运用上述加步探索法时，有时还要考虑一些细节问题例如，当探索得到新点处的目标函数值和出发点处相同时，以及初始步长应如何选取等，都需作适当处理三、
7、单谷区间与单谷函数由于以后要介绍的一些维搜索方法，主要适用于问题（4.3）在搜索区间中只有唯一的最优解的情况，为此，我们再给出下面单谷区间与单谷函数概念定义 4.2 设 1R：，闭区间 1Rba， 若存在点 *bat，使得 )(t在*ta，上严格递减， ()t在 *， 上严格递增，则称 ， 是函数 )(的单谷区间，)(是 b， 上单谷函数开始选取初始点 t0，初始步长h00，加步系数 1， 令 k=0 0= (t0)，比较目标函数值tk+1=tk+hk, k+1= (tk+1) a=mint， tk+1b=maxt，t k+1结束NYNY k+1 khk+1=hk,t=tk ,tk=tk+1
8、, k= k+1,k=k+1k=0hk = hk ,k=k+1图 4.2由定义 4.2 易知，一个区间是某函数的单谷区间意味着，在该区间中函数只有一个“凹谷” （极小值） 例如，图 4.3 中的 ba， 是 )(t的单谷区间，也即 )(t是 ba， 上的单谷函数图 4.4 中的 ba， 不是 )(t的单谷区间，即 不是 ba， 上的单谷函数另外，从定义 4.2 还可知，某区间上的单谷函数在该区间上不一定是连续函数，而凸函数在所给区间上必然是单谷函数（如图 4.3 所示） 由定义 4.1 和定义 4.2 知，函数)(t的单谷区间总是相应问题（4.3）的一个搜索区间（如图 4.3 所示） ，但反之
9、不然（如图4.4 所示） 图 4.3 图 4.4单谷区间和单谷函数有如下有用的性质：定理 4.1 设 1baR，： 是 )(t的单谷区间，任取 21bat， 并且 12t（1）若有 )(2tt，则 ， 是 的单谷区间（2）若有 1，则 2t， 是 t的单谷区间证明略定理 4.1 说明，经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间换句话说，利用这个定理可以把搜索区间无限缩小，从而求出极小点以下介绍的几种，一维搜索方法都是利用这个定理通过不断地缩短搜索区间的长度，来求得一维最优化问题的近似最优解4.2 对分法一、对分法基本原理求解一维最优化问题 min()t一般可先确定它的一个有限搜索区
10、间 ba， ，把问题化为求解问题 )(intbta，然后通过不断缩短区间 ,ba的长度，最后求得最优解设 1R： 在已获得的搜索区间 ， 内具有连续的一阶导数因为 )(t在，上可微，故 )(t在 ba， 上连续，由此知 )(t在 ， 上有最小值令 0)(t，总可求得极小点 *t不妨设 在 *， 上是单减函数；在 *bt， 上是单增函数所以 *t，时， 0)(，故 0a；当 )(bt，时， 0)(，亦即b对分法的原理如图 4.5 所示二、对分法迭代步骤已知 )(t， t表达式，终止限 (1) 确定初始搜索区间 ,ba，要求()0ab，(2) 计算 ,的中点 )(21bac(3) 若 0)(，则
11、，转(4)；若 0)(c，则 图 4.5ct*，转 (5)；若 0)(c，则 cb，转(4)(4) 若 |ba，则 )(21*at，转(5)；否则转(2)(5) 打印 *t，结束对分法的计算流程如图 4.6 所示三、对分法有关说明对分法每次迭代都取区间的中点若这点的导数值小于零，说明 0)(t的根位于右半区间中（如图 4.5 所示） ，因此去掉左半区间；若中点导数值大于零，则去掉右半区间；若中点导数值正好等于零，则该点就是极小点因为每次迭代都使原区间缩短一半，所以称为对分法或二分法Y开始确定a，b ，要求 ()0,c=(a+b)/2b=ct*=(a+b)/2输出 t*结束t*=cNa=cN()
12、0c()YN()0c()Y ab图 4.64.3 Newton 切线法一、Newton 切线法基本原理设 1:R在已获得的搜索区间 ba， 内具有连续二阶导数，求)(mintbta因为 )(t在 ba， 上可微，故 )(t在 ， 上有最小值，令 0)(t下面不妨设在区间 ， 中经过 k次迭代已求得方程 的一个近似根 kt过,kt作曲线 ty的切线，其方程是 )()(kktty （4.4）然后用这条切线与横轴交点的横坐标 1kt作为根的新的近似（如图 4.7 所示） 它可由方程（4.4）在令 0y的解出来，即 )(1kktt这就是 Newton 切线法迭代公式二、Newton 切线法迭代步骤已知
13、 )(t， t表达式，终止限 (1) 确定初始搜索区间 ,ba，要求()0ab，(2) 选定 t(3) 计算 00()/“tt(4) 若 |，则 ，转（3） ；否则转（5） (5) 打印 ()t， ，结束Newton 切线法的计算流程如图 4.8 所示三、Newton 切线法有关说明这种方法如果初始点选得适当，收敛速度很快，通常经过几次迭代就可以得到满足一般精度要求的结果，但是它也有缺点第一，需要求二阶导数如果在多维最优化问题的一维搜索中使用这种方法，就要涉及 Hesse 矩阵，一般是难于求出的第二，当曲线 )(ty在 ,ba上有较复杂的弯曲时，这种方法也往往失效如图 4.9 所示的迭代： 2
14、10tt，结果2t跳出 ,ba迭代或者发散，或者找到的根并不是我们想要的结果第三，即使曲线比较正常，在 ,中或者上凹或者下凹，初始点的选取也必须适当在图 4.10（a）的情况下，曲线上凹，应选点 b 作为初始点；而在图4.10（b）的情况下，曲线下凹，应选点 a为初始点否则都可能失败图 4.700()/ttt输出 *,t开始结束0tYN0t*00,()tt选定 t0,确定a b,要求 ()ab图 4.9图 4.8图 4.10 4.4 黄金分割法一、黄金分割法基本原理要介绍黄金分割法有必要回顾一下古老的黄金分割问题所谓黄金分割就是将一线段分为二段时，要求整段长 L 与较长段 x 的比值正好等于较
15、长段 x 与较短段 xL的比值（如图 4.11 所示） ，即 L于是有 022Lx，解出其正根 x618.025由此可见长段的长度应为全长的 0.618 倍，而短段的长度应为全长的 0.382 倍因为古代的人们认为按 0.618 的比率来分割线段是最协调，胜似黄金，故称之为黄金分割图 4.11用黄金分割法进行一维搜索，其基本思想是在单谷区间 ba， 内适当插入两点 21t， ，由此把区间 ba， 分为三段，然后再通过比较这两点函数值大小，就可以确定是删去最左段还是最右段，或者同时删去左右两段保留中间段如此继续下去可将单谷区间无限缩小 二、黄金分割法迭代步骤现在提出一个问题，就在 ba， 上如何
16、选取二点 21t， 使得迭代次数最小而区间缩短最快？要解决这个问题，人们想到对区间 ba， 选二点 21t， 等价于将区间长度 ab进行黄金分割，也就是将第一个搜索点 1t取在 ， 的 0.618 处，第二个搜索点 2t取成 1t的对称点即ba，的 0.382 处（如图 4.12 所示） ，亦即 )(68.01at，322ba计算 )(1t与 2t的值，并根据 )(与 t的值的大小关系分情况讨论：（1） 若 )(21t，说明 1t是好点，于是把区间 2t， 划掉，保留 2bt， ，则2bt，内有一保留点 t，置新的区间 2t， ；（2）若 )(，说明 t是好点，于是应将 1b， 划掉，保留 1
17、ta， ，则1ta，内有保留点 2t，置新的区间 1tab， （3）若 1，则应具体分析，看极小点可能在哪一边再决定取舍在一般情况下，可同时划掉 ta， 和 1， ，仅保留中间的 12t， ，置新的区间 21tb， 接下来是在留下的区间 b， 内找好点重复上面的步骤，直到搜索区间 i， 小于给定的允许误差0为止这样就得到黄金分割法迭代算法：已知 )(t，常数 0.382，终止限 (1)确定 的初始搜索区间 ba， (2)计算 )()(22tbat， (3)计算 121t， (4) 若 |t，则打印1*tt，结束；否则转(5)(5) 判别是否满足 21：若满足，则置 1212， tta， 然后转
18、(3)；否则，置 )()(2121 tabttb，然后转(4)黄金分割法算法流程如图 4.13 所示三、黄金分割法有关说明黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点 *t该方法适用于单谷区间 ,ba上的任何函数，甚至可以是不连续函数，因此这种算法属于直接法，适用相当广泛图 4.124.5 抛物线插值法一、抛物线插值法基本原理考虑一维搜索问题 )(min21tt，假设其中 )(t是定义在区间 21t， 上的单谷函数首先用试探法在 21t， 上找一点 0t，使之满足 )()(020tt，通过目标函数曲线上的三个点 ( 21t ， ，作它的二次拟合曲线（如图 4.14 所示） 210)tatP*,t开始确定a,b(51)/22tba2()12tabt1()212bt *12()/tt*()t结束NYNY12t1212,att2()()tbat12图 4.13
