Thứ Năm, 20 tháng 2, 2014
Tài liệu CHƯƠNG 8: TỐI ƯU HOÁ pptx
374
ymin=yp;
Đểtìmcựctiểucủahàmtadùngchươngtrình
ctgolden.m:
clearall,clc
f=inline(ʹ1.6*x^3+3*x^2‐2*xʹ);
x=0;
delta=1e‐8;
epsilon=1e‐10;
[a,b]=goldbracket(f,x,0.2);
[xmin,ymin]=golden(f,a,b,delta,epsilon)
§3.PHƯƠNGPHÁPXẤPXỈBẬCHAI
Ýtưởngcủaphươngphápnàylà:
‐xấpxỉhàmđốitượngf(x)bằngmộthàmbậc2p
2(x)qua3điểmcho
trước
‐cậpnhật3điểmnàybằngcáchthaymộttrong3điểmbằngcựctiểu
củahàmp
2(x)
Qua3điểm:
[]
[]
[
]
{
}
00 11 22
(x ,f(x ) , (x ,f(x ) , (x , f(x ) x0<x1<x2
tatìmđượcđathứcnộisuyp
2(x)vàđiểmcóđạohàmbằngzero:
−+ −+ −
==
⎡⎤
−+ −+ −
⎣⎦
22 22 22
01 2 12 0 20 1
3
01 2 12 0 20 1
f(x x) f(x x) f(x x)
xx
2 f (x x ) f (x x ) f (x x )
(1)
Đặcbiệt,nếu cácđiểmtìmđượctrướcđâyphânbốđềuvớikhoảngcáchh(
nghĩalàx
2‐x1=x1‐x0=h)thì(1)trởthành:
−+ −+ − −+
==+
−
+−
⎡⎤
−+ −+ −
⎣⎦
22 22 22
01 2 12 0 20 1 0 1 2
30
012
01 2 12 0 20 1
f(x x) f(x x) f(x x) 3f 4f f
xxh
2( f 2f f )
2 f (x x ) f (x x ) f (x x )
(2)
Ta cập nhật 3điểm theo cách này chođến khi
−≈
20
xx 0 hay
−≈
20
f(x ) f(x ) 0
vàcựctiểulàx3.Quytắccậpnhật3điểmlà:
‐Trongtrườnghợp
<
<
031
xxxtadùng
031
(x ,x ,x)
hay
312
(x ,x,x )
làm3
điểmmớituỳtheof(x
3)<f(x1)haykhông
‐Trongtrườnghợp
<
<
132
xxxtadùng
132
(x ,x ,x )hay
013
(x ,x,x )làm3
điểmmớituỳtheof(x
3)≤f(x1)haykhông.
Quátrìnhtìmcựctiểuđượcmôtảtrênhìnhsau:
375
Taxâydựnghàm
optquad()đểthựchiệnthuậttoánnày.
function[xo,fo]=optquad(f,x0,tolx,tolfun,maxiter)
%Timcuctieucuaf(x)bangphuongphapxapxibac2
iflength(x0)>2
x012=x0(1:3);
else
iflength(x0)==2
a=x0(1);
b=x0(2);
else
a=x0‐10;
b=x0
+10;
end
x012=[a(a+b)/2b];
end
f012=f(x012);
[xo,fo]=optquad0(f,x012,f012,tolx,tolfun,maxiter);
function[xo,fo]=optquad0(f,x012,f012,tolx,tolfun,k)
x0=x012(1);
x1=x012(2);
x2=x012(3);
376
f0=f012(1);
f1=f012(2);
f2=f012(3);
nd=[f0‐f2f1‐f0f2‐f1]*[x1*x1x2*x2x0*x0;x1x2x0]ʹ;
x3=nd(1)/2/nd(2);
f3=feval(f,x3);%Pt.(1)
ifk<=0|abs(x3‐x1)<tolx|abs(f3‐f1)<tolfun
xo=x3;
fo=
f3;
ifk==0
fprintf(ʹDaycothexemladiemcuctieuʹ)
end
else
ifx3<x1
iff3<f1
x012=[x0x3x1];
f012=[f0f3f1];
else
x012=[x3x1x2];
f012=[f3f1
f2];
end
else
iff3<=f1
x012=[x1x3x2];
f012=[f1f3f2];
else
x012=[x0x1x3];
f012=[f0f1f3];
end
end
[xo,fo]=optquad0(f,x012,f012,tolx,tolfun,k‐1);
end
Đểtìmđiểmcựctiểutadùngchươngtrình
ctoptquad.m:
clearall,clc
377
%f=inline(ʹ(x.^2‐4).^2/8‐1ʹ);
a=0;
b=3;
delta=1e‐8;
epsilon=1e‐10;
maxiter=100;
[xmin,ymin]=optquad(f,[ab],delta,epsilon,maxiter)
§4.PHƯƠNGPHÁPNELDER‐MEAD
PhươngphápNelder‐Meadcóthểdùngđểtìmcựctiểucủahàmnhiều
biếnmàphươngphápti ếtdiệnvànghayphươngphápxấpxỉbậc2không
dùngđược.ThuậttoánNelder‐Meadgồmcác
bướcnhưsau:
Bước1:Cho3điểmđầutiêna,b,cvớif(a)<f(b)<f(c)
Bước2:Nếu3điểmvàcácgiátrịtươngứngcủahàmđủgầnnhauthìta
coialàđiểmcựctiểuvàkếtthúcquátrìnhtính
Bước 3: Nếu không ta coi
điểm cực tiểu nằmđối diện với
điểm c trênđường ab(xem hình
vẽ)vàlấy:
e=m+2(m‐c)
với
m=(a+b)/2
vànếuf(e)<
f(b)thìlấy:
r=(m+e)/2=2m‐c
vànếuf(r)<f(c)thìlấyrlàmgiá
trị mới của c; nếu f(r)
≥ f(b) thì
lấy:
s=(c+m)/2
vànếuf(s)<f(c)thìlấyslàmgiátrịmớicủa c;nếukhôngbỏcácđiểmb,cvà
dùngmvàc
1=(a+c)/2làmđiểmbvàcmớivàchorằngcựctiểunằmquanh
điểma.
Bước4:Trởvềbước1
Taxâydựnghàm
neldermead()đểthựchiệnthuậttoánnày:
function[xo,fo]=neldermead(f,x0,tolx,tolfun,maxiter)
n=length(x0);
e
c1
a
m
r
c
b
s2
s1
c2
m=(a+b)/2 r=m+(m‐c)
e=m+2(m‐c) s
1=(c+m)/2
s
2=(m+r)/2 c1=(c+a)/2
c
2=(r+a)/2
378
ifn==1%truonghopham1bien
[xo,fo]=optquad(f,x0,tolx,tolfun);
return
end
S=eye(n);
fori=1:n
i1=i+1;
ifi1>n
i1=1;
end
abc=[x0;x0+S(i,:);x0+S(i1,:)];
fabc
=[feval(f,abc(1,:));feval(f,abc(2,:));feval(f,abc(3,:))];
[x0,fo]=neldermead0(f,abc,fabc,tolx,tolfun,maxiter);
ifn<3,
break;
end
end
xo=x0;
function[xo,fo]=neldermead0(f,abc,fabc,tolx,tolfun,k)
[fabc,I]=sort(fabc);
a=abc(I(1),:);
b=abc(I(2),:);
c=abc(I(3),:);
fa=fabc(1);
fb=fabc(2);
fc=fabc(3);
fba=fb‐fa;
fcb=fc‐fb;
ifk<=0|abs(fba)+abs(fcb)
<tolfun|abs(b‐a)+abs(c‐b)<tolx
xo=a;
fo=fa;
ifk==0
fprintf(ʹXemdayladiemcuctieuʹ)
end
else
379
m=(a+b)/2;
e=3*m‐2*c;
fe=feval(f,e);
iffe<fb
c=e;
fc=fe;
else
r=(m+e)/2;
fr=feval(f,r);
iffr<fc
c=r;
fc=fr;
end
iffr>=fb
s=(c+m)/2;
fs=feval(f,s);
iffs<fc
c=s;
fc=fs;
else
b=m;
c=(a+c)/2;
fb=feval(f,b);
fc=feval(f,c);
end
end
end
[xo,fo]=neldermead0(f,[a;b;c],[fafbfc],tolx,tolfun,k‐1);
end
Để tìm cực tiểu của hàm
=
=− − +−
22
112 122
zf(x,y)x xx 4x x x lân cận [0 0] ta
dùngchươngtrình
ctneldermead.m:
clearall,clc
f=inline(ʹx(1)*x(1)‐x(1)*x(2)‐4*x(1)+x(2)*x(2)‐x(2)ʹ);
x0=[00];
380
b=1;
delta=1e‐8;
epsilon=1e‐10;
maxiter=100;
[xmin,ymin]=neldermead(f,x0,delta,epsilon,maxiter)
§5.PHƯƠNGPHÁPĐỘDỐCLỚNNHẤT
Phương pháp này tìmđiểm cực tiểu của hàm n biến theo hướng
gradientâm:
[] []
⎡⎤
∂∂ ∂
−=−∇=−
⎢⎥
∂∂ ∂
⎣⎦
L
12 n
f(x) f(x) f(x)
g( x ) f ( x )
xx x
vớikíchth ướcbướctínhα
ktạilầnlặpthứkđượchiệuchỉnhsaochogiátrị
hàmcựctiểutheohướngtìm.Thuậttoángồmcácbướcsau:
•Tạilầnlặpthứk=0,tìmgiátrịhàm
f(x0)vớiđiểmkhởiđầux0
•Tạilầnlặpthứk,tìmα
ktheohướng‐g(x)
(
)
−−−−
α= −α
k1 k1 k1 k1
fx g /g (1)
•Tínhgiátrịx
k:
−−−−
=−α
kk1k1k1k1
xx g/g(2)
•Nếux
k≈xk‐1vàf(xk)≈f(xk‐1)thìcoilàcựctiểu,nếukhông thìquayvề
bước2.
function[xo,fo]=steepest(f,x0,tolx,tolfun,alpha0,maxiter)
ifnargin<6
maxiter=100;
end
ifnargin<5
alpha0=10;%kichthuockhoigan
end
ifnargin<4
tolfun=1e‐8;
end%|f(x)|<tolfunmongmuon
ifnargin<3
tolx=
1e‐6;
end%|x(k)‐x(k‐1)|<tolxmongmuon
x=x0;
381
fx0=feval(f,x0);
fx=fx0;
alpha=alpha0;
kmax1=25;
warning=0;
fork=1:maxiter
g=grad(f,x);
g=g/norm(g);%gradientlavectohang
alpha=alpha*2;%dethuditheohuonggradientam
fx1=feval(f,x‐alpha*2*g);
for
k1=1:kmax1%timbuoctoiuu
fx2=fx1;
fx1=feval(f,x‐alpha*g);
iffx0>fx1+tolfun&fx1<fx2‐tolfun%fx0>fx1<fx2
den=4*fx1‐2*fx0‐2*fx2;
num=den‐fx0+fx2;%
alpha=alpha*num/den;Pt.(1)
x=
x‐alpha*g;
fx=feval(f,x);%Pt.(2)
break;
else
alpha=alpha/2;
end
end
ifk1>=kmax1
warning=warning+1;%kgtimduocbuoctoiuu
else
warning=0;
end
ifwarning>=2|(norm(x‐x0)<tolx&abs(fx‐fx0)<tolfun)
break;
end
x0=x;
fx0=fx;
end
xo=x;fo=fx;
382
ifk==maxiter
fprintf(ʹDaylaketquatotnhatsau%dlanlapʹ,maxiter)
end
functiong=grad(func,x)
%Tinhgradientcuahamf(x).
h=1.0e‐6;
n=length(x);
g=zeros(1,n);
f0=feval(func,x);
fori=1:n
temp=x(i);
x(i)=temp+h;
f1=feval(func,x);
x(i)=temp;
g(1,i)=
(f1‐f0)/h;
end
Đểtìmcựctiểucủahàmtadùngchươngtrình
ctsteepest.m:
clearall,clc
f=inline(ʹx(1)*x(1)‐x(1)*x(2)‐4*x(1)+x(2)*x(2)‐x(2)ʹ);
x0=[0.50.5];
tolx=1e‐4;
tolfun=1e‐9;
alpha0=1;
maxiter=100;
[xo,fo]=steepest(f,x0,tolx,tolfun,alpha0,maxiter)
§6.PHƯƠNGPHÁPNEWTON
Việctìmđiểmcựctiểucủahàmf(x)tươngđươngvớiviệcxácđịnhxđể
chogradientg(x)củahàmf(x)bằngzero.Nghiệmcủag(x)=0cóth ểtìmđược
bằngcáchdùngphương
phápNewtonchohệphươngtrình phituyến.Hàm
newtons(x)dùngđểtìmnghiệmcủaphươngtrìnhg(x)=0là:
function[x,fx,xx]=newtons(f,x0,tolx,maxiter)
383
h=1e‐4;
tolfun=eps;
EPS=1e‐6;
fx=feval(f,x0);
nf=length(fx);
nx=length(x0);
ifnf~=nx
error(ʹKichthuoccuagvax0khongtuongthich!ʹ);
end
ifnargin<4
maxiter=100;
end
ifnargin<3
tolx=EPS;
end
xx(1,:)=x0(:).ʹ;
fork=1:maxiter
dx=‐jacob(f,xx(k,:),h)\fx(:);%‐[dfdx]ˆ‐1*fx
xx(k+1,:)=xx(k,:)+dx.ʹ;
fx=feval(f,xx(k+1,:));
fxn=norm(fx);
iffxn<tolfun|norm(dx)
<tolx
break;
end
end
x=xx(k+1,:);
ifk==maxiter
fprintf(ʹKetquatotnhatsau%dlanlap\nʹ,maxiter)
end
functiong=jacob(f,x,h)%Jacobiancuaf(x)
ifnargin<3
h=1e‐4;
end
h2=2*h;
n=length(x);
Đăng ký:
Đăng Nhận xét (Atom)
Không có nhận xét nào:
Đăng nhận xét