《直线搜索》word版

《《直线搜索》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第十七章直线搜索本章讨论的主要问题是解决这个问题的方法承为直线搜索或一维搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。在微积分中解的方法限于方程可以直接求解出来的情况。本章介绍的方法对不作严格要求，它可以很复杂，其导数可能不存在或者很难求出。当然对于可以求导数的情况，相应的方法也会简单些。本章将讨论以下四种直线搜索方法：（1）对分法：适用于的一阶导数连续并可以求出的情况。（2）Newton切线法：适用于的一阶导数和二阶导数都可求出的情况。（3）黄金分割法：适用于一般的函数。（4）抛物线插值法：适用于一般的连续函数。17.1搜索区间的确定

2、定义17.1.1：设，t*是在L上的全局极小点。如果对于L上任取的两点t1和t2且t1

3、1)中。此时有t*≤t1，<4>3〉若，比较，转<5>，<6>。4〉若，计算,直到有某个m≥1使令μ=，v=,ω=就确定了搜索区间{μ，ν，ω}（实际应该为{ν，ω}放大）。但区间[ν，ω]是[μ，ν]的两倍长。（ω-ν=2（ν-μ））图17.1.2因此只

4、需比较ν和区间[ν，ω]的中点的对应函数值，即可将区间[μ，ω]缩短1/3。由图(a),(b)可见，当时，取{μ，ν，γ}为搜索区间（图（a））。当{ν，γ，ω}为搜索区间。（图(b))<5>当，取{t0-h,t0,t0+h}为搜索区间。<6>当，与〈4〉类似，计算，直到有某个m（≥1）使。令μ=，v=,ω=γ=(μ+ν)/2,比较：若,取{ω,γ,ν}为搜索区间(图(d))若,取{γ,ν,ω}为搜索区间。(图(e))378图17.1.3上述过程的关键是开始时怎样选择步长h，如选得太小,需迭代多次才能找到搜索区间，而若选得太大，虽然一次就能找到搜索区间，但给下一步找极小点过程增加

5、了负担。下面将介绍选择初始步长h的一种方法。设具有连续二阶偏导数，且。现在要从t0出发确定一个搜索区间。在t0附近将二次Taylor展开：令由此解得…..(3)这是的唯一极小点，可作为极小点t*的一个近似。因此想到用作为初始步长h。但中要计算二阶导数。一般来说计算二阶导数比较困难，而一阶导数即使较困难，也可用差分近似，因此，要想办法避免二阶导数的计算。假设的极小值可以估计出来，如为，即若对某个，使得，则将作为t*的一个近似。由（1）：则可取步长这样就避免了二阶导数的计算。在多维最优化问题时，若采用迭代计算法时，每次迭代要用直线搜索来确定下一个迭代点，每次迭代需要确定直线搜索的初始

6、步长，如下面考察由Zk到Zk+1迭代的情况。设已获得迭代点Zk，并按某种规则选定了向量Pk为下降方向，并设，则下一迭代点Zk+1由下述直线搜索确定的：378令，则则上述直线搜索（7）就是从t=0出发的直线搜索，因而可按（6）确定初始步长h，但此时公式（6）中应令t0=0,应该取f(z)极小值的估计值fe，即f(z*)≈fe，又从而公式中没有绝对值符号，这是因为：首先：下降方向Pk应选择满足其次：估计值fe一般比真实值f(z*)偏小，从而fe0.实际操作时可采用两种方案：一是下降迭代算法每次迭代均用（8）来确定初始步长，二是在第一次迭代算法时用（

7、8）而以后每次迭代初始步长均用来计算。这是因为一般是接近的。因而用前依次迭代所走的距离作为下一次迭代的初始步长是合适的，计算经验表明，后一种方案更有效些。17.2对分法这个方法的特点是计算量较少，而且总能收敛到一个局部极小点，但收敛速度较慢。我们知道，在极小点处，，且时，递减，即，而当，函数递增，即。若找到一个区间[a,b],满足性质。则[a,b]内必有的极小点，且为找此，取，若则在中有极小点，这时用作新的区间[a,b]，继续这个过程，逐步将区间[a,b]缩小，当区间[a,b]的