Dưới vi phân lồi theo hướng và áp dụng

201 DƯỚI VI PHÂN LỒI THEO HƯỚNG VÀ ÁP DỤNG SV. Nguyễn Thị Thanh Thảo ThS. Võ Đức Thịnh Tóm tắt. Trong bài viết này, chúng tôi nghiên cứu một số tính chất của hàm lồi theo hướng và dưới vi phân lồi theo hướng. Sau đó, chúng tôi áp dụng các kết quả về dưới vi phân lồi theo hướng để đặc trưng điều kiện cần và đủ cho nghiệm bài toán tối ưu. Từ khóa: Hàm lồi theo hướng, dưới vi phân lồi theo hướng, bài toán tối ưu. 1. Giới thiệu và tổng quan Trong Lí thuyết tối ưu, người ta quan tâm đến bài toán sau. Tìm nghiệm tối ưu của bài toán min ( ), .f x x (1) trong đó f là hàm lồi từ n  và  là một tập con khác rỗng của . n Chúng ta nhận thấy rằng, nếu f là khả vi tại một điểm nào đó thì ta có thể xấp xỉ hàm f bởi một hàm bậc nhất tại điểm đó (được gọi là tiếp tuyến trong giải tích thực). Tuy nhiên, nếu f không khả vi thì chúng ta không thể làm được điều tương tự. Năm 1960, Rockafellar [8] đề xuất ý tưởng xấp xỉ hàm lồi, không khả vi f tại một điểm nào đó bởi một tập được gọi là dưới vi phân (lồi) thay vì là một hàm tuyến tính như trong trường hợp khả vi. Cụ thể như sau. Định nghĩa 1.1 ([4]). Cho hàm : nf ®R R . Khi đó (1) f được gọi là hàm lồi nếu ( )(1 ) ( ) (1 ) ( ), , , 0;1 .nx y x y x yf l l l f l f l é ù+ - £ + - " Î Î ê úë ûR (2) nx Î R được gọi là subgradient của hàm f tại x nếu ( )xf là hữu hạn và ( ) ( ) , , .nx x x x xf f x- ³ - " Î R (3) Tập tất cả các subgradient của hàm f tại x được gọi là dưới vi phân của hàm f tại x và được ký hiệu là ( )xf¶ . Vậy { }( ) : ( ) ( ) , , .nx x x x x xf x f f x¶ = Î - ³ - " ÎR R Bằng Lí thuyết dưới vi phân, nhiều tác giả đã đặc trưng các điều kiện cần và đủ cho các bài toán tối ưu và tối ưu điều khiển liên quan đến các hàm lồi như [2], [3] cũng như đặc trưng tính chất tập nghiệm của bài toán tối ưu và bất đẳng thức biến phân như [5], [6]. Tuy nhiên, ngay cả trong có nhiều lớp hàm không lồi trên toàn bộ mà chỉ lồi theo một hướng nào đó. Đối với những hàm này, công cụ dưới vi phân trong giải tích lồi (theo định nghĩa của Rockafellar) không giúp chúng ta giải quyết được bài toán (1) mà chúng ta cần sử dụng một công cụ khác. 202 Năm 1976, trong bài báo [7], T. Munakata và cộng sự đã giới thiệu khái niệm tập lồi theo hướng và xây dựng một số tính chất của tập này sau đó áp dụng vào bài toán điều khiển. Năm 1987, A. Bressan trong bài báo [1] đã đưa ra khái niệm và một số tính chất của tập lồi theo hướng (khái niệm này khác với khái niệm mà T. Munakata và S. Kaneko đã đưa ra trước đó) và áp dụng vào việc giải quyết bài toán tối ưu điều khiển. Trong bài báo này, chúng tôi giới thiệu một số khái niệm về tập lồi theo hướng, hàm lồi theo hướng và dưới vi phân lồi theo hướng. Qua đó, chúng tôi thiết lập một số qui tắc tính cho dưới vi phân theo hướng và áp dụng các kết quả này vào việc giải quyết một số bài toán tối ưu. Các kết quả này đã được trình bày trong [9]. Trước hết chúng tôi nhắc lại một số định nghĩa và kết quả của giải tích lồi như sau. Định nghĩa 1.2 ([4]). Cho F là một tập con của n R . Khi đó F là tập lồi nếu (1 ) , , , 0;1 .x y F x y Fl l l é ù+ - Î " Î Î ê úë û Định nghĩa 1.3 ([4]). Cho F là một tập lồi trong . n R Khi đó phần trong tương đối của tập F được xác định bởi { }: 0,( ) a ,nriF x x ffF Fe e= Î $ > + Ç ÌBR trong đó affF là bao affine của tập F . Định nghĩa 1.4 ([4]). Cho hàm : nf ®R R . Khi đó miền hữu dụng, phần trên đồ thị của hàm f lần lượt được xác định bởi { }: ( ) ,ndom x xf f= Î < + ¥= R { }( , ) : ( ) .nepi x xf a f a= Î ´ £R R Định nghĩa 1.5 ([4]). Cho hàm : . nf ®R R Khi đó f được gọi là chính thường nếu ( )xf > - ¥ với mọi nx Î R và domf ¹ Æ. Định nghĩa 1.6 ([4]). Cho tập F là một tập lồi trong . n R Khi đó (1) Véctơ nx * Î R được gọi là pháp tuyến của tập lồi F tại x FÎ , nếu , 0, .x x x x F* - £ " Î (2) Tập tất cả các véctơ pháp tuyến của tập lồi F tại x FÎ được gọi là nón pháp tuyến của F tại x FÎ , ký hiệu ( ; ).N x F Vậy { }( ; ) : , 0, .nN x F x x x x x F* *= Î - £ " ÎR (3) Hàm : n F d ®R R được gọi là hàm chỉ trên tập F với ( ) 0   khi    ,   khi   .F x F x x F d ìï Îï= í ï + ¥ Ïïî 203 Với x FÎ thì { } { } ( ) : ( ) ( ) , , : 0 , , ( ; ). n n F F F n x x x x x x x x x F N x F d x d d x x x ¶ = Î - ³ - " Î = Î ³ - " Î = R R R Trong [4], các tác giả đã giới thiệu một số tính chất dưới vi phân của hàm lồi. Định lí 1.7 ([4], Định lí 2.91). Cho các hàm lồi chính thường : n i f ®R R , 1, 2i = và 1 2 ( ) ( )ri dom ri domf fÇ ¹ Æ . Khi đó (1) ( ) ( )x xa f a f¶ = ¶ với mọi 0a > , (2) 1 2 1 2 ( )( ) ( ) ( ).x x xf f f f¶ + = ¶ + ¶ Bổ đề 1.8 ([4], Mệnh đề 2.64). Cho hàm lồi : nf ®R R sao cho ( ) .ri domf ¹ Æ Khi đó ( )ri epif ¹ Æ và được xác định bởi { }( ) ( , ) : ( ), ( ) .nri epi x x ri dom xf a f f a= Î ´ Î <R R 2. Dưới vi phân lồi theo hướng Định nghĩa 2.1. Cho tập nF Ì R và : nf ®R R . Khi đó f được gọi là lồi tương ứng với F tại x dom fÎ nếu 1 2 1 2 ( (1 ) ) ( ) (1 ) ( )x x x xf l l l f l f+ - £ + - , i F x x C" Î + 0;1 , 1, 2il é ùÎ =ê úë û trong đó { }: 0,FC u u Fl l= ³ Î là nón sinh ra bởi tập F . Nhận xét 2.2. Cho tập nF Ì R và : . nf ®R R Nếu f là hàm lồi thì f là hàm lồi tương ứng với mọi tập F tại mọi x thuộc vào .dom f Thật vậy, cho tập F nÌ R và : nf ®R R là hàm lồi, lấy x dom fÎ . Khi đó với mỗi , n F x y x CÎ + Ì R , 0,1l é ùÎ ê úë û ta có ( )(1 ) ( ) (1 ) ( ).x y x yf l l l f l f+ - £ + - Do đó f lồi tương ứng với F .  Chú ý rằng tồn tại f là hàm lồi tương ứng với 1 2 , F F tại x và 1 2 n F F C CÈ = R nhưng f không lồi. Cụ thể ta xét ví dụ sau 204 Ví dụ 2.3. Cho khi 0, ( ) 1 khi 0, x x x x x f ìï >ï= í ï - £ïî và 1 2 (0;1) , ( 1;0) .F F= Ì = - ÌR R Khi đó f không là hàm lồi nhưng f lồi tương ứng với tập 1F và 2F tại 0. Thật vậy, f lồi tương ứng với 1F tại 0 vì { } { } ) 1 1 C , 0, 0 0, F u u Fl l l é= ³ Î = ³ = + ¥êë . Với 0,1l é ùÎ ê úë û ta xét các trường hợp sau Trường hợp 1. 0, ( (1 ) ) 1 1x y x yf l l l l= = + - = = + - (0) (1 ) (0)l f l f= + - ( ) (1 ) ( )x yl f l f= + - . Trường hợp 2. 0, 0, ( (1 ) ) (1 )x y x y x yf l l l l= > + - = + - 1 (1 )x yl l£ - + - ( ) (1 ) ( )x yl f l f= + - . Trường hợp 3. 0, 0, ( (1 ) ) (1 )x y x y x yf l l l l> > + - = + - ( ) (1 ) ( ).x yl f l f= + - Suy ra f lồi tương ứng với 1 F . Tương tự ta kiểm tra f lồi tương ứng với 2 F tại 0 . Ta có { } ( 2 2 | 0, , 0 F C u u Fl l ù= ³ Î = - ¥ úû. Với (, , 0x y ùÎ - ¥ úû, 0,1l é ùÎ ê úë û ta xét các trường hợp sau. Trường hợp 1. 0, ( (1 ) ) 1 1x y x yf l l l l= = + - = = + - (0) (1 ) (0)l f l f= + - ( ) (1 ) ( ).x yl f l f= + - Trường hợp 2. 0, 0, ( (1 ) ) 1 (1 )x y x y x yf l l l l= < + - = - - - 1 (1 ) ( ) (1 ) ( ).y x yl l f l f= - - = + - Trường hợp 3. 0, 0, ( (1 ) ) 1 (1 )x y x y x yf l l l l< < + - = - - - ( ) (1 ) ( ).x yl f l f£ + - Suy ra f lồi tương ứng với 2 F . Sau đây, chúng tôi giới thiệu định nghĩa dưới vi phân lồi theo hướng. Định nghĩa 2.4. Cho tập nF Ì R và hàm chính thường : nf ®R R lồi tương ứng với F tại x dom fÎ . Khi đó, nx Î R được gọi là subgradient tương ứng với F tại x của hàm f nếu ( ) ( ) , ,x x x xf f x- ³ - với mọi . F x x CÎ + 205 Tập tất cả subgradient tương ứng với F tại x được gọi là dưới vi phân tương ứng với tập F tại x của f và được kí hiệu ( ) F xf¶ . Vậy { }( ) : ( ) ( ) , , .nF Fx x x x x x x Cf x f f x¶ = Î - ³ - " Î +R Khi { }F u= ta gọi dưới vi phân tương ứng với tập F tại x của f là dưới vi phân theo hướng u tại x của .f Ta gọi chung dưới vi phân tương ứng với tập F tại x của f và dưới vi phân theo hướng u tại x của f là dưới vi phân theo hướng tại x của .f Định lí sau đây là mở rộng của Định lí 1.7 cho trường hợp dưới vi phân lồi theo hướng. Định lí 2.5. Cho tập nF Ì R và các hàm chính thường R R, : n i f f ® , 1, 2i = . Giả sử 1 2 , , f f f là các hàm lồi tương ứng F tại x và 1 2 ( ) ( ) ( ) F ri dom ri dom ri x Cf fÇ Ç + ¹ Æ . Khi đó ta có các khẳng định sau. (1) ( ) ( ) F F x xaf a f¶ = ¶ với mọi 0,a > (2) 1 2 1 2 ( )( ) ( ) ( ). F F F x x xf f f f¶ + = ¶ + ¶ Chứng minh Trước tiên ta chứng minh (1). Với mỗi ( ) F xx afÎ ¶ và F x x CÎ + ta có , ( ( ) ( )) 0x x x xx a f a f- - - £ , ( ( ) ( )) 0x x x x x a f f a é ù ê úÛ - - - £ê ú ê úë û , ( ( ) ( )) 0.x x x x x f f a Û - - - £ Điều này tương đương ( ) F x x f a Î ¶ hay ( ) F xx a fÎ ¶ . Tiếp theo ta chứng minh (2). Với , F x x CÎ + ( ) i F i xx fÎ ¶ ( 1, 2i = ), ta có 1 1 1 2 2 2 ( ) ( ) , , ( ) ( ) , . x x x x x x x x f f x f f x - ³ - - ³ - Do đó 1 2 1 2 1 2 ( ) ( ) ( ( ) ( )) , , .x x x x x x x xf f f f x x+ - + ³ - + - Suy ra 1 2 1 2 1 2 ( )( ) ( )( ) , .x x x xf f f f x x+ - + ³ + - 206 Do đó ta có 1 2 1 2 ( ) ( )( ). F xx x f f+ Î ¶ + Vì vậy 1 2 1 2 ( )( ) ( ) ( ) F F F x x xf f f f¶ + É ¶ + ¶ . Ta chứng minh bao hàm ngược lại, với mỗi nx Î R ta đặt 1 1 1 ( ) ( ) ( ) , ,x x x x xy f f x= + - - 2 2 2 ( ) ( ) ( ).x x x xy f f= + - Ta thấy 1 2 (0) 0, (0) 0y y= = . Với mỗi 1 2 ( )( ), F xx f fÎ ¶ + ta có 1 2 1 2 ( )( ) ( )( ) , ,x x x xf f f f x+ - + ³ - ( ).Fx x C" Î + Với , F x CÎ thay x bởi x x+ ta có 1 2 1 2 ( )( ) ( )( ) , .x x x xf f f f x+ + - + ³ 1 2 1 2 ( )( ) ( )( ) , 0, 0 . x x x x xf f f f xÛ + + - + - ³ - 1 2 1 2 ( )( ) ( )(0) 0, 0 .x xy y y yÛ + - + ³ - Điều này tương đương với 1 2 0 ( )(0). F y yÎ ¶ + Không mất tính tổng quát, giả sử 0x = , 0x = , 1 (0) 0f = và 2 (0) 0f = . Khi đó 1 2 0 ( )(0) F f fÎ ¶ + . Do đó, F x C" Î ta có 1 2 1 2 ( )( ) ( )(0) 0,xf f f f+ ³ + = hay 1 2 ( ) ( ).x xf f³ - Đặt Fi i C j f d= + ( )1,2i = . Khi đó i j ( )1,2i = là hàm lồi. Thật vậy, với , F x y CÎ thì 1 1 ( ) ( ).x xj f= Với , F F x C y CÎ Ï ta xét các trường hợp sau Trường hợp 1. 1 1 0, ( ) ( )y yl j j= £ Trường hợp 2. 1 1 1, ( ) ( )x xl j j= £ Trường hợp 3. ( ) 1 1 10,1 , ( ) (1 ) ( ) (1 ) ( )x y yl l j l j l jÎ + - = - = + ¥ 1 ( (1 ) ).x yj l l³ + - Với , F x y CÏ ta có 1 1 1 ( ) (1 ) ( ) ( (1 ) ).x y x yl j l j j l l+ - = + ¥ ³ + - Vì 1 2 ( ) ( ) ( ) F ri dom ri dom ri x Cf fÇ Ç + ¹ Æ nên 1 2 ( ) ( ) .ri dom ri domj jÇ ¹ Æ Đặt ( ){ }1 1, , , ( ) n F F x x x C xa f a= Î ´ Î + £R R ( ){ }1 1, , , ( ) . n nx x x epia j a j= Î ´ Î £ =R R R Do đó, 1 1 )  (riF ri epij= . Áp dụng Bổ đề 1.8 ta có 1 1   ( )riF ri epij= = ( ){ }1 1, , ( ) : ( ) nx x ri dom xa j j aÎ ´ Î <R R 207 ( ){ }1, , ( ) : ( ) . n F x x ri x C xa j a= Î ´ Î + <R R Đặt ( ){ }2 2 2, , : ( ) . nF x x dom xa j j a= Î ´ Î - <R R Khi đó, 1 2 riF FÇ = Æ . Mặt khác, ta có ( ) 1 20;0 .F FÎ Ç Áp dụng ([4], Định lí 2.26(ii)) tồn tại ( ) , nx a* * Î ´R R với ( ), (0;0)x a* * ¹ sao cho , 0x x a a* *+ ³ , ( ) 1, ,x Fa" Î , 0x x a a* *+ £ , ( ) 2, .x Fa" Î Vì 1 (0) 0f = nên ( ) 10; Fa Î với 0a ³ . Suy ra 0a * ³ . Giả sử 0a * = , suy ra 1 2 , 0 ,x x x x* *³ ³ , , 1,2. i i x dom ij" Î = Do đó 1 domj và 2 domj có thể tách được nên mâu thuẫn với 1 2 ( ) ( )ri dom ri domj jÇ ¹ Æ . Do đó 0a * > . Vì vậy ta có ( ) ( )1 1 1 1 1 2 2 2 2 2, 0, , , , 0, ,x x x F x x x Fa a a a a a * * * *+ ³ " Î + £ " Î hay ( ) ( )1 2, 0, , , , 0, , . x x x x F x x Fa a a a a a * * * * + ³ " Î + £ " Î Vì ( )1 1, ( )x x Ff Î và ( )2 2 , ( )x x Ff- Î nên 1 1 2 2 , ( ) (0) 0, , ( ( ) (0)) 0, . F x x x x x x x Cf f f f a a * * * * + - ³ - - £ " Î Do đó 1 (0) F x f a * * - Î ¶ và 2 (0). F x f a * * Î ¶ Vậy 1 2 0 (0) (0) F F f fÎ ¶ + ¶ .  3. Áp dụng Trong mục này, chúng tôi sẽ đặc trưng điều kiện cần cho nghiệm của bài toán sau. Q - min ( ), f x x Î W (P) trong đó : nf ®¡ ¡ lồi tương ứng với tập lồi nQ Ì ¡ , W là tập lồi. Định nghĩa 3.1. Điểm x domfÎ WÇ được gọi là nghiệm tối ưu tương ứng với Q của (P) nếu ( ) ( )f x f x³ , với mọi ( ) . Q x x CÎ + ÇW Trước tiên, chúng ta xét bài toán đơn giản như sau. Q - min ( ),f x nx Î R (P1) trong đó : nf ®¡ ¡ lồi theo tương ứng với . nQ Ì ¡ 208 Định nghĩa 3.2. Điểm x domfÎ được gọi là nghiệm tối ưu tương ứng với Q của (P1) nếu ( ) ( )f x f x³ , với mọi ( ). Q x x CÎ + Định lí 3.3. Xét bài toán (P1). Khi đó x domfÎ là nghiệm tối ưu theo hướng Q của (P1) nếu và chỉ nếu 0 ( ). Q f xÎ ¶ Chứng minh. Giả sử x là nghiệm tối ưu theo hướng Q của (P1). Khi đó với mọi ( ) Q x x CÎ + ta có ( ) ( ) ( ) ( ) 0, .f x f x f x f x x x³ Û - ³ - Điều này tương đương với 0 ( ). Q f xÎ ¶  Áp dụng Định lí 2.5 chúng tôi đặc trưng điều kiện cần cho nghiệm của bài toán (P) như sau Định lí 3.4. Xét bài toán (P). Giả sử rằng ( ) ( ) . Q ri domf ri ri x CÇ WÇ + ¹ Æ Khi đó x domfÎ ÇW là nghiệm tối ưu theo hướng Q của (P) nếu và chỉ nếu 0 ( ) N ( , ) Q Q f x xÎ ¶ + W Chứng minh. Giả sử x là nghiệm tối ưu theo hướng Q của (P). Từ Định lí 3.3 với f được thay bởi f d W + , điều này tương đương với 0 ( )( ) Q f xd W Î ¶ + . Vì ( ) ( ) ( ) Q ri domf ri dom ri x Cd W Ç Ç + ¹ Æ . Theo Định lí 2.5 ta có 0 ( ) ( ) Q Q f x xd W Î ¶ + ¶ . Ta thấy ( ) N ( , ). Q Q x xd W ¶ = W Vì vậy 0 ( ) N ( , ). Q Q f x xÎ ¶ + W  Sau đây, chúng tôi trình bày ví dụ minh họa cho kết quả đạt được. Ví dụ 3.5. Xét hàm 2( , ) :f x y ®R R 2( , ) ( , )x y z f x y x y= = +a 1,1 1,1é ù é ùW= - ´ -ê ú ê úë û ë û, { }1Q = ´R khi đó )0,QC é= ´ + ¥êëR . ( ) ) * * 2 * *( , ) : ( , ), , (0, 0) (0, 0) ( , ), , 0, Q x y x y x y f f x y x y ì üï ïÎ -ï ïï ï¶ = í ý éï ï£ " Î ´ + ¥ï ïêëï ïî þ R R ){ }* * 2 * * 2( , ) : , , 0,x y x x y y x y x y é= Î + £ + " Î ´ + ¥êëR R { } (0 ,1 .ù= ´ - ¥ úû Do đó (0, 0) là nghiệm tối ưu tương ứng với { }1Q = ´R nhưng không là nghiệm tối ưu trên W của bài toán (1). 209 Tài liệu tham khảo [1]. A. Bressan, Directional convexity and finite optimality conditions, Journal of Mathematical Analysis and Applications, 125, 234-246, 1987. [2]. J. V. Burke and R. A. Poliquin, Optimality conditions for non-finite valued convex composite functions, Mathematical Programming, 57:103-120, 1992. [3]. E. Casas and F. Troltzsch, Second order necessary optimality conditions for some state-constrained control problems of semilinear elliptic equations, Journal of Applied Mathematics & Optimization, 39:211-227,1999. [4]. A. Dhara and J. Dutta, Optimality conditions in convex optimization, CRC Press, 2012. [5]. A. L. Dontchev and R. T. Rockafellar, Characterization of strong regularity for variational inequalities over polyhedral convex sets, SIAM Journal on Control and Optimization, 6: 1087-1105, 1996. [6]. R. Janin and J. Gauvin, Lipschitz-type stability in nonsmooth convex programs, SIAM Journal on Control and Optimization, 38:124-137, 1999. [7]. T. Munakata and S. Kaneko, Directional convexity and the directional discrete maximum principle sfor quantized control system, Keio Engineering Reports, 29:2, 7-12, 1976. [8]. R. T. Rockafellar, Convex analysis, Princeton University Press, 1960. [9]. N. T. T. Thảo và V. Đ. Thịnh, Dưới vi phân lồi theo hướng và áp dụng, 2016, submitted.