数学与计算科学学院
实验报告
实验项目名称使用非精确线搜索Armijo算法确定步长的最速下降法
所属课程名称最优化方法
实验类型算法编程
实验日期
班级
学号
姓名
成绩
，其中为步长。如果步长足够小，则可以保证每一次迭代都在减
的值变化到使得在两次迭代之间的差值足够小，比如直到两次迭代计算出来的基本没有变化，则说明此时已经达
就是使得函数最小时的
其迭代公式为,其中代表梯度负方向，表示梯度方向上的搜索步
其最小值在处，函数值为。但是此函数具有狭窄弯曲的山谷，最小
附录1：源程序
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。
2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。
3．实验原理：简要说明本实验项目所涉及的理论知识。
4．实验环境：实验用的软、硬件环境。
5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。
对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设
计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。
6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。
7．实验结论（结果）：根据实验过程中得到的结果，做出结论。
8．实验小结：本次实验心得体会、思考和建议。
9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。
数学与计算科学学院 实验报告 实验项目名称使用精确搜索算法确定步长的最速下降法 所属课程名称最优化方法 实验类型算法编程 实验日期 201 班级 学号 姓名 成绩 一、实验概述： 【实验目的】
(1) 掌握精确搜索算法确定步长的最速下降法； (2) 使用计算机语言表达最优化方法。 【实验原理】 最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 设无约束问题中的目标函数 f : Rn R1一阶连续可微。 最速下降法的基本思想是：从当前点k x 出发，取函数 f (x)在点k x 处下降最快的方向作为我们的搜索方向k p .由 f (x)的 Taylor 展式知 ()()()() k k k k T k k f x f x tp t f x p o tp -+=-?+ 略去t 的高阶无穷小项不计，可见取()k k p f x =-?时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第 1 步 选取初始点(0)x ，给定终止误差ε ，令k:=0； 第 2 步 计算?f (k x )，，若‖?f (k x )‖≤ ε ，停止迭代.输出k x .否则 进行第三步 第 3 步 取()k k p f x =-?； 第 4 步进行一维搜索，求k t ，使得 1()(())min (()) k k k k k k f x f x t f x f x t f x +=-?=-? 令,k:=k+1，转第2 步。 由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。 【实验环境】 计算机 VC++
最速下降法求解线性代数方程组 要求：对于给定的系数矩阵、右端项和初值，可以求解线性代数方程组 一、最速下降法数学理论 在基本迭代公式k k k k P t X X +=+1中，每次迭代搜索方向k P 取为目标函数)(X f 的负梯度方向，即)(k k X f P -?=，而每次迭代的步长k t 取为最优步长，由此确定的算法称为最速下降法。 为了求解问题)(min X f ，假定我们已经迭代了k 次，获得了第k 个迭代点k X 。现在从k X 出发，可选择的下降方法很多，一个非常自然的想法是沿最速下降方向（即负梯度方向)进行搜索应该是有利的，至少在k X 邻近的范围内是这样。因此，去搜索方向为 )(k k X f P -?=. 为了使目标函数在搜索方向上获得最多的下降，沿k P 进行一维搜索，由此得到第1+k 个跌带点，即 )(1k k k k X f t X X ?-=+， 其中步长因子k t 按下式确定 ))((m in ))((k k k k k k X f t X f X f t X f ?-=?-， ))(,(1k k k X f X ls X -?=+. （1） 显然，令 ,2,1,0=k 就可以得到一个点列 ,,,210X X X ,其中0X 是初始点，由计算者任意选定。当)(X f 满足一定的条件时，由式（1）所产生的点列}{k X 必收敛于)(X f 的极小点。
二、最速下降法的基本思想和迭代步骤 已知目标函数)(X f 及其梯度)(X g ，终止限21,εε和3ε. （1）选定初始点0X ，计算)(),(0000X g g X f f ==；置0=k . （2）作直线搜索：),(1k k k g X ls X -=+；计算)(),(1111++++==k k k k X g g X f f . 用终止准则检验是否满足：若满足，则打印最优解))(,(11++k k X f X ，结束；否则，置1+=k k ，转（2） （3）最速下降法算法流程图如图所示.
《MATLAB 程序设计实践》课程考核 实践一、编程实现以下科学计算法，并举一例应用之。（参考书籍《精通MATLAB 科学计算》，王正林等著，电子工业出版社，2009年） “最速下降法无约束最优化” 最速下降法： 解： 算法说明：最速下降法是一种沿着N 维目标函数的负梯度方向搜索最小值的方法。 原理：由高等数学知识知道任一点的负梯度方向是函数值在该点下降最快的方向，那么利用负梯度作为极值搜索方向，达到搜寻区间最速下降的目的。而极值点导数性质，知道该点的梯度=0，故而其终止条件也就是梯度逼近于0，也就是当搜寻区间非常逼近极值点时，即：当▽f(a ）→0推出f(a ）→极值）（x f ，f(a ）即为所求。该方法是一种局部极值搜寻方法。 函数的负梯度表示如下： -g(x ）=-▽f(x)=-?????1 )(x x f 2)(x x f ?? … T N x x f ?????)( 搜索步长可调整，通常记为αk （第k 次迭代中的步长）。该算法利用一维的线性搜索方法，如二次逼近法，沿着负梯度方向不断搜索函数的较小值，从而找到最优解。 方法特点（1）初始值可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径胃绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。（3）全局收敛，线性收敛，易产生扭摆现象而造成早停。 算法步骤：最速下降法的基本求解流程如下： 第一步 迭代次数初始化为k=0，求出初始点0x 的函数值f 0=f （0x ）。 第二步 迭代次数加1，即k=k+1，用一维线性搜索方法确定沿负梯度方向-1-k g 的步长1k -α，其中1k -α=ArgMinaf （111k /----k k g g x α）。 第三步 沿着负梯度方向寻找下一个接近最小值的点，其中步长为1k -α，得到下一点的坐标为：1111/-----=k k k k k g g x x α。
实验报告 实验名称：加速步长法 院（系）：机电学院 专业班级：机械制造及其自动化 姓名：赵丹 学号：100710431 2013年5 月3 日
实验一：加速步长法实验日期：2013年5 月3日一、实验目的 了解MATLAB的基本运用 了解MATLB在优化中的使用 二、实验原理 加速步长法是利用试探来确定单谷函数的初始搜索区间。其主要思路是：从一点出发，按照一定的步长，试图确定出函数值呈现“高低高”规律的相邻三点。从一个方向试探搜索，如不成功，则沿反方向探索。如方向正确，则加大步长探索。直至最终三点x1x2x3，满足x1 h=-h; x2=x4; f2=f4; else x3=x2; x2=x1; x1=x4; break; end end end left=min(x1,x3); right=x1+x3-left; 四调用执行程序： clc syms t f=t^3-t^2-2*t+1; [left,right]=xiti4_1(f,0,0.1) 执行结果：left = 0.7000 right = 3.1000 实验小结 通过本实验了解了了matlab的基本操作方法，了解加速步长法的原理与基本运用 最速下降法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. 变步长梯形求积法计算定积分 1．原理： 变步长求积法的主要思想是利用若干小梯形的面积代替原方程的积分，当精度达不到要求时，可以通过增加点数对已有的区间再次划分，达到所需精度时即可；其中由于新的式子中有原来n点中的部分项，故可以省略一些计算，符合了计算机计算存储的思想。 主要公式：T2n=T n/2+(h/2)*Σf(x k+; 2．C++语言实现方式： 通过每次的T n值和新增的函数值点计算T2n，再通过判断|T n-T2n|的大小来判断是否达到精度要求。 3．源程序如下： #include"" #include"" double f(double x)//预先输入的待积分函数 { double s; s=log(x*x); return(s); } double ffts(double a,double b,double eps) { int n,k; double fa,fb,h,t1,p,s,x,t; fa=f(a); fb=f(b); n=1; h=b-a; t1=h*(fa+fb)/2; p=eps+1; while(p>=eps) { s=0; for(k=0;k<=n-1;k++) { x=a+(k+*h; s=s+f(x); } t=t1/2+h*s/2; p=fabs(t1-t); cout<<"步长n为:"< 最速下降法 %% 最速下降法图示 % 设置步长为0.1，f_change为改变前后的y值变化，仅设置了一个退出条件。syms x;f=x^2; step=0.1;x=2;k=0; %设置步长,初始值,迭代记录数 f_change=x^2; %初始化差值 f_current=x^2; %计算当前函数值 ezplot(@(x,f)f-x.^2) %画出函数图像 axis([-2,2,-0.2,3]) %固定坐标轴 hold on while f_change>0.000000001 %设置条件，两次计算的值之差小于某个数，跳出循环 x=x-step*2*x; %-2*x为梯度反方向，step为步长，！最速下降法！ f_change = f_current - x^2; %计算两次函数值之差 f_current = x^2 ; %重新计算当前的函数值 plot(x,f_current,'ro','markersize',7) %标记当前的位置 drawnow;pause(0.2); k=k+1; end hold off fprintf('在迭代%d次后找到函数最小值为%e，对应的x值为%e\n',k,x^2,x) wolfe准则 unction [alpha, newxk, fk, newfk] = wolfe(xk, dk) rho = 0.25; sigma = 0.75; alpha = 1; a = 0; b = Inf; while (1) if ~(fun(xk+alpha*dk)<=fun(xk)+rho*alpha*gfun(xk)'*dk) b = alpha; alpha = (alpha+a)/2; continue; end if ~(gfun(xk+alpha*dk)'*dk>= sigma*gfun(xk)'*dk) a = alpha; alpha = min([2*alpha, (b+alpha)/2]); continue; end break; end newxk = xk+alpha*dk; fk = fun(xk); newfk = fun(newxk); 实验的题目和要求 一、所属课程名称： 最优化方法 二、实验日期: 20１０年5月１0日~２010年5月１５日 三、实验目的 掌握最速下降法,牛顿法和共轭梯度法的算法思想，并能上机编程实现相应的算法。 二、实验要求 用ＭA ＴLA Ｂ实现最速下降法，牛顿法和共轭梯度法求解实例。 四、实验原理 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f 在迭代点k x 处的T ａylor 展开式作为模型函数,并利用这个二次模型函数的极 小点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向k d 仅仅是负梯度方向k g -与上一次接 待的搜索方向1-k d 的组合。 五.运行及结果如下： 最速下降法: 题目：f=（x-2）^２+(y-４）^2 Ｍ文件： fu ｎcti ｏn [R,n]=stee ｌ（x0,y0，e ｐs) syms ｘ； syms y ; f=(x-2)^2+(ｙ-４）^2; ｖ=[x,y]; ｊ＝ｊac ｏbi ａｎ(f ，v); T=[s ｕbs(j(１),ｘ,x0）,subs （j （2),ｙ，y0)]; temp=s ｑrt((Ｔ(1)）^2＋(T （2))＾2); x １＝x0;y １=y ０; ｎ=0; sym ｓ k ｋ; w ｈi ｌe (temp>eps ） ｄ=－Ｔ； ｆ1=x １+kk*d(1);f2=ｙ1+k ｋ*ｄ（２); fT=[su ｂs(j （1),ｘ,ｆ１),ｓｕb ｓ(j(2),ｙ,ｆ2)]; fu ｎ=sqrt((fT(1））^2+(ｆT(2)）^２）; 第五题： 解：选择类型为： 2/13()x t y t x e x =+ 其中123,,x x x 是待求参数。根据最小二乘原理，参数123,,x x x 是下面优化问题的解。 []2 8 1231 m in (,,)()i i i f x x x y t y == -? 用最速下降法求解这一无约束的最优化问题。 zuiyouhua.m function sh=zuiyouhua(x0) % x0为初始猜测值 syms x y z a al; %====================================== t=[0.2,1,2,3,5,7,11,16]; r1=[5.05,8.88,11.63,12.93,14.15,14.73,15.30,15.60]; minf=0; for i=1:8 r(i)=x*exp(y/t(i))+z-r1(i); %构造最小二乘最优化的目标函数 minf=r(i)^2+minf; end %====================================== f1=diff(minf,x); f2=diff(minf,y); f3=diff(minf,z); %求目标函数的梯度 F=[f1,f2,f3]; %====================================== Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); k=0; %====================================== %最速下降法核心迭代程序 while 1 x1=x0+a*Fx; P=subs(minf,{x,y,z},x1); xx1=xianxing(P); %调用线性搜索函数 al=huangjing(P,xx1); %调用黄金分割法函数； x0=x0+al*Fx; Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); if norm(Fx1)<5e-4 sh=x0; return; end end %====================================== function xx=xianxing(Pa) %一维搜索法线性搜索函数 aa=findsym(Pa); a1=1; h=0.5; k=0; t1=2; while 1 a2=a1+h; Pa1=subs(Pa,aa,a1); Pa2=subs(Pa,aa,a2); if Pa2< Pa1 h=t1*h; a0=a1; a1=a2; k=k+1; if k>1000 disp('迭代步数太多，可能不收敛！'); end else if k==0 h=-h; a0=a2; else c1=min(a0,a2); d1=max(a0,a2); xx=[c1,d1]; return; end end end %====================================== function al1=huangjing(Pb,xx2) 二维铸造充型过程数值模拟的特征分数步长法? 鲁统超1，葛亮2 1山东大学数学与系统科学学院, （250100） 2 山东大学数学与系统科学学院, （250100） E-mail ：lutc@https://www.doczj.com/doc/6b10638882.html, 摘 要：铸造充型过程的数学模型是包括连续性方程和动量方程的偏微分方程组。本文利用分数步长法将动量方程分裂成两部分，对第一个方程采用特征差分法进行处理，对第二个方程结合连续性方程进行处理后得到压力的 泊松方程，用迭代法进行求解，给出了收敛性分析和稳定性条件。 关键词：分数步长；特征差分；收敛性；迭代。 1. 引 言 铸造生产的实质就是直接将液态金属浇入铸型并在铸型中凝固和冷却，进而得到铸件。液态金属的充型过程是铸件形成的第一个阶段。许多铸造缺陷(如卷气、夹渣、浇不足、冷隔及砂眼等)都是在充型不利的情况下产生的。因此，了解并控制充型过程是获得优质铸件的重要条件。但是，由于充型过程非常复杂，长期以来人们对充型过程的把握和控制主要是建立在大量实验基础上的经验准则。随着计算机的发展，铸件充型过程数值模拟才得到广泛应用。 充型过程流场数值模拟的主控方程均为非线性方程。其计算使用有限差分或有限元等数值方法求解质量守恒方程(连续性方程)和动量守恒 方程即Navier-Stokes 方程，以得出流体运动规律。在以前的研究中，Chorin(1968)和Temam(1969)分别独立的提出投影法。1972年由Minnesota 大学的Patankar 与Spalding 提出了simple 算法，这是一个压力修正算法，在以后的研究中又有simplec 方法,Raithby 提出的simplex 方法, Sheng 等提出的simplet 算法。 本文中利用分数步长法的思想将动量方程分裂成两部分，对第一个方程采用特征差分法求解，对第二个方程结合连续性方程进行处理后得到压力的 泊松方程，我们用迭代法进行求解，给出了收敛性分析和稳定性条件。 2. 问题的数学模型 铸造充型过程的模型主要由连续性方程和动量方程组成。 (a) 流体的动量方程 1x u p V u g u t x μρρ ??=???++???r " (2.1) ? 本课题得到教育部高等学校博士点基金资助，编号：20030422049 - 1 - 梯度法（又名,最速下降法） (该法总可以收敛，但是，在接近真解时收敛的速度会放慢。) 梯度法又称为最速下降法，用于求解实系数非线性方程组 12(,,,)0, 1,2,,i n f x x x i n == （7－15） 的一组根。梯度法首先是定义一个目标函数 2 12121 (,,,)(,,,) n n i n i x x x f x x x =Φ= ∑ （7－16） 使目标函数2 1 n i i f =Φ= ∑ 达到最小的12,,,n x x x 是我们寻找的一组解，这是非 线性最小二乘法问题。 如果第(0,1,2,)k k = 步求得一组解1 2 ,,,n k k k x x x ，使得 12(,,,)n k k k x x x ε Φ< （7－17） 则认为1 2 ,,,n k k k x x x 是原方程组满足一定精度的()ε要求的一组解。 梯度法的计算过程是： （1）先给定一组不全为零的初值1 2 000,,,n x x x ，第k 步的一组根为1 2 ,,,n k k k x x x ； （2）计算目标函数1 2 (,,,)n k k k x x x Φ 的值；(单独子程序:fn =TargetFunction) （3）若1 2 (,,,)n k k k x x x εΦ< ，则认为1 2 ,,,n k k k x x x 是满足一定精度()ε的一组 解，否则，作如下修正计算 1 α +=?Φ=-?i k i i k k k i i x x x x x （7－18） 其中 121212********* 1111222 (,,,) (,,,)(,,,)(,,,)(,,,)(,,,)(,,,)*,1,2,,α ==?Φ= ??? ??Φ ? ? ???Φ+-Φ?Φ=??Φ+-Φ?Φ= ?Φ+-Φ?Φ = ?==∑ n k j j n n n n n n k k k k n j j x x k k k k k k k k k k k k k k k k k k n n n k i i x x x x x h x x x x x x h x x h x x x x x h x x x h x x x x h h H x i n ??? ???? ??? ? ?????? （7－19） H 为控制收敛的常数，通常选为（10－5～10－6），收敛精度ε 选为（10－6～10 －8 ）。 （4）重复修正1 k i x +，直到 12111 (,,,)n k k k ε +++ΦΦΦ< ，计算终止。 牛顿法 迭代公式：(1)2()1()[()]()k k k k x x f x f x +-=-?? Matlab 代码： function [x1,k] =newton(x1,eps) hs=inline('(x-1)^4+y^2'); 写入函数 ezcontour(hs,[-10 10 -10 10]); 建立坐标系 hold on; 显示图像 syms x y 定义变量 f=(x-1)^4+y^2; 定义函数 grad1=jacobian(f,[x,y]); 求f 的一阶梯度 grad2=jacobian(grad1,[x,y]); 求f 的二阶梯度 k=0; 迭代初始值 while 1 循环 grad1z=subs(subs(grad1,x,x1(1)),y,x1(2)); 给f 一阶梯度赋初值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2)); 给f 二阶梯度赋初值 x2=x1-inv(grad2z)*(grad1z)'; 核心迭代公式 if norm(x1-x2) end end end 优点：在极小点附近收敛快 缺点：但是要计算目标函数的hesse 矩阵 最速下降法 1. ：选取初始点xo ，给定误差 2. 计算一阶梯度。若一阶梯度小于误差，停止迭代，输出 3. 取()()()k k p f x =? 4. 10 t ()(), 1.min k k k k k k k k k k t f x t p f x tp x x t p k k +≥+=+=+=+进行一维搜索，求，使得令转第二步 例题： 求min (x-2)^4+(x-2*y)^2.初始值（0,3）误差为0.1 (1)编写一个目标函数，存为f.m function z = f( x,y ) z=(x-2.0)^4+(x-2.0*y)^2; end (2)分别关于x 和y 求出一阶梯度，分别存为fx.m 和fy.m function z = fx( x,y ) z=2.0*x-4.0*y+4.0*(x-2.0)^3; end 和 function z = fy( x,y ) 随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发 展。可以让它们与广义预测控制相结合，建立高精度、多模态的预测模型。 使广义预测控制在异常情况下可以稳定运行，推进广义预测控制的进一步 发展。 2.2.1最速下降法 最速下降法是无约束最优化中是比较有效的方法，它是以d}=一可(x})作为下 降方向的算法。其迭代格式为 xx+i=xx一。*Of (xk) 上式中，一般通过精确线搜索准则求得步长因子。*，当然也不排除可以利用非精确 线搜索准则来求得步长因子。*。不管最速下降法采取何种线搜索准则，它均具有全 局收敛性，但是这也不能直接就认为最速下降算法就是一个良好的优化算法。在实际 试验中，有很多优化问题利用最速下降法并不是下降的特快，反而下将的十分缓慢。 这是因为出现了锯齿现象:就是在计算过程中，最速下降法开始几步还是挺快的，但 是当目标函数f (x)的等高线接近于一个球的时候，就出现了类似锯齿现象，前进十 分缓慢，降低了算法的效能。 2.2.12.2.2 牛顿法 牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二 次泰勒展开式，并将二次泰勒展开式进行极小化。其迭代格式为 x}+}=xA十d} (2-5) 其中步长因子。、=l} d、为02f (x} )d + Of (xA ) = 0的解。当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候， 牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。我们知道目标 函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束 最优化问题((1-1)的最优解x的时候，并且}Z.f (x.)正定的时候，那么牛顿法就会有 很快的收敛速度，而由此算法产生的点列也具有了超线性收敛速度，同时还在一定条 件下具有二次收敛性;假如初始点与无约束最优化问题(1-1)的最优解x’相距比较 远的时候，这时的}Z.}(x})就不一定是正定的了，也就存在了一个问题，那就是此时 的牛顿方向就不一定是下降方向，有可能是上升方向，此时由此算法产生的点列可能 也就不收敛于无约束最优化问题((1-1)的最优解了。综上所述，让步长“R =1即“*恒 取常数是不合适的。经过研究学者们发现了一个方法可以改善这个情况，那就是利用 已有的线搜索方法来确定步长因子，也就是步长因子是可变的。其迭代格式为 x1. }, = x:一a}.OZ f (x}.)一，Of (x,. ) C 2-6 ) 2.2.2牛顿法 牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二 次泰勒展开式，并将二次泰勒展开式进行极小化。其迭代格式为 x}+i=xA+d}(2-5) 其中步长因子。、=l} d、为02f (x} )d + Of (xA ) = 0的解。当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候， 牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。我们知道目标 函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束 %利用wolf-powell线性搜索步长 function alpha1=wolfpowell(f,x,x0,d) g=jacobian(f,x); %求函数f的梯度 sigma1=0.25; %给定常数1 sigma2=0.7; %给定常数2 beta1=5; %步长初始值 theta1=0.5; %步长变化比例1 theta2=0.7; %步长变化比例2 %求步长alpha1 if subs(f,x,x0+d)<=subs(f,x,x0)+sigma1*subs(g,x,x0)*d'&&subs(g,x,x0+d)*d'>=sigm a2*subs(g,x,x0)*d' alpha1=1; %满足第一个条件的最大步长 else alpha1=beta1; while subs(f,x,x0+alpha1*d)>subs(f,x,x0)+sigma1*alpha1*subs(g,x,x0)*d' alpha1=theta1*alpha1; end while subs(f,x,x0+alpha1/theta1*d)<=subs(f,x,x0)+sigma1*alpha1/theta1*subs(g,x,x0)*d' alpha1=alpha1/theta1; end end %使步长满足第二个条件 while subs(g,x,x0+alpha1*d)*d' 微分方程数值解 姓名： 班级： 一．二维抛物方程分布步长法 实验用的二维热传导 是方程是： 22(,,)sin()sin()0,1,0t u x y t x y e x y t πππ-=<<> 它满足书中 0,,0(,,0)(,)(0.,)(,,)(,0.)(,.)0l xx yy u u u x y l t u x y x y u y t u l y t u x t u x l t ?=+<<>?? =??====? 的要求，这里1l =。以0t =为初始时刻，分别用ADI,LOD,对称LOD （记为symLOD ）进行算法设计，求在时刻1t =的数值解，并与精确解做比较。 实验过程： 1.t=1时刻原始图像 当x,y 方向上的网格数是160，时间t 方向上的网格数是40时，t=1时刻的原始图像为 2．ADI法恢复的图像 当x,y 方向上的网格数是160，时间t方向上的网格数是40时，ADI法所绘t=1时刻图像为 3．LOD法恢复图像 当x,y 方向上的网格数是160，时间t方向上的网格数是40时，LOD法所绘t=1时刻图像为 4．对称LOD法（记为symLOD）恢复图像 当x,y 方向上的网格数是160，时间t方向上的网格数是40时，symLOD法所绘t=1时刻图像为 5.x,y方向上的网格数和误差关系 t=40固定,x,y方向的的网格数分别取[10,50,100,250,500] 三者的误差的二范数分别为（见error2.m） ADI=[8.730504221745552e-010, 6.029451734592973e-009, 1.265923756496139e-008, 3.206705449439820e-008, 6.425372124435197e-008]; LOD=[8.730504221745788e-010, 6.029451734600921e-009, 1.265923756507861e-008, 3.206705449886893e-008, 6.425372131563230e-008]; SymLOD=[8.730502288715592e-010, 6.029452708815150e-009, 1.265923951388676e-008, 3.206705936704847e-008, 6.425373098974900e-008]; 1. 算法原理 最速下降法的搜索法向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。 已知目标函数在()k X 点的梯度为： ()() () ()()() () ()12 ... T k k k k n f X f X f X f X x x x ?? ???? ??=?????? ? 当求目标函数的最小点时，由于函数沿负梯度方向下降最快，故在()k X 点的探索方向应取该点的负梯度方向，即 ()() ()()() k k k f X S f X ?=- ? 显然，()k S 为单位向量。这样第1k +次迭代计算所得的新点为 () () ()()(1)()()()()() k k k k k k k k f X X X S X f X αα+?=+=- ? 负梯度仅给出了最优化方向，而没有给出步长的大小，所以可能有各种各样的最速下降的过程，它们依赖于 () () () k k f X α?的大小。 步长()k α有两种取法： 一种方法是任意给定一个初始步长，使满足条件： ()()()()()()k k k k f X S f X α+< 另外一种方法是沿负梯度方向做一维探索，以求解一维最优化问题的最优步长α，即对目标函数极小，以得到最优步长： ()()()()()0 min ()()k k k k k f X S f X S ααα>+=+ 以此最优步长作为由() k X 点出发沿该点的负梯度方向探索的步长() k α 。 这种方法的迭代计算的收敛性，可用以下三式中的任一式或二式作为准则来进行判断： ()()()()()1()(1) 2()() (1) 3k k k k k k f X f X f X f X X X εεε--??≤? ?-?≤?? ?-≤?? 2. 算法步骤 用最速下降法求无约束多维极值问题min (),n f x x R ∈的算法步骤如下： （1） 取初始点 (0)x ，精度0ε>，令0k = （2） 计算搜索方向() ()()k k v f x =-?，其中()()k f x ?表示函数()f x 在点()k x 处的梯 度； （3） 若()k v ε≤，则停止计算；否则，从()k x 出发，沿()k v 进行一维搜索，即求k λ， 使得() ()()()0 ()min ()k k k k k f x v f x v λλλ≥+=+。此处的一维搜索可以用黄金分割 法等算法，当然也可以用MATLAB 的min f bnd 函数； （4） 令(1) ()(),1k k k k x x v k k λ+=+=+，转步骤（2）。 3. 算法的MATLAB 实现 在MATLAB 中编程实现的最速下降法函数为：min FD 功能：用最速下降法求解多维函数的极值。 调用格式：[,min ]min (,0,var,)x f FD f x eps = 其中，f ：为目标函数； 0x ：初始点； var ：自变量向量； eps ：精度； x ：目标函数取最小值时的自变量值； min f ：目标函数的最小值。 最速下降法的MATLAB 程序代码如下： 《最优化方法》 课程设计 题目：共轭梯度法算法分析与实现 院系：数学与计算科学学院 专业：数学与应用数学 姓名：梁婷艳 学号：0800730103 指导教师：李丰兵 日期：2015 年12 月30 日 在各种优化算法中，共轭梯度法是非常重要的一种。本文主要介绍的共轭梯度法是介于最速下降法与牛顿法之间的一种无约束优化算法，它具有超线性收敛速度, 而且算法结构简单, 容易编程实现。 在本次实验中,我们首先分析共轭方向法、对该算法进行分析，运用基于共轭方向的一种算法—共轭梯度法进行无约束优化问题的求解。无约束最优化方法的核心问题是选择搜索方向。共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点。根据共轭方向的基本性质，这种方法具有二次终止性。再结合该算法编写matlab程序，求解无约束优化问题，再结合牛顿算法的理论知识，编写matlab程序，求解相同的无约束优化问题，进行比较分析，得出共轭梯度法和牛顿法的不同之处以及共轭梯度法的优缺点。 共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。 关键词：共轭梯度法；超线性收敛；牛顿法；无约束优化 In a variety of optimization algorithms, conjugate gradient method is a very important one.In this paper, the conjugate gradient method is between the steepest descent method and Newton method for unconstrained optimization between a method, it has superlinear convergence rate, and the algorithm is simple and easy programming. In this experiment, we first analyze the conjugate direction method, the algorithm analysis, the use of a conjugate direction-based algorithm - conjugate gradient method for unconstrained optimization problems. Unconstrained optimization method is to select the core issue of the search direction.Conjugate gradient method is the basic idea of the conjugate descent method with the most combined points in the gradient using the known structure of a set of conjugate directions, and search along the direction of this group, find the minimum point of objective function. According to the basic nature of the conjugate direction, this method has the quadratic termination. Combined with the preparation of this algorithm matlab program for solving unconstrained optimization problems, combined with Newton’s theory of knowledge, writing matlab program to solve the same problem of unconstrained optimization, comparison analysis, the conjugate gradient method and Newton method different Office and the advantages and disadvantages of the conjugate gradient method. Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, is not only the conjugate gradient method to solve large linear systems one of the most useful, but also large-scale solution nonlinear optimization algorithm is one of the most effective. Conjugate gradient method is a typical conjugate direction method, each of its search direction is conjugate to each other, and the search direction d is just the negative gradient direction with the last iteration of the search direction of the portfolio, therefore, storage less computational complexity. Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization最优化算法实验3-最速下降法
数值分析与算法变步长梯形求积法计算定积分
最速下降法
用MATLAB实现最速下降法
最速下降法求解这一无约束的最优化问题
二维铸造充型过程数值模拟的特征分数步长法
非线性方程组-最速下降法(梯度法)
最优化牛顿法最速下降法共轭梯度法matlab代码
最速下降法
wolf-powell算法搜索步长
分步步长法和多重网格法_实验
最速下降法
最优化方法课程设计参考模版
相关主题
文本预览