Tài liệu Luận án tiến sĩ toán học hiệu chỉnh bài toán bù tổng quát

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ NGUYỄN THỊ THÚY HOA HIỆU CHỈNH BÀI TOÁN BÙ TỔNG QUÁT Chuyên ngành: Toán ứng dụng Mã số: 62460112 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC 1. GS.TS Nguyễn Bường 2. TS. Nguyễn Công Điều HÀ NỘI - NĂM 2016 ii LỜI CAM ĐOAN Các kết quả trình bày trong luận án là công trình nghiên cứu của tôi, được hoàn thành dưới sự hướng dẫn của GS.TS. Nguyễn Bường và TS. Nguyễn Công Điều. Các kết quả trình bày trong luận án là mới và chưa từng được công bố trong các công trình của người khác. Tôi xin chịu trách nhiệm về những lời cam đoan của mình. Tác giả Nguyễn Thị Thúy Hoa iii LỜI CẢM ƠN Luận án này được hoàn thành tại Viện Công nghệ thông tin, Học viện Khoa học và Công nghệ thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam dưới sự hướng dẫn tận tình của GS.TS. Nguyễn Bường và TS. Nguyễn Công Điều. Tác giả xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc nhất tới hai thầy. Tác giả cũng xin bày tỏ lòng biết ơn tới các thầy, cô giáo thuộc Viện Công nghệ thông tin, Viện Toán học, Học viện Khoa học và Công nghệ đã tạo điều kiện, giúp đỡ tác giả trong quá trình học tập và nghiên cứu. Tác giả xin chân thành cảm ơn Ban Giám hiệu trường Đại học Nội vụ Hà Nội, Trung tâm Tin học, nơi tác giả đang công tác, đã tạo điều kiện thuận lợi để tác giả hoàn thành luận án. Cảm ơn các anh chị em nghiên cứu sinh, bạn bè đồng nghiệp đã trao đổi những kiến thức và kinh nghiệm trong thời gian tác giả học tập, nghiên cứu tại Viện Công nghệ Thông tin. Cuối cùng, tác giả xin bày tỏ lòng biết ơn sâu sắc tới những người thân trong gia đình đã luôn động viên, chia sẻ và khích lệ tác giả trong quá trình nghiên cứu. Tác giả Nguyễn Thị Thúy Hoa Mục lục Trang bìa phụ i Lời cam đoan ii Lời cảm ơn iii Mục lục iv Một số ký hiệu và viết tắt vi Mở đầu 1 Chương 1. Một số kiến thức chuẩn bị 1.1. Một số khái niệm . . . . . . . . . . . . . . . . . . . . . . . . 7 7 1.2. Bài toán đặt không chỉnh và phương pháp hiệu chỉnh . . . . 8 1.2.1. Khái niệm bài toán đặt không chỉnh . . . . . . . . . 1.2.2. Phương pháp hiệu chỉnh Tikhonov . . . . . . . . . . 8 9 1.2.3. Phương pháp hiệu chỉnh Tikhonov cho bài toán cực trị tổng quát . . . . . . . . . . . . . . . . . . . . . . 10 1.3. Bài toán bù . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.1. Bài toán bù tuyến tính . . . . . . . . . . . . . . . . . 12 1.3.2. Bài toán bù phi tuyến . . . . . . . . . . . . . . . . . 18 Chương 2. Bài toán bù tổng quát và phương pháp hiệu chỉnh 39 2.1. Vấn đề tồn tại nghiệm của bài toán bù tổng quát . . . . . . 39 2.2. Hiệu chỉnh bài toán bù tổng quát . . . . . . . . . . . . . . . 40 2.2.1. Hiệu chỉnh bài toán bù tổng quát dựa trên phiếm hàm Tikhonov . . . . . . . . . . . . . . . . . . . . . . 40 2.2.2. Hiệu chỉnh bài toán bù tổng quát có ràng buộc . . . 49 2.3. Một số bài toán dẫn tới bài toán bù . . . . . . . . . . . . . . 52 v Chương 3. Bài toán cực trị với ràng buộc là bài toán bù tổng quát 62 3.1. Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 62 3.2. Phương pháp hiệu chỉnh Tikhonov cho bài toán đặt ra . . . 67 3.3. Ví dụ số minh họa . . . . . . . . . . . . . . . . . . . . . . . 72 Kết luận chung 79 Kiến nghị hướng nghiên cứu tiếp theo 80 Danh mục các công trình đã công bố liên quan đến luận án 81 Tài liệu tham khảo 82 Một số ký hiệu và viết tắt Rn không gian Ơclit n - chiều Rn×m không gian các ma trận cấp n × m 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 , . . . k.k chuẩn trong không gian Rn hx, yi tích vô hướng của x và y trong Rn y≤0 các thành phần yi ≤ 0, i = 1, 2, . . . , n   ∂θ − gradient của hàm θ : Rn → R ∂xj ∇θ AT chuyển vị của ma trận A PC (x) phép chiếu mêtric phần tử x lên tập đóng lồi C V I(., .) bài toán bất đẳng thức biến phân LCP (., .) bài toán bù tuyến tính N CP (.) bài toán bù phi tuyến P N CP (., .) bài toán bù phi tuyến nhiễu GCP (., .) bài toán bù tổng quát CGCP bài toán bù tổng quát có ràng buộc là tập C đóng, lồi M P EC bài toán cực trị với ràng buộc là bài toán bù tổng quát R(., .) toán tử hiệu chỉnh H(., .) khoảng cách Hausdorff x∗ − M N S x∗ - chuẩn nhỏ nhất x∗ − CM N S x∗ - C chuẩn nhỏ nhất Mở đầu Trong các ấn phẩm về toán, có thể tìm thấy các trường hợp riêng của bài toán bù rất sớm vào những năm 1940, tuy nhiên bài toán bù chỉ thực sự thu hút các nhà toán học từ đầu năm 1960 [10], khi bài toán trở thành một chủ đề nghiên cứu riêng. Bài toán bù có nguồn gốc từ bài toán bất đẳng thức biến phân, bài toán quy hoạch toàn phương, bài toán cân bằng thị trường, bài toán điểm dừng tối ưu, trò chơi song ma trận,...[10] và nó có nhiều ứng dụng trong các lĩnh vực như: kinh tế, tài chính, kỹ thuật, vật lý, sinh thái và điều khiển tối ưu,... Chính vì vậy, việc nghiên cứu bài toán bù hiện nay vẫn đang là vấn đề thời sự [15], [20], [24], [25], đặc biệt là việc nghiên cứu tìm ra phương pháp giải bài toán bù sao cho hiệu quả. Trong bối cảnh đó, luận án này đề cập tới phương pháp hiệu chỉnh Tikhonov cho bài toán bù tổng quát, đó là bài toán: tìm x̃ ∈ Rn sao cho g(x̃) ≤ 0, h(x̃) ≤ 0, hg(x̃), h(x̃)iRm = 0, (0.1) ở đây g(x), h(x) là hai hàm liên tục từ không gian Rn tới không gian Rm , h., .i, k.kRn lần lượt là tích vô hướng và chuẩn trong Rn ; và phương pháp hiệu chỉnh bài toán cực trị với ràng buộc là bài toán bù tổng quát, được phát biểu như sau: tìm một phần tử x̃ ∈ C ∩ S̃, thỏa mãn điều kiện ϕ(x̃) = min ϕ(y), C̃ = C ∩ S̃, (0.2) y∈C̃ ở đây C là tập đóng, lồi trong không gian Ơclit Rn , S̃ = S˜1 ∩ S˜2 , trong đó S˜1 = {x ∈ Rn : g̃(x) ≤ 0, h̃(x) = 0}, S˜2 = {x ∈ Rn : g(x) ≤ 0, h(x) ≤ 0, hg(x), h(x)iRq = 0}, (0.3) các hàm thực ϕ : Rn −→ R, g̃ : Rn −→ Rm , h̃ : Rn −→ Rp , g và h : Rn −→ Rq là liên tục, ký hiệu y = (y1 , y2 , ..., ym ) ≤ 0 có nghĩa là yi ≤ 0 với mọi 2 i = 1, 2, ..., m. Ta giả thiết tập nghiệm của các bài toán (0.1), (0.2) và (0.3) khác rỗng. Những bài toán có dạng (0.2)-(0.3) được biết đến như những bài toán với ràng buộc bù, ký hiệu là MPEC. Thông thường, một bài toán MPEC là bài toán tối ưu với ràng buộc là bất đẳng thức biến phân. Tuy nhiên, trong một số trường hợp MPEC có thể viết dưới dạng (0.2)-(0.3) [38]. Trong trường hợp đặc biệt, khi m = n, g(x) = −x và h(x) = −F (x), trong đó F : Rn −→ Rn là ánh xạ affin, nghĩa là F (x) = M x + q, M ∈ Rn×n , q ∈ Rn , bài toán (0.1) được gọi là bài toán bù tuyến tính, ký hiệu bởi LCP (q, M ). Tìm hiểu nghiệm của bài toán này, Olsson D. [44] đã thu được các kết quả sau. Định lí 0.1 Khi M ∈ Rn×n là P - ma trận với tất cả các định thức con chính của M dương thì LCP (q, M ) có một nghiệm với q ∈ Rn . Định lí 0.2 Nếu q không âm thì bài toán bù tuyến tính LCP (q, M ) luôn giải được và x = 0 là một nghiệm tầm thường của nó. Nghiên cứu mối quan hệ giữa bài toán bù tuyến tính và bài toán bất đẳng thức biến phân, ký hiệu bởi V I(K, F ), là bài toán tìm một vectơ x ∈ K ⊂ Rn sao cho hy − x, F (x)i ≥ 0, ∀y ∈ K, ở đây F : K −→ Rn là hàm liên tục và K là tập đóng, lồi, Olsson D. [44] đã chứng minh tiếp được kết quả dưới đây. Định lí 0.3 Nếu F = M x + q, M ∈ Rn×n , q ∈ Rn , x ∈ Rn+ thì V I(F, Rn+ ) và bài toán bù tuyến tính LCP (q, M ) có nghiệm hoàn toàn trùng nhau. Khi n = m, g(x) = −x và h(x) = −F (x) trong đó F là ánh xạ phi tuyến từ Rn vào Rn , bài toán (0.1) được gọi là bài toán bù phi tuyến, ký hiệu bởi N CP (F ), đó là bài toán tìm vectơ x ∈ Rn sao cho x ≥ 0, F (x) ≥ 0, hx, F (x)i = 0, (0.4) các nhà khoa học cũng đã tìm ra rất nhiều phương pháp giải cho loại bài toán này [13], [17], [18], [23], [33]-[35]. Tất cả các phương pháp đưa ra đều 3 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ó thể chia thành lớp các phương pháp sau: • Phương pháp sử dụng hàm khoảng Trong phương pháp này, họ đã biến đổi bài toán N CP (F ) thành bài toán tương đương nhờ một hàm được gọi là hàm khoảng (merit function) để đưa về bài toán tìm cực tiểu có ràng buộc của một phiếm hàm. Công cụ thuận tiện để thiết lập hàm khoảng là C - hàm [12], đó là hàm φ : R2 −→ R thỏa mãn tính chất: φ(a, b) = 0 ⇐⇒ ab = 0, a ≥ 0, b ≥ 0. Có một số C - hàm sau: φN R (a, b) = min{a, b}; φM S (a, b) = ab +
1 max{0, a − αb}2 − a2 + max{0, b − αa}2 − b2 , α > 1; 2α p φF B (a, b) = a2 + b2 − a − b. Hàm khoảng được xây dựng trên hàm φN R được gọi là hàm số dư tự nhiên. Hàm φM S không âm trên R2 và hàm khoảng được xây dựng trên nó gọi là hàm Lagrange ẩn được giới thiệu bởi Mangasarian và Solodov [41]. Hàm φF B được gọi là hàm Fischer [16]. Gần đây, dựa trên hàm φF B nhiều nhà khoa học đã mở rộng nghiên cứu và đưa ra một số hàm mới có tính chất tốt hơn. Luo và Tseng [39] đã đưa ra một lớp các hàm khoảng mới f˜ : Rn −→ R xác định bởi f˜(x) = ψ0 (hx, F (x)iRn ) + n X ψi (−xi , −Fi ), i=1 ở đây ψ0 : R −→ [0, ∞) và ψi : R2 −→ [0, ∞), i = 1, 2, ..., n là các hàm liên tục. Ý tưởng mới này cũng được Kanzow C., Yamashita N. và Fukushima M. [32] sử dụng để xây dựng hàm khoảng mới. • Phương pháp hiệu chỉnh Thay vì tìm nghiệm trực tiếp, phương pháp này tìm nghiệm của dãy các bài toán đặt chỉnh mà những nghiệm của chúng sẽ hội tụ tới nghiệm của bài toán ban đầu. Lược đồ hiệu chỉnh Tikhonov trong [11], [22] đối với bài toán bù bao gồm việc giải dãy các bài toán: x ≥ 0, Fε (x) ≥ 0, hx, Fε (x)iRn = 0, (0.5) 4 ở đây, Fε (x) = F (x) + εx và ε là tham số dương hội tụ tới 0. • Phương pháp kết hợp hàm khoảng và hiệu chỉnh Trong phương pháp này, việc hiệu chỉnh dựa trên hàm H là hàm đi từ không gian Rn+1 tới Rn+1 , xác định bởi H(ε, z) = 0 ⇐⇒ ε = 0, x ∈ S 0 , (0.6) ở đây S 0 là tập nghiệm của (0.4), z := (ε, x) ∈ R × Rn , H(ε, z) := hε, G(ε, z)i và hàm khoảng G : Rn+1 −→ Rn , với Gi (ε, x) := φ(xi , Fε,i (x)), i = 1, 2, ..., n, trong đó φ(.) là hàm Fischer, Fε,i là thành phần thứ i của Fε . Sự hội tụ của nghiệm hiệu chỉnh đối với (0.5) và (0.6) chỉ được thiết lập trong trường hợp F là đơn điệu hoặc P0 - hàm. Hơn nữa, tốc độ hội tụ của nghiệm hiệu chỉnh vẫn chưa được xem xét. Trong [5], N. Bường đã sử dụng phương pháp hiệu chỉnh Tikhonov để biến đổi bài toán (0.2) thành bài toán cực trị không ràng buộc. Tiếp nối ý tưởng trên, trong luận án này, chúng tôi đã nghiên cứu phương pháp giải bài toán cực trị trong trường hợp bài toán có ràng buộc là bài toán bù tổng quát và đã chứng minh được kết quả hội tụ của nghiệm hiệu chỉnh. Như vậy, trong những trường hợp đặc biệt, bài toán bù đã có nhiều phương pháp giải khác nhau. Tuy nhiên, các kết quả đưa ra đều đòi hỏi các hàm trong bài toán phải có tính chất đơn điệu hoặc là P0 - hàm. Mặt khác, đối với bài toán bù tổng quát, chưa có thuật toán hiệu chỉnh. Chính vì thế, luận án này tập trung nghiên cứu phương pháp hiệu chỉnh bài toán bù tổng quát nhằm khắc phục những nhược điểm trên. Chúng tôi đã tiếp cận bài toán theo hướng khác và đã đưa ra một phương pháp giải bài toán này. Phương pháp mới không yêu cầu hàm g(x) và h(x) phải có tính P0 hàm. Thuật toán hiệu chỉnh dẫn tới cực tiểu một phiếm hàm phụ thuộc tham số nhưng không có ràng buộc, do đó việc giải bài toán trở nên đơn giản hơn rất nhiều. Các kết quả thu được trong luận án là: 1) Đưa ra thuật toán hiệu chỉnh cho bài toán bù tổng quát; 2) Đưa ra thuật toán hiệu chỉnh cho bài toán cực trị với ràng buộc là bài toán bù tổng quát; 3) Đánh giá tốc độ hội tụ của nghiệm hiệu chỉnh; 5 4) Minh họa các phương pháp đưa ra bằng bài toán cụ thể. Ngoài phần mở đầu, kết luận và danh mục các tài liệu tham khảo, luận án được bố cục gồm ba chương. Chương 1 có tính chất bổ trợ, trình bày sơ lược về một số vấn đề có liên quan như: P0 - hàm, P - hàm, P - hàm đều, hàm đơn điệu, hàm đơn điệu mạnh, P0 - ma trận, P - ma trận; giới thiệu bài toán đặt không chỉnh và phương pháp hiệu chỉnh Tikhonov cho bài toán cực trị tổng quát. Chương 1 cũng 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 các bài toán này. Chương 2 trình bày định nghĩa và phương pháp hiệu chỉnh bài toán bù tổng quát; các định lí chứng minh sự tồn tại nghiệm và đánh giá tốc độ hội tụ của nghiệm hiệu chỉnh. Ngoài ra, chương 2 còn giới thiệu một số bài toán dẫn tới bài toán bù tổng quát như: bài toán qui hoạch toàn phương, trò chơi song ma trận và bài toán cân bằng thị trường. Ví dụ số cùng kết quả tính toán minh họa cho phương pháp hiệu chỉnh được trình bày ở cuối chương. Chương 3 giới thiệu bài toán cực trị với ràng buộc là bài toán bù tổng quát, bao gồm: định nghĩa và một số kết quả nghiên cứu gần đây; phương pháp hiệu chỉnh Tikhonov cho bài toán này và một số định lí chứng minh sự tồn tại nghiệm được trình bày trong Mục 3.2. Cuối chương là ví dụ số minh họa cho phương pháp hiệu chỉnh Tikhonov đã trình bày ở Mục 3.2. 6 Các kết quả của luận án được báo cáo tại: • Hội thảo Quốc gia lần thứ XV "Một số vấn đề chọn lọc về công nghệ thông tin và truyền thông", Hà Nội 03 - 04/12/2012; • Hội thảo Quốc gia lần thứ XVI "Một số vấn đề chọn lọc về công nghệ thông tin và truyền thông", Đà Nẵng 14 - 15/11/2013; • Hội thảo Tối ưu và tính toán khoa học lần thứ 12, Ba Vì - Hà Nội 23 - 25/4/2014; • Hội thảo Quốc gia lần thứ XVII "Một số vấn đề chọn lọc về công nghệ thông tin và truyền thông", Đắklắk 30 - 31/10/2014; • Hội thảo Quốc gia lần thứ XVIII "Một số vấn đề chọn lọc về công nghệ thông tin và truyền thông", Thành phố Hồ Chí Minh 5 - 6/11/2015; • Seminar hàng tuần của nhóm Toán ứng dụng, Viện Công nghệ thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Chương 1 Một số kiến thức chuẩn bị Trong chương này, Mục 1.1 giới thiệu một số khái niệm như: P0 - hàm, P - hàm, P - hàm đều, hàm đơn điệu, hàm đơn điệu mạnh, P0 - ma trận, P - ma trận nhằm trang bị những kiến thức cần thiết cho việc trình bày các kết quả nghiên cứu chính của luận án. Mục 1.2 giới thiệu bài toán đặt không chỉnh và phương pháp hiệu chỉnh Tikhonov cho bài toán cực trị tổng quát. Mục 1.3 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 các bài toán này trong trường hợp đơn điệu hoặc P0 - hàm. Một số khái niệm trong chương này được trình bày dựa trên các tài liệu [1], [23] và [48]. 1.1. Một số khái niệm Định nghĩa 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; • 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ố dương µ 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)) ≥ µ k x − y k2 ; • 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 ≥ µkx − yk2 . 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. 8 Định nghĩa 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. Bài toán đặt không chỉnh và phương pháp hiệu chỉnh Trong những bài toán mà chúng ta đặt ra, đặc biệt là lớp những bài toán nảy sinh từ thực tế, tồn tại một lớp các bài toán mà nghiệm của nó không ổn định theo nghĩa một thay đổi nhỏ của dữ liệu đầu vào sẽ dẫn đến những thay đổi lớn của dữ liệu đầu ra (nghiệm của bài toán), thậm chí còn làm cho bài toán trở nên vô nghiệm. Ta có thể nói rằng, lớp các bài toán nói trên có nghiệm không phụ thuộc liên tục vào dữ kiện ban đầu và nó là một trường hợp riêng của lớp bài toán không chính qui hay bài toán đặt không chỉnh. Trong mục này, chúng tôi đề cập đến 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ùng với phương pháp hiệu chỉnh Tikhonov cho lớp bài toán loại này. 1.2.1. Khái niệm bài toán đặt không chỉnh Khái niệm bài toán chỉnh được Hadamard J. [23] đưa ra khi nghiên cứu về ảnh hưởng của các điều kiện biên lên nghiệm của các phương trình elliptic cũng như parabollic. Ở đây, chúng tôi trình bày khái niệm bài toán đặt không chỉnh ở dạng một phương trình toán tử, cụ thể: Xét bài toán tìm nghiệm của phương trình A(x) = f, (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 qui) nếu các điều kiện sau được thỏa mãn: i) Phương trình (1.1) có nghiệm xf với mọi f ∈ Y ; 9 ii) nghiệm xf được xác định một cách duy nhất; iii) nghiệm xf phụ thuộc liên tục vào f . Một thời gian dài người ta nghĩ rằng mọi bài toán đặt ra đều thỏa mãn cả ba điều kiện trên. Nhưng thực tế chỉ ra rằng quan niệm đó sai lầm. Nhất là khi máy tính điện tử ra đời, trong tính toán các bài toán thực tế bằng máy tính luôn xảy ra quá trình làm tròn số. Chính sự làm tròn số đó đã dẫn đến những sai lệch đáng kể. Nếu ít nhất một trong ba điều kiện trên không được thỏa mãn thì bài toán (1.1) được gọi là bài toán đặt không chỉnh. 1.2.2. Phương pháp hiệu chỉnh Tikhonov Trước hết, chúng tôi đề cập một cách sơ lược về phương pháp hiệu chỉnh Tikhonov. Để tìm nghiệm xấp xỉ của bài toán (1.1) khi không biết thông tin về nghiệm chính xác x0 , Tikhonov N. A. đã đưa ra một khái niệm mới. Đó 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 thông tin về (A, fδ ) và mức sai số δ, tìm một phần tử xδ xấp xỉ nghiệm chính xác x0 của bài toán (1.1). Rõ ràng là ta không thể xây dựng phần tử xấp xỉ xδ theo quy tắc xδ = A−1 fδ , vì thứ nhất là A−1 có thể không xác định với mọi f ∈ Y , thứ hai là 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ố δ chỉ cho ta mức độ sai số vế phải của (1.1). Vì vậy một điều tự nhiên nảy sinh là liệu 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 x0 . Ta cũng thấy 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. Định nghĩa 1.3 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: i) 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 ); 10 ii) 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α 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. Phương pháp hiệu chỉnh Tikhonov là một trong những phương pháp nổi tiếng và được sử dụng nhiều cho việc nghiên cứu và giải các bài toán đặt không chỉnh. Chú ý 1.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: i) 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 ) ≤ δ; ii) 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 ) ≤ ε, ở đây xδ ∈ R(fδ , δ). Chú ý 1.2 Toán tử hiệu chỉnh R(f, δ) có thể là một ánh xạ đa trị. 1.2.3. Phương pháp hiệu chỉnh Tikhonov cho bài toán cực trị tổng quát Xét bài toán tối ưu phi tuyến có ràng buộc như sau: tìm x̃ ∈ Rn sao cho ϕN (x̃) = min ϕN (x), (1.2) x∈S n S = {x ∈ R : fi (x) = 0, i = 1, 2, ..., m; ϕ̃j (x) ≤ 0, j = 1, 2, ..., N − 1}, ở đây fi , i = 1, 2, ..., m; ϕ̃j , j = 1, 2, ..., N − 1 và ϕN là những hàm liên tục xác định trong không gian Ơclit Rn . Đặt: S0 := {x ∈ Rn : fi (x) = 0, i = 1, 2, ..., m}, Sj := {x ∈ Rn : ϕ̃j (x) ≤ 0}, j = 1, 2, ..., N − 1, N −1 thì S = ∩j=0 6 ∅. Sj . Giả sử S 0 := {x̃ ∈ S : ϕN (x̃) = minx∈S ϕN (x)} = 11 Trong trường hợp S = Rn , bài toán (1.2) là bài toán cực trị không ràng buộc, có nghĩa là bài toán tìm một phần tử x̃ ∈ Rn sao cho ϕN (x̃) = minn ϕN (x). x∈R (1.3) Do việc giải bài toán cực trị không ràng buộc đơn giản hơn so với bài toán cực trị có ràng buộc nên N. Bường [4] đã biến đổi bài toán tối ưu phi tuyến tổng quát ban đầu thành bài toán tối ưu không ràng buộc, phụ thuộc tham số, bằng cách sử dụng phương pháp hiệu chỉnh Tikhonov. Ý tưởng của phương pháp này như sau: đặt ϕj (x) = max{0, ϕ̃j (x)}, j = 1, 2, ..., N − 1, rõ ràng ϕj liên tục, Sj := {x ∈ Rn : ϕj (x) = minn ϕj (x)}, j = 1, 2, ..., N − 1, x∈R ϕj (x) ≥ 0 ∀x ∈ Rn và ϕj (y) = 0 ∀y ∈ Sj . Khi S0 = Rn và ϕj , j = 1, 2, ..., N là hàm lồi, bài toán (1.2) đã được N. Bường [4] nghiên cứu. Phát triển ý tưởng trên, N. Bường [5] đã nghiên cứu giải bài toán (1.2) trong trường hợp ϕj không lồi và S0 là tập con của Rn , bằng cách xét bài toán: tìm một phần tử x̃ ∈ Rn sao cho ϕj (x̃) = min ϕj (x), j = 1, 2, ..., N, x∈S0 (1.4) n S0 = {x ∈ R : F (x) = 0}, ở đây F (x) = (f1 (x), ..., fm (x))T . Bài toán (1.4) có thể giải bằng cách xét bài toán tối ưu không ràng buộc: tìm một phần tử xα ∈ Rn sao cho Fα (xα ) = minn Fα (x), α > 0, x∈R Fα (x) = kF (x)k2Rm + N X αµj ϕj (x) + αkx − x∗ k2Rn , (1.5) j=1 0 ≤ µ1 < µ2 < ... < µN < 1, j = 2, 3, ..., N − 1, ở đây, x∗ là phần tử nào đó trong Rn . Như đã biết trong [50], Bài toán (1.5) có một nghiệm xα với mỗi α > 0. Không làm mất tính tổng quát, có thể giả thiết ϕN (x) ≥ 0 ∀x ∈ Rn . Hơn nữa, giả sử ϕN có những tập mức đóng, nghĩa là {x ∈ Rn : ϕN (x) ≤ c} là đóng với mọi c > 0. N. Bường [5] đã thu được: 12 Định lí 1.1 Nếu αk −→ 0 khi k −→ ∞ thì mọi dãy {xk }, ở đây xk := xαk là một nghiệm của (1.5) với α thay bởi αk , có một dãy con hội tụ. Giới hạn của mọi dãy con hội tụ là nghiệm của (1.2). Hơn nữa, nếu x̃ là duy nhất thì lim xk = x̃. k−→∞ Trong trường hợp {fi , ϕj } được cho bởi các xấp xỉ {fiδ , ϕδj } thỏa mãn điều kiện: | fi (x) − fiδ (x) | ≤ δ, i = 1, 2, ..., m, | ϕj (x) − ϕδj (x) | ≤ δ, j = 1, 2, ..., N, ∀x ∈ Rn , δ −→ 0, N. Bường [5] đã xét bài toán tối ưu không ràng buộc như sau: tìm một phần tử xδα ∈ Rn sao cho Fαδ (xδα ) = minn Fαδ (x), α > 0, δ ≥ 0, x∈R Fαδ (x) = kF δ (x)k2Rm + N X α µj ϕδj (x) + αkx − x∗ k2Rn . (1.6) j=1 Như đã nói ở trên, với mỗi αk > 0 bài toán (1.6) có một nghiệm xác định bởi xδα . N. Bường [5] đã chứng minh tiếp được kết quả sau. Định lí 1.2 Cho αk , δk −→ 0 sao cho δk αk −→ 0 khi k −→ ∞ thì mọi dãy {xk }, ở đây xk := xδαkk là một nghiệm của (1.6) với α, δ tương ứng thay bởi αk , δk , có một dãy con hội tụ. Giới hạn của mọi dãy con hội tụ là nghiệm của (1.2). Hơn nữa, nếu nghiệm x̃ là duy nhất thì lim xk = x̃. k−→∞ 1.3. 1.3.1. Bài toán bù Bài toán bù tuyến tính Định nghĩa 1.4 Bài toán bù tuyến tính, ký hiệu bởi LCP (q, M ), là bài toán tìm vectơ x ∈ Rn sao cho x ≥ 0, F (x) ≥ 0, hx, F (x)i = 0, trong đó F : Rn −→ Rn là ánh xạ affin, nghĩa là F (x) = M x + q, M ∈ Rn×n , q ∈ Rn . 13 Một số phương pháp giải bài toán bù tuyến tính • 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 hơn cả là phương pháp Lemke. Trước khi nghiên cứu phương pháp Lemke, cần tìm hiểu các khái niệm biến cơ sở và biến phi cơ sở, chúng giống như biến cơ sở và biến phi cơ sở dùng 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 véctơ cột 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 (như trong phương pháp đơn hình). Phép xoay là một thuật ngữ nữa được dùng 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ơ sở và sẽ trở thành biến phi cơ sở mới. Khi một biến cơ sở và một biến phi cơ sở đổi chỗ cho nhau thì hệ phương trình sẽ được biến đổi theo sao cho tập biến cơ sở mới được biểu diễn qua tập biến phi cơ sở mới. Xét bài toán LCP (q, M ) có dạng: tìm hai vectơ z, w ∈ Rn thỏa mãn w − M z = q, z ≥ 0, w ≥ 0, (1.7) hz, wi = 0, (1.8) trong đó q ∈ Rn và M ∈ Rn×n . Nếu q ≥ 0 dễ thấy nghiệm của bài toán là z = 0 và w = q. Trái lại (tức là có qi < 0 với i nào đó), thì thêm vào một biến giả z0 và xét bài toán bù suy rộng w − M z − ez0 = q, (1.9) z0 ≥ 0, zj ≥ 0, wj ≥ 0, j = 1, ..., n, (1.10) zj wj = 0, ∀j = 1, 2, ..., n, (1.11) trong đó e ∈ Rn là véctơ với mọi thành phần bằng 1. Ta gọi (1.10) là điều kiện không âm và (1.11) là điều kiện bù. Ý tưởng phương pháp Lemke như sau: đặt z0 = max{−qi : 1 ≤ i ≤ n} > 0, z = 0, w = q + ez0 , 14 nhận được nghiệm (bù không âm) ban đầu của hệ mở rộng (1.9) - (1.10). 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 = 0. Khi đó sẽ nhận được nghiệm của bài toán bù tuyến tính LCP (q, M ). Bổ đề sau được chứng minh trực tiếp từ định nghĩa của bài toán. Bổ đề 1.1 ([44]). Nếu (z0 , z, w) là một nghiệm của bài toán bù suy rộng (1.9) - (1.11) với z0 = 0 thì (z, w) 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.5 Ta nói (z0 , z, w) ∈ R1+2n là một nghiệm chấp nhận được cơ sở gần bù (almost complementary basic feasible solution) của hệ (1.9) - (1.11) nếu i) (z0 , z, w) là một nghiệm chấp nhận được cơ sở của hệ (1.9) - (1.11); ii) có chỉ số s ∈ {1, 2, ..., n} sao cho cả hai biến zs và ws đều là biến phi cơ sở; iii) z0 là biến cơ sở và có đúng một biến trong mỗi cặp bù nhau (zj , wj ) là biến cơ sở với mọi j = 1, 2, ..., n và j 6= s. Định nghĩa 1.6 Cho một nghiệm chấp nhận được cơ sở gần bù (z0 , z, w), trong đó cả hai zs và ws là biến phi cơ sở. Nếu nghiệm chấp nhận được cơ sở gần bù (zˆ0 , ẑ, ŵ) nhận được từ (z0 , z, w) bằng cách đưa zs hoặc ws vào cơ sở sao cho phép biến đổi hệ (1.9) 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, w). Thuật toán Lemke (gọi là thuật toán xoay bù), xuất phát từ nghiệm bù ban đầu (z0 , z, w) của bài toán (1.9) - (1.11), đi dọc theo các nghiệm chấp nhận được cơ sở gần bù kề nhau cho đến khi đạt tới nghiệm chấp nhận được cơ sở bù hoặc đến khi gặp một tia (vô hạn) của miền xác định bởi (1.9) - (1.10). Với những giả thiết nhất định về ma trận M , thuật toán Lemke sẽ hội tụ sau hữu hạn bước tới một nghiệm chấp nhận được cơ sở bù của bài toán LCP (q, M ). Thuật toán Lemke giải bài toán LCP (q, M ) gồm các thủ tục sau: Khởi sự: Nếu q ≥ 0 thì dừng thuật toán: (z, w) = (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