Thạc Sĩ Vai trò của tính lồi trong bài toán tối ưu

Möc löc
Líi c£m ìn . ii
Mð ƒu 1
Chưìng 1. T“p lçi v  h m lçi 3
1.1. ành ngh¾a v  t‰nh ch§t cıa t“p lçi 3
1.1.1. ành ngh¾a v  t‰nh ch§t . 3
1.1.2. C¡c ành lþ t¡ch . 6
1.2. ành ngh¾a v  t‰nh ch§t cıa h m lçi . 8
1.2.1. H m lçi . 8
1.2.2. C¡c t‰nh ch§t . 10
1.3. C¡c ành lþ cì b£n vã dưîi vi ph¥n h m lçi . 14
Chưìng 2. Vai trÆ cıa t‰nh lçi trong b i to¡n tŁi ưu 16
2.1. B i to¡n tŁi ưu lçi . 16
2.1.1. B i to¡n tŁi ưu hâa ìn möc ti¶u . 16
2.1.2. V‰ dö . 17
2.2. iãu ki»n cƒn v  ı cho b i to¡n tŁi ưu lçi . 18
2.3. Thu“t to¡n chi‚u dưîi ⁄o h m 29
2.3.1. Phưìng ph¡p chi‚u dưîi ⁄o h m . 30
2.3.2. Thu“t to¡n chi‚u dưîi ⁄o h m . 30
K‚t lu“n 35
T i li»u tham kh£o 36ii
Líi c£m ìn
Lu“n v«n n y ưæc ho n th nh t⁄i trưíng ⁄i håc Khoa håc, ⁄i
håc Th¡i Nguy¶n dưîi sü hưîng d¤n cıa GS.TSKH. L¶ Dông Mưu. Tæi
xin b y tä lÆng bi‚t ìn s¥u s›c Łi vîi thƒy vã sü t“n t¥m v  nhi»t t nh
hưîng d¤n, cung c§p t i li»u, truyãn ⁄t nhœng kinh nghi»m vã m°t
nghi¶n cøu trong suŁt qu¡ tr nh t¡c gi£ thüc hi»n lu“n v«n.
Tæi xin ch¥n th nh c£m ìn Ban Gi¡m hi»u, phÆng  o t⁄o Khoa håc,
Khoa To¡n - tin 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 cao håc khâa 2013 - 2015 ¢ quan
t¥m v  gióp ï trong suŁt thíi gian håc t“p t⁄i trưíng.
CuŁi còng, tæi xin gßi líi c£m ìn tîi gia  nh, b⁄n b–, l¢nh ⁄o trưíng
THPT Hòng An, B›c Quang, H  Giang v  c¡c b⁄n çng nghi»p ¢ gióp
ï t⁄o iãu ki»n cho tæi khi håc t“p v  nghi¶n cøu.
Tæi xin ch¥n th nh c£m ìn!
Th¡i Nguy¶n, th¡ng 06 n«m 2015
Håc vi¶n
Nguy„n L¥m H 1
Mð ƒu
Trong thíi ⁄i ng y nay, to¡n håc ng y c ng câ nhiãu øng döng ð c¡c
l¾nh vüc kh¡c nhau cıa íi sŁng x¢ hºi. °c bi»t, lþ thuy‚t vã c¡c t“p
lçi v  h m lçi câ mºt và tr‰ quan trång trong to¡n håc, li¶n quan ‚n
hƒu h‚t c¡c ng nh như gi£i t‰ch lçi, tŁi ưu hâa, gi£i t‰ch h m, h nh håc,
to¡n kinh t‚, . Mºt c¡ch tŒng qu¡t, c¡c h m lçi vîi mºt sŁ t‰nh ch§t
cì b£n ưæc sß döng rºng r¢i trong to¡n håc lþ thuy‚t công như to¡n
håc øng döng.
Trong nhiãu v§n ã øng döng ta thưíng g°p c¡c b i to¡n tŁi ưu lçi,
t‰nh ch§t b i to¡n tŁi ưu lçi, iãu ki»n cƒn v  ı cho b i to¡n tŁi ưu
lçi, công như vai trÆ cıa t‰nh lçi trong b i to¡n tŁi ưu, nhœng d⁄ng to¡n
tr¶n câ nhœng t‰nh ch§t cì b£n r§t kh¡c nhau.
Tuy nhi¶n t‰nh lçi k†o theo nhœng °c thò ri¶ng cho mØi b i to¡n.
Düa tr¶n c¡c t‰nh ch§t n y, ngưíi ta ¢ ưa ra ưæc nhœng phưìng ph¡p
gi£i quy‚t kh¡c nhau cho mØi b i to¡n.
Nh‹m möc ‰ch t m hi”u vã t‰nh lçi trong b i to¡n tŁi ưu to n di»n
v  logic hìn, tæi ¢ chån ã t i "Vai trÆ cıa t‰nh lçi trong b i to¡n tŁi
ưu" cho lu“n v«n cıa m nh.
Lu“n v«n bao gçm phƒn mð ƒu, hai chưìng nºi dung, phƒn k‚t lu“n
v  danh möc t i li»u tham kh£o.
Chưìng 1. Lu“n v«n tr nh b y c¡c ki‚n thøc cì b£n vã gi£i t‰ch lçi:
ành ngh¾a t“p lçi, h m lçi, c¡c t‰nh ch§t cıa h m lçi, dưîi vi ph¥n cıa
h m lçi, i‚u ki»n cƒn v  ı cho b i to¡n tŁi ưu lçi, b i to¡n tŁi ưu lçi
như c§u tróc t“p nghi»m, cho phưìng ph¡p chi‚u ⁄o h m v  dưîi ⁄o
h m, gi£i b i to¡n tŁi ưu lçi.
Chưìng 2. Giîi thi»u vã b i to¡n tŁi ưu lçi, iãu ki»n cƒn v  ı cho2
b i to¡n tŁi ưu lçi v  °c bi»t l  giîi thi»u thu“t to¡n chi‚u dưîi ⁄o
h m cho b i to¡n kh£ vi v  thu“t to¡n chi‚u dưîi ⁄o h m cho b i to¡n
tŁi ưu lçi khæng kh£ vi, .
Th¡i Nguy¶n, th¡ng 06 n«m 2015
Nguy„n L¥m H 
Håc vi¶n Cao håc To¡n K7A
Chuy¶n ng nh To¡n øng döng
Trưíng ⁄i håc Khoa håc - ⁄i håc Th¡i Nguy¶n
Email: [email protected]
Chưìng 1
T“p lçi v  h m lçi
Trong lu“n v«n n y, chóng ta s‡ l m vi»c vîi khæng gian Euclide n -
chiãu tr¶n trưíng sŁ thüc R , k‰ hi»u l  R
n . Chưìng 1 tr nh b y mºt sŁ
ki‚n thøc cì b£n nh§t vã t“p lçi v  h m lçi còng vîi mºt sŁ t‰nh ch§t
°c trưng cıa nâ s‡ ưæc sß döng trong lu“n v«n. Nºi dung cıa chưìng
ưæc tr‰ch d¤n chı y‚u tł t i li»u tham kh£o [1] v  [2].
1.1. ành ngh¾a v  t‰nh ch§t cıa t“p lçi
1.1.1. ành ngh¾a v  t‰nh ch§t
ành ngh¾a 1.1. Cho A ⊂ X, x 1 , x 2 ∈ A.
(i) o⁄n thflng nŁi hai i”m x 1 , x 2 câ d⁄ng
{x ∈ X : x = αx 1 + βx 2 , α, β ∈ R , α + β = 1}.
(ii) ưíng thflng i qua hai i”m x 1 , x 2 ưæc ành ngh¾a
{x ∈ R : x = αx 1 + βx 2 , α ≥ 0, β ≥ 0, α + β = 1}.
ành ngh¾a 1.2. Mºt t“p A ưæc gåi l  affine n‚u A chøa måi ưíng
thflng i qua hai i”m x 1 , x 2 b§t k thuºc A, tøc l :
∀x 1 , x 2 ∈ A, ∀λ ∈ R th λx 1 + (1 ư λ)x 2 ∈ A.
ành ngh¾a 1.3. Gi£ sß a ∈ R
n l  mºt vectì kh¡c 0 v  α ∈ R . Khi â:4
ã {x : a T x ≥ α} l  nßa khæng gian âng.
ã {x : a T x > α} l  nßa khæng gian mð.
ành ngh¾a 1.4. T“p A ⊂ X ưæc gåi l  lçi n‚u
∀x 1 , x 2 ∈ A, ∀λ ∈ R : 0 ≤ λ ≤ 1 th λx 1 + (1 ư λ)x 2 ∈ A.
V‰ dö 1.1.
(i) T“p X v  ∅ l  c¡c t“p lçi.
(ii) C¡c nßa khæng gian trong R
2 v  R
3 l  c¡c t“p lçi.
(iii) C¡c h nh trÆn trong m°t phflng, h nh cƒu ìn và trong khæng gian
Banach, h nh cƒu trong khæng gian Hillbert l  c¡c t“p lçi.
M»nh ã 1.1. T“p lçi l  âng vîi ph†p giao, ph†p cºng, ph†p nh¥n
vîi mºt sŁ thüc, tøc l , n‚u C v  D l  hai t“p lçi trong R
n th C ∩ D,
λC + βD công l  c¡c t“p lçi.
ành l‰ 1.1. Giao cıa mºt hå tòy þ c¡c t“p lçi trong R
n l  mºt t“p lçi
trong R
n .
Chøng minh. Gi£ sß A α ∈ R
n (α ∈ I) l  c¡c t“p lçi vîi I l  t“p ch¿ sŁ
b§t k , ta cƒn chøng minh t“p A = ∩ α∈I A α l  lçi.
L§y tòy þ x 1 , x 2 ∈ A. Khi â, x 1 , x 2 ∈ A α , vîi ∀α ∈ I. Do A α l  lçi
cho n¶n λx 1 + (1 ư λ)x 2 ∈ A α vîi ∀λ ∈ [0, 1] → λx 1 + (1 ư λ)x 2 ∈ A.
V v“y, A l  t“p lçi.
ành l‰ 1.2. Gi£ sß A i ⊂ R
n lçi; λ i ∈ R (i = 1, 2, . , m). Khi â,
λ 1 A 1 + λ 2 A 2 + . + λ m A m l  lçi.
ành ngh¾a 1.5. Vectì x ∈ R
n ưæc gåi l  tŒ hæp lçi cıa c¡c vectì
x 1 , x 2 , . , x m ∈ R
n n‚u
∃λ i ≥ 0, i = 1, 2, . , m,
m
X
i=1
λ i = 1 : x =
m
X
i=1
λ i x i .5
ành l‰ 1.3. T“p A ⊂ R
n l  lçi khi v  ch¿ khi nâ chøa måi tŒ hæp lçi
cıa c¡c vectì cıa nâ, tøc l  A ⊂ R
n lçi khi v  ch¿ khi
∀m ∈ N , ∀λ 1 , . , λ m ≥ 0 :
m
X
i=1
λ i = 1, ∀x 1 , . , x m ∈ A →
m
X
i=1
λ i x i ∈ A.
Chøng minh. Chån m = 2, hi”n nhi”n óng.
Ta chøng minh quy n⁄p. Gi£ sß A l  t“p lçi, ta l§y tòy þ x 1 , . , x m ∈
A; λ 1 , . , λ m ≥ 0 v 
m
P
i=1
λ i = 1; x =
m
P
i=1
. Ta chøng minh x ∈ A.
m = 1 : x 1 ∈ A; λ 1 = 1 → x ∈ A.
m = 2 : x 1 , x 2 ∈ A; λ 1 + λ 2 = 1 m  A lçi suy ra x = λ 1 x 1 + λ 2 x 2 ∈ A.
Gi£ sß x ∈ A óng vîi m ư 1, ta câ
m
X
i=1
λ i x i ∈ A; ∀x i ∈ A;
m
X
i=1
λ i = 1; λ i ≥ 0; i ∈ N .
X†t x =
m
P
i=1
λ i x i =
mư1
P
i=1
λ i x i + λ m x m .
Vîi λ m = 0 → x ∈ A.
Vîi λ m = 1 → λ 1 = . = λ mư1 = 0 → x = x m ∈ A.
Vîi 0 < λ < 1, ta câ:
1 ư λ m = λ 1 + . + λ mư1 > 0,
λ i
1 ư λ m
≥ 0(i = 1, . , m ư 1).
V
mư1
P
i=1
λ i
1 ư λ m
= 1 n¶n theo gi£ thi‚t quy n⁄p y =
mư1
P
i=1
x i ∈ A. Vîi
y ∈ A v  x m ∈ A, ta câ
1 ư λ m > 0 v  (1 ư λ m ) + λ m = 1 → x = (1 ư λ m )y + λ m x m ∈ A.
ành ngh¾a 1.6. Chiãu cıa mºt t“p lçi A ưæc cho bði chiãu cıa a
t⁄p affine nhä nh§t chøa A (khæng gian con song song vîi A), ưæc k‰
hi»u l  dimA. a t⁄p affine n y ưæc gåi l  bao affine cıa A, ưæc k‰
hi»u affA.6
ành ngh¾a 1.7. i”m x 0 cıa t“p lçi A ⊂ R
n ưæc gåi l  i”m trong
tưìng Łi cıa A n‚u vîi måi x ∈ affA câ mºt sŁ λ > 0 sao cho
x 0 + λ(x ư x 0 ) ∈ A. Phƒn trong tưìng Łi cıa A l  t“p c¡c i”m trong
tưìng Łi cıa A, ưæc k‰ hi»u riA.
ành ngh¾a 1.8. T“p A ⊂ R
n ưæc gåi l  nân n‚u:
∀a ∈ A, ∀λ > 0 th λx ∈ A.
Nân A ưæc gåi l  nân nhån n‚u nâ khæng chøa ưíng thflng. Nân A
ưæc gåi l  nân lçi n‚u A l  t“p lçi. N‚u A l  mºt t“p lçi a di»n th ta
nâi nân sinh bði A l  nân lçi a di»n.
Mºt v‰ dö quan trång vã nân lçi trong R
n l  nân orthant dưìng
R
n
+
= {(x 1 , x 2 , . , x n ) : x i ≥ 0, i = 1, 2, . , n}.
ành ngh¾a 1.9. Gi£ sß A ⊆ R
n l  t“p lçi v  x 0 ∈ A. T“p
N A (x
0
) = {x
∗
∈ R
n
: hx
∗
, x ư x
0 i ≤ 0, ∀x ∈ A},
ưæc gåi l  nân ph¡p tuy‚n cıa A t⁄i x 0 .
Hi”n nhi¶n, 0 ∈ N A (x 0 ) n¶n ta câ N A (x 0 ) l  nân lçi âng.
1.1.2. C¡c ành lþ t¡ch
C¡c ành lþ t¡ch t“p lçi l  mºt trong nhœng nºi dung cì b£n v  quan
trång nh§t cıa gi£i t‰ch lçi.
ành ngh¾a 1.10. Si¶u phflng trong khæng gian R
n l  t“p t§t c£ c¡c
i”m câ d⁄ng
{x ∈ R
n
: a
T
x = α},
trong â, a ∈ R
n l  vectì kh¡c 0 v  α ∈ R .
ành ngh¾a 1.11. T“p câ d⁄ng
{x ∈ R
n
: ha, xi ≥ α},
ưæc gåi l  nßa khæng gian âng, trong â a 6= 0 v  α ∈ R .7
T“p
{x ∈ R
n
: ha, xi > α},
ưæc gåi l  nßa khæng gian mð.
Mºt si¶u phflng s‡ chia khæng gian ra l m hai nßa khæng gian, mØi
nßa khæng gian ð vã mºt ph‰a cıa si¶u phflng. Si¶u phflng l  phƒn chung
cıa hai nßa khæng gian n‚u hai nßa khæng gian n y l  âng.
ành ngh¾a 1.12. Cho hai t“p S v  T kh¡c rØng. Ta nâi si¶u phflng
ht, xi = α
(i) t¡ch S v  T n‚u
ht, xi ≤ α ≤ ht, yi, ∀x ∈ S, ∀y ∈ T.
(ii) t¡ch ch°t S v  T n‚u
ht, xi < α < ht, yi, ∀x ∈ S, ∀y ∈ T.
(iii) t¡ch m⁄nh S v  T n‚u
sup
x∈S
ht, xi < α < inf
y∈T
ht, yi, ∀x ∈ S, ∀y ∈ T.
ành l‰ 1.4. (ành lþ t¡ch 1). Cho S v  T l  hai t“p lçi kh¡c rØng trong
R
n sao cho S ∩ T = ∅. Khi â, ta câ mºt si¶u phflng t¡ch S v  T.
ành l‰ 1.5. (ành lþ t¡ch 2). Cho S v  T l  hai t“p lçi âng kh¡c rØng
sao cho S ∩ T = ∅. Gi£ sß câ ‰t nh§t mºt t“p compact. Khi â, hai t“p
n y câ th” t¡ch m⁄nh bði mºt si¶u phflng.
Chó þ 1.1. N‚u gi£ thi‚t "mºt trong hai t“p l  compact" khæng thäa
m¢n th ành lþ 1.5 khæng cÆn óng.
V‰ dö 1.2. S = {(x, y) ∈ R
2 | xy ≥ 1} v  T = {(x, y) ∈ R
2 | y ≤ 0} l 
hai t“p âng, ríi nhau nhưng khæng t¡ch m⁄nh.
H» qu£ 1.1. (BŒ ã Farkas) Cho a ∈ R
n v  A l  ma tr“n c§p m × n.
Khi â ha, xi ≥ 0 vîi måi x thäa m¢n Ax ≥ 0 khi v  ch¿ khi tçn t⁄i
y ≥ 0 thuºc R
m sao cho a = A T y.