ĐẠ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
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
THÁI NGUYÊN - 2015
ĐẠ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
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
THÁI NGUYÊN - 2015
i
LỜI CAM ĐOAN Tôi xin cam đoan rằng, nội dung của bản luận văn này do chính tôi đã tổng
hợp từ các tài liệu được nêu trong phần tài liệu tham khảo. Luận văn không
phải là bản sao chép lại của bất kỳ tài liệu nào khác.
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Thái Ngyên, tháng 2 năm 2015 Tác giả Nguyễn Trần Thành
ii
LỜI CẢM ƠN
Luận văn được thực hiện và hoàn thành tại trường Đại học Sư phạm -
Đại học Thái nguyên dưới sự hướng dẫn khoa học của GS. TSKH. Lê Dũng Mƣu.
Trước tiên, Tôi xin được bày tỏ lòng biết ơn sâu sắc đến thầy giáo, người
hướng dẫn khoa học của mình, GS. TSKH. Lê Dũng Mưu, người đã đặt bài
toán và tận tình hướng dẫn trong suốt quá trình nghiên cứu của tôi. Đồng thời
tôi cũng chân thành cảm ơn các thầy cô trong khoa Toán, khoa Sau đại học -
Trường Đại học sư phạm - Đại học Thái Nguyên, đã tạo mọi điều kiện cho tôi
để tôi có thể hoàn thành bản luận văn này. Tôi cũng gửi lời cảm ơn đến các bạn
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
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
thầy cô và bạn bè, tôi xin chân thành cảm ơn!
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
1.3. Hàm lồi ................................................................................................. 22
Chƣơng 2. ĐỊNH LÝ TÁCH TRONG BÀI TOÁN TỐI ƢU ....................... 25
2.1. Bài toán tối ưu ...................................................................................... 25
2.2. Ứng dụng của định lý tách trong tối ưu hóa ......................................... 28
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
KẾT LUẬN ....................................................................................................... 41
iv
BẢNG KÝ HIỆU
Không gian Euclide n - chiều trên trường số thực;
Trục số thực;
Tọa độ thứ i của x;
Véc-tơ hàng (chuyển vị của a)
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;
Bao đóng của C;
coC Bao lồi của C;
coneC Nón sinh bởi tập C;
aff(C) Bao affine của tập C;
riC Tập hợp các điểm trong tương đối của C;
V(C) Tập các điểm cực biên (đỉnh) của C;
Bao lồi đóng của C;
reC Nón lùi xa (nón các hướng vô hạn) của C;
intC Tập hợp các điểm trong của C;
dimC Thứ nguyên (số chiều) của tập C;
Dưới vi phân của tại x;
Đạo hàm của tại x;
Hình nón pháp tuyến của C tại ;
Nón pháp tuyến ngoài của C tại ;
- Nón pháp tuyến trong của C tại ;
Nón các hướng chấp nhận được;
Nón tiếp xúc của C tại x;
Là khoảng cách từ y đến C;
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Tập hợp các hướng chấp nhận được của C tại
v
DANH MỤC CÁC HÌNH
Hình 1.1: Hình chiếu vuông góc ..................................................................... 13
Hình 1.2: Tách chặt nhưng không tách mạnh ................................................. 18
Hình 1.3: Tách nhưng không tách mạnh ......................................................... 21
Hình 1.4: Bổ đề Farkas .................................................................................... 22
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Hình 1.5: Đồ thị hàm lồi ( ) ................................................................... 23
1
MỞ ĐẦU
1. Lý do chọn luận văn
Tối ưu hóa là một ngành toán học ứng dụng, nghiên cứu lý thuyết và các
thuật toán giải bài toán cực trị. Ngành toán học này đã và đang được nhiều
người quan tâm nghiên cứu, tìm hiểu và ứng dụng. Các bài toán tối ưu rất
phong phú và đa dạng, chúng có nhiều ứng dụng rộng rãi trong thực tiễn.
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-Kuhn-
Tucker, đị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
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
hóa, đó là sử dụng Định lý tách để chứng minh Định lý Karush-Kuhn-Tucker,
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.
Chƣơng 1
ĐỊNH LÝ TÁCH CÁC TẬP LỒI
Định lý tách hai tập lồi là một định lý trung tâm của Giải tích lồi, có
nhiều ứng dụng trong các lĩnh vực khác nhau, đặc biệt là trong tối ưu hóa.
Trong chương này chúng ta sẽ trình bầy một số lý thuyết cơ bản của Giải tích
lồi, đó là các khái niệm về tập lồi cùng các tính chất của chúng, phát biểu và
chứng minh các Định lý tách, Bổ đề Farkas. Các kết quả ở chương này được
tổng hợp ở các tài liệu [1], [2], [3].
1.1. Tập lồi
Một đường thẳng nối hai điểm (hai véc-tơ) a, b trong là tập hợp tất
cả các véc-tơ có dạng:
.
Đoạn thẳng nối hai điểm a và b trong là tập hợp các véc-tơ x có dạng
.
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 gọi là một tập lồi, nếu chứa mọi
đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là lồi khi và chỉ khi
ta nói x là tổ hợp lồi của các điểm (véc-tơ) nếu
.
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Tương tự, x là tổ hợp a-phin của các điểm (véc-tơ) nếu
3
.
Tập hợp của các tổ hợp a-phin của thường được gọi là bao a-
phin của các điểm này.
Ví dụ
1. Trong 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 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
,
trong đó và .
Đây là nửa không gian đóng. Tập
,
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.
1.1.3. Mệnh đề. là tập a-phin khi và chỉ khi nó có dạng
với là một không gian con và , không gian con này được xác
định duy nhất.
Chứng minh. Giả sử là tập a-phin và . Khi đó thì là một
không gian con. Vậy . Ngược lại, nếu với là không
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
gian con, thì với mọi , ta có
4
.
Do và đều thuộc và do là không gian con, nên
.
Vậy
.
Suy ra là tập a-phin.
Không gian con ở trên là duy nhất. Thật vậy, nếu và
, thì
Do , nên . Suy ra .
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:
.
Hoặc nếu ta ký hiệu A là ma trận có m hàng và các véc-tơ
và các véc-tơ thì hệ trên viết được là:
.
Do một phương trình
có thể viết một cách tương đương dưới dạng hai bất phương trình
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
, ,
5
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.
1.1.5. Định nghĩa. Một tập C được gọi là nón nếu
.
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ụ
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:
,
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 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) ,
(ii) .
Chứng minh. Giả sử C là một nón lồi. Do C là một nón, nên ta có (i). Do C là
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
một tập lồi, nên , thì . Vậy theo (i) ta có .
6
Ngược lại, giả sử có (i) và (ii). Từ (i) suy ra ngay C là một nón. Giả sử
và . Từ (i) suy ra và . Theo (ii) 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”.
Cho C là một tập lồi trong . Mặt khác véc-tơ đượ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
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 , chỉ cần đòi hỏi cho một điểm . 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
,
với một điểm x nào đó thuộc C.
Chứng minh. Giả sử , với . Thế thì với mọi và
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
mọi do C lồi ta có
7
.
Cho , do C đóng, ta thấy , với mọi và .
Chú ý: Trong C không đóng mệnh đề trên không đúng.
Ví dụ Trong lấy
.
Hiển nhiên véc-tơ có tính chất là mọi tia xuất phát từ một điểm
theo hướng này đều nằm trọn trong C, nếu xuất phát từ thì điều
này không đúng.
Cho là một tập lồi và . Ký hiệu
.
Hiển nhiên . Dùng định nghĩa dễ kiểm tra được rằng 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 -
được gọi là nón pháp tuyến trong của C tại x. Hiển nhiên
.
Một nón quan trọng khác là nón đối cực được định nghĩa như sau:
.
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à . Ta nói là một hướng
chấp nhận được của C nếu tồn tại sao cho với mọi .
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à và sẽ gọi là nón các hướng chấp nhận được hoặc
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
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
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à , thì . Từ đây suy ra
.
Mệnh đề sau đây dễ dàng được suy ra trực tiếp từ định nghĩa.
1.1.9. Mệnh đề. Nón pháp tuyến và nón tiếp xúc là đối cực của nhau.
Ví dụ Giả sử tập lồi C được cho bởi
.
Với , đặt
,
gọi là tập chỉ số tích cực tại x.
Khi đó
,
.
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 , C là lồi trong , thì các tập sau là lồi:
(i) ,
(ii)
(iii) .
Chứng minh. Dễ dàng được suy ra trực tiếp từ định nghĩa.
1.1.11. Định nghĩa. Một tập được gọi là một diện của tập lồi C nếu F là
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
tập lồi có tính chất là:
9
.
Đ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ư và .
Đ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 với . Dễ thấy rằng d là
hướng cực biên của một tập lồi, nó không thể biểu diễn bằng tổ hợp tuyến tính
dương của hai hướng khác thuộc tập lồi đó.
Từ định nghĩa này suy ngay ra rằng là một điểm cực biên của C
khi và chỉ khi không tồn tại hai điểm sao cho với
. Ngoài ra một điểm hoặc một tia cực biên của một diện của một tập
lồi C cũng là một điểm hoặc một tia cực biên của C. Tập hợp các điểm cực biên
của C thường được ký hiệu là V(C). Khi C là một tập lồi đa diện, thì điểm cực
biên còn được gọi là đỉnh.
1.1.12. Định nghĩa. Siêu phẳng trong không gian là một tập hợp các
điểm có dạng
,
trong đó là một véc-tơ khác 0 và .
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Véc-tơ a thường được gọi là véc-tơ pháp tuyến của siêu phẳng.
10
1.1.13. Định nghĩa. Cho . Ta nói là siêu phẳng tựa của C tại , nếu
.
Như vậy siêu phẳng tựa của C tại là siêu phẳng đi qua và để tập C
về một phía. Nửa không gian trong định nghĩa trên, được gọi là nửa
không gian tựa của C tại .
1.1.14. Mệnh đề. Nếu H là một siêu phẳng tựa của C thì là một diện
của C; diện này là không gian tầm thường khi và chỉ khi .
Chứng minh. Gọi . Do C và H lồi, nên F lồi. Giả sử siêu phẳng tựa
H có dạng
và .
Để chứng tỏ F là một diện của C, hãy cho với
mọi và giả sử . Khi đó
.
Do nên
, .
Từ đây suy ra
.
Như vậy và do F lồi, nên cả đoạn . 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 ,
chỉ cần sử dụng trực tiếp định nghĩa.
1.1.15. Định lý. (Krein-Milman). Mọi tập lồi đóng khác rỗng, không chứa
đường thẳng đều có điểm cực biên.
http://www.lrc.tnu.edu.vn
Chứng minh. Giả sử C là tập lồi nói trong định lý. 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. Giả Số hóa bởi Trung tâm Học liệu – ĐHTN
11
bất kỳ. Xét đường thẳng với . Do C đóng và không
chứa đường thẳng, nên cắt C tại một điểm cực biên của C, giả sử là z. Gọi H
là siêu phẳng tựa của H tại z. Khi đó theo mệnh đề trên, 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ì
.
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ử bất kỳ. xét tia
với sao cho cắt biên của C tại một điểm .
Vậy . Ta có hai trường hợp sau:
a) Trường hợp . Do C lồi, đóng và không chứa đường thẳng,
nên tia này phải cắt C tại ít nhất một điểm nào đó thuộc biên của C. Khi đó
tồn tại một siêu phẳng tựa H của C tại và tập là một diện của C
và dimF < dimC. Hiển nhiên F lồi, đóng và cũng không chứa đường thẳng.
Theo giả thiết qui nạp ta có:
.
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Do F là một diện của C, nên
12
Do và với , nên từ đây suy ra
.
b) Trường hợp (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 (không nhất thiết lồi) và y là một véc-tơ bất kỳ, đặt
ta nói là khoảng cách từ y đến C. Nếu tồn tại số sao cho
, thì ta nói là hình chiếu của y trên C.
Theo định nghĩa, ta thấy rằng hình chiếu của y trên C sẽ là
nghiệm của bài toán tối ưu
.
Nói cách khác việc tìm hình chiếu của y trên C có thể đưa về việc tìm
cực tiểu của hàm toàn phương trên C.
Như thường lệ, sẽ ký hiệu , hoặc đơn giản hơn là nếu
không cần nhấn mạnh đến tập chiếu C. Chú ý rằng, nếu , thì hữu
hạn, vì với mọi .
Cho , . Nhớ lại là nón pháp tuyến (ngoài) của tập C tại
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
là tập hợp
13
Hình 1.1: Hình chiếu vuông góc
1.1.18. Mệnh đề. Cho C là một tập lồi đóng khác rỗng. Khi đó:
(i) Với mọi , hai tính chất sau đây là tương đương:
a) ,
b)
(ii) Với , hình chiếu của của y trên C luôn tồn tại và duy nhất.
(iii) Nếu , thì là siêu phẳng tựa của C
tại và tách hẳn y khỏi C, tức là
,
và
.
(iv) Ánh xạ có các tính chất sau:
a) . (tính không giãn)
b) , (tính đồng bức hay đơn
điệu ngược)
Chứng minh. (i) Giả sử có a). Lấy và . Đặt
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
.
14
Do và C lồi, nên . Hơn nữa do là hình chiếu của y, nên
. Hay
.
Khai triển vế phải, ước lược và chia hai vế cho , ta có
.
Điều này đúng với mọi . Do đó khi cho tiến đến 0, và
ta được:
.
Vậy .
Bây giờ giả sử có b), với mọi , có
Từ đây và b), dùng bất đẳng thức Cauchy-Shwarz ta có:
.
Suy ra , và do đó .
(ii) Do , nên theo định nghĩa của cận dưới đúng
(infimum), tồn tại một dãy sao cho
.
Vậy dãy bị chặn, do đó nó có một dãy con hội tụ đến một
điểm nào đó. Do C đóng, nên . Vậy
.
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Chứng tỏ là hình chiếu của y trên C.
15
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à đều là hình chiếu của y trên C, thì
.
Tức là
và
.
Cộng hai bất đẳng thức này ta suy ra , và do đó .
(iii) Do , nên
.
(iv) Theo phần (ii), ánh xạ xác định khắp nơi. Do
với mọi z, nên áp dụng với và , ta có:
và
.
Cộng hai bất đẳng thức lại sẽ được
.
Từ đây theo bất đẳng thức Cauchy-Schwarz, suy ra
.
Để 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
và , ta có:
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
.
16
Cộng hai bất đẳng thức này ta được
.
Chuyển vế ta có
.
Đâ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à . Khi đó tồn tại
siêu phẳng tựa của tại hình chiếu của trên .
Chứng minh. Gọi hình chiếu của trên là .
Trước hết xét trường hợp . Vậy . Phân biệt hai
trường hợp:
a) . Do lồi, đóng, nên theo (iii) của Mệnh đề 1.1.14, siêu phẳng
là siêu phẳng tựa của C tại và tách hẳn C và .
b) . Khi đó do , nên . Vậy tồn tại dãy
với với mọi k. Do lồi, đóng, nên lại áp dụng (iii) của Mệnh đề 1.1.18,
tồn tại siêu phẳng tựa của tại . Tức là tồn tại , thỏa mãn:
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
.
17
Bằng cách chuẩn hóa ta có thể coi , và do đó có thể giả sử
. 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ú ý (vì ), ta có:
.
Vậy là siêu phẳng tựa của tại .
Trường hợp , thì dimC < n. Vậy C bị chứa trong một siêu phẳng
H chứa . Gọi w là véc-tơ pháp tuyến của H. Khi đó tồn tại số thực sao
cho . Do , nên suy ra H là siêu phẳng tựa của
cả C và .
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
tách C và D nếu
(1.1)
Ta nói siêu phẳng tách chặt C và D nếu
.
Ta nói siêu phẳng tách mạnh C và D nếu
(1.2)
Ví dụ
+ Xét các tập: ,
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
thì siêu phẳng tách C và D nhưng không tách mạnh.
18
+ Xét hai tập ,
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
sao cho . Khi đó có một siêu phẳng tách C và D.
Định lý vừa nêu có thể suy ra ngay từ Bổ đề 1.1 dưới đây, chính là định
lý tách một tập lồi và phần tử không thuộc nó.
1.2.3. Bổ đề. (Bổ đề liên thuộc). Cho là một tập lồi khác rỗng. Giả sử
. Khi đó tồn tại , thỏa mãn
(1.3)
Chứng minh. Do , nên sự tồn tại siêu phẳng tách trong bổ đề, được
suy ra từ Mệnh đề 1.1.19
Chứng minh định lý 1.2.2. Do C và D là lồi, nên C-D cũng lồi. Hơn nữa
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
, vì . Theo bổ đề trên áp dụng với , tồn tại véc-tơ
19
, sao cho với mọi . Vì với ,
, nên ta có:
, .
,
khi đó siêu phẳng tách C và D
Chú ý. Chứng minh Bổ đề liên thuộc ở trên gợi ý cho việc xác định siêu phẳng
tách. Theo chứng minh Mệnh đề 1.1.19, việc xác định siêu phẳng tách điểm
và tập C chính là việc tìm điểm chiếu của trên . Điểm này chính là nghiệm
của bài toán
.
Do phạm vi sử dụng rộng rãi và vai trò quan trọng của Định lý tách trong
nhiều lĩnh vực của toán học, nên việc tìm phương pháp giải cho bài toán tối ưu
này luôn là một đề tài rất được quan tâm. Trong nhiều trường hợp riêng của tập
C, bài toán trên đã có những phương pháp giải hiệu quả. Tuy nhiên trong
trường hợp chung, đây vẫn là một bài toán rất khó giải.
Định lý sau đây nói về việc tách mạnh hai tập lồi:
1.2.4. Định lý. (Định lý tách 2). Cho C và D là hai tập lồi đóng khác rỗng sao
cho . Giả sử có ít nhất một tập là com-pắc. 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.
1.2.5. Bổ đề. Cho là một tập lồi đóng khác rỗng sao cho . Khi đó
tồn tại một véc-tơ , và sao cho
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
.
20
Theo bổ đề này, thì C và điểm gốc tọa độ có thể tách mạnh, ví dụ bởi
siêu phẳng .
Chứng minh bổ đề. Do C đóng và , nên tồn tại quả cầu B tâm ở gốc, bán
kính sao cho . Áp dụng Định lý tách 1 cho hai tập C và B, ta có
và , sao cho
.
Bằng cách chuyển hóa ta có thể xem và do đó khoảng cách từ gốc
đến siêu phẳng ít nhất là bằng . Vậy thì
.
Chứng minh định lý 1.2.4. Giả sử C là tập compact. Ta chỉ ra tập C-D là đóng.
Thật vậy, giả sử và . Ta có với .
Vì C là compact, nên có một dãy con . Vậy khi
. Vậy . Chứng C-D là tập đóng. Do
, nên theo bổ đề trên, tồn tại , sao cho với
mới . Vậy
.
Chứng tỏ C và D có thể tách mạnh.
Chú ý. Điều kiện một trong hai tập com-pắc trong định lý là không thể bỏ
được. Hãy xét ví dụ trong đó
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
, .
21
Hình 1.3: Tách nhưng không tách mạnh
Rõ ràng hai tập này lồi, đóng không có điểm chung, nhưng không thể
tách mạnh được.
Một hệ quả rất quan trọng của định lý tách là bổ đề chọn mang tên nhà
toán học Hungary Farkas, được chứng minh từ năm 1892 dưới dạng định lý
hình học, Bổ đề này rất trực quan, dễ áp dụng trong nhiều lĩnh vực như tối ưu,
điều khiển, lý thuyết toán tử v.v…
1.2.6. Hệ quả. Cho A là một ma trận thực cấp và . Khi đó trong
hai hệ dưới đây có một hệ và chỉ duy nhất một hệ có nghiệm:
với một , (1.4)
với một (1.5)
Một cách phát biểu tương đương, dưới ngôn ngữ hình học của bổ đề
Farkas là:
Nửa không gian chứa nón khi và chỉ khi véc-tơ a
nằm trong nón sinh bởi các hàng của ma trận A. Tức là
khi và chỉ khi .
Tính chất hình học của bổ đề này rất rõ. Nó nói rằng nón lồi, đóng
nằm trong nửa không gian khi và chỉ khi véc-tơ pháp
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
tuyến a ở trong nón sinh bởi các hàng của ma trận A.
22
Hình 1.4: Bổ đề Farkas
Chứng minh bổ đề Farkas. Giả sử (1.5) có một nghiệm y nào đó. Nếu như
, thì , nhân tích vô hướng với x, và cho , , ta có
. Vậy (1.4) không thể có nghiệm.
Bây giờ ta giả sử hệ (1.5) không có nghiệm. Lấy tập .
Hiển nhiên C là tập lồi, đóng và . Do (1.5) không có nghiệm, nên .
Theo định lý tách mạnh, tồn tại và một số sao cho
với mọi . Do , nên . Thay , với , ta viết được
.
Chú ý rằng nếu , thì với mọi , vì từ , có
. Vậy các tọa độ của y có thể lớn tùy ý, nên từ bất đẳng thức
, suy ra và .
Chứng tỏ hệ (1.4) có nghiệm.
1.3. Hàm lồi
1.3.1. Định nghĩa. Cho . Ta nói là hàm lồi trên tập hợp
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
lồi C, nếu
23
Ý nghĩa hình học: Cát tuyến nối hai điểm bất kỳ trên đồ thị của hàm nằm
phía trên đồ thị.
Hình 1.5: Đồ thị hàm lồi ( )
1.3.2. Định nghĩa. Cho
được gọi là dưới vi phân của hàm tại x.
Từ định nghĩa ta thấy rằng là giao của một họ nửa không gian, do
đó là tập lồi.
Ví dụ
1) Xét hàm .
Tại , hàm này không khả vi
Chú ý. Khi khả vi tại x thì
2) Cho là hàm chuẩn của tập C. Tức là
trong ®ã låi. Ta cã
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Thật vậy, giả sử
24
(1.6)
(1.7)
nên (1.7) luôn đúng. Nếu thì
. Khi đó Nếu thì
Nếu thì (1.6) không đúng vì vế trái bằng còn vế phải
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
nếu .
25
Chƣơng 2
ĐỊNH LÝ TÁCH TRONG BÀI TOÁN TỐI ƢU
Trong chương này trình bày ứng dụng của Định lý tách trong tối ưu hóa
cụ thể là sử dụng Định lý tách để chứng minh định lý Karush-Kuhn-Tucker,
định lý Kuhn-Tucker. Ngoài ra dùng các định lý này để chứng minh Định lý vô
hướng hóa trong tối ưu véc-tơ. Nội dung chương này chủ yếu được tổng hợp từ
các tài liệu [3], [4].
2.1. Bài toán tối ƣu
2.1.1. Phát biểu bài toán
Xét bài toán tìm
(P)
trong đó ( : là một số không gian, thông thường ),
: được gọi là miền khả thi (chấp nhận được), : là hàm mục tiêu.
2.1.2. Định nghĩa. được gọi là nghiệm tối ưu địa phương của (P) nếu
tồn tại một lân cận của sao cho
nếu
,
thì được gọi là nghiệm tối ưu toàn cục của (P).
Thông thường
(2.1)
, : là các hàm rằng buộc.
Bài toán (P) với cho bởi (2.1) được gọi là trơn nếu tất cả hàm mục
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
tiêu và các hàm ràng buộc là trơn (khả vi).
26
Nhận xét.
và tập các nghiệm tối ưu là trùng nhau.
2.1.3. Ví dụ
Qui hoạch lồi. : là tập lồi đóng
: là hàm lồi, thông thường, được cho bởi (2.1) với lồi, là tập affine.
Ví dụ (chiếu lên một tập lồi)
với y đã cho.
2.1.4. Định nghĩa. Một véc-tơ được gọi là hướng chấp nhận được của
tại nếu:
đủ nhỏ.
Ký hiệu là tập tất cả các hướng chấp nhận được của tại và
là bao đóng của nó.
2.1.5. Định nghĩa. Giả sử khả vi trên một tập mở chứa và là một điểm
cực tiểu địa phương của trên . Thì ta có:
(2.2)
Một điểm thỏa mãn (2.2) được gọi là điểm dừng của trên
lưu ý rằng một điểm dừng có thể không là một cực tiểu địa phương.
Ví dụ Xét hàm . Tại , . Vậy là điểm dừng,
nhưng không phải điểm cực tiểu địa phương.
2.1.6. Sự tồn tại nghiệm
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Xét bài toán
27
có bốn trường hợp đối với sự tồn tại của nghiệm tối ưu (toàn cục)
(không có nghiệm chấp nhận được)
.
không bị chặn dưới trên ( )
.
nhưng cực tiểu không thuộc (bị chặn dưới nên
.
không có điểm cực tiểu)
sao cho .
. Tồn tại
Câu hỏi Làm thế nào để kiểm tra những khả năng này? Nói chung, việc này
không phải là dễ dàng.
2.1.7. Định lý. Điều kiện cần và đủ để tồn tại nghiệm tối ưu toàn cục của (P) là
là đóng và bị chặn dưới.
Chứng minh. Nếu là nghiệm tối ưu thì là đóng (phần
bù của một tập mở) và rõ ràng là bị chặn dưới.
Ngược lại, giả sử là bị chặn dưới. Thì . Từ
là đóng, nghĩa là sao cho . Suy ra là một điểm
cực tiểu của trên .
2.1.8. Định lý. (Weistrass). Nếu là compact và là nửa liên tục dưới trên
, thì (P) có một nghiệm tối ưu.
2.1.9. Hệ quả. Nếu là nửa liên tục dưới trên và thỏa mãn điều kiện
bức sau
khi
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
thì có một điểm cực tiểu trên .
28
Chứng minh. Đặt với . Rõ ràng, là bị
chặn và đóng. Do vậy có một điểm tối thiểu trong và cũng là điểm cực
tiểu của trên .
2.2. Ứng dụng của định lý tách trong tối ƣu hóa
2.2.1. Điều kiện tối ưu
Câu hỏi Nếu là một nghiệm tối ưu (địa phương hay toàn cục), thì điều gì
xảy ra với ?
2.2.2. Định lý. (cho trường hợp lồi). Giả sử rằng là tập lồi khác rỗng, là
hàm lồi, khả dưới vi trên . Thì là một nghiệm tối ưu của (P) khi và chỉ khi
(2.3)
trong đó ký hiệu hình nón pháp tuyến của tại .
Chứng minh. Đặt là hàm chỉ tiêu của , nghĩa là nếu và
nếu . Vậy bài toán (P) có thể được biến đổi tương đương thành
bài toán không giới hạn
. (UP)
Do đó là nghiệm tối ưu của (UP) khi và chỉ khi
.
Sử dụng Định lý Moreau-Rackafellar ta có thể viết
.
từ
,
ta có
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
.
29
2.2.3. Hệ quả. Nếu và (các tập nghiệm tối ưu của (P)),
thì . Trong trường hợp đặc biệt, nếu là khả vi và C là toàn bộ
không gian, thì .
Hãy xem xét bài toán (P) định nghĩa là:
phụ thuộc vào:
trong đó và , , : . Định nghĩa hàm Lagrange
bằng cách lấy:
.
Ta gọi (P) là bài toán lồi nếu là lồi và tất cả các hàm là lồi,
là affine.
2.2.4. Định lý. (Karush-Kuhn-Tucker). Giả sử (P) là một bài toán lồi. Nếu
là một nghiệm tối ưu cho phương trình (P), thì tồn tại ( ) và
không đồng thời bằng 0 sao cho
(đạo hàm triệt tiêu)
(điều kiện bù).
Hơn nữa nếu và điều kiện Slater
được thỏa mãn các hàm affine là độc lập tuyến tính trên , thì
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
và hai điều kiện trên là đủ cho trở thành nghiệm tối ưu của (P).
30
Chứng minh. Giả sử rằng là một nghiệm tối ưu của (P). Ta đặt
.
Từ lồi, là các hàm lồi, là hàm affine trên , nên tập là một
tập lồi, đóng khác rỗng trong .
Hơn nữa , như vậy tồn tại một nghiệm chấp nhận được sao cho
. Điều này mâu thuẫn với thực tế rằng là một nghiệm tối ưu
của bài toán (P). Vậy theo Định lý tách, tồn tại
, không đồng thời bằng 0 sao cho
. (2.4)
Lưu ý rằng nếu thì bằng cách lấy , ta có
. Bằng thực tế này ta có thể thấy rằng . Ngoài
ra, với và , ta lấy , ,
và sử dụng (2.3) và cho ta có được:
. (2.5)
Hoặc
.
Điều kiện đạo hàm triệt tiêu được chứng minh. Để chứng minh điều kiện
bù, ta thấy rằng, từ là khả thi, với mỗi . Nếu có một sao cho
, thì với mỗi , ta có
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
( ở vị trí thứ ).
31
Thay vào (2.4) và cho , ta có . Nhưng từ suy ra
. Vậy .
Bây giờ ta chứng minh điều kiện đủ. Trước hết ta có . Thật vậy,
nếu ngược lại , theo điều kiện đạo hàm triệt tiêu và điều kiện bù, ta có
. (2.6)
Nhưng từ nên với mỗi phải tồn tại , hoặc nếu ,
thì với mỗi phải tồn tại . Ta xét hai trường hợp sau:
vào bất đẳng thức (2.6) ta có:
. Trường hợp 1: Thay thế
,
suy ra vô lý.
. Trường hợp 2: Ta có.
Từ và là affine với mọi , dẫn đến , .
Bây giờ sử dụng giả thiết là độc lập tuyến tính trên , ta có thể kết luận
với mỗi , điều này mâu thuẫn với giả thiết và không đồng thời
bằng 0. Vậy . Từ bằng cách chia hai vế của (2.5) cho ta có
thể giả thiết rằng hàm Lagrange có dạng
.
Lại giả sử điều kiện đạo hàm triệt tiêu và điều kiện bù ta có, với mỗi
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
nghiệm khả thi ,
32
.
Điều này dẫn đến là nghiệm tối ưu của (P)
2.2.5. Định lý. (Kuhn-Tucker). Cho , , khả vi liên tục. Gọi là nghiệm
tối ưu của (P) và thỏa mãn điều kiện bị chặn thì tồn tại tích Lagrange
(2.7)
sao cho:
(2.8)
(điều kiện bổ xung). (2.9)
Nếu (P), là lồi với mỗi và là affine với mỗi nghĩa là (P) là một
qui hoạch lồi, thì bất kỳ thỏa mãn (2.7), (2.8), (2.9) đều là một nghiệm tối
ưu của (P).
Chứng minh. Sử dụng triển khai Taylor, ta có
.
Ta có với mỗi . Từ , ta có
với mỗi . Sử dụng bổ đề Farkas với ma trận có
các hàng , ta có các số
và sao cho
.
Lấy với mỗi và với mỗi ta có (2.8) và (2.9).
Bây giờ ta giả sử là lồi và là affine với mỗi . Ta sẽ chứng minh
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
(2.7), (2.8) và (2.9) là điều kiện đủ để là nghiệm tối ưu của bài toán (P).
33
Thật vậy, nếu không là nghiệm tối ưu thì tồn tại sao cho
. Đặt . Thì ta có
.
Mặt khác, với mỗi , ta có , nếu .
Đồng thời từ , ta có
.
Do đó
.
Với hàm theo tính chất affine, với mọi , ta có
như vậy, với bất kỳ
,
kết hợp lại với nhau ta có
.
Điều này mâu thuẫn với (2.8)
Lƣu ý. Ta định nghĩa (hàm Lagrange).
Theo điều kiện (2.7) có thể viết dưới dạng
Ví dụ Xét bài toán
, với điều kiện ,
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
trong đó .
34
Đây là bài toán qui hoạch lồi với hàm mục tiêu lồi chặt nên nó có một
nghiệm cực tiểu duy nhất. Trong bài toán này, , , ,
, .
. Giải hệ
.
Từ hai phương trình đầu tiên của hệ này suy ra .
Nếu thì ta có . Vì điểm không phải là điểm
chấp nhận được của bài toán đang xét nên kết luận rằng .
Do nên từ phương trình thứ ba của hệ này ta có . Kết
hợp với sự kiện suy ra .
2.2.6. Tính đối ngẫu Lagrange
Tính đối ngẫu là một chủ đề quan trọng trong tối ưu hóa. Có một số loại
đối ngẫu, nhưng tính đối ngẫu Lagrange được sử dụng rộng rãi nhất. Tính đối
ngẫu Lagrange là dựa trên các hàm Lagrange. Để đơn giản chúng ta xét các bài
toán sau đây:
(P)
trong đó là một tập khác rỗng (thông thường, là toàn bộ không gian).
Với bài toán này ta định nghĩa một bài toán tối ưu khác có dạng
(D)
chính xác hơn nó cần được viết dưới dạng
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
(D)
35
trong đó là một tập nào đó trong .
2.2.7. Định nghĩa. Ta nói rằng (D) là đối ngẫu của (P) nếu với mỗi điểm khả
thi của (P) và của (D) ta có
.
Nếu tồn tại một điểm khả thi của (P) và của (D) sao cho
, thì ta nói (P) và (D) là cặp đối ngẫu chính xác hoặc (D) là bài
toán đối ngẫu chính xác của (P) (và ngược lại).
Vậy, làm thế nào để định nghĩa một bài toán đối ngẫu và khi nào thì nó
là chính xác?
Với bài toán (P) ta định nghĩa hàm Lagrange như sau
và lấy
. (LD)
Thì ta định nghĩa bài toán đối ngẫu
2.2.8. Định lý. Bài toán (LD) là một bài toán đối ngẫu của (P).
Chứng minh. Dễ dàng thấy rằng, nói chung một cặp đối ngẫu là không chính
xác. Ví dụ: Bài toán
là bài toán đối ngẫu Lagrange của chính nó, không chính xác.
2.2.9. Định lý. (đối ngẫu chính xác). Giả sử rằng
(i) (P) có một nghiệm tối ưu
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
(ii) là tập lồi, đóng và với mỗi là liên tục và lồi trên .
36
(iii) Điều kiện Slater được thỏa mãn, nghĩa là tồn tại sao cho
với mỗi .
Thì (P) và (D) là cặp đối ngẫu chính xác.
Chứng minh. Đặt
xét
.
Từ và là lồi với mỗi , là lồi. Đặt là một nghiệm tối ưu của (P).
Thì . Theo Định lý tách tồn tại trong sao cho:
.
Vì tính liên tục của và , bất đẳng thức đúng với mỗi
(đóng kín của ). Từ ,
. (2.10)
Ta thấy . Thật vậy, giả sử có một giá trị sao cho . Đặt
. Thì với mỗi ( là véc-tơ đơn vị thứ
). Áp dụng (2.10) với và cho ta dẫn tới mâu thuẫn. Vậy
. Bằng cách tương tự ta có thể thấy . Nhưng vì thì
. Trong trường hợp này từ (2.10) ta có
.
Điều này mâu thuẫn với điều kiện Slater.
Sử dụng định nghĩa của ta có . Như vậy, từ (D) là đối
ngẫu của (P), chúng phải là đối ngẫu chính xác.
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Ví dụ Trong cho các hàm
37
.
Xét bài toán
. (P)
Lập bài toán đối ngẫu
.
Giả sử khi đó hệ phương trình có nghiệm là: .
Khi đó ta có
.
Xét
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
ta có
38
do xét nên ta được .
.
Để tính ta giải
bằng cách cho
.
2.2.10. Tối ưu véc-tơ
Trong phần này ta nghiên cứu véc-tơ (nhiều mục tiêu) tối ưu hóa. Xét
bài toán:
(VP)
trong đó (ở đây có p - mục tiêu).
2.2.11. Định nghĩa. Một véc-tơ được gọi là một nghiệm (toàn cục) hiệu
quả (Pareto-nghiệm tối thiểu) của (VP) nếu không tồn tại sao cho
và
Nếu không tồn tại sao cho thì được gọi là
nghiệm (toàn cục) hiệu quả yếu hay là nghiệm tối thiểu của (VP).
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Câu hỏi: Làm thế nào để giải quyết các bài toán tối ưu hóa véc-tơ?
39
2.2.12. Định lý. Cho . Thì với mọi nghiệm toàn cục tối thiểu của bài
toán một mục tiêu
là một nghiệm tối ưu toàn cục Pareto của (VP).
Chứng minh. Giả sử là nghiệm của .
Nếu không phải là nghiệm tối ưu Pareto, thì
,
Do , nên
Cộng lại ta được
Ví dụ: Trong xét (p=3 có ba mục tiêu) biểu thị
: Biểu thị cho học lực của học sinh x trong một lớp học,
: Biểu thị cho đạo đức của học sinh x trong một lớp học,
: Biểu thị cho khức khỏe của học sinh x trong một lớp học
và giả sử có trọng số thì ta có
Câu hỏi: Có đúng là với mọi nghiệm tối ưu Pareto x của (VP) tồn tại một trọng
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
số sao cho x là một nghiệm tối ưu của ?
40
2.2.13. Định lý. Giả sử (VP) là một bài toán tối ưu lồi (có nghĩa là F và C là lồi).
Thì với mọi nghiệm Pareto-tối ưu của (VP) tồn tại một sao cho
.
Chứng minh. Đặt
Đặt (bao lồi).
Ta thấy rằng (không dương). , từ . Đặt
thì tồn tại sao cho
, .
Từ , tồn tại sao cho với mọi .
Lấy . Từ F là lồi, ta có
.
Do vậy, từ là hiệu quả dẫn đến , do đó y=0. Vậy .
Theo Định lý tách có sao cho
(2.11)
(2.12)
Bằng cách chia cho ta có thể giả sử rằng .
Từ (2.11) ta có thể thấy trong khi đó từ (2.12) và định nghĩa của K
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
dẫn đến:
41
nghĩa là là một nghiệm tối ưu của .
KẾT LUẬN
Luận văn đã trình bày những vấn đề sau:
1. Tổng hợp một số kiến thức cơ bản của Giải tích lồi, tính chất của các
tập lồi, hàm lồi; phát biểu và chứng minh các Định lý tách.
2. Sử dụng các Định lý tách để chứng minh Định lý Karush-Kuhn-
Tucker, Định lý Kuhn-Tucker và Định lý đối ngẫu Lagrange. Cuối cùng luận
văn trình bày Định lý vô hướng hóa cho bài toán tối ưu véc-tơ lồi, cách chứng
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
minh dựa vào Định lý tách 1.
42
TÀI LIỆU THAM KHẢO
Tiếng Việt
1. Đỗ Văn Lưu, Phan Huy Khải (2000), Giải tích lồi, Nhà xuất bản Khoa
học và Kỹ thuật
2. Lê Dũng Mưu, Nguyễn Văn Hiền, Nguyễn Hữu Điển, Nhập môn Giải
tích lồi ứng dụng, Nhà xuất bản Đại học Quốc gia Hà Nội (sẽ ra).
3. Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi
tuyến, Nhà xuất bản Đại học Quốc gia Hà Nội.
Tiếng Anh
4. Stephen Boys and Lieven Vandenberghe (2004), Convex Optimization,
http://www.lrc.tnu.edu.vn
Số hóa bởi Trung tâm Học liệu – ĐHTN
Cambridge University press, New York.
