Luận văn Bài toán Sylvester và bài toán Fermat – Torricelli cho các hình cầu Euclid

phân dưới của  ' ;f x d theo biến d. Chứng minh Do  ' ;0 0f x  theo định lí 1.12 ta có:      ' ; ' ;0 ,x f x f x d f x x d      d X   ' ;0dx f x  . Định lý 1.13 Giả sử f là hàm lồi chính thường trên X và x domf . Khi đó:       ,x f x f x f x x x        , Thang Long University Library 22 trong đó f*(x*) =  *sup , ( ) x X x x f x     . Chứng minh a) Giả sử  x f x . Khi đó,     ,f x f x x x x    x X           *, , , , sup , x x x f x x x f x x X x x f x x x f x                   = * *( )f x . (1.9) Mặt khác, theo bất đẳng thức Young – Fenchel [1], ta có: * * *, ( ) ( )x x f x f x    (1.10) Từ (1.9),(1.10) suy ra:     ,f x f x x x     (1.11) b) Giả sử (1.11) đúng. Từ bất đẳng thức Young - Fenchel [1] với 0, ,d X   ta có:     ,f x d x x d x x f x                 , , ' ; , , f x d f x x d x d f x d x d d X                      x f x  (định lý 1.12) Ví dụ 1.11 Cho hàm affine    , , ,f x x x x X R        . Khi đó:    ,f x x x X    . 23 Ví dụ 1.12 Cho hàm chỉ    .f x A trong đó A là tập lồi khác rỗng. Khi đó, với mỗi x A ,       , ,x x A x A x A x x x x X            , 0,x x x x A     . Điều đó có nghĩa là x là vecto pháp tuyến của A tại x . Như vậy, ( | )x A là nón pháp tuyến của A tại x :    x A N x A  Với  ,x A x A   . Ví dụ 1.13 Giả sử X là không gian Banach,  f x x . a) Với 0x  , ta có:    : 1, ,f x x X x x x x        Thật vậy, nếu x thỏa mãn 1, ,x x x x    thì   , , , . x z z x z x X x z x z x x f x                Ngược lại, nếu  x f x thì: 0 ,0 , 2 ,2 , x x x x x x x x x x x x x x                    *,x x x   (1.12) Với , 0z X   ta có: Thang Long University Library 24  , , 1 , z x x x z x x x z x z x x z z                    Cho   ta nhận được: , ,z x z z X    1x  Nhưng x không thể nhỏ hơn 1 vì nếu x nhỏ hơn 1 thì:  , 1, , 1x z z X z      Với 1 x z z x    . Do đó, , 1 , . x x x x x x       Điều này mâu thuẫn với (1.12). Vì vậy x =1. b) Với x=0, ta có:    *0 : ,f x X z x z       * : 1x X x     0,1B (hình cầu đơn vị đóng trong X  ) Trường hợp riêng:  ,X R f x x  , Với 0x  : f là hàm khả vi, và:    1f x x x  . Với x=0:    0 : , ,f R z z x R           : 1 1,1R      . 25 Đị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 x X . Khi đó,  f x  ,lồi, compact* yếu. Đồng thời,     ' , max , :f x d x d x f x     . Chứng minh a) Ta chứng minh  f x lồi? Lấy    1 2, , 0,1 , .x x f x x X     Khi đó,               1 2 , , 1 , 1 . x x x f x f x x x x f x f x                           1 2 1 2 1 , , 1 x x x x f x f x x X x x f x                     Suy ra  f x lồi. b) Chứng minh  f x ? Theo định lý 4.2 [1],  ' ;,f x liên tục trên X. Do đó,  f x  (mệnh đề 4.6 [1]) c) Chứng minh  f x compact * yếu? Do  ' ;,f x liên tục,  ' ;,f x là hàm đóng. Theo định lý 4.5 [1] ta có:     sup , : ' , ,x d x f x f x d d X         . Khi d chạy trên các tập hữu hạn A trên X, thì:  max ' , d A f x d      Vì vậy  f x bị chặn theo tôpô * yếu của X*. Thang Long University Library 26 Mặt khác,   d d X f x H    trong đó dH là nửa không gian đóng * yếu trong X*:     : , .dH x X x d f x d f x        Suy ra  f x là tập đóng *yếu trong X*. Vậy  f x là compac * yếu trong X*. Định lý 1.15 Giả sử 1,..., mf f là các hàm lồi chính thường trên X và 1 0,..., 0m   . Khi đó, x X  ta có:       1 1 1 1... ... .m m m mf f x f x f x           Hơn nữa, nếu tồn tại 1 m i i x domf   , tất cả các hàm 1,..., mf f liên tục ( có thể trừ ra một hàm), thì với mọi x X ta có:       1 1 1 1... ... .m m m mf f x f x f x           1.4. DƯỚI VI PHÂN HÀM MAX Cho họ hữu hạn   1 n i i f  các hàm Lipschitz địa phương tại x . Đinh nghĩa hàm:     : max :1 1,...,if x f x n  . Khi đó, f cũng lipschitz địa phương tại x (xem [2]). Đặt:       : : maxi j i j n I x i f x f x     Mệnh đề 1.10       :if x conv f x i I x    . (1.13) Nếu if chính quy tại x   i I x  thì (1.13) có dấu bằng và f chính quy tại x . Chứng minh Định nghĩa các hàm : ng R R và : nh X R như sau: 27           1 1,..., max : 1,..., , ,..., .n i n i g u u u i n h x f x f x   Khi đó: f g h áp dụng định lí 2.5 [2], ta có:        1 : , n i i i i i f x conv f x g h x               Theo ví dụ 1.6 [2] :        1,..., : 0, 1, 0, .n i i jg h x j I x          Vì vậy,       :if x conv f x i I x    . 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  h x (định lí 2.3(ii) [2]). Khi đó (1.13) có dấu bằng và f chính quy tại x . Thang Long University Library 28 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à số phần tử của I. Giả sử 𝔹 là hình cầu đơn vị đóng, và i := 𝔹(ai; ri) (ri  0) với i  I, j := 𝔹(bj; sj) (sj  0) với j  J, là hai tập họ các hình cầu đóng trong ℝ n đượ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 đó 29 ℳ (x) := max {M (x; i ) | i  I} và 𝒟 (x) := max{ D(x; j ) | j  J}. Tương tự, mô hình tối ưu toán học của bài toán Torricelli suy rộng là: min ℋ(x) := ℳ1(x) + 𝒟1(x), x  ℝn, (2.2) trong đó ℳ 1(x) := ( ; )i i I M x   và 𝒟 1(x) := ( ; )j j J D 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: x là một nghiệm của hàm lồi  nếu và chỉ nếu 0  ( )x . (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 { i (x) | i = 1, ... , k}, trong đó i : ℝ n  ℝ với i = 1, ... , k là hàm lồi, thì ta có: ( )x = conv{ ( )i x | i  I( x )}, (2.4) trong đó I( x ) := {i  {1, ... , k} | ( )i x = ( )x } là tập chỉ số tích cực tại x . 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  ℝn và a  b, [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à Thang Long University Library 30 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ử  = 𝔹 (c; r), trong đó c  ℝn và r  0. Với bất kỳ x  ℝn, ta có: D(x;  ) = { 0, 𝑛ế𝑢 ‖𝑥 − 𝑐‖ ≤ 𝑟, ‖𝑥 − 𝑐‖ − 𝑟, 𝑡ạ𝑖 𝑛ℎữ𝑛𝑔 đ𝑖ể𝑚 𝑐ò𝑛 𝑙ạ𝑖, và M(x;  ) = ||x – c|| + r. Hơn nữa, D( x ; ) = { 𝑁(�̅�; 𝛺) ∩ 𝔹, 𝑛ế𝑢 ‖ x − 𝑐‖ ≤ 𝑟; { x −𝑐 ‖ x −𝑐‖ } , 𝑡ạ𝑖 𝑛ℎữ𝑛𝑔 đ𝑖ể𝑚 𝑐ò𝑛 𝑙ạ𝑖, và M( x ; ) = { 𝔹, 𝑛ế𝑢 �̅� = 𝑐, { x −𝑐 ‖ x −𝑐‖ } , 𝑛ế𝑢 𝑥 ≠ 𝑐. Với bất kỳ x  ℝn, ta kí hiệu: K(x) := {i  I | M(x;  i) = 𝒢(x)} và L(x) := {j  J | D(x; j ) = 𝒢(x)}. 31 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  ℝn, ta có 1  |A(x)|  |I| + |J|. Đị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à jj J  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 𝒢(x) = max { ||x – ai|| + ri, ||x – bj|| - sj | i  I, j  J}. (2.5) Bởi vì M(x;  i) = ||x – ai|| + ri và D(x; j ) = max {||x – bj|| - sj, 0}  ||x – bj|| - sj, ta luôn có: 𝒢(x)  max { ||x – ai|| + ri , ||x – bj|| - sj | i  I, j  J}. Cố định i0  I. Nếu K(x)  , thì với một phần tử i  K(x) , ta có: 𝒢(x) = ||x – ai|| + ri  max{||x – ai|| + ri , ||x – bj|| - sj | i  I, j  J}. Trong trường hợp K(x) =  , ta có L(x)  . Cố định j  L(x). Khi đó 𝒢(x) = D(x; j ) > M(x; 0i )  0. Như vậy x j , và khi đó: 𝒢(x) = ||x – bj|| - sj  max{||x – ai|| + ri , ||x – bj|| - sj | i  I, j  J}. Ta đã chỉ ra được (2.5). Chọn một hằng số l sao cho l > max{ sj | j  J}. Từ (2.5) ta suy ra x 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: Thang Long University Library 32 Min �̃�(𝑥) , x  ℝn , (2.6) trong đó �̃�(𝑥) := max{( ||x – ai|| + ri + l)2 , (||x – bj|| + l – sj)2 | i  I, j  J} = (𝒢(x) + l)2 . Bởi vì fi(x) := (||x – ai|| + ri + l)2 và gj(x) := (||x – bj|| + l – sj)2 với i  I và j  J là 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à jj J  chứa nhiều nhất một điểm. Nếu jj J  chứa đúng một điểm x0, thì 𝒢(x0) = 0 và x0 là nghiệm duy nhất. Trong trường hợp jj J  =  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à jj J  chứa nhiều hơn một điểm. Rõ ràng, 𝒢(x) = 0 với bất kỳ x  jj J  . Như vậy, bất kỳ x  jj J  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: 𝒫(x; Q) := {q  Q | ||x – q || = M(x; Q)}, và ∏(x; Q) := {q  Q | ||x – q|| = D(x; Q)}. Nếu Q = 𝔹 (c; r), thì: 33 𝒫(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   với ri > 0 với mọi i  I. Một phần tử x là nghiệm tối ưu của (2.1) nếu và chỉ nếu một trong các điều kiện sau đây đúng: (i) 𝔹 ( x ; r), r = 𝒢( x ), trùng với k hình cầu trong các i với i  I, k  1, 𝔹 ( x ; r) chứa các hình cầu khác trong { i | i  I}, và nó cắt j với j  J. (ii) 𝒫( x ; i ) với i  K( x ) là các tập một điểm, và x j với j  L( x ). Hơn nữa, với pi := 𝒫( x ; i ), qj := ∏( x ; j ), i  K( x ), j  L( x ), ta có: x  conv{ pi , qj | i  K( x ),j  L( x )}. 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, x là nghiệm tối ưu của bài toán, nếu và chỉ nếu: 0  𝒢( x ) = conv { M( x ; i ),D( x ; j ) | i  K( x ), j  L( x )}. (2.7) Giả sử ℐ := { i  K( x ) | M( x ; i ) không là tập một điểm}. Nếu ℐ  , thì x = ai và 𝒢( x ) = r = M( x ; i ) = ri với mọi i  ℐ. Vì thế tất cả các hình cầu i Thang Long University Library 34 với i  ℐ trùng nhau. Hơn nữa, ri = M( x ; i )  M( x ; j ) = ||ai – aj|| + rj với i  ℐ và j  I \ ℐ, và ri = M ( x ; i )  D( x ; j )  ||ai – bj|| - sj với mọi i  ℐ và j  J. Như vậy, 𝔹 ( x ; r) chứa các hình cầu trong { i | i  I \ ℐ} và cắt j với j  J. Xét trường hợp ℐ =  . Khi đó  M( x ; i ) là tập một điểm với mọi i  K( x ). Điều này kéo theo 𝒫( x ; i ) là tập một điểm với một i như vậy. Với mọi j  L( x ), bởi vì D( x ; j )  M( x ; 0i ) > 0 với một chỉ số cố định i0  I, ta có x j . Khi đó (2.7) được viết tương đương như sau: 0  conv , | ( ), ( )ji x qx p i K x j L x r r          , trong đó r = 𝒢( x ) = || x - pi|| = || x - qj||. Như vậy, tồn tại i  0 với i  K( x ) và j  0 với j  L( x ) sao cho ( ) ii K x   + ( ) jj L x  = 1 và 0 = ( ) ( ) ji i j i K x j L x x qx p r r        . Một cách tương đương, x = ( ) ( ) i i j j i K x j L x p q       conv{ pi , qj | i  K( x ),j  L( x )}. 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 35 Giả sử rằng I  với ri > 0 với mọi i  I. Nếu x là nghiệm tối ưu của (2.1), thì tồn tại các tập chỉ số I1  I và J1  J với 1 < |I1| + |J1|  n + 1 sao cho x là nghiệm của bài toán Sylvester suy rộng với tập mục tiêu i , i  I1, và j , j  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 ý i = 𝔹(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: min 𝒢( x ) = max{M (x ; 1 ) , M (x ; 2 ) , M (x ; 3 )} , x  ℝ 2 (2.8) Mệnh đề 2.3 Với x  ℝ2 và r := 𝒢( x ), ta có |K( x )| = 1 và x là nghiệm của (2.8) nếu Thang Long University Library 36 và chỉ nếu 𝔹( x ; r) trùng với một trong các hình cầu 𝔹(ai ; ri) với i  I, và 𝔹( x ; r) 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( x )| = 1, chẳng hạn K( x ) = {1}. Bởi vì x là nghiệm duy nhất của (2.8), ta có: 0  M ( x ; 1 ). Hơn nữa, r = 𝒢( x ) = M ( x ; 1 ), và r > M ( x ; i ) với i = 2, 3. Bởi vì 0  M ( x ; 1 ), ta suy ra biểu diễn dưới vi phân của M ( . ; 1 ) theo mệnh đề 2.1 với x = a1. Vì vậy : r = M ( x ; 1 ) = M (a1 ; 1 ) = r1. Hơn nữa, r > M (a1 ; i ) = ||a1 – ai|| + ri với i = 2, 3. Điều này kéo theo 𝔹( x ; r) = 𝔹 (a1 ; r1) và chứa ngặt hai hình cầu khác. Chứng minh phần ngược lại trực tiếp. Thật vậy, giả sử rằng 𝔹( x ; r) trùng với 𝔹 (a1 ; r1) và chứa ngặt các hình cầu khác. Khi đó x = a1, 𝒢( x ) = r = r1 = M ( x ; 1 ), và 𝒢( x ) > ||a1 – ai|| + ri = M ( x ; i ) với i = 2, 3. Như vậy, K( x ) = {1}, và 0   𝒢( x ) = 𝔹. Do đó, x là nghiệm của (2.8). Chúng ta sẽ sử dụng kí hiệu sau đây : u1 := 𝒫 (a2 ; 3 ), v1 := 𝒫 (a3 ; 2 ), w1 := 1 1 2 u v , t1 := 𝒫 (w1 ; 1 ); u2 := 𝒫 (a3 ; 1 ), v2 := 𝒫 (a1 ; 3 ), w2 := 2 2 2 u v , t2 := 𝒫 (w2 ; 2 ); u3 := 𝒫 (a1 ; 2 ), v3 := 𝒫 (a2 ; 1 ), w3 := 3 3 2 u v , t3 := 𝒫 (w3 ; 3 ). Với a, b, c  ℝ2 , kí hiệu bac có nghĩa là góc tạo bởi vectơ 𝑎𝑏⃗⃗⃗⃗ và vectơ 𝑎𝑐⃗⃗⃗⃗ . 37 Mệnh đề 2.4 Với x  ℝ2 và r := 𝒢( x ), ta có |K( x )| = 2 và x là nghiệm của (2.8) nếu và chỉ nếu các điều kiện sau đây đúng: (i) 𝔹( x ; r) trùng với hai hình cầu trong số 𝔹(ai ; ri) với i  I và chứa ngặt các hình cầu còn lại. (ii) 𝔹( x ; r) trùng với một trong các hình cầu trong số 𝔹(ai ; ri) với i  I, 𝔹( x ; 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 i i iu t v > 90 o, x = wi , và r = 2 i iu v . Chứng minh Giả sử |K( x )| = 2, chẳng hạn, K( x ) = {1, 2}. Xét các trường hợp sau đây: Trường hợp 1: x = a1 = a2. Trong trường hợp này, r = M ( x ; 1 ) = M ( x ; 2 ) = r1 = r2 > M ( x ; 3 ), Vì vậy 𝔹( x ; r) = 1 = 2 , và 𝔹( x ; r) chứa ngặt 3 . Như vậy (i) đúng. Trường hợp 2: x = a1 và x  a2, hoặc x  a1 và x = a2 . Ta xét, chẳng hạn, trường hợp x = a1 và x  a2. Khi đó ta có: x = a1 , ||a1 – a2|| = r1 – r2 và ||a1 – a3|| < r1 – r3 . Như vậy, 𝔹( x ; r) = 𝔹 (a1 ; r1) , 𝔹( x ; r) chứa tiếp xúc 𝔹 (a2 ; r2), và 𝔹( x ; r) chứa ngặt 𝔹 (a3 ; r3). Trong trường hợp này, (ii) đúng. Trường hợp 3: x  a1 và x  a2 . Khi đó cả p1 := 𝒫 ( x ; 1 ) và p2 := 𝒫 ( x ; 2 ) là tập một điểm. Từ định lý 2.2 suy ra x = 1 2 2 p p . Hơn nữa, || x - a3|| + r3 < 1 2 || || 2 p p . Thang Long University Library 38 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ó x thuộc đoạn thẳng mở (a1 , a2) mà nối a1 với a2, và x = w3 . Ta cũng có p1 = u3, p2 = v3, và 3 3 3u t v lớn hơn 90 o. 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 ( x ; 1 ) = M ( x ; 2 ) > M ( x ; 3 ) . Vì vậy K( x ) = {1, 2}. Bởi vì 𝒫 ( x ; 2 ) = u3 , 𝒫 ( x ; 1 ) = v3, và x = 3 3 2 u v , theo Định lý 2.2, phần tử x là nghiệm của (2.8). Hình 1. Mô hình I với |K( x )| = 2 ti ui wi vi Mệnh đề 2.5 Với x  ℝ2 và r := 𝒢( x ), ta có |K( x )| = 3 và x là nghiệm của (2.8) nếu và chỉ nếu các điều kiện sau đây đúng: (i) 𝔹( x ; r) trùng với một trong các hình cầu i với i  I và chứa tiếp xúc với hai hình cầu còn lại (ii) 𝔹( x ; r) trùng với hai hình cầu trong số i với i  I và chứa tiếp xúc với 39 hình cầu còn lại. (iii) 𝔹( x ; r) trùng với cả ba hình cầu. (iv) 𝒫 ( x ; i ) là các tập một điểm với i  I, x  conv {p1 , p2 , p3}, trong đó pi := 𝒫 ( x ; i ) , và: R = || x - p1|| = || x - p2|| = || x - p3|| . Chứng minh Ta hãy chứng minh suy luận trên. Ta có: 0   𝒢( x ) = conv{M ( x ; 1 ) ,  M ( x ; 2 ) ,  M ( x ; 3 )}, và r = M ( x ; 1 ) = M ( x ; 2 ) = M ( x ; 3 ). Xét các trường hợp sau đây. Trường hợp 1: x trùng với ít nhất một trong các tâm ai với i  I. Nếu đúng một tập trong số 𝒫 ( x ; i ) với i  I không là tập một điểm, chẳng hạn 𝒫 ( x ; 1 ), thì x = a1 và r = r1. Hơn nữa M(a1 ; i ) = r = ||a1 – ai|| + ri , với i = 2, 3. Trong trường hợp này, 1 chứa tiếp xúc hai hình cầu còn lại. Nếu đúng hai tập trong số 𝒫 ( x ; i ) với i  I không là các tập một điểm, thì (ii) đúng. Nếu tất cả 𝒫 ( x ; i ) với i  I không là các tập một điểm, thì (iii) đúng. Trường hợp 2: x không trùng với bất kỳ tâm nào ai với i  I. Trong trường hợp này, ta có || x - pi|| = r với i  I, và theo Định lý 2.2, x  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 Thang Long University Library 40 2 3 1   , thì x = 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( x )| = 3 Bước 2: Nếu một trong ba góc i i iu t v , i  I , lớn hơn 90 o , thì wi là nghiệm tối ưu và r = 2 i iu v 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 i 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à i = 𝔹 (ai ; ri) với i = 1, 2 và 1 = 𝔹 (b1 ; s1). Tìm hình cầu nhỏ nhất chứa 1 2,  và cắt 1 . Trong trường hợp này, I = {1, 2}, J = {1}, và (2.1) qui về bài toán: min 𝒢( x ) = max{M(x ; 1 ), M(x ; 2 ), D(x ; 1 )}, x  ℝ 2 . (2.9) Với bất kỳ u  ℝ2, ta có |K(u)|  {0, 1, 2}, |L(u)| {0, 1}, và 1  |K(u)| + |L(u)|  3. 41 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 x  ℝ2 và r := 𝒢( x ) , ta có x là nghiệm của (2.9) và |K(u)| + |L(u)| = 1 nếu và chỉ nếu 𝔹( x ; r) trùng với một trong các hình cầu i với i = 1, 2, chứa ngặt các hình cầu khác, và cắt ngặt 1 . Chứng minh Giả sử |K(u)| + |L(u)| = 1. Khi đó |K( x )| = 1 và |L( x )| = 0, hoặc |K( x )| = 0 và |L( x )| = 1. Ta xét trường hợp đầu tiên |K( x )| = 0 và |L( x )| = 1. Trong trường hợp này, ta có 𝒢( x ) = D( x ; 1 ) > 0 và 0   𝒢( x ) =  D( x ; 1 ). Khi đó x  1 , và vì vậy, D ( x ; 1 ) = 1 1 x b x b   . Ta đi đến một mâu thuẫn bởi vì x  b1 . Xét trường hợp khi |K( x )| = 1 và |L( x )| = 0. Giả sử K( x ) = {1}. Khi đó: 0   𝒢( x ) =  M( x ; 1 ). Điều này kéo theo x = a1, 𝒢( x ) = M( x ; 1 ) = r1 > M( x ; r2) = ||a1 – a2|| + r2 , và: 𝒢( x ) = M( x ; 1 ) = r1 > D( x ; 1 )  ||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 ; 1 ), v1 := Π(a1 ; 1 ), w1 := 1 1 2 u v t1 := 𝒫(w1 ; 2 ); u2 := 𝒫(b2 ; 2 ), v2 := Π(a2 ; 1 ), w2 := 2 2 2 u v t2 := 𝒫(w2 ; 1 ). Mệnh đề 2.7 Thang Long University Library 42 Với x  ℝ2 và r := 𝒢( x ) , ta có x là nghiệm của (2.9) và |K( x )| = |L( x )| = 1 nếu và chỉ nếu một trong các điều kiện sau đây là đúng: (i) 𝔹( x ; r) trùng với một trong các hình cầu i với i = 1, 2, chứa ngặt các hình cầu khác, và giao tiếp xúc với 1 . (ii) Một trong các góc i i iu t v với i = 1, 2 lớn hơn 90 o, x = wi , và r = . 2 i iu v Chứng minh Giả sử x là một nghiệm của bài toán và |K( x )| = |L( x )| = 1. Khi đó |K( x )| = {1} hoặc |K( x )| = {2} và |L( x )| = {1}. Xét trường hợp khi |K( x )| = {1} và |L( x )| = {1}. Khi đó: r := 𝒢( x ) = M( x ; 1 ) = D( x ; 1 ) > M( x ; 2 ) và 0   𝒢( x ) = conv{M( x ; 1 ) , D( x ; 1 )}. Bởi vì D( x ; 1 ) > 0 , ta có x  1 . Để ý rằng, nếu x = a1, thì r1 > M( x ; 2 ) = ||a1 – a2|| + r2, và r1 = M( x ; 1 ) = D( x ; 1 ) = ||a1 – b1|| - s1. Trong trường hợp này, (i) đúng. Xét trương hợp khi x  a1. Theo Định lý 2.2, x = 1 1 2 y z khi y1 = 𝒫( x ; 1 ) và z1 = Π( x ; 1 ). Trong trương hợp này, y1 = u1 , z1 = v1, và x = w1. Bởi vì r = 1 1 2 u v > M(w1 ; 2 ) = ||w1 – t1||, ta có 1 1 1u t v > 90 o. Chứng minh điều ngược lại dễ dàng. Kí hiệu: x1 := 𝒫(a2 ; 1 ), x2 := 𝒫(a1 ; 2 ), y := 1 2 2 x x , z := Π( y ; 1 ). 43 Mệnh đề 2.8 Với x  ℝ2 và r := 𝒢( x ) , ta có x là nghiệm của (2.9) và |K( x )| = 2, |L( x )| = 0 nếu và chỉ nếu một trong các điều kiện sau đây là đúng: (i) 𝔹( x ; r) trùng với cả hai i với i = 1, 2 , và cắt chặt 1. (ii) 𝔹( x ; r) trùng với một trong các hình cầu i với i = 1, 2, chứa tiếp xúc với hình cầu khác và cắt ngặt 1. (iii) Góc 1 2x zx lớn hơn 90 o, x = y, và r = 1 2 . 2 x x Chứng minh Giả sử x là một nghiệm của (2.9), K( x ) = {1, 2}, và L( x ) =  . Khi đó: r = 𝒢( x ) = M( x ; 1 ) = M( x ; 2 ) > D( x ; 1 ), và 0   𝒢( x ) = conv{M( x ; 1 ) , M( x ; 2 ) }. Xét các trường hợp sau: Trường hợp 1: x = a1 và x = a2. Trong trường hợp này, r1 = r2 = r, và vì vậy, 𝔹( x ; r) = 1 = 2 . Mặt khác, bởi vì D( x ; 1 ) < r , ta có 𝔹( x ; r) cắt ngặt 1 . Trường hợp 2: x = a1 và x  a2. Trong trường hợp này, r1 = r = r2 + || x - a2||. Như vậy, 𝔹( x ; r) = 1 . Bởi vì || x - a2|| = r1 – r2 và D( x ; 1 ) < r, ta có 𝔹( x ; r) chứa tiếp xúc 2 và cắt ngặt 1 . Trường hợp 3: x  a1 và x  a2. Sử dụng Định lý 2.2, ta có: x = tx1 + (1 – t)x2 , t  (0, 1). Bởi vì bài toán có một nghiệm duy nhất, t = 1 / 2, tức là x = 1 2 2 x x = y và r = Thang Long University Library 44 1 2 2 x x . Bởi vì D( x ; 1 ) < r, hoặc ||y – z|| < r, góc 1 2x zx lớn hơn 90 o. Dễ dàng chứng minh được điều kiện đủ. Mệnh đề 2.9 Với x  ℝ2 và r := 𝒢( x ) , ta có x là nghiệm của (2.9) và |K( x )| = 2, |L( x )| = 1 nếu và chỉ nếu một trong các điều kiện sau đây đúng: (i) 𝔹( x ; r) trùng với cả hai hình cầu i với i = 1, 2, và giao tiếp xúc với 1. (ii) 𝔹( x ; r) trùng với một trong các hình cầu i với i = 1, 2, chứa tiếp xúc với hình cầu khác và giao tiếp xúc với 1. (iii) 𝒫( x ; i )với i = 1, 2 là các tập một điểm và x  1 , || x - p1|| = || x - p2|| = || x - q1|| , trong đó pi = 𝒫( x ; i ) với i = 1, 2 và q1 := Π( x ; 1 ), và x  conv {p1, p2, q1}. Chứng minh Giả sử x là một nghiệm của bài toán và K( x ) = {1, 2}, và L( x ) = {1}. Khi đó: r = 𝒢( x ) = M( x ; 1 ) = M( x ; 2 ) > D( x ; 1 ) và 0   𝒢( x ) = conv{M( x ; 1 ) ,  M( x ; 2 ) , D( x ; 1 )}. Ta xét các trường hợp sau đây: Trường hợp 1: x = a1 và x = a2. Trong trường hợp này, r1 = r2 = r, và vì vậy 𝔹( x ; r) = 1 = 2 . Mặt khác, bởi vì D( x ; 1 ) = r, ta có 𝔹( x ; r) giao tiếp xúc với 1 Trường hợp 2: x = a1 và x  a2. Trong trường hợp này, r1 = r = r2 + || x - a2||. Như vậy, 𝔹( x ; r) = 1 . Bởi vì || x - a2|| = r1 – r2 và D( x ; 1 ) = r, ta có 𝔹( x ; r) 45 chứa tiếp xúc 2 và giao tiếp xúc 1 . Trường hợp 3: x  a1 và x  a2. Trong trường hợp này, 𝒫( x ; i ) với i = 1, 2 là các tập một điểm. Hình 3. Mô hình II với |K( x )| = 1, |L( x )| = 1 t1 u . . .v1 w1 Hình 4. Mô hình II với |K( x )| = 2, |L( x )| = 0 z x1 x2 Thang Long University Library 46 Hình 5. Mô hình II với |K( x )| = 2, |L( x )| = 1 Sử dụng định lý 2.2, ta có x = t1p1 + t2p2 + t3p1, ti  [0, 1], trong đó t1 + t2 + t3 = 1. Hơn nữa, || x - p1|| = || x - p2|| = || x - 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ố 1 và 2 mà chứa các hình cầu khác và cắt 1 , 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 i i iu t v với i = 1, 2 lớn hơn 90 o , x = wi và r = 2 i iu v . Nếu không, ta đi đến bước tiếp theo. Bước 3: Góc 1 2x zx lớn hơn 90 o, x = y và r = 1 2 2 x x . Nếu không ta đi đến bước 47 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 1 , 2 và giao tiếp xúc 1 . 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 1 = 𝔹 (a1 ; r1), 1 = 𝔹 (b1 ; s1), và 2 = 𝔹 (b2 ; s2), tìm hình cầu nhỏ nhất mà chứa 1 và cắt 1 và 2 . Trong trường hợp này, I = {1}, J = {1, 2}, và (2.1) qui về bài toán: min 𝒢( x ) = max{M(x ; 1 ), D(x ; 1 ), D(x ; 2 )}, x  ℝ 2. (2.10) với {i, j} = {1, 2}, ta sử dụng kí hiệu sau đây: ci := 𝒫(bi ; 1 ), di := Π(a1 ; i ), ei := 2 i ic d , fi := Π(ei ; j ); yj := Π(bi ; j ), z := 1 2 2 y y , t := 𝒫(z ; 1 ) . Tương tự ta có kết quả sau: Mệnh đề 2.10 Với x  ℝ2 và r := 𝒢( x ). Các điều kiện sau đây đúng: (i) Phần tử x là nghiệm của (2.10) và |K( x )| + |L( x )| = nếu và chỉ nếu 𝔹( x ; r) trùng với i và giao ngặt với cả 1 và 2 . (ii) Phần tử x là nghiệm của (2.10) và |K( x )| = |L( x )| = 1 nếu và chỉ nếu một các điều kiện sau đây đúng: (a) 𝔹( x ; r) trùng với 1 , giao tiếp xúc với một trong các hình cầu i với 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 i i ic f d > 90 o , x = ei, và r = 2 i ic d . (iii) Phần tử x là nghiệm của (2.10) và |K( x )| = 0, |L( x )| = 2 nếu và chỉ nếu Thang Long University Library 48 1 2y ty > 90 o , x = z, và r = 1 2 2 y y . (iv) Phần tử x là nghiệm của (2.10) và |K( x )| = 1 và |L( x )| = 2 nếu và chỉ nếu một trong các điều kiện sau đây đúng. (a) 𝔹( x ; r) trùng với 1 , giao tiếp xúc với cả hai i với i = 1, 2. (b) 𝒫( x ; 1 ) là tập một điểm và x  i với i = 1, 2,|| x - p1|| = || x - q2||, trong đó p1 = 𝒫( x ; 1 ) và qi := Π( x ; i ) với i = 1, 2, và x  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( x )| = 1, |L( x )| =1 fi ci ei di 49 Hình 7. Mô hình III với |K( x )| = 0, |L( x )| = 2 t y1 z y2 Hình 8. Mô hình III với |K( x )| = 1, |L( x )| = 2 Bước 1: Nếu 1 1   và 1 2   , thì x = 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 i i ic f d với i = 1, 2, lớn hơn 90 o, thì x = ei, r = 2 i ic d . Nếu không , đi đến bước tiếp theo. Bước 3: nếu góc 1 2y ty > 90 o , thì x = z và r = 1 2 2 y y . Nếu không, đi đến bước Thang Long University Library 50 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 1 và giao tiếp xúc 1 2,  . 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 1 = 𝔹(bi ; si) với i = 1, 2, 3, tìm hình cầu nhỏ nhất mà cắt i 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: min 𝒢( x ) = max{D(x ; 1 ), D(x ; 2 ), D(x ; 3 )} x  ℝ 2. (2.11) Trong trường hợp này 3 1 ii    , đ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( x )| = |L( x )| 2. Ta sẽ sử dụng kí hiệu sau đây: u1 := [b2, b3] bd( ), v1 := [b2, b3] bd( ), u2 := [b1, b3] bd( ), v2 := [b1, b3] bd( ), u3 := [b1, b2] bd( ), v3 := [b1, b2] bd( ), 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.  2 3 3 1 1 2 1 1 2 u v 2 2 2 u v 3 3 2 u v 1 2 3 1 1 1; 2 u v m        2 2 2 ; 2 u v m        3 3 3; 2 u v m         j j ju x v 51 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 Hình 10. Mô hình IV với |L( )| = 3 x x Thang Long University Library 52 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: min ℋ(x) = + , 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: min ℋ(x) = + , 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à đủ: min ℋ(x) = , 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 rằng tập hợp {x ℝ2 | ℋ(x) } compact. Vì vậy, (2.13) luôn có một nghiệm 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. ( ; )i i I M x   ( ; )j j J D x    x i i I x a   ( ; )j j J D x    3 1 ( ; )i i D x      2infx R    53 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 > 0 sao cho 𝔹(x*; ) = với i = 1, 2, 3. Khi đó 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 Giả sử A(x*) = , và tồn tại y* S với x* y*. Bởi vì A(x*) = , ta có x* với i = 1, 2, 3. Khi đó x* là nghiệm của bài toán Fermat – Torricelli 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*] S.    i  i   i    3 * 1 i i x b   3 1 i i s   2infx R  3 1 i i x b   3 1 i i s   3 1 i i x b           i  Thang Long University Library 54 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 ℝ2 với a b, xét tập hợp: 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ó    i         2 x y a   2 x y b    2 x y  2 x y a   2 x y b   1 2  1 2  2 x y a   2 x y b    2 x y    1 1 x k 1 k y k  1 1 x m 1 m y m    2 x y  55 [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à một tập con của ℝn. Ta nói rằng là lồi chặt nếu với mọi x, 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 Giả sử S là tập nghệm của (2.13). Giả sử rằng tồn tại x* S sao cho 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ử: 2 x y 2 x y a   2 x y b    2 x y  2 x y a   2 x y b    2 x y a   2 x y b    2 x y         E      1  2  3  Thang Long University Library 56 := ||x* - b2|| + ||x* - b3|| = 2 inf x R ℋ(x) + s2 + s3. Khi đó > ||b2 – b3||. Kí hiệu: E := { x ℝ2 | ||x – b2|| + ||x – b3|| = } Rõ ràng, x* E . Giả sử ngược lại rằng S không là tập một điểm. Khi đó 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* [x* , y*] để cho nó là đủ gần và phân biệt với x* sao cho [x* , z*] = và [x* , z*] = . Trước hết ta chỉ ra z*  . Thật vậy, giả sử z*  1 . Khi đó D(z* ; ) = 0, và vì thế: ℋ(z*) = 2 inf x R ℋ(x) = D(z* ; ) + D(z* ; ) = ||z* - b2|| - s2 + ||z* - b3|| - s3 . Điều đó kéo theo z* E. Bởi vì S và là lồi, S . Hơn nữa, và . Ta lại có E. Điều này không thể xảy ra theo Bổ đề 2.2. Ta đã chỉ ra rằng z* S và A(z*) = . Điều đó mâu thuẫn với Bổ đề 2.1. Do đó, S phải là tập một điểm. Bổ đề 2.4 Giả sử S là tập nghiệm của (2.13). Giả sử x* S và A(x*) = {i, j} {1, 2, 3}. Khi đó x* bd( ). Chứng minh Giả sử A(x*) = {1, 2}. Khi đó x* và x* . Giả sử ngược lại x* inf( ). Khi đó tồn tại > 0 với 𝔹(x* ; ) . Giả sử p := Π(x* ; ) và := ||x* - p|| > 0. Giả sử q [x* , p] 𝔹(x* ; ) thỏa mãn ||q – p|| < ||x* - p|| = D(x* ; ). Khi đó:      1     2  3  1 1 2 3  1 * * 2 x z  1 * * 2 x z  2 * * 2 x z  3 * * 2 x z       i j   1 2   3  1 2     1 2  3    3 57 ℋ(q) = = D(q; ) ||q – p|| < ||x* - p|| = D(x* ; ) = = ℋ(x*). Đây là mâu thuẫn với sự kiện x* S. Định lý 2.3 Giả sử = . Khi đó (2.13) có nhiều hơn một nghiệm nếu và chỉ nếu tòn tại một tập [bi , bj] , với các chỉ số phân biệt i, j, k {1, 2, 3}, mà chứa một điểm u thuộc phần trong của và |A(u)| = 1. Chứng minh Giả sử [b1 , b2] chứa một điểm u mà thuộc vào phần trong của và |A(u)| = 1. Khi đó u và u . Ta có thể chọn v u, v [b1 , b2], v , 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, ℋ(u) = D(u ; ) + D(u ; ) + D(u ; ) = ||b1 – b2|| - s1 – s2. Chọn > 0 sao cho 𝔹(u ; ) = và 𝔹(u ; ) = và 𝔹(u ; ) . Với mọi x 𝔹(u ; ) , ta có: ℋ(x) = D(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 3 1 ( ; )i i D q   3  3 3 * 1 ( ; )i i D x    3 1 ii   k  k 3  1  2    1  2  3 1 2 3   1   2    3   2 3   Thang Long University Library 58 tử riêng biệt của S. Khi đó [x* , y*] S theo mệnh đề 2.11. Nếu tồn tại một 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 nghiệm bởi vì [b1, b2] cắt phần trong của , và |A(u)| = 1 với mọi u (B, C). 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. Giả sử Vk := [bi , bj] int với các chỉ số phân biệt i, j, k {1, 2, 3}.  i  1 1 1  1 2 3,   1 3  k  b2 59 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}: [Vk ] [|A(u)| = 2 với mọi u 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 [bi , bj] 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, 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 . Khi đó [b1, b2] chứa vô hạn điểm, điều đó là một mâu thuẫn. 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* 3 1 ii        3 1 ii   k  3 3 i  *\ ( ) i i J A x e    * * ( ) [ ( ; ) ]i i A x N x B   * * i i x b x b   Thang Long University Library 60 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 Cố định x* . Khi đó ℋ(x*) = 0, và vì vậy x* S bởi vì 2 inf x R ℋ(x) 0 . Ngược lại, với bất kỳ x S, ta có ℋ(x) ℋ(x*) = 0. Như vậy, D(x ; ) = 0, 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 x* S. 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: (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* int . (iii) Điểm x* thuộc vào giao của biên và biên của , và –e3 = se1 + te2 ,   *( ; )i i J D x    * * \ ( ) ( ; )i i J A x D x    * * ( ) ( ; )i i A x D x    3 1 ii    3 1 i i   3 1 ii        i  i  3 1 ii    3 1 ji     1 2  1  2 2  1 1 2 61 trong đó s, t [0, 1] và ei = với i = 1, 2, 3. 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 Giả sử |A(x*)| = 2 và x* . Theo mệnh đề 2.13, –e3 [N(x*, ) 𝔹] + [N(x*, ) 𝔹]. (2.16) Bởi vì e3 0, ta có x* bd hoặc x* bd . Trường hợp 1: x* bd và x* int . Trong trường hợp này, (2.16) qui về: –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. Trường hợp 2: x* bd và x* int . Tương tự trường hợp 1, với điều kiện này, (ii) thỏa mãn. Trường hợp 3: x* bd và x* bd . Trong trường hợp này, (2.16) qui về: –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 đó: – e2 – e3 N(x*; ) và .  * * i i x b x b    1 2   1 2   1  2  1  2  1 1  2  1  1  2  1 2  1  1 2 3,e e  1 2  Thang Long University Library 62 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: – e2 – e3 N(x* ; ) và || e2 + e3|| 1. Chú ý rằng || e2 + e3|| 1 nếu và chỉ nếu . Bổ đề được chứng minh 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 –  1   2 3,e e  1 2  i b3 63 Torricelli sinh bởi bi với i = 1, 2, 3. Chẳng hạn, nghiệm trong có thể tìm được 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. 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 tại 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 2 và 3 , 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 , và u3 := [b1, b3] bd . Tiếp theo, tìm một điểm duy nhất q1 ở trong đường cong u2u3 sao cho = . Nếu q1 không thuộc vào và (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 1 3 1 ii    1 2 1 2 1 3 1 2  1 1 1 1 1 2 1 1b q b 3 1 1b q b 2 3  2 1 3b q b  Thang Long University Library 64 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)             65 D F A P B C E Thang Long University Library 66 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. 67 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. Thang Long University Library