Luận văn Thạc sĩ Toán học: Bài toán cân bằng với song hàm giả đơn điệu mạnh

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

Thêm vào BST

Báo xấu

47
lượt xem 6
download

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

Luận văn nghiên cứu bài toán cân bằng với song hàm giả đơn điệu mạnh. Cụ thể luận văn đề cập tới sự tồn tại nghiệm của bài toán cân bằng giả đơn điệu mạnh, hơn nữa luận văn còn giới thiệu một số thuật toán để giải bài toán đơn điệu mạnh. Cuối cùng giới thiệu một mô hình sản xuất điện.

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ĩ Toán học: Bài toán cân bằng với song hàm giả đơn điệu mạnh

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ MINH HIẾU BÀI TOÁN CÂN BẰNG VỚI SONG HÀM GIẢ ĐƠN ĐIỆU MẠNH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ MINH HIẾU BÀI TOÁN CÂN BẰNG VỚI SONG HÀM GIẢ ĐƠN ĐIỆU MẠNH Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS. TSKH. LÊ DŨNG MƯU Thái Nguyên - 2015
i Mục lục Lời cảm ơn iii Danh sách ký hiệu iv Mở đầu 1 1 Bài toán cân bằng 2 1.1 Bài toán cân bằng và các trường hợp riêng . . . . . . . . . . . 2 1.1.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Bài toán điểm bất động Brouwer . . . . . . . . . . . . 3 1.1.3 Bài toán bất đẳng thức biến phân tổng quát . . . . . . . 4 1.1.4 Bài toán cân bằng Nash . . . . . . . . . . . . . . . . . 5 1.2 Định nghĩa về tính đơn điệu, giả đơn điệu mạnh của song hàm . 7 1.3 Sự tồn tại nghiệm của bài toán cân bằng . . . . . . . . . . . . . 9 2 Thuật toán chiếu giải bài toán cân bằng giả đơn điệu mạnh 13 2.1 Thuật toán chiếu cho bài toán cân bằng giả đơn điệu mạnh . . 13 2.2 Các thuật toán và tốc độ hội tụ của chúng . . . . . . . . . . . 17 2.2.1 Thuật toán hội tụ tuyến tính . . . . . . . . . . . . . . . 17 2.2.2 Thuật toán không cần biết các hằng số Lipschitz . . . . 23 2.2.3 Thuật toán không có điều kiện Lipschitz . . . . . . . . 25
ii 2.3 Ví dụ áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Kết luận và Đề nghị 33 Tài liệu tham khảo 34
iii Lời cảm ơn Luận văn này được thực hiện và hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên. Em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy GS. TSKH Lê Dũng Mưu (Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam), người đã trực tiếp hướng dẫn tận tình và động viên em trong suốt thời gian nghiên cứu và viết luận văn vừa qua. Tôi cũng xin gửi lời cảm ơn chân thành và sâu sắc tới các thầy, cô trong khoa Toán - Tin, Trường Đại học Khoa học - Đại học Thái Nguyên đã giảng dạy và giúp đỡ tác giả trong suốt quá trình học tập tại trường. Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành viên trong lớp cao học Toán ứng dụng K7A đã luôn quan tâm, động viên, giúp đỡ tôi trong thời gian học tập và quá trình làm luận văn. 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ế, rất mong nhận được sự đóng góp quý báu của quý thầy, cô cùng toàn thể bạn đọc. NGUYỄN THỊ MINH HIẾU Học viên Cao học Toán K7A, Trường Đại học Khoa học - Đại học Thái Nguyên
iv Danh sách ký hiệu Trong toàn luận văn, ta dùng những ký hiệu với các ý nghĩa xác định dưới đây: N tập số tự nhiên R tập hợp các số thực H không gian Hilbert ha, bi tích vô hướng của vectơ a và b ∂f (x) dưới vi phân của hàm f tại x PC (x) hình chiếu (theo chuẩn) của x lên tập C
1 Mở đầu Bài toán cân bằng hay còn gọi là bất đẳng thức Ky Fan là một đề tài hiện nay đang được quan tâm nghiên cứu, do bài toán này có nhiều ứng dụng trong các lĩnh vực khác nhau. Hơn nữa nhiều bài toán quan trọng như bài toán tối ưu, bất đẳng thức biến phân, điểm bất động Brouwer, bài toán cân bằng Nash trong trò chơi không hợp tác đều có thể mô tả dưới bài toán cân bằng. Một trong những hướng nghiên cứu được quan tâm nhiều là các phương pháp giải thông thường. Để xây dựng được các phương pháp giải, người ta phải có những điều kiện đặt lên song hàm của bài toán, một điều kiện thường được sử dụng là tính đơn điệu của song hàm. Bản luận văn này nhằm mục đích tổng hợp những kiến thức cơ bản nhất về bài toán cân bằng. Luận văn nghiên cứu bài toán cân bằng với song hàm giả đơn điệu mạnh. Cụ thể luận văn đề cập tới sự tồn tại nghiệm của bài toán cân bằng giả đơn điệu mạnh, hơn nữa luận văn còn giới thiệu một số thuuật toán để giải bài toán đơn điệu mạnh. Cuối cùng giới thiệu một mô hình sản xuất điện. Thái Nguyên, tháng 05 năm 2015 Nguyễn Thị Minh Hiếu Học viên Cao học Toán K7A Chuyên ngành Toán ứng dụng Trường Đại học Khoa học - Đại học Thái Nguyên Email: ntmhieu.gv08@tuyenquang.edu.vn
2 Chương 1 Bài toán cân bằng Trong chương này chúng ta giới thiệu bài toán cân bằng và trình bày một số trường hợp riêng điển hình của bài toán này. Tiếp đến ta khảo sát một số tính chất của đơn điệu, đặc biệt là song hàm giả đơn điệu mạnh. Cuối chương xét đến sự tồn tại duy nhất nghiệm của bài toán cân bằng với song hàm giả đơn điệu mạnh. Các kết quả của chương này được tổng hợp từ các tài liệu [1], [2], [3], [4], [5], [6], [7]. 1.1 Bài toán cân bằng và các trường hợp riêng Cho H là không gian Hilbert thực với Tôpô yếu được xác định bởi tích vô hướng h.i ứng với chuẩn k.k. Giả sử C là tập lồi đóng khác rỗng trong không gian Hilbert H và một song hàm f : C × C → R thỏa mãn f (x, x) = 0 với mọi x ∈ C . Một hàm f như vậy gọi là song hàm cân bằng. Chúng ta xét bài toán cân bằng được định nghĩa như sau: Tìm x∗ ∈ C sao cho f (x∗ , x) ≥ 0, ∀x ∈ C. (EP) Bài toán này lần đầu tiên được đưa ra vào năm 1955 bởi H. Nikaido, K. Isoda nhằm tổng quát hóa bài toán cân bằng Nash trong trò chơi không hợp tác và vào năm 1972, được Ky Fan giới thiệu năm 1972 và thường được gọi là bất
3 đẳng thức Ky Fan. Bài toán (EP ) còn được đặt tên là bài toán cân bằng bởi tác giả L. D Muu và W. Oettli năm 1992, E. Blum và W. Oettli giới thiệu năm 1994; Bài toán cân bằng (EP ) bao gồm một số bài toán như: bài toán tối ưu hóa, điểm yên ngựa, bất đẳng thức biến phân, điểm bất động và mô hình cân bằng Nash trong lý thuyết trò chơi không hợp tác v.v... 1.1.1 Bài toán tối ưu Xét bài toán min {ϕ (x) : x ∈ C}. Đặt f (x, y) = ϕ (y) − ϕ (x). Khi đó ϕ (x) ≤ ϕ(y), ∀y ∈ C ⇔ f (x, y) ≥ 0, ∀y ∈ C Vậy bài toán tối ưu trên là một trường hợp riêng của bài toán (EP ). 1.1.2 Bài toán điểm bất động Brouwer Giả sử C ⊂ H là một tập lồi compact khác rỗng và ánh xạ đơn trị F : C → C . Khi đó bài toán điểm bất động có dạng sau: Tìm x∗ ∈ C sao cho x∗ = F (x∗ ). (FP) Đặt f (x, y) = hx − F (x), y − xi , ∀x, y ∈ C. Khi đó bài toán (F P ) trở thành bài toán cân bằng (EP ).
4 Tổng quát hơn, bài toán điểm bất động của ánh xạ đa trị (M F P ) là bài toán: Tìm x∗ ∈ C sao cho x∗ ∈ F (x∗ ), với F : C → 2C là ánh xạ đa trị có giá trị lồi compact khác rỗng. Khi đó, x∗ ∈ C là nghiệm của bài toán (M F P ) khi và chỉ khi x∗ là nghiệm của bài toán cân bằng (EP ). 1.1.3 Bài toán bất đẳng thức biến phân tổng quát n Cho T : C → 2R là ánh xạ nửa liên tục sao cho T (x) là tập compact, lồi ∀x ∈ C . Khi đó, bài toán bất đẳng thức biến phân tổng quát được phát biểu như sau: Tìm x∗ ∈ C, ξ ∗ ∈ T (x) sao cho hξ ∗ , y − xi ≥ 0, ∀y ∈ C. (1.1) Nếu ta đặt f (x, y) := max hξ, y − xi , ∀x, y ∈ C ξ∈T (x) thì bài toán cân bằng (EP ) tương đương với bài toán bất đẳng thức biến phân tổng quát. Thật vậy, vì x∗ ∈ C là nghiệm của bài toán (1.1) nên ta có: hξ ∗ , y − x∗ i ≥ 0, ∀y ∈ C, ξ ∗ ∈ T (x∗ ). Mặt khác theo cách đặt ta được: f (x∗ , y) = ∗max∗ hξ ∗ , y − x∗ i ≥ 0, ∀y ∈ C. ξ ∈T (x ) Vậy x∗ ∈ C là nghiệm của bài toán (EP ). Ngược lại, cho x∗ ∈ C là nghiệm của bài toán (EP ), nghĩa là
5 f (x∗ , y) ≥ 0, ∀y ∈ C. Theo cách đặt ta có: f (x∗ , y) = ∗max∗ hξ ∗ , y − x∗ i ≥ 0, ∀y ∈ C. ξ ∈T (x ) Vậy x∗ ∈ C là nghiệm của bài toán (1.1). Nếu T là ánh xạ đơn trị thì bài toán bất đẳng thức biến phân tổng quát là bài toán bất đẳng thức biến phân sau: Tìm x∗ ∈ C sao cho hT (x∗ ) , y − x∗ i ≥ 0, ∀y ∈ C. (1.2) Nếu ta đặt f (x, y) := hT (x), y − xi , ∀x, y ∈ C thì với cách lập luận tương như trên bài toán (1.2) tương đương với bài toán cân bằng (EP ). 1.1.4 Bài toán cân bằng Nash (i) Cho I = {1, 2, ..., p} là tập chỉ số hữu hạn (tập p-người chơi); (ii) Ki là tập lồi khác rỗng của Rni (tập chiến lược của người chơi thứ i); (iii) Hàm fi : K1 × .... × Kp → R cho trước (hàm tổn thất của người chơi thứ i khi vi phạm, chiến lược của người chơi ∀i ∈ I ). Cho x = (x1 , x2 , ..., xp ) ∈ K1 × .... × Kp và y = (y1 , y2 , ..., yp ) ∈ K1 × .... × Kp . Ta định nghĩa vectơ x [yi ] ∈ K1 × .... × Kp như sau:  xj ∀j 6= i  x [yi ]j =  y ∀j = i  j đặt K = K1 × .... × Kp . Khi đó, bài toán cân bằng Nash được phát biểu như sau: Tìm x∗ ∈ K sao cho fi (x∗ ) ≤ fi (x∗ [yj ]) , ∀i ∈ I, ∀y ∈ K (1.3)
6 Điểm thỏa mãn (1.3) gọi là điểm cân bằng Nash. Về ý nghĩa kinh tế, điểm cân bằng Nash nói lên rằng bất kỳ đối thủ nào chọn phương án ra khỏi điểm cân bằng trong khi các đối thủ còn lại vẫn giữ phương án điểm cân bằng thì đối thủ ra khỏi điểm cân bằng sẽ bị thua thiệt. Nếu ta đặt f : K × K → R là hàm số xác định bởi p P f (x, y) := (fi (x [yi ]) − fi (x)) i=1 với mọi ∀x, y ∈ K , thì bài toán cân bằng Nash (1.3) tương đương với bài toán cân bằng (EP). Thật vậy, giả sử x∗ ∈ K là nghiệm của bài toán cân bằng (1.3), khi đó fi (x∗ ) ≤ fi (x∗ [yi ]) , ∀i ∈ I, ∀yi ∈ Ki ⇔ fi (x∗ [yi ]) −fi (x∗ ) ≥ 0, ∀i ∈ I, ∀yi ∈ Ki p (fi (x∗ [yi ]) −fi (x∗ )) ≥ 0, ∀y ∈ K. P ⇔ i=1 Theo định nghĩa của f , ta có f (x∗ , y) ≥ 0, ∀y ∈ K. Vậy x∗ ∈ K là nghiệm của (EP) Ngược lại, giả sử x∗ ∈ K là nghiệm của (EP) nhưng không là nghiệm của (1.3). Khi đó, ta có: f (x∗ , y) ≥ 0, ∀y ∈ K. Theo định nghĩa của f , ta có: n (fi (x∗ [yi ]) −fi (x∗ )) ≥ 0, ∀y ∈ K. P i=1 Vì x∗ ∈ K không là nghiệm của (1.3), nên tồn tại i0 ∈ I sao cho
7 fi0 (x∗ ) > fi0 (x∗ [yi ]) , ∀yi ∈ Ki . Lấy x∗ [yi ] = x∗ , ∀j 6= i0 , ta có fi0 (x∗ ) = fi0 (x∗ [yi ]) , ∀j 6= i0 . Kết hợp với hai điều kiện trên ta suy ra rằng n (fi (x∗ [yi ]) −fi (x∗ )) < 0, ∀y ∈ K. P i=1 Điều này mâu thuẫn với giả thiết. Vậy x∗ ∈ K là nghiệm của bài toán (1.3). 1.2 Định nghĩa về tính đơn điệu, giả đơn điệu mạnh của song hàm Ta ký hiệu PC - toán tử chiếu theo chuẩn lên tập C lồi đóng, tức là: PC (x) ∈ C : kx − PC (x)k ≤ kx − yk , ∀y ∈ C. Bổ đề 1.1. Giả sử C là một tập lồi đóng khác rỗng trong H. (i) PC (x) là duy nhất và được xác định với mọi x; (ii) π=PC (x) khi và chỉ khi hx − π, y − πi ≤ 0, ∀y ∈ C; (iii) kPC (x) − PC (y)k2 ≤ kx − yk2 − kPC (x) − x + y − PC (y)k2 , ∀x, y ∈ C. Định nghĩa 1.1. Một song hàm f : C × C → R được gọi là (i) Đơn điệu mạnh trên C với hệ số β > 0 nếu f (x, y) + f (y, x) ≤ −βky − xk2 , ∀x, y ∈ C; (ii) Đơn điệu trên C nếu
8 f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; (iii) Giả đơn điệu mạnh trên C với hệ số β > 0 nếu f (x, y) ≥ 0 ⇒ f (y, x) ≤ −βky − xk2 , ∀x, y ∈ C; (iv) Giả đơn điệu trên C nếu f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C. Chú ý rằng một song hàm giả đơn điệu mạnh có thể không đơn điệu Từ định nghĩa cho thấy (i) ⇒ (ii) ⇒ (iv) và (i) ⇒ (iii) ⇒ (iv) nhưng không có sự liên hệ giữa (ii) và (iii). Ngoài ra, nếu f là đơn điệu mạnh (tương ứng giả đơn điệu) với hệ số β > 0, thì nó là đơn điệu mạnh (tương ứng giả đơn điệu) với hệ số β 0 cho mọi 0 < β 0 ≤ β Sau đây là một ví dụ cho song hàm giả đơn điệu mạnh. Giả sử f (x, y) := (R − kxk) g (x, y) , Br := {x ∈ H : kxk ≤ r} , khi g là một đơn điệu mạnh trên Br với hệ số β > 0, ví dụ g (x, y) = hx, y − xi , và R > r > 0. Ta thấy rằng f là giả đơn điệu mạnh trên Br . Thực vậy, giả sử rằng f (x, y) ≥ 0, từ x ∈ Br ta có g (x, y) ≥ 0. Với hàm g , β - đơn điệu mạnh trên Br , g (x, y) ≤ −βkx − yk2 , ∀x, y ∈ Cr . Từ định nghĩa của f và y ∈ Br kéo theo f (y, x) = (R − kyk) g (y, x) ≤ −β (R − kyk) kx − yk2 ≤ −β (R − r) kx − yk2 . Vì vậy f là đơn điệu mạnh trên Br với hệ số β (R − r) . Giả thiết sau đây sẽ được sử dụng cho song hàm f : C × C → R (A1) f (., y) là nửa liên tục trên C cho mỗi y ∈ C;
9 (A2) f (x, .) là đóng, lồi và dưới khả vi trên C cho mỗi x ∈ C; (A2a) f (x, .) là đóng, lồi trên C cho mỗi x ∈ C. Điều kiện kiểu Lipschitz sau đây sẽ được sử dụng ở phần tiếp theo. ∃L1 , L2 : f (x, y) + f (y, z) ≥ f (x, z) − L1 kx − yk2 − − L2 ky − zk2 , ∀x, y, z ∈ C. (1.4) Rõ ràng với bài toán cực tiểu minx∈cϕ(x) , song hàm f (x, y) := ϕ (y) − ϕ (x) có tính chất (1.4) với hàm ϕ bất kỳ được định nghĩa trên C . Với F : C → H, cho bất đẳng thức biến phân f (x, y) := hF (x) , y − xi nếu F là Lipschitz trên C với hằng số L > 0, thì cho một số bất kỳ µ > 0 ta có f (x, y) + f (y, z) ≥ f (x, z) − Lµ 2 kx − yk2 − 2µ L ky − zk2 , ∀x, y, z ∈ C, Lµ f thỏa mãn điều kiện Lipschitz với L1 = 2 và L2 = L 2µ . 1.3 Sự tồn tại nghiệm của bài toán cân bằng Bổ đề 1.2. Giả sử f : C × C → R ∪ {∞} là một song hàm cân bằng sao cho f (., y) là bán liên tục trên với mỗi y ∈ C và f (x, .) là lồi với mọi x ∈ C . Nếu ít nhất một trong những giả thiết dưới đây thỏa mãn: (i) C là compact; (ii) Tồn tại một tập hợp W compact khác rỗng sao cho mỗi x ∈ C\W có một y ∈ C ∩ W với f (x, y) < 0; thì bài toán cân bằng (EP) có một nghiệm.
10 Trong những kết quả dưới đây, chúng ta cần các điều kiện về song hàm f : (A1 ) với mỗi x ∈ C, y ∈ C , hàm f (x, .) lồi chính thường (không nhất thiết khả dưới vi phân) và hàm f (., y) là nửa liên tục trên C . (A2 ) f là β - giả đơn điệu mạnh trên C . Kết quả sau đây nói về sự tồn tại nghiệm của bài toán cân bằng giả đơn điệu mạnh. Định lí 1.1. Giả sử rằng f là giả đơn điệu mạnh trên C , khi đó dưới giả thiết (A1 ), (A2 ) bài toán (EP ) có một nghiệm duy nhất. Chứng minh. Theo Bổ đề 1.2 ta chỉ cần chứng minh điều kiện bức sau đây: Tồn tại hình cầu đóng B sao cho: (∀x ∈ C\B, ∃y ∈ C ∩ B : f (x, y) < 0). (C0) Thực vậy, nếu trái lại, với mọi hình cầu đóng Br bao O với bán kính r, có xr ∈ C\Br sao cho f (x, y) ≥ 0, ∀y ∈ C ∩ Br . Cố định r0 > 0, thì với mọi r > r0 , có tồn tại xr ∈ C\Br sao cho f xr , y 0 ≥ 0 với y 0 ∈ C ∩ Br . Do đó, từ f là β - giả đơn điệu mạnh, chúng ta có: 2 f y 0 , xr + β xr − y 0 ≤ 0, ∀r (1.5) Mặt khác, do f y 0 , . là lồi chính thường, tồn tại x0 ∈ C sao cho ∂2 f y 0 , x0 6= φ, tại x0 . Lấy w∗ ∈ ∂2 f y 0 , x0 , theo định nghĩa của dưới vi phân ta có: ∗ w , x − x0 + f y 0 , x0 ≤ f y 0 , x , ∀x.
11 Với x = xr ta được: f (y 0 , xr ) + βkxr − y 0 k2 ≥ f (y 0 , x0 ) + w∗ , xr − x0 + βkxr − y 0 k2 ≥ f (y 0 , x0 ) − kw∗ kkxr − x0 | + βkxr − y 0 k2 . 2 Do r → ∞, từ kxr k → ∞, ta thu được f y 0 , xr + β xr − y 0 → ∞, mâu thuẫn với (1.5). Vì vậy điều kiện bức (C0) phải đúng. Theo Bổ đề 1.2, bài toán (EP ) có nghiệm. Toán tử F : C → H là được gọi là giả đơn điệu mạnh trên C với hệ số β > 0, nếu: hF (x) , y − xi ≥ 0 ⇒ hF (y) , y − xi ≥ βky − xk2 , ∀x, y ∈ C. Ta áp dụng định lý trên với bất đẳng thức biến phân Tìm x∗ ∈ C : hF (x∗ ) , y − x∗ i ≥ 0 , ∀y ∈ C, (VI) Định nghĩa song hàm f theo công thức f (x, y) := hF (x), y − xi (1.6) Rõ ràng x∗ là một nghiệm của (1.6) khi và chỉ khi nó là một nghiệm của bài toán (EP) với f xác định bởi (1.6). Khi đó f là giả đơn điệu mạnh nếu F là giả đơn điệu mạnh. Thật vậy, giả sử f (x, y) ≥ 0 theo (1.6), ta có hF (x) , y − xi ≥ 0 nhưng do F là β− đơn điệu mạnh nên hF (y) , x − yi ≤ −βky − xk2 Theo (1.6) thì f (x, y) = hF (y) , x − yi .
12 Hệ quả 1.1. Giả sử rằng F là liên tục và giả đơn điệu mạnh trên C. Khi đó bài toán bất đẳng thức biến phân (VI) có một nghiệm duy nhất.
13 Chương 2 Thuật toán chiếu giải bài toán cân bằng giả đơn điệu mạnh Trong chương này chúng ta trình bày thuật toán chiếu cho bài toán cân bằng giả đơn điệu mạnh, đặc biệt là ba thuật toán và tốc độ hội tụ của chúng: Thuật toán 1: Thuật toán tuyến tính hội tụ yêu cầu biết được hệ số Lipschitz của song hàm. Thuật toán 2: Thuật toán không cần biết hằng số Lipschitz. Thuật toán 3: Thuật toán không có điều kiện Lipschitz. Các kiến thức trong chương này chủ yếu được tham khảo ở trong các tài liệu [3], [4], [6], [7]. 2.1 Thuật toán chiếu cho bài toán cân bằng giả đơn điệu mạnh Cho ε ≥ 0, chúng ta gọi một điểm xε ∈ C một ε - nghiệm tới bài toán (EP). Nếu f (xε , y) ≥ −ε cho mọi y ∈ C . Bổ đề sau sẽ được sử dụng trong phần chứng minh của định lý hội tụ dưới đây. Bổ đề 2.1. Giả sử rằng {ak }∞ k=0 là một dãy vô hạn các số dương thỏa mãn: ak+1 ≤ ak + ξk ∀k,
14 P∞ với k=0 ξk < ∞. Khi đó dãy {ak } là hội tụ. Thuật toán Bước 1. (Chọn một điểm xuất phát và độ dài bước). Lấy x1 ∈ C , chọn sai số ε > 0 và một dãy các số dương {σk } sao cho ∞ X ∞ X σk = ∞, σk2 < +∞. (2.1) k=1 k=1 Bước 2. (Tìm một hướng chuyển động) Tìm g k ∈ H sao cho f xk , y + g k , xk − y ≥ −σk , ∀y ∈ C. (2.2) a) Nếu g k = 0 và σk ≤ ε, kết thúc: xk là 1 ε - nghiệm; b) Chuyển qua bước 3. Bước 3. (Phép chiếu) Lấy xk+1 := PC xk − σk g k và quay trở lại Bước 2 với k được thay bởi k + 1. Định lí 2.1. Giả sử rằng giả thiết (A1 ) và (A2 ) là thỏa mãn. Khi đó ta có: (i) Nếu thuật toán kết thúc ở Bước 2, thì xk là một ε - nghiệm và 2 2 2 − x∗ ≤ (1 − 2βσk ) xk − x∗ + 2σk2 + σk2 g k , ∀k; (2.3) k+1 x (ii) Nếu thuật toán không kết thúc và g k giới nội thì dãy xk hội tụ mạnh tới nghiệm duy nhất x∗ của (EP ). Chứng minh. (i) Nếu thuật toán kết thúc ở Bước 2, thì g k = 0 và σk ≤ ε. Khi đó, từ (2.2), f xk , y ≥ −σk ≥ −ε với ∀y ∈ C . Như vậy, xk là một ε - nghiệm. Từ xk+1 = PC xk − σk g k , ta có 2 2 − x∗ ≤ xk − σk g k − x∗ k+1 x