Luận văn Cấu trúc tập nghiệm của bài toán bất đẳng thức biến phân Affine

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC NGUYỄN QUANG NGỌC CẤU TRÚC TẬP NGHIỆM CỦA BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE Chuyên ngành: Toán ứng dụng Mã số: 60. 46. 36 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS. TS. TẠ DUY PHƢỢNG Thái Nguyên - 2011 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 MỤC LỤC Trang Lời nói đầu........................................................................................................... Chƣơng 1 Bất đẳng thức biến phân.................................................................. §1 Bất đẳng thức biến phân và các bài toán liên quan......................................... 1.1 Bất đẳng thức biến phân........................................................................... 1.2 Bài toán tối ưu một mục tiêu.................................................................... 1.2.1 Tối ưu hàm một biến....................................................................... 1.2.2 Tối ưu hàm nhiều biến.................................................................... 1.3 Phương trình suy rộng.............................................................................. 1.3.1 Hệ phương trình (hệ phương trình trong n )................................ 1.3.2 Phương trình suy rộng.................................................................... 1.4 Bài toán bù............................................................................................... 1.5 Phép chiếu................................................................................................ 1.6 Điểm bất động.......................................................................................... §2 Tồn tại nghiệm của bài toán bất đẳng thức biến phân.................................... §3 Bất đẳng thức biến phân véctơ ....................................................................... §4 Tính liên thông của tập nghiệm trong bài toán bất đẳng thức biến phân véctơ................................................................................................................ Chƣơng 2 Bất đẳng thức biến phân affine........................................................ §1 Bất đẳng thức biến phân affine........................................................................ 1.1 Bất đẳng thức biến phân affine. 3-4 5 5 5 6 6 7 15 15 16 17 20 23 24 28 33 36 36 36 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 1.2 Bất đẳng thức biến phân véctơ affine... 1.3 Bất đẳng thức biến phân véctơ affine yếu..... 1.4 Bất đẳng thức biến phân affine phụ thuộc tham số.. §2 Tính bị chặn và tính liên thông của tập nghiệm và tập nghiệm yếu trong bài toán bất đẳng thức biến phân vectơ affine...... §3 Bài toán tối ưu đa mục tiêu phân thức tuyến tính và bài toán tối ưu đa mục tiêu toàn phương lồi................................................................................ 3.1 Bài toán tối ưu véctơ 3.2 Bài toán tối ưu vectơ phân thức tuyến tính (LFVOP)............................. 3.3 Bài toán tối ưu véctơ hàm toàn phương lồi (QVOP)... §4 Một số ví dụ tính tập nghiệm trong bài toán tối ưu đa mục tiêu phân thức tuyến tính........................................................................................................ 4.1 Thí dụ 1.... 4.2 Thí dụ 2 4.3 Thí dụ 3 4.4 Thí dụ 4 4.5 Thí dụ 5 4.6 Thí dụ 6 4.7 Thí dụ 7 Kết luận................................................................................................................ Tài liệu tham khảo.............................................................................................. 39 40 40 42 55 55 57 68 70 70 72 75 78 81 84 88 94 95 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 LỜI NÓI ĐẦU Bản thân bất đẳng thức biến phân là một đối tượng toán học được nghiên cứu độc lập. Hơn nữa, bất đẳng thức biến phân còn chứa đựng trong nó hoặc có liên quan đến rất nhiều bài toán khác của toán học và của thực tế (bài toán tối ưu, bài toán bù, bài toán cân bằng, hệ phương trình suy rộng,...), vì vậy nó thu hút sự quan tâm của nhiều nhà toán học trên thế giới cũng như ở Việt Nam trong mấy chục năm qua. Một trong những vấn đề cần trả lời khi nghiên cứu bất đẳng thức biến phân là vấn đề về sự tồn tại nghiệm và các tính chất của tập nghiệm (tính đóng, tính compact, tính liên thông, tính co rút, tính ổn định của tập nghiệm theo tham số,...). Một trong những lớp bài toán bất đẳng thức biến phân được nghiên cứu nhiều nhất là lớp bài toán bất đẳng thức biến phân affine. Tuy là lớp bài toán bất đẳng thức biến phân đơn giản nhất, nhưng bất đẳng thức biến phân affine là một trong những lớp bài toán có cấu trúc đặc thù và chứa một số lớp bài toán quan trọng (tối ưu véc tơ hàm phân thức tuyến tính, tối ưu hàm toàn phương,...). Nghiên cứu bất đẳng thức biến phân affine cũng làm sáng tỏ nhiều vấn đề của bất đẳng thức biến phân tổng quát. Luận văn này cố gắng trình bày một số khái niệm và kết quả liên quan đến sự tồn tại và tính chất tập nghiệm của bất đẳng thức biến phân, đặc biệt là bất đẳng thức biến phân affine. Luận văn gồm hai Chương. Mục 1 của Chương 1 trình bày bài toán bất đẳng thức biến phân và các bài toán liên quan. Mục 2 của Chương 1 trình bày sự tồn tại nghiệm của bài toán bất đẳng thức biến phân. Mục 3 của Chương 1 trình bày bài toán bất đẳng thức biến phân véctơ. Mục 4 của Chương 1trình bày tính liên thông của tập nghiệm trong bài toán bất đẳng thức biến phân véctơ. Chương 2 trình bày hai lớp bất đẳng thức biến phân affine cụ thể. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 Mục 1 Trình bày định nghĩa và một số định lý về bài toán bất đẳng thức biến phân affine,véctơ affine,véctơ affine yếu và bất đẳng thức biến phân affine phụ thuộc tham số Mục 2 Nói về tính bị chặn và liên thông của tập nghiệm và tập nghiệm yếu trong bài toán bất đẳng thức biến phân véctơ affine Mục 3 Trình bày bài toán tối ưu đa mục tiêu phân thức tuyến tính và bài toán tối ưu đa mục tiêu toàn phương lồi Mục 4 Tính toán một số thí dụ cho bài toán tối ưu đa mục tiêu phân thức tuyến tính bằng cách đưa về bài toán bất đẳng thức biến phân affine Các thí dụ trong [8] , [11] và [16] về tập nghiệm của bài toán bất đẳng thức biến phân affine được tính toán chi tiết và trình bày tường minh. Một số thí dụ trước đây được tính toán dựa theo điều kiện cần và đủ tối ưu (tiêu chuẩn Malivert) trong bài toán tối ưu đa mục tiêu hàm phân thức tuyến tính. Ở đây chúng tôi trình bày tính toán theo điều kiện cần và đủ để một điểm là nghiệm của bài toán bất đẳng thức biến phân affine. Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên, dưới sự hướng dẫn của PGS.TS. Tạ Duy Phượng- Viện Toán học. Thông qua luận văn, tôi xin bày tỏ lòng biết ơn tới Thầy hướng dẫn, người tận tình chỉ bảo và giúp đỡ tôi hoàn thành luận văn. Tôi xin cảm ơn Khoa sau đại học, Đại học Khoa học – Đại học Thái Nguyên, tập thể lớp Cao học Toán K2, bạn bè, và đồng nghiệp về sự quan tâm giúp đỡ trong quá trình tôi thực hiện luận văn này. Và cuối cùng, xin cảm ơn Gia đình, vợ và các con đã giúp đỡ, động viên và khích lệ tôi rất nhiều trong thời gian nghiên cứu học tập. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 CHƢƠNG I. BẤT ĐẲNG THỨC BIẾN PHÂN §1 BẤT ĐẲNG THỨC BIẾN PHÂN VÀ CÁC BÀI TOÁN LIÊN QUAN 1.1 Bất đẳng thức biến phân Định nghĩa 1.1. Cho : n nF   là một ánh xạ từ n vào n và K là một tập nào đó trong . n Bài toán bất đẳng thức biến phân (variational inequality, viết tắt là VI) được phát biểu như sau. Tìm x K  sao cho  , 0, .F x x x x K     (1.1) Bất đẳng thức (1.1) cũng thường được viết dưới dạng     0, , T F x x x x K     (1.1’) trong đó ,a b kí hiệu là tích vô hướng của hai véctơ a và b trong không gian n , còn TA và Tx là chuyển vị của ma trận A và véctơ .x Ta luôn qui uớc véctơ nx là véctơ cột. Bài toán bất đẳng thức biến phân được xác định bởi ánh xạ F và tập ,K vì vậy, khi cần làm rõ, ta kí hiệu bài toán bất đẳng thức biến phân là  VI , .F K Các điểm x K  thỏa mãn (1.1) được gọi là nghiệm của bất đẳng thức biến phân (1.1) hay điểm dừng của ánh xạ .F Tập tất cả các điểm x K  thỏa mãn (1.1) được gọi là tập nghiệm của bất đẳng thức biến phân (1.1). Tập tất cả các nghiệm của bất đẳng thức biến phân được kí hiệu là  Sol VI hoặc   Sol VI , .F K Kí hiệu  ; 0 .n nx x     Khi ấy  ; 0 .n nx x     Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 Vậy bất đẳng thức  , 0,F x x x x K     có thể viết dưới dạng  ( ), \ 0 .F x x x    Ngôn ngữ bất đẳng thức biến phân khá thuận tiện, nó có thể thống nhất được nhiều bài toán, thí dụ, bài toán tối ưu, bài toán cân bằng, phương trình suy rộng Dưới đây chúng ta sẽ xét mối liên quan giữa bài toán bất đẳng thức biến phân và các bài toán khác. 1.2 Bài toán tối ƣu một mục tiêu 1.2.1 Tối ƣu hàm một biến Trước tiên ta xét hàm một biến nhận giá trị trong . Cho  : ;f a b   là một hàm số khả vi trên  ; ,a b nghĩa là tồn tại đạo hàm tại mọi điểm  0 ;x a b và tồn tại đạo hàm từ bên phải ( ) : lim ( ) x a f a f x      và tồn tại đạo hàm từ bên trái ( ) : lim ( ). x a f a f x      Điểm x  được gọi là điểm cực tiểu (điểm tối ưu) của f nếu  ; ( ) min ( ). x a b f x f x   Kí hiệu  ; min ( ) x a b f x  là giá trị cực tiểu của hàm số f trên  ; .a b Khi đó theo điều kiện cần cực trị Fermat ta có  Nếu  ;x a b thì ( ) 0.f x   Nếu x a   thì ( ) 0.f a   Nếu x b   thì ( ) 0f b  . Cả ba trường hợp này có thể viết gọn lại như sau. Mệnh đề 1.1. Điểm x  là điểm cực tiểu của f trên  ;a b thì Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7    ( ) 0, ; .f x x x x a b      Thí dụ 1.1 Cho hàm số 2( ) 2 3.y f x x x    a) Tìm [ 2;2] min ( ) x f x   Trên đoạn [ 2;2] thì [ 2;2] min ( ) x f x   1 25 4 8 f          và 1 0 4 f         b) Tìm [1;5] min ( ) x f x  Trên đoạn [1;5] thì [1;5] min ( ) (1) 0 x f x f    và  1 5 0f    . c) Tìm [ 4; 1] min ( ) x f x    Trên đoạn [ 4; 1]  thì [ 4; 1] min ( ) ( 1) 2 x f x f        và  1 3 0f      . 1.2.2 Tối ƣu hàm nhiều biến Cho :f K   là một ánh xạ từ tập nK   vào , 1( ) ( ,..., ).nf x f x x Xét bài toán tối ưu: Tìm  min ( ) : .f x x K (1.2) Định nghĩa 1.2. Nếu điểm x K  được gọi là điểm cực tiểu địa phương của bài toán tối ưu (1.1) nếu tồn tại một lân cận ( )U x của điểm x  sao cho ( ) ( )f x f x  với mọi ( ).x K U x  Giả sử    1 2, ,..., nf x f x x x có đạo hàm riêng ( )f x  1 2 ( ) ( ) ( ) , ,..., n f x f x f x x x x           Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 theo mọi biến tại mọi điểm . nx K   Đặt   : ( ).F x f x Khi ấy với mỗi x K thì ( ) nf x  hay : .nF K   Mệnh đề 1.2. Giả sử nK   là một tập lồi, đóng, khác rỗng. Nếu x K là điểm cực tiểu địa phương của bài toán tối ưu (1.2) trên K thì  , 0, .F x x x x K     (1.3) Điều kiện (1.3) được gọi là điều kiện cần cực trị của bài toán tối ưu (1.2). Chứng minh Giả sử x K  là điểm cực tiểu địa phương của .f Lấy bất kì một điểm ,x K .x x Do K là tập lồi nên đoạn thẳng ;x x   nằm trong ,K tức là    : 0;1 .tx x t x x K t       Đặt  : 0;1u K là hàm số xác định bởi   tt u t x Với mỗi x cố định ta xét hàm số  : 0;1   xác định bởi          .tt t f u t f x f x t x x       Khi đó  là hàm hợp của hai hàm khả vi f và u nên  cũng là hàm khả vi trên  0;1 và nếu f đạt cực tiểu tại x  thì  đạt cực tiểu tại 0.t  Theo điều kiện cần cực tiểu cho bài toán tối ưu hàm một biến ta có     ' 0 grad 0, .f x x x x K        Đặt      : grad .F x f x f x  Khi đó x K là điểm cực tiểu của f thì  , 0, .F x x x x K     Mệnh đề chứng minh xong. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 Nhận xét 1.1. Như vậy, tập các điểm dừng của bài toán tối ưu (1.2) chính là nghiệm của bài toán bất đẳng thức biến phân (1.1). Hơn nữa, theo Mệnh đề dưới đây, nếu  f x là hàm lồi trên K thì ta có điều ngược lại. Mệnh đề 1.3. Cho K là một tập lồi, đóng, khác rỗng trong .n Nếu  f x là hàm lồi khả vi trên K và x K là nghiệm của bài toán bất đẳng thức biến phân (1.1) thì x cũng là nghiệm của bài toán tối ưu (1.2). Chứng minh Vì  f x là hàm lồi trên K nên ta có      ( ) , .Tf x f x f x x x x K       Vì x K  là nghiệm của bài toán bất đẳng thức biến phân (1.1) nên ta có  ( ) 0, .Tf x x x x K      Suy ra    ,f x f x x K   hay x là nghiệm của bài toán tối ưu (1.2). Như vậy, trong trường hợp  f x là hàm lồi khả vi trên K thì bài toán bất đẳng thức biến phân (1.1) và bài toán tối ưu (1.2) là tương đương. Dưới đây ta sẽ xét câu hỏi: Với điều kiện nào thì bài toán bất đẳng thức biến phân (1.1) có thể đưa về bài toán tối ưu (1.2)? Kí hiệu  ,M n n là tập hợp các ma trận vuông cấp .n Trước tiên ta đưa vào các định nghĩa sau. Định nghĩa 1.3. Ma trận  ,A M n n được gọi là nửa xác định dương trên n nếu nó thỏa mãn điều kiện 0x Ax  với mọi .nx Định nghĩa 1.4. Ma trận  ,A M n n được gọi là ma trận xác định dương trên n nếu nó thoả mãn các điều kiện sau Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 0Tx Ax  , 0.nx x   Thí dụ 1.2 Ma trận 1 0 1 0 1 0 0 1 1 A            là ma trận xác định dương trên 3. Thật vậy Xét Tx Ax  1 1 2 3 2 3 1 0 1 ( , , ) 0 1 0 0 1 1 x x x x x x               1 1 2 3 1 3 2 3 ( , , ) x x x x x x x x              2 2 2 1 2 2 3 1 3 3 x x x x x x x     2 2 2 3 3 3 1 2 0. 2 2 2 x x x x x                  Với mọi 3(0,0,0) .x   Mặt khác 0 Tx Ax  3 1 3 2 2 3 0 2 0 2 0 2 x x x x x             1 2 3 0 0 0 x x x        A là ma trận xác định dương trên 3. Thí dụ 1.3 Ma trận 0 1 1 0 M        là ma trận nửa xác định dương trên 2. Thật vậy 1 1 2 2 0 1 ( , ) 1 0 T x x Mx x x x           1 2 1 2 1 1 2 2 ( , ) 0, x x x x x x x x            2.x  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 Ta có 0,Tx Mx  2.x   M là ma trận nửa xác định dương trên 2. Thí dụ 1.4 Ma trận 1 0 1 0 1 2 1 0 1 A            là ma trận nửa xác định dương trên 3. Thật vậy, 1 1 1 2 3 2 1 3 2 1 2 3 2 3 3 1 0 1 ( , , ) 0 1 2 ( , , 2 ) 1 0 1 T x x x Ax x x x x x x x x x x x x x                                 2 2 2 1 1 3 2 1 3 2 3 32x x x x x x x x x      2 2 2 1 2 2 3 32x x x x x      22 1 2 3 0,x x x    3.x  Ta có   2 1 1 2 2 32 3 0 0 0 0 T x x x Ax x xx x            Nghĩa là 3 30 (0, , ). Tx Ax x x x     A là ma trận nửa xác định dương trên 3. Thí dụ 1.5 Ma trận 1 0 0 0 0 1 0 0 2 0 2 0 0 0 2 1 A             là ma trận nửa xác định dương trên 4. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 Thật vậy, 1 1 2 2 1 2 3 4 1 3 2 3 4 4 3 3 4 4 1 0 0 0 0 1 0 0 ( , , , ) ( 2 , ,2 2 , ) 2 0 2 0 0 0 2 1 T x x x x x Ax x x x x x x x x x x x x x x                                  2 2 2 2 1 1 3 2 3 3 4 42 2 2x x x x x x x x        2 2 2 1 3 2 3 4( ) 0,x x x x x      4.x  Ta có   2 1 3 3 1 2 2 2 2 3 43 4 0 0 0 0 ( ) 0 T x x x x x Ax x x x xx x                   Nghĩa là 1 1 10 ( ,0, , ). Tx Ax x x x x    Vậy A là ma trận nửa xác định dương trên 4. Định nghĩa 1.5. Ma trận A được gọi là xác định dương mạnh trên n nếu tồn tại một số dương 0  sao cho 2Tx Ax x với mọi .nx Trong nhiều bài toán thực tế, ta phải xét trường hợp ma trận ( )A v phụ thuộc vào v trên một tâp S nào đó. Vì vậy định nghĩa ma trận xác định dương còn được mở rộng hơn như sau. Định nghĩa 1.3’. Ma trận vuông n chiều  ( ) ( ) , , 1,...,ijA v a v i j n  phụ thuộc vào nv S   được gọi là nửa xác định dương trên S nếu ( ) 0Tx A v x  với mọi nx và với mọi .v S Ma trận ( )A v được gọi là xác định dương trên S nếu ( ) 0Tx A v x  với mọi , nx 0x  và với mọi .v S Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 Ma trận ( )A v được gọi là xác định dương mạnh trên S nếu tồn tại một số dương 0  sao cho 2 ( )Tx A v x x với mọi nx và với mọi .v S Vì ma trận   1 ( ) ( ) 2 TM v M v là một ma trận đối xứng nên giá trị riêng của nó là những số thực. Kí hiệu ( )v là giá trị riêng nhỏ nhất của   1 ( ) ( ) . 2 TM v M v Khi ấy 1) Ma trận ( )A v là nửa xác định dương trên S khi và chỉ khi ( ) 0v  với mọi .v S 2) Ma trận ( )A v là xác định dương trên S khi và chỉ khi ( ) 0v  với mọi .v S 3) Ma trận ( )A v là xác định dương mạnh trên S khi và chỉ khi ( ) 0v   với mọi .v S Ta đã biết rằng, nếu một hàm lồi hai lần khả vi trên tập lồi đóng K thì đạo hàm bậc hai của nó là một ma trận đối xứng xác định dương. Định lí dưới đây chỉ ra rằng, điều ngược lại cũng đúng: ―cho trước một ánh xạ : nF K   có đạo hàm là ma trận đối xứng nửa xác định dương thì tồn tại một hàm lồi có đạo hàm bằng chính hàm .F ‖ Định lí 1.1. Giả sử tập nK   và : nF K   là hàm khả vi liên tục trên K và ma trận Jacobian ( )F x là đối xứng và nửa xác định dương trên .K Khi ấy tồn tại hàm lồi : nf   sao cho ( ) ( )f x F x  với mọi x K và nếu x K là nghiệm của bất đẳng thức biến phân (1.1) thì x K  là nghiệm của bài toán tối ưu (1.2). Chứng minh Do ma trận Jacobian ( )F x là đối xứng trên K nên theo định lí Green ta có ( ) ( ) ,Tf x F x dx  trong đó  là tích phân đường. Do ( )F x là nửa xác định Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 dương trên K nên ( )f x là hàm lồi trên .K Kết luận của Định lí được suy ra từ Mệnh đề 1.2. Như vậy, bài toán tối ưu có thể đưa về bất đẳng thức biến phân. Ngược lại, bất đẳng thức biến phân VI( , )F K cũng có thể phát biểu lại như một bài toán tối ưu lồi chỉ khi điều kiện đối xứng và nửa xác định dương của ma trận ( )F x được thỏa mãn. Điều này nói lên rằng, bài toán bất đẳng thức biến phân nói chung rộng hơn bài toán tối ưu, bởi vì nó chứa cả trường hợp hàm ( )F x có ma trận Jacobian không đối xứng. Nhận xét 1.2. Trong trường hợp nK   thì ta có điều kiện cần cực trị cho bài toán tối ưu không có hạn chế sau đây. Hệ quả 1.1. Nếu nx là điểm cực tiểu địa phương của bài toán (1.2) khi nK   thì   0.F x  Chứng minh Giả sử nx là điểm cực tiểu địa phương của bài toán (1.2) khi nK   thì theo Định lí 1.1 ta có  , 0, .nF x x x x     Thay ( )x x F x   và ( )x x F x   vào bất đẳng thức trên ta được  , ( ) 0F x F x   và  , ( ) 0,F x F x   hay 2 ( ) ( ), ( ) 0.F x F x F x    Suy ra ( ) 0.F x  Nhận xét 1.3. Hệ quả 1.1 vẫn đúng khi int .x K  Thật vậy, ta có Hệ quả 1.2. Nếu intx K  là điểm cực tiểu địa phương của bài toán tối ưu (1.2) thì   0.F x  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 Chứng minh Giả sử intx K  là điểm cực tiểu địa phương của bài toán tối ưu (1.2) thì theo Định lí 1.1 ta có  , 0, .F x x x x K     Do intx K  nên tồn tạ