ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
PHẠM THỊ MINH THUẬN
PHƯƠNG PHÁP GRADIENT
LIÊN HỢP VÀ ỨNG DỤNG
LUẬN VĂN THẠC SỸ TOÁN HỌC
THÁI NGUYÊN - NĂM 2010
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
PHẠM THỊ MINH THUẬN
PHƯƠNG PHÁP GRADIENT
LIÊN HỢP VÀ ỨNG DỤNG
LUẬN VĂN THẠC SỸ TOÁN HỌC
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.36
Người hướng dẫn khoa học:
GS. TS. TRẦN VŨ THIỆU
THÁI NGUYÊN - NĂM 2010
i
Mục lục
Mở đầu 1
1 Cơ sở toán học của phương pháp và các khái niệm liên
quan 3
1.1 Một số khái niệm và kết quả cơ bản của giải tích lồi . . . 3
1.2 Phương pháp hướng giảm . . . . . . . . . . . . . . . . . 7
1.2.1 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . 7
1.2.2 Hướng giảm . . . . . . . . . . . . . . . . . . . . . 9
1.2.3 Độ dài bước . . . . . . . . . . . . . . . . . . . . . 11
1.3 Phương pháp gradient . . . . . . . . . . . . . . . . . . . 13
1.3.1 Thuật toán gradient với thủ tục tìm chính xác theo
tia . . . . . . . . . . . . . . . . . . . . . . . . . . 13

của các nhà nghiên cứu.
Luận văn này đề cập tới phương pháp gradient liên hợp và ứng dụng
của nó. Phương pháp gradient liên hợp được Hestenes và Stiefel nêu ra
đầu tiên vào những năm 1950 để giải hệ tuyến tính. Vì việc giải một hệ
tuyến tính tương đương với tìm cực tiểu của một hàm toàn phương xác
định dương, nên vào năm 1960 Fletcher - Reeves đã cải biên và phát
triển nó thành phương pháp gradient liên hợp cho cực tiểu không ràng
buộc. Nhờ đó phương pháp này hoàn thiện phương pháp giảm nhanh
nhất nhằm làm tăng hiệu quả và độ tin cậy của thuật toán. Phương pháp
gradient liên hợp là trung gian giữa phương pháp gradient và phương
pháp Newton, nó thay đổi hướng tìm trong phương pháp gradient bằng
cách thêm vào một tỷ lệ dương của hướng dùng ở bước ngay trước đó.
Phương pháp này chỉ cần tới đạo hàm riêng bậc nhất nhưng lại khắc
phục được tính hội tụ chậm của phương pháp gradient.
Mục tiêu của luận văn là tìm hiểu và trình bày những kết quả cơ bản
đã biết liên quan đến phương pháp gradient liên hợp, các tính chất như
tính liên hợp, tính trực giao, tính hội tụ và một số phương pháp mở rộng
của phương pháp này. Nội dung đề cập trong luận văn được trình bày
một cách chặt chẽ về mặt toán học kèm theo một số ví dụ minh họa.
Luận văn được chia làm 3 chương:
2
Chương 1: nhắc lại một số khái niệm cơ bản của giải tích lồi, như tập
lồi, hàm lồi và hàm toàn phương, hướng giảm và phương pháp gradient,
phương pháp Newton để phục vụ cho các chương tiếp theo.
Chương 2: trình bày các khái niệm, tính chất của hướng liên hợp,
phương pháp gradient liên hợp giải bài toán cực tiểu hàm toàn phương,
nêu các định lý về tính hội tụ của phương pháp gradient liên hợp và mở
rộng phương pháp này để tìm cực tiểu của một hàm khả vi liên tục bất
kỳ. Cuối chương tác giả nêu ra một số ví dụ áp dụng.
Chương 3: trình bày phương pháp gradient liên hợp 3-số hạng. Đó là

dựng các thuật toán giải các bài toán tối ưu, trước hết ta sẽ nhắc lại các
khái niệm tập lồi và hàm lồi.
Định nghĩa 1.1 (Tập lồi).
Cho hai điểm a, b ∈ R
n
, tập tất cả các điểm x = (1 − λ)a + λb với
0 ≤ λ ≤ 1 gọi là đoạn thẳng đóng nối a và b và được kí hiệu là [a, b].
Tập C ∈ R
n
được gọi là lồi nếu nó chứa mọi đoạn thẳng nối hai điểm
bất kỳ thuộc nó. Nói cách khác, nếu (1 −λ)a + λb ∈ C, ∀a, b ∈ C và mọi
0 ≤ λ ≤ 1.
Định nghĩa 1.2 (Hàm lồi).
Hàm f : X → [−∞, +∞] xác định trên tập lồi X ⊆ R
n
được gọi là lồi
nếu
f(λx
1
+ (1 − λ)x
2
) ≤ λf(x
1
) + (1 −λ)f(x
2
)
với bất kì x
1
, x
2

0
)| < ε với mọi x ∈ X thỏa mãn  x −x
0
< δ.
Nói cách khác, hàm f liên tục tại x
0
∈ X nếu với mọi dãy {x
n
} ⊂ X
hội tụ đến x
0
, ta có {f(x
n
)} → f(x
0
).
Hàm f được gọi là nửa liên tục dưới (t.ư., nửa liên tục trên) tại điểm
x
0
∈ X nếu tồn tại ε > 0, tồn tại δ > 0 sao cho
f(x) ≥ f(x
0
) −ε (t.ư., f(x) ≤ f(x
0
) + ε)
với mọi x ∈ X thỏa mãn  x − x
0
< δ. Nói cách khác, hàm f là nửa
liên tục dưới (t.ư., nửa liên tục trên) tại điểm x
0

trên Xnếu nó liên tục (t.ư., nửa liên tục dưới, nửa liên tục trên) tại mọi
điểm của X.
Định nghĩa 1.4. Giả sử f : R
n
→ [−∞, +∞] là hàm số tùy ý và C ⊂ R
n
là tập tùy ý.
Điểm x
0
∈ C ∩ domf được gọi là điểm cực tiểu toàn cục của f(x)
trên C nếu −∞ < f(x
0
) ≤ f(x) với mọi x ∈ C.
5
Điểm x
0
∈ C được gọi là điểm cực tiểu địa phương của f(x) trên C,
nếu tồn tại lân cận U(x
0
) của x
0
sao cho −∞ < f(x
0
) ≤ f(x) với mọi
x ∈ C ∩U(x
0
).
Các khái niệm cực đại địa phương và cực đại toàn cục được định nghĩa
tương tự. Đối với hàm f tùy ý trên tập C, ta ký hiệu tập tất cả các điểm
cực tiểu (cực đại) toàn cục của f trên C là Argmin

∃γ ∈ [0, 1), ∃k
0
sao cho ∀k > k
0
: x
k+1
− x
∗
≤ γ  x
k
− x
∗
,
hội tụ đến x
∗
với tốc độ trên tuyến tính nếu
∀k : x
k+1
− x
∗
≤ c
k
 x
k
− x
∗
 và c
k
→ 0,
hội tụ đến x

0
, d) = ∇f(x
0
), d , ∀d ∈ R
n
\ {0}.
Chứng minh. Vì f khả vi tại x
0
nên với mọi d ∈ R
n
\ {0} ta có
lim
t→0
+
f(x
0
+ td) −f(x
0
) −∇f(x
0
), td 
t  d 
= 0.
6
Do đó
f

(x
0
, d ) − ∇f(x

= f

(x
0
, d ).
Như vậy, đạo hàm theo hướng của f tại x
0
phản ánh tốc độ biến
thiên của f tại x
0
theo hướng đó. Hơn nữa, theo bất đẳng thức Cauchy-
Bunjakowski-Schwarz trong tất cả các hướng d ∈ R
n
có  d = 1, ta
có
|∇f(x
0
), d | ≤ ∇f(x
0
)  d = ∇f(x
0
) 
⇒ −  ∇f(x
0
) ≤ ∇f(x
0
), d  ≤ ∇f(x
0
)  .
Do đó, đạo hàm theo hướng của f tại x

n
.
Hàm f là lồi chặt trên X nếu ∇
2
f(x) xác định dương trên X, tức là với
mỗi x ∈ X,
y
T
∇
2
f(x)y > 0, ∀y ∈ R
n
\{0}.
ii) Hàm f là lõm trên X khi và chỉ khi ma trận Hessian ∇
2
f(x) là nửa
xác định âm trên X, tức là với mỗi x ∈ X,
y
T
∇
2
f(x)y ≤ 0, ∀y ∈ R
n
.
7
Hàm f là lõm chặt trên X nếu ∇
2
f(x) xác định âm trên X, tức là với
mỗi x ∈ X,
y

1.2.1 Điều kiện tối ưu
Định lí 1.2 (Điều kiện cần cấp 1).
Cho hàm f xác định, khả vi trên R
n
. Nếu x
∗
∈ R
n
là nghiệm cực tiểu địa
phương của bài toán (1.1) thì ∇f(x
∗
) = 0.
Chứng minh. Theo mệnh đề 1.1 và do x
∗
là nghiệm cực tiểu địa phương
nên
f

(x
∗
, d ) = lim
t→0
+
f(x
∗
+ td) −f(x
∗
)
t
= ∇f(x

∗
là nghiệm cực tiểu toàn cục của bài toán (1.1). Thật vậy, do f
là hàm lồi khả vi trên R
n
nên nó có đạo hàm theo mọi hướng d ∈ R
n
tại
x
∗
. Khi đó,
∇f(x
∗
), d = f

(x
∗
, d ) ≤ f(x
∗
+ d) −f(x
∗
), ∀d ∈ R
n
.
Do đó, với điểm bất kỳ x ∈ R
n
, ta có
0 = ∇f(x
∗
), x − x
∗

thì
∇f(x
∗
) = 0 và ∇
2
f(x
∗
) nửa xác định dương.
ii) Nếu ∇f(x
∗
) = 0 và ∇
2
f(x
∗
) xác định dương thì x
∗
là điểm cực
tiểu địa phương chặt của f trên R
n
.
Chứng minh. i) Với mọi d ∈ R
n
mà 0 < d < ε với ε đủ nhỏ, khai triển
Taylor của hàm f tại x
∗
là
f(x
∗
+ d) = f(x
∗

d
T
∇
2
f(ξ)d. (1.3)
9
Bây giờ ta chứng minh ∇
2
f(x
∗
) nửa xác định dương, tức là v
T
∇
2
f(x
∗
)v ≥
0 với mọi v ∈ R
n
.
Thật vậy, giả sử phản chứng rằng tồn tại v ∈ R
n
, v = 0, sao cho
v
T
∇
2
f(x
∗
)v < 0. Ta có thể giả thiết rằng  v < ε. Khi đó, vì f là hàm

.
ii) Giả sử ∇f(x
∗
) = 0 và d
T
∇
2
f(x
∗
)d > 0 với mọi d ∈ R
n
. Vì các
thành phần của ∇
2
f(x) là các hàm liên tục tại x
∗
nên d
T
∇
2
f(x)d cũng
là hàm liên tục tại x
∗
. Do đó ta có d
T
∇
2
f(ξ)d > 0 với mọi ξ sao cho
 ξ − x
∗

0
) ≥ f(x
1
) ≥ f(x
2
) ≥ ···
và dãy {x
k
} hội tụ đến điểm dừng x
∗
∈ R
n
của hàm f, tức là ∇f(x
∗
) = 0.
Thuật toán 1.1 (Hướng giảm).
Bước 1. Cho một điểm x
0
∈ R
n
, ε > 0, k := 0. Tính ∇f(x
0
).
Bước 2. Nếu  ∇f(x
0
) < ε. Dừng. Trái lại đi đến bước 3.
Bước 3. Xác định x
k+1
:= x
k

0
nếu tồn tại
ε > 0 sao cho với mọi t thoả mãn 0 < t < ε ta có f(x
0
+ td) < f(x
0
).
Mệnh đề 1.2. Cho hàm f khả vi trên R
n
, điểm x
0
∈ R
n
và hướng d ∈ R
n
.
Nếu ∇f(x
0
), d  < 0 thì d là hướng giảm của f tại x
0
.
Chứng minh. Vì hàm f khả vi tại x
0
theo mệnh đề 1.1 và giả thiết của
mệnh đề 1.2, ta có
f

(x
0
, d ) = lim

.
Chứng minh. Theo mệnh đề 1.2 ta chỉ cần chứng minh điều kiện cần.
Giả sử d ∈ R
n
là hướng giảm của f tại x
0
, tức là
∃ε > 0 sao cho f(x
0
+ td) < f(x
0
), ∀t : 0 < t < ε. (1.4)
Vì hàm f lồi khả vi trên R
n
và hàm f có đạo hàm theo mọi hướng d tại
điểm x
0
∈ R
n
và
f(x
0
+ td) −f(x
0
) ≥ f

(x
0
, td) = ∇f(x
0

Giả sử đã biết hướng giảm d
k
của hàm f tại x
k
theo lược đồ chung
của phương pháp hướng giảm, điểm lặp tiếp theo được xác định bởi
x
k+1
:= x
k
+ t
k
d
k
,
với t
k
là một số thực dương. Như vậy, x
k+1
là một điểm nằm trên tia
{x
k
+ td
k
, t > 0}, t
k
> 0 thông thường có hai cách lựa chọn t
k
ứng với
hai thủ tục tìm chính xác theo tia và thủ tục quay lui.

t
k
= argmin{ϕ
k
(t)|t ≥ 0}.
Mệnh đề 1.4. Cho hàm toàn phương lồi chặt
f(x) =
1
2
x
T
Ax −b
T
x + c,
trong đó A là ma trận cấp n ×n, đối xứng, xác định dương, vectơ b ∈ R
n
và c ∈ R. Cho x
k
∈ R
n
và hướng giảm d
k
của hàm f tại x
k
. Khi đó, độ
dài bước chính xác t
k
được xác định bởi
t
k

t=t
k
=
dϕ(t)
dt



t=t
k
= lim
t→0
ϕ(t
k
+ t) −ϕ(t
k
)
t
= lim
t→0
+
f((x
k
+ t
k
d
k
) + td
k
) −f(x

+ t
k
d
k
) −b, d
k

= Ax
k
− b, d
k
 + t
k
Ad
k
, d
k
 = 0.
Do d
k
là hướng giảm của hàm f tại x
k
và f(x) là hàm lồi nên theo mệnh
đề 1.3 ∇f(x
k
), d
k
 = Ax
k
−b, d

Mệnh đề sau là cơ sở của thủ tục quay lui xác định điểm x
k+1
khi đã
biết hướng giảm d
k
của hàm f tại x
k
.
Mệnh đề 1.5. Cho hàm f khả vi trên R
n
, điểm x
k
∈ R
n
và vectơ d
k
∈ R
n
thoả mãn ∇f(x
k
), d
k
 < 0. Cho số thực m
1
∈ (0, 1). Khi đó
∃t
0
sao cho f(x
k
+ td

+
f(x
k
+ td
k
) −f(x
k
)
t
= ∇f(x
k
), d
k
,
nên
lim
t→0
+
f(x
k
+ td
k
) −f(x
k
)
t∇f(x
k
), d
k


k
+ t
k
d
k
) ≤ f(x
k
) + m
1
t
k
∇f(x
k
), d
k
 với m
1
∈ (0, 1) và t
k
> 0
được gọi là điều kiện Armijo.
13
1.3 Phương pháp gradient
Đây là phương pháp thông dụng để giải bài toán cực tiểu không ràng
buộc vì nó đơn giản và có thể áp dụng cho những lớp hàm rất rộng. Ý
tưởng của phương pháp này như sau: tại mỗi bước lặp k ta chọn hướng
giảm d
k
của hàm f tại x
k

tia).
Bước 1. Cho một điểm x
0
∈ R
n
, ε > 0, k := 0. Tính ∇f(x
0
).
Bước 2. Nếu  ∇f(x
0
) < ε, dừng. Trái lại, đi đến bước 3.
Bước 3. Xác định x
k+1
:= x
k
− t
k
∇f(x
k
), trong đó
t
k
= argmin{ϕ
k
(t)}.
Bước 4. Tính ∇f(x
k+1
).
Bước 5. Đặt k := k + 1 quay trở lại bước 2.
Định lí 1.5 (xem [1]). Cho x

trong đó t
k
là giá trị đầu tiên trong dãy t, λt, λ
2
t, λ
3
t, thoả mãn
f(x
k+1
)−f(x
k
) ≤ −εt
k
 ∇f(x
k
) 
2
, trong đó t > 0, ε ∈ (0, 1), λ ∈ (0, 1).
Thuật toán 1.3 (Thuật toán gradient với thủ tục quay lui).
Bước 1. Cho một điểm x
0
∈ R
n
, ε > 0, k := 0, chọn m
1
∈ (0, 1), α ∈
(0, 1) . Tính ∇f(x
0
), nếu  ∇f(x
0

1
t
k
 ∇f(x
k
) 
2
thì chuyển sang bước 5. Trái lại, t
k
:= αt
k
quay trở về bước 3.
Bước 5. Tính ∇f(x
k+1
).
Bước 6. Nếu  ∇f(x
k+1
) < ε, dừng. Trái lại, đặt k := k + 1 quay trở
về bước 1.
Định lí 1.6 (xem [1]). Giả sử rằng f bị chặn dưới và gradient ∇f(x) là
Lipschitz, tức là:
∃L > 0 : ∇f(x) −∇f(y) ≤ L  x −y  ∀x, y.
Khi đó, với bất kỳ điểm xuất phát x
0
, dãy {x
k
} được chọn theo thuật toán
gradient với thủ tục quay lui hội tụ theo nghĩa ∇f(x
k
) → 0 khi k → +∞.

i
có các đạo hàm riêng
∂f
i
∂x
j
. Khi đó, ma trận
DF (x) =



∂f
1
∂x
1
···
∂f
1
∂x
n
.
.
. ···
.
.
.
∂f
m
∂x
1

.
Tại điểm x
k
∈ R
n
thuộc dãy này, khai triển Taylor của F tại x
k
là
F (x
k
+ p) = F(x
k
) + DF (x
k
)p + o( p ),
trong đó vectơ p ∈ R
n
có  p  đủ nhỏ, DF (x
k
) là ma trận Jacobian
của F tại điểm x
k
∈ R
n
và o( p ) là vô cùng bé so với chuẩn  p  khi
p → 0. Khi đó xấp xỉ Taylor bậc nhất hàm F tại x
k
là
F (x
k

− [DF (x
k
)]
−1
F (x
k
).
Đặt x
k
:= x
k+1
và lặp lại quá trình tính toán đối với điểm x
k
mới.
17
Chương 2
Phương pháp gradient liên hợp
Trong chương trước ta đã nhắc lại phương pháp gradient, đây là
phương pháp thông dụng để giải bài toán cực tiểu không ràng buộc,
phương pháp này rất đơn giản và có thể áp dụng cho những lớp hàm
rất rộng. Tuy nhiên, phương pháp này có tốc độ hội tụ chậm. Để khắc
phục tình trạng này ta giới thiệu phương pháp gradient liên hợp, đây
là phương pháp trung gian giữa phương pháp gradient và phương pháp
Newton, phương pháp gradient liên hợp thay đổi hướng trong phương
pháp gradient bằng cách thêm vào một tỷ lệ dương của hướng dùng ở
bước cuối cùng, phương pháp này chỉ cần tới đạo hàm riêng bậc nhất
nhưng lại khắc phục được tính hội tụ chậm của phương pháp gradient.
Trong chương này, ta sẽ thảo luận các tính chất, thuật toán và tính
hội tụ của phương pháp gradient liên hợp và một số ví dụ áp dụng. Cần
chú ý rằng, kỹ thuật tái khởi và hiệu chỉnh là rất quan trọng để cải

= 0, ∀i = j, i, j = 1, m thì các vectơ d
1
, d
2
, , d
m
gọi
là G-liên hợp hay đơn giản là liên hợp.
Tính chất 2.1. Nếu d
1
, d
2
, , d
m
là các hướng liên hợp (trong R
n
) đối
với ma trận G thì các vectơ này độc lập tuyến tính.
Chứng minh. Xét đẳng thức
a
1
d
1
+ a
2
d
2
+ ··· + a
m
d

 = 0.
Do d
1
, d
2
, , d
m
là các hướng liên hợp nên d
j
, Gd
i
 = 0, i = j. Từ đẳng
thức trên suy ra a
i
d
i
, Gd
i
 = 0. Do d
i
= 0 và G xác định dương nên
d
i
, Gd
i
 > 0, từ đó suy ra a
i
= 0. Vì i tuỳ ý nên suy ra các vectơ
d
1

p
T
k+1
Gd
i
d
T
i
Gd
i
d
i
, k = 1, 2, , n − 1.
Chứng minh. Ta sẽ chứng minh tính chất này bằng phương pháp quy
nạp.
Với k = 1 ta có
d
1
= p
1
d
2
= p
2
−
p
T
2
Gd
1

, Gd
1

= p
2
, Gd
1
 −
p
T
2
Gd
1
d
T
1
Gd
1
d
1
d
1
, Gd
1

= 0.
Vậy nó đúng với k = 1.
Giả sử tính chất trên đúng với k tức là d
T
i

Gd
i
d
i
, Gd
j

= p
k+1
, Gd
j
 −
k

i=1
p
T
k+1
Gd
i
d
T
i
Gd
i
d
i
, Gd
j
, j = 1, k

0
g
0
<
0.
Bước 2. Tính α
k
sao cho
f(x
k
+ α
k
d
k
) = min
α≥0
f(x
k
+ αd
k
)
Đặt x
k+1
= x
k
+ α
k
d
k
, tính g(x

= (0, 0)
T
, ε = 10
−10
Giải.
Lần lặp 1.
Bước 1. g(x) = ∇f(x) =

2x
1
− 2x
2
−2x
1
+ 4x
2
+ 2

; g
0
= g(x
0
) = ∇f(x
0
) =

0
2

= (0, 2)

T
0
g
0
< 0 ⇔ (d
1
0
, d
2
0
)

0
2

= 2d
2
0
<
0. Vậy ta có thể chọn

d
2
0
< 0
d
1
0
tùy ý
chọn

0
) = min
α≥0
f(0, − 2α).
Trong đó f(0, −2α) = 8α
2
− 4α + 2 ta tính được α
0
=
1
4
.
Đặt x
1
= x
0
+ α
0
d
0
= (0, 0)
T
+
1
4
(0, −2)
T
= (0, −
1
2

, d
2
1
)
T
sao cho d
T
1
Gd
0
= 0 hay
(d
1
1
, d
2
1
)

2 −2
−2 4


0
−
1
2

= (
2d

1
= 2d
2
1
. Chọn d
1
1
= −1, d
2
1
= −
1
2
.
Lần lặp 2.
Bước 2. Tính α
1
sao cho
f(x
1
+ α
1
d
1
) = min
α≥0
f(x
1
+ αd
1

1
+ α
1
d
1
=

0
−
1
2

+

−1
−
1
2

=

−1
−1

g(x
2
) =

0
0

0
, d
1
, , d
i
, nghĩa là {x|x = x
0
+
i

j=0
α
j
d
j
}.
Chứng minh. Vì G là xác định dương và các hướng liên hợp d
0
, d
1
, là
độc lập tuyến tính, nên ta chỉ cần chứng minh i ≤ n −1 là đủ. Tức là
g
T
i+1
d
j
= 0, j = 0, 1, , i. (2.2)
(Chú ý rằng nếu (2.2) là đúng, ngay lập tức ta có g
T

d
j
= g
T
j+1
d
j
+
i

k=j+1
y
T
k
d
j
= g
T
j+1
d
j
+
i

k=j+1
α
k
d
T
k