ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

ĐỖ KHẮC HUẤN

PHƯƠNG PHÁP ĐỐI NGẪU TRONG BÀI TOÁN BIẾN
PHÂN KHÔI PHỤC TÍN HIỆU

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

Hà Nội - 2011


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

ĐỖ KHẮC HUẤN

PHƯƠNG PHÁP ĐỐI NGẪU TRONG BÀI TOÁN BIẾN
PHÂN KHÔI PHỤC TÍN HIỆU

Chuyên ngành: Toán học tính toán
Mã số: 60.46.30

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

Người hướng dẫn khoa học:
GS.TSKH. ĐINH DŨNG

Hà Nội - 2011

Mục lục
Lời cảm ơn

iii

Giới thiệu

1

1 Các kiến thức chuẩn bị

7

1.1

Các công cụ giải tích lồi . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.1

Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.2

Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


8

1.1.3

Hàm nửa liên tục dưới . . . . . . . . . . . . . . . . . . . . . . .

9

1.1.4

Vi phân mạnh, vi phân yếu . . . . . . . . . . . . . . . . . . . .

9

1.1.5

Hàm liên hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.1.6

Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1.1.7
1.2

Toán tử không giãn chặt


. . . . . . . . . . . . . . . . . . . . .

12

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

12

1.2.1

Toán tử proximity . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.2.2

Các ví dụ về toán tử proximity . . . . . . . . . . . . . . . . . .

14

1.2.3

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

18

2 Phương pháp đối ngẫu trong các bài toán biến phân khôi phục tín
hiệu


3

21

2.1

Đối ngẫu Fenchel- Moreau- Rockafellar . . . . . . . . . . . . . . . . . .

21

2.2

Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.3

Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

Ứng dụng trong các bài toán khôi phục tín hiệu
3.1

Xấp xỉ tốt nhất chấp nhận được . . . . . . . . . . . . . . . . . . . . .
i

31
31



MỤC LỤC
3.2

Xấp xỉ tốt nhất mềm chấp nhận được . . . . . . . . . . . . . . . . . . .

37

3.3

Khử nhiễu theo từ điển . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.4

Khử nhiễu với các hàm giá . . . . . . . . . . . . . . . . . . . . . . . .

47

Kết luận

53

Bảng ký hiệu

54

Tài liệu tham khảo


55

Chỉ dẫn

59

ii


Lời cảm ơn
Đầu tiên, tác giả xin được gửi lời cảm ơn sâu sắc đến người thầy, người hướng dẫn
khoa học của mình, GS.TSKH. Đinh Dũng, người đã đưa ra đề tài, luôn quan tâm và
tận tình hướng dẫn trong suốt quá trình nghiên cứu của tác giả. Đồng thời tác giả
cũng chân thành cảm ơn các thầy cô trong khoa Toán - Cơ - Tin học, phòng Sau đại
học, Ban giám hiệu Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, đã
tận tình giảng dạy, hướng dẫn trong thời gian học tập tại trường, đã tạo mọi điều kiện
cho tác giả về tài liệu và thủ tục hành chính để tác giả hoàn thành bản luận văn này.
Tác giả cũng chân thành cảm ơn Ban giám hiệu, tổ Toán trường THPT Sơn Tây đã
tạo mọi điều kiện thuận lợi nhất để tác giả có thế hoàn thành khóa học. Tác giả cũng
gửi lời cảm ơn đến bạn bè, đặc biệt là bạn bè trong nhóm Toán học tính toán 08-10,
đã động viên và cổ vũ rất nhiều trong suốt thời gian vừa qua.
Do thời gian và trình độ còn hạn chế, chắc chắn bản luận văn không thể tránh khỏi
những thiếu sót, tác giả rất mong nhận được những ý kiến đóng góp quý báu của các
thầy cô và bạn bè đồng nghiệp, tác giả xin chân thành cảm ơn!

Hà Nội, tháng 02 năm 2011
Học viên

Đỗ Khắc Huấn


iii


Giới thiệu
Trong tối ưu lồi, lí thuyết đối ngẫu nhiều lúc có thể dẫn đến các phương pháp giải
bài toán đối ngẫu đơn giản và hiệu quả hơn là việc giải trực tiếp bài toán ban đầu.
Trong luận văn này, chúng ta áp dụng phương pháp đối ngẫu cho các bài toán biến
phân phức hợp nảy sinh trong khôi phục tín hiệu. Những bài toán này không dễ giải
với các phương pháp trực tiếp, nhưng thông qua việc áp dụng phương pháp đối ngẫu
Fenchel - Moreau - Rockafellar có thể giải chúng bằng thuật toán tách tiến lùi [18].
Chúng ta sẽ trình bày một thuật toán được đề xuất trong [14], nó đồng thời xây dựng
được một dãy hội tụ yếu đến nghiệm của bài toán đối ngẫu và một dãy hội tụ mạnh
đến nghiệm của bài toán ban đầu.
Trải qua nhiều năm, một số cấu trúc đã được hình thành nhằm hợp nhất các
phương pháp giải tích và các phương pháp giải số đối với các bài toán khôi phục tín
hiệu. Từ năm 1978 Yonla [40] đã chỉ ra rằng một số bài toán khôi phục tín hiệu có
một đặc điểm chung là đều chứa một cấu trúc hình học đơn giản và có thể qui được
về dạng bài toán tối ưu trong một không gian Hilbert H như sau: tìm một tín hiệu x
trong một không gian véctơ con đóng C trong H, sao cho khoảng cách từ x tới tín hiệu
z là nhỏ nhất, biết rằng ảnh của x lên một không gian véctơ con đóng V là r. Điều
này dẫn đến giải bài toán biến phân
minimize
x∈C
PV x=r

1
x − z 2,
2


(1)

trong đó PV kí hiệu là phép chiếu lên V . Các bài toán khôi phục tín hiệu trong không
gian Hilbert đã được nghiên cứu bởi nhiều tác giả khác nhau. Chẳng hạn, năm 1965,
Levi [26] đã nghiên cứu bài toán cực tiểu hóa tín hiệu x, có giải tần hữu hạn và có năng
lượng nhỏ nhất thông qua N phép đo tuyến tính. Trong không gian Hilbert H = L2 (R),

1


Giới thiệu
bài toán biến phân này có dạng
minimize
x∈C
x|s1 =ρ1

1
x 2,
2

(2)

..
.

x|sN =ρN

trong đó C là không gian con của không gian các tín hiệu có giải tần bị chặn, (si )1≤i≤N ∈
HN là các tín hiệu đo, và (ρi )1≤i≤N ∈ RN là các phép đo. Trong [33], Potter và Arun
đã nhận xét rằng: với một tập con lồi đóng C Bài toán (2) xuất hiện trong nhiều bài

toán khác nhau, từ việc đánh giá phổ [3, 36], chụp cắt lớp [27] đến các bài toán ngược
[4]. Họ đã dùng phương pháp đối ngẫu để giải nó, dẫn đến thuật toán.
Mệnh đề 0.0.1. [33, Định lí 1 và 3] Đặt r = (ρi )1≤i≤N và L : H → RN : x →
N

( x | si )1≤i≤N , cho γ ∈]0, 2[ . Giả sử rằng

si

2

≤ 1 và r nằm trong tập các điểm

i=1

trong tương đối của L(C). Đặt
ω0 ∈ RN và (∀n ∈ N) ωn+1 = ωn + γ(r − LPC L∗ ωn ),
trong đó L∗ : RN → H : (vi )1≤i≤N →

(3)

N

vi si là toán tử liên hợp của L. Khi đó dãy
i=1

(ωn )n∈N hội tụ đến một điểm ω sao cho LPC L∗ ω = r và PC L∗ ω là nghiệm của Bài toán
(2).
Phương pháp đối ngẫu đóng một vai trò trọng tâm trong lí thuyết tối ưu hóa hàm
lồi [21, 31, 35, 41] và nó đã được sử dụng một cách rộng rãi với những mục đích khác

nhau trong các bài toán khôi phục tín hiệu, chúng ta có thể tìm thấy điều này trong các
bài báo [3, 5, 8, 10, 18, 20, 22, 23, 24, 25, 39]. Những khía cạnh khác của lí thuyết đối
ngẫu trong xử lí ảnh đã được nghiên cứu trong [6]. Dạng đối ngẫu thích hợp nhất đối
với các bài toán biến phân khôi phục tín hiệu là đối ngẫu Fenchel-Moreau-Rockafellar,
có liên quan đến việc cực tiểu hóa bài toán ban đầu với việc cực tiểu hóa bài toán đối
ngẫu với các hàm liên hợp và toán tử liên hợp với các hàm và toán tử trong bài toán
ban đầu. Nhìn chung, phương pháp đối ngẫu đã mở rộng các lớp bài toán ban đầu.
Hơn nữa, việc giải bài toán đối ngẫu còn có thể giúp ta tìm được nghiệm của bài toán
ban đầu từ bất kì nghiệm đối ngẫu nào. Với các giả thiết như Mệnh đề 0.0.1 Bài toán
(2) sẽ rất khó giải, nhưng nếu C đơn giản, bài toán đối ngẫu có thể giải được một cách
hiệu quả và nghiệm của bài toán ban đầu có thể được khôi phục dễ dàng. Nguyên lí
2


Giới thiệu
đối ngẫu này cũng được áp dụng trong các bài toán khôi phục tín hiệu khác. Chẳng
hạn, nó có thể áp dụng cho bài toán biến phân có nhiễu
minimize g(Lx) +
x∈H

1
x−z
2

2

,

(4)


trong đó z là một tín hiệu quan sát được nhưng bị nhiễu của một tín hiệu lí tưởng, L là
một toán tử tuyến tính bị chặn từ H vào một không gian Hilbert G và g : G →]−∞, +∞]
là một hàm lồi chính thường nửa liên tục dưới. Một hướng phát triển nổi tiếng là thuật
toán biến phân toàn phần giải số bài toán khôi phục ảnh có nhiễu được đưa ra trong
[8] và được hoàn chỉnh trong [9].
Mục đích chính của bản luận văn là trình bày phương pháp đối ngẫu để giải các
Bài toán (1) và (2), cải tiến các thuật toán hiện có, chuẩn hóa các kĩ thuật đối ngẫu
trong các bài toán khôi phục tín hiệu và mở rộng những ứng dụng to lớn của chúng.
Các kết quả này đã được công bố chủ yếu trong bài báo [14] và một phần trong bài
báo [18]. Điều cần nhấn mạnh là các lớp bài toán biến phân mà chúng ta nghiên cứu
phải thỏa mãn các yêu cầu sau đây:
(a) Chúng bao trùm các bài toán cực tiểu ở trên.
(b) Chúng không dễ giải trực tiếp nhưng lại thích hợp cho phương pháp đối ngẫu
Fenchel-Moreau- Rockafellar, phương pháp có thể giải được một cách chắc chắn
theo nghĩa xây dựng một thuật toán khả thi, thuật toán này tạo ra hai dãy lặp:
một dãy hội tụ yếu đến nghiệm của bài toán đối ngẫu và một dãy hội tụ mạnh
đến nghiệm của bài toán ban đầu. Các thuật toán này không chứa các chương
trình con, những chương trình không đảm bảo hội tụ sau một số hữu hạn bước
lặp, điều đó có thể làm khuyếch đại sai số sau mỗi bước lặp.
(c) Các thuật toán này cho phép xây dựng nghiệm của bài toán ban đầu từ một
nghiệm bất kì của bài toán đối ngẫu.
Bài toán 0.0.2. (Bài toán ban đầu) Cho H và G là các không gian Hilbert thực,
z ∈ H, r ∈ G, cho f : H →] − ∞, +∞] và g : G →] − ∞, +∞] là các hàm lồi nửa liên
tục dưới và cho L : H → G là một toán tử tuyến tính khác không, bị chặn sao cho điều
kiện
r ∈ sri (L(dom f ) − dom g)
3

(5)



Giới thiệu
được thỏa mãn. Bài toán là
minimize f (x) + g(Lx − r) +
x∈H

1
x−z
2

2

.

(6)

Trước hết, chúng ta có một số bình luận về bài toán này.
Liên quan đến Điều kiện (a), khi f = 0 thì Bài toán (6) trở thành Bài toán (4).
Nếu cho f và g tương ứng là các hàm chỉ (xem (1.5) ) của các tập con lồi đóng C ⊂ H
và D ⊂ G thì Bài toán (6) được qui về bài toán xấp xỉ tốt nhất
minimize
x∈C
Lx−r∈D

1
x − z 2.
2

(7)


Nếu trong phương trình trên ta chọn C là một không gian véctơ con đóng của H và
D = {0} thì Bài toán (1) tương ứng với trường hợp H = G và L = PV , trong khi đó
Bài toán (2) sẽ ứng với trường hợp G = RN , L : H → RN : x → ( x | si )1≤i≤N , r =
(ρi )1≤i≤N và z = 0. Như trong Chương 3 sẽ trình bày thì Bài toán 0.0.2 là sự mở rộng
của các bài toán khôi phục tín hiệu.
Liên quan đến Điều kiện (b), một câu hỏi tự nhiên được đặt ra là Bài toán (6) có
thể giải được theo các thuật toán đã có hay không ? Chúng ta hãy đặt
h : H →] − ∞, +∞] : x → f (x) + g(Lx − r).

(8)

Do tính chất của các hàm f và g mà ta giả thiết ở trên thì h cũng là một hàm lồi chính
thường nửa liên tục dưới. Do đó toán tử proximity của h (ta sẽ định nghĩa ở phần sau)
proxh : x → argmin h(y) +
y∈H

1
x−y
2

2

tồn tại và duy nhất. Từ đó Bài toán 0.0.2 có nghiệm duy nhất, và nghiệm đó được viết
dưới dạng
x = proxh z.

(9)

Thật khó tính ra một cách cụ thể toán tử proximity của một hàm hợp h như trên,
do đó một trong các phương pháp được sử dụng là tách biểu thức trong Bài toán (6)

để xây dựng proxh z. Bài toán (6) được viết lại dưới dạng
minimize {f1 (x) + f2 (x)} ,
x∈H

(10)

trong đó
f1 : x → f (x) +

1
x−z
2
4

2

và f2 : x → g(Lx − r)

(11)


Giới thiệu
là các hàm lồi nửa liên tục dưới từ H vào ] − ∞, +∞]. Để giải quyết Bài toán (10)
chúng ta có thể sử dụng thuật toán tách tiến lùi được trình bày trong [18] theo lược
đồ sau:




x


n+

1
2

= ∇f2 (xn ) + a2,n
(12)



xn+1 = xn + λn proxγn f1 xn − γn xn+ 1

+ a1,n − xn ,

2

trong đó yêu cầu hàm f2 khả vi Lipschitz trên H; λn > 0; γn > 0 và a1,n , a2,n tương ứng
là các mô phỏng sai số của các toán tử proximity của f1 và gradient của f2 . Các kết
quả cụ thể về sự hội tụ của dãy lặp (xn )n∈N trong thuật toán trên sẽ được trình bày kĩ
hơn trong Định lí 1.2.21. Khi hàm f2 không thỏa mãn điều kiện khả vi Lipschitz trên
H thì ta có thể giải Bài toán (10) bằng cách sử dụng thuật toán Douglas-Rachford [16].



xn+ 1 = proxγf2 xn + a2,n
2
(13)



xn+1 = xn + λn proxγf1 (2xn+ 1 − xn ) + a1,n − xn+ 1 ,
2

2

trong đó λn > 0, γ > 0 và a1,n , a2,n tương ứng là mô phỏng sai số của các toán tử
proximity của f1 và f2 (xem [16, Định lí 20], các kết quả hội tụ chính xác và các ứng
dụng của nó có thể tham khảo thêm trong [12]). Tuy nhiên phương pháp này yêu cầu
toán tử proximity của hàm hợp f2 trong Phương trình (11) phải được tính toán cụ
thể với sai số xác định. Trong trường hợp tổng quát điều này rất khó thực hiện được,
như trong Ví dụ 1.2.6 toán tử proxf2 được tính thông qua toán tử proxg với giả thiết
nghiêm ngặt L ◦ L∗ = κId, trong đó κ > 0. Với yêu cầu khắt khe như vậy thì thật khó
áp dụng phương pháp này cho Bài toán 0.0.2 và nhiều bài toán quan trọng khác khác.
Trong [2] có trình bày một phương pháp thích hợp cho các bài toán
minimize h1 (x) + h2 (x) +
x∈H

1
x−z
2

2

,

(14)

trong đó h1 và h2 là các hàm lồi nửa liên tục dưới từ H vào ] − ∞, +∞] sao cho
dom h1 ∩dom h2 = ∅. Bài toán (14) trùng với Bài toán (6) khi h1 = f và h2 = g(Lx−r).
Để giải Bài toán (14) chúng ta có thể sử dụng thuật toán Dykstra-thuật toán tương tự


5


Giới thiệu
được trình bày trong [2] như sau:



Khởi tạo








y 0 = z





q0 = 0









p0 = 0



For n = 0, 1 · · ·







xn = proxh2 (yn + qn )





qn+1 = yn + qn − xn









yn+1 = proxh1 (xn + pn )





p
n+1 = xn + pn − yn+1

(15)

Thuật toán này yêu cầu các toán tử proximity của các hàm h1 và h2 được tính toán
ở dạng hiển. Cũng giống như thuật toán Douglas-Rachford thì yêu cầu nãy cũng rất
khó thực hiện với những hàm hợp f2 . Như vậy những kĩ thuật tách hiện có thật khó
áp dụng với Bài toán 0.0.2.
Chính vì lẽ đó, chúng ta sẽ xây dựng một đối ngẫu Frechel-Moreau-Rockafellar,
thông qua đối ngẫu này để giải Bài toán 0.0.2, trong đó chúng ta có thể ước lượng
được các toán tử proxf và proxg với sai số xác định.
Luận văn được trình bày thành 3 chương như sau:
• Chương 1 trình bày những kiến thức cơ bản về giải tích lồi, toán tử proximity và
thuật toán tách tiến lùi.
• Chương 2 trình bày phương pháp đối ngẫu trong các bài toán biến phân khôi
phục tín hiệu.
• Chương 3 trình bày những ứng dụng của phương pháp đối ngẫu trong các bài
toán khôi phục tín hiệu.

6


Chương 1

Các kiến thức chuẩn bị
1.1

Các công cụ giải tích lồi

Luận văn sử dụng các kiến thức về giải tích lồi. Để tiện cho việc xem xét các bài
toán trong các chương tiếp theo, chúng tôi sẽ trình bày các khái niệm dưới đây trong
các không gian Hilbert thực, chi tiết độc giả có thể tham khảo trong cuốn sách [41].

1.1.1

Tập lồi

Cho H và G là các không gian Hilbert thực.
Với x, y ∈ H ta kí hiệu [x, y] := {(1 − λ)x + λy | λ ∈ [0, 1]} , [x, y[:= {(1 − λ)x + λy | λ ∈ [0, 1[} ,
và ]x, y[:= {(1 − λ)x + λy | λ ∈]0, 1[} tương ứng gọi là đoạn thẳng đóng, nửa đoạn
thẳng đóng và đoạn thẳng mở. Một tập con C khác rỗng của H được gọi là lồi nếu
[x, y] ⊂ C với mọi x, y ∈ C và bao nón của C là
coneC =

{λx | x ∈ C}.

(1.1)

λ>0

Nếu C là một tập lồi đóng, hình chiếu của một điểm x ∈ H lên C là một điểm duy
nhất PC x ∈ C sao cho PC x = argmin ξ − x . Ta kí hiệu intC là các điểm trong của
ξ∈C


C, spanC là bao tuyến tính của C, spanC là bao đóng của spanC. Nhân của C kí hiệu
là coreC = {x ∈ C | cone(C − x) = H}, miền trong tương đối mạnh của C là
sriC = {x ∈ C|cone(C − x) = span(C − x)} ;

7

(1.2)


Chương 1. Các kiến thức chuẩn bị
và miền trong tương đối của C là riC = {x ∈ C|cone(C − x) = span(C − x)}. Ta có
intC ⊂ coreC ⊂ sriC ⊂ riC ⊂ C.

(1.3)

Miền trong tương đối mạnh là sự mở rộng của khái niệm miền trong tương đối. Sự mở
rộng này đặc biệt quan trọng trong giải tích lồi với các tập không có miền trong tương
đối trong các không gian vô hạn chiều.

1.1.2

Hàm lồi

Kí hiệu R = R ∪ {−∞, +∞}, với mỗi hàm f : H → R và số λ ∈ R, dom f :=
{x ∈ H | f (x) < +∞}, epi f := {(x, t) ∈ H × R | f (x) ≤ t} và epis f := {(x, t)|f (x) < t}
tương ứng được gọi là miền hữu dụng, trên đồ thị và trên đồ thị chặt của f .
Hàm f được gọi là chính thường nếu
dom f = ∅ và f (x) > −∞, với mọi x ∈ H.
Hàm f được gọi là lồi nếu
∀x, y ∈ H, x = y, ∀λ ∈]0, 1[: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y).


(1.4)

Nếu đẳng thức trên đúng với ” < ” thay vì ” ≤ ” khi đó ta nói rằng hàm f là lồi chặt
. Tương tự như vậy ta nói rằng hàm f là lõm (lõm chặt) nếu hàm −f là lồi (lồi chặt)
Định lý 1.1.1. [41, Định lí 2.1.1] Cho f : H → R. Các mệnh đề dưới đây là tương
đương
(i) f là lồi (lồi chặt);
(ii) hàm ϕx,y : R → R, ϕx,y (t) := f ((1 − t)x + ty) là lồi (lồi chặt) với mọi x, y ∈
H(x = y);
(iii) dom f là tập lồi và
∀x, y ∈ dom f, ∀λ ∈]0, 1[: f (λx + (1 − λ)y ≤ λf (x) + (1 − λ)f (y))
( đánh giá trên sẽ trở nên chặt khi x = y)
(iv) ∀n ∈ N, ∀ x1 , · · · , xn ∈ H, ∀λ1 , · · · , λn ∈]0, 1[, λ1 + · · · + λn = 1 :
f (λ1 x1 + · · · + λn xn ) ≤ λ1 f (x1 ) + · · · + λn f (xn )
(đánh giá trên sẽ trở nên chặt khi x1 , · · · , xn không bằng nhau);
8


Chương 1. Các kiến thức chuẩn bị

(v) epif là một tập con lồi của H × R;
(vi) epis f là một tập con lồi chặt của H × R.
Một số ví dụ đơn giản về hàm lồi
Cho C là một tập con lồi đóng khác rỗng của H. Hàm chỉ tiêu của C là


0,
nếu x ∈ C,
ιC : x →


+∞,
nếu x ∈
/ C.

(1.5)

hàm khoảng cách của C là
dC : H → [0, +∞[: x → inf x − y ,

(1.6)

σC : H →] − ∞, +∞] : u → sup x|y .

(1.7)

y∈C

hàm giá của C là
x∈C

1.1.3

Hàm nửa liên tục dưới

Định nghĩa 1.1.2. Một hàm số f : C → R được gọi là nửa liên tục dưới tại một điểm
x0 ∈ C nếu
lim f (x) ≥ f (x0 ) ∀x ∈ C,
x→x0


hay nói cách khác: với mỗi

> 0 có một số δ > 0 sao cho x ∈ C, x − x0 ≤ δ thì

f (x) > f (x0 ) − . Hàm f được gọi là nửa liên tục dưới trên C nếu nó là nửa liên tục
dưới tại mọi điểm x ∈ C.
Định lý 1.1.3. Một hàm lồi trên C là nửa liên tục dưới trên C khi và chỉ khi với mỗi
số thực µ, tập mức
{x ∈ C | f (x) ≤ µ}
là đóng.

1.1.4

Vi phân mạnh, vi phân yếu

Cho Ω là một tập mở khác rỗng trong H, hàm F : Ω → G được gọi là khả vi theo
nghĩa Fréchet ( khả vi mạnh ) tại x0 ∈ Ω nếu:
∀h ∈ H ( h << 1) , F (x0 + h) = F (x0 ) + A.h + ω(x0 , h),
9


Chương 1. Các kiến thức chuẩn bị
trong đó A ∈ L(H, G) là không gian các toán tử tuyến tính liên tục từ H vào G và
ω(x0 , h)
→ 0 khi h → θ, Ah được gọi là vi phân mạnh của F tại x0 và được kí hiệu
h
là dF (x0 , h). Do đó ta có
dF (x0 , h) = Ah.
Toán tử A được gọi là đạo hàm Fréchet của F tại x0 , kí hiệu là F (x0 ). Vi phân yếu
của F tại x0 là biểu thức

dFw (x0 , h) :=

d
F (x0 + th) − F (x0 )
F (x0 + th) |t=0 = lim
∀h ∈ H, h cố định .
t→0
dt
t

Nếu dFw (x0 , h) = Bh, B ∈ L(H, G) thì B được gọi là đạo hàm yếu ( theo nghĩa
Gateaux) của F tại điểm x0 và được kí hiệu là Fw . Do đó ta cũng có
Fw (x0 )h = Bh.
Nếu F khả vi mạnh tại x0 thì F khả vi yếu tại x0 và Fw (x0 ) = F (x0 ). Nếu phiếm hàm
f : H → R khả vi tại mọi x thì
f (x)h = lim
t→0

f (x + th) − f (x)
= ∇f (x).h,
t

và f ∈ L (X , R) = H∗ , ở đây H∗ là phiếm hàm tuyến tính liên tục trên H.
Định lý 1.1.4. [41, Định lí 2.1.11] Cho D ⊂ (H, · ) là một tập mở, lồi khác rỗng,
f : D → R là một phiếm hàm khả vi theo nghĩa Gateaux trên D. Khi đó các mệnh đề
sau là tương đương
(i) f là lồi;
(ii) ∀x, y ∈ D : y − x | ∇f (x) ≤ f (y) − f (x);
(iii) ∀x, y ∈ D : y − x | ∇f (y) − ∇f (x) ≥ 0;
(iv) ∀x ∈ D, ∀u ∈ X : ∇2 f (x)(u, u) ≥ 0 ( khi f là khả vi hai lần theo nghĩa Gateaux

trên D).

1.1.5

Hàm liên hợp

Kí hiệu Γ0 (H) là lớp các hàm lồi chính thường nửa liên tục dưới từ H vào ] − ∞, +∞].
Cho ϕ ∈ Γ0 (H), hàm liên hợp của ϕ là hàm ϕ∗ ∈ Γ0 (H) xác định bởi
(∀u ∈ H)

ϕ∗ (u) = sup { x|u − ϕ(x)} .
x∈H

10

(1.8)


Chương 1. Các kiến thức chuẩn bị

Định lý 1.1.5. [41, Định lí 2.3.1] Cho f, g : H → R, khi đó
(i) Bất đẳng thức Young- Fenchel dưới đây là đúng:
∀x ∈ H, ∀u ∈ H

: f (x) + f ∗ (x∗ ) ≥ x | u ,

(ii) Nếu f ≤ g thì g ∗ ≤ f ∗ ,

(iii) Nếu g(x) = f (x + x0 ) với x ∈ H, thì g ∗ (x∗ ) = f ∗ (x∗ ) − x0 | x∗ với mỗi x∗ ∈ H.
Định lí Fenchel - Moreau phát biểu rằng ϕ∗∗ = ϕ. Chẳng hạn, hàm liên hợp của hàm

chỉ tiêu của một tập lồi đóng khác rỗng của C, tức là hàm ιC là hàm giá của C, tức là
ι∗C = σC : u → sup x|u .

(1.9)

σC∗ = ι∗∗
C = ιC .

(1.10)

x∈C

Ngược lại

Bổ đề 1.1.6. [7, Bổ đề 2.2] Cho C là một tập con lồi đóng khác rỗng của H, φ :
R →] − ∞, +∞] là một hàm chẵn và tăng trên [0, +∞[, đặt ϕ = φ ◦ dC . Khi đó
ϕ∗ = σC + φ∗ ◦ · .

1.1.6

Dưới vi phân

Dưới vi phân của ϕ ∈ Γ0 (H) là toán tử đa trị
∂ϕ : H → 2H : x → {u ∈ H|(∀y ∈ H) y − x | u + ϕ(x) ≤ ϕ(y)} ,

(1.11)

hoặc tương đương
∂ϕ(x) = {u ∈ H | ϕ(x) + ϕ∗ (u) = x | u } .


(1.12)

Ta có
(∀(x, u) ∈ H × H)

u ∈ ∂ϕ(x) ⇔ x ∈ ∂ϕ∗ (u).

(1.13)

Theo Định luật Fermat ta có
(∀x ∈ H)

x ∈ Argmin ϕ = {x ∈ dom ϕ | (∀y ∈ H) ϕ(x) ≤ ϕ(y)} ⇔ 0 ∈ ∂ϕ(x).
(1.14)

Hơn nữa, nếu ϕ khả vi theo nghĩa Gateaux tại x thì
∂ϕ(x) = {∇ϕ(x)} .
11

(1.15)


Chương 1. Các kiến thức chuẩn bị
Bổ đề 1.1.7. [41, Định lí 2.8.3] Cho ϕ ∈ Γ0 (H), ψ ∈ Γ0 (G), và M ∈ B(H, G) sao cho
0 ∈ sri (M (dom ϕ) − dom ψ) .
Khi đó
∂(ϕ + ψ ◦ M ) = ∂ϕ + M ∗ ◦ (∂ψ) ◦ M.

1.1.7


Toán tử không giãn chặt

Một toán tử T : H → H được gọi là toán tử không giãn nếu
∀(x, y) ∈ H2

Tx − Ty ≤ x − y .

(1.16)

Một toán tử T : H → H là không giãn chặt nếu nó thỏa mãn một trong các điều kiện
sau:
(i) (∀(x, y) ∈ H2 )
(ii) (∀(x, y) ∈ H2 )

Tx − Ty

2

≤ Tx − Ty | x − y ,

Tx − Ty ≤ x − y

2

− (Id − T ) x − (Id − T ) y 2 .

Có thể dễ dàng suy ra ngay rằng một toán tử không giãn chặt thì cũng là một toán tử
không giãn.

1.2


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

Như trong phần Giới thiệu đã đề cập, Bài toán (10) có thể giải được nhờ thuật toán
tách tiến lùi. Trong mục này chúng ta sẽ trình bày các tính chất cơ bản của bài toán
(10), sự hội tụ của thuật toán tách tiến lùi. Công cụ chính mà chúng ta sẽ sử dụng là
toán tử proximity, toán tử đã được giới thiệu bởi Moreau trong những năm 1960.

1.2.1

Toán tử proximity

Bao Moreau của một hàm ϕ ∈ Γ0 (H) là hàm lồi liên tục
ϕ : H → R : x → min ϕ(y) +
y∈H

12

1
x−y
2

2

.

(1.17)


Chương 1. Các kiến thức chuẩn bị

x−y 2
đạt giá trị nhỏ nhất tại duy nhất một điểm,
2
điểm đó được kí hiệu là proxϕ x. Toán tử proximity ϕ được định nghĩa bởi
Với mỗi x ∈ H, hàm y → ϕ(y) +

proxϕ : H → H : x → argmin ϕ(y) +
y∈H

1
x−y
2

2

(1.18)

và được đặc trưng bởi hệ thức
(∀ (x, p) ∈ H × H)

p = proxϕ x ⇔ x − p ∈ ∂ϕ(p).

(1.19)

Bổ đề 1.2.1. [30] Cho ϕ ∈ Γ0 (H). Các mệnh đề dưới đây là đúng
(i) (∀x ∈ H) (∀y ∈ H) proxϕ x − proxϕ y

2

≤ x − y | proxϕ x − proxϕ y .


(ii) (∀x ∈ H) (∀y ∈ H) proxϕ x − proxϕ y ≤ x − y .
(iii) ϕ + ϕ∗ =

·
.
2

(iv) ϕ∗ khả vi theo nghĩa Fréchet và ∇ϕ∗ = proxϕ = Id − proxϕ∗ .
Bổ đề 1.2.2. Cho ψ ∈ Γ0 (H), và đặt ϕ : x → ψ(x) +
ϕ∗ : u → ψ ∗ (u + ω) −

x−ω
. Khi đó
2

ω
.
2

Chứng minh. Theo định nghĩa hàm liên hợp ta có
ϕ∗ (u) = sup { x | u − ϕ(x)}
x∈H

= sup

x | u − ψ(x) −

x∈H


1
x−ω
2

2

1
x−ω 2− x|u
x∈H
2
1
= − inf ψ(x) +
x 2−2 x|ω + ω 2 − x|u
x∈H
2
1
1
= − inf ψ(x) + x 2 − x | u + ω + ω 2
x∈H
2
2
1
1
= − inf ψ(x) +
x 2−2 x|u+ω + u+ω 2 − u+ω
x∈H
2
2
1
1

= − inf ψ(x) + x − (u + ω) 2 − u 2 − u | ω
x∈H
2
2
1
1
= u 2 + u | ω − inf ψ(x) + x − (u + ω) 2
x∈H
2
2
1
1
= u + ω 2 − ω 2 − ψ(u + ω).
2
2
= − inf

ψ(x) +

13

2

+

1
ω
2

2



Chương 1. Các kiến thức chuẩn bị

Mặt khác theo Bổ đề 1.2.1(iii) ta có
ψ(u + ω) + ψ ∗ (u + ω) =

1
u+ω
2

2

nên ta có
ϕ∗ (u) = ψ ∗ (u + ω) −

1
ω 2.
2

Bổ đề 1.2.3. [18, Bổ đề 2.10] Cho ϕ ∈ Γ0 (H), x ∈ H và γ ∈]0, +∞[. Khi đó
x = proxγϕ x + γ proxγ −1 ϕ∗ (γ −1 x).

1.2.2

Các ví dụ về toán tử proximity

Ví dụ 1.2.4. Cho C là một tập con lồi đóng khác rỗng của H. Khi đó các mệnh đề
dưới đây là đúng.
(i) Nếu ϕ = ιC thì proxϕ = PC [30, Ví dụ 3.d].

(ii) Nếu ϕ = σC thì proxϕ = Id − PC [18, Ví dụ 2.17].
(iii) [18, Ví dụ 2.14] Nếu ϕ =

d2C
thì
(2α)

(∀x ∈ H) proxϕ x = x + (1 − α)−1 (PC x − x).
(iv) [18, Bổ đề 2.7] Đặt ϕ =

·

(∀x ∈ H)

2

− d2C
. Khi đó
2α
proxϕ x = x − α−1 PC α(α + 1)− 1 .

Ví dụ 1.2.5. [18, Bổ đề 2.7] Cho ψ ∈ Γ0 (H) và đặt ϕ =

·
2

2

− ψ. Khi đó


ϕ ∈ Γ0 (H)
và
x
proxϕ x = x − prox ψ ( ).
2
2
Ví dụ 1.2.6. [16, Mệnh đề 11] Cho G là một không gian Hilbert thực, ψ ∈ Γ0 (H), M ∈
(∀x ∈ H)

B(H, G) và ϕ = ψ ◦ M. Giả sử rằng M ◦ M ∗ = κId với κ ∈]0, +∞[. Khi đó ϕ ∈ Γ0 (H)
và
1
proxϕ = Id + M ∗ ◦ proxκψ −Id ◦ M.
κ
14

(1.20)


Chương 1. Các kiến thức chuẩn bị

Ví dụ 1.2.7. [11, Mệnh đề 2.10 và Nhận xét 3.2 (ii)] Đặt
ϕ : H →] − ∞, +∞] : x →

φκ ( x | oκ ) ,

(1.21)

κ∈K


trong đó :
(i) ∅ = K ⊂ N;
(ii) (ok )k∈K là một cơ sở trực truẩn của H;
(iii) (φk )k∈K là các hàm trong Γ0 (R);
(iv) Hoặc K là hữu hạn hoặc tồn tại một tập con L của K sao cho :
(a) K\L là hữu hạn;
(b) (∀k ∈ L) φk ≥ φk (0) = 0.
Khi đó ϕ ∈ Γ0 (H) và
(∀x ∈ H)

proxφk x | ok

proxϕ x =

ok .

(1.22)

k∈K

Ví dụ 1.2.8. [7, Mệnh đề 2.1] Cho C là một tập con lồi đóng khác rỗng của H, và
φ ∈ Γ0 (H) là một hàm chẵn, đặt ϕ = φ ◦ dC . Khi đó ϕ ∈ Γ0 (H). Hơn nữa, proxϕ = PC
nếu φ = ι{0} + η với η ∈ R, ngoài ra

prox∗φ dC (x)

x +
(PC x − x), nếu dC (x) > max ∂φ(0);




dC (x)

(∀x ∈ H) proxϕ x = PC x,
nếu x ∈
/ C và dC (x) ≤ max ∂φ(0);





x,
nếu x ∈ C.
(1.23)
Nhận xét 1.2.9. Nếu trong Ví dụ 1.2.8 ta cho C = {0} và ψ = ι{0} + η(η ∈ R). Khi đó
dC (x) = x và PC x = 0, hơn nữa sử dụng Bổ đề 1.2.1(iv) ta được proxφ∗ = Id−proxφ .
Do đó
x+

Id − proxφ ( x )
proxφ∗ dC (x)
(PC x − x) = x +
(−x)
dC (x)
x
x − proxφ x
=x+
(−x)
x
proxφ x

=x+ 1−
(−x)
x
proxφ x
=
x.
x
15


Chương 1. Các kiến thức chuẩn bị

Vậy ta có

(∀x ∈ H)


proxφ x



x, nếu x > max ∂φ(0);
x
proxϕ x =


0,
nếu x ≤ max ∂φ(0).

Mặt khác nếu φ = ι{0} + η khả vi tại 0 thì ∂φ(0) = {0} và


proxφ∗ dC (x)


x +
(PC x − x) , nếu x ∈
/ C;
dC (x)
(∀x ∈ H) proxϕ x =


x,
nếu x ∈ C.

(1.24)

(1.25)

Ví dụ 1.2.10. [7, Mệnh đề 2.2] Cho C là một tập con lồi đóng khác rỗng của H, và
φ ∈ Γ0 (R) là một chẵn và không phải là hàm hằng, đặt ϕ = σC + φ ◦

· . Khi đó

ϕ ∈ Γ0 (H) và

(∀x ∈ H)


proxφ dC (x)



(x − PC x), nếu dC (x) > max Argmin φ;



 dC (x)
proxϕ x = x − PC x,
nếu x ∈
/ C và dC (x) ≤ max Argmin φ;





0,
nếu x ∈ C.
(1.26)

Ví dụ 1.2.11. Cho A ∈ B(H) là một toán tử tự liên hợp dương, b ∈ H, α ∈ R, đặt
ϕ:x→

1
Ax | x + x | b + α.
2

Khi đó
ϕ ∈ Γ0 (H)
và
(∀x ∈ H) proxϕ x = (Id + A)−1 (x − b).
Chứng minh. Thật vậy, ϕ là một hàm lồi liên tục nhận giá trị hữu hạn nên ϕ ∈ Γ0 (H).

Cố định x ∈ H và đặt
ψ:y→

1
x−y
2

2

+ Ay | y /2 + y | b + α.

Khi đó
∇ψ : y → y − x + Ay + b.
Do vậy
(∀y ∈ H) ∇ψ(y) = 0 ⇔ y(Id + A) = x − b
16


Chương 1. Các kiến thức chuẩn bị

hay
y = (Id + A)−1 (x − b).

Ví dụ 1.2.12. [11, Ví dụ 4.2 và 4.4] Cho p ∈ [1, +∞[, α ∈]0, +∞[, φ : R → R : η →
α|η|p , ξ ∈ R và đặt π = proxφ ξ. Khi đó các mệnh đề dưới đây là đúng.
(i) π = sign(ξ) max {|ξ| − α, 0} , nếu p = 1;
(ii) π = ξ +

4α
|ρ − ξ|1/3 − |ρ + ξ|1/3 , trong đó ρ =

3.21/3

ξ 2 + 256α3 /729, nếu p =

4/3;
(iii) π = ξ + 9α2 sign(ξ) 1 −

1 + 16|ξ|/(9α2 ) /8 nếu p = 3/2;

(iv) π = ξ/(1 + 2α), nếu p = 2;
1 + 12α|ξ| − 1 /(6α), nếu p = 3;

(v) π = sign(ξ)
ρ+ξ
(vi) π =
8α

1/3

ρ−ξ
−
8α

1/3

, trong đó ρ =

ξ 2 + 1/(27α), nếu p = 4.

Ví dụ 1.2.13. [18, Ví dụ 2.18] Cho α ∈]0, +∞[ và đặt



−α ln(ξ), nếu ξ > 0;
φ:ξ→

+∞,
nếu ξ ≤ 0.

(1.27)

Khi đó
(∀ξ ∈ R) proxφ (ξ) = ξ +

ξ 2 + 4α /2.

Ví dụ 1.2.14. [15, Ví dụ 3.5] Cho ω ∈]0, +∞[ và đặt


ln(ω) − ln(ω − |ξ|), nếu |ξ| < ω;
φ : R →] − ∞, +∞] : ξ →

+∞,
trong các trường hợp còn lại .
(1.28)
Khi đó

(∀ξ ∈ R) proxφ ξ =




sign |ξ| + ω −

|ξ| − ω|2 + 4|
, nếu |ξ| > 1/ω;
2


0,

trong các trường hợp còn lại.
(1.29)
17


Chương 1. Các kiến thức chuẩn bị

Ví dụ 1.2.15. [11, Ví dụ 4.5] Cho ω ∈]0, +∞[, τ ∈]0, +∞[ và đặt

√

τ ξ 2 ,
nếu |τ | ≤ ω/ 2τ ;
(1.30)
φ : R →] − ∞, +∞] : ξ →
√

ω 2τ |ξ| − ω 2 /2, trong các trường hợp còn lại.
Khi đó
√
ξ

,
nếu |ξ| ≤ ω(2τ + 1)/ 2τ ;
(∀ξ ∈ R) proxφ ξ = 2τ + 1

ξ − ω √2τ sign(ξ), nếu |ξ| > ω(2τ + 1)/√2τ .




(1.31)

Bổ đề 1.2.16. [15, Mệnh đề 3.6] Cho φ = ψ + σΩ , trong đó ψ ∈ Γ0 (R) và Ω ⊂ R là
một khoảng đóng khác rỗng. Giả sử rằng ψ khả vi tại 0 với ψ (0) = 0. Khi đó
proxφ = proxψ ◦ softΩ ,
trong đó




ξ − ω, nếu ξ < ω;



softΩ : R → R : ξ → 0,
nếu ξ ∈ Ω;






ξ − ω, nếu ξ > ω

với



ω = inf Ω

(1.32)


ω = sup Ω.

Bổ đề 1.2.17. [16, Mệnh đề 1.2(ii)] Cho φ = ιC + ψ, trong đó ψ ∈ Γ0 (R) và C là một
khoảng đóng trong R sao cho C ∩ dom ψ = ∅. Khi đó
proxιC +ψ = PC ◦ proxψ .

1.2.3

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

Chúng ta phát biểu Bài toán (10) một cách đầy đủ như sau:
Bài toán 1.2.18. [18, Bài toán 1.1] Chof1 : H →] − ∞, +∞] và f2 : H → R là hai
hàm lồi nửa liên tục dưới sao cho f2 là khả vi trên H và có gradient liên tục Lipshitz
1
với hằng số , β ∈ ]0, +∞[. Bài toán đặt ra là
β
minimize {f1 (x) + f2 (x)} .
x∈H


Kí hiệu G là tập các nghiệm của Bài toán 1.2.18.
Mệnh đề 1.2.19. [18, Mệnh đề 3.1]
18

(1.33)


Chương 1. Các kiến thức chuẩn bị

(i) Tồn tại: Bài toán 1.2.18 có ít nhất một nghiệm nếu f1 + f2 bức, tức là
lim

x →+∞

(f1 (x) + f2 (x)) = +∞.

(1.34)

(ii) Duy nhất: Bài toán 1.2.18 có duy nhất một nghiệm nếu f1 + f2 là lồi chặt, điều
này xẩy ra khi f1 hoặc f2 là lồi chặt.
(iii) Đặc trưng : Cho x ∈ H, γ ∈]0, +∞[, các mệnh đề dưới đây là tương đương:
(a) x là nghiệm của Bài toán 1.2.18.
(b) x = proxγf1 (x − γ∇f2 (x)) .
(c) (∀y ∈ H)

x − y | ∇f2 (x) + f1 (x) ≤ f2 (y).

Mệnh đề trên đã gợi ý việc giải Bài toán 1.2.18 bằng một phép lặp
xn+1 = proxγf1 (xn − γ∇f2 (xn )),
với một cách chọn tham số γ thích hợp. Phép lặp này có liên hệ tới một quá trình tách

tiến lùi trong các bài toán tối ưu, nó bao gồm 2 bước tách biệt.
Bước đầu tiên là một bước tiến ( hiển) chỉ bao gồm duy nhất hàm f2 , bước này tính
xn+ 1 = xn − γ∇f2 (xn ).
2

Bước tiếp theo là một bước lùi ( ẩn) chỉ bao gồm duy nhất f1 , bước này tính
xn+1 = proxγf1 xn+ 1 .
2

Điều kiện 1.2.20. [18, Điều kiện 3.2] Cho C là một tập con khác rỗng của một không
gian Hilbert thực H. Chúng ta nói rằng một hàm ϕ(x) ∈ Γ0 (H) thỏa mãn điều kiện
trên C nếu với mọi dãy (yn )n∈N và (vn )n∈N trong H, y ∈ C và ∂ϕ(y), nếu

[yn

y, vn → v, (∀n ∈ N), vn ∈ ∂ϕ(yn )]

(1.35)

thì y là một điểm tích lũy mạnh của (yn )n∈N .
Định lý 1.2.21. [18, Định lí 3.4] Giả sử rằng G = ∅. Cho (γn )n∈N là một dãy trong
]0, +∞[ sao cho 0 < inf γn ≤ sup γn < 2β, cho (λn )n∈N là một dãy trong ]0, 1] sao cho
n∈N

n∈N

19


Chương 1. Các kiến thức chuẩn bị


inf λn > 0 và cho (an )n∈N và (bn )n∈N là các dãy trong H sao cho

n∈N

an < +∞ và
n∈N

bn < +∞. Cố định x0 ∈ H và với mỗi n ∈ N, đặt
n∈N

xn+1 = xn + λn proxγn f1 (xn − γn (∇f2 (xn ) + bn )) + an − xn

(1.36)

Khi đó các mệnh đề sau là đúng
(i) (xn )n∈N hội tụ yếu tới một điểm x ∈ G;
∇f2 (xn ) − ∇f2 (x)

(ii)

2

< +∞;

n∈N

(iii)
n∈N


proxγn f1 (xn − γn ∇f2 (xn )) − xn

2

< +∞;

(iv) (xn )n∈N hội tụ mạnh tới x nếu và chỉ nếu lim dG (xn ) = 0. Trong trường hợp cụ
thể, sự hội tụ mạnh xẩy ra trong các trường hợp sau:
(a) intG = ∅;
(b) f1 thỏa mãn Điều kiện 1.2.20 trên G;
(c) f2 thỏa mãn Điều kiện 1.2.20 trên G.

20