Tài liệu Phương pháp hiệu chỉnh cho bài toán bù tổng quát

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ——————————o0o—————————— NGUYỄN THỊ THẮM PHƯƠNG PHÁP HIỆU CHỈNH CHO BÀI TOÁN BÙ TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ——————————o0o—————————— NGUYỄN THỊ THẮM PHƯƠNG PHÁP HIỆU CHỈNH CHO BÀI TOÁN BÙ TỔNG QUÁT 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, 2017 Một số ký hiệu và viết tắt Rn không gian Euclid n-chiều R tập hợp các số thực R+ tập hợp các số thực không âm R++ tập hợp các số thực dương xT chuyển vị của véctơ x {xk } dãy các véctơ x1 , x2 , x3 , ... ||.||Rn chuẩn trong không gian Rn hx, yiRn tích vô hướng của x và y trong Rn  ∇θ ∂θ ∂xj  - gradient của hàm θ : Rn → R AT chuyển vị của ma trận A PC (x) phép chiếu metric phần tử x lên tập đóng lồi C LCP (., .) bài toán bù tuyến tính N CP (.) bài toán bù phi tuyến GCP (., .) bài toán bù tổng quát i CGCP bài toán bù tổng quát có ràng buộc là tập C đóng, lồi x∗ − M N S x∗ - chuẩn nhỏ nhất x∗ − CM N S x∗ - C chuẩn nhỏ nhất ii Lời cảm ơn Sau một thời gian cố gắng, nỗ lực học tập và nghiên cứu, đến nay tôi đã hoàn thành luận văn tốt nghiệp thạc sĩ của mình. Để có được kết quả này, tôi xin bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành nhất đến thầy tôi, GS. TSKH. Nguyễn Xuân Tấn, người đã định hướng nghiên cứu cho tôi trong suốt thời gian thực hiện luận văn của mình. Tôi xin chân thành cảm ơn sự giúp đỡ quý báu của các thầy cô giáo trong bộ môn Toán Giải tích nói riêng và khoa Toán, trường Đại học Sư phạm Hà Nội 2 nói chung đã giúp đỡ và tạo điều kiện tốt nhất cho tôi trong suốt quá trình học tập và nghiên cứu. Xin cảm ơn những người thân trong gia đình và tất cả những người bạn thân yêu đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và thực hiện luận văn của mình. Tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô và các bạn để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn. Hà Nội, tháng 9 năm 2017 Tác giả Nguyễn Thị Thắm iii Lời cam đoan Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự hướng dẫn của thầy giáo GS. TSKH. Nguyễn Xuân Tấn. Tôi xin cam đoan luận văn này là công trình nghiên cứu của riêng tôi. Trong quá trình nghiên cứu và hoàn thành luận văn tôi đã kế thừa những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự trân trọng và biết ơn. Tôi xin cam đoan rằng các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Hà Nội, tháng 9 năm 2017 Tác giả Nguyễn Thị Thắm iv Mục lục Mở đầu 1 1 4 Kiến thức cơ bản 1.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . . . . . . 4 1.2 Khái niệm bài toán đặt không chỉnh . . . . . . . . . . . . . 5 1.3 Phương pháp hiệu chỉnh . . . . . . . . . . . . . . . . . . . 6 1.4 Bài toán bù tuyến tính và một số phương pháp giải . . . . . 8 1.4.1 Bài toán bù tuyến tính . . . . . . . . . . . . . . . . 8 1.4.2 Một số phương pháp giải . . . . . . . . . . . . . . . 8 1.5 2 Bài toán bù phi tuyến và một số phương pháp giải . . . . . 14 1.5.1 Bài toán bù phi tuyến . . . . . . . . . . . . . . . . . 14 1.5.2 Một số phương pháp giải . . . . . . . . . . . . . . . 15 Phương pháp hiệu chỉnh cho bài toán bù tổng quát 25 2.1 Đặt bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.2 Sự tồn tại nghiệm của bài toán bù tổng quát . . . . . . . . 25 2.3 Phương pháp hiệu chỉnh . . . . . . . . . . . . . . . . . . . 27 2.4 2.3.1 Phương pháp hiệu chỉnh dựa trên phiếm hàm Tikhonov 27 2.3.2 Phương pháp hiệu chỉnh có ràng buộc . . . . . . . . 34 Một số bài toán liên quan . . . . . . . . . . . . . . . . . . . 38 2.4.1 Quy hoạch toàn phương . . . . . . . . . . . . . . . . 38 2.4.2 Trò chơi song ma trận . . . . . . . . . . . . . . . . . 39 2.4.3 Cân bằng thị trường . . . . . . . . . . . . . . . . . . 41 v Kết luận 44 Tài liệu tham khảo 45 vi Mở đầu 1. Lí do chọn đề tài Vào những năm 1940 bài toán bù đã được xuất hiện qua những trường hợp riêng và có nhiều ứng dụng trong việc giải quyết những vấn đề đặt ra trong thực tế. Đến đầu năm 1960 bài toán này mới thực sự thu hút các nhà toán học và nó trở thành một chủ đề nghiên cứu độc lập. Nguồn gốc của bài toán bù có liên quan đến các bài toán bất đẳng thức biến phân, bài toán quy hoạch toán học, bài toán cân bằng thị trường, trò chơi song ma trận,. . . và có ứng dụng trong nhiều lĩnh vực khác nhau trong cơ học, kinh tế, tài chính, điều khiển tối ưu và giải bài toán quy hoạch toàn phương,. . . Những vấn đề này dẫn đến việc giải các bài toán mà nghiệm của chúng không ổn định theo dữ kiện ban đầu, tức là một sự thay đổi nhỏ dẫn đến sự sai khác lớn của nghiệm, thậm chí làm cho bài toán trở nên vô nghiệm hoặc vô định. Đây là những bài toán đặt không chỉnh. Do các số liệu được thu thập bằng thực nghiệm sau đó được sử lý trên máy tính nên không tránh khỏi sai số. Vì vậy, ta cần phải có những phương pháp giải ổn định các bài toán đặt không chỉnh. Nhiều nhà khoa học đã nghiên cứu phương pháp giải bài toán đặt không chỉnh, điển hình là: Tikhonov A.N, Alber Ya.I, Atkinson K.E. Phần lớn các bài toán trong phương trình toán tử cũng như trong lý thuyết tối ưu, ta thường gặp trong thực tế là những bài toán đặt không chỉnh. Để giải chúng Tikhonov đã đưa ra phương pháp hiệu chỉnh để giải. Với mong muốn tìm hiểu sâu hơn về những kiến thức đã học về một lớp 1 bài toán trong lý thuyết tối ưu và mối quan hệ giữa chúng cũng như những ứng dụng trong việc giải những bài toán thực tế, tôi đã chọn đề tài nghiên cứu "Phương pháp hiệu chỉnh cho bài toán bù tổng quát" làm đề tài luận văn Thạc sĩ của mình. Cụ thể là bài toán: Tìm véctơ x ∈ R sao cho F (x) ≥ 0, G(x) ≥ 0, hF (x), G(x)i ≥ 0, trong đó F, G : Rn → Rn là các ánh xạ. Các nhà khoa học đã tìm ra rất nhiều phương pháp giải cho loại bài toán này. Tất cả các phương pháp đưa ra đều dẫn tới giải một bài toán cực tiểu hoặc một hệ phương trình tương đương. Các kết quả thu được trong luận văn là đưa ra được thuật toán hiệu chỉnh cho bài toán bù tổng quát và đánh giá được tốc độ hội tụ của nghiệm hiệu chỉnh. Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, bố cục của luận văn được trình bày trong hai chương. Chương 1 trình bày các khái niệm cơ bản như: P0 - hàm, P - hàm, hàm đơn điệu, hàm đơn điệu mạnh. Giới thiệu bài toán đặt không chỉnh và phương pháp hiệu chỉnh Tikhonov. Trình bày khái niệm về bài toán bù tuyến tính, bài toán bù phi tuyến và một số phương pháp giải. Chương 2 trình bày định nghĩa và phương pháp hiệu chỉnh cho bài toán bù tổng quát. Ngoài ra còn giới thiệu một số bài toán liên quan đến bài toán bù tổng quát. 2. Mục đích và nghiên cứu Nghiên cứu tổng quan về phương pháp hiệu chỉnh cho bài toán bù tổng quát, sự tồn tại nghiệm của bài toán, tốc độ hội tụ nghiệm hiệu chỉnh và thuật toán giải bài toán. 2 3. Nhiệm vụ nghiên cứu Tìm điều kiện để đảm bảo sự tồn tại nghiệm và nghiên cứu thuật toán để giải ra nghiệm của bài toán bù tổng quát bằng phương pháp hiệu chỉnh. 4. Đối tượng và phạm vi nghiên cứu Nghiên cứu bài toán bù tổng quát trong không gian Ơclit n - chiều. Sự tồn tại nghiệm và một số ứng dụng của nó. 5. Phương pháp nghiên cứu Thu thập tài liệu về bài toán bù tổng quát đã công bố trên các tạp chí và sách giáo khoa, chuyên khảo. Tổng hợp, phân tích, đánh giá và sử dụng các kết quả liên quan tới phương pháp hiệu chỉnh trong luận văn của mình. 6. Dự kiến đóng góp của luận văn Luận văn sẽ là một tổng quan về những kiến thức cơ bản và một số phương pháp giải bài toán bù và đi sâu về phương pháp hiệu chỉnh cho bài toán bù tổng quát. 3 Chương 1 Kiến thức cơ bản Việc giải bài toán bù được đưa về giải bài toán tối ưu. Tùy theo tính chất của ánh xạ. Trong bài toán bù ta sử dụng các hàm mục tiêu của bài toán tối ưu khác nhau, dựa trên khái niệm P - hàm. Chương này trình bày một số khái niệm P0 - hàm, P - hàm, P - hàm đều, hàm đơn điệu, hàm đơn điệu mạnh,. . . Giới thiệu bài toán đặt không chỉnh và phương pháp hiệu chỉnh Tikhonov. Trình bày khái niệm về bài toán bù tuyến tính, bài toán bù phi tuyến và một số phương pháp giải. Một số khái niệm trong chương này được trình bày dựa trên tài liệu [8]. 1.1 Một số khái niệm cơ bản Các khái niệm và kiến thức của chương này còn đúng cho các không gian vô hạn chiều tổng quát. Nhưng để cho trực quan, ta trình bày các vấn đề trong không gian Euclid n - chiều Rn . Ta bắt đầu bằng một số định nghĩa phân loại các cặp ánh xạ sau: Định nghĩa 1.1.1 Ánh xạ F : Rn → Rn được gọi là: • P0 - hàm nếu với mọi x, y ∈ Rn , x 6= y tồn tại một chỉ số i sao cho xi 6= yi , (xi − yi )(Fi (x) − Fi (y)) ≥ 0; 4 • P - hàm nếu với mọi x, y ∈ Rn , x 6= y tồn tại một chỉ số i sao cho xi 6= yi , (xi − yi )(Fi (x) − Fi (y)) > 0; • P - hàm đều nếu tồn tại một hằng số µ > 0 sao cho với mọi x, y ∈ Rn tồn tại một chỉ số i sao cho (xi − yi )(Fi (x) − Fi (y)) ≥ µ||x − y||2 ; • Hàm đơn điệu nếu với mọi x, y ∈ Rn , hx − y, F (x) − F (y)i ≥ 0; • Hàm đơn điệu mạnh nếu với mọi x, y ∈ Rn và µ > 0 cố định: hx − y, F (x) − F (y)i ≥ µ||x − y||2 . Từ các định nghĩa trên suy ra hàm đơn điệu là P0 - hàm và hàm đơn điệu mạnh là P - hàm đều. Với ma trận ta có định nghĩa sau: Định nghĩa 1.1.2 Một ma trận M ∈ Rn×n được gọi là: • P0 - ma trận nếu với mọi x ∈ Rn , x 6= 0 tồn tại một chỉ số i0 = i0 (x) sao cho xi0 6= 0, xi0 [M x]i0 ≥ 0; • P - ma trận nếu với mọi x ∈ Rn , x 6= 0 max xi [M x]i > 0. i 1.2 Khái niệm bài toán đặt không chỉnh Ta trình bày khái niệm bài toán đặt không chỉnh dưới dạng phương trình toán tử, cụ thể là: Xét bài toán tìm nghiệm của phương trình A(x) = f, f ∈ Y, 5 (1.1) trong đó A là một toán tử từ không gian mêtric X vào không gian mêtric Y với các khoảng cách tương ứng là ρX , ρY và f ∈ Y. Theo Hadamard J. bài toán (1.1) gọi là đặt chỉnh (chính quy) nếu các điều kiện sau được thỏa mãn: 1. Phương trình (1.1) có nghiệm xf với mọi f ∈ Y ; 2. Nghiệm xf được xác định một cách duy nhất; 3. Nghiệm xf phụ thuộc liên tục vào f. Nếu một trong ba điều kiện trên không thỏa mãn thì bài toán (1.1) được gọi là bài toán đặt không chỉnh. Đối với các bài toán phi tuyến thì điều kiện thứ hai gần như không thỏa mãn. Do đó hầu hết các bài toán phi tuyến đều là bài toán đặt không chỉnh. 1.3 Phương pháp hiệu chỉnh Trước hết ta trình bày một cách sơ lược về phương pháp hiệu chỉnh Tikhonov. Đó là phương pháp hiệu chỉnh dựa trên việc xây dựng toán tử hiệu chỉnh và cách chọn giá trị của một tham số mới đưa vào. Giả sử A−1 không liên tục và thay cho f ta biết fδ : ρY (fδ , f ) ≤ δ → 0. Bài toán đặt ra là dựa vào (A, fδ ) và mức sai số δ , tìm một phần tử xδ xấp xỉ nghiệm chính xác xδ của bài toán (1.1). Rõ ràng là không thể xây dựng phần tử xδ theo quy tắc xδ = A−1 fδ . Vì A−1 có thể không xác định với mọi f ∈ Y và A−1 không liên tục, nên nếu A−1 fδ tồn tại cũng chưa chắc đã xấp xỉ A−1 f. Tham số δ cho ta mức độ sai số vế phải của (1.1). Bài toán đặt ra là ta có thể xây dựng phần tử xấp xỉ phụ thuộc vào một tham số nào đó và tham số này được chọn tương thích với δ sao cho khi δ → 0 thì phần tử xấp xỉ này hội tụ đến nghiệm xδ . Nếu được thì từ fδ ∈ Y ta có phần tử xấp xỉ thuộc X , tức là tồn tại một toán tử nào đó tác động từ không gian Y vào không gian X. 6 Phương pháp hiệu chỉnh Tikhonov dựa trên toán tử hiệu chỉnh được định nghĩa như sau: Định nghĩa 1.3.1 Cho A : X → Y là một toán tử không gian Banach X vào không gian Banach Y . Toán tử R(f, α) phụ thuộc tham số α tác động từ Y vào X được gọi là một toán tử hiệu chỉnh cho bài toán (1.1) nếu: 1. Tồn tại hai số dương α1 và δ1 sao cho toán tử R(f, α) xác định với mọi α ∈ (0, α1 ) và với mọi fδ ∈ Y : ρY (fδ , f ) ≤ δ, δ ∈ (0, δ1 ); 2. Tồn tại một sự phụ thuộc α = α(fδ , δ) sao cho với mọi ε > 0, ∃δ(ε) ≤ δ1 để với mọi fδ ∈ Y thỏa mãn ρY (fδ , f ) ≤ δ ≤ δ1 thì ρX (xα , x0 ) ≤ ε, ở đây x0 là nghiệm chính xác của (1.1) và xα ∈ R(fδ , α(fδ , δ)). Phần tử xấp xỉ xα gọi là nghiệm hiệu chỉnh của bài toán (1.1) và α = α(fδ , δ) gọi là tham số hiệu chỉnh. Tham số hiệu chỉnh α(fδ , δ) phải được chọn sao cho lim α(fδ , δ) = 0. δ→0 Rõ ràng nghiệm hiệu chỉnh ổn định với dữ liệu ban đầu. Như vậy để tìm nghiệm xấp xỉ phụ thuộc liên tục vào dữ kiện của bài toán (1.1) gồm các bước: (B1) Xây dựng bài toán hiệu chỉnh R(f, α), (B2) Chọn giá trị của tham số hiệu chỉnh α dựa vào thông tin của bài toán về phần tử fδ và mức sai số δ. Chú ý 1.3.1 Trong trường hợp α = δ, định nghĩa về toán tử hiệu chỉnh có dạng đơn giản sau: Toán tử R(f, δ) tác động từ Y vào X được gọi là một toán tử hiệu chỉnh, nếu: 1. Tồn tại một số dương δ1 sao cho toán tử R(f, δ) xác định với mọi 0 ≤ δ ≤ δ1 và với mọi f ∈ Y sao cho ρY (f, f0 ) ≤ δ; 2. Với ε > 0 bất kì, tồn tại δ0 = δ0 (ε, fδ ) ≤ δ1 sao cho từ ρY (f, f0 ) ≤ δ ≤ δ0 ta có ρX (xδ , x0 ) ≤ ε, trong đó xδ ∈ R(fδ , δ). 7 Chú ý 1.3.2 Toán tử hiệu chỉnh R(f, δ) có thể là một ánh xạ đa trị. 1.4 1.4.1 Bài toán bù tuyến tính và một số phương pháp giải Bài toán bù tuyến tính Trước hết ta nhắc lại bài toán bù tuyến tính. Định nghĩa 1.4.1 Bài toán bù tuyến tính được ký hiệu: LCP (q, M ), là bài toán tìm véctơ x ∈ Rn sao cho x ≥ 0, F (x) ≥ 0, hx, F (x)i = 0, trong đó F : Rn → Rn là ánh xạ afin, nghĩa là F (x) = M x + q, M ∈ Rn×n , q ∈ Rn . 1.4.2 1.4.2.1 Một số phương pháp giải Phương pháp Lemke Hiện nay có khá nhiều thuật toán được đề xuất để giải bài toán bù tuyến tính, nhưng quen thuộc nhất là phương pháp Lemke. Một số khái niệm được sử dụng trong phương pháp này cũng giống như trong phương pháp đơn hình giải quy hoạch tuyến tính. Biến cơ sở là các biến mà các hệ số tương ứng với chúng là độc lập tuyến tính, các biến còn lại là biến phi cơ sở. Các véctơ cột này tạo nên một cơ sở của hệ bù. Cơ sở có thể thay đổi bằng cách tráo đổi giữa hai biến cơ sở và biến phi cơ sở cho nhau. Phép xoay là thuật ngữ được sử dung thường xuyên trong phương pháp Lemke. Phép xoay là sự thay đổi cơ sở bằng cách đổi chỗ một biến phi cơ sở với một biến cơ sở, nghĩa là một biến phi cơ sở sẽ được đưa vào cơ sở và trở thành biến cơ sở mới để thay thế cho một biến cơ sở bị đưa ra khỏi cơ 8 sở và sẽ trở thành biến phi cơ sở mới. Xét bài toán LCP (q, M ) có dạng: tìm hai véctơ z, ω ∈ Rn thỏa mãn ω − M z = q, z ≥ 0, ω ≥ 0, (1.2) hz, ωi = 0, (1.3) trong đó q ∈ Rn và M ∈ Rn×n . Nếu q ≥ 0 nghiệm của bài toán là z = 0 và ω = q. Ngược lại, nếu qi < 0 với i bất kỳ thì thêm vào một biến giả z0 và xét bài toán bù suy rộng ω − M z − ez0 = q, (1.4) z0 ≥ 0, zj ≥ 0, ωj ≥ 0, j = 1, ..., n, (1.5) zj ωj = 0, ∀j = 1, 2, ..., n, (1.6) trong đó e ∈ Rn là véctơ với mọi thành phần bằng 1. Ta gọi (1.5) là điều kiện không âm và (1.6) là điều kiện bù. Ý tưởng của phương pháp Lemke như sau: đặt z0 = max{−qi : 1 ≤ i ≤ n} > 0, z = 0, ω = q + ez, ta được nghiệm (bù không âm) ban đầu của hệ mở rộng (1.4) - (1.5). Thực hiện một dãy phép xoay tương tự như các phép biến đổi đơn hình, đưa nghiệm bù không âm ban đầu về nghiệm bù không âm với biến giả z0 . Khi đó ta nhận được nghiệm của bài toán bù tuyến tính LCP (q, M ). Ta có bổ đề sau: Bổ đề 1.4.1 ([8]) Nếu (z0 , z, ω) là một nghiệm của bài toán bù suy rộng (1.4) - (1.6) với z0 = 0 thì (z, ω) sẽ là một nghiệm của bài toán bù tuyến tính ban đầu LCP (q, M ). Định nghĩa 1.4.2 Ta nói (z0 , z, ω) ∈ R1+2n là một nghiệm chấp nhận được cơ sở gần bù của hệ (1.4) – (1.6) nếu: 1. (z0 , z, ω) là một nghiệm chấp nhận được cơ sở của hệ (1.4) - (1.6); 9 2. Có chỉ số s ∈ {1, 2, ..., n} sao cho cả hai biến zs và ωs đều là biến phi cơ sở; 3. z0 là biến cơ sở và có đúng một biến trong mỗi cặp bù nhau (zj , ωj ) là biến cơ sở với mọi j = 1, 2, ..., n và j 6= s. Định nghĩa 1.4.3 Cho một nghiệm chấp nhận được cơ sở gần bù (z0 , z, ω) trong đó cả hai biến zs và ωs đều là biến phi cơ sở. Nếu nghiệm chấp nhận b ) nhận được từ (z0 , z, ω) bằng cách đưa zs hoặc được cơ sở gần bù (zb0 , zb, ω ωs vào cơ sở sao cho phép biến đổi hệ (1.4) theo cơ sở mới (gọi là phép xoay) đẩy một biến khác z0 ra khỏi cơ sở thì nghiệm đó sẽ được gọi là nghiệm chấp nhận được cơ sở gần bù kề (z0 , z, ω). Thuật toán Lemke giải bài toán LCP (q, M ) gồm các bước sau: Bước 0( Khởi sự): Nếu q ≥ 0 thì dừng thuật toán: (z, ω) = (0, q) là nghiệm chấp nhận được cơ sở bù của LCP (q, M ). Ngược lại, ghi các hệ số của hệ phương trình xác định theo (1.4) vào bảng hình chữ nhật (như bảng đơn hình). Giả sử −qs = max{−qi : i = 1, 2, ..., n} > 0. Áp dụng quy tắc "hình chữ nhật" và biến đổi bảng như vậy gọi là phép quay theo trụ (ω0 , z0 ). Như vậy, các biến cơ sở z0 và ωj với mọi j = 1, 2, ..., n; i 6= j đều không âm. Đặt ys − zs rồi chuyển sang thực hiện vòng lặp chính, gồm các bước: Bước 1: Giả sử ds là cột trong bảng nhận được tương ứng với cột biến ys . Nếu ds ≤ 0 thì chuyển sang Bước 4. Ngược lại, xác định chỉ số hàng r nhờ kiểm tra tỉ số nhỏ nhất dưới đây, trong đó d˜ là cột hệ số ở vế phải của hệ (1.4)   q̃i d˜r = min : dis > 0 . drs 1≤i≤n dis Nếu biến cơ sở ở hàng r là z0 thì chuyển sang Bước 3. Ngược lại, chuyển sang Bước 2. Bước 2: Giả sử biến cơ sở ở hàng r là zh hoặc ωh với chỉ số h 6= s. Đưa 10 biến ys vào cơ sở và biến đổi bảng theo phần tử trụ ở hàng r và cột ys . Nếu biến ωh bị loại khỏi cơ sở thì đặt ys = zh , còn nếu biến zh bị loại khỏi cơ sở thì đặt ys = ωh . Quay lại thực hiện Bước 1. Bước 3: Đưa biến ys vào cơ sở và loại khỏi cơ sở biến z0 . Sau khi biến đổi bảng theo phần tử trụ ở hàng z0 và cột ys ta sẽ nhận được nghiệm chấp nhận được cơ sở bù của bài toán LCP (q, M ). Dừng thuật toán. Bước 4: Dừng ở tia R = {(z0 , z, ω) + λd : λ ≥ 0} có tính chất: mỗi điểm trên tia R đều thỏa mãn (1.4) - (1.6). Ở đây (z0 , z, ω) là nghiệm chấp nhận được cơ sở gần bù tương ứng với bảng cuối cùng và d là phương án cực biên của tập xác định bởi (1.4) - (1.6). Cụ thể là véctơ d ∈ R1+2n có phần tử ở hàng tương ứng với ys bằng 1, phần tử ở các hàng tương ứng với các biến cơ sở bằng −ds , mọi phần tử khác bằng 0. Trong trường hợp LCP (q, M ) không suy biến, Olsson D. [8] đã chứng minh được. Định lý 1.4.1 ([8]) Nếu M là P - ma trận thì phương pháp Lemke sẽ luôn giải được với bất kỳ LCP (q, M ) không suy biến. 1.4.2.2 Phương pháp dự đoán và hiệu chỉnh(Predictor-corrector) Để giải bài toán bù tuyến tính đơn điệu, Burke J. và Xu S. [1] đã xét bài toán bù tuyến tính: tìm (x, y) ∈ Rn × Rn thỏa mãn M x − y + q = 0, x ≥ 0, y ≥ 0, hx, yi = 0, trong đó M ∈ Rn × Rn là nửa xác định dương và q ∈ Rn . Ký hiệu quỹ đạo trung tâm là tập C = {(x, y) : 0 < µ, 0 < x, 0 < y, M x − y + q = 0, Xy = µ2 e}, trong đó e ∈ Rn là véctơ mà mọi thành phần của nó là 1 và X là ma trận chéo mà mọi phần tử nằm trên đường chéo được cho bởi véc tơ x ∈ Rn . 11 Burke J. và Xu S. đã giải bài toán LCP (q, M ) trong trường hợp đơn điệu bằng cách xây dựng hàm φ(a, b, µ) = a + b − q (a − b)2 + 4µ2 . (1.7) Dễ thấy φ(a, b, µ) = 0 ⇔ a ≥ 0, b ≥ 0, ab = µ2 . Áp dụng phương pháp Newtơn giải hệ phương trình có dạng F (x, y, µ) = υ, trong đó hàm F : Rn × Rn × R++ → Rn × Rn × R++ , xác định bởi   Mx − y + q   F (x, y, µ) :=  φ(x, y, µ)  , µ với   φ(x1 , y1 , µ)   φ(x, y, µ) :=  ... . φ(xn , yn , µ) Chú ý 1.4.1 Ta dễ dàng nhận thấy F (x, y, µ) = 0 khi và chỉ khi (x, y) là nghiệm của LCP (q, M ) và   0   F (x, y, µ) :=  0  , µ 6= 0 µ khi và chỉ khi (x, y) nằm trên quỹ đạo trung tâm C với tham số trơn tương ứng µ. Ký hiệu quỹ đạo trung tâm là N (β) := {(x, y) | M x−y+q = 0, φ(x, y, µ) ≤ 0, ||φ(x, y, µ)|| ≤ βµ, µ > 0}, ở đây β > 0 cho trước. Lân cận này có thể xem là hợp của các lát cắt N (β, µ) := {(x, y) | M x−y+q = 0, φ(x, y, µ) ≤ 0, ||φ(x, y, µ)|| ≤ βµ, µ > 0}. 12