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

ĐỖ THỊ LỆ THỦY

MỘT PHƯƠNG PHÁP DƯỚI ĐẠO HÀM GIẢI BÀI
TOÁN CÂN BẰNG TRÊN TẬP ĐIỂM BẤT ĐỘNG Chuyên ngành : Toán ứng dụng
Mã số : 60460112
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
Tài liệu tham khảo 64

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Danh mục các ký hiệu
Ký hiệu Ý nghĩa
R
n
Không gian Euclide n – chiều trên trường số thực ;
N Tập số tự nhiên;
x
i
Tọa độ thứ i của x;
x
T
Véc tơ hàng (chuyển vị của x) ;
<x,y>=x
T
y Tích vô hướng cả hai véc- tơ x và y;
x

Chuẩn Euclide của x;
)(xf
∂

Dưới vi phân của f tại x;
)(xf

của ánh xạ không giãn.
- Nội dung và tính hội tụ của một thuật toán dưới đạo hàm giải một lớp
bài toán cân bằng trên tập điểm bất động
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ii

Qua việc thực hiện và hoàn thành luận văn cùng với sự hướng dẫn tận tình
của thầy giáo GS. TSKH Lê Dũng Mưu đã giúp tôi nắm chắc và hiểu sâu hơn về
phương pháp dưới đạo hàm giải bài toán cân bằng trên tập điểm bất động. Tuy
nhiên với vốn kiến thức còn hạn hẹp, luận văn sẽ không tránh khỏi những thiếu
sót. Vì vậy em rất mong sự giúp đỡ chỉ dẫn của các thầy cô và thầy giáo hướng
dẫn.
Ngoài phần mở đầu, danh mục các ký hiệu, danh mục tài liệu tham khảo,
luận văn được chia làm 3 chương:
Chương 1: Kiến thức chuẩn bị.
Chương 2:Bài toán cân bằng.
Chương 3: Một phương pháp giải bài toán cân bằng trên tập điểm bất
động.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1

Chương 1. KIẾN THỨC CHUẨN BỊ
Trong chương 1 ta sẽ xét các kiến thức chuẩn bị cho bài luận văn. Luận
văn có liên quan đến không gian Hilbert và các khái niệm, các kết quả liên quan
đến không gian Hilbert, ánh xạ không giãn, tập điểm bất động. Do đó ta sẽ giới
thiệu những khái niệm cơ bản nhất của không gian Hilbert và các tính chất đặc
trưng nhất của nó. Nội dung của chương này được tham khảo từ các tài liệu
[2],[3].
1.1 Không gian Hilbert
Định nghĩa 1.1.1.

∈
X,
α∈
R;
iv. 〈x , x〉
>
0 với mọi x
≠
0 và
〈
x , x
〉
= 0 nếu x = 0.
3. X trở thành không gian Banach với chuẩn được định nghĩa bởi:
||x|| = 〉〈 xx, .
Định nghĩa 1.1.2.
Xét dãy {x
n
}
n
≥
0
và x thuộc không gian Hilbert thực X. Khi đó:
Dãy {x
n
} được gọi là hội tụ mạnh tới x, kí hiệu x
n

→
x, nếu như:

n
} hội tụ mạnh đến x thì cũng hội tụ yếu đến x.
(ii) Nếu {x
n
} hội tụ yếu đến x và
+∞→n
lim || x
n
|| =|| x || thì {x
n
} hội tụ mạnh đến
x.
(iii) Mọi dãy hội tụ mạnh (yếu) đều bị chặn và giới hạn theo sự hội tụ
mạnh (yếu) nếu tồn tại thì là duy nhất.
(iv) Nếu không gian Hilbert X là không gian hữu hạn chiều thì sự hội tụ
mạnh và sự hội tụ yếu là tương đương.
(v) Nếu {x
n
}
n
≥
0
là một dãy bị chặn trong không gian Hilbert X thì ta trích
ra được một dãy con hội tụ yếu.
(vi) Nếu {x
n
}
n
≥
0

222
yxyTIdxTIdTyTx −≤−−−+−
ii)T là không giãn nếu nó Lipschitz liên tục với hằng số 1, tức là với mọi x và y
thuộc C ta có:
.yxTyTx −≤−

iii) T là tựa không giãn nếu ta có:
.yxyxT −≤−
FixTyCx
∈
∀
∈
∀
,
;
iv)T là tựa không giãn chặt nếu ta có:
.
T x y x y
− < −
∈
∀
x
C,
FixTy
∈
∀
.
Định nghĩa 1.2.2.
Fix(T):= {x | Tx = x}.
Định lí 1.2.3.

X,
∀λ

∈
[0,1].
Hàm
ƒ
được gọi là lồi chặt trên C nếu:
ƒ
(
λ
x+(1-
λ
)y ) <
λƒ
(x)+(1-
λ
)
ƒ
(y),
∀
x, y
∈
X; x
≠
y ,
∀λ

∈
[0,1].

,
∀
x,y
∈
X,
∀λ

∈
[0,1].
Ví dụ:
1. Mọi hàm afine
ƒ
(x) = a
T
x+b là hàm lồi. Nó thoả mãn đẳng thức:
ƒ
(
λ
x+(1-
λ
)y) =
λƒ
(x)+(1-
λ
)
ƒ
(y),
∀
x, y.
Do đó nó không lồi chặt.

2
)1(
22
〉〈−+
−
yxyx
λ
λ

=
2
2
)1(
yx −
−
λ
λ
.
Do đó hàm ƒ(x) =
2
2
x
là hàm lồi mạnh với hệ số 1.
3. Giả sử C là một tập khác rỗng. Hàm khoảng cách d
C
(x) được định nghĩa
như sau:
d
C
(x) =

)(lim ydyy
Ckk
=−
→∞
.
Do C lồi nên z
k
:=
λ
x
k
+ (1-
λ
) y
k
∈
C. Ta có:
d
C
( z ) ≤ || z - z
k
|| = ||
λ
(x-x
k
) + (1-
λ
)(y-y
k
) ||

được gọi là hình chiếu
của x lên C. Khi đó π là nghiệm của bài toán tối ưu:
2
min
2
yx
Cy
−
∈
.
Mệnh đề sau đây cho ta điều kiện cần và đủ để
π
là hình chiếu của x lên C
trong trường hợp C lồi.
Mệnh đề 1.2.5. Giả sử C là tập lồi khác rỗng trong X. Đặt:
N
C
(x) = {w
∈
X
|

xyw −,

≤
0,
∀
y
∈
C}.

||
2
≤ || y
λ
- x ||
2
= || (
π
- x) +
λ
(y-
π
) ||
2
.
Khai triển vế phải và giản ước ta thu được :
.0,2 ≥−−+−
πππλ
yxy

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6

Cho λ tiến tới 0 ta thu được bất đẳng thức :
.0, ≤−−
ππ
yx

Điều này đúng với y
∈


= || x -
π
||
2
+ ||
π
- y ||
2
+2
yx −−
ππ
,

≥ || x-

π
||
2
+ ||
π
- y ||
2
≥ || x -
π
||
2
.
Suy ra
π

π
′
||
2
≤ 0 .
Điều này chỉ xảy ra khi
π
=
π
’
.
Vậy khi C lồi thì hình chiếu của x lên C nếu tồn tại là duy nhất. □.
Trong trường hợp C là tập con lồi, đóng khác rỗng của không gian Hilbert
thì với mọi x luôn tồn tại hình chiếu của x trên C.
Thật vậy, theo định nghĩa tồn tại dãy {x
k
} trong C thoả mãn:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7

)(lim x
C
dx
k
x
k
=−
+∞→
.
Suy ra dãy {x


⇔

( ) ( ), ( ) 0. (1.1)
C C C
P x P y P x x− − ≤

và
.0)(),()( ≤−− yPyyPxP
CCC
(1.2)
Cộng hai vế của (1.1) và (1.2) ta có:
.0)()()(),()( ≤−−−− yxyPxPyPxP
CCCC

⇔
.)()(,)()(
2
yPxPyxyPxP
CCCC
−−≤−

Do đó P
C
là không giãn ổn định.
Phép tương ứng mỗi điểm x với hình chiếu của nó trên C kí hiệu là P
C
và
được gọi là phép chiếu khoảng cách. Theo chứng minh mệnh đề trên, ta có tính
chất sau đây của hình chiếu :

X thoả mãn:
0
),()()(
lim
0
=
−
〉−
′
〈−−
→−
xy
xyxGxGyG
xy
.
Phần tử G'(x) được gọi là đạo hàm Fréchet của G tại điểm x.
Hàm G được gọi là khả vi trên K nếu nó khả vi tại mọi điểm thuộc K.
Ta có mệnh đề sau:
Mệnh đề 1.2.8. Xét hàm G: X
→
R. Khi đó:
i) Nếu G liên tục thì G nửa liên tục dưới.
ii) Nếu G khả vi thì G liên tục và
,),(
)()(
0
lim
'
>=<
−+

0
),(')()(
lim
0
=
−
−−−
→−
xy
xyxGxGyG
xy

Và
0),('lim
0
=−
→−
xyxG
xy
.
nên suy ra:
.0))()((lim
0
=−
→−
xGyG
xy

Vậy G liên tục. Đặt x
t

0
lim =−
→
x
t
x
t
nên:
0
||||
),(
'
)()(
0
lim =
−
>−<−−
→
x
t
x
x
t
xxGxG
t
xG
t
. (1.4)
Từ (1.3) và (1.4) suy ra điều phải chứng minh.□.
Mệnh đề 1.2.9. Xét hàm

X, ta có:
2
' '
( ) ( ), .
f y f x y x x y
η
− − ≥ −

Chứng minh. (i) → (ii).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10

Giả sử ƒ lồi mạnh với hệ số η. Với mọi x, y và t ∈ (0,1), ta có:
(1-t)
ƒ
(x) + t
ƒ
(y)
≥ƒ
( ty + (1-t)x ) +
2
η
t (1-t) ||x-y||
2

Suy ra:
t(ƒ(y) - ƒ(x)) ≥
ƒ
( ty + ( 1- t ) x) - ƒ(x) +
2

+
2
η
t
2
||x-y||
2
. (1.5)
ƒ(y) ≥ƒ(z) +
))(1(),(' xytzf −−
+
2
η
(1-t)
2
||x-y||
2
. (1.6)
Nhân hai vế của (1.5) với (1- t) > 0 và nhân hai vế của (1.6) với t > 0, sau
đó cộng lại ta thu được :
(1-t)
ƒ
(x) + t
ƒ
(y)
≥

ƒ
((1-t)x+ty) +
2

Cộng vế hai bất đẳng thức trên ta thu được:
0 ≥
xyyfxf −− ),()(
''
+ η || x - y ||
2
.
Từ đó suy ra (iii).
(iii) → (ii). Giả sử có tính chất (iii), ta đặt :
γ
(t) :=
ƒ
(x + th) với h := x – y.
Khi đó:
t
thxfththxf
t
ttt
t
tt
∆
+
−
∆
+
+
=
∆
−
∆

2
.
Vậy
ƒ(y) - ƒ(x) = γ(1) - γ(0) =
=
hxf ),(
'
+
∫
>ƒ−+ƒ<
1
0
''
),()( dthxthx

≥
hxf ),(
'
+ dtyxt
2
1
0
−
∫
η

=
xyxf −),(
'
+

.
Kết quả tiếp theo cho ta điều kiện cho lời giải bài toán tối ưu hàm lồi:
Mệnh đề 1.2.11. Xét hàm F: X
→
R là hàm khả vi trên K với K là tập con
lồi của X. Khi đó ta có:
Nếu x
*
là nghiệm của bài toán cực tiểu F trên K thì:
,0**),(
'
≥− xyxF

∀
y
∈
K.
Hơn nữa. nếu F lồi thì điều kiện trên cũng là điều kiện đủ.
Chứng minh. Giả sử F(x
*
) là cực tiểu của F trên K. Xét y ∈ K bất kỳ, do
K lồi nên (1-t)x* +ty
∈
K,
∀
t
∈
(0,1). Do đó:
F((1-t)x* +ty) = F (x
*

) ) = F ((1 – t )x
*
+ty)
≤
(1- t ) F(x
*
) + t F(y),
∀
t
∈
(0,1).
Suy ra:
*),x(F)y(F
t
*)x(F*))xy(t*x(F
−≤
−
−
+
∀t ∈ (0 , 1).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13

Có t tiến tới 0
+
ta được:
* x-y (x*),F'
≤ F(y) - F(x*).
Từ đó suy ra F(x*) ≤ F(y) với mọi y ∈ K hay x* là nghiệm của bài toán
cực trị. .

2
1
)x(F
2
1
)'x
2
1
x
2
1
(F)
2
'xx
(F
+
=+<+=
+
.
Điều này dẫn tới mâu thuẫn, suy ra điều giả sử là sai . □
Khái niệm sau là mở rộng của các khái niệm đạo hàm và khả vi.
Định nghĩa 1.2.13. Xét f: X
→
R
∪
{+
∞
} và x
∈
X. Phần tử w

Ta có mệnh đề nói lên tính khả dưới vi phân của hàm lồi :
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14

Mệnh đề 1.2.14. Nếu f : X
→
R là hàm lồi thì
)
x
(
f
∂
≠
0 với mọi x
∈
X hay
là f khả dưới vi phân. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15

Chương 2. BÀI TOÁN CÂN BẰNG
Bài toán cân bằng là bài toán xuất phát từ nhu cầu thực tế. Ta xét mô hình
kinh tế có nhiều đối thủ; trong mỗi đối thủ (đối tác) đều có một hàm lợi ích
riêng. Mỗi quyết định của đối thủ này lại ảnh hưởng đến lợi ích của đối tác kia.
Thông thường lợi ích của các đối thủ thường mâu thuẫn với nhau. Như vậy
phương án tối ưu cho tất cả các đối tác thường là không tồn tại và người ta đã
nghĩ đến một phương án mang tính cân bằng, theo nghĩa là mọi đối tác đều có lý
do để chấp nhận và bài toán cân bằng đã ra đời từ nhu cầu thực tiễn đó. Các khái

nhận các dạng biểu thực đặc biệt, bài toán (EP) sẽ trở thành các
bài toán cơ bản khác. Dưới đây là một vài trường hợp quan trọng.
2.1.2. Các ví dụ
2.1.2.1. Bài toán tối ưu.
Xét bài toán:
(
)
{
}
min
x x C
ϕ
∈ ;
Đặt
(
)
(
)
(
)
, :
x y y x
φ ϕ ϕ
= −
;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16

Hiển nhiên
(

→:
ϕ
là hàm lợi ích của đấu thủ j.
Giả sử
(
)
1
, , , ,
j j p
x x x
ϕ
là lợi ích của đấu thủ j khi đấu thủ này chọn
phương án chơi
j j
x C
∈
, còn các đấu thủ thứ k khác chọn phương án chơi là
k k
x C
∈
với mọi
k j
≠
.
Định nghĩa điểm cân bằng Nash
Ta gọi
(
)
* *
1

x x y x x x x x x x
ϕ ϕ
− + − +
≤ .
Định nghĩa này cho thấy rằng nếu một đối thủ j nào đó rời khỏi phương án
cân bằng, trong khi các đối thủ khác vẫn giữ phương án cân bằng, thì đối thủ j sẽ
bị thua thiệt. Đây chính là lý do mà khái niệm cân bằng này được chấp nhận
trong thực tế. Điểm cân bằng này được gọi là điểm cân bằng Nash vì khái niệm
này do nhà kinh tế học F. Nash đưa ra đầu tiên.
Dưới đây bài toán cân bằng Nash sẽ được hiểu là bài toán tìm một điểm
cân bằng ( Nash) của
ϕ
trên C. Ta sẽ kí hiệu bài toán này là
(
)
,
N C
ϕ
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17

Bài toán cân bằng Nash có thể mô tả dưới dạng bài toán cân bằng (EP).
Thật vậy, ta xây dựng hàm
RCC
→
×
:
φ
bằng cách đặt:

(
)
*, 0
x y y C
φ
≥ ∀ ∈
.
Ta sẽ chứng tỏ
(
)
* *
1
* , ,
p
x x x
= với
*
j j
x C
∈
là một điểm cân bằng Nash.
Thật vậy, nếu trái lại, sẽ tồn tại j và một điểm
j j
y C
∈
sao cho
)., ,,,, (), ,,,, ,(
**
1
*

*
yx
φ
0), ,,,, ,()(
**
1
*
1
*
1
*
<−
+− pjjjjj
xxyxxx
ϕϕ
.
Mâu thuẫn với việc
*
x
là nghiệm của (EP).□.
Vậy x* là một điểm cân bằng Nash khi và chỉ khi x* là nghiệm bài toán
cân bằng (EP).
2.1.2.3. Bất đẳng thức biến phân.
Cho C là một tập lồi đóng khác rỗng trong R
n
và F: C
n
R
2→
là một ánh

tập hợp các giá thành chi phí có thể, ứng với phương án
x
. Khi đó bài toán (2.1),
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18

chính là bài toán tìm phương án sản xuất
*
x
trong tập chiến lược C và giá
*
v

ứng với
*
x
sao cho chi phí là thấp nhất. Trong trường hợp, ánh xạ giá không
phụ thuộc vào phương án sản xuất, tức là
cxF
=
)(
với mọi x, bất đẳng thức biến
phân (2.1) trở thành bài toán quy hoạch quen thuộc:

{
}
min :
T
c x x C
∈ . (LP)

( )
, : max ,
v F x
x y v y x
φ
∈
= −
.
Từ đây suy ra ngay rằng,
(
)
, 0
x y y C
φ
≥ ∀ ∈
, khi và chỉ khi x là nghiệm
của (2.1).
Một trường hợp riêng quan trọng của bài toán (2.1) là khi C = R
n
+
và F
đơn trị. Khi đó bài toán (1) tương đương với bài toán sau, được gọi là bài toán
bù: Tìm

(
)
(
)
0 sao cho 0, 0
T

exFxexxFxF

Vậy
(
)
0
i
F x
≥
với mọi i. Ngoài ra nếu chọn
0
y
=
ta có:
(
)
0 , 0
F x x
≤ − ≤
. Suy ra
(
)
0
T
x F x
=
.
Điều ngược lại mọi nghiệm của bài toán bù đều là nghiệm của bất đẳng
thức biến phân là hiển nhiên.
Bài toán quy hoạch lồi

(
)
* *
v f x
∈∂

nên theo định nghĩa dưới vi phân, ta có:
(
)
(
)
*, - * *
v y x f x f y y
+ ≤ ∀
.
Thế nhưng do
*
x
là nghiệm của bất đẳng thức biến phân, nên :
*, - * 0
v y x y C
≥ ∀ ∈
.
Từ đây suy ra
(
)
(
)
*
f x f y y C

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20

2.1.2.4. Bài toán điểm bất động Kakutani.
Cho
: 2
C
F C
→
. Điểm
x
được gọi là điểm bất động của F nếu
(
)
x F x
∈
.
Giả sử với mọi
(
)
,
x C F x
∈
lồi, compact, khác rỗng. Khi đó bài toán tìm một
điểm bất động của F có thể mô tả dưới dạng bài toán cân bằng (EP).
Để chứng tỏ điều này, với mỗi
,
x y C
∈
, ta đặt:

x
là nghiệm của bài toán (EP), tức là :
x C
∈
và
(
)
, 0
x y y C
φ
≥ ∀ ∈
.
Khi đó lấy
y
là hình chiếu của
x
lên tập lồi đóng
(
)
F x
.Ta có:
.,max,
)(
xvvxxyyx
xFv
−−=−−
∈

Do
x