一维搜索方法的MATLAB 实现
姓名： 班级：信息与计算科学 学号： 实验时间: 2014/6/21 一、实验目的：
通过上机利用Matlab 数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab 软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。
二、实验背景： 黄金分割法
它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。
1、算法原理
黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断
的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。
2、算法步骤
用黄金分割法求无约束问题min f (x ), x ∈R 的基本步骤如下： （1）选定初始区间[a 1, b 1]及精度ε>0，计算试探点：
λ1=a 1+0.382*(b 1-a 1)
f λ>f (μk )（2）若b k -a k
f (λk )≤f (μk )转步骤（4）。 （3） ⎧a k +1=λk ⎪b =b ⎪k +1k ⎨
⎪λk +1=μk ⎪⎩μk +1=a k +1+0.382*(b k +1-a k +1) 转步骤（5）
μ1=a 1+0.618*(b 1-a 1) 。
（4）
转步骤（5）
（5）令k =k +1，转步骤（2）。
算法的MATLAB 实现
function xmin=golden(f,a,b,e) k=0;
x1=a+0.382*(b-a); x2=a+0.618*(b-a); while b-a>e f1=subs(f,x1); f2=subs(f,x2); if f1>f2 a=x1; x1=x2; f1=f2;
x2=a+0.618*(b-a); else b=x2; x2=x1; f2=f1;
x1=a+0.382*(b-a); end k=k+1; end
xmin=(a+b)/2; fmin=subs(f,xmin)
最优化方法上机实验
fprintf('k=\n'); disp(k);
3、实验结果(总结/方案)
黄金分割法求解极值实例。用黄金分割法求解下面函数的最小值：
f (t ) ==t 4-t 2-2t +5, 其中t ∈[-10, 10]
进退法
1. 算法原理
进退法是用来确定搜索区间（包含极小值点的区间）的算法，其理论依据是：f (x ) 为单谷函数（只有一个极值点），且[a , b ]为其极小值点的一个搜索区间，对于任意x 1, x 2∈[a , b ]，如果f (x 1)f (x 2)，则[x 1, b ]为极小值的搜索区间。
因此，在给定初始点x 0，及初始搜索步长h 的情况下，首先以初始步长向前搜索一步，计算f (x 0+h )。
（1） 如果f (x 0)
则可知搜索区间为[x , x 0+h ]，其中x 待求，为确定x ，后退一步计算
f (x 0-λh ) ，λ为缩小系数，且0
f (x 0-λ*h ) >f (x 0)，从而确定搜索区间[x 0-λ*h , x 0+h ]。 （2） 如果f (x 0)>f (x 0+h )
则可知搜索区间为[x 0, x ]，其中x 待求，为确定x ，前进一步计算f (x 0+λh ) ，
λ为放大系数，且λ>1，知道找到合适的λ*，使得f (x 0+h )
2. 算法步骤
用进退法求一维无约束问题min f (x ), x ∈R 的搜索区间（包含极小值点的区间）的基本算法步骤如下：
（1） 给定初始点x (0)，初始步长h 0，令h =h 0，x (1)=x (0)，k =0； （2） 令x (4)=x (1)+h ，置k =k +1；
（3） 若f (x (4))
（4） 令x (2)=x (1), x (1)=x (4)，f (x (2))=f (x (1))，f (x (1))=f (x (4))，令h =2h ，
转步骤（2）；
（5） 若k =1，则转步骤（6）否则转步骤（7）；
（6） 令h =-h ，x (2)=x (4)，f (x (2))=f (x (4))，转步骤（2）；
（7） 令x (3)=x (2), x (2)=x (1), x (1)=x (4)，停止计算，极小值点包含于区间
[x (1), x (3)]或[x (3), x (1)]
3. 算法的MATLAB 实现
function [A,B]=minJT(f,x0,h0,eps) %目标函数:f; %初始点:x0; %初始步长:h0; %精度:eps;
%目标函数取包含极值的区间的左端点:A; %目标函数取包含极值的区间的右端点:B; format long; if nargin==3; eps=1.0e-6; end
x1=x0; k=0; h=h0; while 1
x4=x1+h;%试探步 k=k+1;
f4=subs(f,findsym(f),x4); f1=subs(f,findsym(f),x1); if f4
h=2*h;%加大步长 else if k==1
h=-h;%反向搜索 x2=x4; f2=f4; else x3=x2; x2=x1; x1=x4; break; end end end
A=min(x1,x3); B=x1+x3-A; format short; 例：
取初始点为0，步长为0.1，用进退法求函数f (t ) =(t 2-1) 2+(t -1) 2+3=t 4-t 2-2t +5的
极值区间。
最优化方法上机实验
一维搜索方法的MATLAB 实现
姓名： 班级：信息与计算科学 学号： 实验时间: 2014/6/21 一、实验目的：
通过上机利用Matlab 数学软件进行一维搜索，并学会对具体问题进行分析。并且熟悉Matlab 软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。
二、实验背景： 黄金分割法
它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。
1、算法原理
黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断
的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。
2、算法步骤
用黄金分割法求无约束问题min f (x ), x ∈R 的基本步骤如下： （1）选定初始区间[a 1, b 1]及精度ε>0，计算试探点：
λ1=a 1+0.382*(b 1-a 1)
f λ>f (μk )（2）若b k -a k
f (λk )≤f (μk )转步骤（4）。 （3） ⎧a k +1=λk ⎪b =b ⎪k +1k ⎨
⎪λk +1=μk ⎪⎩μk +1=a k +1+0.382*(b k +1-a k +1) 转步骤（5）
μ1=a 1+0.618*(b 1-a 1) 。
（4）
转步骤（5）
（5）令k =k +1，转步骤（2）。
算法的MATLAB 实现
function xmin=golden(f,a,b,e) k=0;
x1=a+0.382*(b-a); x2=a+0.618*(b-a); while b-a>e f1=subs(f,x1); f2=subs(f,x2); if f1>f2 a=x1; x1=x2; f1=f2;
x2=a+0.618*(b-a); else b=x2; x2=x1; f2=f1;
x1=a+0.382*(b-a); end k=k+1; end
xmin=(a+b)/2; fmin=subs(f,xmin)
最优化方法上机实验
fprintf('k=\n'); disp(k);
3、实验结果(总结/方案)
黄金分割法求解极值实例。用黄金分割法求解下面函数的最小值：
f (t ) ==t 4-t 2-2t +5, 其中t ∈[-10, 10]
进退法
1. 算法原理
进退法是用来确定搜索区间（包含极小值点的区间）的算法，其理论依据是：f (x ) 为单谷函数（只有一个极值点），且[a , b ]为其极小值点的一个搜索区间，对于任意x 1, x 2∈[a , b ]，如果f (x 1)f (x 2)，则[x 1, b ]为极小值的搜索区间。
因此，在给定初始点x 0，及初始搜索步长h 的情况下，首先以初始步长向前搜索一步，计算f (x 0+h )。
（1） 如果f (x 0)
则可知搜索区间为[x , x 0+h ]，其中x 待求，为确定x ，后退一步计算
f (x 0-λh ) ，λ为缩小系数，且0
f (x 0-λ*h ) >f (x 0)，从而确定搜索区间[x 0-λ*h , x 0+h ]。 （2） 如果f (x 0)>f (x 0+h )
则可知搜索区间为[x 0, x ]，其中x 待求，为确定x ，前进一步计算f (x 0+λh ) ，
λ为放大系数，且λ>1，知道找到合适的λ*，使得f (x 0+h )
2. 算法步骤
用进退法求一维无约束问题min f (x ), x ∈R 的搜索区间（包含极小值点的区间）的基本算法步骤如下：
（1） 给定初始点x (0)，初始步长h 0，令h =h 0，x (1)=x (0)，k =0； （2） 令x (4)=x (1)+h ，置k =k +1；
（3） 若f (x (4))
（4） 令x (2)=x (1), x (1)=x (4)，f (x (2))=f (x (1))，f (x (1))=f (x (4))，令h =2h ，
转步骤（2）；
（5） 若k =1，则转步骤（6）否则转步骤（7）；
（6） 令h =-h ，x (2)=x (4)，f (x (2))=f (x (4))，转步骤（2）；
（7） 令x (3)=x (2), x (2)=x (1), x (1)=x (4)，停止计算，极小值点包含于区间
[x (1), x (3)]或[x (3), x (1)]
3. 算法的MATLAB 实现
function [A,B]=minJT(f,x0,h0,eps) %目标函数:f; %初始点:x0; %初始步长:h0; %精度:eps;
%目标函数取包含极值的区间的左端点:A; %目标函数取包含极值的区间的右端点:B; format long; if nargin==3; eps=1.0e-6; end
x1=x0; k=0; h=h0; while 1
x4=x1+h;%试探步 k=k+1;
f4=subs(f,findsym(f),x4); f1=subs(f,findsym(f),x1); if f4
h=2*h;%加大步长 else if k==1
h=-h;%反向搜索 x2=x4; f2=f4; else x3=x2; x2=x1; x1=x4; break; end end end
A=min(x1,x3); B=x1+x3-A; format short; 例：
取初始点为0，步长为0.1，用进退法求函数f (t ) =(t 2-1) 2+(t -1) 2+3=t 4-t 2-2t +5的
极值区间。
最优化方法上机实验