Phương pháp Newton nửa trơn cho bài toán bù phi tuyến

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

Thêm vào BST

Báo xấu

13
lượt xem 3
download

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

Bài viết Phương pháp Newton nửa trơn cho bài toán bù phi tuyến trình bày phương pháp Newton nửa trơn để giải phương trình không trơn. Phương pháp được chứng minh có tốc độ hội tụ bậc hai địa phương đến nghiệm của bài toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phương pháp Newton nửa trơn cho bài toán bù phi tuyến

62 Dương Xuân Hiệp, Phạm Quý Mười, Phan Đức Tuấn PHƯƠNG PHÁP NEWTON NỬA TRƠN CHO BÀI TOÁN BÙ PHI TUYẾN SEMISMOOTH NEWTON METHOD FOR NONLINEAR COMPLEMENTARITY PROBLEMS Dương Xuân Hiệp1, Phạm Quý Mười2, Phan Đức Tuấn2* 1 Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam 2 Trường Đại học Sư phạm – Đại học Đà Nẵng Tác giả liên hệ: pdtuan@ued.udn.vn (Nhận bài: 30/4/2022; Chấp nhận đăng: 29/8/2022) Tóm tắt - Trong bài báo này, nhóm tác giả nghiên cứu phương Abstract - In this paper, we study the semismooth Newton pháp Newton nửa trơn cho bài toán bù phi tuyến trong không gian method for nonlinear complementarity problem in space ℝ𝑛 . ℝ𝑛 . Sử dụng hàm NCP 𝜙(𝑎, 𝑏) = min{𝑎, 𝑏}, nhóm tác giả chuyển Using NCP function 𝜙(𝑎, 𝑏) = min{𝑎, 𝑏}, we rewrite the bài toán bù phi tuyến về bài toán tìm nghiệm của phương trình problem as a nonsmooth equation in space ℝ𝑛 . In order to apply không trơn trong không gian ℝ𝑛 . Để có thể áp dụng được phương the semismooth Newton method to this nonsmooth equation, we pháp Newton nửa trơn cho phương trình không trơn vừa nhận study the Newton differentiability of NCP function and the được, nghiên cứu tính khả vi Newton của hàm số NCP cũng như function on the right hand side of the equation. The inverse hàm số ở bên trái của phương trình này. Tính khả nghịch và bị property and boundedness of Newton derivative of the function chặn của đạo hàm Newton của hàm số được chứng minh với một on the right hand side of the equation is obtained under some số điều kiện phù hợp. Từ đó, trình bày phương pháp Newton nửa mild conditions. Then, we present the semismooth Newton trơn để giải phương trình không trơn. Phương pháp được chứng method to solve the equation. The method is proved to have the minh có tốc độ hội tụ bậc hai địa phương đến nghiệm của bài toán. local convergence rate of second order. This is a main result in Đây là kết quả chính của bài báo này. this paper. Từ khóa - Đạo hàm Newton; Khả vi Newton; đạo hàm Newton Key words - Newton Derivative; Newton differential; Strong mạnh; Khả vi Newton mạnh; Phương pháp Newton nửa trơn Newton Derivative; Strong Newton differential; Semismooth Newton method 1. Đặt vấn đề sớm nhất là của Harker và Pang [10] và được phát triển bởi Trong bài báo này, nhóm tác giả kí hiệu 𝐼 = {1,2, . . . , 𝑛} Kanzow [11]. Tuy nhiên, với cách chọn hàm Φ(𝑥) gồm các và nghiên cứu bài toán bù phi tuyến 𝑁𝐶𝑃(𝐹) như sau: Tìm hàm thành phần là 𝜙(𝑎, 𝑏) = min{𝑎, 𝑏}, các bài viết này chỉ 𝑥 ∈ ℝ𝑛 thỏa mãn mới nghiên cứu cho bài toán bù phi tuyến với 𝐹 là hàm tuyến tính. Một cách tiếp cận khác là sử dụng hàm Φ gồm các hàm 𝑥𝑖 ≥ 0, 𝐹𝑖 (𝑥) ≥ 0, 𝑥𝑖 𝐹𝑖 (𝑥) = 0, ∀𝑖 ∈ 𝐼, (1) thành phần là 𝜙(𝑎, 𝑏) = √𝑎2 + 𝑏 2 − (𝑎 + 𝑏) của Fisher- Trong đó, hàm số 𝐹: ℝ𝑛 → ℝ𝑛 xác định bởi Burmeister, xem trong [3, 4]. Sau này, giải thuật được cải 𝐹(𝑥) = (𝐹1 (𝑥), 𝐹2 (𝑥), . . . , 𝐹𝑛 (𝑥)) là hàm khả vi liên tục và tiến để nhận được sự hội tụ toàn cục cũng như tốc độ hội tụ 𝑥 = (𝑥1 , 𝑥2 , . . . , 𝑥𝑛 ) ∈ ℝ𝑛 . tuyến tính bởi Luca [6], Qi [12], Facchine và Soares [2]. Một Bài toán bù phi tuyến được áp dụng trong rất nhiều ứng trong những ưu điểm của phương pháp này là có thể áp dụng dụng như nghiên cứu các toán tử, hệ cân bằng kinh tế cũng linh hoạt cho các bài toán bù phi tuyến 𝑁𝐶𝑃(𝐹). như trong khoa học kĩ thuật và được giới thiệu lần đầu trong Cách tiếp cận thứ hai được sử dụng rộng rãi trong luận án tiến sĩ của Cottle năm 1964. Phương pháp thường những năm gần đây là xấp xỉ hàm Φ(𝑥) bởi hàm Φ𝜇 (𝑥) dùng để giải bài toán bù phi tuyến này là đưa về bài toán với 𝜇 > 0, được gọi là tham số trơn hóa, thỏa mãn tìm nghiệm của phương trình tương đương. Sau đó, sử lim𝜇→0 Φ𝜇 (𝑥) = Φ(𝑥). Từ đây, thay vì giải hệ Φ(𝑥) = 0, dụng phương pháp số để tìm nghiệm của phương trình này. Một trong các phương pháp thường được sử dụng là đưa ta giải hệ Φ𝜇 (𝑥) = 0. Phương pháp này có những ưu điểm bài toán 𝑁𝐶𝑃(𝐹) về giải hệ phương trình Φ(𝑥) = 0 của là có thể áp dụng trực tiếp giải thuật Newton để tìm nghiệm Mangasarian được giới thiệu trong [1] và sử dụng giải thuật trực tiếp của bài toán. Đến nay, đã có rất nhiều bài báo sử Newton để tìm nghiệm. dụng phương pháp này như Kanzow [5, 13]. Hiện nay, có một số kỹ thuật để đưa bài toán 𝑁𝐶𝑃(𝐹) về Kỹ thuật để đưa bài toán bù phi tuyến 𝑁𝐶𝑃(𝐹) về bài bài toán giải hệ Φ(𝑥) = 0 trong đó hàm Φ(𝑥) được chọn toán tìm nghiệm của phương trình phi tuyến là sử dụng hàm khác nhau, xem [2, 3, 4, 5, 6, 7]. Tuy nhiên, các hàm Φ đều 𝑁𝐶𝑃. Hàm 𝑁𝐶𝑃 là một ánh xạ 𝜑: ℝ2 → ℝ có tính chất là các hàm không trơn nên người ta cần mở rộng giải thuật 𝜑(𝑎, 𝑏) = 0 ⇔ 𝑎 ≥ 0, 𝑏 ≥ 0, 𝑎𝑏 = 0. Newton cho bài toán 𝑁𝐶𝑃(𝐹). Cách tiếp cận thứ nhất là sử Trong bài báo này, nhóm tác giả sẽ dùng một hàm 𝑁𝐶𝑃 dụng giải thuật Newton nửa trơn cho hàm Φ(𝑥) dựa trên cụ thể. Đó là hàm 𝜑 xác định bởi khái niệm dưới vi phân của Clarke [8], của Qi và Sun [9]. Một trong những giải thuật Newton nửa trơn được đưa ra 𝜑(𝑎, 𝑏) = 𝑚𝑖𝑛{𝑎, 𝑏}. (2) 1 Vietnam Academy of Science and Technology - Institute of Mathematics (Duong Xuan Hiep) 2 The University of Danang - University of Science and Education (Pham Quy Muoi, Phan Duc Tuan)
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ - ĐẠI HỌC ĐÀ NẴNG, VOL. 20, NO. 9, 2022 63 𝑛 𝑛 Lúc này, nếu ta định nghĩa toán tử Φ: ℝ → ℝ xác lim ||𝑓(𝑥+ℎ)−𝑓(𝑥)−𝐹(𝑥+ℎ)ℎ|| = 0, (4) ||ℎ|| định bởi ℎ→0 𝑛 𝜑(𝑥1 , 𝐹1 (𝑥)) Trong đó, ℒ(Ω, ℝ ) là tập các phiếm hàm tuyến tính liên Φ(𝑥) = ( ⋮ ), (3) tục từ Ω vào ℝ𝑛 . Khi đó, 𝐹 được gọi là một đạo hàm 𝜑(𝑥n , 𝐹𝑛 (𝑥)) Newton của 𝑓 tại 𝑥. thì ta có: 𝑥 ∗ là nghiệm của bài toán 𝑁𝐶𝑃(𝐹) khi và chỉ khi Định nghĩa 2.2 Cho 𝑈 là một tập mở của Ω ⊂ ℝ𝑛 và 𝑓 𝑥 ∗ là nghiệm của phương trình Φ(𝑥) = 0. Vì vậy, giải bài là một ánh xạ xác định trên Ω. Ánh xạ 𝑓: Ω → ℝ𝑛 được gọi toán 𝑁𝐶𝑃(𝐹) tương đương với việc giải phương trình phi là khả vi Newton mạnh tại 𝑥 ∈ 𝑈 nếu tồn tại ánh xạ tuyến Φ(𝑥) = 0. 𝐹: 𝑈 → ℒ(Ω, ℝ𝑛 ) sao cho ||𝑓(𝑥+ℎ)−𝑓(𝑥)−𝐹(𝑥+ℎ)ℎ|| Trong các phần tiếp theo của bài báo, nhóm tác giả sẽ Lim = 0. (5) ℎ→0 ||ℎ||2 trình bày phương pháp Newton nửa trơn để giải phương trình Φ(𝑥) = 0 với Φ là hàm cho bởi (3). Khi đó, 𝐹 được gọi là một đạo hàm Newton mạnh của 𝑓 tại 𝑥. 2. Một số tính chất của toán tử 𝚽 Định lí 2.1 Hàm 𝜑 xác định bởi (2) khả vi Newton mạnh Bổ đề 2.1 Hàm 𝜑 xác định bởi (2) là hàm liên tục tại mọi điểm với đạo hàm Newton mạnh cho bởi ma trận Lipschitz và khả vi theo hướng tại mọi điểm trong ℝ2 . cỡ 1 × 2 sau: Chứng minh. Trước hết, dễ dàng nhận thấy hàm 𝜑 xác 𝐺(𝑦) = (𝜑1 (𝑦) 𝜑2 (𝑦)), định bởi (2) có thể được biểu diễn dưới dạng trong đó 𝑦 = (𝑦1 , 𝑦2 ) ∈ ℝ2 , 1 𝜑(𝑎, 𝑏) = [𝑎 + 𝑏 − |𝑎 − 𝑏|]. 1, 𝑛ế𝑢 𝑦1 < 𝑦2 , 2 Khi đó với mọi 𝑥 = (𝑎1 , 𝑏1 ); 𝑦 = (𝑎1 , 𝑏2 ) ∈ ℝ2 , ta có: 𝜑1 (𝑦) = 𝜑1 (𝑦1 , 𝑦2 ) = {0, 𝑛ế𝑢 𝑦1 > 𝑦2 , 1 |𝜑(𝑥) − 𝜑(𝑦)| , 𝑛ế𝑢 𝑦1 = 𝑦2 2 1 và ≤ [|(𝑎1 − 𝑎2 ) + (𝑏1 − 𝑏2 )| + |𝑎1 − 𝑏1 | − |𝑎2 − 𝑏2 |] 2 0, 𝑛ế𝑢 𝑦1 < 𝑦2 , 1 ≤ (|(𝑎1 − 𝑎2 ) + (𝑏1 − 𝑏2 )| + |(𝑎1 − 𝑎2 ) − (𝑏1 − 𝑏2 )|) 𝜑2 (𝑦) = 𝜑2 (𝑦1 , 𝑦2 ) = {1, 𝑛ế𝑢 𝑦1 > 𝑦2 , 2 1 , 𝑛ế𝑢 𝑦1 = 𝑦2 . 1 2 ≤ (|(𝑎1 − 𝑎2 ) + (𝑏1 − 𝑏2 )| + |(𝑎1 − 𝑎2 ) − (𝑏1 − 𝑏2 )|) Chứng minh. Ta sẽ chứng minh 𝐺(𝑦) ∈ ℒ(Ω, ℝ𝑛 ). Thật 2 1 vậy, 𝐺(𝑦)(⋅) là một phiếm hàm tuyến tính và ≤ . 2√2√(𝑎1 − 𝑎2 )2 + (𝑏1 − 𝑏2 )2 Nếu 𝑦1 < 𝑦2 thì 2 ≤ √2|𝑥 − 𝑦|. ||𝐺(𝑦)|| = sup ||𝐺(𝑦)ℎ|| ≤ 1. ||ℎ||=1 Do đó, hàm 𝜑 xác định bởi (2) là hàm liên tục Lipschitz Nếu 𝑦1 > 𝑦2 thì tương tự như trên, ta có ||𝐺(𝑦)|| ≤ 1. với hằng số Lipschitz 𝐿 = √2. Nếu 𝑦1 = 𝑦2 thì Tiếp theo, ta sẽ chứng minh hàm 𝜑 xác định bởi (2) là 1 khả vi theo hướng tại mọi điểm 𝑥 = (𝑎, 𝑏) ∈ ℝ2 với đạo ||𝐺(𝑦)|| = sup ||𝐺(𝑦)ℎ|| = . ||ℎ||=1 2 hàm theo hướng 𝑑 = (𝑑1 , 𝑑2 ) ∈ ℝ2 xác định bởi 𝑛 Vậy, ta có 𝐺 ∈ ℒ(Ω, ℝ ) và ||𝐺(𝑦)|| ≤ 1 với mọi 𝑦. 𝑑1 , nếu 𝑎 < 𝑏, 𝜑 ′ (𝑥; 𝑑) = {𝑑2 , nếu 𝑎 > 𝑏, Tiếp theo, sẽ chứng minh 𝐺 là một đạo hàm Newton mạnh của 𝜑. Thật vậy, với mỗi 𝑦 = (𝑦1 , 𝑦2 ) ∈ ℝ2 và min{𝑑1 , 𝑑2 }, nếu 𝑎 = 𝑏. ℎ = (ℎ1 , ℎ2 ) ∈ ℝ2 . Nếu 𝑎 < 𝑏 thì ta có thể chọn 𝜆 → 0+ đủ bé sao cho Nếu 𝑦1 < 𝑦2 thì vì ℎ → 0 nên ta có thể chọn ℎ sao cho 𝑎 + 𝜆𝑑1 < 𝑏 + 𝜆𝑑2 . Khi đó, 𝑦1 + ℎ1 < 𝑦2 + ℎ2 . Khi đó, |𝜑(𝑥+𝜆𝑑)−𝜑(𝑥)| 𝜑 ′ (𝑥; 𝑑) = lim+ = lim+ 𝑑1 = 𝑑1 . ||𝜑(𝑦+ℎ)−𝜑(𝑦)−𝐺(𝑦+ℎ)ℎ|| 𝜆→0 𝜆 𝜆→0 lim ℎ→0 ||ℎ||2 Do đó, 𝜑 ′ (𝑥; 𝑑) = 𝑑1 . Tương tự, nếu 𝑎 > 𝑏 thì ||(𝑦1 +ℎ1 )−𝑦1 −ℎ1 || ′ 𝜑 (𝑥; 𝑑) = 𝑑2 . = lim = 0. ℎ→0 ||ℎ||2 Nếu 𝑎 = 𝑏 thì Nếu 𝑦1 > 𝑦2 tương tự như trên ta có thể chọn ℎ sao cho ′ |𝜑(𝑥+𝜆𝑑)−𝜑(𝑥)| 𝑦1 + ℎ1 > 𝑦2 + ℎ2 . Khi đó, ta cũng thu được 𝜑 (𝑥; 𝑑) = lim+ 𝜆→0 𝜆 ||𝜑(𝑦+ℎ)−𝜑(𝑦)−𝐺(𝑦+ℎ)ℎ|| [(𝑑1 +𝑑2 )−|𝑑1 −𝑑2 |] lim = 0. ℎ→0 ||ℎ||2 = lim+ = min{𝑑1 , 𝑑2 }. 𝜆→0 2 Nếu 𝑦1 = 𝑦2 thì ta xét các trường hợp sau: Vậy, Bổ đề 2.1 được chứng minh. Trường hợp ℎ1 < ℎ2 : Định nghĩa 2.1 Cho 𝑈 là một tập mở của Ω ⊂ ℝ𝑛 và 𝑓 ||𝜑(𝑦+ℎ)−𝜑(𝑦)−𝐺(𝑦+ℎ)ℎ|| là một ánh xạ xác định trên Ω. Ánh xạ 𝑓: Ω → ℝ𝑛 được gọi lim ℎ→0 ||ℎ||2 là khả vi Newton tại 𝑥 ∈ 𝑈 nếu tồn tại ánh xạ ||(𝑦1 +ℎ1 )−𝑦1 −ℎ1 || 𝐹: 𝑈 → ℒ(Ω, ℝ𝑛 ) sao cho = lim = 0. ℎ→0 ||ℎ||2
64 Dương Xuân Hiệp, Phạm Quý Mười, Phan Đức Tuấn Trường hợp ℎ1 > ℎ2 : tương tự như trên. Nếu 𝑥𝑖 + 𝜔𝑖 > 𝐹𝑖 (𝑥 + 𝜔) thì tương tự trường hợp Trường hợp ℎ1 = ℎ2 : 𝑖 ∈ 𝛽, ta có ||𝜑(𝑦+ℎ)−𝜑(𝑦)−𝐺(𝑦+ℎ)ℎ|| |𝑀𝑖 | lim lim = 0. ℎ→0 ||ℎ||2 𝜔→0 ||𝜔|| 1 ||(𝑦1 +ℎ1 )−𝑦1 − (ℎ1 +ℎ2 )|| Nếu 𝑥𝑖 + 𝜔𝑖 = 𝐹𝑖 (𝑥 + 𝜔), thì ta có 2 = lim 2 = 0. |𝑀𝑖 | ℎ→0 ||ℎ|| lim 𝜔→0 ||𝜔|| Do vậy 𝐺 là một đạo hàm Newton mạnh của hàm 𝜑 xác 1 1 𝜕𝐹𝑖 định bởi (2) tại mọi điểm. |𝐹𝑖 (𝑥+𝜔)−𝐹𝑖 (𝑥)− 𝜔𝑖 − ∑𝑛 𝜔 | 2 𝑖=1 2 𝜕𝑥𝑗 𝑗 = lim Định lí 2.2 Hàm 𝛷 xác định bởi 𝜔→0 ||𝜔|| 1 1 𝜕𝐹𝑖 𝜑(𝑥1 , 𝐹1 (𝑥)) |2(𝐹𝑖 (𝑥+𝜔)−𝐹𝑖 (𝑥)−2 ∑𝑛 𝑖=1 𝜕𝑥 𝜔𝑗 )| 𝑗 𝛷(𝑥) = ( ⋮ ), = lim = 0. 𝜔→0 ||𝜔|| 𝜑(𝑥𝑛 , 𝐹𝑛 (𝑥)) Do đó, trong tất cả các trường hợp ta đều có khả vi Newton mạnh tại mọi điểm 𝑥 ∈ ℝ𝑛 với đạo hàm ||Φ(𝑥+𝜔)−Φ(𝑥)−Φ′ (𝑥+𝜔)𝜔|| Newton mạnh cho bởi lim 𝜔→0 ||𝜔|| 𝛷 ′ (𝑥) = 𝐴(𝑥) + 𝐵(𝑥)𝐹 ′ (𝑥), (6) ≤ ∑𝑛𝑖=1 lim |𝑀𝑖 | = 0. 𝜔→0 ||𝜔|| Trong đó 𝜑1 (𝑥1 , 𝐹1 (𝑥)) … 0 Vậy Φ′ xác định bởi (6) là một đạo hàm Newton mạnh 𝐴(𝑥) = (⋮ ⋱ ⋮ ), của hàm Φ. 0 … 𝜑1 (𝑥𝑛 , 𝐹𝑛 (𝑥)) Định nghĩa 2.3 Một ma trận 𝑀 ∈ ℝ𝑛×𝑛 được gọi là 𝜑2 (𝑥1 , 𝐹1 (𝑥)) … 0 𝑃-ma trận nếu với mỗi 𝑥 ∈ ℝ𝑛 \{0}, tồn tại một tập chỉ số 𝐵(𝑥) = (⋮ ⋱ ⋮ ), 𝑖0 = 𝑖0 (𝑥) ⊂ 𝐼 sao cho 𝑥𝑖0 [𝑀𝑥]𝑖0 > 0. 0 … 𝜑2 (𝑥𝑛 , 𝐹𝑛 (𝑥)) Định lí 2.3 Giả sử 𝐹 ′ (𝑥) là một 𝑃-ma trận. Khi đó, đạo và hàm Newton của 𝛷 xác định bởi (6) khả nghịch. 𝜕𝐹𝑖 Chứng minh. Dễ thấy 𝐴(𝑥) và 𝐵(𝑥) là các ma trận 𝐹 ′ (𝑥) = ( ) 𝑙à 𝑚𝑎 𝑡𝑟ậ𝑛 𝐽𝑎𝑐𝑜𝑏𝑖 𝑐ủ𝑎 𝑓 𝑡ạ𝑖 𝑥. đường chéo xác định dương. Hơn nữa 𝐴(𝑥) + 𝐵(𝑥) xác 𝜕𝑥𝑗 Chứng minh. Với mỗi 𝑥 ∈ ℝ𝑛 và 𝜔 ∈ ℝ𝑛 , xét hiệu định dương nên với giả thiết 𝐹 ′ (𝑥) là 𝑃 −ma trận, theo Φ(𝑥 + 𝜔) − Φ(𝑥) − Φ′ (𝑥 + 𝜔)𝜔. Bằng cách khai triển Định lí 2.7 trong [13] ta có điều phải chứng minh. và tính toán trực tiếp ta thu được vectơ biểu diễn hiệu trên Trong [14], ta đã biết rằng với 𝐴, 𝐵 là các ma trận vuông với hàng thứ 𝑖 xác định bởi và 𝐶 là một ma trận có chiều thích hợp thì 𝑀𝑖 = 𝜑(𝑥𝑖 + 𝜔𝑖 , 𝐹𝑖 (𝑥 + 𝜔)) − 𝜑(𝑥𝑖 , 𝐹𝑖 (𝑥)) (𝐴 + 𝐶𝐵𝐶 𝑇 )−1 = 𝐴−1 − 𝐴−1 𝐶(𝐵−1 + 𝐶 𝑇 𝐴−1 𝐶)−1 𝐶 𝑇 𝐴−1 . −𝜑1 (𝑥𝑖 + 𝜔𝑖 , 𝐹𝑖 (𝑥 + 𝜔))𝜔𝑖 Xét ma trận vuông khối có dạng 𝜕𝐹𝑖 𝐴 𝐵 −𝜑2 (𝑥𝑖 + 𝜔𝑖 , 𝐹𝑖 (𝑥 + 𝜔)) ∑𝑛𝑗=1 𝜔𝑗 . 𝑀=( ), (7) 𝜕𝑥𝑗 𝐶 𝐷 Đặt Trong đó, 𝐴, 𝐵, 𝐶, 𝐷 lần lượt là các ma trận cỡ 𝛼 = {𝑗|𝑥𝑗 < 𝐹𝑗 (𝑥)}, 𝑘 × 𝑚, 𝑘 × 𝑛, 𝑙 × 𝑚 và 𝑙 × 𝑛 sao cho 𝑘 + 𝑙 = 𝑚 + 𝑛. Khi đó, theo [15] và [16] ta có mệnh đề sau: 𝛽 = {𝑗|𝑥𝑗 > 𝐹𝑗 (𝑥)}, Mệnh đề 2.1 (i) Giả sử 𝐴 khả nghịch. Khi đó, ma trận 𝛾 = {𝑗|𝑥𝑗 = 𝐹𝑗 (𝑥)}. khối 𝑀 xác định bởi (7) khả nghịch khi và chỉ khi phần bù Ta xét các trường hợp sau: Schur 𝐷 − 𝐶𝐴−1 𝐵 của 𝐴 khả nghịch và Với 𝑖 ∈ 𝛼, chọn 𝜔 đủ bé sao cho 𝑥𝑖 + 𝜔𝑖 < 𝐹𝑖 (𝑥 + 𝜔), 𝑚11 𝑚12 𝑀−1 = (𝑚 ), ta có: 21 𝑚22 |𝑀𝑖 | |𝑥𝑖 +𝜔𝑖 −𝑥𝑖 −𝜔𝑖 | trong đó lim = lim = 0. 𝜔→0 ||𝜔|| 𝜔→0 ||𝜔|| 𝑚11 = 𝐴−1 + 𝐴−1 𝐵(𝐷 − 𝐶𝐴−1 𝐵)−1 𝐶𝐴−1 , Với 𝑖 ∈ 𝛽, chọn 𝜔 đủ bé sao cho 𝑥𝑖 + 𝜔𝑖 > 𝐹𝑖 (𝑥 + 𝜔), 𝑚12 = −𝐴−1 𝐵(𝐷 − 𝐶𝐴−1 𝐵)−1 , ta có: 𝑚21 = −(𝐷 − 𝐶𝐴−1 𝐵)−1 𝐶𝐴−1 , 𝜕𝐹 |𝐹𝑖 (𝑥+𝜔)−𝐹𝑖 (𝑥)−∑𝑛 𝑖 𝑗=1 𝜕𝑥 𝜔𝑗 | |𝑀𝑖 | 𝑗 𝑚22 = (𝐷 − 𝐶𝐴−1 𝐵)−1 . lim = lim = 0. 𝜔→0 ||𝜔|| 𝜔→0 ||𝜔|| (ii) Giả sử 𝐷 là ma trận khả nghịch. Khi đó, ma trận do 𝐹𝑖 là các hàm khả vi. khối 𝑀 xác định bởi (7) khả nghịch khi và chỉ khi phần bù Với 𝑖 ∈ 𝛾, ta có Schur 𝐴 − 𝐵𝐷 −1 𝐶 của 𝐷 khả nghịch và Nếu 𝑥𝑖 + 𝜔𝑖 < 𝐹𝑖 (𝑥 + 𝜔) thì tương tự trường hợp 𝑚11 𝑚12 𝑀−1 = (𝑚 ), 𝑖 ∈ 𝛼, ta có 21 𝑚22 |𝑀𝑖 | trong đó lim = 0. 𝜔→0 ||𝜔|| 𝑚11 = (𝐴 − 𝐵𝐷 −1 𝐶)−1 ,
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ - ĐẠI HỌC ĐÀ NẴNG, VOL. 20, NO. 9, 2022 65 −1 −1 −1 𝑑𝛼 = 𝑦𝛼 𝑚12 = −(𝐴 − 𝐵𝐷 𝐶) 𝐵𝐷 , ′ ′ ′ 𝑚21 = −𝐷 −1 𝐶(𝐴 − 𝐵𝐷 −1 𝐶)−1 , ⇔ {𝐹𝛽𝛽 𝑑𝛽 + 𝐹𝛽𝛾 𝑑𝛾 = 𝑦𝛽 − 𝐹𝛽𝛼 𝑑𝛼 ′ ′ ′ 𝑚22 = 𝐷 −1 + 𝐷 −1 𝐶(𝐴 − 𝐵𝐷 −1 𝐶)−1 𝐵𝐷 −1 . 𝐹𝛾𝛽 𝑑𝛽 + (𝐹𝛾𝛾 + 𝐼𝛾𝛾 )𝑑𝛾 = 2𝑦𝛾 − 𝐹𝛾𝛼 𝑑𝛼 Với mỗi 𝑥 = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ∈ ℝ𝑛 và Từ đây suy ra Φ′ khả nghịch khi và chỉ khi hệ phương 𝐹 = (𝐹1 , 𝐹2 , … , 𝐹𝑛 ), ta kí hiệu các tập chỉ số như sau trình ′ ′ ′ 𝛼 = {𝑖 ∈ 𝐼|𝑥𝑖 < 𝐹𝑖 (𝑥)}, 𝐹𝛽𝛽 𝑑𝛽 + 𝐹𝛽𝛾 𝑑𝛾 = 𝑦𝛽 − 𝐹𝛽𝛼 𝑑𝛼 { ′ ′ ′ 𝛽 = {𝑖 ∈ 𝐼|𝑥𝑖 > 𝐹𝑖 (𝑥)}, 𝐹𝛾𝛽 𝑑𝛽 + (𝐹𝛾𝛾 + 𝐼𝛾𝛾 )𝑑𝛾 = 2𝑦𝛾 − 𝐹𝛾𝛼 𝑑𝛼 𝛾 = {𝑖 ∈ 𝐼|𝑥𝑖 = 𝐹𝑖 (𝑥)}. có nghiệm duy nhất. Hơn nữa, hệ trên có nghiệm duy nhất Cho M là một ma trận vuông cấp cấp 𝑛. Ta kí hiệu 𝑀𝛼𝛽 khi và chỉ khi ma trận khối ′ ′ là ma trận con của 𝑀 ứng với các hàng 𝛼 và các cột 𝛽. Từ 𝐹𝛽𝛽 𝐹𝛽𝛾 𝑀=( ′ ) đây, ta định nghĩa các ma trận con của ma trận Jacobi 𝐹𝛾𝛽 𝐹𝛾𝛾 ′ + 𝐼𝛾𝛾 𝜕𝐹𝑖 𝐹 ′ (𝑥) = ( ) = (𝐹𝑖𝑗′ ) của 𝑓 tại 𝑥: khả nghịch. Do đó, ma trận của đạo hàm Φ′ khả nghịch khi 𝜕𝑥𝑗 1≤𝑖,𝑗≤𝑛 và chỉ khi ma trận khối 𝑀 xác định ở trên khả nghịch. Theo ′ 𝐹𝜇𝜌 = (𝐹𝑖𝑗′ ), 𝑖 ∈ 𝜇, 𝑗 ∈ 𝜌, Định lí 2.1 ta có các kết luận (i) và (ii). với 𝜇, 𝜌 là tập các chỉ số của ma trận Jacobi 𝐹 ′ (𝑥). 3. Phương pháp Newton nửa trơn Khi đó, tính khả nghịch của ma trận ′ ′ Trong phần này, nhóm tác giả trình bày giải thuật 𝐹𝛽𝛽 (𝑥) 𝐹𝛽𝛾 (𝑥) 𝑀(𝑥) = ( ′ ), Newton nửa trơn cho bài toán bù phi tuyến. Giải thuật được ′ 𝐹𝛾𝛽 (𝑥) 𝐹𝛾𝛾 (𝑥) + 𝐼𝛾𝛾 mô tả như sau: Chọn 𝑥 0 ∈ ℝ𝑛 . Với mỗi 𝑘 ≥ 0, xét dãy {𝑥 𝑘 } được đưa ra trong định lí sau. xác định bởi Định lí 2.4 (i) Nếu với mỗi 𝑥 ∈ ℝ𝑛 , 𝐹𝛽𝛽 ′ (𝑥) khả nghịch 𝑥 𝑘+1 = 𝑥 𝑘 − Φ′ (𝑥 𝑘 )Φ(𝑥 𝑘 ). ′ và phần bù Schur của 𝐹𝛽𝛽 (𝑥) khả nghịch thì 𝛷 ′ (𝑥) xác Giả thiết 1 Cho Ω ⊂ ℝ𝑛 là tập mở khác rỗng. Xét ma định bởi (6) khả nghịch. trận ′ ′ (ii) Nếu với mỗi 𝑥 ∈ ℝ𝑛 , 𝐹𝛾𝛾 ′ (𝑥) + 𝐼𝛾𝛾 khả nghịch và 𝐹𝛽𝛽 (𝑥) 𝐹𝛽𝛾 (𝑥) 𝑀(𝑥) = ( ′ ′ ), phần bù Schur của 𝐹𝛾𝛾 (𝑥) + 𝐼𝛾𝛾 khả nghịch thì 𝛷 ′ (𝑥) xác ′ 𝐹𝛾𝛽 (𝑥) 𝐹𝛾𝛾 (𝑥) + 𝐼𝛾𝛾 định bởi (6) khả nghịch. với 𝛽 = {𝑖 ∈ 𝐼|𝑥𝑖 > 𝐹𝑖 (𝑥)}, 𝛾 = {𝑖 ∈ 𝐼|𝑥𝑖 = 𝐹𝑖 (𝑥)}. Giả sử Chứng minh. Với mỗi 𝑥 ∈ ℝ𝑛 , ta có một trong hai điều kiện sau đây thỏa mãn ′ 𝜑1 (𝑥𝑖 , 𝐹𝑖 (𝑥)) = 1, 𝜑2 (𝑥𝑖 , 𝐹𝑖 (𝑥)) = 0, ∀𝑖 ∈ 𝛼, • 𝐹𝛽𝛽 (𝑥) khả nghịch và bị chặn đều trên Ω. Phần bù ′ 𝜑1 (𝑥𝑖 , 𝐹𝑖 (𝑥)) = 0, 𝜑2 (𝑥𝑖 , 𝐹𝑖 (𝑥)) = 1, ∀𝑖 ∈ 𝛽, Schur của 𝐹𝛽𝛽 (𝑥) khả nghịch và bị chặn đều trên Ω. 1 1 ′ 𝜑1 (𝑥𝑖 , 𝐹𝑖 (𝑥)) = , 𝜑2 (𝑥𝑖 , 𝐹𝑖 (𝑥)) = , ∀𝑖 ∈ 𝛾. • 𝐹𝛾𝛾 (𝑥) + 𝐼𝛾𝛾 khả nghịch và bị chặn đều trên Ω. Phần bù 2 2 ′ Schur của 𝐹𝛾𝛾 (𝑥) + 𝐼𝛾𝛾 khả nghịch và bị chặn đều trên Ω. Do đó, để đơn giản các kí hiệu ta viết lại các ma trận 𝐴(𝑥), 𝐵(𝑥), 𝐹 ′ (𝑥), Φ′ (𝑥) dưới dạng Định lí 3.1 Giả sử Giả thiết 1 thỏa mãn. Khi đó, đạo 𝐼𝛼 0 0 hàm 𝛷 ′ (𝑥) khả nghịch với mọi 𝑥 ∈ Ω và [𝛷 ′ (𝑥)]−1 bị chặn đều trên 𝐷. Hơn nữa 𝐴(𝑥): = 𝐴 = (0 0𝛽 0 ), ′ 1 3+∥ 𝐹𝛽𝛼 (𝑥) ∥ 0 0 𝐼 2 𝛾 ||𝛷 ′ (𝑥)−1 || ≤ 1+∥ 𝑀−1 (𝑥) ∥ ( ′ ), +∥ 𝐹𝛾𝛼 (𝑥) ∥ 0𝛼 0 0 trong đó 𝐵(𝑥): = 𝐵 = (0 𝐼𝛽 0 ), ′ 𝐹𝛽𝛽 ′ (𝑥) 𝐹𝛽𝛾 (𝑥) 1 0 0 𝐼𝛾 𝑀(𝑥) = ( ′ ′ ), 2 𝐹𝛾𝛽 (𝑥) 𝐹𝛾𝛾 (𝑥) + 𝐼𝛾𝛾 ′ ′ ′ 𝐹𝛼𝛼 𝐹𝛼𝛽 𝐹𝛼𝛾 ′ ′ ′ và 𝐹 ′ (𝑥): = 𝐹 ′ = (𝐹𝛽𝛼 𝐹𝛽𝛽 𝐹𝛽𝛾 ), 𝛼 = {𝑖 ∈ 𝐼|𝑥𝑖 < 𝐹𝑖 (𝑥)}, ′ ′ ′ 𝐹𝛾𝛼 𝐹𝛾𝛽 𝐹𝛾𝛾 𝛽 = {𝑖 ∈ 𝐼|𝑥𝑖 > 𝐹𝑖 (𝑥)}, Φ𝛼′ 𝛾 = {𝑖 ∈ 𝐼|𝑥𝑖 = 𝐹𝑖 (𝑥)}. ′ Φ (𝑥): = Φ = (Φ𝛽 ). ′ ′ Chứng minh. Theo Định lí 2.4, Φ′ (𝑥) khả nghịch. Phần Φ𝛾′ còn lại của định lí được chứng minh tương tự như chứng Khi đó, với 𝑑, 𝑦 ∈ ℝ𝑛 bất kì, ta có minh của Bổ đề 3.6 trong [17] và Bổ đề 3.4 trong [18]. Thật Φ′ 𝑑 = 𝑦 vậy, với 𝑑, 𝑦 ∈ ℝ𝑛 sao cho Φ′ (𝑥)𝑑 = 𝑦, từ chứng minh của Định lí 2.4 và tính khả nghịch của Φ′ (𝑥), ta có 𝑑𝛼 = 𝑦𝛼 ′ ′ ′ 𝑑𝛼 ⇔ {𝐹𝛽𝛼 𝑑𝛼 + 𝐹𝛽𝛽 𝑑𝛽 + 𝐹𝛽𝛾 𝑑𝛾 = 𝑦𝛽 𝑦𝛼 1 1 1 1 (Φ′ (𝑥))−1 𝑦 = 𝑑 = (𝑑𝛽 ) = ( −1 ), ′ 𝑑𝛾 + 𝐹𝛾𝛼 ′ 𝑑𝛼 + 𝐹𝛾𝛽 ′ 𝑑𝛽 + 𝐹𝛾𝛾 𝑑𝛾 = 𝑦𝛾 𝑀 (𝑥)𝑁(𝑥) 2 2 2 2 𝑑𝛾
66 Dương Xuân Hiệp, Phạm Quý Mười, Phan Đức Tuấn trong đó Lời cảm ơn: Một số kết quả trong bài báo này được tác giả ′ 𝑦𝛽 − 𝐹𝛽𝛼 (𝑥)𝑦𝛼 Dương Xuân Hiệp nghiên cứu trong thời gian học thạc sĩ 𝑁(𝑥) = ( ′ ). tại Viện toán học, Viện khoa học và công nghệ Việt Nam. 2𝑦𝛾 − 𝐹𝛾𝛼 (𝑥)𝑦𝛼 Tác giả Dương Xuân Hiệp xin gửi lời cảm ơn Quỹ Unesco Từ đó suy ra đã hỗ trợ trong đề tài nghiên cứu dành cho tài năng trẻ mã 𝑦𝛼 số ICRTM03_2021.03. ∥ Φ′ (𝑥))−1 𝑦 ∥= ‖( −1 )‖ 𝑀 (𝑥)𝑁(𝑥) ≤∥ 𝑦𝛼 ∥ +∥ 𝑀−1 (𝑥) ∥∥ 𝑁(𝑥) ∥. TÀI LIỆU THAM KHẢO Hơn nữa, [1] Q.L. Mangasarian and M.V. Solodov, “Nonlinear complementarity ′ ′ as unconstrained and constrained minimization”, Mathematical ∥ 𝑁(𝑥) ∥≤∥ 𝑦𝛽 − 𝐹𝛽𝛼 (𝑥)𝑦𝛼 ∥ +∥ 2𝑦𝛾 − 𝐹𝛾𝛼 (𝑥)𝑦𝛼 ∥ Programming, 62(1), 1993, 277-297. ′ ≤∥ 𝑦𝛽 ∥ +∥ 𝐹𝛽𝛼 ′ (𝑥) ∥∥ 𝑦𝛼 ∥ +2 ∥ 𝑦𝛾 ∥ +∥ 𝐹𝛾𝛼 (𝑥) ∥∥ 𝑦𝛼 ∥. [2] F. Facchinei and J. Soares, “A new merit function for nonlinear complementarity problems and a related algorithm”, SIAM Journal Do đó, on Optimization, 7(1), 1997, 226-247. [3] A. Fisher, “A special newton-type optimization method”, ∥ (Φ′ (𝑥))−1 𝑦 ∥ Optimization, 24(3-4), 1992, 269-284. ′ ≤∥ 𝑦𝛼 ∥ +∥ 𝑀−1 (𝑥) ∥ (∥ 𝑦𝛽 ∥ +∥ 𝐹𝛽𝛼 (𝑥) ∥∥ 𝑦𝛼 ∥ [4] A. Fisher, “Solution of monotone complementarity problems with locally lipschitzian function”, Mathematical Programming, 76(3), ′ +2 ∥ 𝑦𝛾 ∥ +∥ 𝐹𝛾𝛼 (𝑥) ∥∥ 𝑦𝛼 ∥) 1996, 513-532. ′ [5] C. Kanzow, “Nonlinear complementarity as unconstrained ≤ (1+∥ 𝑀−1 (𝑥) ∥ (1+∥ 𝐹𝛽𝛼 ′ (𝑥) ∥ +2+∥ 𝐹𝛾𝛼 (𝑥) ∥)) ∥ 𝑦 ∥ optimization”, Journal of Optimization theory and apllications, ′ 88(1), 1996, 139-155. ≤ (1+∥ 𝑀−1 (𝑥) ∥ (3+∥ 𝐹𝛽𝛼 ′ (𝑥) ∥ +∥ 𝐹𝛾𝛼 (𝑥) ∥)) ∥ 𝑦 ∥. [6] T.D. Luca, F. Facchinei, and C. Kanzow, “A semismooth equation approach to the solution of nonlinear complementarity problems”, Định lí 3.2 Giả sử hàm 𝐹 thỏa mãn Giả thiết 1. Khi đó, Mathematical programming, 75(3), 1996, 407-439. với 𝑥 0 ∈ ℝ𝑛 đủ gần nghiệm 𝑥 ∗ ∈ Ω của phương trình [7] Q.L. Mangasarian and M.V. Solodov, “Nonlinear complementarity 𝛷(𝑥) = 0 thì giải thuật Newton nửa trơn xác định bởi as unconstrained and constrained minimization”, Mathematical Programming, 62(1), 1993, 277-297. 𝑥 𝑘+1 = 𝑥 𝑘 − [𝛷 ′ (𝑥 𝑘 )]−1 𝛷(𝑥 𝑘 ), [8] F.H. Clarke, Optimization and nonsmooth analysis, Society for hội tụ bậc hai về nghiệm 𝑥 ∗ . Industrial an Applied Mathematics Philadelphia, 1990. Chứng minh. Vì Giả thiết 1 được thỏa mãn nên tồn tại [9] L. Qi and J. Sun, “A nonsmooth verson of newton’s method”, Mathematical Programming, 58(1), 1993, 353–367. 𝑀 > 0 sao cho ∥ [Φ(𝑥)]−1 ∥≤ 𝑀 với mọi 𝑥 ∈ Ω. [10] P.T. Harker and J.S. Pang, “A damped-newton method for the linear Mặt khác, vì Φ là hàm khả vi Newton mạnh nên tồn tại complementarity problem”, Lectures in applied mathematics, 26, 𝜖 ∈ (0,1) sao cho với mọi 𝑥 ∈ 𝐵(𝑥 ∗ , 𝜖) ta có 1990, 265-284. 𝜖 [11] A. Fischer and C. Kanzow, “On finite termination of an iterative ∥ Φ(𝑥) − Φ(𝑥 ∗ ) − Φ′(𝑥)(𝑥 − 𝑥 ∗ ) ∥≤ ∥ 𝑥 − 𝑥 ∗ ∥2 . method for linear complementarity problems”, Mathematical 𝑀 Programming, 74, 1996, 279-292. Khi đó, với 𝑥0 ∈ 𝐵(𝑥 ∗ , 𝜖) và giả sử 𝑥𝑘 ∈ 𝐵(𝑥 ∗ , 𝜖), ta có [12] H. Jiang and L. Qi, “A new nonsmooth equations approach to ∥ 𝑥𝑘+1 − 𝑥 ∗ ∥ nonlinear complementarity problems”, Journal on Control and Optimization, 35(1), 1997, 178–193. =∥ 𝑥𝑘 − 𝑥 ∗ − [Φ′ (𝑥 𝑘 )]−1 Φ(𝑥 𝑘 ) + [Φ′ (𝑥 𝑘 )]−1 Φ(𝑥 ∗ ) ∥ [13] C. Kanzow and H. Kleinmichel, “A new class of semismooth newton- ≤ ‖[Φ′ (𝑥 𝑘 )]−1 ‖ ∥ Φ(𝑥𝑘 ) − Φ(𝑥 ∗ ) − Φ′(𝑥𝑘 )(𝑥𝑘 − 𝑥 ∗ ) ∥ type methods for nonlinear complementarity problems”, 𝜖 Computational Optimization and Applications, 11(1), 1998, 227-251. ≤𝑀 ∥ 𝑥𝑘 − 𝑥 ∗ ∥2 = 𝜖 ∥ 𝑥𝑘 − 𝑥 ∗ ∥2 . [14] D.P. Bertsekas, Constrained optimization and Lagrange multiplier 𝑀 method, Academic Press, 1982. Điều này chỉ ra rằng, 𝑥𝑘+1 ∈ 𝐵(𝑥 ∗ , 𝜖) và dãy {𝑥𝑘 } hội [15] Z. Fuzhen, The Schur complement and its application, Springer tụ bậc hai về nghiệm 𝑥 ∗ . Science and Business Media, 2005. [16] L.T. Tzer and S.H. Shiou, “Inverses of 2x2 block matrics”, An 4. Kết luận International Journal Computers and Mathematics with Trong bài báo này, đã trình bày giải thuật Newton nửa Application, 43(1-2), 2002, 119-29. trơn cho bài toán bù phi tuyến. Nhóm tác giả sử dụng hàm [17] P.Q. Muoi, D.N. Hao, P. Maass, and M. Pidcock, “Semismooth newton and quasi-newton methods in weighted 𝑙1 -regularization”, NCP 𝜙(𝑎, 𝑏) = min{𝑎, 𝑏} để đưa bài toán bù phi tuyến về Journal of Inverse and Ill-posed Problems, 21(5), 2013, 665-693. bài toán tìm nghiệm của phương trình Φ(𝑥) = 0. Nghiên [18] P.Q. Muoi, D.N. Hao, S.K. Sahoo, D. Tang, N.H Cong, and D. cứu chứng minh rằng, hàm Φ khả vi Newton mạnh và Cuong, “Inverse problems with nonnegative and sparse solutions: phương pháp Newton nửa trơn hội tụ địa phương bậc hai đến algorithms and application to the phase retrieval problem”, Inverse nghiệm của phương trình nếu Giả thiết 1 được thỏa mãn. Problems, 34(5), 2018, 055007.