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

NGUYỄN THÀNH HUẾ

MỘT TIẾP CẬN CÂN BẰNG TÁCH CHO MƠ HÌNH
NASH - COURNOT VỚI MỘT RÀNG BUỘC CHUNG

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

THÁI NGUYÊN - 2019


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

NGUYỄN THÀNH HUẾ

MỘT TIẾP CẬN CÂN BẰNG TÁCH CHO MƠ HÌNH
NASH - COURNOT VỚI MỘT RÀNG BUỘC CHUNG
Chuyên ngành: Toán ứng dụng
Mã số
: 8 46 01 12

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

NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH. Lê Dũng Mưu

THÁI NGUYÊN - 2019


i

Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn của GS.TSKH. Lê
Dũng Mưu (trường Đại học Thăng Long Hà Nội). Tác giả xin được bày
tỏ lòng biết ơn chân thành và sâu sắc tới thầy hướng dẫn khoa học của
mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn
và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm
luận văn.
Tác giả cũng đã học tập được rất nhiều kiến thức chun ngành bổ ích
cho cơng tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm
ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp cao học
Toán, nhà trường và các phịng chức năng của trường, khoa Tố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.
Xin chân thành cảm ơn anh chị em trong lớp cao học và bạn bè đồng
nghiệp đã trao đổi, động viên và khích lệ 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, 10 tháng 4 năm 2019
Tác giả luận văn

Nguyễn Thành Huế


ii

Mục lục

Lời cảm ơn

i

Bảng ký hiệu

iii

Lời nói đầu

1

Chương 1 Kiến thức chuẩn bị

3

1.1. Tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều . .

3

1.2. Các bổ đề hỗ trợ . . . . . . . . . . . . . . . . . . . . . . . . .

19

Chương 2 Một tiếp cận cân bằng tách cho mơ hình NashCournot với một ràng buộc chung
2.1. Bài toán chấp nhận lồi tách . . . . . . . . . . . . . . . . . . .

21
21


2.2. Một thuật tốn giải mơ hình Nash–Cournot có ràng buộc chung 22
2.2.1.Thuật toán

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

24

2.2.2.Một mơ hình thực tế . . . . . . . . . . . . . . . . . . .

31

Kết luận

36

Tài liệu tham khảo

37


iii

Bảng ký hiệu
Rn+

Góc khơng âm của Rn (tập các vectơ không âm)

R

Trục số thực R = R1


R

Trục số thực mở rộng (R = R ∪ {−∞, +∞})

xi

Tọa độ thứ i của x

xT

Vectơ hàng (chuyển vị của x )

||x||

Chuẩn Euclid của x

riA

Tập hợp các điểm trong tương đối của A

reA

Nón lùi xa (nón các hướng vơ hạn) của A

A∗

Đối cực của A

f


Hàm bao đóng của f

domf

Tập hữu dụng của f

f∗

Hàm liên hợp của f

epif

Trên đồ thị của f

∂f (x)

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

∂∈ f (x)

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

∇f (x)

Hoặc đạo hàm của f tại x

f (x)

Đạo hàm f tại x


f (x, d) Đạo hàm theo hướng d của f tại x


1

Lời nói đầu
Bài tốn chấp nhận tách là bài tốn
Tìm x∗ ∈ C sao cho Ax∗ ∈ Q,
trong đó C là một tập lồi đóng trong khơng gian X, cịn Q là một tập lồi
đóng trong khơng gian Y và A là một tốn tử tuyến tính từ X vào Y .
Bài tốn này có thể coi như một sự mở rộng của bài toán chấp nhận
lồi, là một bài toán cơ bản trong Toán ứng dụng. Bài toán chấp nhận
tách lần đầu tiên được nghiên cứu trong không gian Euclid hữu hạn chiều
bởi Censor và Elving năm 1994 trong tài liệu [2]. Trong bài báo này các
tác giả đã giới thiệu một số ứng dụng của bài toán chấp nhận tách trong
không gian hữu hạn chiều, như ứng dụng trong xạ trị khối u, trong xử
lý tín hiệu v.v... Sau cơng trình trên, bài tốn chấp nhận tách được rất
nhiều người quan tâm nghiên cứu, do tính lý thú về mặt toán học, và đặc
biệt là phạm vi ứng dụng rộng rãi của bài toán này. Một hướng mở rộng
được quan tâm nhiều là xét trường hợp khi các tập C và Q là nghiệm của
những bài toán khác, như bài toán tối ưu lồi, bất đẳng thức biến phân
đơn điệu, tập điểm bất động của ánh xạ không giãn, hoặc tổng quát hơn
là tập nghiệm của bài toán cân bằng có một tính chất đơn điệu nào đó.
Mục đích của bản luận văn này là trình bày lại một cách có hệ thống
các kết quả về mơ hình Nash–Cournot trong trường hợp mơ hình có thêm
một ràng buộc chung, theo cách tiếp cận dựa trên việc mô tả mơ hình
dưới dạng bài tốn cân bằng tách.
Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục



2

các tài liệu tham khảo.
Chương 1 trình bày một số khái niệm cơ bản liên quan đến đề tài, đó
là tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều.
Chương 2 giới thiệu bài toán chấp nhận lồi tách, giới thiệu mơ hình
Nash–Cournot và trình bày một thuật tốn giải bài tốn mơ hình Nash–
Cournot có ràng buộc chung theo tiếp cận cân bằng tách.


3

Chương 1

Kiến thức chuẩn bị
Chương này trình bày các khái niệm, các tính chất cơ bản nhất của
giải tích lồi và các bổ đề hỗ trợ sẽ được dùng trong Chương 2. Các kiến
thức ở chương này được tổng hợp từ tài liệu tham khảo [1], [3].

1.1.

Tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều

Định nghĩa 1.1 Một tập C ⊆ Rn được gọi là một tập lồi, nếu C chứa
mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ
khi
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
Ta nói x là tổ hợp lồi của các điểm (vectơ) x1 , ..., xk nếu
k


k
j

λj x , λj > 0 ∀j = 1, ..., k

x=
j=1

λj = 1.
j=1

Tương tự, x là tổ hợp aphin của các điểm (vectơ) x1 , ..., xk nếu
k

k
j

x=

λj x ,
j=1

λj = 1.
j=1

Tập hợp của các tổ hợp aphin của x1 , ..., xk thường được gọi là bao aphin
của các điểm này.



4

Mệnh đề 1.1 Tập hợp C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của
các điểm của nó. Tức là tập C lồi khi và chỉ khi
k

k
1

∀k ∈ N, ∀λ1 , ..., λk > 0 :

k

λj = 1, ∀x , ..., x ∈ C ⇒
j=1

λj xj ∈ C.
j=1

Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh
điều kiện cần bằng quy nạp theo số điểm. Với k = 2, điều cần chứng minh
suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng
với k − 1 điểm. Ta cần chứng minh với k điểm.
Giả sử x là tổ hợp lồi của k điểm x1 , ..., xk ∈ C. Tức là
k

k
j

λj x , λj > 0 ∀j = 1, ..., k


x=
j=1

λj = 1.
j=1

Đặt
k−1

ξ=

λj .
j=1

Khi đó 0 < ξ < 1 và
k−1

k−1
j

x=

k

λj x + λk x = ξ
j=1

do


j=1
k−1

j=1

Với

λj
ξ

λj j
x + λk x k
ξ

λj
= 1.
ξ

> 0 với mọi j = 1, ..., k − 1, nên theo giả thiết quy nạp, điểm
k−1

y :=
j=1

λj j
x ∈ C.
ξ

Ta có
x = ξy + λk xk .

Do ξ > 0, λk > 0 và
k

λj = 1,

ξ + λk =
j=1


5

nên x là một tổ hợp lồi của hai điểm y và xk đều thuộc C. Vậy x ∈ C.

Định nghĩa 1.2 Một tập C được gọi là tập aphin nếu nó chứa đường
thẳng đi qua hai điểm bất kỳ của nó, tức là
∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C.
Vậy tập aphin là một trường hợp riêng của tập lồi. Ví dụ điển hình của
tập aphin là các khơng gian con, siêu phẳng được định nghĩa dưới đây.
Định nghĩa 1.3 Siêu phẳng trong khơng gian Rn là một tập hợp các
điểm có đạng
{x ∈ Rn |aT x = α},
trong đó a ∈ Rn là một vectơ khác 0 và α ∈ R.
Vectơ a thường được gọi là vectơ pháp tuyến của siêu phẳng. Một siêu
phẳng sẽ chia không gian ra hai nửa không gian. Nửa không gian được
định nghĩa như sau:
Định nghĩa 1.4 Nửa khơng gian là một tập hợp có dạng {x|aT x ≥ α},
trong đó a = 0 và α ∈ R. Đây là nửa khơng gian đóng. Tập {x| aT x > α}
là nửa không gian mở.
Định nghĩa 1.5 Các điểm x0 , x1 , ..., xk trong Rn được gọi là độc lập
aphin, nếu bao aphin của chúng có thứ nguyên là k.

Định nghĩa 1.6 Một tập hợp được gọi là tập lồi đa diện, nếu nó là giao
của một số hữu hạn các nửa khơng gian đóng.
Theo định nghĩa, tập lồi đa diện là tập hợp nghiệm của một hệ hữu
hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi
đa diện được cho như sau:
D := {x ∈ Rn | aj , x ≤ bj , j = 1, ..., m}.


6

Hoặc nếu ta ký hiệu A là ma trận có m hàng là các vectơ aj (j = 1, ..., m)
và vectơ bT = (b1 , ..., bm ), thì hệ trên viết được là
D = {x ∈ Rn |Ax ≤ b}.
Chú ý rằng do một phương trình
a, x = b
có thể viết một cách tương đương dưới dạng hai bất phương trình
a, x ≤ b, −a, x ≤ b,
nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương
trình cũng là một tập lồi đa diện.
Một số các tính chất của tập lồi đa diện sẽ được trình bày trong các
phần tiếp theo.
Định nghĩa 1.7 Cho C =

(không nhất thiết lồi) và y là một vectơ

bất kỳ, đặt
dC (y) := inf ||x − y||.
x∈C

Ta nói dC (y) là khoảng cách từ y đến C. Nếu tồn tại π ∈ C sao cho

dC (y) := ||π − y||, thì ta nói π là hình chiếu (vng góc) của y trên C.
Theo định nghĩa, ta có hình chiếu pC (y) của y trên C sẽ là nghiệm của
bài toán tối ưu.
1
min{ ||x − y||2 |x ∈ C}
x
2
Vậy việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu
của hàm tồn phương ||x − y||2 trên C.
Ta sẽ ký hiệu π = PC (y), hoặc đơn giản hơn là p(y) nếu không cần
nhấn mạnh đến tập chiếu C. Chú ý rằng, nếu C =

, thì dC (y) hữu hạn,

vì 0 ≤ dC (y) ≤ ||y − x|| với mọi x ∈ C.
Cho C ⊆ Rn , x0 ∈ C. Nhớ lại là nón pháp tuyến (ngoài) của tập C tại
x0 là tập hợp
NC (x0 ) := {w|wT (x − x0 ) ≤ 0 ∀x ∈ C}.


7

Mệnh đề 1.2 Cho C là một tập lồi đóng khác rỗng. Khi đó:
(i) Với mọi y ∈ Rn , π ∈ C hai tính chất sau là tương đương:
a) π = PC (y),
b) y − π ∈ NC (π).
(ii) Với mọi y ∈ Rn , hình chiếu PC (y) của y trên C luôn tồn tại và duy
nhất.
(iii) Nếu y ∈
/ C, thì PC (y) − y, x − PC (y) = 0 là siêu phẳng tựa của C

tại PC (y) và tách hẳn y khỏi C, tức là
PC (y) − y, x − PC (y) ≥ 0, ∀x ∈ C,
và
PC (y) − y, y − PC (y) < 0.
(iv) Ánh xạ y → PC (y) có các tính chất sau:
a) ||PC (x) − PC (y)|| ≤ ||x − y|| ∀x, ∀y ( tính khơng giãn);
b) PC (x) − PC (y) , x − y ≥ ||PC (x) − PC (y)||2 , (tính đồng bức).
Chứng minh (i) Giả sử có a). Lấy x ∈ C và λ ∈ (0, 1). Đặt
xλ := λx + (1 − λ)π.
Do x, π ∈ C và C lồi, nên xλ ∈ C. Hơn nữa do π là hình chiếu của y, nên
||π − y|| ≤ ||y − xλ ||. Hay
||π − y||2 ≤ ||λ(x − π|| + (π − y)||2 .
Khai triển vế phải, ước lược và chia hai vế cho λ > 0, ta có
λ||x − π||2 + 2 x − π, π − y ≥ 0.
Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ tiến đến 0,
ta được
π − y, x − π ≥ 0 ∀x ∈ C.
Vậy y − π ∈ NC (π).


8

Bây giờ giả sử có b). Với mọi x ∈ C, có
0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π)
= ||y − π||2 + (y − π)T (x − y).
Từ đây và b), dùng bất đẳng thức Cauchy–Schwarz ta có:
||y − π||2 ≤ (y − π)T (y − x) ≤ ||y − π||||(y − x)||.
Suy ra ||(y − π)|| ≤ ||y − x|| ∀x ∈ C, và do đó π = p(y).
(ii) Do dC (y) = infx∈C ||x − y||, nên theo định nghĩa của cận dưới đúng
(infimum), tồn tại một dãy xk ∈ C sao cho

lim ||xk − y|| = dC (y) < +∞
k

Vậy dãy {xk } bị chặn, do đó nó có một dãy con {xkj } hội tụ đến một
điểm π nào đó. Do C đóng, nên π ∈ C. Vậy
||π − y|| = lim ||xkj − y|| = lim ||xk − y|| = dC (y).
j

k

Chứng tỏ π là hình chiếu của y trên C.
Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại
hai điểm π và π 1 đều là hình chiếu của y trên C, thì
y − π ∈ NC (π), y − π 1 ∈ NC (π 1 ).
Tức là
π − y, π 1 − π ≥ 0
và
π 1 − y, π − π 1 ≥ 0.
Cộng hai bất đẳng thức này ta suy ra ||π − π 1 || ≤ 0, và do đó π = π 1 .
(iii) Do y − π ∈ NC (π), nên
π − y, x − π ≥ 0 ∀x ∈ C.


9

Vậy π − y, x = π − y, π là một siêu phẳng tựa của C tai π. Siêu phẳng
này tách y khỏi C vì y = π, nên
π − y, y − π = −||π − y||2 < 0.
(iv) Theo phần (ii) ánh xạ x → p(x) xác định khắp nơi.
Do z − p(z) ∈ NC (p(z)) với mọi z, nên áp dụng với z = x và z = y, ta có:

x − p(x), p(y) − p(x) ≤ 0
và
y − p(y), p(x) − p(y) ≤ 0.
Cộng hai bất đẳng thức lại sẽ được
p(y) − p(x), p(y) − p(x) + x − y ≤ 0.
Từ đây và theo bất đẳng thức Cauchy–Schwarz, suy ra
||p(x) − p(y)|| ≤ ||x − y||.
Để chứng mnh tính đồng bức, áp dụng tính chất b của (i), lần lượt với
p(x) và p(y), ta có
p(x) − x, p(x) − p(y) ≤ 0.
y − p(y), p(x) − p(y) ≤ 0.
Cộng hai bất đẳng thức ta được
p(x) − p(y) + y − x, p(x) − p(y) ≤ 0
= p(x) − p(y), y − x + ||p(x) − p(y)||2 ≤ 0.
Chuyển vế ta có
p(x) − p(y), x − y ≥ ||p(x) − p(y)||2 .
Đây chính là tính đồng bức cần được chứng minh.


10

Định nghĩa 1.8 Một ánh xạ F : C −→ Rn được gọi là đơn điệu trên C,
nếu
F (x) − F (y), x − y ≥ 0 ∀x, y ∈ C
Ánh xạ F được gọi là đơn điệu mạnh trên C với hệ số β > 0, nếu
F (x) − F (y), x − y ≥ β||x − y||2 ∀x, y ∈ C
Cho C ⊆ Rn là tập lồi và f : C → R. Ta sẽ ký hiệu
domf := {x ∈ C| f (x) < +∞}
Tập domf được gọi là miền hữu dụng của f . Tập
epif := {(x, µ) ∈ C × R|f (x) ≤ µ}

được gọi là trên đồ thị của hàm f .
Bằng cách cho f (x) = +∞ nếu x ∈
/ C, ta có thể coi f được xác định
trên tồn khơng gian và hiển nhiên là
domf = {x ∈ Rn | f (x) < +}
epif = {(x, à) Rn | ì R|f (x) ≤ µ}
Do sẽ làm việc với hàm số nhận cả giá trị −∞ và +∞, ta có quy ước sau:
Nếu λ = 0, thì λf (x) = 0 với mọi x.
Định nghĩa 1.9 Cho

= C ⊆ Rn lồi và f : C → R. Ta nói f là hàm

lồi trên C, nếu epif là một tập lồi trong Rn+1 .
Ta sẽ chủ yếu làm việc với hàm f : Rn → R ∪ {+∞} . Trong trường
hợp này, dễ thấy rằng định nghĩa trên tương đương với
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀ λ(0, 1).
Hàm f : Rn → R ∪ {+∞} được gọi là lồi chặt trên C nếu
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀ λ ∈ (0, 1).


11

Hàm f : Rn → R ∪ {+∞} . được gọi là lồi mạnh trên C với hệ số η > 0,
nếu ∀x, y ∈ C, ∀λ ∈ (0, 1) có:
1
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ηλ(1 − λ)||x − y||2 .
2
Kiểm tra được rằng, f lồi mạnh trên C với hệ số η > 0 khi và chỉ khi
hàm
η

h(.) := f (.) − ||.||2
2
lồi trên C.
Bằng quy nạp, dễ dàng chứng minh được rằng, nếu f nhận giá trị hữu
hạn trên tập lồi C, thì với mọi số tự nhiên m và mọi x1 , ..., xm ∈ C thỏa
mãn λ1 ≥ 0, ..., λm ≥ 0,
m

m
j=1 λj

= 1, ta có

m
j

λj f (xj ) (bất đẳng thức Jensen).

λj x ) ≤

f(
j=1

j=1

Hàm f được gọi là một hàm lõm trên C, nếu −f lồi trên C.
Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều
trường hợp.
Mệnh đề 1.3 Một hàm f : C → R là lồi trên C khi và chỉ khi
∀x, y ∈ C, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1]

=⇒ f (λx + (1 − λ)y) ≤ λα + (1 − λ)β).
Chứng minh Chứng minh điều kiện cần. Giả sử f lồi. Chọn x, y, α, β
như đã nêu trong mệnh đề. Chọn α ∈ (f (x), α) và β ∈ (f (y), β). Vậy
(x, α ) và (y, β ) thuộc epif . Do epif lồi, nên;
((1 − λ)x + λy), (1 − λ)α + λβ ) ∈ epif.
Do đó
f ((1 − λ)x + λy) ≤ (1 − λ)α + λβ < (1 − λ)α + λβ.


12

Chứng minh điều kiện đủ. Chọn (x, µ) và (y, ν) thuộc epif và λ ∈ (0, 1).
Thế thì với mọi ε > 0, ta có
f (x) < µ + ε, f (y) << ν + ε.
Do đó
f [(1 − λ)α + λβ ] < (1 − λ)(µ + ε) + λ(ν + ε) = (1 − λ)µ + λν + ε.
Điều này đúng với mọi ε > 0, nên cho ε → 0, ta được
f [(1 − λ)α + λβ ] ≤ (1 − λ)µ + λν.
Chứng tỏ
(1 − λ)(x, µ) + λ(y, ν) ∈ epif.
Vậy f lồi.
Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh
dựa vào khái niệm hệ số lồi,
Định nghĩa 1.10 Cho f : Rn → R ∪ {+∞} (không nhất thiết lồi),
C ⊆ Rn là một tập lồi khác rỗng và η là một số thực. Ta nói η là hệ số
lồi của f trên C, nếu với mọi λ ∈ (0, 1), mọi x, y thuộc C, ta có
1
f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y) − ηλ(1 − λ)||x − y||2 .
2
Hiển nhiên nếu η = 0 thì f lồi trên C. Nếu f có hệ số lồi trên C là

η > 0, thì f lồi mạnh trên C với hệ số η.
Một hàm f được gọi là chính thường nếu domf =

và f (x) > −∞

với mọi x. Hàm f được gọi là đóng, nếu epif là một tập đóng trong Rn+1 .
Như đã nói ở trên, nếu f là một hàm lồi trên tập một tập lồi C, thì có
thể thác triển f lên tồn khơng gian bằng cách đặt
fe (x) :=

f (x), nếu x ∈ C,
+∞, nếu x ∈
/ C.


13

Hiển nhiên fe (x) = f (x) với ∀x ∈ C và fe lồi trên Rn . Hơn nữa fe là chính
thường khi và chỉ khi f chính thường. Tương tự fe đóng khi và chỉ khi f
đóng.
Chú ý rằng, nếu f là một hàm lồi trên Rn thì domf là một tập lồi, vì
domf chính là hình chiếu trên Rn của epif , tức là:
domf = {x|∃µ ∈ R : (x, µ) ∈ epif }.
Sau đây là một số ví dụ về hàm lồi.
Ví dụ 1.1

1. Hàm aphin. f (x) := aT x + α, trong đó a ∈ Rn , α ∈ R.

Dễ dàng kiểm tra được rằng f là một hàm vừa lồi vừa lõm trên tồn
khơng gian. Khi α = 0, thì hàm này được gọi là hàm tuyến tính.

Cho C =

là một tập lồi.

2. Hàm chỉ. Đặt
δC (x) :=

0,

nếu x ∈ C,

+∞,

nếu x ∈
/ C.

Ta nói δC là hàm chỉ của C. Do C lồi nên δC là một hàm lồi.
3. Hàm mặt cầu. Cho S := {x ∈ Rn | ||x|| = 1} là một mặt cầu và
h : S → R+ là một hàm bất kỳ. Định nghĩa hàm f như sau:



 0, nếu ||x|| < 1,
f (x) :=
h(x), nếu ||x|| = 1,


 +∞, nếu ||x|| > 1.
Hàm này được gọi là hàm mặt cầu. Dễ thấy rằng f là một hàm lồi
trên Rn , mặc dù h là một hàm không âm bất kỳ trên mặt cầu S.

4. Hàm tựa. Hàm dưới đây được gọi là hàm tựa của C.
SC (y) := sup y, x .
x∈C


14

5. Hàm khoảng cách. Cho C lồi đóng, hàm khoảng cách đến tập C được
định nghĩa bởi
dC (x) := min ||x − y||.
y∈C

6. Hàm chuẩn. Giả sử x = (x1 , ..., xn ).
f (x) := ||x||1 := max |xj |
j

hoặc
1

f (x) := ||x|| := (x21 + ... + x2n ) 2 .
Định nghĩa 1.11 Cho f : Rn → R ∪ {+∞} và một điểm x0 ∈ Rn sao
cho f (x0 ) < +∞. Nếu với một vectơ y ∈ Rn mà giới hạn
f (x0 + λy) − f (x0 )
lim
λ↓0
λ
tồn tại (hữu hạn hay vơ hạn), thì ta nói f có đạo hàm theo hướng y tại
điểm x0 .
Ta sẽ ký hiệu giới hạn này là f (x0 , y).
Ví dụ sau đây cho thấy hàm f (x, .) có thể khơng phải là hàm chính

thường mặc dù f là hàm chính thường và x ∈ domf . Cho



 0, nếu x < 0,
f (x) :=
1, nếu x = 0,


 +∞, nếu x > 0.
Ta thấy f là hàm lồi, chính thường, domf = (−∞, 0). Dễ thấy rằng
f (0, −1) = −∞, f (0, 0) = 0, f (0, 1) = +∞.
Từ định nghĩa của hàm ξ ở trên, ta có
f (x0 , y) = lim
λ↓0

ξ(λ) − ξ(0)
.
λ

Vậy f (x0 , y) chính là đạo hàm phải của ξ tại 0 nếu f (x0 , y) hữu hạn.
Ta nhắc lại rằng một hàm f là thuần nhất dương (bậc 1), nếu
f (tx) = tf (x) với mọi t > 0 và mọi x trên miền xác định của f . Hàm f


15

được gọi là dưới cộng tính, nếu f (x + y) ≤ f (x) + f (y) với mọi x, y trên
miền xác định của f . Hàm dưới tuyến tính là một hàm vừa thuần nhất
dương, vừa dưới cộng tính.

Đặt
ϕ(λ) :=

f (x + λy) − f (x)
.
λ

Mệnh đề 1.4 Cho f : Rn → R ∪ {+∞} lồi. Khi đó với mọi x ∈ domf
và mọi y ∈ Rn , ta có.
(i) ϕ là hàm đơn điệu khơng giảm trên (0, +∞); f (x, y) tồn tại với
mọi y ∈ Rn và

f (x + λy) − f (x)
.
λ>0
λ
(ii) Hàm f (x, .) thuần nhất dương bậc 1. Ngoài ra nếu f (x, .) > −∞
f (x, y) := inf

thì:
a) Hàm f (x, .) là dưới tuyến tính trên Rn (do đó nó là hàm lồi
chính thường trên Rn ).
b)−f (x, −y) ≤ f (x, y) ∀y ∈ Rn .
c) Hàm f (x, .) nhận giá trị hữu hạn trên F khi và chỉ khi
x ∈ ri(domf ), trong đó F là không gian con của domf.
Chứng minh (i) Ta chứng minh hàm ϕ đơn điệu không giảm trên miền
(0, +∞). Cho x ∈ domf và định nghĩa hàm h : R → R ∪ {+∞} bởi
h(λ) := f (x + λy) − f (x).
Khi đó h(0) = 0.
Giả sử 0 < λ ≤ λ. Khi đó, do h là hàm lồi khơng nhận giá trị −∞,

nên ta có
λ
λ
h(λ ) = h( λ + (1 − )0)
λ
λ
λ
λ
λ
≤ h(λ) + (1 − )h(0) ≤ h(λ)
λ
λ
λ


16

Do

f (x + λy) − f (x) h(λ)
=
.
λ
λ
nên ϕ(λ ) ≤ ϕ(λ). Vậy ϕ là hàm không giảm trên miền (0, +∞). Suy ra
ϕ(λ) :=

f (x, y) = limλ↓0 ϕ(λ) tồn tại và
lim ϕ(λ) = inf ϕ(λ).
λ↓0


λ>0

(ii) Theo định nghĩa, hiển nhiên ta có f (x, 0) = 0. Giả sử hàm
f (x, .) > −∞. Để chứng tỏ tính thuần nhất dương, với t > 0, ta viết
f (x, ty) = lim
λ↓0

f (x + λty) − f (x)
λ

Đặt λ = λt, ta có tiếp
f (x + λ y) − f (x)
= tf (x, y).
λ
λ ↓0

f (x, ty) = t lim

Vậy f (x, .) thuần nhất dương.
Ta chỉ ra tính chất dưới cộng tính. Với mọi u và v, ta có
f (x + λ2 (u + v)) − f (x)
f (x, u + v) = lim
λ↓0
λ/2
= lim

f ( x2 + λ2 u +

λ↓ 0


x
2

+ λ2 v) − 12 f (x) − 12 f (x)
.
λ/2

Do f là hàm lồi không nhận giá trị −∞, nên
x λ
x λ
1
1
f ( + u + + v) − f (x) − f (x)
2 2
2 2
2
2
1
1
≤ [f (x + λu) − f (x)] + [f (x + λv) − f (x)].
2
2
Do đó
f (x, u + v) ≤ lim
λ↓0

f (x + λu) − f (x)
f (x + λv) − f (x)
+ lim

λ
λ
λ ↓0
= f (x, u) + f (x, v).

(Chú ý f (x, u)+f (x, v) có nghĩa vì f (x, .) > −∞). Vậy f (x, .) dưới cộng
tính. Kết hợp lại ta có f (x, .) là dưới tuyến tính trên Rn . Vì f (x, .) > −∞,


17

f (x, 0) = 0 và f (x, .) là dưới tuyến tính trên Rn , nên nó là hàm lồi, chính
thường trên tồn khơng gian.
b) Do f (x, 0) = 0 và theo tính chất dưới cộng tính, ta có
0 = f (x, 0) = f (x, y − y) ≤ f (x, y) + f (x, −y) ∀y.
Từ đây suy ra b).
c) Giả sử x ∈ ri(domf ). Ta cần chứng tỏ f (x, .) hữu hạn trên F . Theo
giả thiết, f (x, .) > −∞. Vậy chỉ cần chỉ ra f (x, y) < +∞ với mọi y ∈ F .
Do x ∈ri(domf ), nên với mọi y ∈ F có x + λy ∈ domf với mọi λ > 0 đủ
nhỏ. Do đó

f (x + λy) − f (x)
< +∞.
λ>0
λ
Ngược lại giả sử f (x, y) hữu hạn với mọi y ∈ F . Ta cần chứng tỏ
f (x, y) = inf

x ∈ri(domf ). Thật vậy, nếu trái lại sẽ tồn tại y ∈ F và một dãy {λk }
các số dương hội tụ đến 0 và x + λk y ∈

/ domf với mọi k đủ lớn. Do đó
f (x, y) = +∞. Mâu thuẫn với giả thiết.
Vậy x ∈ ri(domf ).

Định nghĩa 1.12 Cho f : Rn → R ∪ {+∞}. Ta nói x∗ ∈ Rn là dưới đạo
hàm của f tại x nếu
x∗ , z − x + f (x) ≤ f (z) ∀z.
Ví dụ 1.2

1. f (x) = ||x||, x ∈ Rn . Tại điểm x = 0 hàm này không khả

vi, nhưng nó khả dưới vi phân và
δf (0) = {x∗ | x∗ , x ≤ ||x|| ∀x} .
2. f = δC là hàm chỉ của một tập lồi C =

. Khi đó với x0 ∈ C,

∂δC (x0 ) = {x∗ | x∗ , x − x0 ≤ δC (x) ∀x}.


18

Với x ∈
/ C, thì δC (x) = +∞, nên bất đẳng thức này luôn đúng. Vậy
∂δC (x0 ) = {x∗ | x∗ , x − x0 ≤ 0 ∀x ∈ C} = NC (x0 ).
Vậy dưới vi phân của hàm chỉ của một tập lồi C khác rỗng tại một
điểm x0 ∈ C chính là nón pháp tuyến ngồi của C tại x0 .
Mệnh đề 1.5 Cho f : Rn → R ∪ {+∞} lồi, chính thường.
(i) x∗ ∈ ∂f (x) khi và chỉ khi f (x, y) ≥ x∗ , y ∀y. Nếu ∀x ∈ ri(domf ),
thì f (x, y) = supx∗ ∈∂f (x) x∗ , y với mọi y.

(ii) Nếu f là hàm lồi chính thường trên Rn thì với mọi x ∈ dom(∂f ),
ta có f (x) = f (x), và ∂f (x) = ∂f (x).
Chứng minh (i) Theo định nghĩa
x∗ ∈ ∂f (x) ⇐⇒ x∗ , z − x + f (x) ≤ f (z) ∀z.
Với bất kỳ y, lấy z = x + λy, λ > 0, ta có
x∗ , λy + f (x) ≤ f (x + λy).
Từ đây suy ra
f (x + λy) − f (x)
∀λ > 0.
λ
Theo định nghĩa f (x, y), từ đây suy ra ngay
x∗ , y ≤

x∗ , y ≤ f (x, y) ∀y.

(1.1)

Ngược lại giả sử, bất đẳng thức trên thỏa mãn. Lấy z bất kỳ và áp dụng
(1.1) với y = z − x và λ = 1. ta có
f (x + y) − f (x) ≥ f (x, y) = f (x, z − x) ≥ x∗ , z − x ∀z.
Vậy x∗ ∈ ∂f (x).
Chú ý rằng do f (x, .) là hàm lồi, thuần nhất dương, nên mọi hàm non
a-phin của f (x, .) đều tuyến tính, tức là có dạng p, . . Vậy nếu p, . là
hàm non a-phin của f (x, .) trên Rn thì
p, y ≤ f (x, y) ∀y.


19

Theo Mệnh đề 1.5 ta có p ∈ ∂f (x). Hơn nữa do f (x, .) là một hàm lồi

đóng, nên theo định lý xấp xỉ tập lồi nó là bao trên của các hàm non của
nó. Vậy
f (x, y) = sup

p, y .

p∈∂f (x)

(ii) Cho x ∈ dom(∂f ) và x∗ ∈ ∂f (x). Theo định nghĩa của f , của hàm
liên hợp và do x∗ ∈ ∂f (x) ta có:
f (x) ≥ f (x) = f ∗∗ (x) ≥ x∗ , x − f ∗ (x∗ ) = f (x).
Từ đây suy ra f (x) = f (x).
Nếu y ∗ ∈ ∂f (x), thì với mọi z có:
f (z) ≥ f (z) ≥ f (x) + y ∗ , z − x = f (x) + y ∗ , z − x .
Suy ra ∂f (x) ⊆ ∂f (x).
Để chứng minh điều ngược lại, lấy z 0 ∈ ri(dom)f . Với mọi z ta có
f (z) = lim f (1 − t)z + tz 0 .
t

0

Vậy, theo định nghĩa của dưới vi phân ta có:
f (1 − t)z + tz 0 ≥ f (x) + x∗ , (1 − t)z + tz 0 − x .
Cho t

0 ta được:
f (x) ≥ f (x) + x∗ , z − x = f (x) + x∗ , z − x .

Chứng tỏ x∗ ∈ ∂f (x).


1.2.

Các bổ đề hỗ trợ

Các bổ đề này sẽ được sử dụng để chứng minh tính hợp lệ và sự hội tụ
của thuật tốn được xét phần sau.


20

Bổ đề 1.1 Cho x, y, z ∈ H và 0 ≤ a ≤ 1, ta có
||ax + (1 − a)y − z||2 ≤ a||x − z||2 + (1 − a)||y − z||2
Chứng minh
||ax + (1 − a)y − z||2
= a2 ||x − z||2 + (1 − a)2 ||y − z||2 + 2a(1 − a) x − z, y − z
= a||x − z||2 + (1 − a)||y − z||2
− a(1 − a) ||x − z||2 + ||y − z||2 − 2 x − z, y − z
≤ a||x − z||2 + (1 − a)||y − z||2 .
Bổ đề 1.2 Cho C là tập con lồi đóng khác rỗng trong không gian Hilbert
H và PC là phép chiếu của x lên C. Khi đó
(i) x − y, PC (x) − PC (y) ≥ ||PC (x) − PC (y)||2 ∀ x, y ∈ H.
(ii) x − PC (x), PC (x) − y ≥ 0 ∀x ∈ H, y ∈ C.
Bổ đề 1.3 Cho {vk } và {δk } là dãy không âm vk+1 ≤ vk + δk với

∞
k=1

<

δk + ∞. Khi đó dãy {vk } hội tụ.

Bổ đề 1.4 (xem Anh và Muu 2014). Cho H là không gian Hilbert thực,
{ak } là dãy các số thực có tính chất 0 < a < ak < b < 1 với k = 1, 2, ...,
và {vk }, {wk } là hai dãy thuộc H sao cho
lim sup vk ≤ c, lim sup wk ≤ c,
k→+∞

k→+∞

và
lim

k→+∞

ak vk + (1 − ak )wk = c, với mỗi c >0

Khi đó, limk→+∞ vk − wk = 0.