🔙 Quay lại trang tải sách pdf ebook Giáo trình tối ưu phi tuyến Ebooks Nhóm Zalo GT.00000 I IJC VÀ ĐÀO TẠO 941 ] 1ÁI N G U Y Ê N TRẦN VŨ THIỆU - N G U YỄN THỊ THU THỦY 'ÉN u O K I Q D B H* HQI NHÀ XUẤT BẢN ĐẠI HỌC Q U Ố C GIA HÀ NỘI BỘ G IÁ O DỤC VÀ Đ À O TẠ O ĐẠI HỌC THÁI N G U Y Ê N TRẦN VŨ THIỆU - NGUYỄN THỊ THU THỦY GIÁO TRÌNH TỐI 11 PH I TUYẾN NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA HÀ NỘI SÁCH ĐƯỢC XUẤT BẢN BỜI sự TÀI TRỢ CỦA Dự ẤN CIÁO DỤC ĐẠI HỌC 2 MỤC LỤC T rang Lời nói đ ầ u ..................................................................................................13 Phán 1. LÝ THUYẾT CHUNG C hương 1. BÀI TO ÁN T ố i ư u 1.1. Khái niệm và định nghĩa...................................................................17 1.2. Ví dụ .....................................................................................................20 1.3. Phàn loại bài toán tối ưu ..................................................................25 1.4. Sự tồn tại nghiệm tối ư u ...................................................................27 1.4.1. Hàm nửa liên tục dưới ..........................................................28 1.4.2. Điều kiện bức .........................................................................30 Dài t ậ p ..........................................................................................................35 C hương 2. G IẢ I T ÍC H LỚ I 2.1. Tập lồi....................................................................................................37 2 .1 .1. Tập afin và bao afin .............................................................. 37 2.1.2. Tập lồi, nón lồi và bao lồi ....................................................41 2.1.3. Phần trong tương đối và bao lồi dóng ...............................46 2. ỉ .4. Các định lý tách tập lồi .........................................................49 2.1.5. Phương lùi xa và nón lùi xa .................................................55 2.1.6. Siêu phảng tựa, diện, điểm cực biên và phương cực biên.......57 3 2.1.7. Biểu diễn tập lồi qua các điểm cực biên và phương cực b iê n ....................................................................................59 2.1.8. Tập lồi đa diện ........................................................................ 60 2.2. Hàm lồ i...................................................................................................63 2.2.1. Hàm lồi và hàm lõm .............................................................. 63 2.2.2. Hàm lồi liên t ụ c .......................................................................68 2.2.3. Hàm lồi khả v i.......................................................................... 70 2ắ2.4. Dưới vi phán ............................................................................ 74 2.2.5. Hàm lồi mạnh .......................................................................... 78 Bài tập .......................................................................................................... 80 Chương 3. Đ IỂU K IỆ N T ố i Ư u 3.1. Bài toán tối ưu không ràng buộc......................................................85 3.2. Bài toán tối ưu với ràng buộc tập ....................................................91 3.2.1. Nón chấp nhận được và nón tiếp x ú c .................................92 3.2.2. Điều kiện cần tối ưu cấp 1 và cấp 2 ................................... 94 3.2.3. Điều kiện đủ tối ưu cấp 1 và cấp 2 ..................................... 97 3.2.4. Điều kiện tối ưu cấp 0 dối với bài toán qui hoạch lồ i......100 3.3. Bài toán tối ưu với ràng buộc hiển ......................... 103 3.3.1. Nội dung bài toán ....................................... 103 3.3.2. Điều kiện chính q u i.......................................... Ị04 3.3.3. Điều kiện tối ưu cấp 1 .......................................... J0 7 3.3.4. Điều kiện tối ưu cấp 2 ....................................................... ] Ị J B ài tậ p .......................................................................................................... 118 4 C hương 4. BÀI TO ÁN Đ ố i NGAU 4.1. Đối ngẫu L ag ran g e ........................................................................ 122 4.1.1. Cặp bài toán đối ngẫu ........................................................122 4.1.2. Đối ngẫu y ế u ........................................................................ 125 4.1.3. Đối ngẫu mạnh ....................................................................126 4.1.4. Ràng buộc đẳng th ứ c ......................................................... 128 4.1.5. Qui hoạch tuyến tính ............................ .............................129 4.1.6. Qui hoạch toàn phương....................................................... 129 4.2. Điểm yên ngựa ............................................................................... 130 4.2.1. Hàm Lagrange và điểm yên ngựa.....................................130 4.2.2. Lời giải tối ưu và điểm yên n g ự a .....................................131 Bài tập .......................................................................................................134 Phần 2ệ PHƯƠNG PHÁP TÌM c ự c TIỂU KHÔNG RÀNG BUỘC Chương 5. TÌM c ự c TlỂU HÀM MỘT BIẾN 5.1. Phương pháp tìm theo ti a .............................................................. 135 5.1.1. Tìm chính xác và tìm gần đúng theo tia ........................135 5.1.2. Phương pháp lặp N ew to n ...................................................140 5.2. Phương pháp khử liên tiếp ............................................................142 5.2.1. Phương pháp Fibonacci ..................................................... 143 5.2.2. Phương pháp lát cắt v à n g ...................................................148 5.3. Phương pháp nội suy ......................................................................15 4 5 5.3.1. Nội suy bậc hai .....................................................................154 5.3.2. Nội suy bậc ba .....................................................................157 Bài tập ....................................................................................................... C hương 6. PHƯ Ơ N G PH Á P K H Ô N G DÙNG ĐẠO H À M 6.1. Phương pháp Hooke - Je e v e s........................................................167 6.2. Phương pháp Nelder - M e a d ......................................................... 173 Bài t ậ p .........................................................................................................181 C hương 7. PH Ư Ơ N G PH Á P G R A D IEN T 7.1. Phương pháp hướng dốc nhất ....................................................... 183 7.1.1. Nội dung phương pháp ....................................................... 183 7.1.2. Sự hội tụ của phương pháp g rad ie n t................................ 184 7.1.3. Các dạng khác của phương pháp gradient .....................189 7.2. Phương pháp N ew to n ...................................................................... 194 7.2.1. Nội dung phương pháp ....................................................... 194 7.2.2. Sự hội tụ của phương pháp Newton suy rộng .............. 197 7.2.3. Cải biên phương pháp Newton suy r ộ n g ........................ 200 7.3. Phương pháp tựa N ew to n ................................................................201 7.3.1. Nội dung phương pháp ....................................................... 201 7.3.2. Phương pháp Davidon - Fletcher - Powell .....................201 7.4. Phương pháp gradient liên hợp .................... 209 7.4.1. Hướng liên hợp ................................................ 209 7.4.2. Phương pháp Fletcher - Reeves ............................ 212 Bài tập ........................................................................................................222 6 Phần 3ế PHƯƠNG PHÁP TÌM c ự c TIỂU CÓ RÀNG BUỘC C hương 8. PHƯ Ơ N G PH Á P TRỰ C T IẾ P 8.1. Phương pháp hình học .................................................................. 224 8.2. Phương pháp nhân tử L agrrange................................................. 229 8.2.1. Ràng buộc đẳng thức.......................................................... 230 8.2.2. Ràng buộc không â m ......................................................... 236 8.3. Phương pháp dùng điều kiện KKT ............................................ 240 8.3.1. Bài to á n ..................................................................................240 8.3.2. Các ví d ụ ............................................................................... 243 8.3.3. Bài toán tối ưu lồi ...............................................................249 Bài tậ p ........................................................................................................ 253 C hương 9. PH Ư Ơ N G PH Á P TUYÊN TÍN H HÓA 9.1. Tuyến tính hóa ràng b u ộ c .............................................................255 9.1.1. Bài toán và ý tưởng phương pháp g iả i............................ 255 9.1.2. Thuật toán siêu phẳng cắt Kelley ................................... 255 9.1.3. Một sô' ví d ụ ..........................................................................258 9.2. Tuyến tính hóa mục tiê u ................................................................263 9.2.1. Bài toán và các giả th iế t.....................................................263 9.2.2. Thuật toán Frank - Wolfe ................................................. 264 9.2.3. Ví dụ minh h ọ a .................................................................... 266 B ài t ậ p ........................................................................................................271 7 Chương 10. PHƯƠNG PHÁP HƯỚNG CHẤP NHẬN Đ ư ợ c 10.1. Ràng buộc phi tu y ế n .....................................................................273 10.1.1. Bài toán và ý tường phương pháp g iả i.......................... 273 10.1.2. Chọn điểm xuất phát và hướng giảm ở mỗi bước .....274 10.1.3. Thuật toán Zoutendijk ......................................................277 10.2. Ràng buộc tuyến tín h ....................................................................282 10.2.1. Bài to á n .................................................................................282 10.2.2. Thuật toán giải bài toán tối ưu với ràng buộc tuyến tín h ................................................................................. 286 10.3. Phương pháp chiếu Rosen ...........................................................292 10.3.1. Bài to á n .................................................................................292 10.3.2. Mô tả khái quát thuật to á n ...............................................292 10.3.3. Thuật toán chi t i ế t .............................................................. 294 B ài tậ p ..........................................................................................................299 C hương 11. PH Ư Ơ N G P H Á P PH Ạ T 11.1. Phương pháp hàm c h ắ n .................................................................301 11.1.1. Bài toán và ý tưởng thuật toán ........................................301 11.1.2. Hàm chắn lôga và hàm chắn nghịch đảo .....................304 11.1.3. Đường trung tâ m .................................................................309 11.1.4. Nhân tử Lagrange .............................................................. 311 11.1.5. Trường hợp bài toán không lồi .......................................316 11.2. Phương pháp hàm phạt .................................................................3 1 5 8 l l ể2.1. Hàm phạt bậc hai ..............................................................317 11.2.2. Hàm phạt chính x á c ......................................................... 323 11.2.3. Hàm phạt Lagrange gia tă n g .......................................... 327 Bài tậ p ........................................................................................................331 Trả lời bài tập ..........................................................................................333 Tài liệu tham khảo...................................................................................341 Các từ k h ó a ...............................................................................................343 9 MỘT SỐ KÝ HIỆU TOÁN HỌC R tập số thực (hay đường thẳng thực) r không gian Euclid n chiều X e c X thuộc tập c (x là một phần tử của tập C) x í C X không thuộc tập c (x không phải là phần tử của tập Q 0 tập rỗng (tập không chứa phần tử nào) C + D tổng của tập c và tập D C - D hiệu của tập c và tập D c X D tích của tập c và tập D C u D hợp của tập c và tập D C n D giao của tập c và tập D C c D c là tập con của tập D C c D c là tập con (có thể bằng) của tập D ICI số phần tử của tập c , xTy tích vô hướng của X và y (hai véctơ có cùng số chiều) llxll chuẩn Euclid của véctơ X các tọa độ của điểm hay thành phần của véctơ X X |,x 2,....... x„ (dùng chỉ số dưới) x \ X2, X3, ... liệt kè các véctơ có cùng số chiều (dùng chỉ số trẽn) [a, b] đoạn thẳng nối hai điểm (véctơ) a và b B(0,1) hình cầu đơn vị mở (tâm 0, bán kính 1) B (0 .1) hình cầu đơn vị đóng (tâm 0, bán kính 1) 10 a f f E bao afin của tập E conv E bao lồi của tập E conv E bao lồi đóng của tập E cone E bao nón của tập E dim c thứ nguyên (hay sô' chiều) của tập c int c phán trong của tập c ri c phần trong tương đối của tập c ÕC biên tương đối của tập c rec c nón lùi xa của tập c c bao đóng của tập c c tập đỉnh của tập lồi đa diện c fẼmax giá trị cực đại của hàm f fầmin giá trị cực tiểu của hàm f fÁopl giá trị tối ưu của hàm f ^max điểm (nghiệm, lời giải) cực đại của bài toán tìm cực đại ^min điểm (nghiệm, lời giải) cực tiểu của bài toán tìm cực tiểu xop. điểm (nghiệm, lời giải) tối ưu của một bài toán tối ưu f (Xo, d) đạo hàm theo hướng d của hàm f tại điểm Xo f ' f ' 1xi ’ äi đạo hàm riêng (cấp một) của hàm f theo biến X, f ' , f- XjXj ’ ij đạo hàm riêng cấp hai của hàm f theo biến X; và biến X dom f miền hữu hiệu của hàm f epi f tập trên đồ thị của hàm f hypo f tập dưới đổ thị của hàm f ổf(x°) dưới vi phàn của hàm f tại điểm Xo 11 ỗc(x) hàm chỉ của tập lồi c dc(x) hàm khoảng cách từ điểm X tới tập lồi c sc(x) hàm tựa của tập lồi c Fd(x°) nón chấp nhận được của tập D tại điểm x" T d(xh) nón tiếp xúc với tập D tại điểm x° S(x°) nón chấp nhận được tuyến tính hóa tại điểm x° Nc(x°) nón pháp tuyến trong của tập c tại điểm XH - N c ( x H) nón pháp tuyến ngoài của tập c tại điểm x° V f(x) véctơ gradient của hàm f tại điểm X v 2f(x), ma trận Hessian của hàm f tại điểm X Hf(x) 0 ma trận A xác định dương A -< 0 ma trận A xác định âm A > 0 ma trận A nửa xác định dương A < 0 ma trận A nửa xác định âm rank A hạng của ma trận A A e IKmXn A là ma trận m hàng, n cột (m a trận cấp m xn) At ma trận chuyển vị của ma trận A A-' ma trận nghịch đảo của ma trận A I„ ma trận đơn vị cấp n 12 LỜI NÓI ĐẦU Tối ưu hóa (Optimization) là một môn toán học ứng dụng đã và đang được nghiên cứu, giảng dạy và học tập ở nhiều trường đại học, cao đẳng trong nước, từ Bắc tới Nam, cho sinh viên toán học, tin học, kinh tế và kỹ thuật. Trong lý Ihuyết tối ưu hóa thì phần quan trọng và được phát triển hoàn thiện nhất là tối ưu tuyến tính, còn gọi là qui hoạch tuyến tính. Phần khó hơn và ít được dề cập dến là tối ưu phi tuyến (không tuyến tính), còn gọi là qui hoạch phi tuyến. Có nhiều sách và giáo trình viết về qui hoạch tuyến tính, song sách về tối ưu phi tuyến còn khá khiêm tốn. Giáo trìnli Tối ưu phi tuyến (Nonlinear Optimization) được viết theo đề xuất của Khoa Toán - Tin, Trường Đại học Khoa học - Đại học Thái Nguyên. Đây là một tài liệu tham khảo bàng tiếng Việt về tối ưu phi tuyến, nhằm góp phần thúc đẩy việc nghiên cứu, giảng dạy và học tập môn tối ưu hóa nói chung ở Khoa và Trường. Sách được viết trên cơ sở chỉnh lý, bổ sung và hoàn thiện các bài giáng về tối ưu do các tác giả đã dùng làm tài liệu giảng dạy trong nhiều năm cho nhiều đối tượng sinh vién và học viên cao học ờ một số trường đại học và viện nghiên cứu: Trường Đại học Khoa học Trường Đại học Sư phạm và Trường Đại học Kỹ thuật Công nghiệp - Đại học Thái Nguyên, Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội, Trường Đại học Bách khoa Hà Nội, Trường Đại học Kinh tế Quốc dân Hà Nội, Viện Toán học, v.v ... 13 Cuốn sách này tập trung trình bày những nội dung cơ bản của lý thuyết tối ưu phi tuyến và các phương pháp thường dùng đề giải các bài toán tối ưu phi tuyến có hay không có ràng buộc. Lý thuyết và phương pháp tối ưu tuyến tính đã được viết trong Giáo trình lối IIÌI tuyến tính do Nhà xuất bản Đại học Quốc gia Hà Nội in năm 2004. Nội dung cuốn sách được chia làm ba phần chính, mỗi phần gồm ba hoặc bốn chương, một sô' chương có thể đọc độc lập với nhau, tùy theo nhu cầu học tập. • Phần 1 gồm bốn chương đầu, trình bày lý thuyết chung về các bài toán tối ưu: nội dung và ý nghĩa bài toán, các định lý về sự tồn tại nghiệm tối ưu của bài toán, các điểu kiện cần và đù của tối ưu (điều kiện cấp 0, cấp 1 và cấp 2), các kết quả chính về giải tích lồi thường dùng trong tôi ưu hóa (tập afin, tập lồi, nón lồi, hàm lồi và hàm lõm cùng các tính chất cơ bán của chúng). Guối Phần 1 là lý thuyết đối ngẫu Lagrange. • Phần 2 gồm ba chương 5, 6 và 7, giới thiệu các phương pháp tìm cực tiểu không ràng buộc của hàm, bao gồm các phương pháp tìm cực tiểu của hàm một biến số (phương pháp lập Newton, Fibonacci, lát cắt vàng, nội suy bậc hai và bậc ba), các phương pháp không dùng đạo hàm tìm cực tiểu của hàm nhiều biến (phương pháp Hooke-Jeeves, phương pháp Nelder-M ead) và các phương pháp gradient đòi hỏi sử dụng các đạo hàm riêng cáp một và cấp hai của hàm (phương pháp gradient, gradient liên hợp, phương pháp Newton, tựa Newton). • Phần 3 gồm bốn chương 8 - 1 1 . trình bày các phương pháp tìm cực tiểu có ràng buộc của hàm nhiều biến, trong đó có phương pháp hình học, phương pháp nhân tứ Lagrange, phương pháp dùng điêu kiện KKT, phương pháp tuyên tính hóa hàm m ục tiêu hay hùm ràng buộc, các phương pháp hướng chấp nhận được và các phương pháp phạt điếm trong và điểm ngoài, dùng các hàm chắn và hàm phạt. 14 Cuối sách liệt kê một số tài liệu tham khảo chính đã sử dụng, trả lời bài tập ở các chương và danh sách các từ khóa để tra cứu. Do số trang hạn chế nên cuốn sách này không trình bày một số nội dung chuyên sâu của tối ưu phi tuyến như tối ưu rời rạc (hay tối ưu tổ hợp), tối ưu toàn cục, tối ưu mạng, tối ưu đa mục tiêuắ.. Các vấn để này là chủ đề trong các tài liệu khác. Sách viết có sử dụng một sô' tài liệu mới in năm 2004 - 2009, bổ sung và làm chính xác một số sự kiện về giải tích lồi mà sách hiện có không nêu rõ hoặc nêu thiếu chính xác (Định lý 1.4, Định lý 2.16 và Hệ quả 2.6, Định lý 2.26 - 2.27 và Hệ quả 2.9); cố gắng đưa ra các chứng minh ngắn gọn, trực tiếp cho nhiều sự kiện quen biết trong lý thuyết tối ưu (Định lý Carathéodory, Định lý tách các tập lồi, các định lý điểu kiện tối ưu cấp 2); đưa vào một số nội dung ít quen biết (điều kiện tối ưu cấp 0, dưới vi phân của hàm lồi và tối ưu với hàm lồi không khả vi ...)• Cách trình bày khá trực quan các kết quả lý thuyết trừu tượng, với nhiều hình vẽ minh họa và nhiều ví dụ số cụ Ihể giúp người đọc dẻ hiểu, dễ vận dụng. Các thuật toán trình bày có kèm theo sơ đồ khối, tiện cho lập trình trên máy tính. Cuối mỗi chương đều có các bài tập với đầy đủ đáp án, nhằm giúp bạn đọc tự ôn luyện và kiểm tra kiến thức đã học. Cũng có thể sử dụng bài tập làm các bài kiểm tra giữa môn hoặc cuối môn học. Có thể dùng sách này làm tài liệu giảng dạy (dùng cho giáo viên), tham khảo và học tập (dùng cho sinh viên và học viên cao học) vể một số môn chuyên đề gần nhau như: Giải tích lồi, Lý thuyết tối ưu, Qui hoạch phi tuyến, Phương pháp giải số bài toán cực trị, v.v... Các tác giả xin chân thành cảm ơn GS.TSKH Lê Dũng Mưu (Viện Toán học) và PGS.TS Nguyễn Thị Bạch Kim (Trường Đại học Bách khoa Hà Nội) đã dành không ít thời gian và công sức đọc kỹ bủn thảo, góp nhiều ý kiến xác đáng và bổ ích, giúp hoàn thiện cuốn 15 sách này. Các tác giả cũng xin chân thành cảm ơn Ban chủ nhiệm Khoa Toán - Tin, Ban lãnh đạo Phòng Đào tạo Khoa học và Quan hệ Quốc tế, Ban giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên đã nhiệt tình ủng hộ và tạo mọi điểu kiện thuận lợi để các tác giả hoàn thành sách. Lời cảm ơn chân thành cũng xin được gửi tới Ban giám đốc Đại học Thái Nguyên đã tận tình giúp đỡ đẽ cuốn sách này sớm được xuất bản. Do thời gian và kinh nghiệm có hạn nên cuốn sách chắc chắn không tránh khỏi những sai sót nhất định. Chúng tôi rất mong được bạn đọc góp ý và lượng ihứ Tliái Nguyên, Iigày 17 tháng 8 năm 2010 Các tác giả 16 Phần I. LÝ THUYẾT CHƯNG Chương I BÀI TOÁN TỐI ƯU 1.1. K H Á I N IỆ M VÀ Đ ỊN H N G H ĨA Trong không gian véctơ K", cho D c K" là một tập khác rỗng và hàm sô' thực f : D —> [R tùy ý. Bài toán tối ưu có dạng min (f(x ): X E D | (P) là bài toán tìm véctơ (điểm) X*E D sao cho f(x*) < f(x) với mọi x e D. Định nghĩa 1.1. Hàm f gọi là hàm mục liêu hay liàm chi phí, tập D gọi là tập ràng buộc hay miền chấp nhận được. Một véctơ (điểm) X 6 D gọi là một phương án (lời giải hay ngliiệm) chấp nhận dược. Véctơ X* e D sao cho f(x*) < f(x) với mọi X e D gọi là một phương án (lời giải hay nghiệm) tối ưu của bài toán và f(x*) gọi là giá trị cực tiểu hay giá trị tối Iiìt cùa f trên D, thường dược ký hiệu ^ ^mirr Trường hợp D = Kn ta có bài toán tối ưu không ràng buộc: min |f ( x ) : X e IRnỊ hay min f(x). X € R " Trái lại, (P) là bài toán tối ưu có ràng buộc. Khi ấy tập D (hường được cho bởi 17 D = Ịx e R " : g,(x) < 0 , i = 1 , , m, hj(x) = 0, j = 1 , , p i, (1.1) với g;, h j: Rn —» IR là các hàm số cho trước, gọi là các hàm ràng buộc, và bài toán (P) có thể viết dưới dạng (gọi là bài toán dạng chuẩn): f(x) -» min với điều kiện g ,(x )< 0 , i= 1, ... , m, hj(x) = 0, j = 1 ,..., p. (1.2) (1.3) Các hệ thức gi(x) < 0 gọi là các ràng buộc bất đẳng thúc, các hệ thức hj(x) = 0 gọi là các ràng buộc dẳng thức. Ràng buộc bất đẳng thức dạng Xj > 0 (- Xj < 0) gọi là ràn g bu ộc không âm hay ràng buộc về dấu. N hận xét l . l ế Ràng buộc bất đẳng thức có thể biến đổi thành ràng buộc đẳng thức và ngược lại. Thật vậy, các ràng buộc (1.2) có thể được biểu diễn nhờ hệ thức g;(x) + y f = 0, i = 1, ..., m với y, là các số thực, gọi là các biến bù. Nguợc lại, mỗi ràng buộc đằng thức (1.3) tương đương với hai ràng buộc bất đảng thức hj(x) < 0, - hj(x) < 0, j = 1 ,..., p. Với nhận xét vừa nêu, không giảm tính tổng quát đôi khi ta xét bài toán tối ưu chỉ với ràng buộc đẳng thức hoặc chỉ với ràng buộc bất đẳng thức. N hặn xét 1.2. Do min ( f ( x ) : X e DỊ = - m ax(- f(x) : X e Dị nên bài toán tìm cực tiểu đưa được về bài toán tìm cực đại và ngược lại. Nếu f(x*) > f(x) với mọi X e D thì f(x*) là giá trị cực đại của hàm f trên D và thường được ký hiệu là fmax. Định nghĩa 1.2. Điểm X* 6 D được gọi là một ngliiệm cực tiểu địa phương của f trẽn D nếu có E > 0 sao cho f(x*) < f(x) với mọi X e D và llx - x*ll < £. 8 Nếu f(x*) < f(x) với mọi X e D, X *■X* và llx - x*ll < s thì X* được gọi là nghiệm cực tiểu địa phương chặt của f trên D. Đ ịnh nghĩa l ể3. Điểm X* e D được gọi là nghiệm cực tiểu toàn cục của f trên D nếu f(x*) < f(x) với mọi X 6 D. Nếu f(x*) < f(x) với mọi x e D, X * X* thì X* được gọi là nghiệm cực tiểu toàn cục cliặt của f trên D. Các khái niệm nghiệm cực đại địa phương, cực đại địa phương chặt và nghiệm cực đại toàn cục, cực đại toàn cục chặt được định nghĩa tương tự. Tập D là khoảng đóng [a; + oo) X! điểm cực tiểu toàn cục chặt. (f không có cực đại toàn cục) x2 điểm cực đại địa phương chặt x3 điểm cực tiểu địa phương (không chặt) x4 điểm cực đại địa phương (không chặt) x5 điểm cực tiểu địa phương chặt Hình 1.1. Cực tiểu (cực đại) địa phương (toàn cục) Đối với hàm tùy ý i trên tập D, ta ký hiệu tập tất cả các điểm cực tiểu (cực đại) toàn cục của f trên D là Argmin xSD f(x) (A rgm axx g Df(x)). 19 Khi xét một bài toán tối ưu ta mong muốn tìm nghiệm tối ưu (cực tiểu, cực đại) toàn cục của nó. Tuy nhiên, một nghiệm như thế có thể không tồn tại. Chẳng hạn, hàm một biến f(x) = X và f(x) = ex không có cực tiểu toàn cục trên tập sô' thực [R. Hàm f(x) = X giảm vô hạn tới - 00 khi X dần tới - 00, còn hàm f(x) = e x luôn nhận giá trị dương và giảm tới 0 khi X dần tới - co. Tập {f(x) : X e D} được gọi là miền trị của hàm f. Có hai khả nãng sau: a) Tập 1 f(x): X e D 1 bị chặn dưới, nghĩa là có một số n sao cho ụ. < f(x) với mọi X e D. Trong trường hợp này cận dưới lớn nhất cùa {f(x) : X e DỊ là môt sô' thưc và được ký hiệu là inf f(x). Chẳng x g D hạn, inf ex = 0. xeR b) Tập Ịf(x) : X Ẽ D | không bị chặn dưới (tức là tập này chứa các số thưc nhỏ tùy ý). Trong trường hợp này ta viết inf f(x) = - 00. xeD Điểm cực trị loàn cục thường được tìm trong số các điểm cực trị địa pliương. Nhưng việc tìm này nói chung cũng không dễ vì một bài toán có thể có rất nhiều cực trị địa phương giá trị khác nhau, trừ khi có những giả thiết đảm bảo nghiệm lối ưu địa phương cũng là nghiệm tối ưu toàn cục. Vì thế trên thực tế, trong nhiều trường hợp ta phải bằng lòng với một điểm cực trị địa phương và đôi khi tìm được một diểm cực trị địa phương cũng là đù. 1.2. VÍ DỤ Sau đày là một số ví dụ về bài toán tối ưu không ràng buộc (D = HT). Ví dụ l . l ề Bài toán sản xuất: Có một loại sản phẩm được chê tạo từ m loại vật liệu khác nhau. Hàm sản xuất f(X|, x2........xm) cho 20 biết số lượng sản phẩm sản xuất được khi sử dụng kết hợp Xj đơn vị vật liệu j, j = 1, 2, ... , m. Giá một đơn vị sản phẩm là q và giá một đơn vị các loại vật liệu lần lượt là p„ p2, ..., pm. Để đạt lợi nhuận tối đa, nhà sản xuất cần giải bài toán tối ưu không ràng buộc: q f(x„ x 2, ,.ằ, xm) - CpẨx, + p2x2 + ... + pmx j -> max. Ví dụ l ế2. Bài toán xấp xỉ: Giả sử giá trị của hàm g(x) (x e R) được quan sát bằng thực nghiệm tại m điểm cho trước X|, x2, ..., xm và ta biết được g(X[), g(x2) , ..., g(xm). Ta muốn xấp xỉ g(x) bởi một hàm đa thức h(x) bậc không quá n, với n < m: h(x) = a„x" + an.|Xn'' + ... + a,x + ao Với mỗi cách chọn đa thức xấp xỉ sẽ có các sai số Ek = g(xk) - h(xk), k = 1, 2,..., m. Ta định nghĩa xấp xỉ tốt nhất là đa thức đạt cực tiểu tổng bình phương các sai số này, nghĩa là đạt cực tiểu tổng Ẹ M 2. k=l Điều này cho thấy ta cần làm cực tiểu hàm số f(a )= X [ g ( x k ) - ( a nx k + a n -ix ¡r'+ + a ,x k + a 0) ] 2 k=l đối với a = (ao, a t, ... , a„)T để tìm các hệ số tốt nhất. Hàm f(a) là một dạng toàn phương của ao, a b ... , an. Để tìm biểu thức gọn cho hàm này, ta đặt m m q¡j = £ ( * k ) - bj= £ ể ( x k)(x k) ( i,j = 0, l , ẼỀỀ,n ) k=l k=l và c = ^ g ( x k)2. k=l Khi đó sau vài phép biến đổi đại số đơn giản, ta có thể thấy rằng f(a) = aTQa - 2bTa + Ç với Q = (q¡j) và bT = (b0, ồ!....... bn). 21 Ví dụ 1.3. Bài toán phân hoạch: Cho n số nguyên dương a„ a2,..., a„. Hãy phân chia a|, a2>... , an thành hai phần riêng biệt có tổng bằng nhau? v ề mặt toán học, bài toán này có thể diễn đạt thành bài toán: Tìm các s ố Xj = ± 1 sao cho ¿ a jXj = 0 . j=i (1.4) Ta lại có thể phát biểu (1.4) dưới dạng bài toán tối ưu không ràng buộc: \2 min (f(x) = ẳ ajx j + ¿ ( X j - l ) 2 : X e r } . >> ) j=* Ĩ3. Dê kiểm tra lại rằng (1.4) có nghiệm ±1 khi và chỉ khi fmin = 0. Thật vậy, do f(x) > 0 với m ọi X e K" nên fmin > 0. , , n , Giả sử (1.4) có nghiệm ± 1, ví dụ z. Vì ^ a .z . = 0, Zj = 1 với j=l mọi j nên f(z) = Ẻ ajz j + X (Zj - 1)2 = 0 < fmin => f(z) = fmin = 0. J= ' ) j=> Ngược lại, giả sử fmin = 0, nghĩa là tìm được X £ I " với mọi Xj = ± 1 sao cho " ì 2 " £ a jXj + £ ( x J2 - l ) 2 = 0 . j=i ) j=i Do vế trái là tổng các bình phương nên \2 n n và 22 Z ajx j = 0 c > X a jx j = 0 J=1 ) H ¿ ( x ? - l ) 2 = O o x ? - l = 0 , j = 1 ,2 ,..., n, j=i nghĩa là hệ (1.4) có nghiệm + 1. Sau đây là một số ví dụ về bài toán tối ưu có ràng buộc. Ví dụ 1.4. Bài toán th ể tích ¡ỚII nhất: Trước hết ta nêu một ví dụ quen thuộc trong nhiều giáo trình về tối ưu: Tìm cách dựng một hộp bìa các tông có thể tích lớn nhất với điều kiện diện tích toàn phần của hộp bàng số c (cho trước)? Ký hiệu kích thước hộp là X, y, z. Bài toán có thể diễn đạt thành V(x, y, z) = xyz -» max với điều kiện 2(xy + yz + zx) = c, X > 0, y > 0, z > 0. Ví dụ 1.5. Bài toán dầu tư clumg klioátv. Một nhà đầu tư muốn dùng số vốn hiện có đầu tư vào thị trường chứng khoán. Giả sử có n loại chứng khoán khác nhau, đánh số theo i = 1, 2, , n. Chứng khoán i được đặc trưng bởi tỉ suất thu lời ngẫu nhiên Ij với giá trị trung bình (kỳ vọng) ì j . Hiệp phương sai giữa với các tỉ suất thu lời Ij khác là ơjj với j = 1,2, ..., n. Bài toán đặt ra là nhà đầu tư nên phân bổ như thế nào toàn bộ số vốn hiện có vào n loại chứng khoán này cho có lợi nhất? Gọi Wj là tỉ lệ vốn bỏ vào chứng khoán j. Khi đó, toàn bộ tỉ suất n n thu lời của vốn là r = X w j rj • GiÁ trị trung bình ĩ = ^ W j ĩ ị và j=i j=i n phương sai ơ 2 = WjơjjWj. i.j=i Markowitz đưa ra khái niệm di sản vốn hiệu quả, đó là cách đầu tư đạt tỉ suất thu iời trung bình ĩ (cho trước) với phương sai 23 (độ rủi ro) ơ 2 > 0 nhỏ nhất. Như vậy, bài toán đầu tư chứng khoán đặt ra có thể biểu diễn dưới dạng bài toán tối ưu: nẸ w i° ij min 2 . w iơ ijw j vl.w2....wn j j=l i.j=l với điều kiện ¿ W j î j = r , ¿ W j = 1, W j > 0 , j = 1 , 2 , . . . , n. j=i j=i Ví dụ 1.6. Bài toán lát cắt lớn nhất: Cho một đồ thị vô hướng G = (V, E) với tập đỉnh V = {1, 2, , n | và tập cạnh E ç ((i, j) : 1, j e V }. Giả sử mỗi cạnh (i, j) e E có một trọng số Wịj > 0 và tập con S c V . Lát cắt của G, ký hiệu cut (S), là tập cạnh nối một đỉnh thuộc s với một đỉnh thuộc V \ s , nghĩa là cut(S) = {(i, j) e E : i e s, j e V \ S |. Trọng số của lát cắt này là số (S)w ij ■ t0^n ^ ra là tìm một lát cắt có trọng số lớn nhất. Hãy phát biểu bài toán đó dưới dạng một bài toán tối ưu? Sau đây là cách diễn đạt toán học khá tinh tế của bài toán này. Lát cắt cut (S) (với S c V) được thể hiện bằng một véctơ X e R n (n = IVI là số đỉnh của đồ thị) với các thành phần ±1: Xj = + 1 vói j e s, Xj = - 1 với j e V \ s. Rõ ràng (i, j) 6 cut(S) Ö X|Xj = - 1. 1 n Trọng số của lát cắt bằng - Wjj(l - XịXj) bởi vì 2 i.j=l Í0 nếu(i, j) Ể cut(S), 1 - X¡X: = <[2 n ế u ( i,j) e c u t(S ) . Điểu kiện nguyên Xj = 1 hay - 1 tương dương với X ? = 1 (j = 1 2 , n). Vì thế, bài toán lát cắt lớn nhất được mô hình hóa như sau: 24 max ( i £ w ¡j(l-x ¡x j) : Xj = 1, j = 1 ,2 ,..., n |ẳ 2 i.j=i Vì mọi hàm trong mô hình đều là đa thức (cụ thể là đa thức bậc 2) nên đây là một bài toán tối ưu đa thức. Mô hình này có nhiều ứng dụng trong các vấn đề thiết kế và an ninh mạng và trong nhiều lĩnh vực khác. l ế3. PH  N L O Ạ I BÀ I T O Á N T Ố I ƯU Bài toán tối ưu (P) nêu ở mục l ễl rất rộng và bao quát nhiều lớp bài toán tối ưu với cấu trúc rất khác nhau. Để tiện cho việc nghiên cứu dinh tính và xây dựng các phương pháp giải số cho bài toán, người ta thường phân chia ra một số lớp bài toán tối ưu sau đây, dựa theo tính chất và đặc điểm của hàm mục tiêu, các hàm ràng buộc, các hệ số, các tham số của bài toán. Tối ưu tuyến tính: bài toán (P) với f(x) là một hàm tuyến tính và D là một tập lồi đa diện, D thường được cho ờ dạng (1.1) trong đó mọi g](x) (i = 1 ,..., m), hj(x) (j = 1 , , p) là các hàm tuyến tính afin. Tối ưu tuyến tính là một trong những lớp bài toán tối ưu quan trọng nhất và được ứng dụng rộng rãi nhất trong thực tiễn. Bài toán tối ưu tuyến tính (còn gọi là bài toán qui lioạch tuyến tính) có nhiều đặc tính của bài toán liên tục (mọi biến số nhận các giá trị liên tục). Tuy nhiên, nó cũng có một phần cấu trúc tổ hợp, thể hiện ở chỗ: lời giải của bài toán có thể tìm trong tập hữu hạn các điểm cực biên (đỉnh) của tập ràng buộc D. Tối ưu phi tuyến (hay qui hoạch phi tuyến): bài toán (P) với f(x) không tuyến tính hoặc tập D cho bởi (1.1) trong đó có ít nhất một trong các hàm gà, hj là phi tuyến. Các bài toán tối ưu phi tuyến thuộc loại bài toán tối ưu liên tục (không ràng buộc khi D = R n hay có ràng buộc khi D cho bởi các đẳng thức hay/và bất đẳng thức). Tối ưu phi tuyến lại có thể chia thành các bài toán tối ưu lồi (khi 25 hàm f(x) cần tìm cực tiểu là lồi và D là một tập lồi) và các bài toán tối ưu không lồi (khi hàm f(x) hoặc tập D không lồi). Tối ưu lồi là bài toán tìm cực tiểu hàm lồi (cực đại hàm lõm) trên một tập lồi đóng, còn gọi là bài toán qui lioạclì lồi (qui hoạcli tuyến tính là một trường hợp riêng quan trọng của bài toán này). Tối ưu lồi là lớp bài toán tối ưu phi tuyến được nghiên cứu nhiều nhất. Một trường hợp riêng đáng chú ý nữa của qui hoạch lồi là qui hoạch lồi toàn phương: tìm cực tiểu hàm lồi bậc hai với các ràng buộc tuyến tính. Qui lioạcli lồi tách biến, qui hoạch hình học ... cũng thuộc lớp bài toán tối ưu lồi. Đặc điểm chung của các bài toán tối ưu lồi là nghiệm cực tiểu địa phương luôn là nghiệm cực tiểu toàn cục và để nghiên cứu có thể vận dụng các công cụ của toán giải tích và giải tích lồi. Tối ưu không lồi (hay tối lũt toàn cục): bài toán có nhiều cực tiểu (hay cực đại) địa phương giá trị khác nhau, trong số đó tìm được cực tiểu (cực đại) toàn cục là vấn đề thường rất khó khãn vì số điểm cực tiểu (cực đại) địa phương có thể rất lớn. Ví dụ điển hình về bài toán không lồi là bài toán qui hoạch lõm (bài toán (P) với f(x) lõm, tập D lồi đóng), qui hoạch lồi đảo (bài toán (P) trong đó f(x) lồi, tập D = M \ int c với M, c là các tập lồi đóng), qui hoạch ■ d-c (bài toán (P) với f(x), có thể cả g, hay hj, là hiệu của hai hàm lồi), qui hoạch toàn phươiig không lồi (bài toán (P) với f(x) là hàm toàn phương không xác định), qui hoạch phân thức (f(x) là hàm phân thức), v .v ... Tối ưu rời rạc hay tối ưu tổ hợp là bài toán (P) với D là một tập hợp rời rạc. Trường hợp các biến số (hay một phán biến) chỉ nhận các giá trị nguyên trong một giới hạn nào đó, ta có một qui hoạch nguyên. Một số trường hợp riêng quan trọng của qui hoạch n°uyên là qui hoạch nguyên biến Boole hay qui hoạch nguyên 0-1 (các biến số chỉ nhận giá trị 0 hay 1) và qui lioạch tuyến tính nguyên (qui hoạch tuyến tính với các biến số chỉ lấy giá trị nguyên). Các bài toán tối ưu tổ hợp thường nảy sinh trong các vấn đề lập lịch kế 26 hoạch hóa vận chuyển, tối ưu hóa mạng và ghép cặp. Các bài toán rời rạc được xử lý nhờ dùng các công cụ của toán học tổ hợp và các phương pháp riêng, kể cả phương pháp cùa tối ưu liên tục. Tối ưu (qui hoạch) đa mục tiêu: không chỉ có một hàm mục tiêu duy nhất như trong bài toán (P) mà có một số hàm mục tiêu không hòa hợp với nhau (nghĩa là không có lời giải nào tối ưu theo mọi mục tiêu), cho nền cần dung hòa các mục tiêu theo một cách hợp lý, hữu hiệu nhất. Tối ưu đa mục tiêu lại có thể chia ra nhiều bài toán con khác nhau, tùy theo tính chất hàm mục tiêu và tập ràng buộc (mục tiêu tuyến tính hoặc không tuyến tính, ràng buộc tuyến tính hay lồ i...). Ngoài ra còn có qui hoạch ngẫu nhiên khi các tham số trong bài toán không có giá trị xác định mà được mô tả bởi các phân phối xác suất, qui lioạch tham s ố khi các hệ số trong hàm mục tiêu hay trong các hàm ràng buộc phụ thuộc vào một hay nhiều tham số, qui hoạch động khi các đối tượng được xét là các quá trình có thể chia ra thành nhiều giai đoạn hoặc các quá trình phát triển theo thời gian, qui hoạch Lipscllitz với các hàm trong bài toán là hàm Lipschitz, qui lioạcli nón (bao gồm qui hoạch nửa xác định dương, qui hoạch nón bậc hai), tối ưu nhiều cấp, tối ưu trong không gian vô số chiểu (bài toán biến phân, bài toán điều khiển tối ưu), tối ưu kliông trơn với hàm mục tiêu hay các hàm ràng buộc không khả vi, qui hoạch với vô số ràng buộc, v.v ... l ề4ề S ự T Ồ N T Ạ I N G H IỆ M T ố i Ư u Câu hỏi đầu tiên đặt ra là bài toán có hay không một nghiệm tối ưu (cực tiểu hay cực đại toàn cục)? Trả lời cho câu hỏi này là định lý W eierstrass quen thuộc trong giải tích: nếu hàm f liên tue và tập D compac, kliác rỗng thì bài toán có ngliiệm tối ưu. Ta xét một số điều kiện mở rộng bảo đảm cho bài toán có nghiệm tối ưu. 27 1.4.1. H àm nửa liên tục dưới Định nghĩa 1.4. + Hàm f : D -> R gọi là hàm nửa liên tục dưới tại điểm X e D nếu với mỗi 8 > 0 có một 5 > 0 sao cho f( X ) - e < f(x) với mọi X thuộc D, llx - X II < 5. Hàm f gọi là nửa liên tục dưới trên D nếu f nửa liên tục dưới tại mọi điểm X e D. ís. Định nghĩa trên tương đương với linixeD x->x )■ + Hàm f : D R gọi là hàm nửa liên tục trên tại X e D nếu với m ỗi s > 0 có một ô > 0 sao cho f(x) < f( X ) + E với m ọi X e D, llx - X II < 5. Hàm f gọi là nửa liên tục trên trên D nếu f nửa liên tục trên tại mọi điểm X e D. ís. Hàm f nửa liên tục trên khi và chỉ khi - f nửa liên tục dưới. Hàm f gọi là liên tục nếu nó vừa nửa liên tục dưới, vừa nửa liên tục trên. Định lý sau nêu một số tính chất đặc trưng của hàm nửa liên tục dưới. Định lý 1.1. VỚI bất kỳ liàm f : D ÍR, ba điều sau tương duơìig: a) f nửa liên tục dưới trên tập đóng D ç R"; b) epi f = {(x, a ) £ D X R, f(x) < a ) là tập dóng trong R 1” 1; c) Với mọi a e R, tập mức dưới Ịx 6 D : f(x) < a ) đóng. C hứng m inh. a) => b) Giả sử f nửa liên tục dưới trên D. Ta sẽ chứng tỏ epị f đóng. Thật vậy, giả sử ( x \ a k) e epi f (xk 6 D, f(xk) < a k) và (xk, a k) -> (x, a). Do D đóng nên X e D. Do f nửa liên tục dưới nên lim f(xk) > f(x). Từ đó ta nhận thấy X - > x a = lim k^.œ a k > Ịịm f(xk)> f(x ), X —»X 28 nghĩa là (x, a ) e epi f. Vậy epi f dóng. b) => c) Giả sử xk e D, f(xk) < a và xk -> z. Do epi f đóng nên (z, a ) € epi f, nghĩa là z 6 D, f(z) < a. Chứng tỏ tập mức dưới {x e D : f(x) < a} đóng. c) => a) Với dãy xk e D, xk -> Xo 00f(xk) < f(x°) thì phải có e > 0 để với mọi k đủ lớn f(xk) < f(x°) - 6. Do tập |x e D : f(x) < f(x°) - e} đóng nén f(x°) < f(x°) - 8, vô lý! Vậy Ịịm k _>00f(xk) > f(x°), nghĩa là f nửa liên tục dưới. Ví dụ 1Ế7. Hàm f(x) = X2 với mọi X 0 và f(0) = - 1 nửa liên tục dưới trên K (Hình 1.2a). Hàm f(x) = e x với mọi X * 0 và f(0) = 2 nửa liên tục trên trên R (Hình 1.2b). Tuy nhiên các hàm này không liên tục trên toàn bộ R. a) b) Hình 1.2. a) Hàm nửa liên tục dưới b) Hàm nửa liên tục trên Đ ịnh lý 1Ể2. M ột hàm f(x) nửa Hên tục dưới trên m ột tập compac D khác rỗng phải đạt cực tiểu trẽn D. Tương tự, một hàm f(x) Iiửa liên tục trên trên một tập compac D kliác rổng pliải đạt cực đại trên D. 29 Chứng m inh. Giả sử f nửa liên tục dưới trên D. Theo định nghĩa của số a = inf {f(x) : X e DI (có thể a = - oo), có một dãy xk e D sao cho lirrik-n* f(xk) = a . Do D compac, không giảm tổng quát có thể cho rằng xk —> x° e D. Theo giả thiết f nửa liên tục dưới ta có a > f(x°). Vì f(x°) e R nên điều này cho thấy a > - 00. Nhưng x° e D nên theo định nghĩa của a ta phải có a < f(x°). Vậy f(x°) = a = inf {f(x) : X 6 D Ị. Phần thứ hai chứng minh tương tự. Hệ quả l ắl. M ột hàm tuyến tính afin f bị chặn trẽn (liay dưới) trên m ột tập afin thì f ch ỉ có th ể dồng nhất bằng m ột liằng sô' tiửên lập đó. C hứng m inh. Giả sử f bị chặn dưới trên tập afin M. Lấy bất kỳ a, b e M. Nếu f(b) < f(a), xét tia (x = a + Ầ(b - a) : X > 0 | c M. Do f tuyến tính nên f(x) = f(a) + X[f(b) - f(a)] - 00 khi X -» + 00, trái với giả thiết f bị chặn dưới trên M. Lập luận tương tự ta thấy cũng không thể có f(a) < f(b). Vậy phải có f(a) = f(b) vói mọi a, b e M. 1.4.2. Điều kiện bức Nếu tập D chỉ đóng mà không bị chặn thì nói chung một hàm nửa liên tục dưới (nửa liên tục trên) trên D có thể không đạt cực tiểu (cực đại) trên D. Tuy vậy, ta có định lý sau. Định lý 1.3. a) M ột liàm í : D —> R nửa liên lục dưới trên m ột lập ílỏng D khác rỗng mà bức (coercive) trẽn D, nglũa là f(x) —> + oc khi X e D llxll —» + 00, thì f pliái có cực tie’ll trên D. 30 b) M ột hàm f : D —> R nửa liên tục trên trên một tập đóng D khác rông mà - f bức trên D (tức là f(x) - 00 khi X e D, llxll -> + °o) thì f pliái có cực đại trên D. C hứng m inh. Ta chỉ cần chứng minh phần đầu. Lấy tùy ý một điểm a e D. Do f nửa liên tục dưới, Iheo Định lý 1.1 tập c = (x 6 D: f(x) < f(a)| đóng. Nếu c không bị chặn thì có một dãy (xkỊ c c với f(xk) < f(a), llxkll -> + co và do bức nên f(xk) -» + 00, mâu thuẫn. Vậy c compac và theo Định lý 1.2 hàm f có cực tiểu trên c , cực tiểu này cũng là cực tiểu của f trên D. ís. Ví dụ đơn giản sau đây cho thấy trong Định lý 1.3 không thể thiếu giả thiết nửa liên tục dưới và điểu kiện bức chỉ là dủ chứ không phải là điểu kiện cần. Ví dụ 1.8. a) Cho hàm một biến số Hàm này bức, do f(x) -» 00 khi Ixl —>00, nhưng không nửa liên tục dưới (mặc dù nó nửa liên tục trên). Vì thế, giá trị cực tiểu toàn cục của hàm (bằng 1) không bao giờ đạt được (Hình 1.3). b) Xét hàm hằng f(x) = 1 với mọi x e R. Khi đó, mọi X 6 Ü đều là điểm cực tiểu toàn cục của f, nhưng f(x) -+♦ + 00 khi Ixl —> + 00. ■»/ f(x) = 2, Ịx| < 1 f(x) = X2, |x| > 1 - 1 0 1 X Hình 1.3. Ví dụ 1.8 a) 31 Định lý 1.4. Hàm bậc hai f(x) = — xTAx + bTx với A 6 ỈRn*n đối 2 xứng, b e 0?.n líì bức khi và chỉ khi A xác định dương. C hứng m inh. Giả sử A xác định dương. Nếu f không bức thì có một dãy X1, X2, ... , x \ ... với llxkll -» + 00 nhưng f(xk) < a với a nào đó thuộc R, nghĩa là - (xk)TAxk + b V < a , Vk. (1.5) 2 Đặt yk = xk/llxkll, ta có llykll = 1. Mọi y 1, y2, ằ.. đều nằm trên biên của hình cầu đóng B (0, 1 ) tâm 0 bán kính 1. Do biên này là một tập đóng và bị chặn nên có thể xem rằng yk hội tụ tới một điểm duy nhất w với llwll = 1. Từ (1.5) cho thấy 1 í xk ì T' A xk ' bTx k a 2 l l |x k |lj l | x k II2 | | x k II2 Khi k —» co thì llxkll —» 00 và ta nhận được (thay yk = xk/llxkll) lim ( — (yk)TAyk) + 0 < 0 => — wTAw < 0, trái với A xác đinh k—>00 2 2 dương. Ngược lại, giả sử f bức nhưng A không xác định dương. Khi đó tồn tại phần tử w e KLn (vv * 0) sao cho wTAw < 0. Với X = t.w ta có f(x) = — t2(w TAw) + t.bTw. 2 Do bTvv là một hằng số và wTAw < 0 nên khi t ± 00 (nếu b * 0 chọn t trái dấu với bTw), f(x) -> 0 hoặc - 00, tức là f khôn« bức. Vậy nếu f bức thì A phải xác định dương. Ví dụ 1.9. Hàm toàn phương nào sau đây là bức? Vì sao0 a) L |(x) = L |(x „ x 2, X,) = Xf + 4 x 2 + 3 X3 + 2X|X,. 32 b) L2(x) = L2(x,, x2, x3) = 2 x f +3X 2 ' x 3 + 4xtx2 - 6x,x3 + 10x2x3. Giải: Tính toán trực tiếp cho thấy L|(x) = xTAx và L2(x) = xTBx với ' \ 1 0' ' 2 2 - 3 ' A = 1 4 0 , B = 2 3 5 ,0 0 3, ,-3 5 -1, Có thể thấy A là ma trận xác định dương nên hàm L|(x) là bức, B là ma trận không xác định dương nên hàm L2(x) không bức (x, = x2 = 0, x3 -» 00, L2 -00). Dùng các định lý nêu trẽn ta có thể xét bài toán có nghiệm tối ưu hay không. V í dụ l ề10. Các bài toán sau có nghiệm tối ưu không? Vì sao? a) min (xf+x 2 + ... + x „ : a,x, + a2x2 + ... + anxn = b} với b, a; * 0 (Vi). b) min(X| + 2x2 - X-Ị: 3x, - x2 + 2x3 = 4). Giải: a) Đày là bài toán tối ưu dạng min |f ( x ) : X € DỊ với f(x) = x f + x ị + ... + x„ liên tục và bức (vì f = llxll2 nên khi llxll -» 00 thì f -> 00). Tập D=|xeK": a,x, + a2x2 + ... + anxn = bị có dạng một siêu phảng trong [Rn nên D là một tập đóng. Dễ thấy D khác rỗng, vì X| = b /a|( x2 = . . . = xn = 0 thỏa mãn a,x, + a2x 2 + . . . + anxn = b. Theo Định lý 1.3, bài toán có điểm cực tiểu toàn cục (nghiệm tối ưu). b) Đây là bài toán tìm cực tiểu hàm tuyến tính f(x) = X| + 2x2 - x3 trên tập afin D = |x E i :’ : 3 x , - x 2 + 2x3 = 4 Ị (D là tập nghiệm của 33 một phương trình tuyến tính). Kiểm tra trực tiếp cho thấy a = (1, 1, 1)T, b = (0, 0, 2)t thuộc D và f(a) = 2 * f(b) = - 2. Theo Hệ quả 1.1, hàm f không bị chận dưới trên D, do đó bài toán không có nghiệm cực tiểu (inf (f(x) : X e D} = -oo). Sau đây ta nêu thêm một định lý về điều kiện cần và đủ dể (P) có nghiệm cực tiểu. Định lý l ẽ5. Đê’ bài toán (P) có nghiệm cực tiểu, diêu kiện cần và đủ là tập f(D)t = {a e K : f(x) < a với X e D| đóng và có một cận dưới hữu hạn. Chứng m inh. Trước hết giả sử X* là một nghiệm cực tiểu của bài toán (P). Khi đó ta có f(x*) = min f(x) và f(D)+ = [f(x*), + oo). xeD Rõ ràng f(D)+ là một tập đóng và f(x*) là một cận dưới hữu hạn của f(D )+. Ngược lại, nếu tập f(D)+ có một cận dưới hữu hạn thì cận dưới lớn nhất (hay infimum) của f(D)t cũng là hữu hạn. Ta ký hiệu infimum đó là a*. Theo định nghĩa của infimum, a * < a với mọi a £ f(D)+ và tồn tại dãy sô' { ak) c f(D)+ hội tụ đến a* . Do f(D)+ là tập đóng nên a* e f(D)+. Theo định nghĩa của f(D)+ tồn tại x * e D sao cho f(x*) < oc*. Hiển nhiên f(x*) e f(D)+ và do a * là cận dưới lớn nhất của f(D)+ nên a* < f(x*). Vì thế, a * = f(x*). Điều này chứng tỏ X* là một nghiệm cực tiểu của bài toán (P). Ví dụ sau đây cho thấy Định lý 1.5 không còn đúng nếu thiếu giả thiết về tính đóng của tập f(D)+. Ví dụ 1.11. Xét hàm f(x) = e \ X e D = R. Do e' > 0 với mọi x e I nên 34 f(D)+ = (0, +00). Tập f(D)+ có cận dưới hữu hạn 0, nhưng do nó là tập không đóng nên hàm f(x) = e* không đạt cực tiểu trên D = K. Hàm f(x) = 1/(1 + X2), xeR , cũng có tính chất tương tự. Bài tập 1. a) Trong K2 cho n điểm p' = (a¡, bị), i = 1, , n. Tìm điểm X = (X|, x2) sao cho tổng khoảng cách từ X tới n điểm p' đã cho là nhỏ nhất. b) Cũng câu hỏi như trên nhưng với mọi p' nằm trong tam giác có 3 đỉnh (0, 0), (10, 0) và (0, 10). Hãy diễn đạt các bài toán nêu trên dưới dạng bài toán tối ưu? 2. Bài toán tập Ổn định lớn nhất (được chú ý nhiều trong khoa học tính toán và tối ưu tổ hợp) có nội dung như sau: Cho G = (V, E) là một đồ thị vô hướng với tập đinh V và tập cạnh E. Tập con S £ V gọi là tập ổn đinh của G nếu không có cạnh nào trong G nối hai đinh thuộc s. Bài toán dật ra là tìm tập ổn định của G có nhiều đỉnh nhất. Hãy phát biểu bài toán này dưới dạng một bài toán tối ưu? 3. Nêu thí dụ về bài toán tối ưu không ràng buộc của hàm một hay hai biến số, khả vi vô hạn lần và thỏa mãn một trong các tính chất sau: a) Có vô sô điểm cực trị (cực tiểu và cực đại) toàn cục. b) Hàm hữu hạn có cực đại toàn cục, nhưng không có cực tiểu toàn cục. c) Hàm hữu hạn không có cực trị toàn cục. d) Hàm hữu hạn có điểm dừng, nhưng không có cực tiểu toàn cục và cực đại toàn cục. 35 e) Hàm hữu hạn có cực trị địa phương nhưng không có cực trị toàn cục. 4. Cho biết các tập sau có đóng hay không? Tập nào bị chận? a) D, = (x e R : X nguyên}. b) D 2 = {X e K : X là sô' hữu tỉ e [0, 1]}. c) D , = |( x b x 2) e IR2 : e X| < x2, sin(Xi + x 2) = 0 Ị. d) D4 = {x e K2 : x , > 1, l/x 2 > 0 ). e ) D 5 = Ịx 6 o r : 1 <11x11 < 3 ) . 5. Hàm nào sau đày là bức, hàm nào kliông. Vì sao? a) f = X* + X2 + X 3 - X|X2. b ) f = x / + X2 + X3 - 7 X]X2X3 . c) f = ln íx ^ X jX j) - X| - x2 - x3. d)f=x / + x ị - xfx 2 - e) f(x) = aTx và g(x) = aTx + s II XII2, s > 0. 6. Bài toán nào trong các bài toán sau có nghiệm tối ưu? Vì sao? a) m in (x, ± x ị : 3x, + 2x2 = 3, X| > 0, x 2 > 0 }. b) m in|X |X3 + x ị : x f + x \ + X3 =4). c) m in lq x ! + . . . + cnxn : X? + .. ử + < bỊ (b > 0). 36 Chương 2 GIẢI TÍCH L ổ l 2ềl. TẬP LỐI 2.1.1. T ập afin và bao afin Cho a, b là hai điểm trong !Rn. Đường tliẳng đi qua a và b là tập tắt cả các điểm x e Rn có dạng X = (1 - A.)a + Xb = a + Ầ(b - a) với X e R. Định nghĩa 2.1. Tập M C ÍR" gọi là một tập afín (hay đa tạp tuyến tính) nếu ( 1 - À)a + /vb e M với mọi a, b e M, và mọi X e R, tức là nếu M chứa trọn cả đường thẳng đi qua hai điểm bất kỳ của nó. Rõ ràng nếu M là một tập afin và a e R" thì a + M = {a + X : X 6 M ) cũng là một tập afin và M là một tập afin chứa gốc khi và chỉ khi M là một kltông gian con, nghĩa là nếu a, b e M thì mọi điểm x.a + Ịib cũng thuộc M với X, n e R. Định lý 2.1. Tập M không rỗng là một tập afin khi và chỉ khi M = a + L, trong đó a e M và L tó một không gian con. Chứng minh. Giả sử M là một tập afin v à a e M . Khi đó, M = a + L với L = - a + M. Do - a e R n nên L = - a + M cũng là một tập afin, hơn nữa 0 e L (vì a 6 M) nên L là một không gian con. Ngược lại, giả sử M = a + L với a e M và L là một không gian con. Do không gian con L là một tập afin nên M = a + L cũng là một tập afin. 37 Không gian con L nói trên được gọi là không gian con song song với tập afin M: L // M. Nó được xác định một cách duy nhất. Tliứ nguyên (hay sô'chiều) của một tập afin M, ký hiệu dim M, là số chiểu của không gian con song song với nó. Ta qui ướci dim 0 = -1 . Ví dụ 2.1. Trong R \ điểm M(a, b, c) là một tập afin số chiều 0, vì không gian con song song với M là L = (0) (Hình 2 .la); đường thẳng qua hai điểm A và B là một tập afin số chiều 1, vì không gian con song song |x = X(B - A) : A. e K} là không gian con một chiểu (Hình 2.1b); mặt phẳng là một tập afin số chiều 2 (Hình 2. lc); IR3 là một tập afin có số chiều 3. Tập 0 là tập afin số chiều - 1. a) b) c) Hinh 2.1. Tập afin M và không gian con song song L Định lý 2.2. M ột tập afin k clíiểu bất kỳ có dạng M = (x : Ax = b}, trong đó A e ỊRm*n, b £ Rm và rank A = n - k (M là tập nghiệm cùa m ột hệ phương trình tuyến tính). M ột tập khác rỗng bất kỳ có dạng trên là một tập afin k chiều. C hứng m inh. Giả sử M là một tập afin k chiều. Với x° 6 M, tập L = M - x° là một không gian con k chiểu, vì thế L = (x : Ax = 0 | với A là ma trận cấp m xn có hạng bằng n - k. Do vậy M = IX : A(x - x°) = 0} = {X : Ax = b I với b = Ax°. 38 Ngược lại, nếu M là một tập có dạng trên thì với bất kỳ x° 6 M ta có Ax° = b. Do đó M = (X : A(x - x°) = 0 1 = x° + L với L = (X : A \ = 0}. Do A có hạng n - k, nên L là một không gian con k chiều, do đó M là một tập afin k chiều. Đ ịnh nghĩa 2.2. Một tập afin (n -1) chiều trong K" gọi là một siêu plĩẳng. ■Ẻ:? = í í ẩ É l f e s * > ' 'p p í * 32*2.+ *1 Hình 2.2. Siêu phẳng trong R2 và R3 Hệ qu ả 2.1. M ột siêu phẳng bất kỳ trong R n là một tập có dạng H = {x : = a ị , (2.1) trong đó a e K" \ {0}, a e R. Ngược lại, một tập bất kỳ có dạng trên là một siêu phẳng trong K". Véctơ a trong (2.1) gọi là véctơ plìáp tuyến của siêu phảng H. Tất nhiên, vói siêu phẳng H đã cho, véctơ a và a được xác định sai khác một thừa số chung khác không. Đường thẳng (À,a : Ằ e R } cắt H tại điểm Ằ a sao cho = a , từ đó X = a/llall2. Vì vậy khoảng cáclĩ từ gốc 0 tới siêu phẳng H bằng IẦ lllall = lal/llall (độ dài của véctơ X a). Ví dụ 2Ế2. H = |x = (X|, x2) : 3x! + 4x2 = 50Ị là một siêu phẳng trong mặt phẳng R2. Véctơ pháp tuyến của siêu phảng này là a = (3, 4)T và khoảng cách từ 0 tới H bằng 10, do llall = 5 và a = 50 (xem H ình 2.3). 39 Hình 2.3. Khoảng cách từ gốc 0 tdi siêu phẳng trong R2 và R3 Trong K" siêu phảng H = (x : = a Ị với a 6 R " \ |0 ) và a e l chia K" thành hai nửa không gian đóng-. H = ( X : < a ) và H+ = ( X : > a }, mỗi nửa không gian này ở về một phía của siêu phẳng và phần chung của chúng chính là siêu phẳng H. Tương tự, H cũng chia IRn thành hai nửa không gian mở. {X : < a } và {X : > a }. Đ ịnh nghĩa 2.3. Điểm x e K" có dạng X = A^a1 + Ầ2a2 + ... + x.kak với a' e K" và + k 2 + ... + Ằk = 1 gọi là một t ổ liợp afin của các điểm a 1, a2, ... , ak. M là một tập afin khi và chỉ khi M chứa mọi tổ hợp afin các phần tử thuộc nó. Giao của một họ bất kỳ các tập afin cũng là một tập afin. Cho E là một tập bất kỳ trong R n, có ít nhất một tập afin chứa E, cụ thể là Kn. Đ ịnh nghĩa 2.4. Giao của tất cả các tập afin chứa E gọi là bao afin của E và ký hiệu là a ff E. Đó là tập afin nhỏ nhất chứa E. Dễ thấy X e a ff E khi và chỉ khi X là một tổ hợp afin cùa các phần tử thuộc E. 40 Đ ịnh nghĩa 2.5. Ta nói k điểm a1, a2, ... , ak e K" là độc lập afin nếu các véctơ a2 - a 1, a3 - a 1, ... , ak - a 1 độc lập tuyến tính (xem Hình 2.4). Có duy nhất một siêu phảng đi qua n điểm độc lập afin a1, a2,..., a" trong Kn. Đó chính là tập afin n - 1 chiều M = aff (a 1, a2, ..., an|, vì M = x' + L với L là không gian con n - 1 chiều, xác định duy nhất bởi n - 1 véctơ độc lập tuyến tính a2 - a 1, a3 - a 1, ... , a" - a' (xem Hình 2.5). Hình 2.4. a1, a2, a3, a4 độc lập afin Hình 2.5. Siêu phẳng qua 3 điểm 2Ỗ1.2. T ập lồi, nón lồi và bao lồi Cho hai điểm a, b e R n. Tập tất cả các điểm X = (1 - X)a + Ằ.b với 0 < X < 1 gọi là đoạn thẳng (đóng) nối a và b, và được ký hiệu là [a, b]. Định nghĩa 2.6. Tập C c r được gọi là một tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó; nói cách khác, nếu ( 1 - X)a + Ằb e c với mọi a, b e c và mọi 0 < X < 1. Ví dụ 2.3. Các tập sau đây đều là các tập lồi: a) các tập afin (nói riêng, các siêu phảng); b) các nửa không gian đóng, các nửa không gian mở; c) hình cầu đóng B (a ,r) = (x e I " : llx - all < r } ; 41 d) hình cầu mở B(a, r) = {x e R" : llx - all < r} với a e R", r > 0. Hình 2.6. Một số tập lối và tập không lồi trong R2 Từ định nghĩa của tập lồi trực tiếp suy ra một số tính chất đơn giản sau đây: - Giao của một họ bất kỳ các tập lồi là một tập lồi. - Nếu c , D c r là các tập lồi thì c + D = (x + y : X e c , y 6 D ), aC = {ax : X € c, a e KỊ, c - D = c + (-l)D cũng là các tập lồi trong K". - Nếu C c l n, D c r là các tập lồi thì c X D = |(x , y): X 6 c , y e D} là một tập lồi trong R n+m. (Có thể mờ rộng cho tích nhiều tập lồi). Đ ịnh nghĩa 2.7. Điểm XE Rn có dạng X = x,a' + x 2â2 + ... + >vkak với a' € IR", x.¡ > 0, Â.| + + ... + X* = 1 gọi là một tổ liợp lồi của các điểm a 1, a2, ..., ak. ■Ja, Tập c là lồi khi và chỉ khi nó chứa mọi tổ hợp lói của các phần tử thuộc nó. T hứ nguyên (hay sô' chiều) của một tập lồi c , ký hiệu dim c , là thứ nguyên hay số chiều của bao afin của nó. M ột tập lói c trong R n gọi là có thứ nguyên đày nếu dim c = n. 42 Định nghĩa 2.8. Một tập con M của K" được gọi là một nón (mũi tại 0) nếu X 6 M, X > 0 thì Xx e M. Nón M gọi là nón lồi nếu tập M lồi (Hình 2.7b). Điểm gốc 0 có thể thuộc hoặc không thuộc M. Tập a + M (a e Rn) gọi là nón có mũi tại a. Nón M không chứa đường thẳng nào gọi là nón nhọn. Trong trường hợp này, gốc 0 gọi là đỉnlĩ của M và a + M là nón có đinh tại a. Mỗi nửa không gian (đóng hay mờ) đều là một nón, nhưng không phải là một nón nhọn. Ví dụ 2.4. Các tập sau đây là các nón lồi (đỉnh tại gốc 0) hay gặp trong R": a) K" = (x = (X|, ... , x n) € Kn : X; > 0, i =1, ... , n} (orthant không ám), b) K++ = (x = (X........ x„) e R" : Xj > 0, i =1, , n } (orthant dương). Đ ịnh lý 2.3. Tập con M của IR" là một nón lồi đỉnli tại gốc khi và cliỉ khi m c M , V Ằ > 0 v à M + M c M , (2.2) Iiglũa là với mọi X, y e M và mọi SỐẰ > 0 la có X + y e M vổ Ằx e M. C hứng m inh. Nếu M là một nón lồi thì Ằ.M cM,VẲ>0 theo định nghĩa của nón. Hơn nữa, lấy bất kỳ X, y e M thì do M lồi nên — (x + y) e M, do đó theo trên X + y e M. Vì thế M + M c M. Ngược lại, nếu có (2.2) thì M là một nón và với mọi X, y e M, X 6 [0, 1] ta có (1 - A.)x e M, ly e M. Từđó(l - ^)x + Xy e M, nghĩa là M là một tập lồi. ĩs, Tập con M c I " là một nón lồi khi và chỉ khi nó chứa mọi tổ hợp tuyến tính không âm (còn gọi là lổ hợp nón) của các phần tử thuộc nó. 43 Định nghĩa 2.9. Cho E là một tập lồi. Tập {Ầx : X € E, X > 0} u 10} gọi là bao nón sinh bởi E và ký hiệu là cone E (xem Hình 2 .7 c). a) b) c) Hình 2.7. a) Nón không lồi; b) Nón lồi; c) Bao nón (cone E) Định nghĩa 2.10. Cho E c ÍRn là một tập bất kỳ. G iao cùa tất cả các tập lồi chứa E gọi là bao lồi của E và được ký hiệu conv E. Đó là tập lồi nhỏ nhất chứa E. R3 Hình 2.8. conv E là bao lối của tập E Ví dụ 2.5. Bao lồi của ba điểm a 1, a2, a3 e K 3 là tam giác 3 đỉnh a1, a2, a3. Bao lồi của đường tròn E =(xeK 2:xf+X 2 = lỊ là hình tròn đơn vị B (0, 1) = (x 6 ! 2 : X? + x \ < 11 (Hình 2.8). •ỈS. Bao lồi của một tập E trùng với tập tất cả các tổ hợp lồi của những phần tử thuộc E và M là tập lồi khi và chỉ khi M = com M. 44 Như vậy, một điểm bất kỳ X 6 cortv E có thể biểu diễn như tổ hợp lồi của một số hữu hạn điểm thuộc E. Định lý sau đây cho một giới hạn trên của số điểm tối thiểu trong các biểu diễn như thế, đó là một kết quả cơ bản về số chiều trong lý thuyết giải tích lồi. Định lý 2.4 (C arathéodory). Cho E là một tập chứa trong một tập afin k cliiẻu. Klii đó bất kỳ X e conv E có tìxể biểu diễn dưới dạng một tổ hợp lồi của không quá k + 1 phần tử thuộc E. C h ứ n g m in h . V ới X € CO IIV E ta có biểu diễn X = Ầ|a' + x.2a2 + ... + ^ mam với a 1, a2, ..., am e E, A.¡ > 0 và A-! + A-2 + ... + A.m = 1. Gọi m là số véctơ ít nhất của E cần dùng trong cách biểu diễn đó. Điểu này kéo theo A-i > 0 với mọi i. Giả sử phản chứng m > k + 1. Nếu ký hiệu L là không gian con song song với a ff E thì dim L = k. Khi đó m - 1 véctơ a2 - a 1, a'1 - a 1, ... , am - a' thuộc L và do m - 1 > k nên các véctơ này phụ thuộc tuyến tính. Vì thế tìm được các số cc2, a 3, , a m với ít nhất một số a, > 0 sao cho a 2(a2 - a 1) + a 3(a3 - a 1) + ... + ctm(am - a 1) = 0. Đặt ßi = otj, i = 2, 3 , , m, và ß| = - a 2 - a 3 - ... - a m ta thấy p ,a' + ß2a2 + ... + ßmara = 0 và ß, + ß2 + ... + ßm = 0, đổng thời có ít nhất một trong các số p I, ß2, ..., ßm là số dương. Lấy Xị = X.Ề - 0 p¡, i = 1, 2 ,..., m, trong đó 0 > 0 là số 9 lớn nhất sao cho x¡ - 0ßi > 0 với mọi i. Do ß,a' + ß2a2 + ... + ßmam = o ta cũng có biểu diễn X = Xị a' + Ả2 a2 + ... + A.m am. Vì ß, + ß2 + ... + ßm = 0 nên theo cách chọn 9 thì mọi Ằ.ị > 0, tổng bằng 1 và có ít nhất một Ằị = 0. Như vậy, có thế biểu diễn X như một tố hợp lồi của ít hơn m véctơ thuộc E, trái với giả thiết m là số véctơ ít nhất cần trong cách biểu diễn X. Vậy m < k + 1 và định lý được chứng minh. 45 2.1.3. P hần trong tương đôi và bao lồi đóng Như đã biết trong giải tích hàm, bao đóng của một tập c , ký hiệu c , là giao của tất cả các tập đóng chứa c . Một điểm a thuộc bao đóng của Ccl"(ae c ) nếu mọi hình cầu tâm a đều có chứa ít nhất một điểm thuộc c , hay nếu a là giới hạn của một dãy điểm thuộc c . Một điểm a của tập c gọi là một điểm trong của c nếu có một hình cầu tâm a nằm trọn trong c . Tập các điểm trong của c gọi là pliần trong cúa c và được ký hiệu là int c . Đ ịnh nghĩa 2.11. Một điểm a của một tập lồi CcR" gọi là một điểm trong tương đối (hay điểm bọc) của c nếu với mỗi X e c đều có một số Ằ. > 0 đê cho a + Ằ(x - a) e c . Tập các điểm trong tương đối của c gọi là pliần trong tương đối của c và được ký hiệu là ri c . Hiệu tập hợp c \ (ri C) gọi là biên lương đối của c , ký hiệu là ỔC. Một điểm biên của một tập lồi c là một điểm thuộc ÕC. Một tập lồi C c P gọi là tập m ở tương dối nếu ri c = c . \ Hình 2.9. Tập mở tương đối trong K3 Hình 2.10. Tập mỏ trong R2 Ví dụ 2.6. Tập lồi c = Ịx e R :' : + X? < l, X, = 0} có ri c = {x e IR ': x f + X? < l. x, = 0 | (hình tròn không kể biên)- ÕC = Ịx e R'1 : + X? = 1, X-Ị = 0) (đường tròn). 46 N hận xét 2.1. Với B = {x e K" : llxll < 11 là hình cẩu đơn vị đóng thì i) int c = (x e c : 3e > o, X + sB c C}; ii) ri c = |x e c : 3s > 0, (x + sB) n a ff c Œ C): Phần trong tương đối của c là phần trong của c trong a ff c . Nếu int c ị 0 thì ỉnt c = ri C; iii) C c D không suy ra ri c c ri D. Chẳng hạn, lấy D c lẵ' là một khối lập phương, c là một mặt của D. Khi đó, CcD, ri c ị 0 , ri D ị 0 , nhưng (ri C) n (ri D) = 0 . Định lý 2.5. Một tập lồi bất kỳ c * 0 có phần trong tương đối khác rỗng. Chứng m inh. Giả sử M = a ff c với dim M = k, khi đó tổn tại k + 1 điểm độc lập afín Xo, X1, ..., x k của c . Ta chỉ ra rằng a = (x" + X1 + ... + xk)/(k + 1) là diểm trong tương đối của c . Thật vậy, bất kỳ X 6 M có dạng X = |I0X° + n ,x' + ... + |ikxk với Ho + n ,+ ... + Hk = 1. Vì thế, a + >.(x - a) = a 0x° + a ,x ' + ... + a kxk với a¡ = (1 - X)/(k + 1) + Ầ|ij (i = 0, 1 , , k) => a<)+ ct| + ... + cck= 1. Với X > 0 đủ nhỏ, ta có dị > o, i = 0, 1,..., k. Do đó, a + Ằ{x - a) £ c . Vậy, theo Định nghĩa 2.11, a e ri c . □ Định lý 2.5 cho thấy một tập lồi c c r có phần trong khác rỗng khi và chí khi nó có thứ nguyên đầy. (Tập lồi c vẽ ở Hình 2.9 không có thứ nguyên đầy). Đ ịnh lý 2.6. Bao đóng và phần trong tương đối của m ột tập lồi là lồi. C hứng m inh. Giả sử c là một tập lồi và a, b e c . Chảng hạn, a = lim x \ b = lim y \ k—>00 k—>00 47 trong đó x \ yk 6 c với mọi k. Với mọi Ằ € [0, 1] ta có (1 - X.)xk_+ Ằyk 6 c . Từ đó, (1 - x.)a + Xb = lim k _> ool(l - ^-)xk + ^-yk) e c . Như vậy, nếu a, b e c thì [a, b] c c , chứng tỏ c lồi. Bây giờ giả sử a, b e ri c . Khi đó, tìm được hình cầu B tâm 0 sao cho (a + B) n a ff c và (b + B) n a ff c nằm trọn trong c . Với Vx = (1 - À.)a + Xb, X, € [0, 1 ], ta có (X + B) n aff c = (1 - M a + B) n affC U ( b + B ) n a # C c c. Như vậy, X e ri c , nghĩa là ri c lồi. Có thê’ chứng minh: nếu tập c lồi và a 6 int c , b e c thì X = (1 - X)a + Ảb = a + >*(b - a) e i/ìt c vói mọi X 6 [0, 1), và nếu tập lồi c có phần trong khác rỗng thì intC = c và i/irC = int c. Hệ qu ả 2.2. Bao lồi của một tập compac là compac. Thật vậy, giả sử E là tập compac và ỊxkỊ c COIIV E. Theo Định lý 2.4. = ^-()ka k + ^-1 ka ' k + ••• + Ằ,n ka"'k với al k e E, Xị k > 0, A.() k + Ằị k + ... + A.n k = 1. Do E X [0, 1 ] là một tập com pac nên tồn tại dãy con I I sao cho ^•i.kqa' kq -> vớia' e E, |i, > 0, + ụ, + ... + n„= 1. Khi đó, ta có X q —» |i()a' + Ịj,|a' + ... + |ina" e COIÌV E và hệ quả được chứng minh. ■&. Bao lồi của một tập đóng không nhất thiết là một tập đóng. Chẳng hạn, bao lồi của đường thẳng £ trong R" và điểm a e Ị là một tập không đóng (Hình 2.11). 48 Hình 2.11. Bao lồi của tập đóng ỉ {a} Định nghĩa 2.12. Giả sửEc IRn. Giao của mọi tập lồi đóng chứa E gọi là bao lồi đóng của E, ký hiệu là conv E. Đó là tập lồi đóng nhỏ nhất chứa E. Bao lồi đóng của một tặp E trùng với bao đóng của bao lồi của E, tức là conv E = convE . Thật vậy, theo Định lý 2.6, convE lồi. Như vậy, convE là tập lồi đóng chứa E. Do đó, convE D conv E. Mặt khác, conv E 3 COIÌV E, bởi vì conv E là giao của tất cả các tập lồi (không cần đóng) chứa E. Vì vậy, conv E z> convE , tức là conv E = conv E . 2.1.4. Các định lý tách tập lồi Định lý tách các tập lồi rất hay được dùng trong lý thuyết tối ưu hiện đại và nó có liên hệ mật thiết với phép chiếu một điểm trên một tập lồi. Định nghía 2.13. Cho một tập lồi c <= Kn và một điểm y e R". Ta gọi hình chiếu của y trên c là điểm x° 6 c sao cho llx" - yll = inf xeC llx - yll = dc(y). Ký hiệu x" = p(y) và gọi dc(y) là klioáng cách từ y tới c . Định lý sau cho thấy nếu c là một tập lồi đóng thì hình chiếu p(y) luôn tồn tại và duy nhất (với mọi y e R"). Đ ịnh lý 2.7. Cho c c E" la một tập lồi đóng khác rống và y e R" là một điểm bất kỳ. Klii đó, tồn tại duy nhất một điểm x° G c 1(1 hình chiêu cứa y trên c. 49 Chứng m inh. Nếu y e c thì rõ ràng p(y) = y và dc(y) = 0. Giả sử y í c. Do dc(y) = inf,eCllx - yll nên theo định nghĩa cùa inf tìm được một dãy {xk} c c sao cho lim llxk - yll = dc(y). Vì dãy (xkỊ bị chặn nên tổn tại một dãy con |x kq I hội tụ đến một điểm x° nào đó. Do c đóng nên x° e c. Vì thế ta có llx° - yll = lim llxkq - yll = lim llxk - yll = dc(y). Điều này cho thấy x° là hình chiếu của y trên c, tức là x" = p(y). Để chứng minh tính duy nhất ta giả sử có hai điểm x' € c và x: e c, x' * X2 sao cho Ilx' - yll = llx2 - yll = dc(y). Pytago suy ra llz - yll2 < - llx' - yll2 + - llx2 - yll2 = [dc(y)]2 => llz - yll < dcíy), trái với định nghĩa của dc(y). Định nghĩa 2.14. Cho c c IR" là một tập lồi và một điểm x" 6 c. Tập Nc(x°) = I y e K " : > 0, Vx € c } gọi là nón pháp tuyến trong của c tại x° (- Nc(x°) gọi là nón pháp tuyến ngoài của C). Hình 2.12. Nón pháp tuyến trong Nclx0) Hình 2.13. Hình chiếu của y trèn c 50 H ệ qu ả 2.3. Giả sử c c R" là một tập lồi đóng khác rỗng, y Ể c và XH là lĩìnli clìiếu của y trên c . Khi đó, với t = x° - y ta có > 0 với mọi X e c , tức là t e Nc(x°), < 0 và có m ột s ố T| sao clio > T| > với mọi X e c . C hứng m inh. Lấy một điểm bất kỳ X 6 c và xét điểm z = Xx. + (1 - X)\°. Do c lồi nên z e c với mọi X e [0, 1] và llz - yll2 > llx° - yll2 (x° là hình chiếu của y trên C). Mặt khác, llz - yll2 = X2llx - x°ll2 + 2 Ằ < \ - Xo, Xo - y> + llx° - yll2. Từ đây suy ra X.2llx - x°ll2 + 2 X < \ - Xo, Xo - y> > 0. Do bất đẳng thức này đúng với mọi X £ [0, 1] nên > 0 và vì X e c được chọn bất kỳ nên điểu này chứng tỏ t = x° - y e Nc(x"). Mặt khác, do X1’ * y nên = = - llx° - yll2 < 0. Từ các bất đẳng thức nhận được suy ra > với mọi X e c và > . V ì thế > > với mọi X e c. Đật T| = ( + )/2 bất đẳng thức trên có thể viết lại thành > TI > Vx 6 c , (2.3) (siêu phẳng = T| tách hẳn y Ễ c với c theo Định nghĩa 2.16). Bổ đề 2.1. Clio c là một tập con lồi klìác rỗng của R n. Nếu 0 g c tliì có m ột vé c tơ ỉ e K " \ {0} sao cho > 0, với m ọi X e c . C hứng m inh. Xét hai trường hợp: a) 0 Ể C (bao đóng của C). Theo Định lý 2.7 tồn tại Xo € C (Xo * 0) là hình chiếu của y = 0 trên c . Theo Hệ quả 2.3 ta có > 0 với mọi X e c . Vậy bổ đề đúng với t = x° * 0. b) 0 e ỠC = C - ri c . Lấy một điểm V e ri c (ri c * 0 theo Định lý 2.5) và lấy dãy yk = - v/k với k = 1 ,2 ,... Rõ ràng yk Ể c và yk —> 0 khi k —> + 00. Vì yk Ể c nên lại theo Định lý 2.7 và Hệ quả 51 2 ắ3 có một xk e c , xk * yk (xk là hình chiếu cùa y k trên c ) sao cho < xk - yk, X - x k> > 0 với mọi X e c. Nếu đặt tk = (x k - y k)/llxk - ykll thì > , vói mọi X e c . Do lltkll = 1 và mặt cẩu |t 6 Kn : lltll = 1 1 compac nên bằng cách lấy ra một dãy con có thê xem như tk hội tụ tới t° với llt°ll = 1. Khi yk -> 0 thì xk -> 0 cho nên -» 0. Do đó > 0 với mọi X e c . Vậy trong trường hợp này bổ đề đúng với t = t" * 0. □ Đ ịnh nghĩa 2.15. Ta nói hai tập lồi khác rỗng c , D trong K" tácli được bởi siêu phẳng H = (x e R" : = a | với t G R " \ (0) và a e I , nếu in f > a > sup . xeC (2.4) Về hình học điểu đó có nghĩa là, các tập c và D nằm vể hai phía khác nhau của siêu phẳng H (xem Hình 2.14b). Đ ịnh lý 2.8 (Định lý tách I)ế Hai tập lồi c vờ D trong [Rn khác rỗng, không có điểm chung có th ể tách được bởi một siêu plìảng, nghĩa là tồn tại véctơ t e R n (t * 0) và m ột sô' a e R sao clio (2.4) thỏa mãn. C hứng m inh. Tập c - D là lồi và thỏa mãn 0 Ễ c - D, vì thế theo Bổ để 2.1, tồn tại t e R n\ {0} sao cho > 0 với mọi X e c, y e D. Khi đó, (2.4) đúng với a = in fxeC. C n D = 0 H = {X : = a} a) b) Hình 2.14. a) Minh họa Bô’ đề 2.1; b) Tách hai tập lối rời nhau (Định lý tách I) 52 N hận xét 2.2. Trước khi nêu một sô' hệ quả của kết quả này ta hãy nhắc lại tính chất đơn giản sau đây của các hàm tuyến tính: hàm tuyến tính C(x) = với t e ir\(0) không bao giờ đạt cực tiểu (hay cực đại) trên tập c tại một điểm trong của C; nếu nó bị chặn trên (hay dưới) trên một tập afin thì nó phải bằng một hằng số trên tập afin này (Hệ quả 1.1). Từ tính chất nêu trên suy ra nếu tập D trong Định lý 2.8 là mở thì (2.4) kéo theo > a > Vx € c, Vy e D. Hệ qu ả 2.4. M ột tập afìn c klìông cắt một tập lồi m ở D thì tồn tại một siêu pliẳng chúa c và kliông cắt D. Thật vậy, giả sử = a là siêu phảng thỏa mãn (2.4). Theo Nhận xét 2.2, ta có = const với mọi X e c , tức là c chứa trong siêu phảng H = ịx 6 K ": = 0}, trong đó x° là điểm bất kỳ thuộc c . Cũng theo nhận xét trên, < cc với mọi y e D (do đó H n D = 0 ) vì nếu = a với y° nào đó thuộc D thì điều này chứng tỏ a là cực đại của hàm tuyến tính trên D. Định nghĩa 2.16. Ta nói hai tập lồi khác rỗng c và D của K" là tách hẳn bởi siêu phẳng H = (x e 1 " : = a} (t 6 K "\ {0}, a e l ) nếu in f > a > sup . (2.5) xeC yeD Về hình học điều đó có nghĩa là, các tập c và D nằm ở hai nửa không gian mờ khác nhau xác định bởi siêu phẳng H. 53 Định lý 2.9 (Định lý tách II). Hai tập lối đóng c , D trong [Rn khác rống, không cắt Iiliau với ít nhất một trong liai tập này là compac, có th ể tách hẳn bởi một siêu plìẩng, nghĩa là tổn tại một véctơỉ e [Rn (t * 0) và một sô'a e R sạo cho (2.5) tlìỏa mãn. Chứng m inh. Giả thiết c compac. Xét tập lồi c - D. Ta chứng' minh c - D đóng. Thật vậy, nếu zk = xk - yk —> z với xk e c và yk € D k k thì do c compac nên tồn tại dãy con ( X q } sao cho X q —> X e c. Do D đóng nên y kq = x kq - z kq - > X - z 6 D . Từ đó, z = X - y với X e c , y e D. Vậy, tập c - D đóng. Do 0 Ể c - D nên theo Hệ quả 2.3 (xem (2.3)) tồn tại véctơ t e R n \ (0) và một số T| sao cho > r| > 0, với m ọi X e c , y e D. Khi đó, in fxeC - ^ > s u p yeD + -J Đặt a = inf xeC - J , ta nhận được (2.5). N hặn xét 2.3. • Cả hai định lý tách chi nêu các điều kiện đủ để tách các tập lồi. • Nếu tập c là một nón thì trong cả hai Định lý 2.8 và 2.9 ta có thể lấy a = 0. • Định lý 2.9 không còn đúng nếu thiếu giả thiết "ít nhất một trong liai tập là com pac”. Chẳng hạn, hai tập c = ( x e K2 : x ,x 2 > 1, X| > 0, x2 > 0 ), D = (x e R 2 : X, > 0, x2 < 0Ị lồi dóng, khác rỗng và rời nhau nhưng không tách hẳn được bời một siêu phẳng, vì cả c và D đều không compac (xem Hình 2.15b). 54 :L> Hinh 2.15. Minh họa Định lý tách II và phàn ví dụ Lý thuyết tách các tập lồi được dùng để chứng minh nhiều sự kiện cơ bản của qui hoạch toán học, lý thuyết trò chơi và kinh tế toán. Nói riêng, nó được áp dụng để chứng minh các định lý đối ngẫu trong qui hoạch lồi, định lý minimax tổng quát trong lý thuyết trò chơi ma trận, để chứng minh sự tồn tại tình thế cân bằng trong các mô hình kinh tế cạnh tranh. 2.1.5. Phương lùi xa và nón lùi xa Tập các điểm có dạng x° + Ằ,d với x°, d e R", d * 0 và Ả > 0 gọi là một tia hay nửa đườìig thẳng xuất phát từ điểm x°, nếu x° = 0 thì ta có tia xuất phát từ gốc 0. Ta gọi d là véctơ chỉ phương (hay phương) của tia. Hai phương d' và d2 xem là như nhau nếu d' = a d 2 với a > 0. Định nghĩa 2.17. Cho c là một tập lồi trong IR". Véctơ d e R", d ÍÉ 0 gọi là một phương lùi xa của c nếu (x + Ằ.d:Ằ>0)cCVxeC (2.6) (mọi tia xuất phát từ một điểm bất kỳ X e c theo phương d đều nằm trọn trong c , xem Hình 2 .lóa). 55 o a) b) Hình 2.16. Nón lùi xa Định lý 2.10. Tập tất cả các phương lùi xa của c là một nón lồi. Nếu c đóng thì sẽ có (2.6) khỉ ịx° + Xd : X > 0} c C với một XH nào đó tliuộc c . C hứng m inh. Kết luận đầu có thể kiểm tra dễ dàng. Nếu c đóng và Ị Xo + A-d : X > 0 Ị c c với một Xo e c thì với bất kỳ X e c , n > 0 ta có X + (id G c , bởi vì X + nd = lim x->+00 zx. trong đó Định nghĩa 2.18. Nón lồi tạo nên bởi tập tất cả các phương lùi xa của m ột tập lồi c và véctơ 0 gọi là nón lùi xa của c , ký hiệu là rec c (Hình 2.16b). Đ ịnh lý 2.11 ([17], trang 13). Nón lùi xa của m ột tập lồi dóng c là m ột tập đóng. M ột tập lồi đóng c là compac khi và clù khi nón lùi xa của nó chỉ gồm duy nhất điểm 0. Ví dụ 2.7. Sau đây là các nón lùi xa của một số tập lồi trong KỊ2: C| = ((x, y) e K2 : X > 0, xy > 1Ị => rec c, = Ị(x, y) : X > 0, y > 0 |. c 2 = {(x, y) e [R2 : y > x2ị => rec Q = {(x, y) : X = 0, y > 0Ị. c 3= {(x,y) e K2 : x2 + y2< 1Ị =>recCi = ((x ,y ): x = 0 ,y = 0 |. c 4 = {(x, y) e IR2 : X > 0, y > 0} u {(0, 0)1 => rec C4 = C4 (tập không đóng). 56 2.1.6. Siêu phẳng tựa, diện, điểm cực biên và phương cực biên Sau đây là một số khái niệm quan trọng đối với cấu trúc hình học của tập lồi trong R": siêu phẳng tựa, diện, điểm cực biên và phương cực biên. Đ ịnh nghĩa 2.19. Một siêu phẳng H = (x e IR" : = a ) gọi là một siêu phẳng tựa của tập lồi c c i ” nếu có ít nhất một điểm Xo e c nằm trong H ( = a) và mọi điểm thuộc c cùng nằm trong một nửa không gian xác định bời H, chẳng hạn > a với mọi X e c . Khi đó, nửa không gian > a gọi là nửa không gian tựa của c . Nếu dim c = n thì điểm tựa Xo phải là một điểm biên thuộc ÕC. Ta có định lý sau đây về sự tồn tại siêu phẳng tựa. Đ ịnh lý 2.12. Qua mỗi điểm biên x° của m ột tập lồi C d " đều có ít nhất m ột siêu plìẳng tựa của c . C hứng m inh. Do Xo Ể ri c và ri c lồi (Định lý 2.6) nên theo Định lý 2.8 tồn tại siêu phẳng = a sao cho > a > , với mọi X e ri c . Suy ra = a. Vậy siêu phẳng H = {X : = ) là siêu phẳng tựa của c tại x°. □ Véctơ pháp tuyến của siêu phẳng tựa của c tại XH có tính chất đặc trưng sau: > 0 , Vx Ẽ c . Véctơ t thỏa mãn điều kiện trên không tạo nên góc tù với đoạn thẳng bất kỳ trong c có một đầu mút tại x°. Véctơ t đó còn được gọi là véctơ pháp tuyến trong của c tại xn (-t là véctơ pháp luyến ngoài). Tập tất cả các véctơ pháp tuyến trong của c tại Xo cùng với điểm 0 tạo nên nón pliáp tuyến trong Nc(x°) (Định nghĩa 2.14). Dễ dàng kiểm tra lại rằng Nc(x") là một nón lồi và nó chỉ gồm duy nhất điểm 0 khi x° là điểm trong của c (xem Hình 2.12). Từ các định lý trên suy ra định lý sau đây về biểu diễn các tập lồi đóng. 57 Định lý 2.13. M ột tập lồi đóng, không rỗng c * R" trùng với giao của tất cả các Iiửa kliông gian tựa của nó. C hứng m inh. Do c đóng khác rỗng và c * R" nên c có ít nhất một điểm biên (vì ri c * C). Cho nên theo Định lý 2.12 có ít nhất một nửa không gian tựa của c . Nếu ký hiệu E là giao của tất cả các nửa không gian tựa của c thì E *■ 0 . Rõ ràng, c c E. Giả sử E \ c * 0 và y e E \ c . Gọi Xo là hình chiếu của y Irên c , theo Hệ quả 2.3, (x 6 r : > 0} là một nửa không gian tựa cùa c, nhưng không chứa y, trái với y e E. Vậy c = E. Định nghĩa 2.20. Một tập con lồi F của một tập lồi c gọi là một diện của c nếu X, y e c mà ( 1 - X.)x + ^.y e F, 0 < X < 1 thì [x, y] a F, nghĩa là nếu một đoạn thẳng bất kỳ thuộc c có một điểm trong tương đối thuộc F thì cả đoạn thẳng ấy phải nằm trọn trong F. Một diện có số chiều 0 gọi là một điểm cực biên của c . Nói một cách khác, đó là một điểm thuộc c mà nó không thể là một điểm trong tương đối của một đoạn thẳng bất kỳ nào với hai đầu mút khác nhau thuộc c . Một diện có số chiều 1 gọi !à một cạnh của C: cạnh là hữu hạn nếu diện đó là một đoạn thẳng, cạnh là vô hạn nếu diện đó là một nửa hay cả đường thảng. Nếu một tặp lồi c có diện là một nửa đường thẳng thì véctơ chi phương của nửa đường thảng này gọi là một pliương cục biên cùa c. Tập các phương cực biên cùa c trùng với tập các phương cực biên của nón lùi xa của nó. Ví dụ góc không âm IR l có hai phương cực biên, đó là các véctơ đơn vị e 1 = (1, 0)T và e2 = (0, 1 )T; còn d = ( 1 1 )T cũng là một phương iùi xa, nhưng không là một phương cực biên. Tất nhiên, tập 0 và bản thân c cũng là một diện cùa c . Một diện của c , khác 0 và khác c , gọi là một diện thực sự cùa c . Ví dụ các diện thực sự của một khối lặp phương trong R- là 8 đình, 12 cạnh và 6 mặt cùa nó. 58 Các tính chất sau đây về diện của các tập lồi cũng đáng được chú ý: • Một diện của một nón lồi là một nón lồi. • Một diện của một diện của c cũng là một diện của c . • Một diện F của một tập lồi đóng c là một tập lồi đóng. • Giao của tập lồi c với một siêu phẳng tựa của c là một diện của c. • Giả sử E c K" là một tập bất kỳ và c = conv E. Khi đó, mọi điểm cực biên của c đều thuộc E. 2.1.7. Biểu diễn tập lồi qua các điểm cực biên và phương cực biên Định lý 2.14 ([17], trang 26). Một tập lồi đóng c * 0 có điểm cực biên khi và chỉ khi nó không chứa một đường thẳng nào. Định lý 2.15 ([17], trang 26). Nếu c cz R" là một tập lồi đóng và không cliứa một đường thẳng nào thì c = conv V(C) + cone U(C), trong đó V(C) là tập các điểm cực biên của c và U(C) là tập các phương cực biên của c (xem minh họa ở Hình 2.17 với lưu ý cone U(C) = rec C). Hệ quả trực tiếp của Định lý 2.15 là định lý quan trọng sau đây tương ứng với trường hợp U(C) = 0 (rec c = 10 Ị). Hệ quả 2.5 (Định lý Minkowski). Mọi tập lồi compac C / 0 bằng bao lồi của các điểm cực biền của nó (xem minh họa ở Hình 2.18). Chẳng hạn, hình cầu đơn vị đóng ( x e K3 : x f + X 2 + X 3 < l ) trùng với bao lồi của mặt cầu biên |X S IR 3 :XÍ! + X 2 + X 3 = 1 Ị của nó, mặt cầu này là tập các điểm cực biên của hình cầu đơn vị đóng. 59 Hình 2.17. c = conv V(C) + rec c Hinh 2.18. c = conv V(C) 2.1.8. T ập lồi đa diện Định nghĩa 2.21. Một tập lồi mà là giao của một số hữu hạn nửa không gian đóng gọi là một tập lồi đa diện. Nói cách khác, đó là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính: < a\ x> < bj, i = 1 , , m (a' 6 Kn, b, e IR), (2.7) nghĩa là tập các X nghiệm đúng Ax < b với A là một ma trận cấp mxn và b £ Km. Vì một phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất phương trình tuyến tính nên một tập lồi đa diện cũng là tập nghiệm của một hệ các phương trình và bất phương trình tuyến tính: = bị, i = 1, 2 ,..., p < a\ x> < b„ i = p + 1 ,..., m. Hạng của hệ bất phương trình tuyến tính (2.7) được định nghĩa bằng hạng của ma trận A. Nếu hạng của hệ này bằng m thì ta nói hệ dộc lập tuyến tính. Một tập lồi đa diện có thể không bị chặn (không giới nội). Một tập lồi đa diện mà đồng thời là một nón lồi (tương ứng với trường hợp b = 0) gọi là một nón lối đa diện. M ột tập lồi đa diện bị chặn còn được gọi là một đa diện lối. Các đa giác lồi theo nghĩa thông thường trong R 2 là những ví dụ cụ thể về đa diện lồi. 60 Mỗi điểm cực biên của một tập lồi đa diện còn được gọi là một đỉnh của nó. Tập các đỉnh của c ký hiệu là C . Mỗi cạnh vô hạn của một tập lồi đa diện tương ứng với một phương cực biên của nó. Cho tập lồi đa diện D * 0 xác định bởi hệ bất phương trình tuyến tính (2.7). Khi đó mỗi bất phương trình (2.7) gọi là một ràng buộc của D. Ta nói điểm Xo 6 D thỏa mãn chặt ràng buộc i* nếu < a '\ x°> = b|. Với mỗi X e D ký hiệu I(x) = (i : = bị} là tập chỉ số của những ràng buộc thỏa mãn chặt tại X. Ký hiệu I(, = (i : = bị với mọi X e D}. Tính chất đặc trưng của các diện (nói riêng, các đỉnh và cạnh) của D được cho trong định lý sau: Định lý 2.16 ([17], trang 31). M ột tập con klìác rỗng F c D l à một diện thực sự của D khi và clủ klii F = {x : = b¡, i e I; < b¡, i Ể lị với I là một tập chỉ s ố sao cho 1(1 c I c Ị 1 ,..., m Ị (I - tập chi sô' xác dinh diện F). Hơn nữa, ta có dim F = n - rankịa' : i e 1} VÀ dim D = n - rankja' : i e I0). Hệ quả 2.6. Nếu D là một tập lồi đa diện xác định bởi hệ (2.7) thì a) Điểm x( e D là một đỉnlì của D khi và chỉ khi ra n k ịa‘: i e I(x°)} = n, nghĩa là Xo thỏa mãn chặt n ràng buộc dộc lập tuyến tính của hệ (2.7); b) Nếu một đoạn lliẳng (nửa dường thẳng hay cả dường tliẳng) ĩ c D là m ột cạnli của D thì r dược xác định bởi một tập chi s ố I sao cho rank I a' : i e IỊ = n - 1, tức là mọi X e ri r cùng tliỏa mãn chặt n - 1 ràng buộc dộc lập tuyến tínli của liệ (2.7). Mỗi lập lồi đa diện chi có một sô hữu hạn đỉnh và cạnh (hữu hạn hay vô hạn). 61 Hình 2.19. Tặp lồi đa diện Trong K" một đa diện lồi có k + l (0 < k < n) đỉnh độc lập afin gọi là một k- dơn liình. Ví dụ trong R \ 0 - đơn hình là một điểm, l- đơn hình là một đoạn ihẳng, 2 - đơn hình là một tam giác, 3 - đơn hình là một tứ diện. Tập s = {X e R" : X; > 0 Vi, X| + ... + x„ < 11 gọi là một đơìi lùnli chuẩn trong K". Khi n = 3 ta có một tứ diện với 4 đỉnh là (0, 0, 0); (1, 0, 0); (0, 1, 0) và (0, 0, 1) (xem Hình 2.20). V 0 - đơn hình 1 - đơn hình 2 -đơn hình 3 -đơn hình đơn hình chuẩn Hình 2.20. Các đơn hình trong R3 Ta có định lý biểu diễn sau đây đối với các tập lồi đa diện. Đ ịnh lý 2.17. a) M ỗi đa diện lồi c bâng bao lồi của lất cà các đỉnh của nó: c = convC liay X e c khi và cliỉ klii X = x.,v' + ... +  pv p với mọi X, > 0, + ... + /vp = 1 và v' (i = 1 ,... , p) là các dỉnlì của c. 62 b) Veri tập lồi đa diện c kliông giới nội, m ối X e c có thê biêu diễn dưới dạng một tổ hợp lồi của các đỉnli của c cộng với một tố hợp tuyến tính không ám của các phương cực biên của c , Iiglũa là X e c <=> X = Ầ,,v' + ... + ?,pvp + n,u' + ... + nquq với mọi X; > 0, X| + ... + A,p = 1, |ij > 0, p, q > 0 là s ố nguyên, v' là các đỉnh của c (i = 1, , p), UJ (j = 1, ... , q) là phương của các cạnli vô hạn của c . Với tập lồi đa diện c không có đính thì trong biểu diễn trên chí cần các v 'e C v à các UJ e rec c. Định lý trên cho thấy ứng với mỗi tập lồi đa diện c cho trước có hai nhóm hữu hạn véctơ, sao cho tập lồi ấy chính là tập tất cả các điểm có thể biểu diễn thành tổng của một tổ hợp lồi của các véctơ thuộc nhóm thứ nhất và một tổ hợp tuyến tính không âm của các véctơ thuộc nhóm thứ hai. Các véctơ trong nhóm thứ nhất đều thuộc c , các véctơ trong nhóm thứ hai đều là các phương vô hạn của c . Nếu c bị chặn thì trong biểu diễn trên chỉ còn lại tổng thứ nhất. Ngược lại, có thể chứng minh được rằng nếu cho trước hai nhóm hữu hạn véctơ thì tập tất cả các điểm có biểu diễn như trên xác định một tập lồi đa diện. 2.2. HÀM L ổ l 2.2.1. Hàm lồi và hàm lõm Định nghĩa 2.22ễ + Hàm f : s —> [-00, +00] xác định trên một tập hợp lồi S ç R" gọi là một hàm lồi trên s nếu với mọi X1, X2 e s và mọi số thực X e [0, 1] ta có fl(l - 1 ) \' + l x 2] < (1 - A-)f(x') + À.f(x2), 63 mỗi khi vế phải được xác định, nghĩa là hệ thức trên cần được thỏa mãn trừ khi f(x') = - f(x2) = ± 00 (vì biểu thức + 00, - 00 không có nghĩa). + Hàm f gọi là hàm lồi cliật trên s nếu với mọi X1, X2 e s, x' * X2 và mọi K e (0,1) ta có f[(l -X.)x' + X.X2] < ( 1 -A .)f(x') + Ằ f(x2). Hiển nhiên một hàm lồi chặt là lồi, nhưng điều ngược lại không đúng. + Hàm f gọi là hàm lõm (lõm chặt) trên s nếu - f là lồi (lồi chặt) trên S; gọi là tuyến tính afin (hay đơn giản là afin) trên s nếu f hữu hạn và vừa lồi vừa lõm trên s. Một hàm afin trên R n có dạng f(x ) = + a với a e Mn, a e K, bởi vì với m ọi X1, X2 e R" và mọi X e [0 , 1 ] ta có f[(l - l ) x ' + Xx2] = (1 - Ằ.)f(x‘) + A.f(x2). Tuy nhiên, hàm afin không lồi chặt hay lõm chặt. Hình 2.21. Hàm lồi chặt Hình 2.22. Hàm lối (không chặt) Định nghía 2.23. Cho hàm bất kỳ f : s —> [-0C, + x ] với s c Kn, các tập dom f = {x e S :f(x )< + ooỊ và epi f = ((x, a ) £ SxDS : f ( x ) < a |, được gọi lãn lượt là miên hữu dụng và lập trên dồ thị của hàm f. Nôu dom t khác rông (f không đồng nhất bàng + x ) và f(x) > - X 64 với mọi X € s thì ta nói hàm f là clứnlì tlĩường. Nói cách khác, f chính thường nếu dom f * 0 và f hữu hạn trên dom f. ■&. Có thể chứng minh rằng hàm f lồi trên s khi và chỉ khi a) tập trên đồ thị epi f là một tập lồi, hoặc m m m b) f(2]x.| 0 k=l k=l k=l với mọi k, trong đó m là số nguyên > 2 (bất đẳng thức Jensen). is. Hàm lồi f : s —> [-0O, +00] có thể được mở rộng thành hàm lồi xác định trên toàn không gian [Rn bằng cách đặt f(x) = + 00 với mọi X í s. Vì vậy để đơn giản ta thường xét hàm lồi trên toàn K". Sau đây là một số ví dụ quen thuộc về hàm lồi (C d K" là một tập lồi khác rỗng): Hàm chuẩn Euclid IIXII = yj< x ,x > , X e R n. Hàm chỉ của C: ỗc(x) = Hàm tựa của C: Sc(x) = supyeC (cận trên của xTy ữên tập C). Hàm khoảng cách từ điểm X e K" tới C: dc(x) = infyeC llx - yll. Bốn phép toán cơ bản bảo toàn hàm lồi (suy ưực tiếp từ định nghĩa): a) Nếu f ; : R n —» R (i = 1 ,..., m) là hàm lồi thì a ,f | + ... + a mfm lồi với mọi (X; > 0 và lồi chặt nếu ít nhất một trong các hàm f; lồi chặt với dị > 0. b) Nếu f| (i e I) : K" K là hàm lồi thì f(x) = sup i e I f,(x) là hàm lồi. c) Nếu A : R n -» Km là biến đổi tuyến tính và g : -> 0& là hàm lồi thì hàm hợp f(x) = g(Ax) là hàm lồi. 65 d) Nếu g : D £ K" -» K là hàm lồi và h : R —» IR là hàm lồi không giảm thì hàm hợp f(x ) = h (g (x )) là hàm lồi. Ví dụ 2.8. Theo d), hàm f(x) = c ,e 6,(x) + ... + cme gm 0 và mọi hàm g,(x) lồi (chẳng hạn f(X|, x2) = e x,+x-’ + 2e X|_Xỉ là hàm lồi). Định lý sau đây nêu mối liên hệ đáng chú ý giữa hàm lồi và lặp lồi. Định lý 2.18. Giả sử ỉ : Bỉ" -» [-00, +co] là một liàm lồi trẽn Kn và a e [- 00, + 00]. Khi đó, các tập mức dưới c a = {x : f(x) < a} , Ca = |x : f(x) < a ) là tập lồi. Tương tự, nếu f Jà m ột hàm lõm trên R" thì các lặp mức trên Dp = (x : f(x) = (x : f(x )> Pl là tập lồi. C hứng m inh. Theo định nghĩa của hàm lồi, ta có f[(l - X.)x‘ + Ầx2] < max (f(x'), f(x2)| V x1, X2 6 K". X e (0, 1). Từ đó suy ra các kết luận cùa định lý. Hình 2.23. Tập mút dưới hàm lõi, tập mức ừên hàm lõm ■&. Tuy nhiên, mệnh đề đảo cũa định lý trên không đún°. 66 Mở rộng hàm lồi: Một hàm f mà mọi tập mức dưới là tập lồi gọi là một hàm tựa lồi. Ví dụ f(x) = X3 hay f(x) = Ặ x ị trên R là hàm tựa lồi nhưng không lồi. Định lý sau đây nêu lên một tính chất đặc trưng cơ bản của các hàm lồi. Định lý 2.19. Clio c là một tập lồi, kliác rỗng trong Kn vù f : K" —» K 1(1 một liàm lồi. Mọi điểm cực lie’ll địa phương của f trẽn c (lêu lù điểm cực tiểu toàn cục. Tập ArgminxeCf(x) lù tập con lồi của c. C hứng m inh. Già sứ x" e c là một điêm cực tiểu địa phương của f trên c và U (x°) là m ột lân cận của Xo sao ch o f(x") < f(x ) với mọi X e c n U(x"). Với bất kỳ X £ c ta có X; = A.X + ( 1 - X)x" 6 c n U(x°) với mọi X > 0 đù nhỏ. Khi đó, f(x").) 0 nên f(x°) < f(x). Vì X e c được chọn tùy ý nên x" là điếm cực tiểu toàn cục của f trên c . Nếu a = min (f(x) : X e C | thì A rgm inxeCf(x) trùng với tập c n )x : f(x) < a Ị . Tập này lồi do hàm f(x) lồi (xem Định lý 2.18). Hệ qu ả 2.7. Bất cứ điểm cực (lại địa pliương nào của một hàm lõm trên một tập lồi cũng là điểm cực đại toàn cục. Tập tất cả các điểm cực dại của m ột liàm lõm trẽn một tập lồi là lồi. Định lý 2.20. M ột lìàm lồi chặt f trên một tập lồi c có nlứêit nhất một điểm cực tiểu trên c , nglũa là lập Argmin xeC f(x) gồm nhiêu nliất m ột phần lử. C h ứ n g m in h . N êu f c ó hai điểm cực tiểu khác nhau X1, X2 e c thì do tính lồi chặt của f nên f ( | x ' + j r ) < f ( x ' ) = f(x2), điều này không thể xảy ra! 67 Ví dụ 2.9. Hàm lồi chặt một biến f(x) = X2 có duy nhất mội điểm cực tiểu X* = 0. Còn hàm lồi chặt f(x) = e x (x e R) không có điểm cực tiểu nào. ■&. Hàm lồi n biến có mối quan hệ chặt chẽ với hàm lồi mội biến. Ta có: Đ ịnh lý 2.21. Hàm f(x), X e K", là liàm lồi khi và clù khi hàm một biến số(ỹ{ì.) = f(x + Àd) là liàm lồi tlieo X với mỗi X, d e R". Chứng minh. Điều kiện cần là rõ ràng. Ta chứng minh điều kiện đủ. Giả sử w)x + Ằy) = f(x + x.d) = ọ (X) = cp(( 1 - A.).0 + 'h. 1 ) < ( 1 - X)q>(0 ) + 1 ) = ( 1 - X)f(x) + >J(y). 2.2.2. H àm lói liên tục Định lý 2.22. Hàm lồi chính thường f trên R n liên tục tại mọi điểm trong của miền hữu dụng của nó (f liên tục trên int (dom f))- Chứng m inh. Giả sử x° 6 int (dom 0- Với mọi i = 1, , n, hàm thu hẹp của f trên khoảng mở {t : Xo + te' e int (dom f)l liên tục trên khoảng này. Vì thế, với mọi E > 0 cho trước và với mọi i = 1 , , n ta có thể chọn 5, > 0 đủ nhỏ sao cho lf(x° + X) - f(x°)l < 8 V x e [- 6,e\ + 5,e']. Giả sừ ỗ = min ) ô, : i = 1....... n Ị > 0 và B = (x : llxll, < ÔỊ (llxll, = max {lxàl , ..., lxnl|). Ký hiệu d' = Se1. dn+' = - Se1, i = 1. , n. Khi đó, có thể thấy rằng mọi X e B có dạng X = ^ d ' + ... + A.2nd2n với Xị + ... + = 1, > 0. Từ đó f(x° + x) < A.,f(x° + d 1) + ... + X,2nf(x° + d2n). 68 Vì thế, f(x° + X) - f(x°) < Ầ,[f(x° + d1) - f(x°)] + ... + ^ n[f(x° + d2") - «Xo)]. Như vậy, lf(x° + X) - f(x°)l < Ầ ,lf(x n + d 1) - f(x °)l + ... + X.2nlf(x° + d 2n) - f(x °)l < E với mọi X e B. Điều này chứng tỏ f(x) liên tục tại x°. N hận xét 2.4. Một hàm lồi chính thường chỉ có thể gián đoạn tại những điểm biên của miền hữu dụng của nó. Ví dụ 2.10. Xét hàm một biến số xác định trên tập D = [0, + oo) có dạng: f(x) = ex với mọi X > 0 và f(0) = 2. Dễ thấy epi f là tập lồi nên f là hàm lồi trên D. Hàm f liên tục tại mọi điểm trong X > 0 và gián đoạn tại điểm biên X = 0. Tại X = 0 hàm f nửa liên tục trên. Đ ịnh lý 2.23. Giả sử f là một liàm lồi clĩính tliườiig trên R". Klii đó, các điều sau đây là tương đương: a) f liên tục tại điểm Xo. b) f bị chặn trên trong một tập m ỏ chứa x°. c) int (epi f ) * 0 . d) int (dom f) * 0 và f liên lục trên int (dom f). C hứng m inh. a) => b) Nếu f liên tục tại điểm x° thì tồn tại một lân cận mờ u của Xo sao cho f(x) < f(x°) + 1 với mọi X e u , tức là f(x) bị chặn trên trong u . b) => c) N ếu f(x) < M với mọi X trong một tập m ở u thì u X [M, +00) c epi f, vì thế int (epi f) * 0- c) => d) Nếu int (epi f) * 0 thì tồn tại một tập mở u c 1" và một khoảng mở I c: K sao cho u XI c epi f, nên u c dom f, nghĩa 69 là int (dom f) khác rỗng. Theo Định lý 2.22 hàm f liên tục Irẽn int (d o m f). d) => a) là hiên nhiên. 2.2.3. H àm lồi khá vi Định lý 2.24 ([17], trang 44). a) Một hàm thực một bien cp(l) kliá vi troiiỊỊ một klioàiiỊỊ mà lù lồi klìi và chỉ kill dạo hàm của nó cp’(t) là một hàm không ỊỊŨim. b) Mội liàm thực một biến cp(t) liai lần kluỉ vi trong một klittàng nui là lồi klii và chi khi (lạo liàm cấp liai cùa nó ọ"(t) không âm Il l’ll loàn bộ khoảniỊ mở Iiàv. Ví dụ 2.11. Các hàm c \ x2k với k = 1,2, ... và hàm xlogx (dược xác định bằng 0 khi X = 0) lồi trong R +. Các hàm Inx, yf\ lõm trong 's. Đè nhận biết hùm lồi. người ta còn sử dụng các tiêu chuẩn sau (trường hợp khá vi). Định lý 2.25. Clio một tập lồi C c R " và một liíim f : R" -> R khá vi trên c . a) H ừ m f lồ i Il l'll c k lii và c l i ỉ U ú f(y) > f(x) + với mọi X. y 6 c. b) N ế u f(y ) > f(x ) + < V f( x ), y - x > với m ọ i X, y e c , X * y thì hùm f lồi chặt trên c . C hứng m inh, a) Giá sử hàm f lồi trên c . Vứi mọi X. V 6 c và với mọi số Ằ e [0. 1 ], ta có Âf(y) + (1 - Â)f(x) > t'[Ây + ( 1 ->.)x]. Từ đó suy ra v ) 6 | 0 70 Cho qua giới hạn ở vế phải khi X 4 0+, ta được f(y) - f(x) > . Ngược lại, giả sử f(y) > f(x) + với mọi X, y e c . Với bất kỳ X, y 6 c và 0 < X < 1, đặt z = A.X + (1 - >0y. Do c lồi nên z e c . Với X và z ta có f(x) - f(z) > . Với y và z ta có f(y) - f(z) > . Nhân bất đẳng thức đầu với X, bất đẳng thức sau với (1 - X) và cộng lại ta có Xf(x) - Xf(z) + ( 1 - x.)f(y) - ( 1 - X)f(z) > Ả + (1 - X.) hay Xf(x) + ( 1 - X)f(y) > f(z) + - = f(z). Nhớ rằng z = Xx + ( 1 - Ầ)y nên bất đẳng thức trên trở thành Xf(x) + (1 - Ằ)f(y) > f(A.x + (1 - X)y). điều này chứng lỏ hàm f lồi. Phần b) chứng minh hoàn toàn tương tự như chứng minh điều kiện đù của a) ờ trên. Định lý 2.26. Cho một tập lồi m ở C a Rn và một hàm f : Rn —» R liai lần kliả vi liên tục trên c . v 2f(x) là ma trận Hessian các dạo luìni riêng cấp 2 của ỉ tại X. a) Nếu v 2f(x) nửa xác định dương Yin mỗi X e c ( > 0. với mọi y 6 R n) hoặc nếu v 2f(x) có mọi giá trị riêng không úm thì liàm f lồi trên c . 71 b) Nếu v 2f(x) xác định dương với m ỗi X 6 c (tức là > 0 , với mọi y e 0T \ (0 )) hoặc nếu v 2f(x) có mọi giá trị riêng dương thì hàm f lối chặt trẽn c . c) Nếu c = 1" và hàm ỉ lồi tlù v 2f(x) nửa xác định dương với mọi X e R". Chứng m inh, a) Với mọi X, y E c , theo công thức khai triển Taylor bậc 2 la có f(y) = f(x) + + — với a e [0, 1]. Vì thế, do v 2f nửa xác định dương nên ta nhận được f(y) > f(x) + < V f(x), y - x> với mọi X, y E c. Từ Định lý 2.25 a) suy ra hàm f lồi. b) Chứng minh tương tự như trong phần a) suy ra f(y) > f(x) + < V f(x), y - x> với mọi X, y e c . Theo Định lý 2.25 b) hàm f lồi chặt. c) Giả sử f : r -» R là hàm lồi. Nếu v 2f(x) không nửa xác đ ị n h d ư ơ n g v ớ i m ọ i X € K n t h ì p h ả i c ó m ộ t p h ầ n t ử X e K n v à m ộ t phần tử y e IRn sao cho < 0. Do v 2f(x) gồm các hàm l i ê n t ụ c t h e o X n ê n t a c ó t h ể c h ọ n y v ớ i llyll đ ủ n h ỏ s a o c h o < 0 với mọi a € [0, 1], Khi đó. lại dùng cõng thức khai triển Taylor bậc 2 ta suy ra f(x + y) < f(x) + , trái với kết luận a) Định lý 2.25 vì f là hàm lồi. Vậy v 2f(x) nửa xác định dương với mọi X 6 Kn. Hệ quả 2.8 (Điểu kiện cần cho hàm lồi I lõm). Giá sứ f : ỊRn -> R là một hàm hai lấn khả vi liên tục và fỹ(x) là dạo hàm riêng hai lần của f theo cùng biến Xj. 72 a) N ếu f(x ) lồ i thì fjj (x ) > O, j = 1, . . . , n với m ọi X. b) N ếu f(x) lõm thì fjj (x) < o, j = 1 ,..., n với mọi X. c) N ếu f(x) lồi cliặt liay lõm chặt thì các bất đẳng thức trên được thay tương ứng bảng các bất đẳng thức thực sự > hay <■ Định lý 2.27. Cho Q là một ma trận vuông đối xứng thực cấp nxn. Hàm toàn phương f(x) = lồi khi và chỉ kill Q nửa xác định dương. Hơit nữa, hàm f lồi chặt klii và chỉ khi Q xác định dương. C hứng m inh. Dễ kiểm tra rằng v 2f(x) = 2Q với mọi X e Kn. Vì thế, theo Định lý 2.26 a), c) hàm f lồi khi và chi khi ma trận Q nửa xác định dương. Nếu Q xác định dương thì theo Định lý 2.26 b) hàm f lồi chặt. Ngược lại, nếu hàm f lồi chặt (do đó, f lồi) thì từ kết luận a) suy ra Q nửa xác định dương và do đó Q có mọi giá trị riêng không âm. Ta sẽ chứng tỏ Q xác định dương bằng cách chỉ ra Q không thể có giá trị riêng 0. Thật vậy, giả sử có một véctơ riêng X * 0 tương ứng với giá trị riêng 0, tức là X thỏa mãn Qx = 0. Nếu . h í , M . R . „ . 0 * d . « i KU> * « . , ) ] - 0 . RO), .rái với tính lồi chạt của hàm f. H ệ qu ả 2.9. Hàm bậc hai f(x) = — + + a 2 lồi (lồi chặt) trên R n khi và clii' khi ma trận Q nửa xác định dương (xác định dươìig) và f lõm (lõm cliặt) trên K" khi và chỉ khi ma trận Q nửa xác clịiìli ám (xác địnli âm). Ví dụ 2.12. Xét hàm f(x) = f(X|, x2) = X f - 2x,x2 + 3x 2 . Ta thấy Vf(x) =' 2x, - 2 x 2 ' V-2 X | + 6 x 2y và v 2f(x) = [ 2 -2 1 1 -2 6 73 Do v 2f(x) xác định dương với mọi X nên hàm f đã cho lồi chặt trên [R2. 2.2.4. Dưới vi phân Định nghĩa 2.24. Cho hàm lồi chính thường f trên K", véctơ p e R" gọi là dưới gradient của f tại điểm x" nếu + f(x") < f(x), Vx £ 1". (2.8) Nếu f lõm và trong (2.8) thay < bởi > thì p là dưới gradicnt cùa r ế ■ 0 r tại X . Hình 2.24. Dưói gradient p e <9f(x°) Tập tất cá các dưới gradient của f tại x" gọi là dưới vi pluìn cúa f tại x" và ký hiệu là ỡf(x"). Hàm f được gọi là kliá diári vi phán tại x" nếu + tn+lf(x") > + tn+la với mọi (x, a ) e epi f. 74 Vì (x, a ) e epi f kéo theo (x, ß) e epi f với mọi ß > a cho nên ta cũng có + tn+|f(xH) > + tn+lp với mọi ß > a và cho ß —» + 00 ta suy ra tn+| < 0. Nhưng nếu tn+| = 0 thì bất đẳng thức này trở thành > với mọi X E dom f, tức là Xo đạt cự c đ ại c ủ a h à m tu y ế n tính trê n dom f, m à Xo 6 int (dom 0 , nên điều này chỉ có thể xảy ra khi t = 0, mâu thuẫn với (t. tn+|) * 0. Vậy tn+l < 0. Đặt p = - t/tn+| và a = f(x) ta sẽ nhận được bất đẳng thức (2.8). Để chi rõ ỡf(x") lồi ta lấy bất kỳ p1, p2 e ổf(x"), X € [0, 1]. Khi đó với mọi x e r thì <Ầp', X - x"> < Ầ(f(x) - f(x")) và <(l -7i)p2, x - x " > < ( l -Ầ )(f(x)-f(x'’)) => <^p' + ( 1 - Ầ)p2, X - x"> < f(x ) - f(x") => Ằ.p' + ( 1 - Ầ)p" 6 ổf(x") => ổf(x") lồi. Đê chi rõ ổf(x°) là tập đóng, lấy pk e ổf(x"), pk -> p. Từ < p k, X - x " > + f ( x " ) < f ( x ) v ớ i m ọ i X e D&" s u y r a < p , X - x " > + f ( x ° ) < f ( x ) v ớ i m ọ i X e R n, c h ứ n g t ỏ p € ổ f( x " ). Ví dụ 2.13. Sau đây là dưới vi phân của một số hàm quen thuộc. I ) Hàm afin f(x) = + a (il e IR", a e R) có ỡf(x) = (aỊ, (Vx e Kn). 2) Dưới vi phân cùa hàm chi ỗc(x) của một tập lồi c 5É 0 tại một điểm Xo e c chính là nón pháp tuyến ngoài của C: ổôc(\°) = (p : < 0 Vx e C |. 3) Nếu f(x) = Il X il (chuẩn Euclid) thì 75 0 _ í { p : | | p | | < l } k h i X o = 0, 5f(x ) - | | xoỵ||xO||ỊkhẮ is. Liên hệ giữa dưới vi phàn và đạo hàm: Theo định nghĩa, hàm f khả vi tại điểm x° nếu tồn tại véctơ Vf(x°) (véctơ gradieni cùa f tại x") sao cho f(x" + d) = f(x°) + + o(lldll). Điều nảy tương đương với f(x ° + X .d ) - f ( x J = < v f(x «)i d>) Vd e Ü0 X Định lý 2.29. Nếu f là hàm loi chính thường, kliả vi lại điểm Xo € dom f thì ổf(x") = |V f(x")}, tức là Vf(x°) là véctơ dưới gradient duy nhất của f tại Xo. Chứng m inh. Nếu p € ỡf(x°) thì với mọi d e IRn, d # 0, và mọi X > 0 ta có + f(x°) < f(x° + ^.d) h a y f ( x ° + ?Ld) - f ( x ° ) > Ả. . Chia bất đẳng thức sau cho À. và cho qua giới hạn khi K -> 0+ ta được > với mọi d e IRn. Do đó > 0 với mọi d e R n. Từ đó suy ra p = Vf(x°). Ngược lại có thể chứng minh rằng nếu f có tại x" một véctơ dưới gradient duy nhất thì f khả vi tại x°. Như vậy, khái niệm dưới gradient là sự mở rộng của khái niệm gradient (tại những điểm ờ đó hàm không khá vi). • Đạo hàm theo hướng. Cho f : o r -> [-00, +00] là một hàm bất kỳ và Xo là một điểm tại đó f hữu hạn (nghĩa là lf(x°)l < + 00). 76 Đ ịnh nghĩa 2.25. Với d e R " \ (0 | nếu tồn tại giới hạn (hữu hạn hay không) i:_ f ( x ° + M ) - f ( x ° ) lim ------------- ------------ Ü0 X thì giới hạn đó gọi là đạo hàm theo hướng d của f tại Xo, ký hiệu là f (x , d). Định lý 2.30ỗ Nếu f là hàm lồi clìínli tlìường thì f có đạo liàm tlieo mọi hướng tại mọi điểm Xo e d o m f v à f( x ° + d ) - f i x '1) > f ( x (l, d). Chứng minh. Do hàm f lồi nên hàm một biến (p(Ầ) = f(x" + tai) lồi và theo Định nghĩa 2.25 thì f (Xo, d) = lim k ± M z í < í ! > = Ị to ỉ & t m = cp' (0). ÜÖ X ÜÖ X Nếu với mọi X > 0 mà x° + A.d Ể dom f thì f(x° + Ầd) = 0 cho nên (p+ (0) = + 00, và định lý đúng. Còn nếu có một Ä-0 > 0 để x° + A,od e dom f thì với 0 < À. < A-0 ta có X = — + ( 1 - — )x0 và 0 < — < 1. X0 Ằ,0 X0 Do hàm (p lồi nên cp(A.) < ^ tp ( ^ o ) + (1 - ^ ) 0+. Vì thế tỉ số này dần tới một giới hạn (hữu hạn hoặc - 00) lim Í Í M z S E „ i„ f î W z S Îg ) , , UÖ X >->0 Ả đồng thời với mọi Ằ > 0 ta luôn có 77 (p(X) ^ > ẹ'+ (0 ) = f’(x". d). A, C h o K = 1 ta c ó (f)(1) - cp(0) > (p'+ (0), lức là f(x" + d ) - f(\" ) > r(x". d). Định lý sau nêu mối liên hệ giữa dưới vi phân và đạo hàm theo hướng. Định lý 2.31. Nếu f là một liàm lồi cliínli thường và x" 6 dom f th ì p e ỡ f(x (l) k h i v à c liỉ k lìi < f ’(x". li) v ở i II1ỌI d 6 R " \ | 0 | . C hứng m inh. Bàng cách đặt X = x" + A.d và .d), ta có thể viết lại bất đảng Ihức về dưới gradient (2.8) thành < [f(x" + h i) - f(x")]A = [(P(X.) - cp(0)]A Vd * 0, V/. > 0. bất đẳng thức này tương đương với < in f)>() [(p(>.) - cp(0)] / với mọi d. Từ chứng minh Định lý 2.30 cho thây in f>>0[ọ(/.) - cp(0)]A = f’(x", d) với mọi d 0. Vì thế, ta có < f ’(x", d) với mọi d * 0. 2.2.5. H àm lồi m ạnh Sau đây ta xét một lớp hàm luôn có cực tiểu trôn mọi tập đóng khác rỗng. Hơn nữa, giống như đối với hàm lồi chặt, cực tiêu này là duy nhất nếu tập đó là lồi. Định nghĩa 2.26. Hàm f(x) xác định trên một tập lồi C c R " gọi là lồi m ạnh, nếu tồn tại hằng số p > 0 (hằng sô' lồi mạnh) sao cho với V X, y € c và mọi số Ằ e [0, 1] ta có bất đáng thức: f U x + ( 1 - À )y ] < /,f(x ) + ( 1 - X )f(y ) - M 1 - À.)pllx - yll". Có thể chứng minh rằng hàm f(x) lồi mạnh khi và chỉ khi hàm f(x) - p.llxll lồi. Rõ ràng một hàm lồi mạnh thì lồi chặt, nhưng điều ngược lại không chắc đúng. Chẳng hạn, hàm e x với m ọi X e R . lồi chặt nhưng không lồi mạnh. 78 Các hàm lồi mạnh có vai trò đặc biệt quan trọng trong nghiên cứu các bài toán tối ưu. Ví dụ 2.14ế Hàm f(X|, x2) = x f + 2x? lồi mạnh. Tống quát, xét hàm bậc hai f(x) = — + , với Q là một ma trận vuông đối xứng cấp n xác định dương và p 6 R". Tính lồi mạnh của f được suy ra từ hệ thức (sau khi thực hiện một số tính toán đơn giản): f[Ằx + ( 1 - Ầ)y] < ;ư(x) + ( ] - ^)f(y) - Ằ( 1 - X)<\ - y, Q(x - y)> < Ảf(x) + ( 1 - Ầ)f(y) - Ằ( 1 - A.)pllx - yll2, đè ý rằng với 0 < X < 1 thì Ằ.2 < Ấ, ( 1 - A.)2 < ( 1 - ^-) và vì rằng > pllx - yll2, trong đó p là giá trị riêng nhỏ nhất (dương) của ma trận Q. Định lý 2 .32. N ếu liàm f(x) lồi mạnh và khả vi trên tập lồi dóng c thì a) > pllx - yll2 với mọi X, y 6 C; b) với bất kỳ x° 6 c tập mức dưới C() = ( X e c : f(x) < f(x°) Ị bị chặn; c) tồn tại duy nliâ't điểm X* e c sao cho f(x*) = min ( f(x) : X e C ). C hứng m inh, a) Do f lồi khả vi nên theo Định lý 2.25, với mọi X, y e c thì f(x) - f(y) < . Hơn nữa, do f lồi mạnh nên với X = — ta có: 2 79