B

INH TH THO

GIÁO D C VÀ ÀO T O
TR
NG
I H C TH NG LONG
---------------------------------------

inh Th Tho
CHUYÊN NGÀNH TOÁN

V BÀI TOÁN CÂN B NG GI
N I U M NH VÀ
ÁP D NG VÀO M T MÔ HÌNH KINH T THN TR
NG I N

NG D NG
LU N V N TH C S TOÁN H C

KHOÁ 1

Hà N i – N m 2015


B
TR

GIÁO D C VÀ ÀO T O
NG


Lời cam đoan
Bản luận văn này là của tôi dưới sự hướng dẫn của GS. TSKH Lê
Dũng Mưu. Bản luận văn tổng hợp lại từ các tài liệu trích dẫn dựa trên
các mục tiêu của đề tài. Bản luận văn này không phải là một sự sao chép
lại hoàn toàn từ các tài liệu đã có.


Lời cảm ơn
Tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới GS. TSKH Lê
Dũng Mưu, người thầy đã tận tình hướng dẫn và đóng góp cho tôi nhiều
ý kiến về nội dung của luận văn.
Tôi xin gửi lời cảm ơn đến các thầy cô đã giảng dạy và giúp đỡ tôi
trong suốt quá trình tôi học tập tại trường Đại học Thăng Long.
Tôi xin gửi lời cảm ơn chân thành tới những người thân yêu trong gia
đình, bạn bè, đã luôn cổ vũ, động viên, giúp đỡ tôi để tôi có thể hoàn
thành được luận văn này.
Bước đầu nghiên cứu khoa học nên bản luận văn thạc sĩ của tôi chắc
chắn còn rất nhiều thiếu sót. Tôi rất mong nhận được sự đóng góp ý
kiến của các thầy giáo, cô giáo và bạn đọc để bản luận văn được hoàn
thiện hơn.
Hà Nội, tháng 5 năm 2015
Học viên

Đinh Thế Tho

Thang Long University Libraty


Danh mục các kí hiệu viết tắt

1.1.Một số khái niệm và các kết quả cơ bản. . . . . . . . . . . . . . 2
1.1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3. Toán tử chiếu lên một tập lồi đóng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.Bài toán cân bằng và các trường hợp riêng . . . . . . . . . . . 7
1.2.1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2. Bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3. Bài toán điểm bất động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.4. Bài toán cân bằng Nash trong trò chơi không hợp tác . . . . . . . . 10
1.3.Sự tồn tại nghiệm của bài toán cân bằng. . . . . . . . . . . . 11
Chương 2.HAI THUẬT TOÁN GIẢI BÀI TOÁN CÂN BẰNG
GIẢ ĐƠN ĐIỆU MẠNH VÀ ÁP DỤNG . . . . . . . .

16

2.1.Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1. Thuật toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2. Thuật toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.3. Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.Áp dụng vào mô hình cân bằng thị trường điện . . . . .

23

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

Trong chương này ta nhắc lại những khái niệm cơ bản, tính chất đặc
trưng của tập lồi và hàm lồi trong không gian Hilbert−H thực qua đó
giới thiệu về bài toán cân bằng và các trường hợp riêng của nó cùng một
số điều kiện về sự tồn tại nghiệm của bài toán cân bằng.
Nội dung của chương này được lấy từ [1], [2], [3], [4] .
1.1.
1.1.1.

Một số khái niệm và các kết quả cơ bản
Tập lồi

Định nghĩa 1.1.1. Một tập C ⊆ H được gọi là lồi nếu
∀x, y ∈ C, 0 ≤ λ ≤ 1 ⇒ λx + (1 − λ) y ∈ C.

Định lý 1.1.1. Tập lồi là đóng với phép giao, phép cộng, phép nhân với
một số thực. Tức là nếu C và D là hai tập lồi trong H thì các tập sau
cũng là tập lồi.
(i) C ∩ D = {x : x ∈ C, x ∈ D}.
(ii) αC + βD = {x = α.c + β.d : c ∈ C, d ∈ D} .
Định nghĩa 1.1.2. Tập C ⊆ H được gọi là nón nếu.
∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C.

Định nghĩa 1.1.3. Tập C ⊆ H được gọi là nón lồi nếu C vừa là nón
vừa là tập lồi, tức là.
λ1 x + λ2 y ∈ C, ∀x, y ∈ C, ∀λ1 > 0, ∀λ2 > 0.

Định nghĩa 1.1.4. Cho C ⊆ H là một tập lồi và x ∈ C , tập
NC (x) = {w ∈ H, w, y − x ≤ 0, ∀y ∈ C}
2



Nếu f lồi chặt, khả vi trên tập lồi C , thì với mọi x, y thuộc C ta có:
f (x) − f (y) < ∇f (x) , y − x ;

Nếu f lồi mạnh với hệ số α > 0 , khả vi trên tập lồi C , thì với mọi x, y
thuộc C ta có:
2

f (x) − f (y) ≤ ∇f (x) , y − x − α x − y .
3

Thang Long University Libraty


Định nghĩa 1.1.6. Một hàm f : H → R được gọi là nửa liên tục dưới
đối với C tại một điểm x, nếu như với mọi dãy xk ⊂ C , xk → x ta có
lim inf f xk ≥ f (x). Hàm f được gọi là nửa liên tục trên đối với C tại
x nếu −f nửa liên tục dưới đối với C tại x hay với mọi dãy xk ⊂ C ,
xk → x thì lim sup f xk ≤ f (x).
Định nghĩa 1.1.7. Cho C là một tập lồi và f : C → R ∪ {+∞} là một
hàm lồi, khi đó w ∈ C được gọi là dưới đạo hàm của f tại x nếu:
f (y) ≥ f (x) + w, y − x , ∀y ∈ C.

Tập tất cả các điểm w thỏa mãn bất đẳng thức trên được kí hiệu là ∂f (x)
. Nếu ∂f (x) = φ thì ta nói f khả dưới vi phân tại x
1.1.3.

Toán tử chiếu lên một tập lồi đóng

Định nghĩa 1.1.8. Giả sử C = ∅ (không nhất thiết lồi) là một tập con

w−y
w−y

2

2

≤ λ (x − w) + (w − y) 2 ;

≤ λ2 x − w
λ x−w

2

2

+ 2λ x − w, w − y + w − y 2 ;

+ 2 x − w, w − 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
w − y, x − w ≥ 0∀x ∈ C.
Vậy y − w ∈ NC (w).
Ngược lại: Giả sử y − w ∈ NC (w), với mọi x ∈ C , ta có
T

T

0 ≥ (y − w) (x − w) = (y − w) (x − y + y − w)

Chứng tỏ y là hình chiếu của x 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 y và z đều là hình chiếu của x trên C thì
x − y ∈ NC (y) , x − z ∈ NC (z) .

Tức là
y − x, z − y ≤ 0
5

Thang Long University Libraty


và
z − x, y − z ≤ 0.

Cộng hai bất đẳng thức này ta suy ra y − z ≤ 0, và do đó y = z .
Mệnh đề 1.1.3. Cho C là một tập lồi đóng khác rỗng trong không gian
Hilbert −H, ánh xạ y ֒→ PC (y) khi đó:
(i) PC (x) − PC (y) ≤ x − y ∀x, y ∈ H (tính không giãn);
(ii) PC (x) − PC (y)
bức).

2

≤ PC (x) − PC (y) , x − y ∀x, y ∈ H (tính đồng

Chứng minh: Theo (ii) ánh xạ x ֒→ PC (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ó:


Bài toán cân bằng và các trường hợp riêng

Cho f : C × C → R ∪ {+∞} thỏa mãn f (x, x) = 0, với mọi x ∈ C . C
là tập lồi đóng khác rỗng trong không gian Hilbert −H. Khi đó bài toán
cân bằng hay bất đẳng thức Ky Fan được phát biểu như sau: Tìm
x∗ ∈ C : f (x∗ , y) ≥ 0, ∀y ∈ C.

(1.2.1)

Bài toán cân bằng có ý nghĩa quan trọng trong kinh tế và nhiều lĩnh
vực khác, nó bao hàm được rất nhiều bài toán khác như: bài toán tối
ưu,bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán
cân bằng Nash . . . Phần trình bày dưới đây là một số ví dụ về những bài
toán có thể được mô tả dưới dạng bài toán cân bằng.
1.2.1.

Bài toán tối ưu

Cho C ⊂ H là tập lồi đóng khác rỗng và ϕ : C → R xác định trên C .
Khi đó bài toán tối ưu được phát biểu như sau: Tìm
x∗ ∈ C : ϕ (y) ≥ ϕ (x∗ ) , ∀y ∈ C.

(1.2.2)

Bằng cách đặt
f (x, y) = ϕ (y) − ϕ (x) , ∀x, y ∈ C

thì bài toán (1.2.2) tương đương với bài toán (1.2.1).
Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.2). Nên ta có

Tìm:
x∗ ∈ C, w∗ ∈ F (x∗ ) sao cho
(1.2.3)
w∗ , y − x∗ ≥ 0, ∀y ∈ C.
Bằng cách đặt
f (x, y) = max w, y − x ,

∀x, y ∈ C.

w∈F (x)

thì bài toán (1.2.3) tương đương với bài toán (1.2.1).
Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.3). Ta có
w∗ , y − x∗ ≥ 0,

∀y ∈ C,

w ∈ F (x∗ ) .

Mặt khác theo cách đặt ta có
f (x∗ , y) = max

w∗ , y − x∗ ≥ 0,

y ∈ C.

w∗ ∈F (x∗ )

Vậy x∗ ∈ C là nghiệm của bài toán (1.2.1).
Ngược lại, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.1) nên ta có

Bài toán điểm bất động

Cho C ⊂ H là tập lồi đóng khác rỗng và F : C → 2C là ánh xạ đa trị.
Khi đó bài toán điểm bất động được phát biểu như sau, tìm
x∗ ∈ C, sao cho

(1.2.5)

x∗ ∈ F (x∗ ) .

Bằng cách đặt
f (x, y) = max x − w, y − x ,

∀x, y ∈ C.

w∈F (x)

Thì bài toán (1.2.5) tương đương với bài toán (1.2.1).
Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.5) nên ta có
F (x∗ ) = x∗ .

Mặt khác theo cách đặt ta có
f (x∗, y) = x∗ − F (x∗ ) , y − x∗ ≥ 0,

∀y ∈ C.

Vậy x∗ ∈ C là nghiệm của bài toán (1.2.1). Ngược lại, giả sử x∗ ∈ C là
nghiệm của bài toán (1.2.1) nên ta có
f (x∗ , y) ≥ 0,



x∗ = F (x∗ ) .

(1.2.6)

Bằng cách đặt
f (x, y) = x − F (x) , y − x ,

∀x, y ∈ C.

Thì bài toán (1.2.6) tương đương với bài toán (1.2.1).
9

Thang Long University Libraty


Bài toán cân bằng Nash trong trò chơi không hợp tác

1.2.4.

Xét một trò chơi không hợp tác gồm p đối thủ, C ⊆ H là tập lồi khác
rỗng, Ci là tập chiến lược của người chơi thứ i. Hàm chi phí( tổn thất
của người chơi thứ i) là
fi : C1 × C2 × ... × Cp → R.

Với
C = C1 × C2 × ... × Cp ;
x1 ∈ C1 , x2 ∈ C2 , ..., xp ∈ Cp .

Thì chi phí của mỗi đối thủ tương ứng là

i=1

Thì bài toán (1.2.7) tương đương với bài toán (1.2.1).
Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.7) nên ta có
fi x∗1 , ..., x∗i−1, x∗i , x∗i−1, ..., x∗p ≤ fi x∗1 , ..., x∗i−1, yi , x∗i−1, ..., x∗p ,
∀xi, yi ∈ Ci , ∀i = 1, 2, ..., p.

Suy ra
fi x∗1 , ..., x∗i−1, yi , x∗i−1 , ..., x∗p − fi x∗1 , ..., x∗i−1, x∗i , x∗i−1 , ..., x∗p ≥ 0,
∀xi, yi ∈ Ci , ∀i = 1, 2, ..., p.
10


Suy ra
p

fi x∗1 , ..., x∗i−1, yi , x∗i−1, ..., x∗p − fi x∗1, ..., x∗i−1, x∗i , x∗i−1, ..., x∗p

≥ 0.

i=1

Theo cách đặt ta được
f (x∗ , y) ≥ 0,

∀y ∈ C.

Vậy x∗ ∈ C là nghiệm của bài toán (1.2.1). Ngược lại, giả sử x∗ ∈ C là
nghiệm của bài toán (1.2.1) nên ta có
f (x∗ , y) ≥ 0,


Sự tồn tại nghiệm của bài toán cân bằng

C ⊆ H là một tập lồi đóng, khác rỗng và f : C × C → R ∪ {+∞} là
song hàm cân bằng xác định trên C , với các giả thiết sau:
(P1 ) f (., y) là hàm số nửa liên tục trên với mọi y thuộc C ;
(P2 ) f (x, .) là hàm lồi, nửa liên tục dưới và khả dưới vi phân trên C với
mọi x thuộc C ;
11

Thang Long University Libraty


(P3 ) f thỏa mãn điều kiện bức trên C tức là tồn tại tập compact D sao
cho
C ∩ D = ∅, ∀x ∈ C\D, ∃y ∈ C; f (x, y) < 0.

Định lý 1.3.1. (Ky Fan)
Giả sử C là một tập lồi đóng khác rỗng trong không gian Hilbert −H và
f : C × C → R ∪ {+∞} là song hàm cân bằng xác định trên C . Nếu f
thỏa mãn (P1 ) và f (x, .) tựa lồi trên C với mọi x thuộc C . Khi đó nếu
C là tập compact hoặc điều kiện bức (P3 ) được thỏa mãn thì bài toán
(1.2.1) có nghiệm.
Từ định lí này ta suy ra hệ quả sau.
Hệ quả 1.3.1. Cho f : C × C → R ∪ {+∞} là song hàm cân bằng ,
f (., y) là nửa liên tục trên với mọi y ∈ C và f (x, .) là lồi, nửa liên tục
dưới với mọi x ∈ C . Giả sử điều kiện bức sau đây thỏa mãn. Tồn tại tập
compact B sao cho
C ∩ B = ∅,


f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0,
12

∀x, y ∈ C;


(v) giả đơn điệu mạnh trên C với hệ số λ > 0, nếu:
2

f (x, y) ≥ 0 ⇒ f (y, x) ≤ −λ x − y , ∀x, y ∈ C;

(vi) tựa đơn điệu trên C , nếu:
f (x, y) > 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C.

Từ định nghĩa trên ta có đơn điệu mạnh thì đơn điệu và giả đơn điệu,
đơn điệu thì giả đơn điệu.
Tính chất đơn điệu của song hàm có liên quan chặt chẽ với tính chất
đơn điệu của toán tử sau.
Định nghĩa 1.3.2. Cho C ∈ H và toán tử A : C → R được gọi là:
(i) đơn điệu mạnh trên C với hệ số λ > 0, nếu:
2

A (x) − A (y) , x − y ≥ λ x − y ,

∀x, y ∈ C;

(ii) đơn điệu chặt trên C , nếu:
A (x) − A (y) , x − y > 0,

∀x, y ∈ C, x = y;



Chứng minh: Giả sử C không bị chặn. Khi đó nó thỏa mãn điều kiện
bức sau: Tồn tại hình cầu đóng B sao cho
∀x ∈ C\B, ∃y ∈ C ∩ B :

f (x, y) < 0.

Thật vậy, với bất kì hình cầu đóng Br với tâm 0 và bán kính r, xr ∈ C\Br
sao cho
f (x, y) ≥ 0, ∀y ∈ C ∩ Br .
(1.3.9)
r0 > 0 cố định, khi đó với mỗi r > r0 , tồn tại xr ∈ C\Br sao cho
f xr , y 0 ≥ 0, ∀y 0 ∈ C ∩ Br0 .

Do f giả đơn điệu mạnh với tham số λ, nên ta có
f y 0 , xr + λ xr − y 0

2

(1.3.10)

≤ 0, ∀r.

Mặt khác, Tập C lồi và f y0 , . là lồi trên C . Theo tính lồi tồn tại x0 ∈ C
sao cho ∂2 f y0 , x0 = ∅, ở đây ∂2 f y0 , x0 là dưới vi phân của hàm lồi
f y 0 , . tại điểm x0 . Đặt w∗ ∈ ∂2 f y 0 , x0 là dưới gradient được định
nghĩa bởi
w∗ , x − x0 + f y 0 , x0 ≤ f y 0 , x , ∀x.
Với x = xr ta có

f (y ∗ , x∗ ) ≥ 0
14


Theo tính giả đơn điệu mạnh, từ f (x∗, y∗ ) ≥ 0, suy ra f (y∗ , x∗) ≤
−λ x∗ − y ∗ 2
Tương tự, ta có f (y∗ , x∗) ≥ 0, suy ra f (x∗ , y∗ ) ≤ −λ x∗ − y∗ 2 .
Vì λ > 0 và x∗ − y∗ 2 ≥ 0, nên suy ra f (x∗ , y∗ ) = f (y∗ , x∗ ) = 0, suy ra
x∗ = y ∗ .

15

Thang Long University Libraty


Chương 2

HAI THUẬT TOÁN GIẢI BÀI
TOÁN CÂN BẰNG GIẢ ĐƠN
ĐIỆU MẠNH VÀ ÁP DỤNG
Trong chương này, tôi trình bày hai thuật toán giải bài toán cân bằng
giả đơn điệu mạnh trên tập nghiệm của nó. Qua đó chứng minh tính
đúng đắn và sự hội tụ của thuật toán và đưa vào áp dụng mô hình kinh
tế thị trường điện.
Nội dung của chương này được lấy từ [5], [6], [7].
2.1.

Thuật toán và sự hội tụ

Để tìm được tập nghiệm của bài toán cân bằng trong chương này ta




x∈C

Mặt khác x∗ ∈ C nên

y∈C



sup
inf f (x, y) ≥ inf f (x∗, y) .


x∈C




y∈C

y∈C

Nhưng do x∗ là nghiệm của bài toán (1.2.1) nên
f (x∗, y) ≥ 0, ∀y ∈ C.

Vậy
inf f (x∗ , y) ≥ 0.
y∈C

inf f (x, y) = max inf f (x, y) = inf f (x∗ , y) = 0.




x∈C




y∈C

y∈C

y∈C

Ngược lại, giả sử có (ii). Khi đó theo lập luận ở trên ta có
sup {−f (x∗ , y)} = min sup {−f (x∗, y)} = 0.
y∈C

x∈C y∈C

Chứng tỏ
−f (x∗ , y) ≤ 0, ∀y ∈ C.

Hay
f (x∗, y) ≥ 0, ∀y ∈ C.
17

Thang Long University Libraty

2

.

(2.1.1)

2

2

xk+1 − x∗ ≤ α xk − x∗ , ∀k ≥ 0.
1
Nếu như 0 < ρ ≤
, trong đó x∗ là nghiệm duy nhất của bài toán
2L2
(1.2.1) và
α = 1 − 2ρ (λ − L1 ) .

Chứng minh: Đặt
fk (x) = ρf xk , x +

1
x − xk
2

2

, ∀k ≥ 0.

Do f xk , . lồi, nên hàm fk lồi mạnh trên C với hệ số 1. Vậy


≤ 2ρ f xk , x∗ − f xk , xk+1
18

+ xk − x∗

2

2

− xk+1 − xk .
(2.1.4)