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

ó, hàm ( x ) là tuyến tính trên mỗi đoạn   2k 1 k k kx ,x , ( x ) x  và đƣờng thẳng đi qua các điểm k k( x , ( x )) và   k 1 k 1x , x  là tiếp xúc với đƣờng cong 2y 2x . Nhƣ vậy với điểm kx 0 , xét đƣờng thẳng đi qua điểm 2 k k( x ,x ) và tiếp xúc với đƣờng cong 2y 2x . Đƣờng thẳng này giao với đƣờng cong 2y x tại điểm k 1x  rõ ràng k k 1x x 0  , và có kx 0 . Đặt  2K : ( x,y ) : y ( x )  R . Khi đó với phƣơng d : (1,0 ) ta có   2KT (0,d ) x,y : y 4  ,  2KO (0,d ) ( x,y ) : y 2  . Với mỗi R , '' (0;1, )=2  và '' +(0;1, )=4  và do đó (.) là không khả vi theo phƣơng cấp hai tại điểm 0 . Ta nói rằng tập K là khả vi theo phƣơng cấp hai tại y K theo phƣơng d , nếu 2 2 K KT ( y,d ) O ( y,d ) . Mệnh đề 1.1 Giả sử tập K được xác định như sau  K y Y : h( y ) 0   , 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên trong đó  h :Y   R là hàm lồi chính thường. Giả sử h( y ) 0 ,  h y,d 0  , và giả sử rằng tồn tại y sao cho h( y ) 0 (điều kiện Slater). Khi đó,  2KO ( y,d ) : h ( y;d , ) 0   . (1.8) Nếu giả thiết thêm h(.) là liên tục tại y, thì  2 ''K +T ( y,d ) : h ( y;d , ) 0   . (1.9) Chứng minh Ta chỉ chứng minh (1.8) đúng, còn chứng minh (1.9) là tƣơng tự. Xét 2 KO ( y,d ) và chọn dãy n nt 0 ,   sao cho 2 n n n 1 y t d t K 2    , và do đó, 2 n n n 1 h( y t d t ) 0 2    . Khi đó, 2 n n n n 2 n 1 h( y t d t ) 2h ( y ;d , ) liminf 0 1 t 2       . Ngƣợc lại, giả sử h ( y ;d , )<0 . Khi đó, với nt 0  và n  nào đó, ta có 2 2 2 n n n n n 1 1 h( y t d t ) t h ( y ;d , ) + o(t ) 2 2    . 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Do đó, 2 n n n 1 h( y t d t ) 0 2    với n đủ lớn. Vì vậy, 2 n n n 1 y t d t K 2    . Từ đó suy ra 2 KO ( y,d ) . Bây giờ giả sử h ( y;d , )=0 , và do đó tồn tại nt 0  và n  sao cho 2 2 n n n n 1 h( y t d t ) o( t ) 2    . Lấy '0, Y   . Đặt ' ': ( y y )     . Do tính lồi của h , với 't 0 đủ nhỏ ta có 2'11 t 0 2   và       2 2 2' ' ' ' ' ' '1 1 1h( y t d t ) (1 t ) ( t , ) t h y 2 2 2     , (1.10) trong đó 2 2 2' ' ' ' 1 ' ' 11 1 1( t , ) : h( y t ( 1 t ) d t ( 1 t ) ) 2 2 2          . Đặt:   21' ' 1t (1 t ) t , n n n2  tức là n n 2 n 2t t' (1 1 2 t )    , và   2' ' n n n 1 (1 t ) 2    . Khi đó, ' ' 2 2 n n n n n n 1 ( t , ) h( y t d t ) ( t ) 2       . 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bởi vì ' ' n nt 0 , ( y y )       và h( y ) 0 , từ (1.10) ta suy ra với mọi 0  , h ( y;d , ) h( y ) 0    . Vì vậy, 2 KO ( y,d )  . Vì 2 KO ( y,d ) đóng, cho 0  ta nhận đƣợc 2 KO ( y,d ) . Do đó (1.8) đƣợc chứng minh. Nếu h(.) là lồi và liên tục tại y , thì các đạo hàm cấp hai ''h ( y,d ,.),h ( y,d ,.)  là nhƣ nhau. Khi đó, từ mệnh đề trên, với điều kiện Slater, ta suy ra K là khả vi theo phƣơng cấp hai tại điểm y theo phƣơng d khi và chỉ khi các tập mức  '': h ( y ;d , ) 0   và  '': h ( y ;d , ) 0   trùng nhau. Đặc biệt, K là khả vi theo phƣơng cấp hai nếu h(.) là khả vi theo hƣớng cấp hai. Mệnh đề 1.2 Với mọi Ky K,d T ( y )  , ta có K T ( y )K 2 2 K T ( y ) KT ( y,d ) T ( d ) T ( y,d ) T ( d )   , (1.11) K K 2 2 K T ( y ) K T ( y )O ( y,d ) T ( d ) O ( y,d ) T ( d )   . (1.12) Nhắc lại [5] rằng tập A X lồi khác  đƣợc gọi là lùi xa theo phƣơng 0d  , nếu   0A d A     . Tập các vectơ d X thoả mãn   0A d A     và vectơ d = 0 đƣợc gọi là nón lùi xa của A. 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Từ mệnh đề trên ta suy ra K ( y )T T ( d ) là nón lùi xa của 2 KT ( y,d ) và  2KO y,d khi mà các tập hợp này khác rỗng. Hơn nữa, nếu 2 K0 O ( y,d ) , thì  K 2 K T ( y )O ( y,d ) T ( d ) và khi 2 K0 T ( y,d ) thì ba tập này trùng nhau: K 2 2 K K T ( y )T ( y,d ) O ( y,d ) T ( d )  . Chú ý rằng    KT ( y ) K T ( d ) cl T ( y ) d  , trong đó  Kd T y ; KT ( y ) T ( d ) là rỗng, nếu  Kd T y . Theo công thức (1.14) và (1.15) dƣới đây cho ta một quy tắc để tính các xấp xỉ tiếp tuyến cấp hai của tập chấp nhận đƣợc 1: G ( K )  của ( P ) dƣới ngôn ngữ xấp xỉ tiếp tuyến cấp hai của K . Công thức này đúng với điều kiện chính quy Robinson:  0 00 int G(x ) DG( x )X K   . (1.13) Mệnh đề 1.3 ([3]) Lấy 1 0x : G ( K )   và giả sử điều kiện chính quy Robinson (1.13) đúng. Khi đó, với mọi h X , 2 1 2 2 0 0 K 0 0 0T ( x ,h ) DG( x ) T ( G( x ),DG( x )h ) D G( x )( h,h )      , (1.14) 2 1 2 2 0 0 K 0 0 0O ( x ,h ) DG( x ) O ( G( x ),DG( x )h ) D G( x )( h,h )      . (1.15) 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1.3. ĐIỀU KIỆN CHÍNH QUY CẤP HAI VÀ ĐIỀU KIỆN TỐI ƢU CẤP HAI Phần này trình bày các điều kiện tối ƣu cấp hai cần và đủ cho bài toán ( P ) . Với bài toán ( P ) , ta định nghĩa hàm Lagrange nhƣ sau:    *L( x, ) : f ( x ) ,G( x ) , Y  . Hàm Lagrangian suy rộng đƣợc định nghĩa nhƣ sau:    * *L ( x, , ) : f ( x ) ,G( x ) , ( , ) Y      R. Giả sử 0x là nghiệm tối ƣu địa phƣơng của bài toán ( P ) . Khi đó, các điều kiện tối ƣu kiểu cấp một Fritz John có dạng: tồn tại *( , ) Y ,( , ) (0,0 )     R sao cho * x 0 K 0D L ( x , , ) 0, 0, N (G( x )).      (1.16) Ở đây    * * *KN ( y ) : y Y : y ,z y 0 , với mọi z K là nón pháp tuyến của K tại y . Kí hiệu * 0( x ) là tập hợp các nhân tử Lagrang 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ƣơng tích của hệ tuyến tính thuần nhất 35 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên                    j j i i 0 i i , , a x z 0, j J , 0x z 0, b x z 0,i I c x z 0,i I    cho nên ta nhận đƣợc kết quả bằng cách áp dụng định lý luân phiên Motzkin.  Nhận xét 2.1 Từ bổ đề 2.1 ta suy ra rằng tính không tƣơng thích của (2.1) kéo theo tính tƣơng thích của hệ sau: 0 0 0 i j i i i i j J i I i I i j i i i i j J i I i I 2 j i i j J i I i I j i , . a b c 0, 0, 0 0, j J , 0,i I                                                           \ (2.3) Giả sử n 1 l ( ,..., ):      là hàm khả vi hai lần, J : {1,..., }  là tập chỉ số mà nó ứng với các thành phần của  và nx . Ta đặt jJ( x ): { j J : ( x ) 0 }   . Ta đƣa vào các định nghĩa sau:  Tập các phƣơng giảm của  tại x là        n jD ( ,x ): { d : ( x )d 0, j J( x )};   Tập các phƣơng đạt đƣợc của  tại x là        n jD ( ,x ): { d : ( x )d 0, j J( x )};  36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Với mỗi phƣơng nd ta đặt jJ( x,d ): { j J( x ): ( x )d 0 }   . Ta đƣa vào các định nghĩa:  Tập các phƣơng giảm chặt cấp 2 của  tại x theo phƣơng nd là         2 n 2 j jD ( ,x,d ): { : ( x ) ( x )( d ,d ) 0, j J( x,d )};      Tập các phƣơng giảm cấp 2 của  tại x theo phƣơng nd là        2 n 2j jD ( ,x,d ): { : ( x ) ( x )( d ,d ) 0, j J( x,d )};      Tập các phƣơng đạt đƣợc cấp 2 của  tại x theo phƣơng nd là 2 n 2 j jD ( ,x,d ): { : ( x ) ( x )( d ,d ) 0, j J( x,d )},            trong đó kí hiệu  chỉ đạo hàm cấp 1, 2 chỉ đạo hàm cấp 2. Lấy n 1 l f ( f ,..., f ):    là hàm khả vi hai lần, .....J : {1, ,l}  và nS  . Xét bài toán đa mục tiêu dƣới đây:   int min f ( x ), x S ,  (2.4) trong đó int min   là cực tiểu vectơ theo nón  int : Sx  là cực tiểu vectơ địa phƣơng của (2.4) nếu tồn tại một lân cận N của x , sao cho không tồn tại  x S N thỏa mãn int f ( x ) f ( x )    . Điểm cực tiểu địa phƣơng loại này cũng đƣợc gọi là cực tiểu yếu địa phƣơng. 37 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Để đơn giản, ta sẽ viết D ( f ,x ) thay cho  D ( f f ( x ),x ) và kí hiệu tƣơng tự cho các tập khác. Định nghĩa 2.1 Cho nS   . Tập tiếp liên cấp 2 của S tại x  clS theo phương nd là 2 n 1 2 n n n n nT ( S,x,d ) : { : { } , {t } 0 sao cho x t d 2 t S }.             Tập tiếp liên cấp 2 là một mở rộng của nón tiếp tuyến Bouligand T( S,x ) và nó có một số tính chất. Chẳng hạn, nó là đóng và isotone, tức là Nếu 1 2 1S S và x clS  thì 2 21 2T ( S ,x,d ) T ( S ,x,d ) . Hơn nữa, ta có 2T ( S ,x,0 ) T( S ,x ) . và   2d T( S,x ) T ( S ,x,d ) . (2.5) Về các tính chất khác của loại xấp xỉ này, có thể xem trong [2]. 2.2. ĐIỀU KIỆN CẦN TỐI ƢU CHO BÀI TOÁN ĐA MỤC TIÊU VỚI RÀNG BUỘC TẬP Bằng kĩ thuật tuyến tính hoá với độ chính xác cấp hai ta có kết quả dƣới đây. Định lí 2.1 Nếu x S là cực tiểu yếu địa phương của (2.4) thì với mỗi phương giảm d D ( f ,x ) hệ sau đây không có nghiệm  2T ( S,x,d ) : 38 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 j jf ( x ) f ( x )( d ,d ) 0, j J( x,d )   . (2.6) Chứng minh Ngƣợc lại, giả sử d D ( f ,x ) cho trƣớc và  2T ( S,x,d ) là nghiệm của (2.6). Theo định nghĩa của tập tiếp liên cấp hai tồn tại n n{t } 0 và { }   sao cho      1 2n n n nx x t d 2 t S , n N. Do jf khả vi hai lần, ta có    -1j n j n j n nf ( x ) - f ( x ) t [ f ( x )( d 2 t )     -1 2 -1 -1n j n n n n n n2 t f ( x )( d 2 t ,d 2 t ) t ]  , trong đó n 0  khi n . Ta xét hai trƣờng hợp sau đây  Nếu j J( x,d ) , ta có 1 2 j n nf ( x )( d 2 t ) 0   , và do đó với n đủ lớn ta có j n jf ( x ) f ( x )  Nếu j J( x,d ) , ta có 2 1 1 j n j n n n n n n lim f ( x ) f ( x )( d 2 t ,d 2 t )             2j jf ( x ) + f ( x )( d ,d ) 0 . 39 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Cho nên với n đủ lớn ta có   1 2j n j n j nf ( x ) f ( x ) 2 t [ f ( x )     2 1 1j n n n n nf ( x )( d 2 t ,d 2 t ) ]<0  . Do đó, n N  , sao cho    n intf ( x ) f ( x ), n n . Điều này mâu thuẫn với giả thiết. Ta chú ý rằng, khi 1 , định lí 2.1 quy về điều kiện cần tối ƣu cấp hai trong [7]. Trong trƣờng hợp d 0 , ta có kết quả sau. Hệ quả 2.1.1 Nếu x S là vectơ cực tiểu yếu địa phương của (2.4) thì hệ sau đây không có nghiệm T( S ,x ) :  jf ( x ) <0, j J . (2.7) Khi thay 2 T (S,x,d) bằng 2 clconvT (S,x,d) thì tính tƣơng thích của hệ (2.6) không đúng nữa nhƣ trong ví dụ sau đây. Ví dụ 2.1 Xét bài toán đa mục tiêu (2.4)với 2 2 1 2 1 2 2 1f ( x ,x ): ( x x ,x x )    , và cho tập chấp nhận đƣợc cho bởi    2 4 2 41 1S : {x : x x 4x } . 40 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ta có x (0,0 ) là một điểm cực tiểu yếu. Hơn nữa, với phƣơng  d (1,0 ) D ( f ,x ) , tập tiếp liên cấp hai là    2 2 2T ( S ,x,d ) { : 2 4 } . Hệ (2.6) trở thành 2 2  . Do đó, nó không có nghiệm  2T ( S,x,d ) theo định lý 2.1. Nhƣng (2.6) có một nghiệm  2cl convT (S,x,d ) bởi vì   2 2 2cl convT (S,x,d ) { : 4 } . Để nhận đƣợc tính không tƣơng thích của hệ (2.6) với  2cl convT (S,x,d ) ta có thể xét dạng lồi suy rộng sau đây của bài toán (2.4). Định nghĩa 2.2 Cho tập nS   , hàm f : S  là subconvexlike trên S nếu mọi 1 2x ,x S ,  t 0,1 và   int 0  ,  3x S sao cho l1 2 3 int R tf ( x ) (1 t ) f ( x ) f ( x ) 0.       Định lý 2.2 Giả sử f là subconvexlike trên S. Nếu x S là cực tiểu yếu địa phương của (2.4) thì với mỗi phương giảm d D ( f ,x ) hệ (2.6) không có nghiệm  2cl convT (S,x,d ) . Chứng minh Giả sử ngƣợc lại tồn tại d D ( f ,x ) và  2cl convT (S,x,d ) sao cho (2.6) đúng. Từ (2.5) suy ra d T( S,x ) .Theo định lý 3.1 [9], tồn tại số  41 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên khác không   sao cho x là cực tiểu địa phƣơng của bài toán vô hƣớng sau j j j J f ( x ),min ( x ): x S.      Theo hệ quả 3.1 [7], ta có ( x )d 0, d T( X ,x )   ; (2.8) Và nếu ( x )d 0  , thì     2 2( x ) + ( x )( d ,d ) 0, cl convT ( S ,x,d )   . (2.9) Chọn d d , (2.8) kéo theo j 0  với mỗi j T( x,d ) . Khi đó  mâu thuẫn với (2.9). 2.3. ĐIỀU KIỆN CẦN TỐI ƢU FRITZ JOHN Phần này chúng ta xét tập chấp nhận đƣợc S đƣợc xác định bởi các ràng buộc bất đẳng thức và đẳng thức. Giả sử n p 1 pg ( g ,...,g ) :   và n q 1 qh ( h ,...,h ) :   là hàm khả vi hai lần, và lấy I : {1,..., p }  và 0I : {1,...,q } là các tập chỉ số tƣơng ứng. Giả sử rằng miền chấp nhận đƣợc của bài toán (2.4) đƣợc xác định bởi  g hS : S S , trong đó n g iS : {x : g ( x ) 0,i I }     , n 0 h iS : {x : h ( x ) 0,i I }    . Ta đƣa vào các tập hợp sau: 42 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  Tập các phương giảm tại x của bài toán (2.4):     D( x ): D ( f ,x ) D ( g,x ) D ( h,x ) ;  Tập tuyến tính hóa cấp hai yếu của S tại x theo phương nd  :     2 2 2L ( x,d ) : D ( g,x,d ) D ( h,x,d );  Tập tuyến tính hóa cấp hai của S tại x theo phương nd  :     2 2 2L ( x,d ) : D ( g,x,d ) D ( h,x,d ) . Để nhận đƣợc điều kiện cần tối ƣu cấp hai của bài toán (2.4), ta trình bày kết quả liên hệ các tập tuyến tính hóa cấp hai của S và tập tiếp liên cấp hai của S. Bổ đề 2.2 Giả sử x S và   d D ( g,x ) D ( h,x ) . Khi đó,  2 2T ( S,x,d ) L ( x,d ) . (2.10) Nếu i i I{ h ( x )} là độc lập tuyến tính thì   2 2L ( x,d ) T ( S ,x,d ) . (2.11) Chứng minh Cho  2T ( S,x,d ) , tồn tại n{t } 0 và n{ }  sao cho      1 2n n n nx x t d 2 t S , n N. Bởi vì ig và ih là khả vi hai lần, ta có      1i n i n i n n0 g ( x ) g ( x ) t g ( x )( d 2 t ) 43 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên          1 2 2 1 1 2n i n n n n n n2 t g ( x )( d 2 t ,d 2 t ) t , i I   ; (2.12) 1 i n i n i n n0=h ( x ) h ( x ) t h ( x )( d 2 t )             1 2 2 1 1 2 0n i n n n n n n2 t h ( x )( d 2 t ,d 2 t ) t , i I  . (2.13) Do đó, với mỗi i I ( x,d ) , chia (3.12) cho 1 2 n2 t  , ta có 2 1 1 i n i n n n n n0 g ( x ) g ( x )( d 2 t ,d 2 t ) 2        . Cho n , ta nhận đƣợc  2D ( g,x,d ) . Với mỗi  0i I , chia (2.13) cho nt và qua giới hạn, ta nhận đƣợc ih ( x )d 0  . Bây giờ chia cho 1 n2 t  ta nhận đƣợc 2 1 1 i n i n n n n n0= h ( x ) h ( x )( d 2 t ,d 2 t ) 2        . Cho n ta nhận đƣợc  2D ( h,x,d ) . Vì vậy ta suy ra (2.10). Chứng minh phần thứ hai: Theo định lý 3.5 [10],   2 2 hD ( h,x,d ) T ( S ,x,d ) . Do đó, với mỗi  2L ( x,d ) tồn tại n{t } 0 và n{ }  sao cho 1 2 n: 2 ,      n n n hx x t d t S n N. Ta chỉ cần chỉ rằng n gx S với mọi n đủ lớn. Với mỗi i I( x ) , tính liên tục của ig kéo theo i ng ( x ) 0 . Với mỗi i I( x )\ I ( x,d ) , ta có 1 i n n i n n ng ( x ) t [ g ( x )( d 2 t ) ]<0    . Với mỗi i I ( x,d ) , ta có 44 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 1 1 i n i n n n n n lim g ( x ) g ( x )( d 2 t ,d 2 t )         = 2 i ig ( x ) + g ( x )( d ,d ) 0  . Vì vậy, 1 2 2 1 1 i n n n( ) 2 [ g ( ) ( )( 2 , 2 ) ]<0i n n i n n ng x t x g x d t d t          . Do đó, (2.11) thỏa mãn. Định lý 2.3 Giả sử 0i i I { h ( x )}   là độc lập tuyến tính. Nếu x S là cực tiểu yếu địa phương của (2.4) thì với mỗi phương d D( x ) ,hệ sau đây là không tương thích (ẩn số n ):                2 j j 2 i i 2 0 i i f ( x ) + f ( x )( d ,d ) 0, j J( x,d ), g ( x ) + g ( x )( d ,d ) 0, i I ( x,d ), h ( x ) + h ( x )( d ,d ) 0, i I .    (2.14) Chứng minh Định lý đƣợc suy ra từ định lý 2.1 và bổ đề 2.2. Định lý 2.4 Nếu x S là cực tiểu yếu địa phương của (2.4), thì với mỗi phương giảm d D( x ) tồn tại p,     và q , không đồng thời bằng không, sao cho (i) 0 j j i i i i j J i I i I f ( x ) g ( x ) h ( x ) 0              ; (ii) 0 2 2 2 j j i i i i j J i I i I f ( x ) g ( x ) h ( x ) ( d ,d ) 0                    ; 45 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (iii) i ig ( x ) 0  với mỗi i I  ; (iv) j jf ( x )d 0   với mỗi j J và i ig ( x )d 0  với mỗi i I  . Chứng minh Nếu 0i i I { h ( x )}   là phụ thuộc tuyến tính, ta chọn j i 0   và i không đồng thời bằng không sao cho 0 i i i I h ( x ) 0    . Điều kiện (i), (iii) và (iv) thỏa mãn tầm thƣờng. Nếu (ii) không đúng, thì ta chỉ cần thay i i   . Trƣờng hợp     0i i Ih (x) là độc lập tuyến tính, ta áp dụng bổ đề 2.1 cho hệ (2.14) và lấy j i 0   với mọi j J( x,d ) và i I ( x,d ) . Chú ý rằng các định lý 2.3 và 2.4 bao hàm đƣợc điều kiện tối ƣu cấp 1 bằng cách lấy d 0 . 2.4. ĐIỀU KIỆN TỐI ƢU KUHN - TUCKER Quy tắc nhân tử Lagrange trong định lý 2.4 không đảm bảo ít nhất một nhân tử Lagrange ứng với hàm mục tiêu là khác không. Hiển nhiên là khi tất cả các nhân tử Lagrange tƣơng ứng với hàm mục tiêu bằng không, hàm mục tiêu không đóng vai trò gì trong điều kiện tối ƣu. Để khắc phục điều đó ta đƣa vào các giả thiết chính quy. Định nghĩa 2.3 Cho điểm chấp nhận được  nx  .  Điều kiện chính quy cấp hai Abadie(ASOCQ) đúng tại x theo phương nd  nếu: 46 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 2L ( x,d ) T ( S ,x,d )  ;  Điều kiện chính quy cấp hai Guignard (GSOCQ) đúng tại x theo phương nd  nếu:   2 2L ( x,d ) clconvT ( S ,x,d ) . Chú ý rằng (ASOCQ) và (GSOCQ) trở thành các điều kiện chính quy Abadie và Guignard đã biết khi lấy d 0 . Hiển nhiên là nếu (ASOCQ) đúng thì (GSOCQ) cũng đúng. Chiều ngƣợc lại không đúng nhƣ đã biết với d=0. Kết quả dƣới đây suy ra trực tiếp từ định lý 2.1. Định lý 2.5 Giả sử (ASOCQ) đúng tại x S theo phương giảm d D( x ) . Nếu x là cực tiểu yếu địa phương của (2.4) thì hệ sau đây (ẩn số nR ) không tương thích: 2 j j 2 i i 2 0 i i f ( x ) f ( x )( d ,d ) 0, j J( x,d ), g ( x ) g ( x )( d ,d ) 0, i I ( x,d ), h ( x ) + h ( x )( d ,d ) 0, i I .                (2.15) Ví dụ 2.2 Xét bài toán đa mục tiêu với 2 2 1 2 3 1 2 3 1 2 1 2 3 1 2 3 3 1 2 3 1 2 f ( x ,x ,x ) : ( x ,x ,x x x ), g( x ,x ,x ) : x x x x , h( x ,x ,x ) : x x .          Ta có x (0,0,0 ) là cực tiểu yếu. Tập các phƣơng giảm là 47 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  3 1 2 3D( x ) d : d 0,d 0,d 0    R Với các phƣơng d nhƣ vậy ta có   1 22 3 3 1 2 , d d 0, L ( x,d ) : 0 , d d 0;         R   1 22 3 i 3 i , n u d d 0, T ( S ,x,d ) : 0, 0 , n u d 0,i 1,2.            R Õ Õ Nhƣ vậy (ASOCQ) chỉ đúng với các phƣơng giảm d mà 1 2d d 0 , và nhƣ vậy định lý 3.1 trong [1] không thể áp dụng đƣợc. Với các phƣơng giảm d 0 khác thì hệ (2.15) có nghiệm =(-1,-1,0) . Từ định lý 2.5 ta nhận đƣợc quy tắc nhân tử Kuhn-Tucker sau đây. Định lý 2.6 Giả sử (ASOCQ) đúng tại x S theo phương giảm d D( x ) . Nếu x là cực tiểu yếu địa phương của (2.4) thì tồn tại p q, ,     R R R với 0  sao cho ( i ) ( iv) của định lý 2.4 đúng. Chứng minh Định lý đƣợc suy ra trực tiếp từ bổ đề 2.1 áp dụng cho hệ (2.15) với j 0  và i 0 với mọi j J( x,d )   và i I ( x,d )   .  Định lý 2.7 Giả sử (GSOCQ) đúng tại x S theo phương giảm d D( x ) và f là subconvexlike trên S. Nếu x là cực tiểu yếu địa phương của (2.4), thì tồn tại   ,   R R và q ¡ với 0  sao cho ( i ) ( iv ) của định lý 2.4 đúng. nếu nếu 48 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chứng minh Định lý trên đƣợc suy trực tiếp từ bổ đề 2.1 và định lý 2.2.  Trong các định lý trƣớc, các điều kiện chính quy kéo theo nhân tử Lagrange 0  . Bây giờ ta nghiên cứu điều kiện chính quy đảm bảo tất cả các nhân tử Lagrange ứng với các thành phần của hàm mục tiêu là dƣơng. Ta đƣa vào tập các phƣơng giảm cấp hai tại x của bài toán (2.4) theo nd R : 2 2 2 2D ( x,d ) : D ( f ,x,d ) D ( g,x,d ) D ( h,x,d )     . Ta có 2D ( x,0 ) D( x ) . Định nghĩa 2.4 Cho điểm chấp nhận được x S . Điều kiện chính quy cấp hai (GSORC) đúng tại x theo phương nd R nếu 2 2 s s 1 D ( x,d ) clconvT ( S ,x,d )    , trong đó     s j jS : x S : f ( x ) f ( x ) 0, j J \ s x .       Định lý 2.8 Giả sử (GSORC) đúng tại x S theo phương giảm d D( x ) . Nếu x là cực tiểu yếu địa phương của (2.4), thì với mỗi s J( x,d ) , hệ tuyến tính sau đây (ẩn số nR ): 49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên   2 s s 2 j j 2 i i 2 0 i i f ( x ) + f ( x )( d ,d ) 0, f ( x ) + f ( x )( d ,d ) 0, j J( x,d )\ s , g ( x ) + g ( x )( d ,d ) 0, i I ( x,d ), h ( x ) + h ( x )( d ,d ) 0, i I ,                        không tương thích. Chứng minh Giả sử ngƣợc lại,  là nghiệm của hệ trên với S nào đó  J( x,d ) . Nhƣ vậy (GSORC) kéo theo 2 sclconvT ( S ,x,d ) . Từ định nghĩa của cực tiểu địa phƣơng, ta suy ra x cũng là cực tiểu địa phƣơng của bài toán vô hƣớng:  s s minf ( x ), x S Theo hệ quả 3.1 trong [7] ta nhận đƣợc mâu thuẫn: 2 s sf ( x ) + f ( x )( d ,d ) 0  .  Định lý 2.8 dẫn tới quy tắc nhân tử Kuhn-Jucker sau đây. Định lý 2.9 Giả sử (GSORC) đúng tại x S theo phương giảm d D( x ) . Nếu x là cực tiểu yếu địa phương của (2.4), thì tồn tại    p, , R R và  ¡ q với j 0  với mọi j J( x,d ) sao cho ( i ) ( iv ) của định lý 2.4 đúng. Chứng minh 50 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Định lý suy trực tiếp từ bồ đề 2.1 áp dụng cho mỗi hệ tuyến tính của định lý 2.8 (đặt j 0  và i 0  với mọi j J( x,d ) và i I ( x,d ) ) và cộng các nhân tử nhận đƣợc lại.  KẾT LUẬN Luận văn đã trình bày phƣơng pháp nghiên cứu các điều kiện tối ƣu cấp 2 cho các bài toán tối ƣu đơn mục tiêu và đa mục tiêu dựa trên các xấp xỉ cấp 2 cho các tập và các hàm. Các tập tiếp tuyến hoặc tiếp liên cấp 2 và các tập tuyến tính hoá cấp 2 tỏ ra rất hiệu quả trong việc thiết lập các điều kiện chính quy cấp 2 để dẫn các điều kiện cần tối ƣu cấp 2 Kuhn-Tucker. Việc nghiên cứu các điều kiện tối ƣu cấp 2 và cấp cao cho các bài toán tối ƣu đa mục tiêu là một đề tài đang đƣợc quan tâm nghiên cứu phát triển tiếp tục. 51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO [1] B. Aghezzaf and M. Hachimi, Second-order optimality conditions in multiobjective optimization problems, Journal of Optimization Theory and Applications 102 (1999), 37-50. [2] J.P. Aubin and H. Frankknowzka, Set-valued analysis. Borkhauser, Boston (1990). [3] J. F Bonnans, R. Cominetti and A. Shapiro, Second order optimality conditions based on parabplic second order tangent sets, SIAM J. Optim. 9 (1999), 466- 492. 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên [4] G. Bigi and M. Castellani, Second order optimality conditions for differentiable multiobjective problems, RAIRO Oper. Res. 34 (2000), No 4, 411- 426. [5] Đ. V. Lƣu và P. H. Khải, Giải tích lồi, Nhà xuất bản KHKT, Hà Nội, 2000. [6] O. L. Mangasarian, Nonlinear programming, Mc Graw- Hill, New York (1969). [7] J. P. Penot, Optimality conditions in mathematical programming and composite optimization, Math. Programming 67 (1994), 225-245. [8] S. M. Robinson, First order conditions for general nonlinear optimization, SIAM J. Appl. Math. 30 (1976), 597-607. [9] S. M. Wang and Z. F. Li, Scalarization and Lagrange duality in multiobjective optimization, Optimization 26 (1992), 315-324. [10] D. E. Ward, A chain rule for parabolic second- order epiderivatives, Optimization 28 (1994), 223-236.