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

Luận văn đã trình bày lý thuyết các điều kiện tối ƣu cấp cao cần và đủ dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao trên và dƣới Ginchev cho các điểm cực tiểu, cực tiểu chặt của bài toán tối ƣu đơn mục tiêu không ràng buộc, không trơn trong không gian Banach của I.Ginchev ( 2002 ), 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, 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 của Đ.V.Lƣu – P.T.Kiên ( 2007 ), cùng một số tính chất của 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 ( 2002 ). Các kết quả của luận văn cho ta thấy rằng các khái niệm đạo hàm theo phƣơng cấp cao của I.Ginchev là thích hợp trong việc dẫn các điều kiện tối ƣu cấp cao. Việc nghiên cứu 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 trên và dƣới của I.Ginchev cho các lớp bài toán tối ƣu đa mục tiêu không trơn khác nhau cần đƣợc tiếp tục nghiên cứu và phát triển.

pdf59 trang | Chia sẻ: aloso | Lượt xem: 1743 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Luận văn Về điều kiện tối ưu cấp cao trong tối ưu không trơn, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
heo 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 lớp các hàm đã xét, định lý 1.7 kéo theo định lý 1.8. Thật vậy, giả sử các điều kiện trong định lý 1.7 thoả mãn. Hiển nhiên ta có bất đẳng thức (1) 0 (1) 0( , ) ( , ) 0BZf x v f x v  Nhƣ vậy điều kiện (BZ1) thoả mãn. Bây giờ ta giả sử (1) 0( , ) 0BZf x v  . Từ các bất đẳng thức (1) 0 (1) 00 ( , ) ( , ) 0BZf x v f x v   ta suy ra (1) 0( , ) 0f x v  . Do đó (2) 0( , ) 0f x v  . Theo định nghĩa của (2) 0( , , )BZf x v z , (2) 0( , , )BZf x v z = 0 0 2 0 1 ( ( )) ( ) t lim f x t v tz f x t      Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26  0 (0) 0 (1) 0 2 ( , ') ( 0, ) 1 2 ( ( )) ( , ) . ( , ) 2 t v v lim inf f x t v tz f x v t f x v t           = (2) 01 ( , ) 2 f x v . Do đó, bất đẳng thức (2) 0( , ) 0f x v  kéo theo (2) 0( , , ) 0BZf x v z  , hay điều kiện (BZ2) thoả mãn. Ví dụ sau đây chỉ ra rằng các điều kiện cần (BZ1) và (BZ2) của định lý 1.8 không kéo theo các điều kiện cần (a0) – (a2) của định lý 1.7. Ví dụ 1.7 Hàm 2:f  xác định bởi f (x1, x2) = 3 3 3 2 1 1 1 2 1 3 3 3 1 2 1 1 2 1 1 2 , 0, , 2 3 3 2 , 0, , 2 0 x x x x x x x x x x x x                  Hiển nhiên, x0 = (0, 0) không là điểm cực tiểu. Ta có (1) 0 (2) 0( , ) ( , , ) 0BZ BZf x u f x u z  với mọi u  S, mọi z . Với u0 = (1, 0) ta có 0 (1) 0 00 ( ) ( , )f x f x u  và (2) 0 0( , ) f x u    Nhƣ vậy các điều kiện cần (BZ1) và (BZ2) của định lý 1.8 không kéo theo các điều kiện cần (a0) – (a2) của định lý 1.7. , trong các trƣờng hợp khác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 1.4. CỰC TIỂU CÔ LẬP Trong mục này, ta mô tả điểm cực tiểu thoả mãn các điều kiện đủ của định lý 1.2 và trả lời câu hỏi đã đặt ra sau ví dụ 1.2. Giả sử :f E  và n0 là một số nguyên không âm. Nhắc lại [10]: điểm cực tiểu x0  E của f gọi là cực tiểu địa phương cô lập cấp n0 của f nếu tồn tại lân cận U của x 0 và hằng số  > 0 sao cho 00 0( ) ( ) n f x f x x x   với mọi x  U  0x . (1.6) Ta nói x 0 là điểm cực tiểu địa phương cô lập của f có nghĩa là x0 là điểm cực tiểu địa phƣơng cô lập cấp n0 của f với n0 là một số nguyên không âm nào đó. Trong trƣờng hợp n0 = 0, bất đẳng thức (1.6) trở thành 0( ) ( )f x f x   với mọi x  U  0x . (1.7) Do bất đẳng thức (1.6) là chặt nên 0( ) f x    tại điểm cực tiểu địa phƣơng cô lập x0. Định lý 1.9 ( Điều kiện cần ) Giả sử x0 là điểm cực tiểu địa phương cô lập cấp n0 của hàm :f E  . Khi đó, với u  S bất kỳ, tồn tại số nguyên không âm n(u)  n0 sao cho điều kiện  0( ) ( , )n uS x u thoả mãn. Chứng minh Giả sử có (1.6). Trƣớc hết ta chỉ ra rằng (0) 0 0( , ) ( )f x u f x  , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 và bất đẳng thức là chặt nếu x0 là điểm cực tiểu cô lập cấp 0. Giả sử ngƣợc lại rằng (0) 0 0( , ) ( )f x u f x  . Theo định nghĩa đạo hàm dƣới cấp không thì tồn tại dãy 0kt  và ku  S sao cho 0 0( ) ( ) ( )kk kf x t u f x f x   ,trong đó 0 0k k kx t u x   . Bất đẳng thức này mâu thuẫn với bất đẳng thức (1.6). Giả sử x0 là điểm cực tiểu địa phƣơng cô lập cấp 0. Bây giờ ta chứng minh rằng (0) 0 0 0( , ) ( ) ( )f x u f x f x   . Giả sử bất đẳng thức này không đúng. Khi đó tồn tại dãy 0kt  và ku  S sao cho 0 0( ) ( ) ( )kk kf x t u f x f x    , trong đó 0 0k k kx x t u x  . Bất đẳng thức này mâu thuẫn với bất đẳng thức (1.7). Giả sử n  n0 là số nguyên dƣơng thoả mãn (0) 0 0( , ) ( )f x u f x  , (1) 0 ( 1) 0( , ) ... ( , ) 0nf x u f x u    . Ta chứng minh rằng ( ) 0( , ) 0nf x u  và bất đẳng thức là chặt nếu x0 là điểm cực tiểu địa phƣơng cô lập cấp n. Giả sử ngƣợc lại rằng ( ) 0( , ) 0nf x u  . Theo định nghĩa đạo hàm theo phƣơng dƣới cấp n thì tồn tại dãy 0kt  và ku  S sao cho 1 0 ( ) 0 0 ! ( ) ( , ) ! in i k kn ik n t f x t u f x u t i           = 0 0 ! ( ) ( )k n k n f x f x x x     < 0 , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 trong đó 0 0k k kx x t u x   . Bất đẳng thức này mâu thuẫn với bất đẳng thức (1.6). Giả sử n = n0. Ta chứng minh rằng ( ) 0( , ) ! 0nf x u n    Giả sử ngƣợc lại rằng ( ) 0( , ) !nf x u n   . Khi đó, với dãy 0kt  và ku  S, tƣơng tự nhƣ trên ta có 0 0 ! ( ) ( )k n k n f x f x x x     < !n  . Từ đó suy ra 0 0( ) ( ) n k kf x f x x x   với 0 0k k kx x t u x   . Bất đẳng thức này mâu thuẫn với bất đẳng thức (1.6).  Điều kiện đủ để điểm x0 là điểm cực tiểu cô lập cấp n0 đƣợc phát biểu nhƣ sau: Định lý 1.10 ( Điều kiện đủ ) Giả sử hàm :f E  , x 0  E và S compact đối với tôpô S. Giả sử n0 là một số nguyên không âm và với mỗi u  S, tồn tại số nguyên không âm n = n(u)  n0 sao cho điều kiện  0nS ( , )x u thoả mãn. Khi đó, x0 là điểm cực tiểu địa phương cô lập cấp n0 của f. Chứng minh Bất đẳng thức cuối cùng trong phần chứng minh của bổ đề 1.1 chỉ ra rằng tồn tại số ( )u sao cho Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 0 0( ') ( ) ( ) nf x tu f x u t   , với mọi 0 < t < ( )u và 'u  U(u). Sử dụng u1, ..., us và các ký hiệu sau đây nhƣ trong chứng minh định lý 1.2. Đặt  0 1( ),..., ( ),1smin u u   ,  1( ),..., ( )smin u u   ,  1( ),..., ( )sn max n u n u . Khi đó nhƣ trong chứng minh định lý 1.2 ta đƣợc 0 0( ) ( ) n f x f x x x   với mọi 0 < 0x x < 0 . Do đó x0 là điểm cực tiểu địa phƣơng cô lập cấp n, và vì thế cũng là điểm cực tiểu địa phƣơng cô lập cấp n0 vì n  n0.  Ví dụ 1.8 Lấy E = 2 , C =  0 , n0  1 là số nguyên và x 0 = (0, 0). Hàm :f E  xác định bởi f (x1, x2) = 01 2 2 , 0, 0 , 0. n x x x     Khi đó, x0 là điểm cực tiểu địa phƣơng cô lập cấp n0 của bài toán  ( ), Cmin f x x Chứng minh Đặt g(x1, x2) = 01 2 2 , 0, + , 0. n x x x      Hàm g khác hàm f tại những điểm không thuộc C, tại đó g bằng + . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 Ta nói rằng x0 là điểm cực tiểu địa phƣơng cô lập cấp n0 của bài toán  ( ), Cmin f x x nếu x0 là điểm cực tiểu địa phƣơng cô lập cấp n0 của hàm g. Ta có (0) 0( , ) g x u    , với ( u1, u2) S mà u2  0 . Nếu u = ( 1 , 0) thì ta có 0( 1)(0) 0 0( , ) ... ( , ) 0 n g x u g x u      , 0( ) 0 0( , ) ( )! n g x u n  . Do đó điều kiện đủ của định lý 1.10 cho ta x0 là điểm cực tiểu địa phƣơng cô lập cấp n0.  Ví dụ 1.9 Xét hàm 2:f  xác định bởi f ( x1, x2) = x1. Lấy x0 = (0, 0) và u = (  1, 0). Khi đó đạo hàm cấp hai Hadamard là (2) 0( , ) f x u    còn đạo hàm cấp hai theo phƣơng cổ điển là 0''( , ) 0f x u  . Chứng minh Đạo hàm cấp hai Hadamard là (2) 0( , )f x u = 0 (0) 0 (1) 0 2 ( , ') ( 0, ) 2 ( ') ( , ) ( , ) t u u lim inf f x tu f x u t f x u t          =  (0)12 ( , ') ( 0, ) ( ', ') ( 0, ) 2 1 ' 0 (0 ') (0, ) 't u u t u u lim inf u t lim inf f tu f u t t               =  12 ( , ') ( 0, ) 2 ' t u u lim inf u t t   =   Với đạo hàm theo phƣơng cổ điển ta có 0'( , )f x u = 0 0 0 ( ) ( ) t f x tu f x lim t    1 2( , )u u u Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 = 1 0 0 t tu lim t  = 1u 0''( , )f x u = 0 0 0 2 0 ( ) ( ) '( , ) 2 t f x tu f x t f x u lim t    = 1 1 2 0 0 2 t tu tu lim t   = 0  Ví dụ 1.10 Hàm :f  xác định bởi f (x) = 2 1 ( ), 0, 0 , 0. exp x x x       Ta có f thuộc lớp C . Điểm x0 = 0 là cực tiểu địa phƣơng chặt, nhƣng không là điểm cực tiểu địa phƣơng cô lập. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 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 Chƣơng II trình bày một số tính chất của cực tiểu Pareto địa phƣơng chặt cấp n và cực tiểu Pareto địa phƣơng chặt, và các điều kiện cần và đủ cho hai loại cực tiểu đó 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 dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao Ginchev. Các kết quả trình bày trong chƣơng này là của Đ.V.Lƣu – P.T.Kiên [7] và B.Jiménez [6]. 2.1. CÁC KHÁI NIỆM VÀ KẾT QUẢ BỔ TRỢ Cho hàm f có giá trị thực mở rộng xác định trên không gian định chuẩn X. Nhắc lại [5]: đạo hàm theo phương dưới và trên cấp n, ( ) ( , )nf x d và ( ) ( , )nf x d , tại x X ( n là số nguyên dƣơng ) theo phƣơng d đƣợc định nghĩa lần lƣợt nhƣ sau: (0) ( , )f x d = 0 ' ( ') t d d lim inf f x td    , (2.1) (0) ( , )f x d = 0 ' ( ') t d d lim sup f x td    , (2.2) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 ( ) ( , )nf x d = 1 ( ) 0 0' ! ( ') ( , ) ! jn j n t jd d n t lim inf f x td f x d t j             , (2.3) ( ) ( , )nf x d = 1 ( ) 0 0' ! ( ') ( , ) ! jn j n t jd d n t lim sup f x td f x d t j             , (2.4) trong đó 0t  có nghĩa là 0t  . Chú ý rằng trong các định nghĩa (2.1) – (2.4) của I.Ginchev đã thừa nhận rằng ( ) ( , )nf x d và ( ) ( , )nf x d tồn tại và thuộc khi và chỉ khi tƣơng ứng ( ) ( , )if x d và ( ) ( , )if x d ( i = 0, 1,..., n – 1) tồn tại và thuộc . Hơn nữa, đạo hàm cấp không của các hàm gián đoạn luôn tồn tại và thuộc . Trong trƣờng hợp f liên tục và n = 1, đạo hàm Ginchev trên và dƣới chính là đạo hàm Dini theo phƣơng trên và dƣới [5]. Phù hợp với định nghĩa đạo hàm của Ginchev [5], ta định nghĩa đạo hàm theo phương cấp n của ánh xạ f từ X vào không gian định chuẩn Y nhƣ sau: (0) ( , )f x d = 0 ' ( ') t d d lim f x td    , (2.5) ( ) ( , )nf x d = 1 ( ) 0 0' ! ( ') ( , ) ! jn j n t jd d n t lim f x td f x d t j            , (2.6) nếu các giới hạn đó tồn tại. Nếu f khả vi Fréchet tại x với đạo hàm Fréchet là '( )f x thì (1)( , )f x d = '( )f x d . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Trong trƣờng hợp Y = , sự tồn tại của ( ) ( , )nf x d kéo theo sự tồn tại của ( ) ( , )nf x d và ( ) ( , )nf x d , và chúng trùng nhau. Ta nhắc lại nón tiếp liên của tập C tại x clC : KC( x ) = {d X : tồn tại 0nt  và nd d sao cho n nx t d C  , n }, ở đây clC chỉ bao đóng của C. Trong chƣơng này ta xét bài toán tối ƣu đa mục tiêu sau: (P)  ( ) :min f x x C , trong đó f là ánh xạ từ không gian định chuẩn X vào không gian định chuẩn Y, C là một tập con của X . Giả sử Q là nón lồi đóng trong Y. Nhắc lại: điểm x C gọi là điểm cực tiểu địa phương yếu của bài toán (P) nếu tồn tại một lân cận U của x sao cho ( ) ( )f x f x intQ    x C U   Chú ý rằng với điểm cực tiểu địa phƣơng yếu, ta giả thiết rằng intQ  . Điểm x gọi là điểm cực tiểu Pareto địa phương của bài toán (P) nếu tồn tại một lân cận U của x sao cho ( ) ( )f x f x Q  {0}   x C U   . Điểm x gọi là điểm cực tiểu Pareto địa phương chặt của bài toán (P) nếu tồn tại một lân cận U của x sao cho ( ) ( )f x f x Q   x C U   { }x . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 Với một số nguyên m  1, ta nhắc lại [6] rằng x gọi là điểm cực tiểu Pareto địa phƣơng chặt cấp m của bài toán (P) nếu tồn tại hằng số  > 0 và lân cận U của x sao cho    ( ) ( ), mf x Q B f x x x     x C U   { }x , (2.7) trong đó ( , )B x  là hình cầu mở bán kính  , tâm x . Chú ý rằng hình cầu mở  ( ), mB f x x x  trong (2.7) có thể đƣợc thay bằng hình cầu đóng  ( ), mB f x x x  bán kính m x x  , tâm ( )f x , bởi vì với 1 (0, )  , (2.7) kéo theo    1( ) ( ), mf x Q B f x x x     x C U   { }x . Trƣờng hợp Y = và Q =  , (2.7) trở thành    ( ) ( ), mf x B f x x x     x C U   { }x . Điều đó tƣơng đƣơng với ( ) ( ) m f x f x x x    x C U   { }x , trong đó  là tập các số thực không âm. Điều này có nghĩa là x là cực tiểu địa phƣơng chặt cấp m. Chú ý rằng mọi điểm cực tiểu Pareto địa phƣơng chặt cấp m cũng là điểm cực tiểu Pareto địa phƣơng chặt cấp k với mọi k  m. Với mỗi số nguyên m  1, ta có mối quan hệ sau [6]: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 Cực tiểu Pareto địa phƣơng chặt cấp m  Cực tiểu Pareto địa phƣơng chặt  Cực tiểu Pareto địa phƣơng  Cực tiểu địa phƣơng yếu. Bây giờ, ta trình bày hai kết quả của B.Jiménez [6]. Mệnh đề 2.1 Giả sử x C . Điểm x không là điểm cực tiểu Pareto địa phương chặt cấp m của bài toán (P) khi và chỉ khi tồn tại dãy nx C { }x , nd Q sao cho nx x và ( ) ( ) 0n n m n n f x f x d lim x x      . (2.8) Chứng minh   Bởi vì nx x và (2.8) đúng cho nên 0 00, ( )n n     sao cho 0n n  , ta có ,n nx C x x    và ( ) ( ) m n n nf x f x d x x    . Điều này có nghĩa là  ( ) ( ), mn n nf x d B f x x x   . Nếu nhƣ x là cực tiểu Pareto địa phƣơng chặt cấp m của bài toán (P) thì tồn tại  ,U B x  và 0  sao cho (2.7) đúng. Với  ,min   , tồn tại 0 0( )n n  sao cho với mỗi 0n n ta có  ,nx C B x   và    ( ) ( ), ( ),m mn n n nf x d B f x x x B f x x x     . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 Điều này lại mâu thuẫn với (2.7). Vì vậy, x không là cực tiểu Pareto địa phƣơng chặt cấp m của bài toán (P).   Theo giả thiết, với 0  và 0  ,   ,x C B x     x sao cho    ( ) ( ), mf x Q B f x x x    . Do đó, với 1 n   , 1 n   , tồn tại 1 ,nx C B x n           x và nd D sao cho 1 ( ) ( ), m n n nf x d B f x x x n         . Điều này có nghĩa là ( ) ( ) 1n n m n f x d f x nx x     . Từ đó ta suy ra điều phải chứng minh.  Mệnh đề 2.2 Giả sử x C ,Y = r và Q = r  . Khi đó, a) x là cực tiểu Pareto địa phương chặt cấp m của bài toán (P) khi và chỉ khi tồn tại 0  và lân cận U của x và nhiều nhất r tập Vi , i I { 1, ...,r } sao cho {Vi : i I } là một phủ của  C U { }x và thoả mãn ( ) ( ) m i if x f x x x   ix C    x , (2.9) trong đó    i iC C U V x    . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 b) x là cực tiểu Pareto địa phương chặt của bài toán (P) khi và chỉ khi tồn tại một lân cận U của x và nhiều nhất r tập Vi , i I { 1, ...,r } sao cho {Vi : i I } là một phủ của  C U { }x và thoả mãn ( ) ( )i if x f x với mọi ix C { }x , trong đó   { }i iC C U V x    . Chứng minh a) Giả sử x là cực tiểu Pareto địa phƣơng chặt cấp m. Khi đó, tồn tại 0  và lân cận U của x sao cho    ( ) ( ), mrf x B f x x x    x C U     x (2.10) Lấy 2 r    . Với mỗi i  { 1, ...,r } , ta đặt  : ( ) ( ) mi i iV x f x f x x x     . (2.11) Ta sẽ chứng minh rằng C U   1 r i i x V   (2.12) Lấy x C U   x và giả sử với mọi i  { 1, ...,r } , ( ) ( ) m i if x f x x x   . Vì vậy, ( ) ( )f x f x r e  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 trong đó e = ( 1, 1, ..., 1) r và m r x x   . Do đó, tồn tại rd Q   sao cho    1( ) ( ), ( ),f x d B f x r B f x r    , (2.13) trong đó 1B là hình cấu đóng sau  1 0 ,B y  =  0:y y y    =   0 1 : i i i r y max y y       . Do đó, từ (2.13) ta suy ra    ( ) ( ),rf x B f x r   Điều này mâu thuẫn với (2.10). Vì vậy từ (2.11) ta suy ra (2.12). Từ (2.12) ta suy ra C U     1 r i i x C U V     . Đặt    i iC C U V x    . Khi đó, 1 r i i C U C    , và (2.9) đúng với  thay cho  . Ngƣợc lại, giả sử lân cận U của x và 0  thoả mãn giả thiết. Ta chứng minh (2.10) đúng. Giả sử ngƣợc lại tồn tại x C U   x sao cho    ( ) ( ),rf x B f x r   . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 Từ đó suy ra tồn tại rd  sao cho ( ) ( )f x d f x r   . Vì vậy, ( ) ( )f x f x r e  . Do đó, với mọi i  { 1, ...,r } , ( ) ( ) m i if x f x x x   . Điều này mâu thuẫn với (2.9). Vì vậy (2.10) đúng. b) Chứng minh tƣơng tự.  Với các điểm không là cực tiểu Pareto địa phƣơng chặt của (P), ta có mệnh đề sau đây: Mệnh đề 2.3 Giả sử x C . Giả sử x không là điểm cực tiểu Pareto địa phương chặt của (P). Khi đó với mỗi số nguyên m  1, tồn tại dãy nx C { }x , nd Q sao cho nx x và ( ) ( ) 0n n m n n f x f x d lim x x      . (2.14) Chứng minh Giả sử x không là điểm cực tiểu Pareto địa phƣơng chặt của (P). Khi đó với mỗi số nguyên m  1, x không là điểm cực tiểu Pareto địa phƣơng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 chặt cấp m của (P). Theo mệnh đề 2.1, tồn tại dãy nx C { }x , nd Q sao cho có (2.14).  2.2. ĐIỀU KIỆN CẦN CẤP CAO CHO CỰC TIỂU ĐỊA PHƢƠNG YẾU Định lý sau đây chỉ ra một điều kiện cần dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao của Ginchev cho điểm cực tiểu địa phƣơng yếu, và do đó nó đúng cho cực tiểu Pareto địa phƣơng chặt. Định lý 2.1 Giả sử intQ  và x là điểm cực tiểu địa phương yếu của bài toán (P). Giả sử rằng với mỗi d  KC( x ), tồn tại các đạo hàm theo phương ( ) ( , )jf x d ( j = 0,...,n ) xác định bởi (2.5) và (2.6). Khi đó, các điều kiện tối ưu sau đây đúng: (i) (0)( , ) ( )f x d f x intQ  , với mọi d  KC(x ). (ii) Nếu với d  KC( x ) ta có (0)( , ) ( )f x d f x , ( )( , ) 0jf x d  ( j = 1,...,n – 1) thì ( )( , )nf x d intQ . Chứng minh Vì x là điểm cực tiểu địa phƣơng yếu của (P) nên tồn tại lân cận U của x sao cho ( ) ( )f x f x intQ  với  x C U   . Điều này tƣơng đƣơng với ( ) ( ) (f x f x Y  )intQ với  x C U   . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 Với d  KC( x ), tồn tại dãy 0mt  và md d sao cho m mx t d C  với mọi m. Do vậy với m đủ lớn, ( )m mx t d C U   . Vì vậy, ( ) ( ) (m mf x t d f x Y   )intQ (2.15) Do tính đóng của Y intQ , ta có điều sau (0)( ) ( ) ( , ) ( ) (m m m lim f x t d f x f x d f x Y         )intQ . Do đó, (0)( , ) ( )f x d f x intQ  . Nhƣ vậy (i) đƣợc chứng minh. Để chứng minh (ii), theo giả thiết với d  KC(x ), đạo hàm theo phƣơng ( ) ( , )jf x d ( j = 0, 1, ..., n ) tồn tại. Giả sử (0)( , ) ( )f x d f x , ( ) ( , )jf x d = 0 ( j = 1,..., n – 1), ta có ( ) ( , )nf x d = 1 ( ) 0 0' ! ( ') ( , ) ! jn j n t jd d n t lim f x td f x d t j            = 1 (0) ( ) 1 ! ( ) ( , ) ( , ) ! jn jm m mn m jm n t lim f x t d f x d f x d t j             = ! ( ) ( )m mn m m n lim f x t d f x t     Vì Y intQ đóng nên từ điều trên và (2.15) suy ra ( ) ( , )nf x d Y intQ . Điều này có nghĩa là ( )( , )nf x d intQ . Kết luận (ii) đƣợc chứng minh.  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 2.3. ĐIỀU KIỆN ĐỦ CẤP CAO CHO CỰC TIỂU PARETO ĐỊA PHƢƠNG CHẶT Trong mục này, ta sẽ thiết lập điều kiện đủ cấp cao cho điểm cực tiểu Pareto địa phƣơng chặt cấp n của bài toán (P) trong trƣờng hợp hữu hạn chiều. Định lý 2.2 Giả sử dim X    . Giả sử rằng tồn tại số nguyên dương n sao cho với mọi d ( )CK x {0} , các đạo hàm theo phương ( ) ( , )jf x d ( j = 0, 1, ..., n ) tồn tại và một trong các điều kiện (Ak) ( k = 1, ..., n ) thoả mãn: (Ak) (0) ( , ) ( )f x d f x , ( )( , ) 0jf x d  ( j = 1,...,k – 1), ( ) ( , )kf x d Q . Khi đó, x là điểm cực tiểu Pareto địa phương chặt cấp n của (P). Chứng minh Giả sử ngƣợc lại, x không là điểm cực tiểu Pareto địa phƣơng chặt cấp n của (P). Khi đó theo mệnh đề 2.1, tồn tại dãy mx C , mx x , mx x và mb Q sao cho ( ) ( ) 0m m n m m f x f x b lim x x      . (2.16) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 Đặt m mt x x  , m m m x x d x x    . Khi đó .m m mx x t d  , mx C . Vì dim X    nên dãy { }md hội tụ tới d với 1d  . Không mất tính tổng quát, ta có thể giả sử rằng md d . Vì vậy d ( )CK x {0} . Hơn nữa theo (2.16) ta có ( ) ( ) 0m m m n m m f x t d f x b lim t     . (2.17) Vì 0mt  khi m  nên (2.17) kéo theo với k = 1, ..., n thì ( ) ( ) 0m m m k m m f x t d f x b lim t     . (2.18) Mặt khác, theo giả thiết (Ak), ta có (0)( , ) ( )f x d f x , ( )( , ) 0jf x d  ( j = 1,..., k – 1). Vì ( ) ( , )kf x d tồn tại nên ta có ( ) ( , )kf x d = 1 (0) ( ) 1 ! ( ) ( , ) ( , ) ! jk jm m mk m jm k t lim f x t d f x d f x d t j             = ! ( ) ( )m mk m m k lim f x t d f x t     . Theo giả thiết ( ) ( , )kf x d tồn tại ( k = 1, ..., n ), do đó các giới hạn sau tồn tại Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 ( ) ( )m m k m m f x t d f x lim t   ( k = 1, ..., n ) . (2.19) Sự tồn tại các giới hạn (2.18) và (2.19) dẫn đến sự tồn tại các giới hạn sau m k m m b lim t ( k = 1, ..., n ). Vì Q đóng, mb Q và 0kmt  nên với k = 1, ..., n, m k m m b lim Q t  . Điều này cùng (2.18) dẫn đến với k = 1, ..., n thì ( ) ( , )kf x d Q . Nhƣng điều đó mâu thuẫn với điều kiện (Ak).  Ví dụ 2.1 Lấy X = k , Y = 2 , Q = 2  , C = [0, 1] k–1  [–1, 0], x = ( 0, ..., 0), trong đó k  là orthant không âm trong k , [0, 1] k–1 = [0, 1]  ...  [0, 1] ( k – 1 lần ). Cho hàm f xác định bởi 1 1 1 1 ( ,..., ) , k k k k i i f x x x x           , trong đó k là số nguyên dƣơng chẵn. Khi đó, 1( ) kCK x     , trong đó    và với 1( ,..., )kd d d ( )CK x {0} , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 ( )(0, ) 0jf d  ( j = 1,..., k – 1), ( ) 2 1 (0, ) ,0 k kk i i f d d           . Theo định lý 2.2, điểm 0x  là điểm cực tiểu Pareto địa phƣơng chặt cấp k của hàm f trên C theo nón 2  . Sau đây ta đƣa ra điều kiện đủ cho điểm cực tiểu Pareto địa phƣơng chặt. Định lý 2.3 Giả sử dim X    . Giả sử với mỗi ( )Cd K x {0} , tồn tại số nguyên dương n ( phụ thuộc vào d ) sao cho các đạo hàm theo phương ( ) ( , )jf x d ( j = 0,..., n) tồn tại và một trong các điều kiện (A1), ..., (An) được thoả mãn. Khi đó x là cực tiểu Pareto địa phương chặt của (P). Chứng minh Giả sử ngƣợc lại rằng x không là điểm cực tiểu Pareto địa phƣơng chặt của (P). Khi đó theo mệnh đề 2.3, với mỗi số nguyên 1s  , tồn tại một dãy mx C , mx x , mx x và mb Q sao cho ( ) ( ) 0m m s m m f x f x b lim x x      . Tƣơng tự trong chứng minh định lý 2.2, ta đặt m mt x x  và m m m x x d x x    và nhận đƣợc .m m mx x t d C   và md d với 1d  . Do đó, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 d ( )CK x {0} . Với phƣơng d, tồn tại số nguyên dƣơng n sao cho điều kiện (Ak) thoả mãn với k nào đó  1,...,n và (2.17) thoả mãn. Bằng lập luận đã dùng trong chứng minh định lý 2.2, ta nhận đƣợc ( ) ( , )kf x d Q , và điều này mâu thuẫn với điều kiện (Ak).  2.4. TRƢỜNG HỢP Q = r  Trong mục này, các điều kiện cần và đủ cấp cao khác cho cực tiểu Pareto địa phƣơng chặt đƣợc thiết lập cho trƣờng hợp Y = r , Q = r  , 1( ,..., )rf f f . Cũng nhƣ trên, điều kiện đủ cho nghiệm hữu hiệu đƣợc thiết lập trong không gian X hữu hạn chiều. Định lý 2.4 Giả sử Q = r  , x là cực tiểu Pareto địa phương chặt của bài toán (P). Khi đó, với mọi ( )Cd K x , tồn tại chỉ số {1,...,r}i sao cho các điều kiện sau đây thoả mãn: (a) (0) ( , ) ( )i if x d f x  . (b) Nếu (0) , ( , ) ( )i if x d f x  , ( ) , ( , ) 0 j if x d  ( j = 1,..., n – 1) thì ( ) , ( , ) 0 n if x d  , trong đó ( ) , ( , ) j if x d = 1 ( ) , 0 0' ! ( ) ( , ) ! kj k i ij t kd d j t lim sup f x td f x d t k             ( j = 1,..., n), (0) , ( , )if x d = 0 ' ( ')i t d d lim sup f x td    . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 Chứng minh Giả sử x là cực tiểu Pareto địa phƣơng chặt của (P). Theo mệnh đề 2.2, tồn tại lân cận U của x và các tập V1, ..., Vs ( s r ) sao cho  , 1,...,jV j s là một phủ của C U { }x và ( ) ( )j jf x f x với mọi jx C { }x , (2.20) với   { }j jC C U V x    . Ta có 1 s j j C U C    (2.21) Sử dụng một kết quả của Aubin – Frankowska [1], từ (2.21) suy ra 1 ( ) ( ) ( ) j s C C U C j K x K x K x    . (2.22) Lấy ( )Cd K x , từ (2.22) ta suy ra tồn tại {1,..., }i s sao cho ( ) iC d K x . Do (2.20) ta nhận đƣợc ( ) ( )i if x f x , với mọi ix C { }x . (2.23) Vì ( ) iC d K x cho nên tồn tại dãy 0mt  và md d sao cho m m ix t d C  { }x . Do đó, từ (2.23) ta suy ra ( ) ( )i m m if x t d f x  . (2.24) Vì vậy (0) , ( , )if x d = 0 ' ( ') ( ) ( )i i m m i t m d d lim sup f x td lim sup f x t d f x        . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 Kết luận (a) đƣợc chứng minh. Để chứng minh (b), lấy ( )Cd K x thoả mãn (0) , ( , ) ( )i if x d f x  , ( ) , ( , ) 0 j if x d  ( j = 1, ..., n – 1). Khi đó từ (2.18) ta nhận đƣợc ( ) , ( , ) n if x d = 1 ( ) , 0 0' ! ( ') ( , ) ! jn j i in t jd d n t lim sup f x td f x d t j             1 ( ) , 0 ! ( ) ( , ) ! jn jm i m m in m jm n t lim sup f x t d f x d t j              ! ( ) ( ) 0i m m in m m n lim sup f x t d f x t       Kết luận (b) đƣợc chứng minh.  Ví dụ sau đây minh họa cho định lý 2.4 Ví dụ 2.2 Cho X = Y = 2 , Q = 2  , C = [0, 1]  [–1, 0], x = (0, 0). Trên 2 , xét hàm  1 2 2( ) , , kf x max x x x     với k là số nguyên dƣơng. Đặt 1 1 2( ) ,f x max x x    , 2 2( ) k f x x  thì  1 2,f f f . Hiển nhiên, ( )CK x    và điểm x = (0, 0) là điểm cực tiểu Pareto địa phƣơng chặt của f trên C theo nón 2  . Khi đó, với 1 2( , ) ( )Cd d d K x  , (0) 2, 2(0, ) (0) 0f d f   , ( ) , (0, ) 0 jf d  ( j = 1, ..., k – 1 ), Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 ( ) 2, 2(0, ) 0 kkf d d   . Sau đây ta trình bày một điều kiện đủ cấp cao cho cực tiểu Pareto địa phƣơng chặt cấp n dƣới ngôn ngữ đạo hàm theo phƣơng dƣới của Ginchev. Định lý 2.5 Giả sử dim X    , Y = r và Q = r  , n là một số nguyên dương. Giả sử tồn tại  0 1,...,i r sao cho với mọi ( )Cd K x {0} , một trong các điều kiện (Bk) ( k = 1, ..., n ) thoả mãn: (Bk) 0 0 (0) , ( , ) ( )i if x d f x  , 0 ( ) , ( , ) 0 j if x d  ( j = 1,..., k – 1), 0 ( ) , ( , ) 0 k if x d  . Khi đó x là điểm cực tiểu Pareto địa phương chặt cấp n của bài toán (P), trong đó 0 ( ) , ( , ) j if x d = 0 0 1 ( ) , 0 0' ! ( ') ( , ) ! kj k i ij t kd d j t lim inf f x td f x d t k             (j = 1,...,n ), 0 (0) , ( , )if x d = 00 ' ( ')i t d d lim inf f x td    . Chứng minh Trƣớc hết ta chỉ ra x là điểm cực tiểu Pareto địa phƣơng chặt cấp n của bài toán vô hƣớng sau: 0 ( )iP   0 ( ) :imin f x x C , trong đó 0i f là một thành phần của vectơ 1( ,..., )rf f f đƣợc đề cập đến trong định lý, C nhƣ trong bài toán (P). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 Giả sử điều kiện (Bk) thoả mãn, nhƣng x không là cực tiểu địa phƣơng chặt cấp n của 0 ( )iP . Khi đó, với bất kỳ số nguyên 1m  , tồn tại mx C , mx x , mx x sao cho 0 0 1 ( ) ( ) n i m i mf x f x x x m    . (2.25) Đặt m mt x x  và m m m x x d x x    . Khi đó m m mx x t d C   . Vì dim X    nên tồn tại một dãy con của { }md hội tụ tới d với 1d  . Không mất tính tổng quát, ta có thể giả sử md d . Khi đó, ( )Cd K x {0} . Từ (2.25) ta có 0 0 ( ) ( ) n nm i m m i t f x t d f x d m    . Vì 0mt  khi m  nên với k = 1, ..., n , ta có 0 0 ( ) ( ) k nm i m m i t f x t d f x d m    . (2.26) Do điều kiện (Bk), ta có 0 0 (0) , ( , ) ( )i if x d f x  , 0 ( ) , ( , ) 0 j if x d  ( j = 1,..., k – 1). Kết hợp với (2.26) ta suy ra 0 ( ) , ( , ) k if x d = 0 0 1 ( ) , 0 0' ! ( ') ( , ) ! jk j i ik t jd d k t lim inf f x td f x d t j             Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 0 0 1 ( ) , 0 ! ( ' ) ( , ) ! jk jm i m m ik m jm k t lim inf f x t d f x d t j              0 0 ! ( ) ( )i m m ik m m k lim inf f x t d f x t      ! 0 k nm k m m k t lim inf d t m        Nhƣng theo điều kiện (Bk), ta có 0 ( ) , ( , ) 0 k if x d  . Do vậy dẫn đến một mâu thuẫn. Vậy x là điểm cực tiểu địa phƣơng chặt cấp n của 0 ( )iP . Bây giờ ta phải chỉ ra rằng x là cực tiểu Pareto địa phƣơng chặt cấp n của bài toán (P). Giả sử ngƣợc lại, khi đó theo mệnh đề 2.1, tồn tại dãy mx C , mx x và 1 ( ,..., ) r r m m mb b b Q    sao cho mx x và ( ) ( ) 0m m n m m f x f x b lim x x      . Do đó, ( ) ( ) 0i i m i m n m m f x f x b lim x x      ( i = 1, ..., r) Nói riêng, ta có 0 0 0 ( ) ( ) 0 ii m i m n m m f x f x b lim x x      . Ta lại sử dụng mệnh đề 2.1 để kết luận rằng x không là điểm cực tiểu địa phƣơng chặt cấp n của 0 ( )iP và điều đó dẫn tới điều mâu thuẫn.  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 Ví dụ 2.3 Lấy X = Y = 2 , Q = 2  , C = [–1, 0]  [0, 1], x = (0, 0). Hàm f xác định bởi 2 2 22 1 1 2 1 2( ) ,( ) , ( , ) k f x x x x x x x           , trong đó k là số nguyên dƣơng. Nhƣ vậy 1 2( , )f f f với 1 1( )f x x  , 2 2 2 2 1 2( ) ( ) k k f x x x x   . Ta có ( )CK x    và điểm x = (0, 0) là điểm cực tiểu địa phƣơng chặt cấp k của hàm f2 trên C. Theo định lý 2.5, x là cực tiểu Pareto địa phƣơng chặt cấp k của hàm f trên C theo nón 2  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 KẾT LUẬN Luận văn đã trình bày lý thuyết các điều kiện tối ƣu cấp cao cần và đủ dƣới ngôn ngữ đạo hàm theo phƣơng cấp cao trên và dƣới Ginchev cho các điểm cực tiểu, cực tiểu chặt của bài toán tối ƣu đơn mục tiêu không ràng buộc, không trơn trong không gian Banach của I.Ginchev ( 2002 ), 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, 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 của Đ.V.Lƣu – P.T.Kiên ( 2007 ), cùng một số tính chất của 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 ( 2002 ). Các kết quả của luận văn cho ta thấy rằng các khái niệm đạo hàm theo phƣơng cấp cao của I.Ginchev là thích hợp trong việc dẫn các điều kiện tối ƣu cấp cao. Việc nghiên cứu 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 trên và dƣới của I.Ginchev cho các lớp bài toán tối ƣu đa mục tiêu không trơn khác nhau cần đƣợc tiếp tục nghiên cứu và phát triển. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 TÀI LIỆU THAM KHẢO [1] J.P.Aubin and H.Franknowska, Set – valued Analysis, Birkkhauser Boston, 1990. [2] A. Auslender, Stability in mathematical programming with nondifferentiabledata, SIAM J. Control and Optimization, 22(1984), 239 – 254. [3] A. Ben – Tal and J. Zowe, Derectional derivatives in nonsmooth optimization, J. Optim Theory Appl., 47(1985), 483 – 490. [4] L. Cromme, Strong uniqueness: A far reaching criterion for the convergence of iterative procedures, Numer Math., 29(1978), 179 – 193. [5] I. Ginchev, Higher order optimality conditions in nonsmooth optimization, Optimization,51:1(2002), 47 – 72. [6] B. Jimenez, Strict efficiency in vector optimization, J. Math. Anal. Appl., 265(2002), 264 – 284. [7] D. V. Luu and P. T. Kien , On higher – order conditions for strict efficiency, Soochow Journal of Mathematics, 33(2007), 17 – 31. [8] D. V. Luu and W. Oettli, Higher – order optimality conditions for a minimax, Bull. Austral. Math. Soc., 54(1996), 509 – 516. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 [9] D. V. Luu, Higher – order necessary and sufficient conditions for strict local Pareto minima interms of Studniarski’s derivatives, Optimization, 57(2008), 593 – 605. [10] M. Studinarski, Necessary and sufficient conditions for isolated local minima of nonsmooth functions, SIAM J. Control and Optimization, 24(1986), 1044 – 1049.

Các file đính kèm theo tài liệu này:

  • pdfLuận văn- VỀ ĐIỀU KIỆN TỐI ƯU CẤP CAO TRONG TỐI ƯU KHÔNG TRƠN.pdf
Tài liệu liên quan