Tóm tắt luận văn Thạc sĩ Toán học: Phương pháp giải tích biến phân cho bài toán Fermat – Torricelli suy rộng

Chia sẻ: Huyen Nguyen My | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

16
lượt xem 3
download

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

Luận văn trình bày các kết quả của B. Mordukhovich và N. M. Nam đăng trên tạp chí J. Optim. Theory Appl. 148 (2011), 431-454, giải bài toán Fermat - Torricelli suy rộng cho hữu hạn tập đóng về điều kiện tối ưu cho điểm Fermat - Torricelli suy rộng và từ đó xây dựng thuật toán dưới gradient để xác định điểm Fermat - Torricelli.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ Toán học: Phương pháp giải tích biến phân cho bài toán Fermat – Torricelli suy rộng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG NGUYỄN THỊ GIANG PHƯƠNG PHÁP GIẢI TÍCH BIẾN PHÂN CHO BÀI TOÁN FERMAT – TORRICELLI SUY RỘNG TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp toán sơ cấp Mã số: 8 46 01 13 HÀ NỘI, 2018
Công trình được hoàn thành tại: Trường đại học Thăng Long NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. ĐỖ VĂN LƯU Phản biện 1: TS. Nguyễn Đạt Đăng Phản biện 2: TS. Nguyễn Công Sứ Luận văn được bảo vệ trước Hội đồng chấm luận văn tại: Trường đại học Thăng Long Vào hồi 14 giờ 00 ngày 28 tháng 12 năm 2018
Mở đầu 1. Lí do chọn đề tài Vào đầu thế kỷ 17, nhà toán học Pháp Pierre de Fermat (1601-1665) đã đặt ra toán sau đây:" Cho trước ba điểm trên mặt phẳng .Tìm một điểm thứ tư sao cho tổng khoảng cách Euclid từ điểm này tới ba điểm đã cho là nhỏ nhất." Bài toán của Fermat đã được Evangelista Torricelli (1608-1646) giải và từ đó bài toán được gọi là bài toán Fermat - Torricelli. Lời giải của Torricelli cho bài toán Fermat - Torricelli như sau: Nếu các góc trong của tam giác nhỏ hơn 120o thì điểm cần tìm là điểm trong tam giác nhìn các cạnh của tam giác dưới một góc 1200 . Nếu một trong các góc trong của tam giác không nhỏ hơn 120o thì đỉnh của góc lớn nhất chính là lời giải của bài toán. Điểm này được gọi là điểm Fermat-Torricelli. Torricelli đã giải bài toán bằng phương pháp hình học như sau (Hình 1): Ba điểm cho trước là A, B, C. Ta dựng các tam giác đều ∆ABD, ∆BCE, ∆ACF phía ngoài ∆ABC. Dựng các đường tròn ngoại tiếp các tam giác ∆ABD, ∆BCE, ∆ACF . Ba đường tròn này cắt nhau tại điểm P . Điểm P là điểm Fermat - Torricelli. 2
Hình 1: Cách dựng điểm Torricelli Vào thế kỷ 19 Jakob Steiner đã mở rộng bài toán này cho một số hữu hạn điểm trên mặt phẳng. N. M. Nam, N. Hoang và N.T. An [5] đã sử dụng dưới vi phân hàm lồi để nghiên cứu bài toán Fermat - Torricelli suy rộng, trong đó các điểm được thay thế bằng các hình cầu Euclid. Như vậy, bài toán được xét trong [5] gồm một số hữu hạn tập lồi và công cụ sử dụng là dưới vi phân hàm lồi. Luận văn cao học của H.T.T. Linh [2] đã trình bày cách giải bài toán Fermat - Torricelli với hữu hạn hình cầu Euclid bằng công cụ dưới vi phân hàm lồi. Chú ý rằng các hình cầu Euclid là các tập lồi. B. Mordukhovich và N. M. Nam [3] đã sử dụng dưới vi phân Mor- dukhovich để nghiên cứu bài toán Fermat - Torricelli suy rộng, trong đó thay thế các điểm bằng các tập đóng, bằng phương pháp giải tích biến phân. Như vậy, bài toán được xét trong [3] gồm hữu hạn tập đóng không nhất thiết lồi, công cụ được sử dụng là dưới vi phân Mordukhovich. B. Mordukhovich và N. M. Nam [3] đã nghiên cứu thiết lập các điều kiện tối ưu bài toán Fermat - Torricelli và sử dụng các kết quả đó để xác định điểm Fermat - Torricelli bằng thuật toán dưới gradient. Bài toán Fermat 3
- Torricelli giải bằng công cụ giải tích biến phân hiện đại và dưới vi phân Mordukhovich là đề tài được nhiều tác giả quan tâm nghiên cứu trong toán sơ cấp. Chính vì vậy tôi chọn đề tài "Phương pháp giải tích biến phân cho bài toán Fermat - Torricelli suy rộng" 2. Nội dung đề tài Luận văn trình bày các kết quả của B. Mordukhovich và N. M. Nam [3] đăng trên tạp chí J. Optim. Theory Appl. 148 (2011), 431-454, giải bài toán Fermat - Torricelli suy rộng cho hữu hạn tập đóng về điều kiện tối ưu cho điểm Fermat - Torricelli suy rộng và từ đó xây dựng thuật toán dưới gradient để xác định điểm Fermat - Torricelli. Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục các tài liệu tham khảo. 4
Chương 1 Giải tích biến phân Chương 1 trình bày bài toán Fermat - Torricelli suy rộng với hữu hạn tập đóng và một số kiến thức cơ bản về giải tích biến phân bao gồm dưới vi phân hàm lồi, -dưới vi phân, dưới vi phân Fréchet, dưới vi phân Mordukhovich của hàm thời gian tối thiểu. 1.1. Phát biểu bài toán Fermat - Torricelli suy rộng với hữu hạn tập đóng Chúng ta phát biểu bài toán Fermat - Torricelli suy rộng. Xét hàm thời gian tối thiểu (minimal time function): TΩF (x) := inf{t ≥ 0| Ω ∩ (x + tF ) 6= ∅}. (1.1) với hệ động lực x˙ ∈ F được mô tả bởi một tập lồi đóng bị chặn khác rỗng (F 6= ∅) của không gian Banach X, với tập mục tiêu đóng Ω 6= ∅ trong X. Khi F là hình cầu đơn vị đơn vị đóng B của X thì hàm thời gian tối thiểu trở thành hàm khoảng cách thông thường: d(x; Ω) := inf{kx − ωk, ω ∈ Ω} (1.2) sinh bởi chuẩn k · k trong X. Bây giờ ta cho một số bất kỳ các tập đóng Ωi 6= ∅, i = 1, . . . , n, của X. 5
Khi đó, bài toán Fermat - Torricelli suy rộng được phát biểu như sau: n X min T (x) := TΩFi (x), x ∈ X. (1.3) i=1 Nếu F = B (hình cầu đơn vị đóng của X) trong (1.3), bài toán Fermat - Torricelli suy rộng trở thành n X min D(x) := d(x; Ωi ). (1.4) i=1 Bài toán này quy về bài toán mở rộng kiểu Steiner của bài toán Fermat- Torricelli trong không gian Banach khi các tập Ωi (i = 1, · · · , n) có một phần tử. Chú ý rằng, ngay cả trường hợp cổ điển thì bài toán tối ưu (1.3) và đặc biệt hóa (1.4) của nó đều là các bài toán không trơn. Như vậy, một cách tư nhiên dẫn đến việc nghiên cứu bài toán Fermat - Torricelli suy rộng bằng công cụ giải tích biến phân. Giả sử X là một không gian Banach, X ∗ là không gian đối ngẫu tô pô của X. Cho ánh xạ đa trị G : X ⇒ X ∗ . Giới hạn trên dãy Painlevé- Kuratowski khi x → x được xác định bởi ω∗ n Limsupx→x G(x) := x∗ ∈ X ∗ | tồn tại các dãy xk → x, x∗k → x∗ khi k → ∞ o ∗ ∗ sao cho xk ∈ G(xk ) với mọi k ∈ N := {1, 2, . . . } , Ω trong đó ω ∗ kí hiệu tô pô yếu của X ∗ . Với tập Ω ⊂ X, kí hiệu x → x nghĩa là x → x với x ∈ Ω. Nếu ϕ : X → R := (−∞; +∞]là một hàm ϕ giá trị thực mở rộng, hưũ hạn tại x, kí hiệu x → x nghĩa là x → x với ϕ(x) → ϕ(x). 1.2. Giải tích biến phân Cho hàm lồi ϕ : X → R, x ∈ domϕ := {x ∈ X|ϕ(x) < ∞}. Dưới vi phân của ϕ tại x theo nghĩa giải tích lồi là tập ∂ϕ(x) = {x∗ ∈ X ∗ |hx∗ , x − xi ≤ ϕ(x) − ϕ(x), ∀x ∈ X}. (1.5) 6
Từ định nghĩa (1.5) ta có quy tắc Fermat cho hàm lồi như sau : x là cực tiểu của ϕ nếu và chỉ nếu 0 ∈ ∂ϕ(x). (1.6) Định lí 1.1 (Quy tắc tổng dưới vi phân cho hàm lồi) Giả sử ϕi : X → R ,(i = 1, . . . , m) là các hàm lồi nửa liên tục dưới trên không gian Banach X .Giả sử tồn tại một điểm x ∈ ∩ni=1 domϕi sao cho tất cả các hàm ϕ1 , . . . , ϕm là liên tục (có thể trừ ra một hàm) . Khi đó ta có đẳng thức Xm Xm ∂( ϕi )(x) = ∂ϕi (x) i=1 i=1 Cho một tập lồi Ω ⊂ X và x ∈ Ω nón pháp tuyến của Ω tại x được xác định bởi N (x, Ω) := {x∗ ∈ X| < x∗ , x − x >≤ 0, ∀x ∈ X}. (1.7) Đây chính là dưới vi phân (1.5) của hàm chỉ δ(x, Ω) tại x  0, nếu x ∈ Ω, δ(x, Ω) := ∞, nếu x ∈/ Ω. Cấu trúc lồi thích hợp cho bài toán Fermat - Torricelli suy rộng trong trường hợp các tập Ωi lồi. Ta sẽ nghiên cứu bài toán Fermat - Torricelli suy rộng với các tập Ωi không lồi. Cho hàm giá trị thực mở rộng ϕ : X → R hữu hạn tại x và ≥ 0. -Dưới vi phân của ϕ tại x được xác định bởi n ∗ ∗ ϕ(x) − ϕ(x)− < x∗ , x − x > o ∂ ϕ(x) := x ∈ X | lim inf b ≥ − . (1.8) x→x kx − xk Với = 0 thì ∂ϕ(x) b := ∂b0 ϕ(x) là dưới vi phân Fréchet của ϕ tại x. Dưới vi phân Fréchet quy về gradient cổ điển {∇ϕ(x)} khi ϕ khả vi Fréchet tại điểm này và quy về dưới vi phân (1.5) khi ϕ là hàm lồi. ∂ϕ(x) b có thể bằng rỗng và công thưc tương tự cho quy tắc tổng của Định lý 1.1 không đúng cho ∂ϕ(x) b khi ≥ 0; chẳng hạn ϕ1 (x) = |x| và ϕ2 (x) = −|x|. Ta định nghĩa dưới vi phân Mordukhovich của ϕ tại x như sau: ∂ϕ(x) := Limsupx−− →x ∂ ϕ(x). ϕ b (1.9) ε↓0 7
Ta cũng có thể định nghĩa tương đương bằng cách đặt = 0 trong (1.9), nếu ϕ là nửa liên tục dưới trong một lân cận của x và không gian X là không gian Asplund, tức là mỗi không gian con tách được thì cũng có đối ngẫu tách được. Chú ý rằng trong trường hợp hàm lồi, hàm dưới vi phân Mordukhovich và dưới vi phân theo nghĩa giải tích lồi là trùng nhau. Vì vậy, trong trường hợp lồi ta đều ký hiệu các dưới vi phân là ∂. Nón pháp tuyến Mordukhovich của tâp Ω trong X tại x ∈ Ω có thể xác định qua dưới vi phân (1.9) của hàm chỉ N (x, Ω) = ∂δ(x; Ω). Nón pháp tuyến Mordukhovich quy về nón pháp tuyến (1.7) cho các tập lồi. Định nghĩa nón pháp tuyến Mordukhovich có thể viết tương đương dưới dạng: N (x; Ω) := lim sup N c (x; Ω) (1.10) ϕ x−−→x ε↓0 trong đó với ≥ 0, các tập -pháp tuyến N c (·; Ω) được xác định bởi ∗ c (x; Ω) := {x∗ ∈ X ∗ | lim sup < x , x − x > ≤ }, x ∈ Ω. N (1.11) Ω x→x kx − xk Chú ý rằng N c (x; Ω) = ∅ nếu x ∈ / Ω. Khi tập Ω đóng địa phương ở gần điểm x và không gian X là Asplund, ta có thể thay thế tương đương bởi N c (·; Ω) trong (1.10) bằng nón pháp tuyến Fréchet Nb (·; Ω) := N c0 (·; Ω). Hơn nữa, trong trường hợp X = Rn , nón pháp tuyến (1.10) có dạng N (x; Ω) = Limsupx→x [cone(x − Π(x; Ω)], (1.12) trong đó Π(x; Ω) là phép chiếu Ơclit điểm x ∈ Rn lên tập đóng Ω, coneΩ là tập của các tia sinh ra trên Ω . Mặc dù các dưới vi phân (1.9) và nón pháp tuyến (1.10) không lồi, nhưng ta cúng có các qui tắc tính tốt, đặc biệt là trong không gian Asplund. Qui tắc tổng sau đây cho dưới vi phân (1.9) được sử dụng trong luận văn. Định lí 1.2 (Quy tắc tổng dưới vi phân Mordukhovich cho các hàm không lồi) 8
Giả sử ϕi : X → R (i = 1, . . . , m) là các hàm nửa liên tục dưới trên không gian Asplund X . Giả sử tất cả các hàm là Lipschtz địa phương (có thể trừ một hàm) tại x ∈ ∩m i=1 domϕi . Khi đó, ta có bao hàm thức n P n P ∂( ϕi )(x) ⊂ ∂ϕi (x). i=1 i=1 Các ví dụ sau đây minh họa cho các dưới vi phân Fréchet và dưới vi phân Mordukhovich. Ví dụ 1.1 a) Cho hàm f (x) = −|x|. Ta có ∂f b (0) = ∅, ∂f (0) = [−1, 1]. b) Cho hàm f (x) = −|x|3/2 . Khi đó, ∂f b (0) = ∂f (0) = {∇f (0)} = {0}. Ví dụ 1.2  x2 sin 1 , nếu x 6= 0, x f (x) = 0, nếu x = 0. b (0) = {∇f (0)} = {0}, ∂f (0) = [−1, 1]. Khi đó, ∂f 1.3. Dưới vi phân Mordukhovich của hàm thời gian tối thiểu Phần này sẽ trình bày một số kết quả về dưới vi phân Mordukhovich trong [4] dùng cho bài toán Fecmat-Torricelli suy rộng (1.3). Ta sẽ trình bày kết quả của dưới vi phân Mordukhovich cho cả hai trường hợp lồi và không lồi. Ta nói x ∈ X là một điểm trong tập (in-set point) của hàm thời gian tối thiểu (1.1) nếu x ∈ Ω và x là một điểm ngoài tập (out-of-set point) của (1.1) nếu x ∈/ Ω .Kết quả cho mối quan hệ cho dưới vi phân Mordukhovich của hàm thời gian tối thiểu và nón pháp tuyến Mordukhovich tại các điểm trong tập. Định lí 1.3 (Dưới vi phân Mordukhovich của hàm thời gian tối thiểu và nón pháp tuyến Mordukhovich tại các điểm trong tập) 9
Giả sử x ∈ Ω với hàm thơì gian tối thiểu (1.1) trên không gian Banach X và tập mức tựa C ∗ ⊂ X ∗ được xác định như sau: C ∗ := {x∗ ∈ X ∗ |σF (−x∗ ) ≤ 1} (1.13) qua hàm tựa của hệ động được cho bởi σF (x∗ ) := sup < x∗ , x >, x∗ ∈ X ∗ . (1.14) x∈F Khi đó, ta có ước lượng trên dưới vi phân ∂TΩF (x) ⊂ N (x; Ω) ∩ C ∗ . (1.15) Hơn nữa, (1.15) trở thành đẳng thức ∂TΩF (x) = N (x; Ω) ∩ C ∗ (1.16) nếu tập mục tiêu Ω lồi. Kết quả tiếp theo cho một ước lượng trên của dưới vi phân Mor- dukhovich của hàm thời gian tối thiểu không lồi tại các điểm ngoài tập qua dưới vi phân Mordukhovich của hàm cỡ Minkowski: ρF (x) := inf{t ≥ 0|x ∈ tF }, x ∈ X (1.17) với hệ động F và qua nón pháp tuyến Mordukhovich của hàm mục tiêu Ω tại các điểm thuộc vào hình chiếu thời gian tối thiểu của x ∈ / Ω được xác định bởi ΠFΩ (x) := (x + TΩF (x)F ) ∩ Ω. (1.18) Dễ thấy rằng phép chiếu suy rộng (1.18) qui về phép chiếu mêtric thông thường khi F = B, tức là khi (1.1) trở thành hàm khoảng cách (1.2). Nhắc lại rằng hàm thời gian tối thiểu (1.1) được gọi là đặt chỉnh tại x∈/ Ω với TΩF (x < ∞ nếu với bất kỳ dãy xk → x với TΩF (xk ) → TΩF (x) khi k → ∞, tồn tại dãy điểm hình chiếu ωk ∈ ΠFΩ (xk ) chứa một dãy con hội tụ . Các điều kiện sau đây là điều kiện đủ cho tính đặt chỉnh: • Mục tiêu Ω là tập con compact của X; • Không gian X hữu hạn chiều và Ω là tập con đóng của X; 10
• X là phản xạ ,Ω ⊂ X lồi đóng và hàm cỡ Minkowski sinh ra một chuẩn Kadec trên X, tức là sao cho sự hội tụ yếu và sự hội tụ chuẩn là như nhau trên biên của hình cầu đơn vị của X. Sau đây là một kết quả về ước lượng trên [4, Định lý 6.3]. Định lí 1.4 () Giả sử x ∈ / Ω với TΩF (x) < ∞, và hàm thời gian tối thiểu (1.1) đặt chỉnh tại x. Khi đó, ta có ước lượng trên [ ∂TΩF (x) ⊂ [−∂ρF (ω − x) ∩ N (ω; Ω)]. (1.19) ω∈ΠF Ω (x) Trong trường hợp hàm thời gian tối thiểu (1.1) là lồi, tính lồi của hàm thời gian tối thiểu tương đương với tính lồi của tập mục tiêu Ω (xem [4], Mệnh đề 3.6). Đặc biệt trong trường hợp lồi, ta thiết lập được mối quan hệ của dưới vi phân Mordukhovich và nón pháp tuyến của tập mục tiêu mở rộng: Ωr := {x ∈ X|TΩF (x) ≤ r}, r > 0 (1.20) tại các điểm ngoài tập x ∈ / Ω. Kết quả sau đây (xem [4], Định lý 7.3) cần cho việc áp dụng bài toán Fermat-Torricelli suy rộng. Định lí 1.5 (Dưới vi phân của hàm thời gian tối thiểu lồi tại các điểm ngoài tập) / Ω thỏa mãn ΠFΩ (x) 6= φ với Giả sử hàm thời gian tối thiểu lồi, x ∈ r = TΩF (x) < ∞ trong (1.20). Khi đó, với bất kỳ ω ∈ ΠFΩ (x), ta có các quan hệ sau đây: ∂TΩF (x) = N (x; Ωr ) ∩ [−∂ρF (ω − x)] (1.21) ⊂ N (ω; Ω) ∩ [−∂ρF (ω − x)] Hơn nữa, nếu 0 ∈ F thì bao hàm thức (1.21) có dấu bằng, và ta có ∂TΩF (x) = N (ω; Ω) ∩ [−∂ρF (ω − x)]. (1.22) 11
Chương 2 Điều kiện tối ưu và thuật toán giải bài toán Fermat-Torricelli Chương 2 trình bày các điều kiện tối ưu cho điểm Fermat - Torricelli, thuật toán dưới gradient giải bài toán Fermat - Torricelli suy rộng với các tập đóng, một số trường hợp đặc biệt của thuật toán dưới gradient. Các kiến thức trình bày trong chương này được được tham khảo trong [3]. 2.1. Điều kiện tối ưu cho bài toán Fermat-Torricelli suy rộng Phần này trình bày các kết quả về điều kiện cần và đủ cho nghiệm của bài toán Fermat-Torricelli suy rộng trong các trường hợp lồi và không lồi. Các kết quả đó cho phép chỉ ra cách tìm các điểm Fermat-Torricelli suy rộng. Mệnh đề 2.1 (Sự tồn tại nghiệm tối ưu của bài toán Fermat-Torricelli suy rộng ) Gỉa sử F 6= ∅ lồi đóng bị chặn, Ω1 , . . . , Ωn đóng. Giả thiết thêm rằng ít nhất một trong các tập Ω1 , . . . , Ωn trong (1.3) bị chặn và inf x∈X T (x) < ∞. Khi đó, bài toán Fermat-Torricelli suy rộng (1.3) có nghiệm tối ưu trong các trường hợp sau: (i) X là không gian hữu hạn chiều. (ii) Không gian X là phản xạ và các tập Ωi , i = 1, . . . , n là lồi. 12
Ta có thể cho ví dụ minh họa các giả thiết trong Mệnh đề 2.1 là cốt yếu cho sự tồn tại tối ưu của (1.3). Ví dụ 2.1 Xét trường hợp đặc biệt của (1.4) với X = R2 , n = 2, Ω1 := {(x, y) ∈ R2 |y ≥ ex }, và Ω2 := R × {0}. Rõ ràng bài toán này không có nghiệm tối ưu. Bây giờ ta dẫn các điều kiện tối ưu dẫn cho bài toán Fermat-Torricelli suy rộng (1.3). Định nghĩa tập [ Ai (x) := [−∂ρF (ω − x) ∩ N (ω; Ωi )], x ∈ X (2.1) ω∈ΠF Ω (x) i trong đó ΠFΩi (x) 6= φ. Như trong chứng minh Mệnh đề 2.1 (không cần tính bị chặn của tập mục tiêu Ω và với các giả thiết về hệ động F), ta có thể suy ra từ phép chiếu suy rộng (1.18) rằng ΠFΩ (x) 6= ∅ với mọi x ∈ / Ω trong hai trường hợp sau: • X là không gian hữu hạn chiều và Ω đóng; • X là không gian phản xạ, Ω là lồi và đóng. Hơn nữa , dễ thấy từ (2.1) rằng Ai (x) = N (x; Ωi ) ∩ C ∗ , x ∈ Ωi , i = 1, . . . , n (2.2) cho các tập lồi đóng Ωi , trong đó tập mức tựa C ∗ được xác định như trong (1.13). Mối quan hệ giữa Ai (x) và dưới vi phân ∂TΩFi (x) trong trường hợp ngoài tập x ∈ Ωi suy ra từ Định lý 1.4 và Định lý 1.5 cho các tập mục tiêu Ωi lồi và không lồi. Các quan hệ này được sử dụng rộng rãi sau này . Trước hết ta thiết lập các điều kiện cần tối ưu cho bài toán không lồi tổng quát (1.3) trong trường hợp vô hạn chiều . Để đơn giản, ta giả sử 0 ∈ intF . Điều đó đảm bảo tính liên tục Lipschitz của hàm thời gian tối thiểu TΩFi (·) cho tất cả các tập Ωi , i = 1, . . . , n trong (1.3) và khả năng áp dụng quy tắc tổng của Định lý 1.4. Cách tiếp cận của chúng ta cho phép xử lý trường hợp không Lipschitz khi intF = ∅ bằng cách sử dụng công thức dưới vi phân cho hàm thời gian tối thiểu đã có trong [4] và qui tắc tổng dưới vi phân cơ bản cho các hàm không Lipschitz. 13
Định lí 2.1 (Điều kiện cần tối ưu cho bài toán Fermat - Torricelli suy rộng) Giả xử X là không gian Asplund, và 0 ∈ intF . Nếu x ∈ X là một nghiệm tối ưu địa phương của bài toán Fermat - Toricelli suy rộng (1.3) sao cho với mỗi i = 1, . . . , n, hàm thời gian tối thiểu TΩFi (·) đặt chỉnh tại x khi x ∈ / Ωi , thì Xn 0∈ Ai (x), (2.3) i=1 với các tập Ai (x), i = 1, . . . , n xác định như trong (2.1) Với trường hợp (1.4) của bài toán (1.3) trong không gian Hilbert, một dạng đặc biệt hơn của (2.3) đúng và nó cho ta một điều kiện cần tối ưu cho mở rộng kiểu Steiner (1.4) của bài toán Fermat - Torricelli. Định lí 2.2 ( Điều kiện cần tối ưu cho mở rộng kiểu Steiner của bài toán Fermat - Torricelli trong không gian Hilbert ) Giả xử X là không gian Hilbert và x ∈ X là nghiệm tối ưu của bài toán (1.4) sao cho với i = 1, . . . , n hàm khoảng cách d(·; Ωi ) đặt chỉnh tại x khi x∈/ Ωi . Khi đó, (2.3) là điều kiện cần tối ưu của x trong (1.4), trong đó tập Ai (x) có dạng  x − Π(x; Ωi ) , nếu x ∈ / Ωi ,    d(x; Ωi )   Ai (x) = N (x; Ω ) ∩ B, nếu x ∈ Ω , (2.6)  i i   với mọi i = 1, . . . , n.  Để ý rằng giả thiết đặt chỉnh của Định lý 2.2 thỏa mãn một cách tầm thường khi X là hữu hạn chiều hoặc tập Ωi lồi. Hơn nữa, ta có Π(x; Ωi ) 6= ∅. Tiếp theo ta sử dụng Định lý 2.2 để đặc biệt hóa nghiệm tối ưu của (1.4) với n = 3. Chú ý rằng điều kiện < u, v >≤ −1/2 nhận được dưới đây có nghĩa là góc giữa hai véc tơ đó lớn hơn hoặc bằng 120o . Đó là trường hợp quan trọng trong bài toán Fermat - Torricelli cổ điển. Hệ quả 2.1 (Điều kiện cần cho bài toán Fermat - Torricelli suy rộng với ba tập không lồi trong không gian Hilbert) 14
Giả sử n = 3 trong Định lý 4.2, trong đó Ω1 , Ω2 , Ω3 là không tương giao từng đôi một của X. Các phát biểu sau đúng luân phiên cho nghiệm tối ưu địa phương x ∈ X với các tập Ai (x) xác định bởi (2.6): (i) Điểm x thuộc một trong các tập Ωi , chẳng hạn Ω1 , và không thuộc vào 2 tập kia. Khi đó, ∃a2 ∈ A2 (x) và ∃a3 ∈ A3 (x) sao cho 1 < a2 , a3 >≤ − và − a2 − a3 ∈ N (x; Ω1 ); (2.8) 2 (ii) Điểm x không thuộc tất cả 3 tập Ω1 , Ω2 và Ω3 . Khi đó, tồn tại ai ∈ Ai (x) với i = 1, 2, 3 sao cho −1 < ai , aj >= , khi i 6= j với i, j ∈ 1, 2, 3. (2.9) 2 Ví dụ sau đây minh họa Hệ quả 2.1 cho bài toán trên mặt phẳng với 2 tập lồi và một tập không lồi. Ví dụ 2.2 (Bài toán Fermat - Torricelli suy rộng không lồi trên mặt phẳng) Giả sử Ω1 là hình cầu tâm c1 := (0; −2) với bán kính r = 1, Ω2 là hình cầu tâm c2 := (0; −6) với bán kính r = 1, Ω3 là tập không lồi được xác định bởi Ω3 = {(x1 , x2 ) ∈ R2 |x2 ≥ −|x1 |} (2.12) như trong hình 2.1. Theo Mệnh đề 2.1, tồn tại một nghiệm tối ưu của bài toán này. Bởi vì tất cả các giả thiết của Hệ quả 2.1 thỏa mãn, ta áp dụng Hệ quả 2.1 tìm được 2 điểm nằm trên biên Ω1 và kí hiệu là u và v sao cho [c1 , u] là đường phân giác của góc hình thành bởi 2 đường thẳng uc2 vàupu , trong đó pu là hình chiếu của u trên Ω3 , còn [v, c1 ] là đường phân giác của góc hình thành bởi vc2 và vpv . Hai điểm u, v thỏa mãn điều kiện (i) của Hệ quả 2.1 và nó là nghiệm tối ưu của bài toán. Ta tìm được u = (−0.8706, −2.4920) và v = (0.8706, −2.4920) với 5 chữ số có nghĩa, và giá trị tối ưu của bài toán là 3.7609. 15
Hình 2.1: Bài toán Fermat-Torricelli suy rộng không lồi Bây giờ ta xét bài toán Fermat - Torricelli suy rộng (1.3) với các tập mục tiêu lồi Ωi , i = 1, . . . , n trong không gian Banach. Trong trường hợp này, ta dẫn các điều kiện cần và đủ tối ưu cho điểm Fermat - Torricelli. Từ các Định lý 1.3 và 1.5 ta suy ra trong trường hợp các tập Ωi , i = 1, . . . , n là lồi, với ΠFΩi (x; Ωi ) 6= ∅ khi x ∈ / Ωi và 0 ∈ F , ta có đẳng thức sau: Ai (x) = −∂ρF (ω − x) ∩ N (ω; Ωi ) với bất kỳ x ∈ X và ω ∈ ΠFΩi (x; Ωi ) (2.13) với các tập Ai (x) xác định bởi (2.1), trong đó nón pháp tuyến và dưới vi phân được xác định bởi công (1.7) và (1.5) của giải tích lồi. Dưới đây là một đặc trưng cổ điển của điểm Fermat - Torricelli cho bài toán lồi. Định lí 2.3 (Điều kiện cần và đủ cho điểm Fermat - Torricelli suy rộng của bài toán lồi trong không gian Banach) Giả sử các tập mục tiêu Ωi là lồi; 0 ∈ intF cho bài toán (1.3) trong không gian Banach X. Giả sử x ∈ X thỏa mãn ΠFΩi 6= ∅ khi x ∈ / Ωi với i = 1, . . . , n. Khi đó, điều kiện (2.3) với tập Ai (x) được xác định bởi (2.13) 16
là điều kiện cần và đủ tối ưu của x trong bài toán này. Hệ quả 2.2 (Đặc trưng của nghiệm tối ưu cho mở rộng kiểu Steiner lồi của bài toán Fermat -Torricelli trong không Hilbert) Giả sử X là không gian là không gian Hilbert và tất cả các tập Ωi trong (1.4) là lồi. Khi đó, điều kiện (2.3) với Ai (x) được tính bởi (2.6) là điều kiện cần và đủ tối ưu cho x của bài toán (1.4). Ví dụ 2.3 Xét trường hợp Ω1 = {(−1; 0)}, Ω2 = {(0; 1)} và Ω3 = {(1; 0)} trong √ mặt phẳng R2 . Khi đó, Hệ quả 2.2 cho ta nghiệm tối ưu duy nhất (0, 1/ 3) của bài toán (1.4) với F = [−1, 1] × [−1, 1] và tập Ωi , i = 1, 2, 3, ta có nghiệm tối ưu duy nhất (0, 1) cho bài toán Fermat -Torricelli (1.3) với tâp F và Ωi . Ta trình bày một áp dụng đơn giản của Hệ quả 2.2 cho bài toán Fermat- Torricelli suy rộng (1.4) có một số hữu hạn khoảng đóng của đường thẳng thực rời nhau. Mệnh đề 2.2 (Bài toán Fermat - Torricelli cho các khoảng đóng của đường thẳng thực) Xét bài toán (1.4) với các tập Ωi được cho bởi n khoảng đóng rời nhau [ai , bi ] ⊂ R, i = 1, . . . , n, trong đó a1 ≤ b1 < a2 ≤ b2 < . . . < an ≤ bn . Các khẳng định sau đây đúng: (i) Nếu n = 2k + 1 thì điểm bất kỳ của khoảng [ak+1 , bk+1 ] là nghiệm tối ưu của bài toán; (ii) Nếu n = 2k thì điểm bất kỳ của không gian [bk , ak+1 ] là nghiệm tối ưu của bài toán. Áp dụng khác của Hệ quả 2.2 cho ta đặc trưng đầy đủ của điểm Fermat -Torricelli trong bài toán lồi (1.4) với n = 3 trong không gian Hilbert. Chú ý rằng do tính duy nhất của hình chiếu ta có x − Π(x; Ωi ) Ai (x) = ai = , nếu x ∈ / Ωi , (2.15) d(x; Ωi ) với Ai (x) xác định bởi (2.6). 17
Hình 2.2: Bài toán Fermat-Torricelli suy rộng lồi Mệnh đề 2.3 (Đặc trưng của điểm Fermat - Torricelli suy rộng cho ba tập lồi trong không gian Hilbert) Giả sử X là một không gian Hilbert và Ω1 , Ω2 , Ω3 là các tập lồi không giao nhau từng đôi một trong X. Khi đó, x ∈ X là nghiệm tối ưu của bài toán (1.4) sinh ra bởi các tập này nếu và chỉ nếu và chỉ nếu các điều kiện (i) và (ii) của Hệ quả 2.1 thỏa mãn trong đó các véc tơ ai , i = 1, 2, 3 được xác định trong (2.15) và nón pháp tuyến N (x, Ω1 ) trong (2.8) được tính bởi (1.7). Ví dụ 2.4 (Bài toán Fermat-Torricelli suy rộng lồi trên mặt phẳng) Giả sử các tập Ω1 , Ω2 , Ω3 trong bài toán (1.4) là các hình cầu đóng trong R2 với bán kính r = 1, tâm là các điểm (0, 2), (−2, 0), (2, 0) (xem hình 2.2). Dễ dàng thấy rằng điểm (0, 1) ∈ Ω1 thỏa mãn tất cả các điều kiện trong mệnh đề 2.3 (i), và do đó, nó là nghiệm tối ưu (thực ra là nghiệm duy nhất) của bài toán này. Ví dụ 2.5 18