ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
DƯƠNG THỊ HOA
VỀ SỰ PHÁT TRIỂN CỦA ĐIỀU KIỆN TỐI ƯU
TRONG BÀI TOÁN QUY HOẠCH LỒI
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
DƯƠNG THỊ HOA
VỀ SỰ PHÁT TRIỂN CỦA ĐIỀU KIỆN TỐI ƯU
TRONG BÀI TOÁN QUY HOẠCH LỒI
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Toán ứng dụng
Mã số: 60.46.01.12
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS. TSKH. LÊ DŨNG MƯU
Thái Nguyên - 2017
i
Mục lục
Lời cảm ơn
ii
Bảng ký hiệu
1
Mở đầu
2
1 Các kiến thức chuẩn bị về giải tích lồi
1.1 Tập lồi . . . . . . . . . . . . . . . . . . .
1.1.1 Các định nghĩa cơ bản về tập lồi
1.1.2 Toán tử chiếu tập lồi . . . . . . .
1.2 Hàm lồi . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
3
12
17
2 Điều kiện tối ưu của bài toán quy họach lồi
2.1 Bài toán quy hoạch lồi . . . . . . . . . . . . . . . . . . .
2.2 Điều kiện cần và đủ tối ưu . . . . . . . . . . . . . . . . .
2.2.1 Điều kiện tối ưu theo nguyên lý Fermat của bài
toán tối ưu không ràng buộc hàm một biến khả vi
2.2.2 Điều kiện với ràng buộc hình học . . . . . . . . .
2.2.3 Điều kiện có ràng buộc đẳng thức và bất đẳng
thức . . . . . . . . . . . . . . . . . . . . . . . . .
23
23
24
Kết luận
56
Tài liệu tham khảo
57
24
33
37
ii
Lời cảm ơn
Trước khi trình bày nội dụng chính của bài luận văn, em xin bày tỏ
lời lòng biết ơn sâu sắc tới GS.TSKH. Lê Dũng Mưu người đã tận tình
hướng dẫn và giúp đỡ em trong suốt quá trình học tập và nghiên cứu
để em có thể hoàn thành luận văn này.
Em xin bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo trường
Đại học Khoa Học - Đại học Thái Nguyên đã giảng dạy và giúp đỡ em
hoàn thành khóa học.
Em xin chân thành cảm ơn Ban Giám hiệu, quý thầy cô giáo khoa
Toán - Tin trường Đại học Khoa Học - Đại học Thái Nguyên, gia đình
và bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện cho em về mọi
mặt trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp.
Để hoàn thành được khóa luận bản thân em đã cố gắng rất nhiều
nhưng Luận văn khó tránh khỏi những thiếu sót. Tác giả rất mong
muốn nhận được ý kiến đóng góp của quý thầy, cô và bạn đọc để luận
văn được hoàn thiện hơn. Xin trân trọng cảm ơn!
Thái Nguyên, ngày ... tháng ... năm 2017
Tác giả luận văn
DƯƠNG THỊ HOA
1
Bảng ký hiệu
R
Rn
B
B(0, 1)
Rm
+
∂f (x)
δC (.)
L(x, µ, ν)
f 0 (x), f 00 (x),
∇f
∇2 f
h., .i
∂f
trường số thực
không gian Euclide n-chiều
là hình cầu đơn vị mở trong Rn
hình cầu đơn vị, đóng tâm ở 0
orthant không âm của Rm
dưới vi phân của hàm lồi f tại x
hàm chỉ của tập C
hàm Lagrange
đạo hàm (bậc 1 và bậc 2) của hàm số f (x)
Gradient của hàm f
ma trận Hessian f
tích vô hướng trong Rn
dưới vi phân của hàm f
2
Mở đầu
Bài toán quy hoạch lồi là phần quang trọng của lý thuyết tối ưu.
Trong lý thuyết tối ưu, thì điều kiện tối ưu là rất quan trọng, nó nghiên
cứu tính chất nghiệm, đề suất phương pháp giải. Lý thuyết về bài toán
quy hoạch lồi đã được quan tâm nghiên cứu nhiều và từ lâu đã đạt
được nhiều kết quả quan trọng dựa trên các kết quả của Giải tích lồi
và tối ưu hóa. Về phương diện tính toán đã có khá nhiều phương pháp
hữu hiệu cho lớp toán này.
Trong quá trình học và tìm hiểu về điều kiện tối ưu trong bài toán
quy hoạch lồi ta thấy sự phát triển của bài toán rất phong phú và
nhiều vấn đề được nối tiếp rất khoa học và hay.
Mục đích của luận văn là tổng kết lại giai đoạn phát triển của điều
kiện tối ưu trong bài toán quy hoạch lồi và xét đến các ứng dụng của
chúng trong việc xây dựng phương pháp giải. Trên cơ sở đó khảo sát
đến một số ứng dụng trong việc giải bài toán quy hoạch lồi. Tổng hợp
lại lý thuyết tối ưu thì điều kiện tối ưu là rất quan trọng vì chúng cho
phép nghiên cứu tính chất nghiệm, xây dựng các phương pháp giải.
Điều kiện tối ưu được dựa trên nguyên lý Fermat trong bài toán cực
trị không có nghiệm ràng buộc của hàm một biến khả vi đã được học
trong chương trình PTTH. Theo đó người ta đã phát triển nguyên lí
này bài quy hoạch có ràng buộc của hàm nhiều biến không nhất thiết
khả vi.
Bản luận văn, ngoài phần mở đầu và tài liệu tham khảo còn có hai
chương chính cụ thể là: Chương 1 trình bày các kiến thức cơ bản nhất
về Giải tích lồi. Chương 2 giới thiệu bài toán tối ưu và đặc biệt đi sâu
vào sự phát triển của các điều kiện tối ưu cho các lớp bài toán tối ưu
lồi.
3
Chương 1
Các kiến thức chuẩn bị về giải
tích lồi
Chương này chủ yếu nhắc lại một số khái niệm, định nghĩa và kết
quả cần thiết liên quan đến tập lồi và hàm lồi. Nội dung chương này
tham khảo từ các tài liệu [1], [2].
1.1
1.1.1
Tập lồi
Các định nghĩa cơ bản về tập lồi
Định nghĩa 1.1.1 Một tập C ⊆ Rn đượ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 , ..., xk nếu
x=
k
X
j
λj x , λj > 0 ∀j = 1, ..., k,
j=1
k
X
λj = 1.
j=1
Tương tư, x là tổ hợp a-phin của các điểm (véc - tơ) x1 , ..., xk nếu
x=
k
X
j=1
j
λj x ,
k
X
λj = 1.
j=1
Tập hợp của các tổ hợp a-phin của x1 , ..., xk thường được gọi là bao
a-phin của các điểm này.
4
Định lý 1.1.2 Tập hợp C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi
của các điểm của nó. Tức là: C lồi khi và chỉ khi
∀k ∈ N, ∀λ1 , ..., λk > 0 :
k
X
1
k
λj = 1, ∀x , ..., x ∈ C ⇒
k
X
j=1
λj xj ∈ C.
j=1
Chứng minh.
Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh điều kiện
cần bằng quy nạp theo số điểm. Với k = 2, điều cần chứng minh suy
ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử định lý đúng
với k − 1 điểm. Ta cần chứng minh với k điểm.
Giả sử x là tổ hợp lồi của k điểm x1 , ..., xk ∈ C. Tức là
x=
k
X
j
λj x , λj > 0 ∀j = 1, ..., k,
j=1
k
X
λj = 1.
j=1
Đặt
k−1
X
ξ=
λj .
j=1
Khi đó 0 < ξ < 1 và
x=
k−1
X
j
k
λj x + λk x = ξ
j=1
Do
j=1
k−1
X
λj
j=1
và
k−1
X
λj
ξ
ξ
x j + λk x k .
(1.1)
=1
λj
> 0 với mọi j = 1, ..., k − 1, nên theo giả thiết quy nạp, điểm
ξ
y :=
k−1
X
λj
j=1
ξ
xj ∈ C.
Ta có
x = ξy + λk xk .
5
Do ξ > 0, λk > 0 và ξ + λk =
k
X
λj = 1, nên x là một tổ hợp lồi của
j=1
k
hai điểm y và x đều thuộc C. Vậy x ∈ C.
Lớp các tập lồi là đóng với các phép giao, phép cộng đại số và phép
nhân tích Descartes. Cụ thể, ta có định lý sau:
Định lý 1.1.3 Nếu A, B là các tập lồi trong Rn , C là lồi trong Rm ,
thì các tập sau là lồi:
A ∩ B := {x|x ∈ A, x ∈ B},
λA + βB := {x|x = αa + βb, a ∈ A, b ∈ B, λ, β ∈ R},
A × C := {x ∈ Rn+m |x = (a, c) : a ∈ A, c ∈ C}.
Chứng minh. Dễ dàng được suy ra trực tiếp từ định nghĩa.
Định nghĩa 1.1.4 Một tập C được gọi là tập a-phin nếu nó chứa
đường thẳng đi qua hai điểm bất kỳ của nó, tức là
∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C.
Vậy tập a-phin là một trường hợp riêng của tập lồi. Như đã nêu, một
ví dụ điển hình của tập a-phin là các không gian con. Một ví dụ khác
về tập a-phin là siêu phẳng được định nghĩa dưới đây.
Định nghĩa 1.1.5 Siêu phẳng trong không gian Rn là một tập hợp
các điểm có dạng
{x ∈ Rn |aT x = α},
trong đó a ∈ Rn là một véc - tơ khác 0 và α ∈ R.
Véc - tơ a thường được gọi là véc - tơ pháp tuyến của siêu phẳng. Một
siêu phẳng sẽ chia không gian ra hai nửa không gian. Nửa không gian
được định nghĩa như sau:
Định nghĩa 1.1.6 Nửa không gian là một tập hợp có dạng
{x|aT x ≥ α},
6
trong đó a 6= 0 và α ∈ R. Đây là nửa không gian đóng. Tập
{x|aT x ≥ α}
là nửa không gian mở.
Như vậy một siêu phẳng chia không gian ra làm hai nửa không gian,
mỗi nửa không gian ở về một phía của siêu phẳng. Nếu hai nửa không
gian này là đóng thì phần chung của chúng chính là siêu phẳng đó.
Mệnh đề dưới đây cho thấy tập a-phin chính là ảnh tịnh tiến của
một không gian con.
Định lý 1.1.7 M 6= ∅ là tập a-phin khi và chỉ khi nó có dạng M =
L + a với L là một không gian con và a ∈ M . Không gian con L này
được xác định duy nhất.
Không gian L trong định lý trên được gọi là không gian con song
song với M , hoặc nói ngắn gọn hơn là không gian con của M . Thứ
nguyên (hay chiều) của một tập a-phin M được định nghĩa bởi thứ
nguyên của không gian song song với M và được ký hiệu là dim M .
Định nghĩa 1.1.8 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 ∈ Rn |haj , xi ≤ bj , j = 1, ..., m}.
Hoặc nếu ta ký hiệu A là ma trận có m hàng là các véc - tơ aj (j =
1, ..., m) và véc - tơ bT = (b1 , ..., bm ), thì hệ trên viết được là:
D = {x ∈ Rn |Ax ≤ b}.
Chú ý rằng do một phương trình
ha, xi = b
có thể viết một cách tương đương dưới dạng hai bất phương trình
ha, xi ≤ b, h−a, xi ≤ b,
7
nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương
trình cũng là một tập lồi đa diện.
Định nghĩa 1.1.9 Một tập C được gọi là nón nếu
∀λ > 0, ∀x ∈ C ⇒ λx ∈ C.
Theo định nghĩa, ta thấy rằng gốc tọa độ có thể thuộc nón hoặc không
thuộc nón. Dĩ nhiên một nón không nhất thiết là một tập lồi. Ví dụ
C := {x ∈ R|x 6= 0}
là một nón, nhưng không lồi. 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 0 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).
Định lý 1.1.10 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 ⊆ C ∀λ > 0,
(ii) C + C ⊆ C.
Chứng minh. Giả sử C là một nón lồi. Do C là một nón, nên ta có
1
(i). Do C là một tập lồi, nên với mọi x, y ∈ C, thì (x + y) ∈ C. Vậy
2
theo (i) ta có x + y ∈ C.
Ngược lại, giả sử có (i) và (ii). Từ (i) suy ra ngay C là một nón.
Giả sử x, y ∈ C và λ ∈ [0, 1]. Từ (i) suy ra λx ∈ C, và (1 − λ)y ∈ C.
Theo (ii) có λx + (1 − λ)y ∈ C. Vậy C là một nón lồi.
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".
8
Định nghĩa 1.1.11 Cho C là một tập lồi trong Rn . Một véc - tơ y 6= 0
được gọi là hướng lùi xa của C, nếu mọi 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 ∀x ∈ 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ó định lý sau:
Định lý 1.1.12 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 ∀λ ≥ 0,
với một điểm x nào đó thuộc C.
Chứng minh. Giả sử x + λy ∈ C ∀λ > 0, với x ∈ C. Thế thì với mọi
u ∈ C và mọi µ > 0, do C lồi, ta có
xλ :=
µ
µ
(x + λy) + (1 −
)u ∈ C.
λ+µ
λ+µ
Cho λ → ∞, do C đóng, ta thấy u + µy ∈ C, với mọi u ∈ C và µ > 0.
Chú ý. Trong trường hợp C không đóng, định lý trên không đúng. Ví
dụ, trong R2 lấy
C := {x = (x1 , x2 )|x1 > 0, x2 > 0} ∪ {0}.
Hiển nhiên véc - tơ y = (0, 1) có tính chất là mọi tia xuất phát từ một
điểm 0 6= x ∈ C theo hướng này đều nằm trọn trong C, nhưng nếu
xuất phát từ x = 0 thì điều này không đúng.
Cho C ⊆ Rn là một tập lồi và x ∈ C. Ký hiệu
NC (x) := {w|hw, y − xi ≤ 0 ∀y ∈ C}.
9
Hiển nhiên 0 ∈ NC (x). Dùng định nghĩa, dễ kiểm tra được rằng NC (x)
là một nón lồi đóng. Nón này được gọi là nón pháp tuyến ngoài của
C tại x. Tập −NC (x) được gọi là nón pháp tuyến trong của C tại x.
Hiển nhiên
−NC (x) := {w|hw, y − xi ≥ 0 ∀y ∈ C}.
Một nón quan trọng khác là nón đối cực được định nghĩa như sau:
C ∗ := {w|hw, xi ≤ 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 ∈ Rn là một
hướng chấp nhận được của C nếu tồn tại t0 > 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 nếu lấy bao đóng, ta sẽ
dượ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) = {d ∈ Rn |∃dk → d, ∃tk & 0 : x + tk dk ∈ C ∀k}.
Định nghĩa 1.1.13 Bao lồi của một tập E là giao của tất cả các tập
lồi chứa E.
Tương tự, ta định nghĩa bao a-phin của E là giao của tất cả các
tập a-phin chứa E, và bao nón lồi của tập E (còn gọi là nón lồi sinh
bởi E) là giao của tất cả các nón lồi chứa E. Bao lồi của một tập E
sẽ được ký hiệu là coE; bao a-phin của một tập E sẽ được ký hiệu là
af f E, còn bao nón lồi của E sẽ được ký hiệu là coneE. Do tính chất
của nón, nên nếu một điểm x ∈ coneE, thì λx ∈ coneE với mọi λ > 0.
Do đó để tiện làm việc, người ta thường cho luôn điểm gốc vào bao
nón lồi của một tập.
Chú ý rằng giao của các tập lồi (tập a-phin, nón lồi) cũng là tập lồi
(tập a-phin, nón lồi), nên bao lồi, bao a-phin và bao lồi được xác định
một cách duy nhất. Như vậy bao lồi của một tập E là tập lồi nhỏ nhất
chứa E. Tương tự bao a-phin của E là tập a-phin nhỏ nhất chứa E.
10
Bao nón lồi của E là tập hợp gồm gốc tọa độ và nón lồi nhỏ nhất chứa
E. Như vậy khác với bao lồi và bao a-phin, bao nón lồi của một tập
nói chung khác một chút với nón lồi nhỏ nhất chứa tập đó.
Dĩ nhiên nếu E 6= ∅, thì bao lồi, bao a-phin và bao nón lồi luôn tồn
tại duy nhất và khác rỗng vì các tập này đều chứa E và vì bản thân
toàn bộ không gian đồng thời vừa là một tập lồi, một tâp a-phin và
một nón lồi chứa E.
Chú ý rằng có một số tác giả định nghĩa nón như sau: một tập C
được gọi là một nón nếu với mọi x ∈ C thì λx ∈ C với mọi λ ≥ 0.
Theo định nghĩa này, nón luôn chứa gốc. Khi đó bao nón lồi của một
tập E chính là giao của các nón lồi chứa E.
Nhắc lại rằng, thứ nguyên (còn gọi là chiều) của một tập E bất kỳ
được định nghĩa như là thứ nguyên của bao a-phin của nó. Tức là
dim E := dim(af f E).
Định lý 1.1.14 Cho E là một tập lồi. Khi đó
coneE = {λx|x ∈ E, λ ≥ 0}.
Chứng minh. Gọi M := {λx|x ∈ E, λ > 0}. Hiển nhiên là bất kỳ nón
nào chứa E, đều phải chứa M . Ta sẽ chỉ ra là bản thân M cũng là một
nón lồi. Giả sử y 1 , y 2 ∈ M . Vậy y 1 = λ1 x1 , y 2 = λ2 x2 với λ1 , λ2 > 0 và
x1 , x2 ∈ E. Khi đó, ta có
!
λ1
λ2
x1 +
x2 .
y 1 + y 2 = (λ1 + λ2 )
λ1 + λ2
λ1 + λ2
Do E lồi, nên
λ1
λ2
x1 +
x2 ∈ E.
λ1 + λ2
λ1 + λ2
Vậy y 1 + y 2 ∈ M . Suy ra M là nón lồi nhỏ nhất chứa E và do đó
bao nón lồi của E là tập hợp gồm M và gốc tọa độ. Tức là coneE =
{λx|x ∈ E, λ ≥ 0}.
Định lý 1.1.15 (Carathéodory). Cho E là một tập bị chứa trong một
tập a-phin có thứ nguyên là k. Khi đó mọi x ∈ coE đều có thể biểu
diễn như là tổ hợp lồi của nhiều nhất (k + 1) phần tử của E.
11
Chứng minh định lý này sẽ dùng đến định lý sau, cũng là một dạng
của định lý Carathéodory đối với bao nón lồi.
Định lý 1.1.16 Giả sử E ⊂ Rk . Khi đó mỗi điểm x 6= 0 thuộc coneE
đều có thể biểu diễn dưới dạng
x = λ1 x1 + ... + λr xr ,
trong đó xi ∈ E, λi > 0 với mọi i và các điểm x1 , ..., xr độc lập tuyến
tính. Nói riêng r ≤ k.
Chứng minh.
Bạn đọc tham khảo trong tài liêu [1].
Chứng minh định lý Carathéodory.
Xét tập hợp
B := {1} × E = {(1, x)|x ∈ E} ⊂ R × Rk .
Ta có coB = {1} × coE. Giả sử coneB là nón lồi sinh bởi B. Do coB
là tập lồi nhỏ nhất chứa B, nên
coB ⊂ coneB.
Với mọi (1, x) ∈ coB, theo định lý trên, tồn tại các điểm
(1, x1 ), ..., (1, xr ) ∈ B
và các số λ1 , ..., λr , với r ≤ k + 1 thỏa mãn:
x = λ1 x1 + ... + λr xr , xi ∈ E ∀i,
λ1 + ... + λr = 1, λi > 0 ∀i.
Ta nhắc lại các khái niệm về điểm trong, điểm biên, tập compact
v.v... trong giải tích cổ điển. Cho E ⊆ Rn . Điểm a được gọi là điểm
trong của E nếu tồn tại một lân cận mở U (a) của a sao cho U (a) ⊂ E.
Ký hiệu tập hợp các điểm trong của tập E là intE và B là quả cầu
đơn vị, tâm ở gốc. Khi đó theo định nghĩa, ta có
intE = {x : ∃r > 0, x + rB ⊂ E}.
12
Điểm a được gọi là điểm biên của E nếu mọi lân cận của a đều có
điểm thuộc E và điểm không thuộc E. Tập E được gọi là tập mở nếu
mọi điểm của E đều là điểm trong của E. Tập E được gọi là tập đóng,
nếu E chứa mọi điểm biên của nó. Tập E ⊂ Rn được gọi là một tập
compact, nếu E là một tập đóng và bị chặn. Ta nói điểm a thuộc bao
đóng của tập E nếu mọi lân cận của a đều chứa điểm thuộc E. Ký
kiệu E là bao đóng của E. Khi đó từ định nghĩa, suy ra
E = ∩r>0 (E + rB).
Chú ý rằng bao lồi của một tập đóng không nhất thiết đóng.
Ví dụ, nếu
E = {(x, 0) ∈ R2 , x ∈ R} ∪ {(0, 1)},
thì
coE = {(x, y) ∈ R2 |x ∈ R, 0 ≤ y < 1} ∪ {(0, 1)}.
Tuy nhiên nếu E là compact, thì coE cũng là compact theo hệ qủa sau
đây:
Hệ quả 1.1.17 Nếu E ⊂ R2 là một tập compact, thì coE cũng compact.
1.1.2
Toán tử chiếu tập lồi
Định nghĩa 1.1.18 Cho C 6= ∅ (không nhất thiết lồi) và y là một
véc-tơ bất kỳ, đặt
dC (y) := inf kx − yk.
x∈C
Ta nói dC (y) là khoảng cách từ y đến C. Nếu tồn tại π ∈ C sao cho
dC (y) = kπ − yk, thì ta nói πlà hình chiếu (vuông góc) của y trên C .
Định lý 1.1.19 Cho C là một tập lồi đóng khác rỗng. Khi đó:
i) Với mọi y ∈ Rn , π ∈ C hai tính chất sau là tương đương:
a) π = pC (y),
b) y − π ∈ NC (π).
ii) Với mọi y ∈ Rn , hình chiếu pC (y) của y trên C luôn tồn tại và
duy nhất.
13
iii) Nếu y ∈
/ C, thì hpC (y) − y, x − pC (y)i = 0 là siêu phẳng tựa của
C tại pC (y) và tách hẳn y khỏi C, tức là
hpC (y) − y, x − pC (y)i ≥ 0, ∀x ∈ C,
và
hpC (y) − y, y − pC (y)i < 0.
iv) Ánh xạ y ,→ pC (y) có các tính chất sau:
a) kpC (x) − pC (y)k ≤ kx − yk ∀x, ∀y. (tính không giãn),
b) hpC (x) − pC (y), x − yi ≥ kpC (x) − pC (y)k2 , (tính đồng bức).
Chứng minh.
i) Giả sử có a). Lấy x ∈ C và λ ∈ (0, 1). Đặt
xλ := λx + (1 − λ)π.
Do x, π ∈ C và C lồi, nên xλ ∈ C. Hơn nữa do π là hình chiếu của
y, nên kπ − yk ≤ ky − xλ k. Hay
kπ − yk2 ≤ kλ(x − π) + (π − y)k2 .
Khai triển vế phải, ước lược và chia hai vế cho λ > 0 , ta có
λkx − πk2 + 2hx − π, π − yi ≥ 0.
Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ tiến
đến 0, ta được
hπ − y, x − πi ≥ 0 ∀x ∈ C.
Vậy y − π ∈ NC (π).
Bây giờ giả sử có b). Với mọi x ∈ C, có
0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π)
= ky − πk2 + (y − π)T (x − y).
Từ đây và b), dùng bất đẳng thức Cauchy-Schwarz ta có:
ky − πk2 ≤ (y − π)T (y − x) ≤ ky − πkky − xk.
14
Suy ra ky − πk ≤ ky − xk ∀x ∈ C, và do đó π = p(y).
ii) Do dC (y) = inf x∈C kx − yk, nên theo định nghĩa của cận dưới đúng
(infimum), tồn tại một dãy xk ∈ C sao cho
lim kxk − yk = dC (y) < +∞.
k
Vậy dãy {xk } bị chặn, do đó nó có một dãy con {xkj } hội tụ đến
một điểm π nào đó. Do C đóng, nên π ∈ C. Vậy
kπ − yk = lim kxkj − yk = lim kxk − yk = dC (y).
j
k
Chứng tỏ π là hình chiếu của y trên C.
Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn
tại hai điểm π và π 1 đều là hình chiếu của y trên C, thì
y − π ∈ NC (π), y − π 1 ∈ NC (π 1 ).
Tức là
hπ − y, π 1 − πi ≥ 0
và
hπ 1 − y, π − π 1 i ≥ 0.
Cộng hai bất đẳng thức này ta suy ra kπ − π 1 k ≤ 0, và do đó
π = π1.
iii) Do y − π ∈ NC (π), nên
hπ − y, x − πi ≥ 0 ∀x ∈ C.
Vậy hπ − y, xi = hπ − y, πi là một siêu phẳng tựa của C tại π. Siêu
phẳng này tách y khỏi C vì y 6= π, nên
hπ − y, y − πi = −kπ − yk2 < 0.
15
iv) Theo phần (ii) ánh xạ x ,→ p(x) xác định khắp nơi. Do z − p(z) ∈
NC (p(z)) với mọi z, nên áp dụng với z = x và z = y, ta có:
hx − p(x), p(y) − p(x)i ≤ 0
và
hy − p(y), p(x) − p(y)i ≤ 0.
Cộng hai bất đẳng thức lại sẽ được
hp(y) − p(x), p(y) − p(x) + x − yi ≤ 0.
Từ đây và theo bất đẳng thức Cauchy-Schwarz, suy ra
kp(x) − p(y)k ≤ kx − yk.
Để 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ó:
hp(x) − x, p(x) − p(y)i ≤ 0.
hy − p(y), p(x) − p(y)i ≤ 0.
Cộng hai bất đẳng thức ta được
hp(x) − p(y) + y − x, p(x) − p(y)i
= hp(x) − p(y), y − xi + kp(x) − p(y)k2 ≤ 0.
Chuyển vế ta có
hp(x) − p(y), x − yi ≥ kp(x) − p(y)k2 .
Đây chính là tính đồng bức cần được chứng minh.
Định lý 1.1.20 (Định lý tách 1). Cho C và D là hai tập lồi khác rỗng
trong Rn sao cho C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D.
Định lý tách vừa nêu có thể suy ra ngay từ Bổ đề 1.1.21 dưới đây,
chính là định lý tách một tập lồi và một phần tử không thuộc nó.
16
Bổ đề 1.1.21 (Bổ đề liên thuộc). Cho C ⊂ Rn là một tập lồi khác
rỗng. Giả sử x0 ∈ C. Khi đó tồn tại t ∈ Rn , t 6= 0 thỏa mãn
ht, xi ≥ ht, x0 i∀x ∈ C.
(1.4)
Chứng minh Định lý 1.1.20. Do C và D là lồi, nên C − D cũng
lồi. Hơn nữa 0 ∈
/ (C − D), vì C ∩ D = ∅. Theo bổ đề trên áp dụng
với x0 = 0, tồn tại véc-tơ t ∈ Rn , t 6= 0 sao cho ht, zi ≥ 0 với mọi
z ∈ C − D. Vì z = x − y với x ∈ C, y ∈ D, nên ta có
ht, xi ≥ ht, yi ∀x ∈ C, y ∈ D.
Lấy
α := supht, yi,
y∈D
khi đó siêu phẳng ht, xi = α tách C và D.
Định lý 1.1.22 (Định lý tách 2). Cho C và D là hai tập lồi đóng khác
rỗng sao cho C ∩ D = ∅ . Giả sử có ít nhất một tập là compact. Khi
đó hai tập này có thể tách mạnh được bởi một siêu phẳng
Cũng như trên, định lý tách mạnh được dễ dàng suy ra từ bổ đề sau
nói về sự tách mạnh giữa một tập lồi đóng và một điểm bên ngoài tập
này.
Bổ đề 1.1.23 Cho C ⊂ Rn là một tập lồi đóng khác rỗng sao cho
0∈
/ C. Khi đó tồn tại một véc-tơ t ∈ Rn , t 6= 0 và α > 0 sao cho
ht, xi ≥ α > 0, ∀x ∈ C.
Chứng minh Định lý 1.1.22. Giả sử C là tập compact. Ta chỉ ra tập
C −D đóng. Thật vậy, giả sử z k ∈ C −D và z k → z. Ta có z k = xk −y k
với xk ∈ C, y k ∈ D. Vì C compact, nên có một dãy con xkj → x khi
j → +∞. Vậy y kj = z kj − xkj → z − x ∈ D. Vậy z = x − y ∈ C − D.
Chứng tỏ C − D là tập đóng. Do 0 ∈
/ C − D, nên theo bổ đề trên, tồn
tại t 6= 0, sao cho ht, x − yi ≥ α > 0 với mọi x ∈ C, y ∈ D. Vậy
inf ht, xi −
x∈C
α
α
≥ supht, yi + .
2
2
y∈D
- Xem thêm -