Tài liệu điều kiện cần cực trị bậc nhất trong quy hoạch toàn phương

BË GIO DÖC V€ €O T„O TR×ÍNG „I HÅC S× PH„M H€ NËI 2 €M THÀ THƒO I—U KI›N C†N CÜC TRÀ BŠC NH‡T TRONG QUY HO„CH TO€N PH×ÌNG Chuy¶n ng nh: To¡n gi£i t½ch M¢ sè: 60 46 01 02 LUŠN V‹N TH„C Sž TON GIƒI TCH Ng÷íi h÷îng d¨n khoa håc: PGS. TS. Nguy¹n N«ng T¥m H  Nëi 2017 LÍI CƒM ÌN Luªn v«n n y ÷ñc ho n th nh vîi sü h÷îng d¨n v  ch¿ b£o tªn t¼nh cõa PGS.TS. Nguy¹n N«ng T¥m. Em xin ÷ñc b y tä láng bi¸t ìn s¥u s­c èi vîi sü quan t¥m, ëng vi¶n v  sü ch¿ b£o h÷îng d¨n cõa th¦y. Tæi xin c£m ìn quþ th¦y, quþ cæ Pháng Sau ¤i håc Tr÷íng ¤i håc S÷ ph¤m H  Nëi 2. çng thíi tæi xin c£m ìn tªp thº lîp Cao håc To¡n gi£i t½ch K19 ñt 2 cõa Tr÷íng ¤i håc S÷ ph¤m H  Nëi 2 ¢ ëng vi¶n gióp ï tæi trong qu¡ tr¼nh håc tªp v  l m luªn v«n n y. Tæi xin ch¥n th nh c£m ìn tîi Ban gi¡m hi»u Tr÷íng THPT Quang Minh, H  Nëi, c¡c çng nghi»p v  gia ¼nh ¢ t¤o i·u ki»n gióp ï tæi ho n th nh luªn v«n n y. H  Nëi, th¡ng 8 n«m 2017  m Thà Th£o LÍI CAM OAN Tæi xin cam oan luªn v«n n y l  cæng tr¼nh nghi¶n cùu cõa ri¶ng tæi d÷îi sü h÷îng d¨n cõa PGS.TS Nguy¹n N«ng T¥m. Sè li»u v  c¡c k¸t qu£ nghi¶n cùu trong luªn v«n n y l  trung thüc v  khæng tròng l°p vîi c¡c · t i kh¡c. Trong qu¡ tr¼nh nghi¶n cùu, tæi ¢ k¸ thøa th nh tüu khoa håc cõa c¡c nh  khoa håc vîi sü tr¥n trång v  bi¸t ìn. H  Nëi, th¡ng 8 n«m 2017  m Thà Th£o MÖC LÖC MÐ †U . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 BƒNG K HI›U . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Ch÷ìng 1. KI˜N THÙC CHU‰N BÀ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1. Mët sè kh¡i ni»m cõa Gi£i t½ch lçi . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. B i to¡n tèi ÷u húu h¤n chi·u . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3. B i to¡n tèi ÷u to n ph÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Ch÷ìng 2. I—U KI›N CÜC TRÀ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1. i·u ki»n tçn t¤i nghi»m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. i·u ki»n c¦n cüc trà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Ch÷ìng 3. MËT SÈ ÙNG DÖNG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.1. p döng º t¼m nghi»m b i to¡n tèi ÷u to n ph÷ìng . . . . . 40 3.2. p döng v o nghi¶n cùu t½nh ên ành cõa b i to¡n tèi ÷u to n ph÷ìng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 K˜T LUŠN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 T€I LI›U THAM KHƒO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 1 MÐ †U i·u ki»n cüc trà l  mët trong nhúng èi t÷ñng luæn ÷ñc quan t¥m h ng ¦u trong nghi¶n cùu mët b i to¡n quy ho¤ch to¡n håc. i·u ki»n c¦n cüc trà ÷ñc sû döng rëng r¢i trong lþ thuy¸t v  ùng döng cõa nhi·u l¾nh vüc to¡n håc bao gçm vi»c t¼m nghi»m, nghi¶n cùu sü tçn t¤i nghi»m v  nghi¶n cùu t½nh ên ành b i to¡n quy ho¤ch to¡n håc. Trong nhúng n«m qua vi»c nghi¶n cùu c¡c t½nh ch§t v  ùng döng cõa Quy ho¤ch to n ph÷ìng ¢ ÷ñc ph¡t triºn m¤nh m³. Tuy nhi¶n, nhúng i·u ki»n tèi ÷u cõa nhúng lîp b i to¡n quy ho¤ch to n ph÷ìng câ °c tr÷ng ri¶ng s³ câ nhúng t½nh ch§t ri¶ng bi»t, ¥y câ thº coi l  mët chõ · væ tªn º nghi¶n cùu v  ùng döng trong nhi·u l¾nh vüc to¡n håc. V¼ vªy, sau khi håc ÷ñc c¡c ki¸n thùc v· To¡n gi£i t½ch, vîi mong muèn t¼m hiºu s¥u hìn v· c¡c ki¸n thùc ¢ håc, mèi quan h» v  ùng döng cõa chóng, tæi ¢ chån · t i nghi¶n cùu i·u ki»n c¦n cüc trà bªc nh§t trong quy ho¤ch to n ph÷ìng. Möc ½ch cõa luªn v«n n y, thù nh§t l  t¼m hiºu v· nhúng b i to¡n quy ho¤ch to n ph÷ìng v  nhúng i·u ki»n c¦n cüc trà cõa chóng. Thæng qua â th§y ÷ñc t¦m quan trång cõa nhúng ki¸n thùc ¢ håc v  ùng döng cõa chóng. Thù hai, tr¼nh b y ÷ñc mët c¡ch câ h» thèng nhúng i·u ki»n c¦n cüc trà bªc nh§t cho mët sè lîp b i to¡n quy ho¤ch to n ph÷ìng v  mët sè ùng döng cõa chóng. Luªn v«n tªp trung nghi¶n cùu nhúng i·u ki»n c¦n cüc trà bªc nh§t cho mët sè lîp c¡c b i to¡n quy ho¤ch to n ph÷ìng câ t½nh ch§t °c bi»t trong khæng gian Euclid. p döng k¸t qu£ thu ÷ñc º nghi¶n cùu mët sè nëi dung cõa quy ho¤ch to n ph÷ìng. 2 Trong luªn v«n n y, ngo i ph¦n mð ¦u, k¸t luªn, danh s¡ch c¡c t i li»u tham kh£o, luªn v«n bao gçm ba ch÷ìng: Ch÷ìng 1: Tr¼nh b y mët sè k¸t qu£ v· tªp lçi, h m lçi, t½nh ch§t cõa h m lçi, b i to¡n tèi ÷u húu h¤n chi·u v  b i to¡n quy ho¤ch to n ph÷ìng. Ch÷ìng 2: Tr¼nh b y v· i·u ki»n tçn t¤i nghi»m v  i·u ki»n c¦n cüc trà bªc nh§t cõa b i to¡n quy ho¤ch to n ph÷ìng. Ch÷ìng 3: Tr¼nh b y v· ¡p döng i·u ki»n c¦n cüc trà bªc nh§t v o t¼m nghi»m cõa b i to¡n quy ho¤ch to n ph÷ìng v  nghi¶n cùu t½nh ên ành cõa b i to¡n tèi ÷u to n ph÷ìng. Do thíi gian câ h¤n n¶n luªn v«n n y ch¿ mîi døng l¤i ð vi»c t¼m hiºu, tªp hñp t i li»u, s­p x¸p v  tr¼nh b y k¸t qu£ nghi¶n cùu ¢ câ theo chõ · °t ra. Trong qu¡ tr¼nh vi¸t luªn v«n công nh÷ xû lþ v«n b£n ch­c ch­n khæng tr¡nh khäi nhúng sai sât nh§t ành. T¡c gi£ luªn v«n r§t mong nhªn ÷ñc sü gâp þ cõa quþ th¦y cæ v  c¡c b¤n º luªn v«n ÷ñc ho n thi»n hìn. 3 BƒNG K HI›U ∅ tªp réng x∈X x l  mët ph¦n tû cõa tªp x∈ /X x khæng thuëc {x ∈ X | P (x)} Tªp c¡c ph¦n tû N tªp hñp c¡c sè tü nhi¶n R tªp hñp c¡c sè thüc Rn khæng gian Euclid Rm×n khæng gian c¡c ma trªn c§p Rm×n S khæng gian c¡c ma trªn èi xùng c§p kxk chu©n cõa xn → x xn F tªp ch§p nhªn ÷ñc (tªp r ng buëc) cõa b i to¡n X X x cõa n X tu¥n theo t½nh ch§t P (x) chi·u m×n m×n x hëi tö tîi x tèi ÷u Sol(P) tªp nghi»m cõa b i to¡n (P) loc(P) tªp nghi»m àa ph÷ìng cõa b i to¡n (P) S(P) tªp iºm KKT cõa b i to¡n (P) v. . k. vîi i·u ki»n 4 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, ành ngh¾a v  k¸t qu£ c¦n thi¸t li¶n quan ¸n tªp lçi, h m lçi, b i to¡n tèi ÷u húu h¤n chi·u v  b i to¡n tèi ÷u to n ph÷ìng. Nhi·u k¸t qu£ trong ch÷ìng n y ÷ñc tr¼nh b y ng­n gån khæng k±m theo chùng minh. C¡c k¸t qu£ â ÷ñc tham kh£o tø c¡c t i li»u [1, 6]. 1.1. Mët sè kh¡i ni»m cõa Gi£i t½ch lçi Trong luªn v«n n y, væ h÷îng h· , ·i. Rn k½ hi»u l  khæng gian Euclid Mët t½ch væ h÷îng n chi·u vîi t½ch h· , ·i : Rn × Rn → R l  mët d¤ng song tuy¸n t½nh x¡c ành d÷ìng. Tùc l , (i) (ii) x 7→ hx, yi l  tuy¸n t½nh vîi måi hx, yi = hy, xi (iii) hx, xi > 0 N¸u h· , ·i vîi måi vîi måi x, y ∈ Rn ; x ∈ Rn hx, xi = 0 n¸u v  ch¿ n¸u x = 0. p th¼ kxk = hx, xi x¡c ành mët chu©n v  l  mët t½ch væ h÷îng, tr¶n khæng gian y ∈ Rn ; Rn . 1.1.1. Tªp lçi ành ngh¾a 1.1.1. Tªp C ⊂ Rn ÷ñc gåi l  tªp lçi n¸u: αx + (1 − α)y ∈ C, ∀x, y ∈ C, ∀α ∈ [0, 1] Chó þ : Quy ÷îc tªp ∅ (1.1) l  tªp lçi. Mët sè ph²p to¡n tr¶n c¡c tªp lçi ÷ñc ph¡t biºu trong m»nh · sau. 5 M»nh · 1.1.2. : (a) Gi£ sû Khi â tªp Ci ⊂ Rn (i ∈ I) ∩i∈I Ci (b) Gi£ sû (c) Tªp λC C1 l  c¡c tªp lçi, vîi I l  tªp ch¿ sè b§t ký. l  tªp lçi. v  C2 l  hai tªp lçi. Khi â, l  tªp lçi vîi måi tªp lçi 1.1.2. H m lçi ành ngh¾a 1.1.3. Cho C ⊂ Rn C C1 + C2 v  vîi måi l  mët tªp lçi. H m l  tªp lçi. λ thuëc R . f :C→R ÷ñc gåi l  h m lçi n¸u: f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y), ∀x, y ∈ C, ∀α ∈ [0, 1] Mët h m lçi l  ng°t vîi måi f : C → R ÷ñc gåi l  lçi x, y ∈ C f :C →R H m (1.2) ng°t n¸u b§t ¯ng thùc (1.2) x 6= y , ∀α ∈ [0, 1]. v  ÷ñc gåi l  lãm, trong â C −f l  tªp lçi, khi l  h m lçi. C T½nh lçi cõa mi·n x¡c ành f :C→R Cho l  i·u ki»n ti¶n quy¸t º cho h m l  "lçi". f : C → R l  mët h m v  γ {x ∈ C | f (x) < γ} thuëc R, tªp {x ∈ C | f (x) ≤ γ} v  ÷ñc gåi l  c¡c tªp mùc cõa h m f. N¸u f l  mët h m lçi, khi â t§t c£ c¡c tªp mùc cõa nâ ·u l  tªp lçi. Thªt vªy, l§y x1 , x2 ∈ C tªp lçi khi â, vîi måi αγ + (1 − α)γ = γ sao cho α ∈ [0, 1] f (x1 ) ≤ γ ta câ v  f (x2 ) ≤ γ . αx1 + (1 − α)x2 ∈ C . Tø ta suy ra f (αx1 + (1 − α)x2 ) ≤ αf (x1 ) + (1 − α)f (x2 ) ≤ γ. Do vªy {x ∈ C | f (x) ≤ γ} l  tªp lçi. Chùng minh t÷ìng tü ta câ {x ∈ C | f (x) < γ} 6 lçi. V¼ f C l  lçi v  L÷u þ, tªp mùc cõa mët h m l  lçi ch÷a ch­c h m â l  lçi. Ch¯ng h¤n, h m f (x) = p |x| câ tªp mùc l  lçi nh÷ng nâ khæng ph£i h m lçi. 1.2. B i to¡n tèi ÷u húu h¤n chi·u Nhi·u b i to¡n lþ thuy¸t v  thüc t¸ câ thº ÷a ÷ñc v· d¤ng Minimize trong â f : Rn → R f (x) l  mët h m cho tr÷îc v  tr÷îc. Tø ¥y v· sau x ∈ F, vîi i·u ki»n F ⊂ Rn (P) l  mët tªp cho R = [−∞, +∞] = R ∪ {−∞} ∪ {+∞} ÷ñc k½ hi»u l  ÷íng th¯ng thüc mð rëng. ành ngh¾a 1.2.1. H m f Chóng ta gåi (P) l  b i to¡n quy ho¤ch to¡n håc. ÷ñc gåi l  h m möc ti¶u v  F ÷ñc gåi l  tªp r ng buëc (công ÷ñc gåi l  mi·n ch§p nhªn ÷ñc ) cõa b i to¡n (P). C¡c ph¦n tû cõa ÷ñc gåi l  c¡c v²c tì ch§p nhªn ÷ñc cõa (P). N¸u ta nâi (P) l  mët b i to¡n khæng r ng buëc. N¸u F = Rn F= 6 Rn F th¼ chóng th¼ chóng ta nâi (P) ÷ñc gåi l  b i to¡n câ r ng buëc. ành ngh¾a 1.2.2. B i to¡n (P) ÷ñc gåi l  b i to¡n quy ho¤ch lçi (mët b i to¡n quy ho¤ch to¡n håc lçi) n¸u F l  mët tªp lçi v  f l  mët h m lçi. ành ngh¾a 1.2.3. (xem [10, p. 4]) Mët v²c tì ch§p nhªn ÷ñc x̄ ∈ F ÷ñc gåi l  mët nghi»m (to n cöc) cõa b i to¡n (P) n¸u f (x̄) 6= +∞ v  f (x̄) ≤ f (x) l  mët nghi»m vîi måi x ∈ F. àa ph÷ìng cõa (P) n¸u Chóng ta nâi r¬ng f (x̄) 6= +∞ x̄ ∈ F v  tçn t¤i mët l¥n cªn U cõa x̄ sao cho f (x̄) ≤ f (x) vîi måi 7 x ∈ F ∩ U. (1.3) Tªp t§t c£ c¡c nghi»m, nghi»m àa ph÷ìng cõa b i to¡n (P) ÷ñc k½ hi»u l¦n l÷ñt bði Sol(P) v  loc(P) Chóng ta nâi r¬ng hai b i to¡n quy ho¤ch l  t÷ìng ÷ìng n¸u tªp nghi»m cõa b i to¡n n y tròng vîi tªp nghi»m cõa b i to¡n kia. ành ngh¾a 1.2.4. Gi¡ trà tèi ÷u v (P) cõa (P) ÷ñc x¡c ành bði v (P) = inf{f (x) : x ∈ F}. N¸u F =∅ th¼ ta quy ÷îc v (P) = +∞. Nhªn x²t 1.2.5. D¹ r ng th§y r¬ng Sol Sol(P) Nhªn x²t 1.2.6. (P) ⊂ loc(P). Hiºn nhi¶n l  = {x ∈ F : f (x) 6= +∞, f (x) = v (P)}. Câ thº x£y ra tr÷íng hñp loc(P) \ Sol(P) h¤n, n¸u chóng ta chån x̄ = 1 (1.4) F = [−1, +∞) v  6= ∅. Ch¯ng f (x) = 2x3 − 3x2 + 1 th¼ l  mët nghi»m àa ph÷ìng cõa (P) nh÷ng khæng l  nghi»m to n cöc. Nhªn x²t 1.2.7. Ngo i b i to¡n cüc tiºu (P) ta câ thº g°p b i to¡n cüc ¤i nh÷ sau Maximize Mët iºm v  x̄ ∈ F f (x) v. . k. x ∈ F. (P1 ) ÷ñc gåi l  nghi»m to n cöc cõa (P1 ) n¸u f (x̄) ≥ f (x) vîi måi x ∈ F . Chóng ta nâi r¬ng x̄ ∈ F àa ph÷ìng cõa (P1 ) n¸u f (x̄) ≥ f (x) f (x̄) 6= −∞ f (x̄) 6= −∞ l  mët nghi»m v  tçn t¤i mët l¥n cªn x ∈ F ∩ U. U cõa x̄ D¹ th§y r¬ng x̄ l  nghi»m (nghi»m àa ph÷ìng, t÷ìng ùng) cõa (P1 ) n¸u v  ch¿ n¸u x̄ l  nghi»m sao cho vîi måi (nghi»m àa ph÷ìng, t÷ìng ùng) cõa b i to¡n cüc tiºu Minimize − f (x) 8 vîi i·u ki»n x ∈ F. V¼ vªy b§t ký b i to¡n cüc ¤i d¤ng (P1 ) câ thº suy ra b i to¡n cüc tiºu d¤ng (P). Nhªn x²t 1.2.8. L÷u þ r¬ng trong tr÷íng hñp = ∅. h¤n, câ thº x£y ra r¬ng Sol(P) v  f (x) =    Ch¯ng h¤n n¸u 1 |x|   +∞ v (P) = 0, th¼ trong khi Sol(P) v (P) l  mët sè thüc húu vîi x 6= 0 vîi x=0 F = [1, +∞) ⊂ R = ∅. 1.3. B i to¡n tèi ÷u to n ph÷ìng ành ngh¾a 1.3.1. Chóng ta nâi r¬ng f : Rn → R ph÷ìng tuy¸n t½nh n¸u tçn t¤i mët ma trªn c ∈ Rn v  mët sè thüc α l  mët h m to n Q ∈ Rn×n , mët v²c tì sao cho 1 T 1 x Qx + cT x + α = hx, Qxi + hc, xi + α. 2 2 (1.5) N¸u  d11 · · · d1n     Q= · · · · · · · · ·  , dn1 · · · dnn   c1 . .  c=  . , cn   x=  x1 .. .   ,  xn th¼ (1.5) ÷ñc vi¸t th nh n n n  X 1 X X f (x) = dij xi xj + ci xi + α. 2 j=1 i=1 i=1 1 xT Qx = xT (Q + QT )x vîi méi x ∈ Rn , n¶n (1.5) v¨n thäa m¢n 2 1 T ta thay Q bði ma trªn èi xùng (Q + Q ). V¼ lþ do n y, chóng ta 2 V¼ n¸u 9 s³ gi£ thi¸t r¬ng ma trªn vuæng trong biºu di¹n h m to n ph÷ìng tuy¸n t½nh l  ma trªn èi xùng. Khæng gian c¡c ma trªn vuæng èi xùng c§p n×n s³ ÷ñc k½ hiºu bði ành ngh¾a 1.3.2. n¸u F Rn×n S . Mët tªp F ⊂ Rn ÷ñc gåi l  mët tªp lçi a di»n câ thº ÷ñc biºu di¹n nh÷ l  giao cõa húu h¤n c¡c nûa khæng gian âng trong Rn ; v  c¡c sè thüc ngh¾a l  tçn t¤i c¡c v²c tì kh¡c khæng b1 , . . . , bm sao cho F = {x ∈ Rn : hai , xi ≤ bi Cho vîi i = 1, . . . , m} A l  ma trªn c§p m×n vîi c¡c ph¦n tû aij n), trong â aij a1 , . . . , a m ∈ R n l  th nh ph¦n thù i cõa ai . °t (i=1,. . . , m, (1.6) j=1,. . . , b = (β1 , . . . , βm ). Khi â (1.6) câ thº ÷ñc vi¸t nh÷ sau F = {x ∈ Rn : Ax ≤ b}. ành ngh¾a 1.3.3. B i to¡n (P) ÷ñc gåi l  b i to¡n quy ho¤ch to n f l  h m to n ph÷ìng tuy¸n Q l  ma trªn khæng th¼ f l  mët h m affine. Do vªy ph÷ìng tuy¸n t½nh (ho°c to n ph÷ìng ) n¸u t½nh v  F l  mët tªp lçi a di»n. Trong (1.5) n¸u lîp b i to¡n quy ho¤ch tuy¸n t½nh l  mët lîp con cõa lîp c¡c b i to¡n quy ho¤ch to n ph÷ìng. Nâi chung, quy ho¤ch to n ph÷ìng l  b i to¡n tèi ÷u khæng lçi. V½ dö 1.3.4. B i to¡n quy ho¤ch to n ph÷ìng sau l  b i to¡n khæng lçi: min{f (x) = x21 − x22 : x = (x1 , x2 ), 1 ≤ x1 ≤ 3, 1 ≤ x2 ≤ 3}. Sû döng ành ngh¾a h m lçi, ta câ thº kiºm tra ÷ñc lçi. Tø 1 ≤ x1 ≤ 3, 1 ≤ x2 ≤ 3 nh§t ta câ thº t¼m ÷ñc Sol(P) v  f nhä nh§t khi = {(1, 3)} 10 v  x21 f l  h m khæng nhä nh§t, v (P) = −8. x22 lîn α N¸u xâa h¬ng sè trong biºu di¹n (1.5) cõa h m khæng l m thay êi tªp nghi»m cõa b i to¡n F ⊂ Rn â f th¼ chóng ta min{f (x) : x ∈ F}, trong l  mët tªp lçi a di»n. Do â thay (1.5) chóng ta s³ th÷íng sû döng d¤ng ìn gi£n 1 f (x) = xT Qx + cT x 2 cõa h m möc ti¶u. T÷ìng tü nh÷ èi vîi b i to¡n quy ho¤ch tuy¸n t½nh chóng ta gåi c¡c b i to¡n quy ho¤ch to n ph÷ìng   1 T min x Qx + cT x : x ∈ Rn , Ax ≤ b , 2  1 T T n min x Qx + c x : x ∈ R , Ax ≤ b, x ≥ 0 ,  2 1 T x Qx + cT x : x ∈ Rn , Ax ≤ b, Cx = d min 2 t÷ìng ùng l  d¤ng chu©n, d¤ng ch½nh t­c v  d¤ng têng qu¡t. ành ngh¾a 1.3.5. Ma trªn ành ¥m, t÷ìng ùng) n¸u v ∈ Rn \ {0}. Q N¸u Q ∈ Rn×n ÷ñc gåi l  x¡c ành d÷ìng (x¡c v T Qv > 0 (v T Qv < 0, v T Qv ≥ 0 (v T Qv ≤ 0, t÷ìng ùng) vîi méi t÷ìng ùng) vîi méi v ∈ Rn th¼ ÷ñc gåi l  nûa x¡c ành d÷ìng (nûa x¡c ành ¥m, t÷ìng ùng). M»nh · 1.3.6. Cho f (x) = 21 xT Qx + cT x + α trong â Q ∈ Rn×n S , c∈ Rn v  α ∈ R. N¸u Q l  ma trªn nûa x¡c ành d÷ìng, th¼ f l  mët h m lçi. Chùng minh. V¼ x 7→ cT x + α l  h m lçi v  têng cõa hai h m lçi l  mët h m lçi n¶n º chùng minh m»nh · tr¶n ta ch¿ c¦n chùng minh r¬ng f1 (x) := xT Qx vîi méi u ∈ Rn v  l  h m lçi. Khi v ∈ Rn Q l  ma trªn nûa x¡c ành d÷ìng, ta câ 0 ≤ (u − v)T Q(u − v) = uT Qu − 2v T Qu + v T Qv. Tø i·u n y suy ra v T Qv ≤ uT Qu − 2v T Q(u − v). 11 (1.7) Vîi b§t ký x ∈ Rn , y ∈ Rn v  t ∈ (0, 1), ta °t z = tx + (1 − t)y . Chó þ tîi (1.7), chóng ta câ z T Qz ≤ y T Qy − 2z T Q(y − z), z T Qz ≤ xT Qx − 2z T Q(x − z). V¼ y − z = t(y − x) v  x − z = (1 − t)(x − y), tø hai b§t ¯ng thùc tr¶n ta suy ra (1 − t)z T Qz + tz T Qz ≤ (1 − t)y T Qy + txT Qx, do â f1 (tx + (1 − t)y) = f1 (z) ≤ tf1 (x) + (1 − t)f (y). Do â f1 N¸u Q  l  mët h m lçi. f l  nûa x¡c ành ¥m, th¼ h m cho bði (1.5) l  lãm ngh¾a l  f (tx + (1 − t)y) ≥ tf (x) + (1 − t)f (y) vîi méi x ∈ Rn , y ∈ Rn v  t ∈ (0, 1). Trong tr÷íng hñp ma trªn Q khæng gi£ thi¸t l  nûa x¡c ành d÷ìng ho°c khæng gi£ thi¸t l  ma trªn nûa x¡c ành ¥m, ta nâi r¬ng 1 f (x) = xT Qx + cT x, 2 trong â c ∈ Rn , l  mët h m to n ph÷ìng tuy¸n t½nh khæng x¡c ành. C¡c b i to¡n quy ho¤ch to n ph÷ìng vîi h m möc ti¶u to n ph÷ìng tuy¸n t½nh khæng x¡c ành ÷ñc gåi l  quy ho¤ch to n ph÷ìng khæng x¡c ành. Nhªn x²t 1.3.7. N¸u f ÷ñc cho bði (1.5), trong â thº t¼m ÷ñc ¤o h m c§p hai cõa h m Q ∈ Rn×n S , ta câ f , ∇2 f (x) = Q vîi méi x ∈ Rn . Do â M»nh · 1.3.6 l  mët h» qu£ trüc ti¸p cõa ành lþ sau (xem [9, Theorem 4.5]) "N¸u ∇2 f (x) f : Rn → R l  C 2 -h m l  nûa x¡c ành d÷ìng vîi méi v  n¸u ma trªn Hessian x ∈ Rn , th¼ f l  mët h m lçi." B¬ng c¡ch sû döng M»nh · 1.3.6 ta câ thº kiºm tra ÷ñc khi n o b i to¡n quy ho¤ch to n ph÷ìng l  b i to¡n lçi hay khæng. 12 K¸t luªn Nh¬m möc ½ch chu©n bà cho c¡c ch÷ìng k¸ ti¸p, mët sè k¸t qu£ v· gi£i t½ch lçi, b i to¡n tèi ÷u húu h¤n chi·u v  b i to¡n tèi ÷u to n ph÷ìng ÷ñc tr¼nh b y trong ch÷ìng n y. 13 Ch÷ìng 2 I—U KI›N CÜC TRÀ Ch÷ìng n y tr¼nh b y v· i·u ki»n tçn t¤i nghi»m v  i·u ki»n c¦n cüc trà bªc nh§t cõa b i to¡n quy ho¤ch to n ph÷ìng. Nëi dung cõa ch÷ìng ÷ñc tham kh£o tø c¡c t i li»u [6, 5, 4, 3, 8]. 2.1. i·u ki»n tçn t¤i nghi»m X²t b i to¡n quy ho¤ch to n ph÷ìng d¤ng chu©n trong â    Minimize   vîi i·u 1 f (x) := xT Qx + cT x 2 n ki»n x ∈ R , Ax ≤ b Q ∈ RSn×n , A ∈ Rm×n , c ∈ Rn v  b ∈ Rm . (2.1) Tªp r ng buëc v  gi¡ trà tèi ÷u cõa b i to¡n (2.1) ÷ñc k½ hi»u l¦n l÷ñt bði: F(A, b) = {x ∈ Rn : Ax ≤ b}, θ̄ = inf{f (x) : x ∈ F(A, b)}. N¸u F(A, b) = ∅ th¼ ta quy ÷îc θ̄ = +∞. N¸u F(A, b) 6= ∅ th¼ câ hai tr÷íng hñp x£y ra: (i) (ii) N¸u θ̄ ∈ R, θ̄ = −∞. (ii) x£y ra, t§t nhi¶n (2.1) khæng câ nghi»m. Mët c¥u häi tü nhi¶n ÷ñc °t ra l : Trong tr÷íng hñp (i) x£y ra, khi n o b i to¡n (2.1) luæn câ nghi»m? Chó þ r¬ng b i to¡n tèi ÷u vîi h m möc ti¶u khæng to n ph÷ìng câ thº khæng câ nghi»m thªm ch½ trong tr÷íng hñp gi¡ trà tèi ÷u húu h¤n. 14   1 Ch¯ng h¤n, b i to¡n min : x ∈ R, x ≥ 1 khæng câ nghi»m x   1 khi gi¡ trà tèi ÷u θ̄ = inf : x ∈ R, x ≥ 1 = 0 l  húu h¤n. x trong V o n«m 1956 Frank v  Wolfe ¢ cæng bè k¸t qu£ sau v  ÷ñc gåi l  ành lþ Frank-Wolfe. ành lþ 2.1.1. (xem [5, p. 108]) N¸u θ̄ = inf{f (x) : x ∈ F(A, b)} l  mët sè thüc húu h¤n th¼ b i to¡n (2.1) câ nghi»m. Chùng minh. iºm Tø gi£ thi¸t x0 ∈ F(A, b). L§y θ̄ ∈ R ρ>0 suy ra r¬ng F(A, b) 6= ∅. Chån mët l  mët sè tòy þ. °t Fρ = F(A, b) ∩ B̄(x0 , ρ). Chó þ r¬ng Fρ l  tªp kh¡c réng lçi v  comp­c. X²t b i to¡n sau min{f (x) : x ∈ Fρ }. Theo ành lþ Weierstrass, tçn t¤i y ∈ Fρ (2.2) sao cho f (y) = qρ := min{f (x) : x ∈ Fρ }. V¼ tªp nghi»m cõa b i to¡n (2.2) l  kh¡c réng v  comp­c, n¶n tçn t¤i yρ ∈ Fρ sao cho kyρ − x0 k = min{ky − x0 k : y ∈ Fρ , f (y) = qρ }. Ti¸p theo, chóng ta kh¯ng ành r¬ng tçn t¤i kyρ − x0 k < ρ vîi måi ρ̂ > 0 sao cho ρ ≥ ρ̂. (2.3) Thüc vªy, n¸u kh¯ng ành tr¶n khæng óng th¼ chóng ta câ thº t¼m ÷ñc mët d¢y ρk → +∞ sao cho vîi méi f (yρk ) = qρk , 15 k tçn t¤i kyρk − x0 k = ρk . yρk ∈ Fρk sao cho (2.4) º thuªn ti»n, chóng ta vi¸t ta ph£i câ cõa A Ai y k ≤ bi bi v  vîi yk thay cho i = 1, . . . , m, yρk . V¼ y k ∈ F(A, b), n¶n chóng trong â i k½ hi»u l  th nh ph¦n thù cõa bà ch°n tr¶n, n¶n ta câ thº chån mët d¢y tçn t¤i (nâ câ thº x£y ra tr÷íng hñp b. {A1 y k } sao cho hëi tö. T÷ìng tü, vîi lim A2 y k 0 0 mët d¢y con i = 1, v¼ d¢y i {A1 y k } lim A1 y k0 k 0 →∞ i = 2 0 k →∞ = −∞.) {k 0 } ≡ {k}, tçn t¤i mët d¢y Khæng m§t tùc l  ch½nh {k 0 } ⊂ {k} tçn t¤i. Khæng m§t t½nh têng qu¡t ta câ thº gi£ sû k →∞ {k 0 } ≡ {k}. Vîi k½ hi»u l  dáng thù {k 0 } ⊂ {k} sao cho lim A1 y k 0 t½nh têng qu¡t chóng ta câ thº gi£ sû r¬ng d¢y Ai Cù ti¸p töc qu¡ tr¼nh tr¶n cho tîi khi {k 0 } ⊂ {k} i=m ta t¼m ÷ñc sao cho t§t c£ c¡c giîi h¤n lim Ai y k 0 0 k →∞ (i = 1, . . . , m) tçn t¤i. º cho thuªn ti»n, chóng ta s³ gi£ thi¸t r¬ng I = {1, . . . , m}, I0 = {i ∈ I : lim Ai y k = bi } k→∞ {k 0 } ≡ {k}. °t v  I1 = I \ I0 = {i ∈ I : lim Ai y k < bi }. k→∞ Hiºn nhi¶n, tçn t¤i ε>0 sao cho lim Ai y k ≤ bi − ε k→∞ Tø (2.4) ta câ Rn k(y k − x0 )/ρk k = 1 vîi méi vîi méi k. i ∈ I1 . V¼ h¼nh c¦u ìn và trong l  mët tªp comp­c, n¶n khæng gi£m têng qu¡t ta câ thº gi£ thi¸t r¬ng d¢y  hëi tö tîi v̄ ∈ Rn khi k → ∞. y k − x0 ρk  Rã r ng l  16 kv̄k = 1. Khi ρk → +∞, vîi méi i ∈ I0 , ta câ 0 = lim (Ai y k − bi ) k→∞   Ai y k − bi = lim k→∞ ρk     y k − x0 A i x0 − bi = lim Ai + lim = Ai v̄. k→∞ k→∞ ρk ρk i ∈ I1 ta câ   Ai y k − bi 0 ≥ lim inf k→∞ ρk   Ai y k − Ai x0 Ai x0 − bi + = lim inf k→∞ ρ k   ρk 0   k 0 A i x − bi y −x + lim = Ai v̄. = lim Ai k→∞ k→∞ ρk ρk Mët c¡ch t÷ìng tü, vîi méi Do â Ai v̄ = 0 vîi méi i ∈ I0 , Ai v̄ ≤ 0 Tø i·u n y ta câ thº k¸t luªn ÷ñc l  a di»n v ∈ Rn F(A, b). i ∈ I1 . (2.5) l  mët h÷îng lòi xa cõa tªp lçi Nh­c l¤i r¬ng (xem [9, p. 61]) mët v²c tì kh¡c khæng ÷ñc gåi l  h÷îng lòi ra cõa tªp lçi kh¡c réng x + tv ∈ Ω vîi méi Ta công nh­c l¤i r¬ng tªp bao gçm v ∈ Rn v̄ vîi méi t≥0 0 ∈ Rn v  Ω ⊂ Rn n¸u x ∈ Ω. v  t§t c£ c¡c h÷îng lòi xa thäa m¢n i·u ki»n tr¶n ÷ñc gåi l  nân lòi xa cõa Ω. Trong tr÷íng hñp cõa chóng ta, tø (2.5) chóng ta suy ra ÷ñc y + tv̄ ∈ F(A, b) vîi méi t≥0 v  y ∈ F(A, b). V¼ f (y k ) = f (yρk ) = qρk = min{f (x) : x ∈ Fρk } = min{f (x) : x ∈ F(A, b) ∩ B̄(x0 , ρk )} 17 (2.6)