ĐINH
THẾ THO

BỘ 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
ỨNG
VỀ BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU MẠNH VÀ
DỤNG
ÁP DỤNG VÀO MỘT MÔ HÌNH KINH TẾ THN TRƯỜNG ĐIỆN

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

KHOÁ 1
Hà Nội – Năm 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC THĂNG LONG
---------------------------------------

Đinh Thế Tho

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


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
H : Không gian Hilbert thực;
. | . : Tích vô hướng;
. : Chuẩn trên không gian Hilbert;
NC : Nón chuẩn tắc của C ;
PC : Phép chiếu lên tập C ;
dC : Hàm khoảng cách của tập C ;
∇f (x) : Đạo hàm của hàm f tại x;
arg min f : Tập các cực tiểu của hàm f .


Danh mục hình và bảng
Hình 2.1: Lợi nhuận tốt nhất của nhà máy thủy điện đối với nhà máy
nhiệt điện ( Trang 25)
Hình 2.2: Lợi nhuận tốt nhất của nhà máy nhiệt điện đối với nhà máy
thủy điện ( Trang 25)
Hình 2.3: Lợi nhuận tốt nhất của hai nhà máy ( Trang 26)

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

i


Lời mở đầu
Bài toán cân bằng có nhiều ứng dụng trong khoa học, kĩ thuật và
đời sống. Có rất nhiều bài toán liên quan đến bài toán cân bằng 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 cân bằng
Nash trong các trò chơi không hợp tác,.... Do đó việc trình bày và đưa
ra các thuật toán giải bài toán cân bằng là rất cần thiết.
Luận văn này nhằm giới thiệu về bài toán cân bằng giả đơn điệu mạnh
và hai thuật toán giải bài toán cân bằng giả đơn điệu mạnh qua đó áp
dụng vào mô hình kinh tế thị trường điện.
Luận văn được chia làm hai chương

• Chương 1. của luận văn trình bày tóm tắt một số kết quả đã biết
trong giải tích lồi liên quan đến luận văn. Giới thiệu bài toán cân

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


được gọi là nón pháp tuyến ngoài của C và tập −NC (x) được gọi là nón
pháp tuyến trong của C tại x.
1.1.2.

Hàm lồi

Định nghĩa 1.1.5. Hàm f : C → R ∪ {+∞} được gọi là
(i) Lồi trên C nếu
f [λx + (1 − λ) y] ≤ λf (x) + (1 − λ) f (y) , ∀x, y ∈ C, 0 < λ < 1;

(ii) Lồi chặt trên C nếu
f [λx + (1 − λ) y] < λf (x)+(1 − λ) f (y) , ∀x, y ∈ C, x = y, 0 < λ < 1;

(iii) Lồi mạnh trên C với hệ số γ > 0 nếu
2

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
của không gian Hilbert −H và y ∈ H là một véc tơ bất kì, gọi
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 PC (y) ∈ C sao cho
dC (y) = y − PC (y) , thì ta nói PC (y) là hình chiếu của y trên C .
Từ định nghĩa này hình chiếu PC (y) của y trên C là nghiệm của bài toán
tối ưu
12
x−y.min
x∈C2
Nói cách khác, 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 x − y 2 trên C .
Mệnh đề 1.1.1. Cho C là một tập lồi đóng khác rỗng trong không gian
Hilbert −H, khi đó:
với mọi y ∈ H và w ∈ C thì w = PC (y) khi và chỉ khi y − w ∈ NC (w)

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)
= y−w

2

+ (y − w)T (x − y)

Áp dụng bất đẳng thức Cauchy-Schwarz ta có:
y−w

2

≤ (y − w)T (y − x) ≤ y − w

y−x .

Suy ra y − w ≤ y − x ∀x ∈ C , do đó w = PC (y) .
Mệnh đề 1.1.2. Cho C là một tập lồi đóng khác rỗng trong không gian
Hilbert −H, khi đó với mọi x ∈ H, hình chiếu PC (x) của x trên C luôn
tồn tại và duy nhất.
Chứng minh: Giả sử x ∈ H, y ∈ C , y = PC (x) ta có dC (x) = y − x ,
suy ra tồn tại dãy (xn )n∈N trong C sao cho

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ó:
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 ta được
p (y) − p (x) , p (y) − p (x) + x − y ≤ 0.

Áp dụng bất đẳng thức Cauchy-Schwarz suy ra
p (x) − p (y) ≤ x − y .

Để chứng minh tính đồng bức áp dụng mệnh đề 1.3.1. 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) = p (x)−p (y) , y−x + p (x) − p (y)


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.

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ó
ϕ (y) ≥ ϕ (x∗ ) , ∀y ∈ C mặt khác theo cách đặt
f (x, y) = ϕ (y) − ϕ (x) , ∀x, y ∈ C.

Do đó
f (x∗, y) = ϕ (y) − ϕ (x∗) ≥ 0, ∀x, y ∈ C.

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

∀y ∈ C.

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

Suy ra
ϕ (y) ≥ ϕ (x∗) , ∀y ∈ C.

Vậy x∗ ∈ C là nghiệm của bài toán (1.2.2).
7


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ó
f (x∗ , y) ≥ 0,

∀y ∈ 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.3).
Nếu F là ánh xạ đơn trị thì bài toán bất đẳng thức biến phân có dạng.
Tìm
x∗ ∈ C sao cho
(1.2.4)
f (x∗) , y − x∗ ≥ 0, ∀y ∈ 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,

∀y ∈ C.

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

∀y ∈ C.

Chọn y = F (x∗) ∈ C ta có
f (x∗, y) = x∗ − F (x∗ ) , F (x∗) − x∗ ≥ 0,

∀y ∈ C.

Suy ra
− x∗ − F (x∗ ) ≥ 0,

∀y ∈ C.

Hay
x∗ − F (x∗ ) ≤ 0,


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à
f1 (x1, x2 , ..., xp) , f2 (x1, x2 , ..., xp) , ..., fp (x1 , x2, ..., xp) ;
x = (x1 , x2, ..., xp) .

Khi đó bài toán cân bằng Nash được phát biểu như sau. Tìm:
x ∗x x ∈ C sao cho
x
xfi (x∗ ) ≤ fi (x∗ [yi ])
x ⇔ fi x∗, ..., x∗ , x∗ , x∗ , ..., xp ≤ fi x∗, ..., x∗ , yi , x∗ , ..., xp
11i−1i−1 ii−1i−1

x
x
∀yi ∈ Ci , ∀i = 1, 2, ..., p

(1.2.7)
Điểm x∗ ∈ C được gọi là điểm cân bằng Nash nếu bất kì đối thủ nào
chọn phương án ra khỏi điểm cân bằng trong khi các đối thủ còn lại vẫn
giữ phương án điểm cân bằng thì đối thủ ra khỏi điểm cân bằng sẽ bị
thua thiệt.

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,

∀y ∈ C.

Theo cách đặt ta được
xp
xfi x∗ , ..., x∗ , yi , x∗ , ..., xp − fi x∗ , ..., x∗ , x∗, x∗ , ..., xp11i−1i−1i−1 ii−1
i=1

x∀xi, yi ∈ Ci , ∀i = 1, 2, ..., p.

(1.2.8)
Giả sử x∗ ∈ C không là nghiệm của bài toán (1.2.7) nên tồn tại i và một
yi ∈ Ci sao cho
fi x∗ , ..., x∗ , x∗, x∗ , ..., x∗ > fi x∗ , ..., x∗ , yi , x∗ , ..., x∗ .pi−1pi−1i−11i−1 i1

Suy ra
fi x∗ , ..., x∗ , yi , x∗ , ..., x∗ − fi x∗ , ..., x∗ , x∗, x∗ , ..., x∗ < 0.pi−1pi−1 ii−11i−11

Suy ra
p

fi x∗ , ..., x∗ , yi , x∗ , ..., x∗ − fi x∗, ..., x∗ , x∗ , x∗ , ..., x∗ < 0.1i−1i−1p1i−1 ii−1p
i=1

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 = ∅,

∀x ∈ C\B,

∃y ∈ C :

f (x, y) < 0.

Khi đó bài toán (1.2.1) có nghiệm.
Để xét tính duy nhất nghiệm và các phương pháp tìm nghiệm của bài
toán (1.2.1) ta cần có các định nghĩa về tính đơn điệu của song hàm cân
bằng sau.
Định nghĩa 1.3.1. Giả sử f : C × C → R ∪ {+∞} là song hàm cân
bằng. Khi đó hàm f được gọi là :
(i) đơn điệu mạnh trên C với hệ số λ > 0, nếu:
f (x, y) + f (y, x) ≤ −λ x − y ,

2

∀x, y ∈ C;

(ii) đơn điệu chặt trên C , nếu:
f (x, y) + f (y, x) < 0,

∀x, y ∈ C;


∀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;

(iii) đơn điệu trên C , nếu:
A (x) − A (y) , x − y ≥ 0,

∀x, y ∈ C;

(iv) giả đơn điệu trên C ,nếu:
A (x) , x − y ≥ 0 ⇒ A (y) , x − y ≥ 0,

∀x, y ∈ C;

(v) giả đơn điệu mạnh trên C , nếu:
A (x) , x − y ≥ 0 ⇒ A (y) , x − y ≥ λ x − y ,

2

∀x, y ∈ C;

(vi) tựa đơn điệu trên C , nếu:
A (x) , x − y > 0 ⇒ A (y) , x − y ≥ 0,

∀x, y ∈ C.

Định lý 1.3.2. Cho C ⊂ H là một tập lồi đóng khác rỗng và f : C ×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 0 , x + λ xr − y 0

2

2

≥ f y 0 , x0 + w ∗ , xr − x0 + λ xr − y 0

≥ f y 0 , x0 + w ∗

xr − x0 + λ xr − y 0 .

2

Cho r tiến ra ∞, thì xr → ∞ ta được
f y 0 , x0 + λ xr − y 0

2

→ ∞.

Điều này mâu thuẫn với (1.3.10). Vậy điều kiện bức (1.3.9) được thỏa
mãn, khi đó theo hệ quả 1.3.1 thì bài toán (1.2.1) có nghiệm duy nhất.
Trường hợp C là Compact, thì chứng minh được suy ra bằng định lý Ky
Fan.

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
sử dụng các giả thiết sau với song hàm cân bằng f : C × C → R có các
tính chấ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 .
Mệnh đề 2.1.1. Giả sử f : C × C → R là song hàm cân bằng. Khi đó
với các giả thiết (P1 ) , (P2 ), thì các điều kiện sau đây là tương đương.
(i) x∗ là nghiệm của bài toán (1.2.1)
(ii) min {g (x) : x ∈ C} = 0, trong đó hàm g được cho bởi
g (x) = sup {f (x, y) : y ∈ C} ;

(iii) x∗ = argmin {f (x∗, y) : y ∈ C} .

16


Chứng minh: Từ (i) ⇒ (ii). Giả sử x∗ là nghiệm của bài toán (1.2.1),
do
f (x, x) = 0, ∀x ∈ C

Nên
inf f (x, y) ≤ 0, ∀x ∈ C.

Do đó

x
x

0 ≤ inf f (x∗ , y) ≤ sup
y∈C

x∈C

x

inf f (x, y)
y∈C

x
x
x

Vậy
x
xxx
x
xxx
supinf f (x, y) = max inf f (x, y) = inf f (x∗ , y) = 0.
y∈C
y∈C
x∈C
xxxx

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.

2

− L2 y − z .

2

Khi đó với bất kì x0 ∈ C , dãy xk được xác định theo công thức
x

k+1

k

=s x

1
k
= arg min ρf x , y + y − xk
y2∈C

2

.

(2.1.1)

Có tính chất
2
2
xk+1 − x∗ ≤ α xk − x∗ , ∀k ≥ 0.

wk , x − xk+1 ≥ 0, ∀x ∈ C.

Từ (2.1.2) ta có
fk xk+1 +

1

2

x − xk+1

(2.1.3)

≤ fk (x) , ∀x ∈ C.

2
Thay x = x∗ trong (2.1.3) theo định nghĩa fk ta được
xk+1 − x

2

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

+ xk − x∗

18

2

− xk+1 − xk .