Tài liệu Hiệu chỉnh bài toán bù tổng quát (tt)

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Ị THUÝ 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ố: 62 46 01 12 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2016 Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học 1: GS.TS. Nguyễn Bường Người hướng dẫn khoa học 2: TS. Nguyễn Công Điều Phản biện 1: PGS. TS. Cung Thế Anh Phản biện 2: PGS. TS. Tạ Duy Phượng Phản biện 3: TS. Nguyễn Minh Tuấn Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi .... giờ, ngày .... tháng .... năm 2016. Có thể tìm hiểu về luận án tại: - Thư viện Quốc gia - Thư viện Học viện Khoa học và Công nghệ - Trung tâm Thư viện, Trường Đại học Nội vụ Hà Nội 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, 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,... 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ự, đặ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}, n S̃2 = {x ∈ R : g(x) ≤ 0, h(x) ≤ 0, hg(x), h(x)iRq = 0}, (0.3) 2 n các hàm thực ϕ : R −→ 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 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). 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. đã 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. đã 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 3 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. 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ó 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, đó 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};
1 2 2 2 2 φM S (a, b) = ab+ max{0, a−αb} −a +max{0, b−αa} −b , α > 1; 2α √ φ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. Hàm φF B được gọi là hàm Fischer. 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 đã đư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. 4 và Fukushima M. 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 đố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) ở đâ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. 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 5 đ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; 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. Mục 3.2. trình bà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. Cuối chương là ví dụ số minh họa cho phương pháp nêu trên. 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ị Chương 1 của luận án giới thiệu những kiến thức cơ bản nhất phục vụ cho việc trình bày các kết quả nghiên cứu đạt được trong các chương sau. Cụ thể: Mục 1.1 đề cập đến 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. Mục 1.2 đề cập đến 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 định nghĩa về bài toán bù tuyến tính và một số phương pháp giải như: phương pháp Lemke, phương pháp dự đoán và hiệu chỉnh (Predictor-corrector); định nghĩa bài toán bù phi tuyến và một số phương pháp giải bài toán này trong trường hợp đơn điệu hoặc P0 - hàm. Chương 2 Bài toán bù tổng quát và phương pháp hiệu chỉnh 2.1. Vấn đề tồn tại nghiệm của bài toán bù tổng quát Định nghĩa 2.1 Bài toán bù tổng quát, ký hiệu bởi GCP (F, G), là bài toán tìm vectơ x ∈ Rn sao cho F (x) ≥ 0, G(x) ≥ 0, hF (x), G(x)i = 0, (2.1) trong đó F, G : Rn −→ Rn là các ánh xạ. 2.2. Hiệu chỉnh bài toán bù tổng quát 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 Để giải bài toán bù tổng quát, chúng tôi biến đổi (2.1) bằng cách đặt g(x) = −G(x), h(x) = −F (x) để đưa về bài toán: tìm x̃ ∈ Rn sao cho g(x̃) ≤ 0, h(x̃) ≤ 0, hg(x̃), h(x̃)iRm = 0, (2.2) ở đây, g(x), h(x) là hai hàm liên tục từ không gian Rn tới không gian Rm , tích vô hướng và chuẩn của Rn lần lượt được ký hiệu là h., .i và k.kRn ; y = (y1, y2, ..., ym) ≤ 0 có nghĩa là yi ≤ 0, i = 1, 2, ..., m. Trong trường hợp m = n, g(x) = −x và h(x) = −F (x) là một hàm liên tục trong Rn thì (2.2) chính là bài toán bù phi tuyến N CP (F ) đã xét trong Mục 1.3.2 ở Chương 1. Trước đây, bài toán này chỉ giải được khi F đơn điệu hoặc là P0 - hàm. Khắc phục nhược điểm này, chúng tôi đã đưa ra một phương pháp mới để giải bài toán (2.2) mà không cần g(x) và h(x) phải có các điều kiện trên. Chúng tôi cũng thiết lập tốc độ hội tụ của nghiệm hiệu chỉnh trong trường 9 hợp gi(x)hi(x) khả vi và có đạo hàm liên tục Lipschitz. Bằng cách đặt ϕi(x) = max{0, gi(x)}, i = 1, 2, ..., m, ϕm+i(x) = max{0, hi(x)}, i = 1, 2, ..., m, rõ ràng Si := {x ∈ Rn : gi(x) ≤ 0} = {x ∈ Rn : ϕi(x) = 0}, Sm+i := {x ∈ Rn : hi(x) ≤ 0} = {x ∈ Rn : ϕm+i(x) = 0}, với i = 1, 2, ..., m,. Hàm ϕj liên tục, không âm trên Rn và ϕj (y) = 0 ∀y ∈ ∩N j=1 Sj , j = 1, 2, ..., 2m := N. Hơn nữa n ∩N j=1 Sj = {x ∈ R : g(x) ≤ 0, h(x) ≤ 0}. Hiển nhiên hg(x̃), h(x̃)iRm = m X gi(x̃)hi(x̃) = 0 ⇐⇒ gi(x̃)hi(x̃) = 0, i = 1, m. i=1 Do đó, xét hàm fi(x) = gi(x)hi(x) và đặt S0 = x ∈ Rn : fi(x) = 0, i = 1, 2, ..., m .  (2.3) Bài toán (2.2) tương đương với việc tìm một phần tử x̃ thuộc ∩N i=0 Si hoặc thỏa mãn ϕj (x̃) = minn ϕj (x), j = 1, 2, ..., N, x∈R (2.4) và x̃ ∈ S0. Điều này có nghĩa là nghiệm x̃ của (2.2) thuộc giao giữa tập nghiệm của bài toán cực trị (2.4) và hệ phương trình (2.3). Phương pháp hiệu chỉnh Tikhonov cho (2.2) được xây dựng trên cơ sở giải bài toán cực trị với ràng buộc đẳng thức sau đây: tìm một phần tử x̃ ∈ Rn sao cho ϕj (x̃) = min ϕj (x), j = 1, 2, ..., N. x∈S0 10 Xét bài toán cực tiểu sau: tìm một phần tử xα ∈ Rn thỏa mãn Fα (xα ) = minn Fα (x), x∈R (2.5) ở đây Fα (x) xác định bởi Fα (x) = kF (x)k2Rm + N X αµj ϕj (x) + αkx − x∗k2Rn , j=1 0 ≤ µ1 < µj < µj+1 < 1, j = 2, ..., N − 1, F (x) = (f1(x), ..., fm(x))T , và x∗ là phần tử nào đó trong Rn. Bài toán (2.5) có nghiệm xα với mỗi α > 0. Chúng tôi đã chứng minh được sự hội tụ của nghiệm hiệu chỉnh và đánh giá được tốc độ hội tụ của nó thông qua định lí sau. Định lí 2.1 Cho αk → 0, khi k → ∞ thì mọi dãy {xk }, ở đây xk := xαk là nghiệm của (2.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ó x∗ - chuẩn nhỏ nhất (x∗ - MNS). Nếu x̃ có x∗ - MNS là duy nhất thì lim xk = x̃. k→∞ Định lí 2.2 Nếu các điều kiện dưới đây đúng i) F khả vi; 0 0 ii) tồn tại L > 0 sao cho kF (x̃ − F (z)kL(Rn,Rm) ≤ Lkx̃ − zkRn với z thuộc lân cận nào đó của x̃; 0 iii) tồn tại ω ∈ Rm sao cho x̃ − x∗ = F (x̃)∗ω; iv) LkωkRm < 1 thì √ kxk − x̃kRn = O( αk ). Chú ý 2.1 Khi các hàm gi(x) và hi(x) trơn, ta có thể thay công thức ϕj trong (2.5) bằng ϕ2j thì hàm Fα cũng trơn. Trong trường hợp {fi, ϕj } được cho lần lượt bởi các xấp xỉ liên tục {fiδ , ϕδj } sao cho | fi(x) − fiδ (x) |≤ δ, i = 1, 2, ..., m, | ϕj (x) − ϕδj (x) |≤ δ, j = 1, 2, ..., N, ∀x ∈ Rn, δ −→ 0. (2.6) 11 Dễ thấy, nếu gi, hi với các xấp xỉ của chúng lần lượt là giδ , hδi thỏa mãn điều kiện (2.6) và giới nội thì fi với xấp xỉ của nó là fiδ cũng thỏa mãn điều kiện này. Phương pháp hiệu chỉnh bài toán tối ưu không ràng buộc là: tìm một phần tử xδα ∈ Rn sao cho Fαδ (xδα ) = minn Fαδ (x), α > 0, δ ≥ 0, x∈R (2.7) ở đây Fαδ (x) xác định bởi Fαδ (x) = kF δ (x)k2Rm + N X αµj ϕδj (x) + αkx − x∗k2Rn , j=1 0 ≤ µ1 < µj < µj+1 < 1, j = 2, ..., N − 1,
T F δ (x) = f1δ (x), ..., fmδ (x) , phụ thuộc tham số α > 0. Với mỗi α > 0 bài toán (2.7) có một nghiệm ký hiệu bởi xδα . Trong trường hợp bài toán bù tổng quát có nhiễu, chúng tôi cũng chứng minh được các kết quả tương tự. Định lí 2.3 Cho αk , δk → 0, sao cho αδkk −→ 0 khi k → ∞ thì mọi dãy {xk }, ở đây xk := xδαkk là nghiệm của (2.7) với α, δ lần lượt 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ó x∗ - chuẩn nhỏ nhất (x∗ - MNS). Nếu nghiệm x̃ có x∗ - MNS là duy nhất thì lim xk = x̃. k→∞ Định lí 2.4 Nếu các điều kiện dưới đây đúng i) F khả vi; 0 0 ii) tồn tại L > 0 sao cho kF (x̃) − F (z)kL(Rn,Rm) ≤ Lkx̃ − zkRn với z thuộc lân cận nào đó của x̃; 0 ∗ iii) tồn tại ω ∈ Rm sao cho x̃ − x∗ = F (x̃) √ ω; iv) LkωkRm < 1 thì với cách chọn αk ∼ δk , ta có 1 kxk − x̃kRn = O(δk4 ). 12 Ở Định lí (2.1), nghiệm hiệu chỉnh hội tụ đến nghiệm của bài toán bù tổng quát khi nó có nghiệm x∗ − M N S duy nhất. Trong trường hợp nghiệm này không có tính chất đó thì làm thế nào? Một ý tưởng được đưa ra là cần khoanh một vùng nào đó để cho nghiệm x∗ − M N S nằm trong vùng đó là duy nhất. Chính vì vậy, trong mục tiếp theo chúng tôi xét bài toán bù tổng quát có ràng buộc là một tập đóng lồi. 2.2.2. Hiệu chỉnh bài toán bù tổng quát có ràng buộc Xét bài toán bù tổng quát có ràng buộc, ký hiệu bởi CGCP : đó là tìm một phần tử x̃ ∈ C : g(x̃) ≤ 0, h(x̃) ≤ 0, hg(x̃), h(x̃)iRm = 0, (2.8) ở đây C là tập đóng, lồi trong Rn. Đặt ϕi(x) = max{0, gi(x)}, i = 1, m, ϕm+i(x) = max{0, hi(x)}, i = 1, m. Rõ ràng Si := {x ∈ Rn : gi(x) ≤ 0} = {x ∈ Rn : ϕi(x) = 0}, i = 1, m, Si+m := {x ∈ Rn : hi(x) ≤ 0} = {x ∈ Rn : ϕm+i(x) = 0}, i = 1, m, hàm ϕj liên tục, không âm trên Rn. Ngoài ra, có ϕj (y) = 0 ∀y ∈ ∩N j=1 Sj , j = 1, ..., 2m := N, và n ∩N j=1 Sj = {x ∈ R : g(x) ≤ 0, h(x) ≤ 0}. Hiển nhiên hg(x̃), h(x̃)iRm = m X gi(x̃)hi(x̃) = 0 i=1 ⇐⇒ gi(x̃)hi(x̃) = 0, i = 1, ..., m. Xét hàm fi(x) = gi(x)hi(x) 13 và đặt S0 = {x ∈ Rn : fi(x) = 0, i = 1, ..., m}. (2.9) Bài toán CGCP (2.8) tương đương với việc tìm một phần tử x̃ thuộc C ∩ (∩N i=0 Si ) sao cho ϕj (x̃) = min x∈C∩(∩N i=0 Si ) ϕj (x), j = 1, ..., N, (2.10) Để giải bài toán cực trị, chúng tôi xét bài toán tối ưu vô hướng không ràng buộc sau: tìm một phần tử xα ∈ Rn sao cho Fα (xα ) = minn Fα (x), α > 0, x∈R (2.11) với Fα (x) xác định bởi Fα (x) = kx − PC (x)k2Rn + kF (x)k2Rm + N X αµj ϕj (x) + αkx − x∗k2Rn , j=1 (2.12) 0 ≤ µ1 < µj < µj+1 < 1, j = 2, ..., N − 1, F (x) = (f1(x), f2(x), ..., fm(x))T , ở đây PC (x) là phép chiếu mêtric của x ∈ Rn trên C và x∗ là phần tử nào đó trong Rn. Bài toán (2.11) có một nghiệm xα với mỗi α > 0. Chúng tôi đã thu được các kết quả sau. Định lí 2.5 Cho αk → 0, khi k → ∞ thì mọi dãy {xk }, ở đây xk := xαk là một nghiệm của (2.11)- (2.12) 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ó x∗ - C chuẩn nhỏ nhất (x∗ - CMNS). Nếu x̃ có x∗ - CMNS là duy nhất thì lim xk = x̃. k→∞ Định lí 2.6 Giả sử các điều kiện sau là đúng (i) F khả vi; (ii) tồn tại L > 0 sao cho kF 0(x̃) − F 0(z)kL(Rn,Rm) ≤ Lkx̃ − zkRn với z thuộc lân cận nào đó của x̃; 14 (iii) tồn tại ω ∈ R sao cho x̃ − x∗ = F 0(x̃)∗ω; (iv) LkωkRm < 1 thì √ kxk − x̃kRn = O( αk ). m 2.3. • • • • Một số bài toán dẫn tới bài toán bù Qui hoạch toàn phương Trò chơi song ma trận Cân bằng thị trường Ví dụ số minh họa Xét hai hàm: g(x1, x2) = (x21 + x22 − 25, −x1 + 3), h(x1, x2) = ((x1 − 3)2 + x22 − 4, x1 − 4), (2.13) và đặt C = C1 ∩ C2, xác định như sau: C1 = {(x1, x2) ∈ R2 : x1 − 4x2 + 1 ≤ 0}, C2 = {(x1, x2) ∈ R2 : 2x1 − x2 − 2 ≥ 0}. (2.14) Rõ ràng, với g và h như (2.13) √ thì bài toán (2.2) có√4 nghiệm: x1 = (3, −2), x2 = (3, 2), x3 = (4, 3) và x4 = (4, − 3). Tuy nhiên, khi có thêm ràng buộc là tập C = C1 ∩ C2 như (2.14) thì chỉ có √ x2 = (3, 2), x3 = (4, 3) là nghiệm của bài toán (2.8). Dễ thấy, x2 là nghiệm có x∗ - chuẩn nhỏ nhất. Chọn: µ1 = 161 , µ2 = 18 , µ3 = 14 và µ4 = 21 với x∗ = (0, 0). Tham số αk = (1 + k)−1 và điểm ban đầu đối với trường hợp k = 1 là x0 = (20; 45) ∈ / C. Ta cực tiểu hàm Tikhonov sau Fαk (x) = kx − PC (x)k2R2 + kF (x)k2R2 + 4 X µ αk j ϕej (x) + αk kx − x∗k2R2 , j=1 ở đây PC (x) = 12 [PC1 (x) + PC2 (x)], PCi (x) = x nếu x ∈ Ci và nếu x∈ / Ci thì PCi (x) = Pli (x) với li = {(x1, x2) : aix1 + bix2 = ci} và 15 ai, bi, ci là các hệ số, xác định trong (2.14), ( ϕe1(x) = ϕ1(x) = x21 + x22 − 25 nếu x21 + x22 − 25, 0 nếu x21 + x22 − 25 ≤ 0 ( ϕe2(x) = ϕ22(x) (x1 − 3)2 với x1 > 3 và x2 bất kỳ, 0 với x1 ≤ 3 và x2 bất kỳ, = ( ϕe3(x) = ϕ3(x) = (x1 − 3)2 + x22 − 4 nếu (x1 − 3)2 + x22 − 4 > 0, nếu (x1 − 3)2 + x22 − 4 ≤ 0 0 ( ϕe4(x) = ϕ24(x) = (x1 − 4)2 với x1 > 4 và x2 bất kỳ, 0 với x1 ≤ 4 và x2 bất kỳ. Có thể minh họa nghiệm của bài toán (2.8) như trong Hình 2.1 dưới đây. 16 Sử dụng phần mềm Free Pascal 3.0.0, chạy trên máy tính Core(TM) 2 Duo CPU 2.40GHz, RAM 2.00GB, chúng tôi đã thu được kết quả hội tụ nghiệm của bài toán (2.8) như trong Bảng 2.1 dưới đây. Bảng 2.1. Nghiệm của bài toán (2.8) k 1 10 20 40 50 60 70 80 90 100 200 400 500 600 700 900 1000 2000 3000 4000 6000 8000 9000 10000 x1 1.01992063 1.71908025 2.41207633 2.74195141 2.79533460 2.95653678 2.96117518 2.96121390 2.96131472 2.96158636 2.98441308 2.99083157 2.99197165 2.99258702 2.99318066 2.99646964 2.99662425 2.99844812 2.99893707 2.99913864 2.99946858 2.99957490 2.99966381 2.99969765 x2 0.26863164 1.53345569 1.91106017 1.98316305 1.98941417 1.99951405 1.99961309 1.99961604 1.99961848 1.99962029 1.99993344 1.99997458 1.99998085 1.99998295 1.99998239 1.99999060 1.99999600 1.99999896 1.99999940 1.99999963 1.99999977 1.99999986 1.99999988 1.99999988 Qua kết quả tính toán, ta thấy nghiệm hiệu chỉnh của bài toán (2.8) hội tụ rất gần tới nghiệm x2 = (3, 2) có x∗ - chuẩn nhỏ nhất. 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 3.1. Phát biểu bài toán Định nghĩa 3.1 Bài toán cực trị với ràng buộc là bài toán bù hay bài toán cân bằng được ký hiệu là MPEC, đó là bài toán tìm: min f (x) (3.1) với các ràng buộc g̃i(x) ≤ 0, ∀i = 1, 2, ..., m, h̃i(x) = 0, ∀i = 1, 2, ..., p, ĝi(x) ≥ 0, ĥi(x) ≥ 0, hĝi(x), ĥi(x)i = 0, ∀i = 1, 2, ..., q, ở đây f, g̃i, h̃i, ĝi, ĥi : Rn −→ R là các hàm khả vi liên tục. 3.2. Phương pháp hiệu chỉnh Tikhonov cho bài toán đặt ra Để giải bài toán cực trị với ràng buộc là bài toán bù tổng quát, ta đặt g(x) = −ĝ(x), h(x) = −ĥ(x) và xét bài toán cực trị: tìm một phần tử x̃ ∈ C ∩ S̃, thỏa mãn điều kiện ϕ(x̃) = min ϕ(y), (3.2) y∈C∩S̃ ở đâ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)iRm = 0 ,  (3.3) 18 n các hàm thực ϕ : R −→ R, g̃ : Rn −→ Rm, h̃ : Rn −→ Rp, g và h : Rn −→ Rq là liên tục. Chúng tôi giả thiết tập nghiệm của (3.2)-(3.3) khác rỗng. Khi S̃2 = Rn (3.2)-(3.3) là bài toán cực trị phi tuyến có ràng buộc tổng quát. Bài toán này đã được N. Bường giải bằng phương pháp hiệu chỉnh Tikhonov cho bài toán cực tiểu không ràng buộc như sau F̃α (xα ) = minn F̃α (x), α > 0, x∈R F̃α (x) = kF̃ (x)k2Rp + m X αµj ψj (x) + αµm+1 ϕ(x) (3.4) j=1 + αkx − x∗k2Rn , 0 ≤ µ1 < µ2 < ... < µm+1 < 1 ở đây T F̃ (x) = f˜1(x), f˜2(x), ..., f˜p(x) , f˜i = h̃i(x)
và ψj (x) = max{0, g̃j (x)}. Tiếp theo, để cải tiến (3.4), chúng tôi đưa ra phương pháp hiệu chỉnh mới kiểu Tikhonov cho MPEC (3.2)-(3.3). Để làm điều này, ta đặt: ϕj (x) = max{0, g̃j (x)}, j = 1, 2, ..., m, ϕm+j (x) = max{0, gj (x)}, j = 1, 2, ..., q, ϕm+q+j (x) = max{0, hj (x)}, j = 1, 2, ..., q, fi(x) = h̃i(x), i = 1, 2, ..., p, fp+i(x) = gi(x)hi(x), i = 1, 2, ..., q. Theo giả thiết, g̃, h̃, g, h liên tục, hàm ϕj và fi xác định như trên, với j = 1, 2, ..., N (:= m + 2q) và i = 1, 2, ..., M (:= p + q) là liên tục. Dễ chỉ ra rằng n  n Sj := x ∈ R : g̃j (x) ≤ 0} = {x ∈ R : ϕj (x) = 0 , j = 1, m, Sm+j := x ∈ Rn : gj (x) ≤ 0} = {x ∈ Rn : ϕm+j (x) = 0 , j = 1, q,   n n Sm+q+j := x ∈ R : hj (x) ≤ 0} = {x ∈ R : ϕm+q+j (x) = 0 , j = 1, q do ϕj (x) ≥ 0 với mọi x ∈ Rn và j = 1, 2, ..., N . Ta xét tập S0 := x ∈ Rn : h̃(x) = 0, hg(x), h(x)iRn = 0 .