Chương 5. Chương trình Matlab và một số ví dụ minh họa
5.3. Một số ví dụ minh họa
Ví dụ 5.1. Tìm điểm cực tiểu của hàm số f : R2 → R xác định bởi f(x1, x2) = 1
2x21 + a 2x22, với a ≥1.
Xét điểm xuất phát x0 = (a,1)T. Khi đó ta có f(x1, x2) = 1
2(x1, x2)T 1 0 0 a
! x1 x2
! . Ta có ma trận
Q = 1 0 0 a
!
và ∇f(x)T = (x1, ax2). Bằng quy nạp ta sẽ chứng minh xk =
a−1 a+ 1
k
a (−1)k
!
. (5.1)
Thật vậy, với k = 0, đẳng thức trên đúng. Giả sử đẳng thức đúng với k, ta sẽ chứng minh nó cũng đúng với k + 1. Ta có:
∇f(xk) =
a−1 a+ 1
k
a (−1)ka
! . Vì thế,
xk+1 =
a−1 a+ 1
k
a (−1)k
!
−αk
a−1 a+ 1
k
a (−1)ka
!
=
a−1 a+ 1
k
a(1−αk) (−1)k(1−aαk)
! , với αk là điểm cực tiểu của hàm số
φk(α) = f(xk−α∇f(x)) = 1 2
a−1 a+ 1
2k
a2(1−α)2 +a(1−aα)2. Đây làm hàm bậc hai nên đạt giá trị nhỏ nhất tại
αk = 2 a+ 1. Do đó, ta có
xk =
a−1 a+ 1
k+1
a (−1)k+1
! .
Ví dụ 5.2. Tìm cực tiểu của bài toán tối ưu bậc hai f : R3 → R được cho bởi :
f(x) = 1
2xTQx−xTb, với
Q=
0,78 −0,02 −0,12 −0,14
−0,02 0,86 −0,04 0,06
−0,12 −0,04 0,72 −0,08
−0,14 0,06 −0,08 0,74
và b=
0,76 0,08 1,12 0,68
.
Vì Q là ma trận đối xứng xác định dương nên f lồi chặt. Do đó theo Bổ đề 2.1 và Định lý 2.5, nghiệm x∗ của bài toán thỏa mãn:
∇f(x∗) = 0, hay
Qx∗ = b.
Suy ra
x∗ = Q−1b ≈
1,5350 0,1220 1,9752 1,4130
.
Khi đó: f(x∗) ≈ −2.1747.
Bây giờ chúng ta sẽ giải bài toán bằng Giải thuật (3.103). Ta có : xk+1 = xk−αk∇f(xk), với:
∇f(xk) = Qxk −b và αk = gkTgk gkTQgk
= ∇f(xk)T∇f(xk)
∇f(xk)TQ∇f(xk). Với x0 = (0,0,0,0)T, ta có:
f(x0) = 0, ∇f(x0)T = Qx0 −b = (−0,76;−0,08;−1,12; 0,68).
α0 ≈ 0,5334.
x1 = x0 −α0∇f(x0) ≈ 1,4246; 0,1500; 2,0994; 1,2746 T
f(x1) ≈ −2,1564.
Cứ tiếp tục như vậy ta được bảng sau:
Bước k f(xk) E(xk) ff(x(xk)−f(x∗)
k−1)−f(x∗)
0 0 0,0042
1 −2,1564 0,0183 0,0166
2 −2,1744 2,5304×10−4 0,0038 3 −2,1746 1,5428×10−5 0,0011 4 −2,1747 1,0032×10−6 2,4844×10−4 5 −2,1747 6,6080×10−8 7,5391×10−5 6 −2,1747 4,3568×10−9 1,6354×10−5 Khi đó, ta được nghiệm:
x∗ ≈ (1,5350; 0,1220; 1,9752; 1,4130)T và f(x∗) ≈ −2.1747. Chương trình Matlab cho ví dụ này như sau:
% Định nghĩa hàm mục tiêu, ma trận Q, véctơ b
Q=[0.78 -0.02 -0.12 -0.14;...
-0.02 0.86 -0.04 0.06;...
-0.12 -0.04 0.72 -0.08;...
-0.14 0.06 -0.08 0.74];
b=[0.76;0.08;1.12;0.68];
f=@(x) x’*Q*x/2-b’*x;
% Chọn giá trị khởi tạo;
x0=zeros(4,1);
xstar=[1.534965034965035;...
0.122009569377990;...
1.975156422524844;...
1.412955465587045];
% Lưu thông tin dãy x_n và f(x_n) xn=[];
fn=[];
Error=[];
% Chọn giá trị n cho vòng lặp n=50;
for i=1:n
xn=[xn x0];
tg=(x0-xstar)’*Q*(x0-xstar)/2;
Error=[Error tg];
tg=f(x0);
fn=[fn tg];
gk=Q*x0-b;
ak=gk’*gk/(gk’*Q*gk);
x1=x0-ak*gk;
x0=x1;
end
Ví dụ 5.3. Tìm cực tiểu của bài toán tối ưu bậc hai f : R3 → R xác định bởi:
f(x) = 1
2xTQx−bTx, trong đó
Q =
1 0 0 0 5 0 0 0 25
và b =
−1
−1
−1
.
Tương tự như Ví dụ 5.2, theo Bổ đề 2.1 và Định lý 2.5, ta có cực tiểu của
bài toán là
x∗ =
−1,00
−0,20
−0,04
và f(x∗) = −0.620000.
Bây giờ, ta sẽ giải bài toán bằng Giải thuật (3.103).
Ta có : xk+1 = xk −αk∇f(xk), với:
∇f(xk) =Qxk −b và α = gkTgk gTkQgk
= ∇f(xk)T∇f(xk)
∇f(xk)TQ∇f(xk). Với x0 = (0,0,0)T, ta có:
f(x0) = 0, ∇f(x0) =Qx0 −b = (1; 1; 1)T, α0 = 0,096774.
⇒x1 = x0 −α0∇f(x0) =
−0,0967744
−0,0967744
−0,0967744
⇒f(x1) = −0,1452.
Với x1 = (−0,0968;−0,0968;−0,0968)T, ta có:
∇f(x1) = Qx1 −b= (0,9032; 0,5162;−1,1494)T, α1 = 0,0590.
⇒ x2 = x1 −α1∇f(x1) =
−0,1500
−0,1272
−0,0131
.
⇒ f(x2) = −0,2365.
Bước k f(xk) E(xk) ff(x(xk)−f(x∗)
k−1)−f(x∗)
0 0 0,6200
1 −0,1452 0,4748 0,3829
2 −0,2365 0,3835 0,3704
3 −0,3038 0,3162 0,4708
4 −0,3560 0,2640 0,3551
5 −0,3988 0,2212 0,4355
6 −0,4343 0,1857 0,3368
200 −0,6200 4,3116×10−16 3,9660×10−8 Sau 200 bước lặp ta thu được:
x200 = −1.0000;−0,2000;−0,0400
T
. Vậy nghiệm của bài toán là x∗ ≈ x200 và f(x∗) =−0,6200.
Chương trình Matlab cho ví dụ này như sau:
% Định nghĩa hàm mục tiêu, MT Hesian, véctơ b Q=[1 0 0;...
0 5 0;...
0 0 25];
b=-ones(3,1);
f=@(x) x’*Q*x/2-b’*x;
% Chọn giá trị khởi tạo cho vòng lặp x0=zeros(3,1);
xstar=[-1.00;-0.20;-0.04];
% Lưu thông tin dãy x_n và f(x_n) xn=[];
fn=[];
Error=[];
% Chọn giá trị n cho vòng lặp n=200;
for i=1:n
xn=[xn x0];
tg=(x0-xstar)’*Q*(x0-xstar)/2;
Error=[Error tg];
tg=f(x0);
fn=[fn tg];
gk=Q*x0-b;
ak=gk’*gk/(gk’*Q*gk);
x1=x0-ak*gk;
x0=x1;
end
Đối với các bài toán tối ưu không phải dạng bậc hai, như đã nói ở phần lý thuyết, việc tính toán chính xác giá trị αk là một điều không dễ dàng, chính vì vậy chúng ta cần dùng các phương pháp tính gần đúng. Sau đây chúng ta sẽ xét một ví dụ để thấy rõ điều này:
Ví dụ 5.4. Tìm cực tiểu của hàm số f : R3 → R xác định bởi:
f(x1, x2, x3) = (x1 −4)4 + (x2 −3)2 + 4(x3 + 5)4, với x1, x2, x3 ∈ R.
Cách 1: Sử dụng chương trình Matlab với quy tắc Armijo đã nêu ở trên ta có chương trình sau:
x0=[0;0;0];
f=@(x) (x(1)-4)^4+(x(2)-3)^2+4*(x(3)+5)^4;
gradf=@(x) [4*(x(1)-4)^3;2*(x(2)-3);16*(x(3)+5)^3];
x=[x0]; F=[f(x0)]; eps=1/2;nu=2;
n=50;
for i=1:n
an=1; tg=gradf(x0);x1=x0-an*tg;
if f(x1)<=f(x0)-eps*tg’*tg*an
while f(x1)<=f(x0)-eps*tg*tg’*an an=an*nu; x1=x0-an*tg;
end else
while f(x1)>f(x0)-eps*tg*tg’*an an=an/nu; x1=x0-an*tg;
end end
x0=x1; x=[x x1]; F=[F f(x1)];
end
Lúc đó, ta có bảng sau:
Bước k xk f(xk)
0 (0,0,0)T 2765
1 (0,2500; 0,0059;−1.9531)T 5,5145×102 2 (0,6620; 0,0176;−2,8370)T 2,2059×102 3 (1,2431; 0,0409;−3,4695)T 88,4700 4 (1,8979; 0,0871;−3,9176)T 33,5002 5 (2,4785; 0,1781;−4,2346)T 14,695270 6 (2,9188; 0,3545;−4,4588)T 8,7086 15 (3,9999; 3,0000;−5,0000)T 1,0966×10−17 50 (4,0000; 3,0000;−5.0000)T 1,1627×10−23 Từ bảng trên ta thấy nghiệm của bài toán là xấp xỉ:
x∗ ≈ (4,3,−5)T và f(x∗) = 0.
Cách 2:Sử dụng chương trình Matlab với quy tắc Golstein đã nêu ở trên ta có chương trình sau:
x0=[0;0;0];
f=@(x) (x(1)-4)^4+(x(2)-3)^2+4*(x(3)+5)^4;
gradf=@(x) [4*(x(1)-4)^3;2*(x(2)-3);16*(x(3)+5)^3];
x=[x0];F=[f(x0)]; eps=1/2;nu=2;
n=50;
for i=1:n
an=1;tg=gradf(x0);x1=x0-an*tg;
if f(x1)<=f(x0)-eps*tg’*tg*an
while f(x1)<=f(x0)-eps*tg*tg’*an an=an*nu;x1=x0-an*tg;
end else
while f(x1)>f(x0)-(1-eps)*tg*tg’*an an=an/nu;x1=x0-an*tg;
end end
x0=x1;x=[x x1];F=[F f(x1)];
end
Lúc đó, ta có bảng sau:
Bước k xk f(xk)
0 (0,0,0)T 2765
1 (0,2500; 0,0059;−1.9531)T 5,5145×102 2 (0,6620; 0,0176;−2,8370)T 2,2059×102 3 (1,2431; 0,0409;−3,4695)T 88,4700 4 (1,8979; 0,0871;−3,9176)T 33,5002 5 (2,4785; 0,1781;−4,2346)T 14,6953 6 (2,9188; 0,3545;−4,4588)T 8,7086 15 (3,9999; 3,0000;−5,0000)T 1.0966×10−17 50 (4,0000; 3,0000;−5.0000)T 1.1627×10−23 Từ bảng trên ta thấy nghiệm của bài toán là xấp xỉ:
x∗ ≈ (4,3,−5)T và f(x∗) = 0.
[1] K. Bredies, D. A. Lorenz, and P. Maass. A generalized conditional gra- dient method and its connection to an iterative shrinkage method. Com- putational Optimization and Application, 42(2):173–193, 2009.
[2] I. Daubechies, M. Defrise, and C. Demol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Comm.
Pure Appl. Math, 57:1413–1541, 2004.
[3] Ivar Ekeland and Roger Temam. Convex analysis and variational prob- lems, volume 28. Siam, 1999.
[4] M. Grasmair, M. Haltmeier, and O. Scherer. Sparsity regularization with lq penalty term. Inverse Problems, 24:055020, 2008.
[5] Werner H Greub.Linear algebra, volume 23. Springer Science & Business Media, 2012.
[6] R. Griesse and D. A. Lorenz. A semismooth Newton method for Tikhonov functionals with sparsity constraints. Inverse Problems, 24:035007, 2008.
[7] D. N. Hào and T. N. T. Quyen. Convergence rates for total variation regularization of coefficient identification problems in elliptic equations I. Inverse Problems, 27:075008, 2011.
[8] D.N. Hào and T.N.T. Quyen. Convergence rates for Tikhonov regular- ization of a two-coefficient identification problem in an elliptic boundary value problem. Numerische Mathematik, 120(1):45–77, 2012.
[9] Witold AJ Kosmala. A friendly introduction to analysis. Pearson Pren- tice Hall, 2004.
[10] D. A. Lorenz, P. Maass, and P. Q. Muoi. Gradient descent methods based on quadratic approximations of Tikhonov functionals with sparsity con- straints: theory and numerical comparison of stepsize rules. Electronic Transactions on Numerical Analysis, 39:437–463, 2012.
[11] Pham Quy Muoi, Dinh Nho Hào, Peter Maass, and Michael Pidcock.
Descent gradient methods for nonsmooth minimization problems in ill- posed problems. Journal of Computational and Applied Mathematics, 298:105–122, 2016.
[12] Pham Quy Muoi and Duong Xuan Hiep. Proximal algorithm for min- imization problems in l0-regularization for nonlinear inverse problems.
Numerical Algorithms, pages 1–22, 2022.