ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

ĐẶNG THỊ TUYẾT MAI

PHƯƠNG PHÁP ĐIỂM GẦN KỀ QUÁN TÍNH
CỦA TSENG CHO BÀI TOÁN TỐI ƯU
KHÔNG LỒI VÀ KHÔNG TRƠN

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2016


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

ĐẶNG THỊ TUYẾT MAI

PHƯƠNG PHÁP ĐIỂM GẦN KỀ QUÁN TÍNH
CỦA TSENG CHO BÀI TOÁN TỐI ƯU
KHÔNG LỒI VÀ KHÔNG TRƠN

Chuyên ngành: Toán ứng dụng
Mã số:

60 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

GS.TS. NGUYỄN BƯỜNG

THÁI NGUYÊN - 2016


i

Mục lục

Lời cảm ơn

ii

Danh sách ký hiệu

iii

Mở đầu

1

1

Một số vấn đề cơ bản

4

1.1


Hàm nhiều biến . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Các khái niệm dưới vi phân mở rộng . . . . . . . . . . . . . 11

1.3

Một số khoảng cách cần dùng . . . . . . . . . . . . . . . . 12

1.4

Thuật toán điểm gần kề quán tính cho hàm lồi . . . . . . . . 12

2

Phương pháp điểm gần kề quán tính cho bài toán tối ưu không
lồi và không trơn

15

2.1

Thuật toán tiến-lùi . . . . . . . . . . . . . . . . . . . . . . . 15

2.2

Thuật toán tiến-lùi-tiến loại Tseng . . . . . . . . . . . . . . 19


Tài liệu tham khảo

35


ii

Lời cảm ơn
Luận văn này được hoàn thành tại trường Đại học Khoa học, Đại học
Thái Nguyên dưới sự giúp đỡ và hướng dẫn tận tình của GS.TS. Nguyễn
Bường. Qua đây, tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới
Thầy, người đã dành nhiều thời gian và tâm huyết để hướng dẫn và tạo điều
kiện cho tác giả trong suốt thời gian làm luận văn.
Trong quá trình học tập và làm luận văn, từ bài giảng của các giáo sư,
phó giáo sư công tác tại Viện Toán học, Viện Công nghệ Thông tin - Viện
Hàn lâm Khoa học và Công nghệ Việt Nam, các thầy cô trong trường Đại
học Khoa học - Đại học Thái Nguyên, tác giả đã trau dồi thêm rất nhiều kiến
thức phục vụ cho việc nghiên cứu và công tác của bản thân. Tác giả xin gửi
lời cảm ơn chân thành đến các thầy cô.
Tác giả xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo, khoa Toán
- Tin trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp
đỡ tác giả trong suốt thời gian học tập tại trường.
Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động
viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả trong quá trình học tập,
nghiên cứu và làm luận văn.
Thái Nguyên, tháng 11 năm 2015
Học viên
Đặng Thị Tuyết Mai



iii

Danh sách ký hiệu
H

không gian Hilbert thực

N

tập hợp các số nguyên không âm

R+

tập hợp các số thực không âm

R++

tập hợp các số thực dương

E

ma trận thực n × n

KL

Kurdyka-Lojasiewicz

x, y


tích vô hướng của hai vectơ x và y

·

chuẩn sinh bởi tích vô hướng

dom f

miền hữu dụng của hàm f

Fix T

tập các điểm bất động của toán tử T

proxf

toán tử gần kề của hàm f

Γ0 (H)

họ tất cả các hàm lồi f nửa liên tục dưới từ H đến
(−∞, +∞]

∂f (x)

dưới vi phân của f tại x

crit f

tập tất cả (giới hạn) các điểm kì dị của f


dist (x, E)

khoảng cách điểm x đến tập E

Du

khoảng cách Bregman của hàm u : Rm → R


1

Mở đầu
Bài toán tối ưu là bài toán tìm một phương án chấp nhận được để làm
cực trị một hàm số hoặc một hàm véc tơ. Đây là bài toán có nhiều ứng dụng
trong thực tế. Khó khăn chính trong việc nghiên cứu và giải quyết bài toán
này là phải tìm được một phương án tối ưu trong miền chấp nhận được. Để
giải quyết khó khăn này, phương pháp điểm gần kề quán tính là một cách
tiếp cận cơ bản để giải quyết bài toán tối ưu không lồi và không trơn.
Trong luận văn chúng tôi xét bài toán tối ưu dưới dạng sau
(P )

inf [f (x) + h(x)].

x∈Rm

Khi xét về tính lồi, cụ thể là khi f và h là hàm lồi, có rất nhiều lược đồ
tính số phân tách loại gần kề có thể sử dụng để giải bài toán trên. Lưu ý ở
đây loại thuật toán tiến-lùi [3] và thuật toán tiến-lùi-tiến [4] đây là một cải
tiến của thuật toán tiến-lùi với điều kiện sử dụng độ lớn của các bước loại

Nesterov.
Các thuật toán tách áp dụng cho các hàm f và h ở đây được áp dụng
cho lược đồ lặp riêng biệt. Chính xác hơn, bước tiến áp dụng cho hàm trơn
qua gradient còn bước lùi thì áp dụng cho hàm không trơn qua việc sử dụng
toán tử gần kề. Thuật toán được nói ở trên đã được ứng dụng khi giải các bài
toán thực tế xuất hiện trong các lĩnh vực như xử lí hình ảnh và một số vấn
đề khác trong kĩ thuật. Các sơ đồ lặp này có nguồn gốc trong việc rời rạc
hóa theo thời gian của bao hàm thức vi phân bậc hai và nhìn chung các bước


2
lặp mới được xác định bởi việc dùng hai bước lặp trước nó. Thuật toán này
trong vòng mười lăm năm gần đây càng ngày càng được xét rất nhiều trong
các bài báo [4].
Việc mở rộng sự hội tụ của thuật toán loại gần kề đến tập hợp không lồi
là một vấn đề đầy thách thức. Bằng cách giả thiết là các hàm mục tiêu có
một số tính chất giải tích và sử dụng kết quả không trơn được xét bởi tính
chất Kurdyka-Lojasiewicz cho các hàm trơn, lược đồ tiến-lùi cho giải bài
toán này đã được chứng minh có tính chất hội tụ tốt ngay cả trong trường
hợp không lồi [4].
Mục đích của đề tài luận văn là nghiên cứu kết quả mới đây trong [4] về
phương pháp điểm gần kề quán tính cho bài toán tối ưu không lồi và không
trơn trong không gian hữu hạn chiều.
Nội dung của luận văn gồm hai chương:
Chương 1: Một số vấn đề cơ bản. Trong chương này trình bày một số
khái niệm, định lí, tính chất của một số hàm nhiều biến như: Hàm lồi, hàm
nửa liên tục, KL hàm. Khái niệm dưới vi phân hàm lồi, dưới vi phân Fréchet.
Các khái niệm về đạo hàm khả vi, hàm khoảng cách đến một điểm, khoảng
cách Bregman. Giới thiệu thuật toán điểm gần kề quán tính cho hàm lồi.
Chương 2: Phương pháp điểm gần kề quán tính cho bài toán tối ưu

không lồi và không trơn. Chương này trình bày hai loại thuật toán: thuật
toán tiến-lùi và thuật toán tiến-lùi-tiến loại Tseng.
Thông qua việc hoàn thành luận văn, tác giả nhận thấy rằng các vấn đề
được đề cập trong luận văn là rất rộng lớn mà trong khuôn khổ của luận
văn chỉ thể hiện được một phần nào. Tuy nhiên những vấn đề được trình bày
trong luận văn sẽ là những kiến thức khởi đầu định hướng cho tác giả tiếp
cận các vấn đề sau này. Mặc dù tác giả đã cố gắng hết sức thực hiện luận
văn, nhưng với trình độ hạn chế cùng nhiều lý do khác, luận văn chắc chắn


3
không tránh khỏi những thiếu sót. Kính mong sự góp ý của các thầy cô, các
bạn và các anh chị đồng nghiệp để luận văn này hoàn chỉnh hơn.


4

Chương 1

Một số vấn đề cơ bản
Trong chương này tác giả trình bày một số khái niệm, định lí, tính chất
của một số hàm như: Hàm lồi, hàm nửa liên tục, KL hàm. Dưới vi phân
mở rộng, dưới vi phân Fréchet. Các khái niệm về đạo hàm khả vi của hàm
lồi, hàm khoảng cách đến một điểm, khoảng cách Bregman. Giới thiệu thuật
toán điểm gần kề quán tính cho hàm lồi. Các kiến thức của chương này được
tổng hợp từ các tài liệu [1], [2], [3] và [4].

1.1

Hàm nhiều biến


Trước hết tác giả trình bày một số khái niệm, tính chất quan trọng của
hàm lồi. Đây là một kiến thức chuẩn bị rất cần thiết xuyên suốt toàn bộ luận
văn.
Định nghĩa 1.1. Hàm f : S → [−∞, +∞] xác định trên một tập hợp lồi
S ⊆ Rn được gọi là một hàm lồi trên S nếu với mọi x1 , x2 ∈ S và mọi số
thực λ ∈ [0, 1] ta có:
f ((1 − λ)x1 + λx2 ) ≤ (1 − λ)f (x1 ) + λf (x2 ).
Khi vế phải được xác định, nghĩa là hệ thức trên cần được thỏa mãn trừ
khi f (x1 ) = −f (x2 ) = ±∞ (vì biểu thức +∞, −∞ không có nghĩa).
Hàm f được gọi là lồi chặt trên S nếu với mọi x1 , x2 ∈ S, x1 = x2 và


5
mọi số thực λ ∈ (0, 1) ta có:
f ((1 − λ)x1 + λx2 ) < (1 − λ)f (x1 ) + λf (x2 ).
Hiển nhiên, hàm lồi chặt là hàm lồi, nhưng điều ngược lại không đúng.
Định nghĩa 1.2. Cho hàm bất kì f : S → [−∞, +∞] với S ⊆ Rn . Các tập:
dom f = {x ∈ S : f (x) < +∞}, epi f = {(x, α) ∈ S×R : f (x) ≤ α} được
gọi lần lượt là miền hữu dụng, tập trên đồ thị của hàm f . Nếu dom f = ∅ (f
không đồng nhất bằng +∞) và f (x) > −∞ với mọi x ∈ S thì ta nói hàm f
là chính thường (proper). Nói cách khác, f chính thường nếu dom f = ∅ và
f hữu hạn trên dom f .
Có thể chứng minh rằng hàm f lồi trên S khi và chỉ khi
a) tập trên đồ thị epi f là một tập lồi, hoặc
b) f (

m

k=1


k

m

λk x ) ≤

λk f (x ) với mọi x ∈ S,
k

k

k=1

m

λk = 1 và λk ≥ 0 với

k=1

mọi k trong đó m là số nguyên m ≥ 2 (bất đẳng thức Jensen).
Hàm lồi f : S → [−∞, +∞] có thể mở rộng thành hàm lồi xác định trên
toàn không gian Rn bằng cách đặt f (x) = +∞ với mọi x = S. Vì vậy, để
đơn giản ta thường xét hàm lồi trên toàn Rn .
Ví dụ 1.1. Các hàm sau đây là hàm lồi:
a) f : R → R, f (x) = ax + b với a, b là số thực.
Thật vậy, với bất kì a, b ∈ R; x, y ∈ R, λ ∈ (0, 1) ta có:
f (λx + (1 − λ)y) = a(λx + (1 − λ)y) + b = λ(ax + b) + (1 − λ)(ay + b),
thỏa mãn định nghĩa của hàm lồi.
b) Ánh xạ chuẩn · : X n → R và X là một không gian tuyến tính định

chuẩn thực.


6
Thật vậy, với x, y ∈ X, λ ∈ (0, 1) ta có:
λx + (1 − λy) ≤ λx + (1 − λ)y ≤ λ x + (1 − λ) y ,
thỏa mãn định nghĩa hàm lồi.
Định lí 1.1. Giả sử f : Rn → [−∞, +∞] là một hàm lồi trên Rn và
α ∈ [−∞, +∞]. Khi đó, các tập mức dưới Cα = {x : f (x) < α},
Cα = {x : f (x) ≤ α} là tập lồi. Tương tự, nếu f là một hàm lõm trên Rn thì
các tập mức trên Dβ = {x : f (x) > β}, Dβ = {x : f (x) ≥ β} là tập lồi.
Tuy nhiên, mệnh đề đảo của định lý trên không đúng.
Mở rộng hàm lồi: Một hàm f mà mọi tập mức dưới là tập lồi gọi là một
hàm tựa lồi. Ví dụ f (x) = x3 là hàm tựa lồi nhưng không lồi.
Định lý sau đây nêu lên một tính chất đặc trưng cơ bản của các hàm lồi.
Định lí 1.2. Cho C là một tập lồi, khác rỗng trong Rn và f : Rn → R là một
hàm lồi. Mọi điểm cực tiểu địa phương của f trên C đều là điểm cực tiểu
toàn cục. Tập argminx ∈C f (x ) là tập con lồi của C.
Hệ quả 1.1. Bất cứ điểm cực đại địa phương nào của một hàm lõm trên một
tập lồi cũng là điểm cực đại toàn cục. Tập tất cả các điểm cực đại của một
hàm lõm trên một tập lồi là lồi.
Định lí 1.3. Một hàm lồi chặt f trên một tập lồi C có nhiều nhất một điểm
cực tiểu trên C, nghĩa là tập argminx ∈C f (x ) gồm nhiều nhất một phần tử.
Hàm lồi n biến có mối quan hệ chặt chẽ với hàm lồi một biến.
Định lí 1.4. Hàm f (x), x ∈ Rn , là hàm lồi khi và chỉ khi hàm một biến số
ϕ(λ) ≡ f (x + λd) là hàm lồi theo λ với mỗi x, d ∈ Rn .


7
Định lí 1.5. Hàm lồi chính thường f trên Rn liên tục tại mọi điểm trong của

miền hữu dụng của nó (f liên tục trên int (dom f )).
Nhận xét 1.1. Một hàm lồi chính thường chỉ có thể gián đoạn tại những điểm
biên của miền hữu dụng của nó.
Định lí 1.6. Giả sử f là hàm lồi chính thường trên Rn . Khi đó các điều sau
đây là tương đương:
a) f liên tục tại điểm x0 ;
b) f bị chặn trên trong một tập mở chứa x0 ;
c) int (epi f ) = ∅;
d) int (dom f ) = ∅ và f liên tục trên int (dom f ).
Định lí 1.7. Một hàm thực một biến ϕ(t) khả vi trong một khoảng mở là lồi
khi và chỉ khi đạo hàm của nó ϕ (t) là một hàm không giảm. Một hàm thực
một biến ϕ(t) hai lần khả vi trong một khoảng mở là lồi khi và chỉ khi đạo
hàm cấp hai của nó ϕ (t) không âm trên toàn bộ khoảng này.
√
Ví dụ 1.2. Các hàm ex , x2k với k = 1, 2, ... lồi trên R+ . Các hàm ln x, x
lõm trong R+ .
Để nhận biết hàm lồi, người ta còn sử dụng các tiêu chuẩn sau (trường
hợp khả vi).
Định lí 1.8. Cho một tập lồi C ⊂ Rn và một hàm f : Rn → R khả vi trên C:
a) Hàm f lồi trên C khi và chỉ khi:
f (y) ≥ f (x) + ∇f (x), y − x với mọi x, y ∈ C;
b) Nếu f (y) > f (x) + ∇f (x), y − x với mọi x, y ∈ C và x = y thì
hàm f lồi chặt trên C.


8
Định lí 1.9. Cho một tập lồi C ⊂ Rn và một hàm f : Rn → R hai lần khả vi
liên tục trên C. ∇2 f (x) là ma trận các đạo hàm riêng cấp hai của f tại x.
a) Nếu ∇2 f (x) nửa xác định dương với mỗi x ∈ C tức là
y, ∇2 f (x)y ≥ 0 với mọi y ∈ Rn ,

hoặc nếu ∇2 f (x) có mọi giá trị riêng không âm thì hàm f lồi trên C;
b) Nếu ∇2 f (x) xác định dương với mỗi x ∈ C tức là
y, ∇2 f (x)y > 0 với mọi y ∈ Rn \ {0},
hoặc nếu ∇2 f (x) có mọi giá trị riêng dương thì hàm f lồi chặt trên C;
c) Nếu C = Rn và hàm f lồi thì ∇2 f (x) nửa xác định dương với mọi
x ∈ Rn .
Định lí 1.10. Cho Q là một ma trận vuông đối xứng thực cấp n × n. Hàm
toàn phương f (x) = x, Qx lồi khi và chỉ khi Q nửa xác định dương. Hơn
nữa, hàm f lồi chặt khi và chỉ khi ma trận Q xác định dương.
Tiếp theo tác giả giới thiệu một vài khái niệm của hàm nửa liên tục.
Định nghĩa 1.3. Cho không gian Hilbert thực H, một hàm f : H → R. Khi
đó
i) Một hàm f xác định trên tập H được gọi là nửa liên tục dưới tại điểm
x0 ∈ H nếu với mọi ε > 0, tồn tại δ > 0 sao cho f (x) ≥ f (x0 ) − ε, với mọi
x thuộc H thỏa mãn x − x0 < δ;
ii) Hàm f được gọi là nửa liên tục trên trên H tại x0 ∈ H nếu hàm −f
nửa liên tục dưới tại x0 ∈ H;
iii) Hàm f được gọi là liên tục trên H tại điểm x0 ∈ H nếu hàm f
vừa nửa liên tục dưới trên H tại điểm x0 ∈ H và vừa liên tục trên trên
H tại điểm x0 ∈ H;


9
vi) Hàm f được gọi là liên tục (nửa liên tục) trên H nếu hàm f liên tục
(nửa liên tục) tại mọi điểm trên H.
Tiếp theo, tác giả giới thiệu hàm thỏa mãn tính chất KL. Lớp hàm này
đóng vai trò quan trọng trong các kết quả hội tụ của thuật toán đã trình bày.
Với η ∈ (0, +∞), ta kí hiệu θη hàm liên tục và lõm ϕ : [0, η) → [0, +∞)
sao cho ϕ(0) = 0; ϕ là hàm khả vi liên tục trên (0, η); liên tục tại 0 và
ϕ (s) > 0 ∀s ∈ (0, η). Trong các điều kiện sau xét trong [4] chúng tôi cũng

xét hàm khoảng cách đến một điểm được xác định với E ⊆ Rm như sau
dist (x, E) = infy∈E x − y

∀x ∈ Rm .

Định nghĩa 1.4. (tính chất Kurdyka-Lojasiewicz)
Giả sử f : Rm → (−∞, +∞] hàm nửa liên tục dưới chính thường. Hàm f
thỏa mãn tính chất KL tại
x ∈ dom∂f = {x ∈ Rm : ∂f (x) = ∅} nếu ∃η ∈ (0, +∞],
lân cận U của x và một hàm ϕ ∈ θη sao cho:
U ∩ {x ∈ Rm : f (x) < f (x) < f (x) + η},
ta luôn có bất đẳng thức sau
ϕ (f (x) − f (x)) dist (0, ∂f (x)) ≥ 1.
Nếu f thỏa mãn tính chất KL tại mọi điểm trong dom ∂f , thì f được gọi
là hàm KL.
Hàm f : Rm → R và điểm kì dị x ∈ Rm (tại đó ∇f (x) = 0), tồn tại
θ ∈ [1/2, 1) sao cho hàm | f − f (x) | ∇f

−1

là giới nội chung quanh x.

Tương ứng với trường hợp ϕ(s) = s1−θ . Kết quả của Lojasiewicz cho phép


10
giải thích tính chất KL như việc tham số hóa giá trị của hàm chung quanh
điểm kì dị. Kurdyka mở rộng tính chất này cho hàm lấy khả vi xác định trên
một cấu trúc 0-cực tiểu. Và các mở rộng tiếp theo cho hàm không trơn có
thể xem trong [4].

Bổ đề 1.1. Giả sử Ω ⊆ Rm là tập compact và giả sử f : Rm → (−∞, +∞]
là hàm nửa liên tục dưới chính thường. Giả thiết f là hàm hằng trên Ω và f
thỏa mãn tính chất KL tại mọi điểm của Ω. Thì ta có ε, η > 0 và ϕ ∈ θη ,
sao cho ∀x ∈ Ω và mỗi x trong giao
{x ∈ Rm : dist (x , Ω ) < ε} ∩ {x ∈ Rm : f (x ) < f (x ) < f (x ) + η}, (1.1)
ta luôn có bất đẳng thức sau
ϕ (f (x) − f (x)) dist (0 , ∂f (x )) ≥ 1 .

(1.2)

Bổ đề 1.2. Giả sử (an )n∈N và (bn )n∈N là dãy thực sao cho bn ≥ 0 ∀n ∈ N,
(an )n∈N bị giới nội dưới và an+1 + bn ≤ an ∀n ∈ N thì (an )n∈N là dãy đơn
điệu giảm, hội tụ và Σn∈N bn < +∞ cũng hội tụ.
Bổ đề 1.3. Giả sử (ξn )n∈N và (εn )n∈N là dãy trong [0, +∞) sao cho
Σn∈N εn < +∞vàξn+1 ≤ aξn + bξn−1 + εn ∀n ≥ 1.
Khi đó a ∈ R, b ≥ 0 và a + b < 1 thì Σn∈N ξn < +∞.
Chứng minh. Cố định k ≥ 1 là số nguyên dương. Theo giả thiết bất đẳng
thức cho n = 1, ..., k. Ta có:
k

k

ξn + ξk+1 − ξ0 − ξ1 ≤ a
n=0

từ đó,

k

ξn − aξ0 − bξk +


ξn + b
n=0

k

n=0

ξn ≥ 0 ∀n ∈ N và b ≥ 0,

εn ,
n=1


11
ta được,
k

(1 − a − b)

k

ξn ≤ (1 − a)ξ0 + ξ1 +
n=0

εn .
n=1

Và kết luận.


1.2

Các khái niệm dưới vi phân mở rộng

Cho f : Rm → (−∞, +∞] là hàm nửa liên tục dưới chính thường. Nếu
x ∈ dom f chúng ta xét dưới vi phân Fréchet (độ mềm) của f tại x ta đặt:
ˆ (x) = {v ∈ Rm : lim inf f (y) − f (x) − v, y − x ≥ 0}.
∂f
y→x
y−x
ˆ (x) : = ∅. Giới hạn (Mordukhovich) dưới vi
Cho x ∈
/ dom f ta đặt ∂f
phân được xác định tại x ∈ dom f như sau:
∂f (x) ={v ∈ Rm : ∃xn → x, f (xn ) → f (x)
ˆ (xn ) khi vn → v, n → ∞}.
và ∃vn ∈ ∂f
Trong đó x ∈
/ dom f lấy ∂f (x) : = ∅.
Lưu ý rằng trong trường hợp f là hàm lồi, các khái niệm trên trùng với
dưới vi phân lồi, có nghĩa là ∀x ∈ dom f
ˆ (x) = ∂f (x) = {v ∈ Rm : f (y) ≥ f (x) + v, y − x ∀y ∈ Rm }.
∂f
ˆ (x) ⊆ ∂f (x) với x ∈ Rm . Ta cũng sử dụng các tiêu
Lưu ý bao hàm ∂f
chuẩn liên quan tới đồ thị của dưới vi phân giới hạn: Nếu (xn )n∈N và (vn )n∈N
là dãy trong Rm sao cho (∀n ∈ N)
vn ∈ ∂f (xn ), (xn , vn ) → (x, v) và f (xn ) → f (x) khi n → +∞,
khi đó v ∈ ∂f (x).
Nguyên lý Fremat được phát biểu trong trường hợp không trơn như sau:



12
Nếu x ∈ Rm là lân cận gần của f , thì 0 ∈ ∂f (x). Trong trường hợp f là
khả vi liên tục x ∈ Rm ta có ∂f (x) = {∇f (x)}. Kí hiệu
crit (f ) = {x ∈ Rm : 0 ∈ ∂f (x )},
là tập tất cả (giới hạn) các điểm kì dị của f . Cũng cần lưu ý đến quy tắc
dưới vi phân sau: Nếu f : Rm → (−∞, +∞] là hàm nửa liên tục dưới chính
thường và h : Rm → R là hàm khả vi liên tục khi đó
∂(f + h)(x) = ∂f (x) + ∇h(x) ∀x ∈ Rm .

1.3

Một số khoảng cách cần dùng

Trong các điều kiện sau xét trong [4] tác giả cũng xét hàm khoảng cách
đến một điểm được xác định với E ⊆ Rm như sau
dist (x, E) = infy∈E x − y

∀x ∈ Rm .

Kí hiệu
Du : Rm × Rm → R, Du (x, y) = u(x) − u(y) − ∇u(y), x − y ,
là khoảng cách Bregman từ x đến y dựa vào hàm u : Rm → R giả thiết là
σ
. 2 là một hàm lồi) khả vi sao
σ-lồi mạnh với tham số σ > 0 (đó là u −
2
cho ∇u là L∇u -liên tục Lipschitz với L∇u > 0.
Lưu ý tính chất này thỏa mãn bất đẳng thức sau

σ
x−y
2

1.4

2

≤ Du (x, y) ≤

L∇u
x−y
2

2

∀(x, y) ∈ Rm × Rm .

Thuật toán điểm gần kề quán tính cho hàm lồi

Như đã thấy [3, Mệnh đề 26.1] cực tiểu hóa hàm f ∈ Γ0 (H) rút cuộc là
tìm 0 điểm của toán tử dưới vi phân ∂f , là toán tử đơn điệu cực đại với giải


13
thức J∂f = Proxf . Do đó, cực tiểu hóa của f có thể đạt được qua thuật toán
điểm gần kề [3, (23.31)]
Định lí 1.11 (Thuật toán điểm gần kề). Cho f ∈ Γ0 (H) với argminf = ∅,
cho (γn )n∈N là dãy trong R++ sao cho Σn∈N γn = +∞, và cho x0 ∈ H. Đặt
(∀n ∈ N) xn+1 = Proxγn f xn .


(1.3)

thỏa mãn các điều kiện sau:
(i) (xn )n∈N là dãy cực tiểu hóa của f ; chính xác hơn, f (xn ) ↓ inf f (H);
(ii) (xn )n∈N hội tụ yếu đến điểm trong argminf ;
(iii) Giả sử f là lồi đều trên mỗi tập hợp con bị chặn khác rỗng của domf .
Thì dãy (xn )n∈N hội tụ mạnh đến một điểm duy nhất trong argmin f .
Chứng minh. (i) Cho z ∈ argmin f . Từ (1.3) và [3, (16.30)] ta có:
(∀n ∈ N) xn − xn+1 ∈ γn ∂f (xn+1 ).

(1.4)

Từ [3, (16.1)] ta có (∀n ∈ N)
z − xn+1 | xn − xn+1 /γn ≤ f (z) − f (xn+1 ).

(1.5)

Và (∀n ∈ N)
0 ≤ xn − xn+1 | xn − xn+1 /γn ≤ f (xn ) − f (xn+1 ).

(1.6)

Vì thế, với mỗi n ∈ N, (1.5) cho
xn+1 − z

2

= xn − z


2

+ 2 xn − z | xn+1 − xn

+ xn+1 − xn
= xn − z

2

− xn+1 − xn

2
2

+ 2 xn+1 − z | xn+1 − xn
≤ xn − z

2

− 2γn (f (xn+1 ) − inf f (H)).

(1.7)


14
Điều này cho thấy (xn )n ∈ N là đơn điệu Fejér với argmin f và
γn (f (xn+1 ) − inf f (H)) < +∞.
n∈N

Vì thế, từ


n∈N γn

= +∞, ta có limf (xn ) = inf f (H) và theo (1.6) ta

có f (xn ) ↓ inf f (H).
(ii) Cho x là điểm hội tụ yếu của dãy (xn )n∈N . Theo (i) và [3, Mệnh đề
11.20] ta có x ∈ argmin f . Áp dụng [3, Định lý 5.5].
(iii) Từ (ii) và [3, Định lý 16.2] có x ∈ argmin f ⊂ dom ∂f sao cho
xn → x, và từ (1.7) và (1.4) có (xn+1 )n∈N là dãy bị chặn trong dom f . Vì
thế, {x} ∪ {xn+1 }n∈N là tập hợp con bị chặn của dom ∂f và từ [3, (10.2)]
ta suy ra tồn tại hàm tăng φ : R+ → [0, +∞] triệt tiêu duy nhất ở 0 sao cho
(∀n ∈ N \ {0})
1
f (xn ) + f (x)
φ( xn − x ) ≤
−f
4
2

xn + x
.
2

(1.8)

Từ (i) ta có f (xn ) ↓ f (x). Ngoài ra, từ [3, Mệnh đề 10.23], f là nửa liên
tục dưới yếu và từ (xn + x)/2 → x, ta có
f (x) ≤ limf ((xn + x)/2) ≤ limf ((xn + x)/2)
≤ lim(f (xn ) + f (x))/2 = f (x).

Suy ra, φ( xn − x ) → 0 khi đó xn → x.


15

Chương 2

Phương pháp điểm gần kề quán tính cho bài
toán tối ưu không lồi và không trơn
Chương này tác giả trình bày hai loại thuật toán: Thuật toán tiến-lùi và
thuật toán tiến-lùi-tiến loại Tseng. Thuật toán tiến-lùi-tiến loại Tseng chính
là một cải tiến của thuật toán tiến-lùi với điều kiện sử dụng độ lớn của các
bước loại Nesterov. Trước tiên tác giả giới thiệu về thuật toán tiến-lùi.

2.1

Thuật toán tiến-lùi

Định lí 2.1 (Thuật toán tiến-lùi). Cho A : H → 2H là đơn điệu cực đại,
β ∈ R++ , B : H → H là β-đồng bức, γ ∈ (0, 2β), và đặt:
δ = min{1, β/γ} + 1/2.
Ngoài ra, đặt (λn )n∈N là dãy thuộc [0, δ] sao cho Σn∈N λn (δ−λn ) = +∞,
x0 ∈ H. Giả sử zer(A + B) = ∅ ta đặt:


yn = xn − γBxn ,
(∀n ∈ N)

xn+1 = xn + λn (JγA yn − xn ).
thỏa mãn các điều kiện sau:

(i) (xn )n∈N hội tụ yếu đến điểm thuộc zer(A + B );

(2.1)


16
(ii) Giả sử inf n∈N λn > 0 và đặt x ∈ zer(A + B ). Thì (Bxn )n∈N hội tụ
mạnh đến Bx;
(iii) Giả sử inf n∈N λn > 0 và các điều kiện sau được thỏa mãn:
(a) A là đơn điệu đều trên mỗi tập con khác rỗng bị chặn của dom A
(b) B là đơn điệu đều trên mỗi tập con khác rỗng bị chặn của H.
Khiđó (xn )n∈N hội tụ mạnh đến điểm duy nhất thuộc zer(A + B ).
Chứng minh. Đặt T = JγA ◦ (Id − γB) và α = 1/δ. Từ [3, Hệ quả 23.8] và
[3, Chú ý 4.24(iii)] bao hàm JγA là 1/2-trung bình. Mặt khác, theo [3, Mệnh
đề 4.33] bao hàm Id − γB là γ/(2β)-trung bình. Khi đó, theo[3, Mệnh
đề 4.32] bao hàm T là α-trung bình. Hơn nữa, theo [3, Mệnh đề 25.1(iv)],
FixT = zer(A + B ). Từ (2.1) ta suy ra rằng (xn )n∈N được tạo ra bởi [3,
(5.15)].
(i) Chứng minh dựa trên [3, Mệnh đề 5.15(iii)].
(ii) Đặt x ∈ zer(A + B ) = FixT và ε = inf n∈N λn . Theo [3, Mệnh đề
4.25(iii)] ta được, với mọi n ∈ N,
T xn − x

2

= JγA (xn − γBxn ) − JγA (x − γBx)
≤ (Id − γB)xn − (Id − γB)x
≤ xn − x

2


2

2

− γ(2β − γ) Bxn − Bx

(2.2)
2

.


17
Sử dụng [3, Hệ quả 2.14] và bất đẳng thức δ > 1, ta được:
xn+1 − x

2

= (1 − λn )(xn − x) + λn (T xn − x)
= (1 − λn ) xn − x

2

+ λn T xn − x

− λn (1 − λn ) T xn − xn
≤ xn − x

2


2

2
2
2

− γ(2β − γ)λn Bxn − Bx

− λn (1 − λn ) T xn − xn
≤ xn − x

2

2

− γ(2β − γ)ε Bxn − Bx

+ δ(δ − 1) T xn − xn

2

(2.3)

2

.

Sử dụng [3, Mệnh đề 5.15(i),(ii)] và [3, Mệnh đề 5.4(ii)], ta đạt được:
γ(2β − γ)ε Bxn − Bx


2

≤ ( xn − x

2

− xn+1 − x 2 )

+ δ(δ − 1) T xn − xn

2

(2.4)

→ 0.
Và kết luận.
(iii) Như đã thấy ở (i), tồn tại x ∈ zer(A + B ) sao cho xn → x.
a) Đặt (∀n ∈ N) zn = JγA yn . Khi đó:
−γBx ∈ γAx và xn − γBxn − zn = yn − zn ∈ γAzn .

(2.5)

Mặt khác, từ [3, Mệnh đề 5.15(ii)] ta được:
zn − xn = T xn − xn → 0.

(2.6)

Do đó, zn → x và C = {x} ∪ {zn }n∈N là tập hợp con bị chặn của dom A.
Từ [1, (22.5)] và (2.5) tồn tại hàm tăng φA : R+ → [0, +∞] triệt tiêu duy

nhất tại 0 sao cho:
(∀n ∈ N) zn − x | xn − zn − γ(Bxn − Bx) ≥ γφA ( zn − x ). (2.7)


18
Tuy nhiên, zn −x → 0 và từ (2.6) và (ii) ta có xn −zn −γ(Bxn −Bx) → 0.
Do đó, từ (2.7) ta có φA ( zn − x ) → 0, do đó zn → x. Theo (2.6), ta kết
luận xn → x.
b) Vì xn → x, C = {x} ∪ {xn }n∈N là tập con bị chặn của H. Khi đó, từ
[3, (22.5)] tồn tại hàm tăng φB : R+ → [0, +∞] triệt tiêu duy nhất tại 0 sao
cho:
(∀n ∈ N) xn − x | Bxn − Bx ≥ γφB ( xn − x ).

(2.8)

Do đó, (ii) cho φB ( xn − x ) → 0 suy ra xn → x.
Chúng tôi kết luận mục này với hai trường hợp hội tụ tuyến tính của thuật
toán tiến-lùi.
Mệnh đề 2.1. Cho D là tập con đóng khác rỗng của H, A : H → 2H là đơn
điệu cực đại sao cho dom A ⊂ D, B : D → H và α, β ∈ R++ . Thỏa mãn
các điều kiện sau
(i) A là α-đơn điệu mạnh, B là β-đồng bức, và γ ∈ (0, 2β);
(ii) α ≤ β, B là α-đơn điệu mạnh và β-liên tục Lipschitz, và γ ∈ (0, 2α/β 2 ).
Lấy x0 ∈ D và đặt:
(∀n ∈ N)



yn = xn − γBxn


(2.9)


xn+1 = JγA yn ,
khi đó (xn )n∈N hội tụ tuyến tính đến điểm duy nhất thuộc zer(A + B ).
Chứng minh. Đặt T = JγA ◦ (Id − γB) lưu ý rằng từ [3, Mệnh đề 25.1(iv)],
FixT = zer(A+B ). Vì [3, Mệnh đề 23.2(i)] khẳng định rằng JγA = domA,
T là toán tử xác định từ D đến D, và (2.9) ta có (∀n ∈ N) xn+1 = T xn . Từ
đó, D là tập con đóng của H, là không gian metric đầy đủ [3, Định lý 1.48],
điều này cho thấy trong cả hai trường hợp T là liên tục Lipschitz với hằng số


19
thuộc [0,1).
(i) Đặt τ = 1/(αγ + 1). Từ [3, Mệnh đề 23.11] ta có JγA là liên tục
Lipschitz với hằng số τ . Mặt khác, từ [3, Mệnh đề 4.33] và [3, Chú ý 4.24(i)]
ta có Id − γB là không giãn. Vậy T là liên tục Lipschitz với hằng số
τ ∈ (0, 1).
(ii) Ta có γ(2α−γβ 2 ) ∈ (0, 1] và đặt τ =

1 − γ(2α − γβ 2 ). Mặt khác,

từ [3, Hệ quả 23.10(i)] ta có JγA là không giãn. Lại có, với mọi x, y ∈ D ta
có:
(Id − γB)x − (Id − γB)y

2

= x−y


2

+ γ 2 Bx − By

2

− 2γ x − y | Bx − By
≤ x−y

2

− 2γα x − y

+ γ 2β 2 x − y

2

(2.10)

2

= (1 − γ(2α − γβ 2 )) x − y

2

.

Vậy T là liên tục Lipschitz với hằng số τ ∈ [0, 1).

2.2


Thuật toán tiến-lùi-tiến loại Tseng

Trong phần này, tác giả nghiên cứu tính hội tụ của thuật toán quán tính
loại Tseng cho bài toán tối ưu không lồi và không trơn. Ta xét bài toán sau:
Bài toán 2.1. Giả sử m ≥ 1 là số nguyên dương f : Rm → (−∞, +∞] là
hàm nửa liên tục dưới chính thường và giới nội dưới, cho h : Rm → R là
hàm khả vi Fréchet sao cho ∇h là L∇h -liên tục Lipschitz với L∇h ≥ 0. Ta
xét bài toán cực trị sau:
(P ) infm [f (x) + h(x)].
x∈R

(2.11)

Lấy gần đúng các điểm kì dị của hàm mục tiêu bằng một dãy sinh bởi,


20
thuật toán tiến-lùi-tiến loại quán tính.
Chính xác hơn, chúng tôi trình bày sơ đồ lặp sau
Thuật toán 2.1. Chọn x0 , x1 ∈ Rm , λ, λ > 0, α ≥ 0 và dãy (λn )n≥1 ,
(αn )n≥1 ta có:
0 ≤ αn ≤ α, ∀n ≥ 1 và 0 < λ ≤ λn ≤ λ, ∀n ≥ 1.
Xét sơ đồ lặp


1

pn ∈ argminx∈Rm f(x) + Du (x, xn ) + b1
λn

(∀n ≥ 1)


x
= p + λ [∇h(x ) − ∇h(p )],
n+1

n

n

n

(2.12)

n

với
b1 = x, ∇h(xn ) +

αn
x, xn−1 − xn ,
λn

do đó
Du : Rm × Rm → R, Du (x, y) = u(x) − u(y) − ∇u(y), x − y
được kí hiệu là khoảng cách Bregman từ x đến y dựa vào hàm u : Rm → R
σ
giả thiết là σ - lồi mạnh với tham số σ > 0 (đó là u −
. 2 là một hàm lồi),

2
khả vi sao cho ∇u là L∇u -liên tục Lipschitz với L∇u >0.
Lưu ý là các tính chất này của hàm u thỏa mãn bất đẳng thức sau(xem
[4])
σ
x−y
2

2

≤ Du (x, y) ≤

L∇u
x−y
2

2

∀(x, y) ∈ Rm × Rm .

(2.13)

Tiếp theo, vì f là nửa liên tục dưới chính thường và giới nội dưới và Du
bức với biến thứ nhất (đó là lim

x →+∞ Du (x, y)

= +∞ ∀y ∈ Rm ), sơ đồ

lặp này đã được xác định, nghĩa là sự tồn tại của pn là được đảm bảo với mỗi