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.

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

Trang 1

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

Trang 2

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

Trang 3

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

Trang 4

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

Trang 5

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

Trang 6

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

Trang 7

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

Trang 8

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

Trang 9

pdf 9 trang xuanhieu 2580
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

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:

  • pdfduoi_vi_phan_loi_theo_huong_va_ap_dung.pdf