intTypePromotion=1

Luận văn Thạc sĩ Toán học: Hàm giá trị tối ưu và ánh xạ nghiệm của các bài toán tối ưu có tham số

Chia sẻ: Quỳnh Quỳnh | Ngày: | Loại File: PDF | Số trang:63

0
138
lượt xem
36
download

Luận văn Thạc sĩ Toán học: Hàm giá trị tối ưu và ánh xạ nghiệm của các bài toán tối ưu có tham số

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

Luận văn Thạc sĩ Toán học: Hàm giá trị tối ưu và ánh xạ nghiệm của các bài toán tối ưu có tham số gồm 4 chương, trình bày về các kiến thức chuẩn bị, dưới vi phân Fréchet của hàm giá trị tối ưu, dưới vi phân Mordukhovich của hàm giá trị tối ưu và tính ổn định vi phân của bài toán quy hoạch lồi với ràng buộc bao hàm thức. Mời bạn đọc cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Hàm giá trị tối ưu và ánh xạ nghiệm của các bài toán tối ưu có tham số

  1. VI N HÀN LÂM KHOA H C VÀ CÔNG NGH VI T NAM VI N TOÁN H C ———————o0o——————– HÀM GIÁ TR T I ƯU VÀ ÁNH X NGHI M C A CÁC BÀI TOÁN T I ƯU CÓ THAM S LU N VĂN TH C SĨ TOÁN H C Chuyên ngành: Toán gi i tích Mã s : 60 46 01 02 H c viên th c hi n: Dương Th Vi t An L p: Cao h c K19 Ngư i hư ng d n khoa h c: GS. TSKH. Nguy n Đông Yên HÀ N I - 2013
  2. M cl c L i nói đ u 1 1 Ki n th c chu n b 6 1.1 Tính kh vi và kh vi ch t . . . . . . . . . . . . . . . . 6 1.2 Nón pháp tuy n . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Dư i vi phân . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Đ i đ o hàm . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Hàm giá tr t i ưu . . . . . . . . . . . . . . . . . . . . . 16 2 Dư i vi phân Fréchet c a hàm giá tr t i ưu 18 2.1 Đánh giá dư i vi phân Fréchet . . . . . . . . . . . . . . 18 2.2 M t s ví d minh h a . . . . . . . . . . . . . . . . . . 27 3 Dư i vi phân Mordukhovich c a hàm giá tr t i ưu 29 3.1 Đánh giá dư i vi phân Mordukhovich . . . . . . . . . . 29 3.2 Ví d minh h a . . . . . . . . . . . . . . . . . . . . . . 31 4 Tính n đ nh vi phân c a bài toán quy ho ch l i v i ràng bu c bao hàm th c 34 4.1 Bài toán quy ho ch l i v i ràng bu c bao hàm th c . . . 34 4.2 Bài toán quy ho ch l i v i ràng bu c phi m hàm . . . . 45 4.3 So sánh v i k t qu c a J.-P. Aubin . . . . . . . . . . . 55 K t lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 i
  3. Danh m c ký hi u R trư ng s th c R t p s th c suy r ng N t p các s nguyên dương ∅ t p r ng Rn không gian Euclide n-chi u |x| giá tr tuy t đ i c a x ||x|| chu n c a véctơ x BX hình c u đơn v đóng trong X B(x, ρ) hình c u m tâm x, bán kính ρ > 0 B(x, ρ) hình c u đóng tâm x, bán kính ρ > 0 N (x) h các lân c n c a đi m x int A ph n trong c a t p A A bao đóng c a t p A cone A hình nón sinh c a t p A Limsup gi i h n trên theo nghĩa Painlevé-Kuratowski sup f (x) supremum c a t p s th c {f (x) | x ∈ K} x∈K inf f (x) infimum c a t p s th c {f (x) | x ∈ K} x∈K N (¯; Ω) x nón pháp tuy n Fréchet c a Ω t i x ¯ N (¯; Ω) x nón pháp tuy n Mordukhovich c a Ω t i x ¯ ∂f (x) dư i vi phân Fréchet c a f t i x ∂ + f (x) dư i vi phân Fréchet trên c a f t i x ii
  4. Danh m c ký hi u ∂f (x) dư i vi phân Mordukhovich c a f t i x ∂ ∞ f (x) dư i vi phân suy bi n c a f t i x F :X Y ánh x đa tr t X vào Y dom F mi n h u hi u c a ánh x F gph F đ th c a F D∗ F (¯, y )(·) x ¯ đ i đ o hàm Fréchet c a F t i (¯, y ) x ¯ D∗ F (¯, y )(·) x ¯ đ i đ o hàm Mordukhovich c a F t i (¯, y ) x ¯ Ω x −→ x ¯ x → x và x ∈ Ω ¯ f x −→ x ¯ x → x và f (x) → f (¯) ¯ x α↓α ¯ α → α và α ¯ α ¯ Lα f = {x | f (x) ≤ α} t p m c dư i α c a hàm f iii
  5. L i nói đ u N u bài toán quy ho ch toán h c là ph thu c tham s , t c là các hàm ràng bu c và hàm m c tiêu c a nó ph thu c vào các tham s nào đó, thì giá tr t i ưu là m t hàm c a tham s và ánh x nghi m là m t ánh x đa tr theo tham s c a bài toán. Nói chung thì hàm giá tr t i ưu là m t hàm khá ph c t p theo tham s ; nó thư ng không kh vi theo tham s , dù r ng bài toán đư c xét là bài toán quy ho ch v i các hàm trơn theo t t c các bi n và theo tham s . Vì th , ngư i ta thư ng đ t v n đ tìm các công th c tính toán đ o hàm theo hư ng suy r ng (đ o hàm theo hư ng Dini, đ o hàm theo hư ng Dini-Hadarmard, đ o hàm suy r ng theo hư ng Clarke,...) và các công th c đánh giá dư i vi phân (dư i vi phân theo nghĩa Gi i tích l i, dư i vi phân Clarke, dư i vi phân Fréchet, dư i vi phân qua gi i h n - t c là dư i vi phân Mordukhovich,...) c a hàm giá tr t i ưu. Ngư i ta cũng quan tâm đ n các đi u ki n đ cho tính liên t c, tính Lipschitz, và tính kh vi theo hư ng c a ánh x nghi m. Các nghiên c u v tính ch t kh vi c a hàm giá tr t i ưu và c a ánh x nghi m trong quy ho ch có tham s đư c x p vào ch đ tính n đ nh vi phân c a các bài toán t i ưu. J.-P. Aubin (1998), A. Auslender (1979), J. F. Bonnans và A. Shapiro (2000), P. H. Dien và N. D. Yen (1991), J. Gauvin và F. Dubeau (1982, 1984), B. Gollan (1984), R. T. Rockafellar (1982), B. S. Mordukhovich, N. M. Nam và N. D. Yen (2009), L. Thibault (1991), và r t nhi u tác gi khác, đã có nh ng đóng góp cho hư ng nghiên 1
  6. L i nói đ u c u này. Lu n văn này trình bày v n t t m t s n i dung c a bài báo [7] và đưa ra m t s k t qu m i v tính n đ nh vi phân c a bài toán quy ho ch l i trong không gian vô h n chi u, có ràng bu c d ng bao hàm th c đư c cho b i ánh x đa tr . C th là, nh m lo i b gi thi t v tính khác r ng c a dư i vi phân trên c a hàm m c tiêu trong [7, Theorem 1], m t gi thi t không th th a mãn n u hàm m c tiêu là l i và không kh vi Fréchet, chúng tôi t p trung xét các bài toán quy ho ch l i có tham s trên không gian tôpô tuy n tính l i đ a phương Hausdorff (t c là không gian tôpô tuy n tính l i đ a phương tách) và áp d ng m t k t qu cơ b n c a Gi i tích l i, đó là Đ nh lý Moreau-Rockafellar. K t qu thu đư c cũng cho phép lo i b các gi thi t v tính comp c pháp tuy n theo dãy (tính ch t SNC) c a ánh x t p ràng bu c, tính epi comp c pháp tuy n theo dãy (tính ch t SNEC) c a hàm m c tiêu, và tính µ-n a liên t c dư i n i b (µ-inner semicontinuity), cũng như tính ch t µ-bán-comp c n i b (µ-inner semicompactness) c a ánh x nghi m trong [7, Theorem 7], n u xét các bài toán quy ho ch l i. Không gian đư c xét trong Chương 4 c a lu n văn này cũng t ng quát hơn không gian đư c xét trong [7]: Chúng ta xét các không gian tôpô tuy n tính l i đ a phương Hausdorff thay cho các không gian Banach. Như v y, các k t qu thu đư c Chương 4 c a lu n văn này có ngu n g c t các nghiên c u trong bài báo [7] c a B. S. Mordukhovich, N. M. Nam và N. D. Yen, đ ng th i cũng là k t qu c a s đào sâu các nghiên c u đó cho trư ng h p bài toán quy ho ch l i. M t đi u thú v là, đ thu đư c tính n đ nh vi phân trong quy ho ch l i có tham s , ngư i ta [3] có th s d ng Đ nh lý đ i ng u Fenchel- Moreau (xem [5, Theorem 1, tr. 175]): M t hàm chính thư ng f : X → (−∞, +∞], v i X là không gian véctơ tôpô l i đ a phương Hausdorff, có đ i ng u f ∗∗ trùng v i nó khi và ch khi f là l i và đóng. (Tính đóng 2
  7. L i nói đ u đây đư c hi u là t p trên đ th epi f = {(x, α) | f (x) ≤ α} là đóng trong không gian tích X × R. N u X là không gian có cơ s lân c n g c đ m đư c, đi u này tương đương v i đòi h i f là n a liên t c dư i t i m i đi m trên X ). C th hơn, b ng cách s d ng đ nh lý Fenchel- Moreau v a nêu và m t lo t k t qu b tr khá ph c t p, J.-P. Aubin [3, Problem 35 - Subdifferentials of Marginal Functions, tr. 335] đã thu đư c m t công th c tính dư i vi phân c a hàm giá tr t i ưu dư i gi thi t chính quy. Cách ti p c n này đòi h i hàm m c tiêu c a bài toán đư c xét ph i là l i, n a liên t c dư i, và ánh x t p ràng bu c ph i là l i và có đ th đóng. Cách ti p c n s d ng Đ nh lý Moreau-Rockafellar nói trên không c n hai gi thi t ph này. Vì v y, m c dù ph i đòi h i gi thi t chính quy đôi chút m nh hơn gi thi t chính quy c a Aubin, k t qu c a lu n văn đư c ch ng minh cho l p bài toán quy ho ch l i r ng hơn, và không trùng v i k t qu c a Aubin khi ta xét trư ng h p đ c bi t, đó các không gian là Hilbert và hàm m c tiêu không ph thu c tham s . Khi đư c áp d ng cho các bài toán đi u khi n t i ưu có tham s , v i hàm m c tiêu l i và h đ ng l c tuy n tính, c các h r i r c l n các h liên t c, các k t qu trong chương cu i c a lu n văn có th đưa đ n nh ng quy t c tính toán chính xác dư i vi phân và dư i vi phân suy bi n c a hàm giá tr t i ưu thông qua các d li u c a bài toán đã cho. Lu n văn g m ph n m đ u, ph n k t lu n, danh m c tài li u tham kh o, và b n chương v i n i dung như sau. Chương 1 “Ki n th c chu n b ” trình bày các khái ni m v tính kh vi, tính kh vi ch t, nón pháp tuy n, dư i vi phân, đ i đ o hàm, và hàm giá tr t i ưu. 3
  8. L i nói đ u Chương 2 “Dư i vi phân Fréchet c a hàm giá tr t i ưu” kh o sát m t đánh giá dư i vi phân Fréchet c a hàm giá tr t i ưu và m t s ví d minh h a, d a trên bài báo [7]. Chương 3 “Dư i vi phân Mordukhovich c a hàm giá tr t i ưu" trình bày không có ch ng minh m t đánh giá dư i vi phân Mordukhovich c a hàm giá tr t i ưu và m t ví d minh h a, d a trên bài báo [7]. Chương 4 “Tính n đ nh vi phân c a bài toán quy ho ch l i v i ràng bu c bao hàm th c” ch ng minh m t s k t qu m i v tính n đ nh vi phân c a bài toán quy ho ch l i trong các trư ng h p bài toán có ràng bu c bao hàm th c và bài toán có ràng bu c phi m hàm. Cũng trong chương này, các k t qu c a lu n văn đư c so sánh v i k t qu c a J.-P. Aubin trong [3]. Lu n văn này đư c hoàn thành t i Vi n Toán h c, Vi n Hàn lâm Khoa h c và Công ngh Vi t Nam, dư i s hư ng d n c a GS. TSKH. Nguy n Đông Yên. Tác gi chân thành c m ơn th y Yên đã t n tình hư ng d n tác gi th c hi n các nghiên c u theo đ tài c a lu n văn. Trong quá trình h c t p và làm lu n văn, nh các bài gi ng c a các Giáo sư, Phó Giáo sư công tác t i Vi n Toán h c thu c Vi n Hàn lâm Khoa h c và Công ngh Vi t Nam, tác gi đã trau d i thêm nhi u ki n th c ph c v cho công vi c chuyên môn c a b n thân. Tác gi xin bày t lòng c m ơn sâu s c t i các Th y Cô. Tác gi chân thành c m ơn Ban Giám hi u, Ban ch nhi m Khoa Toán-Tin trư ng Đ i h c Khoa h c, Đ i h c Thái Nguyên đã quan tâm, giúp đ và t o đi u ki n t t nh t cho tác gi khi đi h c t p và nghiên c u Vi n Toán h c. 4
  9. L i nói đ u Cu i cùng, tác gi xin g i l i c m ơn t i gia đình, b n bè, đ ng nghi p và các nghiên c u sinh c a Giáo sư Nguy n Đông Yên đã luôn đ ng viên, giúp đ tác gi trong quá trình nghiên c u và hoàn thành lu n văn. Hà N i, ngày 25 tháng 8 năm 2013 Tác gi Dương Th Vi t An 5
  10. Chương 1 Ki n th c chu n b Chương này trình bày m t s khái ni m cơ b n c a gi i tích bi n phân và đa tr , đó là nón pháp tuy n c a các t p h p, dư i vi phân c a các hàm s th c, và đ i đ o hàm c a ánh x đa tr . M c cu i chương gi i thi u khái ni m hàm giá tr t i ưu trong bài toán quy ho ch toán h c có tham s v i ràng bu c bao hàm th c - là đ i tư ng nghiên c u chính c a các chương sau. 1.1 Tính kh vi và kh vi ch t Cho X, Y là các không gian Banach. Ánh x f : X → Y đư c g i là kh vi Fréchet t i x ∈ X n u t n t i m t phi m hàm tuy n tính liên ¯ t c f (¯) : X → Y , g i là đ o hàm Fréchet c a f t i x, sao cho x ¯ f (x) − f (¯) − f (¯)(x − x) x x ¯ lim = 0. (1.1) x→¯ x ||x − x|| ¯ Đ o hàm Fréchet là khái ni m cơ b n trong gi i tích. Khái ni m sau là ít quen thu c hơn. Đ nh nghĩa 1.1.1. Ánh x f : X → Y đư c g i là kh vi ch t t i x ¯ n u f có đ o hàm Fréchet f (¯) t i x và n u x ¯ f (x) − f (u) − f (¯)(x − u) x lim = 0. (1.2) x→¯ x u→¯ x ||x − u|| 6
  11. Chương 1. Ki n th c chu n b Nh n xét 1.1.1. Do đ nh nghĩa, n u f kh vi ch t t i m t đi m nào đó, thì f ph i kh vi Fréchet t i đi m đó. Đi u ngư c l i là không đúng, t c là có nh ng hàm s kh vi Fréchet mà không kh vi ch t. Ví d 1.1.1. Cho f : R → R đư c cho b i công th c  x2 n u x là s h u t , f (x) = 0 n u x là s vô t . Hàm f là kh vi Fréchet nhưng không kh vi ch t t i x = 0. Th t v y, ¯ d th y r ng f (¯) = 0 là đ o hàm Fréchet t i x. Đ ch ng minh f x ¯ không kh vi ch t t i x = 0, ta l y hai dãy ¯ √ 1 2 1 xk = , uk = 2 + , k = 1, 2, 3, ... k k k Khi đó, n u (1.2) nghi m đúng thì ta ph i có 1 f (xk ) − f (uk ) 2 1 0 = lim = lim k√ =√ , k→∞ ||xk − uk || k→∞ − 2 2 k2 mâu thu n. V y f không kh vi ch t t i x = 0. ¯ M nh đ 1.1.1. (Xem [6, Vol. I, tr. 19]) N u f kh vi Fréchet trong lân c n c a x và ¯ f (.) liên t c trong lân c n y, thì f kh vi ch t t i x. ¯ 1.2 Nón pháp tuy n Cho X là không gian Banach, X ∗ là không gian đ i ng u c a X . V i ánh x đa tr F : X X ∗ đư c cho tùy ý, ký hi u w∗ Lim sup F (x) := x∗ ∈ X ∗ : ∃ xk → x, x∗ − x∗ , ¯ k → x→¯ x x∗ ∈ F (xk ) ∀k = 1, 2, . . . k đư c dùng đ ch gi i h n trên theo dãy theo nghĩa Painlevé-Kuratowski trong tôpô chu n c a X và tôpô y u∗ (đư c ký hi u b ng ch w∗ ) c a 7
  12. Chương 1. Ki n th c chu n b w∗ X ∗. đây, ký hi u x∗ − x∗ đư c dùng đ ch s h i t y u∗ c a dãy k → w∗ {x∗ } ⊂ X ∗ t i ph n t x∗ ∈ X ∗ . Ta có x∗ − x∗ khi và ch khi k k → lim x∗ , u = x∗ , u , k ∀u ∈ X. k→∞ Ω V i Ω ⊂ X là m t t p cho trư c, ký hi u x − x có nghĩa là x → x →¯ ¯ và x ∈ Ω. Đ nh nghĩa 1.2.1. (Xem [6, Vol. I, tr. 4 ]) Cho Ω là t p con khác r ng c a X. (i) V i x ∈ Ω và ε ≥ 0, t p các véctơ ε-pháp tuy n c a Ω t i x đư c cho b i ∗ ∗ x∗ , u − x Nε (x; Ω) := x ∈ X | lim sup ≤ε . (1.3) Ω ||u − x|| u− x → V i ε = 0, t p h p N (x; Ω) := N0 (x; Ω) đư c g i là nón pháp tuy n Fréchet c a Ω t i x. N u x ∈ Ω thì ta đ t Nε (x; Ω) = ∅ v i m i ε ≥ 0. (ii) Cho x ∈ Ω. T p h p ¯ N (¯; Ω) := Lim sup Nε (x; Ω), x (1.4) x→¯ x ε↓0 đư c g i là nón pháp tuy n Mordukhovich hay nón pháp tuy n qua gi i h n c a Ω t i x. Ta đ t N (¯; Ω) = ∅ v i x ∈ Ω. ¯ x ¯ Nh n xét 1.2.1. Hi n nhiên ta có N (x; Ω) ⊂ N (x; Ω) v i m i Ω ⊂ X và v i m i x ∈ Ω. Ngoài ra, cũng d th y r ng t p Nε (x; Ω) là l i v i m i x ∈ Ω và ε ≥ 0. M nh đ 1.2.1. (Xem [6, Vol. I, tr. 6]) Cho Ω là t p l i. Khi đó, Nε (¯; Ω) = x∗ ∈ X ∗ | x∗ , x − x ≤ ε||x − x||, ∀x ∈ Ω , x ¯ ¯ v i m i ε ≥ 0 và x ∈ Ω. Đ c bi t, t p N (¯; Ω) trùng v i nón pháp tuy n ¯ x theo nghĩa gi i tích l i, t c là N (¯; Ω) = {x∗ ∈ X ∗ | x∗ , x − x ≤ 0, ∀x ∈ Ω}. x ¯ 8
  13. Chương 1. Ki n th c chu n b Vì các khái ni m trong Đ nh nghĩa 1.2.1 có tính đ a phương, t c là chúng ch ph thu c vào c u trúc c a Ω trong m t lân c n đư c l y tùy ý c a đi m đư c xét, nên ta có th phát bi u k t qu M nh đ 1.2.1 cho các t p l i đ a phương như sau. M nh đ 1.2.2. (Xem [6, Vol. I, tr. 7]) Cho Ω ⊂ X và x ∈ Ω. N u t n ¯ t i lân c n U ∈ N (¯), x đó N (¯) ký hi u h các lân c n c a đi m x, x ¯ sao cho Ω ∩ U là l i, thì Nε (¯; Ω) = {x∗ ∈ X ∗ | x∗ , x − x ≤ ε||x − x||, ∀x ∈ Ω ∩ U } x ¯ ¯ và N (¯; Ω) = N (¯; Ω) = {x∗ ∈ X ∗ | x∗ , x − x ≤ 0, ∀x ∈ Ω ∩ U }. x x ¯ Ti p theo, chúng ta trình bày hai công th c bi u di n đ c bi t cho nón pháp tuy n Mordukhovich c a các t p con đóng trong không gian h u h n chi u X = Rn . Vì các chu n trong Rn là tương đương v i nhau, nên ta luôn ch n chu n Euclide ||x|| = x2 + x2 + ... + x2 1 2 n trên Rn , tr m t s trư ng h p riêng mà ta s ch rõ chu n c th trên X . Trong trư ng h p này, X ∗ = X = Rn . Cho trư c t p h p khác r ng Ω ⊂ Rn , ta xét hàm kho ng cách dist (x; Ω) := inf ||x − u||, u∈Ω và đ nh nghĩa hình chi u Euclide c a x lên Ω cho b i Π(x; Ω) := {w ∈ Ω | ||x − w|| = dist (x; Ω)}. N u Ω là t p đóng thì t p Π(x; Ω) khác r ng v i m i x ∈ Rn . N u Ω là t p l i thì Π(x; Ω) có không quá m t ph n t v i m i x ∈ Rn . Đ nh lý sau đây mô t nón pháp tuy n qua gi i h n c a các t p Ω ⊂ Rn là đóng đ a phương t i x, nghĩa là t n t i lân c n U c a x sao cho Ω ∩ U ¯ ¯ là đóng. 9
  14. Chương 1. Ki n th c chu n b Đ nh lý 1.2.1. (Xem [6, Vol. I, tr. 8]) Cho Ω ⊂ Rn là t p đóng đ a phương xung quanh x ∈ Ω. Khi đó, ta có ¯ N (¯; Ω) = Lim sup N (x; Ω) x (1.5) x→¯ x và N (¯; Ω) = Lim sup[cone(x − Π(x; Ω))], x (1.6) x→¯ x trong đó cone M := {αx | α ≥ 0, x ∈ M } là hình nón sinh b i M . Đ nh nghĩa 1.2.2. (Xem [6, Vol. I, tr. 196 ]) Không gian Banach X đư c g i là không gian Asplund n u m i hàm l i, liên t c ϕ : U → R xác đ nh trên m t t p con l i m U c a X là kh vi Fréchet trên m t t p con trù m t c a U . Nh n xét 1.2.2. Các tính ch t sau nghi m đúng (xem [6, Vol. I, tr. 196]): (i) M i không gian Banach ph n x đ u là không gian Asplund. (ii) M i không gian Banach có hàm chu n kh vi Fréchet t i nh ng đi m khác 0, đ u là không gian Asplund. Nh n xét 1.2.3. (Xem [6, Vol. I, tr. 221]) N u X là không gian Asplund, thì v i m i t p đóng Ω ⊂ X và v i m i x ∈ Ω ta có ¯ N (¯; Ω) = Lim sup N (x; Ω). x x→¯ x Sau đây là m t s ví d minh h a vi c tính nón pháp tuy n. Ví d 1.2.1. Cho Ω = {(x1 , x2 ) ∈ R2 | x2 ≥ −|x1 |} và x = (0, 0). Gi ¯ s (x∗ , x∗ ) ∈ N (¯; Ω). Khi đó 1 2 x x∗ u1 + x∗ u2 1 2 lim sup 2 + u2 ≤ 0. (1.7) Ω (u1 ,u2 )− (0,0) → u1 2 10
  15. Chương 1. Ki n th c chu n b x22 x Ω x1 x 1 Hình 1 L y (uk , uk ) = (1/k, 0) ∈ Ω, k ∈ N, ta có (uk , uk ) → (0, 0) khi k → ∞. 1 2 1 2 T (1.7) ta có x∗ uk + x∗ uk 0 ≥ lim sup 1 1 2 2 = x∗ . 1 k→∞ (uk )2 + (uk )2 1 2 Do đó x∗ ≤ 0. L y (uk , uk ) = (−1/k, 0) ∈ Ω, k ∈ N, ta có (uk , uk ) → 1 1 2 1 2 (0, 0) khi k → ∞. T (1.7) ta có x∗ uk + x∗ uk 0 ≥ lim sup 1 1 2 2 = −x∗ . 1 k→∞ (uk )2 + (uk )2 1 2 Do đó, x∗ ≥ 0. V y x∗ = 0. Do tính ch t đ i x ng c a x∗ và x∗ ta cũng 1 1 1 2 có x∗ = 0. Ngư c l i, v i (x∗ , x∗ ) = (0, 0) thì (1.7) đư c th a mãn. V y 2 1 2 N (¯; Ω) = {0}. V i (x1 , x2 ) ∈ Ω, ta có x  {0}   n u (x1 , x2 ) ∈ int Ω,   N ((x1 , x2 ); Ω) = {(a, −a) | a ≥ 0} n u x1 = x2 ,    {(a, a) | a ≤ 0}  n u x1 = −x2 . Khi đó, theo Đ nh lý 1.2.1, N (¯; Ω) = Lim sup N ((x1 , x2 ); Ω) x (x1 ,x2 )→(0,0) = {(x∗ , x∗ ) ∈ R2 | x∗ = −|x∗ |}. 1 2 2 1 Ví d 1.2.2. Cho Ω = (x1 , x2 ) ∈ R2 | x1 ≥ 0, x2 ≥ 0 và x = (0, 0). ¯ 11
  16. Chương 1. Ki n th c chu n b Trong trư ng h p này, Ω là t p l i. Vì th , theo M nh đ 1.2.2, N (¯; Ω) = N (¯; Ω) x x = (x∗ , x∗ ) ∈ R2 | x∗ x1 + x∗ x2 ≤ 0, ∀(x1 , x2 ) ∈ Ω 1 2 1 2 = (x∗ , x∗ ) ∈ R2 | x∗ ≤ 0, x∗ ≤ 0 . 1 2 1 2 1.3 Dư i vi phân Xét hàm f : X → R nh n giá tr trong t p s th c suy r ng R = [−∞, +∞]. Ta nói f là chính thư ng (proper) n u như f (x) > −∞ v i m i x ∈ X , và mi n h u hi u dom f := {x ∈ X | f (x) < ∞} là khác r ng. T p trên đ th (epigraph) và dư i đ th (hypograph) c a f tương ng đư c cho b i epi f := {(x, α) ∈ X × R | α ≥ f (x)} và hypo f := {(x, α) ∈ X × R | α ≤ f (x)}. f Sau đây, ký hi u x → x có nghĩa là x → x và f (x) → f (¯). − ¯ ¯ x Đ nh nghĩa 1.3.1. (Xem [6, Vol. I, tr. 82]) Cho X là không gian Banach và cho hàm s f : X → R. Gi s r ng x ∈ X và |f (¯)| < ∞. ¯ x (i) T p h p ∂f (¯) := x∗ ∈ X ∗ | (x∗ , −1) ∈ N ((¯, f (¯)); epi f ) x x x (1.8) đư c g i là dư i vi phân Fréchet c a f t i x. ¯ (ii) T p h p ∂ + f (¯) := x∗ ∈ X ∗ | (−x∗ , 1) ∈ N ((¯, f (¯)); hypo f ) x x x (1.9) đư c g i là dư i vi phân Fréchet trên c a f t i x. ¯ 12
  17. Chương 1. Ki n th c chu n b (iii) T p h p ∂f (¯) := {x∗ ∈ X ∗ | (x∗ , −1) ∈ N ((¯, f (¯)); epi f )} x x x (1.10) đư c g i là dư i vi phân Mordukhovich hay dư i vi phân qua gi i h n c a f t i x. ¯ (iv) T p h p ∂ ∞ f (¯) := {x∗ ∈ X ∗ | (x∗ , 0) ∈ N ((¯, f (¯)); epi f )} x x x (1.11) đư c g i là dư i vi phân suy bi n c a f t i x. ¯ Trong trư ng h p |f (¯)| = ∞, ta quy ư c r ng các t p ∂f (¯), x x ∂ + f (¯), ∂f (¯), và ∂ ∞ f (¯) là r ng. x x x Nh n xét 1.3.1. (i) (Xem [6, Vol. I, tr. 90]) Dư i vi phân Fréchet c a f t i x có th đư c bi u di n dư i d ng ¯ f (x) − f (¯) − x∗ , x − x x ¯ ∂f (¯) = x x∗ ∈ X ∗ | lim inf ≥ 0 . (1.12) x→¯ x ||x − x|| ¯ (ii) Bao hàm th c ∂f (¯) ⊂ ∂f (¯) đúng v i m i x ∈ X. x x (iii) (Xem [6, Vol. I, tr. 95]) N u f là hàm l i thì ∂f (¯) = ∂f (¯) = {x∗ ∈ X ∗ | x∗ , x − x ≤ f (x) − f (¯), ∀x ∈ X}, x x ¯ x t c là dư i vi phân Fréchet và dư i vi phân Mordukhovich c a f t i x ¯ trùng v i dư i vi phân c a f t i x theo nghĩa Gi i tích l i. ¯ N u f là kh vi hay kh vi ch t, thì ta có các k t qu sau. M nh đ 1.3.1. (Xem [6, Vol. I, tr. 90]) Cho f : X → R v i |f (¯)| < ∞. Khi đó, ∂f (¯) = ∅ và ∂ + f (¯) = ∅ n u và ch n u f kh vi x x x Fréchet t i x. Trong trư ng h p này, ta có ∂f (¯) = ∂ + f (¯) = { f (¯)}. ¯ x x x M nh đ 1.3.2. (Xem [6, Vol. I, tr. 87]) N u f là hàm kh vi ch t t i x, thì t p ∂f (¯) ch ch a m t ph n t , đó là đ o hàm ch t c a f t i x. ¯ x ¯ 13
  18. Chương 1. Ki n th c chu n b Ví d 1.3.1. Xét hàm ϕ : R → R đư c cho b i công th c ϕ(x) = −|x|. Ta có epi ϕ = (x1 , x2 ) ∈ R2 | x2 ≥ −|x1 | , hypo ϕ = (x1 , x2 ) ∈ R2 | x2 ≤ −|x1 | . S d ng k t qu Ví d 1.2.1 v i Ω = epi ϕ và x = 0 ta thu đư c ¯ N ((¯, ϕ(¯)); epi ϕ) = {(0, 0)}, x x N ((¯, ϕ(¯)); epi ϕ) = (x∗ , x∗ ) ∈ R2 | x∗ = −|x∗ | . x x 1 2 2 1 Do hypo ϕ là t p l i, theo M nh đ 1.2.1 ta có N ((¯, ϕ(¯)); hypo ϕ) = (x∗ , x∗ ) ∈ R2 | x∗ ≥ |x∗ | . x x 1 2 2 1 Vì v y, ∂ϕ(¯) = ∅, x ∂ + ϕ(¯) = [−1, 1], x ∂ϕ(¯) = {−1; 1}, x ∂ ∞ ϕ(¯) = {0}. x Trong ph n cu i m c này, chúng ta trình bày m i liên h gi a nón pháp tuy n và dư i vi phân thông qua hàm ch . Cho X là không gian Banach và t p h p Ω ⊂ X . Hàm nh n giá tr th c suy r ng δ(·; Ω) : X → R v i  0 n u x ∈ Ω, δ(x; Ω) := (1.13) +∞ n u x ∈ Ω, đư c g i là hàm ch (indicator function) c a t p Ω. M nh đ 1.3.3. (Xem [6, Vol. I, tr. 84 và tr. 88]) V i m i Ω ⊂ X và v i m i x ∈ Ω, ta có ¯ ∂δ(¯; Ω) = N (¯; Ω) x x (1.14) và ∂ ∞ δ(¯; Ω) = ∂δ(¯; Ω) = N (¯; Ω). x x x (1.15) 14
  19. Chương 1. Ki n th c chu n b 1.4 Đ i đ o hàm Cho F : X Y là ánh x đa tr gi a các không gian Banach. Đ th gph F và mi n h u hi u dom F c a F đư c xác đ nh b i các công th c sau gph F := {(x, y) ∈ X × Y | y ∈ F (x)}, dom F := {x ∈ X | F (x) = ∅}. Đư c trang b b i chu n (x, y) := x + y , không gian tích X ×Y là m t không gian Banach. Nh các khái ni m nón ti p tuy n đã đư c xét trên, ta có th đ nh nghĩa các khái ni m đ i đ o hàm Fréchet và đ i đ o hàm Mordukhovich (còn đư c g i là đ i đ o hàm qua gi i h n) c a ánh x đa tr như sau. Đ nh nghĩa 1.4.1. (Xem [6, Vol. I, tr. 40]) (i) Đ i đ o hàm Fréchet c a F t i (¯, y ) ∈ gph F là ánh x đa tr x ¯ D∗ F (¯, y )(y ∗ ) : Y ∗ x ¯ X ∗ đư c cho b i công th c D∗ F (¯, y )(y ∗ ):= x∗ ∈ X ∗ | (x∗ , −y ∗ ) ∈ N ((¯, y ); gph F ) , ∀y ∗ ∈ Y ∗ . x ¯ x ¯ (1.16) (ii) Đ i đ o hàm Mordukhovich c a F t i (¯, y ) ∈ gph F là ánh x x ¯ đa tr D∗ F (¯, y )(y ∗ ) : Y ∗ x ¯ X ∗ đư c cho b i công th c D∗ F (¯, y )(y ∗ ):={x∗ ∈ X ∗ | (x∗ , −y ∗ ) ∈ N ((¯, y ); gph F )}, ∀y ∗ ∈ Y ∗ . x ¯ x ¯ (1.17) N u (¯, y ) ∈ gph F thì ta quy ư c r ng các t p D∗ F (¯, y )(y ∗ ) và x ¯ / x ¯ D∗ F (¯, y )(y ∗ ) là r ng, v i m i y ∗ ∈ Y ∗ . x ¯ Ví d 1.4.1. Xét hàm s th c f : R → R, f (x) = |x|, 15
  20. Chương 1. Ki n th c chu n b và ánh x đa tr F : R R đư c cho b i công th c F (x) = {f (x)} = {|x|}, ∀x ∈ R. Khi đó, gph F = (x, y) ∈ R2 | y = |x| . T i đi m (¯, y ) = (0, 0) ∈ gph F , ta có x ¯ D∗ F (¯, y )(y ∗ ) = x∗ ∈ R | (x∗ , −y ∗ ) ∈ N ((0, 0); gph F ) x ¯ = x∗ ∈ R | y ∗ ≥ |x∗ |  ∅ n u y ∗ < 0, = [−y ∗ , y ∗ ] n u y ∗ ≥ 0. và  {y ∗ , −y ∗ } n u y ∗ < 0, ∗ ∗ D F (¯, y )(y ) = x ¯ [−y ∗ , y ∗ ] n u y ∗ ≥ 0. 1.5 Hàm giá tr t i ưu Cho G : X Y là ánh x đa tr gi a các không gian Banach, ϕ : X × Y → R là hàm nh n giá tr trong t p s th c suy r ng. Hàm giá tr t i ưu (optimal value function) c a bài toán quy ho ch toán h c có ràng bu c đa tr , đư c cho b i G và ϕ, là hàm µ : X → R, v i µ(x) := inf {ϕ(x, y) | y ∈ G(x)} . (1.18) Do quy ư c inf ∅ = +∞, ta có µ(x) = +∞ khi x ∈ dom G. / Ánh x G (tương ng, hàm ϕ) đư c g i là ánh x mô t t p ràng bu c (tương ng, hàm m c tiêu) c a bài toán v ph i c a (1.18). ng v i m i c p d li u {G, ϕ} ta có m t bài toán t i ưu ph thu c tham s x sau đây: (Px ) min{ϕ(x, y) | y ∈ G(x)}. (1.19) 16

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản