ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ VĂN DỰ VỀ HAI BÀI TOÁN TỐI ƯU HAI CẤP Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.01.12 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 2013 i Mục lục Mục lục i Lời cảm ơn iii Mở đầu 1 Bài toán tối ưu tập Pareto toán tối ưu đa mục tiêu hàm phân thức affine 1.1 Bài toán tối ưu véc tơ 1.2 Hàm phân thức affine 1.3 Bài toán tối ưu véc tơ phân thức affine 10 1.4 Phép tính cận đối ngẫu Lagrange để giải toán tối ưu tập Pareto yếu toán tối ưu đa mục tiêu phân thức affine 13 1.4.1 Bài toán tối ưu tập Pareto 13 1.4.2 Phương pháp giải 18 Bài toán bất đẳng thức biến phân hai cấp 2.1 2.2 26 Bài toán bất đẳng thức biến phân đơn điệu 26 2.1.1 Mô tả toán 27 2.1.2 Sự tồn nghiệm 27 Bài toán bất đẳng thức biến phân hai cấp 36 2.2.1 Mô tả toán 36 2.2.2 Bất đẳng thức biến phân giả đơn điệu 37 2.2.3 Thuật toán hội tụ 39 Kết luận 46 ii Tài liệu tham khảo 47 iii Lời cảm ơn Trong suốt trình làm luận văn, nhận hướng dẫn giúp đỡ nghiêm túc GS.TSKH Lê Dũng Mưu (Viện Toán học, Viện Hàn lâm Khoa học Công nghệ 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 kính chúc thầy ln ln mạnh khỏe Tôi xin cảm ơn quý thầy, cô giảng dạy Đại học Thái Nguyên Viện Tốn học mang đến cho tơi nhiều kiến thức bổ ích khơng khoa học mà cịn sống Tôi xin chân thành cảm ơn bạn đồng môn giúp đỡ thời gian học tập Đại học Thái Nguyên trình hồn thành luận văn Cuối cùng, xin cảm ơn bố mẹ Nhờ có bố mẹ khơng quản gian khó, vất vả sớm khuya tạo điều kiện tốt để có thành ngày hơm Xin kính tặng luận văn cho Bố Mẹ Thái Nguyên, tháng - 2013 Người viết Luận văn Vũ Văn Dự Mở đầu Bài toán tối ưu đa mục tiêu toán bất đẳng thức biến phân hai lớp tốn nảy sinh q trình nghiên cứu giải toán thực tế, như: toán kinh tế, vật lý tốn, giao thơng thị, lý thuyết trị chơi Cả hai lớp tốn quan tâm đến khoảng 50 năm trở lại đây, tính ứng dụng rộng rãi đời sống kinh tế - xã hội Tuy nhiên, việc nghiên cứu toán lại gặp nhiều khó khăn, nhiều vấn đề liên quan đến toán chưa giải Bài toán tối ưu đa mục tiêu toán bất đẳng thức biến phân có mối quan hệ tương hỗ cho Nhiều việc tìm nghiệm tối ưu toán tối ưu đa mục tiêu lại quy việc giải tốn bất đẳng thức biến phân có tham số Cụ thể, luận văn thấy: việc tìm điểm Pareto Pareto yếu toán tối ưu đa mục tiêu hàm phân thức affine lại quy việc giải toán tối ưu với ràng buộc bất đẳng thức biến phân phụ thuộc tham số Trong luận văn này, tìm hiểu toán tối ưu tập Pareto toán tối ưu đa mục tiêu hàm phân thức affine toán bất đẳng thức biến phân hai cấp (viết tắt BVI - Bilevel Variational Inequalities) Cụ thể: Đối với toán tối ưu tập Pareto toán tối ưu đa mục tiêu hàm phân thức affine, tìm hiểu kiến thức bản, như: toán tối ưu véc tơ phân thức affine, điểm Pareto (hay nghiệm hữu hiệu), điểm Pareto yếu (hay nghiệm hữu hiệu yếu), định lý điều kiện cần đủ điểm Pareto Pareto yếu toán tối ưu đa mục tiêu hàm phân thức affine Đồng thời, trình bày thuật toán nhánh-cận để giải toán tối ưu tập Pareto yếu toán tối ưu đa mục tiêu hàm phân thức affine (còn gọi Thuật toán LB) Những nghiên cứu ban đầu toán tối ưu đa mục tiêu lần đầu giới thiệu từ cuối kỷ XIX nhà kinh tế học Vilfredo Federico Damaso Pareto (1848 - 1923) Tuy nhiên tối ưu đa mục tiêu quan tâm có bước phát triển đột phá khoảng 40 năm trở lại Bài toán tối ưu đa mục tiêu hàm phân thức affine (viết tắt toán (V P )) mở rộng tự nhiên tốn tối ưu véc tơ tuyến tính Các kết nghiên cứu cho thấy tập Pareto toán (V P ) khác biệt phức tạp nhiều so với tập Pareto toán tối ưu đa mục tiêu tuyến tính Bài tốn tối ưu tập Pareto tập Pareto yếu thuộc lớp toán tối ưu hai cấp, lớp toán lần đầu đề xuất năm 1972 quan tâm ứng dụng rộng rãi thực tiễn Bài tốn tối ưu tập Pareto (hoặc tập Pareto yếu) toán tối ưu đa mục tiêu phân thức affine viết tắt toán (P ) (hoặc toán (W P )) dạng toán tối ưu hai cấp Trên thực tế, hoạt động lao động sản xuất địi hỏi việc giải tốn Ví dụ, cơng ty sản xuất đồ ăn nhanh có p nhà máy (được đặt địa phương khác nhau), nhà máy lại sản xuất n loại đồ ăn khác Hàm lợi nhuận f (x) công ty phụ thuộc vào phương án sản xuất số lượng sản phẩm x = (x1 , x2 , , xn ) Cơng ty muốn tìm phương án sản xuất số lượng sản phẩm x cho lợi nhuận thu cao Nhưng để đảm bảo chất lượng sản phẩm lại không làm hại đến môi trường cơng ty phải tìm phương án sản xuất số lượng sản phẩm x cho tỷ số chi phí sản xuất nhà máy với chi phí cơng ty nhỏ Vì vậy, thay tìm hàm cực đại f (x) tập phương án chấp nhận được, công ty phải thực toán cực đại hàm f (x) tập hữu hiệu toán (V P ) Tức là, tìm phương án sản xuất số lượng sản phẩm x cho thu lợi nhuận cao tập phương án sản xuất thỏa mãn yêu cầu tiết kiệm chi phí sản xuất đảm bảo mơi trường Việc nghiên cứu tốn (P ) toán (W P ) gặp nhiều khó khăn, tập nghiệm tốn (V P ) thường khơng lồi, khơng cịn hợp mặt đa diện ràng buộc có cấu trúc phức tạp Đối với toán bất đẳng thức biến phân hai cấp xét luận văn tìm hiểu về: tốn bất đẳng thức biến phân đơn điệu, điều kiện tồn nghiệm bất đẳng thức biến phân đơn điệu Đồng thời, trình bày toán bất đẳng thức biến phân tập nghiệm toán bất đẳng thức biến phân giả đơn điệu; tìm hiểu thuật tốn sử dụng quy tắc tìm kiếm theo tia Armijo có kết hợp phương pháp đạo hàm tăng cường kỹ thuật cắt siêu phẳng để giải toán hai cấp nói Bài tốn bất đẳng thức biến phân giới thiệu lần đầu Hartman Stampacchia năm 1966 Những nghiên cứu toán liên quan đến việc giải toán điều khiển tối ưu toán biên phương trình đạo hàm riêng Chúng ta phải kể đến đóng góp nhà tốn học, như: D Kinderlehrer, Stampacchia, S Facchinei, J Pang có cơng trình nghiên cứu cơng phu liên quan đến bất đẳng thức biến phân ứng dụng Ở Việt Nam, có nhiều nhà nghiên cứu theo đuổi lĩnh vực này, như: Lê Dũng Mưu, Phạm Quốc Khánh, Nguyễn Đơng n, có nghiên cứu chun sâu bất đẳng thức biến phân xây dựng phương pháp giải cho toán bất đẳng thức biến phân Những năm gần toán bất đẳng thức biến phân có bước phát triển mạnh mẽ thu hút nhiều quan tâm nhà nghiên cứu tính ứng dụng rộng rãi Một hướng nghiên cứu quan trọng xây dựng phương pháp giải Công cụ cho hữu hiệu phương pháp dựa vào việc tính điểm bất động Tuy nhiên, gặp phải tốn bất đẳng thức biến phân có tham số việc giải lại khơng dễ dàng phải sử dụng đến kỹ thuật tối ưu toàn cục Ngay luận văn này, gặp phải trường hợp tương tự phải tìm điểm Pareto Pareto yếu toán (V P ), ta đưa việc giải toán bất đẳng thức biến phân có tham số Điều thật khó khăn Bài tốn bất đẳng thức biến phân hai cấp xét luận văn trường hợp đặc biệt toán bất đẳng thức biến phân có tham số Bài tốn xây dựng toán tối ưu tập nghiệm toán bất đẳng thức biến phân (điều trình bày rõ ràng Mục 2.2, Chương 2) Ta lưu ý phương pháp hiệu chỉnh hiệu chỉnh Tikhonov điểm gần kề, toán bất đẳng thức biến phân đơn điệu tốn cần giải đơn điệu, toán bất đẳng thức biến phân giả đơn điệu tốn cần giải lại khơng kế thừa tính đơn điệu Vấn đề đặt là: Xây dựng thuật toán để giải toán BVI với ràng buộc bất đẳng thức biến phân giả đơn điệu tập nghiệm Vấn đề dẫn tới việc xây dựng thuật toán ([4]) Thuật tốn coi kết hợp phương pháp đạo hàm tăng cường cách sử dụng nguyên tắc toán phụ với kỹ thuật cắt siêu phẳng Mục đích luận văn trình bày hai tốn tối ưu hai cấp: toán tối ưu tập Pareto toán tối ưu đa mục tiêu hàm phân thức affine toán bất đẳng thức biến phân hai cấp thuật tốn có liên quan để giải hai toán Qua luận văn, ta thấy cách tiếp cận bất đẳng thức biến phân toán tối ưu tập Pareto toán tối ưu đa mục tiêu phân thức affine Luận văn có chương: Chương Trình bày toán tối ưu đa mục tiêu phân thức affine (bài toán (V P )), toán tối ưu tập Pareto toán (V P )( gọi toán (P )), toán tối ưu tập Pareto yếu toán (V P )(gọi tốn (W P )) Cuối cùng, trình bày phương pháp giải toán (W P ) phương pháp tính cận đối ngẫu Lagrange Chương Trình bày toán bất đẳng thức biến phân đơn điệu, tồn nghiệm Trình bày tốn (BV I) thuật tốn để giải Cuối trình bày định lý để khẳng định hội tụ thuật toán Luận văn hoàn thành trường Đại học Khoa học, Đại học Thái Nguyên hướng dẫn trực tiếp GS TSKH Lê Dũng Mưu Mặc dù, tác giả cố gắng vấn đề nghiên cứu phức tạp mẻ, lại thời gian có hạn kinh nghiệm nghiên cứu cịn hạn chế nên khó tránh khỏi thiếu sót Tác giả mong nhận góp ý thầy bạn Chương Bài tốn tối ưu tập Pareto toán tối ưu đa mục tiêu hàm phân thức affine Bài toán tối ưu đa mục tiêu phân thức affine, gọi toán tối ưu véc tơ phân thức affine mở rộng toán tối ưu đa mục tiêu tuyến tính, lớp tốn tối ưu đa mục tiêu phân thức affine thực rộng lớp toán tối ưu đa mục tiêu tuyến tính Các kết nghiên cứu cho thấy rằng, tập Pareto toán tối ưu đa mục tiêu phân thức affine khác biệt phức tạp nhiều so với tập Pareto toán tối ưu đa mục tiêu tuyến tính Nhiều tính chất trường hợp tuyến tính khơng cịn cho trường hợp phân thức affine Nhiều vấn đề nghiên cứu cho lớp toán tối ưu đa mục tiêu phân thức affine chưa có kết Trong chương này, nghiên cứu toán tối ưu véctơ hàm phân thức affine Cụ thể, tìm hiểu kiến thức bản, như: toán tối ưu véc tơ phân thức affine, điểm Pareto (hay nghiệm hữu hiệu), điểm Pareto yếu (hay nghiệm hữu hiệu yếu), định lý điều kiện cần đủ điểm Pareto Pareto yếu toán tối ưu đa mục tiêu hàm phân thức affine Đồng thời, trình bày thuật tốn nhánh-cận để giải tốn tối ưu tập Pareto yếu toán tối ưu đa mục tiêu hàm phân thức affine (còn gọi Thuật toán LB) Các kiến thức chương trích dẫn từ tài liệu [6], [7], [8], [9], [10] [11] 1.1 Bài toán tối ưu véc tơ Cho D ⊂ Rn tập lồi, đóng, khác rỗng; K ⊂ Rp nón lồi, đóng Cho f = (f1 , , fp ) : D → Rp hàm véc tơ Xét toán {f (x) : x ∈ D} , K (1.1) "min" hiểu cực tiểu theo nón K định nghĩa sau: K Định nghĩa 1.1 Ta nói x ∈ D điểm Pareto (hay nghiệm hữu hiệu) toán (1.1) với quan hệ thứ tự cho nón lồi K khơng tồn x ∈ D cho f (x) − f (x) ∈ K\{0} (1.2) Ký hiệu tập Pareto (hay tập nghiệm hữu hiệu) (1.1) S(f, D) Vậy, x ∈ S(f, D) ⇔ f (x) − K ∩ f (D) = {f (x)} Định nghĩa 1.2 Giả sử intK = ∅, intK ký hiệu phần tơpơ tập K Ta nói x ∈ D điểm Pareto yếu (hay nghiệm hữu hiệu yếu) tốn (1.1) khơng tồn x ∈ D cho f (x) − f (x) ∈ intK (1.3) Ký hiệu tập Pareto yếu (hay tập nghiệm hữu hiệu yếu) (1.1) W S(f, D) Vậy, x ∈ W S(f, D) ⇔ f (x) − intK ∩ f (D) = ∅ Nhận xét 1.1 Với K = y = (y1 , , yp ) ∈ Rp : y1 ≥ 0, , yp ≥ (1.2) có nghĩa fi (x) ≤ fi (x), ∀i = 1, p ∃i0 : fi0 (x) < fi0 (x); (1.3) có nghĩa fi (x) < fi (x), ∀i = 1, p 10 34 Hơn F (xr ), xr − y ≥ − F (xr ) xr − y ≥ − F (xr ) xr − y = F (xr ) y − xr F (xr ), xr − y ≥ F (xr ) y − xr Hay Suy y − xr > 0, hay xr < y < r Khi đó, với x ∈ C , tồn ε > đủ nhỏ cho xr + ε(x − xr ) ∈ C ∩ Br Do xr ∈ C ∩ Br , nên F (xr ), xr + ε(x − xr ) − xr ≥ 0, ∀x ∈ C Chia hai vế cho ε, ta F (xr ), x − xr ≥ 0, ∀x ∈ C Vậy xr nghiệm toán (2.1) Định lý chứng minh Hệ 2.2 Nếu F : C → Rn ánh xạ liên tục tồn x0 ∈ C , thỏa mãn F (x) − F (x0 ), x − x0 → +∞, x ∈ C x − x0 x → +∞, tồn nghiệm tốn (2.4) Chứng minh Vì F thỏa mãn điều kiện trên, nên ta chọn c > 0, r > cho c > F (x0 ) r > x0 , thỏa mãn F (x) − F (x0 ), x − x0 ≥ c x − x0 , ∀x ∈ C Suy F (x), x − x0 ≥ c x − x0 + F (x0 ), x − x0 ≥ c x − x0 − F (x0 ) x − x0 = c − F (x0 ) x − x0 ≥ c − F (x0 ) > 0, x = r 38 x − x0 (2.5) 35 Gọi xr nghiệm tốn (2.4), F (xr ), x − xr ≥ 0, ∀x ∈ C Đặc biệt, x = x0 F (xr ), x0 − xr ≥ Kết hợp với (2.5), ta ⇔ F (xr ), xr − x0 ≥ c − F (x0 ) xr − x0 ≤ F (xr ), x0 − xr ≤ c − F (x0 ) x0 − xr Suy x0 − x r ≥ ⇔ xr ≤ x0 < r Vậy hệ chứng minh Thơng thường, tốn bất đẳng thức biến phân khơng có nghiệm Tuy nhiên có điều kiện đảm bảo cho tính nghiệm tốn (2.1) Ta xét mệnh đề sau: Mệnh đề 2.4 (xem [6]) Giả sử F đơn điệu chặt, tốn (2.1) có nghiệm nghiệm Chứng minh Giả sử toán (2.1) tồn hai nghiệm x x Khi x ∈ C : F (x ), x − x ≥ 0, ∀x ∈ C x ∈ C : F (x ), x − x ≥ 0, ∀x ∈ C Cộng hai vế bất đẳng thức lại với nhau, ta ⇔ F (x ) − F (x ), x − x ≥ 0, ∀x , x ∈ C F (x ) − F (x ), x − x ≤ 0, ∀x , x ∈ C Do F đơn điệu chặt, nên F (x ) − F (x ), x − x Vậy x = x 39 = 0, ∀x , x ∈ C 36 Định lí 2.4 (xem [6]) Giả sử C tập lồi, đóng, khác rỗng khơng gian Euclide hữu hạn chiều Rn F : C → Rn đơn điệu mạnh liên tục Khi đó, tốn (2.1) có nghiệm Chứng minh Cố định điểm x ∈ C , ta có F (x), x − x ≥ F (x), x − x + τ x − x → +∞, x − x → +∞ Vì thế, theo điều kiện Định lý 2.3 ta có nghiệm tốn (2.1) Mặt khác, theo Mệnh đề 2.4 suy nghiệm F thỏa mãn tính đơn điệu chặt 2.2 2.2.1 Bài toán bất đẳng thức biến phân hai cấp Mơ tả tốn Bài tốn bất đẳng thức biến phân hai cấp xét mục viết tắt BVI (Bilevel Variational Inequality) xác định sau: { x − xg : x ∈ S} , (2.6) xg ∈ C S = {u ∈ C : F (u), y − u ≥ 0, ∀y ∈ C}, nghĩa là, S tập nghiệm tốn (2.1) định nghĩa Tìm x∗ ∈ C cho F (x∗ ), y − x∗ ≥ 0, ∀y ∈ C (2.7) Trong suốt phần ta ln giả sử C tập con, lồi, đóng không gian Euclide hữu hạn chiều Rn F : C → Rn cho C ⊆ domF Ta gọi tốn (2.6) tốn cấp trên, cịn toán (2.7) toán cấp Các bất đẳng thức biến phân hai cấp đơn điệu quan tâm nhiều nghiên cứu Cần lưu ý tập nghiệm toán cấp (2.7) lồi với F giả đơn điệu C Tuy nhiên, khó khăn tập ràng buộc S lồi, khơng mơ tả cách tường minh toán quy hoạch toán học, phương pháp có sẵn tối ưu lồi bất đẳng thức biến phân áp dụng cho toán (2.6) cách trực tiếp Hiệu chỉnh Tikhonov phương pháp cho bất đẳng thức biến phân đơn điệu Đã có nhiều nhà nghiên cứu quan tâm đến vấn đề 40 37 Trong báo:"The Tikhonov regularization for pseudomotone vairiational inequalities, ACTA Math Vietnamica 31 (2006), 283 - 289" ta thấy tất quỹ đạo Tikhonov xác định toán hiệu chỉnh V I(C, Fε ), Fε = F + εI với ε > I toán tử đồng nhất, tiến đến nghiệm có chuẩn nhỏ bất đẳng thức biến phân giả đơn điệu V I(C, F ) ε → Do đó, vấn đề tìm giới hạn phương pháp Tikhonov áp dụng cho bất đẳng thức biến phân giả đơn điệu dẫn tới toán (2.6) với S tập nghiệm toán gốc xg = Ta biết rằng, F đơn điệu Fε đơn điệu mạnh, với ε > Tuy nhiên, F giả đơn điệu Fε khơng đơn điệu mạnh, chí, khơng giả đơn điệu, với ε > Ví dụ dẫn đến câu hỏi đặt cho phương pháp hiệu chỉnh Tikhonov, là:"Tại lại thay toán bất đẳng thức biến phân giả đơn điệu ban đầu toán phụ V I(C, Fε ) đó, khơng có tốn tử giả đơn điệu?" Câu hỏi gợi ý việc xây dựng thuật toán để giải toán (2.6) 2.2.2 Bất đẳng thức biến phân giả đơn điệu Trong phần đề cập đến tồn nghiệm toán (2.6) với F toán tử giả đơn điệu Các kiến thức phần trích dẫn từ tài liệu [4], [6] [12] Bổ đề 2.1 (xem [4]) Giả sử ta có giả thiết: (A1) F liên tục miền xác định nó; (A2) F giả đơn điệu C với nghiệm toán V I(C, F ), nghĩa F (x∗ ), x − x∗ ≥ =⇒ F (x), x − x∗ ≥ 0, ∀x ∈ C, ∀x∗ ∈ S Và toán cấp (2.7) có nghiệm Khi đó, tập nghiệm (2.7) lồi đóng Theo ngun lý tốn phụ, ta định nghĩa song hàm L : C × C → R cho (B1) L(x, x) = 0, ∃β > : L(x, y) ≥ β x − y , với x, y ∈ C; (B2) L liên tục, L(x, ) khả vi lồi mạnh C với x ∈ C ∇2 L(x, x) = với x ∈ C , ∇2 L(x, x) ký hiệu hàm khả vi theo biến thứ hai điểm x 41 38 Ví dụ cho song hàm khoảng cách Bregman L(x, y) = g(y) − g(x) − ∇g(x), y − x với g hàm lồi mạnh, khả vi C với β > 0, đặc biệt, g(x) = x 2 Mệnh đề sau có từ nguyên tắc toán phụ bất đẳng thức biến phân Bổ đề 2.2 (xem [4]) Giả sử F thỏa mãn (A1), (A2) L thỏa mãn (B1), (B2) Khi đó, với ρ > khẳng định sau tương đương: (i) x∗ nghiệm toán V I(C, F ); ρ (ii) x∗ ∈ C : F (x∗ ), y − x∗ + L(x∗ , y) ≥ 0, ∀y ∈ C ; F (x∗ ), y − x∗ + L(x∗ , y) : y ∈ C ; ρ ∗ ∗ (iv) x ∈ C : F (y), y − x ≥ 0, ∀y ∈ C (iii) x∗ = argmin Chứng minh Đầu tiên ta chứng minh (i), (ii) (iii) tương đương Thật vậy, L(x, y) ≥ với x, y ∈ C , nên (i) suy (ii) Tuy nhiên, (ii) (iii) đúng, tức x∗ = argmin F (x∗ ), y − x∗ + L(x∗ , y) : y ∈ C ρ Mặt khác, theo điều kiện cần đủ tối ưu cho toán lồi, điều tương đương với ∈ F (x∗ ) + ∇2 L(x∗ , x∗ ) + NC (x∗ ) = F (x∗ ) + NC (x∗ ) ρ Điều tương đương với (i), NC (x∗ ) = {y ∈ Rn : y, x − x∗ , ∀x ∈ C} Chứng minh (iv) suy (i) Giả sử ngược lại rằng, tồn ω ∈ C cho F (x∗ ), ω − x∗ < Khi đó, lấy yt = (1 − t)ω + tx∗ với < t < Do tính liên tục F , ta có F (yt∗ ), ω − x∗ < với < t∗ < Kết hợp với (iv), ta ≤ F (yt∗ ), yt∗ − x∗ = F (yt∗ ), (1 − t∗ )ω + t∗ x∗ − x∗ = (1 − t∗ ) F (yt∗ ), ω − x∗ < 0, mâu thuẫn Vậy F (x∗ ), ω − x∗ ≥ 0, ∀ω ∈ C Điều ngược lại suy trực tiếp từ Định nghĩa 2.2 tính giả đơn điệu F C với x∗ ∈ C 42 39 2.2.3 Thuật toán hội tụ Trong phần trình bày thuật tốn để giải bất đẳng thức biến phân hai cấp (2.6) toán (2.7) giả đơn điệu tập nghiệm Thuật tốn coi kết hợp phương pháp đạo hàm tăng cường cách sử dụng nguyên tắc toán phụ với kỹ thuật cắt siêu phẳng Thuật toán giới thiệu cho thấy với trợ giúp toán phụ V I(C, Fε ), điểm giới hạn quỹ đạo Tikhonov thu cách giải toán hai cấp (2.6) Chúng ta nhận thấy khác biệt thuật tốn trình bày phần với thuật tốn có trước cho tốn hai cấp liên quan đến (2.6), bất đẳng thức biến phân (2.6) giả đơn điệu tập nghiệm khơng phải đơn điệu tài liệu khác đề cập Hơn nữa, toán giải thuật toán giới thiệu sau tốn lồi mạnh, nên giải dễ dàng so với việc giải bất đẳng thức biến phân đơn điệu Như đề cập cho trường hợp giả đơn điệu, bất đẳng thức biến phân V I(C, Fε ) khơng cịn đơn điệu mạnh, chí không giả đơn điệu Ta biết rằng, tập nghiệm toán V I(C, F ) tập điểm bất động toán tử T xác định theo số cách, ví dụ: T (x) = PC x − ρF (x) với ρ > 0, T (x) = Tprox (x) = {u ∈ C : F (u), y − u + c y − u, u − x ≥ 0, ∀y ∈ C, c > 0} Vì tốn bất đẳng thức biến phân hai cấp (2.6) thuộc lớp toán bất đẳng thức biên phân tập điểm bất động toán tử T Thuật toán 2.1 (xem [4]) Chọn ρ > η ∈ (0, 1) Bắt đầu từ x1 = xg ∈ C (với xg đóng vai trị nghiệm đoán) Phép lặp k (k = 1, 2, ) Cho xk thực bước sau: Bước Giải toán lồi mạnh 43 40 F (xk ), y − xk + L(xk , y) : y ∈ C ρ ta có nghiệm y k , CP (xk ) Nếu y k = xk , lấy uk = y k tới Bước Nếu không, tới Bước Bước (Quy tắc tìm kiếm theo tia Armijo) Tìm mk số nguyên không âm nhỏ số m, thỏa mãn z k,m = (1 − η m )xk + η m y k , F (z k,m ), y k − z k,m + L(xk , y k ) ≤ ρ (2.8) (2.9) Đặt ηk = η mk , z k = z k,mk tính σk = −ηk F (z k ), y k − z k (1 − ηk ) F (z k ) , uk = PC xk − σk F (z k ) (2.10) Bước Với xk uk có, ta xây dựng hai nửa khơng gian Ck = {y ∈ Rn : uk − y ≤ xk − y }, Dk = {y ∈ Rn : xg − xk , y − xk ≤ 0}, đặt Bk = Ck ∩ Dk ∩ C Bước Tính xk+1 = PBk (xg ) Nếu xk+1 ∈ S , dừng kết luận xk+1 nghiệm tốn hai cấp (2.6) Nếu khơng, tăng k thêm đơn vị đến Phép lặp k Chú ý 2.1 (i) Tìm kiếm theo tia Bước hoàn toàn xác định Thật vậy, không, với số nguyên không âm m, ta có F (z k,m ), y k − z k,m + L(xk , y k ) > ρ (2.11) Do đó, cho m → ∞, tính liên tục F z k,m = (1 − η m )xk + η m y k → xk , ta có F (xk ), y k − xk + L(xk , y k ) ≥ 0, ρ với F (xk ), xk − xk + L(xk , xk ) = 0, ρ 44 41 suy xk nghiệm toán lồi mạnh CP (xk ) Nên xk = y k mâu thuẫn quy tắc tìm kiếm theo tia thực xk = y k Chú ý mk > Thật vậy, mk = theo quy tắc Armijo, ta có z k = y k 1 L(xk , y k ) = F (z k ), y k − z k + L(xk , y k ) ≤ 0, ρ ρ với tính khơng âm L, suy L(xk , y k ) = Do L(xk , y k ) ≥ β k x − yk 2, nên xk = y k (ii) Theo (2.10) độ dài bước σk > xk = y k Bổ đề 2.3 Từ giả thiết Bổ đề 2.2, ta có uk − x∗ ≤ xk − x ∗ − σk2 F (z k ) , ∀x∗ ∈ S, ∀k (2.12) Chứng minh Để đơn giản ký hiệu, ta viết F k thay F (z k ) v k thay xk − σk F k Từ uk = PC (v k ), tính khơng giãn phép chiếu, nên ta có uk − x∗ = PC (v k ) − PC (x∗ ) ≤ v k − x∗ k ∗ = x − x − σk F = xk − x∗ 2 (2.13) k − 2σk F k , xk − x∗ + σk2 F k Do x∗ ∈ S sử dụng (iv) Bổ đề 2.2, ta viết F k , xk − x∗ = F k , xk − z k + z k − x∗ ≥ F k , xk − z k (2.14) Từ xk − z k = ηk (z k − y k ) − ηk suy F k , xk − z k = ηk F k , z k − y k = σk F k − ηk Phương trình cuối định nghĩa σk từ (2.10) Kết hợp (2.13), (2.14), (2.15) ta (2.12) 45 (2.15) 42 Định lí 2.5 Giả sử giả thiết (A1), (A2) (B1), (B2) thỏa mãn V I(C, F ) có nghiệm Khi đó, hai dãy {xk }, {uk } hội tụ đến nghiệm toán hai cấp (2.6) Chứng minh Theo Chú ý 2.1, quy tắc tìm kiếm theo tia sử dụng thuật tốn hồn tồn xác định Để chứng tỏ tính đắn thuật tốn, ta chứng minh S ⊆ Bk , với k Thật vậy, từ Bổ đề 2.3 nhận thấy uk − x∗ ≤ xk − x∗ với x∗ ∈ S , k Do đó, từ định nghĩa Ck ta có ∅ = S ⊆ Ck , với k Hơn nữa, S ⊆ Dk , với k Từ x1 = xg , S ⊆ D1 = Rn Do định nghĩa xk+1 , nên ta quy nạp rằng: S ⊆ Dk từ xk+1 = PBk (xg ) ta có S ⊆ Dk+1 Cho nên ∅ = S ⊆ Ck ∩ Dk ∩ C = Bk , với k Do đó, phép chiếu lên Bk hồn tồn xác định Từ định nghĩa Dk Mệnh đề 2.1, ta có xk = PDk (xg ) Chú ý xk+1 ∈ Dk , ta viết xk − xg ≤ xk+1 − xg với k Hơn nữa, từ xk = PDk (xg ) S ⊂ Dk với k , ta có xk − xg ≤ x∗ − xg , x∗ ∈ S, ∀k Do đó, dãy {xk } giới nội Từ giới nội {xk } xk − xg ≤ xk+1 − xg với k , ta thấy lim xk − xg tồn hữu hạn Bây giờ, ta chứng minh dãy {xk } tiệm k cận quy, nghĩa là: xk+1 − xk → 0, k → ∞ Thật vậy, từ xk , xk+1 ∈ Dk tính lồi Dk , ta có xk + xk+1 ∈ Dk Từ định nghĩa Dk , ta có xk = PDk (xg ) Khi đó, ta viết xg − xk xk + xk+1 2 g k+1 x −x xg − xk = + 2 g k+1 x −x xg − xk xg − xk+1 xg − xk =2 + − − 2 2 g k+1 g 2 = x − xk+1 + x − xk − x − xk 2 ≤ xg − Vì vậy, ta có k+1 x − xk 2 ≤ xg − xk+1 − xg − xk Chú ý lim xk − v g tồn hữu hạn, nên ta có xk+1 − xk → k→∞ k → ∞ 46 43 Mặt khác, từ xk+1 ∈ Bk ⊆ Ck từ định nghĩa Ck , ta có uk − xk+1 ≤ xk+1 − xk Do uk − xk = uk − xk+1 + xk+1 − xk ≤ uk − xk+1 + xk+1 − xk ≤ xk+1 − xk , mà xk+1 − xk → nên suy uk − xk → k → ∞ Tiếp theo, ta chứng minh điểm tụ dãy {xk } nghiệm toán bất đẳng thức biến phân V I(C, F ) Thật vậy, giả sử x điểm tụ dãy {xk } Khơng tính tổng qt, ta giả sử xk → x Ta xét hai trường hợp sau: Trường hợp Quy tắc tìm kiếm theo tia thực k hữu hạn Trong trường hợp theo thuật toán, uk = xk uk = z k với hữu hạn k Trong trường hợp đầu tiên, xk nghiệm toán V I(C, F ), trường hợp sau uk nghiệm toán V I(C, F ) với hữu hạn k Vì vậy, từ uk − xk → 0, ta nhận thấy x nghiệm toán V I(C, F ) Trường hợp Quy tắc tìm kiếm theo tia thực với vô hạn k Khi đó, cách lấy dãy con, cần thiết ta giả sử quy tắc tìm kiếm theo tia thực với k Chúng ta phân biệt hai khả năng: (a) lim ηk > Từ xk → x uk − xk → kéo theo uk → x Khi đó, áp dụng k (2.12) với x∗ ∈ S , ta thấy σk F k → Nên theo định nghĩa σk , ta −ηk F k , y k − z k → Từ lim ηk > 0, cần thiết, ta giả sử có − ηk k F k , y k − z k → Mặt khác, sử dụng giả thiết (B1) quy tắc Armijo, ta viết 0≤ β k x − yk 2ρ ≤ L(xk , y k ) ≤ − F k , y k − z k → ρ Do đó, xk − y k → với xk → x kéo theo y k → x Do y k nghiệm toán F (xk ), y − xk + L(xk , y) : y ∈ C ρ 47 CP (xk ) 44 nên F (xk ), y − xk + L(xk , y) ≥ F (xk ), y k − xk ρ + L(xk , y k ), ∀y ∈ C ρ Cho k → ∞, tính liên tục F L, ta F (x), y − x + 1 L(x, y) ≥ F (x), x − x + L(x, x), ∀y ∈ C ρ ρ Nghĩa x nghiệm tốn CP (x) Khi đó, từ Bổ đề 2.2, suy x nghiệm toán V I(C, F ) (b) lim ηk = Trong trường hợp này, dãy {y k } giới nội Thật vậy, y k k nghiệm tốn CP (xk ), ta có 1 F (xk ), y − xk + L(xk , y) ≥ F (xk ), y k − xk + L(xk , y k ), ∀y ∈ C ρ ρ Đặc biệt, với y = xk theo tính chất (B1) nên ta viết β k x − yk 2, ≥ F (xk ), y k − xk + L(xk , y k ) ≥ F (xk ), y k − xk + ρ 2ρ hay ⇔ β k x − yk 2ρ + F (xk ), y k − xk ≤ β k x − yk 2ρ ≤ F (xk ), xk − y k ≤ F (xk ) xk − y k 2ρ F (xk ) Do {xk } giới nội F liên tục nên {y k } β giới nội Vì vậy, ta giả sử y k → y, ∀y Theo chứng minh trên, ta có suy xk − y k ≤ 1 F (x), y − x + L(x, y) ≤ F (x), y − x + L(x, y), ∀y ∈ C ρ ρ (2.16) Mặt khác, mk số tự nhiên nhỏ thỏa mãn quy tắc tìm kiếm theo tia Armijo, ta có F (z k,mk −1 ), y k − z k,mk −1 + L(xk , y k ) > ρ Chú ý z k,mk −1 → x k → ∞, từ bất đẳng thức cuối cùng, tính liên tục F L, ta có F (x), y − x + L(x, y) ≥ ρ 48 (2.17) 45 Thay y = x (2.16) để có F (x), y − x + L(x, y) ≤ 0, ρ với (2.17) cho F (x), y − x + L(x, y) = ρ (2.18) Từ (2.18) F (x), x − x + L(x, x) = 0, ρ suy hai điểm x y nghiệm toán lồi mạnh F (x), y − x + L(x, y) : y ∈ C ρ Do đó, x = y từ Bổ đề 2.2, suy x nghiệm V I(C, F ) Hơn nữa, từ uk − xk → ta kết luận rằng: điểm tụ {uk } nghiệm toán V I(C, F ) Cuối cùng, ta thấy {xk } hội tụ tới nghiệm toán hai cấp (2.6) Tới đây, cho x∗ điểm tụ {xk } Khi đó, tồn dãy {xkj } cho xkj → x∗ j → ∞ Từ thuật toán, ta có xkj = PBkj −1 (xg ), nên xkj − xg , y − xkj ≥ 0, ∀y ∈ Bkj −1 ⊇ S, ∀j Cho j → +∞, ta x∗ − xg , y − x∗ ≥ 0, ∀y ∈ S Điều với x∗ ∈ S kéo theo x∗ = PS (xg ) Vì vậy, tồn dãy phải hội tụ tới nghiệm tốn hai cấp (2.6) Khi đó, từ xk − uk → 0, suy {uk } hội tụ tới nghiệm toán hai cấp (2.6) Định lý chứng minh 49 46 Kết luận Luận văn đề cập đến vấn đề sau: Giới thiệu số kiến thức hàm phân thức affine, toán tối ưu đa mục tiêu phân thức affine (bài toán VP), định lý điều kiện cần đủ điểm Pareto điểm Pareto yếu toán (VP) số kết khác liên quan đến tập Pareto Pareto yếu Trình bày phép chia đơi đơn hình cách tính cận theo đối ngẫu Lagrange để giải toán tối ưu tập Pareto yếu toán tối ưu đa mục tiêu phân thức affine Giới thiệu tóm tắt bất đẳng thức biến phân đơn điệu, điều kiện tồn nghiệm bất đẳng thức biến phân đơn điệu Trình bày tốn bất đẳng thức biến phân tập nghiệm toán bất đẳng thức biến phân giả đơn điệu Đồng thời trình bày thuật tốn sử dụng quy tắc tìm kiếm theo tia Armijo có kết hợp phương pháp đạo hàm tăng cường kỹ thuật cắt siêu phẳng để giải toán bất đẳng thức biến phân hai cấp nêu 50 47 Tài liệu tham khảo Tài liệu Tiếng Việt [1] Lê Dũng Mưu (1998), Nhập môn phương pháp tối ưu, nxb Khoa học Kỹ thuật, Hà Nội [2] Lê Dũng Mưu, Nguyễn Văn Hiền, Nhập mơn giải tích lồi ứng dụng, nxb Khoa học Tự nhiên Công nghệ (sẽ ra) [3] Trần Vũ Thiệu, Nguyễn Thị Thu Thủy (2010), Giáo trình tối ưu phi tuyến, nxb Đại học Quốc gia Hà Nội Tài liệu Tiếng Anh [4] B V Dinh and L D Muu, Algorithms for a class of bilevel programming involving pseudomotone variational inequalities, ACTA Math Vietnamica (sẽ ra) [5] I V Konnov (2000), Combined Relaxation Methods for Variational Inequalities, Springer-Verlag, Berlin [6] I V Konnov (2007), Equilibrium Models and Variational Inequalities, Mathematics in Science and Engineering, Volume 210 [7] C Malivert (1995), Multicriteria fractional optimization, in: Proceeding of the 2nd Catalan Days on Applied Mathematics, Presses of Universitaires de Perpinan, pp 189 - 198 [8] L D Muu and H Q Tuyen (2002), Bilinear programming approach to optization over the efficient sets of a vector affine fractional problem, ACTA Mathematica Vietnamica, Volume 27, pp 119 - 139 51 48 [9] S Schaible (1981), Fractional programming: Applications and Algorithms, European Operational Research Volume 7, pp 111 - 120 [10] R E Steuer (1986), Multiple Criteria Optimization: Theory, Computation, Applications, John Willey and Sons, New York [11] H Q Tuyen and L D Muu (2001), Biconvex programming approach to optimization over the weakly efficient set of a multiple objective affine fractional problem, Operations Research Letters Volume 28, pp 81 - 92 [12] Stephan Dempe (2002), Foundations of Bilevel Programming, Freiberg University of Mining and Technology, Freiberg, Germany [13] R T Rockafellar (1970), Convex Analysis, Princeton University Press, New Jersey 52 ... toán tối ưu đa mục tiêu tuyến tính Bài tốn tối ưu tập Pareto tập Pareto yếu thuộc lớp toán tối ưu hai cấp, lớp toán lần đầu đề xuất năm 1972 quan tâm ứng dụng rộng rãi thực tiễn Bài tốn tối ưu. .. toán phụ với kỹ thuật cắt siêu phẳng Mục đích luận văn trình bày hai tốn tối ưu hai cấp: toán tối ưu tập Pareto toán tối ưu đa mục tiêu hàm phân thức affine toán bất đẳng thức biến phân hai cấp. .. Chương Bài tốn tối ưu tập Pareto toán tối ưu đa mục tiêu hàm phân thức affine Bài toán tối ưu đa mục tiêu phân thức affine, gọi toán tối ưu véc tơ phân thức affine mở rộng toán tối ưu đa mục tiêu