Luận văn Về điều kiện chính quy cấp hai và điều kiện tối ưu cấp hai

g suy rộng ( , ) (0,0 )   thỏa mãn điều kiện (1.16). Chú ý rằng với không gian Banach Y tập hợp * 0( x ) có thể rỗng. Điều kiện tối ƣu Fritz John ở trên là điều kiện cần cho nghiệm tối ƣu địa phƣơng, tức là * 0( x )  . Ta chú ý hai trƣờng hợp quan trọng. Cụ thể là khi Y là không gian hữu hạn chiều, hoặc khi K có phần trong khác rỗng. Nếu nhân tử  trong (1.16) khác không thì ta có thể lấy 1  , và vì vậy điều kiện cần cấp 1 trở thành  x 0 K 0D L( x , ) 0, N (G( x )) . (1.17) Với điều kiện chính quy Robinson (1.13), tập hợp 0( x ) các nhân tử Lagrange thỏa mãn (1.17) là khác rỗng và bị chặn (xem [8]). 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Khi tập K là một nón lồi và y K , nón pháp tuyến KN ( y ) có dạng:  0* *KN ( y ) y K : y ,y   , trong đó  * * *K : y Y : y ,y 0, y K      là nón cực của nón K (đối ngẫu âm). Trong trƣờng hợp đó, điều kiện K 0N (G( x )) trở thành K  và 0,G( x ) 0  . Nhắc lại rằng: nón  0 0 K 0 0C( x ): h X : DG( x )h T (G( x )),Df ( x )h 0    (1.18) đƣợc gọi là nón tới hạn (critical cone) của bài toán ( P ) tại điểm 0x . Nón này biểu diễn các phƣơng tuyến tính hóa cấp một của ( P ) . Chú ý rằng khi tập 0( x ) các nhân tử Lagrange khác rỗng thì 0Df ( x )h 0 với mọi h X thỏa mãn 0 K 0DG( x )h T (G( x )) . Trong trƣờng hợp đó bất đẳng thức 0Df ( x )h 0 , trong định nghĩa của nón tới hạn có thể thay bởi đẳng thức 0Df ( x )h 0 . Điều đó là tƣơng đƣơng với 0,DG( x )h 0  với mọi 0( x )  . Bây giờ ta có thể phát biểu điều kiện cần tối ƣu cấp hai dựa trên sự phân tích đƣờng cong chấp nhận đƣợc parabol có dạng 2 2 0 1 x(t) = x th t + o(t ) 2   , (1.19) trong đó t 0 . Điều kiện cần này kết hợp với điều kiện đủ trong định lý 1.2 dẫn tới khái niệm chính quy cấp hai. 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Định lý 1.1 Giả sử 0x là nghiệm tối ưu địa phương của bài toán ( P ) . Giả sử rằng điều kiện chính quy Robinson (1.13) đúng. Khi đó, với mọi 0h C( x ) và tập lồi bất kỳ T 2 K 0 0( h ) O (G( x ),DG( x )h ) ,  0 2 xx 0 ( x ) Sup D L( x , )( h,h ) ( ,       T ( )) 0h  . (1.20) Chứng minh Chú ý rằng nếu T (h)=  thì (., T (h)) =   và (1.20) đúng một cách tầm thƣờng. Ta giả sử T (h) và do đó tập 2 K 0 0O (G( x ),DG( x )h ) khác rỗng. Ta khẳng định rằng giá trị tối ƣu của bài toán: 2 0 0 X MinDf ( x ) +D f ( x )( h,h )  , (1.21) 2 2 0 0 K 0 0DG( x ) +D G( x )( h,h ) O (G( x ),DG( x )h )  là không âm. Thật vậy, nếu  là điểm chấp nhận đƣợc của bài toán này, sử dụng mệnh đề 1.3 ta nhận đƣợc 2 00 ( x ,h ) , trong đó: 1: G ( K )  . Vì thế ta có thể tìm đƣợc dãy kt 0 sao cho    2 2k 0 k k 1 x : x t h t + o(t ) 2  . 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Dãy kx là chấp nhận đƣợc của bài toán ( P ) và hội tụ đến cực tiểu địa phƣơng 0x . Do đó, k 0f ( x ) f ( x ) với mọi k đủ lớn. Sử dụng khai triển Taylor cấp hai ta có 2 2 2 0 k 0 k 0 k 0 0 k 1 f ( x ) f ( x ) f ( x ) t Df ( x )h t Df ( x ) +D f ( x )( h,h ) ( t ) 2        . Bởi vì 0Df ( x )h 0 , với bất kỳ 0h C( x ) , ta nhận đƣợc 2 0 0Df ( x ) +D f ( x )( h,h ) 0 . Nhƣ vậy, giá trị tối ƣu của bài toán (1.21) không âm. Bây giờ ta xét tập T(h) := cl {T (h) K 0T (G( x )) . Tập này là bao đóng tôpô của tổng hai tập lồi và vì thế là lồi. Hơn nữa, từ bao hàm thức (1.12) và sự kiện: các tập tiếp tuyến ngoài cấp hai đóng, ta suy ra 2 K 0 0T( h ) O (G( x ),DG( x )h ) . Rõ ràng nếu ta thay đổi các tập tiếp tuyến cấp hai ngoài trong (1.21) bằng tập con T( h ) của nó thì giá trị tối ƣu của bài toán tối ƣu sẽ lớn hơn hay bằng giá trị tối ƣu của (1.21). Do đó, giá trị tối ƣu của bài toán: 2 0 0 X MinDf ( x ) +D f ( x )( h,h )  , (1.22) 2 0 0DG( x ) +D G( x )( h,h ) T( h )  là không âm. Bài toán tối ƣu (1.22) lồi và đối ngẫu (tham số) của nó là:   0 2 xx 0 (x ) Max D L( x , )( h,h ) ( ,T( h ))      (1.23) Thật vậy, hàm Lagrange của (1.22) là 19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 x 0 xx 0L( , )=D L( x , ) +D L( x , )( h,h )   . Bởi vì với bất kỳ z T( h ) , ta có K 0z T (G( x )) T( h ),  cho nên ( ,T( h ))    với mỗi  K 0 K 0T (G( x )) N (G( x ))  . Vì thế miền hữu hiệu của đối ngẫu tham số của (1.22) là nằm trong 0( x ) . Khi đó ta suy ra tính đối ngẫu. Hơn nữa, điều kiện chính quy Robinson (1.13) kéo theo 0 K 0DG( x )X T (G( x )) Y  . Bởi vì với bất kỳ z T( h ) thì K 0z T (G( x )) T( h )  , ta có 0z DG( x )X T( h ) Y   . Do đó (1.22) có một nghiệm chấp nhận đƣợc và điều kiện chính quy Robinson cho bài toán (1.22) cũng đúng. Do đó, không có lỗ hổng đối ngẫu giữa (1.22) và đối ngẫu (1.23) (xem [3]). Ta nhận đƣợc giá trị tối ƣu của (1.23) không âm. Bởi vì T (h) T( h ) , ta có ( ,  T (h)) ( ,T( h ))  . Vì vậy ta suy ra (1.20) và định lý đƣợc chứng minh. Nhận xét (i) Nhƣ chúng ta đã đề cập ở phần trƣớc, tập tiếp tuyến cấp hai ngoài 2 K 0 0O (G( x )),DG( x )h ) có thể không lồi. Tuy nhiên khi nó lồi ta có thể sử dụng tập này ở trong điều kiện cấp hai (1.20), và ta nhận đƣợc một điều kiện cần tốt hơn. Trong bất kỳ trƣờng hợp nào có thể lấy T (h) là tập tiếp tuyến cấp hai trong 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 K 0 0T (G( x )),DG( x )h . Nói chung, tập T (h) có thể lấy lớn hơn 2 K 0 0T (G( x ),DG( x )d ) và do đó định lý 1.1 là mạnh hơn. (ii) Chú ý rằng trong điều kiện cần tối ƣu cấp hai, giá trị tối ƣu của bài toán (1.21) là không âm. (iii) Nếu 2 K 0 00 O (G( x ),DG( x )h ) với mọi 0h C( x ) , nói riêng nếu tập K là một đa diện, thì K 0 2 K 0 0 T ( G( x )) 0O ( G( x ),DG( x )h ) T ( DG( x )h ) , và ( ,  T (h)) = 0 với mỗi 0( x )  , và T (h) 2 K 0 0: O (G( x ),DG( x )h ) . (iv) Giả sử  là tập hợp của các dãy  nt các số dƣơng hội tụ tới 0. Với bất kỳ  ns= t  , y K , và Kd T ( y ) ta có thể đƣa vào tập tiếp tuyến cấp hai dƣới đây: 2,s 2 2 K n 1 T ( y,d ) : :dist(y+t d t ,K)= (t ) 2         . Với bất kỳ s  , tập 2,s KT (y,d) là lồi và đóng. Rõ ràng giao của 2,s KT ( y,d ) theo tất cả s  là 2 KT (y,d) , và hợp của 2,s KT ( y,d ) lấy theo s  là 2 KO ( y,d ) . Một cách chọn T (h) là 2,s K 0 0T (G( x ),DG( x )h ) với bất kỳ s  . (v) Ta có thể phát biểu điều kiện cần cấp hai (1.20) dƣới dạng   0 2 xx 0 O(h) ( x ) inf sup D L( x , )( h,h ) ( ,T( h )) 0          , (1.24) T (h) 21 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên trong đó O(h) kí hiệu tập tất cả các tập con lồi của 2 K 0 0O (G( x ), DG( x )h ) . Nói riêng, nếu ta lấy tất cả các tập con một phần tử của 2 K 0 0O (G( x ), DG( x )h ) thì điều kiện (1.24) kéo theo điều kiện cần dƣới đây   2 0K 0 0 2 xx 0 ( x )y O ( G( x ),DG( x )h ) inf sup D L( x , )( h,h ) ,y 0      . (1.25) Nếu 0( x ) là tập một phần tử, chẳng hạn  0 0( x )  , thì điều kiện (1.25) trở thành 2 2 xx 0 0 0 K 0 0D L( x , )( h,h ) ( ,O (G( x ),DG( x )h )) 0   . (1.26) Định nghĩa 1.1 Giả sử S  là tập các điểm chấp nhận được của bài toán ( P ) thoả mãn 0f ( x ) f với mỗi x S . Ta nói rằng điều kiện tăng trưởng cấp hai đúng tại S nếu tồn tại hằng số c 0 và lân cận N của S sao cho    2 0f ( x ) f c dist(x,S) với mọi x N  . (1.27) Nói riêng, nếu   0S x là tập một phần tử, điều kiện tăng trƣởng cấp hai (1.27) sẽ có dạng 2 0 0f ( x ) f ( x ) c x x   với mọi x N  . (1.28) Điều này rõ ràng kéo theo 0x là một nghiệm tối ƣu địa phƣơng của ( P ) . Hơn nữa, với giả thiết điều kiện Ronbinson (1.13) đúng, khi đó với bất kỳ 0h C( x ) giá trị tối ƣu của (1.21) là lớn hơn hay bằng 2 2c h . Vì 22 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên thế điều kiện cần cấp hai (1.20) trở thành bất đẳng thức chặt với mọi 0h C( x ) khác không. Điều kiện cần cấp hai (1.20) đƣợc dựa trên đánh giá ƣớc lƣợng trên của hàm mục tiêu dọc theo đƣờng cong parabol chấp nhận đƣợc có dạng (1.19). Để đánh giá ƣớc lƣợng dƣới, và do đó để nhận đƣợc điều kiện đủ cấp 2 ta đƣa vào khái niệm sau. Định nghĩa 1.2 Giả sử Ky K,d T ( y )  và xét ánh xạ tuyến tính liên tục M : X Y . Ta nói rằng tập đóng K,MA ( y,d ) Y là xấp xỉ trên cấp 2 của K tại y theo phương d và theo M , nếu với bất kỳ dãy ky K có dạng 2 k k k k 1 y : y t d t r 2    , trong đó kt 0 và k k kr M a  với  ka là dãy hội tụ trong Y và  k X  thỏa mãn k kt 0  , điều kiện dưới đây đúng: k K ,M k limdist( r ,A ( y,d )) 0   . (1.29) Nếu điều kiện trên đúng với bất kỳ X và M , tức là (1.29) thỏa mãn với bất kỳ dãy   2k k k 1 y t d t r K 2 sao cho k kt r 0 , thì ta bỏ qua M và nói rằng tập KA ( y,d ) là tập xấp xỉ trên cấp hai của K tại điểm y theo phương d . Định nghĩa trên nhằm mục đích cho ta tập đủ lớn KA ( y,d ) sao cho nếu y td ( t )  là đƣờng cong trong K mà tiếp xúc với d với 23 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ( t ) ( t )  , thì số dƣ cấp hai 2 ( t ) r( t ) : 1 t 2   tiến đến KA ( y,d ) khi t 0 . Chú ý rằng số dƣ r(t) và dãy k kr r( t ) có thể không bị chặn. Xấp xỉ trên cấp hai KA ( y,d ) không duy nhất. Rõ ràng, nếu KA ( y,d ) B , thì B cũng là xấp xỉ trên cấp hai. Nếu Ky K,d T ( y )  và y d K   thì Kd+ T ( y ) . Vì vậy, KT ( y ) T ( d ) . Do đó, KT ( y ) T ( d ) là tập xấp xỉ trên cấp hai. Từ định nghĩa suy ra tập tiếp tuyến cấp hai ngoài 2 KO ( y,d ) nằm trong các tập xấp xỉ trên cấp hai K ( y,d ) . Định lý 1.2 Giả sử 0x là điểm chấp nhận được của bài toán ( P ) thỏa mãn điều kiện tối ưu cấp một ( kiểu Fritz John) (1.16). Giả sử mỗi 0h C( x ) tương ứng với một tập xấp xỉ trên cấp hai trên K ,M 0( h ) : ( y ,d )  của tập K tại điểm 0 0y : G( x ) theo phương 0d : DG( x )h và theo ánh xạ tuyến tính 0M : DG( x ) . Giả sử rằng điều kiện cấp hai dưới đây thỏa mãn:   * 0 2 * xx 0 ( , ) ( x ) sup D L ( x , , )( h,h ) ( , ( h )) 0            (1.30) với mọi  0h C( x )\ 0 . Khi đó, điều kiện tăng trưởng cấp hai (1.28) đúng tại 0x , và vì vậy 0x là nghiệm tối ưu địa phương chặt của ( P ) . Chứng minh Ta chứng minh phản chứng. Giả sử rằng điều kiện tăng trƣởng cấp hai là không đúng tại 0x . Khi đó tồn tại dãy điểm chấp nhận đƣợc k k 0x ,x x  , hội tụ tới 0x và sao cho 24 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 k 0 kf ( x ) f ( x ) o( t )  , (1.31) trong đó k k 0t : x x  . Bởi vì không gian X là hữu hạn chiều, các tập con đóng bị chặn trong X là compact. Vì vậy ta có thể giả sử rằng k 0 k k x x h : t   hội tụ đến một vectơ h X . Rõ ràng h 1 , và vì vậy h 0 . Sử dụng khai triển Taylor cấp một, do kG( x ) K , ta nhận đƣợc 0 K 0DG(x )h T (G( x )) . Từ (1.31) ta có 0Df ( x )h 0 . Vì vậy 0h C( x ) . Khai triển Taylor cấp hai của kG( x ) tại 0x , ta có 2 2 2 k 0 k k 0 k 0 k 1 G( x ) y t d t ( DG( x ) D G( x )( h,h ) o( t ) 2     , trong đó 0 0 0y : G( x ),d : DG( x )h  và  2k k k 0 k: 2t x x t h    . Chú ý rằng k 0 k kx x t h o( t )   , và vì thế k kt 0  . Từ định nghĩa xấp xỉ trên cấp hai ta suy ra 2 0 k 0 YDG(x ) D G( x )( h,h ) ( h ) o(1)B   . (1.32) Ta cũng có 2 2 2 k 0 k 0 k 0 k 0 k 1 f(x ) f ( x ) t Df ( x )h t ( Df ( x ) D f ( x )( h,h )) o( t ) 2     . 25 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Vì vậy, sử dụng (1.31) và (1.32) ta tìm đƣợc dãy k 0 sao cho         1 2 k 0 0 k 0 k 2 0 k 0 k Y 2t Df ( x )h ( Df ( x ) D f ( x )( h,h ) , DG( x ) G( x )( h,h ) ( h ) B .      (1.33) Từ (1.30) suy ra tồn tại  * 0( , ) x   sao cho 2 * xx 0D L ( x , , )( h,h ) ( , ( h ))      , (1.34) với 0  nào đó. Từ điều kiện thứ hai trong (1.33) ta suy ra   20 k 0 k Y k ,DG( x ) D G( x )( h,h ) , h ( , ( h ) k .                Ta cũng có 0  , và nếu 0  thì 0Df ( x )h 0 . Trong trƣờng hợp bất kỳ 0Df ( x )h 0  , và vì vậy từ (1.33) và (1.34) ta nhận đƣợc 1 2 k 0 0 k 0 k 2 0 k 0 k 0 ( 2t Df ( x )h Df ( x ) D f ( x )( h,h ) ) ,DG( x ) D G( x )( h,h ) ( ,A( h ))                  2 * xx 0 k k D L ( x , , )( h,h ) ( , ( h )) ( ) ( ).                    Bởi vì k 0  cho nên dẫn tới một mâu thuẫn, và định lý đƣợc chứng minh. Chú ý tính hữu hạn chiều của X đƣợc sử dụng để dẫn điều kiện đủ cấp hai còn điều kiện cần cấp hai không đòi hỏi giả thiết này. Nếu tập 0( x ) của các nhân tử Lagrange khác rỗng thì điều kiện đủ (1.30) là tƣơng đƣơng với: 26 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   0 2 xx 0 ( x ) sup D L( x , )( h,h ) ( ,A( h ) 0         , với mọi  0h C( x )\ 0 (1.35) Nhƣ đã nói ở trên, tập K 0T ( G( x )) 0 (h):=T ( DG( x )h ) luôn là tập xấp xỉ trên cấp hai. Hơn nữa, K 0 00, T (G( x )), ,DG( x )h 0  , +  , trong trƣờng hợp ngƣợc lại. Vì thế với cách chọn tập xấp xỉ trên cấp hai đó, điều kiện đủ cấp hai (1.30) có dạng * 0 2 * xx 0 ( , ) ( x ) sup D L ( x , , )( h,h ) 0        , với mọi  0h C( x )\ 0 . (1.36) Ta nhận đƣợc kết quả sau đây Hệ quả 1.2.1 Giả sử 0x là điểm chấp nhận được của bài toán ( P ) thỏa mãn điều kiện tối ưu cấp một (kiểu Fritz John) (1.16). Giả sử điều kiện đủ cấp hai (1.36) thỏa mãn. Khi đó điều kiện tăng trưởng (1.28) đúng tại 0x . Nếu tập các nhân tử Lagrange 0( x ) là khác rỗng, thì có thể thay thế * 0( x ) trong (1.36) bằng 0( x ) . Định nghĩa 1.3 Ta nói tập K là chính quy cấp hai ngoài tại điểm y K theo phương Kd T ( y ) và theo ánh xạ tuyến tính M : X Y nếu với bất kỳ dãy ny K có dạng 2 n n n n 1 y : y t d t r 2    , trong đó n n n nt 0,r M a   , với  na là dãy hội tụ trong Y và  n là dãy trong X thỏa mãn n nt 0  , điều kiện dưới đây đúng ( , ( ))h    27 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 n K n limdist( r ,O ( y,d )) 0   . (1.37) Nếu K là chính quy cấp hai ngoài tại y K theo mọi phương Kd T ( y ) và theo bất kỳ X và M thì ta nói rằng K là chính quy cấp hai ngoài tại y . Nếu thêm vào 2 2 K KO ( y,d ) T ( y,d ) với mọi Kd T ( y ) , ta nói rằng K là chính quy cấp hai tại y . Chính quy cấp hai ngoài có nghĩa là tập tiếp tuyến cấp hai ngoài 2 KO ( y,d ) cho ta một xấp xỉ cấp hai trên của K tại y theo phƣơng d . Nếu các tập tiếp tuyến cấp hai trong và ngoài trùng nhau, ta gọi đơn giản là chính quy cấp hai. Tính chính quy cấp hai có nghĩa là nếu y td+ (t) là đƣờng cong trong K tiếp xúc với d với ( t ) o( t )  , thì 2 ( t ) r( t ) : 1 t 2   là gần tùy ý với 2 KT ( y,d ) khi t 0 . Định lý 1.3 Giả sử 0x là điểm chấp nhận được của ( P ) thỏa mãn điều kiện cần cấp một (1.17). Giả sử điều kiện chính quy Robinson (1.13) đúng và với mọi 0h C( x ) thì tập K là chính quy cấp hai ngoài tại 0G( x ) theo phương 0DG( x )h và theo 0M : DG( x ) , và tập tiếp tuyến cấp hai ngoài  2K 0 0O G( x ),DG( x )h là lồi. Khi đó, điều kiện tăng trưởng cấp hai (1.28) đúng khi và chỉ khi điều kiện đủ cấp hai (1.35) thỏa mãn với 2 K 0 0A(h)=O (G( x ),DG( x )h ) . Chứng minh 28 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Suy luận (1.35)  (1.28) suy từ định lý 1.2. Điều ngƣợc lại là hệ quả của định lý 1.1 và phần nhận xét về (1.28).  Nhắc lại rằng các tập tiếp tuyến cấp hai trong luôn luôn lồi, và do đó trong trƣờng hợp 2 2 K 0 0 K 0 0O (G( x ),DG( x )h ) T (G( x ),DG( x )h ) , tập tiếp tuyến cấp hai ngoài cũng lồi. Sau đây ta sẽ thấy rằng nghịch ảnh của các ánh xạ khả vi liên tục hai lần thỏa mãn điều kiện chính quy Robinson là chính quy cấp 2. Mệnh đề 1.4 Giả sử K là tập con lồi đóng của Y và G : X Y là ánh xạ khả vi liên tục hai lần. Nếu điều kiện chính quy Robinson (1.13) đúng và K là chính quy cấp hai ngoài tại 0G( x ) theo phương 0DG( x )h và ánh xạ tuyến tính 0M : DG( x ) , thì tập 1G ( K ) là chính quy cấp hai ngoài tại 0x theo phương h . Chứng minh Giả sử 2 1 k 0 1 x : ( ) 2 k k kx t h t r G K     sao cho k k kt 0,t r 0  . Theo mệnh đề 1.3 và định lý ổn định Robinson - Ursescu, tồn tại hằng số L sao cho mọi k đủ lớn ta có   1 2 k 0G ( K ) 1 2 2 k 0 K 0 0 0 2 2 0 k 0 K 0 0 dist(r ,O ( x ,h )) dist r ,DG( x ) O ( G( x ),DG( x )h ) D G( x )( h,h ) Ldist(DG(x )r D G( x )( h,h ),O ( G( x ),DG( x )h )).         Bây giờ khai triển cấp hai kG( x ) ta nhận đƣợc 29 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 2 2 k 0 k 0 k 0 k 0 k 1 G( x ) G( x ) t DG( x )h t ( DG( x )r D G( x )( h,h ) o( t ) 2      . Bởi vì kG( x ) K , tính chính quy cấp hai ngoài của K kéo theo 2 2 0 k 0 K 0 0dist(DG(x )r D G( x )( h,h ),O (G( x ),DG( x )h )) 0  . Vì thế  1 2 k 0G ( K ) dist(r ,O x ,h ) 0 . Do đó, -1 G (K) chính quy cấp 2 ngoài tại 0 x theo phƣơng h. Xét tập  i jF : x X : g ( x ) 0,i 1,..., p;h ( x ) 0, j 1,...,q      đƣợc xác định bởi một số hữu hạn ràng buộc. Giả sử hàm ig và jh là khả vi liên tục hai lần. Từ mệnh đề 1.4 và sự kiện: các tập đa diện là chính quy cấp hai, ta suy ra tập F là chính quy cấp hai tại mọi điểm 0x F thỏa mãn điều kiện chính quy Mangasarian-Fromovitz. Hệ quả 1.4.1 Giả sử 1 nK ,...,K là các tập lồi đóng chính quy cấp hai tại điểm 0 1 ny K ... K   theo phương 1 nK 0 K 0 d T ( y ) ... T ( y )   . Nếu tồn tại một điểm trong nK mà thuộc phần trong của K i, i 1,...,n 1  , thì tương giao 1 nK ... K  chính quy cấp hai tại 0y theo phương d . Chứng minh Ta áp dụng mệnh đề 1.4 cho hàm nG :Y Y đƣợc cho bởi 1 nG( y ) ( y,...,y ),K K ... K    . Ta có K là chính quy cấp hai tại 0 0( y ,.. ,y ) theo phƣơng ( d ,...,d ) . Để kiểm tra điều kiện chính quy Robinson, ta lấy y Y , 0  sao cho ny K và Y 1 n 1y 2 B K ... K     . Nếu 30 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 n Yu ,...,u B , lấy ny y u  , ta có i i Y ik : y u y 2 B K     với mọi i 1,...,n 1  . Vì thế nếu đặt n nk : y K  , ta có i i iu y k y K ,i 1,...,n     và do đó   n YB G(Y ) K   . Điều đó chứng tỏ rằng điều kiện chính quy Robinson thoả mãn.  Trở lại trƣờng hợp các tập đƣợc xác định bởi ràng buộc bất đẳng thức ta sẽ thấy rằng khi các hàm ràng buộc là lồi, ta có thể giảm nhẹ đƣợc giả thiết khả vi. Mệnh đề 1.5 Giả sử  K : y : h( y ) 0  , trong đó h(.) là hàm lồi liên tục tại điểm 0y . Giả sử điều kiện Slate đúng và 0h( y ) 0 . Khi đó, K là chính quy cấp hai ngoài tại 0y khi và chỉ khi với bất kỳ K 0d T ( y ) thỏa mãn ' 0h ( y ,d ) 0 và bất kỳ đường cong y( t ) K có dạng 2 0 1 y( t ) y td+ t r( t ),t 0 2    với tr( t ) 0 khi t 0 , thì bất đẳng thức sau đúng   '' 0 t 0 limsuph ( y ;d ,r( t )) 0 . (1.38) Chứng minh Vì h là lồi và liên tục tại 0y , nên h là khả vi theo phƣơng tại 0y . Xét phƣơng K 0d T ( y ) và dãy 2 k k k k 1 y : y t d t r K 2     với kt 0 và k kt r 0 . Do K 0d T ( y ) ta suy ra ' 0h ( y ,d ) 0 . Bởi vì ' 0h ( y ,d ) 0 kéo theo 2 K 0O ( y ,d ) Y , cho nên ta chỉ cần xét trƣờng hợp ' 0h ( y ,d ) 0 . Do điều kiện Slater, tồn tại điểm y Y sao cho h( y ) 0 . Bởi h(.) lồi, ta có 0 0h( y t( y y )) 0   , với mỗi t ( 0;1) . Do 31 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên đó, điểm y thoả mãn h( y ) 0 có thể chọn gần 0y tùy ý. Vì thế ta có thể giả sử h(.) là liên tục tại y . Giả sử (1.38) đúng. Với 0  , đặt k 0: r ( y y )    . Do tính lồi, với mọi t 0 đủ nhỏ, ta có 2 2 2 2 2 0 0 k k 1 1 1 1 1 h y td+ t 1 t h y td+ t r t h y td+ t r 2 2 2 2 2                               . Bởi vì  0h y 0 và  ' 0h y ,d 0 , chia cho 21 t 2 và cho t 0 , ta rút ra      '' ''0 0 kh y ;d , h y ,d ,r h y .    Do (1.38) ta suy ra   '' 0 k 0h y ;d ,r y y 0    , với mọi k đủ lớn. Mệnh đề 1.1 kéo theo    2k 0 K 0r y y O y ,d   , và do đó   2k K 0 0 k lim sup dist r ,O y ,d y y     . Vì  là nhỏ tùy ý, nên K là chính quy cấp hai. Ngƣợc lại, giả sử K là chính quy cấp hai. Giả sử kt 0 là dãy mà giới hạn trên (1.38) là một giới hạn. Đặt  k kr : r t ,   2k k K 0 1 : dist r ,O y ,d k    . Ta có k 0  . Chọn 2 k K 0r O ( y ,d )  sao cho  k k kr r   . Bởi vì k 0  không mất tính tổng quát ta giả sử rằng với mọi k ta có 1 k Yy 2 B K    . Chọn dãy 0  sao cho 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   2 20 1 2    ky d r o K     . Do đó,    2 20 k k Y 1 1 y d r K B 2 2       . Khi đó, với mọi 0  và  k 0: r y y    ta có 2 2 2 2 2 0 0 k k 2 2 2 2 k Y k 2 2 2 2 k k Y 1 1 1 1 1 y d 1 y d r y d r 2 2 2 2 2 1 1 1 1 1 K B y d r 2 2 2 2 1 1 1 1 1 K y d r 1 B . 2 2 2 2                                                                                                        Bởi vì 1 k Yy 2 B K    ta suy ra 2 0 k 1 y d K 2       . Theo mệnh đề 1.1,  '' 0h y ,d , 0  . Bởi vì h là liên tục tại 0y , cho nên nó là liên tục Lipschitz địa phƣơng. Do đó  '' 0h y ,d ,. là liên tục Lipschitz toàn cục với cùng một hằng số chẳng hạn là L, và  '' 0 k k 0h y ,d ,r L r L y y      . Vì vậy,    '' ''0 0 k 0 t 0 k lim sup h y ,d ,r( t ) lim h y ,d ,r L y y      . Bởi vì  nhỏ tùy ý cho nên ta suy ra kết luận.  33 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chƣơng 2 ĐIỀU KIỆN CẦN TỐI ƢU CẤP HAI CHO BÀI TOÁN TỐI ƢU ĐA MỤC TIÊU Chƣơng 2 trình bày các điều kiện cần tối ƣu cấp 2 cho cực tiểu yếu địa phƣơng của bài toán tối ƣu đa mục tiêu trên cơ sở phát triển định lý luân phiên Motzkin không thuần nhất. Các điều kiện cấp 2 kiểu Kuhn- Tucker đƣợc dẫn khi đƣa vào các điều kiện chính quy cấp 2 kiểu Abadie và Guignard. Các kết quả chƣơng này là của G.Bigi và M.Castellani [4]. 2.1. KIẾN THỨC CHUẨN BỊ Trong chƣơng này, ta đƣa vào một số kí hiệu và định nghĩa mà ta sẽ sử dụng. Giả sử  là không gian ơclit l-chiều;  i: x : x 0,i 1,...,        là orthant dƣơng. Với mỗi tập A  , int A , cl A và conv A kí hiệu tƣơng ứng là phần trong tôpô, bao đóng tôpô và bao lồi của A . Với hai vectơ bất kỳ x,y  ta sử dụng kí hiệu sau đây 34 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên int x y y x int         . Để nhận đƣợc quy tắc nhân tử Lagrange, ta cần dạng không thuần nhất của định lý luân phiên Motzkin (xem [6]) sau. Bổ đề 2.1 (Định lý Motzkin không thuần nhất) Giả sử n j i ia ,b ,c  và j i i, ,    với j J ,i I    , và 0i I (các tập chỉ số hữu hạn). Khi đó, hệ sau ( nx là ẩn số): j j i i 0 i i , , a x 0, j J , b x 0,i I c x 0,i I                   (2.1) không tương thích khi và chỉ khi hệ sau (các ẩn j i i, ,  ) tương thích   0 0 j j i i i i j J i I i I i j i i i i 0 j J i I i I j0 j J j i , , , . a b c 0 0 0, j J 0 , 0,i I                                                       (2.2) Hơn nữa, nếu các hàng của (2.1) là độc lập tuyến tính thì tất cả các nghiệm của (2.2) có 0 0 . Chứng minh Do tính không tƣơng thích của (2.1) là tƣơng đƣơng với tính không t