TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN

NGUYỄN THỊ KIỀU TRANG

TẬP LỒI VÀ MỘT SỐ TÍNH CHẤT CỦA TẬP LỒI

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC

Hà Nội – 2017


TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN

NGUYỄN THỊ KIỀU TRANG

TẬP LỒI VÀ MỘT SỐ TÍNH CHẤT CỦA TẬP LỒI

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Giải tích

Người hướng dẫn khoa học

ThS. Bùi Ngọc Mười

Hà Nội – 2017


Ký hiệu toán học



Mục lục
LỜI MỞ ĐẦU
1 Các
1.1
1.2
1.3
1.4

khái niệm
Tập afin .
Tập lồi . .
Phần trong
Bao lồi . .

1
cơ bản của tập lồi
. . . . . . . . . . . . .
. . . . . . . . . . . . .
tương đối và bao đóng
. . . . . . . . . . . . .

.
.
.
.

.
.
.

.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.

.
.
.

18
19
20
22
22

4

Tập đa diện lồi
4.1 Mặt của khối đa diện . . . .
4.2 Đỉnh và cạnh của khối đa diện
4.3 Cực của một khối đa diện . . .
4.4 Biểu diễn của khối đa diện lồi

Tài liệu tham khảo

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

25

ii



Tập M ⊂ Rn được gọi là tập afin ( hay còn gọi là đa tạp afin) nếu nó
bao hàm mọi đường thẳng bất kì đi qua hai điểm nằm trong nó.
Tức là: (1 − λ)a + λb ∈ M, ∀λ ∈ R.
Tập afin bao hàm điểm gốc thì được gọi là không gian con.
Định lý 1.1. (Xem [1, Proposition 1.1. P.3]) Tập M = ∅ là tập afin
nếu và chỉ nếu M = a + L, với a ∈ M và L là không gian con.
Mệnh đề 1.1. Không gian con L được gọi là song song với tập afin M .
Có duy nhất một tập M = ∅ và song song với không gian con L.
Số chiều của không gian con L song song với tập afin M được gọi là
2


Khóa luận tốt nghiệp Đại học

NGUYỄN THỊ KIỀU TRANG

số chiều của M .
Ví dụ 1.1.1. Điểm a ∈ Rn được gọi là tập afin có số chiều bằng 0 bởi
vì không gian con song song với tập M = {a} là L = {0}.
Đường thẳng đi qua hai điểm a và b là tập afin có số chiều là 1.
Vì không gian con song song với nó là không gian con 1 chiều x =
{λ(b − a)|λ ∈ R}.
Tập afin (n − 1) chiều được gọi là siêu phẳng.
Định lý 1.2. (Xem [1, Proposition 1.2. P.4])
Mọi tập afin r-chiều có dạng:
M = {x|Ax = b}, b ∈ Rn , A ∈ Rm×n sao cho: rank A = n − r.
Ngược lại, mọi tập có dạng trên là tập afin r-chiều.
Hệ quả 1.1. (Xem [1, Corollary 1.1. P.4]) Mọi siêu phẳng là tập có
dạng:
H = {x| a; x = α}, a ∈ Rn \{0}, α ∈ R


k

x

x

1

1 ... 1


 (∗)

có hạng là r + 1.
Hệ quả 1.2. (Xem [1, Corollary 1.2. P.5]) Bao afin M của tập k các
điểm afin độc lập là:
{x1 , ..., xk } ∈ Rn là tập afin (k − 1) chiều. ∀x ∈ M , ta có cách biểu
diễn duy nhất: x =

1.2

k
i
i=1 λi x ,

k
i=1 λi

= 1.

và chỉ nếu nó bao hàm tất cả các tổ hợp lồi cơ bản của nó.
Định lý 1.6. (Xem [1, Proposition 1.6. P.7]) Giao của một họ các tập
lồi là một tập lồi. Nếu C, D là tập lồi thì C + D := {x + y|x ∈ C, y ∈ D};
βC := {βx|x ∈ C} là một tập lồi.
Định nghĩa 1.4. Tập M ⊂ Rn được gọi là mặt nón nếu:
x ∈ M, λ > 0 ⇒ λx ∈ M .
Gốc 0 của nó có thể không nằm trong tập M .
Mặt nón M không bao gồm đường thẳng nào thì được gọi là điểm.
Trong trường hợp 0 cũng được gọi là đỉnh của M và a + M là nón với
đỉnh tại a.
Định lý 1.7. (Xem [1, Proposition 1.7. P.7]) Tập M ⊂ Rn là nón lồi
nếu và chỉ nếu:
λM ⊂ M, ∀λ > 0.

(1.2)

M +M ⊂M

(1.3)

Hệ quả 1.3. (Xem [1, Corollary 1.4. P.8])
Cho E là một nón lồi. Tập {λx|x ∈ E, λ > 0} là nón lồi nhỏ nhất
chứa E.
Nón sinh bởi E kí hiệu là cone E.

5


Khóa luận tốt nghiệp Đại học


+

Ví dụ 1.3.1. Chuẩn cơ bản trong Rn là chuẩn lp :
x

p=

(

n
i=1

1

| xi |p ) p , 1 ≤ p ≤ ∞.

Và chuẩn l∞ :
x

∞=

max1≤i≤n | xi | được gọi là chuẩn Tchebycheff.

Chuẩn l2 có thể được định nghĩa thông qua tích vô hướng. Có nghĩa
là:
x =

x, x được gọi là chuẩn Ơ-clit.

Cho chuẩn . trong Rn , khoảng cách giữa hai điểm x, y ∈ Rn là một

hoặc tương đương a là giới hạn dãy điểm của C.
a ∈ int C nếu và chỉ nếu hình cầu quanh a hoàn toàn nằm trong C.
Hệ quả 1.4. (Xem [1, Corollary 1.6. P.9]) Một điểm của tập lồi C ⊂ Rn
là điểm nằm trong của C nếu ∀x ∈ Rn , ∃α > 0 thỏa mãn:
a + α(x − a) ∈ C.
Số chiều của tập lồi được định ghĩa bằng số chiều của bao afin. Tập
lồi C ⊂ Rn được gọi là số chiều toàn phần nếu dim C = n.
Định lý 1.9. (Xem [1, Proposition 1.10. P.10]) Bao đóng và điểm trong
tương đối của tập lồi là tập lồi.
Cho C ⊂ Rn là tập lồi chứa điểm gốc. Hàm số pC : Rn → R thỏa
mãn:
pC (x) = inf{λ > 0|x ∈ λC} được gọi là độ đo của C.
Định lý 1.10. (Xem [1, Proposition 1.11. P.11]) Hàm độ đo pC (x) của
tập lồi C ⊂ Rn , 0 thuộc phần trong tương đối của nó thỏa mãn:
(i) pC (αx) = αpC (x), ∀x ∈ Rn , α > 0.
(ii) pC (x + y) ≤ pC (x) + pC (y), ∀x, y ∈ C.
7


Khóa luận tốt nghiệp Đại học

NGUYỄN THỊ KIỀU TRANG

(iii) pC là hàm liên tục.
(iv) int C = {x|pC (x) < 1} ⊂ C ⊂ cl C = {x|pC (x) ≤ 1}.
Hệ quả 1.5. (Xem [1, Corollary 1.7. P.11]) Nếu a ∈ int C, b ∈ cl C, thì
x = (1 − λ)a + λb ∈ int C, ∀λ ∈ [0, 1). Nếu tập lồi C có phần trong khác
rỗng thì cl(int C) = cl C, int(cl C) = int C.
Định nghĩa 1.6. Cho C là một tập lồi trong Rn , vectơ y khác 0 được
gọi là phương lùi xa của C nếu:


Bao lồi

Mọi tập E ⊂ Rn cho trước, đều tồn tại một tập lồi bao hàm E. Đó là
Rn . Phần giao nhau của tất cả các tập lồi bao hàm E được gọi là Bao
lồi của E và kí hiệu là : conv E.
Định lý 1.12. (Xem [1, Proposition 1.13. P.13])Bao lồi của tập E ⊂ Rn
gồm có tất cả các tổ hợp của tất cả các phần tử của nó. trong đó
νkc :=

gk
gk

k

.

Như vậy, ∀x ∈ conv E có thể biểu thị như một tổ hợp lồi của hữu hạn
các điểm của E.
Định lý 1.13. Định lí Caratheodory’s Cho E là tập chứa trong tập afin
−
k-chiều. Khi đó, ∀→
x ∈ conv E có thể biểu thị như tổ hợp lồi của k+1
hoặc ít hơn các phần tử của E.

9


Chương 2
Các định lí tách cơ bản của tập lồi


Khóa luận tốt nghiệp Đại học

NGUYỄN THỊ KIỀU TRANG

trên , nó là có ích để nhắc lại một tính chất cơ bản của hàm tuyến tính:
Một hàm tuyến tính l(x) := t, x với t ∈ Rn \{0} không bao giờ đạt
giá trị nhỏ nhất (hoặc giá trị lớn nhất) trong tập C tại điểm trong của
C. Nếu nó là giới hạn trên (hoặc dưới) trên một tập afin thì nó là một
số không đổi trong tập afin đó.
Nếu tập D trong định lí trên tập mở thì (2.4) dẫn đến:
t, x ≥ α > t, y , ∀x ∈ C, y ∈ D.
Hệ quả 2.1. (Xem [1, Corollary 1.10. P.20]) Nếu một tập afin C không
thỏa mãn cắt một tập mở D thì tồn tại một siêu phẳng chứa C và cắt D.
Hệ quả 2.2. (Xem [1, Lemma 1.3. P.20])Cho C là một tập lồi khác rỗng
trong Rn . Nếu C là đóng và 0 ∈
/ C thì tồn tại một t ∈ Rn \{0} thỏa mãn:
t, x ≥ η > 0, ∀x ∈ C.
Định nghĩa 2.1. Hai tập con C, D khác rỗng của Rn được gọi là "tách
mạnh mẽ" bởi một siêu phẳng t, x = α(t ∈ Rn {0}, α ∈ R) nếu
inf x∈C t, x > α > supy∈D t, y .

(2.5)

Định lý 2.3. (Định lý tách thứ 2)
Cho C, D là hai tập lồi, đóng, rời nhau và khác rỗng nằm trong Rn
thỏa mãn: C hoặc D là tập compact có thể tách mạnh mẽ bởi một siêu
phẳng.

11

thẳng trong C với x0 như điểm cuối.
Nó chỉ gọi là pháp tuyến hay chính xác hơn là pháp tuyến trong đến
C tại điểm x0 .
Tập tất cả các vectơ pháp tuyến t đến C tại x0 được gọi là nón pháp
tuyến đến C tại x0 . Kí hiệu là : NC (x0 ).
Định lý 3.2. (Xem [1, Proposition 1.15. P.22]) Cho C là một tập lồi
đóng, ∀y 0 ∈
/ C, ∃x0 ∈ ∂C thỏa mãn: x0 − y 0 ∈ NC (x0 ) với mọi siêu phẳng
tựa đến C tại x0 .
Định lý 3.3. (Xem [1, Theorem 1.6. P.23]) Một tập lồi đóng C, mà
không phải là rỗng và cũng không phải toàn bộ không gian, sẽ là giao
của tất cả các siêu phẳng tựa của nó.

3.2

Mặt và điểm cực biên

Định nghĩa 3.2. Một tập lồi con F của tập lồi C được gọi là mặt của
C nếu với mọi đường thẳng trong C với họ các điểm nằm trong F nằm
trọn trong F , tức là :
x, y ∈ C, (1 − λ)x + λy ∈ F, 0 < λ < 1 ⇔ [x, y] ⊂ F.

(3.2)

Vì tập ∅ và C chính là mặt của C.
Mặt đúng của C là mặt mà không là tập rỗng cũng không là chính
nó.
Mặt của một nón lồi chính là một nón lồi.
13


14


Khóa luận tốt nghiệp Đại học

NGUYỄN THỊ KIỀU TRANG

→
−
Nó thực sự là tập con lớn nhất chứa trong rec C và gồm có 0 và tất
cả các vectơ khác 0 sao cho: ∀x ∈ C đường thẳng đi qua x theo hướng
của y được chứa trong C.
Số chiều của tập con tuyến tính của C được gọi là lineality của C.
Một tập lồi C của lineality 0 tức là: (rec C) (− rec C) = {0}, không
chứa đường thẳng nào. Vì vậy ta thường gọi nó là line - free.
Định lý 3.7. (Xem [1, Proposition 1.20. P.26]) Cho C là một tập lồi,
đóng, khác rỗng có điểm cực trị nếu và chỉ nếu nó không chứa đường
thẳng nào.
Kí hiệu của một tập các điểm cực trị của C là U (C) và tập các hướng
cực trị của C là V (C).
Định lý 3.8. (Xem [1, Theorem 1.7. P.26]) Cho C ⊂ Rn là một tập lồi
đóng mà không chứa đường thẳng nào. Khi đó:
C = conv V (C) + cone U (C).

(3.3)

Mặt khác, x là một điểm bất kì thuộc C có thể được biểu diễn dưới
dạng: x =

i∈I

Với một tập bất kì của E trong Rn , tập E 0 = {y ∈ Pn | y, x ≤ 1, ∀x ∈ E}
được gọi là cực của E.
Nếu E là một nón lồi, đóng sao cho: λE ⊂ E, ∀x ∈ E thì điều kiện
y, x ≤ 1, ∀x ∈ E tương đương với y, x ≤ 0, ∀x ∈ E.
Vì vậy, cực của một nón M là nón M 0 = {y ∈ Rn | y, x ≤ 0, ∀x ∈ M }
. Cực của không gian con cũng như một phần bù trực giao của nó.
Định lý 3.9. (Xem [1, Proposition 1.22. P.29])
Nếu M1 , M2 ⊂ Rn là một nón lồi, đóng thì :
(M1 + M2 )0 = M10 ∩ M20 , (M1 ∩ M2 )0 = M10 + M20 .
Cho tập C ⊂ Rn ,hàm số x ∈ Rn −→ sc (x) = supy∈C x, y được gọi là
hàm tựa của C.
Định lý 3.10. (Xem [1, Proposition 1.23. P.29])Cho C là một tập lồi,
đóng, bao hàm 0
(i) Độ đo của C là một hàm tựa của C 0 .
(ii) Nón lùi xa của C và bao đóng của một nón sinh ra bởi C 0 là cực
lẫn nhau.
16


Khóa luận tốt nghiệp Đại học

NGUYỄN THỊ KIỀU TRANG

(iii) Tập con tuyến tính của C và không gian con sinh ra bởi C là phần
bù trực giao của nhau. Với C và C 0 là hoán vị của nhau.
Hệ quả 3.4. (Xem [1, Corollary 1.15. P.30]) Với mọi tập lồi đóng
C ⊂ Rn chứa 0 ta có:
dim C 0 = n − lineality C. (1)
lineality C 0 = n − dim C. (2)
Số dim C − lineality C được gọi là rank C.

khi A là ma trận cấp m × n của hệ ai và b ∈ Rm .
Vì một đẳng thức tuyến tính có thể biểu diễn thành hai bất đẳng
thức , một khối đa diện cũng là tập nghiệm của một hệ của đẳng thức
và bất đẳng thức tuyến tính có dạng :

18


Khóa luận tốt nghiệp Đại học

NGUYỄN THỊ KIỀU TRANG

ai , x = bi , i = 1, ..., m1 .
ai , x ≤ bi , i = m1 + 1, ..., m.
Hạng của hệ của các bất đẳng thức tuyến tính dạng (4.2) là định
nghĩa hạng của ma trận A. Khi đó nó bằng số của bất đẳng thức,ta nói
rằng bất đẳng thức này là độc lập tuyến tính.
Định lý 4.1. (Xem [1, Proposition 1.24. P.30])
Khối đa diện D = ∅ định nghĩa bởi hệ (4.2) có số chiều r nếu và
chỉ nếu hệ con của (4.2) hình thành bởi bất đẳng thức mà thỏa mãn như
đẳng thức bởi tất cả điểm của D có hạng n − r.
Hệ quả 4.1. (Xem [1, Corollary 1.16. P.31])Khối đa diện (4.2) là đủ
chiều nếu và chỉ nếu x0 thỏa mãn ai , x0 ≤ bi , ∀i = 1, ..., m.

4.1

Mặt của khối đa diện

Như trên, ký hiệu bởi D khối đa diện (4.2) và cho:
I0 = {i | ai , x = bi , ∀x ∈ D}.

4.2

Đỉnh và cạnh của khối đa diện

Một điểm cực trị (mặt 0-chiều) của một khối đa diện được gọi là một
đỉnh và mặt 1-chiều được gọi là một cạnh.
Hệ quả 4.2. (Xem [1, Corollary 1.17. P.33])
(i) Một điểm x ∈ D là một đỉnh nếu và chỉ nếu nó thỏa mãn như một
đẳng thức của n bất đẳng thức độc lập tuyến tính từ (4.1).
(ii) Một đường thẳng (hoặc nửa đường hoặc đường) Γ ⊂ D là một cạnh
của D nếu và chỉ nếu nó là một tập điểm của D thỏa mãn như đẳng
thức (n − 1) bất đẳng thức độc lập tuyến tính từ (4.1).
Định lý 4.4. (Xem [1, Theorem 1.9. P.33]) Cho x0 là một đỉnh không
suy biến của khối đa diện đủ chiều D định nghĩa bởi hệ (4.2).
20


Khóa luận tốt nghiệp Đại học

NGUYỄN THỊ KIỀU TRANG

Khi đó, nó là đúng n cạnh của D bắt nguồn từ x0 .
Nếu I là tập của các chỉ số của bất đẳng thức thỏa mãn bởi x0 như
đẳng thức thì ∀k ∈ I một cạnh xuất phát từ x0 theo hướng z là định
nghĩa bởi hệ:
ak , z = −1, ai , z = 0, i ∈ I \ {k}.

(4.5)

Một khối đa diện liên kết với nhau được gọi là một hình đa diện.