Luận văn Thạc sĩ Toán học: Một vài ứng dụng của định lý tách trong tối ưu hóa

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

28
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung luận văn này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một vài ứng dụng của định lý tách trong tối ưu hóa

ĐẠ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 http://www.lrc.tnu.edu.vn
ĐẠ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 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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. Thái Ngyên, tháng 2 năm 2015 Tác giả Nguyễn Trần Thành Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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 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 http://www.lrc.tnu.edu.vn
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 KẾT LUẬN....................................................................................................... 41 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iv BẢNG KÝ HIỆU n Không gian Euclide n - chiều trên trường số thực;  Trục số thực; xi Tọa độ thứ i của x; aT Véc-tơ hàng (chuyển vị của a) 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 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; coC 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; f ( x) Dưới vi phân của f tại x; f ( x) Đạ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* Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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 Hình 1.5: Đồ thị hàm lồi ( C  ) ................................................................... 23 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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 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 http://www.lrc.tnu.edu.vn
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  n là tập hợp tất cả các véc-tơ x  n có dạng: x n x a b, , , 1 . Đoạn thẳng nối hai điểm a và b trong  n là tập hợp các véc-tơ x có dạng x n x a b, 0, 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 0 j 1,..., k , j 1. j 1 j 1 Tương tự, x là tổ hợp a-phin của các điểm (véc-tơ) x1, x2 ,..., xk nếu Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
3 k k j x j x , j 1. j 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 a- phin 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ở. 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 đề. M 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. Chứng minh. Giả sử M là tập a-phin và a M . Khi đó thì L M a là một không gian con. Vậy L M a . Ngược lại, nếu L M a với L là không gian con, thì với mọi x, y M ,  ta có Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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 )( x a ) ( y a) L . Vậy (1 )x y M. Suy ra M là tập a-phin. Không gian con L ở trên là duy nhất. Thật vậy, nếu L M a và M a' L' , thì L' M a' a L a' L (a a ' ) Do a ' M a L , nên a ' a L . Suy ra L' 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 (b1,..., bm ) thì hệ trên viết được là: D: x  n Ax b . Do một phương trình a, x b có thể viết một cách tương đương dưới dạng hai bất phương trình a, x b, a, x b, Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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 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  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 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ó (i). Do C là 1 một tập lồi, nên x, y C , thì (x y ) C . Vậy theo (i) ta có x y C . 2 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
6 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”. 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, 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ó Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
7 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 C không đóng mệnh đề trên không đúng. Ví dụ Trong  2 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 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  n là một tập lồi và x C . Ký hiệu N C ( x) : w w, y x 0, y C . 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 w, y x 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 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  n 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 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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) d  n dk d , tk  0 : x tk d k C k . 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 C: x n aj ,x b j , j 1,..., m . Với x C , đặt J ( x) : j a j, x bj , gọi là tập chỉ số tích cực tại x. Khi đó TC ( x) y n a j, y 0, j J ( x) , N C ( x) cone(a j , 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 B: xx A, x B , (ii) A B: xx a b, a A, b B , ,  (iii) AxC : x n 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.  1.1.11. Định nghĩa. Một tập F C được gọi là một diện của tập lồi C nếu F là tập lồi có tính chất là: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
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 0 . 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 x 0 C 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 x, y C sao cho x0 x (1 ) y với 0 1. 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  n là một tập hợp các điểm có dạng x  n aT x , trong đó a  n là một véc-tơ khác 0 và . Véc-tơ a thường được gọi là véc-tơ pháp tuyến của siêu phẳng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
10 1.1.13. Định nghĩa. Cho x0 C . Ta nói aT x là siêu phẳng tựa của C tại x 0 , nếu aT x , aT x 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 là một diện của C; diện này là không gian tầm thường khi và chỉ khi H riC . Chứng minh. Gọi F C H . Do C và H lồi, nên F lồi. Giả sử siêu phẳng tựa H có dạng H: x t, x và t, x x C. Để chứng tỏ F là một diện của C, hãy cho a, b C , x a (1 )b với mọi 0 1 và giả sử x F . Khi đó t, x t, a (1 ) t,b . Do a, b C nên t, x , t, b . Từ đây suy ra t, a , t,b . 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.  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. 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 http://www.lrc.tnu.edu.vn
11 x C bất kỳ. Xét đường thẳng : x u với u 0 . 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, F H 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ì C coV (C ) coneU (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 x u, 0 với u 0 sao cho cắt biên của C tại một điểm v . Vậy v x u . Ta có hai trường hợp sau: a) Trường hợp u U (C ) . 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 v 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 và tập F : H C 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ó: v F coV ( F ) coneU ( F ) . Do F là một diện của C, nên v F coV ( F ) coneU ( F ) coV (C ) coneU (C ) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
12 Do u U ( F ) và x v u với 0 , nên từ đây suy ra x v 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 (không nhất thiết lồi) và y là một véc-tơ bất kỳ, đặt dC ( y ) : inf x C x y ta nói dC ( y ) là khoảng cách từ y đến C. Nếu tồn tại số C sao cho dC ( y) y , 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 pC ( y) của y trên C sẽ là nghiệm của bài toán tối ưu 1 2 min x y x C . x 2 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 2 cực tiểu của hàm toàn phương x y trên C. Như thường lệ, sẽ ký hiệu 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 , thì dC ( y ) hữu hạn, vì 0 dC ( y) y x với mọi x C . Cho 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 http://www.lrc.tnu.edu.vn
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 y  n , C hai tính chất sau đây là tương đương: a) pC ( y) , b) y NC ( ) (ii) Với y  n , hình chiếu của pC ( y) của y trên C luôn tồn tại và duy nhất. (iii) Nếu y C , thì pC ( y) y, x pC ( y) 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à pC ( y) y, x pC ( y) 0, x C , và pC ( y) y, y pC ( y) 0. (iv) Ánh xạ y pC ( y) có các tính chất sau: a) pC ( x) pC ( y) x y x, y . (tính không giãn) 2 b) pC ( x) pC ( y), x y pC ( x) pC ( y) , (tính đồng bức hay đơn điệu ngược) Chứng minh. (i) Giả sử có a). Lấy x C và (0,1) . Đặt x : x (1 ) . Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn