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

Chia sẻ: Carol123 Carol123 | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST

Báo xấu

120
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lý thuyết các điều kiện tối ƣu trong tối ƣu đơn mục tiêu và đa mục tiêu trơn và không trơn phát triển rất mạnh mẽ và thu đƣợc nhiều kết quả đẹp đẽ và phong phú. Lý thuyết các điều kiện tối ƣu cấp 2 là một bộ phận quan trọng của lý thuyết các điều kiện tối ƣu. Từ các điều kiện cần ta có đƣợc tập các điểm dừng mà trong đó bao hàm các nghiệm của bài toán tối ƣu. Các điều kiện đủ tối ƣu cấp 2 cho phép ta tìm ra nghiệm của bài toán đó. Thông thƣờng ngƣời ta...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM -----------------o0o------------------ NGUYỄN THỊ LAN ANH VỀ ĐIỀU KIỆN CHÍNH QUY CẤP HAI VÀ ĐIỀU KIỆN TỐI ƯU CẤP HAI LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM -----------------o0o------------------ NGUYỄN THỊ LAN ANH VỀ ĐIỀU KIỆN CHÍNH QUY CẤP HAI VÀ ĐIỀU KIỆN TỐI ƯU CẤP HAI Chuyên ngành: TOÁN GIẢI TÍCH Mã số: 60.46.01 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS.TS Đỗ Văn Lưu THÁI NGUYÊN - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỤC LỤC Trang 1 Mục lục......................................................... ......................................... Mở đầu................................................................................................... 2 Chƣơng 1 ĐIỀU KIỆN TỐI ƢU CẤP HAI CHO BÀI TOÁN TỐI ƢU ĐƠN MỤC TIÊU 1.1. Các khái niệm và định nghĩa.......................................................... 4 1.2. Các tập tiếp tuyến cấp một và cấp hai.............................................. 8 1.3. Điều kiện chính quy cấp hai và điều kiện tối ƣu cấp hai.................. 15 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 2.1. Kiến thức chuẩn bị........................................................................... 33 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... 37 2.3. Điều kiện cần tối ƣu Fritz John....................................................... 41 2.4. Điều kiện tối ƣu Kuhn-Tucker....................................................... 45 KẾT LUẬN............................................................................................ . 50 TÀI LIỆU THAM KHẢO ................................................................... ... 51 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỞ ĐẦU Lý thuyết các điều kiện tối ƣu trong tối ƣu đơn mục tiêu và đa mục tiêu trơn và không trơn phát triển rất mạnh mẽ và thu đƣợc nhiều kết quả đẹp đẽ và phong phú. Lý thuyết các điều kiện tối ƣu cấp 2 là một bộ phận quan trọng của lý thuyết các điều kiện tối ƣu. Từ các điều kiện cần ta có đƣợc tập các điểm dừng mà trong đó bao hàm các nghiệm của bài toán tối ƣu. Các điều kiện đủ tối ƣu cấp 2 cho phép ta tìm ra nghiệm của bài toán đó. Thông thƣờng ngƣời ta đƣa vào các tập tiếp tuyến cấp 2, các tập tuyến tính hoá cấp 2 và các điều kiện chính quy cấp 2 và từ đó dẫn tới các điều kiện tối ƣu cấp 2 kiểu Fritz John và Kuhn-Tucker. J. F. Bonnans, R. Cominetti và A. Shapiro [3] đã nghiên cứu các tập tiếp tuyến cấp 2 trong và ngoài, tập xấp xỉ cấp 2 trên, các khái niệm chính quy cấp 2 và chính quy cấp 2 ngoài. Từ đó, các tác giả đã thiết lập các điều kiện cần tối ƣu cấp 2 với điều kiện chính quy Robinson, và các điều kiện đủ tối ƣu cấp 2 cho bài toán tối ƣu đơn mục tiêu không trơn với ràng buộc nón. G. Bigi và M.Castellani [4] đã nghiên cứu tập các phƣơng giảm cấp 2. Tập các phƣơng chấp nhận đƣợc cấp 2 tập tiếp liên cấp 2 và các điều kiện chính quy cấp 2 kiểu Abadie và Guignard. Từ đó, các tác giả dẫn các điều kiện cần tối ƣu Fritz John cấp 2 trên cơ sở phát triển một định lý luân phiên kiểu Motzkin, và các điều kiện cần tối ƣu Kuhn-Tucker cấp 2 với các điều kiện chính quy cấp 2 kiểu Abadie và Guignard. Luận văn tập trung trình bày các điều kiện chính quy cấp 2 và các điều kiện tối ƣu cấp 2 dƣới ngôn ngữ tập tiếp tuyến cấp 2, tập tiếp liên cấp 2, tập tuyến tính hoá cấp 2 và các đạo hàm theo phƣơng cấp 2. Luận văn bao gồm phần mở đầu, hai chƣơng, kết luận và danh mục các tài liệu tham khảo. 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Chƣơng 1: Trình bày các nghiên cứu của J. F. Bonnans, R. Cominetti và A. Shapiro [3] về các tập tiếp tuyến cấp 2 trong và ngoài, tập xấp xỉ cấp 2 trên, điều kiện chính quy cấp 2 và điều kiện chính quy cấp 2 ngoài. Với điều kiện chính quy Robinson, các điều kiện cần tối ƣu cấp 2 cho bài toán tối ƣu với ràng buộc nón không trơn đƣợc trình bày cùng với các điều kiện đủ tối ƣu cấp 2. Chƣơng 2: Trình bày các kết quả nghiên cứu của G. Bigi và M.Castellani [4] về đ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 có ràng buộc trên cơ sở phát triển một định lý luân phiên Motzkin không thuần nhất. Các nghiên cứu về tập tiếp liên cấp 2, tập tuyến tính hoá cấp 2, các điều kiện chính quy cấp 2 kiểu Abadie và Guignard đƣợc trình bày cùng với các điều kiện cần cấp 2 Fritz John và Kuhn-Tucker. Nhân dịp này tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Đỗ Văn Lƣu, ngƣời đã tận tình hƣớng dẫn, giúp đỡ tôi hoàn thành bản luận văn này. Tôi xin chân thành cảm ơn Ban chủ nhiệm khoa Toán trƣờng Đại học sƣ phạm - Đại học Thái Nguyên cùng các thầy cô giáo đã tham gia giảng dạy khoá học, xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành viên trong lớp Cao học Toán K15 đã luôn quan tâm, động viên, giúp đỡ tôi trong suốt thời gian học tập và quá trình làm luận văn. Thái Nguyên, tháng 9 năm 2009 Nguyễn Thị Lan Anh 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
C hƣơng 1 ĐIỀU KIỆN TỐI ƢU CẤP HAI CHO BÀI TOÁN TỐI ƢU ĐƠN MỤC TIÊU Chƣơng 1 trình bày các nghiên cứu của J.F.Bonnans, R.Cominetti và A.Shapiro [3] về các tập tiếp tuyến cấp 2 trong và ngoài, tập xấp xỉ cấp 2 trên, điều kiện chính quy cấp 2 ngoài và điều kiện chính quy cấp 2 cùng với các điều kiện cần và đủ tối ƣu cấp 2 cho bài toán tối ƣu với ràng buộc nón. 1.1. C ÁC KHÁI NIỆM VÀ Đ ỊNH NGHĨA 1.1.1. Bài toán Ta xét bài toán tối ƣu có dạng min f(x), x X (P) G(x)  K, trong đó X là không gian hữu hạn chiều, Y là không gian Banach, K là một tập con lồi đóng của Y , hàm mục tiêu f : X  R và á nh xạ ràng buộc G : X  Y đƣợc giả thiết là khả vi liên tục hai lần. Kí hiệu  : G1 ( K ) là tập chấp nhận của bài toán ( P) . Một số bài toán tối ƣu có thể phát biểu dƣới dạng bài toán ( P) . Khi và K  0  R  q . Tập chấp nhận đƣợc của ( P) đ ƣợc xác định bởi Y  p p một s ố hữu hạn ràng buộc đẳng thức và bất đẳng thức , và ( P) trở thà nh bài toán quy hoạch phi tuyến. Ví dụ khác, ta xét không gian Y  C () gồm các hàm liên tục  :   ¡ xác định trên không gian metric compăc  trang bị chuẩn sup. 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
 : sup  (  ) .  Lấy K : C (  ) là nón của các hàm nhận g iá trị không âm, t ức là C (  ):   C(  ): (  )  0,   .  Trong trƣờng hợp này, ràng buộc G( x )  K tƣơng ứng với g ( x, )  0 với mọi    , tro ng đó g( x,.) : G( x )(.) . Nếu tập  là vô hạn, ta nhận đ ƣợc một số vô hạn các ràng buộc , và (P) trở thành bài toán q uy hoạch bán vô hạn . Một cách tiếp cận khác để nghiên cứu điều kiện tối ƣu là xét các bài toán tối ƣu có dạng min g( F( x )), (1.1) xX trong đó g : Y  R   là hàm lồi chính t hƣờng nửa liên tục dƣới và F : X  Y . Bài toán này tƣơng đ ƣơng với bài t oá n t ối ƣu sau (xem [7 ]): min c, (1.2) ( x ,c )X R ( F( x ),c ) epi( g ), trong đó epi( g ) : ( y,c ) Y  R : g( y )  c là t rên đồ thị của g và do đó nó đƣợc xét nhƣ một trƣờng hợp riêng của bài toán (P). Điều ngƣợc lại c ũng đúng, có nghĩa là bài toán ( P) có t hể biểu diễn dƣới dạng (1. 1) bằng cách lấy g( r, y )  r  I K ( y ) và F ( x )  ( f ( x ),G( x )) , trong đó I K ( y )  0 , nếu y  K và bằng  nếu y  K (xem [7]). C ho nên hai cách tiếp cận là tƣơng đƣơng. 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1.1.2. Các khái niệm và định nghĩa Giả sử h :Y  R     là hàm giá trị thực mở rộng. Giả sử h(.) là hữu hạn tại điểm y  Y ta kí hiệu h' ( y,d ) là đạo hàm t heo phƣơng của nó tại điểm y theo phƣơng d  Y h( y  td )  h( y ) h' ( y;d ) : lim . t 0 t N hắc lại [ 5] rằng nếu h(.) lồi, giá trị hữu hạn t ại y, chính t hƣờng t rê n Y, y  dom h t hì h' ( y;d ) tồn tại và hữu hạn. Ta cũng sử dụng đạo hàm theo phƣơng dƣới sau: h( y  td')  h( y ) h ( y;d )  liminf . t 0 t d ' d C hú ý rằng trên đồ thị của h ( y,.) đóng và h ( y,.) là hàm nửa liên t ục dƣới. Nếu h(.) là lồi, nhận giá trị hữu hạn và liên tục tại y và do đó là liên tục Lipschitz t rong một lân cận của y , thì h ( y,.)  h' ( y,.) . Nói c hung, nếu h là lồi, có thể gián đoạn, t hì bao đóng c ủa t rên đồ thị của h' ( y,.) trùng với trên đồ thị của h ( y,.) . Khi h' ( y,d ) tồn tại và là hữu hạn, ta kí hiệu h'' ( y ;d , ) và h' ( y ;d , ) là đạo hàm parabolic cấp hai trên và d ƣới [3 ], tƣơng ứng c ủa ' h t ức là 1 h( y  td  t 2 ) - h( y ) - th' ( y,d ) h'' ( y ;d , ) :  liminf 2 12 t 0 t 2 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1 h( y  td  t 2 )  h( y )  th' ( y,d ) h ( y ;d , ) : lim sup 2 '' 12 t 0 t 2 Ta nói rằng h(.) là k hả vi theo phƣơng cấp hai tại y theo phƣơng d, nếu h' ( y ;d , ) = h+( y ;d , ) và hữu hạn với mọi   Y . Trong trƣờng ' '' hợp này, giá trị chung đó đƣợc ký hiệu h ( y ;d , ) . Khi h( y ) và '' h ( y,d ) hữu hạn, đạo hàm parabolic cấp hai dƣới đƣợc định nghĩa nhƣ sau 1 h( y  td  t 2' )  h( y )  th ( y,d ) h ( y ;d , ) : liminf 2  12 t 0 , '  t 2 C hú ý rằng nếu là liên tục Lipschitz gần y, thì h(.) h ( y ;d , )  h' ( y ;d , ) . Nói riêng, đ iều này đúng, nếu h(.) lồi, hữu  ' hạn, và liên tục, và do đó là liên tục Lipschitz tại y. Kí hiệu Y * là không gian đ ối ngẫu của Y và y* , y giá trị y* ( y ) c ủa hàm tuyến tính y*  Y * tại y  Y . Với ánh xạ tuyến tính liên tục A: X Y A* : Y *  X * ta kí hiệu là ánh xạ liên hợp , tức là , A* y* ,x  y* ,Ax , với mọi x  X ,y* Y * . Với tập T  Y k í hiệu  (.,T ) là hàm tựa c ủa T, t ức là  ( y* ,T ) : sup y* , y . yT Ký hiệu dist  .,T  là hàm k hoảng cách dist  y,T  : inf y  z . zT 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Df ( x ),D2 f ( x ) t ƣơng ứng là đạo hàm cấp một và đạo hàm cấp hai f ( x ) ; BY :  y  Y : y  1 là hình cầu đơn vị trong Y ; c ủa hàm  y : ty : t  R là không gian tuyến tính sinh bởi vec tơ y (một chiều nếu y  0 ). 1.2. C ÁC TẬP T IẾP TUYẾN CẤP MỘT VÀ CẤP HAI G iả s ử K là tập con đóng của không gian Banach Y . Nón t iếp t uyến cấp 1 c ủa K tại điểm y  K đ ƣợc định nghĩa nhƣ sau: TK ( y ) :  h Y : dist(y + th, K) = o(t), t  0. (1.3) Nhắc lại [2] các khái niệm giới hạn trên và dƣới của hàm đa trị : X  2Y (t ừ k hô ng gian đ ịnh c huẩn X vào họ các tập con c ủa Y) theo nghĩa Painlevé - Kuratowski: lim sup   x   y  Y : x n  x 0 sao cho yn   x n  , yn  y, x  x0 liminf   x   y  Y : x n  x 0 , yn   x n  , yn  y. x  x0 Theo đ ịnh nghĩa của giới hạn tập hợp dƣới , ta có thể viết Ky TK  y   liminf . (1.4) t 0 t Ta biết rằng khi K là lồi t hì c ũng có Ky TK ( y )  lim sup . ( 1.5) t 0 t C hú ý rằng nếu K là nón lồi và y  K , thì TK ( y )  cl  K   y  , trong   đó  y  k ý hiệu không gian tuyế n tính sinh bởi vec tơ y và cl k ý hiệu bao đóng theo t ôpô c huẩn của Y . 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Tƣơng tự (1.4) và (1.5 ), ta xét biến phân cấp hai của tập K tại điểm y  K t heo phƣơng d K - y - td TK2 ( y,d ) : liminf , (1.6) 12 t 0 t 2 K  y  td OK ( y,d ) : lim sup 2 . (1.7) 12 t 0 t 2 Ta gọi TK ( y,d ),OK ( y,d ) t ƣơ ng ứng là các tập tiếp tuyến cấp hai 2 2 trong và ngoài. Các tập tiếp tuyến này có thể viết dƣới dạng sau:   1 TK2 ( y,d )    Y: dist (y+td+ t 2 , ) = o(t 2 ),t  0  ,   2  2 12 OK ( y,d )  : tn  0 : dist (y+tn d+ tn  ,K) = o(tn ) . 2   2 Từ định nghĩa t rê n ta thấy rằng TK ( y,d )  OK ( y,d ) , và các tập tiếp 2 2 d TK ( y ) . Cả hai tập t uyến cấp hai này khác rỗng chỉ nếu TK ( y,d ),OK ( y,d ) đóng. Nếu K lồi, thì tập TK ( y,d ) lồi; Tập tiếp tuyến 2 2 2 cấp hai ngoài OK ( y,d ) có thể không lồi. 2 V í dụ dƣới đây chứng minh rằng không giống nhƣ c ác nón t iếp tuyến cấp một, các tập tiếp tuyến cấp hai trong và ngoài có thể khác nhau. Ví dụ 1.1 Ta xây dựng một hàm tuyến tính từng khúc lồi y   ( x ),x  R , dao động giữa hai p arabol y  x2 và y  2x2 . Ta xây dựng  ( x ) t hoả mãn: 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
( x )  (  x ), ( 0 )  0, và với dãy đơ n đ iệu giảm đến k hông xk nào đó, hàm  ( x ) là tuyến tính  xk 1 ,xk  ,( xk )  xk2 trên mỗi đ oạn và đƣờng thẳng đi qua các điểm ( xk ,( xk )) và  xk 1 ,  xk 1   là tiếp xúc với đƣờng cong y  2x2 . N hƣ vậy với đ iểm xk  0 , xét đƣờng thẳng đi qua điểm ( xk ,xk ) và 2 t iếp xúc với đƣờng cong y  2x2 . Đƣờng thẳng này giao với đƣờng cong y  x2 tại điểm xk 1 rõ ràng xk  xk 1  0 , và có xk  0 . Đặt K : ( x, y )  R 2 : y  ( x ) . Khi đó với phƣơng d : ( 1,0 ) ta có TK2 ( 0,d )   x, y  : y  4 , OK ( 0,d )  ( x, y ) : y  2 . 2 Với mỗi   R , ' ( 0;1, )=2 và +( 0;1, )=4 và do đó  (.) là ' '' k hông khả vi t heo 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 p hƣơng d , nếu TK ( y,d )  OK ( y,d ) . 2 2 M ệnh đề 1.1 Giả sử tập K được xác đ ịnh như sau K   y Y : h( y )  0 , 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
trong đó h :Y  R   l à hàm lồi chính thường. G iả 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 k iện Slater). Khi đó,   OK ( y,d )  : h ( y;d , )  0 .  2 (1.8) Nếu giả thiết thêm h(.) là liên tục tại y, thì TK2 ( y,d )  : h+( y;d , )  0 . '' (1.9) C hứng minh Ta chỉ c hứng minh (1.8) đúng, còn c hứng minh ( 1.9 ) là tƣơng tự. Xét   OK ( y,d ) và chọn dãy tn  0 ,n   sao cho 2 12 y  tn d  tn  n  K , và do đó, 2 12 h( y  tn d  tn n )  0 . 2 Khi đó, 12 h( y  tn d  tn n ) h ( y ;d , )  liminf 2  0. 12 n tn 2 N gƣợc lại, giả sử h ( y ;d , )
12 Do đó, h( y  tn d  tn n )  0 với n đủ lớn. 2 V ì vậy, 12 y  t n d  t n n  K . 2 Từ đó suy ra   OK ( y,d ) . 2 Bâ y giờ giả sử h ( y;d , )=0 , và do đ ó tồn tại tn  0  và n    sao cho 12 h( y  tn d  tn n )  o( tn ) . 2 2 Lấy   0,' Y . Đặt  : '   ( y  y ) . Do t ính lồi của h , với ' 12 t '  0 đ ủ nhỏ ta c ó 1   t'  0 và 2  12' 12 12 h( y  t' d  t'  )  ( 1   t' ) ( t ' ,' )   t ' h y , (1.10) 2 2 2 trong đó 1 1 '2 1 '2  ( t' ,' ) : h( y  t' ( 1  t' ) 1 d t ( 1  t ) 1 .   2 ) 2 2 2 Đặt : ' ( 1  1  t' 2 )1  t , tức là t'  1 '2 ' 2tn , và ( 1   tn )n  n . t n n 2n n ( 1  1  2 tn ) 2 2 Khi đó, 1  ( tn ,n )  h( y  tn d  tn n )   ( tn ) . ' ' 2 2 2 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Bởi vì tn  0  ,n   ( 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,   OK ( y,d ) . Vì OK ( y,d ) đóng, cho   0  ta nhận đ ƣợc 2 2   OK ( y,d ) . Do đó (1.8 ) đƣợc chứng minh. 2 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 ' S later, ta suy ra K là khả vi theo phƣơng cấp hai tại điểm y t heo phƣơng d k hi 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 t heo hƣớng cấp hai. M ệnh đề 1.2 Với mọi y  K ,d TK ( y ) , ta có TK2 ( y,d )  TTK ( y )( d )  TK2 ( y,d )  TT ( d ), (1.11) K(y) OK ( y,d )  TTK ( y )( d )  OK ( y,d )  TTK ( y )( d ) . 2 2 (1.12 ) N hắc lại [5 ] rằng tập A  X lồi k hác  đƣợc gọi là lùi xa theo p hƣơ ng d  0 , nếu A  d  A    0 . Tập các vectơ d  X t hoả mãn A  d  A    0 và vectơ d = 0 đ ƣợc gọi là nón lùi xa c ủa A. 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Từ mệnh đề trên ta suy ra TTK ( y ) ( d ) là nón lùi xa của TK ( y,d ) và 2 OK  y,d  k hi mà các tập hợp này khác rỗng. 2 OK ( y,d )  TTK ( y )( d ) 0  OK ( y,d ) , thì Hơn nữa, nếu 2 2 và khi 0 TK ( y,d ) t hì b a tập này trùng nhau : 2 TK2 ( y,d )  OK ( y,d )  TTK ( y )( d ) . 2 C hú ý rằng TTK ( y ) ( d )  cl TK ( y )   d  , trong đó d TK  y  ; TTK ( y )( d ) là rỗng, nếu d TK  y  . Theo công thức (1.14) và (1.15 ) d ƣới đâ y c ho 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  : G1( 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  int G(x0 )  DG( x0 )X  K . (1.13) M ệnh đề 1.3 ([3]) Lấy x0  : G 1( K ) và giả s ử điều kiện chính quy Robinson (1.13) đúng. Khi đó, với mọi h  X , T2 ( x0 ,h )  DG( x ) 1  T2 ( G( x ),DG( 0 )h  D G( 0x )( h,h ) ,  )2 x (1.14) K  0 0 O ( x0 ,h )  DG( x ) 1  O2 ( G( x ),DG( 0 )h  D G( 0x )( h,h ) .  2 )2 x (1.15) K  0 0 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1.3. ĐIỀU KIỆN CHÍNH QUY CẤP HAI VÀ ĐIỀU KIỆN TỐI ƢU CẤP HAI P hầ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 ) , (  , )  R  Y * . G iả sử x0 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 (  , )  R  Y * ,(  , )  (0,0 ) sao cho Dx L* ( x0 , , )  0,   0,  N K ( G( x0 )). (1.16)  Ở đây N K ( y ) : y*  Y * : y* ,z  y  0 , với mọi z  K là nón pháp t uyến của K tại y . Kí hiệu * ( x0 ) là tập hợp các nhân tử Lagrang suy rộng (  , )  ( 0,0 ) t hỏa mãn điều kiện ( 1.16). Chú ý rằng với không gian Banach Y tập hợp * ( x0 ) có thể rỗng. Đ iều kiện tối ƣu F ritz John ở trên là điều kiện cần cho nghiệm tối ƣu địa phƣơng, tức là * ( x0 )   . 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 k hi 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 Dx L( x0 , )  0,   N K ( G( x0 )) . (1.17) Với đ iều kiện chính quy Robinson ( 1.13 ), tập hợp ( x0 ) các nhân tử Lagra nge t hỏa mãn (1.17 ) là khác rỗng và bị chặn (xem [8 ] ). 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Khi tập K là một nón lồi và y  K , nón pháp tuyến N K ( y ) có dạng:   N K ( y )  y*  K  : y* , y  0 , 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   N K ( G( x0 )) trở thành   K  và  ,G( x0 )  0 . N hắc lại rằng: nón C( x0 ): h  X : DG( x0 )h TK ( G( x0 )),Df ( x0 )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 x0 . Nón này b iểu diễn các phƣơng tuyến tính hóa cấp một của ( P ) . C hú ý rằng khi tập ( x0 ) các nhân tử Lagrange k hác rỗng thì Df ( x0 )h  0 với mọi h  X t hỏa mãn DG( x0 )h TK ( G( x0 )) . Trong trƣờng hợp đó bất đẳng t hức Df ( x0 )h  0 , trong đ ịnh nghĩa của nón tới hạn có th ể thay bởi đẳng thức Df ( x0 )h  0 . Đ iều đó là tƣơng đƣơng với   ,DG( x0 )h  0 với mọi   ( x0 ) . Bâ y giờ ta có thể phát b iểu đ iều kiện cần tối ƣu cấp hai dựa trên sự p hân tích đƣờng cong c hấp nhận đ ƣợc parabol có dạng 1 x(t) = x0  th  t 2 + o(t 2 ) , (1.19 ) 2 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. 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Định lý 1.1 Giả sử x0 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 h  C( x0 ) và tập lồi bất kỳ T ( h )  OK ( G( x0 ),DG( x0 )h ) , 2 Sup Dxx L( x0 , )( h,h )   (  , T (h))  0 . 2 ( x0 ) (1.20) C hứng minh Chú ý rằng nếu T (h)=  t hì  (., T (h)) =   và (1.20 ) đ úng một cách tầm thƣờng. Ta giả sử T (h) và do đó tập OK ( G( x0 ),DG( x0 )h ) k hác rỗng. 2 Ta khẳng định rằng giá trị tối ƣu của b ài toán: Min Df ( x0 )+D2 f ( x0 )( h,h ) , (1.21) X DG( x 0 )+D2G( x0 )( h,h )  OK ( G( x0 ),DG( x0 )h ) 2 là không âm. Thật vậy, nếu  là đ iểm c hấp nhận đƣợc của bài toán này, sử dụng mệnh đề 1.3 ta nhận đ ƣợc   0 ( x0 ,h ) , trong đó:  : G1( K ) . Vì thế ta 2 1 có thể tìm đƣợc dãy tk  0 sao cho xk : x0  tk h  tk2 + o(t 2 )  . 2 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Dãy xk 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 x0 . Do đó, f ( xk )  f ( x0 ) với mọi k đủ lớn. Sử dụng khai triển Taylor cấp hai ta có 1 f ( x0 )  f ( xk )  f ( x0 )  tk Df ( x0 )h  t k2  Df ( x0 )+D 2 f ( x0 )( h,h )   ( t k2 ) . 2  Bởi vì Df ( x0 )h  0 , với bất kỳ h  C( x0 ) , ta nhận đ ƣợc Df ( x0 )+D2 f ( x0 )( h,h )  0 . N hƣ 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) TK ( G( x0 )) . 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 T( h )  OK ( G( x0 ),DG( x0 )h ) . 2 Rõ ràng nếu ta thay đổi các tập tiếp tuyến cấp hai ngoài trong ( 1.2 1 ) 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). D o đó, giá trị tối ƣu của bài toán: Min Df ( x0 )+D2 f ( x0 )( h,h ) , (1.22) X DG( x0 )+D2G( x0 )( 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à : Max Dxx L( x0 , )( h,h )   (  ,T( h )) 2 (1.23) (x0 ) Thậ t vậy, hàm Lagra nge c ủa (1.22) là 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn