Phương pháp newton nửa trơn cho bài toán bù phi tuyến

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

Mục lục

1 Lời nói đầu

2 Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG

DỤNG

1.1 Phát biểu bài toán

1.2 Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân

1.3 Ứng dụng của bài toán bất đẳng thức biến phân

3 CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN

CHO BÀI TOÁN BÙ PHI TUYẾN

2.1 Giới thiệu bài toán

2.2 Tính chất của toán tử Φλ

Tính chất của hàm Ψλ

2.4 Thuật toán và sự hội tụ

2.5 Kết quả tính toán

4 KẾT LUẬN

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

Lý do chọn đề tài

Lý thuyết bất đẳng thức biến phân ra đời vào những năm 60 của

thế kỷ XX, là một công cụ mạnh và thống nhất để nghiên cứu các

bài toán cân bằng. Bài toán bất đẳng thức biến phân được giới

thiệu lần đầu tiên vào năm 1966.Những nghiên cứu đầu tiên về bất

đẳng thức biến phân liên quan tới việc giải các bài toán biến phân,

bài toán điều khiển tối ưu và các bài toán biên cho phương trình

đạo hàm riêng.

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

Lý do chọn đề tài

Bất đẳng thức biến phân là một công cụ khá hữu ích trong việc

nghiên cứu và giải các bài toán cân bằng trong kinh tế, cơ khí,

nghiên cứu toán tử và vật lí toán. Bài toán bất đẳng thức biến

phân liên quan mật thiết đến các bài toán tối ưu khác. Gần đây, bài

toán bất đẳng thức biên phân cũng là một đề tài được nhiều người

quan tâm nghiên cứu vì vai trò của nó được sử dụng như một công

cụ lập trình toán học trong mô hình một lớp rộng các vấn đề phát

sinh trong ngành khoa học thuần túy và ứng dụng. Trong những

hướng nghiên cứu gần đây, việc giải bài toán bất đẳng thức biến

phân được đưa về việc giải một bài toán tương đương có tên là bài

toán bù phi tuyến (Nonlinear complementarity problems - NCP)

[4]. Với mong muốn tìm hiểu những kiến thức mới so với bản thân,

dưới sự gợi ý và hướng dẫn của cô Phan Quang Như Anh, em

chọn đề tài: Phương pháp Newton nửa trơn cho bài toán bù

phi tuyến để làm khóa luận tốt nghiệp của mình.

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

Mục đích nghiên cứu

• Bất đẳng thức biến phân.

• Bài toán bù phi tuyến.

• Phương pháp Newton nửa trơn cho bài toán bù phi tuyến.

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

Bố cục của khóa luận

Ngoài phần mở đầu, kết luận, tài liệu tham khảo, khóa luận được

trình bày trong ba chương:

• Chương 1: Kiến thức chuẩn bị. Chương này trình bày các kiến

thức liên quan đến không gian Euclid - n chiều, tập lồi, nón lồi,

hàm lồi, đạo hàm riêng, gradient, phép chiếu trực giao.

• Chương 2: Trình bày bài toán bất đẳng thức biến phân và ứng

dụng, các định lý về nghiệm của bài toán bất đẳng thức biến phân,

mối liên hệ giữa bài toán bất đẳng thức biến phân và bài toán bù

phi tuyến.

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

Bố cục của khóa luận

• Chương 3: Trình bày phương pháp Newton nửa trơn cho bài toán

bù phi tuyến. Thuật toán thoạt đầu rất giống phương pháp

Newton cổ điển ứng dụng cho hệ phương trình trơn. Tuy nhiên,

điểm khác biệt ở đây là ta sử dụng khái niệm Jacobian suy rộng

theo Clark [14] thay vì dùng khái niệm Jacobian cổ điển. Thuật

toán ở đây hội tụ toàn cục với tốc độ hội tụ là siêu tuyến tính.

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

1.1 Phát biểu bài toán

Bài toán

Cho C là một tập con, lồi, đóng, khác rỗng của R

n và

F : C → R

n

. Khi đó bài toán bất đẳng thức biến phân, viết tắt

VI(F, C), được phát biểu dưới dạng:

Tìm x

∗ ∈ C sao cho hF (x

∗

), x − x

∗

i ≥ 0 ∀x ∈ C .

Như thường lệ, F được gọi là ánh xạ giá.

Một biểu diễn hình học của bài toán bất đẳng thức biến phân

VI(F, C) có dạng: x

∗ ∈ C là một nghiệm của VI(F, C) khi và chỉ

khi góc tạo bởi véc tơ F(x

∗

) và véc tơ y − x

∗

là góc nhọn hoặc

vuông góc với mọi y ∈ C.

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

1.2 Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân

Định nghĩa 1.2.1

Cho C là một tập con, lồi, khác rỗng của không gian R

n

và một

ánh xạ F : C → R

n

. Ánh xạ F được gọi là

(a) đơn điệu mạnh (strongly monotone) trên C với hằng số β > 0,

nếu

hF (x) − F (y), x − yi ≥ βkx − yk

2

∀x, y ∈ C,

(b) đơn điệu chặt (strictly monotone) trên C, nếu

hF (x) − F (y), x − yi > 0 ∀x, y ∈ C, x 6= y,

(c) đơn điệu (monotone) trên C, nếu

hF (x) − F (y), x − yi > 0 ∀x, y ∈ C,

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

1.2 Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân

(d) γ-giả đơn điệu mạnh (strongly pseudomonotone) trên C, nếu

với mỗi x, y ∈ C,

hF (y), x − yi ≥ 0 ⇒ hF (x), x − yi ≥ γkx − yk

2

,

(e) giả đơn điệu (pseudomonotone) trên C, nếu với mỗi x, y ∈ C,

hF (y), x − yi ≥ 0 ⇒ hF (x), x − yi ≥ 0,

(f) tựa đơn điệu (quasimonotone) trên C, nếu với mỗi x, y ∈ C,

hF (y), x − yi > 0 ⇒ hF (x), x − yi ≥ 0,

(g) tựa đơn điệu hiển (explicilty quasimonotone) trên C, nếu với

mỗi x, y ∈ C,

hF (y), x − yi > 0 ⇒ hF (z), x − yi ≥ 0 ∀z ∈



x + y

2

, x



.

Lời nói đầu Chương 1. BẤT ĐẲNG THỨC BIẾN PHÂN VÀ ỨNG DỤNG CHƯƠNG 2. PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN KẾT LUẬN

1.2 Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân

Mệnh đề 1.2.2

Cho C là một tập con, lồi khác rỗng của R

n

. Nếu F : C → R

n

là

ánh xạ tựa đơn điệu và affine (hay F(x) = Mx + q, M là một ma

trận vuông cấp n), thì F là tựa đơn điệu hiển trên C.

Mệnh đề 1.2.3

Cho C là một tập còn, lồi, mở và khác rỗng của R

n

. Nếu

F : C → R

n

là ánh xạ tựa đơn điệu và affine (hay F(x) = Mx + q,

M là một ma trận vuông cấp n), thì F là giả đơn điệu trên C.