无约束优化方法---鲍威尔方法
本实验用鲍威尔方法求函数 f(x)=(x1-5)2+(x2-6)2 的最优解。
一、 简述鲍威尔法的基本原理
从任选的初始点x⑴o出发,先按坐标轮换法的搜索方向依次沿e1.e2.e3进行一维搜索,得各自方向的一维极小点x⑴ x⑵ x⑶.连接初始点xo⑴和最末一个一维极小点x3⑴,产生一个新的矢量 S1=x3⑴-xo⑴
再沿此方向作一维搜索,得该方向上的一维极小点x⑴.
从xo⑴出发知道获得x⑴点的搜索过程称为一环。S1是该环中产生的一个新方向,称为新生方向。
接着,以第一环迭代的终点x⑴作为第二环迭代的起点xo⑵,即 Xo⑵←x⑴
弃去第一环方向组中的第一个方向e1,将第一环新生方向S1补在最后,构成第二环的基本搜索方向组e2,e3,S1,依次沿这些方向求得一维极小点x1⑵,x2⑵,x3⑵.连接
Xo⑵与x3⑵,又得第二环的新生方向
S2=x3⑵-xo⑵
沿S2作一维搜索所得的极小点x⑵即为第二环的最终迭代点
二、 鲍威尔法的程序
#include "stdafx.h" /* 文件包含*/
#include
#include
#include
#define MAXN 10
#define sqr(x) ((x)*(x))
double xkk[MAXN],xk[MAXN],sk[MAXN];
int N,type,nt,et; //N--变量个数, type=0,1,2,3
约束个数
double rk;
double funt(double *x,double *g,double *h)
{
g[0]=x[0]; g[1]=x[1]-1; g[2]=11-x[0]-x[1];
return sqr(x[0]-8)+sqr(x[1]-8);
}
double F(double *x)
{
double f1,f2,ff,fx,g[MAXN],h[MAXN];
int i;
fx=funt(x,g,h);
f1=f2=0.0;
if(type==0 || type==2)for(i=0;
f1+=(fabs(g[i])>1.0e-15)?1.0/g[i]:1.0e15; nt,et--不等式、等式i
else for(i=0; i0)?0:g[i]*g[i];
for(i=0; i
if(type==0 || type==2)ff=fx+rk*f1+f2/sqrt(rk);
else ff=fx+rk*(f1+f2);
return ff;
}
double f(double x)
{
int i;
for (i=0; i
return F(xkk);
}
void find_ab(double x0,double h0,double *a,double *b)
{
double h,x1,y1,x2,y2,x3,y3;
h=h0;
x1=x0; y1=f(x1); x2=x1+h; y2=f(x2);
if (y2>=y1) {
h=-h0; x3=x1; y3=y1;
x1=x2; y1=y2; x2=x3; y2=y3;
}
for (;;) {
h*=2.0; x3=x2+h; y3=f(x3);
if (y2
x1=x2; y1=y2; x2=x3; y2=y3;
}
if (h>0) {*a=x1; *b=x3;}
else {*a=x3; *b=x1;}
}
void search_gold(double a,double b,double e,double *x,double *y) {
double x1,x2,y1,y2;
x1=a+0.382*(b-a); y1=f(x1);
x2=a+0.618*(b-a); y2=f(x2);
do {
if (y1
b=x2; x2=x1; y2=y1; x1=a+0.382*(b-a); y1=f(x1);
} else {
a=x1; x1=x2; y1=y2; x2=a+0.618*(b-a); y2=f(x2);
}
} while ((b-a)>e);
*x=0.5*(a+b); *y=f(*x);
}
double nc_powell(double *x0,double e1,double e2)
{
int i,j,k=1,m;
double a,b,ax,ay,d;
double
ss[MAXN][MAXN],s1[MAXN],ff[MAXN],x[MAXN],xn[MAXN],xn1[MAXN],f0,f1,f2,f3;
for (i=0; i
for (;;) {
for (j=0; j
for (i=0; i
for (j=0; j
}
for (j=0; j
for (j=0; j
search_gold(a,b,e2,&ax,&ay);
for (j=0; j
d=0;
for (j=0; j
printf("k=%d;",k);
for (j=0; j
if (d
for (j=0; j
}
f0=F(x0);
d=f0-ff[0]; m=0;
for (j=1; j
f1=F(x0); f2=F(xn); f3=F(xn1);
if (0.5*(f1-2*f2+f3)>=d) {
if (f2
else for (j=0; j
} else {
for (i=m+1; i
}
k++;
}
for (j=0; j
return F(xkk);
}
main()
{
double fk,fkk,ck,d1,d2,e1,e2;
double g[MAXN],h[MAXN],x1[MAXN],x0[MAXN]; int i;
N=2;
nt=3;
et=0;
type=1;
e1=0.0001;
e2=0.0001;
rk=0.001; ck=2;
x0[0]=8; x0[1]=8;
printf("=========\n");
fk = nc_powell(x0,0.01,0.001);
for(i=0; i
printf("rk=%lf\n",rk);
for (i=0; i
for(;;) {
rk*=ck;
fkk = nc_powell(x0,0.01,0.005);
printf("rk=%lf\n",rk);
for (i=0; i
d1=0; for(i=0; i
d2=fabs((fkk-fk)/fk);
printf("d1=%lf d2=%lf\n",d1,d2);
if(d1
for(i=0; i
fk=fkk;
}
fk=funt(x0,g,h);
printf("**********************\n");
for (i=0; i
for (i=0; i
}