Về điều kiện tối ưu cấp cao trong tối ưu không trơn

h 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 1 MỤC LỤC Trang MỤC LỤC……………………………………………………………………1 MỞ ĐẦU……………………………………………………………………...2 Chƣơng I ĐIỀU KIỆN TỐI ƢU CẤP CAO CHO BÀI TOÁN TỐI ƢU ĐƠN MỤC TIÊU KHÔNG TRƠN KHÔNG CÓ RÀNG BUỘC 1.1. Đạo hàm theo phƣơng cấp cao Ginchev và điều kiện tối ƣu cấp cao….4 1.2. Xấp xỉ đa thức và điều kiện đủ tối ƣu……………………………….. 13 1.3. Điều kiện tối ƣu cấp hai……………………………………………... 19 1.4. Cực tiểu cô lập…………………………………………………….......26 Chƣơng II ĐIỀU KIỆN TỐI ƢU CẤP CAO CHO BÀI TOÁN TỐI ƢU ĐA MỤC TIÊU KHÔNG TRƠN CÓ RÀNG BUỘC TẬP 2.1. Các khái niệm và kết quả bổ trợ………………………………………33 2.2. Điều kiện cần cấp cao cho cực tiểu địa phƣơng yếu………………….42 2.3. Điều kiện đủ cấp cao cho cực tiểu Pareto địa phƣơng chặt…………..44 2.4. Trƣờng hợp rQ  …………………………………………………..48 KẾT LUẬN…………………………………………………………………55 TÀI LIỆU THAM KHẢO…………………………………………………56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 MỞ ĐẦU Do nhu cầu của kinh tế và kỹ thuật, lý thuyết tối ƣu hoá đã phát triển mạnh mẽ và ngày càng thu đƣợc nhiều kết quả quan trọng. Lý thuyết các điều kiện tối ƣu là một bộ phận quan trọng của lý thuyết tối ƣu hoá. Các điều kiện tối ƣu cấp cao đƣợc nghiên cứu bởi nhiều tác giả và dƣới nhiều ngôn ngữ đạo hàm hoặc đạo hàm theo phƣơng khác nhau ( xem chẳng hạn [2] – [10] ). Năm 2002, I.Ginchev [5] đƣa ra khái niệm đạo hàm theo phƣơng cấp cao cho một hàm giá trị thực mở rộng và thiết lập các điều kiện tối ƣu cấp cao cho bài toán tối ƣu không trơn không ràng buộc. B.Jiménez ( [6] , 2002 ) đƣa ra khái niệm cực tiểu Pareto địa phƣơng chặt cấp m và cực tiểu Pareto địa phƣơng chặt cho bài toán tối ƣu đa mục tiêu. Sử dụng các khái niệm cực tiểu chặt của Jiménez [6], Đ.V.Lƣu và P.T.Kiên [7] đã dẫn các điều kiện cần và đủ cho cực tiểu Pareto địa phƣơng chặt cấp m và cực tiểu Pareto địa phƣơng chặt của bài toán tối ƣu đa mục tiêu không trơn với ràng buộc tập trong không gian định chuẩn, dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao của Ginchev [5]. Luận văn tập trung trình bày các điều kiện tối ƣu cấp cao dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao của I.Ginchev trên và dƣới cho bài toán tối ƣu đơn mục tiêu không trơn không có ràng buộc và bài toán đa mục tiêu không trơn với ràng buộc tập. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 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. Chƣơng I trình bày các điều kiện tối ƣu cấp cao của I.Ginchev [5] cho bài toán tối ƣu đơn mục tiêu không trơn, không có ràng buộc trong không gian Banach. Kết quả chỉ ra rằng với các điểm cực tiểu cô lập, điều kiện đủ cũng là điều kiện cần, và nhƣ vậy ta nhận đƣợc một điều kiện đặc trƣng cho cực tiểu cô lập. Chƣơng II trình bày các nghiên cứu về các điểm cực tiểu Pareto địa phƣơng chặt cấp m và cực tiểu Pareto địa phƣơng chặt của B.Jiménez [6] và các điều kiện cần và đủ cho các điểm cực tiểu yếu, cực tiểu Pareto địa phƣơng chặt cấp m và cực tiểu Pareto địa phƣơng chặt của Đ.V.Lƣu và P.T.Kiên [7] cho bài toán tối ƣu đa mục tiêu không trơn trong không gian định chuẩn với ràng buộc tập, dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao của I.Ginchev [5]. Cuối cùng, 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, tạo mọi điều kiện giúp đỡ tôi hoàn thành luận văn này. Tôi xin chân thành cảm ơn Ban chủ nhiệm Khoa Sau đại học, Ban chủ nhiệm Khoa Toán – Trƣờng ĐH Sƣ phạm – ĐH Thái Nguyên cùng các thầy giáo, 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 bạn cùng lớp cao học Toán K15 đã luôn quan tâm, động viên và giúp đỡ tôi trong suốt thời gian học tập và làm luận văn. Tác giả Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 Chƣơng I ĐIỀU KIỆN TỐI ƢU CẤP CAO CHO BÀI TOÁN TỐI ƢU ĐƠN MỤC TIÊU KHÔNG TRƠN KHÔNG CÓ RÀNG BUỘC Năm 2002, I.Ginchev [5] đƣa ra một khái niệm đạo hàm theo phƣơng cấp cao cho các hàm giá trị thực mở rộng xác định trên không gian Banach và thiết lập các điều kiện tối ƣu cấp cao cho bài toán tối ƣu không trơn không có ràng buộc. Các kết quả trình bày trong chƣơng này là của I.Ginchev [5]. 1.1. ĐẠO HÀM THEO PHƢƠNG CẤP CAO GINCHEV VÀ ĐIỀU KIỆN TỐI ƢU CẤP CAO Giả sử E là không gian Banach thực, là tập các số thực và { } {+ }     . Ta sẽ đƣa vào đạo hàm theo phƣơng cấp cao cho hàm không trơn :f E  tại điểm 0x E để dẫn điều kiện tối ƣu cấp cao cho bài toán tối ƣu : ( )f x min . Ở đây ta xét hàm f không trơn, thậm chí f không nhất thiết liên tục. Nhắc lại: điểm 0x E gọi là điểm cực tiểu địa phương của f nếu tồn tại lân cận U của x0 sao cho 0( ) ( ),f x f x x U   . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 Nếu bất đẳng thức này chặt với 0x x thì x 0 đƣợc gọi là cực tiểu địa phương chặt. Ký hiệu B và S tƣơng ứng là hình cầu đơn vị  : 1x E x  và mặt cầu đơn vị  : 1x E x  trong E. Ta chỉ cần xét các phần tử của S thay cho các phƣơng ( khác 0 ) trong E. Ký hiệu S là tôpô trên S. Tôpô S đƣợc dùng để định nghĩa đạo hàm theo phƣơng của f. Ta chỉ hạn chế xét tôpô mạnh, tôpô yếu, tôpô rời rạc và tôpô phản rời rạc ( tôpô tầm thƣờng ). Tôpô mạnh và tôpô yếu trên S cảm sinh tƣơng ứng từ tôpô mạnh ( tôpô chuẩn ) và tôpô yếu trên E. Mỗi tập con của S là mở đối với tôpô rời rạc, còn đối với tôpô phản rời rạc trên S, chỉ có hai tập mở là S và tập rỗng. Lấy u  S. Ta định nghĩa đạo hàm dưới cấp không của f tại x0 theo phƣơng u bởi công thức (0) 0 0 ( , ') ( 0, ) ( , ) ( ') t u u f x u lim inf f x tu     , trong đó 'u  S. Chú ý rằng trong giới hạn trên, ta bắt đầu với đạo hàm cấp không để bao hàm đƣợc cả những hàm không liên tục trong lý thuyết. Đạo hàm (0) 0( , )f x u luôn tồn tại và là một phần tử của . Với mỗi số nguyên dƣơng n và mỗi phƣơng u  S, ta thừa nhận rằng: đạo hàm dƣới cấp n ( ) 0( , )nf x u theo phƣơng u tồn tại và là một phần tử của khi và chỉ khi các đạo hàm ( ) 0( , )if x u , i = 0, 1, ..., n – 1 tồn tại trong . Ta định nghĩa đạo hàm theo phương dưới cấp n nhƣ sau : Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 1 ( ) 0 0 ( ) 0 ( , ') ( 0, ) 0 ! ( , ) ( ') ( , ) ! in n i n t u u i n t f x u lim inf f x tu f x u t i                . (1.1) Vì ( ) 0( , )if x u  với i = 0, ..., n – 1, chỉ có số hạng 0( ')f x tu trong (1.1) có thể nhận giá trị vô hạn. Do đó biểu thức  không thể xuất hiện trong (1.1). Ta sẽ dùng khái niệm đã đƣa vào để dẫn điều kiện tối ƣu cấp cao. Liên quan đến tính tối ƣu không trơn, các điều kiện cấp cao sau đây là quan trọng. Ở đây u  S là một phƣơng cố định và n là một số dƣơng.  00( , )S x u (0) 0 0( , ) ( )f x u f x  ,  0( , )nS x u (0) 0 0 ( ) 0( , ) ( ), ( , ) 0 ( 1,..., 1)if x u f x f x u i n     và ( ) 0( , ) 0nf x u  ,  00 ( , )N x u (0) 0 0( , ) ( )f x u f x  ,  0n ( , )N x u Nếu (0) 0 0( , ) ( )f x u f x  và ( ) 0 ( , ) 0 ( 1,..., 1)if x u i n    thì ( ) 0( , ) 0nf x u  . Định lý 1.1( Điều kiện cần cấp cao) Giả sử x0 là điểm cực tiểu địa phương của hàm :f E  . Giả sử u  S và n = n(u) là số nguyên không âm tuỳ ý sao cho tất cả các đạo hàm ( ) 0( , )if x u , i = 0,..., n, tồn tại. Khi đó tất cả các điều kiện  0i ( , )N x u , i = 0, ..., n đều thỏa mãn. Chứng minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 Lấy  > 0 sao cho 0( ) ( )f x f x với 0x x   . Lấy u  S. Với 'u  S và 0 t   , ta có 0 0( ') ( ) 0f x tu f x   . Do đó, (0) 0 0( , ) ( )f x u f x  . Đây chính là điều kiện  00 ( , )N x u . Mặt khác, giả sử với n = n(u), các đạo hàm ( ) 0( , )if x u , i = 0,..., n tồn tại, (0) 0 0( , ) ( )f x u f x  và ( ) 0( , ) 0 ( 1,..., 1)if x u i n    . Khi đó, 1 0 (0) 0 ( ) 0 1 ! ( ') ( , ) ( , ) ! in i n i n t f x tu f x u f x u t i              = 0 (0) 0! ( ') ( , ) 0 n n f x tu f x u t       . Vì vậy ( ) 0( , ) 0nf x u  . Đây chính là điều kiện  0n ( , )N x u .  Để có điều kiện đủ, ta cần có bổ đề sau đây Bổ đề 1.1 Giả sử hàm :f E  . Lấy 0x E và u S sao cho tồn tại một số nguyên không âm n để điều kiện  0nS ( , )x u thoả mãn. Khi đó, tồn tại số ( ) 0u   và một lân cận U = U(u)  S của u ( đối với tôpô S ) sao cho 0 0( ') ( )f x tu f x  với mọi 0 < t < ( )u và 'u  U(u). Chứng minh Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 Giả sử  00( , )S x u đúng. Lấy số  thoả mãn (0) 0 0( , ) ( )f x u f x   . Từ định nghĩa của (0) 0( , )f x u suy ra tồn tại ( ) 0u   và lân cận U = U(u)  S của u sao cho 0 0( ') ( )f x tu f x   với mọi 0 < t <  và 'u  U(u). Giả sử điều kiện  0( , )nS x u thoả mãn với số dƣơng n nào đó, và số  thoả mãn ( ) 0( , ) 0nf x u    . Do (0) 0 0 ( ) 0( , ) ( ), ( , ) 0 ( 1,..., 1)if x u f x f x u i n     , nên ta có 1 0 0 0 ( ) 0 0 1 ! ( ') ( ) ( ') ( , ) ! ! in i n n i n t f x tu f x f x tu f x u t n t i               . Theo định nghĩa của ( ) 0( , )nf x u , với số dƣơng t đủ nhỏ và 'u đủ gần u, ta có 0 0 1( ') ( ) 0 ! nf x tu f x t n     .  Định lý 1.2 ( Điều kiện đủ cấp cao) Giả sử hàm :f E  , 0x E và S là compact đối với tôpô S. Giả sử với mỗi u  S, tồn tại số nguyên không âm n = n(u) sao cho điều kiện  0( , )nS x u thoả mãn. Khi đó, x0 là cực tiểu địa phương chặt của hàm f. Chứng minh Theo bổ đề 1.1. với mỗi u  S, tồn tại số ( ) 0u   và một lân cận U = U(u)  S của u ( đối với tôpô S ) sao cho Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 0 0( ') ( )f x tu f x  với mọi 0 < t < ( )u và 'u  U(u). Do S compact cho nên S nằm trong hợp một số hữu hạn các lân cận U(u), tức là S  ( U(u1)  ... U(us)) với u1, ..., us nào đó. Đặt 0 = min ( 1( )u ,..., ( )su ). Khi đó, 0 0( ') ( )f x tu f x  với mọi 'u  S và 0 < t < 0 . Điều này có nghĩa là 0( ) ( )f x f x với mọi 0 < 0 0x x   , và do đó x 0 là điểm cực tiểu địa phƣơng chặt của f.  Hệ quả 1.1 Giả sử E là không gian Banach hữu hạn chiều và S là tôpô mạnh trên S. Hàm :f E  và đạo hàm dưới của f được xác định theo tôpô S. Giả sử với mỗi u  S, tồn tại số nguyên không âm n = n(u) sao cho điều kiện  0( , )nS x u thoả mãn. Khi đó, x0 là điểm cực tiểu địa phương chặt của f. Ví dụ 1.1 Cho E là không gian Banach tùy ý. Hàm :f E  xác định bởi f(x) = x . Hiển nhiên x0 = 0 là điểm cực tiểu chặt của f. Giả sử S là tôpô phản rời rạc trên S. Khi đó mặt cầu đơn vị S là compact. Với mỗi phƣơng u  S ta có (0)(0, ) 0 (0)f u f   và (1)(0, ) 1 0u   . Vậy x0 là cực tiểu địa phƣơng chặt theo điều kiện cấp một trong định lý 1.2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 Chú ý rằng với các cách chọn tôpô S khác, chẳng hạn nếu không gian E trong ví dụ 1.1 là vô hạn chiều và tôpô mạnh thay thế cho tôpô phản rời rạc thì điểm x0 = 0 không là cực tiểu bởi vì mặt cầu S không compact. Giả sử S là tôpô rời rạc. Vì tập một điểm là mở, sự hội tụ ( , ') ( 0, )t u u  có nghĩa đơn giản là 0t  và ta nhận đƣợc đạo hàm Dini. Tuy nhiên, đối với tôpô rời rạc, S là compact chỉ nếu S là tập hữu hạn, nghĩa là chỉ trong trƣờng hợp một chiều. Ngoài trƣờng hợp một chiều, đạo hàm theo phƣơng dƣới Dini không thể sử dụng đƣợc điều kiện đủ của định lý 1.2. Đạo hàm Dini hữu ích trong điều kiện cần của định lý 1.1 bởi vì việc tính toán giới hạn 0t  thuận tiện hơn so với giới hạn ( , ') ( 0, )t u u  . Trong trƣờng hợp tôpô S trên S là tôpô mạnh, ta sử dụng đạo hàm theo phƣơng dƣới Hadamard. Hệ quả 1.1 cho thấy rằng đạo hàm Hadamard là hữu ích cho các điều kiện đủ trong không gian Banach hữu hạn chiều. Ví dụ 1.2 Cho E = l 2 là không gian Hilbert thực gồm các dãy x = ( x1, ..., xn , ...) trong đó 2 2 1 i i x x      . Với mỗi x , đặt  1 2, ,..., ,...nx x x x . Lấy c = ( c1, ..., cn , ...) là một vectơ cố định trong l 2 mà tất cả các thành phần đều dƣơng. Trên l2 xét hàm 1 ( ) , i i i f x c x c x     , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 ( ở đây là tích vô hƣớng trên l2). Hiển nhiên x0 = 0 là điểm cực tiểu chặt của f. Với mỗi u = ( u1, ..., un , ...) cố định thuộc mặt cầu đơn vị S  l 2 , các điều sau thoả mãn: 1) (0) 0( , ) 0f x u  đối với mọi tôpô S trên S. 2) (1) 0( , ) ,f x u c u   nếu S là các tôpô rời rạc, mạnh hoặc yếu trên S và (1) 0( , ) 0f x u  nếu S là tôpô phản rời rạc. Chứng minh Lấy 1' ( ',..., ',...)nu u u  S và t > 0. Ta có 0 < 0( ')f x tu = , 't c u   t c . Từ đó suy ra (0) 0( , )f x u = 0. Để có đạo hàm dƣới cấp một, ta để ý rằng 0 (0) 01 ( ') ( , )f x tu f x u t      = 1 ( ')f tu t = , 'c u  . Do đó, (1) 0 '( , ) , ' 0u uf x u lim inf c u     . Sự hội tụ ku u theo tôpô rời rạc nghĩa là ku trùng với u từ một lúc nào đó trở đi. Khi đó ta có kết luận 2) cho đạo hàm Dini. Kết luận cũng nhƣ thế cho đạo hàm Hadamard, bởi vì phép toán x x và tích vô hƣớng là liên tục theo tôpô mạnh. Sự hội tụ ku u theo tôpô yếu kéo theo , ku u   ,u u  = 1. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 Do đó, 2 2 2 2 , , 2 , ,k k k k k ku u u u u u u u u u u u               = 2 – 2 , ku u   0. Điều đó nghĩa là ku u theo tôpô mạnh. Do vậy đạo hàm (1) 0( , )f x u theo tôpô yếu và tôpô mạnh trên S là trùng nhau. Lấy  > 0. Do c  l 2 nên tồn tại số nguyên dƣơng k sao cho i i k c     . Nếu 'u  S mà 'iu = 0 với i < k thì , 'c u    . Do đó, (1) 0( , )f x u = 0, nếu S là tôpô phản rời rạc.  Ví dụ trên đã đặt ra câu hỏi sau đây: Với một hàm bất kỳ :f E  có x 0 là cực tiểu chặt, có luôn tồn tại hay không một tôpô S sao cho mặt cầu đơn vị S là compact theo tôpô S và x0 là điểm cực tiểu chặt đƣợc nhận biết theo định lý 1.2 ( xác định các đạo hàm của f theo S )? Câu trả lời là phủ định ở trong mục 1.4. Kết quả khẳng định rằng nếu x0 là điểm cực tiểu theo tôpô S nào đó thì nó cũng là điểm cực tiểu theo tôpô phản rời rạc. Một cách chính xác hơn, ta thấy rằng định lý 1.2 chỉ đặc trƣng cho điểm cực tiểu cô lập. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 Ví dụ 1.3 Lấy E = và ( ) m f x x   với m là số nguyên không âm nào đó và 0 <  < 1. Hiển nhiên x0 = 0 là điểm cực tiểu chặt. Các đạo hàm Dini dƣới là 1) ( ) ( )(0,1) (0, 1)i if f   = 0, i = 0, ..., m . 2) ( 1) ( 1)(0,1) (0, 1)m mf f      . Do đó, x0 = 0 là điểm cực tiểu địa phƣơng chặt cấp m + 1 theo điều kiện đủ của định lý 1.2. 1.2. XẤP XỈ ĐA THỨC VÀ ĐIỀU KIỆN ĐỦ TỐI ƢU Trong mục này, ta mô tả đạo hàm theo phƣơng dƣới của hàm :f E  dƣới ngôn ngữ của phép xấp xỉ đa thức địa phƣơng và dẫn các điều kiện tối ƣu. Ký hiệu Pn , n = 0, 1, ... là tập các đa thức một biến bậc n hoặc nhỏ hơn. Với hai đa thức  ,  , ta viết ( ) ( ) ( )nt t o t   khi 0t  (1.2) nếu với mỗi số  > 0, tồn tại  > 0 sao cho ( ) ( ) nt t t    với 0 < t <  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 Định lý 1.3 Các đa thức 0 ( ) n i i i t a t   và 0 ( ) n i i i t b t   thoả mãn ( ) ( ) ( )nt t o t   khi 0t  , nếu ai = bi, i = 0,...,n ( hay   ), hoặc tồn tại số nguyên dương k sao cho ai = bi, i = 0,...,k – 1, và ak  bk . Chứng minh Giả sử   và ai = bi, i = 0,...,k – 1. Chia hai vế bất đẳng thức (1.2) cho tk và qua giới hạn khi 0t  , ta đƣợc ak  bk. Từ đó ta suy ra điều phải chứng minh.  Ta nói đa thức  là cận dưới bậc n của :f E  tại x0 theo phƣơng u  S nếu với mỗi  > 0, tồn tại  > 0 và lân cận U = U(u) của u trong S sao cho 0( ) ( ') nt f x tu t    với 0 < t <  , 'u  U. Tính chất này còn đƣợc viết dƣới dạng 0( ) ( ') ( )nt f x tu o t    khi ( , ') ( 0, )t u u  . Ta kí hiệu 0( , , )nP f x u  là tập các đa thức nP là cận dƣới của f tại x0 theo phƣơng u. Một đa thức 0( , , )nP f x u  đƣợc gọi là cận dưới đúng của f tại x0 theo phƣơng u nếu ( ) ( ) ( )nt t o t   khi 0t  với mỗi 0( , , )nP f x u  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 Định lý 1.4 ( [5] ) Đạo hàm dưới ( ) 0( , )nf x u của hàm :f E  tồn tại và là một phần tử của khi và chỉ khi cận dưới đúng bậc n của f tại x0 theo phương u tồn tại và khi đó cận này là đa thức Taylor dưới 0 ( ) 0 0 1 ( , , , ) ( , ) ! n n i i i T f x u t f x u t i     . Hàm :f E  có đạo hàm dưới cấp n ( ) 0( , )nf x u khi và chỉ khi cận dưới đúng bậc n – 1 tồn tại ( và nó chính là đa thức Taylor dưới 1 0( , , , )nT f x u t ). Trong trường hợp đó ta có  , nếu 0( , , )nP f x u  rỗng,  , nếu 0( , , )nP f x u  khác rỗng, nhưng f không có cận dưới đúng bậc n. Sử dụng định lý 1.4, các điều kiện cần và đủ tối ƣu của mục 1.1 có thể đƣợc biểu diễn dƣới ngôn ngữ của phép xấp xỉ đa thức. Ở đây, ta chỉ phát biểu lại điều kiện đủ tối ƣu của định lý 1.2. Định lý 1.5 Cho hàm :f E  và 0x E . Giả sử S là tập compact đối với tôpô S. Giả sử với mỗi u  S, tồn tại số nguyên không âm n = n(u) và cận dưới bậc n 0 ( ) n i i i t a t   của f tại x0 theo phương u thoả mãn 0( ) , 0, 0 , 1, i f x i a i      ( ) 0( , ) nf x u  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 và bất đẳng thức tương ứng với i = n là chặt. Khi đó, x0 là điểm cực tiểu địa phương chặt của f. Chứng minh Trƣớc hết giả sử tất cả các đạo hàm dƣới ( ) 0( , )if x u , i = 0,...,n tồn tại và hữu hạn. Do đó, 0( ) ( , , , ) ( )n nt T f x u t o t   khi 0t  , trong đó 0( , , , )n nT T f x u t  là đa thức Taylor dƣới duy nhất cấp n. So sánh hệ số của  và nT ta thấy điều kiện  0( , )nS x u đƣợc thoả mãn. Giả sử ( ) 0( , )kf x u vô hạn với k nào đó. Đa thức  là một cận dƣới bậc k – 1 và so sánh hệ số của nó với hệ số của đa thức Taylor dƣới cấp k – 1, ta sẽ thu đƣợc điều kiện cần  0i ( , )N x u , i = 0,..., k – 1. Nếu một bất đẳng thức chặt nào đó trong số các điều kiện này đúng và m là chỉ số i đầu tiên thoả mãn tính chất này thì điều kiện này thực chất chính là  0( , )mS x u . Nếu không có bất đẳng thức chặt nào trong số các điều kiện này xuất hiện thì ( ) 0( , )kf x u   và  0( , )kS x u đúng. Với mỗi trƣờng hợp đƣa ra, điều kiện đủ của định lý 1.2. đều thoả mãn. Do đó, x0 là điểm cực tiểu địa phƣơng chặt.  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 Ví dụ 1.4 Lấy E = và ( ) m f x x   với m là số nguyên không âm nào đó và 0 <   1 ( so sánh với ví dụ 1.3.). Khi đó, đa thức 11( ) 2 mt t  hiển nhiên là cận dƣới bậc m + 1 của f tại x0 = 0 theo cả hai phƣơng u = 1 và u = – 1. Vậy  thoả mãn điều kiện đủ của định lý 1.5, do đó x0 = 0 là điểm cực tiểu địa phƣơng chặt của f . Ví dụ 1.5 Cho hàm :f  xác định nhƣ sau f (x) = 211 sin , 0, 0 , 0. x x khi x x khi x               Hiển nhiên, x0 = 0 là điểm cực tiểu chặt nếu  > 0 ( không là cực tiểu chặt nếu  = 0 ) và x 0 không là cực tiểu nếu  < 0. Nếu  > 0 thì điểm cực tiểu chặt x0 = 0 có thể tìm đƣợc bằng cách áp dụng định lý 1.5 khi lấy phƣơng u = 1, u = – 1 và đa thức 21( ) 2 t t  . Trƣờng hợp  < 0, ta có x 0 không phải là điểm cực tiểu. Tiếp theo ta chỉ ra rằng đạo hàm theo phƣơng cấp cao có thể biểu diễn dƣới ngôn ngữ hiệu chia. Giả sử :f E  . Ta nhắc lại: miền hữu hiệu của hàm f là tập   : ( ) dom f x E f x     . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 Lấy 0x E và u0, ..., un  S là các phƣơng cho trƣớc. Giả sử t0, ..., tn là các biến thực dƣơng khác nhau và 0' ,..., ' Snu u  là các biến phƣơng. Ta định nghĩa hiệu chia cấp n 0 0 0( , ' ,..., ' , ,..., ) n n n nf f x u u t t  nhƣ sau: 0 0 0 0 0 1 ( ' ) ( , ' ,..., ' , ,..., ) ( ) n n i i n n i n i f x t u f x u u t t t     = 0 0 0 ( ' ) ( ) n i i n i i j j j i f x t u t t       Ở đây 1 0 ( ) ( ) n n j j t t t     và 1( )n t   là đạo hàm của 1( )n t  . Hơn nữa, ta đặt 0( ) 1t  . Ta thừa nhận rằng : hiệu chia cấp n xác định khi và chỉ khi 0 ' i ix t u dom f  trừ ra nhiều nhất một số hạng. Nó hữu hạn khi và chỉ khi tất cả các giá trị 0( ' )i if x t u là hữu hạn. Hiệu chia còn có thể đƣợc định nghĩa quy nạp nhƣ sau 0 0 0 0 0 0 0( , ' , ) ( ' )f x u t f x t u   , và 0 0 0( , ' ,..., ' , ,..., ) n n nf x u u t t =  1 0 ' ' '0 2 0 2( , ,..., , , ,..., , )n n n n nf x u u u t t t   1 0 ' ' '0 2 1 0 2 1( , ,..., , , ,..., , )n n n n nf x u u u t t t      1n nt t  ( Nếu   nằm trong số các giá trị của hàm f thì các chỉ số cần phải sắp xếp lại). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 19 Tính chất sau đây là một trong số các tính chất chính của hiệu chia và đƣợc sử dụng khi chứng minh biểu diễn lại đạo hàm theo phƣơng qua hiệu chia. 0( ')f x tu = 1 0 0 0 1 ( , ' ,..., ' , ' ,..., ' ) ( ) n i i i i i f x u u t t t    + 0 0 1 0 1( , ' ,..., ' , ', ' ,..., ' , ) ( ) n n n nf x u u u t t t t  . Ta giả thiết rằng 0 ' i ix t u dom f  , i = 0, ..., n – 1 và do đó cùng lắm thì 0( ')f x tu và hiệu chia cuối cùng trong vế phải có thể nhận giá trị vô hạn. Mối quan hệ giữa đạo hàm theo phƣơng và hiệu chia đƣợc chỉ ra trong định lý sau đây. Định lý 1.6 ( [5] ) Đạo hàm theo phương ( ) 0( , )nf x u , n = 0, 1,..., được biểu diễn quy nạp dưới ngôn ngữ hiệu chia cùng với dãy các số A0, ..., An  như sau A0 : = 0 0 ( , ') ( 0, ) ( , ', ) t u u lim inf f x u t    = (0) 0( , )f x u . Đạo hàm ( ) 0( , )nf x u , n  1, tồn tại khi và chỉ khi các số A0,..., An-1 xác định và hữu hạn. Khi đó, An := 0 0 1 0 1 ( , ') ( 0, ) ( , ,..., , ', ,..., , )k s s s sn n st u u lim inf lim f x u u u t t t     = 1 !n ( ) 0( , )nf x u , trong đó 0 1 0 1( ,..., , ,..., ) s s s s n nu u t t  là dãy tuỳ ý thoả mãn ba điều kiện sau: 1) 0sit  , s iu u khi s , với i = 0, ..., n – 1, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 20 2) 0 s si ix t u dom f  với i = 0, 1, ..., n – 1, 3) Ai = 0 0 0 ( , ,..., , ,..., ) i s s s s i i s lim f x u u t t với i = 0, 1, ..., n – 1. 1.3. ĐIỀU KIỆN TỐI ƢU CẤP HAI Đạo hàm cấp một (1) 0( , )f x u của hàm :f E  có thể biểu diễn nhƣ sau (1) 0( , )f x u = 1 0 (0) 0 1 ( , ' ) ( 0, ) 1 ( ' ) ( , ) u u lim inf f x tu f x u t        . (1.3) Để tiện cho việc khai triển đạo hàm cấp hai, ta đƣa ra ký hiệu 0 2 1( , , , ' , ' , )f t x u u u = 0 2 1 ( ' ) 1 f x tu    – 0 1 1 ( ' ) (1 ) f x tu     + (0) 01 ( , )f x u   . (1.4) Ta xét khai triển dƣới đây với giả thiết rằng t > 0 là cố định, u  S, đạo hàm dƣới cấp không (0) 0( , )f x u và đạo hàm dƣới cấp một (1) 0( , )f x u là hữu hạn, ' ' 1 2, Su u  và  là số thực dƣơng thoả mãn 0 ' 1 x tu dom f  . Với giả thiết (0) 0( , )f x u và (1) 0( , )f x u hữu hạn, ta nhận đƣợc biểu diễn sau đây cho đạo hàm dƣới cấp hai (2) 0( , )f x u : (2) 0( , )f x u = 2 0 (0) 0 (1) 0 22 ( , ' ) ( 0, ) 2! ( ' ) ( , ) . ( , ) t u u lim inf f x tu f x u t f x u t          Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21 =  2 0 (0) 0 22 ( , ' ) ( 0, ) 2! ( ' ) ( , ) t u u lim inf f x tu f x u t        1 0 (0) 0 1 ( , ' ) ( 0, ) 1 ( ' ) ( , ) u u t lim inf f x tu f x u t          = 2 1 0 22 ( , ' ) ( 0, ) ( , ' ) ( 0, ) 2(1 ) 1 ( ' ) 1t u u u u lim inf lim sup f x tu t         0 (0) 0 1 1 1 ( ' ) ( , ) (1 ) f x tu f x u           = 2 1 0 2 12 ( , ' ) ( 0, ) ( , ' ) ( 0, ) 2 ( , , , ' , ' , )f t u u u u lim inf lim sup t x u u u t       . (1.5) Trong các đẳng thức trên, sự hội tụ 1( , ' ) ( 0, )u u   chỉ theo những giá trị 1( , ' )u mà 0 1' x tu dom f  . Để đơn giản, ta xét trƣờng hợp hàm f liên tục tại x0 . Khi đó ta có (0) 0 0( , ) ( )f x u f x  và 2 0 0 1 2( , ' , ' , ' ,0, , )f x u u u t t = 0 22 1 1 ( ' ) 1 f x tu t      0 (0) 0 1 1 1 ( ' ) ( , ) (1 ) f x tu f x u          . Sử dụng phép biểu diễn này và định lý 1.6, ta có thể thu đƣợc sự biểu diễn (1.5). Từ các định lý 1.1, 1.2 ta có định lý sau cho trƣờng hợp cấp hai. Định lý 1.7 ( Điều kiện cấp hai ) Cho hàm :f E  và 0 Ex  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22 (A) Điều kiện cần: Giả sử x0 là điểm cực tiểu địa phương của f, u  S. Khi đó, một trong ba điều kiện sau đây được thoả mãn: (a0) (0) 0 0( , ) ( )f x u f x  , (a1) Nếu (0) 0 0( , ) ( )f x u f x  thì (1) 0( , ) 0f x u  , (a2) Nếu (0) 0 0( , ) ( )f x u f x  và (1) 0( , ) 0f x u  thì (2) 0( , ) 0f x u  . (B) Điều kiện đủ:Giả sử S compact đối với tôpô S. Giả sử với mỗi u  S, một trong ba điều kiện sau được thoả mãn: (b0) (0) 0 0( , ) ( )f x u f x  , (b1) (0) 0 0( , ) ( )f x u f x  và (1) 0( , ) 0f x u  , (b2) (0) 0 0( , ) ( )f x u f x  , (1) 0( , ) 0f x u  và (2) 0( , ) 0f x u  . Khi đó x0 là điểm cực tiểu địa phương chặt của f. Ở đây đạo hàm (1) 0( , )f x u và (2) 0( , )f x u được biểu diễn lần lượt bởi (1.3) và (1.5). Ví dụ 1.6 Lấy E = 2 và hàm :f E  xác định bởi 2( ) 2 ( )f x r r r sin   , trong đó ( , )r  là toạ độ cực của x , nghĩa là x = (x1, x2) = ( , )rcos rsin  . Hiển nhiên x0 = (0,0) là điểm cực tiểu chặt của f(x). Ta có thể áp dụng điều kiện đủ của định lý 1.7 để suy ra x0 là cực tiểu. Chứng minh Hàm f liên tục, do đó với phƣơng bất kỳ u = ( , )cos sin  ta có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 23 (0) 0 0( , ) ( )f x u f x  = 0. Nếu 0sin  thì 2( ) 2f x r r sin   , 0 r sin  , và (1) 0( , ) 2f x u sin  > 0. Trong trƣờng hợp nếu u = ( 1, 0) ta đƣợc (1) 0( , ) 0f x u  và do đó điều kiện cấp hai phải sử dụng để thiết lập tính tối ƣu của x0. Xét trƣờng hợp u = (1, 0). Phƣơng đơn vị v = ( , )cos sin  với 0  đủ nhỏ gần u tuỳ ý. Các điểm tv và tv có toạ độ cực lần lƣợt là ( , )t  và ( , )t  . Do đó với 0 t sin  và 0 1  ta có 0 2( ) 2f x tv t tsin   , và 0 2( ) ( ) 2f x tv t tsin       . Do đó 0 2 1 ( , , , , , ) 1f t x v v u t    . Bây giờ ta chỉ ra rằng điều kiện cấp hai trong định lý 1.7 thoả mãn. Với u = (1, 0) , ta lấy lân cận của các vectơ đơn vị W =  w w w 2 = ( , ) :w cos sin    , V =  v v v 1 = ( , ) :v cos sin    , trong đó 1 20   . Chọn t < 2sin và lấy 0 <  < 1. Nếu v  V , ta có 0( )f x tv = 2 2 1 2 2 2 . , ( ) , 3 2 . , 0 ( ), v v v v t t sin arcsin t t t sin arcsin t                    Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 và 0( )f x tv  2 2t . Dấu bằng xảy ra khi ( )v arcsin t  . Khi đó, 0 2 ( , ) ( 0, ) 2 ( , , , , , )f v u lim sup t x w v u t     = 0 2 ( , ) ( 0, ) 2 2 ( ) (1 ) 1v u lim sup f x tw t            = 0 2 2 ( )f x tw t  . Tƣơng tự, với w  W , 0( )f x w = 2 w w 2 2 w w 2 , ( ) , 3 2 , 0 ( ), t tsin arcsin t t tsin arcsin t              và ƣớc lƣợng 0( )f x tw  2t . Dấu bằng xảy ra khi w ( )arcsin t  . Do đó, (2) 0( , )f x u = 0 2 ( , ) ( 0, ) 2 ( ) t w u lim inf f x tw t   = 2 > 0. Do tính đối xứng nên ta cũng có đẳng thức nhƣ vậy với phƣơng u = ( –1, 0 ). Do đó, các điều kiện đủ của định lý 1.7 thoả mãn. Nhƣ vậy, tính tối ƣu của điểm x0 có thể suy ra từ định lý này.  Ta so sánh kết quả trên với một số kết quả khác. Giả sử :f E  với E là không gian hữu hạn chiều, f liên tục và tại x 0 có các đạo hàm sau: (1) 0( , )BZf x v = 0 0 0 1 ( ) ( ) t lim f x tv f x t     , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 (2) 0( , , )BZf x v z = 0 2 0 (1) 0 2 0 1 ( ) ( ) ( , )BZ t lim f x tv t z f x tf x v t       , với v, z  S tuỳ ý. Đạo hàm (1) 0( , )BZf x v là đạo hàm theo phƣơng thông thƣờng cấp một, (2) 0( , , )BZf x v z là đạo hàm parabolic cấp hai theo nghĩa BenTal – Zowe [3]. Định lý sau đây cho ta các điều kiện cần dƣới ngôn ngữ các đạo hàm parabolic. Định lý 1.8 ( [3] ) Nếu x0 là điểm cực tiểu địa phương của hàm :f E  thì (BZ1) (1) 0( , ) 0BZf x v  với mọi v  S, (BZ2) (1) 0( , ) 0BZf x v  kéo theo (2) 0( , , ) 0BZf x v z  với mọi z  S. Ta chỉ ra rằng với._.