Phương pháp hàm phạt điểm trong giải bài toán cân bằng giả đơn điệu

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

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

DƯƠNG HỒNG PHÚC

PHƯƠNG PHÁP HÀM PHẠT

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

CÂN BẰNG GIẢ ĐƠN ĐIỆU

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

THÁI NGUYÊN - NĂM 2010

1Số 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 HỌC THÁI NGUYÊN

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

DƯƠNG HỒNG PHÚC

PHƯƠNG PHÁP HÀM PHẠT

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

CÂN BẰNG 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

2Số 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ột số kí hiệu và chữ viết tắt iv

Lời nói đầu 1

1 Bài toán cân bằng 2

1.1 Các kiến thức cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.1.1 Tập lồi và các phép toán về tập lồi . . . . . . . . . . . . . . 2

1.1.2 Hàm lồi và dưới vi phân . . . . . . . . . . . . . . . . . . . . 5

1.2 Bài toán cân bằng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.2 Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Phương pháp hàm phạt điểm trong 15

2.1 Phương pháp hàm phạt điểm trong ([2]) . . . . . . . . . . . . . . . 15

2.1.1 Ý tưởng chính . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.2 Phương pháp hàm phạt điểm trong . . . . . . . . . . . . . 16

2.2 Hàm toàn phương logarit ([3]) . . . . . . . . . . . . . . . . . . . . . 19

2.3 Mô tả thuật toán và sự hội tụ ([3]) . . . . . . . . . . . . . . . . . . 23

2.4 Thuật toán bỏ qua điều kiện Lipschitz ([3]) . . . . . . . . . . . . . 30

3 Một số ứng dụng 36

3.1 Bài toán bất đẳng thức biến phân ([3]) . . . . . . . . . . . . . . . . 36

3Số 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.2 Thuật toán điểm gần kề giải bài toán (MV I) . . . . . . . . . . . . 39

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

3.2.2 Đề xuất thuật toán . . . . . . . . . . . . . . . . . . . . . . . 44

3.2.3 Sự hội tụ của phương pháp . . . . . . . . . . . . . . . . . . 46

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

Kết luận 54

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

Tài liệu tham khảo 56

4Số 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

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 chân thành và sâu sắc tới thầy 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 nghiên cứu và 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 Bộ môn Toán-Tin, Phòng

Đào tạo khoa học và Quan hệ quốc tế, các bạn học viên lớp Cao học Toán K2

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

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 và động viên tác giả trong suốt quá trình học cao học và viết

luận văn này.

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à các

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 11 - 2010

Tác giả

Dương Hồng Phúc

5Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iv

Một số kí hiệu và chữ viết tắt

R

n không gian Euclide n-chiều

|β| trị tuyệt đối của số thực β

x := y x được định nghĩa bằng y

∀x với mọi x

∃x tồn tại x

k x k chuẩn của véc tơ x

hx, yi tích vô hướng của hai véc tơ x, y

A ⊂ B tập A là tập con thực sự của tập B

A ⊆ B tập A là tập con của tập B

A ∪ B A hợp với B

A ∩ B A giao với B

A × B tích Đề-các của hai tập A và B

argmin{f(x) | x ∈ C} tập các điểm cực tiểu của hàm f trên C

AT ma trận chuyển vị của ma trận A

x

k → x dãy {x

k} hội tụ mạnh tới x

V IP bài toán bất đẳng thức biến phân đơn trị

MV I bài toán bất đẳng thức biến phân đa trị

EP bài toán cân bằng

t.ư. tương ứng

6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn