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

BÙI THỊ NGOAN

MỘT SỐ TẬP LỒI ĐẶC BIỆT VÀ ỨNG DỤNG

K HÓ A LU ẬN T ỐT N GHI ỆP Đ ẠI HỌ C
Chuyên ngành: Hình học

Người hướng dẫn khoa học T.s TRẦN VĂN NGHỊ

HÀ NỘI - 2015

Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lòng biết ơn sâu sắc tới

THS. TRẦN

V Ă N N G H Ị , người đã tận tình hướng dẫn để em có thể hoàn thành tốt khóa luận này.
Em cũng xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo khoa Toán, trường Dại học Sư phạm Hà Nội
2 đã dạy bảo em tận tình trong suốt quá trình học tập tại khoa.
Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, cổ vũ, dộng
viên, giúp đỡ em trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp.
Xin chân thành cảm ơn!


Hà Nội, ngày 05 tháng 5 năm 2015.
Sinh viên

Bùi Thị Ngoan

LỜI CẢM


để làm đề tài khóa luận tốt nghiệp.

2. Mục đích nghiên cứu
•

Tìm hiểu sâu hơn các kiến thức về tập lồi.

•

Làm rõ tính chất của các tập lồi đặc biệt.

•

ứng dụng tính lồi vào một số bài toán cực trị.

3. Đối tượng và phạm vi nghiên cứu
•

Dối tượng nghiên cứu: Kiến thức về tập lồi.

•

Phạm vi nghiên cứu: Một số tập lồi đặc biệt và ứng dụng.

4. Nhiệm vụ nghiên cứu
•

Trình bày c,ơ sở lý thuyết về tập lồi.


A C X

được gọi là

LỒI,

nếu

VXX, X2 ẽ /4, VA (E K : 0 ^ A 5^ 1 =7’" À £ 1 -b (1 —

XỴx2

ẽ

Á.

Chú ý. Theo định nghĩa trên, tập 0 được xem là tập lồi.
Giả sử

A

c

X; X1,X2

Định nghĩa 1.2.

€

A.

1.1. Giả sử

Khi đó, tập

A

A

=n

A

A

A

c

X

(tt 6

I)

là các tập lồi, với / là tập

lồi...

chỉ số bất



lồi, cho


\XỊ
A.

Suy ra Axi + (1 — A)a ?2 £

+ (1 — A)X'2 €

A

(VA € [0,1]).

A

Từ Định nghĩa 1.1 ta nhận được các mệnh đề sau:
Mệnh đề 1.2. Giả sử tập

AI C X

(I

lồi, Àj G R.

= 1,..., ra). Khi đó,

A1.41 + ...
+ \mAm

là các không gian tuyến tính,

T

lồi

X ... X

(I

X .
M

X —> Y

:

= 1,...,

là toán tử

tuyến tính. Khi đó,
a) Nếu A c X lồi, thì
b)

T ( A ) lồi;
Nếu B c Y lồi, thì nghịch ảnh T ~ ( B )
L

Định nghĩa 1.3. Vectơ

= 1, . . . , r a ) ,

^2

của các vectơ
m

= 1 , s ao c h o

X

= ^ AjX ị .

¿=1
Định lý 1.1. Giả sử tập

A

c

X

lồi;

xi,...,xm

€

A.



ta sẽ chứng minh rằng:

k +1
1), x i =
I= 1
X — AjXi + • • • + AfcXjfc + X K + I X K + I € A .
Vxi,...

Có thể xem như

,xk+i e A, y Xi > 0(i = ỉ,... ,k +

\K+I
0;



Y

A

€

và
1

xk
"X H G

+•••+

Á.

1-A f c+1

X K +1 G Ẩ, ta có
—

^ K +1 > 0, (1 — A f c+1 ) + Afc + 1 = 1.

Do đó,

X

= (1 —



của tập

A

A

và ký hiệu là

nhỏnhất

được gọi là

COA.

chứa

A;

CO A.

=

trùng với tập tất cả các tố hợp lồi của

A.

Chứng minh.
Theo Nhận xét 1.2,


chứa tất cả

A.

chứa tất cả các tổ liỢp lồi của

Giao của tất cả các

BAO LỒI ĐÓNG
Nhận xét 1.3.

COA.

A.

là không gian lồi địa phương.

Định nghĩa 1.5. Giả sử
gọi là

A

là lồi khi và chỉ khi

X

c

(Định lý 1.1).



INTA

a) Phần trong

X1

b) Nếu

€

A

c

X

lồi. Khi đó,

INTA,X2€ A
[ X U X 2)

Nói riêng, nếu

A

và bao đóng

là các tập lồi;


6

INTA,X2€ A.

U của X Ị

Khi đó, tồn tại lân cận

Ư
Đặt

X = ẰXI

+ (1 — A)x 2 , (0 < A < 0), ta có

c

XU +

và

XU

+ (1 —

Bây giờ lấy
Giả sử
Dü

XỊ

X

INTA

= AjiCi + (1 — A)x 2 ,

lồi.

(0 < A


=

coA.

cho

A.

(1—

lân

sao

A,

tức

là

một


Chương 2

MỘT SỐ TẬP LỒI ĐẶC BIỆT

••••


tùy ý thì

Điểm

OM

=

M

thuộc

XOP +

¡1 = 1

với A +

hay là

ÕM
Tập hợp những điểm
được gọi là

M

sao cho

P = Q , đoạn thẳng P Q



0)

=

PQ gồm

điểm

P.

P (khi

A

=

1)

và

ọ

(khi

A

=

điểm ứng với A (0 < A < 1).


P(). PỊ, , P .

Ta biết rằng m-phẳng

M

O

M

sao cho (với điểm

M-ĐƠN HÌNH

A

đi qua

M +

nào đó)

với các

Đ Ỉ N H : P ( Ị , P I ,..., P

M

Ta chứng minh rằng, m-đơn hình là tập lồi bé nhất chứa các đỉnh của đơn hình. Rõ ràng


Õx = tÕM + (1 - t)ÕN
hay

OX

—

[ T X Ị + (1 — í)/ij]OPj.

i—Q

^ 2 [ X I + (! - *)/'•*] = \ Ị + ( Ì - T ) ^ 2
Ị I Ị I =0 ¿=0 ¿=0 — T \ — T = 1
và T X Ị + (1 — T ) N I > 0 vì Àj > 0, H I > 0,1 — T >
Rõ ràng

T

Vậy điểm
đỉnh

X

S(P0

thuộc đơn hình. Tóm lại đơn hình

Ì



s

chứa một đơn hình

S ( P q , P ị , ..., P k ) ,

0

Àj
Đăt OJV = /
— O P Ị thì vì / — và — > 0
A
^ A
A

2=0
X- n / T~t T~i
cho nên N € S ( P ( ) ,

z=o

___
ATsnỉ
Pi,..., P ) quy ra N E S ' .

AT

Khi đó, OM

M

Vậy

\

K

— XON + Ằk+iO Pk+1 với A + Xk+1 = 1 và A > 0, Afc+1 >


c 5".

N

P\,... , P

M

và

0, bởi vậy

chứa Pjfc+1 nên M

€

đều chứa m-đơn hình

S ( P 0 , Pi ,..., P m ) . Nói cá ch k há c, đơn hì nh S ( P ( ) , P ị , . . . , P m ) là tập l ồi
bé nhấ t
chứa các đỉnh của nó.

2.3 Hộp
Cho

M

+ 1 điểm độc lập P 0 ,


Hi

2.4.1

Tập affine
Định nghĩa 2.2. Tập

A

c M” được gọi là

A F F I N E , nếu ( 1 — X ) X + X Y

Ễ

A

, Vx,

TẬP

Y

6

A,

VA G M.

A

Nhận xét 2.1. Nếu


Ữ

G

L\

=r*

LỊ

Z) i/j -I-

0- = L 2-


Tương tự, ta nhận được

L2 D LỊ.

LỊ

Do đó,

=

L2.

Như vậy, tính duy nhất được



Y

Vậy

A — Y

tùy ý, cho nên

L

=

là không gian

A — A.

Từ Dịnh lv 2.1 ta có thể định nghĩa được chiều của một tập affine.
Định nghĩa 2.4. Chiều của một tập affine không rỗng được định nghĩa là chiều của
không gian con song song với Ĩ 1Ó.
Chú ý. Ta quy ước
Giả sử

L

DIRNỰÌ

= — 1.

là một không gian con trong


M" :
=

{x

0} =

+ a :< x,b
{y e

R B :
= 0}
y, b > = ß }.

X


Định lý 2.3. Giả sử

B

M

là

N-


A

trong R" là giao của một số hữu hạn các siêu phẳng.

Bao affine

A C

Định nghĩa 2.6. Giao của tất cả các tập affine chứa tập

được gọi là

bao

affine (affine hull) của A. và ký hiệu là ữffA.
Nhận xét 2.2.

AFF A
X

là tập affine nhỏ nhất chứa

A.

T Ổ H Ợ P A F F I N E của các điểm
m
X Ị , . . . , X € M , nếu 3A 1? ..., A m € M, Aj = 1 sao cho X = 2 ^ ^ I I i=l
¿=1
Nhận xét 2.3. A F F A trùng với tập tất cả các tố hợp affine các điểm của Ả
Định nghĩa 2.7. Điểm


của

X.

R m được gọi là

A F F I N E , nếu với

M

—


T(( 1 - A)x + Ay) = (1 - A)Tx + ATy.
Nhận xét 2.6. Nếu ánh xạ T : R n —> M m là affine, là tập affine trong M" thì

TA

là tập

m

affine trong R .


T\X + A,

trong đó

Ì

— B0

— B[Y

N

A

N

=

B'()

—

TỊB0,

ta nhận được

T

là ánh xạ



là ánh xạ tuyến tính,

A

6 Mm.

Chứng minh.
a) Nến

T

là affine, thì ta lấy

A — TO

và

TYX — TX —
T Y là ánh

nhận được
affine với

TỊO

Vậy

T


+ X T\IJ + u

= (1 —

X ) T X + X Ty.


K +

Định nghĩa 2.10. Bao lồi của

ĐƠN

là

B I ,..., B
Định

lý

HÌNH

K-CHIỀU

2.6.

Giả

B(F,BỊ,... ,B .


đơn

hình

n-chiều

Rn

trong

với

các

đỉnh

INTS Ỷ $■

CHIỀU CỦA TẬP LỒI A

là chiều của

UF F A.

Chú ý. Bởi vì một đơn hình là một tập lồi, cho nên có thể xét chiều của các đơn hình
theo Định nghĩa 2.11.
Định lý 2.7. Giả sử
hình trong

A

là số

R R I lớn Iihất sao cho Ả chứa một tập M + 1 điểm độc lập affine, chẳng hạn
1 BỊ 5 • • • 5 BM } •
Đặt M — a f f ị b ị ) . b ị , , b m } . Khi đó, d i m M — m và M c a f f A .
Mặt khác, A c M , bởi vì nếu 3 B 6 A \ M thì tập M + 2 phần tử { B 0 ,
{^0

B I , ..., B ,
M

Suy l'a

A

Dẫn đến
Do đó

c

0} c

M

c

A

lập


c

X

được gọi là
Ax G

/í được gọi là nón có đỉnh tại
2.5.2

Nón lồi

X0,

K,

nếu

K

NÓN
V.X e

có đỉnh tại ơ, nếu

K,

VA > 0.

— Xo là nón có đĩnh tại

Ví dụ 2.1. Các tập sau đây trong R” :
{( 0, I =

1,...

,77,}

(orthant

không âm);
e

{(Cl* - • - » £n)

:

ÍI

1,..., n} (orthant

> 0, ¿ =

dương)


Ví dụ 2.2.

= EN , B A

X

là một nón lồi bởi vì

K

E

(A E

Kn

K = { x € R n :< x , b a >

X,B

1}

>< 0}

A

là nón lồi.
Định lý 2.8. Tập

K C X

là một nón lồi có đỉnh tại

X + y

€

K, \x G K,

Vx,

O

khi và chỉ khi

y £ K,v

A > 0.

XX

6

K,

ta có (1 —

\)X

G

K, XY

X + y
ii) Ngược lại, với Vx 6
Với 0 < À < 1,

K.YX >

X, Y

€

K

K.
vậy

K


là nón lồi

O.

Hệ quả 2.3. Tập

K

X

c

là nón lồi khi và chỉ khi

K,

dương của các phần tử của

K

X\., X

tức là nếu

M

chứa tất cả các tổ hợp tuyến tính
G



là tập chứa tất cả các tố hợp tuyến tính

là nón lồi Iihỏ nhất chứa

A.

Chứng minh.

K
Ta có

là nón lồi có đỉnh tại o, bởi vì

K D A.

K

đóng đối với phép cộng và phép nhân vô hướng.

Hơn nữa, mọi nón lồi chứa

A

thì phải chứa

Định nghĩa 2.14. Giao của tất cả các nón lồi (có đỉnh tại
một nón lồi và được gọi là

O)


=

C O

của tập
A

A,

ký hiệu là

A

được gọi

HNA.

\

là tập lồi thì

KA

IJ

XA {X

ç



A.

Khi đó,

mỗi

điểm X Ỷ 0 thuộc K A có thể biểu diễn dưới dạng
X
t r o n g đ ó A j > 0,
Nói

Xị

€

A (i =

=

Ai^i “h • • • "I“

1,...,

riêng, r < n.

Định lý 2.10. (Định lý Carathéodory)

r),


{(l,x)

: X £

coB

= {1} X

coA.

D.

Khi đó,

B = {1} X A =

A}

c R X

R".

Ta có

Giả sử

KSS

là nón lồi sinh bởi


€

X*

PHÁP TUYẾN
X £ A,

được gọi là

< X*, X — X

>< 0

Tập tất cả các vectơ pháp tuyến của tập lồi

PHÁP TUYẾN
Như vậy,

là không gian các phiếm hàm tuyến tính

của

A

tại

X,

A


A

2.7. Nón pháp tuyến của tập lồi

tại

X >

A

D

lùi xa theo phương

Iiếu

A

thẳng xuất phát từ các điểm của

A

và theo phương

Định nghĩa 2.18. Tập các vectơ

D

€

X

(2.2)

o.yx e A).
chứa

tất


A,

ký hiệu là 0 + Ấ.
A

lồi, khác 0. Khi đó, 0 +

là nón lồi chứa điểm

o,

đồng thời,
0+A = {d. e X

:

Ả

+

d

c

A).

(2.3)

Chứng minh.

+

A ), tức là
A + d

c

A.

Suy ra
1
Ngưực lại, lấy

Á
=>

(1

-Ị- 2 D =

X + MD

€

(Á
€

X

+

Do

A

đoạn thẳng

nối

X , X + D , X + 2d,.. . nằm

các điểm

trong

A.

Vì

vậy,
X + Xd G A

(VA >0)

=^íle 0 + Ẩ.
Suy ra
{d e X : A + d

c

A)

A

1. Do

A

X)A + XA = Ả

lồi.

là nón lồi.

Ví dụ 2.3. X = K 2 .
a)

c 1 = {{x,y) : X > 0,y > -}.
X

{(X,Y) : X > 0,Y

+

Khi đó 0 Ci =
b)
Khi đó

c)

c2 = {{x,y) : y > X2}.


Khi dó 0 + Ơ4 = ơ 4 .

>

{( 0, 0) } .

0} u {(0,0)}.

là một nón.

lồi nên ta có

A) + \{d2

G 0 + v4.

0+ A

+ A).


2.8 Phần trong tương đối
P H Ầ N T R O N G T Ư Ơ N G Đ Ố I ( R E L AT I V E

Định nghĩa 2.19.

INTERIOR)
là

của tập

i n t A — { x € M” : 3e > 0, X + e B
r i A — { x € a f f A : 3 e > 0,
affA
c
B

c

A}\
(x
Ẩ}.

đó

Định

nghĩa2.20. Tập

A \ RIA

được gọi là

mở tương đối (relatively open),

A

eB)

n


nếu

A.

ĐỐI

của

riA — A.

Khi đó,

(0 < A < 1).

Chứng minh.
Giả sử
2 —1

T :

A

là tập lồi TO-chiều trong R'\ Theo Hệ quả 2.2, tồn tại ánh xạ affine

K n —> M n sao cho

L {x [ x I ) . . .
Không gian con

L


cần chứng minh cho trường hợp

trong đó

ánh xạ

là n-chiều. Khi đó,

€ >

RIA

=

lý ta chỉ

INTA.

0 sao cho

X)X

+

XY

+

EB

ta có

G
với


(1 —

\)X

+A Y + E . B

—
—

EB)

(1 —

X)[x

+ € ( 1 + A )( l

1

B]

+

XA = A.


a f f {ri A) = a f f A.
Hệ quả 2.6. Giả sử

A

là tập lồi trong IR". Khi đó,

a f f (ri A ) = a f f (A).
Hệ quả 2.7. Giả sử

A

là tập lồi trong M”. Khi đó,

dim A — dim (ri A) — dim A.
Nói riêng, nếu A Ỷ 0 thì R I A Ỷ 0Định lý 2.16. Giả sử A là tập lồi trong K n . Khi dó,
riA

=

A\ riA

=

riA.

(2.6)

Chứng minh.



Hệ quả 2.8. Giả sử

AỊ, A2

là các tập lồi trong E". Khi đó,
A\

= Ả ‘2 <í=>

rỉ Ai

=

riA2-

2.9 Tập lồi đa diện
Một tập lồi đa diện trong R” là một tập được biểu diễn bằng giao của hữu hạn các
Iiửa không gian đóng, nghĩa là tập nghiệm của một hệ hữu hạn các bất phương trình có
dạng

< BỊ, I


7 < 0

x2

+

— x3 — 1

là không gian lồi địa phương,

Định nghĩa 2.21.

EPIF.

: ữ Ru {±oc}.

TRÊN DÒ THỊ (EPIGRAPH)

của hàm /, ký hiệu là

được định nghĩa như sail

EPIF —
Định

D C X, F

nghĩa

DOMAIN)

2.22.

{(x,r) 6

MIỀN


EPIF

là tập lồi trong

( C O N C AV E O N D ) ,
Nhận xét 2.10. Nếu / lồi thì

trên X, trong đó

X*

(VX

D ).

G

LỒI TRÊN D (CONVEX ON D),
X R. Hàm / được gọi là

nếu —/ là hàm lồi trên

DOMF

F(X)

Ví dụ 2.5. Hàm affine

X


( IN DI C ATO R FU N C T I ON )

X.
Ổ(.|Ấ) của tập

\ 0 nếu X € A ,
ỗ{.\A)=\
]
+OC nếu X ặ A .
X*

Ví dụ 2.7. Giả sử
lồi

A

c

X*

là không gian liên hợp của

-s(.|v4) của tập

là hàm lồi
s(.|j4) = sup


AF ( X )

+

Định lý 2.19. Giả sử / là hàm lồi trên

X,

F(X) < Ụ,}


.

F

{X : F(X)
A

là hàm lồi trên

(1 - A ) F ( Y ) (VA G [0,1 ],Vx,ỉ/ €
//• € [— 00, + 00]. Khi đó, các

FI}

được gọi là

THUẦN NHẤT

DƯƠNG (POSI TIVELY HOMOGENEOUS)I
(0, +oc),

F(XX)

=A

F(X).

nếu Vx Ễ ỊV A e