Một số mở rộng phương pháp Korpelevich cho bài toán bất đẳng thức biến phân

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

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

-------------------------------

ĐỖ MẠNH CƯỜNG

MỘT SỐ MỞ RỘNG

PHƯƠNG PHÁP KORPELEVICH CHO BÀI TOÁN

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

Chuyên ngành: Toán ứng dụng

Mã số: 8 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

Hướng dẫn 1: TS. Nguyễn Song Hà

Hướng dẫn 2: TS. Đinh Diệu Hằng

THÁI NGUYÊN - 2021

ii

LỜI CẢM ƠN

Tôi muốn gửi lời cảm ơn và biết ơn chân thành của mình tới tất cả những

người đã hỗ trợ, giúp đỡ tôi về chuyên môn, vật chất và tinh thần trong quá

trình thực hiện luận văn.

Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS. Nguyễn Song Hà và TS. Đinh

Diệu Hằng, người đã hướng dẫn, nhận xét và giúp đỡ tôi rất nhiều trong suốt

quá trình thực hiện và hoàn thiện luận văn.

Tôi cũng xin cảm ơn các Thầy Cô giáo, các phòng ban chức năng, Khoa

Toán-Tin thuộc trường Đại học Khoa học - Đại học Thái Nguyên, những

người đã trực tiếp giảng dạy, đã động viên và giúp đỡ tôi trong suốt quá trình

học tập tại trường.

Tôi xin gửi lời cám ơn đến tập thể lớp K12A6, lớp K13A, gia đình bạn bè

và đồng nghiệp đã giúp đỡ, động viên tôi trong suốt quá trình học tập và

thực hiện luận văn này.

Tác giả

Đỗ Mạnh Cường

Mục lục

Trang bìa phụ i

Lời cảm ơn ii

Mục lục iii

Danh mục ký hiệu và chữ viết tắt iv

Danh sách bảng v

Mở đầu 1

Chương 1. Kiến thức chuẩn bị 2

1.1. Không gian Hilbert thực . . . . . . . . . . . . . . . . . . . . . 2

1.2. Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3. Phép chiếu mêtric . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4. Ánh xạ đơn điệu và liên tục . . . . . . . . . . . . . . . . . . . 15

Chương 2. Phương pháp kiểu Korpelevich cho bài toán bất đẳng

thức biến phân 18

2.1. Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2. Phương pháp EGM và PCM . . . . . . . . . . . . . . . . . . . 23

2.3. Phương pháp SEGM . . . . . . . . . . . . . . . . . . . . . . . 30

2.4. Phương pháp MSEGM . . . . . . . . . . . . . . . . . . . . . . 37

Kết luận chung và đề nghị 43

Tài liệu tham khảo 44

Danh mục ký hiệu và chữ viết tắt

H Không gian Hilbert thực

R

n Không gian thực hữu hạn chiều

co(C) Bao lồi của tập C

cl(C) Bao đóng của tập C

C\D Phần bù của tập hợp D trong C

⟨x, y⟩ Tích vô hướng của hai véctơ x và y

∥x∥ Chuẩn của véctơ x

∀x Với mọi x

F : X → Y Ánh xạ đơn trị từ X vào Y

F : X ⇒ Y Ánh xạ đa trị từ X vào Y

PC(x) Phép chiếu mêtric phần tử x lên tập C

α ↓ 0 α giảm dần về 0

∇f(x) Gradient của ánh xạ f tại x

∂f(x) Dưới vi phân của ánh xạ f tại x

xn → x Dãy {xn} hội tụ mạnh đến x khi n → +∞

xn ⇀ x Dãy {xn} hội tụ yếu đến x khi n → +∞

(VIP) Bài toán bất đẳng thức biến phân

Sol(VIP(F, C)) Tập nghiệm của bài toán (VIP) với ánh xạ giá F

và miền hữu hiệu C

(EGM) Phương pháp đạo hàm tăng cường

(PCM) Phương pháp chiếu co

(SEGM) Phương pháp dưới đạo hàm - Đạo hàm tăng cường

(MSEGM) Phương pháp dưới đạo hàm - Đạo hàm tăng cường cải biên

Danh sách bảng

2.1 Kết quả tính toán cho phương pháp (EGM) tương ứng với các

giá trị τ thay đổi . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.2 Kết quả tính toán cho phương pháp (SEGM) tương ứng với

các giá trị τ thay đổi . . . . . . . . . . . . . . . . . . . . . . . 37

2.3 Kết quả tính toán cho phương pháp (MSEGM) tương ứng với

các giá trị αk thay đổi . . . . . . . . . . . . . . . . . . . . . . 42