.
数学与计算科学学院
实验报告
实验项目名称使用非精确线搜索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 α。
最速下降法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为:"< . 数学与计算科学学院 实验报告 实验项目名称使用精确搜索算法确定步长的最速下降法所属课程名称最优化方法 实验类型算法编程 实验日期 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++ 二、实验内容： 【实验方案】 1. 列举例题 2. 手工计算 3. 将计算步骤等实现程序化 4. 实验结果分析 最速下降法 %% 最速下降法图示 % 设置步长为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); ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2006年第46卷第10期 2006,V o l.46,N o.1021/40 1719-1722 基于自适应步长的直线生成算法 黄斌茂, 张 利 (清华大学电子工程系,北京100084) 收稿日期:2005-07-13 基金项目:国家自然科学基金资助项目(60172027)作者简介:黄斌茂(1981-),男(汉),江西,硕士研究生。通讯联系人:张利,副教授, E-mail:chin azh angli@mail.tsingh https://www.doczj.com/doc/b09658024.html, 摘 要:为了改进计算机图形学中画线算法的效率,提出一种基于自适应步长的直线生成算法和一种集成了对称性、最大公约数和自适应步长的集成算法。由于直线仅包含一种或两种与斜率有关的像素模式,算法利用这一特性,自适应地采用最佳步长,在单次判决中生成多个像素。通过综合使用直线像素的中点对称性、最大公约数性质以及像素模式的有限性等3种相互独立的特性,集成算法在单次判决中可生成更多像素。算法的仿真结果表明:新算法生成直线的效率更高、速度更快。 关键词:Bresenham 算法;自适应步长;对称性;最大公约 数;像素模式 中图分类号:T P 391.4文献标识码:A 文章编号:1000-0054(2006)10-1719-04 Self -adaptive step straight -line algorithms HUA NG Binmao ,ZH ANG Li (Department of Electronic Engineering , T s inghua University ,Beij ing 100084,China ) Abstract :Line draw ing algorithm in computer grap hics sys tems is improved w ith a self-adaptive s tep straight-line algor ith m and an oth er integrated algorithm th at combines self-adaptive step algorithm w ith th e s ymmetr y an d greatest com mon divisor (GCD)-based algor ith ms.Th e self-adaptive step algorithm uses the limited pixel patter ns inherent in line s egments to adaptively determine the best step that corres ponds to the line slope an d then gen erates m ulti-pixels in each judgemen t.T he integrated algorithm utilizes the sym metry,GCD,an d limited pixel patterns and gen erates more p ixels in each https://www.doczj.com/doc/b09658024.html,parisons w ith Bresen ham 's algorithm sh ow th at the integrated algorithms are m ore effective and efficient. Key words :Bresen ham's algorithm ;self-adaptive steps;s ymmetr y; greatest common divisor (GCD);pixel patter n 直线段(简称直线)是图形的基本单元,图形渲染的速度很大程度上取决于直线的生成速度。 Br esenham 算法[1] 是目前使用最为广泛的直线生成算法,它采用整数加减运算,避免了浮点数操作和乘除运算,从而极大地提高了算法的效率。在该算法的 基础上,研究界提出了多种改进算法。其改进思路可分为两类:1)将直线分割成多条短线段,采用并行算法生成直线[2] ;2)通过一次误差判别操作,在一次循环中生成多个像素[312]。 直线上的像素点关于直线中点对称,文[5]利用这一特性,每个循环生成两个像素点。 对端点为S (x s ,y s )及E (x e ,y e )的直线,当 x e -x s 和 y e -y s 的最大公约数r 不为1时,直线上有r 段像素模式相同的线段。文[4]通过在每个循环内生成r 个像素,加速了直线的生成。但当r =1时,该算法比Brensenham 算法效率要低。文[68]采用N 步长(N ≥2)直线生成方法,将八分圆分成多个子区,每个子区有N +1种像素模式,根据直线的斜率可决定其子区归属。该算法每个循环可生成N 个像素。其不足是:每个子区中的N +1种像素模式的初始化开销很大;步长固定,不能采用最佳步长。还有一些研究者结合对称性、多步长、最大公约数提出集成算法[9]。 文[10]简要地提出自适应步长的思想,但未给出推导证明与具体算法;文[11,12]在直线斜率为0< m <0.5时,一次生成多个像素以提高直线的生成效率,但没有注意到直线像素模式关于m =±0.5的对称性。此外,文[11,12]都没有给出算法的仿真结果。 上述各种改进算法的共同点是在每个循环中生成多个像素,但每次生成的像素个数固定,不能自适应地采用最合适的步长。本文利用直线在八分圆中像素模式的对称性,以及任一直线只有一种或者两种与斜率相关的像素模式这一特性,提出一种基于 实验的题目和要求 一、所属课程名称： 最优化方法 二、实验日期: 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) 梯度法（又名,最速下降法） (该法总可以收敛，但是，在接近真解时收敛的速度会放慢。) 梯度法又称为最速下降法，用于求解实系数非线性方程组 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' Richardson 外推加速法在数值微分与积分 中的应用 信息与计算科学专业学生：XX 指导老师：XX [摘要]：本文介绍了数值微分与数值积分的Richardson 外推加速算法，基于Euler-Maclaurin 公式给出了算法的推导过程，再根据Richardson 外推方法推导出了收敛更快的数值微分与积分公式，经数值实验验证该公式有良好的计算效果. 关键词：Richardson 外推法，Romberg 算法,Euler-Maclaurin 公式 Abstract: the paper gives a introduction of Richardson ’s Extrapolation Method, then, listing the derivation and proof of Richardson ’s Extrapolation depending on Euler-Maclaurin. According to the Richardson ’s Extrapolaton,this paper got the faster numerical differentiation and integral formula.The formula is prove to be efficient by numerical experiment. Keyword: Richardson’s Extrapolation, Romberg’s Algoritm, Euler-Maclaurin Algoritm 0 引言： Richardson 外推法用以低阶公式产生高精度收敛效果进而改善序列收敛效率，它是 在20世纪前期由英国数学家，物理学家，气象学家Lewis Fry Richardson 提出的.在数值分析领域，Richardson 外推法有很多实际应用，如隆贝格积分方法，是在梯形公式的基础上应用Richardson 外推法导出的；还有用于求解常微分方程的Bulirsch –Stoer 算法. 1 Richardson 外推加速算法 1.1 Richardson 外推加速算法 李查逊外推加速法基于如下原理 定理 设: ()[]b a C x f ,∞∈ ，则成立 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使用精确搜索算法确定步长的最速下降法
最速下降法
基于自适应步长的直线生成算法
用MATLAB实现最速下降法
最速下降法求解这一无约束的最优化问题
非线性方程组-最速下降法(梯度法)
最优化牛顿法最速下降法共轭梯度法matlab代码
最速下降法
wolf-powell算法搜索步长
【精品】Richardson外推加速算法在数值分析公式中的应用
最速下降法
最优化方法课程设计参考模版
相关主题
文本预览