BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC THĂNG LONG
-----------------------------------------
HOÀNG THỊ THÙY LINH
BÀI TOÁN SYLVESTER VÀ BÀI TOÁN FERMAT – TORRICELLI CHO CÁC HÌNH CẦU EUCLID
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội - Năm 2016
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC THĂNG LONG
-----------------------------------------
HOÀNG THỊ THÙY LINH
BÀI TOÁN SYLVESTER VÀ BÀI TOÁN FERMAT– TORRICELLI CHO CÁC HÌNH CẦU EUCLID
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Ố : 60 46 01 13
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS. TS. ĐỖ VĂN LƯU
Hà Nội – Năm 2016
Lời cảm ơn
Trước tiên, em xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới
PGS.TS. ĐỗVăn Lưu – Người Thầy đã luôn giúp đỡ và hướng dẫn em trong
suốt học tập và làm luận văn này.
Em xin cảm ơn tới trường Đại học Thăng Long Hà Nội. Em xin cảm ơn
tới các Giáo sư, Tiến sỹ và các Thầy, cô giáo trong bộ môn Toán đã giảng dạy
cho em những kiến thức cơ bản, nền tảng quý báu trong thời gian học cao học.
Em xin cảm ơn phòng Quản lý Sau đại học đã tạo điều kiện thuận lợi
để em hoàn thành khóa luận này.
Cảm ơn các bạn trong lớp cao học Toán K3 Đại học Thăng Long,
chuyên ngành Phương pháp toán sơ cấp, đã luôn thân thiện và nhiệt tình
giúp đỡ tôi trong thời gian học tập vừa qua.
Tôi cảm ơn những người thân yêu trong gia đình và các bạn bè luôn
ủng hộ, động viên và là chỗ dựa tinh thần vững chắc trong suốt quá trình học
tập và thời gian làm luận văn.
Tác giả
Hoàng Thị Thùy Linh
MỤC LỤC
Trang
Mở đầu......................................................................................................1
Chương 1: CÁC KIẾN THỨC CƠ BẢN VỀ HÀM LỒI VÀ DƯỚI
VI PHÂN HÀM LỒI
1.1. Tập lồi và nón lồi.....................................................................3
1.1.1. Tập lồi......................................................................................3
1.1.2. Nón lồi.....................................................................................4
1.2. Hàm lồi.....................................................................................8
1.2.1. Hàm lồi.....................................................................................8
1.2.2. Các phép toán về hàm lồi.......................................................14
1.3. Dưới vi phân hàm lồi.............................................................17
1.4. Dưới vi phân hàm max..........................................................23
Chương 2: BÀI TOÁN SYLVESTER VÀ BÀI TOÁN FERMAT -
TORRICELLI CHO HÌNH CẦU EUCLID
2.1. Khái niệm và định nghĩa.......................................................25
2.2. Bài toán Sylvester cho hình cầu Euclid...........................26
2.2.1. Sự tồn tại, duy nhất nghiệm và điều kiện tối ưu..............26
2.2.2. Bài toán Sylester suy rộng cho ba hình cầu....................32
2.3. Bài toán Fermat – Torricelli cho hình cầu Euclid.............49
2.3.1. Sự tồn tại và duy nhất nghiệm của nghiệm tối ưu............49
2.3.2. Cấu trúc nghiệm...............................................................56
KẾT LUẬN.......................................................................................63
TÀI LIỆU THAM KHẢO......................................................................64
MỞ ĐẦU
1. Lý do chọn đề tài
Giải tích lồi cho ta một lý thuyết phong phú và đẹp đẽ về hàm lồi
và ứng dụng trong tối ưu hóa với nhiều kết quả nổi tiếng chẳng hạn như:
Bất đẳng thức Jensen, Định lý Fenchel – Moreau về hàm liên hợp, Định
lý Moreau – Rockafellar về dưới vi phân hàm lồi, Định lý Kuhn – Tucker
cho bài toán tối ưu lồi có ràng buộc,…Có thể nói tập lồi, hàm lồi các đối
tượng đẹp trong tối ưu hóa.Với các bài toán lồi ta có các điều kiện đặc
trưng cho nghiệm của bài toán đó dưới ngôn ngữ dưới vi phân của hàm
lồi.
Trong toán sơ cấp nhiều bài toán được phát biểu với các hàm lồi.
Với các bài toán cực trị, hàm lồi đóng một vai trò rất quan trọng. Cực trị
địa phương của hàm lồi trên miền lồi cũng là cực tiểu toàn cục, cực đại của
một hàm lồi trên một đa giác lồi đạt tại một trong các đỉnh của đa giác đó.
Nhiều bài toán sơ cấp hay được phát biểu theo hướng này. Bài toán
Sylvester cho các hình cầu Euclid được phát biểu như sau: “ Cho hai họ
hữu hạn các hình cầu Euclid. Tìm một hình cầu Euclid nhỏ nhất chứa các
hình cầu của họ thứ nhất và cắt tất cả các hình cầu của họ thứ hai”. Bài
toán Fermat – Torricelli cho các hình cầu Euclid được phát biểu như sau: “
Cho hai họ các hình cầu Euclid. Hãy tìm một điểm làm cực tiểu tổng
khoảng cách xa nhất đến các hình cầu của họ thứ nhất và khoảng cách gần
nhất đến các hình cầu của họ thứ hai”. Các bài toán đó được nghiên cứu
bằng công cụ giải tích lồi trong [3]. Chính vì vậy, tôi chọn đề tài “BÀI
TOÁN SYLVESTER VÀ BÀI TOÁN FERMAT - TORRICELLI
CHO CÁC HÌNH CẦU EUCLID ”
4
2. Nội dung đề tài
Luận văn trình bày một số kiến thức cơ bản về hàm lồi, dưới vi phân
hàm lồi và các kết quả về sự tồn tại duy nhất nghiệm, điều kiện tối ưu và
cách giải cho bài toán Sylvester và bài toán Fermat – Torricelli của N. M.
Nam, N. Hoang và N. T. An đăng trên tạp chí J. Optim. Theory Appl. 160
(2014) bằng phương pháp giải tích lồi.
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.
Chương 1: “Các kiến thức cơ bản vê hàm lồi và dưới vi phân hàm lồi”
Trình bày một số kiến thức cơ bản về tập lồi, nón lồi, hàm lồi và các phép
toán về hàm lồi, dưới vi phân hàm lồi và dưới vi phân của hàm max.
Chương 2: “ Bài toán Sylester và bài toán Fermat – Torricelli cho hình cầu
Euclid”
Trình bày các kết quả về sự tồn tại và duy nhất nghiệm, điều kiện
tối ưu và cách giải của Nam – Hoang – An (2014) cho bài toán Sylester
với các hình cầu Euclid và bài toán Fermat – Torricelli với ba hình cầu
Euclid. Trường hợp quan trọng của bài toán Sylester với ba hình cầu và
mối quan hệ với bài toán Apollonius cũng được trình bày trong chương
này.
5
Chương 1
CÁC KIẾN THỨC CƠ BẢN VỀ HÀM LỒI VÀ DƯỚI VI PHÂN
HÀM LỒI
Chương 1 trình bày một số kiến thức cơ bản về tập lồi, nón lồi, hàm lồi và
các phép toán về hàm lồi, dưới vi phân của hàm lồi và dưới vi phân của hàm
max. Các kiến thức trình bày trong chương này được tham khảo trong [1], [2].
1.1. TẬP LỒI VÀ NÓN LỒI
1.1.1. Tập lồi
Giả sử X là không gian tuyến tính, R là tập các số thực.
Định nghĩa 1.1
Tập A X được gọi là lồi, nếu:
A, R : 0 1 A . x1 + (1 - ) x2
A . x1, x2 X; x1, x2 Giả sử A
Định nghĩa 1.2
Đoạn nối x1, x2 được định nghĩa như sau:
1}. [x1, x2] = { x A : x = x1 + (1 - ) x2, 0
Định nghĩa 1.3
Vectơ x X , nếu X được gọi là tổ hợp lồi của các vectơ x1, ... , xm
( i = 1, ..., m), = 1, sao cho x = .
Nhận xét 1.1
A A. Tập A là lồi, nếu: x1, x2 [x1, x2]
Ví dụ 1.1
6
Các nửa không gian là các tập lồi. Các tam giác và hình tròn trong mặt
phẳng là các tập lồi. Hình cầu đơn vị trong không gian Banach là tập lồi ...
Mệnh đề 1.1
Giả sử A X ( I) là các tập lồi, với I là tập chỉ số bất kỳ. Khi đó,
tập A = A cũng lồi.
Từ định nghĩa 1.1 ta nhận được các mệnh đề sau:
Mệnh đề 1.2
X lồi, Giả sử tập Ai R ( i = 1, ..., m). Khi đó, A1 + ... + A2 là
tập lồi.
Mệnh đề 1.3
Giả sử Xi là không gian tuyến tính, tập Ai Xi lồi ( i = 1, ..., m). Khi đó,
... tích Đề các A1 Am là tập lồi trong X1 ... Xm .
Mệnh đề 1.4
Giả sử X, Y là các không gian tuyến tính, T : X Y là toán tử tuyến
tính. Khi đó
a) A X lồi T(A) lồi;
b) B Y lồi Nghịch ảnh T –1(B) của B là tập lồi.
Định lý 1.1
Giả sử tập A A. Khi đó, A chứa tất cả các tổ hợp X lồi; x1, ... , xm
lồi của x1, ... , xm . 1.1.2. Nón lồi
Giả sử X là không gian tuyến tính.
Định nghĩa 1.4
Tập K X được gọi là nón có đỉnh tại 0 , nếu:
7
x K, > 0 x K.
K được gọi là nón có đỉnh tại x0, nếu K – x0 là nón có đỉnh tại 0.
Định nghĩa 1.5
Nón K có đỉnh tại 0 được gọi là nón lồi, nếu K là một tập lồi, có nghĩa là:
x, y K , , > 0 x + y K.
Ví dụ 1.2
Các tập sau đây trong Rn :
{( , ... , Rn : 0, i = 1, ... , n}, )
{( , ... , Rn : > 0, i = 1, ... , n} )
là các nón lồi có đỉnh tại 0.
Mệnh đề 1.5
Giả sử ( ) là các nón lồi có đỉnh tại x0 với I là tập chỉ số bất kỳ.
Khi đó, là nón lồi có đỉnh tại x0 .
Ví dụ 1.3
( X = Rn , ). Khi đó:
K = { x Rn : < x , > 0, }
là một nón lồi bởi vì K = , trong đó:
= { x Rn : < x , > 0}
là nón lồi.
Định lý 1.2
Tập K X là một nón lồi có đỉnh tại 0 khi và chỉ khi:
x, y K, > 0 x + y K, x K.
Chứng minh
a) Giả sử K là nón lồi. Khi đó, do K là tập lồi, ta có:
8
z = (x + y) K .
Do K là nón có đỉnh tại 0, ta lại có:
x + y = 2z K .
b) Ngược lại, với x K, > 0 ta có x K, vậy K là một nón có đỉnh tại
0. Với 0 < < 1, x, y K ta có (1 - )x K, y K và (1 - )x + y K.
Chú ý với = 0 hoặc 1 ta vẫn có (1 - )x + y K. Vậy K là nón lồi có đỉnh
tại 0.
Hệ quả 1.1
Tập K X là nón lồi K chứa tất cả các tổ hợp tuyến tính dương của
K, , ... , > 0 thì . các phần tử của K, tức là nếu x1, ... , xm
Hệ quả 1.2
Giả sử A là tập bất kỳ trong X, K là tập tất cả các tổ hợp tuyến tính
dương của A. Khi đó, K là nón lồi nhỏ nhất chứa A.
Định nghĩa 1.6
Tương giao của tất cả các nón lồi (có đỉnh tại 0) chứa tập A và điểm 0 là
một nón lồi và được gọi là nón lồi sinh bởi A, ký hiệu là KA.
Định nghĩa 1.7
Tương giao của tất cả các không gian con tuyến tính chứa tập A được
gọi là bao tuyến tính của tập A, ký hiệu là lin A.
Nhận xét 1.2
lin A = KA - KA .
Mệnh đề 1.7
a) KA = KconvA ,
b) Nếu A là tập lồi thì :
9
= {x X : x = z, 0, z A}, KA =
trong đó convA là bao lồi của A.
Giả sử X là không gian lồi địa phương, X* là không gian các phiếm hàm
tuyến tính liên tục trên X.
Định nghĩa 1.8
Vec tơ x* X* được gọi là pháp tuyến của tập lồi A tại A, nếu:
< x* , x - > 0 ( ).
Tập tất cả các vec tơ pháp tuyến của tập lồi A tại A được gọi là nón pháp
tuyến của A tại , ký hiệu là N ( |A). Như vậy:
N( |A) = {x* X* : < x*, x – > 0, }.
Nhận xét 1.3
Nón pháp tuyến của tập lồi A tại A là lồi đóng.
Bây giờ giả sử X là không gian tuyến tính.
Định nghĩa 1.9
Giả sử A X lồi, khác . Ta nói tập A lùi xa theo phương d 0, nếu
A + d A ( 0), hay:
x + d A ( 0, ). (1.1)
Nhận xét 1.4
Tập A lùi xa theo phương d nếu A chứa tất cả các nửa đường thẳng xuất
phát từ các điểm của A và theo phương d.
Định nghĩa 1.10
Tập các vectơ d X thỏa mãn (1.1) và vec tơ d = 0 được gọi là nón lùi
xa (recession cone) của A; ký hiệu là o+ A.
Định lý 1.3
10
Giả sử tập A X lồi, khác . Khi đó, o+ A là nón lồi chứa điểm 0.
Đồng thời :
o+ A = {d X : A + d A}.
Ví dụ 1.4
X = R2 .
} a) C1 = {(x, y) : x > 0, y
0, y 0} . o+ C1 = {(x, y) : x
x2 } b) C2 = {(x, y) : y
0} o+ C2 = {(x, y) : x = 0, y
1.2. HÀM LỒI.
1.2.1 Hàm lồi.
Giả sử X là không gian lồi địa phương, D X, f : D R { }.
Định nghĩa 1.11
Trên đồ thị ( epigraph ) của hàm f, ký hiệu là epif, được định nghĩa như
sau:
epif = {(x, r) D R : f(x) r}.
Định nghĩa 1.12
Miền hữu hiệu (effective domain) của hàm f, ký hiệu là dom f, được định
nghĩa như sau:
Dom f = {x D : f(x) < + }.
Định nghĩa 1.13
Hàm f được gọi là chính thường (proper), nếu dom f và f(x) > -
( x D).
Định nghĩa 1.14
11
Hàm f được gọi là lồi trên D, nếu epif là tập lồi trong X R. Hàm f được
gọi là lõm trên D, nếu –f là hàm lồi trên D.
Nhận xét 1.5
Nếu f lồi dom f lồi.
Thật vậy, dom f là hình chiếu trên X của epif :
dom f = { x : f(x) < + } = {x : r , (x, r) epif }.
Như vậy, dom f là ảnh của tập lồi epif qua một ánh xạ tuyến tính. Do đó, dom f
lồi.
Ví dụ 1.5
Hàm affine
f(x) = < x* , x > + ( x* X* , R)
là hàm lồi trên X, trong đó X* là không gian các phiếm hàm tuyến tính liên tục
trên X.
Ví dụ 1.6
Giả sử f là hàm giá trị thực khả vi liên tục hai lân trên tập lồi mở A Rn . Khi
đó, f lồi trên A khi và chỉ khi ma trận Hessian :
Qx =
là bán xác định dương ( x A), tức là :
Rn, x A). < z, Qxz > 0 ( z
Ví dụ 1.7
2 )1/2 ,
Chuẩn Euclide là một hàm lồi trên Rn :
2 + ... + xn
|| x || = < x, x >1/2 = (x1
Rn trong đó x = (x1, ... , xn)
Ví dụ 1.8
12
Hàm chỉ (indicator function ) ( . |A) của tập lồi A X là hàm lồi:
( x |A) = { 0, 𝑛ế𝑢 𝑥 ∈ 𝐴 , +∞, 𝑛ế𝑢 𝑥 ∉ 𝐴 .
Ví dụ 1.9
Giả sử X* là không gian liên hợp của X. Hàm tựa (support funtion) s( . |A) của
tập lồi A X* là một hàm lồi:
s (x|A) = < x* , x> .
Định lý 1.4
Giả sử D là tập lồi trong không gian X, hàm f : D ( ]. Khi đó, f
lồi trên D khi và chỉ khi:
f( x + (1 - )y) ≤ f(x) + (1 - )f(y)
( [0,1], x, y D). (1.2)
Chứng minh
a) Giả sử f là hàm lồi. Không mất tính tổng quát có thể xem như (0, 1).
Không thể xảy ra trường hợp f(x) < , f(y) < , mà f ( x +(1 - )y) = ,
bởi vì dom f lồi, với x, y dom f thì [x, y] dom f. Do (0, 1), nên: f(x) =
f(x) = . Nếu x hoặc y dom f , thì f(x) = hoặc f(y) = và
(1.2) đúng.
Bởi vì epif lồi, (x, r) epif , (y, s) epif, (0, 1), (x, r) + (1 - )
(y, s) = ( x + (1 - )y, r + (1 - )s) epif .
f( x + (1 - )y) r + (1 - )s.
f( x + (1 - )y) f(x) + (1 - )f(y)
( lấy r = f(x), s = f(y) ).
b) Ngược lại, giả sử (1.2) đúng. Lấy (x, r) epif , (y, s) epif , [0, 1]
ta phải chứng minh:
13
(x, r) + (1 - )(y, s) epif.
Thật vậy:
(x, ) epif, (y, s) epif f(x) r, f(y) s.
f( x + (1 - )y) f(x) + (1 - )f(y) r + (1 - )s
( x + (1 - )y, r + (1 - )s) epif
(x, r) + (1 - )(y, s) epif
Định lý 1.5 (Bất đẳng thức Jensen)
Giả sử f : X ( ]. Khi đó, f là hàm lồi khi và chỉ khi 0 (i =
X, = 1, x1, ... , xm 1, ... , m),
f( x1 + ... + xm) f(x1) + ... + f(xm). (1.3)
Chứng minh
Không giảm tổng quát, có thể xem như > 0 (i = 1, ... , m). Khi đó, nếu
, và bất đẳng thức (1.3) là tầm thường. Do xi dom f thì f(xi) = f(xi) =
(i = 1, ... , m) mà f = dom f lồi nên không xảy ra trường hợp f(xi) <
, bởi vì khi đó dom f.
epif (i = 1, ... , m), Nếu xi dom f (i = 1, ... , m), do epif lồi và (xi, f(xi))
theo định lý 1.4, ta có:
epif. ( x1 + ... + xm, f(x1) + ... + f(xm))
f( x1 + ... + xm) f(x1) + ... + f(xm).
Mệnh đề 1.8
Giả sử f : X [ ]. Khi đó, f là hàm lồi khi và chỉ khi:
f( x + (1 - )y) < r + (1 - )s
14
( (0, 1), x, y : f(x) < r, f(y) < s) .
Định lý 1.6
Giả sử f là hàm lồi trên X, [ ]. Khi đó, các tập mức { x : f(x)
< } và {x : f(x) } lồi.
Chứng minh
. Từ mệnh đề 1.8 a) Lấy x1, x2 {x : f(x) < }, ta có f(x1) < , f(x2) <
suy ra : (0, 1) :
+ (1 - ) = f( x1 + (1 - ) x2) <
{x : f(x) < } x1 + (1 - ) x2
{x : f(x) < } lồi.
b) Tập {x : f(x) } lồi, bởi vì:
{ x : f(x) } = { x : f(x) < } .
Hệ quả 1.3
là hàm lồi trên X, R ( I), I là tập chỉ số bất kỳ. Giả sử
Khi đó, tập
A = {x X : (x) , I} – lồi.
Định nghĩa 1.15
Hàm f(x) xác định trên X được gọi là thuần nhất dương , nếu x X,
(0, ),
f( x) = f(x).
Định lý 1.7
Hàm thuần nhất dương là lồi khi và chỉ khi:
. (1.4)
15
Chứng minh
a) Giả sử hàm thuần nhất dương f là lồi. Lấy . Khi đó,
=
b) Ngược lại, giả sử (1.4) đúng. Lấy epif (i = 1, 2)
Ta có epif , bởi vì:
.
Hơn nữa, bởi vì f là hàm thuần nhất dương, cho nên nếu thì
và
(0 < < ) .
.
Như vậy, epif đóng đối với phép cộng và phép nhân vô hướng. Do đó,
epif là một nón lồi. Vậy f là hàm lồi.
Hệ quả 1.4
Giả sử f là hàm lồi chính thường, thuần nhất dương. Khi đó,
Định lý 1.8
Hàm f đóng khi và chỉ khi tất cả tập mức có dạng của f là
đóng.
Chứng minh
Kí hiệu các tập mức của f là .Ta có:
16
Vì vậy, epif đóng kéo theo tất cả các tập đóng.
Ngược lại, giả sử tất cả các tập đóng. Ta chứng minh đóng?
Thật vậy,
(1.5)
Giả sử . Để chứng minh đóng, ta chứng minh tồn tại lân cận V
của sao cho:
.
Bởi vì , cho nên . Từ (1.5) suy ra Do đó
tồn tại lân cận U của .
Đặt:
Khi đó, V là lân cận của điểm trong .
Nếu thì x < , x , nghĩa là ℒαf . Vì vậy, f(x) > ℒβf. Do
(epif) V = .
1.2.2. Các phép toán về hàm lồi
Định lý 1.9
Giả sử là các hàm lồi chính thường trên X. Khi đó tổng
là một hàm lồi.
Nhận xét 1.6
Nếu là các hàm lồi chính thường, thì là hàm lồi nhưng
có thể không chính thường.
Định lý 1.10
17
Giả sử F là tập lồi trong và
(1.6)
Khi đó f chính là hàm lồi trên X.
Chú ý: Ta quy ước infimun trên tập (các số thực) bằng .
Chứng minh
Nếu thì từ (1.6) suy ra:
Nếu thì
(0 < < 1)
Suy ra f là hàm lồi (mệnh đề 1.8)
Định nghĩa 1.15
Giả sử là các hàm chính thường trên X. Tổng chập infimal ( infimal
convolution) của , được xác định như sau:
. (1.7)
và được kí hiệu là hay .
Nhận xét 1.7
Trường hợp m=2, thì (1.7) có dạng:
Định lý 1.11
Giả sử là các hàm lồi chính thường trên X. Khi đó là hàm lồi
18
trên X.
Chứng minh
Đặt . Khi đó, F là tập lồi trong . Theo định
nghĩa sao cho:
Do đó, hàm f được xác định bởi (1.7) là một hàm lồi được xây dựng theo định lý
1.10 bởi tập F.
Định nghĩa 1.16
Giả sử là một họ tùy ý các hàm.
a) Cận trên của các hàm , kí hiệu là , được xác định như sau:
;
b)Cận dưới của hàm , kí hiệu là , được xác định như sau:
c) Bao lồi cận dưới của các hàm , kí hiệu , được xác định như sau:
Mệnh đề 1.9
Giả sử là các hàm lồi trên X. Khi đó,
là hàm lồi, a)
là hàm lồi. b)
Định nghĩa 1.17
a) Bao đóng của hàm f, kí hiệu là , được xác định như sau:
epi =
19
b) Bao lồi và bao lồi đóng của hàm f, kí hiệu là convf và được xác
định tương ứng như sau:
Nhận xét 1.8
Hàm f đóng a)
b) Bao đóng của một hàm lồi là một hàm lồi;
Ví dụ 1.10
Giả sử với các hàm chỉ . Khi đó:
a)
b)
1.3. DƯỚI VI PHÂN HÀM LỒI
Giả sử f là hàm lồi trên X; X* là không gian liên hợp của X.
Định nghĩa 1.18
.
Phiếm hàm được gọi là dưới gradient của hàm f tại nếu :
Định nghĩa 1.19
Tập tất cả các dưới gradient của f tại được gọi là dưới vi phân của f
.
tại , kí hiệu là , tức là:
Định nghĩa 1.20
Hàm f được gọi là khả dưới vi phân tại nếu .
Định lý 1.12
20
Giả sử f là hàm lồi chính thường trên X và Khi đó:
.
Chứng minh
Nếu , thì với mọi , ta có:
Theo định lý 4.1 [1], f có đạo hàm tại theo phương d, cho nên:
(1.8)
Ngược lại, nếu (1.8) đúng, ta lấy từ dịnh lí 4.1 [1] ta nhận được:
.
Do đó, .
Hệ quả 1.5
,
trong đó là vi phân dưới của theo biến d.
Chứng minh
Do theo định lí 1.12 ta có:
Định lý 1.13
.
Giả sử f là hàm lồi chính thường trên X và . Khi đó:
,
21
trong đó f*(x*) = .
Chứng minh
a) Giả sử . Khi đó,
= . (1.9)
(1.10)
Mặt khác, theo bất đẳng thức Young – Fenchel [1], ta có:
Từ (1.9),(1.10) suy ra:
(1.11)
b) Giả sử (1.11) đúng. Từ bất đẳng thức Young - Fenchel [1] với
ta có:
(định lý 1.12)
Ví dụ 1.11
Cho hàm affine . Khi đó:
.
22
Ví dụ 1.12
Cho hàm chỉ trong đó A là tập lồi khác rỗng.
Khi đó, với mỗi ,
.
Điều đó có nghĩa là là vecto pháp tuyến của A tại .
Như vậy, là nón pháp tuyến của A tại :
Với .
Ví dụ 1.13
Giả sử X là không gian Banach, .
a) Với , ta có:
Thật vậy, nếu thỏa mãn thì
Ngược lại, nếu thì:
(1.12)
Với ta có:
23
Cho ta nhận được:
Nhưng không thể nhỏ hơn 1 vì nếu nhỏ hơn 1 thì:
Với . Do đó,
Điều này mâu thuẫn với (1.12). Vì vậy =1.
b) Với x=0, ta có:
(hình cầu đơn vị đóng trong )
Trường hợp riêng: ,
Với : f là hàm khả vi, và:
.
Với x=0:
.
24
Định lý 1.14
Giả sử f là hàm lồi chính thường trên không gian lồi địa phương
Hausdorff X, liên tục tại . Khi đó, ,lồi, compact* yếu. Đồng thời,
.
Chứng minh
a) Ta chứng minh lồi?
Lấy Khi đó,
Suy ra lồi.
b) Chứng minh ?
Theo định lý 4.2 [1], liên tục trên X. Do đó, (mệnh đề 4.6 [1])
c) Chứng minh compact * yếu?
Do liên tục, là hàm đóng. Theo định lý 4.5 [1] ta có:
.
Khi d chạy trên các tập hữu hạn A trên X, thì:
Vì vậy bị chặn theo tôpô * yếu của X*.
25
Mặt khác, trong đó là nửa không gian đóng * yếu trong X*:
Suy ra là tập đóng *yếu trong X*. Vậy là compac * yếu trong X*.
Định lý 1.15
Giả sử là các hàm lồi chính thường trên X và . Khi
đó, ta có:
Hơn nữa, nếu tồn tại , tất cả các hàm liên tục ( có thể trừ ra
một hàm), thì với mọi ta có:
1.4. DƯỚI VI PHÂN HÀM MAX
Cho họ hữu hạn các hàm Lipschitz địa phương tại . Đinh nghĩa
hàm:
.
Khi đó, f cũng lipschitz địa phương tại (xem [2]).
Đặt:
Mệnh đề 1.10
. (1.13)
Nếu chính quy tại thì (1.13) có dấu bằng và f chính quy tại .
Chứng minh
Định nghĩa các hàm và như sau:
26
Khi đó: áp dụng định lí 2.5 [2], ta có:
Theo ví dụ 1.6 [2] :
Vì vậy, .
Chú ý phép lấy bao đóng ở đây bỏ được.
Vì g là hàm lồi, cho nên g chính quy tại (định lí 2.3(ii) [2]). Khi đó (1.13)
có dấu bằng và f chính quy tại .
27
Chương 2
BÀI TOÁN SYLVESTER VÀ BÀI TOÁN
FERMAT – TORRICELLI CHO HÌNH CẦU EUCLID
Chương 2 trình bày các kết quả nghiên cứu mới của N. M. Nam, N. Hoang,
N. T. An ( [3], 2014 ) về sự tồn tại và duy nhất nghiệm, điều kiện tối ưu và cách
giải cho bài toán Sylvester và bài toán Fermat – Torricelli với các hình cầu
Euclid bằng công cụ dưới vi phân hàm lồi. Trường hợp riêng quan trọng của bài
toán Sylvester với ba hình cầu cũng được trình bày trong chương này. Các kết
quả trình bày trong chương này được tham khảo trong [3] – [6].
2.1. KHÁI NIỆM VÀ ĐỊNH NGHĨA
Giả sử I và J là hai tập chỉ số hữu hạn sao cho |I| + |J| > 1, trong đó |I| là
0) với số phần tử của I. Giả sử 𝔹 là hình cầu đơn vị đóng, và := 𝔹(ai; ri) (ri
i I, 0) với j J, là hai tập họ các hình cầu đóng trong ℝn := 𝔹(bj; sj) (sj
được trang bị chuẩn || . || .
Với một tập lồi đóng bị chặn Q, hàm khoảng cách xa nhất và hàm khoảng
cách đến Q được cho bởi:
M (x; Q) := sup {||x – q|| | q Q},
và
D (x; Q) := inf {||x – q|| | q Q}.
Bài toán Sylvester suy rộng cho các hình cầu Euclidean qui về bài toán tối ưu
sau đây:
min 𝒢(x) := max {ℳ (x), 𝒟 (x)}, x ℝn , (2.1)
trong đó
28
) | i ) | j J}. ℳ (x) := max {M (x; I} và 𝒟 (x) := max{ D(x;
Tương tự, mô hình tối ưu toán học của bài toán Torricelli suy rộng là:
ℝn, (2.2) min ℋ(x) := ℳ1(x) + 𝒟1(x), x
trong đó
. ℳ 1(x) := và 𝒟 1(x) :=
Tổng quát hóa qui tắc Fermat sau đây được gọi là qui tắc dưới vi phân
Fermat sẽ đóng vai trò quan trọng trong chương này:
là một nghiệm của hàm lồi nếu và chỉ nếu 0 . (2.3)
Bởi vì hàm 𝒢 và ℋ trong (2.1) và (2.2) được trình bày dưới ngôn ngữ là hàm
“max” và “tổng” của một số hữu hạn hàm lồi, chúng ta sẽ sử dụng các qui tắc
dưới vi phân trong giải tích lồi để sau đó nghiên cứu các bài toán này. Nếu (x)
:= max { (x) | i = 1, ... , k}, trong đó : ℝn ℝ với i = 1, ... , k là hàm lồi,
thì ta có:
= conv{ | i I( )}, (2.4)
trong đó I( ) := {i {1, ... , k} | = } là tập chỉ số tích cực tại .
Trong chương này chúng ta sẽ sử dụng các kí hiệu sau: bd và int
tương ứng là biên và phần trong của ; conv là kí hiệu bao lồi của ; với a, b
b, ℝn và a
[a, b] := {ta + (1 – t)b | t [0. 1]};
(a, b) := {ta + (1 – t)b | t (0. 1)};
L(a, b) := {ta + (1 – t)b | t ℝ}.
2.2. BÀI TOÁN SYLVESTER CHO HÌNH CẦU EUCLID
2.2.1. Sự tồn tại, duy nhất nghiệm và điều kiện tối ưu.
Trong chương này chúng ta nghiên cứu bài toán Sylvester suy rộng và
29
mối quan hệ của nó với bài toán Apollonius: Cho hai họ hữu hạn các hình cầu
Euclid, hãy tìm một hình cầu Euclid nhỏ nhất chứa các hình cầu của họ thứ nhất
và cắt tất cả các hình cầu của họ thứ hai. Chúng ta cũng nghiên cứu bài toán
Fermat – Torricelli suy rộng như sau: Cho hai họ hữu hạn các hình cầu Euclid,
tìm một điểm làm cực tiểu tổng khoảng cách xa nhất đến các hình cầu của họ thứ
nhất và khoảng cách gần nhất đến các hình cầu của họ thứ hai.
Ta bắt đầu mục này với các công thức đơn giản để tính khoảng cách đến
hình cầu Euclid trong ℝn cũng như dưới vi phân.
Mệnh đề 2.1
Giả sử 0. Với bất kỳ x = 𝔹 (c; r), trong đó c ℝn và r ℝn, ta có:
D(x; ) = { 0, 𝑛ế𝑢 ‖𝑥 − 𝑐‖ ≤ 𝑟, ‖𝑥 − 𝑐‖ − 𝑟, 𝑡ạ𝑖 𝑛ℎữ𝑛𝑔 đ𝑖ể𝑚 𝑐ò𝑛 𝑙ạ𝑖,
và
M(x; ) = ||x – c|| + r.
Hơn nữa,
𝑁(𝑥̅; 𝛺) ∩ 𝔹, 𝑛ế𝑢 ‖ − 𝑐‖ ≤ 𝑟;
−𝑐
‖ −𝑐‖
D( ; ) = } , 𝑡ạ𝑖 𝑛ℎữ𝑛𝑔 đ𝑖ể𝑚 𝑐ò𝑛 𝑙ạ𝑖,
{ {
và
−𝑐
𝔹, 𝑛ế𝑢 𝑥̅ = 𝑐,
M( ; } , 𝑛ế𝑢 𝑥 ≠ 𝑐. ) = { { ‖ −𝑐‖
Với bất kỳ x ℝn, ta kí hiệu:
i) = 𝒢(x)}
K(x) := {i I | M(x;
và L(x) := {j J | D(x; ) = 𝒢(x)}.
30
Tập các chỉ số tích cực A(x) được cho bởi hợp rời nhau A(x) = K(x) ⊔ L(x). Rõ
ràng với mọi x |A(x)| |I| + |J|. ℝn, ta có 1
Định lý sau đây thiết lập điều kiện cần và đủ cho tính duy nhất của
nghiệm tối ưu.
Định lý 2.1
Bài toán tối ưu (2.1) luôn có một nghiệm tối ưu. Hơn nữa, nghiệm là duy
nhất nếu và chỉ nếu I , hoặc I = và chứa không quá một điểm.
Chứng minh
Sự kiện (2.1) luôn có một nghiệm tối ưu suy ra từ tính liên tục của hàm 𝒢
ở đó và tính bị chặn của các tập mức.
Ta chứng minh điều kiện đủ cho tính duy nhất của nghiệm tối ưu. Xét
trường hợp I ta sẽ chỉ ra rằng
I, j J}. (2.5) 𝒢(x) = max { ||x – ai|| + ri, ||x – bj|| - sj | i
i) = ||x – ai|| + ri và D(x;
Bởi vì M(x; ) = max {||x – bj|| - sj, 0} ||x – bj|| -
sj, ta luôn có:
I, j J}. 𝒢(x) max { ||x – ai|| + ri , ||x – bj|| - sj | i
I. Nếu K(x) , thì với một phần tử i K(x) , ta có: Cố định i0
I, j J}. 𝒢(x) = ||x – ai|| + ri max{||x – ai|| + ri , ||x – bj|| - sj | i
Trong trường hợp K(x) = , ta có L(x) . Cố định j L(x). Khi đó 𝒢(x) =
D(x; ) > M(x; ) 0. Như vậy x , và khi đó:
I, j J}. 𝒢(x) = ||x – bj|| - sj max{||x – ai|| + ri , ||x – bj|| - sj | i
J}. Từ (2.5) Ta đã chỉ ra được (2.5). Chọn một hằng số l sao cho l > max{ sj | j
ta suy ra là một nghiệm tối ưu của (2.1) nếu và chỉ nếu nó là một nghiệm của
bài toán tối ưu sau:
31
Min 𝒢̃(𝑥) , x ℝn , (2.6)
trong đó
I, j J} = (𝒢(x) + l)2 . 𝒢̃(𝑥) := max{( ||x – ai|| + ri + l)2 , (||x – bj|| + l – sj)2 | i
I và j J là Bởi vì fi(x) := (||x – ai|| + ri + l)2 và gj(x) := (||x – bj|| + l – sj)2 với i
các hàm lồi chặt, cho nên (2.6) có một nghiệm tối ưu duy nhất, và khi đó (2.1)
cũng có một nghiệm tối ưu duy nhất.
Giả sử rằng I = và chứa nhiều nhất một điểm. Nếu
chứa đúng một điểm x0, thì 𝒢(x0) = 0 và x0 là nghiệm duy nhất. Trong trường
hợp = thì dễ chỉ ra rằng (2.5) thỏa mãn với mọi x ℝn, và (1) có một
nghiệm duy nhất.
Bây giờ ta chứng minh điều kiện cần cho tính duy nhất nghiệm. Giả sử
(2.1) có một nghiệm duy nhất và giả sử ngược lại rằng I = và chứa
. Như vậy, bất kỳ nhiều hơn một điểm. Rõ ràng, 𝒢(x) = 0 với bất kỳ x
x là nghiệm tối ưu của bài toán. Vì vậy, ta đi đến một mâu thuẫn và
định lý được chứng minh.
Với bất kỳ điểm x ℝn, hình chiếu xa nhất và hình chiếu gần nhất từ x
đến tập Q được cho, tương ứng, bởi:
Q | ||x – q || = M(x; Q)}, 𝒫(x; Q) := {q
và
∏(x; Q) := {q Q | ||x – q|| = D(x; Q)}.
Nếu Q = 𝔹 (c; r), thì:
32
𝑥−𝑐 ‖𝑥−𝑐‖
𝑏𝑑(𝑄), 𝑛ế𝑢 𝑥 = 𝑐 𝒫(x; Q) = { {𝑐 − 𝑟 } , 𝑛ế𝑢 𝑥 ≠ 𝑐,
và
𝑥−𝑐 ‖𝑥−𝑐‖
{𝑥} , 𝑛ế𝑢 ‖𝑥 − 𝑐‖ ≤ 𝑟, ∏(x; Q) = { {𝑐 + 𝑟 } , 𝑡ạ𝑖 𝑐á𝑐 đ𝑖ể𝑚 𝑐ò𝑛 𝑙ạ𝑖.
Trong trường hợp ri = 0, hình cầu 𝔹(ai ; ri) = {ai}, vì vậy một hình cầu
chứa 𝔹(ai ; ri) nếu và chỉ nếu nó cắt tất cả các hình cầu. Hơn nữa, trong trường
hợp I = đã được xét trong [18]. Như vậy, ta loại bỏ được trường hợp này trong
định lý dưới đây.
Định lý 2.2
Giả sử rằng I I. Một phần tử là nghiệm tối với ri > 0 với mọi i
ưu của (2.1) nếu và chỉ nếu một trong các điều kiện sau đây đúng:
), trùng với k hình cầu trong các với i I, k (i) 𝔹 ( ; r), r = 𝒢( 1,
; r) chứa các hình cầu khác trong { | i I}, và nó cắt với j J. 𝔹 (
; ) với i K( ) là các tập một điểm, và với j L( ). Hơn nữa, (ii) 𝒫(
; ; ), i K( ), j L( ), ta có: với pi := 𝒫( ), qj := ∏(
K( ),j L( )}. conv{ pi , qj | i
Chứng minh
Chú ý rằng trong trường hợp này, (2.1) có một nghiệm duy nhất. Theo qui tắc
Fermat dưới vi phân, là nghiệm tối ưu của bài toán, nếu và chỉ nếu:
0 ) = conv { M( ; ), D( ; ) | i K( ), j L( )}. (2.7) 𝒢(
K( ) | M( ; , thì Giả sử ℐ := { i ) không là tập một điểm}. Nếu ℐ
) = r = M( ; ℐ. Vì thế tất cả các hình cầu = ai và 𝒢( ) = ri với mọi i
33
với i ℐ trùng nhau. Hơn nữa,
; ) M( ; ℐ và j I \ ℐ, ri = M( ) = ||ai – aj|| + rj với i
; ) D( ; ) J. Như ℐ và j và ri = M ( ||ai – bj|| - sj với mọi i
; r) chứa các hình cầu trong { | i với j J. vậy, 𝔹 ( I \ ℐ} và cắt
. Khi đó M( ; ) là tập một điểm với mọi Xét trường hợp ℐ =
i K( ; ) là tập một điểm với một i như vậy. Với ). Điều này kéo theo 𝒫(
mọi j L( ), bởi vì D( ; ) ; ) > 0 với một chỉ số cố định i0 M( I,
ta có . Khi đó (2.7) được viết tương đương như sau:
0 conv ,
) = || trong đó r = 𝒢( - pi|| = || - qj||.
Như vậy, tồn tại 0 với i K( ) và 0 với j L( ) sao cho
= 1 và
+
0 = .
Một cách tương đương,
= K( ),j L( )}. conv{ pi , qj | i
Chứng minh phần ngược lại suy ra từ qui tắc dưới vi phân Fermat bởi vì chúng ta
có thể kiểm tra rằng (2.7) thỏa mãn trong mỗi trường hợp.
Cuối cùng, sử dụng định lý Caratheodory và định lý 1.3.6 [4], ta có thể
chứng minh mệnh đề dưới đây.
Mệnh đề 2.2
34
Giả sử rằng I I. Nếu là nghiệm tối ưu của với ri > 0 với mọi i
n + 1 sao cho (2.1), thì tồn tại các tập chỉ số I1 I và J1 J với 1 < |I1| + |J1|
là nghiệm của bài toán Sylvester suy rộng với tập mục tiêu , i , j I1, và
J1.
2.2.2. Bài toán Sylvester suy rộng ba hình cầu.
Trong phần này, chúng ta nghiên cứu bài toán Sylvester suy rộng cho trường hợp
ba hình cầu Euclid trong không gian hai chiều. Từ mệnh đề 2.2, ta thấy rằng đây
là trường hợp quan trọng nhất bởi vì nó có thể qui về bài toán bao hàm một số
lớn các hình cầu qui từ bài toán đó về bài toán ba hình cầu hoặc ít hơn. Quan sát
này được sử dụng như một ý tưởng chính cho nhiều thuật giải để giải các bài
toán hình cầu cực tiểu cổ điển.
Với hai hình cầu 𝔹(a; r) và 𝔹(b; s), ta nói rằng 𝔹(a; r) chứa ngặt 𝔹(b; s)
nếu 𝔹 (b; s) 𝔹 (a; r) và chúng không có điểm biên chung; 𝔹 (a; r) chứa tiếp
xúc 𝔹 (b; s) nếu 𝔹 (b; s) 𝔹 (a; r) và chúng có đúng một điểm biên chung. Ta
cũng nói rằng hai hình cầu giao chặt nếu chúng cắt tại nhiều hơn một điểm, và
giao tiếp xúc nếu chúng cắt tại đúng một điểm.
Bài toán ba hình cầu: Mô hình I Mô hình thứ nhất chúng ta nghiên cứu trong
phần này được phát biểu như sau: cho ba hình cầu tùy ý = 𝔹(ai ; ri) với i = 1,
2, 3 trong mặt phẳng Euclid, hãy dựng hình cầu nhỏ nhất chứa được tất cả các
hình cầu đã cho. Trong trường hợp này, I = {1, 2, 3}, J = , và (2.1) qui về bài
toán:
) = max{M (x ; ) , M (x ; ) , M (x ; )} , x min 𝒢( ℝ2 (2.8)
Mệnh đề 2.3
Với ), ta có |K( )| = 1 và là nghiệm của (2.8) nếu ℝ2 và r := 𝒢(
35
và chỉ nếu
; r) 𝔹( I, và 𝔹( ; r) trùng với một trong các hình cầu 𝔹(ai ; ri) với i
chứa ngặt các hình cầu khác .
Chứng minh
Để ý rằng (2.8) có một nghiệm duy nhất theo định lý 2.1. Giả sử |K( )| =
1, chẳng hạn K( ) = {1}. Bởi vì là nghiệm duy nhất của (2.8), ta có:
0 M ( ; ).
) = M ( ; ), và r > M ( ; ) với i = 2, 3. Bởi vì Hơn nữa, r = 𝒢(
0 M ( ; ), ta suy ra biểu diễn dưới vi phân của M ( . ; ) theo mệnh đề
2.1 với = a1. Vì vậy :
r = M ( ; ) = M (a1 ; ) = r1.
; r) Hơn nữa, r > M (a1 ; ) = ||a1 – ai|| + ri với i = 2, 3. Điều này kéo theo 𝔹(
= 𝔹 (a1 ; r1) và chứa ngặt hai hình cầu khác.
; r) trùng Chứng minh phần ngược lại trực tiếp. Thật vậy, giả sử rằng 𝔹(
với 𝔹 (a1 ; r1) và chứa ngặt các hình cầu khác. Khi đó = a1, 𝒢( ) = r = r1 =
M ( ; ; ) với i = 2, 3. Như vậy, K( ) = ), và 𝒢( ) > ||a1 – ai|| + ri = M (
{1}, và 0 là nghiệm của (2.8). 𝒢( ) = 𝔹. Do đó,
Chúng ta sẽ sử dụng kí hiệu sau đây :
); u1 := 𝒫 (a2 ; ), v1 := 𝒫 (a3 ; ), w1 := , t1 := 𝒫 (w1 ;
); u2 := 𝒫 (a3 ; ), v2 := 𝒫 (a1 ; ), w2 := , t2 := 𝒫 (w2 ;
). u3 := 𝒫 (a1 ; ), v3 := 𝒫 (a2 ; ), w3 := , t3 := 𝒫 (w3 ;
Với a, b, c ℝ2 , kí hiệu có nghĩa là góc tạo bởi vectơ 𝑎𝑏⃗⃗⃗⃗ và vectơ 𝑎𝑐⃗⃗⃗⃗ .
36
Mệnh đề 2.4
Với ), ta có |K( )| = 2 và là nghiệm của (2.8) nếu ℝ2 và r := 𝒢(
và chỉ nếu các điều kiện sau đây đúng:
I và chứa ngặt (i) 𝔹( ; r) trùng với hai hình cầu trong số 𝔹(ai ; ri) với i
các hình cầu còn lại.
I, (ii) 𝔹( ; r) trùng với một trong các hình cầu trong số 𝔹(ai ; ri) với i
; r) chứa ngặt các hình cầu còn lại và chứa tiếp xúc với các hình cầu còn 𝔹(
lại.
(iii) Tồn tại i I sao cho > 90o, . = wi , và r =
Chứng minh
Giả sử |K( )| = 2, chẳng hạn, K( ) = {1, 2}. Xét các trường hợp sau đây:
Trường hợp 1: = a1 = a2. Trong trường hợp này,
r = M ( ; ) = M ( ; ; ), ) = r1 = r2 > M (
; r) = = ; r) chứa ngặt . Như vậy (i) đúng. Vì vậy 𝔹( , và 𝔹(
Trường hợp 2: = a1 và a2, hoặc a1 và = a2 . Ta xét, chẳng hạn,
trường hợp = a1 và a2. Khi đó ta có:
= a1 , ||a1 – a2|| = r1 – r2 và ||a1 – a3|| < r1 – r3 .
; r) Như vậy, 𝔹( ; r) = 𝔹 (a1 ; r1) , 𝔹( ; r) chứa tiếp xúc 𝔹 (a2 ; r2), và 𝔹(
chứa ngặt 𝔹 (a3 ; r3). Trong trường hợp này, (ii) đúng.
Trường hợp 3: ; ; ) a1 và a2 . Khi đó cả p1 := 𝒫 ( ) và p2 := 𝒫 (
là tập một điểm. Từ định lý 2.2 suy ra = . Hơn nữa,
|| . - a3|| + r3 <
37
Trong trường hợp này, sử dụng biểu diễn của khoảng cách xa nhất, ta có thuộc
đoạn thẳng mở (a1 , a2) mà nối a1 với a2, và = w3 . Ta cũng có p1 = u3, p2 = v3,
và lớn hơn 90o. Như vậy, (iii) đúng.
Từ Định lý 2.2, chiều ngược lại với điều kiện (i) hoặc (ii) được suy ra trực
tiếp. Giả sử (iii) đúng. Khi đó:
M ( ; ) = M ( ; ) > M ( ; ) .
Vì vậy K( ; ; = , ) = {1, 2}. Bởi vì 𝒫 ( ) = u3 , 𝒫 ( ) = v3, và
theo Định lý 2.2, phần tử là nghiệm của (2.8).
)| = 2
Hình 1. Mô hình I với |K( ti
ui wi vi
Mệnh đề 2.5
Với ), ta có |K( )| = 3 và là nghiệm của (2.8) nếu ℝ2 và r := 𝒢(
và chỉ nếu các điều kiện sau đây đúng:
; r) trùng với một trong các hình cầu với i I và chứa tiếp xúc với (i) 𝔹(
hai hình cầu còn lại
; r) trùng với hai hình cầu trong số với i I và chứa tiếp xúc với (ii) 𝔹(
38
hình cầu còn lại.
; r) trùng với cả ba hình cầu. (iii) 𝔹(
; ) là các tập một điểm với i I, (iv) 𝒫 ( conv {p1 , p2 , p3}, trong đó
; ) , và: pi := 𝒫 (
R = || - p1|| = || - p2|| = || - p3|| .
Chứng minh
Ta hãy chứng minh suy luận trên. Ta có:
0 ) = conv{ M ( ; ) , M ( ; ) , M ( ; )}, 𝒢(
và r = M ( ; ) = M ( ; ) = M ( ; ).
Xét các trường hợp sau đây.
Trường hợp 1: I. Nếu đúng một trùng với ít nhất một trong các tâm ai với i
; ) với i ; tập trong số 𝒫 ( I không là tập một điểm, chẳng hạn 𝒫 (
), thì = a1 và r = r1. Hơn nữa
M(a1 ; ) = r = ||a1 – ai|| + ri , với i = 2, 3.
Trong trường hợp này, chứa tiếp xúc hai hình cầu còn lại. Nếu đúng hai tập
; ) với i I không là các tập một điểm, thì (ii) đúng. Nếu tất trong số 𝒫 (
; ) với i I không là các tập một điểm, thì (iii) đúng. cả 𝒫 (
Trường hợp 2: I. Trong trường hợp không trùng với bất kỳ tâm nào ai với i
này, ta có || I, và theo Định lý 2.2, - pi|| = r với i conv{p1 , p2 , p3}.
Phần ngược lại được suy trực tiếp từ định lý 2.2.
Ta có thể xây dựng hình cầu nhỏ nhất mà nó chứa ba hình cầu trong mặt
phẳng như sau:
Bước 1: Nếu một trong ba hình cầu đã cho chứa hai hình cầu còn lại, chẳng hạn
39
, thì = a1 là nghiệm của bài toán và r = r1 là giá trị tối ưu. Nếu
không, ta chuyển sang bước tiếp theo
Hình 2. Mô hình I với |K(
)| = 3
Bước 2: Nếu một trong ba góc , i I , lớn hơn 90o , thì wi là nghiệm tối ưu
và r = là giá trị tối ưu. Nếu không, ta chuyển sang bước tiếp theo.
Bước 3: Hình cầu bao quanh nhỏ nhất trùng với hình cầu Apollonius mà chứa
tiếp xúc với i I (xem [5]) .
Bài toán Ba hình cầu: Mô hình II Ta xét mô hình thứ hai của bài toán
Sylvester suy rộng có ba hình cầu: cho ba hình cầu trong ℝ2, đó là = 𝔹 (ai ; ri)
với i = 1, 2 và và cắt . = 𝔹 (b1 ; s1). Tìm hình cầu nhỏ nhất chứa
Trong trường hợp này, I = {1, 2}, J = {1}, và (2.1) qui về bài toán:
) = max{M(x ; ), M(x ; ), D(x ; )}, x min 𝒢( ℝ2 . (2.9)
Với bất kỳ u {0, 1, 2}, |L(u)| {0, 1}, và 1 |K(u)| + |L(u)| ℝ2, ta có |K(u)|
3.
40
Trong trường hợp này, (2.9) có một nghiệm tối ưu duy nhất theo Định lý 2.1 .
Mệnh đề 2.6
Với ) , ta có là nghiệm của (2.9) và |K(u)| + |L(u)| ℝ2 và r := 𝒢(
; r) trùng với một trong các hình cầu với i = 1, 2, = 1 nếu và chỉ nếu 𝔹(
chứa ngặt các hình cầu khác, và cắt ngặt .
Chứng minh
Giả sử |K(u)| + |L(u)| = 1. Khi đó |K( )| = 1 và |L( )| = 0, hoặc |K( )| = 0
và |L( )| = 1. Ta xét trường hợp đầu tiên |K( )| = 0 và |L( )| = 1. Trong trường
) = D( ; ) > 0 và hợp này, ta có 𝒢(
0 ) = D( ; ). 𝒢(
Khi đó , và vì vậy, D ( ; ) = . Ta đi đến một mâu thuẫn
bởi vì b1 .
Xét trường hợp khi |K( )| = 1 và |L( )| = 0. Giả sử K( ) = {1}. Khi đó:
0 ) = M( ; ). 𝒢(
Điều này kéo theo ) = M( ; = a1, 𝒢( ) = r1 > M( ; r2) = ||a1 – a2|| + r2 , và:
) = M( ; ; ) 𝒢( ) = r1 > D( ||a1 – b1|| - s1 .
Trong trường hợp này, kết luận thỏa mãn. Điều ngược lại dễ chứng minh.
Chúng ta sẽ sử dụng kí hiệu sau đây:
); u1 := 𝒫(b1 ; ), v1 := Π(a1 ; ), w1 := t1 := 𝒫(w1 ;
). u2 := 𝒫(b2 ; ), v2 := Π(a2 ; ), w2 := t2 := 𝒫(w2 ;
Mệnh đề 2.7
41
Với ) , ta có là nghiệm của (2.9) và |K( )| = |L( )| ℝ2 và r := 𝒢(
= 1 nếu và chỉ nếu một trong các điều kiện sau đây là đúng:
; r) trùng với một trong các hình cầu với i = 1, 2, chứa ngặt các hình (i) 𝔹(
cầu khác, và giao tiếp xúc với .
(ii) Một trong các góc với i = 1, 2 lớn hơn 90o, = wi , và r =
Chứng minh
Giả sử là một nghiệm của bài toán và |K( )| = |L( )| = 1. Khi đó |K(
)| = {1} hoặc |K( )| = {2} và |L( )| = {1}. Xét trường hợp khi |K( )| = {1} và
|L( )| = {1}. Khi đó:
) = M( ; ) = D( ; ) > M( ; ) r := 𝒢(
và
0 ) = conv{ M( ; ) , D( ; )}. 𝒢(
Bởi vì D( ; ) > 0 , ta có . Để ý rằng, nếu ; ) = = a1, thì r1 > M(
; ) = D( ; ||a1 – a2|| + r2, và r1 = M( ) = ||a1 – b1|| - s1. Trong trường hợp
này, (i) đúng.
Xét trương hợp khi = ; a1. Theo Định lý 2.2, khi y1 = 𝒫(
; ) và z1 = Π( ). Trong trương hợp này, y1 = u1 , z1 = v1, và = w1. Bởi vì
r = > 90o. Chứng minh điều ngược > M(w1 ; ) = ||w1 – t1||, ta có
lại dễ dàng.
Kí hiệu:
), y := , z := Π( ; ). x1 := 𝒫(a2 ; ), x2 := 𝒫(a1 ;
42
Mệnh đề 2.8
Với ) , ta có là nghiệm của (2.9) và |K( )| = 2, ℝ2 và r := 𝒢(
|L( )| = 0 nếu và chỉ nếu một trong các điều kiện sau đây là đúng:
; r) trùng với cả hai với i = 1, 2 , và cắt chặt (i) 𝔹(
; r) trùng với một trong các hình cầu với i = 1, 2, chứa tiếp xúc với (ii) 𝔹(
hình cầu khác và cắt ngặt
(iii) Góc lớn hơn 90o, = y, và r =
Chứng minh
Giả sử là một nghiệm của (2.9), K( ) = {1, 2}, và L( ) = . Khi đó:
) = M( ; ) = M( ; ) > D( ; ), r = 𝒢(
và
0 ) = conv{ M( ; ) , M( ; ) }. 𝒢(
Xét các trường hợp sau:
Trường hợp 1: = a1 và = a2. Trong trường hợp này, r1 = r2 = r, và vì vậy,
; r) = = . Mặt khác, bởi vì D( ; ; r) cắt ngặt . 𝔹( ) < r , ta có 𝔹(
Trường hợp 2: = a1 và a2. Trong trường hợp này, r1 = r = r2 + || - a2||.
; r) = . Bởi vì || ; ; r) Như vậy, 𝔹( ) < r, ta có 𝔹( - a2|| = r1 – r2 và D(
chứa tiếp xúc và cắt ngặt .
Trường hợp 3: a1 và a2. Sử dụng Định lý 2.2, ta có:
(0, 1). = tx1 + (1 – t)x2 , t
Bởi vì bài toán có một nghiệm duy nhất, t = 1 / 2, tức là = = y và r =
43
. Bởi vì D( ; ) < r, hoặc ||y – z|| < r, góc lớn hơn 90o.
Dễ dàng chứng minh được điều kiện đủ.
Mệnh đề 2.9
Với ) , ta có là nghiệm của (2.9) và |K( )| = 2, |L( ℝ2 và r := 𝒢(
)| = 1 nếu và chỉ nếu một trong các điều kiện sau đây đúng:
; r) trùng với cả hai hình cầu với i = 1, 2, và giao tiếp xúc với (i) 𝔹(
; r) trùng với một trong các hình cầu với i = 1, 2, chứa tiếp xúc với (ii) 𝔹(
hình cầu khác và giao tiếp xúc với
; )với i = 1, 2 là các tập một điểm và , || (iii) 𝒫( - p1|| = || - p2||
= || ; ; ), và conv - q1|| , trong đó pi = 𝒫( ) với i = 1, 2 và q1 := Π(
{p1, p2, q1}.
Chứng minh
Giả sử là một nghiệm của bài toán và K( ) = {1, 2}, và L( ) = {1}.
Khi đó:
) = M( ; ) = M( ; ) > D( ; ) r = 𝒢(
và
0 ) = conv{ M( ; ) , M( ; ) , D( ; )}. 𝒢(
Ta xét các trường hợp sau đây:
Trường hợp 1: = a1 và = a2. Trong trường hợp này, r1 = r2 = r, và vì vậy 𝔹(
; r) = = . Mặt khác, bởi vì D( ; ; r) giao tiếp xúc với ) = r, ta có 𝔹(
Trường hợp 2: = a1 và a2. Trong trường hợp này, r1 = r = r2 + || - a2||.
; r) = . Bởi vì || ; ; r) Như vậy, 𝔹( ) = r, ta có 𝔹( - a2|| = r1 – r2 và D(
44
chứa tiếp xúc và giao tiếp xúc .
Trường hợp 3: ; ) với i = 1, 2 là a1 và a2. Trong trường hợp này, 𝒫(
các tập một điểm.
Hình 3. Mô hình II với |K(
)| = 1, |L(
)| = 1
t1
u . . .v1
w1
Hình 4. Mô hình II với |K(
)| = 2, |L(
)| = 0
z
x1 x2
45
Hình 5. Mô hình II với |K(
)| = 2, |L(
)| = 1
Sử dụng định lý 2.2, ta có = t1p1 + t2p2 + t3p1, ti [0, 1], trong đó t1 + t2 + t3
= 1. Hơn nữa, || - p1|| = || - p2|| = || - q1||.
Chứng minh điều kiện đủ là tức khắc.
Bây giờ ta có thể xây dựng hình cầu nhỏ nhất mà tương ứng với nghiệm
của (2.9) như sau (xem các hình 3, 4, 5).
Bước 1: nếu có một hình cầu trong số và mà chứa các hình cầu khác và
cắt , thì hình cầu đó là nghiệm của bài toán Sylvester suy rộng. Nếu không, ta
đi đến bước tiếp theo.
Bước 2: Một trong các góc với i = 1, 2 lớn hơn 90o , . = wi và r =
Nếu không, ta đi đến bước tiếp theo.
Bước 3: Góc lớn hơn 90o, = y và r = . Nếu không ta đi đến bước
46
tiếp theo.
Bước 4: Trong trường hợp này, hình cầu nhỏ nhất là hình cầu Apollonius mà
chứa tiếp xúc , và giao tiếp xúc .
Bài toán Ba - Hình Cầu: Mô hình III. Ta xét mô hình thứ ba của bài toán
Sylvester suy rộng gồm ba hình cầu: Cho ba hình cầu = = 𝔹 (a1 ; r1),
và cắt và 𝔹 (b1 ; s1), và = 𝔹 (b2 ; s2), tìm hình cầu nhỏ nhất mà chứa
. Trong trường hợp này, I = {1}, J = {1, 2}, và (2.1) qui về bài toán:
) = max{M(x ; ), D(x ; ), D(x ; )}, x min 𝒢( ℝ2. (2.10)
với {i, j} = {1, 2}, ta sử dụng kí hiệu sau đây:
); ci := 𝒫(bi ; ), di := Π(a1 ; ), ei := , fi := Π(ei ;
), z := ) . , t := 𝒫(z ; yj := Π(bi ;
Tương tự ta có kết quả sau:
Mệnh đề 2.10
Với ). Các điều kiện sau đây đúng: ℝ2 và r := 𝒢(
(i) Phần tử là nghiệm của (2.10) và |K( )| + |L( ; r) )| = nếu và chỉ nếu 𝔹(
trùng với và giao ngặt với cả và .
(ii) Phần tử là nghiệm của (2.10) và |K( )| = |L( )| = 1 nếu và chỉ nếu một
các điều kiện sau đây đúng:
; r) trùng với , giao tiếp xúc với một trong các hình cầu với (a) 𝔹(
i = 1, 2 và giao ngặt với các hình cầu còn lại.
(b) Tồn tại i J sao cho > 90o , . = ei, và r =
(iii) Phần tử là nghiệm của (2.10) và |K( )| = 0, |L( )| = 2 nếu và chỉ nếu
47
> 90o , = z, và r = .
(iv) Phần tử là nghiệm của (2.10) và |K( )| = 1 và |L( )| = 2 nếu và chỉ nếu
một trong các điều kiện sau đây đúng.
; r) trùng với , giao tiếp xúc với cả hai với i = 1, 2. (a) 𝔹(
; ) là tập một điểm và với i = 1, 2,|| (b) 𝒫( - p1|| = || - q2||,
; ; ) với i = 1, 2, và trong đó p1 = 𝒫( ) và qi := Π( conv{p1, q1, p2}.
Bây giờ ta có thể dựng hình cầu nhỏ nhất mà tương ứng với nghiệm của
(2.10) như sau (xem các hình 6, 7, 8).
Hình 6. Mô hình III với |K(
)| = 1, |L(
)| =1
fi ci ei di
48
Hình 7. Mô hình III với |K(
)| = 0, |L(
)| = 2
t y1 z y2
)| = 1, |L(
)| = 2
Hình 8. Mô hình III với |K(
Bước 1: Nếu và , thì = a1 là nghiệm của bài toán
và r1 là giá trị tối ưu. Nếu không, đi đến bước tiếp theo.
Bước 2: Nêu một trong các góc với i = 1, 2, lớn hơn 90o, thì = ei, r =
. Nếu không , đi đến bước tiếp theo.
Bước 3: nếu góc > 90o , thì = z và r = . Nếu không, đi đến bước
49
tiếp theo.
Bước 4: Trong trường hợp này, hình cầu nhỏ nhất là hình cầu Apollonius mà
chứa tiếp xúc và giao tiếp xúc .
Bài toán Ba Hình Cầu: Mô hình IV. Bây giờ ta xét bài toán hình cầu giao nhỏ
nhất: Cho ba hình cầu = 𝔹(bi ; si) với i = 1, 2, 3, tìm hình cầu nhỏ nhất mà cắt
với i = 1, 2, 3. Trong trường hợp này, I = , J = {1, 2, 3}, và (2.1) qui về bài
toán:
) = max{D(x ; ), D(x ; ), D(x ; )} x min 𝒢( ℝ2. (2.11)
Trong trường hợp này , điểm bất kỳ trong giao này là một nghiệm
của (2.11). Vì thế ta chỉ xét trường hợp khi giao này bằng rỗng. Từ Định lý 2.1,
(2.11) có một nghiệm duy nhất. Dễ thấy rằng |A( )| = |L( )| 2.
Ta sẽ sử dụng kí hiệu sau đây:
bd( bd( ), u1 := [b2, b3] ), v1 := [b2, b3]
bd( bd( ), u2 := [b1, b3] ), v2 := [b1, b3]
bd( bd( ), u3 := [b1, b2] ), v3 := [b1, b2]
, m1 := , m2 := , m3 :=
) , x1 := Π(m1 ; ) , x2 := Π(m2 ; ) , x3 := Π(m3 ;
. 𝔹1 := 𝔹 , 𝔹2 := 𝔹 , 𝔹3 := 𝔹
Dễ thấy rằng hình cầu giao nhỏ nhất có thể được dựng như dưới đây
(xem các hình 9, 10).
Bước 1: Nếu tồn tại j {1, 2, 3} sao cho lớn hơn 90o, thì 𝔹j là hình cầu
nhỏ nhất. Nếu không, đi đến bước tiếp theo.
50
Bước 2: Hình cầu giao nhỏ nhất là hình cầu Apollonius giao tiếp xúc với ba hình
cầu.
Hình 9. Mô hình IV với |L(
)| = 2
xj uj mj vj
)| = 3
Hình 10. Mô hình IV với |L(
51
2.3. BÀI TOÁN FERMAT – TORRICELLI CỔ ĐIỂN CHO HÌNH CẦU
EUCLID.
Trong phân này, ta xét bài toán sau:
+ , x min ℋ(x) = ℝ2, (2.12)
Trong đó |I| + |J| = 3. Rõ ràng, là nghiệm của (2.12) nếu và chỉ nếu nó là
nghiệm của bài toán dưới đây:
+ , x min ℋ(x) = ℝ2. (2.13)
Vì tập một điểm là một hình cầu với bán kính 0, cho nên ta chỉ cần xét bài toán
sau là đủ:
, x min ℋ(x) = ℝ2.
Trong phần này, ta giả sử rằng cho hình cầu có tâm phân biệt bởi vì các trường
hợp khác là tầm thường.
2.3.1. Sự tồn tại và duy nhất của nghiệm tối ưu.
Ta nghiên cứu tính chất nghiệm của (2.13) mà từ đó có thể dẫn điều kiện cần và
đủ cho bài toán có một nghiệm duy nhất.
Mệnh đề 2.11
Tập nghiệm S của (2.13) là một tập lồi compact khác rỗng trong ℝ2 .
Chứng minh
Rõ ràng, hàm ℋ(x) là liên tục. Với bất kỳ ℋ(x) , dễ thấy
} compact. Vì vậy, (2.13) luôn có một nghiệm rằng tập hợp {x ℝ2 | ℋ(x)
tối ưu. Nói riêng, S là compact. Bởi vì ℋ là lồi và liên tục, tập nghiệm cẩu bài
toán cũng lồi.
52
Với bất kỳ u ℝ2, kí hiệu:
A(u) := {i {1, 2, 3} | u }.
Mệnh đề 2.12
Giả sử |A(x*)| = 0. Khi đó x* là một nghiệm tối ưu của (2.13) nếu và chỉ
nếu x* là nghiệm của bài toán Fermat – Torricelli sinh ra bởi các tâm của các
hình cầu: b1, b2, b3.
Chứng minh
Giả sử rằng |A(x*)| = 0 và x* là một nghiệm tối ưu của (14). Khi đó x*
với i = 1, 2, 3. Chọn ) = với i = 1, 2, 3. Khi đó > 0 sao cho 𝔹(x*;
các điều kiện sau đây đúng với mọi x ): 𝔹(x*;
- - . ℋ(x) = = ℋ(x) = ℋ(x*)
Như vậy, x* là cực tiểu của bài toán.
Min ℱ(x) := , x ℝ2.
Vì thế nó cũng là cực tiểu toán cục của bài toán đó bởi vì ℱ là một hàm lồi. Do
đó, x* là nghiệm của Fermat – Torricelli sinh bởi b1, b2, b3. Điều ngược lại dễ
dàng chứng minh.
Bổ đề 2.1
Giả sử S là tập nghiệm của (2.13). Giả sử tồn tại x* S sao cho A(x*) =
. Khi đó S là tập một điểm, cụ thể S = {x*}.
Chứng minh
, ta Giả sử A(x*) = , và tồn tại y* S với x* y*. Bởi vì A(x*) =
có x* với i = 1, 2, 3. Khi đó x* là nghiệm của bài toán Fermat – Torricelli
S. sinh bởi tâm của các hình cầu b1, b2 và b3 . Bởi vì S là lồi , ta có [x*, y*]
53
Như vậy, có thể tìm được z* x* , z* S, và z* với i = 1, 2, 3. Khi đó z*
cũng là nghiệm của bài toán Fermat – Torricelli sinh bởi các tâm của các hình
cầu. Điều này là mâu thuẫn bởi vì bài toán này có nghiệm duy nhất.
Bổ đề 2.2
Với bất kỳ > 0, và a, b b, xét tập hợp: ℝ2 với a
E := {x }. ℝ2 | ||x – a|| + ||x – b|| =
Giả sử rằng||a – b|| < .Với x, y E và x y, ta có + < ,
và nói riêng, E.
Chứng minh
Ta có:
+ = (||x – a + y – a|| + ||x – b + y – b||)
(||x – a|| + ||y – a|| + ||x – b|| + ||y – b||) = .
Giả sử ngược lại:
+ = . (2.14)
Điều này nghĩa là E. Do một tính chất của chuẩn Euclid, ta có:
x – a = k(y – a) và x – b = m(y – b),
với các số k, m nào đó trong (0, ) \ {1} bởi vì x y. Điều này kéo theo:
a = - L(x, y) và b = - L(x, y).
Bởi vì > ||a – b||, dễ chỉ ra rằng x, y L(x, y) \ [a, b]. Ta cũng có
54
[a, b]. Thật vậy, giả sử chẳng hạn, thứ tự các điểm là: x, , a, b, y. Khi đó:
+ < ||x – a|| + ||x – b|| = .
Điều này mâu thuẫn với (2.14). Vì [a, b], ta có:
+ = ||a – b|| < .
Đây là một mâu thuẫn. Ta đã chứng minh được rằng + < .
Như vậy, E.
Giả sử là lồi chặt nếu với mọi x, là một tập con của ℝn. Ta nói rằng
y với x y và với bất kỳ t (0, 1), ta có tx + (1 – t)y int . Trong Bổ đề
2.2, tập:
:= {x } ℝ2 | ||x – a|| + ||x – b||
là lồi chặt.
Bổ đề 2.3
S sao cho Giả sử S là tập nghệm của (2.13). Giả sử rằng tồn tại x*
A(x*) = {i} và x* [bj, bk], trong đó i, j, k là các chỉ số phân biệt trong {1, 2, 3}.
Khi đó S là một tập một điểm, cụ thể S = {x*}.
Chứng minh
Giả sử rằng A(x*) = {1}. Khi đó x* , x* , x* và x* [b2,
b3].
Giả sử:
55
:= ||x* - b2|| + ||x* - b3|| = ℋ(x) + s2 + s3.
Khi đó > ||b2 – b3||. Kí hiệu:
E := { x ℝ2 | ||x – b2|| + ||x – b3|| = }
. Giả sử ngược lại rằng S không là tập một điểm. Khi Rõ ràng, x* E
đó tồn tại y* S và y* x*. Bởi vì S là lồi, [x* , y*] S. Ta có thể chọn z*
= và [x* , y*] để cho nó là đủ gần và phân biệt với x* sao cho [x* , z*]
. Khi đó [x* , z*] = . Trước hết ta chỉ ra z* . Thật vậy, giả sử z*
) = 0, và vì thế: D(z* ;
ℋ(z*) = ℋ(x) = D(z* ; ) + D(z* ; ) = ||z* - b2|| - s2 + ||z* - b3|| - s3 .
E. Bởi vì S và là lồi, S . Hơn nữa, Điều đó kéo theo z*
và . Ta lại có E. Điều này không thể xảy ra
. Điều đó mâu thuẫn với theo Bổ đề 2.2. Ta đã chỉ ra rằng z* S và A(z*) =
Bổ đề 2.1. Do đó, S phải là tập một điểm.
Bổ đề 2.4
{1, 2, 3}. Giả sử S là tập nghiệm của (2.13). Giả sử x* S và A(x*) = {i, j}
bd( ). Khi đó x*
Chứng minh
. Giả sử ngược lại Giả sử A(x*) = {1, 2}. Khi đó x* và x*
inf( ). Khi đó tồn tại ) . Giả sử p := x* > 0 với 𝔹(x* ;
) và ) thỏa mãn ||q Π(x* ; := ||x* - p|| > 0. Giả sử q [x* , p] 𝔹(x* ;
). Khi đó: – p|| < ||x* - p|| = D(x* ;
56
= D(q; ) ) ℋ(q) = ||q – p|| < ||x* - p|| = D(x* ;
= = ℋ(x*).
S. Đây là mâu thuẫn với sự kiện x*
Định lý 2.3
Giả sử = . Khi đó (2.13) có nhiều hơn một nghiệm nếu và chỉ
, với các chỉ số phân biệt i, j, k {1, 2, 3}, mà nếu tòn tại một tập [bi , bj]
chứa một điểm u thuộc phần trong của và |A(u)| = 1.
Chứng minh
và |A(u)| = 1. Giả sử [b1 , b2] chứa một điểm u mà thuộc vào phần trong của
Khi đó u và u . Ta có thể chọn v u, v , v [b1 , b2], v
và v int . Khi đó |A(v)| = 1. Trước hết ta chứng minh u là một nghiệm của
bài toán. Thật vậy, trong trường hợp này,
) + D(u ; ) + D(u ; ℋ(u) = D(u ; ) = ||b1 – b2|| - s1 – s2.
Chọn ) = ) = ) và 𝔹(u ; và 𝔹(u ; > 0 sao cho 𝔹(u ;
. Với mọi x ) , ta có: 𝔹(u ;
) + D(x ; ) ℋ(x) = D(x ;
= ||x – b1|| + ||x – b2|| - s1 – s2 ||b1 – b2|| -s1 – s2
= ℋ(u)
Điều này kéo theo u là cực tiểu địa phương của ℋ. Vì vậy nó cũng là một cực
tiểu toàn cục bởi vì ℋ(u) là lồi. Một lý luận tương đương có thể áp dụng với v.
Khi đó u, v S.
Bây giờ ta giả sử S có nhiều hơn một phần tử. Giả sử x* , y* là hai phần
57
S theo mệnh đề 2.11. Nếu tồn tại một tử riêng biệt của S. Khi đó [x* , y*]
nghiệm mà không thuộc vào với mọi i {1, 2, 3}, thì S qui về một tập một
điểm, điều đó là mâu thuẫn. Ta có thể giả sử rằng chứa vô hạn nghiệm. Khi
đó int cũng chứa vô hạn nghiệm do tính lồi chặt của . Nếu tồn tại một
nghiệm u như vậy với A(u) = {1} thì u int và u không thuộc vào .
Như vậy, u [b2, b3], bởi vì, nếu không, nghiệm đó phải duy nhất do bổ đề 2.3.
Do đó, kết luận đúng. Giả sử |A(u)| = 2 với mọi nghiệm mà thuộc vào int . Khi
đó có vô hạn nghiệm nằm trong tương giao của hai tập, là lồi chặt trong trường
hợp này. Vì vậy có một nghiệm mà thuộc vào phần trong của tương giao này,
điều đó là mâu thuẫn do Bổ đề 2.4.
Ví dụ 2.1. Trong hình 11, cho bài toán Fermat – Torricelli suy rộng có vô hạn
, và |A(u)| = 1 với mọi u (B, C). nghiệm bởi vì [b1, b2] cắt phần trong của
b2
Thật vậy, tập nghiệm là S = [B, C].
b3 B C b1
Hình 11. Một bài toán Fermat – Torricelli suy rộng với vô hạn nghiệm.
int với các chỉ số phân biệt i, j, k {1, 2, 3}. Giả sử Vk := [bi , bj]
58
Như một hệ quả trực tiếp của định lý 2.3, ta có hệ quả sau:
Hệ quả 2.1. Giả sử = . Khi đó (2.13) có nghiệm duy nhất nếu và chỉ
nếu suy luận sau là đúng với bất kỳ k {1, 2, 3}:
] [|A(u)| = 2 với mọi u [Vk Vk].
Hệ quả dưới đây cho ta điều kiện đủ để (2.13) có nghiệm duy nhất.
Hệ quả 2.2. Giả sử . Khi đó (2.13) có một nghiệm duy nhất nếu =
chứa nhiều nhất một điểm với các chỉ số phân biệt i, j, k {1, 2, [bi , bj]
3}.
Chứng minh
Giả sử ngược lại (2.13) có nhiều hơn một nghiệm. Do định lý trước, tồn
tại một khoảng, chẳng hạn [b1 , b2], mà nó chứa một điểm thuộc phần trong của
chứa vô hạn điểm, điều đó là một mâu thuẫn. . Khi đó [b1, b2]
2.3.2. Xây dựng nghiệm
Trong mục này, chúng ta trình bày một phương pháp xây dựng nghiệm của
(2.13) với ba hình cầu , i J = {1, 2, 3}.
Mệnh đề 2.13
Một phần tử x* là một nghiệm tối ưu của (2.13) nếu và chỉ nếu:
- , (2.15)
. trong đó ei :=
Chứng minh
Theo công thức dưới vi phân Fermat (3) và công thức dưới vi phân (5), x*
59
là một nghiệm tối ưu của (2.13) nếu và chỉ nếu:
0 = + . ℋ(x*) =
Khi đó kết luận được suy ra từ kết quả của mệnh đề 2.1.
Mệnh đề 2.14
Xét (2.13). Giả sử rằng . Khi đó:
S = .
Chứng minh
S bởi vì Cố định x* . Khi đó ℋ(x*) = 0, và vì vậy x*
0 . ℋ(x)
Ngược lại, với bất kỳ x ) = 0, S, ta có ℋ(x) ℋ(x*) = 0. Như vậy, D(x ;
với i = 1, 2, 3. Điều này kéo theo x với i = 1, 2, 3, hoặc tương đương x
.
Từ đây ta chỉ xét trường hợp = . Khi đó |A(x*)| < 3 với mọi
S. x*
Mệnh đề 2.15
Giả sử |A(x*)| = 2 và x* là một nghiệm tối ưu của (2.13), chẳng hạn x*
. Khi đó một trong các điều kiện sau đây đúng:
int . (i) Điểm x* là tương giao của [b1, b3] và biên của , và x*
int . (ii) Điểm x* là tương giao của [b2, b3] và biên của , và x*
và biên của , và (iii) Điểm x* thuộc vào giao của biên
–e3 = se1 + te2 ,
60
trong đó s, t với i = 1, 2, 3. [0, 1] và ei =
Ngược lại, nếu một trong các điều kiện trên thỏa mãn, thì x* là nghiệm tối ưu
của bài toán (2.13).
Chứng minh
. Theo mệnh đề 2.13, Giả sử |A(x*)| = 2 và x*
) ) 𝔹]. (2.16) –e3 [N(x*, 𝔹] + [N(x*,
bd bd . Bởi vì e3 0, ta có x* hoặc x*
bd int . Trong trường hợp này, (2.16) qui về: Trường hợp 1: x* và x*
) . –e3 N(x*,
. Điều này tương đương với sự kiện rằng x* là giao của [b1, b3] và biên của
Như vậy, (i) thỏa mãn.
bd int . Tương tự trường hợp 1, với điều kiện Trường hợp 2: x* và x*
này, (ii) thỏa mãn.
bd bd . Trong trường hợp này, (2.16) qui về: Trường hợp 3: x* và x*
–e3 = se1 + te2 ,
trong đó s, t [0, 1]. Chú ý trong trường hợp này, x* là tương giao
của bd và bd . Vì có nhiều nhất hai điểm trong tương giao này, điều kiện
này là thỏa mãn
Mệnh đề 2.16
. Giả sử |A(x*)| = 1 và x* là nghiệm tối ưu của (2.13), chẳng hạn x*
Khi đó:
) và . – e2 – e3 N(x*;
61
b3
Ngược lại, nếu điều kiện này thỏa mãn, thì x* là một nghiệm của (2.13)
b2 b1
Hình 12. Bài toán Fermat – Torricelli suy rộng và nghiệm của nó.
Chứng minh
Điều kiện (2.15) có thể viết như sau:
1. – e2 – e3 N(x* ; ) và || e2 + e3||
1 nếu và chỉ nếu . Bổ đề được chứng minh Chú ý rằng || e2 + e3||
Việc xây dựng để tìm một nghiệm như sau: trước hết ta sẽ tìm tất cả các
nghiệm có thể trong mỗi tập với i = 1, 2, 3. Nếu một nghiệm tìm được, thì sẽ
không có nghiệm ở bên ngoài của tập đó do Bổ đề 2.1. Nếu không có nghiệm
nào tìm được, thì nghiệm tối ưu được tìm bằng cách giải bài toán Fermat –
62
có thể tìm được Torricelli sinh bởi bi với i = 1, 2, 3. Chẳng hạn, nghiệm trong
bởi các bước sau đây.
Bước 1: Nếu , thì mỗi một điểm trong tương giao này là một
nghiệm. Nếu không, ta chuyển sang bước tiếp theo.
tại Bước 2: Nối các tâm [b1, bj], j = 2, 3. Nếu chẳng hạn, [b1, b3] giao với bd
một điểm thuộc vào int , thì điểm đó là một nghiệm. Nếu không, ta chuyển
sang bước tiếp theo.
Bước 3: Tìm giao của biên của các hình cầu và , và . Chẳng hạn, giả
sử p và q là giao của bd và bd . Khi đó kiểm tra nếu điều kiện –e3 [0, 1]e1
+ [0, 1]e2 thỏa mãn tại một điểm. Nếu điều kiện này thỏa mãn, chẳng hạn, tại p,
thì p là một nghiệm (xem Hình 12). Nếu không, ta đi đến bước tiếp theo.
, Bước 4: Kiểm tra nếu [b2, b3] giao với . Nếu chẳng hạn, [b2, b3] giao với
thì tìm tất cả các điểm trong giao không thuộc vào và , và đó là các
nghiệm. Trong trường hợp này, [b2, b3] không cắt . Khi đó ta tìm u2 := [b1, b2]
bd bd , và u3 := [b1, b3] . Tiếp theo, tìm một điểm duy nhất q1 ở trong
= và đường cong u2u3 sao cho . Nếu q1 không thuộc vào
(trong trường hợp khác, ta có |I(q1)| 2, vì vậy nếu q1 là một nghiệm, thì nó đã
được tìm trước đây), và 120o, khi đó q1 là một nghiệm của bài toán.
Bài toán Fermat – Torricelli cho ba điểm là một trường hợp đặc biệt của
bài toán Fermat – Torricelli cho hình cầu Euclid (2.12).
Ví dụ 2.2 (Bài toán Fermat – Torricelli cho ba điểm)
Cho trước ba điểm trong mặt phẳng. Hãy tìm điểm thứ tư sao cho tổng khoảng
63
cách từ điểm này tới ba điểm cho trước là nhỏ nhất.
F D A P B C E
Bài toán của Fermat trên đã được E. Torricelli giải bằng phương pháp
hình học như sau:
1. Cho ABC. Dựng các tam giác đều: ABD, BCE, ACF bên ngoài
ABC .
2. Dựng các đường tròn ngoại tiếp các tam giác đều ABD, BCE, ACF.
Ba đường tròn này cắt nhau tại một điểm, ký kiệu là P. Điểm P chính là điểm có
tổng khoảng cách đến ba điểm A, B, C ngắn nhất.
Điểm này được gọi là điểm Torricelli của ABC đã cho.
Điểm Torricelli P nhìn ba cạnh của ABC dưới các góc bằng 120o.
Một phương pháp khác tìm điểm Torricelli như sau: vẽ ba đường nối mỗi
đỉnh của tam giác đều nằm ngoài ABC với ba đỉnh đối diện của ABC. Ba
đường đó cắt nhau tại một điểm, điểm này cũng là điểm Torricelli (phương pháp
giải của T. Simpson)
64
D F A P B C E
65
KẾT LUẬN
Luận văn đã trình bày một số kiến thức cơ bản về tập lồi, hàm lồi, dưới vi
phân hàm lồi và các kết quả về sự tồn tại và duy nhất nghiệm, điều kiện tối ưu và
cách giải cho bài toán Sylester và bài toán Fermat – Torricelli bằng công cụ dưới
vi phân hàm lồi của N. M. Nam, N. Hoang và N. T. An (2014). Nội dung chính
của luận văn gồm :
- Một số kiến thức cơ bản về tập lồi, nón lồi;
- Hàm lồi và các phép tính về hàm lồi;
- Dưới vi phân hàm lồi và các tính chất;
- Dưới vi phân của hàm max;
- Các kết quả về sự tồn tại và duy nhất nghiệm, điều kiện tối ưu và cách giải
cho bài toán Sylvester với các hình cầu Euclid bằng công cụ dưới vi phân
hàm lồi;
- Các kết quả về sự tồn tại và duy nhất nghiệm, điều kiện tối ưu và cách giải
cho bài toán Fermat – Torricelli với ba hình cầu Euclid bằng công cụ dưới
vi phân hàm lồi
Sử dụng phương pháp giải tích lồi để giải các bài toán sơ cấp đã và đang được
nhiều tác giả quan tâm nghiên cứu.
66
TÀI LIỆU THAM KHẢO
[1] Đỗ Văn Lưu và Phan Huy Khải (2000), Giải tích lồi, NXB Khoa học và Kỹ
thuật Hà Nội.
[2] Đỗ Văn Lưu (1999), Giải tích Lipschitz, NXB Khoa học và Kỹ thuật, Hà
Nội.
[3] N. M. Nam ; N. Hoang và N. T. An (2014), Problem Sylvester and Problem
Fermat – Torricelli, J. Optime. Theory Appl, Vol. 160, pp.483 – 509.
[4] J.-B. Hiriart-Urruty, C. Lemaréchal (1993), Convex Analysis and
Minimization Algorithms I. Fundamentals, Springer, Berlin.
[5] D. Gisch, J. M. Ribando (2004), Apollonius’ Problems : a study of
Solutions and their connections, Am. J. Undergrad. Res. 3, 15 – 26.
[6] B. Mordukhovich, N. M. Nam (2011), Applications of variational analysis to
a generalized Fermat – Torricelli problem, J. Optim. Theory Appl. 148, 431 –
454.
67
