一维黄金分割法程序

一维搜索方法的MATLAB 实现姓名： 班级：信息与计算科学 学号： 实验时间: 2014/6/21 一、实验目的：通过上机利用Matlab 数学软件进行一维搜索，并学会对具体问题进行分析。

并且熟悉Matlab 软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。

二、实验背景： 黄金分割法它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。

1、算法原理黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。

2、算法步骤用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下：（1）选定初始区间11[,]a b 及精度0ε>，计算试探点： 11110.382*()a b a λ=+- 11110.618*()a b a μ=+-。

（2）若k k b a ε-<，则停止计算。

否则当()()k k f f λμ>时转步骤（3）。

当()()k k f f λμ≤转步骤（4）。

（3） 11111110.382*()k k k k k k k k k k a b b a b a λλμμ+++++++=⎧⎪=⎪⎨=⎪⎪=+-⎩转步骤（5）（4）转步骤（5）（5）令1k k =+，转步骤（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; endxmin=(a+b)/2; fmin=subs(f,xmin)fprintf('k=\n'); disp(k);3、实验结果(总结/方案)黄金分割法求解极值实例。

黄金分割法的优化设计实验报告学院：机电工程机制自动化11-03班学号：541102010326姓名：刘点点1，黄金分割法的程序流程图2，对应流程图的C语言程序下面应用C语言程序利用黄金分割法求一元函数F=x^2+2*x的最优解，已知初始区间为[-3,5] ,取收敛精度e=10-4。

C语言程序如下：#include<stdio.h>#include<math.h>#define f(x) pow(x,2)+2*x#define M 0.618void main(){double y1,y2,x1,x2,x,a,b,e;int n;n=1;printf("请输入收敛精度e=");scanf("%lf",&e);printf("请输入区间左值a=");scanf("%lf",&a);printf("请输入区间右值b=");scanf("%lf",&b);printf("n a b x1 x2 y1 y2\n");x1=b-M*(b-a);x2=a+M*(b-a);y1=f(x1);y2=f(x2);printf("%d %.4lf %.4lf %.4lf %.4lf %.4lf %.4lf\n",n,a,b,x1,x2,y1,y2);n=n++;do{if(y1<y2){b=x2;x2=x1;y2=y1;x1=b-M*(b-a);y1=f(x1);printf("%d %.4lf %.4lf %.4lf %.4lf %.4lf %.4lf\n",n,a,b,x1,x2,y1,y2);n=n++;}else{a=x1;x1=x2;y1=y2;x2=a+M*(b-a);y2=f(x2);printf("%d %.4lf %.4lf %.4lf %.4lf %.4lf %.4lf\n",n,a,b,x1,x2,y1,y2);n=n++;}}while(fabs((b-a)/b)>=e&&fabs((y2-y1)/y2)>=e);x=(a+b)*0.5;printf("x=%.5lf\n",x);getchar();}3.运行结果:假定经十二次迭代后已满足收敛精度要求，则得x*=1/2(a+b)=1/2(-1.0214-0.9812)=-1.0013，相应的函数极值f(x*)=-0.9999；近似精确值x*=-1,f(x*)=-1,与解析法求得的精确值相同。

机械优化设计黄金分割法实验报告1、黄金分割法基本思路：黄金分割法适用于［a,b］区间上的任何单股函数求极小值问题，对函数除要求“单谷”外不做其他要求，甚至可以不连续。

因此，这种方法的适应面非常广。

黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间［a,b］内适当插入两点al,a2,并计算其函数值。

al,a2将区间分成三段，应用函数的单谷性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。

然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。

2黄金分割法的基本原理一维搜索是解函数极小值的方法之一，其解法思想为沿某一已知方向求目标函数的极小值点。

一维搜索的解法很多，这里主要采用黄金分割法（0.618法）。

该方法用不变的区间缩短率0.618代替斐波那契法每次不同的缩短率，从而可以看成是斐波那契法的近似，实现起来比较容易，也易于人们所接受。

rl=a+O382(Js-a)r2=a+0,618(b-a)如图fi(r2)>f(rl)所以新区间为［迈以为新区间，继续求新的试点黄金分割法是用于一元函数f(x)在给定初始区间［a,b］内搜索极小点**的一种方法。

它是优化计算中的经典算法，以算法简单、收敛速度均匀、效果较好而著称，是许多优化算法的基础，但它只适用于一维区间上的凸函数⑹，即只在单峰区间内才能进行一维寻优，其收敛效率较低。

其基本原理是：依照“去劣存优”原则、对称原则、以及等比收缩原则来逐步缩小搜索区间［7］。

具体步骤是：在区间［a,b］内取点：al,a2把［a,b］分为三段。

如果f(a1)>f(a2),令a=a1,a1=a2,a2=a+r*(b-a);如果f(a1)<f(a2),令b=a2,a2=a1,a1=b-r*(b-a),如果|(b-a)/b|和|(y1-y2)/y2|都大于收敛精度e重新开始。

因为［a,b］为单峰区间，这样每次可将搜索区间缩小0.618倍或0.382倍，处理后的区间都将包含极小点的区间缩小，然后在保留下来的区间上作同样的处理，如此迭代下去，将使搜索区［a,b］逐步缩小，直到满足预先给定的精度时，即获得一维优化问题的近似最优解。

一维寻优法(0.618法)程序设计一维寻优法，又叫作黄金分割法或者0.618法，是一种基于比较大小的优化算法，能够在一维搜索空间中找到最优解或者一定程度上接近最优解。

这是一种简单而经典的算法，在实际应用中有很多的应用场景。

接下来我们将介绍一下如何设计一维寻优法的程序，包括算法原理、代码实现和测试结果。

### 1. 算法原理一维寻优法的核心思想是找到一段区间，通过不断缩小这个区间的范围来逼近最优解。

具体来讲，我们首先需要给出一个初始的搜索区间，假设这个区间是[a, b]。

我们可以通过计算出0.618的值（记为c），将这个区间划分为两个子区间[a, c]和[c, b]。

对于这两个子区间中的一个，我们可以进一步将其划分为两个子区间，之后对于这两个子区间分别计算其函数值，保留其中更小的一个（因为我们是要找最小值），并更新原始的搜索区间。

如此往复进行下去，直到搜索区间的长度小于一定的阈值或者我们已经满足了一定的精度要求为止。

### 2. 代码实现下面是一维寻优法的Python示例代码：```pythondef golden_section(func, a, b, epsilon=1e-5):""":param func: 要进行最优化的函数:param a: 搜索区间左边界:param b: 搜索区间右边界:param epsilon: 精度控制参数:return: 函数极小值所在的x值"""c = 0.618 # 黄金分割点x1 = a + (1 - c) * (b - a) # 初始化搜索区间x2 = a + c * (b - a)y1 = func(x1)y2 = func(x2)while abs(b - a) > epsilon:if y1 <= y2:b = x2x2 = x1y2 = y1x1 = a + b - x2y1 = func(x1)else:a = x1x1 = x2y1 = y2x2 = a + b - x1y2 = func(x2)return (a + b) / 2```代码中，我们首先计算出黄金分割点，并初始化搜索区间。

课程设计（实验）材料（2）机械优化设计课程设计（实验）报告专业班级：设计题目：黄金分割法程序设计学生姓名：学生学号：任课教师：2013年月日一、设计要求：基于一维搜索的试探方法思想，运用黄金分割法编写C语言程序，得到极小点的数值近似解。

已知条件：1、目标函数：f(x)=x*x+2*x2、给定搜索区间：（-3,5）二、方法原理黄金分割法适用于【a，b】区间上的任何单股函数求极小值问题，对函数除要求“单谷”外不做其他要求，甚至可以不连续。

因此，这种方法的适应面非常广。

黄金分割法也是建立在区间消去法原理基础上的试探方法，即在搜索区间【a，b】内适当插入两点a1，a2，并计算其函数值。

a1，a2将区间分成三段，应用函数的单谷性质，通过函数值大小的比较，删去其中一段，是搜索区间得以缩小。

然后再在保留下来的区间上作同样的处理，如此迭代下去，是搜索区间无限缩小，从而得到极小点的数值近似解。

三、程序清单：#include<stdio.h>#include<math.h>double hanshu (double x);void main(){int k;double a,a1,a2,b,y1,y2,c,e,i,j;e=0.618,k=0;printf("a=");scanf("%lf",&a);printf("b=");scanf("%lf",&b);printf("c=");scanf("%lf",&c);a1=b-e*(b-a);y1=hanshu(a1);a2=a+e*(b-a);y2=hanshu(a2);printf("输出次数=%d\n a=%lf, a1=%lf, a2=%lf, b=%lf, y1=%lf, y2=%lf\n",k,a, a1,a2,b,y1,y2);i=(b-a)/b;j=(y2-y2)/y2;while(fabs(i)>=c||fabs(j>=c)){k++;if(y1>=y2){a=a1,a1=a2,y1=y2,a2=a+e*(b-a),y2=hanshu(a2);}else{b=a2,a2=a1,y2=y1,a1=b-e*(b-a),y1=hanshu(a1);}printf("输出次数=%d\n a=%lf, a1=%lf, a2=%lf, b=%lf, y1=%lf, y2=%lf\n",k,a,a1,a2,b,y1,y2);i=(b-a)/b;j=(y2-y1)/y2;}printf("k=%lf\n",0.5*(a+b));}double hanshu (double x){double m;m = x*x+2*x;return m;}实验结果（要求附上程序运行结果截图）五、手算过程如以下表格：。

凸优化之⽆约束优化（⼀维搜索⽅法：黄⾦分割法、斐波那契数列法）⽬标函数为⼀元单值函数f：R->R的最⼩化优化问题，⼀般不会单独遇到，它通常作为多维优化问题中的⼀个部分出现，例如梯度下降法中每次最优迭代步长的估计。

⼀维搜索⽅法是通过迭代⽅式求解的，这不同于我们⼈脑的直接通过解表达式求解⽅法。

迭代算法是从初始搜索点x(0)出发，产⽣⼀个迭代序列x(1),x(2),...。

在第k=0,1,2，...次迭代中，通过当前迭代点x(k)和⽬标函数 f 构建下⼀个迭代点x(k+1)。

某些算法可能只需要⽤到迭代点处的⽬标函数值，⽽另⼀些算法还可能⽤到⽬标函数的导数 f'(x)，甚⾄是⼆阶导数 f''(x)。

1、问题描述：如果⼀元单值函数 f:R->R 在闭区间[a0,b0]上是单峰的，求解 f 在该区间上的极⼩点。

2、计算机求解⽅法：以下⽅法的本质是：区间压缩(截取)法，通过不断缩⼩极⼩点所在的区间长度到⾜够的精度⽔平来逼近极⼩点。

（1）黄⾦分割法（每次区间截取⽐例为固定值）第⼀步：初始区间[a0,b0]，设定截取⽐例为 r，则第⼀次挑选两个中间点 a1和 b1，它们满⾜对称要求：a1-a0=b0-b1= r(b0-a0)，显然r<1/2，如果 f(a1) < f(b1)，那么极⼩点应该在区间 [a0,b1] 中; 否则，如 f(a1) >= f(b1)，极⼩点应该位于区间 [a1,b0] 中。

第⼆步：经过第⼀次压缩后，极⼩点所在区间变为[a0,b1]，或者[a1,b0]。

假定为[a0,b1]，下⾯需要第⼆次挑选中间点 a2和 b2 。

为了充分利⽤第⼀次的挑选点信息，减少计算次数，那么第⼆次挑选的点 b2可以取第⼀次的挑选点 a1，这样就只需要计算b2（即a1）在新区间上的对称点 a2 和 f(a2) 。

为了实现这样的想法，那么必须满⾜下⾯的要求: r(b1-a0)= b1 - b2=b1-a1 <=> r[b0-r(b0-a0)-a0]=(1-2r)(b0-a0)<=>r2-3r+1=0<=>1-r=(sqrt(5)-1)/2 = 0.618，即每次截取后保留⽐例为0.618 故称此⽅法为黄⾦分割法。

最优化理论与算法一维搜索一维是最优化问题求解中常用的一种算法。

在一维中，我们需要在给定的区间内寻找函数的最小值或最大值。

一维算法的基本思想是通过不断的迭代，在区间内不断缩小最优解的范围，最终找到最优解。

常用的一维算法包括黄金分割法、斐波那契法、插值法等。

黄金分割法是一种较为简单且常用的一维算法。

该算法基于黄金分割点的性质，通过不断缩小区间来逼近最优解。

黄金分割法的具体步骤如下：1.初始化区间的上下界，确定迭代终止条件；2.计算黄金分割点的位置；3.根据黄金分割点分割区间；4.更新区间的上下界；5.判断是否满足迭代终止条件，如果满足，则输出最优解；如果不满足，则返回第2步。

斐波那契法是另一种常用的一维算法。

该算法通过斐波那契数列的性质，不断缩小区间来逼近最优解。

斐波那契法的具体步骤如下：1.初始化斐波那契数列，确定迭代终止条件；2.计算斐波那契点的位置；3.根据斐波那契点分割区间；4.更新区间的上下界；5.判断是否满足迭代终止条件，如果满足，则输出最优解；如果不满足，则返回第2步。

插值法是一种基于函数插值的一维算法。

该算法通过插值函数来拟合原函数，并通过求解插值函数的最小值或最大值来近似求解原函数的最小值或最大值。

插值法的具体步骤如下：1.初始化区间的上下界，确定迭代终止条件；2.根据插值函数拟合原函数，得到插值函数的表达式；3.求解插值函数的最小值或最大值；4.更新区间的上下界；5.判断是否满足迭代终止条件，如果满足，则输出最优解；如果不满足，则返回第2步。

除了上述算法，还存在其他一维算法，如割线法、牛顿法等。

这些算法各有特点，适用于不同类型的最优化问题。

一维算法的优势在于其计算简单、耗时少的特点。

然而，一维算法也存在一些缺点，例如容易陷入局部最优解、收敛速度较慢等。

因此，对于一些复杂的最优化问题，可能需要使用更高维度的算法进行求解。

总之，一维是最优化问题求解中常用的一种算法。

通过在给定的区间内不断迭代，可以逼近最优解。