MATLAB黄金分割法课程论文--
中南林业科技大学
本科课程论文
学院：理学院
专业年级：14级信息与计算科学2班
学生姓名：邱文林学号：20144349
课程：MATLAB程序设计教程
设计题目：基于MATLAB的黄金分割法与抛物线插值法指导教师：龚志伟
2016年4月
中文摘要
为了求解最优化模型的最优解，可使用基于MATLAB算法编程的黄金分割法与抛物线插值法，来实现求解的过程。黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点，利用迭代进而得出结论。抛物线插值法亦称二次插值法，是一种多项式插值法，逐次以拟合的二次曲线的极小点，逼近原寻求函数极小点的一种方法。通过将MATLAB与最优化问题相结合，不仅可以加深对黄金分割法、抛物线插值法的基本理解和算法框图及其步骤的全面理解，也有利于帮助我们掌握MATLAB的使用方法。
关键词：MATLAB，黄金分割法，抛物线插值法，最优解，迭代
英文摘要
In order to solve the optimization model of the optimal solution, using MATLAB algorithm based on the golden section method and the parabola interpolation method, to realize the process of solving. The golden section method is used to search the most advantage through the function value of the selected pilot, which can be used to search for the most advantage. Parabolic interpolation method, also known as the two interpolation method, is a polynomial interpolation method, successive to fit the two curve of the minimum point, the original search function to find a very small point of the method. By combining MATLAB and optimization problems can not only deepen the comprehensive understanding of the golden section method, the parabola interpolation basic understanding and block diagram of the algorithm and steps, but also conducive to help us to grasp the method of using MATLAB.
Key words: MATLAB, golden section method, parabolic interpolation method, optimal solution, iteration
目录
1. 黄金分割法?????????????????????????????????????????????????????????????????2
1.1 算法原理??????????????????????????????????????????????????????2
1.2 算法步骤??????????????????????????????????????????????????????2
1.3黄金分割法算法框图???????????????????????????????????????3
2. 抛物线插值法??????????????????????????????????????????????????????4
2.1 算法原理??????????????????????????????????????????????????????4
2.2 算法步骤??????????????????????????????????????????????????????4
2.3 抛物线插值法算法框图?????????????????????????????????????5
3. 算法的MATLAB实现???????????????????????????????????????????????6
3.1黄金分割法程序代码??????????????????????????????????????????????6
3.2 实例验证??????????????????????????????????????????????????????6
3.3 误差分析??????????????????????????????????????????????????????9
3.4 抛物线插值法程序代码?????????????????????????????????????10
3.5 实例验证??????????????????????????????????????????????????????11
3.6 误差分析??????????????????????????????????????????????????????12
3.7黄金分割法与抛物线插值法的对比?????????????????????????13 参考文献??????????????????????????????????????????????????????????????????????????15
引言
为了对最优化问题进行求解，为了更好的掌握MATLAB的运用，本文主要介绍一维最优化问题的一维搜索法黄金分割法与抛物线插值法，利用MATLAB算法将其实现。黄金分割法也叫0.618法，它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体是哪个点，无法得知。黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。抛物线插值法(parabolic interpolation met-hod)亦称二次插值法一种多项式插值法.逐次以拟合的二次曲线的极小点，逼近原寻求函数极小点的一种方法,能求得精度较高的解，但速度会比较慢。时至今日，经过Math Works公司的不断完善，MATLAB已经发展成为适合多学科、多种工作平台的功能强劲的大型软件。在国外，MATLAB已经经受了多年考验。在欧美等高校，MATLAB已经成为线性代数、自动控制理论、数理统计、数字信号处理、时间序列分析、动态系统仿真等高级课程的基本教学工具；成为攻读学位的大学生、硕士生、博士生必须掌握的基本技能。在设计研究单位和工业部门，MATLAB 被广泛用于科学研究和解决各种具体问题。
1. 黄金分割法
1.1 算法原理
黄金分割法的基本原理：
黄金分割法又称0.618法，它是通过不断缩短搜索区间的长度来寻求一维函数的极小点。这种方法的原理是：在搜索区间[a, b]内按如下规则对称地取两点：
计算它们的函数值f1=f(a1), f2=f(a2) ,比较它们的大小，结果有两种可能：
1.2 算法步骤
（1）f1>f2,如图1所示，极小点必在[a1, b]内，消去区间[a, a1), 令a=a1，产生新区间[a, b],到此区间缩短了一次。值得注意的是新区间的a1点与原区间的a2点重合，可令a1=a2,这样可少找一个新点和节省一次函数值计算。
（2）f1<=f2,极小点必在[a, a2]内，消去区间 (a2,b],令b=a2,产生新区间[a ,b],到此区间缩短了一次。同样新区间a2点与原区间的a1点重合，可令a2=a1,f2<=f1。（3）当缩短的新区间长度小于等于某一精度ε，即b-a<=ε时，取a* =(a1+a2)/2。
1.3黄金分割法算法框图
2. 抛物线插值法 2.1 算法原理:
抛物线也叫二次插值法，其理论依据为二次多项式可以在最优点附近较好的逼近函数的形状，做法是在函数f(x)的最优点附近取三个构造点，然后用这三个点构造一条抛物线，把这条抛物线的极值点作为函数f(x)的极值点的近似。
每次构造一条抛物线后，抛物线的极值点就可作为一个新的构造点，新的构造点与原来的三个构造点经过某种算法，得到下一步抛物线逼近的三个构造点，这就是抛物线法的算法过程。
2.2 算法步骤：
用抛物线求无约束问题minf(x),x ∈R 的算法步骤如下：
① 确定初始区间[a,b],选定初始插值内点t 0∈(a,b)及精度e>0,令a 0=a,b 0=b,k=0; ② 求二次插值多项式的极小点：
t k+1=
)
)(())(())(())(())(())((212
22222k k k k k k k k k k k k k k k k k k b a t f a t b f t b a f b a t f a t b f t b a f -+-+--+-+-. (2.10)
③ 若f(t k+1) ≤f(t k ),则当|t k+1 -t k |≤e 时，停止迭代输出t k+1;否则转④; ④ 若f(t k+1) ＞f(t k ),则当|t k+1 -t k |≤e 时，停止迭代输出t k ;否则转⑤; ⑤ 若t k+1 ≤ t k ,令
a k+1=a k ,
b k+1=t k ,t k+1=t k+1; 置k=k+1转②,否则令
a k+1=t k ,
b k+1=b k ,t k+1=t k+1;
置k=k+1转②。
⑥ 若t k+1 ≤ t k ,令
a k+1=t k+1,
b k+1=t k ,t k+1=t k ;
置k=k+1转②,否则令
a k+1=a k ,
b k+1=t k+1,t k+1=t k ;
置k=k+1转②。
初始插值内点可以取搜索区间[a, b]的中点。
2.3抛物线插值法算法框图
3. 算法的MATLAB实现
3.1 黄金分割法程序代码
在MATLAB中编程实现的黄金分割法函数为: golden。
功能：用黄金分割法求解一维函数的极值。
调用格式：tmin=golden(f,a,b,e)
其中， f=目标函数；
a=极值区间左端点；
b=极值区间右端点；
e=精度；
tmin=目标取最小值时的自变量值；
黄金分割法的MATLAB程序代码如下：
主程序：
syms t a b e ;
a=input('搜索区间第一点 \a=');
b=input('搜索区间第二点 \b=');
e=input('搜索精度\ne=');
disp('需求的最优化函数 f=f(t),tmin=golden(f,a,b,e)');
m文件：
function tmin=golden(f,a,b,e)
format long;
k=0;
a1=b-0.618*(b-a);
a2=a+0.618*(b-a);
while b-a>e
y1=subs(f,a1);
y2=subs(f,a2);
if y1>y2
a=a1;
a1=a2;
y1=y2;
a2=a+0.618*(b-a);
else
b=a2;
a2=a1;
y2=y1;
a1=b-0.618*(b-a);
end
k=k+1;
end
tmin=(a+b)/2;
fmin=subs(f,tmin)
fprintf('k=\n');
disp(k);
x=-3:0.001:5;
y=x.*(x+2);
plot(x,y,'k-',tmin,fmin,'bp');
3.2 实例验证
minf(t)=t*(t+2), 已知初始单谷区间[a,b]=[-3,5],按精度e=0.001计算。
代入到主程序代码：
搜索区间的第一点 a=-3
搜索区间的第二点 b=5
搜索精度
e=0.001
需求的最优化函数 f=f(t),tmin=golden(f,a,b,e)
>> f=t*(t+2)
f =
t*(t + 2)
>> tmin=golden(f,a,b,e)
k=
19
tmin =
-1.000120312207862
>> fmin=tmin*(tmin+2)
fmin =
-0.999999985524973
目标函数的曲线图如图1-1所示:
注：图中☆所标识的点为黄金分割法所求的极小点。
图1-1 函数f(t)=t(t+2)的曲线图
3.3 误差分析:
1. f(t)=t*(t+2) 的精确解如下：
f=[1,2,0];
p=polyder(f);
t1=roots(p)
f1=polyval(f,t1)
t1 =
-1
f1 =
-1
极小点误差： e1=(tmin-t1)/t1=(-1.000120312207862-(-1))/(-1)≈ 1e-4
极小值误差： e2=(f1-fmin)/f1=( -1 +0.999999985524973)/(-1) ≈ 1e-8
结论：在精度e=0.001的情况下，通过黄金分割法经过19次迭代，求得：
tmin=-1.000120312207862,与精确值的误差e1=1e-4 3.4 抛物线插值法程序代码 在MATLAB中编程实现的抛物线法函数为: minPWX。 功能：用抛物线插值法求解一维函数的极值。 调用格式：[x,minf]=minPWX(f,a,b,e) 其中， f:目标函数； A:初始搜索区间左端点； b:初始搜索区间右端点； e:精度； x:目标取最小值时的自变量值； minf:目标函数的最小值。 抛物线法的MATLAB程序代码如下： function [x,minf]=minPWX(f,a,b,e) %目标函数：f; %初始搜索区间左端点：a; %初始搜索区间右端点：b; %精度：e; %目标函数取最小值时的自变量值: x; %目标函数的最小值: minf format long; if nargin == 3 e=1.0e-3; end t0=(a+b)/2; k=0; tol=1; while tol>e fa=subs(f,findsym(f),a); %区间左端点函数值 fb=subs(f,findsym(f),b); %区间右端点函数值 ft0=subs(f,findsym(f),t0); %内插点函数值 tu=fa*(b^2-t0^2)+fb*(t0^2-a^2)+ft0*(a^2-b^2); td=fa*(b-t0)+fb*(t0-a)+ft0*(a-b); t1=tu/2/td; %插值多项式的极小点 ft1=subs(f,findsym(f),t1); %插值多项式的极小值 tol=abs(t1-t0); if ft1<=ft0 if t1<=t0 b=t0; t0=t1; else a=t0; t0=t1; end k=k+1; else if t1<=t0 a=t1; else b=t1; end k=k+1; end end x = t1; minf= subs(f,findsym(f),x); format short; 3.5 实例验证 用抛物线法求函数f(t)=t*(t+2)，已知初始单谷区间[a,b]=[-3,5],按精度e=0.001计算。 解：在MATLAb 命令窗口中输入： >> syms t; >> f=t*(t+2); >> [tmin,fmin]=minPWX(f,-3,5) tmin = -1 fmin = -1 目标函数的曲线图如图1-2所示: 注：图中O所标识的点为抛物线插值法所求的极小点。 图1-2 函数f(t)=t(t+2)的曲线图 3.6 误差分析: 1. f(t)=t*(t+2) 的精确解如下： f=[1,2,0]; p=polyder(f); t1=roots(p) f1=polyval(f,t1) t1 = -1 f1 = -1 极小点误差： e3=(tmin-t1)/t1=（-1-(-1)）/(-1)=0 极小值误差： e4=（fmin-f1）/f1=0 3.7 黄金分割法与抛物线插值法的对比 注：下图中红色☆是黄金分割法的极小点标识位置，蓝色O是抛物线插值法的极小点标识位置。 图1-3 函数f(t)=t(t+2)的曲线图 对比结论： 由图分析： 精度e=0.001 的情况下，如上图1-3所示，黄金分割法与抛物线插值法求出的极小点都极为接近精确值。 由误差分析： 黄金分割法极小点误差： e1=(tmin-t1)/t1=(-1.000120312207862-(-1))/(-1)≈ 1e-4 抛物线插值法极小点误差： e3=(tmin-t1)/t1=（-1-(-1)）/(-1)=0 可见，在满足同精度的情况下，抛物线插值法能求出精度更高的解，但是速度会比较慢。黄金分割法的优点是可以用来迅速缩小极值区间，而抛物线法可以提高解的精度。若将两者综合，用黄金分割法求一个比较小的极值区间，再用抛物线插值法提高精度，这样既满足了精度，又提高了效率，这样的方法会更好。 参考文献： [1] 郭科，陈聆，魏友华.最优化方法及其运用. [2] 刘卫国，MATLAB程序设计教程（第二版）. [3] 龚纯，王正林，精通MATLAB最优化计算(第2版). 用二 4224min ()f t t t t =--[,.]t ∈内的极小值点，要求准 1. function [t d]=erfenfa(a,b) k=1; %记录循环次数 while abs(a-b)>0.0005 c=(a+b)/2; C(k)=c; %存储每次循环中点c 的值 if ff(c)<0 a=c; end if ff(c)==0 t1=c; break ; end if ff(c)>0 b=c; end k=k+1; end t=(a+b)/2; %最终符合要求的值 d=f(t); %最优解 C k function y=f(t) y=t^4-2*t^2-4*t; function y=ff(t) y=4*t^3-4*t-4; 运行结果 >> [t d]=erfenfa(1,1.5) C = Columns 1 through 9 1.2500 1.3750 1.3125 1.3438 1.3281 1.3203 1.3242 1.3262 1.3252 Column 10 1.3247 k = 11 t = 1.3250 d = -5.7290 2.黄金分割法 f (x)=x3-2x+1 初始区间[0, 3]，收敛精度0.5 function [t,f]=huangjinfenge(a,b) m=1-(sqrt(5)-1)/2; t2=a+m*(b-a) f2=g(t2); t1=a+b-t2 f1=g(t1); while abs(t1-t2)>0.5 if f1 实验报告 实验题目: 0.618法的MATLAB实现学生姓名: 学号: 实验时间: 2013-5-13 一．实验名称: 0.618法求解单峰函数极小点 二．实验目的及要求: 1. 了解并熟悉0.618法的方法原理, 以及它的MATLAB 实现. 2. 运用0.618法解单峰函数的极小点. 三．实验内容： 1. 0.618法方法原理: 定理: 设f 是区间],[b a 上的单峰函数, ] ,[ ,)2()1(b a x x ∈, 且)2()1(x x <. 如果)()()2()1(x f x f >, 则对每一个],[)1(x a x ∈, 有)()()2(x f x f >; 如果)()()2()1(x f x f ≤, 则对每一个] ,[) 2(b x x ∈, 有)()()1(x f x f ≥. 根据上述定理, 只需选择两个试探点, 就可将包含极小点的区间缩短. 事实上, 必有 如果)()()2()1(x f x f >, 则],[)1(b x x ∈; 如果)()() 2()1(x f x f ≤, 则][)2(x a x ，∈. 0.618 法的基本思想是, 根据上述定理, 通过取试探点使包含极小点的区间(不确定区间)不断缩短, 当区间长度小到一定程度时, 区间上各点的函数值均接近极小值, 因此任意一点都可作为极小点的近似. 0.618 法计算试探点的公式: ). (618.0),(382.0k k k k k k k k a b a a b a -+=-+=μλ 2. 0.618法的算法步骤: ①置初始区间],[11b a 及精度要求0>L , 计算试探点1λ和1μ, 计算函数值)(1λf 和)(1μf . 计算公式是 ).(618.0 ),(382.011111111a b a a b a -+=-+=μλ 令1=k . ②若L a b k k <-, 则停止计算. 否则, 当)()(k k f f μλ>时, 转步骤③; 当)()(k k f f μλ≤时, 转步骤④. ③置k k a λ=+1, k k b b =+1, k k μλ=+1,)(618.01111++++-+=k k k k a b a μ, 计算函数值)(1+k f μ, 转步骤⑤. 《现代设计方法》课程 关于黄金分割法和二次插值法的Matlab语言实现在《现代设计方法》的第二章优化设计方法中有关一维搜索的最优化方法的 一节里，我们学习了黄金非分割法和二次插值法。它们都是建立在搜索区间的优先确定基础上实现的。 为了便于方便执行和比较，我将两种方法都写进了一个程序之内，以选择的方式实现执行其中一个。下面以《现代设计方法》课后习题为例。见课本70页，第2—7题。原题如下： 求函数f(x)=3*x^2+6*x+4的最优点，已知单谷区间为[-3,4],一维搜索精度为0.4。 1、先建立函数f(x),f(x)=3*x^2+6*x+4。函数文件保存为：lee.m 源代码为：function y=lee(x) y=3*x^2+6*x+4; 2、程序主代码如下，该函数文件保存为：ll.m clear; a=input('请输入初始点'); b=input('请输入初始步长'); Y1=lee(a);Y2=lee(a+b); if Y1>Y2 %Y1>Y2的情况 k=2; Y3=lee(a+2*b); while Y2>=Y3 %直到满足“大，小，大”为止 k=k+1; Y3=lee(a+k*b); end A=a+b;B=a+k*b; elseif Y1 #include"stdio.h" #include"stdlib.h" #include"math.h" double objf(double x[]) {double ff; ff=x[0]*x[0]+x[1]*x[1]-x[0]*x[1]-10*x[0]-4*x[1]+60; return(ff); } double gold(double a[],double b[],double eps,int n,double xx[]) {int i; double f1,f2,*x[2],ff,q,w; for(i=0;i<2;i++) x[i]=(double*)malloc(n*sizeof(double)); for(i=0;i 1黄金分割法的优化问题 （1）黄金分割法基本思路： 黄金分割法适用于[a，b]区间上的任何单股函数求极小值问题，对函数除要求“单谷”外不做其他要求，甚至可以不连续。因此，这种方法的适应面非常广。黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间[a，b]内适当插入两点a1，a2，并计算其函数值。a1，a2将区间分成三段，应用函数的单谷性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。 （2）黄金分割法的基本原理 一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。 黄金分割法是用于一元函数f(x)在给定初始区间[a,b]内搜索极小点α*的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数[6]，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间[7]。具体步骤是：在区间[a,b]内取点：a1 ，a2 把[a,b]分为三段。如果f(a1)>f(a2)，令 a=a1,a1=a2,a2=a+r*(b-a)；如果f(a1) 题目和要求 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻 两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f 在迭代点k x 处的Taylor 展开式作为模型函数，并利用这个二次模型函数的极小 点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向k d 仅仅是负梯度方向k g -与上一次接待 的搜索方向1-k d 的组合。 运行及结果如下: 最速下降法： 题目：f=(x-2)^2+(y-4)^2 M 文件： function [R,n]=steel(x0,y0,eps) syms x ; syms y ; f=(x-2)^2+(y-4)^2; v=[x,y]; j=jacobian(f,v); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=0; syms kk ; while (temp>eps) d=-T; f1=x1+kk*d(1);f2=y1+kk*d(2); fT=[subs(j(1),x,f1),subs(j(2),y,f2)]; fun=sqrt((fT(1))^2+(fT(2))^2); Mini=Gold(fun,0,1,0.00001); x0=x1+Mini*d(1);y0=y1+Mini*d(2); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=n+1; end R=[x0,y0] 调用黄金分割法： M文件： function Mini=Gold(f,a0,b0,eps) syms x;format long; syms kk; u=a0+0.382*(b0-a0); v=a0+0.618*(b0-a0); k=0; a=a0;b=b0; array(k+1,1)=a;array(k+1,2)=b; while((b-a)/(b0-a0)>=eps) Fu=subs(f,kk,u); Fv=subs(f,kk,v); if(Fu<=Fv) b=v; v=u; u=a+0.382*(b-a); k=k+1; elseif(Fu>Fv) a=u; u=v; v=a+0.618*(b-a); k=k+1; end array(k+1,1)=a;array(k+1,2)=b; end Mini=(a+b)/2; 输入： [R,n]=steel(0,1,0.0001) R = 1.99999413667642 3.99999120501463 R = 1.99999413667642 3.99999120501463 n = 1 牛顿法： 题目：f=(x-2)^2+(y-4)^2 M文件： 1黄金分割法的优化问题（1）黄金分割法基本思路： 黄金分割法适用于[a，b]区间上的任何单股函数求极小值问题，对函数除要求“单谷”外不做其他要求，甚至可以不连续。因此，这种方法的适应面非常广。黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间[a，b]内适当插入两点a1，a2，并计算其函数值。a1，a2将区间分成三段，应用函数的单谷性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。 （2）黄金分割法的基本原理 一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（法）。该方法用不变的区间缩短率代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。 黄金分割法是用于一元函数f(x)在给定初始区间[a,b]内搜索极小点α*的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而着称，是许多优化算法的基础，但它只适用于一维区间上的凸函数[6]，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间[7]。具体步骤是：在区间[a,b]内取点：a1 ，a2 把[a,b]分为三段。如果 f(a1)>f(a2)，令a=a1,a1=a2,a2=a+r*(b-a)；如果f(a1) 黄金分割法-进退法-原理及流程图 1黄金分割法的优化问题 （1）黄金分割法基本思路： 黄金分割法适用于[a，b]区间上的任何单股函数求极小值问题，对函数除要求“单谷”外不做其他要求，甚至可以不连续。因此，这种方法的适应面非常广。黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间[a，b]内适当插入两点a1，a2，并计算其函数值。a1，a2将区间分成三段，应用函数的单谷性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。 （2）黄金分割法的基本原理 一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。 黄金分割法是用于一元函数f(x)在给定初始区间[a,b]内搜索极小点α*的一种方法。它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数[6]，即只在单峰区间内才能进行一维寻优，其收敛效率较低。其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间[7]。具体步骤是：在区间[a,b]内取点：a1 ，a2 把[a,b]分为三段。如果f(a1)>f(a2)，令 a=a1,a1=a2,a2=a+r*(b-a)；如果f(a1) revisenewton.m syms x1 x2 x3 xx; % f = x1*x1 +x2*x2 -x1*x2 -10*x1 -4*x2 + 60 ; % f = x1^2 + 2*x2^2 - 2*x1 *x2 -4*x1 ; f = 100 * (x1^2 - x2^2) + (x1 -1 )^2 ; hessen = jacobian(jacobian(f , [x1,x2]),[x1,x2]) ; gradd = jacobian(f , [x1,x2]) ; X0 = [0,0]' ; B = gradd' ; x1 = X0(1); x2 = X0(2); A = eval(gradd) ; % while sqrt( A(1)^2 + A(2)^2) >0.1 i=0; while norm(A) >0.1 i = i+1 ; fprintf('the number of iterations is: %d\n', i) if i>10 break; end B1 = inv(hessen)* B ; B2= eval(B1); % X1 = X0 - B2 % X0 = X1 ; f1= x1 + xx * B2(1); f2= x2 + xx* B2(2); % ff = norm(BB) ? syms x1 x2 ; fT=[subs(gradd(1),x1,f1),subs(gradd(2),x2,f2)]; ff = sqrt((fT(1))^2+(fT(2))^2); MinData = GoldData(ff,0,1,0.01); x1 = X0(1); x2 = X0(2); x1 = x1 + MinData * B2(1) x2 = x2 + MinData * B2(2) A = eval(gradd) End GoldData.m function MiniData = GoldData( f,x0,h0,eps) syms xx; 实验的题目和要求 一、所属课程名称： 最优化方法 二、实验日期: 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)）^２）; 中南林业科技大学 本科课程论文 学院：理学院 专业年级：14级信息与计算科学2班 学生姓名：邱文林学号：20144349 课程：MATLAB程序设计教程 设计题目：基于MATLAB的黄金分割法与抛物线插值法指导教师：龚志伟 2016年4月 中文摘要 为了求解最优化模型的最优解，可使用基于MATLAB算法编程的黄金分割法与抛物线插值法，来实现求解的过程。黄金分割法是通过所选试点的函数值而逐步缩短单谷区间来搜索最优点，利用迭代进而得出结论。抛物线插值法亦称二次插值法，是一种多项式插值法，逐次以拟合的二次曲线的极小点，逼近原寻求函数极小点的一种方法。通过将MATLAB与最优化问题相结合，不仅可以加深对黄金分割法、抛物线插值法的基本理解和算法框图及其步骤的全面理解，也有利于帮助我们掌握MATLAB的使用方法。 关键词：MATLAB，黄金分割法，抛物线插值法，最优解，迭代 英文摘要 In order to solve the optimization model of the optimal solution, using MATLAB algorithm based on the golden section method and the parabola interpolation method, to realize the process of solving. The golden section method is used to search the most advantage through the function value of the selected pilot, which can be used to search for the most advantage. Parabolic interpolation method, also known as the two interpolation method, is a polynomial interpolation method, successive to fit the two curve of the minimum point, the original search function to find a very small point of the method. By combining MATLAB and optimization problems can not only deepen the comprehensive understanding of the golden section method, the parabola interpolation basic understanding and block diagram of the algorithm and steps, but also conducive to help us to grasp the method of using MATLAB. Key words: MATLAB, golden section method, parabolic interpolation method, optimal solution, iteration 牛顿法 迭代公式：(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 ) 线性搜索之黄金分割法及其应用 摘要 最优化理论和方法日益受到重视，已经渗透到生产、管理、商业、军事、决策等各个领域，而最优化模型与方法广泛应用于工业、农业、交通运输、商业、国防、建筑、通讯和政府机关等领域。伴随着计算机技术的高速发展，最优化理论与方法的迅速进步为解决实际最优化问题的软件也在飞速发展。其中，MATLAB 软件已经成为最优化领域应用最广的软件之一。有了MATLAB这个强大的计算平台，既可以利用MATLAB优化工具箱（OptimizationToolbox）中的函数，又可以通过算法变成实现相应的最优化计算。 在最优化计算中一维最优化方法是优化设计中最简单、最基本的方法。一维搜索，又称为线性搜索，一维问题是多维问题的基础，在数值方法迭代计算过程中，都要进行一维搜索，也可以把多维问题化为一些一维问题来处理。一维问题的算法好坏，直接影响到最优化问题的求解速度。而黄金分割法是一维搜索方法中重要的方法之一，它适用于任何单峰函数求最小值的问题，甚至于对函数可以不要求连续，是一种基于区间收缩的极小点搜索算法。 关键词：最优化、黄金分割法、MATLAB软件、一维搜索 引言 数学科学不仅是自然科学的基础，也是一切重要技术发展的基础。最优化方法更是数学科学里面的一个巨大的篇幅，在这个信息化的时代，最优化方法广泛应用于工业、农业、国防、建筑、通信与政府机关、管理等各领域；它主要解决最优计划、最优分配、最优决策、最佳设计、最佳管理等最优化问题。而最优解问题是这些所有问题的中心，是最优化方法的重中之重，在求最优解问题中，有多种方法解决，我们在这里着重讨论无约束一维极值问题，即非线性规划的一维搜索方法之黄金分割法。黄金分割法也叫0.618法，属于区间收缩法，首先找出包含极小点的初始搜索区间，然后按黄金分割点通过对函数值的比较不断缩小搜索区间。当然要保证极小点始终在搜索区间内，当区间长度小到精度范围之内时，可以粗略地认为区间端点的平均值即为极小值的近似值。所以用0.618法得出的 1 黄金分割法求解的最小值，区间[-10，10]，精度：0.001 c程序： #include"stdio.h" #include"math.h" double eq(double x) {double y; y =8.0*x * x * x - 2.0 * x * x -7.0 * x + 3.0; return y; } void main() { double a1,a2,a3,a4,f2,f3,x; a1 =-10.0; // 左边界 a4 = 10.0; // 右边界 Lab1: a3 = a1 + 0.618 * (a4 - a1); f3 = eq(a3); Lab2: a2 = a1 + 0.382 * (a4 - a1); f2 = eq(a2); Lab3: if (fabs(a4-a1) < 0.001) { x = (a1 + a4) / 2.0; printf("x=%g fmin=%e \n",x,eq(x)); } else { if (f2 < f3) {a4=a3; a3 = a2; f3 = f2; goto Lab2;}; if (f2 == f3) {a1=a2; a4=a3; goto Lab1;}; if (f2 > f3) {a1=a2; a2=a3; f2=f3; a3 = a1 + 0.618*(a4-a1); f3=eq(a3); goto Lab3;}; }; } 运行结果： 2 黄金分割法求解的最小值，区间[-10，10]，精度：0.001 Matlab程序： ●建立M文件：func.m function f=func(x) f = 8.0*x * x * x - 2.0 * x * x -7.0 * x + 3.0 ●命令窗口： a1 = -10 ; %左边界 a4 = 10 ; %右边界 e = 0.001 ; %精度 r = ( sqrt (5) -1 ) / 2 ; %即0.618 a2 = a1 + (1-r) * (a4 - a1) ; a3 = a1 + r* (a4 - a1) ; f2 = func (a2) ; f3 = func (a3) ; k = 1 ; while ( abs (a4 - a1 ) >= e ) if f2 < f3 ; a4 = a3 ; 黄金分割法 东南大学机械学院** 一黄金分割法基本思路 黄金分割法适用于[a，b]区间上的任何单谷函数求极小值问题，对函数除要求“单谷”外不做其他要求，甚至可以不连续。因此，这种方法的适应面非常广。 黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间[a，b]内适当插入两点a1，a2，并计算其函数值。a1，a2将区间分成三段，应用函数的单谷性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。 二黄金分割法的基本原理 一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。 黄金分割法是用于一元函数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(a1) 黄金分割法求极小的MATLAB程序 function [x,y] = goldmin(f, a ,b ,tol, maxsearch) if nargin<5, maxsearch=500; end if nargin<4, tol=1e-6; end; golden=0.6180339887498949025257; % golden=(sqrt(5)-1)/2 x=b-(b-a)*golden; % x是离端点a较近的试探点 y=feval(f,x); % 求x的函数值y for k=1:maxsearch % 作最大叠代次数为maxsearch的循环。 h=b-a; % h是区间长（当b 用黄金分割法求极小点程序 用黄金分割法求目标函数82430163)(234+-+-=x x x x x f 在[0,3]中的极小点，迭代精度取0.001。 解：在搜索区间[0,3]内取两试点a 1和a 2，计算它们的函数值 a 1= b ?0.618 b ?a =3?0.618? 3?0 =1.146 f 1=f a 1 =3?1.1464?16?1.1463+30?1.1462?24?1.146+8=0.9889 a 2=a +0.618 b ?a =0.618?3=1.854 f 2=f a 2 =3?1.8544?16?1.8543+30?1.8542?24?1.854+8=0.1044 比较函数值f 1和f 2，缩短搜索区间 由于f 2 . 郑州大学 机械优化设计部分程序 1.外推法 2.黄金分割法 3.二次插值法 4.坐标轮换法 5.随机方向法 6.四杆机构优化设计 . 1.外推法 源程序： #include 黄金分割法的优化设计 实验报告 学院：机电工程 机制自动化11-03班 学号：541102010326 姓名：刘点点 1，黄金分割法的程序流程图 2，对应流程图的C语言程序 下面应用C语言程序利用黄金分割法求一元函数F=x^2+2*x的最优解，已知初始区间为[-3,5] ,取收敛精度e=10-4。 C语言程序如下： #include printf("%d %.4lf %.4lf %.4lf %.4lf %.4lf %.4lf\n",n,a, b,x1,x2,y1,y2); n=n++; do { if(y1matlab编程实现二分法,牛顿法,黄金分割法,最速下降matlab程序代码
0.618法的matlab实现
matlab编程实现求解最优解
黄金分割法-机械优化设计程序
黄金分割法,进退法,原理及流程图
用MATLAB实现最速下降法-牛顿法和共轭梯度法求解实例
黄金分割法,进退法,原理及流程图
黄金分割法-进退法-原理及流程图
最优化方法之修正牛顿法matlab源码(含黄金分割法寻找步长)
用MATLAB实现最速下降法
MATLAB黄金分割法课程论文--分析
最优化牛顿法最速下降法共轭梯度法matlab代码
黄金分割法及其代码
黄金分割法调试程序
matlab 黄金分割法
黄金分割法求极小的MATLAB程序
用黄金分割法求极小点程序
机械优化设计黄金分割法 外推法
黄金分割法-机械优化设计-C语言程序
- matlab编程实现二分法牛顿法黄金分割法最速下降matlab程序代码
- 0.618法的matlab实现
- 最优化牛顿法最速下降法共轭梯度法matlab代码
- 黄金分割法求极小的MATLAB程序
- 利用MATLAB实现黄金分割法求极值问题-北京理工大学-机械优化设计
- matlab实验黄金分割法
- matlab 黄金分割法
- 【精品毕设】黄金分割法及其算法实现
- matlab黄金分割法求解
- 最优化方法地Matlab实现(公式(完整版))
- matlab编程实现二分法,牛顿法,黄金分割法,最速下降matlab程序代码
- 最优化方法之修正牛顿法matlab源码(含黄金分割法寻找步长)
- 黄金分割法的matlab程序
- 黄金分割法matlab程序
- 最优化牛顿法最速下降法共轭梯度法matlab代码
- 0.618法matlab实验报告
- 黄金分割法编程
- 黄金分割法,进退法,原理及流程图
- 0.618法的matlab实现
- 坐标轮换法 matlab实现