ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THANH HẰNG MỘT SỐ PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN TỐI ƯU VÀ BẤT ĐẲNG THỨC BIẾN PHÂN Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.36 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TSKH. LÊ DŨNG MƯU THÁI NGUYÊN - NĂM 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i Mục lục Mục lục i Lời cảm ơn iii Mở đầu 1 1 Toán tử chiếu lên tập lồi đóng 3 1.1 Một số khái niệm và tính chất cơ bản . . . . . . . . . . . . 3 1.1.1 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . 3 1.1.2 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Tính đơn điệu. . . . . . . . . . . . . . . . . . . . . . 7 1.2 Phép chiếu lên tập lồi . . . . . . . . . . . . . . . . . . . . . 8 2 Phương pháp chiếu giải quy hoạch lồi. 14 2.1 Bài toán quy hoạch lồi. . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . 16 2.1.3 Điều kiện tối ưu. . . . . . . . . . . . . . . . . . . . . 17 2.2 Phương pháp chiếu dưới gradient xấp xỉ. . . . . . . . . . . 26 3 Phương pháp chiếu giải bài toán bất đẳng thức biến phân (VIP). 33 3.1 Bài toán bất đẳng thức biến phân. . . . . . . . . . . . . . . 33 3.1.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . 33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii 3.1.2 Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . 34 3.1.3 Các bài toán liên quan. . . . . . . . . . . . . . . . . 39 3.2 Phương pháp chiếu giải bài toán (VIP) . . . . . . . . . . . 42 3.2.1 Phương pháp chiếu cơ bản. . . . . . . . . . . . . . . 42 3.2.2 Phương pháp đạo hàm tăng cường. . . . . . . . . . . 48 Kết luận. 51 Tài liệu tham khảo 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn iii Lời cảm ơn Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn và giúp đỡ của GS.TSKH Lê Dũng Mưu (Viện Toán học Việt Nam). Tôi xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy. Tôi xin cảm ơn quý thầy, cô giảng dạy lớp cao học khóa 4 (2010 - 2012) đã mang đến cho tôi nhiều kiến thức bổ ích trong khoa học và cuộc sống. 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. Tác giả mong nhận được những ý kiến đóng góp của quý thầy, cô và bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! Hải Phòng, tháng 05 năm 2012. Người viết Luận văn Nguyễn Thanh Hằng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 Mở đầu Giải tích lồi là bộ môn cơ bản của giải tích hiện đại, nghiên cứu về tập lồi và hàm lồi cùng những vấn đề liên quan. Bộ môn này có vai trò quan trọng trong nhiều lĩnh vực khác nhau của toán học ứng dụng, đặc biệt là trong tối ưu hoá, bất đẳng thức biến phân, các bài toán cân bằng. Một trong những vấn đề quan trọng của giải tích lồi đó là phép chiếu. Đây là một công cụ sắc bén và khá đơn giản để chứng minh nhiều định lý quan trọng như Định lý tách, Định lý xấp xỉ tập lồi, Định lý về tồn tại nghiệm của Bất đẳng thức biến phân. Hơn nữa phép chiếu còn được dùng để xây dựng các phương pháp giải nhiều lớp bài toán quan trọng như bài toán quy hoạch lồi, bất đẳng thức biến phân. Bài toán bất đẳng thức biến phân được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau như kinh tế, kỹ thuật, vật lý toán, vận trù học. Bài toán bất đẳng thức biến phân được giới thiệu bởi Hartman và Stampacchia vào năm 1966. Những nghiên cứu đầu tiên về bài toán này liên quan tới việc giải các bài toán điều khiển tối ưu và các bài toán biên của phương trình đạo hàm riêng. Bài toán bất đẳng thức biến phân trong không gian vô hạn chiều và các ứng dụng của nó được giới thiệu trong cuốn sách "An Introduction to Variational Inequalities and Their Applications" của D. Kinderlehrer và G. Stampacchia , xuất bản năm 1980 và trong cuốn sách "Variational and Quasivariational Inequalities: Application to Free Boundary Problems" của C. Baiocci và A. Capelo , xuất bản năm 1984. Bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều được giới thiệu khá đầy đủ trong cuốn Finite-Dimensional Variational-Inequalities and Complementarity Problems của S. Facchinei and J. Pang (2003). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 Những năm gần đây, bài toán bất đẳng thức biến phân đã có những bước phát triển rất mạnh và thu hút được sự quan tâm của nhiều nhà nghiên cứu. Một trong các hướng nghiên cứu quan trọng của bài toán bất đẳng thức biến phân là việc xây dựng các phương pháp giải. Có rất nhiều phương pháp giải, trong đó có phương pháp dựa vào cách tiếp cận điểm bất động. Ý tưởng chính của phương pháp này là chuyển việc giải bất đẳng thức biến phân về bài toán tìm điểm bất động của một ánh xạ thích hợp. Một trong những cách tiếp cận điểm bất động là dựa trên phương pháp chiếu. Một lớp bài toán quan trọng của bất đẳng thức biến phân là bài toán Quy hoạch lồi là một lớp bài toán cơ bản của tối ưu hóa. Một đặc điểm cơ bản nhất của bài toán này là mọi điểm cực tiểu địa phương đều là cực tiểu tuyệt đối. Hơn nữa lý thuyết về bài toán quy hoạch lồi đã được quan tâm nghiên cứu và đã thu được nhiều kết quả quan trọng dựa trên lý thuyết của giải tích lồi và tối ưu hóa. Có nhiều phương pháp hữu hiệu cho bài toán này, các phương pháp đó được giới thiệu trong cuốn sách Tối ưu lồi (Convex Optimization) của tác giả Stephen Boyd and Lieven Vandenberghe do nhà xuất bản Cambridge University Press in năm 2004. Mục đích của luận văn này chủ yếu trình bày về ứng dụng của phép chiếu vuông góc vào bài toán bất đẳng thức biến phân và bài toán tôí ưu. Luận văn bao gồm 3 chương: Chương 1 nhắc lại các kiến thức cơ bản của tập lồi và hàm lồi, dưới vi phân, tính đơn điệu, phép chiếu lên tập lồi. Chương 2 giới thiệu về bài toán quy hoạch lồi và trình bày phương pháp chiếu dưới gradient xấp xỉ. Chương 3 giới thiệu bài toán bất đẳng thức biến phân và trình bày một số phương pháp chiếu để giải bài toán bất đẳng thức biến phân. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Chương 1 Toán tử chiếu lên tập lồi đóng Dưới đây, ta nhắc lại một số khái niệm và tính chất cơ bản của giải tích lồi như: Tập lồi, hàm lồi, dưới vi phân, Các kiến thức trong chương này được lấy chủ yếu từ các tài liệu ([1]), ([2]), ([3]) và sẽ được sử dụng ở các chương sau. 1.1 Một số khái niệm và tính chất cơ bản 1.1.1 Tập lồi và hàm lồi Đoạn thẳng nối hai điểm a, b ∈ R n là tập các véc tơ x có dạng {x ∈ R n : x = αa + βb; α ≥ 0; β ≥ 0; α + β = 1}. Tập lồi là một khái niệm cơ bản nhất của giải tích lồi nó được định nghĩa như sau. Định nghĩa 1.1. Một tập C ⊂ R n được gọi là một tập lồi, nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi ∀x, y ∈ C; ∀λ ∈ [0, 1] ⇒ λx + (1 −λ) y ∈ C. Ví dụ 1.1. • Hình cầu đóng B(a, r) = {x ∈ R n : x −a ≤ r}. • Toàn không gian, siêu phẳng, hình tam giác, hình vuông, hình tròn, mặt phẳng, nửa mặt phẳng trong R 2 . Mệnh đề 1.1. Giao của một họ bất kỳ các tập lồi là một tập lồi. Chứng minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Giả sử {A α } α∈I là họ các tập lồi. Cần chứng minh A =  α∈I A α là một tập lồi. • Với mọi x 1 , x 2 ∈ A suy ra x 1 , x 2 ∈ A α (∀α ∈ I). • Với mọi α ∈ I. Do A α lồi nên với mọi λ ∈ [0; 1] ta có λx 1 + (1 − λ) x 2 ∈ A. Theo định nghĩa A =  α∈I A α là một tập lồi. ✷ Mệnh đề 1.2. (Tính chất tập lồi) (i) Nếu C, D ⊂ R n là các tập lồi thì C + D = {x + y : x ∈ C, y ∈ D}; αC = {αx : x ∈ C, α ∈ R}. cũng là các tập lồi trong R n , do đó C −D = C + (−1) D là tập lồi trong R n . (ii) Nếu C ⊂ R n , D ⊂ R m là tập lồi thì C ×D = {(x, y) : x ∈ C, y ∈ D} cũng là tập lồi trong R n+m . Định nghĩa 1.2. Một tập C ⊂ R n được gọi là nón nếu ∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C. Một nón được gọi là nón lồi nếu nó là nón và là một tập lồi. Định nghĩa 1.3. Cho C ⊆ R n là một tập lồi và x o ∈ C. (i) Tập N C  x 0  :=  w : w t (x −x 0 ) ≤ 0; ∀x ∈ C  được gọi là nón pháp tuyến ngoài của C tại x 0 và tập −N C  x 0  được gọi là nón pháp tuyến trong của C tại x 0 . (ii) Tập N ε C  x 0  :=  w : w t (x −x 0 ) ≤ ε; ∀x ∈ C  được gọi là nón ε - pháp tuyến ngoài của C tại x 0 . Định nghĩa 1.4. Cho hàm f : C → (−∞; +∞], C lồi là tập con của R n . Khi đó: (a) f được gọi là hàm lồi trên C nếu f(λx + (1 −λ)y) ≤ λf(x) + (1 − λ)f(y), ∀x, y ∈ C, λ ∈ [0, 1]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 (b) f được gọi là lồi chặt trên C nếu với mọi x, y ∈ C sao cho x = y với mọi λ ∈ (0, 1), ta có f(λx + (1 −λ)y) < λf(x) + (1 − λ)f(y). (c) f được gọi là tựa lồi tại y ∈ C nếu với mọi x ∈ C sao cho f (x) ≤ f (y) với mọi λ ∈ [0, 1], ta có f(λx + (1 −λ)y) ≤ f(y). Hàm f được gọi là lồi trên C, nếu nó tựa lồi tại mọi điểm của C. (d) f được gọi là tựa lồi chặt tại y ∈ C nếu với mọi x ∈ C sao cho f (x) < f (y) với mọi λ ∈ (0, 1), ta có f(λx + (1 −λ)y) < f(y). (e) f được gọi là lồi mạnh trên C với hệ số β > 0 nếu với mọi x, y ∈ C, λ ∈ (0, 1), ta có f(λx + (1 −λ)y) ≤ λf(x) + (1 − λ)f(y) − λ(1 − λ)β||x − y|| 2 . Hàm lồi mạnh là lồi chặt và lồi chặt suy ra lồi. Chẳng hạn hàm y = x 2 là lồi mạnh, do đó lồi chặt và lồi. Điều ngược lại nói chung không đúng. Ví dụ hàm affine y = ax + b lồi nhưng không lồi chặt, hàm y = 1 x lồi chặt nhưng không lồi mạnh trên (0, ∞) . Ví dụ 1.2. • Giả sử C ⊆ R n . Hàm đặc trưng của C là hàm: δ C (x) :=  0 khi x ∈ C +∞ khi x /∈ C. δ C (x) là hàm lồi khi và chỉ khi C là tập lồi. • Hàm chuẩn f (x) = x =  x, x, x ∈ R n là lồi ✷ Định nghĩa 1.5. Cho hàm f : C → (−∞; +∞], C lồi là tập con của R n . Khi đó, miền hữu hiệu của f, kí hiệu là domf, được xác định bởi domf := {x ∈ C : f(x) < +∞}. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Hàm f được gọi là chính thường nếu: domf = ∅ và f(x) > −∞, ∀x ∈ domf. Mệnh đề 1.3. Cho hàm f : C → R với C ⊆ R n . Nếu f là hàm số khả vi và ∇f liên tục. Khi đó, f là hàm lồi khi và chỉ khi f(y) −f(x) ≥ ∇f(x), y − x, ∀x, y ∈ C. Định nghĩa 1.6. Hàm f : C → R ∪ {+∞} được gọi là liên tục Lipchits quanh x 0 nếu có L > 0 và lân cận U của x 0 sao cho f (x) −f (x  ) ≤ L x − x  , ∀x, x  ∈ U ∩ C. Khi đó, L được gọi là hằng số Lipchits. Hàm f được gọi là liên tục Lipchits trên C nếu . f (x) −f (x  ) ≤ L x − x  , ∀x, x  ∈ C. 1.1.2 Dưới vi phân Định nghĩa 1.7. Véc tơ w ∈ R n được gọi là dưới đạo hàm của f tại x 0 ∈ R n nếu w, x − x 0  ≤ f(x) − f(x 0 ), ∀x ∈ R n . • Tập hợp tất cả các dưới đạo hàm của hàm f tại x 0 được gọi là dưới vi phân của f tại x 0 và kí hiệu là ∂f(x 0 ). Vậy ∂f(x 0 ) := {w ∈ R n : w, x − x 0  ≤ f(x) − f(x 0 ), ∀x ∈ R n }. • Hàm f được gọi là khả dưới vi phân tại x 0 nếu ∂f(x 0 ) = ∅. Ví dụ 1.3. Cho C là một tập lồi, khác rỗng của không gian R n . Xét hàm chỉ trên tập lồi C có dạng δ C (x) :=  0 nếu x ∈ C, +∞ nếu x /∈ C. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn [...]... ứng với phương án này là thấp nhất Định nghĩa 2.1 Điểm x∗ ∈ C được gọi là lời giải tối ưu địa phương của bài toán (P ) nếu tồn tại một lân cận U của x sao cho f (x∗ ) ≤ f (x) , ∀x ∈ U ∩ C Và x∗ được gọi là lời giải tối ưu toàn cục của (P) nếu f (x∗ ) ≤ f (x) , ∀x ∈ C Bổ đề 2.1 Đối với bài toán quy hoạch lồi (P ) mọi nghiệm tối ưu địa phương đều là tối ưu toàn cục Hơn nữa tập nghiệm tối ưu là một tập... pC (x) là ε - chiếu của x trên C Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 Chương 2 Phương pháp chiếu giải quy hoạch lồi Trong chương này chúng ta sẽ trình bày phương pháp cơ bản nhất dùng để giải bài toán quy hoạch lồi đó là phương pháp chiếu dưới gradient xấp xỉ Các kiến thức trong chương này chủ yếu được lấy từ tài liệu ([1]), ([7]) 2.1 Bài toán quy hoạch... tả bài toán Cho C là tập lồi đóng, khác rỗng trong Rn và f : C → R là hàm lồi trên C Bài toán quy hoạch lồi là bài toán Tìm x∗ ∈ C sao cho f (x∗ ) := min {f (x) : x ∈ C } (P ) Bài toán này được hiểu là hãy tìm x∗ ∈ C sao cho f (x∗ ) ≤ f (x) với mọi x ∈ C Mỗi điểm x ∈ C được gọi là một phương án chấp nhận được của bài toán (P ) Tập C được gọi là miền (tập) chấp nhận được, f gọi là hàm mục tiêu của bài. .. với một x ∈ Rn có nghiệm 2 Định lí 2.5 Giả sử C là tập lồi và f là hàm lồi, khả vi phân trên C Khi đó x∗ là nghiệm tối ưu của bái toán (P ) khi và chỉ khi 0 ∈ ∂f (x∗ ) + NC (x∗ ) , (2.2) trong đó NC (x∗ ) ký hiệu nón pháp tuyến của C tại x∗ Chứng minh ⇒ Giả sử x∗ là nghiệm tối ưu của bài toán Đặt: E := {(t, x) ∈ R × C : t > f (x) − f (x∗ )} , G := {0} × C ⊂ R × Rn Cả E và G đều là tập lồi (Do C và. .. http://www.lrc-tnu.edu.vn 15 Bài toán (P ) có rất nhiều ứng dụng trong các lĩnh vực khác nhau, ví dụ trong kinh tế nó là bài toán xác định phương án sản xuất sao cho chi phí thấp nhất Ví dụ x là phương án sản xuất mà mỗi tọa độ xj của nó là số lượng sản phẩm loại j cần sản xuất, còn f (x) là chi phí ứng vơi phương án x Bài toán (P ) trong mô hình này có nghĩa là tìm một phương án sản xuất trong tập hợp của các phương án... sử dụng kiến thức sau Định nghĩa 1.10 Cho C ⊆ Rn là tập lồi và f : C → Rn là hàm lồi và ε ≥ 0 Xét bài toán min f (x) (P ) x∈C Một điểm x ∈ D được gọi là ε - nghiệm của bài toán (P ) nếu ¯ f (¯) ≤ min f (x) + ε x x∈C Mệnh đề 1.5 Véctơ x ∈ D được gọi là ε - nghiệm của bài toán (P ) khi ¯ và chỉ khi 0 ∈ ∂ε f (¯) x Định nghĩa 1.11 Cho C là tập lồi đóng khác rỗng trong Rn , x ∈ Rn và ε ≥ 0 Một điểm px ∈... gọi là hàm mục tiêu của bài toán (P) Thông thường tập C được cho như tập nghiệm của một hệ bất đẳng thức và đẳng thức có dạng: C := {x ∈ X : gj (x) ≤ 0, hi (x) = 0, j = 1 , m; i = 1 , k} (2.1) Trong đó X là tập lồi khác rỗng trong Rn và gj , hi : Rn → R, gj lồi, hi là hàm affine Bài toán (P ) cho bởi (2.1) gọi là trơn trên hàm mục tiêu và các ràng buộc đều trơn (khả vi) Số hóa bởi Trung tâm Học liệu... ) ≤ f (x) , ∀x ∈ C Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 Lấy z ∗ = λx∗ + (1 − λ) y ∗ với 0 < λ < 1 Do C lồi nên z ∗ ∈ C và do f lồi nên: f (z ∗ ) ≤ λf (x∗ ) + (1 − λ) f (y ∗ ) ≤ f (x) ⇒ f (z ∗ ) ≤ f (x) , ∀x ∈ C Vậy z ∗ là điểm tối ưu của f trên C hay tập nghiệm tối ưu của f trên C 2 là lồi 2.1.2 Sự tồn tại nghiệm tối ưu Xét bài toán tối ưu toàn cục (P ) Có... i hi (x∗ ) , d = 0 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (2.14) 26 Từ (2.12), (2.13), (2.14), ta có m ∗ k λ∗ j f (x ) , d + ∗ µ∗ i gj (x ) , d + j=1 hi (x∗ ) , d < 0 i=1 điều này mâu thuẫn với (2.10) Vậy x∗ là nghiệm tối ưu toàn cục của bài 2 toán (P ) 2.2 Phương pháp chiếu dưới gradient xấp xỉ Xét bài toán (P ), ký hiệu tập nghiệm của bài toán (P ) là S (f,... ∀z Áp dụng với z = y và z = x , ta có x − p (x) , p (y) − p (x) ≤ 0, y − p (y) , p (x) − p (y) ≤ 0 Cộng vế hai bất đẳng thức được p (y) − p (x) , p (y) − p (x) + x − y ≤ 0 Theo bất đẳng thức Cauchy-Schwarz ta có: p (x) − p (y) ≤ x − y b) Theo tính chất (ii) áp dụng lần lượt với p(x) và p(y), ta có: p (x) − x, p (x) − p (y) ≤ 0, y − p (y) , p (x) − p (y) ≤ 0 Cộng hai bất đẳng thức này ta được p (x) . dựa trên phương pháp chiếu. Một lớp bài toán quan trọng của bất đẳng thức biến phân là bài toán Quy hoạch lồi là một lớp bài toán cơ bản của tối ưu hóa. Một đặc điểm cơ bản nhất của bài toán này. HẰNG MỘT SỐ PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN TỐI ƯU VÀ BẤT ĐẲNG THỨC BIẾN PHÂN Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.36 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TSKH. LÊ DŨNG MƯU THÁI. chiếu còn được dùng để xây dựng các phương pháp giải nhiều lớp bài toán quan trọng như bài toán quy hoạch lồi, bất đẳng thức biến phân. Bài toán bất đẳng thức biến phân được ứng dụng rộng rãi trong