最优化课程设计黄金分割法及其算法实现3

1、机械优化设计报告 姓名： 刘洋 学号： 院系： 机械工程学院 专业： 机械设计及理论 2012年 12月 4日 摘 要最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、同学、政府机关等各个部门及各个领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB软件已经成为最优化领域应用最广的软件之一。有了MATLAB这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相

2、应的最优化计算。关键词：优化、黄金分割法、最速下降法、MATLAB、算法 AbstractOptimization theory and methods and more attention, have penetrated into the production, management, business, military, decision-making and other fields, and optimization models and methods widely used in industry, agriculture, transportation, commerce,

3、defense, construction, students, government various departments and agencies and other fields. With the rapid development of computer technology, optimization theory and methods for the rapid progress of the optimization problem to solve practical software is also developing rapidly. Which, MATLAB s

4、oftware has become the most optimization software is one of the most widely used. With this powerful computing platform MATLAB, either using MATLAB optimization toolbox (OptimizationToolbox) in the function, but also can achieve the appropriate algorithm to optimize into the calculation.Key words: O

5、ptimization、Golden section method、steepest descent method、MATLAB、algorithm 目 录摘要2第一章 绪论5第二章 黄金分割法的基本思想与原理62.1 黄金分割法的基本思路62.2 算法流程图72.3 用matlab编写源程序72.4 黄金分割法应用举例8第三章 最速下降法的基本思想与原理93.1 最速下降法的基本思路93.2 算法流程图113.3 用matlab编写源程序113.4 最速下降法应用举例13第四章 惩罚函数法的基本思想与原理134.1 惩罚函数法的基本思路134.2 算法流程图144.3 用matlab编写源程

6、序14 4.4 最速下降法应用举例16第五章 总结17参考文献18第1章 绪论在人类活动中，要办好一件事（指规划、设计等），都期望得到最满意、最好的结果或效果。为了实现这种期望，必须有好的预测和决策方法。方法对头，事半功倍，反之则事倍功半。优化方法就是各类决策方法中普遍采用的一种方法。 历史上最早记载下来的最优化问题可追溯到古希腊的欧几里得（Euclid，公元前300年左右），他指出：在周长相同的一切矩形中，以正方形的面积为最大。十七、十八世纪微积分的建立给出了求函数极值的一些准则，对最优化的研究提供了某些理论基础。然而，在以后的两个世纪中，最优化技术的进展缓慢，主要考虑了有约束条件的最优化问

7、题，发展了一套变分方法。 六十年代以来，最优化技术进入了蓬勃发展的时期，主要是近代科学技术和生产的迅速发展，提出了许多用经典最优化技术无法解决的最优化问题。为了取得重大的解决与军事效果，又必将解决这些问题，这种客观需要极大地推动了最优化的研究与应用。另一方面，近代科学，特别是数学、力学、技术和计算机科学的发展，以及专业理论、数学规划和计算机的不断发展，为最优化技术提供了有效手段。 现在，最优化技术这门较新的科学分支目前已深入到各个生产与科学领域，例如：化学工程、机械工程、建筑工程、运输工程、生产控制、经济规划和经济管理等，并取得了重大的经济效益与社会效益。机械优化设计是最优化技术在机械设计领域

8、的移植和应用,其基本思想是根据机械设计的理论,方法和标准规范等建立一反映工程设计问题和符合数学规划要求的数学模型,然后采用数学规划方法和计算机计算技术自动找出设计问题的最优方案，求解优化问题可以采用解析法，也可以采用数值法。由于数值法可用于求复杂函数的优化解，也可以用于处理没有数学解析表达式的优化设计问题，因此它是实际问题中常用的解法，很受重视。第2章 黄金分割法的基本思想与原理2.1 黄金分割法的基本原理与步骤一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。该方法用不变的区间缩短率0.618代替斐波

9、那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。黄金分割法是用于一元函数f(x)在给定初始区间a,b内搜索极小点xmin的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间。具体步骤是：在区间a,b内取点：a1 ，a2 把a,b分为三段。 如果f(a1)>f(a2)，令a=a1,a1=a2,a2=a+0.618*(b-a)； 如果f(a

10、1)<f(a2) ，令b=a2，a2=a1,a1=b-0.618*(b-a)；如果(b-a)/b和(y1-y2)/y2都大于收敛精度重新开始循环。因为a,b为单峰区间，这样每次可将搜索区间缩小0.618倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区a,b逐步缩小，直到满足预先给定的精度时，即获得一维优化问题的近似最优解。插入点原理图如下：2.2 算法流程图2.3 用matlab编写源程序编写程序，并且输出每次的搜索区间。则源程序如下：golden程序function x,fval=golden1(f,a,b,eps)k=0;a1=a

11、+0.382*(b-a);%插入点的值a2=a+0.618*(b-a);y1=f(a1);y2=f(a2);while abs(b-a)>=eps%循环条件,eps为收敛精度 if y1>=y2%比较插入点的函数值的大小 a=a1;%缩短搜索区间 a1=a2; y1=y2; a2=a+0.618*(b-a); y2=f(a2); else b=a2; a2=a1; y2=y1; a1=b-0.618*(b-a); y1=f(a1); endk=k+1; end%停止迭代x=(a+b)/2;%取最后两点的平均值作为极小点的数值近似解fval=f(x);fprintf('k=n

12、');%显示迭代次数disp(k); end2.4 黄金分割法应用举例 例1根据0.618算法编写程序，求函数在区间上的极大值。解：程序为：>> z=(t) t2-10*t+36;x,fval=golden(z,0,10,10-6)运行结果：k= 34t = 5.0000fval = 11.0000说明最小值点为，最小值为，迭代次数为34第3章 最速下降法的基本思想与原理3.1 最速下降法基本思路最速下降法的搜索法向是目标函数的负梯度方向，最速下降法从目标函数的负梯度方向一直前进，直到到达目标函数的最低点。已知目标函数在点的梯度为：当求目标函数的最小点时，由于函数沿负梯度方

13、向下降最快，故在点的探索方向应取该点的负梯度方向，即显然，为单位向量。这样第次迭代计算所得的新点为负梯度仅给出了最优化方向，而没有给出步长的大小，所以可能有各种各样的最速下降的过程，它们依赖于的大小。步长有两种取法：一种方法是任意给定一个初始步长，使满足条件：另外一种方法是沿负梯度方向做一维探索，以求解一维最优化问题的最优步长，即对目标函数极小，以得到最优步长：以此最优步长作为由点出发沿该点的负梯度方向探索的步长。这种方法的迭代计算的收敛性，可用以下三式中的任一式或二式作为准则来进行判断：用最速下降法求无约束多维极值问题的算法步骤如下：（1） 取初始点，精度，令（2） 计算搜索方向，其中表示函

14、数在点处的梯度；（3） 若，则停止计算；否则，从出发，沿进行一维搜索，即求，使得。此处的一维搜索可以用黄金分割法等算法，当然也可以用MATLAB的函数；（4） 令，转步骤（2）。3.2 算法流程图3.3 用matlab编写源程序编写程序，并且输出每次的搜索区间。则源程序如下：fsxsteep程序function x=fsxsteep(f,e,a,b)% fsxsteep函数 最速下降法% x=fsxsteep(f,e,a,b)为输入函数 f为函数 e为允许误差 (a,b)为初始点; x1=a;x2=b;Q=fsxhesse(f,x1,x2);x0=x1 x2'fx1=diff(f,&#

15、39;x1'); %对x1求偏导数fx2=diff(f,'x2'); %对x2求偏导数g=fx1 fx2' %梯度g1=subs(g); %把符号变量转为数值d=-g1;while (abs(norm(g1)>=e)t=(-d)'*d/(-d)'*Q*d);t=(-d)'*d/(-d)'*Q*d); %求搜索方向x0=x0-t*g1; %搜索到的点v=x0;a=1 0*x0;b=0 1*x0;x1=a;x2=b;g1=subs(g);d=-g1;end;x=v; function x=fsxhesse(f,a,b)% fsx

16、hesse函数 求函数的hesse矩阵；% 本程序仅是简单的求二次函数的hesse矩阵！；% x=fsxhesse(f)为输入函数 f为二次函数 x1,x2为自变量； x1=a;x2=b;fx=diff(f,'x1'); %求f对x1偏导数fy=diff(f,'x2'); %求f对x2偏导数fxx=diff(fx,'x1'); %求二阶偏导数 对x1再对x1fxy=diff(fx,'x2'); %求二阶偏导数 对x1再对x2fyx=diff(fy,'x1'); %求二阶偏导数 对x2再对x1fyy=diff(fy,

17、'x2'); %求二阶偏导数 对x2再对x2fxx=subs(fxx); %将符号变量转化为数值fxy=subs(fxy);fyx=subs(fyx);fyy=subs(fyy);x=fxx,fxy;fyx,fyy; %求hesse矩阵3.4 最速下降法应用举例 例根据算法编写程序，求函数 在初始点上的极小值。解：程序为：>> syms x1 x2;X=x1,x2;fx=(4*X(1)-5)2+(X(2)-6)2;x=fsxsteep(fx,0.001,8,9)运行结果：x = 5 6第4章 惩罚函数法的基本思想与原理4.1 惩罚函数法基本思路惩罚函数法是应用广泛,

18、非常有效的间接解法，又称为序列无约束极小化方法(SUMT法)。该方法通过将原约束优化问题中的等式和不等式约束函数加权处理后与原目标函数结合,得到新的目标函数(惩罚函数)。原问题转化为新的无约束优化问题,求解该新的无约束优化问题,间接得到原约束优化问题的最优解。程序步骤： 选择适当的初始罚因子、初始点、收敛精度和罚因子系数c。在本程序中分别取令迭代步数k=0。 采用牛顿法求无约束问题的极值点。检验迭代终止准则，若满足 及 则停止迭代计算，输出最优点；否则，转入步骤。取，k=k+1，转入步骤继续迭代。4.2 算法流程图给定、c、k=0i=0求与Hessian矩阵输出和YNi=i+1k=k+1YN结

19、束牛顿法求的极值点4.3 用matlab编写程序clcsyms x1 x2 M; %M为罚因子。m(1)=1;c=8; %c为递增系数。赋初值。a(1)=20;b(1)=20;f=(x1-2)2+(x2-1)2+M*(x12-x2)2+(x1+x2-2)2);%外点罚函数f0(1)=500;%求偏导、Hessian元素fx1=diff(f,'x1');fx2=diff(f,'x2');fx1x1=diff(fx1,'x1');fx1x2=diff(fx1,'x2');fx2x1=diff(fx2,'x1');fx2

20、x2=diff(fx2,'x2');%外点法M迭代循环for k=1:100x1=a(k);x2=b(k);M=m(k);%牛顿法求最优值for n=1:100f1=subs(fx1); %求解梯度值和Hessian矩阵f2=subs(fx2);f11=subs(fx1x1);f12=subs(fx1x2);f21=subs(fx2x1);f22=subs(fx2x2);if(double(sqrt(f12+f22)<=1e-6) %最优值收敛条件a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f);brea

21、k;elseX=x1 x2'-inv(f11 f12;f21 f22)*f1 f2'x1=X(1,1);x2=X(2,1);endendif(double(sqrt(a(k+1)-a(k)2+(b(k+1)-b(k)2)<=1e-6)&&(double(abs(f0(k+1)-f0(k)/f0(k)<=1e-6) %罚因子迭代收敛条件%输出最优点坐标，罚因子迭代次数，最优值a(k+1)b(k+1)kf0(k+1)break;elsem(k+1)=c*m(k);endend4.4 惩罚函数法应用举例 例根据算法编写程序，求函数在初始点上的极小值。解：运行结果：ans = 1.0000ans = 1.0000k = 18ans = 1.0000第五章 总结刚开始觉得学习优化设计有很大的困