最优化算法实验3-最速下降法

最优化方法及其Matlab程序设计习题作业暨实验报告学院：数学与信息科学学院班级：12级信计一班姓名：李明学号：1201214049第三章 最速下降法和牛顿法一、上机问题与求解过程1、用最速下降法求212221216423),(x x x x x x f --+=的极小值。

解：仿照书上编写最速下降法程序如下：function [x,val,k]=grad(fun,gfun,x0) %功能：用最速下降法求解无约束化问题：min f(x) %输入：x0是初始点，fun,gfun 分别是目标函数和梯度 %输出：x,val 分别是近似嘴有点和最优值，k 是迭代次数 maxk=5000;rho=0.5;sigma=0.4;%一开始选择时选择的rho 和sibma 选择的数据不够合理，此处我参照书上的数据编写数据 k=0;epsilon=1e-5; while (k<maxk)g=feval(gfun,x0); %计算梯度 d=-g;%计算搜索方向if (norm(d)<epsilon),break ;end m=0;mk=0; while (m<20)%Armijo 搜索if (feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d) mk=m;break ;%直接利用Armijo 搜索公式,一开始的时候没有记住公式编写出现错误 end m=m+1; endx0=x0+rho^mk*d; k=k+1; end x=x0;val=feval(fun,x0) %求得每一个的函数值然后仿照书上建立两个目标函数和梯度的M 文件：function f=fun(x)f=3*x(1)^2+2*x(2)^2-4*x(1)-6*x(2); function g=gfun(x) g=[6*x(1)-4,4*x(2)-6]';选取初始点为']0,0[，调用函数程序，得出最小极值点为']500.1,6667.0[，极小值为8333.5-，在界面框中输入的程序如下：[x,val,k]=grad('fun','gfun',x0) val = -5.8333 x =0.6667 1.5000 val =-5.8333 k = 10从结果可以看出迭代次数为10次，如果选取不同的初值点则迭代次数不一样，但是极小值相同。

最优化方法实验报告Numerical Linear Algebra And ItsApplications学生所在学院：理学院学生所在班级：计算数学10-1学生姓名：甘纯指导教师：单锐教务处2013年5月实验三实验名称：无约束最优化方法的MATLAB实现实验时间: 2013年05月10日星期三实验成绩：一、实验目的：通过本次实验的学习，进一步熟悉掌握使用MATLAB软件，并能利用该软件进行无约束最优化方法的计算。

二、实验背景：（一）最速下降法1、算法原理最速下降法的搜索方向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。

2、算法步骤用最速下降法求无约束问题n R()min的算法步骤如下：xxf，a ）给定初始点)0(x ，精度0>ε，并令k=0；b ）计算搜索方向)()()(k k x f v -∇=，其中)()(k x f ∇表示函数)(x f 在点)(k x 处的梯度；c ）若ε≤)(k v ，则停止计算；否则，从)(k x 出发，沿)(k v 进行一维搜索，即求k λ，使得)(min )()()(0)()(k k k k v x f v x f λλλ+=+≥； d ）令1,)()()1(+=+=+k k v x x k k k k λ，转b ）。

（二）牛顿法1、算法原理牛顿法是基于多元函数的泰勒展开而来的，它将)()]([-)(1)(2k k x f x f ∇∇-作为搜索方向，因此它的迭代公式可直接写出来：)()]([)(1)(2)()(k k k k x f x f x x ∇∇-=-2、算法步骤用牛顿法求无约束问题n R x x f ∈),(min 的算法步骤如下：a ）给定初始点)0(x ,精度0>ε，并令k=0；b ）若ε≤∇)()(k x f ，停止，极小点为)(k x ，否则转c ）；c ）计算)()]([,)]([)(1)(2)(1)(2k k k k x f x f p x f ∇∇-=∇--令；d ）令1,)()()1(+=+=+k k p x x k k k ，转b ）。

1、最速下降法function f=fun_obj(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function g=fun_grad(x)g=[2*x(1)-400*x(1)*(-x(1)^2+x(2))-2,-200*x(1)^2+200*x(2)];% 用armijo搜索确定步长，其中xk是当前迭代点,rho,sigma为armijo参数，gk为当前下降方向function mk=armijo(xk,rho,sigma,gk )%assert(rho>0&&rho<1); % 限制Armijo参数rho在(0,1)之间%assert(sigma>0&&sigma<0.5); % 限制Armijo参数sigma在(0,0.5)之间mk=0;max_mk=100; % 最大迭代次数while mk<=max_mkx=xk+rho^mk*gk; % 求解x(k+1)iffeval('fun_obj',x)<=feval('fun_obj',xk)-sigma*rho^mk*(fun_grad(xk))*g k' %终止条件break;endmk=mk+1; % 更新迭代endfunction [xk,fk,k]=steepestmain(x0)max_iter=5000; % max number of iterationsEPS=1e-6; % threshold of gradient normrho=0.8;sigma=0.59; % Armijo parametersk=0;xk=x0; % initializationwhile k<max_iterdk=fun_grad(xk);d=-dk; % search directionif norm(dk)<EPS %precisionbreak;endmk=armijo(xk,rho,sigma,d); %armijo line searchxk=xk+rho^mk*d; %updatefk=fun_obj(xk);k=k+1;endx0=[-1,2];[xk,fk,k]=steepestmain(x0);2、Newton法function f=fun_obj(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function g=fun_grad(x)g=[2*x(1)-400*x(1)*(-x(1)^2+x(2))-2,-200*x(1)^2+200*x(2)];function He=Hess(x)He=[1200*x(1)^2-400*x(2)+2,-400*x(1);-400*x(1),200];% 用armijo搜索确定步长，其中xk是当前迭代点,rho,sigma为armijo参数，gk为当前下降方向function mk=armijo(xk,rho,sigma,gk )%assert(rho>0&&rho<1); % 限制Armijo参数rho在(0,1)之间%assert(sigma>0&&sigma<0.5); % 限制Armijo参数sigma在(0,0.5)之间mk=0;max_mk=100; % 最大迭代次数while mk<=max_mkx=xk+rho^mk*gk; % 求解x(k+1)iffeval('fun_obj',x)<=feval('fun_obj',xk)-sigma*rho^mk*(fun_grad(xk))*g k' %终止条件break;endmk=mk+1; % 更新迭代endfunction [xk,fk,k]=Newtonmain(x0)max_iter=5000; % 最大迭代次数EPS=1e-6; % 精度rho=1;sigma=1e-4; % Armijo 参数k=0;xk=x0; % 初值while k<max_iter % 迭代次数超过最大迭代次数时跳出循环k=k+1;dk=fun_grad(xk); % x(k)处的梯度H=Hess(xk); % x(k)处的Hessian矩阵d=-H\dk'; % x(k)处的搜索方向if norm(dk)<EPS % 终止条件break;endmk=armijo(xk,rho,sigma,d'); % 利用armijo搜索确定步长xk=xk+rho^mk*d'; % 计算x(k+1)的值fk=fun_obj(xk); % 计算x(k+1)处函数的值endx0=[1.2,1.2];[xk,fk,k]=Newtonmain(x0);3、Newton-最速下降法function f=fun_obj(x)f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;function g=fun_grad(x)g=[2*x(1)-400*x(1)*(-x(1)^2+x(2))-2,-200*x(1)^2+200*x(2)];function He=Hess(x)He=[1200*x(1)^2-400*x(2)+2,-400*x(1);-400*x(1),200];% 用armijo搜索确定步长，其中xk是当前迭代点,rho,sigma为armijo参数，gk为当前下降方向function mk=armijo(xk,rho,sigma,gk )%assert(rho>0&&rho<1); % 限制Armijo参数rho在(0,1)之间%assert(sigma>0&&sigma<0.5); % 限制Armijo参数sigma在(0,0.5)之间mk=0;max_mk=100; % 最大迭代次数while mk<=max_mkx=xk+rho^mk*gk; % 求解x(k+1)iffeval('fun_obj',x)<=feval('fun_obj',xk)-sigma*rho^mk*(fun_grad(xk))*g k' %终止条件break;endmk=mk+1; % 更新迭代endfunction [xk,fk,k]=newton_steepest(x0)max_iter=5000; % 最大迭代次数EPS=1e-6; % 精度rho=1;sigma=1e-4; % Armijo 参数 rho=0.8;sigma=0.59;k=0;xk=x0; % 初值while(k<max_iter)k=k+1;dk=fun_grad(xk); % x(k)处的梯度，注意dk为行向量G=Hess(xk); % x(k)处的Hessian矩阵d=-G\dk'; % x(k)处的搜索方向,注意此时d为列向量if norm(dk)<EPS % x(k)处的搜索方向break;end%% 判断d是否为下降方向if d'*dk'<0 % 若d'*dk<0,则d为下降方向d=d;else% 若d'*dk>=0,则d不为下降方向，令下降方向为负梯度方向 d=-dk';endmk=armijo(xk,rho,sigma,d'); % 利用armijo搜索确定步长 xk=xk+rho^mk*d'; % 计算x(k+1)的值fk=fun_obj(xk); % 计算x(k+1)处函数的值endx0=rand(1,2000);[xk,fk,k]=newton_steepest(x0);。

最速下降法Matlab实现实验目的：1.掌握迭代法求解无约束最优化问题的基本思想2.通过实验掌握最速下降法的Matlab算法的基本步骤实验内容：1.迭代法求解无约束最优化问题的基本思想给定一个初始点x(0), 按照某一迭代规则产生一个迭代序列{x(k)}. 使得若该序列是有限的, 则最后一个点就是原问题的极小点; 否则, 若序列{x(k)} 是无穷点列时, 它有极限点且这个极限点即为原问题的极小点.设x(k) 为第k 次迭代点, d(k) 为第k 次搜索方向, a(k)为第k 次步长因子, 则第k 次迭代完成后可得到新一轮(第k + 1 次) 的迭代点x(k+1) = x(k) + a(k) d(k).2.无约束优化问题迭代算法的一般框架步0 给定初始化参数及初始迭代点x(0). 置k := 0.步1 若x(k) 满足某种终止准则, 停止迭代, 以x(k) 作为近似极小点.步2 通过求解x(k) 处的某个子问题确定下降方向d(k).步3 通过某种搜索方式确定步长因子a(k), 使得f(x(k) + a(k) d(k)) < f(x(k)).步4 令x(k+1) := x(k) + a(k) d(k), k := k + 1, 转步1.3. 最速下降法的基本步骤步0 选取初始点x(0) ∈R^n, 容许误差0 ≤e ≪1. 令k := 1.步1 计算g(k) = ∇f(x(k)). 若‖g(k)‖≤e, 停算, 输出x(k)作为近似最优解.步2 取方向d(k)= −g(k).步3 由线搜索技术确定步长因子a(k),即min f(a(k))=f(x(k)+a(k)d(k)).步4 令x(k+1) := x(k) + a(k)d(k)), k := k + 1, 转步1.4. 编写最速下降法Matlab 程序5. 利用程序求解无约束最优化问题f(x，y)=x^2+2y^2的最优值.。

上机报告一.最速下降法算法简述：1.在本例中，先将最速下降方向变量赋一个值，使其二范数满足大于ε的迭代条件，进入循环。

2.将函数的一阶导数化简，存在一个矩阵，将其hesse矩阵存在另一个矩阵。

依照公式求出α，进而求出下一任迭代的矩阵初值。

循环内设置一个计数功能的变量，统计迭代次数。

3.求其方向导数的二范数，进行判别，若小于ε，则跳出循环，否则将继续迭代。

4.显示最优解，终止条件，最小函数值。

心得体会：最速下降法的精髓，无疑是求梯度，然后利用梯度和hesse矩阵综合计算，求解下一个当前最优解。

但是，要求函数是严格的凸函数，结合严格凸函数的大致图像，这就给初值的选取提供了一点参考。

例如在本例中，由于含有两个变量的二次方之和，结合大致图像，想当然的，初值的选取应当在原点附近；又因为变量的二次方之和后面，还减去了变量的一次形式和一次混合积，所以初值的选取应该再向第一象限倾斜。

综合以上考量，第一次选取（1,1）作为初值，判别精度方面，取到千分位，暂定为0.001。

运行以后，结果显示迭代了25次，最优解为（3.9995，1.9996），终止条件为5.4592e-04，目标函数为-8.0000。

这个结果已经相当接近笔算结果。

整体的运行也比较流畅，运算速度也比较快。

第二次取值，决定保留判别精度不变，将初值再适当向第一象限倾斜，取（2,2）作为初值，运行后，显示只迭代了11次！最优结果显示（3.9996，1.9997），终止条件为3.6204e-04，最优解-8.0000。

可见，最优结果更接近理想值，终止条件也变小了，最关键的是，迭代次数减少至第一次的一半以下！这说明以上初选取的方向是对的！第三次再进行初值细化，判别精度仍然不变，初值取（3,3）。

结果令人兴奋，只迭代了四次！最优解已经显示为（4.0000,2.0000），终止条件为2.4952e-04，目标函数-8.0000。

第四次，判别精度不变，取初值（4,4）。

最优化Armijo算法确定步长的最速下降法资料最速下降法是最优化算法中最简单、最基础的一种方法，但其收敛速度较慢且容易陷入局部最优解。

因此，在最速下降法的基础上，可以通过引入步长的方法来提高算法的收敛速度。

而Armijo算法就是一种常见的用于确定步长的方法。

最速下降法基础假设我们要最小化目标函数f(x)，那么最速下降法的思路就是从一个初始点x0开始，不断朝着负梯度方向进行迭代，直到找到最优解x∗，即：$x_{k+1} = x_k - \\alpha_k \ abla f(x_k)$其中，ablaf(x k)是f(x)在x k处的梯度，$\\alpha_k$ 是步长（也称为学习率），表示每次迭代的步长大小。

但这里还有一个问题：如何确定每次迭代的步长呢？Armijo算法Armijo算法是一种基于梯度下降法的步长确定方法。

它的思路是，每次迭代的步长不应该过大，否则容易导致超出收敛区域。

同时，步长也不应该过小，否则收敛速度会变得非常缓慢。

因此，步长的大小应该恰到好处，即在一定范围内找到一个最优的步长大小。

具体地，Armijo算法通过二分搜索的方法，在可行步长范围内找到一个最优的步长 $\\alpha_k$。

具体过程如下：1.首先初始化 $\\alpha_0$，并设定一些参数，如尝试步长大小t、可行步长下界 $\\tau$ 和函数下降的最小比例 $\\gamma$。

2.计算目标函数f(x k−t ablaf(x k))，以及根据一定准则确定下一个$\\alpha$。

3.如果 $f(x_k - \\alpha_k\ abla f(x_k))$ 函数值比f(x k)减小了一些比例$\\gamma$，则认为当前 $\\alpha_k$ 是可行的步长。

4.如果当前 $\\alpha_k$ 不是可行的步长，则将其折半，即 $\\alpha_k\\leftarrow \\alpha_k/2$，直到找到一个可行的步长为止。

最速下降法原理及其算法实现最速下降法（Gradient Descent）是一种常用的优化算法，用于寻找函数的最小值。

它是一种迭代的方法，每次迭代都沿着负梯度方向更新参数，以减小目标函数的值。

在本文中，我们将介绍最速下降法的原理和算法实现。

1.最速下降法原理假设有一个目标函数f(x)，其中x是一个向量。

我们的目标是找到使得f(x)最小的x。

最速下降法的思想是从任意初始点x0开始迭代，按照梯度方向更新参数，直到达到最优解。

具体地，设f(x)的梯度为g(x)，即g(x)=∇f(x)。

最速下降法的迭代公式为：x(n+1)=x(n)-α*g(x(n))其中，x(n)表示第n次迭代的参数向量，α是迭代步长，也称为学习率。

每次迭代时，我们沿着梯度方向更新参数，α控制更新的步长。

我们期望通过不断迭代，逐渐逼近最优解。

2.最速下降法算法实现步骤1:初始化参数。

选择初始点x(0)，设定学习率α，设定最大迭代次数。

步骤2:迭代过程。

重复以下步骤，直到达到最大迭代次数或满足收敛条件：a)计算梯度g(x(n))=∇f(x(n))。

b)更新参数。

根据迭代公式进行更新，x(n+1)=x(n)-α*g(x(n))。

c)判断终止条件。

比较f(x(n+1))和f(x(n))的差异，如果差异小于一定阈值，停止迭代。

步骤3:输出结果。

输出最优参数x*，即使得f(x)最小的参数。

需要注意的是，在实际应用中，我们可能需要进行一些改进来提高最速下降法的性能。

例如，可以使用线来自适应地选择学习率以保证每次更新获得合理的进展。

此外，为了加快收敛速度，可以使用加速算法，如动量法、Nesterov 加速梯度法等。

3.总结。