ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM

NGUYỄN TRẦN THÀNH

MỘT VÀI ỨNG DỤNG CỦA ĐỊNH LÝ TÁCH
TRONG TỐI ƢU HÓA

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2015
Số hóa bởi Trung tâm Học liệu – ĐHTN




ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM

NGUYỄN TRẦN THÀNH

MỘT VÀI ỨNG DỤNG CỦA ĐỊNH LÝ TÁCH
TRONG TỐI ƢU HÓA
Chuyên ngành: Toán Giải tích
Mã số: 60.46.01.02

LUẬN VĂN THẠC SĨ TOÁN HỌC

Ngƣời hƣớng dẫn: GS. TSKH. LÊ DŨNG MƢU

THÁI NGUYÊN - 2015

trong lớp Cao học Toán K21, đã chia sẻ động viên và giúp đỡ tôi trong quá
trình học tập và làm luận văn.
Tôi cũng vô cùng biết ơn Bố, mẹ, anh, chị, em trong gia đình của mình
đã cảm thông chia sẻ cùng tôi trong hơn một năm qua để tôi có thể học tập và
hoàn thành luận văn này.
Do thời gian ngắn và khối lượng kiến thức lớn nên bản luận văn sẽ khó
tránh khỏi những thiếu sót, tôi rất mong nhận được sự chỉ bảo tận tình của các
thầy cô và bạn bè, tôi xin chân thành cảm ơn!

Số hóa bởi Trung tâm Học liệu – ĐHTN




iii

MỤC LỤC
LỜI CAM ĐOAN ................................................................................................. i
LỜI CẢM ƠN ...................................................................................................... ii
MỤC LỤC .......................................................................................................... iii
BẢNG KÝ HIỆU ................................................................................................ iv
DANH MỤC CÁC HÌNH ................................................................................... v
MỞ ĐẦU ............................................................................................................. 1
1. Lý do chọn luận văn .................................................................................. 1
2. Mục đích nghiên cứu ................................................................................. 1
3. Nhiệm vụ nghiên cứu ................................................................................ 1
4. Bố cục của luận văn ................................................................................... 1
Chƣơng 1. ĐỊNH LÝ TÁCH CÁC TẬP LỒI ................................................. 2
1.1. Tập lồi ..................................................................................................... 2
1.2. Định lý tách các tập lồi ......................................................................... 17

<x,y> xT y

Tích vô hướng cả hai véc-tơ x và y;

x

Chuẩn Euclide của x;

[x,y]

Đoạn thẳng đóng nối x và y;

(x,y)

Đoạn thẳng mở nối x và y;

C
coC

Bao đóng của C;

coneC

Nón sinh bởi tập C;

aff(C)

Bao affine của tập C;

riC


Đạo hàm của f tại x;

NC ( x* )

Hình nón pháp tuyến của C tại x* ;

N C ( x)

Nón pháp tuyến ngoài của C tại x ;

- N C ( x)

Nón pháp tuyến trong của C tại x ;

FC ( x)

Nón các hướng chấp nhận được;

TC ( x)

Nón tiếp xúc của C tại x;

dC ( y )

Là khoảng cách từ y đến C;

C ( x* )

Tập hợp các hướng chấp nhận được của C tại x*

Trong tối ưu hóa thì các Định lý tách đóng một vai trò hết sức quan
trọng, nhờ Định lý tách mà ta có thể chứng minh được định lý Karush-KuhnTucker, định lý Kuhn-Tucker đây là hai định lý quan trọng dùng để giải quyết
các bài toán trong tối ưu. Ngoài ra các Định lý tách còn có nhiều ứng dụng
khác trong Giải tích toán học. Chính vì thế mà tôi chọn đề tài “ Một vài ứng
dụng của định lý tách trong tối ưu hóa”
2. Mục đích nghiên cứu
Mục đích của luận văn này là trình bày một vài ứng dụng của Định lý
tách trong tối ưu hóa.
3. Nhiệm vụ nghiên cứu
Luận văn tập trung vào các nhiệm vụ sau đây:
Tổng hợp lại một số kiến thức cơ bản của Giải tích lồi, một số tính chất
của tập lồi, hàm lồi và các phép toán liên quan.
Trình bày các Định lý tách và các ứng dụng của các Định lý này trong tối
ưu hóa.
4. Bố cục của luận văn
Ngoài phần mở đầu, phần kết luận và tài liệu tham khảo, luận văn được
trình bày trong hai chương.
Chương 1: Tổng hợp các kiến thức về tập lồi, hàm lồi, các tính chất của
chúng, phát biểu và chứng minh Định lý tách.
Chương 2: Trình bày một vài ứng dụng của Định lý tách trong tối ưu
hóa, đó là sử dụng Định lý tách để chứng minh Định lý Karush-Kuhn-Tucker,

Số hóa bởi Trung tâm Học liệu – ĐHTN




2
Định lý Kuhn-Tucker, Định lý đối ngẫu Lagrange. Ngoài ra xét đến áp dụng
Định lý tách trong kỹ thuật vô hướng hóa của bài toán tối ưu đa mục tiêu.


0,

1 .

Tập lồi là một khái niệm cơ bản nhất của Giải tích lồi, nó được định
nghĩa như sau:
1.1.1. Định nghĩa. Một tập C

 n được gọi là một tập lồi, nếu C chứa mọi

đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi

x,y C,

0,1

x (1

)y C

ta nói x là tổ hợp lồi của các điểm (véc-tơ) x1, x2 ,..., xk nếu
k

k
j

x

j


x ,

j

j 1

1.

j 1

Tập hợp của các tổ hợp a-phin của x1, x2 ,..., xk thường được gọi là bao aphin của các điểm này.
Ví dụ
1. Trong  2 thì các đa giác lồi, hình tròn, hình elíp…là các tập lồi.
2. Trong  3 thì các đa diện, hình cầu,… là các tập lồi.
1.1.2. Định nghĩa. Nửa không gian là một tập hợp có dạng
x aT x

,

trong đó a 0 và

.

Đây là nửa không gian đóng. Tập
x aT x

,

là nửa không gian mở.




4
(1

)x

y

a (1

)( x a )

( y a) .

Do x a và y a đều thuộc L và do L là không gian con, nên
(1

( y a) L .

)( x a )

Vậy
(1

y M.

)x



L a a'

L.



1.1.4. Định nghĩa. Một tập được gọi là tập lồi đa diện, nếu nó là giao của một
số hữu hạn các nửa không gian đóng.
Như vậy, theo định nghĩa, tập lồi đa diện là tập hợp nghiệm của một hệ
hữu hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi đa
diện được cho như sau:
D:

x n

a j,x

b j , j 1,..., m .

Hoặc nếu ta ký hiệu A là ma trận có m hàng và các véc-tơ

a j ( j 1,..., m) và các véc-tơ bT
D:

(b1,..., bm ) thì hệ trên viết được là:

x  n Ax b .

Do một phương trình

x  x

0

là một nón nhưng không lồi.
1.1.6. Định nghĩa. Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi.
Một nón lồi được gọi là nón nhọn nếu nó không chứa đường thẳng. Khi
đó ta nói O là đỉnh của nón. Nếu nón lồi này lại là một tập lồi đa diện thì ta nói
nó là nón lồi đa diện. Một ví dụ điển hình của nón lồi đa diện, thường được sử
dụng, là tập hợp nghiệm của hệ bất phương trình tuyến tính có dạng:
x Ax

0 ,

với A là một ma trận thực cấp hữu hạn (số dòng và số cột là hữu hạn).
Ví dụ Tập  n :

x  n : x 0 là một nón lồi.

1.1.7. Mệnh đề. Một tập C là nón lồi khi và chỉ khi nó có các tính chất sau:
(i) C

0,

C,

(ii) C C

C.




Một số nón điển hình. Dưới đây ta sẽ xét một số nón lồi điển hình
thường được sử dụng trong giải tích lồi.
Tập lồi có một đặc trưng là: một tia xuất phát từ một điểm thuộc nó,
thì hoặc nằm hẳn trong tập này hoặc một khi đã ra khỏi tập này thì sẽ
không “trở lại”.
Cho C là một tập lồi trong  n . Mặt khác véc-tơ y

0 được gọi là hướng

lùi xa của C, nếu một tia xuất phát từ một điểm bất kỳ của C theo hướng y đều
nằm trọn trong C, tức là y là hướng lùi xa khi và chỉ khi
x

y C,

0.

Một hướng lùi xa còn được gọi là hướng vô hạn. Ta sẽ ký hiệu tập hợp
của tất cả các hướng lùi xa của C cùng với điểm gốc là reC. Tập hợp này được
gọi là nón lùi xa của C. Hiển nhiên nếu C là một tập bị chặn, thì reC chỉ gồm
duy nhất điểm gốc. Chú ý rằng, nếu C là một tập lồi đóng, thì trong định nghĩa
trên, thay vì đòi hỏi với mọi x C , chỉ cần đòi hỏi cho một điểm x C . Cụ thể
ta có mệnh đề sau:
1.1.8. Mệnh đề. Giả sử C là một tập lồi đóng. Khi đó y là một hướng lùi xa của
C khi và chỉ khi
x

y C,

)u C .

y C , với mọi u C và

0.



Chú ý: Trong C không đóng mệnh đề trên không đúng.
Ví dụ Trong  2 lấy
C:

x ( x1 , x2 ) x1

0, x2

Hiển nhiên véc-tơ y
0

0

0 .

(0,1) có tính chất là mọi tia xuất phát từ một điểm

x C theo hướng này đều nằm trọn trong C, nếu xuất phát từ x 0 thì điều

này không đúng.
Cho C



w, x

0, x C .

Dễ thấy rằng đây cũng là một nón lồi đóng chứa gốc.
Cho C là một tập lồi khác rỗng và x C . Ta nói d
chấp nhận được của C nếu tồn tại t0

 n là một hướng

0 sao cho x td C với mọi 0 t t0 .

Tập tất cả các hướng chấp nhận được là một nón lồi (dễ kiểm tra) chứa gốc. Ta
sẽ ký hiệu nón này là FC ( x) và sẽ gọi là nón các hướng chấp nhận được hoặc
nói ngắn gọn là nón chấp nhận được. Nón này có thể không đóng, tuy nhiên
Số hóa bởi Trung tâm Học liệu – ĐHTN




8
nếu lấy bao đóng, ta sẽ được một nón khác gọi là nón tiếp xúc của C tại x. Ký
hiệu nón này là TC ( x) , thì FC ( x) TC ( x) . Từ đây suy ra
TC ( x)

 n dk

d


a j, y

N C ( x) cone(a j , j

J ( x) ,

0, j

J ( x))

y

j

aj :

j

0 .

j J ( x)

1.1.10. Tính chất của các tập lồi
Nếu A, B là các tập lồi trong  n , C là lồi trong  m , thì các tập sau là lồi:
(i) A
(ii)

B:
A


tập lồi có tính chất là:
Số hóa bởi Trung tâm Học liệu – ĐHTN




9

x, y C : tx (1 t ) y F ,0 t 1

x, y

F.

Điều này có nghĩa rằng, tập lồi F là một diện của C, nếu như khi F chứa
một điểm của đoạn mở (x,y) thì F chứa toàn bộ khoảng [x,y]. Do C lồi, nên bản
thân C cũng là một diện của chính nó. Ta sẽ nói F là một diện không tầm
thường của C nếu như F

và F

C.

Điểm cực biên là diện có thứ nguyên bằng 0. Cạnh là diện có thứ nguyên
bằng 1. Tia cực biên là một diện nửa đường thẳng. Như vậy tia cực biên là một
cạnh vô hạn. Hướng cực biên là hướng của tia cực biên. Ta nói hướng d và h là
khác nhau nếu không thể biểu diễn được d

h với





10
1.1.13. Định nghĩa. Cho x0 C . Ta nói aT x

aT x

, aT x

là siêu phẳng tựa của C tại x 0 , nếu

x C.

Như vậy siêu phẳng tựa của C tại x 0 là siêu phẳng đi qua x 0 và để tập C
về một phía. Nửa không gian aT x

trong định nghĩa trên, được gọi là nửa

không gian tựa của C tại x 0 .
1.1.14. Mệnh đề. Nếu H là một siêu phẳng tựa của C thì H
của C; diện này là không gian tầm thường khi và chỉ khi H
Chứng minh. Gọi F

C

C là một diện

riC



) t,b .

Do a, b C nên
t, x

t, b

.

, t,b

.

,

Từ đây suy ra
t, a

Như vậy a, b F và do F lồi, nên cả đoạn [a, b]

F . Do đó F là một diện.

Việc chứng minh rằng F không tầm thường khi và chỉ khi H

,

riC

chỉ cần sử dụng trực tiếp định nghĩa.


C là một

diện của C và dimF < dimC. Hiển nhiên F là tập lồi, đóng và không chứa
đường thẳng. Theo giả thiết qui nạp, F có điểm cực biên. Vì F là một diện của
C, nên điểm cực biên của F cũng là điểm cực biên của C.



1.1.16. Định lý. (Biểu diễn tập lồi). Nếu C là một tập lồi đóng không chứa trọn
một đường thẳng nào thì
coV (C ) coneU (C ) .

C

Tức là mọi điểm của C đều biểu diễn được như là tổng của một tổ hợp
lồi của các điểm cực biên và tổ hợp không âm của các hướng cực biên của C.
Chứng minh. Ta chứng minh bằng qui nạp theo số chiều. Hiển nhiên định lý
đúng khi số chiều của C là 0 và 1. Giả sử x C bất kỳ. xét tia

:

y

Vậy v

x
x

u,



12
u với

Do u U ( F ) và x v
x v

0 , nên từ đây suy ra

u coV (C ) coneU (C ) coneU (C )
coV (C ) coneU (C ) .

b) Trường hợp u U (C ) (chú ý U(C) có thể bằng rỗng). Trong trường
hợp này tia

có thể cắt biên của C tại hai điểm, nhưng định lý cũng được

chứng minh hoàn toàn tương tự.
1.1.17. Định nghĩa. Cho C
dC ( y ) :

inf

x



(không nhất thiết lồi) và y là một véc-tơ bất kỳ, đặt


cực tiểu của hàm toàn phương x
Như thường lệ, sẽ ký hiệu

y

2

trên C.

pC ( y) , hoặc đơn giản hơn là p ( y ) nếu

không cần nhấn mạnh đến tập chiếu C. Chú ý rằng, nếu C
hạn, vì 0 dC ( y)
Cho C

, thì dC ( y ) hữu

y x với mọi x C .

 n , x0

C . Nhớ lại là nón pháp tuyến (ngoài) của tập C tại x 0

là tập hợp
NC ( x 0 ) :

w wT ( x x0 ) 0 x C

Số hóa bởi Trung tâm Học liệu – ĐHTN



pC ( y) y, x

pC ( y)

0, x C ,

pC ( y) y, y

pC ( y)

0.

và

(iv) Ánh xạ y
a) pC ( x)
b)

pC ( y) có các tính chất sau:

pC ( y)

pC ( x)

pC ( y), x

x

y


C . Hơn nữa do

là hình chiếu của y, nên

y x . Hay

y

y

2

(x

2

y) .

) (

Khai triển vế phải, ước lược và chia hai vế cho
2

x

2 x

,



) (y

2

y

y

y

)

)T ( x

(y

y).

Từ đây và b), dùng bất đẳng thức Cauchy-Shwarz ta có:
2

y

)T ( y x)

(y

Suy ra y


Vậy dãy x k
điểm

C sao cho

bị chặn, do đó nó có một dãy con x

nào đó. Do C đóng, nên

y
Chứng tỏ

lim x
j

kj

y

lim x k
k

kj

hội tụ đến một

C . Vậy

y


y,

0

và
1

1

y,

0.

Cộng hai bất đẳng thức này ta suy ra
(iii) Do y

0 , và do đó

1

.

NC ( ) , nên

y, y

y

2



và

Cộng hai bất đẳng thức lại sẽ được
p( y )

p( x), p( y )

p( x)

x

y

0.

Từ đây theo bất đẳng thức Cauchy-Schwarz, suy ra

p ( x)

p( y )

x

y .

Để chứng minh tính đồng bức, áp dụng tính chất b) của (i), lần lượt với
p ( x) và p ( y ) , ta có:
p ( x ) x, p ( x )



0.

Chuyển vế ta có

p ( x)

p( y), x

y

p ( x)

2

p( y ) .

Đây chính là công thức cần được chứng minh.



1.1.19. Mệnh đề. Cho C là một tập lồi khác rỗng và x0

riC . Khi đó tồn tại

siêu phẳng tựa của C tại hình chiếu của x 0 trên C .
Chứng minh. Gọi hình chiếu của x 0 trên C là p( x0 ) .
Trước hết xét trường hợp int C

. Vậy x 0 int C . Phân biệt hai


x C.

Số hóa bởi Trung tâm Học liệu – ĐHTN




17
Bằng cách chuẩn hóa
k

0

ta có thể coi

k

1 , và do đó có thể giả sử

k

. Do ánh xạ chiếu liên tục, nên từ bất đẳng thức trên, qua giới hạn và

chú ý p( x0 )
0

x0 (vì x0 C ), ta có:
0


. Do C

C

sao

H , nên suy ra H là siêu phẳng tựa của

cả C và C .



1.2. Định lý tách các tập lồi
1.2.1. Định nghĩa. Cho hai tập hợp C và D khác rỗng, ta nói siêu phẳng
aT x

tách C và D nếu

aT x

aT y, x C, y D

Ta nói siêu phẳng aT x

aT x

x C

tách chặt C và D nếu


Số hóa bởi Trung tâm Học liệu – ĐHTN




18
+ Xét hai tập C

( x, y )  2 y

1
,x 0 , D
x

( x, y )  2 y

1
,x 0
x

thì siêu phẳng tách là trục hoành tách chặt nhưng không tách mạnh hai tập C và D.

Hình 1.2: Tách chặt nhưng không tách mạnh
1.2.2. Định lý. (Định lý tách 1). Cho C và D là hai tập lồi khác rỗng trong  n
sao cho C

D

. Khi đó có một siêu phẳng tách C và D.


. Theo bổ đề trên áp dụng với x 0

Số hóa bởi Trung tâm Học liệu – ĐHTN

0 , tồn tại véc-tơ