《最优化方法资料》由会员分享，可在线阅读，更多相关《最优化方法资料（12页珍藏版）》请在金锄头文库上搜索。
1、最优化方法结课作业年级 数学121班学号201200144209姓名李强1、几种方法比较无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。这是因 为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即 为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。(直 接法：又称数值方法，它只需计算目标函数驻点的函数数值，而不是求其倒数，如坐标轮换 法，单纯型法等。间接法：又称解析法，是应用数学极值理论的解析方法。首先计算出目标 函数的一阶或一阶、二阶导数，然后根据梯度及海赛矩阵提供的信息，构造何种算法，从而 间接地求出目标函数的最优
2、解，如牛顿法、最速下降法共轭梯度法及变尺度法。)在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又 有所不同。根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速 下降法,牛顿法,拟牛顿法以及共辄梯度法等。一维搜索又称线性搜索(Line Search)，就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题 常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基 本思想。由于一维搜索的使用频率较高,因此努力
3、提高求解单变量问题算法的计算效率具有 重要的实际意义。在多变量函数的最优化中，迭代格式Xk+1=Xk+akdk其关键就是构造搜索方向dk和步长因子 ak设(a)=f(xk+adk)这样从凡出发，沿搜索方向dk,确定步长因子ak,使e (a)0)则称这样的一维搜索为最优一维搜索，或精确一维 搜索,ak叫最优步长因子;如果选取ak使目标函数f得到可接受的下降量，即使得下降量f (xk) 一 f (xk+akdk)0 是用户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索, 或可接受一维搜索。由于在实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到 这一点,因为精确的一维搜索需要
4、付出较高的代价 ,而对加速收敛作用不大,因此花费计算量 较少的不精确一维搜索方法受到了广泛的重视和欢迎。精确一维搜索,作为一种理想的状态,虽然在实际计算中被采用的概率较之不精确一维搜 索要小,但有关精确一维搜索技术的研究历史悠久成果相当丰富 ,方法众多 ,其理论体系也相 对比较完备,对其进行进一步的研究仍有着重要的理论意义和现实意义。通常我们根据算法 中有无使用导数的情况,将精确一维搜索算法分为两大类:一类是不用函数导数的方法,这其 中就包括二分法（又称作对分法或中点法）、0.618法（黄金分割脚、Fibonacci法（分数法）、割 线法、成功一失败法等;另一类是使用函数导数的方法,包括经典的
5、 Newton 法、抛物线法以 及各种插值类方法等。（1）在不用导数的方法中,二分法、 0.618 法（黄金分割法）以及 Fibonacci 法均是分割方 法,其基本思想就是通过取试探点和进行函数值比较 ,使包含极小点的搜索区间不断缩短,当 区间长度缩短到一定程度时,区间上各点的函数值均接近函数的极小值,从而各点均可看作极 小点的近似。分割类方法仅需计算函数值,因此使用的范围较广,尤其适用于非光滑及导数表 达式复杂或写不出等情形。二分法是一种最简单的分割方法,每次迭代都将搜索区间缩短一半,故二分法的收敛速度 是线性的,收敛比为 0.5,收敛速度较慢。其优势就是每一步迭代的计算量都相对较小,程序
6、简 单,而且总能收敛到一个局部极小点。黄金分割法是一种针对目标函数是单峰函数亦即目标函数为凸的情形的分割类方法,因 其不要求函数可微,且每次迭代只需计算一个函数值,程序简单容易实现而被广泛采用。由于 黄金分割法是以等比例T =0.618分割缩小区间的,因此它是一种近似最优方法。针对在实际 中遇到的目标函数往往不是单峰函数的情况HPonfiger（1976）提出了 .0618法的改进形式，即在 缩小区间时,不只是比较两个内点处的函数值,而是对两内点及其两端点处的函数值进行综合 比较,以避免搜索得到的函数值反而比初始区间端点处的函数值大的情况。经过这样的修改, 算法比.0618法要更加可靠。Fib
7、onacci 法是另一种与.0618 法相类似的分割类方法,两者的主要区别在于 Fibonacci 法 搜索区间的缩短比率不是采用黄金分割数T，而是采用Fibonacci数列。在使用Fibonacci法时, 通常是由用户给定最终区间长度的上限 ,从而确定探索点的个数 ,逐步进行搜索。通过对 Fibonacci 数列进行分析表明,在迭代次数 n 趋于无穷的情形。 Fibonacci 法与.0618 法的区间 缩短率相同,因而 Fibonacci 法的收敛速度也是线性的 ,收敛比也是黄金分割数 T 。可以证 明Fibonacci法是分割方法求解一维极小化问题的最优策略而0.618法只是近似最优的，
8、但因 0.618法不必预先知道探索点的个数,程序实现更加容易,因而应用也更加广泛。抛物线法也可称作三点二次插值法,其基本思想与下面要叙述的牛顿法相同,也是用二次 函数近似目标函数,并以其极小点去近似目标函数的极小点,不同之处是牛顿法是利用目标函 数fx()在X0处的二阶Tyalor展式来逼近f(x),而抛物线法则是利用目标函数fx()在三个点 x0,xl,xZ 处的函数值构造一个二次函数作为其近似。一般地,抛物线法并不能保证算法一定收 敛,在迭代过程中有可能会出现相邻迭代点 xk，xk+1 充分接近且 xk+1 并非函数近似极小点的 退化情况。但在己知迭代点列收敛到目标函数极小点的情况,可以证
9、明:在一定的条件下,抛物 线法是超线性收敛的,收敛的阶约为 1.3。割线法与分割法类似,也是通过取试探点和进行函数值比较,使包含所求点的搜索区间缩 小,但试探点的取法与分割法不同,它是选取连接两个端点的线段与横轴的交点作为试探点。 割线法不能保证每次都使搜索区间缩小一定的比例,因而不具有全局线性收敛性,但是它却利 用了函数的一些性质。在函数接近线性时,它是非常快的。如果函数本身是线性函数时,它可 以一步找到解。(ii) 一般地，使用导数的方法通常包括牛顿法、插值法等，其中插值法又有一点二次插值法 (牛顿法)、二点二次插值法)、三点二次插值法以及三次插值法、有理插植法等常用方法。求一维无约束极小
10、化问题的牛顿法是从计算方法中方程求根的牛顿法演化而来的,其基 本思想是用目标函数f (x)在己知点x0处的二阶Tylor展式g (x)来近似代替目标函数，用g (x) 的极小点作为f (x)的近似极小点，迭代公式是叽一 gy77忘牛顿法的优点是收敛速度快,具有局部二阶收敛速度;缺点是要在每个迭代点处计算函数 的二阶导数值,增加了每次迭代的工作量,而且它要求迭代初始点要选的好,也就是说初始点 不能离极小值太远,在极小点未知的情况下,做到这一点是很困难的,这就限制了算法的应用 范围,导致算法不实用。事实上,牛顿法也是插值类方法的一种。插值法是一类重要的一维搜 索方法,其基本思想是在搜索区间内不断用
11、低次(通常不超过三次)多项式来逼近目标函数,并 用插值多项式的极小点去近似目标函数的极小点。实践表明,在目标函数具有较好的解析性 质时,插值方法比直接方法(如.0618 或 Fibonacci 法)效果更好。所谓不精确一维搜索方法是指应用各种可接受的步长选择律的线性搜索方法。常用的不 精确一维搜索算法包括利用简单准则的后退方法、经典的Armijo-Goldstein方法 Wolfe-Powell 方法和强 Wolfe-Powell 方法、以及其后发展起来的利用 Curry-Altman 步长律、改进的 Curry-Altman 步长律、Danilin-Pshenichuyi 步长律、De Le
12、one-Grippo 步长律、Backtracking 步长律等的各种方法方法特占八、可靠性有效性简便性备注度程特点度程特点度程特点问题大小接法坐标轮换法对背中稳问题舍入误差不具 低 有收敛性程序简 高 单，内存少n10鲍威尔法Si(k)有高高的共轭程度近似二次收敛性程序较繁,内存量较大n1020V接法梯度法舍入 中 误差不具侑二次收敛性结构简 高 单，内存少低维间牛顿法函数低次性要求严具有二次收敛性程序复 低 杂，内存大低维变尺度法对函 高 数要求低高二 高 次收敛性程序较繁，内存量一般高维V坐标轮换法：可靠性较高，算法效率太低，操作方便，一般只用于低维问题，n10鲍威尔法：可靠性高，算法效
13、率较高，操作较复杂，一般适用于n1020的问题 梯度法：可靠性较高，算法效率低，操作方便用于低维、低精度的问题。 牛顿法：可靠性低，算法效率高，操作不方便，很少用。变尺度法：可靠性高(BFGS比DFP更高)，算法效率高，使用较复杂，适用于高维问题2、牛顿法如前面所提到的，最速下降法在最初几步迭代中函数值下降很快外，总的说来下降的并 不快，且愈接近极值点下降的愈慢。因此，应寻找使目标函数下降更快的方法。牛顿法就是 一种收敛很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极 小值点来近似原目标函数的极小值点并逐渐逼近改点。一维目标函数f ( x)在x (k)点逼近用的二次曲线
14、(即泰勒二次多项式)为9 ( x (k) = f ( x (k) + f( x (k)( x 一 x (k) + f( X (k)( X 一 X (k )22此二次函数的极小点可由(x( k) = 0求得。对于n维问题，n为目标函数f (X)在X (k)点逼近用的二次曲线为：9 (X(k)二 f (x(k) + vf (X(k).X - X(k) +1X - X(k)T,v2f (X(k).X - X(k)2令式中的Hessian V2f (X(k) = H(X(k)，则上式可改写为：9(X(k) = f (x(k) + Vf (X(k).X - X(k) + 丄X - X(k)t.H(X(k).X -X(k)2沁 f (X)当V9(X)二0时可求得二次曲线9 (X)的极值点，且当且仅当改点处的Hessian矩阵 为正定时有极小值点。由上式得：V9 (X) = Vf (X(k) + H(X(k)X - X(k)令 V9(X)二 0，则 Vf (X(k) + H(X(k)X - X(k) = 0若H (X (k)为可逆矩阵，将上式等号两边左乘H (X (k) -1，贝y得-1 Vf (X(k) +1 X - X(k) = 0n整理后得X = X(k) -H(X(k)-1 Vf (X(k)当目标函数/(X)是二次函
