Tài liệu Về bài toán quy hoạch lồi

„I HÅC THI NGUY–N TR×ÍNG „I HÅC KHOA HÅC BÒI THÀ THU HUY—N V— B€I TON QUY HO„CH LÇI LUŠN V‹N TH„C Sž TON HÅC Th¡i Nguy¶n - N«m 2014 „I HÅC THI NGUY–N TR×ÍNG „I HÅC KHOA HÅC BÒI THÀ THU HUY—N V— B€I TON QUY HO„CH LÇI 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 Ng÷íi h÷îng d¨n khoa håc GS-TSKH L– DÔNG M×U Th¡i Nguy¶n - N«m 2014 i LÍI CƒM ÌN Líi ¦u ti¶n cõa khâa luªn n y, tæi xin b y tä láng bi¸t ìn s¥u s­c nh§t tîi th¦y gi¡o h÷îng d¨n GS.TSKH. L¶ Dông M÷u, ng÷íi th¦y ¢ tªn t¼nh h÷îng d¨n, gióp ï tæi trong suèt qu¡ tr¼nh l m v  ho n thi»n luªn v«n. Trong qu¡ tr¼nh håc tªp ch÷ìng tr¼nh cao håc t¤i tr÷íng ¤i håc khoa håc - ¤i håc Th¡i nguy¶n, tæi ¢ nhªn ÷ñc sü gióp ï v  sü gi£ng d¤y tªn t¼nh cõa GS.TSKH L¶ Dông M÷u, GS.TS. Tr¦n Vô Thi»u, PGS. Næng Quèc Chinh, PGS.TS. L¶ Thà Thanh Nh n, PGS.TS. T¤ Duy Ph÷ñng, TS. Nguy¹n Thà Thu Thõy, còng r§t nhi·u th¦y cæ cæng t¡c t¤i Vi»n To¡n håc Vi»t Nam, tr÷íng ¤i håc Th«ng Long, tr÷íng ¤i håc khoa håc - ¤i håc Th¡i Nguy¶n. Tæi xin b y tä láng bi¸t ìn s¥u s­c ¸n c¡c th¦y, c¡c cæ. Nhªn dàp n y, tæi công xin gûi líi c£m ìn tîi c¡c th¦y gi¡o, cæ gi¡o tr÷íng ¤i håc khoa håc - ¤i håc Th¡i Nguy¶n ¢ quan t¥m, t¤o i·u ki»n gióp ï tæi trong suèt qu¡ t¼nh håc tªp. çng thíi, tæi công xin gûi líi c£m ìn tîi Tr÷íng THCS H÷ng ¤o ¢ t¤o i·u ki»n, tîi gia ¼nh v  b¤n b± ¢ luæn ëng vi¶n, gióp ï tæi trong suèt qu¡ tr¼nh håc tªp v  l m luªn v«n tèt nghi»p. M°c dò ¢ câ nhi·u cè g­ng nh÷ng luªn v«n khâ tr¡nh khäi nhúng thi¸u sât v  h¤n ch¸. T¡c gi£ mong nhªn ÷ñc nhúng þ ki¸n âng ghâp cõa c¡c th¦y cæ v  b¤n åc º luªn v«n ÷ñc ho n thi»n hìn. Xin tr¥n trång c£m ìn! H£i Pháng, ng y 11 th¡ng 08 n«m 2014 T¡c gi£ Bòi Thà Thu Huy·n i Möc löc Mð ¦u 1 1 Mët sè kh¡i ni»m cì b£n 2 1.1 Mët sè kh¡i ni»m v  t½nh ch§t cì b£n . . . . . . . . . . . . 2 1.2 Ph¡t biºu b i to¡n v  v½ dö . . . . . . . . . . . . . . . . . 9 1.2.1 B i to¡n quy ho¤ch tuy¸n t½nh . . . . . . . . . . . . 10 1.2.2 B i to¡n quy ho¤ch to n ph÷ìng lçi . . . . . . . . . 10 1.3 Sü tçn t¤i v  t½nh ch§t cõa tªp nghi»m . . . . . . . . . . . 10 1.4 i·u ki»n tèi ÷u . . . . . . . . . . . . . . . . . . . . . . . . 13 2 MËT SÈ PH×ÌNG PHP GIƒI CÌ BƒN 2.1 Ph÷ìng ph¡p ¤o h m v  d÷îi ¤o h m 2.1.1 22 Thuªt to¡n h÷îng ¤o h m (dèc nh§t) gi£i quy ho¤ch lçi 2.2 . . . . . . . . . . 22 . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.2 Ph÷ìng ph¡p Newton . . . . . . . . . . . . . . . . . 25 2.1.3 Ph÷ìng ph¡p Frank  Wolfe . . . . . . . . . . . . . 27 2.1.4 Ph÷ìng ph¡p chi¸u d÷îi ¤o h m . . . . . . . . . . 29 Ph÷ìng ph¡p h m ph¤t . . . . . . . . . . . . . . . . . . . 31 2.2.1 Ph÷ìng ph¡p h m ph¤t iºm trong . . . . . . . . . 32 2.2.2 Ph÷ìng ph¡p h m ph¤t iºm ngo i . . . . . . . . . 35 K¸t luªn 37 T i li»u tham kh£o 38 1 MÐ †U Quy ho¤ch lçi l  mët b i to¡n cì b£n cõa lþ thuy¸t tèi ÷u. mët °c tr÷ng quan trång cõa lîp b i to¡n n y l  nghi»m tèi ÷u àa ph÷ìng ·u l  tèi ÷u to n cöc. Do â c¡c cæng cö mang t½nh ch§t àa ph÷ìng nh÷ giîi h¤n, ¤o h m... câ thº sû döng mët c¡ch r§t hi»u qu£ cho lîp b i to¡n n y. B i to¡n quy ho¤ch lçi xu§t hi»n trong nhi·u v§n · thüc t¸ thuëc c¡c l¾nh vüc kinh t¸, khoa håc, k¾ thuªt, mæi tr÷íng... B i to¡n n y xu§t hi»n nh÷ mët b i to¡n phö trong c¡c ph÷ìng ph¡p gi£i b i to¡n tèi ÷u khæng lçi nh÷ tèi ÷u to n cöc, tèi ÷u ríi r¤c. V¼ vªy vi»c nghi¶n cùu c¡c ph÷ìng ph¡p gi£i b i to¡n quy ho¤ch lçi l  mët · t i quan trång, luæn ÷ñc sü quan t¥m cõa nhi·u ng÷íi. Möc ½ch cõa b£n luªn v«n n y l  nh¬m giîi thi»u nhúng iºm cì b£n cõa b i to¡n tèi ÷u lçi trong khæng gian Euclid húu h¤n chi·u. Sau khi giîi thi»u nhúng i·u ki»n v· sü tçn t¤i nghi»m, i·u ki»n tèi ÷u nh÷ ành lþ Karush-kuhn-Tucker, ành lþ Kuhn-Tucker... luªn v«n i s¥u v o giîi thi»u mët sè ph÷ìng ph¡p gi£i b i to¡n quy ho¤ch lçi câ r ng buëc v  khæng r ng buëc, kh£ vi v  khæng kh£ vi. B£n luªn v«n gçm 2 ch÷ìng. Ch÷ìng 1: Nh¬m möc ½ch giîi thi»u c¡c ki¸n thùc cì b£n v· h m lçi, tªp lçi s³ ÷ñc sû döng trong ch÷ìng sau. Ngo i ra trong ch÷ìng n y cán ph¡t biºu b i to¡n v  v½ dö, n¶u sü tçn t¤i v  t½nh ch§t cõa tªp nghi»m, ch¿ ra i·u ki»n tèi ÷u. Ch÷ìng 2: Trong ch÷ìng n y chóng ta nghi¶n cùu mët sè ph÷ìng ph¡p gi£i b i to¡n quy ho¤ch lçi cì b£n â l  c¡c ph÷ìng ph¡p ¤o h m v  d÷îi ¤o h m, ph÷ìng ph¡p Newton v  ph÷ìng ph¡p h m ph¤t. 2 Ch÷ìng 1 Mët sè kh¡i ni»m cì b£n Ch÷ìng n y gçm ba möc. Möc 1.1 tr¼nh b y mët sè kh¡i ni»m v  t½nh ch§t cì b£n. Möc 1.2 ph¡t biºu b i to¡n v  v½ dö. Möc 1.3 nâi v· sü tçn t¤i v  t½nh ch§t cõa tªp nghi»m. Möc 1.4 l  i·u ki»n tèi ÷u. K¸t qu£ v  kh¡i ni»m d÷îi ¥y ÷ñc l§y tø c¡c t i li»u [1], [2], [3]. 1.1 Mët sè kh¡i ni»m v  t½nh ch§t cì b£n Trong b£n luªn v«n n y, chóng ta s³ l m vi»c vîi khæng gian Euclid Méi ph¦n tû x trong khæng gian Rn l  mët bë n Rn . sè thüc v  ÷ñc vi¸t d÷îi d¤ng cët sè   x  1  x   2  x :=  .  .  ..    xn xi , i ∈ {1, ..., n}, ÷ñc gåi l  tåa ë thù i cõa iºm x. º thuªn vi¸t, ta quy ÷îc vectì chuyºn và cõa x l  Méi sè ti»n khi xT = (x1 , x2 , ..., xn ) . x = (x1 , x2 , ..., xn )T cõa x v  y l : Cho hai v²c tì T½ch væ h÷îng v  y = (y1 , y2 , ..., yn )T . hx, yi := x1 y1 + x2 y2 + ... + xn yn . 3 Kþ hi»u chu©n kxk := p x21 + x22 ... + x2n . Tr÷îc h¸t ta nh­c l¤i mët sè kh¡i ni»m v  t½nh ch§t cì b£n cõa gi£i t½ch lçi nh÷: Tªp lçi, h m lçi, d÷îi vi ph¥n,. . . Cho hai iºm 0 ≤ λ ≤1 a, b ∈ Rn . x = (1 − λ) a + λb vîi a v  b, v  kþ hi»u [a, b] . Tªp t§t c£ c¡c iºm ÷ñc gåi l  o¤n th¯ng (âng) nèi Mët tªp C ⊆ Rn ÷ñc gåi l  mët tªp lçi n¸u nâ chùa trån o¤n th¯ng nèi hai iºm b§t ký thuëc nâ. Tùc l  (1 − λ) a + λb ∈ C vîi måi a, b ∈ C v  måi 0 ≤ λ ≤ 1. ành ngh¾a 1.1. C¡c v½ dö v· tªp lçi v  tªp khæng lçi: H¼nh 1.1: (a), (b), (e)-Tªp lçi; (c), (d)- Tªp khæng lçi ành ngh¾a 1.2. iºm Rn câ d¤ng 1 2 x = λ1 a + λ2 a + ... + λk a k = k X λi ai , i=1 vîi i n a ∈ R , λi ≥ 0, k X λi = 1, i=1 ÷ñc gåi l  mët tê hñp lçi cõa c¡c iºm a1, a2, ..., ak . Tªp C l  lçi khi v  ch¿ khi nâ chùa måi tê hñp lçi cõa c¡c ph¦n tû thuëc nâ. ành ngh¾a 1.3. . Mët tªp C ⊆ Rn ÷ñc gåi l  mët nân n¸u ∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C. Mët nân ÷ñc gåi l  nân lçi n¸u nâ l  nân v  l  mët tªp lçi. 4 Tªp C ⊆ Rn d÷îi ¥y luæn ÷ñc gi£ thi¸t l  mët tªp lçi (n¸u khæng gi£i th½ch g¼ th¶m). H¼nh 1.2: Nân lçi v  nân khæng lçi ành ngh¾a 1.4. Cho x ∈ C , nân ph¡p tuy¸n ngo i cõa C l  NC (x), ÷ñc x¡c ành bði cæng thùc t¤i x, k½ hi»u NC (x) : = {w ∈ Rn \ hw, y − xi ≤ 0, ∀y ∈ C} . Cho mët tªp lçi C ⊆ Rn v  mët iºm y h¼nh chi¸u cõa y tr¶n C l  iºm x0 ∈ C sao cho ành ngh¾a 1.5. ∈ Rn . Ta gåi 0 x − y = min kx − yk = dC (y) . Kþ hi»u x0 N¸u C x∈C = p (y) v  gåi dC (y) l  kho£ng c¡ch tø y tîi C . l  mët tªp lçi âng th¼ h¼nh chi¸u p (y) luæn luæn tçn t¤i v  duy nh§t. ành ngh¾a 1.6. Ta nâi hai tªp lçi kh¡c réng C bði si¶u ph¯ng H n¸u = {x ∈ Rn : ht, xi = v  D trong Rn t¡ch ÷ñc α} vîi t ∈ Rn \ {0} v  α ∈ R, infx∈C ht, xi ≥ α ≥ sup ht, yi . (1) y∈D ành lþ 1.7. (ành lþ t¡ch I). Hai tªp C v  D trong Rn kh¡c réng, khæng câ iºm chung câ thº t¡ch ÷ñc bði mët si¶u ph¯ng, ngh¾a l  tçn t¤i v²c tì t ∈ Rn (t 6= 0 ) v  mët sè α ∈ R sao cho (1) thäa m¢n. ành ngh¾a 1.8. Ta nâi hai tªp lçi kh¡c réng C , D trong Rn l  t¡ch h¯n bði si¶u ph¯ng H = {x ∈ Rn : ht, xi = α} , n¸u infx∈C ht, xi > α > sup ht, yi . y∈D (2) 5 (ành lþ t¡ch II). Hai tªp lçi âng C v  D trong Rn kh¡c réng, khæng c­t nhau vîi ½t nh§t mët trong hai tªp n y l  compact.Khi â câ thº t¡ch h¯n bði mët si¶u ph¯ng, ngh¾a l  tçn t¤i mët v²c tì t ∈ Rn, t 6= 0 v  mët sè α ∈ R sao cho (2) thäa m¢n. ành lþ 1.9. H¼nh 1.3: (a) Hai tªp lçi C v  D ÷ñc t¡ch h¯n bði mët si¶u ph¯ng; (b) Hai tªp lçi C v  D ÷ñc t¡ch bði si¶u ph¯ng x ∈ R2 |x2 = 0 nh÷ng khæng t¡ch h¯n ÷ñc; (c) Hai tªp C v  D giao nhau b¬ng réng  nh÷ng khæng thº t¡ch ÷ñc v¼ D khæng ph£i tªp lçi ành ngh¾a 1.10. Mët tªp ÷ñc gåi l  tªp lçi a di»n, n¸u nâ l  giao cõa mët sè húu h¤n c¡c nûa khæng gian âng. Nh÷ vªy, theo ành ngh¾a, tªp lçi a di»n l  tªp hñp nghi»m cõa mët h» húu h¤n c¡c b§t ph÷ìng tr¼nh tuy¸n t½nh. D¤ng t÷íng minh cõa mët tªp lçi a di»n ÷ñc cho nh÷ sau: D :=   x ∈ Rn | aj , x ≤ bj , j = 1, ..., m . A l  ma trªn câ m h ng l  c¡c v²c tì aj (j = 1, ..., m) = (b1 , ..., bm ), th¼ h» tr¶n vi¸t ÷ñc l : Ho°c n¸u ta kþ hi»u v  v²c tì bT D := {x ∈ Rn | Ax ≤ b} . ha, xi = b câ thº vi¸t mët c¡ch t÷ìng tr¼nh ha, xi ≤ b, h−a, xi ≤ b, n¶n tªp Chó þ r¬ng do mët ph÷ìng tr¼nh ÷ìng d÷îi d¤ng hai b§t ph÷ìng nghi»m cõa mët h» húu h¤n c¡c ph÷ìng tr¼nh v  b§t ph÷ìng tr¼nh công l  mët tªp lçi a di»n. H m f : S → (−∞, +∞] x¡c ành tr¶n mët tªp hñp ⊆ Rn ÷ñc gåi l  mët h m lçi tr¶n S n¸u vîi måi x, y ∈ S v  måi ành ngh¾a 1.11. lçi S 6 sè thüc λ ∈ [0, 1] ta câ f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) . +) H m f ÷ñc gåi l  h m lçi ch°t tr¶n S n¸u vîi måi x, v  måi λ ∈ (0, 1) ta câ y ∈ S , x 6= y f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) . +) H m f ÷ñc gåi l  h m lãm (lãm ch°t) tr¶n S n¸u −f l  lçi (lçi ch°t) tr¶n S . H m f ÷ñc gåi l  tuy¸n t½nh afin (hay ìn gi£n l  afin) tr¶n S n¸u f vøa lçi vøa lãm tr¶n S . Mët h m afin tr¶n vîi måi x, y ∈ Rn Rn f (x) = ha, xi + α λ ∈ [0, 1] ta câ câ d¤ng v  måi vîi a ∈ Rn , nh÷ vªy f (λx + (1 − λ) y) = λf (x) + (1 − λ) f (y) . Tuy nhi¶n, h m afin khæng lçi ch°t hay lãm ch°t. H¼nh 1.4: (a)-H m lçi; (b)-H m lãm H m f (x) x¡c ành tr¶n mët tªp lçi C ⊂ Rn ÷ñc gåi l  lçi m¤nh, n¸u tçn t¤i h» sè ρ > 0 (h» sè lçi m¤nh) sao cho vîi måi ∀x, y ∈ C v  måi sè λ ∈ [0, 1] ta câ b§t ¯ng thùc: ành ngh¾a 1.12. f [λx + (1 − λ) y] ≤ λf (x) + (1 − λ) f (y) − λ (1 − λ) ρkx − yk2 . Câ thº chùng minh r¬ng h m ρkxk2 f (x) lçi m¤nh khi v  ch¿ khi h m f (x) − lçi. Rã r ng mët h m sè lçi m¤nh th¼ lçi ch°t, nh÷ng i·u ng÷ñc l¤i khæng ch­c óng. Ch¯ng h¤n, h m khæng lçi m¤nh. ex vîi måi x ∈ R, lçi ch°t nh÷ng 7 C¡c h m lçi m¤nh câ vai trá °c bi»t quan trång trong nghi¶n cùu c¡c b i to¡n tèi ÷u. ành ngh¾a 1.13. tªp Cho h m b§t ký f : S → (−∞, +∞] vîi S ⊆ Rn , c¡c dom f = {x ∈ S : f (x) < + ∞} v  epi f = {(x, α) ∈ S × R : f (x) ≤ α} , ÷ñc gåi l¦n l÷ñt l  mi·n húu döng v  tªp tr¶n ç thà cõa h m f . N¸u dom f kh¡c réng (khæng çng nh§t b¬ng +∞) v  f (x) > −∞ vîi måi x ∈ S th¼ ta nâi h m f l  ch½nh th÷íng. Tø ành ngh¾a, ta th§y h m f lçi tr¶n S khi v  ch¿ khi a) Tªp tr¶n ç thà epif l  mët tªp lçi. i·u n y t÷ìng ÷ìng vîi: b) f m X ! λk x k ≤ m X k=1 vîi måi xk ∈ S, m P λk = 1
λk f xk , k=1 v  λk ≥ 0 vîi måi k, trong â m≥1 l  mët k=1 sè nguy¶n tè (b§t ¯ng thùc Jensen). f : S → (−∞, +∞] câ n to n khæng gian R b¬ng H m lçi ành tr¶n thº ÷ñc mð rëng th nh h m lçi x¡c c¡ch °t V¼ vªy º ìn gi£n ta th÷íng x²t h m lçi f (x) = +∞ vîi n tr¶n to n R . måi x 6= S . V½ dö 1.14. . Sau ¥y l  mët sè v½ dö quen thuëc v· h m lçi. Cho C ⊂ Rn l  mët tªp lçi kh¡c réng, c¡c h m sau l  lçi: p H m chu©n Euclid kxk = (hx, xi, x ∈ Rn. H m ch¿ cõa C : δC (x) = 0 khi x ∈ C, +∞ khi x ∈ / C. tüa cõa C : sC (x) = supy∈C hy, xi(cªn tr¶n cõa tr¶n tªp ). kho£ng c¡ch tø iºm x ∈ Rn tîi C : dC (x) = miny∈C kx − yk . H m H m Bèn ph²p to¡n cì b£n b£o to n t½nh lçi (suy trüc ti¸p tø ành ngh¾a). a) N¸u fi : Rn → R (i = 1, ..., m) l  h m lçi th¼ α1f1 + ... + αmfm lçi 8 vîi måi αi ≥ 0 v  lçi ch°t n¸u ½t nh§t mët trong c¡c h m fi lçi ch°t vîi α i > 0. b) N¸u fi (i ∈ I) : Rn → R l  h m lçi th¼ f (x) = supi∈I fi (x) l  h m lçi. c) N¸u A : Rn → Rm l  bi¸n êi tuy¸n t½nh v  g : Rm → R l  h m lçi th¼ h m hñp f (x) = g(Ax) l  h m lçi. d) N¸u g : D ⊆ Rn → R l  h m lçi v  h : R → R l  h m lçi khæng gi£m th¼ h m hñp f (x) = h (g (x)) l  h m lçi. ành lþ 1.15. : Cho mët tªp lçi D ⊂ Rn v  mët h m f : Rn → R kh£ vi tr¶n D. a) H m f lçi tr¶n D khi v  ch¿ khi f (y) ≥ f (x) + h∇f (x) , y − xi ∀x, y ∈ D. b) N¸u f (y) > f (x) + h∇f (x) , y − xi ∀x, y ∈ D, x 6= y th¼ f h m D lçi ch°t tr¶n . ành lþ 1.16. Gi£ sû f : S → (−∞, +∞] l  mët h m lçi tr¶n Rn v  α ∈ (−∞, +∞]. Khi â, c¡c tªp mùc d÷îi Cα = {x : f (x) < α} , Cα = {x : f (x) ≤ α} , l  tªp lçi. T÷ìng tü, n¸u f l  mët h m lãm tr¶n Rn th¼ c¡c tªp mùc tr¶n Dβ = {x : f (x) < β} , Dβ = {x : f (x) ≥ β} , l  tªp lçi. Mët h m f m  måi tªp mùc d÷îi l  tªp lçi gåi l  mët h m tüa lçi. p Chó þ 1.17. h m f (x) = x3 hay f (x) = kxk tr¶n R l  c¡c h m tüa lçi nh÷ng khæng lçi. ành lþ 1.18. Mët h m lçi ch°t f tr¶n mët tªp lçi C câ nhi·u nh§t mët iºm cüc tiºu tr¶n C , ngh¾a l  tªp Arg minx∈C f (x) gçm nhi·u nh§t mët ph¦n tû. Chùng minh. N¸u f câ hai iºm
cüc tiºu kh¡c nhau x, y ∈ C th¼ do t½nh lçi ch°t cõa vîi x f n¶n l  iºm cüc tiºu. f 1 2x + 12 y < f (x) = f (y), i·u n y m¥u thu¨n 9 H m lçi m¤nh mët bi¸n f (x) = x2 câ duy nh§t mët iºm cüc tiºu x∗ = 0. Cán h m lçi ch°t f (x) = ex (x ∈ R) khæng câ iºm cüc tiºu n o. ành ngh¾a 1.20. Cho h m lçi ch½nh th÷íng f tr¶n Rn , v²c tì p ∈ Rn gåi l  d÷îi ¤o h m cõa f t¤i iºm x0 n¸u V½ dö 1.19. 
p, x − x0 + f x0 ≤ f (x) ∀x ∈ Rn . (3) ≤ bði d§u ≥. 0 Tªp t§t c£ c¡c d÷îi ¤o h m cõa f t¤i x ÷ñc gåi l  d÷îi vi ph¥n cõa
f t¤i x0 v  ÷ñc kþ hi»u l  ∂f x0 . H m f ÷ñc gåi l  kh£ d÷îi vi ph¥n
0 0 t¤i x n¸u ∂f x 6= ∅. N¸u f lãm th¼ trong (3) thay d§u . Sau ¥y l  d÷îi vi ph¥n cõa mët sè h m quen thuëc. 1) H m afin f (x) = ha, xi + α ( a ∈ Rn, α ∈ R) câ V½ dö 1.21. ∂f (x) = {a} , (∀x ∈ Rn ) . 2) D÷îi vi ph¥n cõa h m ch¿ δC (x) cõa mët tªp lçi C x0 ∈ C ch½nh l  nân ph¡p tuy¸n ngo i cõa C : ∂δC x0 Thªt vªy, n¸u p
= 6= ∅  p : p, x − x0 ≤ 0 ∀x ∈ C .
0 t¤i mët iºm  ∈ ∂δC x , theo ành ngh¾a 
p, x − x0 + δ x0 ≤ δ (x) ∀x,
n¸u x ∈ C , th¼ δC (x) = 0 v  do
δC x0 = 0.  Ng÷ñc l¤i n¸u p ∈ NC x0 , ta câ p : p, x − x0 ≤ 0 ∀x ∈ C m 
δ x0 = 0 (do x0 ∈ C ) 
•) x ∈ C , δ (x) = 0 suy ra p, x − x0 + δ x0 ≤ δ (x). 
•) x ∈ / C suy ra δ (x) = +∞ suy ra p, x − x0 + δ x0 ≤ δ (x) luæn óng ∀x. 3) N¸u f (x) = kxk (chu©n Euclid) th¼ (
{p : kpk ≤ 1} khi x0 = 0, 0 ∂f x =  0 0 x / x khi x0 6= 0 . 10 X²t h m sè f (x) Khi ∂f 1.2 x0
= |x| ch¿ quanh mët ∂f (0) = [−1, 1] .

iºm th¼ ∂f x0 = f 0 x0 . Ph¡t biºu b i to¡n v  v½ dö B i to¡n quy ho¤ch lçi ÷ñc · cªp ¸n trong luªn v«n n y câ d¤ng to¡n håc nh÷ sau: min {f (x) : x ∈ D ⊆ Rn } (Co) D ⊆ Rn l  mët tªp lçi âng v  f : Rn → R ∪ {+∞} l  mët n h m lçi tr¶n R . Tªp D ÷ñc gåi l  mi·n r ng buëc (hay mi·n ch§p nhªn ÷ñc) v  f ÷ñc trong â gåi l  h m möc ti¶u cõa b i to¡n (Co). D÷îi ¥y l  mët sè lîp quan trång cõa b i to¡n quy ho¤ch lçi. 1.2.1 f B i to¡n quy ho¤ch tuy¸n t½nh l  tuy¸n t½nh, D l  mët tªp a di»n lçi. V½ dö, f (x) = dT x, D : = {x ≥ 0 : Ax = b} , ð ¥y: A ∈ Rm×n , b ∈ Rm . 1.2.2 B i to¡n quy ho¤ch to n ph÷ìng lçi B i to¡n câ d¤ng :  min xT Qx + q T x trong â Q : x∈ D , l  ma trªn èi xùng nûa x¡c ành d÷ìng v  D ⊂ Rn . 11 Mët tr÷íng hñp ri¶ng quan trång cõa b i to¡n quy ho¤ch to n ph÷ìng lçi l  b i to¡n t¼m h¼nh chi¸u cõa mët iºm cho tr÷îc x0 tr¶n mët tªp lçi, tùc l  b i to¡n n o 2 0 min x − x : x ∈ D . 1.3 Sü tçn t¤i v  t½nh ch§t cõa tªp nghi»m Trong möc n y chóng ta x²t ¸n sü tçn t¤i v  c¡c t½nh ch§t cõa b i to¡n quy ho¤ch lçi. iºm x0 ∈ D ÷ñc gåi l  nghi»m tèi ÷u àa ph÷ìng cõa (Co) n¸u tçn t¤i mët l¥n cªn mð U cõa x0 sao cho ành ngh¾a 1.22. f x0
≤ f (x) ∀x ∈ D ∩ U. iºm x∗ ÷ñc gåi l  nghi»m tèi ÷u to n cöc n¸u: f (x∗ ) ≤ f (x) ∀x ∈ D. èi vîi quy ho¤ch lçi ta câ m»nh · sau: Trong b i to¡n quy ho¤ch lçi th¼ måi nghi»m tèi ÷u àa ph÷ìng ·u l  nghi»m tèi ÷u to n cöc v  tªp nghi»m l  tªp lçi. Chùng minh. Cho h m lçi f : Rn → R v  tªp lçi kh¡c réng D ⊂ Rn. M»nh · 1.23. min {f (x) \x ∈ D}. x∗ ∈ D l  mët nghi»m tèi X²t b i to¡n Gi£ sû ÷u àa ph÷ìng cõa b i to¡n min {f (x) \x ∈ D} . Theo ành ngh¾a, tçn t¤i mët ε - l¥n cªn B (x∗ , ε) cõa iºm x∗ ∈ D cho f (x∗ ) ≤ f (x) Vîi b§t ký x ∈ D, ∀x ∈ B (x∗ , ε) ∩ D. ta câ x = λx + (1 − λ) x∗ = x∗ + λ (x − x∗ ) ∈ B (x∗ , ε) ∩ D, sao 12 khi 0 <λ < 1 v  λ õ nhä. Do x∗ l  nghi»m cüc tiºu àa ph÷ìng v  f l  h m lçi n¶n f (x∗ ) ≤ f (x) ≤ λf (x) + (1 − λ) f (x∗ ) ⇒ f (x∗ ) ≤ f (x) i·u â chùng tä x∗ ∀x ∈ B (x∗ , ε) ∩ D. l  mët nghi»m tèi ÷u to n cöc cõa b i to¡n ang x²t. x∗ , y ∗ ∈ D l  c¡c nghi»m tèi ÷u àa ph÷ìng cõa f tr¶n D. Vªy f (x∗ ) = f (y ∗ ) ≤ f (x) vîi måi x ∈ D. L§y z ∗ := λx∗ + (1 − λ) y ∗ , vîi 0 < λ < 1. Do D lçi, n¶n z ∗ ∈ D v  do f lçi, n¶n Gi£ sû f (x∗ ) ≤ λf (x∗ ) + (1 − λ) f (y ∗ ) ≤ f (x) . Suy ra z∗ công l  nghi»m tèi ÷u cõa ¡n tèi ÷u cõa f tr¶n D f tr¶n D. Chùng tä tªp c¡c ph÷ìng l  lçi. (Weistrass) N¸u D l  tªp compact v  f nûa li¶n töc d÷îi tr¶n D, th¼ f ¤t cüc tiºu tr¶n D. ành lþ 1.25. Cho tªp âng kh¡c réng D ⊂ Rn . N¸u h m f l  nûa li¶n töc d÷îi tr¶n D v  thäa m¢n i·u ki»n bùc tr¶n D, f (x) → +∞ khi x ∈ D v  kxk → +∞ th¼ b i to¡n (Co) câ nghi»m tèi ÷u. Chùng minh. L§y mët iºm b§t ký. Tr÷îc h¸t, ta chùng minh r¬ng tªp ành lþ 1.24. mùc d÷îi 
D = x ∈ D\f (x) ≤ f x0 , f l  nûa n d¢y {f (x )} l  tªp compact. Thªt vªy, do li¶n töc d÷îi tr¶n {xn } ⊂ D, {xn } → x hëi tö, ta câ m  D n¶n méi d¢y
f (x) ≤ lim f (xn ) ≤ f x0 . n→∞ x ∈ D, chùng tä D l  tªp âng. Hìn núa, n¸u D khæng bà ch°n th¼  k

ph£i tçn t¤i mët d¢y x ⊂ D, tùc f xk ≤ f x0 , sao cho xk → +∞.
 k Do i·u ki»n bùc n¶n f x → +∞, m¥u thu¨n vîi sü ki»n xk ⊂ D. Suy ra 13 Vªy D l  tªp compact. f ¤t cüc tiºu tr¶n D, tùc l  tçn t¤i x∗ ∈ D ∗ måi x ∈ D . D¹ th§y, x công ch½nh l  nghi»m Theo ành lþ Weistrass h m f (x∗ ) ≤ f (x) sao cho vîi cüc tiºu cõa b i to¡n (Co). N¸u h m f lçi m¤nh v  kh£ vi tr¶n tªp lçi âng D th¼ tçn t¤i duy nh§t iºm x∗ ∈ D sao cho f (x∗) = min {f (x) : x ∈ D}. Chùng minh. :Do f l  h m lçi n¶n theo ành lþ 1.15, vîi måi x, y ∈ D ành lþ 1.26. th¼ f (x) − f (y) ≤ h∇f (x) , x − yi . Hìn núa, do f lçi m¤nh n¶n vîi 0 ≤ 14 ρkx − yk2 ≤ 1 2  f (x) − f 1 2x λ= 1 2 ta câ: + 12 y
 + ≤ 14 h∇f (x) , x − yi + 14 h∇f (y) , y − xi = 1 1 1 2 f (y) − f 2 x + 2 y 1 4 h∇f (x) − ∇f (y) , x 
 − yi .(4) Do f (x) − f (y) = R1 h∇f [y + λ (x − y)] , x − yi dλ 0 = h∇f (y) , x − yi + R1 h∇f [y + λ (x − y)] − ∇f (y) , x − yi dλ, 0 n¶n k¸t hñp vîi b§t ¯ng thùc (4) ta ÷ñc f (x) − f (y) ≥ h∇f (y) , x − yi + 12 ρkx − yk2 2

 ⇒ 0 ≥ f (x) − f x0 ≥ ∇f x0 , x − x0 + 21 ρ x − x0 2

⇒ x − x0 ≤ 2 ∇f x0 , x − x0 ≤ 2 ∇f x0 × x − x0 . ρ Tø â suy ra x − x0 2 ≤ ρ 2 ρ
∇f x0 vîi måi x ∈ D0 ngh¾a l  D0 bà ch°n. Do h m D0 ⊂ D f (x) sao cho D0 ⊂ D, n¶n tçn f (x∗ ) = min {f (x) : x ∈ D0 } = min {f (x) : x ∈ D}. li¶n töc tr¶n tªp lçi âng bà ch°n t¤i V¼ h m lçi m¤nh công l  h m lçi ch°t, n¶n theo ành lþ 1.18 iºm cüc tiºu x∗ l  duy nh§t. 14 1.4 i·u ki»n tèi ÷u C¥u häi: n¸u x∗ l  mët ph÷ìng ¡n tèi ÷u (àa ph÷ìng ho°c to n cöc), th¼ i·u g¼ x£y ra vîi x∗ ? (cho tr÷íng hñp lçi) Gi£ sû D l  tªp lçi v  f l  h m lçi kh£ d÷îi vi ph¥n tr¶n D. Khi â l  líi gi£i tèi ÷u cõa (Co) khi v  ch¿ khi ành lþ 1.27. 0 ∈ ∂f (x∗ ) + ND (x∗ ) . (5) trong â ND (x∗) l  nân ph¡p tuy¸n cõa D t¤i x∗. Chùng minh. . (i) i·u ki»n õ: Gi£ sû (5) óng. Khi â tçn t¤i p∗ sao cho p∗ ∈ ∂f (x∗ ) ∩ (ND (x∗ )) . Do p∗ ∈ ∂f (x∗ ) ta câ hp∗ , x − x∗ i ≤ f (x) − f (x∗ ) ∀x, p∗ ∈ −ND (x∗ ) do n¶n hp∗ , x − x∗ i ≥ 0 ∀x ∈ D. Do â f (x) − f (x∗ ) ≥ 0 (ii) i·u ki»n c¦n: Gi£ sû x∗ ∀x ∈ D. l  líi gi£i tèi ÷u. B¬ng c¡ch h¤n ch¸ trong D, chóng ta câ thº gi£ ành intD 6= ∅. X²t hai tªp sau: khæng gian afin cõa Do D l  lçi, n¶n r¬ng D câ ¦y õ chi·u. E : = {(t, x) ∈ R × Rn : t > f (x) − f (x∗ ) , x ∈ D} G : = {0} × D. D¹ th§y: C£ p döng E v  G l  hai tªp lçi (tø D v  f l  lçi). Hìn th¸ núa G ∩E = ∅. n+1 ành lþ t¡ch, tçn t¤i (u0 , u) 6= 0 ∈ R sao cho u0 t + uT x ≤ u0 0 + uT y ∀ (t, x) ∈ E, x ∈ D. (6) 15 Tø (6), vîi t → +∞ suy ra u0 < 0. N¸u u0 = 0, th¼ hu, x − yi ≤ 0 ∀x, y ∈ D. Ho°c hu, zi ≤ 0 ∀z ∈ D − D ≡ C. 0 ∈ D, gi£ sû 0 ∈ intD. Khi â tø (7) thäa m¢n v¼ u0 = 0). Do â u0 < 0. B¬ng c¡ch ∗ cho −u0 > 0, ta câ vîi t → f (x) − f (x ) Rã r ng − [f (x) − f (x∗ )] + uT x ≤ uT y Cho y = x∗ , ta câ (7) u = 0 ( khæng chia c£ hai v¸ cõa (6) ∀x, y ∈ D. (8) tø (8) chóng ta câ − [f (x) − f (x∗ )] + uT x ≤ uT x∗ ∀x, ∈ D. Suy ra f (x∗ ) − f (x) + uT (x − x∗ ) ∀x ∈ D. f (x) = ∞ V¼ vîi måi x ∈ / C n¶n tø (9) chóng ta câ f (x∗ ) − f (x) + uT (x − x∗ ) ≤ 0 vîi u ∈ ∂f (x∗ ). (9) M°t kh¡c, cho x = x∗ ∀x ∈ Rn tø (9) chóng ta câ uT (y − x∗ ) ≥ 0 ∀y ∈ D. Vîi −u ∈ ND (x∗ ). Tø u ∈ ∂f (x∗ ) ta câ 0 ∈ ∂f (x∗ ) + ND (x∗ ) . ∈ intD v  x∗ ∈ S (D, f ) ( l  líi gi£i tèi ÷u cõa (Co)), khi â 0 ∈ ∂f (x∗). °c bi»t, n¸u f l  kh£ vi tr¶n to n bë khæng gian th¼ 0 = ∇f (x∗). H» qu£ 1.28. N¸u x∗ B¥y gií ta x²t b i to¡n min f (x) v..k. x ∈ D, 16 trong â D := { x ∈ X : gj (x) ≤ 0, hi (x) = 0 vîi j = 1, ..., m; i = 1, ..., k } , (∗) ∅ 6= X ⊆ Rn v  f, gj , hi : Rn → R ∀i, j . Ta nâi (Co) l  quy ho¤ch lçi n¸u X l  tªp lçi âng v  t§t c£ f, gj vîi måi j ·u lçi, cán hi l  afin vîi måi i. (Karush-Kuhn-Tucker) Gi£ sû (Co) l  quy ho¤ch lçi vîi D ÷ñc cho bði (∗). Khi â n¸u x∗ l  mët líi gi£i tèi ÷u cõa b i to¡n (Co), th¼ tçn t¤i λ∗i ≥ 0 (i = 0, 1, ..., m) v  µ∗i (i = 1, ..., k) khæng çng thíi b¬ng 0 thäa m¢n L (x∗ , λ∗ , µ∗ ) = min L (x, λ∗ , µ∗ ) (¤o h m tri»t ti¶u) x∈X ành lþ 1.29. (i·u ki»n bò). Ng÷ñc l¤i, n¸u intX 6= ∅ v  i·u ki»n Slater: λ∗i gj (x∗ ) = 0 (i = 1, ..., m)
∃x0 ∈ D : gi x0 < 0 (i = 1, ..., m) thäa m¢n v  c¡c h m afin hi (i = 1, ..., k) l  ëc lªp tuy¸n t½nh tr¶n X , khi â λ∗0 > 0 v  hai i·u ki»n tr¶n thäa m¢n t¤i iºm ch§p nhªn ÷ñc x∗, th¼ x∗ l  líi gi£i tèi ÷u cõa (Co). Chùng minh. Gi£ sû x∗ l  líi gi£i tèi ÷u àa ph÷ìng cõa (Co). X¡c ành K := { (λ0 , λ1 , ..., λm , µ1 , ..., µk ) / (∃x ∈ X) : f (x)−f (x∗ ) < λ0 , X 6= ∅ gi (x) ≤ λi , i = 1, ..., m, hi (x) = µj , j = 1, ..., k } . f, gi lçi v  hi afin, n¶n X, K l  mët tªp âng trong Rm+k+1 , ta câ 0 ∈ / D. Thªt vªy, n¸u 0 ∈ K th¼ câ x l  líi gi£i ch§p ∗ ∗ nhªn ÷ñc sao cho f (x) < f (x ). i·u n y m¥u thu¨n vîi gi£ thi¸t x l  ∗ nghi»m tèi ÷u cõa (Co). p döng ành lþ t¡ch, ta câ λj (j = 1, ..., k) khæng Do lçi, çng thíi b¬ng 0, sao cho m X λ∗i λi i=0 + k X µ∗i µi ≥ 0 ∀ (λ0 , λ1 , ..., λm , µ1 , ..., µk ) ∈ K. j=1 λ0 , ..., λm > 0 (λ0 , ..., λm , 0, ..., 0) ∈ K . L÷u þ n¸u th¼ ta l§y x = x∗ khi â ta câ (10)