[最优化第一次作业.docx

无约束优化算法最优化课程作业（一）姓名：丁敏学号：31130510012014/6/24一、无约束优化算法无约束优化计算方法是数值计算领域中十分活跃的研究课题。快速地求解无约束优化问题已经成为当今的焦点，除了其自身的重要性外，还由于目前求解约束优化问题的基本思想之一就是把约束问题变换为一系列无约束子问题进行求解。因此，无约束优化算法的求解效率将直接影响到约束问题的求解，尤其是在大规模优化问题中。所以，对无约束优化算法的研究具有重要的理论意义和实际价值。无约束优化问题，是指优化问题的可行集为，无约束的标准形式（1-1）为： 求解无约束优化问题时将会涉及到以下概念：(1) 驻点、鞍点：若在点处可微，并且，则称为的一个驻点(或者平稳点)。既不是极小点，也不是极大点的驻点称为鞍点。(2) 全局最优解：若均有，则称为问题(1-1)的全局最优解(3) 局部最优解：若且存在使得则称为问题(1-1)的一个局部最优解（极小点）；若且存在使得则称为问题(1-1)的一个局部最优解（极大点）；当目标函数 f ( x )为凸函数时，我们认为全局最优解即是局部最优解，然而，通常寻求全局最优解并不容易。因此，在非线性优化中我们认为局部最优解即为所求。无约束优化算法可以分为两大类: 一类是借助目标函数的导数信息来构造下降的搜索方向。另一类是由目标函数值信息直接搜索求解的方法。本文章重点介绍最速下降法，阻尼牛顿法以及共轭梯度法。二、最速下降法1、最速下降法思想经典最速下降法是由 Cauchy于 1847 年提出的，Forsythe 和 Motzkin在 1951 年对它做了初步的分析。1959 年，Akaike对最速下降法做出了最全面的分析。最速下降法以负梯度方向为极小化算法的下降方法设函数在附近连续可微，且迭代序列为当时，目标函数值最大。2、算法流程步1 给出；步2 计算；步3 如果，则，停止；否则，令，由一维搜索步长，使得；步4 令，，转步骤2。3、算法代码（最速下降法程序）function [x,val,k]=grad(fun,gfun,x0)maxk=5000;rho=0.5;sigma=0.4;k=0;epsilon=1e-5;while(kmaxk) g=feval(gfun,x0); d=-g; if(norm(d)epsilon),break;end m=0;mk=0; while(m20) if(feval(fun,x0+rho^m*d)feval(fun,x0)+sigma*rho^m*g*d) mk=m;break; end m=m+1; end x0=x0+rho^mk*d; k=k+1;endx=x0;val=feval(fun,x0); 4、实例分析利用最速下降法程序求解无约束优化问题该问题有精确解解：首先建立两个分别计算目标函数和梯度的M文件：function f=fun(x)f=200*(x(1)^2-x(2))^2+(x(1)-1)^2+x(3)^2+(x(4)-2)^2+x(5)^2+x(6)^2+x(7)^2+x(8)^2+x(9)^2+x(10)^2;function g=gfun(x)g=[800*x(1)*(x(1)^2-x(2))+2*(x(1)-1),-400*(x(1)^2-x(2)),2*x(3),2*(x(4)-2),2*x(5),2*x(6),2*x(7),2*x(8),2*x(9),2*x(10)];利用程序，取不同的初始点，数值结果如下：初始点（x0）迭代次数（k）目标函数值（f(xk) ）[0.0,0.0, 0.0,1.0, 0.0,0.0, 0.0,0.0, 0.0,0.0]’30038.9143e-011[2.0, 1.0, 0.0, 1.0, 0.0, 0.0,0.0, 0.0,0.0,0.0]12301.2395e-010[-1.0, -1.0, 0.0, 3.0, 0.0, 0.0,0.0, 0.0,0.0,0.0]27509.4859e-011[-1.0, -1.0,1.0, 3.0, 1.0, 0.0,0.0, 0.0,0.0,0.0]7061.0869e-010[-1.2, 1, 0, 1, 0, 0, 0, 0, 0 ,0]27759.1509e-011[-10, 10, 0, 10, 0, 0, 0, 0, 0 ,0]29801.2009e-010三、阻尼牛顿法1、阻尼牛顿法思想与最速下降法一样，牛顿法也是求解无约束优化问题最早使用的经典算法之一，其基本思想是用迭代点处一阶导数（梯度）和二阶导数（Hesse矩阵）对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的极小值点。阻尼牛顿法的迭代公式是：2、算法流程步1 给