机械优化设计上机实践报告班级：机械（茅以升）101姓名:学号: 1004010510成绩:指导教师: 张迎辉日期: 2013.11.201 《一维搜索方法》上机实践报告1、写出所选择的一维搜索算法的基本过程、原理（可附流程图说明）。

（一）进退法 1. 算法原理进退法是用来确定搜索区间（包含极小值点的区间）的算法，其理论依据是：()f x 为单谷函数（只有一个极值点），且[,]a b 为其极小值点的一个搜索区间，对于任意12,[,]x x a b ∈，如果()()12f x f x <，则2[,]a x 为极小值的搜索区间，如果()()12f x f x >，则1[,]x b 为极小值的搜索区间。

因此，在给定初始点0x ，及初始搜索步长h 的情况下，首先以初始步长向前搜索一步，计算()0f x h +。

（1） 如果()()00f x f x h <+则可知搜索区间为0[,]x x h +，其中x 待求，为确定x ，后退一步计算0()f x h λ-，λ为缩小系数，且01λ<<，直接找到合适的*λ，使得()*00()f x h f x λ->，从而确定搜索区间*00[,]x h x h λ-+。

（2） 如果()()00f x f x h >+则可知搜索区间为0[,]x x ，其中x 待求，为确定x ，前进一步计算0()f x h λ+，λ为放大系数，且1λ>，知道找到合适的*λ，使得()*00()f x h f x h λ+<+，从而确定搜索区间*00[,]x x h λ+。

2. 算法步骤用进退法求一维无约束问题min (),f x x R ∈的搜索区间（包含极小值点的区间）的基本算法步骤如下：（1） 给定初始点(0)x ，初始步长0h ，令0h h =，(1)(0)x x =，0k =； （2） 令(4)(1)x x h =+，置1k k =+；（3） 若()()(4)(1)f x f x <，则转步骤（4），否则转步骤（5）；（4） 令(2)(1)(1)(4),x x x x ==，()()(2)(1)f x f x =，()()(1)(4)f x f x =，令2h h =，转步骤（2）； （5） 若1k =，则转步骤（6）否则转步骤（7）；（6） 令h h =-，(2)(4)x x =，()()(2)(4)f x f x =，转步骤（2）；（7） 令(3)(2)(2)(1)(1)(4),,x x x x x x ===，停止计算，极小值点包含于区间(1)(3)(3)(1)[,][,]x x x x 或（二）黄金分割法1、黄金分割法基本思路：黄金分割法适用于[a ，b]区间上的任何单股函数求极小值问题，对函数除要求“单谷”外不做其他要求，甚至可以不连续。

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

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

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

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

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

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

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

图1黄金分割法是用于一元函数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)<f(a2) ，令b=a2，a2=a1,a1=b-r*(b-a),如果｜(b-a)/b｜和｜(y1-y2)/y2｜都大于收敛精度ε重新开始。

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

黄金分割法原理如图１所示，3 程序流程如下：4 实验所编程序框图否算例1：min f(x)= x*x+2*x(1)C++程序如下：#include <math.h>#include <stdio.h>#define f(x) x*x+2*xdouble calc(double *a,double *b,double e,int *n){ double x1,x2,s;if(fabs(*b-*a)<=e)s=f((*b+*a)/2);else{ x1=*b-0.618*(*b-*a);x2=*a+0.618*(*b-*a);if(f(x1)>f(x2))*a=x1;else*b=x2;*n=*n+1;s=calc(a,b,e,n);}return s;}main(){ double s,a,b,e;int n=0;scanf("%lf %lf %lf",&a,&b,&e);s=calc(&a,&b,e,&n);printf("a=%lf,b=%lf,s=%lf,n=%d\n",a,b,s,n);}2、程序运行结果：算例2：min f=x^2-10*x+36理论最优解：x*=5.0，f（x*）=11.0（1）MATLAB程序清单：function f=myfun_yi(x)f=x^2-10*x+36>> fminbnd(@myfun_yi,1,12)（2）运行结果：>> fminbnd(@myfun_yi,1,12)f =11.0407f =18.8309f =12.9691f =11f =11.000011.0000ans =5（3）结果分析：由迭代程序f=11.0，ans=5，与理论结果相等算例3：minf=x^4-5*x^3+4*x^2-6*x+60理论最优解：x*=3.2796，f（x*）=22.6590（1）MATLAB程序清单：function f=myfun_yi(x)f=x^4-5*x^3+4*x^2-6*x+60>> fminbnd(@myfun_yi,1,12)（2）运行结果：>> fminbnd(@myfun_yi,1,12)f =165.3948f =1.5836e+03f =24.8730f =35.9194f =23.9089f =22.7621f =31.7507f =22.6673f =22.6594f =22.6590f =22.6590f =22.6590f =22.6590 ans =3.2796（3）结果分析：由迭代程序得f =22.659，ans =3.2796，与理论最优解相等2 《无约束优化搜索方法》上机实践报告1、写出所选择的无约束优化搜索算法的基本过程、原理（可附流程图说明）。

鲍威尔改进方法鲍威尔（Powell）法是直接利用函数值来构造共轭方向的一种方法在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。

在改进的算法中首先判断原向量组是否需要替换。

如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。

2、程序计算结果分析：中间各步骤的结果分析及与理论计算结果分析对比。

算例1：min f=4*(x(1)-5)^2+(x(2)-6)^2初始点：x0=[8;9],f(x0)=45最优解：x*=[5;6],f(x*)=0(1)MATLAB程序清单：function f=myfun_wuyueshu(x)f=4*(x(1)-5)^2+(x(2)-6)^2>> [x,fval]=fminunc(@myfun_wuyueshu,x0)(2)运行结果：f =45Warning: Gradient must be provided for trust-region algorithm;using line-search algorithm instead.> In fminunc at 367f =45.0000f =45.0000f =f =23.5625f =23.5625f =2.6958f =2.6958f =2.6958f =1.3788f =1.3788f =1.3788f =0.00540.0054f =0.0054f =6.4975e-05f =6.4973e-05f =6.4975e-05f =6.1579e-09f =6.1522e-09f =6.1443e-09f =1.7876e-121.8627e-12f =1.5586e-12Local minimum found.Optimization completed because the size of the gradient is less thanthe default value of the function tolerance.<stopping criteria details>x =5.00006.0000fval =1.7876e-12(3)结果分析：由迭代程序得x =[ 5.0000；6.0000],fval =1.7876e-12，与理论最优解相等。

算例2：min f=(x(1)^2+x(2)-11)^2+(x(1)+x(2)^2-7)^2初始点：x0=[1;1],f(x0)=106最优解：x*=[3;2],f(x*)=0(1)MATLAB程序清单：function f=myfun_wuyueshu(x)f=(x(1)^2+x(2)-11)^2+(x(1)+x(2)^2-7)^2>> [x,fval]=fminunc(@myfun_wuyueshu,x0)(2)运行结果：>> x0=[1;1]11>> [x,fval]=fminunc(@myfun_wuyueshu,x0)f =106Warning: Gradient must be provided for trust-region algorithm; using line-search algorithm instead.> In fminunc at 367f =106.0000f =106.0000f =29.5430f =29.5430f =29.5430f =1.7450e+041.7450e+04f =1.7450e+04f =90.3661f =90.3661f =90.3661f =0.3575f =0.3575f =0.3575f =0.0179f =0.0179f =0.0179f =0.0064f =0.0064f =0.0064f =1.0048e-06f =1.0044e-06f =1.0049e-06f =4.8639e-09f =f =4.8781e-09f =5.2125e-12f =5.8703e-12f =5.7870e-12Local minimum found.Optimization completed because the size of the gradient is less thanthe default value of the function tolerance.<stopping criteria details>x =3.00002.0000fval =5.2125e-12(3)结果分析：由迭代程序得x=[3;2],fval = 5.2125e-12,与理论最优解相等算例3:ff=x[0]*x[0]+2*x[1]*x[1]-4*x[0]-2*x[0]*x[1];（1）鲍威尔改进算法C++程序清单：#include "stdio.h"#include "stdlib.h"#include "math.h"double objf(double x[]){double ff;ff=x[0]*x[0]+2*x[1]*x[1]-4*x[0]-2*x[0]*x[1];return(ff);}void jtf(double x0[ ],double h0,double s[ ],int n,double a[ ],double b[ ]) {int i;double *x[3],h,f1,f2,f3;for (i=0;i<3;i++)x[i]=(double *)malloc (n*sizeof(double));h=h0;for(i=0;i<n;i++)*(x[0]+i)=x0[i];f1=objf(x[0]);for(i=0;i<n;i++)*(x[1]+i)=*(x[0]+i)+h*s[i];f2=objf(x[1]);if(f2>=f1){h= -h0;for (i=0;i<n;i++)*(x[2]+i)=*(x[0]+i);f3=f1;for(i=0;i<n;i++){*(x[0]+i)= *(x[1]+i);*(x[1]+i)= *(x[2]+i);}f1=f2;f2=f3;}for(;;){h=2. *h;for(i=0;i<n;i++)*(x[2]+i)=* (x[1]+i) +h*s[i];f3= objf(x[2]);if(f2<f3)break;else{ for(i=0;i<n;i++){*(x[0]+i)= *(x[1]+i);*(x[1]+i)= *(x[2]+i);}f2=f3;}}if(h<0. )for(i=0;i<n;i++){a[i]=*(x[2]+i);b[i]=*(x[0]+i);}elsefor(i=0;i<n;i++){a[i]=*(x[0]+i);b[i]=*(x[2]+i);}for(i=0;i<3;i++)free(x[i]);}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<n;i++){*(x[0]+i)=a[i]+0.618*(b[i]-a[i]);*(x[1]+i)=a[i]+0.382*(b[i]-a[i]);}f1=objf(x[0]);f2=objf(x[1]);do{if(f1>f2){for(i=0;i<n;i++){b[i]=*(x[0]+i);*(x[0]+i)=*(x[1]+i);}f1=f2;for(i=0;i<n;i++)*(x[1]+i)=a[i]+0.382*(b[i]-a[i]);f2=objf(x[1]);}else{for(i=0;i<n;i++){a[i]=*(x[1]+i);*(x[1]+i)=*(x[0]+i);f2=f1;for(i=0;i<n;i++)*(x[0]+i)=a[i]+0.618*(b[i]-a[i]);f1=objf(x[0]);}q=0;for(i=0;i<n;i++)q=q+(b[i]-a[i])*(b[i]-a[i]);w=sqrt(q);}while(w>eps);for(i=0;i<n;i++)xx[i]=0.5*(a[i]+b[i]);ff=objf(xx);for(i=0;i<2;i++)free(x[i]);return(ff);}double oneoptim(double x0[],double s[],double h0,double epsg,int n,double x[]) {double *a,*b,ff;a=(double *)malloc(n*sizeof(double));b=(double *)malloc(n*sizeof(double));jtf(x0,h0,s,n,a,b);ff=gold(a,b,epsg,n,x);free(a);free(b);return(ff);}double powell(double p[],double h0,double eps,double epsg,int n,double x[]) {int i,j,m;double *xx[4],*ss,*s;double f,f0,f1,f2,f3,fx,dlt,df,sdx,q,d;ss=(double *)malloc(n*(n+1)*sizeof(double));s=(double *)malloc(n*sizeof(double));for (i=0;i<n;i++){for (j=0;j<=n;j++)*(ss+i*(n+1)+j)=0;*(ss+i*(n+1)+i)=1;}for (i=0;i<4;i++)xx[i]=(double *)malloc(n*sizeof(double));for (i=0;i<n;i++)*(xx[0]+i)=p[i];for(;;){for (i=0;i<n;i++){*(xx[1]+i)=*(xx[0]+i);}f0=f1=objf(x);dlt=-1;for (j=0;j<n;j++){for (i=0;i<n;i++){*(xx[0]+i)=x[i];*(s+i)=*(ss+i*(n+1)+j);}f=oneoptim(xx[0],s,h0,epsg,n,x);df=f0-f;if(df>dlt){dlt=df;m=j;}}sdx=0.;for (i=0;i<n;i++)sdx=sdx+fabs(x[i]-(*(xx[1]+i)));if(sdx<eps){free(ss);free(s);for (i=0;i<4;i++)free(xx[i]);return(f);}for (i=0;i<n;i++)*(xx[2]+i)=x[i];f2=f;for (i=0;i<n;i++){*(xx[3]+i)=2.*(*(xx[2]+i)-(*(xx[1]+i))); x[i]=*(xx[3]+i);}fx=objf(x);f3=fx;q=(f1-2*f2+f3)*(f1-f2-dlt)*(f1-f2-dlt);d=0.5*dlt*(f1-f3)*(f1-f3);if((f3<f1)||(q<d)){if(f2<=f3)for (i=0;i<n;i++)*(xx[0]+i)=*(xx[2]+i);elsefor (i=0;i<n;i++)*(xx[0]+i)=*(xx[3]+i);}else{*(ss+(i+1)*(n+1))=x[i]-(*(xx[1]+i)); *(s+i)=*(ss+(i+1)*(n+1));}f=oneoptim(xx[0],s,h0,epsg,n,x);for(i=0;i<n;i++)*(xx[0]+i)=x[i];for (j=m+1;j<=n;j++)for (i=0;i<n;i++)*(ss+i*(n+1)+j-1)=*(ss+i*(n+1)+j);}}}void main(){double p[]={1,1};double ff,x[2],x1,x2,f;ff=powell(p,0.3,0.001,0.0001,2,x); printf("shuchuzuiyoujie：\n");x1=x[1];x2=x[2];f=ff;printf("x1=%f,x2=%f,f=%f\n",x1,x2,f); getchar();}（2）运行结果为：3《约束优化搜索方法》上机实践报告1、写出所选择的约束优化搜索算法的基本过程、原理（可附流程图说明）。