Tài liệu Bổ đề suy rộng và bài toán tối ưu toàn phương (lv01075)

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 NGUYỄN THỊ LIÊN S-BỔ ĐỀ SUY RỘNG VÀ BÀI TOÁN TỐI ƢU TOÀN PHƢƠNG Chuyên ngành: Toán Giải tích Mã số: 60 46 01 02 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 HÀ NỘI, 2013 2 LỜI CẢM ƠN Để hoàn thành luận văn tốt nghiệp em đã nhận đƣợc sự dìu dắt, chỉ bảo và tạo điều kiện giúp đỡ của các thầy cô trong khoa Toán nói chung và tổ Giải tích nói riêng, đặc biệt là sự hƣớng dẫn, chỉ bảo giúp đỡ hết sức tận tình của thầy giáo PGS TS Tạ Duy Phƣợng. Qua đây, em xin bày tỏ lời cảm ơn chân thành tới thầy giáo PGS TS Tạ Duy Phƣợng. Em xin gửi lời cảm ơn sâu sắc tới các thầy cô tổ môn Giải tích, các thầy cô giáo trong khoa Toán, cảm ơn gia đình, bạn bè và các bạn sinh viên quan tâm và đóng góp ý kiến cho đề tài của em. Em xin chân thành cảm ơn! Hà Nội, tháng 12 năm 2013 Học viên Nguyễn Thị Liên 3 LỜI CAM ĐOAN Tôi xin cam đoan rằng các số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các tài liệu khác. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã đƣợc cảm ơn và các thông tin trích dẫn trong luận văn đã đƣợc chỉ rõ nguồn gốc. Trong luận văn, tôi đã kế thừa những thành quả nghiên cứu của các nhà khoa học, các nhà nghiên cứu với sự tôn trọng và biết ơn. Những kết quả nêu trong luận văn chƣa đƣợc công bố trên bất kỳ công trình nào khác. Hà Nội, tháng 12 năm 2013 Học viên Nguyễn Thị Liên 4 MỤC LỤC Trang TRANG PHỤ BÌA 1 LỜI CẢM ƠN 2 LỜI CAM ĐOAN 3 MỤC LỤC 4 MỞ ĐẦU 5 CHƢƠNG 1 S-BỔ ĐỀ SUY RỘNG 7 1.1 Định lí Minimax 7 1.2 Giới thiệu S-Bổ đề và S-Bổ đề suy rộng 14 1.2.1 S-Bổ đề 14 1.2.2 S-Bổ đề suy rộng 19 CHƢƠNG 2 BÀI TOÁN TỐI ƢU TOÀN PHƢƠNG 25 2.1 Bài toán tối ƣu toàn phƣơng với một hạn chế 25 2.2 Bài toán tối ƣu toàn phƣơng với nhiều hạn chế 35 KẾT LUẬN 52 TÀI LIỆU THAM KHẢO 53 5 MỞ ĐẦU 1. Lí do chọn đề tài Do có nhiều ứng dụng, bài toán tối ƣu đƣợc sự quan tâm nghiên cứu của nhiều nhà toán học trong và ngoài nƣớc. Có thể nói, bài toán tối ƣu tuyến tính (qui hoạch tuyến tính) với thuật toán đơn hình về cơ bản đã đƣợc giải quyết vào những năm 50 của thế kỉ trƣớc. Lớp bài toán tiếp theo đƣợc nhiều nhà toán học quan tâm là lớp bài toán tối ƣu với hàm mục tiêu là hàm toàn phƣơng (tối ƣu toàn phƣơng) và lớp bài toán tối ƣu đa thức. Tuy nhiên, cho đến nay, mặc dù phát biểu tƣơng đối rõ ràng và đơn giản, bài toán tối ƣu toàn phƣơng không lồi vẫn chƣa đƣợc giải quyết trọn vẹn. Một trong những kĩ thuật quan trọng áp dụng trong bài toán tối ƣu toàn phƣơng là S-Bổ đề (do Yakubovich phát biểu năm 1971). Gần đây, Giáo sƣ Hoàng Tụy đã viết một số bài báo với những nghiên cứu mới, trong đó có S-Bổ đề suy rộng, giải quyết khá cơ bản lớp bài toán tối ƣu toàn phƣơng và tối ƣu đa thức. Với mong muốn tìm hiểu sâu hơn về bài toán tối ƣu toàn phƣơng, nhằm bổ sung và nâng cao kiến thức đã học trong chƣơng trình đại học và cao học, đồng thời sử dụng các kiến thức về tối ƣu trong giảng dạy, tôi chọn đề tài S-Bổ đề suy rộng và Bài toán tối ưu toàn phương làm luận văn cao học của mình. Do sử dụng S-Bổ đề suy rộng nêu trong bài báo [12] với những giải thích chi tiết trong chứng minh nên luận văn này không trùng với hai luận văn cao học với đề tài S-Bổ đề và Bài toán tối ưu toàn phương [1] và [2] đã đƣợc bảo vệ. 2. Mục đích nghiên cứu Nghiên cứu và trình bày S-Bổ đề suy rộng và bài toán tối ƣu toàn phƣơng, từ đó áp dụng để nghiên cứu về một số lớp bài toán tối ƣu toàn phƣơng. 6 3. Nhiệm vụ nghiên cứu Nghiên cứu bài toán tối ƣu toàn phƣơng. 4. Đối tƣợng và phạm vi nghiên cứu Đối tƣợng nghiên cứu: Nghiên cứu bài toán tối ƣu toàn phƣơng. Phạm vi nghiên cứu: Các bài báo và các tài liệu liên quan đến bài toán tối ƣu toàn phƣơng, đặc biệt là bài báo [12]. 5. Phƣơng pháp nghiên cứu Sử dụng các kiến thức và công cụ của giải tích, giải tích hàm, lí thuyết tối ƣu để tiếp cận và giải quyết vấn đề. Thu thập, nghiên cứu và tổng hợp các tài liệu liên quan, đặc biệt là các bài báo mới về vấn đề mà luận văn đề cập tới. 6. Dự kiến đóng góp của luận văn Hy vọng luận văn là một tài liệu tổng quan và tham khảo tốt cho sinh viên và học viên cao học về bài toán tối ƣu toàn phƣơng. 7 CHƢƠNG 1. S-BỔ ĐỀ SUY RỘNG Chƣơng này phát biểu và chứng minh định lý minimax và S-bổ đề, từ đó phát biểu S-bồ đề suy rộng. 1.1 ĐỊNH LÍ MINIMAX Cho hàm số F : C ¡ số thực ¡ . Điểm x C đƣợc gọi là điểm cực tiểu địa phương của F ( x) trong xác định trên tập hợp C ¡ n nhận giá trị trong tập C nếu tồn tại hình cầu W có tâm x sao cho F ( x ) F ( x) với mọi x W C. Điểm x đƣợc gọi là điểm cực tiểu toàn cục của F ( x) trên C nếu F ( x ) F ( x) với mọi x C. Mục tiêu đặt ra là nghiên cứu bài toán tối ƣu toàn phƣơng (nói chung không lồi) dựa trên các định lí minimax. Các định lí minimax cổ điển thƣờng đƣợc phát biểu dựa trên giả thiết về tính (tựa) lồi-lõm của hàm số. Các định lí này không áp dụng đƣợc cho bài toán tối ƣu không lồi. Vì vậy, để nghiên cứu bài toán tối ƣu không lồi, trong [12] đã phát biểu và chứng minh định lí minimax dƣới dạng sau. Định lý 1.1.1 (Định lý minimax, [12]) Giả sử C là tập hợp con đóng của ¡ n , D là khoảng (đóng hoặc mở) của ¡ và L( x, y) : ¡ n ¡ ¡ là hàm liên tục. Giả sử các điều kiện sau đây đƣợc thoả mãn: (i) Với mỗi x ¡ (ii) Mọi điểm y D là cực tiểu địa phƣơng của L(., y ) trong C là cực tiểu n thì L( x,.) là hàm lõm; toàn cục của L(., y ) trên C ; (iii) Tồn tại y* D sao cho L( x, y* ) Khi ấy ta có đẳng thức minimax: khi x C, x . 8 (1.1) inf sup L( x, y) supinf L( x, y). x C x C y D y D Ngoài ra, nếu inf sup L( x, y) x C thì tồn tại x C thoả mãn y D sup L( x , y) y D Chứng minh Đặt (1.2) minsup L( x, y). x C y D : inf sup L( x, y), x C : supinf L( x, y). x C y D Chúng ta có thể giả thiết y D thì đẳng , bởi vì nếu ngƣợc lại, tức là thức (1.1) là hiển nhiên. Thật vậy, giả sử . Khi ấy tồn : supinf L( x, y) x C y D tại dãy yn L( x, yn ) D sao cho inf x C , tức là với mọi x C khi n . Suy ra với mọi x C ta có sup L( x, y) ta có L( x, yn ) . Suy ra y D hay : inf sup L( x, y) x C . y D Nhƣ vậy coi hiệu C ( y) : . Lấy số thực x C | L( x, y) tuỳ ý và với mỗi y D cố định, kí . Đầu tiên chúng ta chứng minh với bất kì đoạn a, b D điều kiện sau đây đƣợc thoả mãn: y C ( y) . Ta luôn luôn có thể giả thiết rằng y* (1.3) a, b . Bởi vì inf L( x, y * ) supinf L ( x, y ) : x C x C y D nên tồn tại x C thoả mãn L( x , y* ) theo biến y, tồn tại u, v sao cho u và theo tính liên tục của hàm L( x , y ) y * v và L( x , y ) với mọi y u, v . Hơn nữa, đặt s : sup y u, b | u z y C ( z) . (1.4) 9 với mọi u Do L( x , z ) với mọi u v y có s z v nên x u, b | u z y z v nên C ( z) : u z v C ( z ) hay u z v , tức là C ( z) . Mà s : sup y C ( z) chứa x x C : L( x, z) u, b | u z y nên ta C ( z) v. Theo định nghĩa của s , tồn tại dãy yk Z s sao cho Ck : Theo giả thiết (iii), C ( y* ) : tính liên tục của hàm x C : L( x, y* ) . Nếu xn ( xn ) . Hơn nữa, C ( y* ) : ( x) lim ( xn ) x x C ( y) . là compact. Thật vậy, theo ( x) : L( x, y* ) tập mức C ( y* ) : là tập đóng vì nếu xn C ( y* ) thì u y yk x C : L( x, y* ) x thì x C ( y * ) do là bị chặn. x C : L( x, y* ) n Thật vậy, nếu C ( y * ) không bị chặn thì tồn tại L( xn , y* ) mà xn xn C ( y * ), tức là . Nhƣng theo giả thiết (iii) ta có L( x, y* ) . Vô lí. Chứng tỏ C ( y * ) là bị chặn hay C ( y * ) compact. Do đó Ck : u y yk C ( y) . (k 1, 2,...) tạo thành dãy các tập con đóng khác rỗng lồng nhau của tập hợp compact C ( y* ). Vì vậy, theo định lí về giao của các tập compact lồng nhau, tồn tại x 0 y u , s . Bởi vì L( x 0 , yk ) k 1 Ck , nghĩa là thoả mãn L( x 0 , y ) với mọi k , cho k của hàm L( x 0 , y ) theo y ta đƣợc L( x 0 , s) y ; , theo tính liên tục . Do đó L( x 0 , y ) với mọi u, s . Ta khẳng định rằng s b. Thật vậy, giả sử s b thì do L( x 0 , s ) nên L( x 0 , s) . Thật vậy, nếu L( x 0 , s) tục của hàm L( x 0 , s ) tồn tại q s thoả mãn L( x 0 , y ) thì theo tính liên với mọi y Điều này trái với (1.4). Vì vậy, nếu s b thì ta phải có L( x 0 , s) . s, q . 10 Hơn nữa, bất kì hình cầu W tâm x 0 ta không thể có vậy, nếu tồn tại hình cầu W ( x 0 , r ) mà min L( x, s). Thật x C W min L( x, s) thì theo giả thiết (ii) x C W ( x0 , r ) (cực tiểu địa phƣơng là cực tiểu toàn cục) kéo theo theo chứng minh trên ta đã có Điều này trái với min L( x, s), nhƣng x C L( x 0 , s) min L( x, s), x C L( x 0 , s). Suy ra : supinf L( x, y) inf L( x, s). x C x C y D Do đó tồn tại x k C sao cho x k Nếu với một y s , b nào đó và một k nào đó ta có L( x k , y ) k x0 và L( x , s) . nên từ giả thiết (i) kéo theo L( x k , z ) L( x k , s ) nữa, vì L( x k , s) y tồn tại s q và L( x k , y ) với mọi z u, s . Hơn , nên theo tính liên tục của L( x k , y ) theo với mọi y y sao cho L( x k , q) với mọi k , và với mọi y (1.4). Vì vậy, L( x k , y ) , thì do theo tính liên tục của L( x, y ) theo x, ta có L( x 0 , y ) s, q . Mâu thuẫn với s , b . Cho x k , với mọi y x0 s ,b . Điều này chứng minh s b và do đó u y b Tƣơng tự, đặt t inf y nghĩa là a y b C ( y) C ( y) a, v | a (1.5) ; z v C ( z) . Ta có thể chứng tỏ t a, , từ đó (1.3) đƣợc chứng minh. Nhƣ đã chứng minh ở trên, theo giả thiết (iii), tập hợp C ( y * ) là compact. Bởi vì mọi tập hợp hữu hạn E ra từ (1.3) rằng họ C ( y ) D phải chứa trong một đoạn ∆ nào đó nên suy C ( y * ), y D, có tính chất giao hữu hạn. Do đó, tồn tại x C thoả mãn L( x, y ) với mọi y D. Lấy ta thấy rằng, với mỗi k 1,2,... tồn tại x k 1 k 1,2,...; k k C thoả mãn L( x , y ) 1 với k 11 1 k mọi y D. Nói riêng, L( x k , y * ) 1, nghĩa là x k C 1 ( y* ) với mọi k . Vì tập hợp C 1 ( y* ) là compact nên dãy x k có điểm tụ x C thoả mãn L( x , y ) với mọi y D. Suy ra sup L( x , y) và y D : inf sup L( x, y) sup L( x , y) x C y D Vì L( x , y) inf L( x, y) với mọi x x C mọi x . y D C nên sup L( x , y) supinf L( x, y) với x C y D y D C và do đó inf sup L( x , y) supinf L( x, y) hay x C x C y D . Vậy . Hệ y D thức (1.2) đƣợc chứng minh. Nhận xét 1.1.1 Giả thiết (ii) là hiển nhiên thoả mãn nếu L(., y ) là hàm lồi và C là tập hợp lồi (Định lý 1.1.1 trở về định lý minimax cổ điển). Hơn nữa, sau này ta sẽ thấy, giả thiết (ii) thoả mãn trong nhiều trƣờng hợp của bài toán tối ƣu toàn phƣơng. Mở rộng cho trƣờng hợp D ¡ m với m 1, ta có Hệ quả 1.1.1 Giả sử C là tập hợp con đóng của ¡ n , D là tập lồi trong ¡ và L( x, y ) : ¡ n m ¡ là hàm liên tục. D Giả thiết các điều kiện sau đây đƣợc thoả mãn: (i) Với mỗi x ¡ n hàm L( x,.) là affine; (ii) Mọi điểm y D là cực tiểu địa phƣơng của L( x, y ) trên C cũng là cực tiểu toàn cục của L( x, y ) trên C ; (iii*) Tồn tại y* D thoả mãn L( x, y* ) khi x C, x * * L( x* , y* ) min L ( x , y ) inf L ( x , y ) maxinf L ( x , y ) và x C x C y D x C với duy nhất x* C. Khi ấy ta có đẳng thức minimax và (1.6) 12 min sup L( x, y) x C Chứng minh Đặt (1.7) max inf L( x, y). x C y D y D tuỳ ý. Với mỗi y D giả sử : supinf L( x, y). Xét x C y D C ( y) : . Theo giả thiết (iii*) ta có x C | L( x, y) * inf L ( x , y ) maxinf L( x, y) : x C x C . y D * * L( x, y* ) với duy nhất x* C. Do đó Cũng theo (iii*), L( x , y ) min x C C ( y* ) : Với mỗi y D đặt Dy : x C | L( x, y* ) y* , y x* . yt : (1 t ) y* ty | 0 t 1 Ly ( x, t ) : L x,(1 t ) y* ty , là hàm xác định trên C D và 0,1 . Ta có thể dễ dàng thử lại C , 0,1 và Ly ( x, t ) thoả mãn tất cả các điều kiện của Định lý 1.1.1. Do đó, từ kết luận của Định lý 1.1.1 ta có inf sup Ly ( x, y ) supinf Ly ( x, y). x C x C t 0,1 t 0,1 Bởi vì inf sup Ly ( x, t ) supinf Ly ( x, t ) x C x C t 0,1 t 0,1 z sup inf L( x, z ) supinf L ( x, z ) x C x C y* , y z D D nên suy ra tồn tại x C sao cho sup Ly ( x , t ) hay sup Ly ( x , z ) t 0,1 x C ( z ) với mọi z z y* , y , hay x C ( y* ) Hơn nữa, do giả thiết L( x, y* ) , tức là y* , y C ( y) C ( y* ) C. , tập C ( y * ) là khi x C, x compact (xem chứng minh Định lí 1.1.1) và do đó C ( y * ) C ( y ) là compact vì C ( y) là tập đóng. Cho L( x* , y ) khi ấy ta có C ( y* ) C ( y) với mọi y D. Vì vậy, sup L( x* , y) y D C ( y* ) . Suy ra x* . Do đó 13 * : inf sup L ( x , y ) sup L ( x , y) x C y D Bao giờ ta cũng có . y D (xem chứng minh Định lí 1.1.1). Vậy , đẳng thức (1.7) đƣợc chứng minh. Hệ quả đƣợc chứng minh hoàn toàn. Chú ý 1.1.1 a) Khi C là đa tạp affine (tức là nếu x1 , x2 C thì xt : tx1 (1 t ) x2 C với mọi t ¡ ) và L( x, y ) là hàm toàn phƣơng theo x thì trong giả thiết (iii*) không cần tính duy nhất của x*. Thật vậy, trong trƣờng hợp này tính duy nhất của x* suy ra từ điều kiện L( x, y* ) khi x C, x (kéo theo x a L( x, y* ) là hàm lồi ngặt trên đa tạp affine C ). Thật vậy, không hạn chế tổng quát, có thể coi ai 0, i 1,2,...m. Chọn x( q ) khi q . Do đó L( x, y* ) L( x, y* ) a1 x12 ... ak xk2 với ak 1 xk2 1... am xm2 0,...,0, q,..., q . Khi ấy x( q ) m k q theo giả thiết. Vô lí vì L( x, y* ) a1 x12 ... ak xk2 ak 1xk2 1... am xm2 q 2 ak 1 ... am . Suy ra L( x, y* ) chỉ có thể có dạng L( x, y* ) a1 x12 ... ak xk2 là hàm lồi chặt. Mà ta đã biết, hàm lồi chặt chỉ đạt giá trị nhỏ nhất tại nhiều nhất một điểm. L( x, y* ) chỉ đạt đƣợc tại duy nhất nghiệm. Do đó min x C b) Điều kiện (iii*) là thoả mãn nếu điều kiện sau đây đƣợc thỏa mãn (iii!) Tồn tại duy nhất cặp ( x* , y* ) C D sao cho và L( x, y* ) L( x* , y* ) max min L ( x , y ) x C y D khi x C, x L( x, y ) max min L( x, y ) và L( x, y ) Thật vậy, giả sử y thoả mãn min x C x C y D khi x C, x . . 14 Vì L(., y ) là lồi theo x nên tồn tại x thoả mãn L( x , y ) min L( x, y ). Khi ấy x C L( x , y ) max min L( x, y ) do đó theo điều kiện duy nhất nghiệm ta có y C y D ( x* , y * ) ( x , y ). Do đó min L( x, y* ) max min L( x, y) tức là (iii*) đƣợc thoả x C y D x C mãn. Hàm F ( x) : ¡ hợp C ¡ n n ¡ đƣợc gọi là thoả mãn điều kiện bức (coercive) trên tập nếu F ( x) . Điều kiện (iii) trong Định khi x C, x lý 1.1.1 có nghĩa là luôn tồn tại y* D sao cho hàm x a L( x, y* ) thoả mãn điều kiện bức trên C. Dƣới đây, ta sẽ xét hàm L( x, y ) có dạng L( x, y ) f ( x) yg ( x); trong đó f ( x) và g ( x ) là các hàm toàn phƣơng trong ¡ n . Vì L( x, y ) f ( x) yg ( x) là tuyến tính theo y nên nó cũng là hàm lõm theo y và điều kiện (i) trong Định lý 1.1.1 là hiển nhiên. Dƣới đây chúng ta sẽ xét các trƣờng hợp, khi điều kiện (ii) và (iii) đƣợc thoả mãn. 1.2 GIỚI THIỆU S-BỔ ĐỀ VÀ S-BỔ ĐỀ SUY RỘNG 1.2.1 S-Bổ đề Bổ đề 1.2.1 (Lemma 1, [12]) Giả sử F ( x) : ¡ H ¡ n n ¡ là hàm toàn phƣơng, là đa tạp affine. Mọi cực tiểu địa phƣơng x của F ( x ) trên H là cực tiểu toàn cục trên H . Nếu F ( x ) bị chặn dƣới trên H thì nó là lồi trên H . Chứng minh Xét đƣờng thẳng tuỳ ý trong H đi qua x . Trên đƣờng thẳng này, vì F ( x ) là hàm toàn phƣơng của một biến thực, nó sẽ là lồi hoặc lõm ngặt. Do đó bất kỳ điểm cực tiểu địa phƣơng của nó trên cũng là cực tiểu trên toàn . Nếu F ( x ) bị chặn dƣới trên H thì nó phải lồi trên mọi đƣờng thẳng H , do đó F ( x) lồi trên toàn H . 15 Bồ đề 1.2.2 (Lemma 2, [12] Hàm toàn phƣơng F ( x ) là lồi ngặt trên đa tạp affine H nếu và chỉ nếu nó thoả mãn điều kiện bức trên H nghĩa là khi x H , F ( x) . Điều này tƣơng đƣơng với tập hợp x là compact với mọi số thực . x H | F ( x) Chứng minh Nếu hàm toàn phƣơng F ( x ) là lồi ngặt trên H thì lồi ngặt trên mọi đƣờng thẳng trên H . Nghĩa là với bất kì ¡ tập hợp đóng và lồi không chứa bất kì nửa đƣờng thẳng nào, do đó phải là x H | F ( x) compact, nghĩa là thoả mãn điều kiện bức trên H . Ngƣợc lại, nếu hàm toàn phƣơng F ( x ) không phải là hàm lồi ngặt trên H . Khi ấy F ( x ) không là lồi ngặt trên một đƣờng thẳng H nào đó. Do đó F ( x ) là lõm trên đƣờng thẳng này và vì vậy F ( x ) không thoả mãn điều kiện bức trên H . Bổ đề 1.2.3 (Lemma 3, [12]) Giả sử f ( x) và g ( x ) là những hàm toàn phƣơng trên ¡ n , L( x, y ) đƣờng thẳng trong ¡ n f ( x) yg ( x) với x ¡ n , y ¡ . Khi ấy với mỗi ta có đẳng thức minimax (1.8) inf sup L( x, y) supinf L( x, y). x x y ¡ y ¡ Nếu g ( x ) không phải là hàm affine trên thì ta vẫn có đẳng thức minimax (1.9) inf sup L( x, y ) supinf L( x, y ). x x y ¡ y ¡ Chứng minh Nếu cả hai f ( x) và g ( x ) là hàm lõm trên và một trong chúng không phải là hàm affine thì rõ ràng inf f ( x) | g ( x) 0, x sup L( x, y ) inf f ( x) | g ( x) 0, x do đó inf x , . Vậy (1.8) là hiển y R nhiên thoả mãn. Nếu cả hai f ( x) và g ( x ) là affine trên thì (1.8) suy ra từ kết quả của bài toán qui hoạch tuyến tính đối ngẫu. Nói cách khác, ta chỉ cần 16 xét trƣờng hợp f ( x) hoặc g ( x ) là lồi ngặt trên . Khi đó tồn tại y * ¡ cho f ( x) y* g ( x) là lồi ngặt trên , do đó L( x, y* ) sao khi x , . Từ đó theo Bổ đề 1.2.1, điều kiện (ii) trong Định lý 1.1.1 đƣợc thoả x mãn. Đẳng thức (1.8) là đẳng thức (1.9) khi C Nếu g ( x ) không phải là hàm affine trên y* g ( x) là lồi ngặt trên f ( x) khi g ( x ) là lõm ngặt trên ( y* , D ¡ . ¡ sao cho thì luôn tồn tại y* 0 khi g ( x ) là lồi ngặt trên và y* 0 ). Suy ra mọi điều kiện của Định lý 1.1.1 thỏa và D ¡ và ta có đẳng thức (1.9). mãn với C Định lí 1.2.1. (S-bổ đề, Yakubovich, 1971) Cho f , g : ¡ n ¡ là những hàm toàn phương. Giả sử rằng điều kiện Slater được thoả mãn với hàm g , tức là có một x ¡ n sao cho g ( x ) 0. Khi đó hai phát biểu sau là tương đương: (i) Hệ f ( x) 0 g ( x) 0 (1.10) không tương thích. (ii) Có một số thực không âm y 0 sao cho f ( x) yg ( x) 0 với mọi x ¡ n . (1.11) Nhận xét 1.2.1 S-Bổ đề không còn đúng nếu nhƣ điều kiện Slater không còn đƣợc thoả mãn. Thật vậy, lấy f ( x) x và g ( x) 2 x 2 . Khi đó, rõ ràng không tồn tại x ¡ để g ( x) 0. Nghĩa là điều kiện Slater không thỏa mãn. Ta thấy hệ f ( x) 0 g ( x) 0 là vô nghiệm. Giả sử tồn tại y 0 sao cho 17 f ( x) Nếu y 0 thì rõ ràng f ( x) x không thể lớn hơn 0 với mọi x ¡ . yg ( x) Nếu y 0 thì phƣơng trình f ( x) x 0, x x(2 yx 1) 0, với mọi x ¡ . x 2 yx 2 yg ( x) yg ( x) 0 luôn có hai nghiệm phân biệt là 1 . Từ đây ta thấy rằng f ( x) 2y yg ( x) không thể lớn hơn hoặc bằng 0 trên cả trục thực đƣợc. Do đó điều kiện Slater không đƣợc thỏa mãn thì S-Bổ đề cũng không còn đúng. Ví dụ 1.2.1 Cho f ( x) 2 x1 g ( x) x12 2 x2 1 0 2 x1 x22 2 x2 1 0 x12 x22 Nếu 2 x1 2 x2 1 0 thì ta có x12 g ( x) x1 1, x2 x12 x22 2 x2 1 0 2 x1 2 x2 1 0 f ( x) 0 vô nghiệm. g ( x) 0 Vô lí. Suy ra hệ Vì g ( x) 2 x1 2 x1 x22 2 x2 1 ( x1 1) 2 ( x2 1) 2 3 0 khi, thí dụ, 1 nên hàm g ( x ) thỏa mãn điều kiện Slater. Ta thấy rằng tồn tại y 1 thoả mãn f ( x) yg ( x) x12 0, với mọi x ¡ 2 . x22 Ví dụ 1.2.2 Xét hệ f ( x) x12 g ( x) x1 x2 Ta thấy hệ trên vô nghiệm vì nếu g ( x) f ( x) x12 x22 3x1 x2 x22 3x1 x2 0 x1 x2 0 0 x12 0 thì 3x1 x2 x22 3x1 x2 0 và 0. Vô lí. Hàm g ( x ) thoả mãn điều kiện Slater, thí dụ, khi x1 0, x2 y 1 ta có f ( x) yg ( x) 0, với mọi x ¡ 2 . Định nghĩa 1.2.1 Cho A, B là hai ma trận vuông cấp n. Kí hiệu 0. Cho 18 AoB trace ( A.B), AoB là vết của ma trận tích AB. Định nghĩa 1.2.2 Ma trận A đƣợc gọi là ma trận xác định dương nếu xT Ax 0 với mọi x 0. Nhận xét 1.2.2 S-Bồ đề chỉ đúng với hai hàm toàn phƣơng, nếu tăng thêm một hàm thì S-Bồ đề là không đúng trong trƣờng hợp tổng quát. Ví dụ sau sẽ chỉ ra điều đó. Ví dụ 1.2.3 Xét f ( x) x1 x2 x2 x3 ; g ( x) 2 x12 x32 ; h( x) x22 . Rõ ràng hệ f ( x) x1 x2 x2 x3 g ( x) 2 x12 h( x ) là vô nghiệm vì nếu h( x) x22 x22 0 thì x2 x32 0 0 0 0. Do đó f ( x) Ta có 1 2 0 1 2 0 1 , B 2 0 1 2 0 0 A Xét ma trận X Ta có: 0 2 1 2 0 0 2 0 0 0 0 0 1 0 0 0 0 , C 1 0 0 0 0 1 0 0 0 0 x1 x2 x2 x3 0. . 19 1 2 0 1 2 0 1 2 0 1 2 0 0 AX 2 0 0 0 0 0 BX CX 0 2 1 2 0 0 1 1 2 1 1 0 0 0 0 1 0 2 1 2 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 2 1 2 0 0 1 0 0 0 0 1 2 0 1 0 0 0 1 4 0 0 2 0 0 0 0 0 2 0 0 0 0 0 AoX BoX CoX 2 0, 0, 0. Ta thấy X là ma trận đối xứng, nửa xác định dƣơng. Giả sử tồn tại y1 , y2 thoả mãn f ( x) y1 g ( x) y2h( x) 0, với mọi x ¡ 3. Khi đó A y1B y2C 0. Ta có ( A y1B y2C)oX Vậy A y1B AoX y1BoX y2CoX 2 0. y2C không thể là ma trận nửa xác định dƣơng đƣợc. Bây giờ chúng ta có thể phát biểu S-Bổ đề suy rộng, mà thực chất nó vẫn còn đúng với mọi hàm nửa liên tục dƣới bất kì, không đòi hỏi f ( x) và g ( x ) là hàm toàn phƣơng. 1.2.2 S-Bổ đề suy rộng Định lý 1.2.2 (S-Bổ đề suy rộng, [12]) Giả sử f ( x) và g ( x ) là những hàm toàn phƣơng trên ¡ n , W là tập hợp con đóng của ¡ n , D là tập hợp con đóng của ¡ và L( x, y ) f ( x) yg ( x) với y ¡ . Giả thiết 20 và các điều kiện sau đây thoả mãn: : inf sup L( x, y) x W y D (i) và tồn tại x* W sao cho g ( x * ) 0 hoặc D ¡ và tồn tại D ¡ a, b W sao cho g (a) 0 g (b). (ii) Với bất kỳ hai điểm a, b W sao cho g (a) 0 g (b) chúng ta có sup xinf L( x, y) a ,b . y D (iii) Khi đó tồn tại y D thoả mãn inf L( x, y ) x W . (1.12) Chứng minh Đầu tiên chúng ta chỉ ra rằng với bất kỳ số thực tập hợp hữu hạn E W tồn tại y D thoả mãn inf L( x, y) x E Từ đó x E và bất kì . (1.13) W , g ( x) 0 kéo theo L( x, y) f ( x) yg ( x) f ( x) với mọi y D. Ta chỉ cần chứng minh (1.13) đúng với mọi tập hợp hữu hạn E x W | g ( x) 0 . Khi ấy E E2 : x E | g ( x) 0 . Với mọi x E1 E2 với E1 : x E | g ( x) 0 , f ( x) . Khi g ( x) E ta định nghĩa ( x) : đó - Với mọi x E1 : ( x) 0 và L( x, y) - Với mọi x E2 : L( x, y) Về sau, nếu E1 y y ( x) ; ( x). ( x) 0 và ta có L( x, y ) thì min x E 1 với mọi x E1 khi 0 y min ( x). x E 1 Nếu E2 chúng ta có L( x, y ) Ngoài ra, nếu Ei với mọi x E2 khi y max ( x). x E2 ( x), , i 1,2 , thì do giả thiết (ii) ta có a arg min x E 1