Xem mẫu
- CHƯƠNG 8: TỐI ƯU HOÁ
§1. KHÁI NIỆM CHUNG VỀ TỐI ƯU HOÁ
Tối ưu hoá là thuật ngữ thường được dùng để cực tiểu hoá hay cực đại
hoá một hàm. Thông thường ta chỉ cần tìm cực tiểu một hàm là đủ. Việc tìm
cực đại của f(x) thực hiện một cách đơn giản bằng cách tìm cực tiểu của hàm
−f(x) . Hàm f là hàm giá trị hay hàm đối tượng, cần được giữ cực tiểu. Biến x
là biến có thể hiệu chỉnh tự do.
Các thuật toán cực tiểu hoá là các thủ thuật lặp đòi hỏi một giá trị ban
đầu của biến x. Nếu f(x) có nhiều cực tiểu địa phương, việc chọn giá trị đầu sẽ
xác định cực tiểu nào được tính. Ta không có cách nào bảo đảm là tìm được
cực tiểu toàn cục.
Các biến có thể bị ràng buộc bằng các đẳng thức hay bất đẳng thức.
Phần lớn các phương pháp là tìm cực tiểu không ràng buộc, nghĩa là không có
hạn chế nào đối với biến x. Các bài toán này bao gồm tìm cực tiểu của hàm,
tìm điểm tĩnh ‐ điểm có gradient triệt tiêu. Các bài toán tìm cực tiểu có ràng
buộc khó hơn và thuật toán khá phức tạp.
Trong chương này chúng ta sẽ lần lượt xét các thuật toán tìm cực tiểu
không ràng buộc và có ràng buộc.
§2. PHƯƠNG PHÁP TIẾT DIỆN VÀNG
Ta xét bài toán tìm cực tiểu của hàm một biến f(x). Điểm cực tiểu được
xác định theo điều kiện df/dx = 0. Do có thể có nhiều điểm cực tiểu nên ta
phải vây điểm cực tiểu(xác định lân cận chứa điểm cực tiểu) trước. Thủ thuật
vây điểm cực tiểu khá đơn giản: cho điểm đầu x0 và tính giá trị của hàm đang
đi xuống tại các điểm tiếp theo x1, x2, x3,... cho đến tại xn hàm tăng lại thì
dừng. Điểm cực tiểu bị vây trong khoảng (xn‐2, xn). Khoảng (xi+1, xi) không nên
chọn là hằng số vì như vậy cần nhiều bước tính. Hợp lí nhất là nên tăng kích
thước bước tính để đạt được cực tiểu nhanh hơn, ngay cả khi cực tiểu bị vây
trong một đoạn khá rộng. Ta chọn kích thước tăng theo dạng hằng số:
h i+1 = ch i với c > 1 . ta xây dựng hàm goldbracket() để vây điểm cực tiểu của
hàm:
function [a, b] = goldbracket(func, x1, h)
% vay diem cuc tieu cua f(x).
c = 1.618033989;
370
- f1 = feval(func, x1);
x2 = x1 + h;
f2 = feval(func,x2);
if f2 > f1
h = ‐h;
x2 = x1 + h;
f2 = feval(func, x2);
if f2 > f1
a = x2;
b = x1 ‐ h;
return
end
end
for i = 1:100
h = c*h;
x3 = x2 + h;
f3 = feval(func, x3);
if f3 > f2
a = x1;
b = x3;
return
end
x1 = x2;
f1 = f2;
x2 = x3;
f2 = f3;
end
error(ʹGoldbracket khong tim thay diem cuc tieuʹ)
Tiết diện vàng là một biến thể của phương pháp chia đôi dùng khi tìm
nghiệm của phương trình f(x) = 0. Giả sử điểm cực tiểu bị vây trong khoảng
(a, b) có độ dài h. Để thu nhỏ khoảng (a, b) ta tính giá trị của hàm tại
x1 = b − rh và x 2 = a + rh như hình vẽ. Nếu f1 = f(x1) lớn hơn f2 = f(x2) như hình
a thì cực tiểu nằm trong khoảng (x1, b) nếu ngược lại cực tiểu nằm trong
khoảng (a, x2).
371
- Giả sử f1 > f2 , ta đặt a = x1 và và x1 =
x2 và có khoảng (a, b) mới như hình b. Để
2rh‐h
thực hiện bước thu gọn tiếp theo ta lại
rh
tính giá trị của hàm tại x2 = a + rh’ và lặp rh
lại quá trình. Quá trình làm việc chỉ nếu
a x1 x2 b
hình a và hình b tương tự, nghĩa là hằng
h
số r không đổi khi xác định x1 và x2 ở cả
hai hình. Từ hình a ta thấy: a
x 2 − x1 = 2rh − h
Cùng một khoảng cách đó từ hình b ta có: rh’
x1 ‐ a = h’ ‐ rh’ rh’
Cân bằng các khoảng này ta được:
a x1 x2 b
2rh ‐ h = h’ ‐ rh’
Thay h’ = rh và khử h: h’
2r ‐ 1 = r(1 ‐ r) b
Giải phương trình này ta nhận được tỉ lệ vàng:
5 −1
r= = 0.618033989...
2
Chú ý là mỗi lần thu gọn khoảng chứa điểm cực tiểu thì khoảng (a, b) giảm tỉ
lệ với r. Điều này làm số lần tính lớn hơn phương pháp chia đôi. Tuy nhiên
phương pháp tỉ lệ vàng chỉ đòi hỏi tính giá trị hàm một lần trong khi phương
pháp chia đôi cần tính giá trị hàm 2 lần. Số lần tính xác định bằng:
b − a rn = ε
ε
ln
b−a ε
hay: n = = −2.078087 n
ln b−a
h = b ‐ a = 0.382
Ta xây dựng hàm golden() để thực hiện thuật toán này:
function [xmin, ymin] = golden(f, a, b, delta, epsilon)
% a va b la doan tim cuc tieu
% delta sai so cua x
% epsilon sai so cua y
r1 = (sqrt(5) ‐ 1)/2;
r2 = r1^2;
h = b ‐ a;
372
- fa = f(a);
fb = f(b);
x1 = a + r2*h;
x2 = a + r1*h;
f1 = f(x1);
f2 = f(x2);
k = 1;
while (abs(fb‐fa) > epsilon)|(h > delta)
k = k + 1;
if (f1
- ymin = yp;
Để tìm cực tiểu của hàm ta dùng chương trình ctgolden.m:
clear all, 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ƯƠNG PHÁP XẤP XỈ BẬC HAI
Ý tưởng của phương pháp này là:
‐ xấp xỉ hàm đối tượng f(x) bằng một hàm bậc 2 p2(x) qua 3 điểm cho
trước
‐ cập nhật 3 điểm này bằng cách thay một trong 3 điểm bằng cực tiểu
của hàm p2(x)
Qua 3 điểm:
{[(x0 ,f(x0 )] , [(x1 ,f(x1 )] , [(x2 ,f(x2 )]} x0
-
Ta xây dựng hàm optquad() để thực hiện thuật toán này.
function [xo, fo] = optquad(f, x0, tolx, tolfun, maxiter)
%Tim cuc tieu cua f(x) bang phuong phap xap xi bac 2
if length(x0) > 2
x012 = x0(1:3);
else
if length(x0) == 2
a = x0(1);
b = x0(2);
else
a = x0 ‐ 10;
b = x0 + 10;
end
x012 = [a (a + b)/2 b];
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);
375
- f0 = f012(1);
f1 = f012(2);
f2 = f012(3);
nd = [f0 ‐ f2 f1 ‐ f0 f2 ‐ f1]*[x1*x1 x2*x2 x0*x0; x1 x2 x0]ʹ;
x3 = nd(1)/2/nd(2);
f3 = feval(f, x3); %Pt.(1)
if k
- %f = inline(ʹ(x.^2 ‐ 4).^2/8 ‐ 1ʹ);
a = 0;
b = 3;
delta = 1e‐8;
epsilon = 1e‐10;
maxiter = 100;
[xmin, ymin] = optquad(f, [a b], delta, epsilon, maxiter)
§4. PHƯƠNG PHÁP NELDER ‐ MEAD
Phương pháp Nelder ‐ Mead có thể dùng để tìm cực tiểu của hàm nhiều
biến mà phương pháp tiết diện vàng hay phương pháp xấp xỉ bậc 2 không
dùng được. Thuật toán Nelder ‐ Mead gồm các bước như sau:
Bước 1: Cho 3 điểm đầu tiên a, b, c với f(a)
- if n == 1 %truong hop ham 1 bien
[xo,fo] = optquad(f, x0, tolx, tolfun);
return
end
S = eye(n);
for i = 1:n
i1 = i + 1;
if i1 > 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);
if n
- m = (a + b)/2;
e = 3*m ‐ 2*c;
fe = feval(f, e);
if fe
- b = 1;
delta = 1e‐8;
epsilon = 1e‐10;
maxiter = 100;
[xmin, ymin] = neldermead(f, x0, delta, epsilon, maxiter)
§5. PHƯƠNG PHÁP ĐỘ DỐC LỚN NHẤ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:
⎡ ∂f(x) ∂f(x) ∂f(x) ⎤
−g([ x ]) = −∇f([ x ]) = − ⎢ L
⎣ ∂x1 ∂x 2 ∂x n ⎥
⎦
với kích thước bước tính αk tại lần lặp thứ k được hiệu chỉnh sao cho giá trị
hàm cực tiểu theo hướng tìm. Thuật toán gồm các bước sau:
• Tại lần lặp thứ k = 0, tìm giá trị hàm f(x0) với điểm khởi đầu x0
• Tại lần lặp thứ k, tìm αk theo hướng ‐g(x)
α k −1 = f ( x k−1 − αg k−1 / g k−1 ) (1)
• Tính giá trị xk:
x k = x k −1 − α k −1g k−1 / g k−1 (2)
• Nếu xk ≈ xk‐1 và f(xk) ≈ f(xk‐1) thì coi là cực tiểu, nếu không thì quay về
bước 2.
function [xo, fo] = steepest(f, x0, tolx, tolfun, alpha0,maxiter)
if nargin
- fx0 = feval(f, x0);
fx = fx0;
alpha = alpha0;
kmax1 = 25;
warning = 0;
for k = 1:maxiter
g = grad(f, x);
g = g/norm(g); %gradient la vec to hang
alpha = alpha*2; %de thu di theo huong gradient am
fx1 = feval(f, x ‐ alpha*2*g);
for k1 = 1:kmax1 %tim buoc toi uu
fx2 = fx1;
fx1 = feval(f, x ‐ alpha*g);
if fx0 > fx1+ tolfun & fx1 fx1 = kmax1
warning = warning + 1; %kg tim duoc buoc toi uu
else
warning = 0;
end
if warning >= 2|(norm(x ‐ x0)
- if k ==maxiter
fprintf(ʹDay la ket qua tot nhat sau %d lan lapʹ, maxiter)
end
function g = grad(func, x)
% Tinh gradient cua ham f(x).
h = 1.0e‐6;
n = length(x);
g = zeros(1, n);
f0 = feval(func, x);
for i = 1:n
temp = x(i);
x(i) = temp + h;
f1 = feval(func, x);
x(i) = temp;
g(1, i) = (f1 ‐ f0)/h;
end
Để tìm cực tiểu của hàm ta dùng chương trình ctsteepest.m:
clear all, clc
f = inline(ʹx(1)*x(1) ‐ x(1)*x(2) ‐ 4*x(1) + x(2) *x(2) ‐ x(2)ʹ);
x0 = [0.5 0.5];
tolx = 1e‐4;
tolfun = 1e‐9;
alpha0 = 1;
maxiter = 100;
[xo, fo] = steepest(f, x0, tolx, tolfun, alpha0, maxiter)
§6. PHƯƠNG PHÁP NEWTON
Việc tìm điểm cực tiểu của hàm f(x) tương đương với việc xác định x để
cho gradient g(x) của hàm f(x) bằng zero. Nghiệm của g(x) = 0 có thể tìm được
bằng cách dùng phương pháp Newton cho hệ phương trình phi tuyến. Hàm
newtons(x) dùng để tìm nghiệm của phương trình g(x) = 0 là:
function [x, fx, xx] = newtons(f, x0, tolx, maxiter)
382
- h = 1e‐4;
tolfun = eps;
EPS = 1e‐6;
fx = feval(f, x0);
nf = length(fx);
nx = length(x0);
if nf ~= nx
error(ʹKich thuoc cua g va x0 khong tuong thich!ʹ);
end
if nargin
- x = x(:).ʹ;
I = eye(n);
for n = 1:n
g(:, n) = (feval(f, x + I(n, :)*h) ‐ feval(f, x ‐ I(n,:)*h))ʹ/h2;
end
Để tìm cực tiểu của hàm bằng phương pháp Newtons ta dùng chương trình
ctnewtons.m:
clear all, clc
f = inline(ʹx(1).^2 ‐ x(1)*x(2) ‐ 4*x(1) + x(2).^2 ‐ x(2)ʹ);
g = inline(ʹ[(2*x(1) ‐ x(2) ‐4) ( 2*x(2) ‐ x(1) ‐ 1)]ʹ);
x0 = [0.1 0.1];
tolx = 1e‐4;
maxiter = 100;
[xo, fo] = newtons(g, x0, tolx, maxiter)
§7. PHƯƠNG PHÁP GRADIENT LIÊN HỢP
1. Khái niệm chung: Một trong các phương pháp giải bài tón tìm cực tiểu của
hàm nhiều biến là tìm cực tiểu theo một biến liên tiếp để đến gần điểm cực
tiểu. Chiến thuật chung là:
• chọn điểm [x0]
• lặp với i = 1, 2, 3,...
‐ chọn vec tơ [vi]
‐ cực tiểu hoá f([x]) dọc theo đường [xi‐1] theo hướng [vi]. Coi [xi]
là cực tiểu. Nếu [ xi ] − [ xi−1 ] < ε thì kết thúc lặp
• kết thúc
2. Gradient liên hợp: Ta khảo sát hàm bậc 2:
1 1 T
f ([ x ]) = c − ∑ bi xi + ∑∑ A i ,jxi x j = c − [ b] [ x ] + [ x ] [ A ][ x ]
T
(1)
i 2 i j 2
đạo hàm của hàm theo xi cho ta:
∂f
= − bi + ∑ A i ,jx j
∂x i j
Viết dưới dạng vec tơ ta có:
∇f = − [ b ] + [ A ][ x ] (2)
384
- với ∇f là gradient của f.
Bây giờ ta khảo sát sự thay đổi gradient khi ta di chuyển từ [x0] theo
hướng của vec tơ [u] dọc theo đường:
[x] = [x0] + s[u]
với s là khoảng cách di chuyển. Thay biểu thức này vào (2) ta có gradient dọc
theo [u]:
∇f [x0 ]+s[u] = − [ b ] + [ A ] ([ x0 ] + s [ u ]) = ∇f [x0 ] + s [ A ][ u ]
Như vậy sự thay đổi gradient là s[A][u]. Nếu ta di chuyển theo hướng vuông
góc với vec tơ [v], nghĩa là
[v]T[u] = 0 hay [v]T[A][u] = 0 (3)
thì hướng của [u] và [v] là liên hợp. Điều này cho thấy khi ta muốn cực tiểu
hoá f(x) theo hướng [v], ta cần di chuyển theo hướng [u] để không làm hỏng
cực tiểu trước đó. Với hàm bậc hai n biến độc lập ta có thể xây dựng n hướng
liên hợp. Các phương pháp gradient liên hợp khác nhau dùng các kỹ thuật
khác nhau để tìm hướng liên hợp.
3. Phương pháp Powell: Phương pháp Powell là phương pháp bậc zero, chỉ
đòi hỏi tính f([x]). Thuật toán gồm các bước:
• chọn điểm [x0]
• chọn vec tơ [vi], thường lấy [vi] = [ei] với [ei] là vec tơ đơn vị theo
hướng [xi]
• vòng tròn
‐ lặp với i = 1, 2,...
∗ tìm cực tiểu của f([x]) dọc theo đường đi qua [xi‐1] theo
hướng [vi]; coi [xi] là cực tiểu
‐ kết thúc lặp
‐ [vn+1] = [x0] ‐ [xn]; tìm cực tiểu của f([x]) dọc theo đường đi qua[x0]
theo hướng [vn+1]; coi [xn+1] là cực tiểu
‐ nếu [ x n +1 ] − [ x n ] < ε thì kết thúc vòng lặp
‐ lặp
∗ [vi+1] = [v]
• kết thúc vòng tròn
Ta xây dựng hàm powell() để thực hiện thuật toán trên:
function [xmin, fmin, ncyc] = powell(h, tol)
% Phuong phap Powell de tim cuc tieu cua ham f(x1,x2,...,xn).
385
- global x func v
if nargin
- imax = i;
dfmax = df(i);
end
end
for i = imax:n‐1
u(1:n, i) = u(1:n, i+1);
end
u(1:n, n) = v;
end
error(ʹPhuong phap Powell khong hoi tuʹ)
function z = fiine(s) % f theo huong cua v
global x func v
z = feval(func, x+s*v);
function y = f(x)
y = 100.0*(x(2) ‐ x(1).^2).^2 + (1.0 ‐ x(1)).^2;
Để tìm điểm cực tiểu ta dùng chương trình ctpowell.m:
clear all, clc
global x func
func = @f;
x = [‐1.0; 1.0];
[xmin, fmin, numcycles] = powell
fminsearch(func, x)
3. Phương pháp Fletcher ‐ Reeves: Phương pháp Powell cần n đường cực tiểu
hoá. Ta có thể chỉ cần dùng một đường với phương pháp bậc 1. Phương pháp
này có 2 phương án: thuật toán Fletcher ‐ Reeves(FR) và thuật toán Polak ‐
Ribiere(PR). Thuật toán tóm tắt như sau:
‐ cho [x0], tính f([x0])
‐ khởi gán x(n) = xk; tính [g0] = ‐∇f([x0]); s(k) = ‐ g(xk)
‐ lặp k = 0, 1, 2,...
• [xk+1] = [xk] + αk[sk]
387
- • βk =
([g k +1 ] −[g k ] )[g k+1 ]
T T
(FR) hay βk =
[g k+1 ] [g k+1 ] (PR)
T
[g k ] [g k ] [g k ] [g k ]
T T
• [ s k+1 ] = − [g k +1 ] + βk [ s k ]
• cập nhật [xk]
cho đến khi hội tụ
Ta xây dựng hàm conjugate() để thực hiện thuật toán trên:
function [xo, fo] = conjugate(f, x0, tolx, tolfun, alpha0, maxiter, KC)
%KC = 1: Phuong phap gradient lien hop Polak–Ribiere
%KC = 2: Phuong phap gradient lien hop Fletcher–Reeves
if nargin
- alpha = alpha0;
g = grad(f, x);
s = ‐g;
for n = 1:n
alpha = alpha0;
fx1 = feval(f, x + alpha*2*s);
for n1 = 1:nmax1
fx2 = fx1;
fx1 = feval(f, x+alpha*s);
if (fx0 > fx1 + tolfun) & ( fx1 fx1
nguon tai.lieu . vn
