ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐẶNG HIẾU TRỌNG
GRADIENT SUY RỘNG VÀ ỨNG DỤNG VÀO BÀI TOÁN
TỐI ƯU KHÔNG TRƠN
LUẬN VĂN THẠC SỸ TOÁN HỌC
THÁI NGUYÊN - NĂM 2010
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐẶNG HIẾU TRỌNG
GRADIENT SUY RỘNG VÀ ỨNG DỤNG VÀO BÀI TOÁN
TỐI ƯU KHÔNG TRƠN
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
Mục lục
Mở đầu 1
1 Gradient suy rộng 3
1.1 Định nghĩa và ký hiệu . . . . . . . . . . . . . . . . . . . 3
1.2 Một số tính chất cơ bản của gradient suy rộng . . . . . . 8
2 Một số phương pháp giải bài toán tối ưu không trơn 11
2.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Một số phương pháp giải bài toán tối ưu không trơn . . . 18
2.3.1 Phương pháp dưới gradient . . . . . . . . . . . . 18

Hàm không trơn được hiểu là những hàm không khả vi. Vì thế những
hàm này còn được gọi là những hàm không khả vi.
Bài toán quy hoạch phi tuyến
min{f(x) : g
i
(x) = 0, i = 1, , p, g
i
(x) ≤ 0, i = p + 1, , m}
được gọi là bài toán tối ưu không trơn nếu hàm mục tiêu f(x) hay một
trong các hàm ràng buộc g
i
(x) là một hàm không trơn.
Như chúng ta đã biết với bài toán tối ưu trơn, do các hàm khả vi có
rất nhiều tính chất đẹp, do đó các phương pháp giải đối với bài toán
này đã được xây dựng và phát triển khá hoàn thiện. Nhưng với bài toán
tối ưu không trơn thì việc xây dựng các phương pháp g iải gặp rất nhiều
khó khăn, ngay cả những bài toán trong R
1
việc giải cũng không đơn
giản. Tuy nhiên, bài toán tối ưu không trơn có tính ứng dụng thực tiễn
rất cao. Vì vậy, xây dựng phương pháp giải cho bài toán tối ưu không
trơn thu hút rất nhiều người làm toán quan tâm. Chính vì lẽ đó mà tác
giả đã chọn đề tài "Gradient suy rộng và ứng dụng vào bài toán tối ưu
không trơn".
Mục đích của luận văn này là trình bày những kiến thức ban đầu về
tối ưu không trơn, đề cập tới điều kiên tối ưu không trơn và giới thiệu
một số phương pháp bằng số giải bài toán tối ưu không trơn.
Luận văn được chia làm hai chương.
Chương 1: Gradient suy rộng
Trong chương này, tác giả trình bày một số khái niệm về hàm Lipschitz,

Định nghĩa 1.1. Cho X là một không gian Banach với chuẩn  .  được
xác định trên X. Giả sử Y là một tập con của X. Một hàm f : Y → R
được gọi là Lipschitz trên Y nếu f(x) thỏa mãn điều kiện
|f(x) −f(y)| ≤ K  x − y , ∀x, y ∈ Y ⊆ X. (1.1)
Bất đẳng thức (1.1) gọi là điều kiện Lipschitz và K được gọi là hằng
số Lipschitz.
Ký hiệu B(x, ε) = {y|  x − y ≤ ε} là hình cầu suy rộng tâm x bán
kính ε > 0.
Hàm f gọi là Lipschitz ở gần x nếu f thỏa mãn điều kiện Lipschitz
trên hình cầu B(x, ε) với một số ε > 0 nào đó.
Định nghĩa 1.2. Đạo hàm của hàm f theo phương d tại x ký hiệu là
f

(x, d) và được định nghĩa là giới hạn
f

(x, d) = lim
t↓0
f(x + td) −f (x)
t
nếu giới hạn này tồn tại.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Có thể thấy một hàm có tính Lipschitz ở gần một điểm không nhất
thiết khả vi tại điểm đó và có thể không có đạo hàm theo hướng theo
nghĩa cổ điển vừa nêu.
Định nghĩa 1.3. Đạo hàm theo hướng Dini trên của f tại x theo hướng
d, ký hiệu là f
(D)
(x, d) được định nghĩa là giới hạn

f
(D)
(x, d) ≤ f
0
(x, d), ∀x và d.
ii) Nếu f(x) là một hàm Lipschitz địa phương và tồn tại f

(x, d) thì
f

(x, d) = f
(D)
(x, d).
Nếu f

(x, d) tồn tại tại x với mọi hướng d thì f gọi là khả vi theo
hướng tại x.
Nếu f khả vi theo hướng tại x và f

(x, d) = f
0
(x, d) thì f gọi là chính
quy tại x.
Hàm f được gọi là hàm chính quy nếu nó chính quy khắp mọi nơi.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
Bổ đề 1.1. Nếu f(x) là hàm Lipschitz ở gần x thì
i) Hàm d → f
0
(x, d) là hàm thuần nhất dương, dưới cộng tính và thỏa

= λ lim
y →x
η↓0
sup
f(y + ηd) −f(y)
η
= λf
0
(x, d).
Vậy f
0
(x, d) là hàm thuần nhất dương.
Theo định nghĩa ta có
f
0
(x, d
1
+ d
2
) = lim
y →x
t↓0
sup
f(y + t(d
1
+ d
2
)) −f(y)
t
≤ lim

(x, d) là dưới cộng tính.
f
0
(x, d) = lim
y →x
t↓0
sup
f(y + td) −f(y)
t
≤ lim
t↓0
K  y + td −y 
t
= K  d 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
Suy ra |f
0
(x, d)| ≤ K  d  .
ii) Với d
1
, d
2
∈ X, từ điều kiện Lipschitz ta thấy
f(y + td
1
) −f(y) ≤ f(y + td
2
) −f(y) + Kt  d
1

2
 . (1.3)
Tương tự, ta có
f
0
(x, d
2
) ≤ f
0
(x, d
1
) + K  d
1
− d
2
 (1.4)
từ (1.3) và (1.4) suy ra
|f
0
(x, d
1
) −f
0
(x, d
2
)| ≤ K  d
1
− d
2
 .

(x
k
, d
k
) −
1
k
≤
f(y
k
+ t
k
d
k
) −f(y
k
)
t
k
≤
f(y
k
+ t
k
d
k
) −f(y
k
+ t
k

(x, d) là nửa liên tục trên.
iv) Ta có
f
0
(x, −d) = lim
y →x
t↓0
sup
f(y −td) −f(y)
t
= lim
u→x
t↓0
sup
(−f)(u + td) −(−f )(u)
t
= (−f)
0
(x, d).
Bổ đề trên cho thấy f
0
(x, d) là một hàm thuần nhất dương và dưới
cộng tính, vì thế theo định lý Han-Banach sẽ tồn tại phiếm hàm tuyến
tính ξ : X → R sao cho f
0
(x, d) ≥ ξ, d với ∀d ∈ X và ξ bị chặn. Do đó
ξ thuộc không gian liên hợp X
∗
các phiếm hàm tuyến tính liên tục trên
X mà để cho tiện ta dùng các ký hiệu ξ, d hay d, ξ thay cho ký hiệu

y + td −y
t
= d
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
từ đó,
∂f(x) = {ξ|d ≥ ξd, ∀d ∈ R} = {1}
Tương tự, với x < 0 ta có
∂f(x) = {−1}.
Với x = 0 ta có
f
0
(0, d) =



d nếu d ≥ 0
−d nếu d < 0,
nghĩa là f
0
(x, d) = |d|. Vậy ∂f(0) gồ m những ξ thỏa mãn |d| ≥ ξd, nghĩa
là ∂f (x) = [−1; 1]. Vì thế ta kết luận
∂f(x) =








∗
≤ K với
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
∀ξ ∈ ∂f(x).
ii) Với mọi d ∈ X ta có
f
0
(x, d) = max
ξ∈∂f(x)
{ξ, d}.
Chứng minh. i) Suy ra trực tiếp từ các nhận xét trước đây và từ bổ đề
1.1.
ii) Là cách diễn đạt khác của sự kiện nói rằng ∂f (x) theo định nghĩa là
tập lồi đóng yếu
∗
và có hàm tựa là f
0
(x, d). Để chứng minh sự kiện này
một cách độc lập ta giả sử f
0
(x, d) > max
ξ∈∂f(x)
{ξ, d} với một d nào đó
(f
0
(x, d) không thể nhỏ hơn theo định nghĩa của dưới vi phân ∂f(x)).
Theo định lý Hahn-Banach tồn tại phiếm hàm tuyến tính ξ không vượt
quá f
0

f
0
(x, d) = lim
ε↓0
sup
x

−x<εδ
sup
0<t<ε
f(x

+ td) −f (x

)
t
trong đó δ > 0 là một số cho trước tùy ý. Do f(x) là hàm lồi nên hàm
g(t) =
f(x

+ td) −f (x

)
t
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
không giảm. Vì thế
f
0
(x, d) = lim

≤ 2δK,
do đó
f
0
(x, d) ≤ lim
ε↓0
f(x + εd) −f (x)
ε
+ 2δK
= f

(x, d) + 2δK.
Do δ được chọn tùy ý nên f
0
(x, d) ≤ f

(x, d). Vậy, f
0
(x, d) = f

(x, d).
Bổ đề 1.4. Nếu f (x ) Lipschitz gần x thì ξ ∈ ∂f(x) khi và chỉ khi
f
0
(x, d) ≥ ξ, d với mọi d ∈ X.
Ngoài ra, ∂f (x) có các tính chất sau
i)
∂f(x) =

δ>0

1
(x), , h
n
(x))
T
với mỗi h
i
(x) là
Lipschitz gần x và g(x) là Lipschitz gần h(x) thì f (x) là Lipschitz gần
x và
∂f(x) ⊂ CO

n

i=1
α
i
ξ
i
: ξ
i
∈ ∂h
i
(x), α ∈ ∂g(h)


h
= h(x)

trong đó CO là bao lồi compact yếu

Khi đó, nếu x không phải là nghiệm cực tiểu của bài toán thì f (x) khả
vi và ta có
|∂f(x)| = |∇f(x)| = 1.
Do đó, trong trường hợp này ta không thể dùng (2.2) làm tiêu chuẩn
dừng.
Thứ hai, nếu f(x) không khả vi mà ta sử dụng phương pháp hướng
giảm nhanh nhất với thủ tục tìm chính xác theo tia để giải (2.1) có thể
nhận được dãy {x
k
} hội tụ về điểm không dừng.
Ví dụ 2.2. Xét hàm f : R
2
→ R, x = (u, v)
T
và
f(x) = max[
1
2
u
2
+ (v −1)
2
;
1
2
u
2
+ (v −1)
2
]

|)

1
t
k

,
trong đó t
k
= sign(ε
k
). Nếu ta sử dụng hướng đối gradient −∇f (x
k
) ta
nhận được
x
k+1
= x
k
+ α
k
(−∇f(x
k
))
=


2(1 +
|ε|
3

T
. Nhưng rõ
ràng điểm (2, 0)
T
không phải là điểm dừng.
Bài toán tối ưu có ràng buộc có dạng
min
x∈Y
f(x) (2.3)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
trong đó Y ⊆ X là một tập hay miền chấp nhận được. Ta định nghĩa
khoảng cách từ điểm x đến Y là
dist(x, Y ) = min
y∈Y
 y − x  .
Theo lý thuyết hàm phạt, với những giả thiết thích hợp bài toán (2.3)
tương đương với bài toán
min
x∈X
f(x) + σdist(x, Y ) (2.4)
trong đó f (x) + σdist(x, Y ) là hàm không khả vi. Như vậy, bài toán tối
ưu có ràng buộc không trơn được đưa về bài toán tương đương không
ràng buộc không trơn. Điều này giải thích tại sao người ta lại hay quan
tâm nghiên cứu các bài toán tối ưu không ràng buộc không trơn cụ thể
là bài toán (2.1).
Có nhiều ví dụ về bài toán tối ưu không trơn chẳng hạn bài toán
minimax: min
x∈X
max

Ví dụ 2.3 (Bài toán đối ngẫu). Xét bài toán
(P )















min f(x)
s.t. g
i
(x) ≤ 0; i = 1, , m.
h
j
(x) = 0; j = 1, , p.
x ∈ C,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
trong đó f, g
i
, i = 1, , m; h

x ∈ C; λ ≥ 0; µ ∈ R
p
.
Các vecto λ và µ gọi là nhân tử Lagrange suy rộng của bài toán (P ).
Nhờ có hàm này, ta có thể viết bài toán (P ) dưới một dạng khác. Trước
hết chú ý rằng
∀
x ∈ C, ∀(λ, µ), λ ≥ 0, inf
x∈C
L(x, λ, µ) ≤ L(x, λ, µ).
Do đó, khi ta lấy supremum với (λ, µ), λ ≥ 0 và sau đó lấy infimum với
x ∈ C ta thu được các kết quả.
∀x ∈ C, sup
λ≥0
inf
x∈C
L(x, λ, µ) ≤ sup
λ≥0,µ
L(x, λ, µ)
và
sup
λ≥0,µ
inf
x∈C
L(x, λ, µ) ≤ inf
x∈C
sup
λ≥0,µ
L(x, λ, µ).
Khi đó ta có

j
(x) = 0, ∀j
+∞ trong các trường hợp khác.
2.2 Điều kiện tối ưu
Mục này đề cập tới điều kiện tối ưu đối với cực tiểu của hàm Lipschitz.
Cho X là một không gian Banach với chuẩn  .  được định nghĩa
trên X. Xét hàm f : X → R.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
Định nghĩa 2.1. i) Ta nói x
∗
∈ X là điểm cực tiểu (cực tiểu chặt) của
f trên X nếu f (x
∗
) ≤ f(x), ∀x ∈ X (f(x
∗
) < f(x), ∀x ∈ X, x = x
∗
).
ii) x
∗
∈ X được gọi là điểm cực tiểu địa phương của f trên x nếu tồn tại
một lân cận U chứa x
∗
để các bất đẳng thức trên thỏa mãn ∀x ∈ U ∩X.
Bài toán tìm cực đại của một hàm trên tập đã cho được phát biểu
một cách tương tự nhưng để ý
min
x∈X
f(x) = −max

∗
). Dễ thấy rằng với bất kỳ số s ta có
∂(sf)(x) = s∂f(x) cho nên với s = −1 ta có 0 ∈ ∂(−f)(x
∗
) = −∂f (x
∗
),
nghĩa là 0 ∈ ∂f(x
∗
). Định lý được chứng minh.
Định nghĩa 2.2. Điểm x
∗
gọi là điểm dừng của hàm f nếu f có đạo
hàm theo mọi hướng tại x
∗
và với mọi hướng d thì
f

(x
∗
, d) ≥ 0.
Điểm x
∗
gọi là điểm dừng Dini của hàm f nếu với mọi d ta có
f
(D)
(x
∗
, d) ≥ 0.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

thì x
∗
là điểm cực tiểu của f(x).
Chứng minh. Do f (x) là hàm lồi và Lipschitz gần x
∗
nên theo bổ đề 1.3
vi phân suy rộng và dưới vi phân của f tại x
∗
là trùng nhau, tức là
{ξ ∈ X
∗
|f(z) −f (x
∗
) ≥ ξ, z −x
∗
, ∀z ∈ X}
= {ξ ∈ X
∗
|f
0
(x
∗
, d) ≥ ξ, d, ∀z ∈ X}.
Do 0 ∈ ∂f(x
∗
) nên ta có
f(z) −f (x
∗
) ≥ 0, z −x
∗

Hơn nữa, ta còn có điều kiện đủ cho cực tiểu chặt như sau.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
Định lí 2.3. Cho f(x) là hàm lồi và Lipschitz gần x
∗
. Nếu f

(x, d) >
0, ∀d = 0, d ∈ X thì x
∗
là điểm cực tiểu chặt của f(x), nghĩa là tồn tại
số δ > 0 sao cho
f(x) −f(x
∗
) > δ  x − x
∗

với mọi x đủ gần x
∗
.
Chứng minh. Đặt
S = {d|d ∈ X,  d = 1}.
Hiển nhiên S là một tập compact và đóng. Do f

(x
∗
, d) là dương trên S
và f

(x

Với hàm f(x) không lồi thì kết quả trên không còn đúng nữa, như chỉ
ra ở ví dụ sau:
Ví dụ 2.4. Xét hàm f : R
1
→ R
1
f(x) =



(−1)
k+1

1
2
k+1
− 3x

; x ∈

1
2
k−1
;
1
2
k

0; x = 0
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

n
và xét bài toán cực tiểu không ràng buộc
dạng min
x∈R
n
f(x). Ta đã biết hàm lồi và Lipschitz gần x thì khả vi hầu
khắp nơi và
∂f(x) = convΩ(x)
trong đó convΩ là bao lồi của Ω và
Ω(x) = {g|g = lim ∇f(x
i
), x
i
→ x, ∃∇f(x
i
)}.
Phương pháp dưới gradient được mô tả như sau
Thuật toán 2.1. (Phương pháp dưới gradient.)
Bước 1. Chọn điểm ban đầu x
1
∈ R
n
, đặt chỉ số bước lặp k := 1.
Bước 2. Tính f(x
k
), g
k
∈ ∂f(x
k
).

k
d
k
) ≤ f(x
k
) + α
k
C
1
d
T
k
∇f(x
k
),
trong đó, c
1
∈ (0, 1) là một hằng số.
Với phương pháp hướng giảm nhanh nhất thì quy tắc trên trở thành
f(x
k
− α
k
∇f(x
k
)) ≤ f(x
k
) + α
k
C

Để ý là độ dà i bước hằng số là không thích hợp, bởi vì hàm cần tìm
cực tiểu có thể không khả vi tại lời giải và khi đó dãy {g
k
} không nhất
thiết hội tụ tới 0, ngay cả khi {x
k
} hội tụ tới điểm tối ưu.
Quy tắc xác định α
k
trong phương pháp dưới gradient hoà n toàn khác
với cách xác định α
k
trong phương pháp hướng giảm nhanh nhất.
Mặc dầu thủ tục tìm chính xác và gần đúng theo tia dùng trong tối
ưu trơn không thể mở rộng một cách đơn giản cho trường hợp không
trơn, nhưng hướng đố i dưới gradient vẫn là hướng tốt để cho điểm lặp
mới gần hơn với nghiệm cực tiểu cần tìm. Ta cần b ổ đề sau.
Bổ đề 2.1. Giả sử f(x) là hàm lồi và tập
S
∗
= {x|f(x) = f
∗
= min
x∈R
n
f(x)}
không rỗng. Nếu x
k
∈ S
∗

2
với mọi α ∈ (0, T
k
).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Chứng minh. Với bất kỳ x
k
ta có
 x
k
− α
g
k
 g
k

2
− x
∗

2
2
= x
k
− x
∗

2
+2α

− x
k
) ≤ f(x
∗
) −f(x
k
) < 0.
Đặt T
k
= −2
g
T
k
(x
∗
− x
k
)
 g
k

2
> 0 thì có thể viết lại đẳng thức trước đó
thành
 x
k
− α
g
k
 g


2
− x
∗

2
2
< x
k
− x
∗

2
2
hay
 x
k
− α
g
k
 g
k

2
− x
∗

2
< x
k

21
toán 2.1 không hội tụ. Vì vậy, để khắc phục ta nên chọn α
k
thỏa mãn
điều kiện
α
k
> 0, lim
k→∞
α
k
= 0 (2.6)
∞

k=1
α
k
= ∞. (2.7)
Với cách chọn α
k
như trên ta có định lý hội tụ sau.
Định lí 2.5. Giả sử f(x) là một hàm lồi và S
∗
là một tập khác rỗng
và bị chặn. Nếu α
k
thỏa mãn điều kiện (2.6)-(2.7) thì dãy {x
k
} sinh bởi
Thuật toán 2.1 sẽ thỏa mãn điều kiện

k
= f(x
k
) −f
∗
≥ 0.
Nếu ε
k
> 0 thì
 x
k+1
− x
∗

2
= x
k
− x
∗

2
+α
2
k
− 2α
k
(x
k
− x
∗

)
g
k
 g
k

2

g
k
 g
k

2
≤ x
k
− x
∗

2
+α
2
k
− 2δ(ε
k
)α
k
.
Do đó,
[dist(x