Tài liệu Phép vô hướng hóa và điều kiện tối ưu cho bài toán cân bằng véc tơ

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYÔN THÞ VIÖT HåNG PHÐP V¤ H¦íng hãa vµ ®iÒu kiÖn tèi -u cho bµi to¸n c©n b»ng vÐc t¬ LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2014 Luận văn được hoàn thành tại: Trường Đại học Khoa học - Đại học Thái Nguyên Người hướng dẫn khoa học: PGS. TS. ®ç v¨n l-u Phản biện 1: GS.TS. NGUYỄN BƯỜNG Phản biện 2: TS. HÀ TRẦN PHƯƠNG . Luận văn được bảo vệ tại hội đồng chấm luận văn họp tại Trường Đại học Khoa học – Đại học Thái Nguyên vào hồi…..ngày…..tháng ….năm 2014 Có thể tìm hiểu luận văn tại: - Trung tâm học liệu - Đại học Thái Nguyên - Và thư viện trường Đại học Khoa học- Đại học Thái Nguyên „I HÅC THI NGUY–N TR×ÍNG „I HÅC KHOA HÅC NGUY™N THÀ VI›T HÇNG PH’P VÆ H×ÎNG HÂA V€ I—U KI›N TÈI ×U CHO B€I TON C…N BŒNG V’C TÌ LUŠN V‹N TH„C Sž TON HÅC Th¡i Nguy¶n - 2014 „I HÅC THI NGUY–N TR×ÍNG „I HÅC KHOA HÅC NGUY™N THÀ VI›T HÇNG PH’P VÆ H×ÎNG HÂA V€ I—U KI›N TÈI ×U CHO B€I TON C…N BŒNG V’C TÌ Chuy¶n ng nh: To¡n ùng döng M¢ sè: 60. 46. 01. 12 LUŠN V‹N TH„C Sž TON HÅC H÷îng d¨n khoa håc: PGS. TS é V«n L÷u Th¡i Nguy¶n - 2014 Möc löc Mð ¦u 2 1 MËT SÈ KI˜N THÙC V— D×ÎI VI PH…N CLARKE V€ D×ÎI VI PH…N X‡P XŸ 5 1.1 D÷îi vi ph¥n Clarke . . . . . . . . . . . . . . . . . . . . 5 1.2 D÷îi vi ph¥n x§p x¿ . . . . . . . . . . . . . . . . . . . . . 15 2 I—U KI›N C†N V€ Õ CHO NGHI›M HÚU HI›U CÕA B€I TON C…N BŒNG V’C TÌ 19 2.1 2.2 2.3 2.4 Kh¡i ni»m nghi»m húu hi»u cõa b i to¡n c¥n b¬ng v²c tì Ph²p væ h÷îng hâa . . . . . . . . . . . . . . . . . . . . . i·u ki»n tèi ÷u . . . . . . . . . . . . . . . . . . . . . . . p döng cho b i to¡n b§t ¯ng thùc bi¸n ph¥n v²c tì v  b i to¡n tèi ÷u v²c tì . . . . . . . . . . . . . . . . . . . . 20 23 27 39 K¸t luªn 46 T i li»u tham kh£o 47 1 Mð ¦u Trong nhúng n«m g¦n ¥y, b i to¡n c¥n b¬ng v²c tì thu hót nhi·u t¡c gi£ quan t¥m nghi¶n cùu do ph¤m vi ¡p döng rëng r¢i cõa nâ (xem [3]-[7], [9], [12] v  c¡c t i li»u tham kh£o trong c¡c b i b¡o â). Lîp c¡c b i to¡n c¥n b¬ng v²c tì bao h m c¡c lîp b i to¡n sau ¥y nh÷ c¡c tr÷íng hñp °c bi»t: b i to¡n b§t ¯ng thùc bi¸n ph¥n v²c tì, b i to¡n tèi ÷u v²c tì, b i to¡n c¥n b¬ng Nash v²c tì, b i to¡n bò v²c tì, . . . Ng÷íi ta nghi¶n cùu c¡c b i to¡n c¥n b¬ng v· sü tçn t¤i nghi»m, i·u ki»n tèi ÷u, c§u tróc tªp nghi»m, ph÷ìng ph¡p gi£i, . . . C¡c lo¤i nghi»m cõa b i to¡n c¥n b¬ng v²c tì th÷íng ÷ñc nghi¶n cùu l : nghi»m húu hi»u y¸u, nghi»m húu hi»u, nghi»m húu hi»u Henig, nghi»m húu hi»u to n cöc v  nghi»m si¶u húu hi»u. º d¨n c¡c i·u ki»n tèi ÷u cho b i to¡n c¥n b¬ng v²c tì ng÷íi ta dòng ph÷ìng ph¡p væ h÷îng hâa. X.H. Gong ([4], 2010) ¢ thi¸t lªp c¡c k¸t qu£ v· væ h÷îng hâa cho nghi»m húu hi»u y¸u, nghi»m húu hi»u Henig, nghi»m húu hi»u to n cöc cõa b i to¡n c¥n b¬ng v²c tì. Tø c¡c k¸t qu£ v· væ h÷îng hâa, X.H. Gong ([4]) ¢ d¨n c¡c i·u ki»n c¦n tèi ÷u cho c¡c nghi»m húu hi»u y¸u, nghi»m húu hi»u Henig, nghi»m húu hi»u to n cöc v  nghi»m si¶u húu hi»u cõa b i to¡n c¥n b¬ng v²c tì câ r ng buëc tªp. Khi ÷a v o gi£ thi¸t v· t½nh lçi, t¡c gi£ d¨n c¡c i·u ki»n õ tèi ÷u cho c¡c lo¤i nghi»m húu hi»u â. C¡c k¸t qu£ â ÷ñc ¡p döng cho b i to¡n b§t ¯ng thùc bi¸n ph¥n v²c tì v  b i to¡n tèi ÷u 2 v²c tì. ¥y l  · t i thíi sü ang ÷ñc nhi·u nh  to¡n håc quan t¥m nghi¶n cùu. Ch½nh v¼ th¸ em chån · t i: "Ph²p væ h÷îng hâa v  i·u ki»n tèi ÷u cho b i to¡n c¥n b¬ng v²c tì". Luªn v«n tr¼nh b y c¡c k¸t qu£ cõa X.H. Gong [4] v· ph²p væ h÷îng hâa v  c¡c i·u ki»n c¦n v  õ tèi ÷u cho nghi»m húu hi»u y¸u, nghi»m húu hi»u Henig, nghi»m húu hi»u to n cöc v  nghi»m si¶u húu hi»u cõa b i to¡n c¥n b¬ng v²c tì câ r ng buëc tªp còng vîi c¡c ¡p döng cho b i to¡n b§t ¯ng thùc bi¸n ph¥n v²c tì v  b i to¡n tèi ÷u v²c tì. Luªn v«n bao gçm ph¦n mð ¦u, hai ch÷ìng, k¸t luªn v  danh möc c¡c t i li»u tham kh£o. Ch÷ìng 1: Mët sè ki¸n thùc v· d÷îi vi ph¥n Clarke v  d÷îi vi ph¥n x§p x¿. Tr¼nh b y mët sè ki¸n thùc cì b£n v· d÷îi vi ph¥n Clarke v  d÷îi vi ph¥n x§p x¿ cõa Mordukhovich cho h m Lipschitz àa ph÷ìng. Ch÷ìng 2: i·u ki»n c¦n v  õ cho nghi»m húu hi»u cõa b i to¡n c¥n b¬ng v²c tì. Tr¼nh b y c¡c k¸t qu£ cõa X.H. Gong [4] v· ph²p væ h÷îng hâa cho c¡c nghi»m húu hi»u y¸u, nghi»m húu hi»u Henig, nghi»m húu hi»u to n cöc cõa b i to¡n c¥n b¬ng v²c tì. Tø c¡c k¸t qu£ â, chóng tæi tr¼nh b y c¡c i·u ki»n c¦n cho c¡c nghi»m húu hi»u y¸u, nghi»m húu hi»u Henig, nghi»m húu hi»u to n cöc v  nghi»m si¶u húu hi»u cõa b i to¡n c¥n b¬ng v²c tì câ r ng buëc tªp d÷îi ngæn ngú d÷îi vi ph¥n Clarke v  d÷îi vi ph¥n x§p x¿ cõa Mordukhovich cho h m Lipschitz àa ph÷ìng. Vîi c¡c gi£ thi¸t v· t½nh lçi cõa c¡c h m dú li»u chóng tæi tr¼nh b y c¡c i·u ki»n õ tèi ÷u cho c¡c lo¤i nghi»m â. Ph¦n cuèi ch÷ìng tr¼nh b y c¡c i·u ki»n c¦n v  õ tèi ÷u cho b i to¡n b§t ¯ng thùc bi¸n ph¥n v²c tì v  b i to¡n tèi ÷u v²c tì düa tr¶n c¡c k¸t qu£ cho b i to¡n c¥n b¬ng 3 v²c tì. Nh¥n dàp n y tæi xin b y tä láng bi¸t ìn s¥u s­c tîi th¦y gi¡o PGS. TS é V«n L÷u, ng÷íi ¢ tªn t¼nh h÷îng d¨n, gióp ï tæi ho n th nh b£n luªn v«n n y. Tæi xin ch¥n th nh c£m ìn Ban chõ nhi»m khoa To¡n, pháng  o t¤o tr÷íng ¤i håc Khoa håc - ¤i håc Th¡i Nguy¶n còng c¡c th¦y, cæ gi¡o ¢ tham gia gi£ng d¤y khâa håc. Xin ch¥n th nh c£m ìn gia ¼nh, b¤n b± çng nghi»p v  c¡c th nh vi¶n trong lîp cao håc To¡n K6A ¢ luæn quan t¥m, ëng vi¶n, gióp ï tæi trong suèt thíi gian håc tªp v  qu¡ tr¼nh l m luªn v«n. Do thíi gian v  tr¼nh ë cán h¤n ch¸ n¶n luªn v«n khæng tr¡nh khäi nhúng thi¸u sât. Chóng tæi r§t mong nhªn ÷ñc sü gâp þ cõa c¡c th¦y cæ º luªn v«n ÷ñc ho n thi»n hìn. Tæi xin ch¥n th nh c£m ìn! Th¡i Nguy¶n, th¡ng 5 n«m 2014. Ng÷íi thüc hi»n Nguy¹n Thà Vi»t Hçng 4 Ch÷ìng 1 MËT SÈ KI˜N THÙC V— D×ÎI VI PH…N CLARKE V€ D×ÎI VI PH…N X‡P XŸ Ch÷ìng 1 tr¼nh b y mët sè ki¸n thùc cì b£n v· d÷îi vi ph¥n Clarke v  d÷îi vi ph¥n x§p x¿ cõa Mordukhovich cho h m Lipschitz àa ph÷ìng. C¡c ki¸n thùc tr¼nh b y trong ch÷ìng n y ÷ñc tham kh£o trong c¡c t i li»u [1], [8], [10], [11]. 1.1 D÷îi vi ph¥n Clarke Gi£ sû X l  khæng gian Banach, f : X → R. ành ngh¾a 1.1.1. Gi£ sû X l  khæng gian Banach, f : X → R. a) H m f ÷ñc gåi l  Lipschitz àa ph÷ìng t¤i x ∈ X, hay Lipschitz ð g¦n x, n¸u tçn t¤i l¥n cªn U cõa x, sè K > 0 sao cho (∀x, x0 ∈ U ) |f (x) − f (x0 )| 6 Kkx − x0 k. H m f ÷ñc gåi l  Lipschitz àa ph÷ìng tr¶n tªp Lipschitz àa ph÷ìng t¤i måi x ∈ Y . 5 Y ⊂ X, (1.1) n¸u f b) H m f ÷ñc gåi l  Lipschitz vîi h¬ng sè Lipschitz K tr¶n tªp Y n¸u (1.1) óng vîi måi x, x0 ∈ Y . ⊂ X, ành ngh¾a 1.1.2. Gi£ sû F : X → Y , trong â X v  Y l  c¡c khæng gian Banach. nh x¤ F ÷ñc gåi l  Lipschitz àa ph÷ìng t¤i x, n¸u tçn t¤i sè γ > 0 v  sè K > 0 sao cho kF (x0 ) − F (x00 )kY 6 Kkx0 − x00 kX (∀x0 , x00 ∈ x + γB), (1.2) trong â B l  h¼nh c¦u ìn và mð. ành ngh¾a 1.1.3. Gi£ sû f l  h m Lipschitz àa ph÷ìng t¤i x ∈ X . ¤o h m suy rëng Clarke cõa h m f theo ph÷ìng v(∈ X) t¤i x, kþ hi»u l  f ◦(x̄; v), ÷ñc x¡c ành nh÷ sau: f ◦ (x̄; v) = lim sup x→x̄;t↓0 f (x + tv) − f (x) , t (1.3) trong â x ∈ X, t > 0. Sau ¥y l  mët sè t½nh ch§t quan trång cõa ¤o h m suy rëng Clarke. ành lþ 1.1.1. Gi£ sû f l  h m Lipschitz àa ph÷ìng vîi h¬ng sè Lipschitz K t¤i x. Khi â, (i) H m v → f ◦(x; v) húu h¤n, thu¦n nh§t d÷ìng, d÷îi cëng t½nh tr¶n X v  |f ◦ (x; v)| ≤ Kkvk; (ii) f ◦(x; v) nûa li¶n töc tr¶n theo (x, v); f ◦(x; .) Lipschitz (theo v) vîi h¬ng sè K tr¶n X ; (iii) f ◦(x; −v) = (−f )◦(x; v). 6 ành ngh¾a 1.1.4. Gi£ sû f : X → R l  h m Lipschitz àa ph÷ìng tr¶n khæng gian Banach X , X ∗ l  khæng gian èi ng¨u cõa X . Gradient suy rëng Clarke, hay d÷îi vi ph¥n Clarke cõa h m f t¤i x̄, kþ hi»u bði ∂f (x̄), l  tªp hñp sau ¥y trong X ∗ ∂f (x̄) := {ξ ∈ X ∗ : f ◦ (x̄; u) ≥ hξ, ui, ∀u ∈ X}. ành lþ sau ¥y tr¼nh b y mët sè t½nh ch§t quan trång cõa d÷îi vi ph¥n Clarke. ành lþ 1.1.2. Gi£ sû f l  h m Lipschitz àa ph÷ìng vîi h¬ng sè Lipschitz K t¤i x̄. Khi â, a) ∂f (x̄) 6= ∅, lçi, compact ∗y¸u trong X ∗ v  kξk∗ ≤ K (∀ξ ∈ ∂f (x̄)), trong â k.k∗ l  chu©n trong X ∗; b) Vîi måi v ∈ X , ta câ f ◦ (x̄; v) = max{hξ, vi : ξ ∈ ∂f (x̄)}. Chùng minh. a) Theo ành lþ 1.1.1 suy ra f ◦ (x̄; .) d÷îi cëng t½nh, thu¦n nh§t d÷ìng tr¶n X . Theo ành lþ Hahn-Banach, tçn t¤i h m tuy¸n t½nh ζ : X → R sao cho f ◦ (x̄; v) ≥ hζ; vi (∀v ∈ X) Tø â suy ra ζ ∈ ∂f (x̄), v  do â ∂f (x̄) 6= ∅. Ta chùng minh ∂f (x̄) lçi: l§y ξ1, ξ2 ∈ ∂f (x̄), 0 ≤ α ≤ 1. Khi â, f ◦ (x̄; u) ≥ hξi , ui (∀u ∈ X, i = 1, 2) 7 ⇒ f ◦ (x̄; u) = αf ◦ (x̄; u) + (1 − α)f ◦ (x̄; u) ≥ αhξ1 , ui + (1 − α)hξ2 , ui = hαξ1 + (1 − α)ξ2 , ui ⇒ αξ1 + (1 − α)ξ2 ∈ ∂f (x̄) ⇒ f (x̄) lçi. B¥y gií chùng minh ∂f (x̄) compact ∗y¸u: vîi ξ ∈ ∂f (x̄), kξk∗ ≤ K ⇒ ∂f (x̄) ⊂ B̄∗ (0, K), trong â B̄∗ (0, K) l  h¼nh c¦u âng t¥m 0, b¡n k½nh K . M  h¼nh c¦u B̄∗ (0, K) l  compact ∗ y¸u trong X ∗ (ành lþ Alaoglu), ∗ ∂f (x̄) l  âng y¸u⇒ ∂f (x̄)compact ∗ y¸u. b) Theo ành ngh¾a 1.1.4 max{hξ, vi : ξ ∈ ∂f (x̄)} ≤ f ◦ (x̄, v). Gi£ sû tçn t¤i v0 sao cho max{hξ, v0 i : ξ ∈ ∂f (x̄)} ≤ f ◦ (x̄, v0 ). Theo ành lþ Hahn-Banach, tçn t¤i phi¸m h m tuy¸n t½nh ζ thäa m¢n hζ, vi ≤ f ◦ (x̄, v) (∀v ∈ X), hζ, v0 i = f ◦ (x̄, v0 ) ⇒ ζ ∈ ∂f (x̄) ⇒ f ◦ (x̄, v0 ) > hζ, v0 i = f ◦ (x̄, v0 ). Væ l½ (!). Sau ¥y ta tr¼nh b y c¡c ph²p t½nh cho d÷îi vi ph¥n Clarke. ành lþ 1.1.3. Gi£ sû f l  h m Lipschitz àa ph÷ìng t¤i x̄, ∂(sf )(x̄) = s∂f (x̄). 8 s ∈ R. Khi â, Chùng minh. Hiºn nhi¶n f Lipschitz àa ph÷ìng t¤i x̄ suy ra sf Lipschitz àa ph÷ìng t¤i x̄. Vîi s ≥ 0, (sf )◦ = sf ◦ ⇒ ∂(sf )(x̄) = s∂f (x̄). Vîi s < 0, ta ch¿ c¦n chùng minh cho s = −1 l  õ. ζ ∈ ∂(−f )(x̄) ⇔ (−f )◦ (x̄; v) ≥ hζ; vi (∀v) ⇔ f ◦ (x̄, −v) ≥ hζ; vi (∀v) (ành lþ 1.1.1) ⇔ −ζ ∈ ∂f (x̄) ⇔ ζ ∈ −∂f (x̄). Vªy ∂(−f )(x̄) = −∂f (x̄). ành lþ 1.1.4. n n X X
∂ fi (x̄) ⊂ ∂fi (x̄). i=1 i=1 (1.4) Chùng minh. V¸ ph£i cõa (1.4) l  tªp compact ∗y¸u. Ta ch¿ c¦n chùng minh (1.4) cho tr÷íng hñp n = 2, cán tr÷íng hñp têng qu¡t s³ nhªn ÷ñc b¬ng quy n¤p. H m tüa cõa hai v¸ (1.4) t÷ìng ùng l  (f1 + f2 )◦ (x̄; v) v  f1◦ (x̄; v) + f2◦ (x̄; v). Tø ành ngh¾a ta câ (f1 + f2 )◦ (x̄; v) ≤ f1◦ (x̄; v) + f2◦ (x̄; v). Theo m»nh · 1.5 [1], ta câ ∂(f1 + f2 )(x̄) ⊂ ∂f1 (x̄) + f2 (x̄). 9 H» qu£ 1.1.1. Vîi si ∈ R, (i = 1, . . . , n), ta câ n n X X
∂ si fi (x̄) ⊂ si ∂fi (x̄). i=1 (1.5) i=1 D§u b¬ng x£y ra khi: trø ra mët h m, cán l¤i ·u kh£ vi ch°t t¤i x̄. Chùng minh. Ta câ n n X X
∂ si fi (x̄) ⊂ ∂(si ∂fi )(x̄) (ành lþ 1.1.4) i=1 = i=1 n X si ∂fi (x̄) (ành lþ 1.1.3). i=1 Ph¦n cán l¤i ta ¡p döng ành lþ 1.1.3 v  h» qu£ 2.2.1 [1]. ành lþ 1.1.5 (ành l½ v· gi¡ trà trung b¼nh cõa G. Lebourg). Gi£ sû x, y ∈ X, f l  h m Lipschitz tr¶n tªp mð chùa o¤n [x, y]. Khi â tçn t¤i u ∈ (x, y) sao cho f (y) − f (x) ∈ h∂f (u), y − xi. (1.6) º chùng minh ành lþ 1.1.5 ta c¦n bê · sau ¥y. °t g(t) := f (xt), trong â xt = x + t(y − x), x v  y ∈ X . Bê · 1.1.1. H m g : [0, 1] → R thäa m¢n i·u ki»n Lipschitz tr¶n (0, 1), çng thíi ∂g(t) ⊂ h∂f (xt ), y − xi. (1.7) Chùng minh. Hiºn nhi¶n g l  h m Lipschitz tr¶n (0, 1). Hai tªp lçi âng trong cæng thùc (1.7) l  c¡c o¤n trong R. V¼ th¸ ta ch¿ c¦n ch¿ ra r¬ng vîi v = ±1 th¼ max{∂g(t)v} ≤ max{h∂f (xt ), y − xiv}. 10 Ta câ g(s + λv) − g(s) λ s→t;λ↓0 f (x + (s + λv)(y − x)) − f (x + s(y − x)) = lim sup λ s→t;λ↓0 0 f (y + λv(y − x)) − f (y 0 ) ≤ lim sup λ y 0 →xt ;λ↓0 max{∂g(t)v} = g ◦ (t; v) = lim sup = f ◦ (xt ; v(y − x)) = maxh∂f (xt ), v(y − x)i. Chùng minh ành lþ 1.1.5. °t θ(t) = f (xt ) + t[f (x) − f (y)], (0 ≤ t ≤ 1). Ta câ θ(0) = θ(1) = f (x), θ(.) li¶n töc tr¶n [0, 1], suy ra tçn t¤i t̄ ∈ (0, 1) sao cho θ(.) ¤t cüc ¤i àa ph÷ìng ho°c cüc tiºu àa ph÷ìng t¤i t̄. Do â 0 ∈ ∂θ(t̄). ⇒ 0 ∈ [f (x) − f (y)] + ∂g(t̄) (c¡c ành lþ 1.1.3 , 1.1.4) ⇒ 0 ∈ [f (x) − f (y)] + h∂f (xt̄ ), y − xi (Bê · 1.1.1) L§y u = xt̄ ta nhªn ÷ñc (1.6). Gi£ sû h : X → Rn, g : Rn → R, f = g ◦ h. Khi â h = (h1, . . . , hn). ành lþ 1.1.6. Gi£ sû méi hi Lipschitz àa ph÷ìng t¤i x̄, àa ph÷ìng t¤i h(x̄). Khi â, (i = 1, . . . , n), g n X ∂f (x̄) ⊂ co{ αi ζi : ζi ∈ ∂hi (x̄), α ∈ ∂g(h(x̄))}, i=1 trong â co kþ hi»u bao lçi âng ∗y¸u. 11 Lipschitz (1.8) (1.8) câ d§u b¬ng n¸u câ mët trong c¡c i·u ki»n sau: 1) g ch½nh qui t¤i h(x̄), méi hi ch½nh qui t¤i x̄, méi α ∈ ∂g(h(x̄)) câ c¡c th nh ph¦n αi ≥ 0 (çng thíi suy ra f l  h m ch½nh qui t¤i x̄); 2) g kh£ vi ch°t t¤i h(x̄) v  n = 1 (trong tr÷íng hñp n y ph²p to¡n co câ thº bä ÷ñc); 3) g ch½nh qui t¤i h(x̄) v  h kh£ vi ch°t t¤i x̄ (çng thíi suy ra f ch½nh qui t¤i x̄ v  ph²p to¡n co câ thº bä ÷ñc). ành ngh¾a 1.1.5. Cho tªp A ⊂ X, t¤i x̄ ∈ A, n¸u A 6= ∅. V²c tì v ∈ X ÷ñc gåi l  ti¸p xóc vîi tªp A d◦A (x̄; v) = 0. Kþ hi»u TC (A, x̄) l  tªp t§t c£ c¡c v²c tì ti¸p xóc vîi A t¤i x̄ ∈ A TC (A, x̄) := {v ∈ X : d◦A (x̄; v) = 0}. ành ngh¾a 1.1.6. ÷ñc gåi l  nân ti¸p tuy¸n Clarke (Clarke tangent cone) cõa tªp A t¤i x̄. TC (A, x̄) ành ngh¾a 1.1.7. Nân ph¡p tuy¸n Clarke (Clarke normal cone) cõa tªp A t¤i x̄ ÷ñc ành ngh¾a nh÷ sau: NC (A, x̄) := {ξ ∈ X ∗ : hξ, vi ≤ 0, ∀v ∈ TC (A, x̄)}. ành lþ 1.1.7. [1] Gi£ sû A l  mët tªp lçi. Khi â NC (A, x̄) tròng vîi nân ph¡p tuy¸n theo ngh¾a gi£i t½ch lçi. ành ngh¾a 1.1.8. Nân ti¸p li¶n (contingent cone) cõa tªp A t¤i x̄ ÷ñc ành ngh¾a nh÷ 12 sau: KC (A, x̄) := {v ∈ X : ∀ > 0, ∃t ∈ (0, ), ∃ω ∈ v + tB sao cho x̄ + tω ∈ A}. ành ngh¾a 1.1.9. Tªp A ÷ñc gåi l  ch½nh qui t¤i x̄, n¸u TC (A, x̄) = KC (A, x̄). ành ngh¾a 1.1.10. Cho ¡nh x¤ G : X → Y v  iºm x ∈ X . N¸u tçn t¤i mët ¡nh x¤ tuy¸n t½nh li¶n töc G0(x) : X → Y sao cho vîi méi h ∈ X , 1 (G(x0 + λh) − G(x0 )), x →x λ G0 (x)(h) = lim 0 λ↓0 v  sü hëi tö l  çng ·u theo h trong c¡c tªp compact, th¼ ¡nh x¤ G ÷ñc gåi l  kh£ vi ch°t t¤i x. Bê · 1.1.2. [1] Cho X l  khæng gian Banach, A ⊂ X, g : X → R. Gi£ sû g Lipschitz àa ph÷ìng t¤i x v  ¤t cüc tiºu tr¶n A t¤i x. Khi â, 0 ∈ ∂g(x) + NC (A, x). Bê · 1.1.3. [1] Cho X, Y l  khæng gian Banach, G l  ¡nh x¤ tø X v o Y v  ϕ l  h m gi¡ trà thüc tr¶n Y . Gi£ sû r¬ng G kh£ vi ch°t t¤i x v  ϕ Lipschitz àa ph÷ìng t¤i G(x). Khi â f = ϕ ◦ G l  Lipschitz àa ph÷ìng t¤i x v  ta câ ∂f (x) ⊂ (G0 (x))∗ ∂ϕ(G(x)). 13 ành ngh¾a 1.1.11. Tr¶n ç thà (epigraph) cõa h m f : X → R ÷ñc ành ngh¾a nh÷ sau: epi f := {(x, r) ∈ X × R : f (x) ≤ r}. ành lþ 1.1.8. Gi£ sû f l  h m Lipschitz àa ph÷ìng t¤i x̄. Khi â, Tepif (x̄, f (x̄)) = epi f ◦ (x̄, .), tùc l  (v, r) ∈ Tepif (x̄, f (x̄)) ⇔ f ◦ (x̄; v) ≤ r. Chùng minh. a) L§y (v, r) ∈ Tepif (x̄, f (x̄)). Ta chån d¢y {xi } → x̄ sao cho f (xi + ti v) − f (xi ) = f ◦ (x̄; v). i→∞ ti (1.9) lim Hiºn nhi¶n l  (xi, f (xi)) ∈ epif v  {(xi, f (xi))} → (x̄, f (x̄)). Theo ành lþ 2.12 [1], tçn t¤i d¢y {(vi, ri)} → (v, r) sao cho (xi , f (xi )) + ti (vi , ri ) ∈ epif. Do â, f (xi ) + ti ri ≥ f (xi + ti vi ) ⇒ f (xi + ti vi ) − f (xi ) ≤ ri ti cho i → ∞, tø (1.9) ta nhªn ÷ñc f ◦ (x̄; v) ≤ r ⇒ (v, r) ∈ epif ◦ (x̄, .). b) Ng÷ñc l¤i, ta ch¿ c¦n chùng minh r¬ng: vîi måi (v, f ◦ (x̄; v) + δ) ∈ Tepi f (x̄, f (x̄)). 14 v, δ ≥ 0 th¼ Gi£ sû {(xi, ri)} ⊂ epif hëi tö ¸n (x̄, f (x̄)) v  ti ↓ 0 ta ph£i chùng minh tçn t¤i d¢y {(vi, si)} → (v, f ◦(x̄; v) + δ) sao cho (xi , ri ) + ti (vi , si ) ∈ epif (∀i), tùc l  Ta l§y Bði v¼ f (xi + ti vi ) ≤ ri + ti si (∀i). f (xi + ti v) − f (xi ) vi = v, si = max{f ◦ (x̄; v) + δ, }. ti lim sup i→∞ f (xi + ti v) − f (xi ) ≤ f ◦ (x̄; v), ti cho n¶n si → f ◦(x̄; v) + δ v  nh÷ vªy (vi , si ) → (v, f ◦ (x̄; v) + δ). Ta câ (xi , ri ) ∈ epif ⇒ f (xi ) ≤ ri . Do â, ri + ti si ≥ ri + [f (xi + ti v) − f (xi )] ≥ f (xi + ti v). 1.2 D÷îi vi ph¥n x§p x¿ ành ngh¾a 1.2.1. Gi£ sû g : X → R l  mët h m Lipschitz àa ph÷ìng. ¤o h m theo ph÷ìng Dini d÷îi cõa g t¤i x theo ph÷ìng v ∈ X ÷ñc cho bði g − (x, v) = lim inf t↓0 g(x + tv) − g(x) . t D÷îi vi ph¥n Dini d÷îi cõa g t¤i x ÷ñc cho bði ∂ − g(x) = {x∗ ∈ X ∗ : g − (x, v) ≥ hx∗ , vi, vîi måi v ∈ X}. Cho L l  mët khæng gian con âng cõa X . Ta °t ∂L− g(x) = {x∗ ∈ X ∗ : g − (x, v) ≥ hx∗ , vi, 15 vîi måi v ∈ L}. Cho ¡nh x¤ a trà Φ : X ⇒ Y , giîi h¤n tr¶n cõa h m Φ(u) khi u → x ÷ñc ành ngh¾a nh÷ sau: lim sup Φ(u) = {y ∈ Y : ∃uk → x, yk → y u→x vîi yk ∈ Φ(uk ), ∀k = 1, 2, . . . }. Kþ hi»u F l  tªp hñp c¡c khæng gian húu h¤n chi·u cõa X . Khi â d÷îi vi ph¥n x§p x¿ ∂ag(x) cõa h m Lipschitz àa ph÷ìng g t¤i x ∈ X ÷ñc cho bði ∂a g(x) = \ lim sup ∂L− g(u). u→x L∈F Nân ph¡p tuy¸n cõa mët tªp âng D t¤i iºm x ∈ D ÷ñc cho bði Na (D, x) = [ λ∂a dD (x), λ≥0 trong â dD l  h m kho£ng c¡ch tr¶n tªp D v  nh÷ ta ¢ bi¸t h m kho£ng c¡ch dD l  h m Lipschitz vîi h¤ng b¬ng mët. Kh¡i ni»m d÷îi vi ph¥n x§p x¿ v  nân ph¡p tuy¸n ¢ ÷ñc Mordukhovich nghi¶n cùu trong [10], [11] trong khæng gian húu h¤n chi·u, Ioffe [8] ¢ mð rëng kh¡i ni»m trong khæng gian Banach. Bê · 1.2.1. Cho X l  khæng gian Banach, A ⊂ X, g v  ϕ Lipschitz àa ph÷ìng t¤i x ∈ X . Khi â, (i) 0 ∈ ∂ag(x) n¸u g ¤t cüc tiºu àa ph÷ìng t¤i x; (ii) ∂a(g + ϕ)(x) ⊂ ∂ag(x) + ∂aϕ(x); (iii) ∂g(x) = cl∗co(∂ag(x)), trong â cl∗co l  bao lçi âng ∗y¸u; (iv) N¸u g(x) = λϕ(Ax + y), trong â λ > 0 v  A l  to¡n tû tuy¸n t½nh bà ch°n tø X v o Y , th¼ ∂ag(x) = λA∗∂aϕ(Ax + y); (v) NC (A, x) = cl∗coNa(A, x), vîi måi x ∈ A. 16