Trờng Đại học Vinh
Khoa toán


Đoàn Văn Tùng

Bất đẳng thức biến phân
Với biến số rời rạc
Khoá luận tốt nghiệp đại học
Ngành cử nhân khoa học Toán

Vinh - 2004

Trờng Đại học Vinh

Khoa toán


Đoàn Văn Tùng

2


Bất đẳng thức biến phân
Với biến số rời rạc

Khoá luận tốt nghiệp đại học
Ngành cử nhân khoa học Toán
Lớp B1, Khoá 41 Toán

Cán bộ hớng dẫn khoa học:

2.1.
2.2.

Kết luận
Tài liệu tham khảo

3

6
6
8
11
12
18
18
23
24
27
28


Mở đầu
Bài toán bất đẳng thức biến phân có vị trí rất quan trọng trong toán học. Do
tính đa dạng và phong phú của bài toán mà nội dung bao gồm nhiều lĩnh vực
nghiên cứu khác nhau. Bài toán bất đẳng thức biến phân ngày càng khẳng định
những giá trị về mặt lý thuyết cũng nh những ứng dụng trong các chuyên
ngành Đại số, Giải tích, Hình học, Điều khiển ...
Do đòi hỏi của khoa học kỹ thuật và thực tiễn mà bất đẳng thức biến phân
có nhiều dạng khác nhau. Khoá luận này nghiên cứu về bài toán Bất đẳng
thức biến phân với biến số rời rạc với hy vọng thể hiện một phơng pháp và


2

n

k

k

i x , i 0, i
i

i =1

i =1

= 1 đợc gọi là

tổ hợp lồi của hệ điểm đã cho.
1.1.2. Đoạn thẳng
Cho x1, x2 Rn, tập hợp
[x1, x2] = {x Rn : x = 1x1 + 2x2 , 1, 2 0, 1 + 2 = 1}
đợc gọi là đoạn thẳng nối hai điểm đã cho.
Chú ý: Nếu kí hiệu 1 = , 2 = 1- thì [0, 1] và đoạn thẳng nối x1, x2
sẽ là [x1, x2] = {x Rn : x = x1 + (1- ) x2, 0 1}. Đoạn thẳng [x1, x2] đợc
gọi là thuộc (hay nằm trọn trong) tập hợp M nếu điểm x [x1, x2] thì
M.
Nếu có

x

Nghĩa là x không thể là điểm trong của một đoạn thẳng nào bất kì thuộc M.
1.1.5. Siêu phẳng, siêu phẳng tựa
Cho c Rn và số thực . Tập hợp
S = {x Rn : c, x = }
đợc gọi là siêu phẳng trong Rn.
Tập hợp {x Rn : c, x } đợc gọi là nửa không gian giới hạn bởi siêu
phẳng {x Rn : x, c = }.
Cho tập lồi M và siêu phẳng S = {x Rn: c, x = }. Nếu tồn tại x0 M mà
c, x0 = và c, x , x M thì ta nói rằng S là siêu phẳng tựa đối với M.
Tập hợp
M = {x Rn : aj, x bi , i = 1, ..., m, aj = (aij) Rn}
là một tập hợp lồi và đợc gọi là tập lồi đa diện.
1.1.6. Bao đóng, bao lồi của tập hợp
Cho hợp M bất kì thuộc Rn, tập đóng nhỏ nhất thuộc Rn chứa M đợc gọi là
bao đóng của M và kí hiệu M .
Cho tập M Rn, tập lồi nhỏ nhất thuộc Rn chứa M đợc gọi là bao lồi, kí hiệu
là convM.
Nhận xét:
a) Bao đóng của M là bằng giao của tất cả các tập đóng chứa M.
b) Bao lồi của M là bằng giao của tất cả các tập lồi chứa M.
1.1.7. Nón lồi
Tập con K của Rn đợc gọi là một nón nếu với x K, > 0 thì x K.
Điểm gốc O có thể thuộc hoặc không thuộc K.
Nếu K là một nón thì với a Rn, a + K cũng là một nón. Nón K không
chứa đờng thẳng nào gọi là nón nhọn. Nón a + K nhọn thì ta nói a + K là nón
nhọn có mũi tại a. Nếu K là nón nhọn chứa 0, thì 0 là đỉnh của nó (nón nhọn
có mũi tại 0). Nếu nón K là tập lồi thì ta cũng nói K là nón lồi.

6


Theo định nghĩa hình chiếu, ta có
||p - v||2 ||z - v||2 = ||p + (x - p) - v ||2 = ||(x - p) + (p - v)||2 =
= 2||x - p||2 + 2x - p, p - v + ||p - v||2.
Điều đó xẩy ra khi và chỉ khi

2||x - p||2 + 2x - p, p - v 0, với [0, 1].
Bất đẳng thức (*) đúng với mọi [0, 1], từ đó suy ra
7

(*)


x - p, p - v 0, hay là x - p, v - p 0.
Hệ quả. x - v, x - p ||x - p||2 và || x - p|| ||v - p||.
1.2.2.3. Định lý (Định lý tách điểm). Nếu M là tập lồi thuộc Rn với mọi
điểm v nằm ngoài bao đóng của M, tồn tại siêu phẳng
P = {x Rn : c, x = }
sao cho c, v = và c, x < , với x M.
Chứng minh. Kí hiệu p là hình chiếu của v trên M , xét siêu phẳng
P = {x Rn : c, x = }
trong đó c = v - p, = c, x.
Khi đó rõ ràng c, x = , mặt khác từ định lý 1.2.2.2
x - p, v - p 0, hay là x, v - p p, v - p
cho ta

x, v - p p, v - p < v, v - p, x M

(Vì v - p, v - p = ||v - p||2 > 0 nên v, v - p > p, v - p).
Do vậy, với mọi x M ta có
c, x = v - p, x, v - p, v = c, v = .

Định nghĩa: Tập M Rn đợc gọi là giới nội nếu nó chứa trong một hình
cầu nào đó tâm O (tức là tồn tại r đủ lớn để với x M, ||x|| r).
Một tập hợp con F của một tập lồi C đợc gọi là diện của nó nếu F là tập lồi
và bất cứ đoạn thẳng nào của C chứa một điểm x F làm điểm trong đều nằm
trọn trong F, nghĩa là
x F, x = y + (1- )z , y, z C, 0 < < 1 thì y, z F.
1.2.2.7. Định lý. Giao của một tập hợp lồi C với một siêu phẳng tựa P của
nó là một diện của C.
Chứng minh. Hiển nhiên C P là một tập lồi.
Mặt khác, nếu một đoạn [y, z] C chứa một điểm x C P làm điểm
trong thì chỉ có thể là {y; z} P (do đó {y; z} C P). Vì nếu trái lại siêu
phẳng P sẽ tách hẳn y với z và không còn là siêu phẳng tựa của C nữa.
1.2.2.8. Định lý. Cho C là một tập hợp lồi đóng, không giới nội.
i) Tại mỗi điểm x C có ít nhất một nửa đờng thẳng phát xuất từ x và nằm
trọn trong C.
ii) Hợp tất cả các nửa đờng thẳng này là một nón lồi đóng có dạng G(x) =
Ct + {x} trong đó G là một nón lồi đóng không phụ thuộc vào x, có mũi tại O.
iii) Nón G là nhọn khi và chỉ khi C có ít nhất một đỉnh G gọi là nón các phơng vô hạn của C.
Hệ quả. Nếu một tập lồi đóng C có đỉnh thì mọi diện của nó đều chứa ít
nhất một đỉnh của C.
1.2.2.9. Định lý. Tập con K thuộc Rn là nón lồi có đỉnh tại gốc 0 khi và chỉ
khi với mọi x, y K và mọi số > 0 ta có x K và x + y K.

9


Thật vậy, nếu K là nón lồi thì với x K, ta có x K (theo định nghĩa của
nón). Hơn nữa K là tập lồi nên với x, y K thì

1

Hàm f(x) xác định trên tập lồi M đợc gọi là hàm lồi mạnh nếu tồn tại hằng
số p > 0 sao cho với mọi x, y M và [0, 1] ta có
f[x + (1- )y] f(x) + (1- )f(y) - k,
trong đó k = (1- )p||x - y||2.
Chú ý: - Hàm f(x) lồi mạnh thì f(x) là hàm lồi.
- Hàm tuyến tính và tuyến tính afin là hàm vừa lồi vừa lõm.
- Nếu hàm f(x) là hàm lõm thì g(x) = - f(x) là hàm lồi.
1.3.2. Các tính chất quan trọng của hàm lồi ([3], [5]).
1.3.2.1. Định lý
i) Hàm f liên tục trên tập lồi M là hàm lồi khi và chỉ khi
10


x+
f
2

y
1
1
f(x) + f(y).
2
2


ii) Cho f(x) là hàm lồi, liên tục trên tập lồi M, khi đó hàm
y = max{f(x), 0} , x M
là hàm lồi.
iii) Tổng hữu hạn các hàm lồi là hàm lồi.
iv) Cho fi(x), i = 1, 2, ..., k là các hàm lồi. Khi đó

k

i f(xi), xi M

(1.5)

i =1

k

i
i =1

= 1.

Chứng minh. Giả sử có bất đẳng thức (1.5). Khi đó với k = 2, theo định
nghĩa thì f là hàm lồi.
Ngợc lại, giả sử f(x) là hàm lồi trên M. Xét
11


x=

k

i xi, i 0,
i =1

k




i f(xi) = (1- k) 1 i
= kf(xl) + (1- k)

f(xk) + kf(xk)
k

k 1

i f(xi).
i =1

i
Với i =
0 i = 1, k 1 . Rõ ràng
1 k

k 1

i = 1.
i =1

Do vậy, theo giả thuyết quy nạp ta đợc
k

k 1

k 1




f(λ1x1 + λ2x2) ≤ λ1 f(x1) + λ2f(x2).
[

(

a

x1

ξ1

λ1x1 + λ2x2

ξ2

)

]

x2

b

XÐt ®o¹n th¼ng [x1, λ1x1 + λ2x2]. Theo ®Þnh lý Lagr¨ng th× tån t¹i ξ1 mµ
x1 < ξ1 < λ1x1 + λ2x2 sao cho
f(λ1x1 + λ2x2) - f(x1) = (λ1x1 + λ2x2 - x1)f’(ξ1).
⇔ f’(ξ1) =


f ( x2 ) − f ( λ1 x1 + λ2 x2 )
λ1 ( x1 − x2 )

(b)

V× f”(x) ≥ 0, ∀x ∈ [a, b] nªn f’(x) lµ hµm ®ång biÕn trªn [a, b] do ξ1 < ξ2, ta
f’(ξ1) < f’(ξ2).
Tõ (a), (b) vµ (c) suy ra
f (λ1 x1 + λ2 x2 ) − f ( x1 )
f ( x2 ) − f ( λ1 x1 + λ2 x2 )

0, 0 < λ1 < 1, nªn tõ (d) ta cã

λ1[f(λ1x1 + λ2x2) - f(x2)] < (1 - λ2)[f(x2) - f(f(x2) - f(λ1x1 + λ2x2)]
⇔

f(λ1x1 + λ2x2) < λ1f(x1) + (1 - λ1)f(x2)

⇔

f(λ1x1 + λ2x2) < λ1f(x1) + λ2f(x2).

VËy f(x) lµ hµm låi trªn [a, b].
13

Nếu M Wx0 = M thì ta nói x0 là điểm cực tiểu tuyệt đối của f trên M.
1.3.2.9. Định lý. Cực tiểu địa phơng của hàm lồi f trùng với cực tiểu tuyệt
đối trên tập lồi M.
Chứng minh. Giả sử x0 M là điểm cực tiểu địa phơng của f trên M. Khi
đó tồn tại lân cận Wx0 sao cho
f(x0) f(x), với x M Wx0 .
Lấy bất kì x M. Xét y = x + (1- )x0, 0 1. Rõ ràng với đủ bé ta
thì y rơi vào lân cận Wx0 . Mặt khác, do M lồi nên y M.
Từ đó ta suy ra y M Wx0 . Do vậy f(x0) f(y).
Nhng f là hàm lồi nên f(x0) f(y) f(x) + (1- )f(x0)
Ta suy ra

f(x0) f(x), với x M.

14


Điểm x0 M lồi đợc gọi là điểm trong của M nếu với mỗi x M thì tồn tại
y M mà x0 = x + (1- )y , 0 < < 1.
1.3.2.10. Định lý. Nếu hàm f đạt cực đại tại điểm trong x 0 của tập lồi M
thì f không đổi trên tập M.
Chứng minh. Giả sử x0 là điểm trong M là f đạt cực đại tức là
f(x), f(y) f(x0), với x, y M.

(*)

Vì x0 là điểm trong nên tồn tại y M, với mỗi x M ta có
x0 = x + (1- )y , 0 < < 1.
Mặt khác, f là hàm lồi nên
f(x0) f(x) + (1- )f(y), 0 < < 1.

Chơng này nghiên cứu một số tính chất của bài toán bất đẳng thức biến
phân rời rạc và nêu thuật toán đa thức giải bài toán xét trong không gian R2,
dựa trên thuật toán tìm bao lồi của một số hữu hạn điểm trong mặt phẳng.
2.1. Phát biểu bài toán
2.1.1. Định nghĩa
2.1.1.1. Cho tập hợp X Rn. Ta ký hiệu hàm vectơ F = (F1, F2, ..., Fn), trong
đó
Fi : X R, i = 1, 2, ..., n
và với x, y X thì F(x), y =

i=1
n

Fi(x)yi.

Hàm F đợc gọi là liên tục nếu mỗi hàm Fi là liên tục.
Trong [1] đã chứng minh đợc định lý sau đây:
2.1.1.1. Định lý (Định lý Brower). Giả sử X là tập lồi, compact thuộc không
gian Rn và F : X X liên tục. Khi đó F tồn tại điểm bất động, nghĩa là tồn tại
x X, sao cho F(x) = x.
2.1.1.3. Bất đẳng thức
F(x), y - x 0, với x, y X

(2.1)

đợc gọi là bất đẳng thức biến phân.
Việc tìm x X, sao cho (2.1) thoả mãn với mọi y X gọi là bài toán bất
đẳng thức biến phân. Nghĩa là bài toán bất đẳng thức biến phân có dạng: tìm
x X sao cho
F(x), y - x 0, với mọi y X.

(*)

ở đây p là hình chiếu của z trên X. Trong trờng hợp này của chúng ta nh đã nêu
trên p = x, z = (I - F)x = x - F(x). Thay vào (*) ta đợc
x - F(x), y - x x, y - x, với mọi y X.
Hay là
x, y - x - x - F(x), y - x 0, với mọi x X.
Đó là điều phải chứng minh.
2.1.2. Về bài toán bất đẳng thức biến phân
Xét trở lại bài toán bất đẳng thức biến phân, kí hiệu là VIP(F, X): tìm vectơ
x* X sao cho
F(x*), x - x* 0, với mọi x X ,
17

(2.2)


trong đó ta giả thiết X là tập hợp lồi, compact và F là hàm liên tục.
Chú ý rằng giả thiết bị chặn của tập X là cần thiết đối với bài toán bất đẳng
thức biến phân VIP(F, X).
Ví dụ. Lấy X = R, khi đó bất đẳng thức biến phân
F(x), y - x = f(x)(y - x) 0, với mọi y R,
là không có nghiệm đối với f(x) = ex.
Bây giờ chúng ta xét tập lồi, đóng X. Lấy hình cầu đóng r Rn, với bán
kính r, chứa điểm gốc O Rn. Ký hiệu Xr = X r. Lúc này, ta có tập Xr là
compact và nếu Xr thì theo định lý 2.1.1.7 cho ta nghiệm của bài toán
VIP(F, Xr), nghĩa là tồn tại xr Xr sao cho
F(xr), y - xr 0, với mọi y Xr.

(2.6)

ta thay x := (x + x* ), với mọi x Rn ta có
0 F(x*), (x + x* ) - x* = F(x*), x .
Vậy
F(x*), x 0, với mọi x Rn.
Bất đẳng thức đúng với mọi x Rn, nên cũng đúng với - x Rn, tức là cũng
có đợc
F(x*), - x 0, với mọi x Rn.
Hay
F(x*), x 0, với mọi x Rn.
Ta suy ra
F(x*), x = 0, với mọi x Rn.
Từ đó ta có điều phải chứng minh F(x*) = 0.
2.1.2.2. Trờng hợp 2. X R n+ .
Trong trờng hợp này bài toán VIP(F, X) trở thành bài toán bù:
Tìm x = x* X thoả mãn
x 0 , F(x) 0, x, F(x) = 0.
Thật vậy, vì X R n+ nên x* 0, đồng thời trong (2.2) ta thay x := x* + ei, với
ei là vectơ toạ độ đơn vị thứ i của Rn, ta có
F(x*), ei = Fi(x*), (i = 1, 2, ..., n).
Từ đó ta có F(x*) 0.
Mặt khác, trong (2.2) lấy x = 0 thì
F(x*), x* 0.
Lại vì x* 0 và F(x*) 0, ta suy ra
F(x*), x* 0.
19


Vậy F(x*), x* = 0.
Nh vậy, nếu tìm đợc nghiệm bài toán bất đẳng thức biến phân thì cũng đồng
nghĩa với việc tìm đợc nghiệm của bài toán bù vừa nêu.


trong đó F : X Rn và X {x1, x2, ..., xp}, với xi Rn (i = 1, 2, ..., p). Về mặt
hình học, bài toán này thực ra là tìm một điểm xk X (nếu có) sao cho mọi
điểm của x thuộc X đều nằm về một phía theo hớng pháp tuyến F(x*) của siêu
phẳng vuông góc với F(xk) tại xk.
20


Rõ ràng nếu có xk X thoả mãn F(xk) = 0 thì đơng nhiên xk là nghiệm của
bài toán đã cho. Vì thế không giảm tổng quát ta giả thiết F(xi) 0 đối với mọi
i = 1, 2, ..., p.
Ký hiệu C = convX (bao lồi của X) và C = vertC (tập đỉnh của C), nh ta đã
biết C là đa diện lồi và C = C X, nghĩa là mọi đỉnh của C đều thuộc X, ta có.
2.2.2. Tính chất
2.2.2.1. Định lý. Giả sử xk là nghiệm của bài toán DVIP(F, X) và F(xk) 0.
Khi đó xk phải ở trên biên của C.
Chứng minh. Theo (2.8) ta có F(xk), xk F(xk), xi i = 1, 2, ..., p.
Từ đó suy ra
F(xk), xk F(xk), x , x C,
nghĩa là
H = {x Rn : F(xk), x F(xk), xk}
là siêu phẳng tựa của C tại xk và là một diện của C [5]. Vậy với xk H C thì
xk không thể là một điểm trong của C.
Định lý 2.2.2.1 nêu trên cho thấy để tìm nghiệm của bài toán ta chỉ cần
tìm trong số các điểm biên của C. Để ý rằng định lý 2.2.2.1 cũng đúng với bài
toán VIP(F, X).
Giả sử điểm xk X ở trên biên của C = convX. Kí hiệu D là diện thứ
là tập đỉnh của D. Nh đã biết mỗi đỉnh
nguyên nhỏ nhất của C chứa xk và D
của D cũng là một đỉnh của C, nghĩa là phải thuộc X. Khi đó ta có:

2.3.1.1. Thuật toán 1 [4].
Bớc 1. Sắp xếp các điểm xi (i = 1, 2, ..., p) theo thứ tự tọa độ x tăng dần.
Những điểm có cùng toạ độ x thì lấy theo tọa độ y tăng dần (chỉ cần giữ
lại hai điểm ứng với tọa độ y nhỏ nhất và lớn nhất, vì các điểm khác sẽ
không thể là đỉnh của bao lồi). Giả sử dãy điểm sau khi sắp xếp là: x1, x2, ..., xh
(h p).
Các đỉnh thuộc bao lồi đợc chia thành hai loại: Các đỉnh ở phía trên của
bao lồi C, tức là các đỉnh ta gặp khi đi trên biên của C từ x1 đến xh theo chiều
kim đồng hồ và các đỉnh còn lại là các đỉnh ở phía dới. Sau đây là cách tìm
các đỉnh ở phía trên, các đỉnh còn lại đợc tìm tơng tự.
Bớc 2. Rõ ràng x1 là đỉnh của C và ta đa x1 vào danh sách, ký hiệu là . Ta
sẽ lần lợt kiểm tra các điểm còn lại thuộc dãy điểm nào là đỉnh ở phía trên của
C.
Bớc 3. Giả sử trong có các điểm x1, ..., xi -1 (2 i h) ta bổ sung vào
điểm tiếp theo xi. Kiểm tra i > h hay không?
+ Nếu có, là tập đỉnh trên của C.
+ Nếu i h thì chuyển tới bớc 4.

22


Bớc 4. Nếu trong có ít nhất 3 điểm thì ta kiểm tra xem 3 điểm cuối
trong danh sách này có tạo nên một rẽ trái không (việc này đợc thực hiện
nhờ thuật toán đã nêu trong [2]). Nếu phát hiện thấy có sự rẽ trái thì loại bỏ
khỏi điểm giữa trong số 3 điểm vừa xét và lại tiếp tục kiểm tra 3 điểm cuối
trong (nếu có). Còn nếu 3 điểm cuối không tạo nên một rẽ trái hoặc trong
có ít hơn 3 điểm thì quay lại bớc 3.
Cuối cùng, khi mọi điểm đã đợc xét ta sẽ nhận đợc danh sách chứa các
đỉnh phía trên cần tìm. Xuất phát từ xh, thực hiện các bớc tơng tự nh trên ta
sẽ tìm đợc các đỉnh phía dới. Tập các đỉnh trên và đỉnh dới chính là tập đỉnh

kiểm tra đỉnh đầu tiên gặp phải). Có q đỉnh nh vậy. Do đó thuật toán 2 nêu trên
có độ phức tạp là O(qì(p-1)).

Kết luận

Kết quả khoá luận có thể đợc tóm tắt là:
1. Tiếp cận đợc một số thành tựu mới thông qua các kiến thức cơ bản về
giải tích lồi.
2. Trên cơ sở tiếp cận các kiến thức đã nêu, rút ra đợc các trờng hợp đặc
biệt của bài toán bất đẳng thức biến phân.
3. Nêu đợc thuật toán đa thức giải bài toán trong không gian R2, chứng
minh đợc độ phức tạp tính toán của thuật toán.
Kết quả của khoá luận còn có thể mở rộng theo nhiều hớng. Chúng tôi hy
vọng theo hớng mở rộng khác nhau, chẳng hạn xét trong R3, chúng ta sẽ có đợc
những kết quả thú vị mới.
Kết quả có đợc là sự tập dợt nghiên cứu, chắc còn nhiều điều cần phải xem
xét. Rất mong quý thầy cô giáo, cùng các bạn đồng nghiệp góp ý giúp đỡ.
Một lần nữa, tác giả xin chân thành cảm ơn thầy giáo hớng dẫn, các thầy cô
giáo trong tổ Điều khiển và khoa Toán. Xin cảm ơn bố và gia đình cùng bạn bè
đã động viên giúp đỡ tác giả trong quá trình học tập và làm khoá luận.

tài liệu tham khảo

24


[1]. David Kinderlehrer and Guido Stampacchia, An introduction to
Vairational Inequalities and their Applications, Academic press, New York
London Toronto Sydney San Francisco, 1980.
[2]. Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried