Tài liệu Thuật toán dca và ứng dụng

  • Số trang: 59 |
  • Loại file: PDF |
  • Lượt xem: 97 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN VĂN HỒNG THUẬT TOÁN DCA VÀ ỨNG DỤNG Luận văn Thạc sỹ Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60. 46. 01. 12 Người hướng dẫn khoa học PGS. TS. PHẠM NGỌC ANH THÁI NGUYÊN - NĂM 2014 MỤC LỤC Mục lục 2 Lời cảm ơn 3 Bảng ký hiệu 4 Lời nói đầu 5 1. Một số khái niệm cơ bản 7 1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2. Phần trong tương đối và bao lồi đóng . . . . . . . . . . . . 9 1.1.3. Phương lùi xa và nón lùi xa . . . . . . . . . . . . . . . . . . . . . . . 10 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1. Hàm lồi và hàm lõm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2. Hàm lồi liên tục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.3. Hàm lồi khả vi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.4. Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Hàm D.C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.1. Định nghĩa và tính chất của hàm D.C . . . . . . . . . . 16 1.3.2. Bài toán quy hoạch D.C . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Bài toán đối ngẫu Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.4.1. Điều kiện tối ưu trong bài toán lồi . . . . . . . . . . . . . . . 23 1.4.2. Định lý Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . 27 1.2. 1.3. 1.4. 2. Thuật toán DCA 31 2.1. 31 Bài toán D.C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3. 2.2. Thuật toán DCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3. Sự hội tụ của thuật toán DCA . . . . . . . . . . . . . . . . . . . . . . . 37 Ứng dụng thuật toán DCA 47 3.1. Điều kiện tối ưu hóa toàn bộ cho (P1 ) và (P2 ) . . . . . . . . 47 3.2. Ứng dụng thuật toán DCA giải bài toán (P1 ) . . . . . . . . . 48 3.3. 51 Tính hội tụ của DCA đến nghiệm cục bộ của bài toán (P1 ) 3.4. Ứng dụng thuật toán DCA giải bài toán (P2 ) . . . . . . . . 54 Kết luận 56 Tài liệu tham khảo 57 Lời cảm ơn Luận văn này được hoàn thành tài trường Đại học Khoa học - Đại học Thái Nguyên. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến PGS. TS. Phạm Ngọc Anh (Học viện Công nghệ Bưu chính Viễn thông), thầy đã trực tiếp hướng dẫn tận tình và động viên tác giả trong suốt thời gian viết luận văn vừa qua. Xin chân thành cảm ơn các thầy, cô giáo trong Ban chủ nhiệm khoa, các bạn học viên lớp cao học Toán K6B trường Đại học Khoa học - Đại học Thái Nguyên và các bạn đồng nghiệp đã tạo điều kiện thuận lợi, động viên tác giả trong quá trình học tập và nghiên cứu tại nhà trường. Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân luôn khuyến khích, động viên tác giả trong suốt quá trình học tập và làm luận văn. Mặc dù có nhiều cố gắng, nhưng luận văn khó tránh khỏi những thiếu sót và hạn chế. Tác giả rất mong nhận được những ý kiến đóng góp quý báu của các thầy cô và bạn đọc để luận văn được hoàn thiện hơn. Xin chân thành cảm ơn! Thái Nguyên, tháng 6 năm 2014 Tác giả Nguyễn Văn Hồng Bảng ký hiệu R R+ : Tập hợp số thực : Tập hợp các số trong nửa đoạn [0, +∞) Rn Rn+ : Không gian số thực n - chiều : Không gian số thực không âm n - chiều x∈C x 6∈ C : x thuộc tập C : x không thuộc tập C ∀x ∃x : Với mọi x : Tồn tại x ∅ : Tập hợp rỗng ∩ ∪ : Phép giao các tập hợp : Phép hợp các tập hợp x=y hx, yi : x được định nghĩa bằng y : Tích vô hướng của x và y ∇x f (x) xk * x : Véc tơ đạo hàm của hàm f tại điểm x : Dãy xk hội tụ yếu tới x xk → x : Dãy xk hội tụ mạnh tới x I : Ánh xạ đồng nhất arg min {f (x) |x ∈ C} : Tập các điểm cực tiểu của hàm f trên C kxk : Chuẩn của véc tơ x. Lời nói đầu DCA được viết tắt của "difference of convex functions optimization algorithms". Thuật toán DCA đã được đề xuất từ năm 1986 bởi giáo sư Phạm Đình Tảo với các ứng dụng của nó được phát triển khá mở rộng (xem [1, 2, 4, 5, 6]). DCA được áp dụng trong nhiều lĩnh vực khoa học và liên quan đến nhiều bài toán tối ưu. Thuật toán DCA áp dụng để giải bài toán D.C (viết tắt của difference of convex functions) dạng f = g − h. Để giải bài toán này, tác giả đã sử dụng phương pháp D.C bằng cách phân rã hàm mục tiêu thành hiệu hai hàm lồi và sử dụng các kỹ thuật đối ngẫu Lagrange để chuyển bài toán D.C thành bài toán lồi mạnh không ràng buộc bằng cách tuyến tính hóa hàm lồi g. Một cách đơn giản, chúng ta có thể thấy mô hình của bài toán D.C có dạng: (P ) α = inf {f (x) = g (x) − h (x) : x ∈ Rn } trong đó f là hàm mục tiêu, g, h là các hàm lồi nửa liên tục dưới trên Rn , và bài toán đối ngẫu của nó là (D) α = inf {h∗ (y) − g ∗ (y) : y ∈ Rn } . trong đó h∗ , g ∗ là các hàm liên hợp của g, h trong Rn với g ∗ (y) = sup {hx, yi − g (x) : x ∈ Rn } . Bằng cách áp dụng thuật toán DCA vào giải bài toán (P ) và (D), các tác giả đã chứng minh được rằng sau hữu hạn bước, ta có thể xác định được nghiệm tối ưu địa phương của bài toán ban đầu. Luận văn trình bày về bài toán D.C, thuật toán DCA và ứng dụng thuật toán DCA vào bài toán cực tiểu của hàm không lồi trên hình cầu và mặt cầu trong không gian Euclide Rn . Luận văn gồm hai phần chính: Phần thứ nhất trình bày về bài toán D.C, thuật toán DCA và sự hội tụ của nó trong bài báo của Pham Dinh Tao and Le Thi Hoai An (1997), 6 Convex analysis approach to D.C programming: Theory, algorithms and applications, Acta mathematica Vietnamica, vol. 22, pp. 289 - 355 [8]. Phần thứ hai đề cập đến ứng dụng của DCA vào giải bài toán cực tiểu của hàm không lồi trên hình cầu và mặt cầu trong không gian Euclide Rn trong bài báo "Pham Dinh Tao and Le Thi Hoai An (1996), Difference of convex functions optimization algorithms (DCA) for globally minimizing nonconvex quadratic forms on Euclidean balls and spheres, Operations Research Letters, vol. 19, pp. 207-216". Ngoài phần mở đầu, kết luận và các tài liệu tham khảo, luận văn được trình bày thành ba chương. Chương 1: Trình bày một số kiến thức về giải tích lồi làm cơ sở cho việc nghiên cứu bài toán D.C. Sau đó sẽ trình bày một số vấn đề của bài toán tối ưu lồi, bài toán đối ngẫu Lagrange, Định lý Karush-Kuhn-Tucker, hàm D.C và một số tính chất của hàm D.C. Chương 2: Trình bày bài toán D.C, thuật toán DCA và thuật toán DCA rút gọn. Chương 3: Trình bày ứng dụng thuật toán DCA vào bài toán tìm nghiệm cực tiểu của hàm không lồi trên hình cầu và mặt cầu trong không gian Rn . Chương 1 Một số khái niệm cơ bản 1.1. 1.1.1. Tập lồi Tập lồi Cho a, b là hai điểm trong Rn . Đường thẳng đi qua a và b là tập tất cả các điểm x ∈ Rn có dạng x = (1 − λ) a + λb = a + λ (b − a) với λ ∈ R. Định nghĩa 1.1.1. Tập M ⊆ Rn gọi là một tập afin (hay đa tạp tuyến tính) nếu (1 − λ) a + λb ∈ M với mọi a ∈ M, b ∈ M và mọi λ ∈ 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 ∈ Rn thì a + M = {a + x : x ∈ 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 không gian con, nghĩa là nếu a, b thuộc M thì mọi điểm λa + µb cũng thuộc M với λ, µ ∈ R. Định lý 1.1.1. Tập M không rỗng là một tập afin khi và chỉ khi M = a + L trong đó a ∈ M và L là một không gian con. 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. Thứ 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 ước: dim ∅ = −1. Định lý 1.1.2. Một tập afin k−chiều bất kỳ có dạng M = {x : Ax = b} với A ∈ Rm×n , b ∈ Rm và rankA = 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. 8 Định nghĩa 1.1.2. Một tập afin (n − 1) chiều trong Rn gọi là một siêu phẳng. Định nghĩa 1.1.3. Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn và λ1 + λ2 + ... + λk = 1 gọi là một tổ hợp afin của các điểm a1 , 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ử của 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 Rn , khi đó có ít nhất một tập afin chứa E, cụ thể là Rn . Định nghĩa 1.1.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à af f E. Đó là tập afin nhỏ nhất chứa E. Dễ thấy x ∈ af f E khi và chỉ khi x là một tổ hợp afin của các phần tử thuộc E. Định nghĩa 1.1.5. Ta nói k điểm a1 , a2 , ..., ak ∈ Rn là độc lập afin nếu các véctơ a2 − a1 , a2 − a1 , ..., ak − a1 độc lập tuyến tính. Định nghĩa 1.1.6. Cho hai điểm a, b ∈ Rn . Với 0 6 λ 6 1 tập tất cả các điểm x = (1 − λ) a + λb gọi là đoạn thẳng (đóng) nối a và b, và được ký hiệu là [a, b]. Định nghĩa 1.1.7. Tập C ⊂ Rn đượ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 với mọi a, b ∈ C và mọi 0 6 λ 6 1 thì (1 − λ)a + λb ∈ C . Định nghĩa 1.1.8. Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn , λi > 0, λ1 + λ2 + ... + λk = 1 gọi là một tổ hợp lồi của các điểm a1 , a2 , ..., ak . 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ử của nó. Thứ nguyên (hay số chiều) của một tập lồi C, ký hiệu dimC, là số chiều của bao afin của nó. Một tập lồi C trong Rn gọi là có thứ nguyên đầy nếu dimC = n. Định nghĩa 1.1.9. Cho E ⊂ Rn là một tập bất kỳ. Giao của tất cả các tập lồi chứa E gọi là bao lồi của E, ký hiệu là convE. Đó là tập lồi nhỏ nhất chứa E. 9 Định lý 1.1.3 (Carathéodory). Cho E là một tập chứa trong một tập afin k−chiều. Khi đó bất kỳ x ∈ convE có thể 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. 1.1.2. Phầ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  C ⊂ Rn a ∈ 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 một 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à phần trong của C và được ký hiệu là intC. Định nghĩa 1.1.10. Một điểm a ∈ C ⊂ Rn gọi là một điểm trong tương đối của C nếu với mỗi x ∈ C đều có một số λ > 0 sao cho a+λ(x−a) ∈ C. Tập các điểm trong tương đối của C gọi là phần trong tương đối của C và được ký hiệu là riC. Hiệu tập hợp C/ (riC) gọi là biên tương đối của C và được ký hiệu là ∂C. Một tập C ⊂ Rn gọi là một tập mở tương đối nếu riC = C. Nhận xét 1.1.1. Với B = {x ∈ Rn : ||x| 6 1|} là hình cầu đơn vị đóng thì (i) int C = {x ∈ C : ∃ε > 0, x + εB ⊂ C} . (ii) riC = {x ∈ C : ∃ε > 0, (x + εB) ∩ af f C ⊂ C}: Phần trong tương đối của C là phần trong của C trong af f C. Nếu intC 6= ∅ thì intC = riC. C ⊂ D không suy ra riC ⊂ riD. Chẳng hạn, lấy D ∈ R3 là một khối lập phương, C là một mặt của D. Khi đó, C ⊂ D, riC 6= ∅, riD 6= ∅ nhưng (riC) ∩ (riD) = ∅. Định lý 1.1.4. Một tập lồi bất kỳ C 6= ∅ có phần trong tương đối khác rỗng. Định lý 1.1.5. Bao đóng và phần trong tương đối của một tập lồi là lồi. Nhận xét 1.1.2. Với tập C lồi và a ∈ int C, b ∈ C với mọi λ ∈ [0, 1) thì x = (1 − λ) a + λb = a + λ (b − a) ∈ int C. Và nếu tập lồi C có phần 10 trong khác rỗng thì int = C và int C = int C. Tập lồi C ⊂ Rn có phần trong khác rỗng khi và chỉ khi nó có thứ nguyên đầy. Định nghĩa 1.1.11. Giả sử E ⊂ Rn . Giao của mọi tập lồi đóng chứa E gọi là bao lồi đóng của E và ký hiệu là convE. Đó 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à convE = convE. Định nghĩa 1.1.12. Cho một tập lồi C ⊂ Rn và một điểm y ∈ Rn . Ta gọi hình chiếu của y trên C là điểm x0 ∈ C sao cho 0 x − y = inf ||x − y|| = dC (y) . x∈C Ký hiệu x0 = p(y) và gọi dC(y) là khoả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. Định lý 1.1.6. Cho C ⊂ Rn là một tập lồi đóng khác rỗng và y ∈ Rn là một điểm bất kỳ. Khi đó, tồn tại duy nhất một điểm x0 ∈ C là hình chiếu của y trên C. Định nghĩa 1.1.13. Cho C ⊆ Rn là một tập lồi và một điểm x0 ∈ C. Tập   NC x0 = y ∈ Rn : y, x − x0 >> 0, ∀x ∈ C gọi là nón pháp tuyến ngoài của C tại điểm x0 . 1.1.3. Phương lùi xa và nón lùi xa Tập các điểm có dạng x0 + λd với x0 , d ∈ R, d 6= 0 và λ > 0 gọi là một tia hay nửa đường thẳng xuất phát từ điểm x0 , nếu x0 = 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 d1 và d2 xem là như nhau nếu d1 = αd2 với α > 0. Định nghĩa 1.1.14. Cho C là một tập lồi trong Rn . Véctơ d ∈ Rn , d 6= 0 gọi là một phương lùi xa của C nếu {x + λd:λ > 0} ⊂ C ∀x ∈ C (1.1) (mọi tia xuất phát từ một điểm bất kỳ x ∈ C theo phương d đều nằm trọn trong C. 11 Định lý 1.1.7. 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ó (1.1) khi x0 + λd : λ > 0 ⊂ C với một x0 nào đó thuộc C. Định nghĩa 1.1.15. 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 và ký hiệu là recC. Định lý 1.1.8. Nón lùi xa của một tập lồi đóng C là tập đóng. Một tập lồi đóng C là compac khi và chỉ khi nón lùi xa của nó chỉ gồm duy nhất một phẩn tử 0. 1.2. 1.2.1. Hàm lồi Hàm lồi và hàm lõm Định nghĩa 1.2.1. Hàm f : X → [−∞, +∞] xác định trên một tập lồi X ⊆ Rn được gọi là một hàm lồi trên R nếu với mọi x1 , x2 ∈ R và mọi số thực λ ∈ [0, 1] ta có     f (1 − λ) x2 + λx2 6 (1 − λ) f x1 + λf x2 . Hàm f gọi là lồi chặt trong R nếu với mọi x1 , x2 ∈ X, x1 6= x2 , λ ∈ (0, 1) ta có     f (1 − λ) x1 + λx2 < (1 − λ) f x1 + λ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. Định nghĩa 1.2.2. Hàm f gọi là lõm (lõm chặt) trên C nếu −f là lồi (lồi chặt) trên C. Hàm f gọi là tuyến tính afin (hay đơn giản là afin) trên C nếu f hữu hạn và vừa lồi vừa lõm trên X. Một hàm afin trên Rn có dạng f (x) = ha, xi + α với a ∈ Rn , α ∈ R bởi vì với mọi x1 , x2 ∈ Rn và     mọi λ ∈ [0, 1] ta có f (1 − λ)x1 + λx2 = (1 − λ) f x1 + λf x2 . Tuy nhiên, hàm afin không lồi chặt hay lõm chặt. Định nghĩa 1.2.3. Cho hàm bất kỳ f : X → [−∞, +∞] với X ⊆ Rn , các tập domf = {x ∈ X : f (x) < +∞} , epif = {(x, α) ∈ X × R : f (x) 6 α} được gọi lần lượt là miền hữu dụng và tập trên đồ thị của hàm f . Nếu domf 6= ∅ (f không đồng nhất bằng +∞) và f (x) > −∞ với mọi x ∈ X thì ta nói hàm f là chính thường. 12 Hàm lồi f : X → [−∞, +∞] 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) = +∞ với mọi x ∈ / X. n Vì vậy để đơn giản ta thường xét hàm lồi trên toàn R . Sau đây là một số ví dụ quen thuộc về hàm lồi (C ⊂ Rn là một tập lồi khác rỗng). p (i) Hàm chuẩn Euclid kxk = hx, xi, x ∈ Rn ( 0 : x∈C (ii) Hàm chỉ của C: δC (x) = +∞ : x ∈ /C (iii) Hàm tựa của C: SC (x) = supy∈C hy, xi (cận trên của xT y trên tập C). (iv) Hàm khoảng cách từ điểm x ∈ Rn tới C: dC (x) = inf y∈C kx − yk . Nhận xét 1.2.1. (a) Nếu fj : Rn → R (i = 1, ..., m) là hàm lồi thì α1 f1 + ... + αm fm lồi với mọi αi > 0 và lồi chặt nếu ít nhất một trong các hàm fi lồi chặt với αi > 0. (b) Nếu fi(i∈I) : Rn → R là hàm lồi thì hàm f (x) = supi∈I fi (x) là hàm lồi. (c) Nếu A : Rn → Rm là biến đổi tuyến tính và g : Rn → R là hàm lồi thì hàm hợp f (x) = g (Ax) là hàm lồi. (d) Nếu g : D ⊆ Rn → R là hàm lồi và h : R → R là hàm lồi không giảm thì hàm hợp f (x) = h (g (x)) là hàm lồi. 1.2.2. Hàm lồi liên tục Định nghĩa 1.2.4. Cho x0 ∈ X. Khi đó, hàm chính thường f : X → [−∞, +∞] được gọi là: (i) Nửa liên tục dưới tại x0 nếu lim sup f (y) > f (x) (y → x) . 13 (ii) Nửa liên tục trên tại x0 nếu lim sup f (y) 6 f (x) (y → x) . Nếu hàm số f vừa nửa liên tục trên và nửa liên tục dưới tại x0 thì nó sẽ liên tục tại điểm đó. Định lý 1.2.1. Đối với một hàm lồi chính thường f : X → [−∞, +∞] các điều kiện sau tương đương: (i) f bị chặn trên trong một lân cận mở của x0 . (ii) f liên tục tại x0 . (iii) int(domf ) 6= ∅ và f liên tục tại mọi điểm thuộc int(domf ). Chứng minh. (i) ⇒ (ii). Bằng cách tịnh tiến có thể coi như f (0) = 0. Giả sử f (x) < t với mọi x trong hình cầu B tâm 0, bán kính r > 0. Lấy ε ∈ (0, 1).Do f là hàm lồi nên với mọi x ∈ εB ta sẽ có:  x ∈ B, do đó f (x) 6 εf xε + (1 − ε) f (0) 6 εt. ε  −x ∈ B, do đó f (x) > −εf − xε + (1 + ε) f (0) > −εt. ε Vậy f liên tục tại x0 . (ii) ⇒ (iii). Nếu f liên tục tại x0 thì với r > 0 đủ nhỏ x − x0 < r ⇒   f (x) < f x0 + 1. Có nghĩa x : x − x0 6 r ⊂ {x : f (x) < +∞} tức là a ∈ int(domf). Mặt khác, nếu x0 ∈ int(domf) thì có một α > 1 để  cho u = a + α x0 − a ∈ domf. Cho U là một hình cầu tâm x0 , bán kính α−1 chuyển x0 tới a và r nằm trong domf . Phép vị tự h tâm u và tỉ số α biến hình cầu U thành hình cầu h(U ) tâm a nằm trong h(U ). Với mọi 1 x ∈ U ta sẽ có x = u + α−1 α h (x) và do f lồi: α 1 α−1 1 α−1 f (x) 6 f (u) + f (h (x)) 6 f (u) + t. α α α α Chứng tỏ f bị chặn trong hình cầu U và do đó liên tục tại điểm x0 . (iii) ⇒ (i). Hiển nhiên. 1.2.3. Hàm lồi khả vi Định lý 1.2.2. (a) Một hàm thực một biến ϕ(t) khả vi trong một khoảng mở là lồi khi và chỉ khi đạo hàm của nó ϕ0 (t) là một hàm không giảm. 14 (b) Một hàm thực một biến ϕ(t) hai lần khả vi trong một khoảng mở là lồi khi và chỉ khi đạo hàm cấp hai của nó ϕ00 (t) không âm trên toàn bộ khoảng mở này. Định lý 1.2.3. Cho một tập lồi C ⊂ Rn và một hàm f : Rn → R khả vi trên C. (a) Hàm f lồi trên C khi và chỉ khi f (y) > f (x) + h∇f (x) , y − xi ∀x, y ∈ C. (b) Nếu f (y) > f (x) + h∇f (x) , y − xi với mọi x, y ∈ C và x 6= y thì hàm f lồi chặt trên C. Định lý 1.2.4. Cho một tập lồi mở C ⊂ Rn và một hàm f : Rn → R hai lần khả vi liên tục trên C. ∇2 f (x) là ma trận các đạo hàm riêng cấp hai của f tại X. (a) Nếu ∇2 f (x) nửa xác định dương với mỗi x ∈ C hoặc nếu ∇2 f (x) có mọi giá trị riêng dương thì hàm f lồi trên C. (b) Nếu ∇2 f (x) xác định dương với mỗi x ∈ C hoặc nếu ∇2 f (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 = Rn và hàm f lồi thì ∇2 f (x) nửa xác định dương với mọi x ∈ Rn . Hệ quả 1.2.1 (Điều kiện cần cho hàm lồi (lõm)). Giả sử f : Rn → R là 00 một hàm hai lần khả vi liên tục và fjj (x) là đạo hàm riêng hai lần của f theo cùng biến xj . 00 (a) Nếu f (x) lồi thì fjj (x) > 0, j = 1, ..., n với mọi x. 00 (b) Nếu f (x) lõm thì fjj (x) 6 0, j = 1, ..., n với mọi x. (c) Nếu f (x) lồi chặt hay 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ý 1.2.5. Cho Q là một ma trận vuông đối xứng thực cấp n × n. Hàm toàn phương f (x) = hx, Qxi lồi khi và chỉ khi Q nửa xác định dương. Hơn nữa, hàm f lồi chặt khi và chỉ khi Q xác định dương. 15 Hệ quả 1.2.2. Hàm f (x) = 12 < x, Qx > + < c,x > + α (lồi chặt) trên Rn khi và chỉ khi ma trận Q nửa xác định dương (xác định dương) và f lõm (lõm chặt) trên Rn khi và chỉ khi ma trận Q nửa xác định âm (xác định âm). 1.2.4. Dưới vi phân Định nghĩa 1.2.5. Cho hàm lồi chính thường f trên Rn , véc tơ p ∈ Rn gọi là dưới gradient của f tại điểm x0 nếu  p, x − x0 + f x0 6 f (x) ∀x ∈ Rn . (1.2) (Nếu f lõm và trong (1.2) thay > bởi 6 thì p gọi là dưới gradient của f tại x0 ). Định lý 1.2.6. Nếu f là hàm lồi chính thường thì f có đạo hàm theo    mọi hướng tại mọi điểm x0 ∈ domf và f x0 + d − f x0 > f 0 x0 , d . Định lý 1.2.7. Nếu f là một hàm lồi chính thường và x0 ∈ domf thì   p ∈ ∂f x0 khi và chỉ khi hp, di 6 f 0 x0 , d với mọi d ∈ Rn \ {0} . Định nghĩa 1.2.6. Hàm f (x) xác định trên một tập lồi C = Rn gọi là lồi mạnh, nếu tồn tại hằng số ρ > 0 (hằng số lồi mạnh) sao cho với mọi x, y ∈ C và mọi số λ ∈ [0, 1] ta có bất đẳng thức: 2 f [λx + (1 − λ) y] 6 λf (x) + (1 − λ) f (y) − λ (1 − λ) ρkx − yk . 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 ex , x ∈ R lồi chặt nhưng không lồi mạnh. Định lý 1.2.8. Nếu hàm f (x) lồi mạnh và khả vi trên tập lồi đóng C thì: 2 (a) h∇f (x) − ∇f (y) , x − yi > ρkx − yk với mọi x, y ∈ C.   (b) Với bất kỳ x0 ∈ C tập mức dưới C0 = x ∈ C : f (x) < f x0 bị chặn. (c) Tồn tại duy nhất điểm x∗ ∈ C sao cho f (x∗ ) = min {f (x) : x ∈ C}. 16 (d) Tập tất cả các dưới gradient của f tại x0 gọi là dưới vi phân của f  tại x0 và ký hiệu là ∂f x0 . Hàm f được gọi là khả dưới vi phân  tại x0 nếu ∂f x0 6= ∅. Định lý 1.2.9. Một hàm lồi chính thường f trên Rn có dưới vi phân  khác rỗng tại mỗi điểm x0 ∈ int(domf) và ∂f x0 là một tập lồi đóng. Định lý 1.2.10. Nếu f là hàm lồi chính thường, khả vi tại điểm x0 ∈     domf thì ∂f x0 = ∇f x0 nghĩa là ∇f x0 là véctơ dưới gradient duy nhất của f tại x0 . Ngược lại có thể chứng minh rằng nếu f có tại x0 một véctơ dưới gradient duy nhất thì khả vi tại x0 . 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). Định nghĩa 1.2.7. Cho f : Rn → [−∞, +∞] là một hàm bất kỳ và x0 là  một điểm tại đó f hữu hạn (nghĩa là f x0 < +∞).Vớid ∈ Rn \{0}, f x0 + λd − f x0 nếu tồn tại giới hạn (hữu hạn hay vô hạn) lim thì λ↓0 λ giới hạn đó gọi là đạo hàm theo hướng d của hàm f tai x0 , kí hiệu là  f 0 x0 , d . 1.3. 1.3.1. Hàm D.C Định nghĩa và tính chất của hàm D.C Định nghĩa 1.3.1. Cho một tập lồi Ω ⊂ X (không gian Euclide hữu hạn chiều). Một hàm f gọi là hàm D.C trên Ω nếu f (x) = f1 (x) − f2 (x) với f 1 , f2 là các hàm lồi trên Ω. Định lý 1.3.1. Mọi hàm lồi hay lõm đều là hàm D.C. Định lý 1.3.2. Dạng toàn phương bất kì f (x) = hx, Qxi là hàm D.C.   Chứng minh. Thật vậy, nếu U = u1 , u2 , ..., un là ma trận các véc tơ riêng chuẩn hóa của Q thì U T QU = diag (λ1 , ..., λn ) cho nên đặt x = U y P P 1 ta có f (x) = f (U y) = hU y, QU yi do đó f (x) = λi yi2 − λi yi2 . 2 λi >0 λi <0 17 Định lý 1.3.3. Nếu fi , i = 1, ..., m là D.C trên Ω thì các hàm sau cũng là D.C: Pm (a) i=1 αi fi (x) với α ∈ R. (b) g (x) = max {f1 (x) , ..., fm (x)} . (c) h (x) = min {f1 (x) , ..., fm (x)} . Chứng minh. Tính chất (a) là hiển nhiên, ta sẽ chứng minh tích chất (b) (tính chất (c) chứng minh tương tự). P Pm Giả sử fi = pi − qi với pi , qi là các hàm lồi. Vì fi = pi + j6=i qj − i=1 qi nên n o Xm X maxi=1,...,m fi = max pi + qj − qi = p − q j6=i n với p = max pi + P o j6=i qj ; q = Pm i=1 qi i=1 là các hàm lồi. Ví dụ 1.3.1. Nếu fi (x) , i = 1, ..., m là các hàm lồi thì h (x) = min {f1 (x) , ..., fm (x)} là hàm D.C. Định lý 1.3.4. Mọi hàm f ∈ C 2 (Rn ) là D.C trên một tập lồi compac bất kì Ω ⊂ Rn . 2 Chứng minh. Xét hàm g (x) = f (x) + ρkxk . Nếu chứng minh được rằng có thể chọn ρ đủ lớn để g (x) trở thành hàm lồi thì khi ấy hàm 2 f (x) = g (x) − ρkxk là hàm D.C. 2 Vấn đề là chọn ρ để cho g (x) = f (x) + ρkxk lồi, tức là theo Định lí 1.3.1 để có ∇2 g (x) > 0 với mọi x. Để ý rằng 2 u, ∇2 g (x) u = u, ∇2 f (x) u + ρkuk . Muốn cho ∇2 g (x) > 0 tức là u, ∇2 g (x) u > 0 với mọi u, hay 2 u, ∇2 f (x) u + ρkuk > 0 18 với mọi u mà kuk = 1. Vậy chỉ cần chọn ρ để cho ρ > − u, ∇2 f (x) u với mọi u mà kuk = 1 và mọi x ∈ Ω, nghĩa là  ρ > − min u, ∇2 f (x) u x ∈ Ω, kuk = 1 , điều này có thể được vì  − min u, ∇2 f (x) u x ∈ Ω, kuk = 1 > −∞ do Ω compact. Nhận xét 1.3.1. Mỗi đa thức P (x) đều thuộc C 2 (Rn ), cho nên đều là hàm D.C. Mà theo định lí Weierstrass, với mỗi hàm liên tục f (x) trên một tập lồi compac Ω ⊂ Rn và mỗi số ε > 0 đều tìm được một đa thức P (x) sao cho maxx∈Ω |f (x) − P (x)| 6 ε (nói cách khác mỗi hàm liên tục trên Ω ⊂ Rn đều có thể xấp xỉ tùy ý bởi một đa thức). Do đó mỗi hàm liên tục f (x) trên một tập lồi compac Ω ⊂ Rn đều có thể xấp xỉ tùy ý bởi một hàm D.C. Nói cách khác, tập DC (Ω) các hàm D.C trên Ω trù mật trong không gian Banach C (Ω) các hàm liên tục trên Ω. 1.3.2. Bài toán quy hoạch D.C Xét bài toán min {f (x) | x ∈ Ω, hi (x) > 0, i = 1, ..., m} trong đó f (x) , hi (x) đều là các hàm D.C và Ω là một tập lồi đóng. Vì hàm hi (x) > 0, (i = 1, ..., m) ⇔ min hi (x) > 0 nên bao giờ cũng có thể đưa bài toán về trường hợp chỉ có một ràng buộc. Định nghĩa 1.3.2. Một quy hoạch D.C có dạng tổng quát (chính tắc): min {f (x) | x ∈ Ω, h (x) > 0} (1.3) trong đó f (x) , h (x) đều là các hàm D.C. Ta có một số trường hợp riêng của quy hoạch D.C. Bài toán cực tiểu hàm lõm ( Cực đại hàm lồi): min {f (x)| x ∈ Ω} trong đó f (x) là hàm lõm, Ω là tập lồi đóng, chẳng hạn Ω = {x| g (x) 6 0} với g (x) là một hàm lồi. 19 Bài toán lồi đảo (CDC): min {f (x) | x ∈ Ω, h (x) > 0} với f (x) , h (x) là các hàm lồi và Ω là tập lồi đóng, Đặt C = {x| h (x) 6 0} thì C là tập lồi đóng và bài toán (CDC) cũng có thể viết min {f (x) | x ∈ Ω\intC} . Định lý 1.3.5. Mọi quy hoạch D.C đều có thể đưa về dạng (CDC). Chứng minh. Thật vậy (1.3) có thể viết lại: min {f1 (x) − u | x ∈ Ω, f2 (x) > u, h (x) > 0} . Hai ràng buộc D.C f2 (x) > u, h (x) > 0 có thể gộp lại thành một ràng buộc D.C duy nhất h1 (x) − h2 (x) > 0 trong đó h1 (x) , h2 (x) là các hàm lồi. Ràng buộc D.C này lại tách ra thành hai ràng buộc: h1 (x) > t, t > h2 (x). Sau cùng, đặt z = (x, u, t) khi đó f (z) = f1 (x) − u, Ω = {z = (x, u, t)| x ∈ Ω, h1 (x) − t 6 0} ,  và h (z) = h2 (x) − t. Bài toán trở thành min f (x) x ∈ Ω, h (x) > 0 . Vì f (x) , h (x) là hàm lồi, và Ω là tập lồi nên đây là một bài toán dạng (CDC). 1.4. Bài toán đối ngẫu Lagrange Dạng chuẩn của một bài toán tối ưu ("Quy hoạch toán học") trong n R min {f (x) gi (x) 6 0 i = 1, ..., m, x ∈ Ω|} (P ), trong đó f, gi : Rn → R, Ω ⊂ Rn . Nhận xét 1.4.1. ( sup f (x) + λ>0 m X i=1 ) λi gi (x)  f (x) , nếu g (x) 6 0 i = 1, ..., m i = +∞, nếu trái lại . (1.4)
- Xem thêm -