Tài liệu Bài toán quy hoạch toàn phương với ràng buộc toàn phương lồi

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN THÀNH CHUNG BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG VỚI RÀNG BUỘC TOÀN PHƯƠNG LỒI LUẬN VĂN THẠC SĨ Chuyên ngành: Toán Giải tích Hà Nội-2012 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN THÀNH CHUNG BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG VỚI RÀNG BUỘC TOÀN PHƯƠNG LỒI Chuyên ngành: Toán giải tích Mã số: 60 46 01 LUẬN VĂN THẠC SĨ TOÁN GIẢI TÍCH Người hướng dẫn khoa học: PGS. TS. Nguyễn Năng Tâm Hà Nội 2012 LỜI CẢM ƠN Luận văn này được hoàn thành với sự hướng dẫn và chỉ bảo của PGS.TS. Nguyễn Năng Tâm . Em xin được bày tỏ lòng biết ơn sâu sắc đối với sự quan tâm, động viên và sự chỉ bảo hướng dẫn của thầy. Tôi xin cảm ơn các thầy cô Phòng Sau đại học Trường Đại học Sư phạm Hà Nội 2. Đồng thời tôi xin cảm ơn tập thể lớp Cao học Toán giải tích K13- K14 của Trường Đại học Sư phạm Hà Nội 2 đã động viên giúp đỡ tôi trong quá trình học tập và làm luận văn này. Tôi xin chân thành cảm ơn tới Ban giám hiệu Trường THPT Yên Dũng số 1, Bắc Giang, các đồng nghiệp và gia đình đã tạo điều kiện giúp đỡ tôi hoàn thành luận văn này. Hà Nội, tháng 06 năm 2012 Tác giả Nguyễn Thành Chung LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của PGS.TS Nguyễn Năng Tâm. Số liệu và các kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác. Trong quá trình nghiên cứu, tôi đã kế thừa thành qủa khoa học của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 06 năm 2012 Tác giả Nguyễn Thành Chung Mục lục Bảng ký hiệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Chương 1. MỘT SỐ KIẾN THỨC CHUẨN BỊ . . . . . . . . . . 9 1.1. Không gian Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.1. Định nghĩa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.2. Tích vô hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.3. Chuẩn Euclid của véc tơ x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.4. Khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.5. Hình cầu mở, tập mở, tập đóng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.6. Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.1.7. Tập bị chặn và tập compact. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2. Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.2. Hàm lồi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3. Ma trận nửa xác định dương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4. Ánh xạ đa trị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4.1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5. Kết luận chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 16 Chương 2. BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG VỚI RÀNG BUỘC TOÀN PHƯƠNG LỒI . . . . . . . . . . . . . . . . . . 17 2.1. Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2. Định lý Frank- Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1. Định lý Frank- Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 18 4 2.2.2. Định lý kiểu Frank- Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Định lý Eaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 25 2.3.1. Định lý Eaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3.2. Định lý kiểu Eaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4. Bài toán tối ưu toàn phương chỉ có một ràng buộc toàn phương lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.5. Bài toán tối ưu toàn phương có hàm mục tiêu tựa lồi . . . . . 43 2.6. Kết luận chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Chương 3. TÍNH ỔN ĐỊNH NGHIỆM CỦA BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1. Tính ổn định nghiệm của bài toán quy hoạch toàn phương với ràng buộc toàn phương lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2. Tính nửa liên tục trên, nửa liên tục dưới . . . . . . . . . . . . . . . . . . 52 3.3. Kết luận chương 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Kết luận. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 BẢNG KÝ HIỆU ∅ tập rỗng x∈X x thuộc tập X x∈ /X x không thuộc tập X A\B hiệu của tập A và tập B A∪B hợp của tập A và tập B A∩B giao của tập A và tập B R đường thẳng thực Rn không gian Euclid- n chiều < x, y > tích vô hướng của x và y pPn 2 chuẩn Euclid của x trong Rn ||x|| = i=1 (xi ) xT chuyển vị của x B(x0 , ) hình cầu mở tâm x0 , bán kính  lim inf giới hạn dưới lim sup giới hạn trên inf (A) cận dưới đúng của A intA phần trong của A 5f (x) gradient của f tại x Rn×n S Không gian các ma trận đối xứng cấp n MỞ ĐẦU 1. Lý do chọn đề tài Bài toán quy hoạch toàn phương (còn gọi là bài toán tối ưu toàn phương) là bài toán tìm nghiệm tối ưu (lớn nhất hoặc nhỏ nhất) của một hàm toàn phương (gọi là hàm mục tiêu) trên một tập hợp xác định bởi một số hàm toàn phương (gọi là miền ràng buộc). Một bộ phận quan trọng của quy hoạch toán học nghiên cứu về những khía cạnh khác nhau của các bài toán tối ưu toàn phương gọi là Quy hoạch toàn phương. Những bài toán tối ưu toàn phương xuất hiện một cách tự nhiên trong nhiều lĩnh vực của tối ưu hóa, điều khiển học và kĩ thuật. Những ví dụ về những bài toán đó có thể kể đến những bài toán miền tin cậy (trustregion problems) trong tối ưu hóa và những bài toán lưu chứa (pooling problem) trong Hóa dầu. Người ta cũng dùng những bài toán tối ưu toàn phương để giải xấp xỉ những bài toán tối ưu phi tuyến phức tạp. Với bài toán tối ưu nói chung, bài toán tối ưu toàn phương nói riêng, một việc quan trọng luôn được đặt ra là bài toán có lời giải (còn gọi là nghiệm) hay không? Câu trả lời sẽ đơn giản nếu tập ràng buộc là giới nội hoặc hàm mục tiêu không bị chặn trên miền ràng buộc. Vấn đề sẽ trở nên phức tạp trong trường hợp tập ràng buộc không giới nội và hàm mục tiêu bị chặn trên đó. Khi ấy việc khẳng định bài toán có nghiệm hay không là một vấn đề không dễ. Một số kết quả nghiên cứu đã được đăng và được viết trong cuốn sách chuyên khảo “G. M. Lee, N. N. Tam and N. D. Yen, Quadratic Programming and Affine Variational Inequalities: A Qualitative Study, Springer Verlag, New York, 2005”. 7 Những bài toán tối ưu toàn phương với ràng buộc toàn phương lồi lập thành một lớp bài toán tối ưu quan trọng, nó chứa những bài toán toàn phương với ràng buộc tuyến tính. Nhiều tác giả trong và ngoài nước đã và đang quan tâm nghiên cứu những tính chất khác nhau của lớp bài toán này và đã thu được nhiều kết quả quan trọng (xem [1], [2], [3], [7], [8]và những tài liệu dẫn trong đó). Sau khi học xong chương trình cao học giải tích, với lòng mong muốn củng cố những kiến thức đã học và hiểu biết thêm về ứng dụng của Giải tích toán học vào những môn toán học khác, tôi chọn đề tài: “ Bài toán quy hoạch toàn phương với ràng buộc toàn phương lồi” để nghiên cứu. 2. Mục đích nghiên cứu Nghiên cứu một số lớp bài toán tối ưu toàn phương (lồi, không lồi) với ràng buộc toàn phương. 3. Nhiệm vụ nghiên cứu Nghiên cứu những tính chất định tính của Bài toán tối ưu toàn phương với ràng buộc toàn phương lồi. 4. Đối tượng và phạm vi nghiên cứu Bài toán tối ưu toàn phương lồi với ràng buộc toàn phương lồi và nghiên cứu sự tồn tại nghiệm, điều kiện cực trị, tính ổn định,. . . của chúng. 8 5. Phương pháp nghiên cứu Tìm hiểu các thông tin trong sách báo liên quan đến nội dung nghiên cứu. Sử dụng các phương pháp của giải tích và đại số tuyến tính. Tổng hợp kiến thức vận dụng cho mục đích nghiên cứu. 6. Những đóng góp của đề tài Luận văn trình bày và nêu ra một cách tổng quan một số kết quả định tính của bài toán tối ưu toàn phương với ràng buộc toàn phương lồi. Hà Nội, ngày 15 tháng 06 năm 2012 Tác giả Nguyễn Thành Chung Chương 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ Trong chương này trình bày một số kiến thức cơ bản về không gian Rn , tập mở, hình cầu mở, tập lồi, hàm lồi, ánh xạ đa trị và tính liên tục...Các kiến thức trong chương này được trích dẫn từ [2], [3], [10]. 1.1. Không gian Rn 1.1.1. Định nghĩa Với R là tập số thực, Rn là tập hợp tất cả các bộ được sắp n số thực: x = (x1 , x2 , . . . , xn ), xi ∈ Rn , 1 ≤ i ≤ n và xi được gọi là tọa độ thứ i của x. Với mỗi cặp phần tử trong Rn : x = (x1 , x2 , . . . , xn ), y = (y1 , y2 , . . . , yn ) ta gọi tổng x + y là phần tử trong Rn được cho bởi x + y = (x1 + y1 , x2 + y2 , . . . , xn + yn ). Với mỗi λ ∈ Rn , x = (x1 , x2 , . . . , xn ) ∈ Rn ta gọi tích của một số vô hướng λ là phần tử λx = (λx1 , λx2 , . . . , λxn ). Ta chứng minh được rằng Rn cùng với hai phép toán trên lập thành không gian véc tơ trên trường số thực R. 10 1.1.2. Tích vô hướng Trong Rn ta định nghĩa tích vô hướng chính tắc < ., . > như sau: với x = (x1 , x2 , . . . , xn )T , y = (y1 , y2 , . . . , yn )T ∈ Rn , < x, y >= n X xi yi i=1 Với tích vô hướng chính tắc ta có: (i) (ii) < x, y >=< y, x > . < x + x0 , y >=< x, y > + < x0 , y > . (iii) λ < x, y >=< λx, y > . (iv) < x, x >≥ 0 và < x, x >= 0 khi và chỉ khi x = 0. 1.1.3. Chuẩn Euclid của véc tơ x v u n uX √ ||x|| = < x, x > = t (xi )2 i=1 Chuẩn Euclid có những tính chất sau: (i) ||x|| ≥ 0, ∀x ∈ Rn , ||x|| = 0 ⇐⇒ x = 0. (ii) ||λx|| = |λ| ||x||, ∀λ ∈ R, ∀x, y ∈ Rn . (iii) | < x, y > | ≤ ||x|| ||y||, ∀x, y ∈ Rn , dấu bằng xảy ra khi và chỉ khi x, y phụ thuộc tuyến tính. (iv) | ||x|| − ||y|| | ≤ ||x + y|| ≤ ||x|| + ||y||, ∀x, y ∈ Rn . 1.1.4. Khoảng cách Cho tập M và ánh xạ d : Rn × Rn −→ R, d được gọi là một khoảng cách (hay mêtric) trên Rn nếu nó thỏa mãn các điều kiện sau: (i) d(x, y) ≥ 0, ∀x, y ∈ Rn và d(x, y) = 0 khi và chỉ khi x = y. 11 (ii) d(x, y) = d(y, x), ∀x, y ∈ Rn . (iii) d(x, z) ≤ d(x, y) + d(y, z), ∀x, y, z ∈ Rn . (iv) |d(x, y) − d(y, z)| ≤ d(x, z), ∀x, y, z ∈ Rn . (M, d) được gọi là một không gian metric. 1.1.5. Hình cầu mở, tập mở, tập đóng Định nghĩa 1.1.1. Cho x0 ∈ Rn ,  > 0 , ta gọi tập B(x0 , ) := {x ∈ Rn : ||x − x0 || < } là hình cầu mở tâm x0 , bán kính . Định nghĩa 1.1.2. Tập U ∈ Rn gọi là tập mở nếu ∀x0 ∈ U , tồn tại  > 0 sao cho B(x0 , ) ⊂ U . Ví dụ 1.1.1. Các tập sau là tập mở: i) Tập hợp các điểm (x, y) thỏa mãn x2 + y 2 < r2 là tập mở. ii) Tập hợp các số thực x thuộc khoảng (0; 1) là tập mở. Định nghĩa 1.1.3. Tập F được gọi là tập đóng nếu U := Rn \ F là tập mở. Ví dụ 1.1.2. Về tập đóng và tập không đóng không mở : i) Tập hợp các điểm (x, y) thỏa mãn x2 + y 2 = r2 là tập đóng. ii) Tập hợp các số thực x thuộc đoạn [0; 1] là tập đóng. iii) Tồn tại tập không đóng, không mở như (0; 1]. Định lý 1.1.1. Trong Rn (i) Tập rỗng ∅ là tập mở, cả không gian Rn là mở. (ii) Giao của một họ hữu hạn các tập mở là mở. (iii) Hợp của một họ bất kì các tập mở là mở. Như vậy, họ tất cả các tập mở lập thành không gian tô pô trong Rn và là tô pô thông thường. 12 Định lý 1.1.2. Trong Rn (i) Tập rỗng ∅ là tập đóng, cả không gian Rn là đóng. (ii) Hợp của một họ hữu hạn các tập đóng là đóng. (iii) Giao của một họ bất kì các tập đóng là đóng. 1.1.6. Sự hội tụ Định nghĩa 1.1.4. Dãy điểm {xk } trong Rn gọi là hội tụ đến x0 ∈ Rn khi k → ∞ nếu dãy số ||xk − x0 || hội tụ đến 0 ∈ R khi k → ∞. Khi đó ta gọi x0 là giới hạn của dãy {xk }, kí hiệu : xk → x0 . Khi x ∈ Rn tiến tới x0 ∈ Rn , kí hiệu x → x0 , nếu ||xk − x0 || → 0. Giả sử xk = (xk1 , xk2 , . . . , xkn ), x0 = (x01 , x02 , . . . , x0n ). Từ v u n uX ||xk − x0 || = t (xk − x0 ) i i i=1 Suy ra, xk → x0 khi và chỉ khi xki → x0i , ∀i = 1, 2, . . . , n. Như vậy sự hội tụ trong Rn là hội tụ theo tọa độ. 1.1.7. Tập bị chặn và tập compact Định nghĩa 1.1.5. Tập B trong Rn được gọi là bị chặn nếu tồn tại m > 0 sao cho ||x|| ≤ m, ∀x ∈ B. Ví dụ 1.1.3. Tập ∅ , tập gồm hữu hạn điểm, hình cầu B(x0 , ) là những tập bị chặn. Định nghĩa 1.1.6. Tập X trong Rn được gọi là compact nếu mọi dãy {xk } trong X đều có dãy con {xkm } hội tụ đến một điểm x∗ ∈ X. Định lý 1.1.3. Tập X trong Rn là compact khi và chỉ khi X là tập đóng và bị chặn. 13 1.2. Tập lồi và hàm lồi 1.2.1. Tập lồi Định nghĩa 1.2.1. Tập X ⊂ Rn được gọi là tập lồi, nếu ∀x, y ∈ X, ∀λ ∈ [0, 1]. ta có λx + (1 − λ)y ∈ X. Nếu X là tập lồi và đồng thời là tập đóng (mở) trong Rn thì ta gọi X là tập lồi đóng (tương ứng, mở). Ví dụ 1.2.1. Tập rỗng, hình cầu trong Rn , Rn là những tập lồi. Định nghĩa 1.2.2. Tập X ⊂ Rn gọi là tập lồi đa diện nếu X có dạng X = {x : Ax ≤ b}, trong đó A là ma trận cấp m × n, b ∈ Rm . Định nghĩa 1.2.3. Tập K ⊂ Rn gọi là nón nếu với mọi x ∈ K, t ≥ 0 ta có tx ∈ K. Nếu nón K là tập lồi thì K gọi là nón lồi. Định nghĩa 1.2.4. Cho X là tập lồi khác rỗng trong Rn . Véc tơ v ∈ Rn , v 6= 0 gọi là một phương lùi xa của X nếu với mọi x ∈ X, t ≥ 0 ta có x + tv ∈ X. Tập tất cả các phương lùi xa của X lập thành một nón, gọi là nón lùi xa của X và kí hiệu là 0+ X. 1.2.2. Hàm lồi Định nghĩa 1.2.5. Cho X ⊂ Rn là một tập lồi và f : X → R. Ta nói f là hàm lồi trên X khi và chỉ khi f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ X, λ ∈ [0; 1]. Ví dụ 1.2.2. Về hàm lồi và không lồi trên R: i) Hàm hằng f (x) = a là một hàm lồi. ii) Hàm f (x) = x3 là hàm không lồi trên R. 14 Định nghĩa 1.2.6. Hàm số f được gọi là tựa lồi, nếu ∀x, y ∈ X ⊂ Rn , ∀z ∈ [x, y] thì f (z) ≤ max{f (x), f (y)}. Định nghĩa 1.2.7. Hàm f được gọi là hàm giả lồi, nếu ∀x, y ∈ X ta có: ∃z sao cho < z, y − x >≥ 0 ⇒ f (x) ≤ f (y). 1.3. Ma trận nửa xác định dương Định nghĩa 1.3.1. Ma trận vuông Q cấp n được gọi là ma trận nửa xác định dương nếu < x, Qx >≥ 0, ∀x ∈ Rn . Định nghĩa 1.3.2. Ma trận vuông Q cấp n được gọi là ma trận xác định dương nếu < x, Qx >> 0, ∀x ∈ R. Định lý 1.3.1. Cho ma trận vuông Q cấp n, đối xứng, c ∈ Rn . Khi đó hàm toàn phương f (x) = 1 < x, Qx > + < c, x > 2 là hàm lồi khi và chỉ khi Q là ma trận nửa xác định dương. Chứng minh. Vì Q là nửa xác định dương nên với mọi x, y ∈ Rn :< x − y, Q(x − y) >≥ 0, suy ra 1 1 < x, Qx > + < y, Qy >≥< x, Qy > . 2 2 15 Do đó, với mọi x, y ∈ Rn , ∀λ ∈ [0, 1] ta có: (1 − λ)2 λ2 < x, Qx > +λ < c, x > + < y, Qy > f [λx + (1 − λ)y] = 2 2 + (1 − λ) < c, y > +λ(1 − λ) < x, Qy > λ2 < x, Qx > +λ < c, x > ≤ 2 (1 − λ)2 < y, Qy > +(1 − λ) < c, y > + 2   1 1 + λ(1 − λ) < x, Qx > < y, Qy > 2 2 ≤ λf (x) + (1 − λ)f (y). Vậy f là hàm lồi. 1.4. Ánh xạ đa trị Định nghĩa 1.4.1. Cho X, Y là hai tập hợp bất kì. Quy tắc F cho ứng mỗi x ∈ X với một tập con F (x) của Y được gọi là ánh xạ đa trị từ X vào Y , kí hiệu F : X =⇒ Y . Định nghĩa 1.4.2. Liên tục, nửa liên tục trên và nửa liên tục dưới: a. Ta nói F là nửa liên tục trên tại x̄ ∈ X, nếu với mọi tập mở V ⊂ Y thỏa mãn F (x̄) ⊂ V , tồn tại lân cân mở U của x̄ sao cho F (x) ⊂ V với mọi x ∈ U. Nếu F là nửa liên tục trên tại mọi điểm thuộc X, thì F được gọi là nửa liên tục trên X. b. Ta nói F là nửa liên tục dưới tại x̄ ∈ X, nếu với mọi tập mở V ⊂ Y thỏa mãn F (x̄) ∩ V 6= ∅, tồn tại lân cận mở U của x̄, sao cho F (x) ∩ V 6= ∅ với mọi x ∈ U. Nếu F là nửa liên tục dưới tại mọi điểm thuộc X, thì F được gọi là nửa liên tục dưới trên X. c. F là liên tục tại x̄ ∈ X, nếu F đồng thời là nửa liên tục trên và nửa liên tục dưới tại x̄. F liên tục tại mọi điểm thuộc X thì nói F liên tục trên X. 16 1.4.1. Bài toán tối ưu Định nghĩa 1.4.3. Cho X ⊂ Rn , f : X → R . Bài toán tìm giá trị nhỏ nhất của f trên X gọi là bài toán tối ưu, kí hiệu    min f (x) .   x∈X (*) Khi đó, X được gọi là tập ràng buộc hoặc tập chấp nhận được; f (x) gọi là hàm mục tiêu. Mỗi véc tơ x ∈ X là một phương án chấp nhận được hay một lời giải của bài toán (*). Một lời giải x̄ ∈ X được gọi là nghiệm (hoặc nghiệm tối ưu hoặc cực tiểu), nếu f (x̄) ≤ f (x), ∀x ∈ X. Tập tất cả các nghiệm tối ưu của (*) được gọi là tập nghiệm của bài toán (*). 1.5. Kết luận chương 1 Trong chương này chúng ta đã trình bày một số khái niệm về không gian Rn , tập lồi, hàm lồi và một số kiến thức sẽ được sử dụng trong các chương sau. Chương 2 BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG VỚI RÀNG BUỘC TOÀN PHƯƠNG LỒI Chương này dành cho việc nghiên cứu bài toán quy hoạch toàn phương với ràng buộc toàn phương lồi. Nội dung (kiến thức) trong chương 2 được trích dẫn từ [4], [5], [6], [8], [9]. 2.1. Định nghĩa Định nghĩa 2.1.1. Xét bài toán tối ưu toàn phương dạng    minf0 (x) = 1 xT Q0 x + b0 T x + β0 2 (2.1)   x ∈ Rn , f (x) = 1 xT Q x + bT x + β ≤ 0, i i i i 2 trong đó Qi là ma trận đối xứng cấp n, bi ∈ Rn , βi ∈ R, i = 0, 1, 2, ...m, xT là chuyển vị của x. Kí hiệu 1 C = {x ∈ Rn | fi (x) = xT Qi x + bTi x + βi ≤ 0}. 2 (2.2) là tập ràng buộc của (2.1). Nếu Qi là ma trận nửa xác định dương, i = 1, 2, ..., m, thì (2.1) được gọi là bài toán quy hoạch toàn phương với ràng buộc toàn phương lồi. 18 2.2. Định lý Frank- Wolfe Sự tồn tại nghiệm của bài toán quy hoạch toàn phương với ràng buộc toàn phương lồi trong trường hợp Qi = 0, ∀i = 1, 2, ...m và C 6= ∅, f0 bị chặn trên C đã được Frank-Wolfe chứng minh vào năm 1956. 2.2.1. Định lý Frank- Wolfe Xét bài toán toàn phương dạng chuẩn:    min f (x) := 1 xT Qx + cT x 2   x ∈ Rn , bT x + β ≤ 0, i i (2.3) i = 1, ..., m, trong đó: Q là matrận đối xứng cấp n, bi ∈ Rn , βi ∈ R. Tập ràng buộc và giá trị tối ưu của hệ (2.3) có thể viết gọn lại như sau: C = {x ∈ Rn , bTi x + βi ≤ 0, i = 1, ..., m}, θ̄ = inf {f (x) : x ∈ C}. Định lý 2.2.1. (Xem [8] và các trích dẫn trong đó) Giả sử C 6= ∅. Nếu f(x) bị chặn dưới trên C : θ̄ = inf {f (x) : x ∈ C} > −∞, thì bài toán (2.3) có nghiệm. 2.2.2. Định lý kiểu Frank- Wolfe Định lý 2.2.2. Xét bài toán tối ưu toàn phương (2.1) và giả sử rằng, fi (x), i = 0, ..., m, đều là những hàm lồi. Khi đó, nếu tập ràng buộc C trong (2.2) khác rỗng và hàm mục tiêu f0 (x) bị chặn dưới trên tập C thì (2.1) có nghiệm.