Phương pháp xấp xỉ trong để giải bài toán bất đẳng thức biến phân đa trị giả đơn điệu

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

DƯƠNG THỊ BÌNH

PHƯƠNG PHÁP XẤP XỈ

TRONG ĐỂ GIẢI BÀI TOÁN

BẤT ĐẲNG THỨC BIẾN PHÂN

ĐA TRỊ GIẢ ĐƠN ĐIỆU

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:

TS. PHẠM NGỌC ANH

THÁI NGUYÊN - NĂM 2010

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 Bài toán bất đẳng thức biến phân đa trị 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Ánh xạ đa trị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Bài toán bất đẳng thức biến phân đa trị . . . . . . . . . . . . . . . . . 12

1.3.1 Bất đẳng thức biến phân đa trị và các bài toán liên quan . . . . 12

1.3.2 Sự tồn tại nghiệm của bài toán (MV I) . . . . . . . . . . . . . . 18

2 Phương pháp xấp xỉ trong với điều kiện Lipschitz 20

2.1 Phương pháp hàm phạt điểm trong [1] . . . . . . . . . . . . . . . . . . 20

2.2 Thuật toán xấp xỉ trong và sự hội tụ . . . . . . . . . . . . . . . . . . . 23

3 Phương pháp xấp xỉ trong không Lipschitz 33

3.1 Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2 Một số kết quả tính toán cụ thể . . . . . . . . . . . . . . . . . . . . . . 39

4 Thuật toán kiểu điểm gần kề cho bài toán (MV I) 41

4.1 Thuật toán kiểu điểm gần kề . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1.1 Sơ bộ về phương pháp kiểu điểm gần kề . . . . . . . . . . . . . 41

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

4.1.2 Thuật toán điểm gần kề . . . . . . . . . . . . . . . . . . . . . . 43

4.2 Thuật toán mới và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . 45

4.2.1 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.2.2 Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . 47

4.3 Áp dụng thuật toán ánh xạ co Banach cho (MV I) . . . . . . . . . . . 51

Kết luận 55

Danh mục các công trình có liên quan đến luận văn 56

Tài liệu tham khảo 57

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 này, tôi luôn nhận được sự hướng dẫn và chỉ

bảo tận tình của thầy giáo TS. Phạm Ngọc Anh (Học viện Công nghệ Bưu chính Viễn

thông). Thầy luôn động viên và hướng dẫn tận tình cho tôi trong thời gian học tập,

nghiên cứu và làm luận văn. Tôi xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy.

Xin cảm ơn Ban giám hiệu, các bạn đồng nghiệp trường THPT Chuyên Thái Nguyên

đã tạo điều kiện tốt nhất để tôi hoàn thành khóa cao học này.

Tôi cũng xin cảm ơn các thầy, cô thuộc Bộ môn Toán - Tin, Phòng Đào tạo và Quan

hệ Quốc tế và các thầy cô trong trường Đại học Khoa học - Đại học Thái Nguyên,

cùng các thầy cô trực tiếp giảng dạy lớp cao học khóa 2 (2008 - 2010) đã mang đến

cho tôi nhiều kiến thức bổ ích trong khoa học và cuộc sống.

Xin cảm ơn các bạn học viên cao học toán khóa 2 đã tạo điều kiện thuận lợi, động

viên, giúp đỡ tôi trong quá trình học tập và rèn luyện tại trườ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 xót và

hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các 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!

Thái Nguyên, tháng 9-2010

Người viết luận văn

Dương Thị Bình

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

Bài toán bất đẳng thức biến phân là một công cụ rất hữu hiệu để nghiên cứu và giải

các bài toán ứng dụng như các bài toán cân bằng trong kinh tế, tài chính, vận tải, lí

thuyết trò chơi, bài toán cân bằng mạng, · · · .

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ó dạng 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 application" của D.Kinderlehrer và G. Stampacchia xuất bản năm 1980 [8]

và trong cuốn sách "Variational and quasivariational inequalities: Application to free

boundary problem" của Baiocci và Capelo xuất bản năm 1984.

Từ đó, 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. Thực tế cho thấy việc giải trực tiếp để tìm nghiệm của bài toán bất đẳng thức

biến phân là khó khăn và không phải trường hợp nào cũng thực hiện được. Vì vậy các

nhà toán học đã nghiên cứu và xây dựng nhiều thuật toán vô hạn để tìm nghiệm của

bài toán này, tuy nhiên việc tìm ra nghiệm chính xác là khó thực hiện được. Do đó

người ta thường phải lấy nghiệm xấp xỉ với độ chính xác nào đó.

Những năm gần đây việc nghiên cứu giải tích đa trị cũng phát triển mạnh, điều

này giúp cho các nhà toán học có cái nhìn rộng hơn về lớp các bài toán tối ưu, trong

đó có bài toán bất đẳng thức biến phân. Vì vậy việc nghiên cứu bất đẳng thức biến

phân đa trị cũng có những bước phát triển mới. Nhiều phương pháp đã được đề xuất

để tìm nghiệm xấp xỉ của bài toán bất đẳng thức biến phân đa trị như: Phương pháp

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

chiếu tổng quát, phương pháp siêu phẳng cắt, · · · .

Luận văn này trình bày phương pháp xấp xỉ trong giải bài toán bất đẳng thức biến

phân đa trị giả đơn điệu được viết trong bài báo của Phạm Ngọc Anh " An interior

proximal method for solving pseudomonotone nonlipschitzian multivalued variational

inequalities, Nonlinear Analysis Forum 14, (2009), 27-42." [4] và một kết quả mới về

thuật toán điểm gần kề mở rộng cho bài toán bất đẳng thức biến phân đa trị. [6]

Ngoài lời nói đầu và phần tài liệu tham khảo, luận văn gồm 4 chương. Chương 1

nhắc lại các kiến thức cơ bản của giải tích lồi, ánh xạ đa trị liên tục Lipschitz và ánh

xạ đa trị đơn điệu. Phần tiếp theo, phát biểu bài toán bất đẳng thức biến phân đa trị,

các bài toán liên quan và một số ví dụ thực tế, đồng thời trình bày điều kiện có nghiệm

của bài toán này. Chương 2 gồm hai phần chính: Phần thứ nhất giới thiệu về phương

pháp hàm phạt điểm trong; Phần thứ hai trình bày thuật toán xấp xỉ trong giải bài

toán (MV I) giả đơn điệu Lipschitz và chứng minh sự hội tụ của thuật toán. Chương

3 đề xuất thuật toán giải bài toán (MV I) không có điều kiện Lipschitz. Chương này

đưa ra thuật toán xấp xỉ, trong đó có sự kết hợp hàm logarit toàn phương với kĩ thuật

đường tìm kiếm. Cuối chương trình bày một số kết quả tính toán cụ thể minh họa cho

thuật toán ở chương 2 và chương 3. Chương 4 trình bày phương pháp mới để giải bài

toán (MV I) và các kết quả tính toán để minh họa thuật toán đã đề xuất.

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