常用一维搜索算法.docx

无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。
这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。
实际上也没有必要做到这一点,因为精确的一维搜索需要付出较高的代价,而对加速收敛作用不大,因此花费计算量较少的不精确一维搜索方法受到了广泛的重视和欢迎。
精确一维搜索,作为一种理想的状态,虽然在实际计算中被采用的概率较之不精确一维搜索要小,但有关精确一维搜索技术的研究历史悠久成果相当丰富,方法众多,其理论体系也相对比较完备,对其进行进一步的研究仍有着重要的理论意义和现实意义。通常我们根据算法中有无使用导数的情况,将精确一维搜索算法分为两大类:一类是不用函数导数的方法,这其中就包括二分法（又称作对分法或中点法）、（黄金分割脚、Fibonacci法（分数法）、割线法、成功一失败法等;另一类是使用函数导数的方法，包括经典的Newton法、抛物线法以及各种插值类方法等。
（1）在不用导数的方法中，二分法、（黄金分割法）以及Fibonacci法均是分割方法，其基本思想就是通过取试探点和进行函数值比较,使包含极小点的搜索区间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均接近函数的极小值,从而各点均可看作极小点的近似。分割类方法仅需计算函数值,因此使用的范围较广,尤其适用于非光滑及导数表达式复杂或写不出等情形。
二分法是一种最简单的分割方法,每次迭代都将搜索区间缩短一半,故二分法的收敛速度是线性的,,收敛速度较慢。其优势就是每一步迭代的计算量都相对较小,程序简单,而且总能收敛到一个局部极小点。
黄金分割法是一种针对目标函数是单峰函数亦即目标函数为凸的情形的分割类方法,因其不要求函数可微,且每次迭代只需计算一个函数值,程序简单容易实现而被广泛采用。由于黄金分割法是以等比例T=,因此它是一种近似最优方法。针对在实际中遇到的目标函数往往不是单峰函数的情况,HPonfiger（1976），即在缩小区间时，不只是比较两个内点处的函数值,而是对两内点及其两端点处的函数值进行综合比较,以避免搜索得到的函数值反而比初始区间端点处的函数值大的情况。经过这样的修改,
,两者的主要区别在于Fibonacci法搜索区间的缩短比率不是采用黄金分割数T，而是采用Fibonacci数列。在使用Fibonacci法时,通常是由用户给定最终区间长度的上限，从而确定探索点的个数，逐步进行搜索。通过对Fibonacci数列进行分析表明,在迭代次数n趋于无穷的情形。,因而Fibonacci法的收敛速度也是线性的，收敛比也是黄金分割数T。可以证明,Fibonacci法是分割方法求解一维极小化问题的最优策略,,,程序实现更加容易,因而应用也更加广泛。
抛物线法也可称作三点二次插值法,其基本思想与下面要叙述的牛顿法相同,也是用二次函数近似目标函数，并以其极小点去