黄金分割法
一、一维搜索方法
1、黄金分割法
1.1、基本思想
黄金分割法是通过不断缩短单峰区间的长度来搜索极小点的一种有效方法。它按比例因
子缩小,通过比较的大小确定取舍区间,最终使区间缩短到足够小和
fx(),,0.618
值收敛到足够近,取最后两试验点的平均值作为极小点的数值近似解。 2.1、程序框图
开始
给定a b epson on
,,0.618
xabaffx2()4(2),,,,,
xabaffx1(1)*()3(1),,,,,,
N Y ff43,
ff43, ax,1 bx,2 xxff1234,, xxff2143,, 结束
xaba2(),,,,xaba1(1)*(),,,,, ffx4(2), ffx3(1),1 xab*(),, 2
baff,,43 ,,,,和bf3
基本程序
clear all;
Syms x;
syms a;
syms b;
fx=x*x-10*x+36;
a=1;
b=7;
k =0;
f1=subs(fx,a);
f2=subs(fx,b);
epson=2.0e-9;
x1=a+0.382*(b-a);
x2=a+0.618*(b-a);
f3=subs(fx,x1);
f4=subs(fx,x2);
while(b-a)>epson;
if(f3<=f4)
b=x2;
x2=x1;
f4=f3;
x1=a+0.382*(b-a);
f3=subs(fx,x1);
k=k+1;
else
a=x1;
x1=x2;
f3=f4;
x2=a+0.618*(b-a);
f4=subs(fx,x2);
k=k+1;
end
end
k
x=(a+b)/2
f=subs(fx,x) 二 无约束多维优化方法
2.1 共轭梯度法
基本思想:对梯度法作一个修正,将搜索方向由负梯度方向旋转一个角度,使相邻的
两次搜索方向由正交变为共轭,成为二次收敛。
程序框图
基本程序
clear all;
clc;
syms t x1 x2;
f=4*(x1-5)^2+(x2-6)^2;
k=0;
shi=0;
v=[x1 x2];
df=jacobian(f,v); G=jacobian(df,v); df=df';
G=G';
espon=2.0e-3;
x0=[1 1]';
g0=subs(df,{x1,x2},{x0(1,1),x0(2,1)}); d0=-g0;
p0=norm(g0);
while shi==0
if p0>espon
x=x0+t*d0;
f0=subs(f,{x1,x2},{x(1,1),x(2,1)});
df0=jacobian(f0,t);
T=eval(solve(df0,t));
x0=x0+T*d0;
g1=subs(df,{x1,x2},{x0(1,1),x0(2,1)});
b=norm(g1)^2/norm(g0)^2;
d0=-g1+b*d0;
p0=norm(d0);
k=k+1;
else
shi=1
k
x0
G=subs(G,{x1,x2},{x0(1,1),x0(2,1)});
f=subs(f,{x1,x2},{x0(1,1),x0(2,1)});
G
f
end
end
2.2牛顿法(二维)
基本思想
将f(x)在x(k)点作泰勒展开,取二次函数式Φ(x) 作为近似函数,以Φ(x)的极小值点作为 f(x)的近似极小值点。
1()()()2()()2kkTkkk fXfXXXfXXXx,,,,,,,,()[()]()()()()2
求二次函数的极值:
()2()()kkk ,,,,,,,,()()()()0XXXXXff
程序框图
基本程序
clc;
clear all;
syms x1 x2;
f=(x1^2+x2-11)^2+(x1+x2^2-7)^2; v=[x1 x2];
df=jacobian(f,v);
G=jacobian(df,v);
df=df';
G=G';
epson=2.0e-7;
x0=[2 1]';
g1=subs(df,{x1,x2},{x0(1,1),x0(2,1)}); G1=subs(G,{x1,x2},{x0(1,1),x0(2,1)}); k=0;
p=-G1\g1;
p1=subs(sqrt(p(1,1)^2+p(2,1)^2)); while(p1>epson)
x0=x0+p;
g1=subs(df,{x1,x2},{x0(1,1),x0(2,1)});
G1=subs(G,{x1,x2},{x0(1,1),x0(2,1)});
p=-G1\g1;
p1=subs(sqrt(p(1,1)^2+p(2,1)^2));
k=k+1;
end;
f=subs(f,{x1,x2},{x0(1,1),x0(2,1)}); k
x0
f
三 约束优化方法
3.1 外点法
基本思想
外点法是从可行域的外部构造一个点序列去逼近原约束问
的最优解。外点法可以用来
求解含不等式和等式约束的优化问题。
程序框图
基本程序
clc;
k=0;
M=1;
c=8;
eps=1.0e-4;
X0=[3 3]';
flag=1;
while (flag==1)&(k<20) syms x1 x2
f=(x1-2)^2+(x2-1)^2;
g1=x1^2-x2;
g2=x1+x2-2;
q=f+M*(g1^2+g2^2); f1=diff(q,x1);
f2=diff(q,x2);
s=solve(f1,f2,'x1','x2'); X1=[s.x1 s.x2]';
norm= subs( sqrt( (X1(1)-X0(1))^2+(X1(2)-X0(2))^2));
if(norm