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

Chia sẻ: LaLi Sa | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

38
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 f : R ® R . Khi đó n (1) f được gọi là hàm lồi nếu f (l x + (1 - l )y ) £ l f (x ) + (1 - l )f (y ), " x , y Î Rn , l Î éêë0;1ù û. ú (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à n f (x ) - f (x ) ³ x, x - x , " x Î 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. n Định nghĩa 1.2 ([4]). Cho F là một tập con của R . Khi đó F là tập lồi nếu l x + (1 - l )y Î F , " x , y Î F , l Î éêë0;1ù û. ú n Định nghĩa 1.3 ([4]). Cho F là một tập lồi trong R . Khi đó phần trong tương đối của tập F được xác định bởi { riF = x Î Rn : $ e > 0,(x + eB) Ç a ffF Ì F , } trong đó affF là bao affine của tập F . Định nghĩa 1.4 ([4]). Cho hàm f : R ® R . Khi đó miền hữu dụng, phần trên n đồ thị của hàm f lần lượt được xác định bởi { dom f = =x Î Rn : f (x ) < + ¥ , } { epi f = (x , a ) Î Rn ´ R : f (x ) £ a . } Định nghĩa 1.5 ([4]). Cho hàm f : R ® R.. Khi đó f được gọi là chính thường n nếu f (x ) > - ¥ với mọi x Î R và dom f ¹ Æ. n n Định nghĩa 1.6 ([4]). Cho tập F là một tập lồi trong R . Khi đó Véctơ x Î R được gọi là pháp tuyến của tập lồi F tại x Î F , nếu * n (1) x *, x - x £ 0, " 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 { N (x ; F ) = x * Î Rn : x *, x - x £ 0, " x Î F . } dF : Rn ® R (3) Hàm được gọi là hàm chỉ trên tập F với ìï 0 khi x Î F , dF (x ) = ïí ïï + ¥ khi x Ï F . î
203 Với x Î F thì { ¶ dF (x ) = x Î Rn : dF (x ) - dF (x ) ³ x, x - x , " x Î Rn } = {x Î Rn : 0 ³ x, x - x , " x Î F } = N (x ; F ). 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 i : Rn ® R Định lí 1.7 ([4], Định lí 2.91). Cho các hàm lồi chính thường , i = 1, 2 và ri(dom f 1 ) Ç ri(dom f 2 ) ¹ Æ. Khi đó (1) ¶ a f (x ) = a ¶ f (x ) với mọi a > 0 , ¶ (f 1 + f 2 )(x ) = ¶ f 1(x ) + ¶ f 2(x ). (2) Bổ đề 1.8 ([4], Mệnh đề 2.64). Cho hàm lồi f : R ® R sao cho n ri (dom f ) ¹ Æ. Khi đó ri (epif ) ¹ Æ và được xác định bởi { ri(epi f ) = (x , a ) Î Rn ´ R : x Î ri(dom f ), f (x ) < a . } 2. Dưới vi phân lồi theo hướng Định nghĩa 2.1. Cho tập F Ì R và f : R ® R . Khi đó f được gọi là lồi n n tương ứng với F tại x Î dom f nếu f (l x 1 + (1 - l )x 2 ) £ l f (x 1 ) + (1 - l )f (x 2 ) " x i Î x + C F , l Î éêë0;1ùúû, i = 1, 2 trong đó { C F := l u l ³ 0, u Î F } là nón sinh ra bởi tập F . Nhận xét 2.2. Cho tập F Ì R và f : R ® R.. Nếu f là hàm lồi thì f là hàm n n 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 Ì R và f : R ® R là hàm lồi, lấy x Î dom f . Khi đó với n n x , y Î x + C F Ì Rn l Î éêë0,1ùúû mỗi , ta có f (l x + (1 - l )y ) £ l f (x ) + (1 - l )f (y ). Do đó f lồi tương ứng với F .  F1, F2 C F È C F = Rn Chú ý rằng tồn tại f là hàm lồi tương ứng với tại x và 1 2 nhưng f không lồi. Cụ thể ta xét ví dụ sau
204 ìï x khi x > 0, f (x ) = ïí ïï 1 - x khi x £ 0, Ví dụ 2.3. Cho î F1 = (0;1) Ì R, F2 = (- 1;0) Ì R. và Khi đó f không là hàm lồi nhưng f lồi tương ứng với tập F1 và F2 tại 0. Thật vậy, f lồi tương ứng với F1 tại 0 vì CF = {l u, l ³ 0, u Î F1 }= {l ³ 0}= éêë0, + ¥ ) 1 . l Î éêë0,1ù ú û ta xét các trường hợp sau Với Trường hợp 1. x = y = 0, f (l x + (1 - l )y ) = 1 = l + 1 - l = l f (0) + (1 - l )f (0) = l f (x ) + (1 - l )f (y ) . Trường hợp 2. x = 0, y > 0, f (l x + (1 - l )y ) = l x + (1 - l )y £ 1 - l x + (1 - l )y = l f (x ) + (1 - l )f (y ) . Trường hợp 3. x > 0, y > 0, f (l x + (1 - l )y ) = l x + (1 - l )y = l f (x ) + (1 - l )f (y ). F F Suy ra f lồi tương ứng với 1 . Tương tự ta kiểm tra f lồi tương ứng với 2 tại C F = {l u | l ³ 0, u Î F2 }= (- ¥ , 0ù ù é ù û. Với x , y Î (- ¥ , 0úû, l Î êë0,1úû ta xét các ú 0 . Ta có 2 trường hợp sau. Trường hợp 1. x = y = 0, f (l x + (1 - l )y ) = 1 = l + 1 - l = l f (0) + (1 - l )f (0) = l f (x ) + (1 - l )f (y ). Trường hợp 2. x = 0, y < 0, f (l x + (1 - l )y ) = 1 - l x - (1 - l )y = 1 - (1 - l )y = l f (x ) + (1 - l )f (y ). Trường hợp 3. x < 0, y < 0, f (l x + (1 - l )y ) = 1 - l x - (1 - l )y £ l f (x ) + (1 - l )f (y ). F Suy ra f 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. Định nghĩa 2.4. Cho tập F Ì R và hàm chính thường f : R ® R lồi tương n n ứng với F tại x Î dom f . Khi đó, x Î R được gọi là subgradient tương ứng với F tại n x của hàm f nếu f (x ) - f (x ) ³ x, x - x , x Î x + CF . với mọi
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 { ¶ F f (x ) = x Î Rn : f (x ) - f (x ) ³ x, x - x , " x Î x + C F . } F = {u } 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. f , f i : Rn ® R i = 1, 2 Định lí 2.5. Cho tập F Ì R và các hàm chính thường n , . f , f 1, f 2 x Giả sử là các hàm lồi tương ứng F tại và ri(dom f 1 ) Ç ri(dom f 2 ) Ç ri(x + C F ) ¹ Æ . Khi đó ta có các khẳng định sau. ¶ F a f (x ) = a ¶ F f (x ) (1) với mọi a > 0, ¶ (f + f 2 )(x ) = ¶ F f 1(x ) + ¶ F f 2 (x ). (2) F 1 Chứng minh x Î ¶ F a f (x ) x Î x + CF Trước tiên ta chứng minh (1). Với mỗi và ta có x, x - x - (a f (x ) - a f (x )) £ 0 é x ù Û a êê , x - x - (f (x ) - f (x ))ú ú£ 0 êë a ú û x Û , x - x - (f (x ) - f (x )) £ 0. a x Î ¶ F f (x ) x Î a ¶ F f (x ) Điều này tương đương a hay . x Î x + C F , xi Î ¶ F f i (x ) i = 1, 2 Tiếp theo ta chứng minh (2). Với ( ), ta có f 1 (x ) - f 1 (x ) ³ x1, x - x , f 2 (x ) - f 2 ( x ) ³ x2, x - x . f 1(x ) + f 2 (x ) - (f 1(x ) + f 2 (x )) ³ x1, x - x + x2, x - x . Do đó Suy ra (f 1 + f 2 )(x ) - (f 1 + f 2 )(x ) ³ x1 + x2, x - x .
206 (x1 + x2 ) Î ¶ F (f 1 + f 2 )(x ). Do đó ta có Vì vậy ¶ F (f 1 + f 2 )(x ) É ¶ F f 1(x ) + ¶ F f 2(x ) . Ta chứng minh bao hàm ngược lại, với mỗi x Î R ta đặt n y 1 (x ) = f 1 (x + x ) - f 1 (x ) - x, x , y 2 (x ) = f 2 (x + x ) - f 2 (x ). y 1(0) = 0, y 2 (0) = 0 x Î ¶ F (f 1 + f 2 )(x ), Ta thấy . Với mỗi ta có (f 1 + f 2 )(x ) - (f 1 + f 2 )(x ) ³ x, x - x , " x Î (x + C F ). x Î CF, Với thay x bởi x + x ta có (f 1 + f 2 )(x + x ) - (f 1 + f 2 )(x ) ³ x, x . Û (f 1 + f 2 )(x + x ) - (f 1 + f 2 )(x ) - x, x ³ 0, x - 0 . Û ( y 1 + y 2 )(x ) - ( y 1 + y 2 )(0) ³ 0, x - 0 . 0 Î ¶ F (y 1 + y 2 )(0). Điều này tương đương với Không mất tính tổng quát, giả sử x = 0 , x = 0 , f 1(0) = 0 và f 2 (0) = 0 . Khi đó 0 Î ¶ F (f 1 + f 2 )(0) . Do đó, " x Î C F ta có (f 1 + f 2 )(x ) ³ (f 1 + f 2 )(0) = 0, f 1(x ) ³ - f 2 (x ). hay Đặt j i = f i + dC F (i = 1, 2) . Khi đó j i (i = 1, 2) là hàm lồi. Thật vậy, với x, y Î C F j 1(x ) = f 1(x ). x Î CF ,y Ï CF thì Với ta xét các trường hợp sau l = 0, j 1(y ) £ j 1(y ) Trường hợp 1. l = 1, j 1(x ) £ j 1(x ) Trường hợp 2. l Î (0,1), l j 1(x ) + (1 - l )j 1(y ) = (1 - l )j 1(y ) = + ¥ Trường hợp 3. ³ j 1(l x + (1 - l )y ). x, y Ï C F Với ta có l j 1(x ) + (1 - l )j 1(y ) = + ¥ ³ j 1(l x + (1 - l )y ). ri(dom f 1 ) Ç ri(dom f 2 ) Ç ri(x + C F ) ¹ Æ ri(dom j 1 ) Ç ri(dom j 2 ) ¹ Æ. Vì nên Đặt F1 = {(x, a ) Î Rn ´ R, x Î x + C F , f 1(x ) £ a } = {(x, a ) Î Rn ´ R, x Î Rn , j 1(x ) £ a = epi j 1.} riF1 = ri(epij 1 ) Do đó, . Áp dụng Bổ đề 1.8 ta có riF1 = ri(epij 1 ) = {(x, a ) Î Rn ´ R, x Î ri(dom j 1 ) : j 1(x ) < a }
207 = {(x, a ) Î Rn ´ R, x Î ri (x + C F ) : j 1(x ) < a . } Đặt F2 = {(x, a ) Î Rn ´ R, x Î dom j 2 : - j 2 (x ) < a . } Khi đó, riF1 Ç F2 = Æ . Mặt khác, ta có (0; 0) Î F1 Ç F2 . Áp dụng ([4], Định lí 2.26(ii)) tồn tại (x , a ) Î * * R ´ R n với (x , a ) ¹ * * (0; 0) sao cho x *, x + a *a ³ 0 " (x , a ) Î F1, , x *, x + a *a £ 0 " (x , a ) Î F2 . , Vì f 1(0) = 0 nên (0; a ) Î F1 với a ³ 0 . Suy ra a ³ 0 . Giả sử a = 0 , suy ra * * x *, x 1 ³ 0 ³ x *, x 2 " x i Î dom j i , i = 1, 2. domj domj , Do đó 1 và 2 có thể tách được ri(dom j 1 ) Ç ri(dom j 2 ) ¹ Æ * nên mâu thuẫn với . Do đó a > 0 . Vì vậy ta có x *, x 1 + a *a 1 ³ 0, " (x 1, a 1 ) Î F1, x *, x 2 + a *a 2 £ 0, " (x 2, a 2 ) Î F2 x* x* , x + a ³ 0, " (x , a ) Î F1, , x + a £ 0, " (x , a ) Î F2 . a* a* hay Vì (x , f 1 (x )) Î F1 và (x , - f 2 (x )) Î F2 nên x* x* , x + f 1(x ) - f 1(0) ³ 0, , x - (f 2 (x ) - f 2 (0)) £ 0, " x Î C F . a* a* - x* x* * Î ¶ f F 1 (0) * Î ¶ F f 2 (0). Do đó a và a 0 Î ¶ F f 1(0) + ¶ F f 2 (0) Vậy .  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 đó f : ¡ ® ¡ lồi tương ứng với tập lồi Q Ì ¡ n n , W là tập lồi. Định nghĩa 3.1. Điểm x Î WÇ domf đượ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 x Î (x + C Q ) Ç W. Trước tiên, chúng ta xét bài toán đơn giản như sau. Q - min f (x ), x Î Rn (P1) trong đó f : ¡ ® ¡ lồi theo tương ứng với Q Ì ¡ n . n
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 x Î (x + C 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 Î ¶ Q f (x ). của (P1) nếu và chỉ nếu 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ó f (x ) ³ f (x ) Û f (x ) - f (x ) ³ 0, x - x . 0 Î ¶ Q f (x ). Điều này tương đương với  Á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 ri(domf ) Ç ri WÇ ri (x + C Q ) ¹ Æ. Định lí 3.4. Xét bài toán (P). Giả sử rằng Khi đó x Î domf Ç W là nghiệm tối ưu theo hướng Q của (P) nếu và chỉ nếu 0 Î ¶ Q f (x ) + NQ (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 f + dW 0 Î ¶ Q ( f + dW)(x ) với f được thay bởi , điều này tương đương với . ri(domf ) Ç ri(dom dW) Ç ri(x + C Q ) ¹ Æ Vì . Theo Định lí 2.5 ta có 0 Î ¶ Q f (x ) + ¶ Q dW(x ) ¶ Q dW(x ) = NQ (x , W). 0 Î ¶ Q f (x ) + NQ (x , W). . Ta thấy Vì vậy  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 f (x , y ) : R ® R 2 (x , y ) a z = f (x , y ) = x 2 + y W= éêë- 1,1ù é ù Q = R ´ {1} û´ êë- 1,1ú ú û, C = R ´ éêë0, + ¥ ) khi đó Q . ìï (x *, y * ) Î R2 : (x *, y * ), x , y - (0, 0) ü ïï ¶ Q f (0, 0) = í ïï ( ) ïý ïï £ f (x , y ), " x , y Î R ´ éêë0, + ¥ )ïï îï ï þ = (x , y ) Î R : x x + y y £ x + y, " x , y Î R ´ éêë0, + ¥ ) { * * 2 * * 2 } = {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.