Dưới vi phân lồi theo hướng và áp dụng
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.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Bạn đang xem tài liệu "Dưới vi phân lồi theo hướng và áp dụng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: 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 m in ( )f x, x. (1) n n trong đó f là hàm lồi từ và là một tập con khác rỗng của . 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. n Định nghĩa 1.1 ([4]). Cho hàm f : RR® . Khi đó (1) f được gọi là hàm lồi nếu f lllxyxyx fl+-£+-"ÎÎ(1)( fl y )(1) ( ),,,0;1 . Rn éù ( ) êúëû n (2) x Î R được gọi là subgradient của hàm f tại x nếu f ()x là hữu hạn và ffx()(),,.xxxxx-³-"Î Rn (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à ¶ f ()x . Vậy ¶f():()(),,.x = x ÎR: f x - f x ³ x x - x " x Î Rn { } 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 Rn . Khi đó là tập lồi nếu lllxyFxyF+-Î"ÎÎ(1),,,0;1 . éù êúëû Định nghĩa 1.3 ([4]). Cho F là một tập lồi trong Rn . Khi đó phần trong tương đối của tập F được xác định bởi riFxxffFF=Î$>+ÇÌRn :0,()a,eeB { } trong đó affF là bao affine của tập . n Định nghĩa 1.4 ([4]). Cho hàm f : RR® . 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 domxxff=Î<=R + ¥ n :(), { } epixxfafa=δ£( ,):( ). RRn { } n Định nghĩa 1.5 ([4]). Cho hàm f :.RR.® Khi đó f được gọi là chính thường nếu f ()x >-¥ với mọi x Î Rn và domf ¹Æ. Định nghĩa 1.6 ([4]). Cho tập F là một tập lồi trong Rn . Khi đó (1) Véctơ x * Î Rn được gọi là pháp tuyến của tập lồi F tại xFÎ , nếu xxxxF*,0, -£"Î. (2) Tập tất cả các véctơ pháp tuyến của tập lồi F tại xFÎ được gọi là nón pháp tuyến của F tại xFÎ , ký hiệu NxF(;). Vậy N( x ; F )= x** ÎRn : x , x - x £ 0, " x Î F . { } d : RRn ® (3) Hàm F được gọi là hàm chỉ trên tập F với ì ï 0 khi xFÎ , d x = í F ( ) ï + ¥ khi xF Ï . ïî 203 Với xFÎ thì nn ¶=Î-³-"ÎdxddxFFF():()(),,xxxxxx{ RR} :=γ-"Î 0,,{xxRn xxxF } (;).= NxF 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. f : RRn ® Định lí 1.7 ([4], Định lí 2.91). Cho các hàm lồi chính thường i , ridomridom()() ffÇ¹Æ i = 1, 2 và 12. Khi đó (1) ¶a f()()xx = a ¶ f với mọi a > 0 , ¶+=¶+¶()()()().ffff xxx (2) 1212 n Bổ đề 1.8 ([4], Mệnh đề 2.64). Cho hàm lồi f : RR® sao cho ri dom( ) . f ¹Æ Khi đó ri epi()f ¹Æ và được xác định bởi ri()(,):(),(). epixxrifaffa=δÎ< domx RRn { } 2. Dưới vi phân lồi theo hướng n Định nghĩa 2.1. Cho tập F Ì Rn và f : RR® . Khi đó f được gọi là lồi tương ứng với F tại xdomÎ f nếu f((1))()(1) lllxxxx fl+-£+- f () "Î+xxC , l Î=éù0;1 , 1,2i 1212 iFêúëû CuuF:0,=³Î ll trong đó F { } là nón sinh ra bởi tập F . n Nhận xét 2.2. Cho tập F Ì Rn và f :.RR.® 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 domf . n Thật vậy, cho tập Ì Rn và f : RR® là hàm lồi, lấy xdomÎ f . Khi đó với xyxC, Î+Ì Rn l Î éù0,1 mỗi F , êúëû ta có f lllxyxy fl+-£+-(1)( f ) (1) ( ). ( ) Do đó f lồi tương ứng với F . n f FF, CCFFÈ=R Chú ý rằng tồn tại là hàm lồi tương ứng với 12 tại x và 12 nhưng f không lồi. Cụ thể ta xét ví dụ sau 204 ì ï xx khi 0,> f ()x = í ï 1 -£ khixx 0, Ví dụ 2.3. Cho ïî FF=Ì=-Ì(0;1), (1;0).RR và 12 Khi đó f không là hàm lồi nhưng f lồi tương F F ứng với tập 1 và 2 tại 0. Thật vậy, f lồi tương ứng với tại 0 vì C,0,00,=³Î=³=+llluuF ¥ é F { 1} { } ê ) 1 ë . l Î éù0,1 Với êúëû ta xét các trường hợp sau Trường hợp 1. xyxy==+-==+-0, ((1))11fllll =+-lflf(0)(1)(0) =+-lflf()(1)()xy. Trường hợp 2. x=0, y > 0, f( l x + (1 - l )) y = l x + (1 - l ) y £-+-1(1)llxy =+-lflf()(1)()xy. Trường hợp 3. xyxyxy>>+-=+-0, 0, ((1))(1)fllll =+-l flf()(1)().xy f F f F Suy ra lồi tương ứng với 1 . Tương tự ta kiểm tra lồi tương ứng với 2 tại CuuF=³Î=-ll ¥|0,, 0 ù ù éù F { 2 } ( ú xy,, 0Î-¥( ú l Î êú0,1 0 . Ta có 2 û. Với û, ëû ta xét các trường hợp sau. Trường hợp 1. xyxy==+-==+-0, f ((1) llll )11 =l f(0) + (1 - l ) f (0) =+-l flf()(1)().xy Trường hợp 2. xyxyxy=<+-=---0, 0, ((1)f )1(1) llll =--=+-1(1)( )(1)ll flfyxy ( ). Trường hợp 3. xyxyxy<<+-=---0, 0, ((1)f )1(1) llll £l f(xy ) + (1 - l ) f ( ). f F Suy ra lồi tương ứng với 2 . Sau đây, chúng tôi giới thiệu định nghĩa dưới vi phân lồi theo hướng. n n Định nghĩa 2.4. Cho tập F Ì R và hàm chính thường f : RR® lồi tương n ứng với F tại xÎ domf . Khi đó, x Î R được gọi là subgradient tương ứng với F tại x của hàm f nếu f()(),,x- f x ³ x x - x xÎ+ x C . với mọi F 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 ¶ f ()x ứng với tập F tại x của f và được kí hiệu F . Vậy ¶=Î-³-"Î+fxffx():()(),,.xxxxxxxC Rn FF{ } Fu= Khi { } 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. n n ff,:RR® Định lí 2.5. Cho tập F Ì R và các hàm chính thường i , i = 1, 2 . f, f , f Giả sử 12 là các hàm lồi tương ứng F tại x và ri()()() domriff domrixCÇÇ+¹Æ 12 F . Khi đó ta có các khẳng định sau. ¶=¶afaf()()xx (1) FF với mọi a > 0, ¶+=()()()().ffff ¶+ ¶ xxx (2) FFF 1212 Chứng minh xafζ ()x xxCÎ+ Trước tiên ta chứng minh (1). Với mỗi F và F ta có xa,(()())0xxxx fa---£ f éùx Û---£affêú,(xxxx ( )())0 êúa êúëû x Û---£ ,((xxxx )())0. ff a x ζf ()x F xafζ()x Điều này tương đương a hay F . xxCÎ+ , xfζ ()x Tiếp theo ta chứng minh (2). Với F iFi (i = 1,2 ), ta có f1()(),,x- f 1 x ³ x 1 x - x f()(),.x- f x ³ x x - x 2 2 2 f()x+ f ()(() x - f x + f ()) x ³ x , x - x + x , x - x . Do đó 1 2 1 2 1 2 Suy ra (f+ f )(x ) - ( f + f )( x ) ³ x + x , x - x . 1 2 1 2 1 2 206 (x+ x ) Î ¶ ( f + f )(x ). Do đó ta có 1 2F 1 2 Vì vậy ¶+ɶ+¶()()()()ffff xxx FFF 1212 . n Ta chứng minh bao hàm ngược lại, với mỗi x Î R ta đặt yffx()()(),,xxxxx=+-- yff()()().xxxx=+- 111 222 yy(0)0,== (0)0 xffζ+ ()(), x Ta thấy 12. Với mỗi F 12 ta có (f+ f )(x ) - ( f + f )( x ) ³ x , x - x , "x Î x + C . 1 2 1 2 ( F ) xCÎ , Với F thay x bởi xx+ ta có ()()()(),.ffffx++-+³ xxxx 1212 Û(f + f )(x + x ) - ( f + f )() x - x , x ³ 0, x - 0. 1 2 1 2 Û+-+³-()()()(0)0,0.yyyy xx 1212 0()(0).ζ+ yy Điều này tương đương với F 12 Không mất tính tổng quát, giả sử f (0 ) 0= f (0 ) 0= 0()(0)ζ+ ff "ÎxC x = 0 , x = 0 , 1 và 2 . Khi đó F 12. Do đó, F ta có ()()()(0)0,ffff+³+= x ff()().xx³- 1212 hay 12 ji=+ f i d C (i = 1,2) j (i = 1,2) Đặt F . Khi đó i là hàm lồi. Thật vậy, với xyC, Î jf()().xx= xCyCÎÏ, F thì 11 Với FF ta xét các trường hợp sau ljj=£0, ()()yy Trường hợp 1. 11 l=£1, j (xx ) j ( ) Trường hợp 2. 11 ll jlÎ+-=-= jl0,1 j , + ( ¥ )(1)(xyy )(1)( ) Trường hợp 3. ( ) 111 ³+-jll((1)).xy 1 x, yÏ C Với F ta có l jl( jjxyxy )+ ll (1) -= ( + )((1) ¥ ³+ ). - 111 ridom()()()ffÇ ridom Ç rix + C ¹ Æ ri()(). domjjÇ ri dom ¹ Æ Vì 12 F nên 12 Đặt F=( x,,,()a) ÎRRn ´ x Î x + C f x £ a 11{ F } =δΣ=(xxxepi,,,ajaj) (RRR ).nn { 11} (riF= ri epij ) Do đó, 1 1 . Áp dụng Bổ đề 1.8 ta có n (riF= ri epij ) = {(x,,():()a)ÎRR ´ x Î ri dom j11 j x < a } 1 1 207 =δÎ+<xxri,,()aja :().xCxRRn {( ) F 1 } n Fxxdomx222=δÎ-<{( ,,:().ajja) RR } riF FÇ = Æ Đặt Khi đó, 12 . Mặt 0 ;0 . ÎÇFF x **, a δRRn khác, ta có ( ) 12 Áp dụng ([4], Định lí 2.26(ii)) tồn tại ( ) với x **, (0a ;0 )¹ ( ) sao cho xx**,0+³aa "ÎxF,,a , ( ) 1 xx**,0+£aa "ÎxF,.a , ( ) 2 f (0 ) 0= (0; a )Î F * * Vì 1 nên 1 với a ³ 0 . Suy ra a ³ 0. Giả sử a = 0 , suy ra xxxx**,0, ³³ "Î=xdomi j ,1,2. domj domj 12 , ii Do đó 1 và 2 có thể tách được ri()() domjjÇ ri dom ¹ Æ * nên mâu thuẫn với 12. Do đó a > 0. Vì vậy ta có x****, x+a a ³ 0, "( x , a) Î F , x , x + a a £ 0, "( x , a ) Î F 1 1 1 1 1 2 2 2 2 2 xx** ,x+a ³ 0,, "( x a) Î F , , x + a £ 0,, "( x a ) Î F . aa**12 hay xxF,()f Î xxF,()-Îf Vì ( 11) và ( 22) nên xx** ,(xxxxxC )(0)0,+-³--£"ffff ,( ( Î )(0))0,. aa**1122 F - x * x * ζF f 1(0) ζF f 2(0). Do đó a * và a * 0(0)(0)ζ+¶ff Vậy FF12. 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) n n trong đó f : ¡¡® lồi tương ứng với tập lồi Q Ì ¡ , W là tập lồi. Định nghĩa 3.1. Điểm xdomfÎWÇ được gọi là nghiệm tối ưu tương ứng với xÎ(). x + C Ç W của (P) nếu fxfx()() ³ , với mọi Q Trước tiên, chúng ta xét bài toán đơn giản như sau. n - min fx ( ), x Î R (P1) n n trong đó f : ¡¡® lồi theo tương ứng với Q Ì ¡ . 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 x xÎ+ C( ). f x( f) x ( ) ³ , với mọi Q Định lí 3.3. Xét bài toán (P1). Khi đó x domfÎ là nghiệm tối ưu theo hướng Q 0 (ζ ). fx của (P1) nếu và chỉ nếu Q Chứng minh. Giả sử x là nghiệm tối ưu theo hướng Q của (P1). Khi đó với mọi x xÎ+ C() Q ta có fxfxfxfxxx()()()()0,.³Û-³- 0 (ζ ). fx Điều này tương đương với Q Á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 ridomfririxC()(). ÇWÇ+¹Æ Định lí 3.4. Xét bài toán (P). Giả sử rằng Q Khi đó xdomfÎÇ W là nghiệm tối ưu theo hướng Q của (P) nếu và chỉ nếu 0()N(,)ζ+Wfxx QQ Chứng minh. Giả sử x là nghiệm tối ưu theo hướng Q của (P). Từ Định lí 3.3 f + d 0()()ζ+ fxd với f được thay bởi W, điều này tương đương với Q W . ri()()() domfriÇÇ+¹Æ domri xCd Vì W Q . Theo Định lí 2.5 ta có 0()()ζ+¶ fxx d ¶=Wd ()N(,).xx 0()N(,).ζ+Wfxx QQW . Ta thấy QQW Vì vậy QQ Sau đây, chúng tôi trình bày ví dụ minh họa cho kết quả đạt được. 2 Ví dụ 3.5. Xét hàm fxy(,) : RR® 2 (x , y ) a z= f ( x , y ) = x + y W=-´-éùéù1,11,1 Q =´R 1 C =´+R ¥ é0, êúêúëûëû , { } khi đó Q êë ). ïïìü* * 2 * * ïï(,)x yÎ-R :(,),, x y( x y) (0,0) ¶=Q f (0, 0) íý ïï £f ( x , y ), " x , y ÎR ´é 0, + ¥ ) îþïïëê =(x* , y * ) ÎRR 2 : x * x + y * y £ x 2 + y , " x , y Î ´é 0, + ¥ ) { êë } =0 ´ - ¥ ,1ù . { } ( úû Q =´R 1 Do đó (0, 0) là nghiệm tối ưu tương ứng với { } 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.
File đính kèm:
- duoi_vi_phan_loi_theo_huong_va_ap_dung.pdf