LèI CÁM ƠN

Em xin chân thành cám ơn thay giáo Nguyen Văn Tuyên đã t¾n
tình hưóng dan, giúp đõ em trong suot thòi gian thnc hi¾n khoá lu¾n.
Xin chân thành cám ơn các thay, các cô trong to giái tích-khoa
Toán, trưòng Đai hoc sư pham Hà N®i 2 đã tao moi đieu ki¾n giúp đõ
em hoàn thành khoá lu¾n này.
Xin chân thành cám ơn gia đình và ban bè đã tao moi đieu ki¾n
thu¾n loi cho em trong quá trình thnc hi¾n khoá lu¾n.
Em xin chân thành cám ơn.

Hà N®i, ngày ..... tháng 05 năm 2012
Sinh viên

Nguyen Văn Mùng

i


LèI CAM ĐOAN

Tôi xin cam đoan, dưói sn hưóng dan cna ThS. Nguyen Văn Tuyên
khóa lu¾n tot nghi¾p “Bat đang thNc bien phân vector affine đơn
đi¾u” đưoc hoàn thành không trùng vói bat kỳ khóa lu¾n nào khác.
Trong quá trình hoàn thành khóa lu¾n, tôi đã thùa ke nhung
thành tnu cna các nhà khoa hoc vói sn trân trong và biet ơn.

Hà N®i, ngày ..... tháng 05 năm 2012
Sinh viên

Nguyen Văn Mùng

ii


Mnc lnc

Má đau

1

1

4

Bat đang thNc bien phân affine
1.1. Bat đang thúc bien phân

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

4

1.2. Bài toán bù.................................................................................10
1.3. Bat đang thúc bien phân affine...............................................11
1.4. Sn ton tai nghi¾m cna bat đang thúc bien phân affine . .

19

1.4.1. Sn ton tai nghi¾m dưói giá thiet đơn đi¾u . . . . .

19


1.4.2. Sn ton tai nghi¾m dưói giá thiet đong dương . . .

26

2 Bat đang thNc bien phân vector affine đơn đi¾u

34

2.1. Bat đang thúc bien phân vector affine đơn đi¾u......................34
2.2. Tính on đ%nh cna t¾p nghi¾m......................................................39
2.3. Tính liên thông cna t¾p nghi¾m...............................................48
Ket lu¾n

52

Tài li¾u tham kháo

53

iii


Mé ĐAU
1. Lý do chon đe tài
Bài toán bat đang thúc bien phân (Variational Inequality
Problem) ra đòi vào nhung năm 1960, gan lien vói công trình cna G.
Stampacchia,
J. L. Lions [6] . Hi¾n nay, bài toán bat đang thúc bien phân đã đưoc
phát trien thành nhieu dang khác nhau, ví du: bat đang thúc bien phân

vector, tna bat đang thúc bien phân, giá bat đang thúc bien phân, bat
đang thúc bien phân an, bat đang thúc bien phân suy r®ng ...
Bài toán này thu hút đưoc sn quan tâm cna nhieu nhà toán hoc vì
các mô hình cna nó chúa nhieu bài toán quan trong cna m®t so lĩnh
vnc khác nhau trong toán hoc như là trưòng hop riêng, ví du: toi ưu
hóa, lý thuyet trò chơi, cân bang Nash, cân bang mang giao thông ...
Khái ni¾m bat đang thúc bien phân vector (Vector Variational
Inequality) (viet tat là VVI) đưoc đưa ra bói F. Giannessi trong bài báo
[4]. Có rat nhieu bài báo nghiên cúu ve van đe này có the tìm thay
trong cuon sách chuyên kháo cna GS. F. Giannessi [5]. Ta cũng chú
ý rang VVI có the coi như m®t công cu thích hop đe nghiên cúu các
bài toán toi ưu vector và VVI còn là m®t trong nhung công cu quan
trong nhat đe nghiên cúu các bài toán cân bang vector. Các tác giá có
nhung đóng góp cho sn phát trien cna bài toán này có the ke đen: F.
Giannessi [4, 5, 6],
T. N. Hoa, T. D. Phuong và N. D. Yen [8, 9], G. M. Lee, N. N. Tam và
N. D. Yen [13, 14, 15], N. D. Yen và J.-C. Yao [26], ...
Tính on đ%nh, đ® nhay nghi¾m và các tính chat tôpô cna t¾p
nghi¾m cna bài toán bat đang thúc bien phân đơn đi¾u đã đưoc nghiên
cúu trong [12, 13, 26].


2

Trong lu¾n văn này chúng tôi h¾ thong lai m®t so ket quá ve đieu
ki¾n đn cho tính núa liên tuc trên cna ánh xa t¾p nghi¾m cna bat đang
thúc bien phân vector affine đơn đi¾u có tham so đã đưoc trình bày
trong [26]. Ngoài ra, trong lu¾n văn còn trình bày m®t so tính chat tôpô
cna t¾p nghi¾m cho lóp bài toán này.
Lu¾n văn đưoc chia thành hai phan. Chương 1 trình bày các kien

thúc cơ bán ve bài toán bat đang thúc bien phân affine, các bài toán
liên quan và m®t so đieu ki¾n ton tai nghi¾m. Chương 2 trình bày các
tính chat cơ bán cna t¾p nghi¾m cna bài toán bat đang thúc bien phân
vector affine đơn đi¾u, tính on đ%nh cna ánh xa t¾p nghi¾m và tính liên
thông cna t¾p nghi¾m.

2. Mnc đích nghiên cNu
Nghiên cúu ve bài toán bat đang thúc bien phân vector affine đơn
đi¾u và các tính chat cna ánh xa t¾p nghi¾m.

3. Nhi¾m vn nghiên cNu
Nghiên cúu tính on đ%nh cna ánh xa t¾p nghi¾m và tính các tính
chat tôpô cna t¾p nghi¾m cna bài toán bat đang thúc bien phân vector
affine đơn đi¾u.

4. Phương pháp nghiên cNu
Đoc tài li¾u, phân tích, so sánh, tong hop.


5. Cau trúc khoá lu¾n
Chương 1 trình bày các kien thúc cơ bán ve bài toán bat đang
thúc bien phân affine, các bài toán liên quan và m®t so đieu ki¾n ton tai
nghi¾m.
Chương 2 trình bày các tính chat cơ bán cna t¾p nghi¾m cna bài
toán bat đang thúc bien phân vector affine đơn đi¾u, tính on đ%nh cna
ánh xa t¾p nghi¾m và tính liên thông cna t¾p nghi¾m.


Chương 1
Bat đang thNc bien phân affine

1.1.

Bat đang thNc bien phân
Bài toán bat đang thúc bien phân đưoc náy sinh m®t cách tn

nhiên tù các bài toán toi ưu. Cho f : Rn → R vói f thu®c lóp C 1 và
6 ⊂ Rn là m®t t¾p loi, đóng và khác rong.
M¾nh đe 1.1. Neu
x¯

là m®t nghi¾m đ%a phương cúa bài toán
min {f (x) : x ∈ 6}
(∇f (x¯), y − x¯) ≥ 0
∈ 6.
(1.2)

th
ì

(1.1)
∀y

Chúng minh. Lay x¯ ∈ 6 là nghi¾m đ%a phương cna (1.1). Chon µ >
sao cho
0
f (y) ≥ f (x¯),
Vói moi y ∈ 6 \ {x¯}, ∃δ > 0 sao
cho

∀y ∈ 6 ∩ B(x¯, µ)

x¯ + t(y − x¯) ∈ 6 ∩ B¯ (x¯,
µ) vói

t ∈ (0, δ). Khi đó
0

r
lim f (x¯ + t(y − x¯)) = f (x¯, y − x¯)
≤ t→0
= (∇f (x¯), y − x¯) .
− f (x¯)
t


5

Do đó ta có đieu phái chúng minh.
Đ¾t




φ(x) = ∇f (x) = 




∂f (x)
∂x 


∀x ∈ Rn,
1

.. 
.
∂ f (x )
∂xn

(1.3)

thì (1.2) đưoc viet lai như sau
(φ(x¯), y − x¯) ≥ 0 ∀ y ∈ 6.

(1.4)

Đ%nh nghĩa 1.1. Neu 6 ⊂ Rn là t¾p con loi, đóng, khác rong và φ :
6 → Rn là m®t toán tú thì bài toán tìm x¯ ∈ 6 thóa mãn (1.4)
đưoc
goi là bài toán bat đang thúc bien phân, hay đơn gián là bat đang
thúc bien phân, kí hi¾u là VI(φ, 6). T¾p nghi¾m Sol(VI(φ, 6)) cna
VI(φ, 6) là t¾p tat cá x¯ ∈ 6 thóa mãn (1.4) .
Đ%nh nghĩa 1.2. Nón pháp tuyen N 6(x¯) cna m®t t¾p loi 6 ⊂ n tai
R
m®t điem x¯ ∈ Rn đưoc đ%nh nghĩa bói công thúc
 .
.
:
,x−

x∗ ∈ Rn ∗ ∗

) ≤ 0 vói moi x ∈ 6 neu x¯ ∈
(x x
N 6(x¯) =
6

∅ neu x¯ ∈/ 6.
De dàng kiem tra đưoc rang
x¯ 0 ∈ φ(x¯) + N 6(x¯).

∈ Sol(VI(φ, 6)) khi và chí
khi

M¾nh đe (1.1) cho thay tù bài toán toi ưu hóa có the dan đen bat
đang thúc bien phân. M®t câu hói tn nhiên đ¾t ra: Cho m®t bat đang
thúc bien phân VI(φ, 6) vói m®t toán tú liên tnc φ : Rn → Rn có
the tìm m®t hàm thu®c lóp C1 f : Rn → R sao cho VI(φ, 6) có the thu
đưoc tù bài toán toi ưu hóa (1.1) bang phương pháp trên hay không ?
Neu có hàm f ton tai thì phái có
φ(x) = ∇f (x) ∀x ∈ 6.

(1.5)


Có the thay rang neu f thu®c lóp C2 thì toán tú φ : Rn → Rn
đưoc đ%nh nghĩa ó (1.3) là m®t ma tr¾n Jacobian đoi xúng. Nhó lai rang
neu m®t hàm vector φ : Rn → Rn có các thành phan trơn φ1, ..., φn
thì
ma tr¾n Jacobian cna φ tai x đưoc đ%nh nghĩa bói công thúc



∂φ1(x)
∂φ1 (x) ∂φ1(x
...
)



∂xn
∂x
∂x
.

Jφ(x) = 
1
2
..  .
.
.


..
..

 ∂φn(x) ∂φn(x
∂φ
n
(x)
)
...
∂xn

∂x1
∂x2
Tù giá thiet f thu®c lóp C2 và tù (1.3) ta có
∂φi(x)
∂xj

=

∂ 2f
(x)
∂xj∂xi

=

∂ 2f
(x)
∂xi∂xj

=

∂φj
(x)
∂xi

i, j.
∀

Đieu này chí ra rang Jφ(x) là ma tr¾n đoi xúng.
M¾nh đe 1.2. Cho 6 ⊂ Rn là m®t t¾p loi, đóng, khác rong. Neu φ :
Rn → Rn là m®t hàm vector vói các thành phan trơn mà

∂φi(x = ∂φj (x)
∀ i, j (m®t toán tú đoi xúng trơn), thì ó đó ton tai
)
∂xi
∂xj
m®t hàm thu®c lóp C2, f : Rn → R sao cho (1.5) đưoc thóa mãn. Đieu
đó có nghĩa là bài toán bat đang thúc bien phân VI(φ, 6) có the đưoc
coi như là đieu ki¾n can b¾c nhat cúa bài toán toi ưu (1.1) .
Như v¾y, ta thay rang bài toán toi ưu hóa trơn lóp C2 tương
úng vói bat đang thúc bien phân vói toán tú đoi xúng trơn.
M¾nh đe đơn gián sau đây cho thay, khác vói nghi¾m cna bài
toán quy hoach toán hoc, nghi¾m cna bài toán VI có m®t đ¾c trưng đ%a
phương.
M¾nh đe 1.3. Cho


x¯ ∈ 6. Neu ton tai
ε > 0 sao cho
(∇f (x¯), y − x¯) ≥ 0 ∀ y ∈ 6 ∩ B¯ (x¯, ε),
th
ì

x¯ ∈ Sol(VI(φ, 6)).

(1.6)


Chúng minh. Giá sú ε > 0 thóa mãn (1.6). Hien nhiên vói moi
y ∈ 6, ∃t = t(y) ∈ (0, 1) sao cho y(t) x¯ + t(y − x¯) ∈ 6 ∩ B¯
:=


(x¯, ε).

Tù (1.6), 0 ≤ (φ(x¯), y(t) − x¯) = t (φ(x¯), y − x¯) Đieu này có
nghĩa là
(φ(x¯), y − x¯) ≥ 0 ∀y ∈ 6. Do đó x¯ ∈ Sol(VI(φ, 6)).
Bài toán VI(φ, 6) phu thu®c vào hai du ki¾n: t¾p 6 và toán tú
φ. Cau trúc cna t¾p nghi¾m Sol(VI(φ, 6)) đưoc quyet đ%nh bói tính
chat cna t¾p hop và toán tú. Trong lý thuyet bat đang thúc bien phân
có các van đe cơ bán sau: sn ton tai và duy nhat cna nghi¾m, tính on đ
%nh và đ® nhay cna t¾p nghi¾m tương úng vói bài toán nhieu du
ki¾n, thu¾t toán đe tìm t¾p nghi¾m hay m®t phan cna t¾p nghi¾m.
Đ%nh lý Hartman-Stampacchia sau đây là m®t đ%nh lý cơ bán ve
sn ton tai nghi¾m cna bài toán VI. Nó đưoc chúng minh bang vi¾c sú
dung đ%nh lý điem bat đ®ng Brouwer.
Đ%nh lý 1.1. (Đ%nh lý Hartman-Stampacchia) Neu 6 ⊂ Rn là
m®t t¾p loi, compact, khác rong và φ : 6 → Rn là liên tnc thì bài
toán VI(φ, 6) có nghi¾m.
Dưói các đieu ki¾n búc thích hop, ta có the thu đưoc các đ%nh lý
ve sn ton tai nghi¾m cna bài toán VI trên các t¾p loi nhưng không
compact. Chang han, ta có ket quá sau:
Đ%nh lý 1.2. Cho 6 ⊂ Rn là m®t t¾p loi, đóng, khác rong và φ : 6 → Rn
là toán tú liên tnc. Neu ton tai x0 ∈ 6 sao cho
.
.
φ(y) − φ(x0), y − x0 " y − x0 "→ +∞ khi " y "→ +∞, y ∈ 6,
(1.7)
thì bài toán VI(φ, 6) có nghi¾m.
. Ý nghĩa chính xác cna (1.7) là: cho γ > 0 ta có the tìm ρ > 0 sao
0

φ(y) − φ(x
. ), y −
cho
x0
≥ γ vói moi y ∈ 6 thóa mãn ||y|| > ρ.


|
|

y−

||


Rõ ràng là neu 6 là compact thì, vói moi x0 ∈ 6, (1.7) đúng. Neu ton
tai x0 ∈ 6 sao cho (1.7) đúng thì ta nói rang đieu ki¾n búc đưoc
thóa
mãn. Đieu ki¾n búc có vai trò quan trong khi nghiên cúu bat đang thúc
bien phân trên các t¾p ràng bu®c không compact. Chú ý rang (1.7) chí
là m®t dang quen thu®c cna đieu ki¾n búc.
Neu ton tai x0 ∈ 6 và α > 0 sao cho
.
.
φ(y) − φ(x0), y − x0 ≥ α||y − x0||2
∀y
∈6
(1.8) thì (1.7) thóa
mãn. Rõ ràng là neu ton tai x0 ∈ 6 và α > 0 sao cho
(φ(y) − φ(x), y − x) ≥ α||y −


2

∀x, y ∈ 6,

(1.9)

x||
thì (1.8) đưoc thóa mãn.
Đ%nh nghĩa 1.3. Neu ton tai α > 0 sao cho (1.9) thóa mãn thì φ
đưoc goi là đơn đi¾u manh trên 6. Neu các đieu ki¾n yeu hơn là:
(φ(y) − φ(x), y − x) > 0
∈ 6, x ƒ= y,
(1.10)

∀x, y

(φ(y) − φ(x), y − x) ≥ 0

∀x, y

và

∈ 6,

(1.11)

là đúng thì φ đưoc goi tương úng là đơn đi¾u ch¾t và đơn đi¾u trên 6 .
Ví dn 1.1. Cho 6 ⊂ Rn là m®t t¾p loi, đóng, khác rong. Cho D ∈
Rn×n và c ∈ Rn. Neu ma tr¾n D là xác đ%nh dương thì toán tú φ :

6 → Rn đưoc đ%nh nghĩa bói φ(x) = Dx + c, x ∈ 6, là đơn đi¾u
manh trên 6. Trong trưòng hop này, de dàng thay rang đieu ki¾n α >
0 đe (1.9) đưoc thóa mãn có the đưoc đ%nh nghĩa bang cách đ¾t
.
.
α = inf vT Dv : v ∈ Rn, ||v|| = 1 .


Tương tn, neu D là núa xác đ%nh dương thì công thúc φ(x) =
Dx+c, x ∈ 6, đ%nh nghĩa m®t toán tú đơn đi¾u.


M¾nh đe 1.4. Các khang đ%nh sau đây là đúng
(i) Neu φ là đơn đi¾u ch¾t trên 6 thì bài toán VI(φ, 6) không the
có nhieu hơn m®t nghi¾m.
(ii) Neu φ là liên tnc và đơn đi¾u trên 6 thì t¾p nghi¾m cúa bài toán
VI(φ, 6) là loi và đóng (có the rong).
Đe chúng minh (ii) ta phái sú dung bo đe sau.
Bo đe 1.1. Neu 6 ⊂ Rn là m®t t¾p loi, đóng và φ : 6 → Rn là toán tú
đơn đi¾u, liên tnc
x¯ ∈ Sol(VI(φ, 6)) khi và chs x¯ ∈ 6 và
thì
khi
(φ(y), y − x¯) ≥ 0
6.

∀y ∈

(1.12)


Chúng minh. Đieu ki¾n can: Cho x¯ ∈ Sol(VI(φ, 6)). Do φ đơn đi¾u
nên ta có
(φ(y) − φ(x¯), y − x¯) ≥ 0 ∀y ∈ 6.
Ket hop đieu này vói (1.4) ta đưoc
(φ(y), y − x¯) ≥ (φ(x¯), y − x¯) ≥ 0 ∀y ∈ 6.
Đieu ki¾n đú: Giá sú
x¯

∈ 6 và (1.12) đưoc thóa mãn. Co đ%nh

y ∈ 6. Do 6 là t¾p loi nên y(t) := x¯ + t(y − x¯) ∈ 6 vói moi t
∈ (0, 1).
The y = y(t) thì (1.12) tró thành
0 ≤ (φ(y(t)), y(t) − x¯) = (φ(x¯ + t(y − x¯)), t(y − x¯)) .
Đieu này có nghĩa
(φ(x¯ + t(y − x¯)), y − x¯) ≥ 0 ∀t ∈ (0, 1).
Cho t → 0, do φ liên tuc nên thu đưoc (φ(x¯), y − x¯) ≥ 0. Do bat
đang thúc cuoi đúng vói y ∈ 6 bat kỳ, nên ta có x¯ ∈ Sol(VI(φ, 6)).


Ta se chúng minh M¾nh đe 1.4
Chúng minh. (i) Giá sú phán chúng φ là đơn đi¾u ch¾t trên 6 nhưng
bài toán VI(φ, 6) có hai nghi¾m khác nhau x¯ và y¯. Khi đó, ta có
(φ(x¯), y¯ − x¯) ≥ 0 và (φ(y¯), x¯ − y¯) ≥ 0. C®ng theo các ve các
bat đang thúc này ta đưoc (φ(x¯) − φ(y¯), y¯ − x¯) ≥ 0. Đieu này
mâu thuan vói (φ(y¯) − φ(x¯), y¯ − x¯) > 0.
(ii) Giá thiet rang φ đơn đi¾u và liên tuc trên 6. Vói moi y ∈ 6, ký
hi¾u Ω(y) là t¾p tat cá x¯ ∈ 6 thóa mãn bat đang thúc (φ(y), y − x¯)
≥ 0. Rõ ràng Ω(y) là loi và đóng. Tù Bo đe 1.1 ta có
\

Sol(VI(φ, 6)) =
Ω(y).
y∈6

Do đó Sol(VI(φ, 6)) là t¾p loi và đóng (có the rong).
Tù Đ%nh lý 1.2 và M¾nh đe 1.4 (i) ta có: neu 6

∅ và φ : 6 →

=ƒ

Rn

là toán tú đơn đi¾u manh và liên tuc thì bài toán (VI(φ, 6)) có nghi¾m
duy nhat.
Trong muc tiep theo, chúng ta se xét các bài toán bat đang thúc
bien phân trong trưòng hop t¾p ràng bu®c 6 là m®t nón.

1.2.

Bài toán bù
Sau đây ta se đ%nh nghĩa m®t cách chính xác ve khái ni¾m bài

toán bù (không tuyen tính).
M¾nh đe 1.5. Neu 6 là nón loi đóng, thì bài toán VI(φ, 6) có the
đưoc viet tương đương như sau
x¯ ∈ 6, φ(x¯) ∈ 6+ ,
(φ(x¯), x¯) = 0,

(1.13)


ó đó 6+ = {ξ ∈ Rn : (ξ, υ) ≥ 0 ∀υ ∈ 6} là nón đoi ngau dương cúa
6.


Chúng minh. Giá sú
x¯

là m®t nghi¾m cna (1.4). Vói moi υ ∈ 6, do 6

là nón loi, ta có x¯ + υ ∈ 6. Tù (1.4), ta ket có
0 ≤ (φ(x¯), (x¯ + υ) − x¯) = (φ(x¯), υ) .
1
+
Do đó φ(x¯) ∈ 6 . Hơn nua,
x¯ ∈ 6 và 2x¯ ∈ 6, theo (1.4) ta có
2
do
1
.
.
0 ≤ φ(x¯),1 −
= − (φ(x¯), x¯)
x¯
2
x¯ 2
và
0 ≤ (φ(x¯), 2x¯ − x¯) = (φ(x¯), x¯) .
Vì v¾y (φ(x¯), x¯) = 0. Ta đã chúng minh đưoc (1.13).
Bây giò, giá sú x¯ thóa mãn (1.13). Vói moi y ∈ 6, tù (φ(x¯), x¯)

=0
và φ(x¯) ∈ 6+, ta có
(φ(x¯), y − x¯) = (φ(x¯), y) ≥ 0.
Đieu này có nghĩa là x¯ ∈ Sol(VI(φ, 6)).
Đ%nh nghĩa 1.4. Bài toán (1.13) ó đó 6 ⊂ Rn là nón loi, đóng và
φ : Rn → Rn, đưoc kí hi¾u là NCP(φ, 6) và đưoc goi là bài toán
bù (không tuyen tính) đưoc đ%nh nghĩa bói φ và 6.
Tù bài toán bù là bài toán bat đang thúc bien phân đ¾c bi¾t, các
đ%nh lý ve sn ton tai nghi¾m cna bài toán VI có the đưoc áp dung cho
nó.

1.3.

Bat đang thNc bien phân affine
Theo đ%nh lý 3.1 [13], neu

là m®t nghi¾m đ%a phương cna bài

x¯ toán quy hoach toàn phương
.
.
min
1 T
f (x)
x Mx + qT x : x ∈ ,
2
=
6

(1.14)



ó đó M là ma tr¾n đoi xúng cap n × n, q ∈ Rn và 6 ⊂ Rn là t¾p
loi đa di¾n thì (M x¯ + q, y − x¯) ≥ 0 vói moi y ∈ 6. Túc là x¯ là
m®t nghi¾m cna bài toán VI(φ, 6) ó đó φ(x) = Mx + q là toán tú
affine có ma tr¾n
Jacobian M đoi xúng.
Đ%nh nghĩa 1.5. Cho M ∈ Rn×n, q ∈ Rn. Cho 6 ⊂ Rn là t¾p loi đa
di¾n. Bài toán bat đang thúc bien phân:
Tìm x¯ ∈ 6 sao cho
(M x¯ + q, y − x¯) ≥ 0 ∀y ∈ 6

(1.15)

đưoc goi là bài toán bat đang thúc bien phân affine đưoc xác đ%nh bói
t¾p du li¾u {M, q, 6} và đưoc kí hi¾u là AVI(M, q, 6). T¾p nghi¾m
cna bài toán đưoc kí hi¾u là Sol(AVI(M, q, 6)).
Đ%nh lý 1.3.
Vector công thúc

x¯ ∈ Rn là nghi¾m cúa (1.15), vói 6 đưoc cho
bói

6 = {x ∈ Rn : Ax ≥ b}
(1.16)
m×n
m
vói A ∈ R
, b ∈ R , khi và chs khi ton
λ¯ = (λ¯1 , ..., λ¯m ) ∈

tai cho

Rm sao
 M x¯ − AT λ¯ + q
= 0,
(1.17)

Ax¯ ≥ b, λ¯ ≥ 0,

 λ¯ T (Ax¯ − b) =
0.

Chúng minh. Đieu ki¾n can: Ta kí hi¾u Ai là hàng thú i cna A và bi là
thành phan thú i cna vector b. Ta đ¾t ai = AiT vói i = 1, ..., m. Giá sú x¯
∈ Sol(AVI(M, q, 6)). Đ%nh nghĩa I = {1, ..., m} , I0 = {i ∈ I : (ai,
x¯) = bi} và I1 = {i ∈ I : (ai, x¯) > bi}. Vói moi υ ∈ Rn thóa mãn
(ai, υ) ≥ 0 vói i ∈ I0,
de dàng thay rang ton tai δ1 > 0 sao cho (ai , x¯ + tυ) ≥ bi vói
moi
i ∈ I và t ∈ (0, δ1). The y x¯ + tυ, vói t ∈ (0, δ1), vào (1.15) ta
=

đưoc


(−M x¯ − q, υ) ≤ 0

(M x¯ + q, υ) ≥ 0. Do
đó


vói moi υ ∈ Rn thóa
mãn

(−ai, υ) ≤ 0 vói i ∈ I0.
Theo Bo đe Farkas (xem đ%nh lý 3.2 [13]) ton tai các so thnc không âm
λ¯i(i ∈ I0 ) sao cho
.
λ¯i(−ai) = −M x¯ − q.
(1.18)
i∈I0

Đ¾t λ¯i = 0 vói moi i ∈ I1 và λ¯ = (λ¯1 , ..., λ¯m ). Do ai = AiT vói i
= 1, ..., m,
tù (1.18) ta đưoc đang thúc thú nhat trong (1.17). Tù x¯ ∈ 6(A, b)
và
λ¯i(Aix¯ − bi) = 0 vói moi i ∈ I, các đieu ki¾n khác trong (1.17) cũng
thóa
mãn.
Đieu ki¾n đú: Giá sú ton tai λ¯ = (λ¯1 , ..., λ¯m ) ∈ Rm sao cho
(1.17) thóa mãn. Khi đó, vói moi y ∈ 6 ta có
. T
.
.
¯
(M x¯ + q, y − x¯) = A λ , y − x¯ = λ¯ , (Ay − b) − (Ax¯
.
− b)
= λ¯ T (Ay − b) + λ¯ T (Ax¯ −
b)
= λ¯ T (Ay − b) ≥ 0.

Đieu này cho thay

là m®t nghi¾m cna (1.15). Đ%nh lý đã đưoc chúng

x¯ minh.
Ta có the suy ra tù đ%nh lý 1.3 hai h¾ quá sau, m®t h¾ quá có the
áp dung cho trưòng hop 6 có bieu dien:


6 = {x ∈ Rn : Ax ≥ b, x ≥ 0}
và trưòng hop còn lai áp dung khi 6 có bieu dien:
6 = {x ∈ Rn : Ax ≥ b, Cx = d} .
é đó A ∈ Rm×n, b ∈ Rm, C ∈ Rs×n và d ∈ Rs.

(1.19)
(1.20)


H¾ quá 1.1. Vector x¯ ∈ Rn là m®t nghi¾m cúa (1.15), ó đó 6 đưoc
cho bói công thúc (1.19) khi và chs khi ton tai λ¯ = (λ¯1 , ..., λ¯m ) ∈
Rm sao cho

 M x¯ − AT λ¯ + q ≥ 0,

(1.21)
¯
Ax¯ ≥ b, x¯ ≥ 0, λ ≥ 0,

x¯T (M x¯ − AT λ + q) + λT (Ax¯
− b) = 0.



¯

¯

H¾ quá 1.2. Vector ∈ Rn là m®t nghi¾m cúa (1.15) ó đó 6 đưoc
x¯
cho bói công thúc (1.20) khi và chs khi ton
λ¯ = (λ¯ 1 , ..., λ¯ m ) ∈
tai
Rm và
s
µ¯ = (µ¯1 , ..., µ¯s ) ∈ R sao cho

 M x¯ − AT λ¯ − C T µ¯ + q = 0,

(1.22)
Ax¯ ≥ b, Cx¯
λ¯ ≥
= d,
0,

 λ¯ T (Ax¯ − b)
= 0.
Không giong vói t¾p nghi¾m và t¾p nghi¾m đ%a phương cna bài
toán quy hoach toàn phương không loi, t¾p nghi¾m cna bài toán AVI có
cau trúc đơn gián hơn.
Đ%nh lý 1.4. T¾p nghi¾m cúa bài toán bat đang thúc bien phân affine
là hop cúa huu han các t¾p loi đa di¾n.

Chúng minh. Xét m®t bài toán AVI tong quát dang (1.15). Do 6 là t¾p
loi đa di¾n nên ton tai m ∈ N, A ∈ Rm×n, b ∈ Rm sao cho
6 = {x ∈ Rn : Ax ≥ b} . Theo Đ%nh lý 1.3, x ∈ Sol(AVI(M, q,
6)) khi và chí khi ton tai λ = (λ1, ..., λm) ∈ Rm sao cho


 Mx − AT λ + q =
0,


Ax ≥ b, λ ≥
0,

 λT (Ax − b) = 0.

(1.23)


Cho I = {1, ..., m}. Cho x ∈ Sol(AVI(M, q, 6)), ta đ¾t
I0 = {i ∈ I : Aix = bi} , I1 = I \ I0 = {i ∈ I : Aix > bi}. Tù bat
đang thúc cuoi trong (1.23) ta đưoc
λi = 0 ∀i ∈ I1.
Do đó (x, λ) thóa mãn h¾








Mx − AT λ + q =
0, AI0 x = bI0 , λI0
≥ 0,
AI

I

I

1x ≥ b 1, λ

1

(1.24)

= 0.

Co đ%nh I0 ⊂ I và kí hi¾u QI0 là t¾p tat cá (x, λ) thóa mãn (1.24).
Rõ
ràng QI0 là t¾p đa di¾n loi. Ta có
Sol(AVI(M, q, 6)) =

[

{Pr0 Rn (QI ) : I0 ⊂ I} ,
(1.25)

ó đó PrRn (x, λ) := x. Do PrRn (.) : Rn × Rm → Rn là m®t toán
tú tuyen tính, vói moi I0 ⊂ I, PrRn (QI0 ) là t¾p loi đa di¾n. Tù (1.25)
ta có Sol(AVI(M, q, 6)) là hop cna huu han các t¾p loi đa di¾n.

Đ%nh nghĩa 1.6. M®t núa đưòng ω = {x¯ + tυ¯ : t ≥ 0}, ó đó υ¯
∈ Rn \{0}, và là m®t t¾p con cna Sol(AVI(M, q, 6)), đưoc goi là
m®t tia nghi¾m cna bài toán (1.15).
Đ%nh nghĩa 1.7. M®t đoan ωδ = {x¯ + tυ¯ : t ∈ [0, δ)}, ó đó υ¯
∈ Rn \ {0}, δ > 0, và là m®t t¾p con cna Sol(AVI(M, q, 6)), đưoc
goi là m®t khoáng nghi¾m cna bài toán (1.15).
H¾ quá 1.3. Các khang đ%nh sau đây là đúng:
(i) T¾p nghi¾m cúa bat dang thúc bien phân affine là m®t t¾p đóng (có
the rong).
(ii) Neu t¾p nghi¾m cúa bat đang thúc bien phân affine không b% ch¾n


thì bài toán có m®t tia nghi¾m.
(iii) Neu t¾p nghi¾m cúa bat đang thúc bien phân affine là vô han thì bài
toán có m®t khoáng nghi¾m.
Chúng minh. Khang đ%nh (i) đưoc suy ra trnc tiep tù công thúc (1.25)
vì, vói moi I0 ⊂ I, t¾p PrRn (QI0 ) là loi đa di¾n và đóng.
Neu Sol(AVI(M, q, 6)) là không b% ch¾n thì tù (1.25), ton tai t¾p chí
so
I0 ⊂ I sao cho
ΩI0 := PrRn (QI0 )

(1.26)

là m®t t¾p không b% ch¾n. Do ΩI0 là m®t t¾p loi đa di¾n, nên nó là t¾p
loi, đóng và không b% ch¾n. Theo đ%nh lý 8.4 (xem [21], Rockafellar), ΩI0
chúa m®t phương lùa xa; có nghĩa là ton tai υ¯ ∈ Rn \ {0} sao cho
x + tυ¯ ∈ ΩI0 ∀x ∈ ΩI0 , ∀t ≥ 0.

(1.27)


Lay x¯ ∈ ΩI0 tùy ý, tù (1.25) và (1.27) ta có x¯ + tυ¯ ∈ Sol(AVI(M,
q, 6))
vói moi t ≥ 0. Do đó ta đã chúng minh đưoc bài toán (1.15) có m®t
tia nghi¾m. Neu Sol(AVI(M, q, 6)) là vô han thì tù (1.25) ta suy
ra ton tai t¾p chí so I0 ⊂ I sao cho t¾p loi đa di¾n ΩI0 là vô han.
Do đó phái ton tai hai điem khác nhau x ∈ ΩI0 và y ∈ ΩI0 . Rõ ràng là
t¾p [x, y) := {x + t(y − x) : t ∈ [0, 1)} là m®t khoáng nghi¾m
cna (1.15).
Bang cách sú dung Đ%nh lý 1.4 ta có the thu đưoc m®t đ¾c trưng
đay đn cna tính chat không b% ch¾n cna t¾p nghi¾m cna bài toán
AVI. Chúng ta xét bài toán (1.15) ó đó 6 đưoc cho bói công thúc
(1.16) và ta đưa vào các kí hi¾u sau
δ(A) = {υ ∈ Rn : Aυ ≥ 0} ,
.
.
δ(A)+ = z ∈ Rn : zT υ ≥ 0 ∀υ ∈ δ(A) ,
.
.
n
T
l(M ) = z ∈ R : z Mz = 0 .


Chú ý rang δ(A) và {υ ∈ Rn : Aυ ∈ δ(A)+} là các nón loi đa di¾n,
trong
khi l(M ), trong trưòng hop tong quát, là nón đóng, không loi. Chú
ý rang δ(A) = 0+6 và δ(A)+ = (0+6)+.
Đ%nh lý 1.5. T¾p nghi¾m cúa (1.15) là không b% ch¾n khi và chs khi
ton tai m®t c¾p (υ, u0 ) ∈ Rn × Rn , υ ƒ= 0, u0 ∈ Sol(AVI(M, q,

6)), sao cho
(i) υ ∈ δ(A), Mυ ∈ δ(A)+, υ ∈ l(M );
(ii) (Mu0 + q)T υ = 0;
.
.
0
(iii) Mυ, y − u ≥ 0 ∀y ∈ 6.
Chúng minh. Đieu ki¾n đú: Giá sú rang có c¾p (υ, u0) ∈ Rn × Rn,
υ ƒ= 0, u0 ∈ Sol(AVI(M, q, 6)), sao cho (i)-(iii) thóa mãn. Đ¾t
xt = u0 + tυ, t > 0. Cho y ∈ 6, tù (i)-(iii) ta có
.
.
(Mxt + q, y − xt) = M (u0 + tυ) + q, y − (u0 + tυ)
.
.
.
.
= Mu0 + q, y − u0 −t Mu0 + q, υ
s
¸¸
x
s
¸= ¸0 x
≥0
.
.
+ t Mυ, y − u0 −t2 (M υ, υ)
s
¸¸
x

s ¸= ¸0 x
≥0
≥ 0.
Đieu này suy ra xt ∈ Sol(AVI(M, q, 6)) vói t > 0. Do đó t¾p
nghi¾m
không b% ch¾n.
Đieu ki¾n can: Giá sú rang t¾p Sol(AVI(M, q, 6)) là không b
% ch¾n. Tù (1.25), ton tai I0 ⊂ I sao cho t¾p ΩI0 đưoc đ%nh nghĩa
bói (1.26) là b% ch¾n. Áp dung Đ%nh lý 8.4 ([21], Theorem 8.4) suy ra
ton
tai υ ∈ Rn, υ ƒ= 0, và u0 ∈ 0 sao cho
ΩI
u0 + tυ ∈
ΩI

0

⊂ Sol(AVI(M, q, 6)) ∀t ≥ 0.

(1.28)