Luận văn Dưới vi phân của hàm lồi và một số ứng dụng trong tối ưu

‖ 6 ‖x‖+ ‖y‖ = f(x) + f(y). MÖnh ®Ò 1.2. Cho f : Rn −→ R ∪ {+∞} lµ mét hµm thuÇn nhÊt d­¬ng trªn Rn. Khi ®ã: f låi khi vµ chØ khi f lµ d­íi céng tÝnh. 15 1.2.2 TÝnh liªn tôc cña hµm låi §Þnh nghÜa 1.20. Cho hµm f : E −→ R ∪ {−∞,+∞}. Hµm f ®­îc gäi lµ nöa liªn tôc d­íi t¹i mét ®iÓm x ∈ E nÕu víi mäi d·y {xk} ⊂ E, xk → x ta cã lim inf f(xk) > f(x). Hµm f ®­îc gäi lµ nöa liªn tôc trªn t¹i x ∈ E nÕu −f nöa liªn tôc d­íi t¹i x ∈ E. Nh­ vËy f nöa liªn tôc trªn t¹i x ∈ E nÕu víi mäi d·y {xk} ⊂ E, xk → x ta cã lim sup f(xk) 6 f(x). Hµm f ®­îc gäi lµ liªn tôc t¹i x ∈ E nÕu nh­ nã võa nöa liªn tôc trªn vµ nöa liªn tôc d­íi t¹i x ∈ E. Hµm f ®­îc gäi lµ nöa liªn tôc d­íi trªn E nÕu nã nöa liªn tôc d­íi t¹i mäi ®iÓm thuéc E. Hµm f ®­îc gäi lµ nöa liªn tôc trªn trªn E nÕu nã nöa liªn tôc trªn t¹i mäi ®iÓm thuéc E. Hµm f ®­îc gäi lµ liªn tôc trªn E nÕu nã nöa liªn tôc trªn vµ nöa liªn tôc d­íi trªn E. §Þnh nghÜa 1.21. Cho hai hµm f vµ g x¸c ®Þnh trªn Rn. Ta nãi g lµ bao ®ãng cña f , nÕu epi g = epi f . Bao ®ãng cña f sÏ ®­îc kÝ hiÖu lµ f . VËy epi f = epi f . Hµm f ®­îc gäi lµ ®ãng nÕu epi f = epi f . 1.2.3 C¸c phÐp to¸n b¶o toµn tÝnh låi §Þnh nghÜa 1.22. Gi¶ sö {fα}α∈I lµ mét hä tuú ý c¸c hµm sè trªn Rn vµ E ⊆ Rn. Hµm cËn trªn cña hä hµm nµy trªn coE, ký hiÖu lµ Vα∈Ifα lµ hµm sè ®­îc ®Þnh nghÜa nh­ sau: (Vα∈Ifα)(x) := Supα∈I fα(x) víi mçi x ∈ coE. 16 MÖnh ®Ò 1.3. Gi¶ sö {fα}α∈I lµ mét hä hµm låi trªn Rn vµ E ⊆ Rn. Khi ®ã hµm cËn trªn cña hä hµm nµy lµ mét hµm låi trªn coE. 1.2.4 BÊt ®¼ng thøc låi §Þnh nghÜa 1.23. Cho D ⊆ Rn lµ mét tËp låi vµ f1, ..., fm lµ c¸c hµm låi trªn Rn. HÖ bÊt ®¼ng thøc x ∈ D, fi(x) <= 0, i ∈ I ®­îc gäi lµ hÖ bÊt ®¼ng thøc låi, trong ®ã I lµ tËp chØ sè vµ ký hiÖu <= cã thÓ hiÓu lµ < hoÆc 6. MÖnh ®Ò 1.4. Cho f1, ..., fm lµ c¸c hµm låi h÷u h¹n trªn mét tËp låi D 6= ∅ vµ A lµ mét ma trËn thùc cÊp k × n. Gi¶ sö b ∈ riA(D). Khi ®ã hÖ x ∈ D, Ax = b, fi(x) < 0 i = 1, ..,m kh«ng cã nghiÖm, khi vµ chØ khi tån t¹i t ∈ Rk vµ λi > 0, i = 1, ..,m sao cho ∑m i=1 λi = 1 vµ 〈t, Ax− b〉+ m∑ i=1 λifi(x) > 0 ∀x ∈ D. 1.2.5 Hµm liªn hîp §Þnh nghÜa 1.24. Cho f : Rn −→ [−∞,+∞] lµ mét hµm bÊt kú. Hµm f ∗(x∗) := Sup{〈x∗, x〉 − f(x) | x ∈ Rn} ®­îc gäi lµ hµm liªn hîp cña f . Chó ý 1.2. Nh­ th­êng lÖ, trong ®Þnh nghÜa trªn ta qui ­íc cËn trªn ®óng trªn mét tËp rçng lµ −∞. Nh­ vËy nÕu f ≡ +∞, th× f ∗ ≡ −∞, ngoµi ra nÕu f cã nhËn gi¸ trÞ −∞ th× f ∗ ≡ +∞. §Ó khái ph¶i lµm viÖc víi hµm liªn hîp ®ång nhÊt b»ng +∞ hoÆc ®ång nhÊt b»ng −∞, ta sÏ h¹n chÕ viÖc xÐt hµm liªn hîp trong líp hµm cã tÝnh chÊt sau: f 6≡ +∞ vµ tån t¹i mét hµm non a-phin cña f. 17 VÝ dô 1.12. XÐt hµm chØ δC(x) = { 0 nÕu x ∈ C, +∞ nÕu x 6∈ C. Ta cã: δ∗C(x ∗) := Supx∈Rn{〈x∗, x〉 − δC(x)} = Supx∈C{〈x∗, x〉 − δC(x)} = Supx∈C{〈x∗, x〉 − 0} = Supx∈C〈x∗, x〉 = SC(x ∗). MÖnh ®Ò 1.5. Víi mäi hµm sè f , hµm liªn hîp f ∗ lµ mét hµm låi ®ãng tho¶ m·n bÊt ®¼ng thøc Fenchel sau: f ∗(x∗) > 〈x∗, x〉 − f(x) ∀x,∀x∗. Chó ý 1.3. Trong nhiÒu tr­êng hîp, ta quan t©m ®Õn hµm liªn hîp thø hai. Theo ®Þnh nghÜa hµm liªn hîp th× f ∗∗(x) := (f ∗)∗(x) = Sup{〈x, s〉 − f ∗(s) | s ∈ Rn}. Hµm liªn hîp thø hai tÊt nhiªn lu«n lµ mét hµm låi ®ãng. MÖnh ®Ò 1.6. Gi¶ sö f 6≡ +∞ vµ tån t¹i mét hµm non a-phin cña f . Khi ®ã epi f ∗∗ = co(epi f). HÖ qu¶ 1.3. f ≡ f ∗∗ khi vµ chØ khi f lµ hµm låi, ®ãng. §Þnh nghÜa 1.25. Hµm l lµ hµm non a-phin cña mét hµm f trªn Rn nÕu l lµ hµm a-phin trªn Rn vµ l(x) 6 f(x) ∀x ∈ Rn. Ch­¬ng 2 D­íi vi ph©n cña hµm låi PhÐp tÝnh vi ph©n lµ mét trong nh÷ng ®Ò tµi c¬ b¶n nhÊt cña gi¶i tÝch cæ ®iÓn. Trong gi¶i tÝch låi, lý thuyÕt nµy l¹i cµng trë nªn phong phó nhê nh÷ng tÝnh chÊt ®Æc biÖt cña tËp låi vµ hµm låi. Môc ®Çu tiªn cña ch­¬ng nµy sÏ xÐt ®Õn ®¹o hµm theo ph­¬ng cña mét hµm låi. TiÕp ®Õn ë môc 2, sÏ ®­a ra ®Þnh nghÜa vÒ d­íi vi ph©n vµ c¸c tÝnh chÊt cña nã nh­: XÐt tÝnh kh¶ vi cña hµm låi, kh¶o s¸t tÝnh ®¬n ®iÖu cña d­íi vi ph©n, kh¶o s¸t tÝnh liªn tôc cña ¸nh x¹ d­íi vi ph©n vµ mét sè phÐp tÝnh víi d­íi vi ph©n. Môc cuèi cña ch­¬ng sÏ giíi thiÖu vÒ d­íi vi ph©n xÊp xØ vµ mét sè tÝnh chÊt cña nã. 2.1 §¹o hµm theo ph­¬ng Cho mét hµm n-biÕn f : Rn −→ R∪{+∞}. Khi cè ®Þnh mét ph­¬ng vµ xÐt hµm nhiÒu biÕn trªn ph­¬ng ®ã , th× ta cã mét hµm mét biÕn. Gi¶ sö y 6= 0 lµ mét ph­¬ng cho tr­íc xuÊt ph¸t tõ ®iÓm x0. Khi ®ã mäi ®iÓm x thuéc ®­êng th¼ng ®i qua x0 vµ cã ph­¬ng y ®Òu cã d¹ng x = x0 + λy víi λ ∈ R. NÕu ®Æt ξ(λ) = f(x0 + λy) th× ξ låi trªn R khi vµ chØ khi f låi trªn Rn. §Þnh nghÜa 2.1. Cho f : Rn −→ R ∪ {+∞} vµ x0 ∈ Rn sao cho f(x0) < +∞. NÕu víi mét vÐc-t¬ y ∈ Rn mµ giíi h¹n lim λ→0 f(x0+λy)−f(x0) λ tån t¹i (h÷u h¹n hay v« h¹n) th× ta nãi f cã ®¹o hµm theo ph­¬ng y t¹i ®iÓm x0. Ta sÏ ký hiÖu giíi h¹n nµy lµ f ′(x0, y). 18 19 VÝ dô 2.1. Gi¶ sö f ®­îc cho nh­ sau: f(x) =  0 nÕu x < 0, 1 nÕu x = 0, +∞ nÕu x > 0. Ta cã dom f = (−∞; 0]⇒ dom f 6= ∅ , f(x) > −∞,∀x . VËy f lµ hµm chÝnh th­êng . Ta cã: f ′(0,−1) = lim λ→0 f(0+λ(−1))−f(0) λ = limλ→0 0−1 λ = −∞, f ′(0, 0) = lim λ→0 f(0+λ0)−f(0) λ = limλ→0 1−1 λ = 0, f ′(0, 1) = lim λ→0 f(0+λ1)−f(0) λ = limλ→0 ∞−1 λ = +∞. Suy ra f ′(0, .) kh«ng lµ hµm chÝnh th­êng. MÖnh ®Ò 2.1. Cho f : Rn −→ R ∪ {+∞} låi. Khi ®ã víi mäi x ∈ dom f vµ mäi y ∈ Rn ta cã: i) ϕ lµ hµm ®¬n ®iÖu kh«ng gi¶m trªn (0; +∞) , trong ®ã ϕ(λ) := f(x+ λy)− f(x) λ , vµ do ®ã f ′(x, y) tån t¹i víi mäi y ∈ Rn vµ f ′(x, y) := infλ>0 f(x+ λy)− f(x) λ . ii) Hµm f ′(x, .) thuÇn nhÊt d­¬ng bËc 1. Ngoµi ra nÕu f ′(x, .) > −∞ th× hµm f ′(x, .) lµ d­íi tuyÕn tÝnh trªn Rn (do ®ã nã lµ hµm låi chÝnh th­êng trªn Rn). iii) −f ′(x,−y) 6 f ′(x, y) ∀y ∈ Rn. iv) Hµm f ′(x, .) nhËn gi¸ trÞ h÷u h¹n trªn F khi vµ chØ khi x ∈ ri(dom f), trong ®ã F lµ kh«ng gian con cña dom f . Chøng minh. i) Ta chøng minh hµm ϕ ®¬n ®iÖu kh«ng gi¶m trªn miÒn (0; +∞). 20 §Þnh nghÜa hµm h : R −→ R ∪ {+∞} x¸c ®Þnh bëi h(λ) = f(x+ λ.y)− f(x). Khi ®ã h(0) = 0. Gi¶ sö 0 < λ′ 6 λ, do f lµ hµm låi nªn h lµ hµm låi , kh«ng nhËn gi¸ trÞ −∞. Ta cã h(λ′) = h[ λ′ λ λ+ (1− λ ′ λ )0] 6 λ ′ λ h(λ) + (1− λ ′ λ )h(0) = λ′ λ h(λ). Do ϕ(λ) = f(x+λy)−f(x)λ = h(λ) λ nªn ϕ(λ ′) 6 ϕ(λ). VËy ϕ lµ hµm kh«ng gi¶m trªn miÒn (0; +∞). Suy ra f ′(x, y) = lim λ→0 ϕ(λ) tån t¹i vµ lim λ→0 ϕ(λ) = infλ>0 ϕ(λ) = infλ>0 f(x+ λ.y)− f(x) λ . ii) Theo ®Þnh nghÜa, ta cã f ′(x, 0) = lim λ→0 f(x+ λ0)− f(x) λ = 0. Chøng minh tÝnh thuÇn nhÊt d­¬ng . Víi t > 0, ta viÕt f ′(x, ty) = lim λ→0 f(x+ λty)− f(x) λ . §Æt λ′ = λt, ta cã tiÕp f ′(x, ty) = t lim λ→0 f(x+ λ′y)− f(x) λ′ = tf ′(x, y). VËy f ′(x, .) thuÇn nhÊt d­¬ng. Chøng minh tÝnh d­íi tuyÕn tÝnh. 21 Gi¶ sö f ′(x, .) > −∞, víi mäi u vµ v ta cã: f ′(x, u+ v) = infλ>0 f [x+ λ2(u+ v)]− f(x) λ 2 (theo i) = infλ>0 f [(x2 + λ 2u) + ( x 2 + λ 2v)]− 12f(x)− 12f(x) λ 2 . Do f lµ hµm låi kh«ng nhËn gi¸ trÞ −∞ ,nªn f [( x 2 + λ 2 u) + ( x 2 + λ 2 v)]− 1 2 f(x)− 1 2 f(x) 6 1 2 [f(x+ λu)− f(x)] + 1 2 [f(x+ λv)− f(x)]. Do ®ã f ′(x, u+ v) 6 infλ>0 f(x+ λu) λ + infλ>0 f(x+ λv) λ = f ′(x, u) + f ′(x, v). (f ′(x, u) + f ′(x, v) cã nghÜa v× f ′(x, .) > −∞). VËy f ′(x, .) lµ hµm d­íi céng tÝnh. Suy ra f ′(x, .) lµ hµm d­íi tuyÕn tÝnh trªn Rn. V× f ′(x, .) > −∞, f ′(x, 0) = 0 vµ f ′(x, .) lµ d­íi tuyÕn tÝnh trªn Rn, nªn nã lµ hµm låi, chÝnh th­êng trªn toµn kh«ng gian. iii) Do f ′(x, 0) = 0 vµ theo tÝnh chÊt d­íi céng tÝnh, ta cã: 0 = f ′(x, 0) = f ′(x, y − y) 6 f ′(x, y) + f ′(x,−y) ∀y ∈ Rn. Suy ra −f ′(x,−y) 6 f ′(x, y) víi mäi y ∈ Rn. iv) Gi¶ sö x ∈ ri(dom f) . Ta cÇn chøng tá f ′(x, .) h÷u h¹n trªn F . Tõ iii) suy ra f ′(x, .) > −∞. VËy cÇn chØ ra f ′(x, y) < +∞ víi mäi y ∈ F . Do x ∈ ri(dom f), nªn ∀y ∈ F , x+ λ.y ∈ dom f ∀λ > 0 ®ñ nhá. Do ®ã f ′(x, y) = infλ>0 f(x+λ.y)−f(x) λ < +∞. Ng­îc l¹i, gi¶ sö f ′(x, y) h÷u h¹n víi mäi y ∈ F . Ta cÇn chøng tá x ∈ ri(dom f). 22 ThËt vËy, nÕu tr¸i l¹i sÏ tån t¹i y ∈ F vµ mét d·y {λk} c¸c sè d­¬ng héi tô ®Õn 0 vµ x+ λk.y 6∈ dom f víi mäi k ®ñ lín. Trong tr­êng hîp nµy f(x+ λk.y)− f(x) = +∞ víi mäi k ®ñ lín. Do ®ã f ′(x, y) = +∞. M©u thuÉn víi gi¶ thiÕt. VËy x ∈ ri(dom f). 2.2 D­íi vi ph©n vµ c¸c tÝnh chÊt 2.2.1 D­íi vi ph©n §Þnh nghÜa 2.2. Cho f : Rn −→ R ∪ {+∞}. Ta nãi x∗ ∈ Rn lµ d­íi ®¹o hµm cña f t¹i x nÕu 〈x∗, z − x〉+ f(x) 6 f(z) ∀z. KÝ hiÖu tËp hîp tÊt c¶ c¸c d­íi ®¹o hµm cña f t¹i x lµ ∂f(x). VËy ∂f(x) lµ mét tËp (cã thÓ b»ng ∅) trong Rn. Khi ∂f(x) 6= ∅, th× ta nãi hµm f kh¶ d­íi vi ph©n t¹i x. Theo ®Þnh nghÜa, mét ®iÓm x∗ ∈ ∂f(x) khi vµ chØ khi nã tho¶ m·n mét hÖ v« h¹n c¸c bÊt ®¼ng thøc tuyÕn tÝnh . Nh­ vËy ∂f(x) lµ giao cña c¸c nöa kh«ng gian ®ãng. VËy ∂f(x) lu«n lµ mét tËp låi ®ãng (cã thÓ rçng). KÝ hiÖu dom(∂f) := {x|∂f(x) 6= ∅}. VÝ dô 2.2. 1) Hµm chuÈn f(x) = ‖x‖, x ∈ Rn. T¹i ®iÓm x = 0, ta cã ∂f(0) = {x∗|〈x∗, x〉 6 ‖x‖,∀x}. VËy hµm f(x) kh¶ d­íi vi ph©n. L¹i cã lim x→0 f(x)− f(0)− 〈x∗, x− 0〉 ‖x− 0‖ = limx→0 ‖x‖ − 〈x∗, x〉 ‖x‖ = 1 6= 0. VËy hµm f(x) kh«ng kh¶ vi t¹i x = 0. 23 2) Hµm chØ f(x) = δC(x) := { 0 nÕu x ∈ C, +∞ nÕu x 6∈ C. Trong ®ã C lµ mét tËp låi kh¸c ∅. Khi ®ã víi x0 ∈ C, ta cã ∂f(x0) = ∂δC(x 0) = {x∗|〈x∗, x− x0〉 6 δC(x),∀x}. Víi x 6∈ C th× δC(x) = +∞, nªn bÊt ®¼ng thøc nµy lu«n ®óng. VËy ∂f(x0) = ∂δC(x 0) = {x∗|〈x∗, x− x0〉 6 0,∀x ∈ C} = NC(x0). VËy d­íi vi ph©n cña hµm chØ cña mét tËp låi C kh¸c ∅ t¹i mét ®iÓm x0 ∈ C chÝnh lµ nãn ph¸p tuyÕn ngoµi cña C t¹i x0. MÖnh ®Ò 2.2. i) x∗ ∈ ∂f(x) khi vµ chØ khi f ′(x, y) > 〈x∗, y〉 ,∀y. ii) NÕu f lµ hµm låi chÝnh th­êng trªn Rn, th× víi mäi x ∈ dom(∂f), ta cã f(x) = f(x) vµ ∂f(x) = ∂f(x). Chøng minh. i) Theo ®Þnh nghÜa x∗ ∈ ∂f(x)⇔ 〈x∗, z − x〉+ f(x) 6 f(z) ∀z. Víi bÊt k× y, lÊy z = x+ λ.y, λ > 0, ta cã 〈x∗, λ.y〉+ f(x) 6 f(x+ λ.y). Tõ ®©y suy ra 〈x∗, y〉 6 f(x+ λ.y)− f(x) λ ∀λ > 0. (2.1) Theo ®Þnh nghÜa cña f ′(x, y), suy ra ngay 〈x∗, y〉 6 f ′(x, y) ∀y. Ng­îc l¹i, gi¶ sö (2.1) tho¶ m·n. LÊy z bÊt k× vµ ¸p dông (2.1) víi y = z − x vµ λ = 1, ta cã 〈x∗, z − x〉 6 f(z)− f(x) ∀z. VËy x∗ ∈ ∂f(x). ii) Cho x ∈ dom(∂f), th× ∂f(x) 6= ∅, tøc lµ tån t¹i x∗ ∈ ∂f(x). 24 Theo ®Þnh nghÜa cña f , ta cã epi f = epi f . MÆt kh¸c, ta l¹i cã epi f ⊂ epi f , suy ra epi f ⊂ epi f . VËy f(x) > f(x). (2.2) Theo gi¶ thiÕt f lµ hµm låi chÝnh th­êng trªn Rn, nªn f lµ hµm låi ®ãng trªn Rn, theo hÖ qu¶ 1.1, ta cã f(x) = f ∗∗(x). (2.3) Theo tÝnh chÊt cña hµm liªn hîp thø 2, ta cã f ∗∗(x) >< 〈x∗, x〉 − f ∗(x∗) = f(x). (2.4) Tõ (2.2),(2.3) vµ (2.4) ta cã f(x) = f(x). Ta lÊy y∗ ∈ ∂f(x) th× ∀z tacã 〈y∗, z − x〉+ f(x) 6 f(z). MÆt kh¸c f(z) > f(z) > 〈y∗, z − x〉+ f(x) = 〈y∗, z − x〉+ f(x). Suy ra y∗ ∈ ∂f(x). VËy ∂f(x) ⊂ ∂f(x). (2.5) Ng­îc l¹i, lÊy z0 ∈ ri(dom f). Víi mäi z ta cã f(z) = f(z) = lim t→0 f [(1− t).z + t.z0]. VËy theo ®Þnh nghÜa cña d­íi vi ph©n ta cã : x∗ ∈ ∂f(x)⇔ 〈x∗, (1− t).z + t.z0 − x〉+ f(x) 6 f [(1− t).z + t.z0]. Cho t→ 0 ta ®­îc : 〈x∗, z − x〉+ f(x) 6 f(z). 25 Hay 〈x∗, z − x〉+ f(x) 6 f(z) Chøng tá x∗ ∈ ∂f(x). VËy ∂f(x) ⊂ ∂f(x). (2.6) Tõ (2.5) vµ (2.6) ta cã ∂f(x) = ∂f(x). MÖnh ®Ò 2.3. Cho f : Rn −→ R ∪ {+∞} låi, khi ®ã : i) NÕu x 6∈ dom f , th× ∂f(x) = ∅. ii) x ∈ ri(dom f) khi vµ chØ khi ∂f(x) 6= ∅ vµ comp¾c. Chøng minh. i) Cho z ∈ dom f , th× f(z) < +∞. VËy nÕu x 6∈ dom f th× f(x) = +∞ vµ do ®ã kh«ng thÓ tån t¹i x∗ tho m·n 〈x∗, z − x〉+ f(x) 6 f(z) < +∞. VËy ∂f(x) = ∅. ii) Gi¶ sö x ∈ ri(dom f). Ta cã ®iÓm (x, f(x)) n»m trªn biªn cña epi f . Do f låi, chÝnh th­êng, nªn tån t¹i siªu ph¼ng tùa cña epi f ®i qua (x, f(x)). Tøc lµ tån t¹i p ∈ Rn, t ∈ R kh«ng ®ång thêi b»ng 0 sao cho 〈p, x〉+ t.f(x) 6 〈p, y〉+ t.µ , ∀(y, µ) ∈ epi f. (2.7) Ta cã t 6= 0, v× nÕu t = 0 th× 〈p, x〉 6 〈p, y〉 ,∀y ∈ dom f . Hay 〈p, x− y〉 6 0 ,∀y ∈ dom f . Nh­ng do x ∈ ri(dom f), nªn ®iÒu nµy kÐo theo p = 0. M©u thuÉn víi p, t kh«ng ®ång thêi b»ng 0. VËy t 6= 0. H¬n n÷a t > 0, v× nÕu t < 0 th× trong bÊt ®¼ng thøc (2.7), khi cho µ→∞ ta suy ra m©u thuÉn v× vÕ tr¸i cè ®Þnh. Chia hai vÕ cña (2.7) cho t > 0, ta ®­îc: 〈p t , x〉+ f(x) 6 〈p t , y〉+ µ ∀y ∈ dom f. 26 Thay µ = f(y), ta ®­îc 〈p t , x〉+ f(x) 6 〈p t , y〉+ f(y) ∀y ∈ dom f. §Æt x∗ = −pt , ta ®­îc −〈x∗, x〉+ f(x) 6 −〈x∗, y〉+ f(y) ∀y ∈ dom f. Hay 〈x∗, y − x〉+ f(x) 6 f(y) ∀y ∈ dom f. NÕu y 6∈ dom f th× f(y) =∞, do ®ã 〈x∗, y − x〉+ f(x) 6 f(y) ∀y. Chøng tá x∗ ∈ ∂f(x). VËy ∂f(x) 6= ∅ . B©y giê ta chØ ra tËp ∂f(x) comp¾c. Do x ∈ ri(dom f), theo mÖnh ®Ò (2.2) x∗ ∈ ∂f(x)⇐⇒ f ′(x, d) > 〈x∗, d〉 ∀d. (2.8) Gäi F lµ kh«ng gian tuyÕn tÝnh cña dom f . LÊy ei lµ vÐc-t¬ ®¬n vÞ thø i (i=1,...,n) cña Rn (to¹ ®é thø i cña ei b»ng 1 vµ mäi to¹ ®é kh¸c lµ 0). Kh«ng gi¶m tæng qu¸t, ta gi¶ sö r»ng c¸c vÐc-t¬ ®¬n vÞ e1, ...ek ∈ F , ¸p dông (2.8) lÇn l­ît víi d = ei víi i=1,...k, ta cã x∗i 6 f ′(x, ei). T­¬ng tù , ¸p dông víi d = −ei víi i=1,...k, ta cã −x∗i 6 f ′(x,−ei). Hay x∗i > −f ′(x,−ei). Tãm l¹i −f ′(x,−ei) 6 x∗i 6 f ′(x, ei) ,víi mäi i=1,...k. Theo (iv) mÖnh ®Ò (2.1), do x ∈ ri(dom f) vµ F lµ kh«ng gian con cña dom f , nªn f ′(x, y) h÷u h¹n víi mäi y ∈ F . Nãi riªng f ′(x,−ei) vµ f ′(x, ei) h÷u h¹n víi mäi i=1,...k. VËy ∂f(x) bÞ chÆn , vµ do tÝnh ®ãng nªn nã lµ comp¾c. Ng­îc l¹i, gi¶ sö r»ng ∂f(x) 6= ∅ vµ ∂f(x) comp¾c. Ta chØ ra r»ng x ∈ ri(dom f). Do ∂f(x) 6= ∅ nªn x ∈ dom f . NÕu tr¸i l¹i x 6∈ ri(dom f), th× x ë trªn biªn t­¬ng ®èi cña dom f . 27 Do dom f låi, theo mÖnh ®Ò vÒ siªu ph¼ng tùa, tån t¹i mét siªu ph¼ng tùa cña dom f t¹i x, tøc lµ tån t¹i vect¬ p ∈ Rn, p 6= 0 sao cho 〈p, x〉 > 〈p, z〉 ∀z ∈ dom f. LÊy x∗ ∈ ∂f(x). Tõ ®©y vµ theo ®Þnh nghÜa d­íi vi ph©n ta cã: f(z)− f(x) > 〈x∗, z − x〉 > 〈x∗, z − x〉+ λ.〈p, z − x〉 = 〈x∗ + λ.p, z − x〉 ∀λ > 0,∀z. Chøng tá x∗ + λ.p ∈ ∂f(x) ∀λ > 0. §iÒu nµy m©u thuÉn víi tÝnh bÞ chÆn cña ∂f(x). VËy x ∈ ri(dom f). VÝ dô 2.3. Cho hµm mét biÕn f(x) = { −2x 12 nÕu x > 0, +∞ nÕu x < 0. Ta cã dom f = [0; +∞) , 0 6∈ int(dom f). x∗ ∈ ∂f(0)⇔ 〈x∗, x〉+ f(0) 6 f(x) ,∀x ⇔ x∗.x 6 −2x 12 ,∀x > 0. (2.9) NÕu x∗ < 0 , ta chän x = 0.01 th× (2.9) kh«ng tho¶ m·n. NÕu x∗ 6 0 th× (2.9) kh«ng tho¶ m·n. VËy ∂f(0) = ∅. VÝ dô trªn cho thÊy nÕu x 6∈ int(dom f) th× tËp ∂f(x) cã thÓ b»ng rçng. MÖnh ®Ò 2.4. Cho f : Rn −→ R ∪ {+∞} vµ x ∈ dom f . Khi ®ã i) NÕu x ∈ ri(dom f), th× f ′(x, y) = maxx∗∈∂f(x) 〈x∗, y〉 ,∀y. ii) Víi mäi tËp bÞ chÆn C ⊂ int(dom f), tËp ∪x∈C∂f(x) bÞ chÆn . iii) NÕu cã thªm f ®ãng, th× f ∗(x∗) + f(x) = 〈x∗, x〉 ⇐⇒ x∗ ∈ ∂f(x), x ∈ ∂f(x∗). 28 Chøng minh. i) Do f ′(x, .) lµ hµm låi, thuÇn nhÊt d­¬ng, nªn mäi hµm non a-phin cña f ′(x, .) ®Òu tuyÕn tÝnh, tøc lµ cã d¹ng 〈p, .〉. VËy nÕu 〈p, .〉 lµ hµm non a-phin cña f ′(x, .) trªn Rn, th× 〈p, y〉 6 f ′(x, y) ,∀y. Theo mÖnh ®Ò 2.2 ta cã p ∈ ∂f(x). H¬n n÷a, do f ′(x, .) lµ mét hµm låi ®ãng, nªn theo ®Þnh lý xÊp xØ tËp låi nã lµ bao trªn cña c¸c hµm non a-phin cña nã. VËy f ′(x, y) = Supp∈∂f(x) 〈p, y〉. ii) Gi¶ sö C ⊆ int(dom f). §Æt ξ = Supx∗∈∂f(C) ‖x∗‖ = Supx∈C Supx∗∈∂f(C) ‖x∗‖ (2.10) XÐt ¸nh x¹ tuyÕn tÝnh 〈x∗, z〉. ChuÈn cña ¸nh x¹ tuyÕn tÝnh nµy lµ ‖x∗‖ = Sup‖z‖=1 〈x∗, z〉. Thay vµo (2.10) ta cã : ξ = Supx∈C Supx∗∈∂f(C) Sup‖z‖=1 〈x∗, z〉. Do f ′(x, z) = Supx∗∈∂f(x) 〈x∗, z〉 nªn ta cã tiÕp ξ = Sup‖z‖=1 Supx∈C f ′(x, z). §Æt g(z) = Supx∈C f ′(x, z). Do x ∈ C ⊆ int(dom f), nªn hµm f ′(x, .) låi trªn Rn ( do ®ã liªn tôc ). Suy ra hµm g liªn tôc v× lµ bao trªn cña mét hä hµm låi liªn tôc trªn Rn. VËy ξ = Sup‖z‖=1 g(z) = max‖z‖=1 g(z) < +∞. Chøng tá ∂f(C) bÞ chÆn. 29 iii) Theo ®Þnh nghÜa hµm liªn hîp, ta cã f ∗(x∗) = Supx {〈x∗, x〉 − f(x)}. §iÒu nµy t­¬ng ®­¬ng víi f ∗(x∗) > 〈x∗, y〉 − f(y) ,∀y. Do ®ã f ∗(x∗) + f(x) = 〈x∗, x〉 ⇔ 〈x∗, y〉 − f(y) + f(x) 6 〈x∗, x〉 ,∀y. Hay 〈x∗, y − x〉+ f(x) 6 f(y) ,∀y. VËy x∗ ∈ ∂f(x). Do f ®ãng, nªn theo hÖ qu¶ 1.1, ta cã f = f ∗∗. Theo ®Þnh nghÜa cña hµm liªn hîp, ta cã: f ∗∗ = Supx∗ {〈x, x∗〉 − f ∗(x∗)}. §iÒu nµy t­¬ng ®­¬ng víi f ∗∗(x) > 〈x, y〉 − f ∗(y) ,∀y. Hay f(x) > 〈x, y〉 − f ∗(y) ,∀y. Do ®ã f ∗(x∗) + f(x) = 〈x∗, x〉 ⇔ 〈x, y〉 − f ∗(y) + f ∗(x∗) 6 〈x∗, x〉 ,∀y. Hay 〈x, y − x∗〉+ f ∗(x∗) 6 f ∗(y) ,∀y. VËy x ∈ ∂f ∗(x∗). 30 2.2.2 TÝnh kh¶ vi cña hµm låi §Þnh nghÜa 2.3. Cho mét hµm f x¸c ®Þnh trªn mét l©n cËn cña x ∈ Rn. Hµm f ®­îc gäi lµ kh¶ vi t¹i x, nÕu tån t¹i x∗ sao cho lim z→x f(z)− f(x)− 〈x∗, z − x〉 ‖z − x‖ = 0. Mét ®iÓm x∗ nh­ thÕ nÕu tån t¹i sÏ duy nhÊt vµ ®­îc gäi lµ ®¹o hµm cña f t¹i x. Th«ng th­êng ®¹o hµm nµy ®­îc kÝ hiÖu lµ Of(x) hoÆc f ′(x). Gi¶ sö f : Rn −→ R ∪ {+∞} låi, chÝnh th­êng vµ x ∈ dom f . NÕu f kh¶ vi t¹i x, th× víi mäi y 6= 0, ta cã: lim λ→0 f(x+ λ.y)− f(x)− 〈Of(x), λ.y〉 λ.‖y‖ = 0. Hay lµ f ′(x, y)− 〈Of(x), y〉 ‖y‖ = 0. Suy ra f ′(x, y) = 〈Of(x), y〉 ,∀y. LÊy y = ei (i=1,...,n) lµ vÐc-t¬ ®¬n vÞ thø i cña Rn, ta cã : 〈Of(x), ei〉 = ( ∂f ∂xi )(x)(i = 1, .., n). VËy f ′(x, y) = n∑ i=1 yi( ∂f ∂xi )(x). Tõ ®©y ta cã mÖnh ®Ò sau: MÖnh ®Ò 2.5. Gi¶ sö f : Rn −→ R ∪ {+∞} låi, chÝnh th­êng vµ x ∈ dom f . Khi ®ã f kh¶ vi t¹i x khi vµ chØ khi tån t¹i x∗ ∈ Rn sao cho f ′(x, y) = 〈x∗, y〉 ,∀y. Ngoµi ra x ∈ int(dom f) vµ Of(x) = x∗. Chøng minh. NÕu f kh¶ vi t¹i x th× nh­ ë trªn, ta ®· chØ ra r»ng f ′(x, y) = 〈Of(x), y〉 ,∀y. 31 VËy f ′(x, y) h÷u h¹n trªn toµn Rn, nªn x ∈ int(dom f). Ng­îc l¹i f ′(x, y) = 〈Of(x), y〉 ,∀y. Tr­íc hÕt ta cã x ∈ int(dom f) v× f ′(x, .) h÷u h¹n trªn toµn Rn. §Ó chøng minh tÝnh kh¶ vi cña f t¹i x, ta lÊy g(y) := f(x+ y)− f(x)− 〈x∗, y〉. Do f låi, chÝnh th­êng vµ f h÷u h¹n, nªn g còng lµ mét hµm låi, chÝnh th­êng trªn Rn. Ta cÇn chøng tá lim y→0 g(y) ‖y‖ = 0. Tr­íc hÕt tõ f ′(x, y) = 〈x∗, y〉, theo ®Þnh nghÜa cña f ′(x, y), ta cã g(y) > 0 ,∀y vµ g(0) = 0. NÕu y 6= 0 th× vÐc-t¬ y‖y‖ thuéc siªu hép H := [−1, 1]n. VËy theo ®Þnh lý Krein-Milman ®iÓm y ‖y‖ biÓu diÔn ®­îc bëi mét tæ hîp låi cña c¸c ®Ønh cña H, tøc lµ tån t¹i c¸c sè thùc βi (phô thuéc y) sao cho βi > 0, ∑ i∈I βi = 1 vµ y ‖y‖ = ∑ i∈I βiv i, trong ®ã vi(i ∈ I) lµ c¸c ®Ønh cña H. Ta cã g(y) := g(‖y‖ y‖y‖) = g(‖y‖ ∑ i∈I βiv i) = g( ∑ i∈I βi‖y‖vi). Theo tÝnh låi cña g th× g( ∑ i∈I βi‖y‖vi) 6 ∑ i∈I βig(‖y‖vi). Tãm l¹i 0 6 g(y)‖y‖ 6 ∑ i∈I βi g(‖y‖vi) ‖y‖ . Theo ®Þnh nghÜa cña g ta l¹i cã g(‖y‖vi) ‖y‖ → 0 khi y → 0. VËy g(y) ‖y‖ → 0. Chøng tá f kh¶ vi t¹i x vµ do ®ã Of(x) = x∗. 32 MÖnh ®Ò 2.6. Cho f : Rn −→ R ∪ {+∞} kh¶ vi vµ C ⊂ Rn. Ba ®iÒu kiÖn sau t­¬ng ®­¬ng. a) η lµ hÖ sè låi cña f trªn C. b) f(y) > f(x) + 〈f ′(x), y − x〉+ η2‖x− y‖2 ∀x, y ∈ C c)〈f ′(y)− f ′(x), y − x〉 > η‖x− y‖2 ∀x, y ∈ C Chøng minh. (a)→ (b): Do η lµ hÖ sè låi cña trªn C, nªn víi t ∈ (0; 1) vµ mäi x,y thuéc C ta cã: f [t.y + (1− t)x] 6 tf(y) + (1− t)f(x)− η 2 t(1− t)‖x− y‖2. Suy ra f(y)− f(x) > f [ty + (1− t)x]− f(x) + η 2t(1− t)‖x− y‖2 t = f [x+ t(y − x)]− f(x) t + η 2 (1− t)‖x− y‖2. Cho t→ 0, do f kh¶ vi, ta ®­îc: f(y)− f(x) > f ′(x, y − x) + η 2 ‖x− y‖2. (b)→(a): Cho t ∈ (0; 1) vµ ω = (1− t)x+ ty. Khi ®ã y = ω + (1− t)(y − x), x = ω + (−t)(y − x). Ap dông (b), ta ®­îc: f(y) > f(ω) + 〈f ′(ω), y − ω〉+ η 2 ‖ω − y‖2, f(x) > f(ω) + 〈f ′(ω), x− ω〉+ η 2 ‖ω − x‖2. Hay f(y) > f(ω) + 〈f ′(ω), (1− t)(y − x)〉+ η 2 (1− t)2‖y − x‖2, f(x) > f(ω) + 〈f ′(ω), (−t)(y − x)〉+ η 2 t2‖y − x‖2. 33 Nh©n bÊt ®¼ng thøc trªn víi t > 0 vµ bÊt ®¼ng thøc d­íi víi 1− t > 0 ta ®­îc : tf(y) > tf(ω) + 〈f ′(ω), t(1− t)(y − x)〉 + η 2 t(1− t)2‖y − x‖2, (1− t)f(x) > (1− t)f(ω) + 〈f ′(ω),−t(1− t)(y − x)〉 + η 2 t2(1− t)‖y − x‖2. Céng hai bÊt ®¼ng thøc trªn vµ chuyÓn vÕ, ta cã: tf(y) + (1− t)f(x) > f(ω) + η 2 t(1− t)‖y − x‖2. Hay f [(1− t)x+ ty] 6 (1− t)f(x) + tf(y)− η 2 t(1− t)‖y − x‖2. Chøng tá η lµ hÖ sè låi cña f trªn C. (b)→(c): Do (b), nªn ∀x, y ∈ C, ta cã: f(y)− f(x) > 〈f ′(x), y − x〉+ η 2 ‖x− y‖2, f(x)− f(y) > 〈f ′(y), x− y〉+ η 2 ‖x− y‖2. Céng hai bÊt ®¼ng thøc l¹i ta ®­îc: 0 > 〈f ′(x)− f ′(y), y − x〉+ η‖x− y‖2. Hay 〈f ′(y)− f ′(x), y − x〉 > η‖x− y‖2. (c)→(b): §Æt γ(t) = f [(1− t)x+ ty] = f [x+ t(y − x)]. Khi ®ã γ′(t) = 〈f ′[x+ t(y − x)], y − x〉, 34 vµ f(y)− f(x) = γ(1)− γ(0) = ∫ 1 0 γ′(t)dt. B©y giê gi¶ sö cã (c). Víi x, y ∈ C, ®Æt h := y − x. Khi ®ã f(y)− f(x) = ∫ 1 0 γ′(t)dt = ∫ 1 0 〈f ′[x+ t(y − x)], y − x〉dt = ∫ 1 0 f ′(x+ th).hdt = ∫ 1 0 [f ′(x) + f ′(x+ th)− f ′(x)]hdt = ∫ 1 0 (f ′(x)h+ [f ′(x+ th)− f ′(x)]h)dt = f ′(x)ht|10 + ∫ 1 0 [f ′(x+ th)− f ′(x)]hdt = f ′(x)h+ ∫ 1 0 [f ′(x+ th)− f ′(x)]hdt. Theo (c) ta cã : 〈f ′(x+ th)− f ′(x), th〉 > η‖th‖2, hay [f ′(x+ th)− f ′(x)]h > ηt‖h‖2. Suy ra ∫ 1 0 [f ′(x+ th)− f ′(x)]hdt > ∫ 1 0 ηt‖h‖2dt = η t2 2 ‖h‖2|10 = η 2 ‖h‖2. VËy f(y)− f(x) > f ′(x)h+ η 2 ‖h‖2, 35 hay f(y)− f(x) > 〈f ′(x), y − x〉+ η 2 ‖y − x‖2. 2.2.3 TÝnh ®¬n ®iÖu cña d­íi vi ph©n Cho T lµ mét to¸n tö ®a trÞ trªn Rn, tøc lµ víi mçi x ∈ Rn, th× T (x) lµ mét tËp (cã thÓ b»ng rçng). Nh­ th­êng lÖ ta ký hiÖu tËp hîp tÊt c¶ c¸c tËp con cña Rn lµ 2R n . KÝ hiÖu miÒn x¸c ®Þnh cña T lµ domT := {x ∈ Rn | T (x) 6= ∅}, vµ ®å thÞ cña T lµ G(T ) := {(x, y) ∈ Rn ×Rn | y ∈ T (x)}. §Þnh nghÜa 2.4. Cho T : Rn −→ 2Rn vµ C ⊆ domT . Ta nãi T lµ ®¬n ®iÖu tuÇn hoµn trªn C, nÕu víi mäi sè nguyªn d­¬ng m vµ mäi cÆp (xi, yi) ∈ G(T ), xi ∈ C (i=0,...,m) ta cã: 〈x1 − x0, y0〉+ 〈x2 − x1, y1〉+ ...+ 〈x0 − xm, ym〉 6 0. (2.11) NÕu (2.11) chØ ®óng víi m = 1, th× ta nãi T ®¬n ®iÖu trªn C, tøc lµ 〈y − y′, x− x′〉 > 0 ,∀x, x′ ∈ C , ∀y ∈ T (x) ,∀y′ ∈ T (x′). NÕu T ®¬n ®iÖu (hoÆc ®¬n ®iÖu tuÇn hoµn) trªn toµn domT , th× ta nãi ng¾n gän lµ T ®¬n ®iÖu (®¬n ®iÖu tuÇn hoµn). NÕu T ≡ ∂f th× T ®¬n ®iÖu tuÇn hoµn trªn dom(∂f). ThËt vËy: ∀m ∈ N ,∀(xi, yi) ∈ G(∂f) , xi ∈ dom(∂f) (i = 0, ...n) ta cã: G(∂f) = {(xi, yi) | yi ∈ ∂f(xi)}. 36 Suy ra 〈y0, x1 − x0〉+ f(x0) 6 f(x1) 〈y1, x2 − x1〉+ f(x1) 6 f(x2) ... ... ... 〈ym, x0 − xm〉+ f(xm) 6 f(x0). Céng vÕ víi vÕ cña c¸c bÊt ®¼ng thøc trªn, ta ®­îc: 〈y0, x1 − x0〉+ 〈y1, x2 − x1〉+ ...+ 〈ym, x0 − xm〉 6 0. Theo ®Þnh nghÜa, T ≡ ∂f ®¬n ®iÖu tuÇn hoµn trªn dom(∂f). Mét c©u hái ®­îc ®Æt ra lµ ®iÒu ng­îc l¹i cã ®óng kh«ng? Tr¶ lêi c©u hái nµy ta cã mÖnh ®Ò sau: MÖnh ®Ò 2.7. Gi¶ sö S lµ mét to¸n tö ®a trÞ tõ Rn −→ Rn. §iÒu kiÖn cÇn vµ ®ñ ®Ó tån t¹i mét hµm låi, ®ãng, chÝnh th­êng f trªn Rn sao cho S(x) ⊆ ∂f(x) ,∀x lµ to¸n tö S ®¬n ®iÖu tuÇn hoµn. Chøng minh. §iÒu kiÖn cÇn: NÕu tån t¹i mét hµm f låi, ®ãng, chÝnh th­êng trªn Rn sao cho S(x) ⊆ ∂f(x) ,∀x th× S lµ to¸n tö ®¬n ®iÖu tuÇn hoµn. ∀m ∈ N ,∀(xi, yi) ∈ G(S), xi ∈ domS(i = 0, ...m). Tõ (xi, yi) ∈ G(S) ⇒ yi ∈ S(xi) ⊆ ∂f(xi), (∀i = 0, ..m), do ∂f lµ ®¬n ®iÖu tuÇn hoµn trªn dom(∂f) nªn 〈y0, x1 − x0〉+ 〈y1, x2 − x1〉+ ...+ 〈ym, x0 − xm〉 6 0. Suy ra S lµ ®¬n ®iÖu tuÇn hoµn trªn domS. §iÒu kiÖn ®ñ: NÕu S lµ to¸n tö ®¬n ®iÖu tuÇn hoµn th× tån t¹i mét hµm f låi, ®ãng, chÝnh th­êng trªn Rn sao cho S(x) ⊆ ∂f(x) ,∀x Gi¶ sö (x0, y0) ∈ G(S), ®Þnh nghÜa hµm f b»ng c¸ch lÊy f(x) := Sup{〈x− xm, ym〉+ ...+ 〈x1 − x0, y0〉}, 37 trong ®ã cËn trªn ®óng ®­îc lÊy trªn tÊt c¶ c¸c cÆp (xi, yi) ∈ G(S) vµ c¸c sè nguyªn d­¬ng m. Ta chøng minh: f låi, ®ãng, chÝnh th­êng vµ S(x) ⊆ ∂f(x) ,∀x. Do f lµ bao trªn cña mét hä c¸c hµm a-phin, nªn f lµ mét hµm låi ®ãng. Do tÝnh ®¬n ®iÖu tuÇn hoµn cña S, nªn f(x0) := Sup{〈xo−xm, ym〉+〈xm−xm−1, ym−1〉+ ...+〈x1−x0, y0〉} := 0, suy ra dom f 6= ∅. VËy f lµ chÝnh th­êng. Víi bÊt k× cÆp (x, x∗) ∈ G(S), ta cã x∗ ∈ S(x), ta sÏ chøng minh x∗ ∈ ∂f(x). Muèn thÕ ta sÏ chøng minh r»ng ∀α < f(x) vµ y ∈ Rn , ta cã α + 〈x∗, y − x〉 < f(y). ThËt vËy, do α < f(x), nªn theo tÝnh chÊt cña cËn trªn ®óng, sÏ tån t¹i c¸c cÆp (xi, yi) ∈ G(S) vµ sè nguyªn d­¬ng m (i=1,...m) tháa m·n α < 〈x− xm, ym〉+ 〈xm − xm−1, ym−1〉+ ...+ 〈x1 − x0, y0〉. Theo ®Þnh nghÜa cña f(y), ta ®­îc: f(y) > 〈y − xm, ym〉+ ...+ 〈x1 − x0, y0〉 = 〈y − xm+1, ym〉+ 〈xm+1 − xm, ym〉+ ...+ 〈x1 − x0, y0〉. Thay xm+1 = x , ym = x∗, ta cã f(y) > 〈y − x, x∗〉+ 〈x− xm, ym〉+ 〈xm − xm−1, ym−1〉 + ...+ 〈x1 − x0, y0〉 > 〈y − x, x∗〉+ α. §iÒu nµy ®óng víi mäi (x, x∗) ∈ G(S) nªn S(x) ⊂ ∂f(x) ,∀x. §Þnh nghÜa 2.5. Ta nãi mét to¸n tö T : Rn −→ 2Rn lµ ®¬n ®iÖu cùc ®¹i nÕu nã lµ ®¬n ®iÖu vµ ®å thÞ cña nã kh«ng ph¶i lµ tËp con thùc sù cña ®å thÞ cña mét to¸n tö ®¬n ®iÖu nµo kh¸c. To¸n tö T ®­îc gäi lµ ®¬n ®iÖu tuÇn hoµn cùc ®¹i, nÕu nã lµ ®¬n ®iÖu tuÇn hoµn vµ ®å thÞ cña nã kh«ng ph¶i lµ tËp con thùc sù cña ®å thÞ cña mét to¸n tö ®¬n ®iÖu tuÇn hoµn nµo kh¸c. 38 VÝ dô 2.4. (To¸n tö ®¬n ®iÖu) XÐt NC(x) := {ω | 〈ω, y − x〉 6 0 , ∀y ∈ C}. Ta chøng tá r»ng nãn ph¸p tuyÕn cã tÝnh chÊt ®¬n ®iÖu theo nghÜa 〈ω − ω′, x− x′〉 > 0 ∀x, x′ ∈ C , ∀ω ∈ NC(x) , ∀ω′ ∈ NC(x′). ThËt vËy: ∀x, x′ ∈ C ta cã: + ω ∈ NC(x)⇔ 〈ω, y − x〉 6 0 ∀y ∈ C. Víi y = x′, ta cã 〈ω, x′ − x〉 6 0. + ω′ ∈ NC(x′)⇔ 〈ω′, y − x′〉 6 0 ∀y ∈ C. Víi y = x, ta cã 〈ω′, x− x′〉 6 0. ⇒ 〈ω, x′ − x〉+ 〈ω′, x− x′〉 6 0. ⇒ 〈ω − ω′, x− x′〉 > 0. VÝ dô 2.5. (To¸n tö ®¬n ®iÖu) XÐt ¸nh x¹ f : R2 −→ R2 x 7−→ f(x) = Qx = (x2,−x1). Víi x = (x1, x2), Q = ( 0 1 −1 0 ) . Víi mäi x = (x1, x2), y = (y1, y2) ∈ R2 ta cã: + x− y = (x1 − y1, x2 − y2). + f(x)− f(y) = (x2 − y2,−x1 + y1). Suy ra 〈f(x)− f(y), x− y〉 = (x2 − y2)(x1 − y1) + (−x1 + y1)(x2 − y2) = 0 ∀x, y ∈ R2. VËy f lµ ¸nh x¹ ®¬n ®iÖu trªn R2. HÖ qu¶ 2.1. Mäi to¸n tö ®¬n ®iÖu tuÇn hoµn cùc ®¹i trong Rn ®Òu lµ d­íi vi ph©n cña mét hµm låi, ®ãng, chÝnh th­êng trªn Rn. 39 Chøng minh. Gi¶ sö S lµ to¸n tö ®¬n ®iÖu tuÇn hoµn cùc ®¹i trong Rn. Theo ®Þnh nghÜa ta cã : + S lµ to¸n tö ®¬n ®iÖu tuÇn hoµn . + G(S) kh«ng lµ tËp con thùc sù cña ®å thÞ cña mét to¸n tö ®¬n ®iÖu tuÇn hoµn nµo kh¸c. Do S lµ to¸n tö ®¬n ®iÖu tuÇn hoµn nªn theo mÖnh ®Ò 2.7, tån t¹i mét hµm låi, ®ãng, chÝnh th­êng f trªn Rn sao cho S(x) ⊆ ∂f(x) , ∀x. Ta cã :∀(x, y) ∈ G(S)⇒ y ∈ S(x) do S(x) ⊆ ∂f(x),∀x nªn y ∈ ∂f(x) ⇒ (x, y) ∈ G(∂f). VËy G(S) ⊂ G(∂f). Do G(S) kh«ng lµ tËp con thùc sù cña ®å thÞ cña mét to¸n tö ®¬n ®iÖu tuÇn hoµn nµo kh¸c vµ ∂f lµ to¸n tö ®¬n ®iÖu tuÇn hoµn nªn G(S) = G(∂f). Suy ra S ≡ ∂f . 2.2.4 TÝnh liªn tôc cña d­íi vi ph©n §Þnh nghÜa 2.6. Mét ¸nh x¹ T : Rn −→ 2Rn ®­îc gäi lµ ®ãng t¹i x, nÕu víi mäi d·y xk → x, mäi yk ∈ T (xk) vµ yk → y th× y ∈ T (x) §Þnh nghÜa 2.7. Mét ¸nh x¹ T : Rn −→ 2Rn ®­îc gäi lµ nöa liªn tôc trªn t¹i x, nÕu víi mäi tËp më G chøa T(x), tån t¹i mét l©n cËn më U cña x sao cho T (z) ⊂ G,∀z ∈ U. Ta nãi ¸nh x¹ T lµ ®ãng (nöa liªn tôc trªn) trªn tËp C, nÕu nã ®ãng (nöa liªn tôc trªn) t¹i mäi ®iÓm thuéc C. Mét ¸nh x¹ T ®­îc gäi lµ ®ãng nÕu ®å thÞ cña T lµ mét tËp ®ãng. Nãi mét c¸ch kh¸i qu¸t, bæ ®Ò d­íi ®©y chØ ra r»ng: Mét d·y hµm låi nÕu bÞ chÆn trªn bëi mét hµm låi theo tõng ®iÓm ë trªn mét tËp låi, më, th× sÏ bÞ chÆn trªn ®Òu bëi chÝnh hµm låi ®ã trªn mäi tËp comp¾c thuéc tËp më nµy. Bæ ®Ò 2.1. Cho mét tËp låi, më G ⊆ Rn vµ f lµ mét hµm låi nhËn gi¸ trÞ h÷u h¹n trªn G. Gi¶ sö {fi}i ∈ I lµ mét d·y c¸c hµm låi h÷u h¹n trªn G vµ héi tô theo tõng ®iÓm trªn G ®Õn f . Gi¶ sö lim sup fi(x) 6 f(x) ,∀x ∈ G. 40 Khi ®ã víi mäi tËp comp¾c K ⊆ G, víi mäi  > 0, tån t¹i chØ sè i sao cho fi(x) 6 f(x) +  , ∀i > i ,∀x ∈ K. Chøng minh. Víi mäi x ∈ G, mäi i ∈ N , ®Þnh nghÜa gi(x) := max{fi(x), f(x)}. Hµm gi låi, h÷u h¹n trªn G v× nã lµ hµm bao trªn cña hai hµm låi, h÷u h¹n trªn G. Do G më, nªn gi liªn tôc trªn G. Do K ⊆ G comp¾c, nªn d·y {gi(x)}i ∈ I bÞ chÆn. Kh«ng gi¶m tæng qu¸t, b»ng c¸ch qua d·y con, ta cã thÓ coi gi(x)→ l(x) khi i→ +∞. Theo ®Þnh nghÜa cña gi(x) vµ do lim sup fi(x) 6 f(x) ∀x ∈ K, ta suy ra l(x) = f(x). VËy d·y gi(x) héi tô theo tõng ®iÓm ®Õn f trªn tËp comp¾c K, nªn nã héi tô ®Òu ®Õn f trªn K. Nh­ng do gi := max{fi(x), f(x)}, nªn víi mäi tËp comp¾c K ⊆ G, víi mäi  > 0,∃i : ∀i > i ta cã fi(x) 6 f(x) +  , ∀x ∈ K. Tõ mÖnh ®Ò sau, suy ra tÝnh nöa liªn tôc trªn cña ¸nh x¹ ∂f . Cô thÓ lµ: MÖnh ®Ò 2.8. Cho mét tËp låi, më U ⊆ Rn vµ f lµ mét hµm låi nhËn gi¸ trÞ h÷u h¹n trªn U . Gi¶ sö {fi}i ∈ I lµ mét d·y c¸c hµm låi h÷u h¹n trªn U vµ héi tô theo tõng ®iÓm trªn U ®Õn f . Khi ®ã, nÕu d·y {xi} ⊂ U héi tô ®Õn x ∈ U , th× víi mäi  > 0, tån t¹i chØ sè i sao cho ∂fi(x i) ⊂ ∂f(x) + .B(0, 1) ,∀i > i, trong ®ã B(0, 1) lµ h×nh cÇu ®¬n vÞ ®ãng t©m ë O 41 Chøng minh. Cho α > 0 , y ∈ Rn. Víi mçi x ∈ U ®Æt µ := f ′(x, y) + α. Do f låi, h÷u h¹n trªn tËp U më vµ x ∈ U , nªn x ∈ int(dom f), do ®ã µ h÷u h¹n. Do x ∈ int(dom f), nªn víi mäi y, tån t¹i δ > 0 sao cho x+ λ.y ∈ int(dom f) víi mäi 0 < λ < δ. Do α > 0 vµ ®Þnh nghÜa cña f ′(x, y), ta cã : f(x+ λ.y)− f(x) λ < µ ,∀λ ∈ (0, δ). (2.12) Do fi(x+ λ.y)→ f(x+ λ.y) vµ fi(xi)→ f(x), nªn tõ (2.12), tån t¹i i1 sao cho fi(x i + λ.y)− fi(xi) λ i1 ,∀λ ∈ (0, δ). Do f ′i(x i, y) 6 fi(x i + λ.y)− fi(xi) λ nªn f ′i(x i, y) 6 µ víi mäi i > i1. VËy lim sup f ′i(x i, y) 6 µ = f ′(x, y) + α. Do ®iÒu nµy ®óng víi mäi α > 0, ta suy ra lim sup f ′i(x i, y) < f ′(x, y). V× f ′i(x i, .) vµ f ′(x, .) låi, h÷u h¹n trªn U ( do x ∈ U ⊂ int(dom f)) nªn ¸p dông bæ ®Ò 2.1 cho c¸c hµm låi f ′i(x i, .) vµ f ′(x, .) víi G = Rn, K = B(0, 1) ta cã : Víi mäi tËp comp¾c B(0, 1) ⊆ Rn ,∀ > 0 ,∃i sao cho ∀i > i ta cã f ′i(x i, y) 6 f ′(x, y) +  , ∀y ∈ B(0, 1). Tõ ®©y, víi mäi y 6= 0, theo tÝnh chÊt thuÇn nhÊt d­¬ng cña f ′(x, .), ta cã: 1 ‖y‖f ′ i(x i, y) = f ′i(x i, y ‖y‖) 6 f ′(x, y ‖y‖) + . 42 Hay f ′i(x i, y) 6 f ′(x, y) + .‖y‖ ,∀i > i ,∀y. Do f ′i(x i, y) lµ hµm tùa cña ∂fi(x i) vµ f ′(x, y) lµ hµm tùa cña ∂f(x) nªn tõ ®©y suy ra ∂fi(x i) ⊆ ∂f(x) + .B(0, 1). MÖnh ®Ò 2.9. Cho f lµ mét hµm låi chÝnh th­êng trªn Rn. Khi ®ã ¸nh x¹ d­íi vi ph©n x −→ ∂f(x) nöa liªn tôc trªn t¹i mäi ®iÓm x ∈ int(dom f) Chøng minh. Ta cã f låi nªn nã h÷u h¹n trªn tËp int(dom f). VËy ¸p dông mÖnh ®Ò 2.8 víi U = int(dom f) vµ fi = f, ∀i, ta cã: NÕu x ∈ int(dom f) vµ {xi} ⊂ int(dom f) héi tô ®Õn x th× víi mäi  > 0, tån t¹i i sao cho ∀i > i ta cã ∂f(xi) ⊂ ∂f(x) + .B(0, 1). Suy ra ∂f nöa liªn tôc trªn t¹i mäi ®iÓm x ∈ int(dom f). MÖnh ®Ò 2.10. Cho f lµ mét hµm låi chÝnh th­êng trªn Rn. NÕu f kh¶ vi trªn tËp int(dom f) th× nã kh¶ vi liªn tôc trªn tËp nµy. Chøng minh. Cho x ∈ int(dom f) vµ d·y{xi} ⊂ int(dom f). Ta ¸p dông mÖnh ®Ò 2.8 víi U = int(dom f) vµ Ofi = Of , ∀i, ta cã: ∀ > 0 tån t¹i i sao cho ∀i > i, ‖Of(xi)− Of(x)‖ 6 . Chøng tá Of(.) liªn tôc t¹i x. 2.2.5 PhÐp tÝnh víi d­íi ®¹o hµm T­¬ng tù gi¶i tÝch cæ ®iÓn, nÕu f lµ mét hµm låi chÝnh th­êng trong Rn th× ∂(λf)(x) = λ.∂f(x) ,∀λ > 0 ,∀x. 43 ThËt vËy x∗ ∈ ∂(λf)(x)⇔ 〈x∗, z − x〉+ (λf)(x) 6 (λf)(z) ,∀z ⇔ 〈x∗, z − x〉+ λf(x) 6 λf(z) ,∀z ⇔ 〈x ∗ λ , z − x〉+ f(x) 6 f(z) ,∀z ⇔ x ∗ λ ∈ ∂f(x) ⇔ x∗ ∈ λ∂f(x). §èi víi d­íi vi ph©n cña tæng c¸c hµm låi, ta cã ®Þnh lý sau: MÖnh ®Ò 2.11. (§Þnh lý Moreau-Rockafellar). Cho fi, i=1,...,m lµ c¸c hµm låi chÝnh th­êng trªn Rn. Khi ®ã m∑ i=1 ∂fi(x) ⊆ ∂( m∑ i=1 fi(x)) ,∀x. NÕu ∩ ri(dom fi) 6= ∅ th× m∑ i=1 ∂fi(x) = ∂( m∑ i=1 fi(x)) ,∀x Chøng minh. Ta chøng minh m∑ i=1 ∂fi(x) ⊆ ∂( m∑ i=1 fi(x)),∀x. NÕu x∗ ∈∑mi=1 ∂fi(x) th× x∗ = ∑mi=1 x∗i , x∗i ∈ ∂fi(x), i = 1, ..,m. Ta cã x∗i ∈ ∂fi(x), i = 1, ...,m⇔ 〈x∗i , z − x〉+ fi(x) 6 fi(z) ,∀z , i = 1, ...,m ⇒ 〈 m∑ i=1 x∗i , z − x〉+ m∑ i=1 fi(x) 6 m∑ i=1 fi(z),∀z ⇔ 〈x∗, z − x〉+ m∑ i=1 fi(x) 6 m∑ i=1 fi(z),∀z ⇔ x∗ ∈ ∂( m∑ i=1 fi(x)) ,∀x. VËy ∑m i=1 ∂fi(x) ⊆ ∂( ∑m i=1 fi(x)),∀x. 44 Ta chøng minh m∑ i=1 ∂fi(x) ⊇ ∂( m∑ i=1 fi(x)) ,∀x. ChØ cÇn chøng minh víi m = 2, víi m > 2 dïng quy n¹p. LÊy x0 ∈ Rn vµ x∗ ∈ ∂( 2∑ i=1 fi(x 0)) = ∂(f1(x 0) + f2(x 0)) = ∂(f1 + f2)(x 0). Theo ®Þnh nghÜa cña d­íi vi ph©n ta cã: 〈x∗, x− x0〉+ f1(x0) + f2(x0) 6 f1(x) + f2(x) ∀x ⇔f1(x) + f2(x)− f1(x0)− f2(x0)− 〈x∗, x− x0〉 > 0 ∀x ⇔ { f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉 < 0 x = y kh«ng cã nghiÖm. LÊy D = dom f1× dom f2 vµ A(x, y) = x− y. Theo gi¶ thiÕt f1 liªn tôc t¹i mét ®iÓm a ∈ dom f1 ∩ dom f2, nªn tån t¹i mét l©n cËn U cña gèc sao cho U = (a+ U)− a ⊂ dom f1 − dom f2 = A(D). VËy 0 ∈ intA(D), ¸p dông mÖnh ®Ò 1.4 víi f(x, y) = f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉 A(x, y) = x− y. Ta cã 〈t, x− y〉+ [f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉] > 0, ∀x ∈ dom f1 , y ∈ dom f2. §èi víi x 6∈ dom f1 vµ y 6∈ dom f2, th× bÊt ®¼ng thøc trªn lµ hiÓn nhiªn. VËy 〈t, x− y〉+ [f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉] > 0 ,∀x, y. 45 LÊy x = x0 ta cã 〈t, y − x0〉+ f2(x0) 6 f2(y) ,∀y. Chøng tá t ∈ ∂f2(x0). LÊy y = x0 ta cã 〈x∗ − t, x− x0〉+ f1(x0) 6 f1(x) ,∀x. Chøng tá x∗ − t ∈ ∂f1(x0). Do ®ã x∗ = (x∗ − t) + t ∈ ∂f1(x0) + ∂f2(x0). 2.3 D­íi vi ph©n xÊp xØ D­íi vi ph©n xÊp xØ, hay cßn ®­îc gäi lµ -d­íi vi ph©n, th­êng ®­îc sö dông trong thùc tÕ bëi hai lý do chÝnh sau ®©y. Mét lµ hµm låi cã thÓ kh«ng kh¶ d­íi vi ph©n t¹i nh÷ng ®iÓm thuéc biªn cña miÒn h÷u dông cña nã, trong khi ®ã, nh­ sÏ thÊy d­íi ®©y, trong miÒn nµy, d­íi vi ph©n xÊp xØ lu«n tån t¹i. Lý do thø hai quan träng h¬n lµ trong øng dông, th­êng ng­êi ta chØ cÇn, vµ nhiÒu khi chØ tÝnh ®­îc d­íi vi ph©n mét c¸ch xÊp xØ. §Þnh nghÜa 2.8. Cho  > 0. Mét vÐct¬ x∗ ®­îc gäi lµ -d­íi ®¹o hµm cña f t¹i x, nÕu 〈x∗, y − x〉+ f(x) 6 f(y) +  , ∀y. KÝ hiÖu tËp hîp tÊt c¶ -d­íi ®¹o hµm cña f t¹i x lµ ∂f(x). TËp hîp nµy ®­îc gäi lµ -d­íi vi ph©n. HiÓn nhiªn ∂0f(x) = ∂f(x). VËy d­íi ®¹o hµm xÊp xØ lµ mét kh¸i niÖm tæng qu¸t ho¸ cña d­íi ®¹o hµm chÝnh x¸c. NhËn xÐt: Theo ®Þnh nghÜa x∗ ∈ ∂f(x)⇔ 〈x∗, z − x〉+ f(x) 6 f(z) +  , ∀z. 46 Thay z = y + x , ta ®­îc 〈x∗, y〉+ f(x) 6 f(x+ y) +  , ∀y. Tõ ®©y, nÕu ®Æt h(y) = f(x+ y)− f(x) , ta cã 〈x∗, y〉 − h(y) 6  , ∀y. Theo ®Þnh nghÜa hµm liªn hîp, ta cã ∂f(x) = {x∗|h∗(x∗) 6 }. Do h∗ lµ mét hµm låi, ®ãng nªn tõ ®©y thÊy r»ng ∂f(x) lu«n lµ mét tËp låi, ®ãng . HiÓn nhiªn ∂f(x) ⊆ ∂′f(x) nÕu  6 ′. H¬n n÷a ∩>0∂f(x) nÕu kh¸c rçng th× sÏ b»ng ∂f(x). VÝ dô 2.6. Cho hµm mét biÕn f(x) = { −2x 12 nÕu x > 0, +∞ nÕu x < 0. Ta cã ∂f(0) 6= ∅ víi  > 0. ThËt vËy, lÊy x∗ ∈ ∂f(0), ta cã: x∗ ∈ ∂f(0)⇔ 〈x∗, y − 0〉+ f(0) 6 f(y) +  , ∀y ⇔ x∗y 6 −2√y +  , ∀y > 0. NÕu y = 0 th× 0 6 . VËy bÊt ®¼ng thøc trªn ®­îc tho¶ m·n víi mäi x∗. NÕu y > 0 th× x∗ 6 −2 √ y y . VËy ∂f(0) 6= ∅ víi  > 0. MÆt kh¸c ∂f(0) = ∅ ( ®· chøng minh phÇn tr­íc ). VÝ dô trªn cho thÊy r»ng ∂f(x) 6= ∅ víi mäi  > 0, tuy nhiªn ∂f(x) = ∅. MÖnh ®Ò sau ®©y nãi r»ng mäi hµm låi ®ãng ®Òu kh¶ -d­íi vi ph©n víi mäi  > 0 t¹i mäi ®iÓm thuéc miÒn h÷u dông cña nã . MÖnh ®Ò 2.12. Cho f lµ mét hµm låi ®ãng chÝnh th­êng trªn Rn. Khi ®ã víi mäi  > 0 vµ mäi x0 ∈ dom f , tËp ∂f(x0) 6= ∅. H¬n n÷a víi mäi tËp bÞ chÆn C ⊂ int(dom f) tËp ∂f(C) bÞ chÆn. 47 Chøng minh. Do f låi, ®ãng, chÝnh th­êng nªn epi f låi, ®ãng, kh¸c rçng. Do epi f ®ãng nªn ®iÓm (x0, f(x0) − ) 6∈ epi f víi mäi  > 0. Ta ¸p dông ®Þnh lý t¸ch chÆt cho hai tËp C := epi f vµ D := {(x0, f(x0)− )}, sÏ tån t¹i (p, t) 6= 0, p ∈ Rn, t ∈ R vµ sè thùc η ( phô thuéc ) sao cho: 〈p, t〉 − tν < η < 〈p, x0〉 − t[f(x0)− ] ,∀(x, ν) ∈ epi f. (2.13) Tõ ®©y ta cã t 6= 0, v× nÕu t=0 th× 〈p, x〉 < η < 〈p, x0〉 ,∀x ∈ dom f vµ do ®ã ta cã m©u thuÉn nÕu lÊy x = x0. H¬n n÷a t > 0, v× nÕu t < 0 ta sÏ cã m©u thuÉn tõ (2.13) khi cho ν ®ñ lín . Thay ν = f(x) vµ chia hai vÕ cña (2.13) cho t > 0, ta cã 〈p t , x〉 − f(x) < η t < 〈p t , x0〉 − f(x0) + . Suy ra 〈p t , x− x0〉+ f(x0) < f(x) + . VËy p t ∈ ∂f(x0) hay ∂f(x0) 6= ∅. Gi¶ sö C ⊂ int(dom f), C bÞ chÆn. §Æt ξ = Supx∗∈∂f(C) ‖x∗‖ = Supx∈C Supx∗∈∂f(C) ‖x∗‖. (2.14) XÐt ¸nh x¹ tuyÕn tÝnh 〈x∗, z〉. ChuÈn cña ¸nh x¹ tuyÕn tÝnh nµy lµ ‖x∗‖ = Sup‖z‖=1〈x∗, z〉. Thay vµo (2.14) ta cã ξ = Supx∈C Supx∗∈∂f(x) Sup‖z‖=1〈x∗, z〉. MÆt kh¸c x∗ ∈ ∂f(x)⇔ f ′(x, y) + β > 〈x∗, y〉 ,∀β > 0 ,∀y. 48 Do ®ã f ′(x, y) + β = Supx∗∈∂f(x)〈x∗, y〉 ,∀β > 0 ,∀y. Hay f ′(x, z) + β = Supx∗∈∂f(x)〈x∗, z〉 ,∀β > 0 ,∀z. Ta cã tiÕp ξ = Sup‖z‖=1 Supx∈C(f ′(x, z) + β) = Sup‖z‖=1 Supx∈C f ′(x, z) + β. §Æt g(z) := Supx∈C f ′(x, z). Do x ∈ C ⊆ int(dom f), nªn hµm f ′(x, z) låi trªn Rn (do ®ã liªn tôc). Suy ra hµm g liªn tôc v× lµ bao trªn cña mét hä hµm låi liªn tôc trªn Rn. VËy ξ = Sup‖z‖=1 g(z) + β = max‖z‖=1 g(z) + β < +∞. Chøng tá ∂f(C) bÞ chÆn. MÖnh ®Ò 2.13. Cho f : Rn −→ R lµ hµm låi ®ãng. Khi ®ã mét vÐc-t¬ x∗ lµ - d­íi vi ph©n cña f t¹i x ∈ dom f khi vµ chØ khi f ∗(x∗) + f(x)− 〈x∗, x〉 6 . Chøng minh. Dïng ®Þnh nghÜa -d­íi ®¹o hµm ta cã: x∗ ∈ ∂f(x)⇔ 〈x∗, y − x〉+ f(x) 6 f(y) +  , ∀y ∈ dom f ⇔ [〈x∗, y〉 − f(y)] + f(x)− 〈x∗, x〉 6  , ∀y ∈ dom f. Theo ®Þnh nghÜa cña f ∗(x∗) ta cã: f ∗(x∗) = Supy{〈x∗, y〉 − f(y)}. VËy f ∗(x∗) + f(x)− 〈x∗, x〉 6 . 49 §Þnh nghÜa 2.9. Cho C ⊆ Rn lµ mét tËp låi, ®ãng vµ x ∈ C. TËp -nãn ph¸p tuyÕn ngoµi cña C t¹i x lµ -d­íi vi ph©n cña hµm chØ cña C t¹i x. Tøc lµ: NC,(x) := ∂δC(x) = {x∗ ∈ Rn | 〈x∗, y − x〉 6  , ∀y ∈ C} §Þnh lý 2.1. Cho f lµ hµm låi, ®ãng, chÝnh th­êng trªn Rn. 0 ∈ ∂f(x)⇔ f(x) 6 f(y) +  , ∀y ∈ Rn. Chøng minh. Theo ®Þnh nghÜa d­íi vi ph©n xÊp xØ ta cã: 0 ∈ ∂f(x)⇔ 〈0, y − x〉+ f(x) 6 f(y) +  , ∀y ∈ Rn ⇔ f(x) 6 f(y) +  , ∀y ∈ Rn. MÖnh ®Ò 2.14. Cho fi, i=1,...,m lµ c¸c hµm låi chÝnh th­êng trªn R n . Gi¶ sö ∩ri(dom fi) 6= ∅. Khi ®ã ∂ ( m∑ i=1 fi(x) ) ⊆ m∑ i=1 ∂fi(x) ∀x. §Æc biÖt ∂ ( m∑ i=1 fi(x) ) = m∑ i=1 ∂fi(x), ∀x⇔  = 0. Chøng minh. Ta chøng minh cho m = 2. Víi m > 2 dïng quy n¹p. Ta lÊy x0 ∈ Rn vµ x∗ ∈ ∂( 2∑ i=1 fi(x 0)) = ∂(f1(x 0) + f2(x 0)) = ∂(f1 + f2)(x 0). 50 Theo ®Þnh nghÜa cña d­íi vi ph©n xÊp xØ, ta cã: x∗ ∈ ∂(f1 + f2)(x0) ⇔〈x∗, x− x0〉+ (f1 + f2)(x0) 6 (f1 + f2)(x) +  ∀x ⇔〈x∗, x− x0〉+ f1(x0) + f2(x0) 6 f1(x) + f2(x) +  ∀x ⇔f1(x) + f2(x)− f1(x0)− f2(x0)− 〈x∗, x− x0〉+  > 0 ∀x ⇒hÖ { f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉+  < 0 x = y kh«ng cã nghiÖm. (2.15) LÊy D = dom f1 × dom f2, A(x, y) = x− y, f(x, y) = f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉+ . Theo gi¶ thiÕt f1 liªn tôc t¹i mét ®iÓm a ∈ dom f1 ∩ dom f2, nªn tån t¹i mét l©n cËn U cña gèc sao cho U = (a+ U)− a ⊂ dom f1 − dom f2 = A(D). VËy 0 ∈ intA(D). Lóc nµy (2.15) cã d¹ng: hÖ  f(x, y) < 0 A(x, y) = 0 (x, y) ∈ D kh«ng cã mghiÖm Ap dông mÖnh ®Ò 1.4 ta cã: 〈t, A(x, y)− 0〉+ f(x, y) > 0 ∀(x, y) ∈ D. ⇔ 〈t, x− y〉+ f1(x) + f2(y)− f1(x0)− f2(x0) + 〈x∗, x− x0〉+  > 0, ∀x ∈ dom f1 ,∀y ∈ dom f2. 51 §èi víi x 6∈ dom f1 vµ y 6∈ dom f2 th× bÊt ®¼ng thøc trªn lµ hiÓn nhiªn. VËy 〈t, x− y〉+ f1(x) + f2(y)− f1(x0)− f2(x0) + 〈x∗, x−x0〉+  > 0 ∀x, y. LÊy x = x0 ta cã : 〈t, x0 − y〉+ f2(y)− f2(x0) +  > 0 ∀y ⇔ 〈t, y − x0〉+ f2(x0) 6 f2(y) +  ∀y ⇔ t ∈ ∂f2(x0). LÊy y = x0 ta cã: 〈t, x− x0〉+ f1(x)− f1(x0)− 〈x∗, x− x0〉+  > 0 ∀x ⇔ 〈x∗ − t, x− x0〉+ f1(x0) 6 f1(x) +  ∀x ⇔ x∗ − t ∈ ∂f1(x0). Do ®ã x∗ = (x∗ − t) + t ⊆ ∂f1(x0) + ∂f2(x0). VËy ∂(f1(x 0) + f2(x 0)) ⊆ ∂f1(x0) + ∂f2(x0). Ch­¬ng 3 Mét sè øng dông cña d­íi vi ph©n trong tèi ­u ho¸ Ch­¬ng nµy tr­íc hÕt giíi thiÖu mét sè kh¸i niÖm chung vÒ cùc tiÓu, - cùc tiÓu cña mét hµm låi. TiÕp theo tr×nh bµy ®iÒu kiÖn cÇn vµ ®ñ cña nghiÖm tèi ­u cña bµi to¸n låi víi c¸c rµng buéc kh¸c nhau (Kh«ng rµng buéc, rµng buéc ®¼ng thøc, rµng buéc bÊt ®¼ng thøc). Cuèi ch­¬ng tr×nh bµy ®iÒu kiÖn cÇn vµ ®ñ cña nghiÖm tèi ­u xÊp xØ cña bµi to¸n låi víi c¸c rµng buéc kh¸c nhau. 3.1 C¸c kh¸i niÖm §Þnh nghÜa 3.1. Cho C ⊆ Rn kh¸c rçng vµ f : Rn −→ R ∪ {+∞}. a) §iÓm x∗ ∈ C ®­îc gäi lµ cùc tiÓu ®Þa ph­¬ng cña f trªn C nÕu tån t¹i mét l©n cËn U cña x∗ sao cho f(x∗) 6 f(x),∀x ∈ U ∩ C. b) §iÓm x∗ ∈ C ®­îc gäi lµ cùc tiÓu toµn côc (hay cùc tiÓu tuyÖt ®èi ) cña f trªn C nÕu f(x∗) 6 f(x),∀x ∈ C. c) §iÓm x ∈ C ®­îc gäi lµ ®iÓm chÊp nhËn ®­îc cña bµi to¸n. §Þnh nghÜa 3.2. Cho  > 0. Mét ®iÓm x ∈ C ®­îc gäi lµ ®iÓm -cùc tiÓu toµn côc cña f trªn C nÕu f(x) 6 f(x) + ,∀x ∈ C. 52 53 3.2 Bµi to¸n låi kh«ng cã rµng buéc XÐt bµi to¸n (P1) {minh(x) | x ∈ Rn}. Trong ®ã h lµ mét hµm låi chÝnh th­êng trªn Rn. MÖnh ®Ò 3.1. x∗ lµ nghiÖm cña bµi to¸n (P1)⇔ 0 ∈ ∂h(x∗). Chøng minh. Ta cã: x∗lµ nghiÖm cña bµi to¸n (P1)⇔ x∗lµ ®iÓm cùc tiÓu cña h trªn Rn ⇔ h(x∗) 6 h(x) ,∀x ∈ Rn ⇔ 〈0, x− x∗〉+ h(x∗) 6 h(x) ,∀x ∈ Rn ⇔ 0 ∈ ∂h(x∗). 3.3 Bµi to¸n låi víi rµng buéc ®¼ng thøc XÐt bµi to¸n (P2) {min f(x) | x ∈ C}. Trong ®ã C ⊆ Rn lµ mét tËp låi kh¸c rçng vµ f lµ mét hµm låi trªn C. MÖnh ®Ò 3.2. Gi¶ sö ri(dom f) ∩ riC 6= ∅. x∗ ∈ C lµ nghiÖm cña bµi to¸n (P2)⇔ 0 ∈ ∂f(x∗) +NC(x∗), trong ®ã NC(x ∗) := {ω | 〈ω, x− x∗〉 6 0 ,∀x ∈ C} lµ nãn ph¸p tuyÕn ngoµi cña C t¹i x∗. Chøng minh. Gäi δC(.) lµ hµm chØ cña tËp C , tøc lµ δC(x) := { 0 nÕu x ∈ C, +∞ nÕu x 6∈ C. 54 Khi ®ã x∗ lµ nghiÖm cña bµi to¸n (P2) ⇔x∗ lµ ®iÓm cùc tiÓu cña f trªn C ⇔x∗ lµ ®iÓm cùc tiÓu cña h(x) := f(x) + δC(x) trªnRn ⇔0 ∈ ∂h(x∗) (theo mÖnh ®Ò 3.1). Do ri(dom f) ∩ riC 6= ∅, theo ®Þnh lý Moreau-Rockafellar ta cã: ∂h(x∗) = ∂[f(x∗) + δC(x∗)] = ∂f(x∗) + ∂δC(x∗). V× x∗ ∈ C nªn ∂δC(x∗) = NC(x∗). VËy ∂h(x∗) = ∂f(x∗) +NC(x∗). Suy ra 0 ∈ ∂f(x∗) +NC(x∗). 3.4 Bµi to¸n låi víi rµng buéc bÊt ®¼ng thøc XÐt bµi to¸n t×m cùc tiÓu cña mét hµm låi trªn mét tËp låi cã d¹ng sau: (OP ) {min f(x) | gi(x) 6 0 (i = 1, ....m), x ∈ X}. Trong ®ã X ⊆ Rn lµ mét tËp låi ®ãng kh¸c rçng vµ f, gi (i=1,..m) lµ c¸c hµm låi h÷u h¹n trªn X . Ta sÏ lu«n gi¶ sñ r»ng X cã ®iÓm trong. Bµi to¸n (OP) nµy ®­îc gäi lµ mét quy ho¹ch låi. Hµm f ®­îc gäi lµ hµm môc tiªu. C¸c ®iÒu kiÖn x ∈ X, gi(x) 6 0 (i = 1, ...m) ®­îc gäi lµ c¸c rµng buéc. TËp D := {x ∈ X | gi(x) 6 0 i = 1, ...m} ®­îc gäi lµ miÒn chÊp nhËn ®­îc. Mét ®iÓm x ∈ D ®­îc gäi lµ ®iÓm chÊp nhËn ®­îc cña bµi to¸n (OP). Do X lµ tËp låi, c¸c hµm gi (i=1,..,m) låi trªn X nªn D lµ mét tËp låi. §iÓm cùc tiÓu cña f trªn D còng ®­îc gäi lµ nghiÖm tèi ­u cña bµi to¸n (OP). 55 Ta x©y dùng hµm sau, ®­îc gäi lµ hµm Lagrange, cho bµi to¸n (OP): L(x, λ) := λ0f(x) + m∑ i=1 λigi(x), víi λ = (λ0, ..., λm) Dùa vµo hµm Lagrange ta cã kÕt qña sau: §Þnh lý 3.1. (Karush- Kuhn- Tucker) Gi¶ sö ri(dom f) ∩ ri(dom gi) ∩ riX 6= ∅ a) NÕu x∗ lµ nghiÖm cña bµi to¸n (OP) th× tån t¹i λ∗i > 0 (i=0,...,m) kh«ng ®ång thêi b»ng 0 sao cho: 1) L(x∗, λ∗) = minx∈X L(x, λ∗) (®iÒu kiÖn ®¹o hµm triÖt tiªu ) (⇔ 0 ∈ λ∗0∂f(x∗) + m∑ i=1 λ∗i∂gi(x ∗) +NX(x∗) ). Trong ®ã NX(x ∗) lµ nãn ph¸p tuyÕn ngoµi cña X t¹i x∗ . 2) λ∗i gi(x ∗) = 0 (i = 1, ...,m) (®iÒu kiÖn ®é lÖch bï). H¬n n÷a nÕu ®iÒu kiÖn Slater sau tho¶ m·n: ∃x0 ∈ X : gi(x0) 0. b) NÕu hai ®iÒu kiÖn ®¹o hµm triÖt tiªu vµ ®é lÖch bï ë trªn ®­îc tho¶ m·n víi λ∗0 > 0 th× ®iÓm chÊp nhËn ®­îc x ∗ lµ nghiÖm tèi ­u cña bµi to¸n (OP) Chøng minh. a) Gi¶ sö x∗ lµ nghiÖm cña bµi to¸n (OP). §Æt C :={(λ0, λ1, ..., λm) ∈ Rm+1|∃x ∈ X : f(x)− f(x∗) < λ0, gi(x) 6 λi, i = 1, ...,m}. Do X 6= ∅ låi, f, gi låi trªn X , nªn C lµ mét tËp låi . 56 Ta cã C 6= ∅. ThËt vËy: + LÊy (λ0, ..., λm) ∈ intRm+1+ . Khi ®ã λi > 0 (i = 1, ...,m). + Víi x = x∗, ta cã f(x∗)− f(x∗) = 0 < λ0 gi(x ∗) 6 0 < λi (i = 1, ...,m). ⇒ (λ0, ..., λm) ∈ C. ⇒ intRm+1+ ⊂ C. ⇒ C 6= ∅ trong Rm+1. H¬n n÷a 0 6∈ C. ThËt vËy, nÕu 0 ∈ C th× ∃x ∈ X : f(x)− f(x∗) < 0 gi(x) 6 0 (i = 1, ...,m). Do ®ã x∗ kh«ng lµ nghiÖm cña bµi to¸n (OP)⇒ m©u thuÉn. VËy 0 6∈ C. Theo ®Þnh lý t¸ch thø 1, cã thÓ t¸ch c¸c tËp C vµ {0}, tøc lµ ∃λ∗i (i=0,...m) kh«ng ®ång thêi b»ng 0 sao cho m∑ i=0 λ∗iλi > 0 ∀(λ0, ..., λm) ∈ C. (3.1) Do intRm+1+ ⊂ C, ta suy ra λ∗i > 0. Víi  > 0 vµ x ∈ X , lÊy λ0 = f(x)− f(x∗) +  λi = gi(x) (i = 1, ...,m). Thay vµo (3.1) ta cã λ∗0[f(x)− f(x∗) + ] + m∑ i=1 λ∗i gi(x) > 0 ∀x ∈ X. Cho → 0 ta ®­îc λ∗0f(x) + m∑ i=1 λ∗i gi(x) > λ∗0f(x∗) ∀x ∈ X. (3.2) 57 Do x∗ lµ ®iÓm chÊp nhËn ®­îc nªn ta cã gi(x∗) 6 0 (i = 1, ...,m). VËy λ∗0f(x ∗) > λ∗0f(x∗) + m∑ i=1 λ∗i gi(x ∗). (3.3) Tõ (3.2) vµ (3.3) ta cã λ∗0f(x) + m∑ i=1 λ∗i gi(x) > λ∗0f(x∗) + m∑ i=1 λ∗i gi(x ∗) ∀x ∈ X ⇔L(x, λ∗) > L(x∗, λ∗) ∀x ∈ X ⇔L(x∗, λ∗) = minx∈X L(x, λ∗) (®iÒu kiÖn ®¹o hµm triÖt tiªu). Ta chó ý r»ng x∗ lµ nghiÖm cña bµi to¸n {minL(x, λ∗), x ∈ X} khi vµ chØ khi x∗ lµ ®iÓm cùc tiÓu cña hµm L(x, λ∗) trªn X ⇔x∗ lµ ®iÓm cùc tiÓu cña hµm L1(x, λ∗) := L(x, λ∗) + δX(x) trªnRn. ⇔0 ∈ ∂L1(x∗, λ∗) (theo mÖnh ®Ò 3.1). Do ri(dom f) ∩ ri(dom gi) ∩ riX 6= ∅ vµ f, gi (i:=1,...,m) lµ c¸c hµm låi, h÷u h¹n trªn X nªn theo ®Þnh lý Moreau-Rockafellar ta cã ∂L1(x ∗, λ∗) = ∂[L(x∗, λ∗) + δX(x∗)] = ∂[λ∗0f(x ∗) + m∑ i=1 λ∗i gi(x ∗)] + ∂δX(x∗) = λ∗0∂f(x ∗) + m∑ i=1 λ∗i∂gi(x ∗) +NX(x∗) (v× ∂δX(x ∗) = NX(x∗) ). VËy 0 ∈ λ∗0∂f(x∗) + m∑ i=1 λ∗i∂gi(x ∗) +NX(x∗). Do x∗ lµ ®iÓm chÊp nhËn ®­îc nªn gi(x∗) 6 0 (i = 1, ...,m). NÕu ∃i ∈ {1, ...,m} : gi(x∗) = ξ < 0 th× ∀ > 0 , f(x∗)− f(x∗) = 0 <  gj(x ∗) 6 0 < (j = 1, ..., i− 1, i+ 1, ...,m). 58 ⇒ (, ..., , ξ, , ..., ) ∈ C (ξ ë vÞ trÝ thø i). ⇒ λ∗i ξ > 0 ( thay vµo (3.1) vµ cho → 0) ⇒ λ∗i 6 0. Theo chøng minh trªn ta cã λ∗i > 0. VËy λ∗i = 0. Nh­ vËy lµ, nÕu gi(x ∗) < 0 th× λ∗i = 0. Do ®ã λ∗i gi(x ∗) = 0 (i = 1, ..,m) (®iÒu kiÖn ®é lÖch bï ). Gi¶ sö ®iÒu kiÖn Slater ®­îc tho¶ m·n: ∃x0 ∈ X : gi(x0) < 0. Khi ®ã nÕu λ∗0 = 0 th× do ®iÒu kiÖn ®¹o hµm triÖt tiªu vµ ®é lÖch bï ta cã 0 = λ∗0f(x ∗) + m∑ i=1 λ∗i gi(x ∗) 6 λ∗0f(x) + m∑ i=1 λ∗i gi(x) ,∀x ∈ X. Do λ∗0 = 0 nªn ph¶i cã Ýt nhÊt mét λ ∗ i > 0. Thay x0 vµo bÊt ®¼ng thøc trªn, sÏ ®­îc 0 = λ∗0f(x ∗) + m∑ i=1 λ∗i gi(x ∗) 6 λ∗0f(x0) + m∑ i=1 λ∗i gi(x 0) < 0. Suy ra m©u thuÉn. VËy λ∗0 6= 0 tøc lµ λ∗0 > 0. b) Gi¶ sö x∗ lµ ®iÓm chÊp nhËn ®­îc tho¶ m·n hai ®iÒu kiÖn ®¹o hµm triÖt tiªu vµ ®é lÖch bï ë trªn víi λ∗0 > 0, λ ∗ i > 0 (i = 1, ...,m). Do λ∗0 > 0, nªn b»ng c¸ch chia cho λ ∗ 0, ta cã thÓ coi hµm Lagrange lµ L(x, λ) = f(x) + m∑ i=1 λigi(x). Tõ ®iÒu kiÖn ®¹o hµm triÖt tiªu vµ ®é lÖch bï, ta cã: f(x∗) + m∑ i=1 λ∗i gi(x ∗) 6 f(x) + m∑ i=1 λ∗i gi(x) ∀x ∈ X λ∗i gi(x ∗) = 0 (i = 1, ...,m). Suy ra f(x∗) 6 f(x) + m∑ i=1 λ∗i gi(x) ,∀x ∈ X. (3.4) 59 Víi mäi x lµ ®iÓm chÊp nhËn ®­îc, tøc lµ: x ∈ X : gi(x) < 0 , i = 1, ...,m, ta cã f(x) + m∑ i=1 λ∗i gi(x) 6 f(x). (3.5) Tõ (3.4) vµ (3.5) suy ra f(x∗) 6 f(x) ,∀x ∈ X .Chøng tá x∗ lµ nghiÖm tèi ­u cña bµi to¸n (OP). VÝ dô 3.1. Ap dông ®Þnh lý cho bµi to¸n sau: {min f(x) | gi(x) 6 0 (i = 1, 2) , x ∈ X}, (OP ) trong ®ã f(x) = x2, g1(x) = x 2 − x, g2(x) = −x,X = [−12 , 12 ]. Gi¶i: Ta cã miÒn chÊp nhËn ®­îc D = {x ∈ X | gi(x) 6 0 (i = 1, 2)} = [0, 1 2 ]. Gi¶ sö tån t¹i λ∗i > 0 (i = 0, ..., 2) kh«ng ®ång thêi b»ng 0 sao cho: 1) L(x∗, λ∗) = minx∈X L(x, λ∗) (⇔ 0 ∈ λ∗0∂f(x∗) + ∑2 i=1 λ ∗ i∂gi(x ∗) +NX(x∗) ). 2) λ∗i gi(x ∗) = 0, i = 1, 2. 3) λ∗0 > 0. Tõ ®Þnh lÝ 3.1, suy ra x∗ lµ nghiÖm tèi ­u cña bµi to¸n (OP) ⇔f(x∗) 6 f(x), ∀x ∈ D ⇔x∗2 6 x2, ∀x ∈ D ⇔x∗2 6 0 ⇔x∗ = 0. Ng­îc l¹i, nÕu x∗ = 0 lµ nghiÖm cña bµi to¸n (OP) th× tõ ®Þnh lÝ 3.1, suy ra tån t¹i λ∗i > 0 (i = 0, ..., 2) kh«ng ®ång thêi b»ng 0 sao cho : 60 1) L(x∗, λ∗) = minx∈X L(x, λ∗) (⇔ 0 ∈ λ∗0∂f(x∗) + ∑2 i=1 λ ∗ i∂gi(x ∗) +NX(x∗) ). 2) λ∗i gi(x ∗) = 0, i = 1, 2. Ta cã L(x∗, λ∗) = minx∈X L(x, λ∗) ⇔L(x, λ∗) > L(x∗, λ∗), ∀x ∈ X ⇔λ∗0f(x) + 2∑ i=1 λ∗i gi(x) > λ∗0f(x∗) + 2∑ i=1 λ∗i gi(x ∗), ∀x ∈ X ⇔λ∗0x2 + λ∗1(x2 − x)− λ∗2x > 0, ∀x ∈ X. Ta cã λ∗i gi(x ∗) = 0, i = 1, 2⇔ λ∗i .0 = 0, i = 1, 2⇔ λ∗i > 0, i = 1, 2. Do λ∗i > 0 (i = 0, ..., 2) kh«ng ®ång thêi b»ng 0 nªn: + Chän λ∗1 = λ ∗ 2 = 0. Ta cã λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔λ∗0x2 > 0, ∀x ∈ X ⇔λ∗0 > 0 ⇒Chänλ∗0 = 1. + Chän λ∗1 = λ ∗ 2 = 1. Ta cã λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔(λ∗0 + 1)x2 − 2x > 0, ∀x ∈ X ⇒Kh«ng tån t¹i λ∗0. + Chän λ∗1 = 0, λ ∗ 2 = 1. Ta cã λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔λ∗0x2 − x > 0, ∀x ∈ X ⇒Kh«ng tån t¹i λ∗0. 61 + Chän λ∗1 = 1, λ ∗ 2 = 0. Ta cã λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔(λ∗0 + 1)x2 − x > 0, ∀x ∈ X ⇒Kh«ng tån t¹i λ∗0. VËy x∗ = 0 lµ nghiÖm tèi ­u cña bµi to¸n (OP) vµ λ∗0 = 1, λ ∗ 1 = λ ∗ 2 = 0 lµ c¸c nh©n tö Lagrang t­¬ng øng. Chó ý 3.1. Trong nhiÒu tr­êng hîp bµi to¸n (P1), (P2) vµ (OP) cã thÓ kh«ng cã lêi gi¶i tèi ­u chÝnh x¸c. H¬n n÷a trong thùc tÕ th­êng ng­êi ta kh«ng tÝnh ®­îc lêi gi¶i tèi ­u (chÝnh x¸c), mµ chØ tÝnh ®­îc lêi gi¶i xÊp xØ. Khi ®ã ta dïng kh¸i niÖm lêi gi¶i tèi ­u xÊp xØ hay cßn gäi lµ - tèi ­u. MÖnh ®Ò 3.3. x lµ  -nghiÖm cña bµi to¸n (P1)⇔ 0 ∈ ∂h(x) Chøng minh. Ta cã: x lµ − nghiÖm cña bµi to¸n (P1) ⇔x lµ ®iÓm − cùc tiÓu cña h trªn Rn ⇔h(x) 6 h(x) +  , ∀x ∈ Rn (theo ®Þnh nghÜa3.2) ⇔0 ∈ ∂h(x) (theo ®Þnh lý2.1). MÖnh ®Ò 3.4. Gi¶ sö ri(dom f) ∩ riC 6= ∅. Khi ®ã x ∈ C lµ  -nghiÖm cña bµi to¸n (P2) =⇒ 0 ∈ ∂f(x) +NC,(x), trong ®ã NC,(x) := {ω | 〈ω, x − x〉 6  , ∀x ∈ C} lµ  -nãn ph¸p tuyÕn ngoµi cña C t¹i x. Chøng minh. Gäi δC(.) lµ hµm chØ cña tËp C , tøc lµ δC(x) := { 0 nÕu x ∈ C, +∞ nÕu x 6∈ C. 62 Khi ®ã x lµ − nghiÖm cña bµi to¸n (P2) ⇔x lµ ®iÓm − cùc tiÓu cña f trªn C ⇔x lµ ®iÓm − cùc tiÓu cña h(x) := f(x) + δC(x) trªn Rn ⇔0 ∈ ∂h(x) (theo mÖnh ®Ò 3.3). Do ri(dom f) ∩ riC 6= ∅, ta cã: ∂h(x) = ∂[f(x) + δC(x)] ⊆ ∂f(x) + ∂δC(x) (theo mÖnh ®Ò 2.14) = ∂f(x) +NC,(x) (V× x ∈ C nªn theo ®Þnh nghÜa 2.9 ∂δC(x) = NC,(x) ). VËy 0 ∈ ∂f(x) +NC,(x). 63 KÕt luËn Nh­ vËy, luËn v¨n nµy ®· tr×nh bµy mét c¸ch hÖ thèng c¸c kh¸i niÖm, tÝnh chÊt c¬ b¶n cña tËp låi vµ hµm låi. Sau ®ã l¹i ®Ò cËp vÒ ®¹o hµm theo ph­¬ng, d­íi vi ph©n, d­íi vi ph©n xÊp xØ vµ chøng minh mét c¸ch cô thÓ mét sè tÝnh chÊt cña chóng. Cuèi cïng luËn v¨n tr×nh bµy c¸c ®iÒu kiÖn cùc trÞ cho c¸c bµi to¸n quy ho¹ch låi víi c¸c r»ng buéc kh¸c nhau. Tµi liÖu tham kh¶o [1] Lª Dòng M­u vµ NguyÔn V¨n HiÒn (2003), NhËp m«n gi¶i tÝch låi øng dông, Gi¸o tr×nh. [2] . T¹ Quang S¬n (2008), Some Qualitative Problems In Optimization, LuËn ¸n tiÕn sÜ. [3] T. Rockafellar (1970), Convex Analysis, Princeton University Press, Princeton, New Jersey. [4] J. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms. 64