Luận văn Phần chính của Luận văn, trong chương này tác giả trình bày nội dung hai định lý tách và hệ quả (Bổ đề Farkas)

    . 1.2 Hàm lồi Trong chương trình Toán phổ thông, chúng ta đã làm quen với khái niệm hàm lồi một cách cơ bản. Mục này, chúng tôi trình bày khái niệm tổng quát về hàm lồi và một số tính chất của nó. Định nghĩa 1.14. Cho tập nC R và :f C R . Ta sẽ ký hiệu   dom : |f x C f x    ,     epi : , | f x C R f x     . Các tập dom f , epi f lần lượt được gọi là miền hữu dụng và trên đồ thị của hàm f . Bằng cách cho  f x   nếu x C , ta có thể coi f được xác định trên toàn không gian và   ndom : R |f x f x    , 16     epi : , | nf x R R f x     . Quy ước nếu 0  thì   0f x  với mọi x . Định nghĩa 1.15 Cho nC R   lồi và :f C R . Ta nói f là hàm lồi trên C nếu epif là một tập lồi trong 1nR  . Hàm f được gọi là hàm lõm trên C nếu f là hàm lồi trên C . Sau đây chủ yếu ta xét hàm  : nf R R   . Dễ thấy định nghĩa trên tương đương với:           1 1 , , 0;1f x y f x f y x y C             Định nghĩa 1.16 Hàm  : nf R R   được gọi là lồi chặt trên C nếu           1 1 , , 0;1f x y f x f y x y C             Hàm  : nf R R   được gọi là lồi mạnh trên C với hệ số 0  nếu             211 1 - 1 - , , 0;1 2 f x y f x f y x y x y C                Nhận xét 1.4 Dễ dàng kiểm tra rằng hàm f lồi mạnh trên C với hệ số 0  khi và chỉ khi hàm     2. : . . 2 h f   lồi trên C . Sau đây ta sẽ đề cập đến một bất đẳng thức quen thuộc trong chương trình phổ thông. Đây là bất đẳng thức tương đối tổng quát trong các bất đẳng thức về hàm 17 lồi. Các bất đẳng thức giữa trung bình cộng và trung bình nhân, Holder là những trường hợp riêng của bất đẳng thức này. Bất đẳng thức Jensen Nếu f là hàm lồi và nhận giá trị hữu hạn trên tập lồi C thì * 1 2, , ,..., mm N x x x C    và 0j  thỏa mãn 1 1 m j j    , ta có:   1 1 m m j j j j j j f x f x            . Mệnh đề 1.8 (xem [2], mệnh đề 8.1) Một hàm :f C R là lồi trên C khi và chỉ khi           , , , , 0;1 1 1 x y C f x f y f x y                     Chứng minh Điều kiện cần: Giả sử f lồi, chọn , , ,x y   như đã nêu trong mệnh đề. Chọn   ' ,f x  và   ' ,f y  . Vậy    , ' , , ' epi x y f   . Do epi f lồi nên     1 , 1 ' ' epi x y f         .       1 1 ' ' 1f x y                . Điều kiện đủ: Chọn    , , , epi x y f   và  0,1 .Với mọi 0  , ta có    ,f x f y       . Do đó nên         1 ' ' 1 1f                          .     1 , , epi x y f       . Vậy hàm f lồi. 18 Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh dựa vào khái niệm hệ số lồi. Định nghĩa 1.17 Hàm  : nf R R   (không nhất thiết lồi), nC R là một tập lồi khác rỗng và  là một số thực. Ta nói  là hệ số lồi của f trên C , nếu với mọi  0,1 , mọi ,x y thuộc C , ta có           211 1 1 2 f x y f x f y x y               . Hiển nhiên, nếu 0  thì f lồi trên C . Nếu f có hệ số lồi trên C là 0  , thì f lồi mạnh trên C vớih hệ số lồi  . Định nghĩa 1.18 Một hàm f được gọi là chính thường nếu dom f   và  f x   với mọi x . Hàm f được gọi là đóng nếu epi f là một tập đóng trong 1nR  . Nhận xét 1.5 a) Từ định nghĩa của epi f , ta thấy rằng một hàm lồi hoàn toàn được xác định nếu biết epi f . b) Nếu f là một hàm lồi trên một tập lồi C thì có thể thác triển f lên toàn không gian bằng cách đặt     , : .e f x x C f x x C       Hiển nhiên    ef x f x với mọi x C và  ef x lồi trên nR . Hơn nữa  ef x là chính thường khi và chỉ khi f chính thường. Tương tự,  ef x đóng khi và chỉ khi f đóng. nếu nếu 19 c) Nếu f là một hàm lồi trên nR thì dom f là một tập lồi, vì dom f chính là hình chiếu trên nR của epi f , tức là:   dom | : , epi f x R x f     . Ví dụ 1.4 Một số hàm lồi 1. Hàm a-phin:   ,f x a x   , trong đó ,na R R  . Dễ dàng kiểm tra được rằng f là hàm vừa lồi vừa lõm trên toàn không gian. Khi 0  thì hàm này được gọi là hàm tuyến tính. 2. Hàm chỉ: Cho C   là một tập lồi. Đặt   0 , : .C x C x x C       Ta nói C là hàm chỉ của C . Do C lồi nên C là một hàm lồi. 3. Hàm mặt cầu. Cho  : | x 1nS x R   là một mặt cầu và :h S R là một hàm bất kỳ. Định nghĩa hàm f như sau:     0 1, : 1, + 1. x f x h x x x        Hàm này được gọi là hàm mặt cầu. Dễ thấy rằng f là một hàm lồi trên nR . 4. Hàm tựa. Hàm dưới đây được gọi là hàm tựa của C ( ) : sup ,C x C s y y x   . 5. Hàm khoảng cách. nếu nếu nếu nếu nếu 20 Cho C lồi đóng, hàm khoảng cách đến tập C được định nghĩa bởi   : min .C y Cd x x y  6. Hàm chuẩn. Giả sử  1,..., nx x x .   1: : max iif x x x  Hoặc     1 2 2 2 1: : ... nf x x x x    . 21 Chương 2 ĐỊNH LÝ TÁCH CÁC TẬP LỒI Trong giải tích lồi và nhiều lĩnh vực khác như giải tích hàm, giải tích không trơn và giải tích phi tuyến, các định lý tách hai tập lồi có một vai trò trung tâm. Về bản chất, định lý tách trả lời câu hỏi rằng một phần tử có thuộc một tập lồi không, và nếu không thuộc thì nó sẽ có tính chất gì? Ví dụ tập lồi là nghiệm của hệ phương trình đại số, hay vi tích phân, tập các điểm bất động của một ánh xạ, hay là tập nghiệm của một bài toán tối ưu Nếu điểm thuộc tập lồi đó thì vấn đề được giải quyết, trái lại, nếu không thì sẽ xảy ra điều gì? Điều này giải thích vì sao các định lý tách thuộc loại các định lý chọn và là công cụ rất mạnh, thường được dùng để chứng minh sự tồn tại của một đối tượng trong nhiều vấn đề thuộc những lĩnh vực khác nhau. Một mệnh đề thường được dùng làm nền tảng lý thuyết tối ưu hiện đại là định lý tách các tập lồi, mà một dạng tương đương của nó trong giải tích hàm là định lý Hahn – Banach rất quen thuộc trong giải tích hàm. 2.1. Định lý tách 1 Định nghĩa 2.1 Cho , nC C R   (không nhất thiết lồi) và y là véc tơ bất kỳ, đặt   : inf .C x Cd y x y  Ta nói  Cd y là khoảng cách từ y đến C . Nếu tồn tại C  sao cho  Cd y y  , thì ta nói  là hình chiếu (vuông góc) của y trên C . Ký hiệu  Cp y  . Mệnh đề 2.1 (xem [2], mệnh đề 5.1) Cho C là một tập lồi đóng khác rỗng trong nR . Khi đó: (i) Với mọi , ny R C  hai tính chất sau là tương đương: 22 a)  Cp y  , b) ( )Cy N   . (ii) Với mọi ny R , hình chiếu ( )Cp y của y trên C luôn tồn tại và duy nhất. (iii) Nếu y C , thì    , 0C Cp y y x p y   là siêu pẳng tựa của C tại ( )Cp y và tách hẳn y khỏi C , tức là    , 0,C Cp y y x p y x C     , và    , 0C Cp y y y p y   . Chứng minh (i) Giả sử có a). Lấy x C và  0,1 . Đặt  : 1x x      . Do ,x C  và C lồi, nên x C  . Hơn nữa do  là hình chiếu của y , nên y y x    . Hay     22y x y        . Khai triển vế phải, ước lược và chia hai vế cho 0  , ta có 2 2 , 0x x y        . Điều này đúng với mọi x C và  0,1 . Do đó khi cho  tiến đến 0 ta được , 0 y x x C      . Vậy  Cy N   . Bây giờ giả sử có b). Với mọi x C , có 23            2 0 = . T T T y x y x y y y y x y                   Từ đây và b), dùng bất đẳng thức Cauchy – Scharz ta có:    2 Ty y y x y y x         . Suy ra y y x x C     , và do đó ( )p y  . ii) Do ( ) infC x Cd y x y  , nên theo định nghĩa của cận dưới đúng (infimum), tồn tại một dãy kx C sao cho lim ( )k Ck x y d y    . Vậy dãy  kx bị chặn, do đó nó có một dãy con  kjx hội tụ đến một điểm  nào đó. Do C đóng nên C  . Vậy  lim limkj k Cj ky x y x y d y       . Chứng tỏ  là hình chiếu của y trên C . Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm  và 1 đều là hình chiếu của y trên C , thì    1 1, C Cy N y N       . Tức là 1, 0y     và 1 1, 0y     Cộng hai bất đẳng thức này ta suy ra 1 0   , và do đó 1  . iii) Do  Cy N   , nên 24 , 0 y x x C      . Vậy , ,y x y     là một siêu phẳng tựa của C tại  . Siêu phẳng này tách y khỏi C vì y  , nên 2, 0y y y        . Mệnh đề 2.2 (xem [2], mệnh đề 5.4) Cho C là một tập lồi khác rỗng và 0x riC . Khi đó tồn tại siêu phẳng tựa của C tại hình chiếu của 0x trên C . Chứng minh Gọi hình chiếu của 0x trên C là 0( )p x Trước hết xét trường hợp int C   . Vậy 0 intx C . Phân biệt trường hợp: a) 0x C . Do C lồi, đóng, nên theo (iii) của mệnh đề 2.1, siêu phẳng 0 0 0 0 0( ) , ( ) , ( )p x x x p x x p x   là siêu phẳng tựa của C tại 0( )p x tách hẳn C và 0x . b) 0x C . Khi đó do 0 intx C , nên 0 \nx R C . Vậy tồn tại dãy 0kx x với kx C với mọi k . Do C lồi, đóng, nên lại áp dụng (iii) của Mệnh đề 2.1, tồn tại siêu phẳng tựa của C tại ( )kp x . Tức là tồn tại 0k  , thỏa mãn: , , ( ) k k kx p x x C    . Bằng cách chuẩn hóa k , ta có thể coi 1k  , và do đó có thể giả sử 0k  . Do ánh xạ chiếu liên tục, nên từ bất đẳng thức trên, qua giới hạn và chú ý là 0 0( )p x x (Vì 0x C ), ta có: 0 0 0 0 0, , ( ) = , x p x x x C     . Vậy 0 0 0, = , x x x C    là siêu phẳng tựa của C tại 0x . 25 Định nghĩa 2.2 Cho hai tập C và D khác rỗng, ta nói siêu phẳng Ta x  tách C và D nếu , , T Ta x a y x C y D      . Ta nói siêu phẳng Ta x  tách chật C và D nếu , , T Ta x a y x C y D      . Ta nói siêu phẳng Ta x  tách mạnh C và D nếu y D sup inf , , T T x C a x a y x C y D        . Bổ đề 2.1 Cho nC R là một tập lồi khác rỗng. Giả sử 0x C . Khi đó tồn tại , 0nt R t  thỏa mãn 0, ,t x t x . Chứng minh Do 0x riC , nên sự tồn tại siêu phẳng tách trong bổ đề được suy ra từ mệnh đề 2.2. Định lý 2.1 (Định lý tách 1) (xem [2], định lý 6.1) Cho C và D là hai tập lồi khác rỗng trong nR sao cho C D  . Khi đó có một siêu phẳng tách C và D . Chứng minh Do C và D là lồi, nên C D cũng lồi. Hơn nữa,  0 C D  , vì C D  . Theo bổ đề 2.1 áp dụng với 0 0x  , tồn tại véc tơ , 0nt R t  sao cho , 0t z  với mọi z C D  . Vì z x y  , với , x C y D  , nên ta có , , , t x t y x C y D    . Lấy : sup , , y D t y   26 khi đó siêu phẳng ,t x  tách C và D . 2.2 Định lý tách 2 Bổ đề 2.2 (xem [2], bổ đề 6.2) Cho nC R là một tập lồi đóng khác rỗng sao cho 0 C . Khi đó tồn tại một véc-tơ , 0nt R t  và 0  sao cho , 0, t x x C    . Chứng minh Do C đóng và 0 C , nên tồn tại quả cầu B tâm ở gốc, bán kính 0r  sao cho C B  . Áp dụng định lý tách 1 cho hai tập C và B , ta có  \ 0nt R và R  , sao cho , , , t x t y x C y B      . Bằng chuẩn hóa ta có thể xem 1t  và do đó khoảng cách từ gốc đến siêu phẳng ít nhất là bằng r  . Vậy thì , 0t x r   . Nhận xét 2.1 Theo bổ đề này thì C và điểm gốc tọa độ có thể tách mạnh, ví dụ bởi siêu phẳng , 2 t x  . Định lý 2.2 (Định lý tách 2) (xem [2], định lý 6.2) Cho C và D là hai tập lồi đóng khác rỗng sao cho C D  . Giả sử có ít nhất một tập là com-pắc. Khi đó hai tập này có thể tách mạnh được bởi một siêu phẳng. Chứng minh Giả sử C là tập Compact. Ta chỉ ra tập C D đóng. 27 Thật vậy, giả sử kz C D  và kz z . Ta có k k kz x y  với , k kx C y D  . Vì C compact, nên có một dãy con jkx x khi j  . Vậy j j jk k ky x z x z D     . Vậy z x y C D    . Chứng tỏ C D là tập đóng. Do 0 C D  nên theo bổ đề 2.2, tồn tại 0t  sao cho , 0t x y    với mọi ,x C y D  . Vậy inf , sup , 2 2x C y D t x t y       . Chứng tỏ C và D có thể tách mạnh. Nhận xét 2.2 Điều kiện một trong hai tập là com-pắc trong định lý là không thể bỏ được Ví dụ 2.1 Cho hai tập hợp:      2 2 : , | 0, 0 , 1: , | , 0, 0 C x t R x t D x t R t t x x              . Rõ ràng hai tập này lồi, đóng, không có điểm chung, nhưng chúng không thể tách mạnh được. Hình 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C O 28 Từ định nghĩa ta thấy rằng, nếu hai tập nằm trong cùng một siêu phẳng, thì chúng vẫn tách được, ví dụ chính bằng siêu phẳng đó. Để tránh trường hợp này người ta đưa ra khái niệm tách đúng sau: Định nghĩa 2.3 Hai tập C và D được gọi là tách đúng bởi siêu phẳng Ta x  nếu , , T Ta x a y x C y D      và cả hai tập này không cùng nằm trọn trong siêu phẳng tách. Mệnh đề 2.3 (xem [2], mệnh đề 6.1) Cho hai tập lồi khác rỗng A và B . Điều kiện cần và đủ để hai tập này tách đúng là ri riA B  . Chứng minh Điều kiện cần Giả sử có siêu phẳng Tt x  tách A và B , tức là ' ' , , T Tt x t y x A y B      . Giả sử siêu phẳng này không chứa B , khi đó , riTt y y B   . Suy ra ri riA B   . Điều kiện đủ Giả sử ri riA B  . Khi đó,    0 ri ri riA B A B    . Xét hai trường hợp: i) Trường hợp  int A B   . Khi đó  0 int A B  . Vậy tồn tại 0t  và , int , intT Tt x t y x A y B     . Đặt    inf | int , sup | intT Tt y y B t x x A     , thì   . Lấy     . Khi đó siêu phẳng Tt x  sẽ tách A và B , nhưng không thể đồng thời chứa cả A và B . ii) Trường hợp  int A B   . 29 Đặt C A B  và F là không gian con song song với bao a-phin của C . Khi đó, áp dụng lập luận ở phần trên cho không gian F , sẽ tồn tại một siêu phẳng 'H (trong F ) tách đúng A và B . Gọi 't là phiếm hàm tuyến tính từ F R xác định siêu phẳng 'H . Gọi F  là không gian vuông góc với F . Với mỗi nx R đặt  t x là hàm hợp giữa 't và p , trong đó p là ánh xạ chiếu xuống không gian con F . Do p là tuyến tính, nên dễ thấy t và 't cũng là tuyến tính và là siêu phẳng tách đúng hai tập A và B . Nhận xét 2.3 Nếu A và B là hai tập lồi mà ri riA B  , thì hai tập này vẫn có thể tách được. Ví dụ 2.2 A và B là hai đường chéo của một hình chữ nhật trong mặt phẳng 2-chiều. Rõ ràng A và B là hai tập lồi mà ri riA B  , chúng vẫn tách được bằng chính mặt phẳng nhưng chúng không tách đúng được. Một hệ quả rất quan trọng của định lý tách là bổ đề chọn mang tên nhà toán học Hungary Farkas, được chứng minh từ năm 1892 dưới dạng một định lý hình học. Bổ đề này rất trực quan, dễ áp dụng trong nhiều lĩnh vực như tối ưu, điều khiển, lý thuyết toán tử Hệ quả 2.1 (Bổ đề Farkas) (xem [2], hệ quả 6.1) Cho A là một ma trận thực cấp m n và na R . Khi đó trong hai hệ dưới đây có một hệ và chỉ duy nhất một hệ có nghiệm: 0, 0TAx a x  với một nx R , (2.1) , 0TA y a y  với một my R . (2.2) Một cách phát biểu tương đương dưới ngôn ngữ hình học là: 30 Nửa không gian  | 0Tx a x  chứa nón  | 0x Ax  khi và chỉ khi véc tơ a nằm trong nón sinh bởi các hàng của ma trận A tức là 0 0T TA x a x   khi và chỉ khi , 0TA y a y  Tính chất hình học của bổ đề này rất rõ. Nó nói rằng nón lồi, đóng  | 0x Ax  nằm trong nửa không gian  | 0Tx a x  khi và chỉ khi véc tơ pháp tuyến a ở trong nón sinh bởi các hàng của ma trận A . Hình 2 Chứng minh Giả sử (2.2) có một nghiệm y nào đó. Nếu như 0Ax  , thì từ TA y a , nhân tích vô hướng với x , và do 0, 0Ax y  , ta có 0T Ta x y Ax  . Vậy (2.1) không thể có nghiệm. Giả sử hệ (2.2) không có nghiệm. Lấy tập  | 0 : TC x y A y x    Hiển nhiên C là tập lồi đóng và 0 C . 0Ax  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a . . . . . . . . . . . . 31 Do (2.2) không có nghiệm nên a C . Theo định lý tách 2, tồn tại 0p  và một số R  sao cho T Tp a p x  với mọi x C . Do 0 C nên 0  .Thay Tx A y , với 0y  , ta viết được T T Tp A y y Ap   . Bên cạnh đó, nếu x C thì x C  với mọi 0  . Vì từ Tx A y , có Tx A y  . Vậy các tọa độ của y có thể lớn tùy ý, nên từ bất đẳng thức T T Tp A y y Ap   , suy ra 0Ap  . Vậy, ta đã chỉ ra sự tồn tại của một véc tơ p sao cho 0Ap  và 0Ta p  . Chứng tỏ rằng (2.1) có nghiệm. 32 CHƯƠNG 3 ỨNG DỤNG CỦA ĐỊNH LÝ TÁCH 3.1. Điều kiện tối ưu. Định nghĩa 3.1. Cho nC R khác rỗng và : nf R R . Một điểm *x C được gọi là điểm cực tiểu địa phương của f trên C nếu tồn tại một lân cận U của *x sao cho    * f x f x x U C    . Điểm *x C được gọi là điểm cực đại địa phương nếu nếu tồn tại một lân cận U của *x sao cho    * f x f x x U C    . Nếu    * f x f x x C   thì *x được gọi là cực tiểu toàn cục hay cực tiểu tuyệt đối của f trên C , và nếu    * f x f x x C   thì *x được gọi là cực đại toàn cục hay cực đại tuyệt đối của f trên C. Bài toán OP: Tìm cực tiểu của một hàm lồi trên một tập lồi có dạng sau min  f x với các điều kiện   0, 1,...,ig x i m  ,   0, 1,...,jh x j k  x X 33 Trong đó nX R là một tập lồi đóng khác rỗng và  , 1,...,if g i m là các hàm lồi hữu hạn trên X , còn   1,...,jh j k là các hàm a-phin hữu hạn trên tập a-phin của X . Ta sẽ luôn giả sử rằng X có điểm trong và các hàm aphin   1,...,jh j k độc lập tuyến tính trên X , theo nghĩa, nếu   1 0 k j j j h x   với mọi x X , thì 0j  với mọi j . Bài toán (OP) này được gọi là một quy hoạch lồi. Hàm f được gọi là hàm mục tiêu. Các điều kiện    , 0 1,...,ix X g x i m   ,    0, 1,...,jh x j k  được gọi là ràng buộc. Tập     : | 0 1,..., , 0, 1,...,i jD x X g x i m h x j k      . được gọi là miền chấp nhận được. Một điểm x D được gọi là điểm chấp nhận được của bài toán (OP). Do X là tập lồi, các hàm  1,...,ig i m lồi trên X và  1,...,jh k aphin, nên D là một tập lồi. Điểm cực tiểu của f trên D cũng được gọi là nghiệm tối ưu của bài toán (OP). Ta xây dựng hàm sau, được gọi là hàm Lagrange, cho bài toán (OP):        0 1 1 , , : m k i i j j i j L x f x g x h x           . Dựa vào hàm Lagrange, ta có kết quả sau: Định lý 3.1 (Karush – Kuhn - Tucker) (xem [2], Định lý 9.1) Nếu *x là nghiệm của bài toán quy hoạch lồi (OP) thì tồn tại  * 0 0,1,...,i i m   và  * 1,...,j j k  không đồng thời bằng 0 sao cho    * * * * *, , min , , x X L x L x      (điều kiện đạo hàm triệt tiêu)    * * 0 1,..,i ig x i m   (điều kiện độ lệch bù) Hơn nữa nếu int X   và điều kiện Slater sau thỏa mãn 34    0 0: 0 1,...,ix D g x i m    thì *0 0  và hai điều kiện đạo hàm triệt tiêu và độ lệch bù ở trên cũng là điều kiện đủ để điểm chấp nhận được *x là nghiệm tối ưu của bài toán (OP). Chứng minh Giả sử *x là nghiệm của (OP). Đặt             *0 1 1 0: , ,..., , ,..., | : , , 1,..., , , 1,...,m k i i j JC x X f x f x g x i m h x j k                Do X   lồi, , if g lồi và jh a-phin hữu hạn trên X nên C là một tập lồi khác trống trong 1m kR   . Hơn nữa 0 C . Thật vậy, vì nếu trái lại 0 C , thì tồn tại một điểm chấp nhận được x thỏa mãn    *f x f x . Điều này mâu thuẫn với việc *x là nghiệm tối ưu của (OP). Khi đó theo định lý tách 1, tồn tại    * *0,1,..., , 1,...,i ji m j k   không đồng thời bằng 0 sao cho  * * 0 1 1 0 1 0 , ,..., , ,..., m k i i i i m k i j C                . (3.1) Chú ý rằng với mọi 0 ,..., 0m   , thì  0 1,..., , ,...,m k C     , vì theo định nghĩa của C ta chỉ lấy *x x . Từ chú ý này, ta suy ra ngay tất cả * * *0 1, ,..., 0m    . Hơn nữa, với mọi 0  và x X , ta lấy           *0 , 1,..., , 1,...,i i j jf x f x g x i m h x j k          , thì  0 ,..., , 0,...,0m C   . Thay vào (3.1) và cho 0  , sẽ được            * * * * * * * * *0 0 1 1 1 1 m k m k i i i i i i i i i i i i f x g x h x f x g x h x x X                    . Hay    * * * * *, , , , L x L x x X      . 35 Đây chính là điều kiện đạo hàm triệt tiêu. Để chứng minh độ lệch bù, ta chú ý rằng do *x chấp nhận được, nên  * 0 ig x i  . Nếu như tồn tại một i nào đó mà  *ig x  , thì với mọi 0  , ta có  ,..., , ,..., , 0,...,0 C     ( ở vị trí thứ 1i  ) Thay vào (*) và cho 0  , ta thấy * 0i   . Nhưng 0  , nên * 0i  . Suy ra * 0i  . Điều kiện độ lệch bù do đó cũng được thỏa mãn. Để chứng minh điều kiện đủ, ta giả sử điều kiện Staler thỏa mãn. Ta có * 0 0  . Thật vậy, vì nếu *0 0  , thì do điều kiện đạo hàm triệt tiêu và điều kiện độ lệch bù, ta có        * * * * * * 1 1 1 1 0 m k m k i i j j i i j j i j i j g x h x g x h x x X                 . Thế nhưng do *0 0  , nên phải có hoặc * 0i  với một i nào đó, hoặc nếu * 0i  với mọi i , thì sẽ có * 0j  với một j nào đó. Trong trường hợp đầu, thay 0x vào bất đẳng thức trên sẽ được        * * * * * 0 * 0 1 1 1 1 0 <0 m k m k i i j j i i j j i j i j g x h x g x h x               . Mâu thuẫn. Trong trường hợp sau, ta có:    * * * 1 1 0 k k j j j j j j h x h x x X         Do int X   và jh aphin với mọi j , nên từ đây suy ra   0 0 k j j h x x X     . Từ đây và do các hàm jh độc lập tuyến tính trên X , ta có * 0 j j   . Điều này mâu thuẫn với việc tất cả các nhân tử *i và * j không đồng thời bằng 0. Vậy *0 0  . Do *0 0  , nên bằng cách chia cho *0 0  , ta có thể coi hàm Lagrange là 36         1 1 , , m k i i j j i j L x f x g x h x          . Từ điều kiện đạo hàm triệt tiêu và độ lệch bù, nên với mọi x chấp nhận được, ta có:              * * * *0 1 1 1 1 m k m k i i j j i i j j i j i j f x f x g x h x g x h x f x                 . Chứng tỏ *x là lời giải tối ưu của (OP). Nhận xét 3.1 Khi X là tập mở (nói riêng là toàn không gian) và mọi hàm đều khả vi, thì điều kiện đạo hàm triệt tiêu sẽ là      * * * * * *0 0 1 1 0 m k j j i i j i f x g x h x            . Như vậy, bài toán trên cho ta thấy một cách định lượng khi xét một bài toán tìm cực tiểu của một hàm lồi trên một tập lồi. Người ta cũng đã chứng minh một cách định tính được rằng mọi điểm cực tiểu địa phương của một hàm lồi trên một tập lồi cũng chính là điểm cực tiểu tuyệt đối (xem [2] chương 9,mệnh đề 9.1). Tính chất trên không thể áp dụng cho cực đại của hàm lồi: Cực đại địa phương của một hàm lồi không nhất thiết là cực đại tuyệt đối. Ví dụ 3.1 Xét hàm số 2( )f x x trên đoạn  1, 2 . Hàm số 2( )f x x đạt cực đại địa phương trên đoạn  1, 2 là 1x   , nhưng điểm cực đại tuyệt đối lại là 2x  . 3.2. Hệ bất đẳng thức lồi Trong phần này chúng ta sử dụng định lý tách để tìm điều kiện cần và đủ để hệ bất đẳng thức lồi có nghiệm. Định nghĩa 3.2 37 Cho nD R là một tập lồi và 1,..., mf f là các hàm lồi trên nR . Hệ bất đẳng thức  , 0,ix D f x i I   Được gọi là hệ bất đẳng thức lồi, trong đó I là tập chỉ số và ký hiệu  có thể hiểu là  hoặc  . Hệ bất đẳng thức lồi xuất hiện trong nhiều ứng dụng. Do tính chất của hàm lồi, tập nghiệm của một hệ bất đẳng thức lồi luôn là một tập lồi. Dựa vào các định lý tách, ta có thể đưa ra những điều kiện cần và đủ về sự tồn tại nghiệm của một hệ bất đẳng thức lồi. Mệnh đề 3.1 (xem [2], mệnh đề 9.5) Giả sử 0 1, ,..., mf f f là các hàm lồi hữu hạn trên tập lồi D   . Khi đó, hệ  , 0, 0,1,...,ix D f x i m   (3.2) không có nghiệm, khi và chỉ khi tồn tại các số  0 0,1,...,i i m   không đồng thời bằng 0 sao cho   0 0 m i i i f x x D     . Ngoài ra, nếu có điều kiện chính quy Slater: tồn tại  0 0, 0ix D f x  với mọi 1,...,i m thì 0 0  . Chứng minh Điều kiện đủ là hiển nhiên, nên ta chỉ cần chứng minh điều kiện cần. Giả sử hệ (3.2) không có nghiệm. Đặt     10 1: , ,..., | , , 0,...,mm i iC y y y y R x D f x y i m       . Do D và if lồi  0,...,i m nên C lồi. Theo giả thiết hệ (9.4) không có nghiệm nên 0 C . Áp dụng định lý tách, tồn tại  0 1, ,..., 0m     sao cho 38 0 0 m i i i y y C     . Chú ý rằng theo định nghĩa của C , với mọi x D và 0  , ta có     0 ,..., mf x f x C    . Vậy    0 0 m i i i f x x D       . Điều này đúng với mọi 0  , nên suy ra   0 0 m i i i f x x D     . (3.3) Ta sẽ chứng tỏ 0 i i   . Thật vậy, nếu trái