Luận văn Thạc sĩ Khoa học: Một tiếp cận tối ưu hai cấp cho hiệu chỉnh bài toán cân bằng giả đơn điệu

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

57
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn nghiên cứu và trình bày một số phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu và thông qua bài toán tối ưu hai cấp để tìm điểm giới hạn của các quỹ đạo nghiệm hiệu chỉnh.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Một tiếp cận tối ưu hai cấp cho hiệu chỉnh bài toán cân bằng giả đơn điệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- NGUYỄN THỊ THANH HẢI MỘT TIẾP CẬN TỐI ƯU HAI CẤP CHO HIỆU CHỈNH BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU LUẬN VĂN THẠC SỸ KHOA HỌC Hà Nội – Năm 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- NGUYỄN THỊ THANH HẢI MỘT TIẾP CẬN TỐI ƯU HAI CẤP CHO HIỆU CHỈNH 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.01.12 LUẬN VĂN THẠC SỸ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. LÊ DŨNG MƯU Hà Nội – Năm 2015
Mục lục Lời cảm ơn 3 Mở đầu 4 1 Kiến thức chuẩn bị 6 1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Không gian tuyến tính định chuẩn. . . . . . . . . . . . . . . . 6 1.1.2 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Tập lồi, nón lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Nón lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.4 Tính chất của hàm lồi . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Bài toán cân bằng 13 2.1 Bài toán cân bằng và các khái niệm . . . . . . . . . . . . . . . . . . . 13 2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.2 Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Các trường hợp riêng của bài toán cân bằng . . . . . . . . . . . . . . 18 2.2.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Bài toán điểm bất động . . . . . . . . . . . . . . . . . . . . . 19 2.2.3 Bài toán cân bằng Nash trong trò chơi không hợp tác . . . . . 19 2.2.4 Bài toán điểm yên ngựa . . . . . . . . . . . . . . . . . . . . . 20 2.3 Sự tồn tại nghiệm của bài toán cân bằng . . . . . . . . . . . . . . . . 21 2.4 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 Hiệu chỉnh dựa trên tối ưu hai cấp 31 3.1 Hiệu chỉnh bài toán cân bằng giả đơn điệu . . . . . . . . . . . . . . . 31 1
MỤC LỤC 3.1.1 Phương pháp hiệu chỉnh Tikhonov . . . . . . . . . . . . . . . 31 3.1.2 Phương pháp điểm gần kề . . . . . . . . . . . . . . . . . . . 35 3.2 Thuật toán giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.2 Tính hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . 42 3.3 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 Kết luận chung 48 Tài liệu tham khảo 49 2
LỜI CẢM ƠN Qua luận văn này em xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến Thầy GS.TSKH Lê Dũng Mưu, người đã tận tình chỉ bảo, hướng dẫn, giúp đỡ em trong suốt quá trình học tập, nghiên cứu và hoàn thiện luận văn này. Tác giả xin trân trọng cám ơn Ban Giám hiệu, Phòng Đào tạo sau đại học đặc biệt là quý thầy cô trong Khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi cho em hoàn thành khóa học này. Tác giả xin gửi lời cám ơn chân thành tới gia đình, đồng nghiệp, các anh chị, bạn bè trong lớp cao học khóa 2013 - 2015 đã luôn động viên, khích lệ tác giả cố gắng trong suốt khóa học để luôn đạt được kết quả học tập cao nhất. Em xin chân thành cảm ơn! 3
MỞ ĐẦU Lớp các bài toán cân bằng đang ngày càng được áp dụng nhiều vào các lĩnh vực trong cuộc sống như kinh tế, xã hội,... Chính vì vậy mà ngày càng được các nhà khoa học quan tâm, nghiên cứu. Hơn nữa, bài toán cân bằng còn là sự mở rộng của lớp các bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán cân bằng Nash, bài toán điểm yên ngựa,... Mô hình chung cho bài toán cân bằng là Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0 với mọi y ∈ C (EP(C, f )) trong đó H là không gian Hilbert, C ⊆ H là một tập lồi và f : C ×C → R ∪ {+∞} là một song hàm. Bài toán hiệu chỉnh được xây dựng bằng cách thay song hàm ban đầu bằng song hàm fε := f + εg, trong đó ε, g lần lượt là tham số hiệu chỉnh và song hàm hiệu chỉnh, thông thường ta chọn g là một song hàm đơn điệu mạnh. Nếu f là một song hàm đơn điệu thì fε là đơn điệu mạnh, khi đó bài toán hiệu chỉnh luôn có duy nhất nghiệm. Tuy nhiên, nếu f là một song hàm giả đơn điệu thì bài toán hiệu chỉnh trong trường hợp tổng quát không còn là đơn điệu mạnh hay đơn điệu, thậm chí không là giả đơn điệu do đó bài toán hiệu chỉnh nói chung không có nghiệm duy nhất, thậm chí tập nghiệm là không lồi, khi đó không thể áp dụng trực tiếp các phương pháp để hiệu chỉnh cho bài toán EP(C, f ) giả đơn điệu như trong trường hợp đơn điệu. Do đó, luận văn nghiên cứu và trình bày một số phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu và thông qua bài toán tối ưu hai cấp để tìm điểm giới hạn của các quỹ đạo nghiệm hiệu chỉnh. Dựa trên ý tưởng của phương pháp hiệu chỉnh Tikhonov, trong [4] các tác giả đã đưa ra phương pháp hiệu chỉnh với bài toán hiệu chỉnh như sau Tìm x ∈ C sao cho fk (x, y) := f (x, y) + εk g(x, y) ≥ 0 với mọi y ∈ C, trong đó εk > 0 là tham số hiệu chỉnh, g(x, y) là một song hàm đơn điệu mạnh gọi là song hàm hiệu chỉnh. 4
MỞ ĐẦU Năm 1970 Martine đưa ra phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đơn điệu và sau này được mở rộng bởi Rockafellar (1976) cho toán tử đơn điệu cực đaị. Bài toán hiệu chỉnh có dạng Tìm xk ∈ C sao cho fk (xk , y) := f (xk , y) + ck hxk − xk−1 , y − xk i ≥ −δk với mọi y ∈ C, trong đó ck > 0, δk > 0 lần lượt là các tham số hiệu chỉnh và sai số cho trước. Sự khác biệt giữa hai phương pháp này là ở phương pháp hiệu chỉnh điểm gần kề tại mỗi bước lặp bài toán hiệu chỉnh phụ thuộc vào điểm lặp ở bước trước và tham số hiệu chỉnh ck 6→ 0 khi k → ∞. Nội dung của luận văn gồm ba chương • Chương 1: Kiến thức chuẩn bị. • Chương 2: Bài toán cân bằng. • Chương 3: Hiệu chỉnh dựa trên tối ưu hai cấp. Chương 1 trình bày một số kiến thức cơ sở như không gian tuyến tính, không gian Hilbert; các kiến thức về giải tích lồi như tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới. Chương 2 phát biểu bài toán cân bằng, một số trường hợp có thể đưa về bài toán cân bằng và sự tồn tại nghiệm của bài toán. Chương 3 trình bày phương pháp hiệu chỉnh bài toán cân bằng giả đơn điệu, thuật toán tiếp cận dựa trên bài toán tối ưu hai cấp và sự hội tụ của thuật toán. Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế nên luận văn khó tránh khỏi những thiếu sót. Vì vậy em rất mong nhận được sự góp ý của các thầy cô và các bạn để luận văn được hoàn thiện hơn. Hà Nội, ngày 28 tháng 09 năm 2015 Tác giả Nguyễn Thị Thanh Hải 5
Chương 1 Kiến thức chuẩn bị Chương này chúng ta nhắc lại một số kiến thức về không gian tuyến tính, không gian Hilbert, tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới. Các kiến thức này được lấy ra từ các tài liệu [1], [2]. 1.1 Không gian Hilbert 1.1.1 Không gian tuyến tính định chuẩn. Định nghĩa 1.1.1. Cho X là một không gian tuyến tính thực. Một chuẩn trên X, kí hiệu là k.k, là một ánh xạ k.k : X → R thỏa mãn các tính chất sau 1. kxk ≥ 0, ∀x ∈ X; kxk = 0 ⇔ x = 0; 2. kαxk = |α|kxk, ∀x ∈ X, α ∈ R; 3. kx + yk ≤ kxk + kyk, ∀x, y ∈ X. Khi đó (X, k.k) được gọi là không gian tuyến tính định chuẩn. Định nghĩa 1.1.2. Cho X là không gian tuyến tính thực, X được gọi là không gian tiền Hilbert nếu với mọi x, y ∈ X, xác định một tích vô hướng, kí hiệu là hx, yi, thỏa mãn các tính chất 1. hx, yi = hy, xi, ∀x, y ∈ X; 2. hx + y, zi = hx, zi + hy, zi, ∀x, y, z ∈ X; 3. hαx, yi = αhx, yi, ∀x, y ∈ X, α ∈ R; 4. hx, xi ≥ 0, ∀x ∈ X; hx, xi = 0 ⇔ x = 0. 6
Chương 1. Kiến thức chuẩn bị 1.1.2 Không gian Hilbert Bổ đề 1.1.1. Mọi không gian tiền Hilbert X là không gian tuyến tính định chuẩn, với chuẩn được xác định như sau p kxk = hx, xi, ∀x ∈ X. Định nghĩa 1.1.3. Cho X là không gian định chuẩn. Dãy {xn } ⊆ X được gọi là dãy cơ bản trong X nếu lim kxn − xm k = 0. n,m→∞ Nếu trong X, mọi dãy cơ bản đều hội tụ, tức là kxn − xm k → 0 kéo theo sự tồn tại xo ∈ X sao cho xn → xo thì X được gọi là không gian đủ. Định nghĩa 1.1.4. Không gian tiền Hilbert và đủ được gọi là không gian Hilbert. Trong luận văn này ta thống nhất kí hiệu H là một không gian Hilbert trên trường số thực. Ví dụ 1.1.1. Lấy H = Rn với tích vô hướng xác định bởi hệ thức hx, yi = ∑ xi yi . i=1→n Trong đó x = (x1 , x2 , ..., xn ), y = (y1 , y2 , ..., yn ) ∈ Rn . Khi đó H là một không gian Hilbert. Trên H có hai kiểu hội tụ sau Định nghĩa 1.1.5. Xét dãy {xn }n≥0 và x thuộc không gian Hilbert thực H . Dãy {xn } được gọi là hội tụ mạnh đến x, kí hiệu là xn → x nếu lim kxn − xk = 0. n→+∞ Dãy {xn } được gọi là hội tụ yếu đến x, kí hiệu là xn * x nếu lim hw, xn i = hw, xi, ∀w ∈ H . n→+∞ Điểm x được gọi là điểm tụ mạnh (hay yếu) của dãy {xn } nếu từ dãy này có thể trích ra một dãy con hội tụ mạnh (hay yếu) tới x. Mệnh đề 1.1.1. 1. Nếu {xn } hội tụ mạnh đến x thì cũng hội tụ yếu đến x. 2. Nếu {xn } hội tụ yếu đến x và limn→+∞ kxn k = kxk thì {xn } hội tụ mạnh đến x. 7
Chương 1. Kiến thức chuẩn bị 3. Mọi dãy hội tụ mạnh (yếu) đều bị chặn và giới hạn theo sự hội tụ mạnh (yếu) nếu tồn tại là duy nhất. 4. Nếu H là không gian Hilbert hữu hạn chiều thì sự hội tụ mạnh và hội tụ yếu là tương đương. 5. Nếu {xn } là dãy bị chặn trong không gian Hilbert H thì ta luôn trích ra được một dãy con hội tụ yếu. 6. Nếu {xn } là dãy bị chặn trong không gian Hilbert hữu hạn chiều H thì ta luôn trích ra được một dãy con hội tụ mạnh. 1.2 Tập lồi, nón lồi, hàm lồi 1.2.1 Tập lồi Định nghĩa 1.2.1. Một tập C ⊆ H được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λ x + (1 − λ )y ∈ C. Mệnh đề 1.2.1. Tập hợp C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó. Tức là, C lồi khi và chỉ khi k k 1 k ∀k ∈ N, ∀λ1 , λ2 , ..., λk ≥ 0 : ∑ λ j = 1, ∀x , ..., x ∈C ⇒ ∑ λ j x j ∈ C. (1.1) j=1 j=1 Chứng minh. Ta thấy, điều kiện đủ được suy ra trực tiếp từ định nghĩa. Ta chứng minh điều kiện cần bằng quy nạp. Với k = 2 công thức (1.1) tương đương với chứng minh C lồi khi và chỉ khi ∀λ1 , λ2 ≥ 0 : λ1 + λ2 = 1, ∀x1 , x2 ∈ C ⇒ λ1 x1 + λ2 x2 ∈ C. Điều này suy ra trực tiếp từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng với (k − 1) điểm. Ta cần chứng minh đúng với k điểm. Giả sử x là tổ hợp lồi của k điểm x1 , ..., xk ∈ C. Tức là k k j x= ∑ λ jx , λ j ≥ 0, ∀ j = 1, 2, ..., k, ∑ λ j = 1. j=1 j=1 Đặt k−1 ξ= ∑ λ j. j=1 8
Chương 1. Kiến thức chuẩn bị Khi đó 0 < ξ < 1 và k−1 k−1 λj j x= ∑ λ j x j + λk xk = ξ ∑ x + λk xk . j=1 j=1 ξ Do k−1 λj ∑ =1 j=1 ξ λj và ξ > 0 với mọi j = 1, 2, ..., k − 1, nên theo giả thiết quy nạp, điểm k λj j y := ∑ x ∈ C. j=1 ξ Ta có x = ξ y + λk xk . Do ξ > 0, λk > 0 và k ξ + λk = ∑ λj = 1 j=1 nên x là tổ hợp lồi của hai điểm y và xk đều thuộc C. Vậy x ∈ C. 1.2.2 Nón lồi Định nghĩa 1.2.2. Tập C được gọi là nón nếu với mọi λ > 0 và với mọi x ∈ C suy ra λ x ∈ C. Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi. Mệnh đề 1.2.2. Một tập C là nón lồi khi và chỉ khi có các tính chất sau 1. λC ⊆ C ∀λ > 0; 2. C +C ⊆ C. Chứng minh. Giả sử C là một nón lồi. Do C là một nón nên ta có 1). Mặt khác, do C là một tập lồi nên với mọi x, y ∈ C thì 12 (x + y) ∈ C. Vậy theo 1) ta có x + y ∈ C. Ngược lại, giả sử ta có 1) và 2). Từ 1) ta suy ra C là một nón. Giả sử x, y ∈ C và λ ∈ [0, 1]. Từ 1) suy ra λ x ∈ C và (1 − λ )y ∈ C. Vậy C là một nón lồi. Định nghĩa 1.2.3. Cho C ⊆ H là một tập lồi khác rỗng và x ∈ C. Khi đó tập NC {x} := {w| w, y − x ≤ 0 ∀y ∈ C} 9
Chương 1. Kiến thức chuẩn bị được gọi là nón pháp tuyến ngoài của C tại x. Tập −NC {x} := {w| w, y − x ≤ 0 ∀y ∈ C} được gọi là nón pháp tuyến trong của C tại x. Định nghĩa 1.2.4. Cho C 6= 0/ (không nhất thiết lồi) và y là một vectơ bất kỳ, đặt dC (y) := inf kx − yk. x∈C Ta nói dC (y) là khoảng cách từ y đến C. Nếu tồn tại π ∈ C sao cho dC (y) = kπ − yk, thì ta nói π là hình chiếu của y trên C, kí hiệu pC (y). Theo định nghĩa trên ta thấy rằng, hình chiếu pC (y) của y trên C sẽ là nghiệm của bài toán tối ưu 1 min{ kx − yk2 |x ∈ C}. x 2 1.2.3 Hàm lồi Định nghĩa 1.2.5. Cho C ⊆ H là một tập lồi và f : C → R ∪ {+∞}. Khi đó tập dom f := {x ∈ C| f (x) < +∞} được gọi là miền hữu dụng của tập f. Tập epi f := {(x, µ) ∈ C × R | f (x) ≤ µ} được gọi là trên đồ thị của hàm f. Định nghĩa 1.2.6. 1. Cho 0/ 6= C ⊆ H lồi và f : C → R ∪ {+∞}. Ta nói f là hàm lồi trên C nếu f λ x + (1 − λ )y ≤ λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ [0, 1]. 2. Hàm f : H → R ∪ {+∞} được gọi là lồi chặt trên C nếu f λ x + (1 − λ )y < λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1). 3. Hàm f : H → R ∪ {+∞} được gọi là lồi mạnh trên C với hệ số η nếu với mọi x, y ∈ C và với mọi λ ∈ (0, 1) 1 f λ x + (1 − λ )y ≤ λ f (x) + (1 − λ ) f (y) − ηλ (1 − λ )kx − yk2 . 2 10
Chương 1. Kiến thức chuẩn bị 4. Hàm f được gọi là hàm lõm trên C nếu − f là hàm lồi trên C. Định nghĩa 1.2.7. Một hàm số thực ϕ được gọi là tựa lồi trên một tập lồi C nếu với mọi số thực γ tập mức dưới {x ∈ C|ϕ(x) ≤ γ} lồi. Tương tự hàm ϕ được gọi là tựa lõm trên C nếu −ϕ là hàm tựa lồi trên C. Nhận thấy nếu ϕ là tựa lồi trên C thì với mọi x, y ∈ C và λ ∈ [0, 1] ta có ϕ(λ x + (1 − λ )y) ≤ max(ϕ(x), ϕ(y)). Tương tự nếu ϕ là tựa lõm trên C thì với mọi x, y ∈ C và λ ∈ [0, 1] ta có ϕ(λ x + (1 − λ )y) ≥ min(ϕ(x), ϕ(y)). Từ định nghĩa ta thấy, mọi hàm lồi (lõm) trên C, đều tựa lồi (tựa lõm) trên C. Định nghĩa 1.2.8. Cho f là một hàm lồi trên tập lồi A. Một véc tơ y∗ ∈ H được gọi là dưới vi phân của f tại x∗ ∈ A nếu f (x) ≥ f (x∗ ) + hy∗ , x − x∗ i, ∀x ∈ A. Tập hợp tất cả các điểm y∗ thỏa mãn bất đẳng thức trên được kí hiệu là ∂ f (x∗ ). Định nghĩa 1.2.9. Hàm f : H → R ∪ {+∞} được gọi là nửa liên tục dưới đối với E tại một điểm x nếu như với mọi dãy {xn } ⊂ E, xk → x ta có lim in f f (xk ) ≥ f (x). Hàm f : H → R ∪ {+∞} được gọi là nửa liên tục trên đối với E tại một điểm x nếu như với mọi dãy {xn } ⊂ E, xk → x ta có lim sup f (xk ) ≤ f (x). Hàm f được gọi là nửa liên tục dưới (nửa liên tục trên) đối với E trong tập A nếu nó nửa liên tục dưới (nửa liên tục trên) đối với E tại mọi điểm thuộc A. Nhận xét Nếu f là nửa liên tục dưới thì − f là nửa liên tục trên. Khi f liên tục (nửa liên tục) tại một điểm x, đối với toàn không gian, thì ta nói đơn giản f liên tục (nửa liên tục) tại x. 1.2.4 Tính chất của hàm lồi Mệnh đề 1.2.3. Một hàm f : C → R ∪ {+∞} là lồi trên C khi và chỉ khi ∀x, y ∈ C, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1] ⇒ f (λ x + (1 − λ )y) ≤ λ α + (1 − λ )β . 11
Chương 1. Kiến thức chuẩn bị Chứng minh. Điều kiện cần. Giả sử f lồi. Chọn x, y, α, β thỏa mãn các giả thiết của mệnh đề. Chọn α 0 ∈ ( f (x), α) và β 0 ∈ ( f (y), β ). Vậy (x, α 0 ) và (y, β 0 ) thuộc epi f . Do epi f lồi, nên ((1 − λ )x + λ y, (1 − λ )α 0 + λ β 0 ) ∈ epi f . Do đó f ((1 − λ )x + λ y) ≤ (1 − λ )α 0 + λ β 0 < (1 − λ )α + λ β . Điều kiện đủ. Chọn (x, µ) và (y, υ) thuộc epi f và λ ∈ (0, 1). Khi đó, với mọi ε > 0, ta có f (x) < µ + ε, f (y) < υ + ε. Do đó f [(1 − λ )α 0 + λ β 0 ] < (1 − λ )(µ + ε) + λ (υ + ε), = (1 − λ )µ + λ υ + ε. Điều này đúng với mọi ε > 0, nên cho ε → 0, ta được f [(1 − λ )α 0 ] ≤ (1 − λ )µ + λ υ. Chứng tỏ (1 − λ )(x, µ) + λ (y, υ) ∈ epi f . Vậy f lồi. 1.3 Kết luận Chương 1 đã trình bày một số kiến thức chuẩn bị cho nội dung chính của luận văn. Các kiến thức về giải tích hàm như không gian tuyến tính định chuẩn, không gian tiền Hilbert, không gian Hilbert; sự hội tụ mạnh, hội tụ yếu trong không gian Hilbert. Các kiến thức về giải tích lồi như tập lồi, nón lồi, hàm lồi, hàm lồi chặt, hàm lồi mạnh với hệ số η; các tính chất của hàm lồi; khái niệm về hàm nửa liên tục trên, nửa liên tục dưới. 12
Chương 2 Bài toán cân bằng Chương này chúng ta nhắc lại các khái niệm về song hàm cân bằng, toán tử cân bằng và phát biểu bài toán cân bằng. Một số bài toán có thể đưa về dạng bài toán cân bằng và sự tồn tại nghiệm của bài toán. Các kiến thức này được tham khảo từ các tài liệu [2], [3]. 2.1 Bài toán cân bằng và các khái niệm Trong kinh tế và nhiều lĩnh vực khác bài toán cân bằng có nhiều ý nghĩa quan trọng. Hơn nữa, bài toán là sự mở rộng của nhiều bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash, bài toán điểm yên ngựa,... Vì vậy mà lớp các bài toán cân bằng được nhiều nhà toán học quan tâm, nghiên cứu. 2.1.1 Phát biểu bài toán Định nghĩa 2.1.1. Giả sử C ⊆ H là một tập lồi, đóng, khác rỗng và f : H × H → R ∪ {+∞} thỏa mãn f (x, x) = 0 với mọi x ∈ C. Khi đó ta gọi hàm f là một song hàm cân bằng trên C. Cho f là một song hàm cân bằng trên C. Ta xét bài toán Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. (EP(C, f )) Ta kí hiệu bài toán này là EP(C, f ) và gọi là bài toán cân bằng, tập nghiệm của nó được kí hiệu là S(C, f ). 2.1.2 Các khái niệm Định nghĩa 2.1.2. Song hàm f : H × H → R ∪ {+∞} được gọi là 13
Chương 2. Bài toán cân bằng 1. đơn điệu mạnh trên C với hệ số γ > 0 nếu f (x, y) + f (y, x) ≤ −γkx − yk2 , ∀x, y ∈ C; 2. đơn điệu trên C nếu f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; 3. giả đơn điệu trên C nếu f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C. Từ định nghĩa trên ta suy ra: 1) ⇒ 2) ⇒ 3). Điều ngược lại chưa chắc đã đúng.Thật vậy, để làm rõ vấn đề này ta xét một số ví dụ sau. Ví dụ 2.1.1. Xét song hàm f (x, y) = εhx, y − xi, ∀x, y ∈ H , trong đó ε > 0. Với hằng số γ > 0 nào đó thỏa mãn γ ≤ ε ta có f (x, y) + f (y, x) = εhx, y − xi + εhy, x − yi; = εh−x + y, x − yi; = −εkx − yk2 ≤ −γkx − yk2 . Chứng tỏ f là song hàm đơn điệu mạnh trên H . Do γ > 0 nên từ đẳng thức f (x, y) + f (y, x) ≤ −γkx − yk2 ta suy ra f (x, y) + f (y, x) ≤ 0 ∀x, y ∈ H , chứng tỏ f là đơn điệu trên H . Giả sử f (x, y) ≥ 0 với mọi x, y ∈ H . Khi đó, do f (x, y) + f (y, x) ≤ 0, suy ra f (y, x) ≤ − f (x, y) ≤ 0, ∀x, y ∈ H . Vậy f là song hàm giả đơn điệu. 14
Chương 2. Bài toán cân bằng Ví dụ 2.1.2. Xét song hàm f (x, y) = (x2 + 1)(y − x), ∀x, y ∈ R. Giả sử f (x, y) ≥ 0 với mọi x, y ∈ R, suy ra y ≥ x với mọi x, y ∈ R. Khi đó f (y, x) = (y2 + 1)(x − y) ≤ 0, ∀x, y ∈ R. Vậy f là song hàm giả đơn điệu. Tuy nhiên f (x, y) + f (y, x) = (x2 + 1)(y − x) + (y2 + 1)(x − y); = −(x − y)2 (x + y). Khi đó, nếu chọn x, y ∈ R sao cho x 6= y và x + y < 0 thì f (x, y) + f (y, x) > 0, nghĩa là f không đơn điệu trên R. Ví dụ 2.1.3. Cho không gian Hilbert thực ∞ H = l2 := x = (x1 , x2 , ..., xi , ...) := ∑ |xi |2 < +∞, ∀xi ∈ R . i=1 Tích vô hướng và chuẩn trên H tương ứng được xác định bởi ∞ p hx, yi := ∑ xi yi , kxk := hx, xi i=1 với mọi x = (x1 , x2 , ..., xi , ...) = (x1 , xb) ∈ H , y = (y1 , y2 , ..., yi , ...) = (y1 , yb) ∈ H , trong đó xb := (x2 , ..., xi , ...), yb := (y2 , ..., yi , ...). Kí hiệu ∞ p hb x, ybi := ∑ xi yi , kb xk := hb x, xbi. i=2 √ Xét tập C = {x ∈ H : kxk ≤ 2} và hàm f : C ×C → R được cho bởi f (x, y) = (2 − kb xk)hb x, yb− xbi. Nhận thấy, tập nghiệm của bài toán EP(C, f ) là Ce := S(C, f ) = {(x1 , 0, ..., 0, ...) : x1 ∈ R)}. 15
Chương 2. Bài toán cân bằng Với x, y ∈ C ta có 2 − kb xk > 0 và 2 − kb yk > 0. Do đó f (x, y) = (2 − kb xk)hb x, yb− xbi ≥ 0; ⇒ hb x, yb− xbi ≥ 0; ⇒ hb y, xb− ybi ≤ 0; ⇒ f (y, x) = (2 − kb yk)hb y, xb− ybi ≤ 0. Chứng tỏ f là song hàm giả đơn điệu trên C. √ Lấy x = (0, 1, 0, ..., 0, ...), y = (0, 2, 0, ..., 0, ...) ∈ C. Khi đó √ xb = (1, 0, ..., 0, ...), yb = ( 2, 0, ..., 0, ...) và √ kb xk = 1, kb yk = 2. Nhận thấy √ √ √ √ f (x, y) + f (y, x) = (2 − 1) × 1 × ( 2 − 1) + (2 − 2) × 2 × (1 − 2) √ √ = ( 2 − 1) × (2 2 − 1) > 0. Vậy, f không đơn điệu trên C. Định nghĩa 2.1.3. Cho C ⊂ H . Toán tử F : C → H được gọi là 1. đơn điệu mạnh trên C với hệ số γ > 0 nếu hF(x) − F(y), x − yi ≥ γkx − yk2 , ∀x, y ∈ C; 2. đơn điệu trên C nếu hF(x) − F(y), x − yi ≥ 0, ∀x, y ∈ C; 3. giả đơn điệu trên C nếu hF(x), x − yi ≤ 0 ⇒ hF(y), y − xi ≥ 0. Ta đặt f (x, y) = hF(x), y − xi. Khi đó toán tử cân bằng trở thành song hàm cân bằng. 16
Chương 2. Bài toán cân bằng Nhận xét Nếu F là toán tử đơn điệu mạnh, đơn điệu hoặc giả đơn điệu trên C thì f cũng là song hàm đơn điệu mạnh, đơn điệu hoặc giả đơn điệu trên C. Thật vậy Nếu toán tử F là đơn điệu mạnh trên C với hệ số γ > 0, khi đó hF(x) − F(y), x − yi ≥ γkx − yk2 , ∀x, y ∈ C; ⇔ hF(x), x − yi − hF(y), x − yi ≥ γkx − yk2 , ∀x, y ∈ C; ⇔ −hF(x), y − xi − hF(y), x − yi ≥ γkx − yk2 , ∀x, y ∈ C; ⇔ − f (x, y) − f (y, x) ≥ γkx − yk2 , ∀x, y ∈ C; ⇔ f (x, y) + f (y, x) ≤ −γkx − yk2 , ∀x, y ∈ C; Vậy f là song hàm đơn điệu mạnh trên C với hệ số γ > 0. Nếu toán tử F là đơn điệu trên C, khi đó hF(x) − F(y), x − yi ≥ 0, ∀x, y ∈ C; ⇔ hF(x), x − yi − hF(y), x − yi ≥ 0, ∀x, y ∈ C; ⇔ −hF(x), y − xi − hF(y), x − yi ≥ 0, ∀x, y ∈ C; ⇔ − f (x, y) − f (y, x) ≥ 0, ∀x, y ∈ C; ⇔ f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; Vậy f là song hàm đơn điệu trên C. Nếu toán tử F là giả đơn điệu trên C, khi đó nếu hF(x), x − yi ≤ 0 thì hF(y), y − xi ≥ 0, ∀x, y ∈ C; ⇔ −hF(x), y − xi ≤ 0 thì hF(y), y − xi ≥ 0, ∀x, y ∈ C; ⇔ −hF(x), y − xi ≤ 0 thì − hF(y), x − yi ≥ 0, ∀x, y ∈ C; suy ra − f (x, y) ≤ 0 thì − f (y, x) ≥ 0, ∀x, y ∈ C; ⇔ f (x, y) ≥ 0 thì f (y, x) ≤ 0 ∀x, y ∈ C. Vậy f là song hàm giả đơn điệu trên C. Sau đây ta xét một vài trường hợp riêng có thể đưa về bài toán cân bằng. 17
Chương 2. Bài toán cân bằng 2.2 Các trường hợp riêng của bài toán cân bằng 2.2.1 Bài toán tối ưu Cho hàm số ϕ : C → R. Xét bài toán tối ưu Tìm x∗ ∈ C sao cho ϕ(x∗ ) ≤ ϕ(y), ∀y ∈ C. (OP) Đặt f (x, y) := ϕ(y) − ϕ(x). Rõ ràng f (x, x) = ϕ(x) − ϕ(x) = 0. Vậy f là một song hàm cân bằng. Khi đó bài toán tối ưu (OP) tương đương với bài toán Tìm x∗ ∈ C sao cho ϕ(y) − ϕ(x∗ ) ≥ 0, ∀y ∈ C hay Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. Đây chính là bài toán cân bằng. Nhận thấy, tập nghiệm của bài toán tối ưu (OP) chính là S(C, f ). Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (OP), theo định nghĩa ta có ϕ(x∗ ) ≤ ϕ(y), ∀y ∈ C. Suy ra ϕ(y) − ϕ(x∗ ) ≥ 0, ∀y ∈ C. Mặt khác f (x, y) := ϕ(y) − ϕ(x), ∀x, y ∈ C, nên f (x∗ , y) := ϕ(y) − ϕ(x∗ ) ≥ 0, ∀y ∈ C. Vậy x∗ là nghiệm cuả bài toán EP(C, f ). Ngược lại, lấy x∗ ∈ C là nghiệm của bài toán EP(C, f ). Khi đó f (x∗ , y) ≥ 0 với mọi y ∈ C. Theo cách đặt ta có f (x∗ , y) := ϕ(y) − ϕ(x∗ ) ≥ 0, ∀y ∈ C. Suy ra ϕ(y) ≥ ϕ(x∗ ), ∀y ∈ C. Vậy x∗ là nghiệm của bài toán (OP). 18