Bộ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC sư PHẠM HÀ NỘI 2 • ••• NGUYỄN THỊ LANH PHƯƠNG PHÁP GRADIENT CẢI BIÊN KÉO DÀI GIẢI BÀI TOÁN BẤT ĐẲNG THỨC BIỂN PHÂN Chuyên ngành: Toán giải tích Mã số: 60 46 01 02 LUẬN VĂN THẠC sĩ TOÁN HỌC • •• Người hướng dẫn khoa học: GS. TSKH. NGUYỄN XUÂN TẤN HÀ NỘI, 2015 LỜI CẢM ƠN Trước khi trình bày nội dung chính của luận văn tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy GS. TSKH. Nguyễn Xuân Tấn người đã tận tình hướng dẫn tôi toong thời gian qua để tôi hoàn thành luận văn này. Tôi cũng xin cảm ơn các thầy cô giáo trong khoa Toán và phòng Sau đại học Trường đại học sư phạm Hà Nội 2 đã dạy bảo tôi tận tình trong suốt quá trình học tập tại trường. Nhân dịp này tôi cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên tôi, cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và hoàn thả nh luận văn cao học. Hà Nội, tháng 6 năm 2015 Học viên Nguyễn Thị Lanh LỜI CAM ĐOAN Luận văn của tôi được hoàn thảnh dưới sự hướng dẫn của thầy GS. TSKH. Nguyễn Xuân Tấn cùng với sự cố gắng của bản thân tôi. Trong quá trình thực hiện tôi có tham khảo một số tài liệu (như đã nêu trong mục tài liệu tham khảo) Tôi xin cam đoan những nội dung trình bày trong luận văn là kết quả của quá trình tìm hiểu, tham khảo và học tập của bản thân, không trùng lặp với kết quả của các tác giả khác. Hà Nội, tháng 6 năm 2015 Học viễn Nguyễn Thị Lanh LỜI CẢM ƠN Mục lục Danh mục kí hiệu 3 Mở đầu 4 1 Kiến thức cơ bản 7 1.1 Bất đẳng thức biến phân và bài toán bù....................................... 7 1.2 Toán tử đơn điệu và đơn điệu tổng quát...................................... 9 1.3 Phép chiếu metric......................................................................... 11 1.4 Phương pháp chỉnh hóa Tikhonov............................................... 14 1.5 Thuật toán điểm gần kề................................................................ 15 1.6 Phương pháp gradient kéo dài...................................................... 17 2 Phương pháp gradient cải biên kéo dài 19 2.1 Đặt bài toán.................................................................................. 19 2.2 Thuật toán ................................................................................... 19 2.3 Sự hội tụ của dãy lặp.................................................................... 20 2.3.1 Sự hội tụ mạnhdưới tính giả đơn điệu............................. 20 2.3.2 Cận đúng cho điểm cuối................................................ 28 2.3.3 Sự hội tụ yếu dưới tính đơn điệu ................................. 30 2.4 Tốc độ hội tụ của dãy lặp............................................................. 34 2.4.1 Tốc độ hội tụ R - tuyến tính ..................................... 35 LỜI CAM ĐOAN 2.4.2 Tốc độ hội tụ Q - tuyến tính ..................................... 45 3 Phương pháp gradient kéo dài mới 49 3.1 Đặt bài toán.............................................................................. 49 3.2 Thuật toán .................................................................................. 49 3.3 Sự hội tụ của dãy lặp................................................................... 50 3.4 Phân tích sâu hơn........................................................................ 55 Kết luận 60 Tài liệu tham khảo 61 Danh mục kí hiệu N: tập số tự nhiên R: tập số thực C: tập số phức G, Ệ'. thuộc, không thuộc của một phần tử đối với tập hợp 0, C: tập rỗng, tập con H: không gian Hilbert thực /2: không gian các dãy bình phương khả tổng không gian Euclide n chiều M™: ortang không âm trong Mn Rnxm: không gian các ma trận cấp n X m {xfc}: dãy các phần tử X 1 , X 2 , X 3 , . . . ||a;||: chuẩn của véctơ X (X , y ): tích vô hướng của véctơ X và y n, x: giao, tích Decart F : u —>■ V: ánh xạ từ u vào V B (u, r): hình cầu mở tâm u, bán kính r B (u, r): hình cầu đóng tâm u, bán kính r LỜI CẢM ƠN VI (K, F): bất đẳng thức biến phân xác định bởi tập K và ánh xạ F CP (K, F): bài toán bù xác định bởi nón K và ánh xạ F LCP (M, q): bài toán bù tuyến tính xác định bởi ma trận M và véctơ q Soỉ {K, F): tập nghiệm của VI (K, F) và CP (K, F) Sol (K, q): tập nghiệm của LCP (M, q) MỞ ĐẦU 1. Lý do chọn đề tài Bất đẳng thức biến phân và bài toán điểm cân bằng đóng vai trò rất quan trọng vì có nhiều ứng dụng trong thực tế. Khái niệm toán tử đơn điệu được đưa LỜI CAM ĐOAN ra từ đầu những năm 1960. P.Hartman và Stampac- chia đã nghiên cứu bất đẳng thức biến phân với toán tử đơn điệu một cách độc lập. Bất đẳng thức biến phân đơn điệu được sử dụng trong nghiên cứu phương trình vi phân đạo hàm riêng của các loại phương trình elliptic, parabolic và nhiều bài toán tối ưu, lí thuyết cân bằng. Chúng trở thành một công cụ hữu hiệu cho việc giải các bài toán và xử lý tính toán cho nhiều bài toán. Cho đến nay, bất đẳng thức biến phân đơn điệu vẫn là chủ đề được quan tâm của nhiều nhà nghiên cứu. Phương pháp tìm nghiệm khác nhau đã được đề xuất cho bất đẳng thức biến phân đơn điệu: phương pháp chiếu metric, phương pháp chỉnh hóa Tikhonov, phương pháp điểm gần kề, phương pháp gradient kéo dài,.... Phương pháp gradient cải biên kéo dài có hai phương pháp chiếu liên tiếp cho từng bước một. Nó lấy tên từ sự đánh giá kéo dài của trường véctơ trong bất đẳng thức biến phân và phép chiếu kéo dài, bắt nguồn từ trường hợp của bất đẳng thức biến phân đối xứng. Trong trường hợp đó, bất đẳng thức biến phân biểu diễn điều kiện tối ưu của một bài toán tối ưu trơn và sự đánh giá thêm của trường véctơ tương ứng với giá trị kéo dài của gradient của hàm mục tiêu (cho nên tính từ gradient kéo dài được sử dụng). Mặc dù điều này chắc chắn đòi hỏi một lượng tính toán gấp đôi tại mỗi lần lặp, nhưng lợi ích là đáng kể vì thuật toán thu được được sử dụng cho những lớp bài toán bất đẳng thức biến phân giả đơn điệu. Để đảm bảo sự hội tụ của phương pháp gradient cải biên kéo dài, người ta phải giả thiết trường véctơ là liên tục Lipschitz và ước tính hằng số Lipschitz của nó phải được đưa ra một cách tường minh. Mục tiêu của luận văn này là vận dụng các thuật toán để giải bất đẳng thức biến phân không đơn điệu. Để làm điều này, chúng ta nghiên cứu phạm vi của các ứng dụng của phương pháp gradient cải biên kéo dài, thuật toán của nó để đề xuất LỜI CẢM ƠN sửa đổi hợp lý để có được kết quả tốt hơn về sự hội tụ và tốc độ hội tụ của dãy lặp. Với mong muốn tìm hiểu sâu về vấn đề này, cùng sự giúp đỡ tận tình của thầy GS. TSKH. Nguyễn Xuân Tấn, tôi đã chọn nghiên cứu đề tài: “Phương pháp gradient cải biên kéo dài giải bài toán bất đẳng thức biến phân”. 2. Cấu trúc của luận văn Luận văn này gồm 3 chương: Chương 1: Kiến thức cơ bản Chương 2: Phương pháp gradient cải biên kéo dài Chương 3: Phương pháp gradient kéo dài mới 3. Mục đích nghiên cứu Tìm hiểu về phương pháp gradient cải biên kéo dài giải bất đẳng thức biến phân giả đơn điệu trong không gian Hilbert. Sự hội tụ và tốc độ hội tụ của dãy lặp sinh bởi phương pháp này được bảo đảm. 4. Nhiệm vụ nghiên cứu Tìm đọc các tài liệu liên quan đến bất đẳng thức biến phân và thuật toán giải. Trình bày các khái niệm và các kết quả có liên quan đến bất đẳng thức biến phân. Giới thiệu phương pháp gradient cải biên kéo dài giải bài toán bất đẳng thức biến phân. 5. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu: phương pháp gradient cải biên kéo dài cho bất đẳng thức biến phân và các vấn đề liên quan. LỜI CAM ĐOAN Phạm vi nghiên cứu: Các bài báo, các cuốn sách và các tài liệu có liên quan đến phương pháp gradient cải biên kéo dài giải bài toán bất đẳng thức biến phân. 6. Phương pháp nghiên cứu Sử dụng kiến thức cơ bản của giải tích hàm, lý thuyết tối ưu để làm công cụ cho việc xây dựng thuật toán giải bài toán bất đẳng thức biến phân. 7. Dự kiến đóng góp mới Đưa ra một tổng quan về phương pháp giải bất đẳng thức biến phân thông qua phép chiếu biến dạng. Chương 1 Kiến thức cơ bản 1.1 Bất đẳng thức biến phân và bài toán bù Trước hết, ta nhắc lại bài toán bất đẳng thức biến phân trong không gian Hilbert. Định nghĩa 1.1. Cho K là tập con khác rỗng của không gian Hilbert (H, (.,.)) và F : K —>■ H là ánh xạ đơn trị. Bất đẳng thức biến phân được định nghĩa bởi K và F, kí hiệu là VI (K, F), là bài toán: Tìm véctơ u* e K sao cho (F{u*),u- u*) > 0, VueK. (1.1) u* được gọi là nghiệm của VI (K, F). Tập tất cả nghiệm của nó được kí hiệu là Sol (K, F). Để không phải nhắc lại nhiều lần, ta luôn giả thiết K là tập lồi, đóng và F là LỜI CẢM ƠN ánh xạ liên tục. Khi K là một nón, nghĩa là nếu u E K thì TU E K với mọi r > 0, công thức (1.1) đã được rút gọn và bài toán được biết đến dưới tên là bài toán bù. Định nghĩa 1.2. Bài toán bù được cho bởi nón lồi K và một ánh xạ F : K H. Bài toán: Tìm một véctơ u* € H sao cho u* e K, F (u*) 0, Vu € K} là nón đối ngẫu của K. Bài toán (1.2) được viết tắt là CP (K, F). Nếu u e K và F (u) e K* thì u được gọi là véctơ chấp nhận được của CP (K, F). Nếu bài toán CP (K, F) có một véc tơ chấp nhận được thì nó được cho là có tính chấp nhận được. Khi H = Rn, F là một ánh xạ affin, nghĩa là, F (u) = Mu + q với M e Rmxn, q G Mn và K = (trong trường hợp này K* = M"), CP (K, F) trở thành bài toán bù tuyến tính, kí hiệu là LCP (M, q): lí* > 0, Mu* + q > 0, (Mu* + ợ, u*} = 0. (1.3) ở đây bất đẳng thức trong M" được hiểu là các thành phần không âm được gọi là ortang dương. Tập nghiệm của bài toán được kí hiệu là Sol (M, q). Sự liên hệ chính xác giữa VI(K : F) và CP{K,F) với K là một nón được mô tả như sau. Mệnh đề 1.1. Nếu K là một nón lồi thiu* là một nghiệm của VI (K, F) khi và chỉ khi u* là một nghiệm của CP (K, F). Chứng minh. Nếu u* là nghiệm của VI (K, F) thì u* G K. Trong (1.1) cho lí = 0, ta được (F (u*), u*) < 0. Hơn nữa, khi u = 2u* G K, từ (1.1) ta được (F LỜI CAM ĐOAN (u*) , w*) > 0. Do đó (F (u*) , w*) = 0. Kết hợp với (1.1) có (F (u*) ,u) > 0 Vm g if, do đó F (u*) G K*. Vì vậy, li* là nghiệm của CP (K : F). Ngược lại, u* là nghiệm của CP (K : F) : khi đó dễ thấy u* là nghiệm của VI (K, F). 1.2 Toán tử đơn điệu và đơn điệu tổng quát Việc giải bài toán (1.1) được thuận lợi nếu ánh xạ thỏa mãn một số tính chất: đơn điệu, giả đơn điệu,.... Ta nhắc lại các khái niệm sau. Định nghĩa 1.3. Ánh xạ F : K c H —»• H được gọi là (a) Đơn điệu mạnh nếu 37 > 0 sao cho ( F (lí) — F ( v ), u — v ) > 7ỊỊií — v \ \ 2 , V u , V G K \ (b) Giả đơn điệu mạnh nếu 37 > 0 sao cho (F (u), V — u) > 0 =>■ {F (v) ,v — ù) > 7II u — v\\ 2 , 'in, V ẽ K\ (c) Đơn điệu nếu (F (u) — F (v) ,u — v) >0, Vu,V ẽ K; (1d) Giả đơn điệu nếu (F (u) ,v — u) > 0 (F (v) ,v — u) > 0, Vu, V £ K; (e) Tựa đơn điệu nếu (F (u) ,v — u) > 0 =>■ (F (v) ,v — u) >0, Vm,V £ K. Sự kéo theo (a) =>• (6) =>- (d) =>- (e) và (a) =>- (c) =>- (d) =>• (e) là hiển nhiên. Nhưng điều khẳng định ngược lại nói chung không đúng. Không có mối quan hệ giữa (6) và (c). LỜI CẢM ƠN Mệnh đề sau đây cho biết tính khác rỗng của tập nghiệm và cấu trúc tập nghiệm của bất đẳng thức biến phân. Mệnh đề 1.2. Cho K c H là tập ỉồỉ, đóng và ánh xạ F : K —> H là liên tục. (а) Nếu F là giả đơn điệu mạnh thì VI (K, F) có nhiều nhất một nghiệm. (б) Nếu F là giả đơn điệu thì Sol (K, F) là lồi. Chứng minh. Giả sử F là ánh xạ giả đơn điệu mạnh với môđun 7 > 0 và u*,v* G Sol (K,F). Khi đó (F (V*), u* - V*) > 0 và (F (V*), V* - u*) > 'Yịịu* - V* ||2. Từ bất đẳng thức 0 > 7||u* — v*\\ 2 suy ra u* — V* và khẳng định (a) được chứng minh. Cho F là ánh xạ liên tục và giả đơn điệu. Để chứng minh được (6), ta phải chứng minh Sol (K, F)= Pl K e K : (F (u), u - u*} > 0}. ueK Hiển nhiên, nếu u* G Sol (K, F) thì (F (u*), u — u*) > 0 với mọi u G K. Do tính giả đơn điệu của F nên (F (u) ,u — u*} > 0 \/u £ K, suy ra u* thuộc vế phải của đẳng thức trên. Ngược lại, giả sử u* thuộc tập thứ hai. Cho K là tập lồi bất kì. Vì TU* + (1 — r) u G K với mọi r G (0,1) nên ( F ( T U * + (1 — T ) U ) , u — u * ) >0, Vr € (0,1). Cho T —>• 1 ta được (F (u*), u — u*) > 0. Do vậy, u* G 0} là lồi và giao của các tập lồi là lồi nên Sol (K, F) là lồi. LỜI CAM ĐOAN Trong chứng minh của Mệnh đề 1.2 (6) ta thấy nếu F là liên tục và giả đơn điệu trên một tập lồi, đóng K thì u* € Sol (K, F) khi và chỉ khi (-F (lí) ,u — u*) > 0, Vw ẽ if. Kết quả trên được gọi là bổ đề Minty cho bất đẳng thức biến phân giả đơn điệu. Nó là sự tổng quát của bổ đề Minty cổ điển. 1.3 Phép chiếu metric Để giải bài toán (1.1) ta sử dụng phương pháp chiếu. Nội dung của phương pháp này dựa trên phép chiếu từ mọi điểm của không gian lên tập K. Mệnh đề 1.3. (Xem [11, Chương 1, Bổ đề 2.1]) Cho K c H là tập lồi, đóng, khác rỗng. Khi đó, với mỗi u E H có duy nhất V £ K sao cho \\u-v\\= mị\\u-u)\\. (1.4) ueK Định nghĩa 1.4. Véctơ V thỏa mãn (1.4) là duy nhất và được gọi là phép chiếu metric của u trên K, kí hiệu là P K (u). Ta nhận thấy P K (w) = u với mọi u G K và ||m — P K (w)|| < ||w — I’ll , Vv e K. Định lý tiếp theo đặc trưng cho phép chiếu metric. Định lý 1.1. (Xem [11, Chương 1, Định lý 2.3]) Cho K c H là tập lồi, đóng. Khi đó, V — P K (ù) khi vàchỉ khi V G K và ( u — V , U J — v ) <0, Vcư G K . (1-5) Một số tính chất của phép chiếu metric được tóm tắt trong các hệ quả dưới LỜI CẢM ƠN đây. Hệ quả 1.1. Cho K c H là tập lồi, đóng. (|a) Với bất kì u € H và V € K, ||v - P K (u)||2 < ||u - f ||2 - ||u - P K KHI2. (6) Với bất kì u,v G H, \ \ P K { Ù ) - P K (v)|| < ||w - v|| • Chứng minh. Cho u £ H, V £ K. Ta có llw - ^ll2 = II ( u - P K («)) - ( v - P K (w))||2 = \\u - P K (w)||2 + IIV - P K (w)||2 - 2 (u - P K (u), V - P K (u)). Vì (u — P K { Ù ) , V — P K (u)) < 0 do (1.5) nên \\u - v\\ 2 > IIu - P K (w)|Ị2 + ||v - P K (w)|Ị2. Khẳng định (a) được chứng minh. Cho u,v £ H tùy ý. Từ Định lý 1.1, ta có (P K (u) - P K { V ) , P K { V ) - v) > 0 và (P K (v) - P K (u) , P K (u) - u) > 0. Cộng bất đẳng thức lại với nhau và sắp xếp lại số hạng, ta được (P K (u) - P K (v) , U - v) > IIP K (u) - P K (^)||2- Áp dụng bất đẳng thức Cauchy-Schwarz, IIP K (u) - P K (v)|| II« - u|| > (P K (u) - P K (v) ,u - v) . Do vậy, khẳng định (6) được chứng minh. LỜI CAM ĐOAN Trở lại bài toán VI (K, F), từ Định lý 1.1, ta có thể biểu thị nghiệm của bất đẳng thức qua phép chiếu metric. Hệ quả 1.2. Cho K c H là tập lồi, đóng và ánh xạ F : K —¥ H, u* là nghiệm của VI (K,F) khi và chỉ khi u* = P K (u* - XF (u*)), VA > 0. Chứng minh. Cho A > 0. Từ Định lý 1.1, u* = P K (u* — AF (u*)) khi và chỉ khi u* G K và (u* - XF (u*) - u\ u - u*) < 0, Vmễ K. Điều này tương đương với u* £ K và (F{u*),u-u*) > 0, Vw 0. Để giải VI (K, F), ta giải LỜI CẢM ƠN một dãy các bài toán VI (K, F S k ) với {£*;} là một dãy các số thực dương hội tụ tới 0 và F e k = F + £ k I. Với mỗi k e N, chọn một nghiệm u k ẽ Sol (K,F Sk) và tính giới hạn lim u k . Khi giới hạn tồn tại, k—>00 ta có thể hi vọng thu được nghiệm của VI (K, F). Hoàn thành việc tính toán sau hữu hạn bước và thu được nghiệm gần đúng của VI (K, F), ta đưa ra điều kiện dừng. Ví dụ, ta có thể hoàn thành việc tính toán khi IIu k — u k ~ 1 II < 6 với 6 là một hằng số. Định lý 1.2. (Xem [15, Định lý 2.1]) Cho F : K —¥ H là ánh xạ giả đơn điệu và liên tục trên K. Nếu Sol(K,F ) khác rỗng và ũ là chuẩn nhỏ nhất trong tập nghiệm thì ta có các khẳng định: ('a) Ve > 0, nếu ánh xạ Fe là giả đơn điệu thì tập Sol (K, F£) khác rỗng, (ỏ) Tập Sol (K, F e) với £ > 0 bị chặn đều. Hơn nữa, với mỗi £ > 0; Soi (K,F e ) cbQ«,Ì||b||Ì njrcB(o,||a||)nK-; (c) Bất kì dẫy con của {u (e)} đều hội tụ đến ũ, với {u (e)} là một nghiệm của VI{K,F e ). Nếu H = Mn, định lý trên có thể phát biểu như sau. Định lý 1.3. (Xem [15, Định lý 2.2] và [16]) Cho K c Rn là một tập lồi, đóng, khác rỗng. F : K —»■ Mn là một ánh xạ liên tục, giả đơn điệu. Nếu bài toán VI (K,F) có một nghiệm thì (a) Sol (K, F e) khác rỗng và compact với mọi £ > 0; (b) Dẫy {u (e)} hội tụ tới chuẩn nhỏ nhất trong Sol (K, F) khi £ —»• 0+; với u (e) là một véctơ thuộc Sol (K, F e ); (c) lim diamSoỉ (K, F e ) = 0 với diamíì := sup {IIlí — î;II :u,v £ íĩ} là eịo LỜI CAM ĐOAN đường kính của tập con ri c Mn. 1.5 Thuật toán điểm gần kề Phương pháp chỉnh hóa Tikhonov khả năng tính toán bị hạn chế. Cụ thể là, khi Eỵ 0 làm đảo lộn sự gần đúng của bài toán ban đầu do đó có nhiều khó khăn hơn khi giải thậm chí là không đúng. Thuật toán điểm gần kề (viết tắt là PPA) đã giải quyết những khó khăn như vậy. Thuât toán điểm gần kề cho bài toán VI (K, F) được mô tả như sau. Chọn u ữ ẽ H và {pk} là dãy các số thực dương thỏa mãn điều kiện Pk > p > 0 với mọi k e N. Nếu u k ~ l được xác định, cho u k là nghiệm bất kì của bài toán bổ trợ VI (K, với F ( u ) = p k F (u)+u- u k ~\ U&K, (1.6) và {p k F (u k) +u k - u k -\v- u k ) > 0, Vv € K, u k G K. Giả sử Sol (K, Fkhác rỗng. Nếu sơ đồ lặp có một dãy {u k} thì tính lim u k trong tôpô chuẩn hoặc tôpô yếu của H. Khi giới hạn tồn tại, ta k—>00 CÓ thể hi vọng các phần tử thu được thuộc tập nghiệm của VI (K, F). Hoàn thành việc tính toán sau hữu hạn bước và thu được nghiệm gần đúng của VI(K,F), ta đưa ra điều kiện dừng. Ví dụ, ta có thể hoàn thành việc tính toán khi IIu k — u k ~ 1 ịị < ớ, với ỡ là một hằng số. Định lý 1.4. (Xem [15, Định lý 3.1]) Giả sử ánh xạ F : K H là giả đơn điệu và liên tục trên, Sol (K, F) khác rỗng, u° £ H là một véctơ và {wfc} là một dãy sinh bởi thuật toán điểm gần kề. Khi đó, {wfc} là một dãy bị chặn. Hơn nữa, nếu tồn tại dãy con ịu k j } c {wfc} hội tụ LỜI CẢM ƠN tới ũ e H thì ũ e Sol (K, F) và lim u k = ũ . k—>00 Nếu H = Rn thì định lý hội tụ có thể phát biểu như sau. Định lý 1.5. (Xem [12, Định lý 3.1] và [15, Định lý 3.2]) Giả sử K cl" là tập lồi, đóng, ánh xạ F : K -ỳ- M. n là giả đơn điệu và liên tục trên K. Nếu Sol (K,F) khác rỗng, u° G Rn là một véctơ tùy ý và {u k} là một dãy sinh bởi thuật toán điểm gần kề thì tồn tại u € Sol (K : F) thỏa mãn lim u k — ũ . k-ì 00 1.6 Phương pháp gradient kéo dài Có một phương pháp giải cho VI (K,F) mà thực hiện hai phép chiếu cho mỗi lần lặp đó là phương pháp gradient kéo dài (viết tắt là EGM). Đây là phương pháp lấy tên từ việc mở rộng đánh giá của ánh xạ (và mở rộng phép chiếu) cho mỗi lần lặp. Lợi ích của phương pháp này là có thể sử dụng bất đẳng thức biến phân giả đơn điệu cổ điển một cách hiệu quả. Ánh xạ F đòi hỏi phải liên tục Lipschitz và sự đánh giá hằng số Lipschitz là cần thiết. F : K —»■ H được gọi là L liên tục Lipschitz nếu Il F (u) — F (t>)|| < L \\u — î; II , Vu,v G K. (1-7) Thuật toán 1.1 Dữ liệu: u° G K và a £ (o, ỵ) . Bước 0: Cho k = 0. LỜI CAM ĐOAN Bước 1: Nếu u k = P K (u k — aF (u k)) thì dừng. Bước 2: Tính U = P K (u k - aF ('u k)) , u k + 1 = P K (u k - aF («*)) ; thay k bởi k + 1 và quay lại bước 1. Định lý 1.6. (Xem [1, Định lý 3.1]) Giả sử K là tập lồi, đóng, khác rỗng trong không gian Hilbert H. Ánh xạ F : K —»■ H là đơn điệu và L - liên tục Lipschitz trên K. Giả sử Sol (K, F) khác rỗng và {wfc} ỉà dẫy sinh bởi Thuật toán 1.1. Khỉ đó, tồn tại ũ € Sol (K : F) mà {wfe} hội tụ yếu tới ũ. Định lý 1.7. (Xem [3, Định lý 12.1.11]) Giả sử K c Mn là tập lồi, đóng, khác rỗng. Ánh xạ F : K —>■ Mn là giả đơn điệu và L - liên tục Lipschitz trên K. Nếu Soỉ (K, F) khác rỗng và dãy {wfc} sinh bởi Thuật toán 1.1 thì tồn tại ũ e Sol (K, F) mà {wfc} hội tụ tới ũ. Chương này đã giới thiệu bài toán bất đẳng thức biến phân và trình bày khái niệm cơ bản của bất đẳng thức biến phân liên quan đến ánh xạ giả đơn điệu. Ta nhắc lại bốn phương pháp tìm nghiệm cho bài toán bất đẳng thức biến phân và một số kết quả về sự hội tụ của dãy lặp đến nghiệm của bài toán. LỜI CẢM ƠN Chương 2 Phương pháp gradient cải biên kéo dài 2.1 Đặt bài toán Xét bài toán VI {K,F) được phát biểu trong Định nghĩa 1.1, với K là tập lồi, đóng, khác rỗng của không gian Hilbert H và F thỏa mãn điều kiện Lipschitz (1.7). Hằng số Lipschitz L > 0 . Phương pháp gradient cải biên kéo dài để giải VI (K, F) được mô tả như sau. 2.2 Thuật toán Dữ liệu: u° £ K và {a;fc}£L0 c [a, 6] với 0 < a < b < ỵ. Bước 0: Cho k = 0. Bước 1: Nếu u k = P K ịu k — OiỵF (u k )) thì dừng. Bước 2: Đặt u = P K (u k - a t F («*)) , u t + 1 = P K ịu h - a t F (ũ k ^ , (2.1) thay k bởi k + 1 và quay lại bước 1. Chú ý 2.1. Không giống như phương pháp gradient kéo dài cổ điển của Korpelevich, độ dài bước a k trong mỗi bước lặp của phương pháp gradient cải