BË GIO DÖC V O TO
TR×ÍNG I HÅC S× PHM H NËI 2
NGUYN L QU
N
IU KIN TÈI ×U TON CÖC
TRONG QUY HOCH TON PH×ÌNG
LUN VN THC S TON HÅC
H Nëi - 2018
BË GIO DÖC V O TO
TR×ÍNG I HÅC S× PHM H NËI 2
NGUYN L QU
N
IU KIN TÈI ×U TON CÖC
TRONG QUY HOCH TON PH×ÌNG
Chuy¶n ng nh: To¡n gi£i t½ch
M¢ sè: 8 46 01 02
LUN VN THC S TON HÅC
Ng÷íi h÷îng d¨n khoa håc:
PGS. TS. Nguy¹n N«ng T¥m
H Nëi - 2018
LÍI CM ÌN
Luªn v«n ÷ñc ho n th nh t¤i tr÷íng ¤i håc S÷ ph¤m H Nëi 2, d÷îi
sü h÷îng d¨n cõa PGS. TS. Nguy¹n N«ng T¥m. Em xin b y tä láng bi¸t
ìn s¥u sc tîi Th¦y, ng÷íi ¢ tªn t¼nh h÷îng d¨n v gióp ï em trong
suèt qu¡ tr¼nh nghi¶n cùu º em câ thº ho n th nh luªn v«n n y.
Em công b y tä láng bi¸t ìn ch¥n th nh tîi quþ th¦y, cæ gi¡o tr÷íng
¤i håc S÷ ph¤m H Nëi 2 ¢ gi£ng d¤y v gióp ï em ho n th nh khâa
håc. Nh¥n dàp n y em công xin ch¥n th nh c£m ìn Ban gi¡m hi»u, çng
nghi»p Tr÷íng THPT Hçng Th¡i - Huy»n an Ph÷ñng - H Nëi, gia ¼nh
v b¤n b± ¢ luæn ëng vi¶n, gióp ï v t¤o i·u ki»n cho em v· måi m°t
trong suèt qu¡ tr¼nh håc tªp v thüc hi»n luªn v«n n y.
H Nëi, ng y 28 th¡ng 07 n«m 2018
Nguy¹n L¶ Qu¥n
1
LÍI CAM OAN
Tæi xin cam oan, d÷îi sü h÷îng d¨n cõa PGS. TS. Nguy¹n N«ng T¥m,
luªn v«n Chuy¶n ng nh To¡n gi£i t½ch vîi · t i:
cöc trong quy ho¤ch to n ph÷ìng do tæi tü l m.
i·u ki»n tèi ÷u to n
Trong qu¡ tr¼nh nghi¶n cùu v thüc hi»n luªn v«n, tæi ¢ k¸ thøa nhúng
th nh qu£ cõa c¡c nh khoa håc vîi sü tr¥n trång v bi¸t ìn.
C¡c k¸t qu£ tr½ch d¨n trong luªn v«n l trung thüc v ÷ñc ch¿ rã nguçn
gèc.
H Nëi, ng y 28 th¡ng 07 n«m 2018
Nguy¹n L¶ Qu¥n
2
Möc löc
LÍI CM ÌN
LÍI CAM OAN
LÍI MÐ U
1 KIN THÙC CHUN BÀ
1
2
4
6
1.1
Mët sè nëi dung cì b£n cõa gi£i t½ch lçi . . . . . . . . . . .
6
1.2
B i to¡n tèi ÷u . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3
C¡c i·u ki»n õ cho cüc tiºu to n cöc v °c tr÷ng nh¥n
tû Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 IU KIN TÈI ×U TON CÖC TRONG QUY HOCH
TON PH×ÌNG
19
2.1
Tèi ÷u to n ph÷ìng vîi c¡c r ng buëc to n ph÷ìng . . . . . 19
2.2
°c tr÷ng cõa Bê · S v ch½nh quy hâa khæng i·u ki»n
Slater . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3
i·u ki»n c¦n v õ cho tèi ÷u to n cöc . . . . . . . . . . . 37
KT LUN
T i li»u tham kh£o
42
43
3
LÍI MÐ U
Tèi ÷u to n ph÷ìng l mët bë phªn cõa quy ho¤ch to¡n håc câ nhi·u
ùng döng trong lþ thuy¸t công nh÷ trong íi sèng thüc t¸. Vi»c nghi¶n
cùu c¡c t½nh ch§t ành t½nh công nh÷ c¡c thuªt to¡n gi£i húu hi»u c¡c b i
quy ho¤ch to n ph÷ìng l mët chõ · ¢ v ang ÷ñc nhi·u t¡c gi£ trong
v ngo i n÷îc quan t¥m. V¼ vªy, sau khi ÷ñc håc v nghi¶n cùu nhúng
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· nhúng
ki¸n thùc ¢ håc v ùng döng cõa chóng, tæi ¢ chån · t i nghi¶n cùu :
i·u ki»n tèi ÷u to n cöc trong quy ho¤ch to n ph÷ìng .
Luªn v«n n y nghi¶n cùu v· c¡c i·u ki»n tèi ÷u to n cöc cõa nhúng
lîp b i to¡n trong quy ho¤ch to n ph÷ìng. Qua â th§y ÷ñc t¦m quan
trång cõa nhúng ki¸n thùc ¢ håc v c¡c ùng döng cõa chóng. Vîi nëi dung
nghi¶n cùu n y, ngo i ph¦n líi mð ¦u, k¸t luªn v t i li»u tham kh£o, luªn
v«n ÷ñc chia th nh hai ch÷ìng. K¸t qu£ ch½nh tªp trung trong Ch÷ìng
2. Cö thº nh÷ sau:
Ch÷ìng 1. Ki¸n thùc chu©n bà. Trong ch÷ìng n y, luªn v«n ph¦n
¦u tr¼nh b y nhúng ki¸n thùc c¦n thi¸t v· gi£i t½ch lçi v lþ thuy¸t tèi
÷u º sû döng cho ch÷ìng ti¸p theo nh÷ tªp lçi, h m lçi, d÷îi vi ph¥n,
vv. . . Sau â, luªn v«n tr¼nh b y v· b i to¡n tèi ÷u còng vîi c¡c kh¡i ni»m
v· iºm ch§p nhªn ÷ñc, cüc tiºu àa ph÷ìng, cüc tiºu to n cöc.
Ch÷ìng 2. i·u ki»n tèi ÷u to n cöc trong quy ho¤ch to n
ph÷ìng. Trong ch÷ìng n y, tr÷îc ti¶n, luªn v«n s³ tr¼nh b y v· tèi ÷u
to n ph÷ìng vîi c¡c r ng buëc to n ph÷ìng. Qua â, thu ÷ñc c¡c i·u
ki»n õ công nh÷ i·u ki»n c¦n v õ cho c¡c cüc tiºu to n cöc. Ti¸p â,
luªn v«n tr¼nh b y c¡c °c tr÷ng cõa Bê · S v èi ng¨u Lagrange cho
4
tèi ÷u to n ph÷ìng tr¶n mët r ng buëc to n ph÷ìng thæng qua i·u ki»n
Slater. V sau â l ch½nh quy hâa Bê · S khæng i·u ki»n Slater. Cuèi
ch÷ìng, luªn v«n tr¼nh b y c¡c i·u ki»n c¦n v õ cho tèi ÷u to n cöc
trong quy ho¤ch to n ph÷ìng.
5
Ch֓ng 1
KIN THÙC CHUN BÀ
Trong ch÷ìng n y, luªn v«n s³ tr¼nh b y mët sè kh¡i ni»m, ành ngh¾a
v c¡c k¸t qu£ c¦n thi¸t v· gi£i t½ch lçi v lþ thuy¸t tèi ÷u nh¬m phöc vö
cho Ch÷ìng 2. T i li»u tham kh£o ch½nh cõa ch÷ìng n y l [1], [15], [16],
[18] v [26].
1.1 Mët sè nëi dung cì b£n cõa gi£i t½ch lçi
Trong to n bë luªn v«n, ta kþ hi»u Rn l khæng gian Euclide n-chi·u
tr¶n tr÷íng sè thüc R. Méi v²c tì x ∈ Rn s³ gçm n tåa ë l c¡c sè thüc.
Vîi hai v²c tì x = (x1 , . . . , xn )T v y = (y1 , . . . , yn )T thuëc Rn , ta nhc
l¤i r¬ng
hx, yi :=
n
X
xi yi
i=1
gåi l
t½ch væ h÷îng cõa hai v²c tì x v y. Chu©n Euclide cõa ph¦n tû x
÷ñc ành ngh¾a nh÷ sau:
kxk :=
q
hx, xi.
Kþ hi»u Rn+ l tªp t§t c£ c¡c v²c tì khæng ¥m cõa Rn . Vîi c¡c v²c tì
x, y ∈ Rn , x ≥ y ÷ñc hiºu l xi ≥ yi , vîi i = 1, . . . , n. Ma trªn ìn và
(n × n) ÷ñc kþ hi»u l In v A 0 câ ngh¾a l ma trªn A l nûa x¡c
ành d÷ìng.
Ma trªn ch²o vîi c¡c ph¦n tû ÷íng ch²o α1, . . . , αn ÷ñc kþ
hi»u bði diag(α1 , . . . , αn ).
Khæng gian cõa t§t c£ c¡c ma trªn èi xùng (n × n) ÷ñc kþ hi»u l
S n . Khi vi¸t A B v A B t÷ìng ùng ÷ñc hiºu l ma trªn A − B
6
l nûa x¡c ành d÷ìng v x¡c ành d÷ìng.
Nân nûa x¡c ành d÷ìng ÷ñc
ành ngh¾a bði
S+n := {M ∈ S n : M 0}.
T½ch trong (v¸t) cõa A v B ÷ñc ành ngh¾a bði
A · B = Tr[AB] =
n X
n
X
aij bji ,
i=1 j=1
trong â aij l ph¦n tû (i, j) cõa A v bji l ph¦n tû (j, i) cõa B .
Cho K l mët nân trong S n .
Chu©n cõa A ∈ S n v kho£ng c¡ch tø A
¸n nân K ÷ñc ành ngh¾a l¦n l÷ñt l kAk = (A · A)1/2 v
d(A, K) = inf kA − Bk.
B∈K
Nh¥n (kernel ) cõa mët ma trªn A ∈ S n ÷ñc ành ngh¾a bði
KerA := {x ∈ Rn : Ax = 0}.
bao âng cõa D ÷ñc kþ hi»u l D. Mët tªp
mët nân n¸u λK ⊆ K vîi måi λ ≥ 0. Cüc ¥m
Vîi mët tªp con D ⊂ Rn ,
K ⊂ Rn ÷ñc gåi l
(negative
polar ) cõa K kþ hi»u l
K ◦ := {d : dT x ≤ 0 ∀x ∈ K}.
Vîi c¡c nân K1 , K2 ∈ Rn , cæng thùc cüc ([16]) sau ÷ñc thäa m¢n:
(K1◦ ∩ K2◦ )◦ = K1 + K2 .
n
°c bi»t, khi K1 = −S+
v K2 =
S
t≥0 tH2 ,
trong â H2 l ma trªn n o
â trong S n , ta thu ÷ñc:
{X ∈ S+n : H2 · X ≤ 0}◦ = (K1◦ ∩ K2◦ )◦
= K1 + K2
[
= −S+n +
tH2 .
t≥0
7
(1.1)
Mët ÷íng th¯ng nèi hai iºm (hai v²c tì) a, b trong Rn l tªp hñp t§t
c£ c¡c v²c tì x ∈ Rn câ d¤ng
{x ∈ Rn : x = αa + βb, α, β ∈ R, α + β = 1}.
o¤n th¯ng nèi hai iºm a, b trong Rn l tªp hñp t§t c£ c¡c v²c tì x ∈ Rn
câ d¤ng
{x ∈ Rn : x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}.
ành ngh¾a 1.1.1
Mët tªp C ⊆ Rn ÷ñc gåi l mët
tªp lçi ([1]), n¸u C
chùa måi o¤n th¯ng i qua hai iºm b§t ký cõa nâ. Nâi kh¡c i, tªp C
l lçi n¸u v ch¿ n¸u
∀x, y ∈ C, ∀λ ∈ [0, 1] =⇒ λx + (1 − λ)y ∈ C.
ành ngh¾a 1.1.2
([16])
Cho h : Rn −→ R ∪ {−∞, +∞}.
(i)
dom h := {x ∈ Rn | h(x) < +∞} l
(ii)
H m h ÷ñc gåi l
mi·n húu döng cõa h;
ch½nh th÷íng n¸u h khæng l§y tr¶n gi¡ trà −∞
v dom h 6= ∅;
(iii)
Tr¶n ç thà (epigraph) cõa h ÷ñc ành ngh¾a nh÷ sau:
epi h := {(x, r) ∈ Rn × R | x ∈ dom h, h(x) ≤ r};
(iv)
H m li¶n hñp (conjugate function) cõa h, h∗ : Rn −→ R ∪ {+∞},
÷ñc ành ngh¾a bði
h∗ (v) := sup{v(x) − h(x) | x ∈ dom h},
trong â v(x) := v T x.
ành ngh¾a 1.1.3
([1])
Cho C ⊆ Rn l mët tªp lçi, kh¡c réng v ¡nh
x¤ h : C −→ R. N¸u epi h l mët tªp lçi trong Rn+1 , th¼ ta nâi h l mët
h m lçi tr¶n C .
8
Trong tr÷íng hñp ta l m vi»c vîi h m h : Rn −→ R ∪ {+∞}, th¼ ành
ngh¾a tr¶n t÷ìng ÷ìng vîi h l h m lçi tr¶n C n¸u v ch¿ n¸u
h(λx + (1 − λ)y) ≤ λh(x) + (1 − λ)h(y) ∀x, y ∈ C, ∀λ ∈ [0, 1].
V½ dö 1.1.4
(1)
C¡c v½ dö v· h m lçi.
H m kho£ng c¡ch ¸n tªp lçi âng C ÷ñc ành ngh¾a bði
dC (x) := min kx − yk,
y∈C
l mët h m lçi.
(2)
Gåi C 6= ∅ l mët tªp lçi. N¸u °t
(
0
khi x ∈ C,
h(x) :=
+∞ khi x 6= C,
th¼ h l mët h m lçi. H m n y cán ÷ñc gåi l
h m ch¿
v th֒ng ֖c
kþ hi»u l δC (x).
ành ngh¾a 1.1.5
([16])
Cho h : Rn −→ R l mët h m lçi li¶n töc,
d÷îi vi ph¥n cõa h t¤i x ∈ Rn ÷ñc ành ngh¾a bði
∂h(x) = {a ∈ Rn : aT (y − x) ≤ h(y) − h(x) ∀y ∈ Rn }.
Vîi ε ≥ 0, ε-d÷îi
(1.2)
vi ph¥n (ε- subdifferential ) cõa h t¤i x ∈ Rn ÷ñc ành
ngh¾a nh÷ sau:
∂ε h(x) = {a ∈ Rn : aT (y − x) ≤ h(y) − h(x) + ε ∀y ∈ Rn }.
(1.3)
Ta câ thº th§y r¬ng ∂h(x) ⊆ ∂ε h(x) vîi måi ε > 0 v ∂h(x) = {∇h(x)}
n¸u h l mët h m lçi kh£ vi li¶n töc.
Cho h : Rn −→ R, ta kþ hi»u
[h ≤ 0] := {x ∈ Rn | h(x) ≤ 0}.
Nân ph¡p tuy¸n cõa [h ≤ 0] t¤i iºm x ∈ [h ≤ 0] l
N[h≤0] (x) := {a ∈ Rn : aT (z − x) ≤ 0, ∀z ∈ [h ≤ 0]}.
9
N¸u h l mët h m lçi kh£ vi li¶n töc tr¶n Rn , th¼ vîi méi x ∈ [h ≤ 0], ta
câ
)
(
N[h≤0] (x) =
a ∈ Rn : (a, aT x) ∈
[
(1.4)
epi (λh)∗
λ≥0
v
)
(
[
{λ∇h(x)} =
a ∈ Rn : (a, aT x) ∈
S
epi (λh)∗ .
(1.5)
λ≥0
λ≥0,λh(x)=0
Do â, n¸u
[
λ≥0 epi
(λh)∗ l âng, th¼
[
N[h≤0] (x) =
{λ∇h(x)}
(1.6)
λ≥0,λh(x)=0
vîi méi x ∈ [h ≤ 0].
Cho f l mët
h m to n ph÷ìng (quadratic function) ÷ñc ành ngh¾a
bði
f (x) = xT Ax + aT x + α,
trong â A ∈ S n , a ∈ Rn v α ∈ R. ành ngh¾a Hf bði
!
Hf =
Nhªn x²t 1.1.6
A
a/2
aT /2
α
.
(1.7)
n+1
Vîi måi x ∈ Rn , f (x) ≥ 0 n¸u v ch¿ n¸u Hf ∈ S+
.
Hai k¸t luªn sau ¥y (xem [16], Bê · 2.1 v Bê · 2.2) câ vai trá
quan trång trong ành lþ v· ch½nh quy hâa Bê · S m ta s³ · cªp trong
Ch֓ng 2.
Bê · 1.1.7 N¸u f, g : Rn −→ R (n ≥ 3) l c¡c h m to n ph÷ìng thu¦n
nh§t, ÷ñc ành ngh¾a bði
f (x) = xT Ax v g(x) = xT Bx,
trong â A, B ∈ S n, th¼
V := {(f (x), g(x)) | kxk = 1} ⊂ R2
10
l mët tªp compact lçi.
Bê · 1.1.8 ([16], Bê · 2.2 ) Cho A, B l hai ma trªn èi xùng thüc
cï 2 × 2. ành ngh¾a K = {(xT Ax, xT Bx) : x ∈ R2}. Khi â,
K = {(A · X, B · X) : X ∈ S+2 }
v K l mët tªp lçi.
1.2 B i to¡n tèi ÷u
B i to¡n tèi ÷u r ng buëc phi tuy¸n ([26]) câ d¤ng têng qu¡t nh÷ sau:
min
x∈Rn
sao cho
f (x)
(1.8)
gi (x) = 0, i = 1, . . . , me ;
(1.9)
gi (x) ≥ 0, i = me + 1, · · · , m,
(1.10)
trong â, h m möc ti¶u f (x) v c¡c h m r ng buëc gi (x) (vîi i = 1, . . . , m)
·u trìn, l c¡c h m thüc tr¶n Rn v ½t nh§t mët trong sè â l h m phi
tuy¸n; me v m l c¡c sè nguy¶n khæng ¥m vîi 0 ≤ me ≤ m. Ta gåi
E = {1, . . . , me } v I = {me + 1, · · · , m}
l¦n l÷ñt l tªp ch¿ sè cõa c¡c r ng buëc ph÷ìng tr¼nh v c¡c r ng buëc b§t
ph÷ìng tr¼nh.
-
N¸u khæng câ hai i·u ki»n (1.9) v (1.10) th¼ b i to¡n (1.8)-(1.10)
l mët
-
-
b i to¡n tèi ÷u khæng r ng buëc ;
N¸u me = m 6= 0 th¼ b i to¡n (1.8)-(1.10) ÷ñc gåi l mët
tèi ÷u r ng buëc ph÷ìng tr¼nh ;
b i to¡n
N¸u t§t c£ c¡c h m gi (x) (vîi i = 1, . . . , m) l tuy¸n t½nh, th¼
b i to¡n (1.8)-(1.10) ÷ñc gåi l mët
b i to¡n tèi ÷u r ng buëc tuy¸n
t½nh. Mët b i to¡n tèi ÷u r ng buëc tuy¸n t½nh vîi h m möc ti¶u to n
ph÷ìng f (x) ÷ñc gåi l mët b i to¡n quy ho¤ch to n ph÷ìng.
11
ành ngh¾a 1.2.1
iºm x ∈ Rn ÷ñc gåi l mët
iºm ch§p nhªn ÷ñc
n¸u v ch¿ n¸u (1.9)-(1.10) thäa m¢n. Tªp t§t c£ c¡c iºm ch§p nhªn ÷ñc
÷ñc gåi l mët
tªp ch§p nhªn ÷ñc.
Trong b i to¡n (1.8)-(1.10), c¡c i·u ki»n (1.9)-(1.10) ÷ñc gåi l c¡c
i·u ki»n r ng buëc. Tø ành ngh¾a 1.2.1, iºm ch§p nhªn ÷ñc l iºm
thäa m¢n t§t c£ c¡c r ng buëc. Ta vi¸t tªp ch§p nhªn ÷ñc X nh÷ sau:
(
)
g (x) = 0, i = 1, . . . , m ;
e
i
X = x ∈ Rn
(1.11)
gi (x) ≥ 0, i = me + 1, . . . , m
hay
X = {x ∈ Rn | gi (x) = 0, i ∈ E; gi (x) ≥ 0, i ∈ I}.
(1.12)
Do â, b i to¡n (1.8)-(1.10) câ thº ÷ñc vi¸t l¤i nh÷ sau
minf (x).
x∈X
(1.13)
i·u n y câ ngh¾a l vi»c t¼m nghi»m cõa b i to¡n tèi ÷u r ng buëc (1.8)(1.10) quy v· vi»c t¼m mët iºm x tr¶n tªp ch§p nhªn ÷ñc X sao cho
h m möc ti¶u f (x) ¤t cüc tiºu.
Sau ¥y, ta s³ ành ngh¾a v·
ành ngh¾a 1.2.2
cüc tiºu àa ph÷ìng v cüc tiºu to n cöc.
N¸u x∗ ∈ X v
f (x) ≥ f (x∗ ),
th¼ x∗ ÷ñc gåi l
∀x ∈ X,
(1.14)
cüc tiºu to n cöc (global minimizer ) ([26]) cõa b i to¡n
(1.8)-(1.10). N¸u x∗ ∈ X v
f (x) > f (x∗ ),
th¼ x∗ ÷ñc gåi l
∀x ∈ X, x 6= x∗ ,
(1.15)
cüc tiºu to n cöc ng°t (strict global minimizer ).
ành ngh¾a 1.2.3
N¸u x∗ ∈ X v n¸u tçn t¤i mët l¥n cªn B(x∗ , δ) cõa
x∗ sao cho
f (x) ≥ f (x∗ ),
∀x ∈ X ∩ B(x∗ , δ),
12
(1.16)
th¼ x∗ ÷ñc gåi l cüc
tiºu àa ph÷ìng (local minimizer ) ([26]) cõa b i to¡n
(1.8)-(1.10), trong â
B(x∗ , δ) = {x : kx − x∗ k2 ≤ δ}
(1.17)
v δ > 0.
N¸u x∗ ∈ X v n¸u tçn t¤i mët l¥n cªn B(x∗ , δ) cõa x∗ sao cho
f (x) > f (x∗ ),
th¼ x∗ ÷ñc gåi l
∀x ∈ X ∩ B(x∗ , δ), x 6= x∗ ,
(1.18)
cüc tiºu àa ph÷ìng ng°t (strict local minimizer ).
ành ngh¾a 1.2.4
N¸u x∗ ∈ X v n¸u tçn t¤i mët l¥n cªn B(x∗ , δ) cõa
x∗ sao cho x∗ ch¿ l cüc tiºu àa ph÷ìng tr¶n X ∩ B(x∗ , δ), th¼ x∗ ÷ñc gåi
l mët
cüc tiºu àa ph÷ìng cæ lªp.
Gi£ sû r¬ng x∗ l mët cüc tiºu àa ph÷ìng cõa b i to¡n (1.8)-(1.10).
N¸u tçn t¤i mët ch¿ sè i0 ∈ I = [me + 1, m] sao cho
gi0 (x∗ ) > 0,
(1.19)
khi â, n¸u ta xâa r ng buëc thù i0 th¼ x∗ v¨n l cüc tiºu àa ph÷ìng cõa
b i to¡n thu ÷ñc b¬ng c¡ch xâa r ng buëc thù i0 . Do â, ta nâi r¬ng r ng
buëc thù i0 l
khæng ho¤t (inactive ) t¤i x∗.
B¥y gií, ta s³ ÷a ra c¡c ành ngh¾a v· r ng buëc ho¤t v r ng buëc
khæng ho¤t. Tr÷îc h¸t, ta °t
I(x) = {i | gi (x) = 0, i ∈ I}.
ành ngh¾a 1.2.5
([26])
(1.20)
Vîi méi x ∈ Rn , tªp
A(x) = E ∪ I(x)
(1.21)
tªp ch¿ sè ho¤t c¡c r ng buëc (index set of active constraints ) t¤i x;
gi (x)(i ∈ A(x)) l mët r ng buëc ho¤t (active constraint ) t¤i x; gi (x)(i ∈
/
A) l mët r ng buëc khæng ho¤t (inactive constraint ) t¤i x.
l mët
13
Gi£ sû r¬ng A(x∗ ) l mët tªp ch¿ sè ho¤t c¡c r ng buëc cõa b i to¡n
(1.8)-(1.10) t¤i x∗ , khi â, d÷îi c¡ch nh¼n v· c¡c r ng buëc khæng ho¤t,
õ º cho ta câ thº gi£i b i to¡n tèi ÷u r ng buëc
(1.22)
min f (x)
sao cho
gi (x) = 0, i ∈ A(x∗ ).
(1.23)
Vi»c gi£i b i to¡n r ng buëc ph÷ìng tr¼nh (1.22), th÷íng th¼ d¹ hìn so vîi
b i to¡n gèc (1.8)-(1.10).
1.3 C¡c i·u ki»n õ cho cüc tiºu to n cöc v °c
tr÷ng nh¥n tû Lagrange
Trong möc n y, luªn v«n tr¼nh b y c¡c k¸t qu£ v· tèi ÷u to n cöc v
c¡c nh¥n tû Lagrange cho c¡c b i to¡n tèi ÷u r ng buëc khæng lçi. Ta s³
bt ¦u vîi mët sè ành ngh¾a cì b£n v chó þ quan trång m s³ ÷ñc sû
döng cho ch÷ìng sau.
ành ngh¾a 1.3.1 ([18], [23])(L-d÷îi vi ph¥n )
Cho L l mët tªp c¡c
h m gi¡ trà thüc l : Rn −→ R v f : Rn −→ R. Mët ph¦n tû l ∈ L ÷ñc
gåi l mët L-d÷îi
gradient cõa f t¤i mët iºm x0 ∈ Rn n¸u
f (x) ≥ f (x0 ) + l(x) − l(x0 ), ∀x ∈ Rn .
Tªp ∂L f (x0 ) cõa t§t c£ c¡c L-d÷îi gradient cõa f t¤i x0 ÷ñc gåi l L-d÷îi
vi ph¥n (L-subdifferential ) cõa f t¤i x0.
Chó þ r¬ng, n¸u L ÷ñc chån nh÷ l tªp t§t c£ c¡c h m tuy¸n t½nh
÷ñc ành ngh¾a tr¶n Rn , th¼ khi â vîi måi h m lçi mang gi¡ trà thüc f
÷ñc ành ngh¾a tr¶n Rn , ta câ ∂L f (x) = ∂f (x), trong â ∂f (x) l d÷îi
vi ph¥n theo ngh¾a gi£i t½ch lçi ([11]).
X²t b i to¡n tèi ÷u r ng buëc b§t ph÷ìng tr¼nh:
min
x∈Rn
sao cho
(P)
f (x)
gi (x) ≤ 0, i = 1, · · · , m,
14
trong â f, gi : Rn −→ R, i = 1, · · · , m. Tªp ch§p nhªn ÷ñc cõa (P )
÷ñc kþ hi»u bði
S := {x ∈ Rn | gi (x) ≤ 0, i = 1, · · · , m}.
(1.24)
M»nh · 1.3.2 (C¡c i·u ki»n õ cho cüc tiºu to n cöc )
Gi£ sû L l mët tªp c¡c h m mang gi¡ trà thüc ÷ñc ành ngh¾a tr¶n Rn
sao cho −l ∈ L vîi l ∈ L. Trong b i to¡n (P ), cho x ∈ S. Gi£ sû r¬ng
(∃λ ∈
Rm
+)
0 ∈ ∂L f (x) + ∂L
m
X
!
λi gi (x)
v
m
X
λi gi (x) = 0.
i=1
i=1
(1.25)
Khi â, x l mët cüc tiºu to n cöc cõa (P ).
Chùng minh .
Theo i·u ki»n (1.24) th¼ tçn t¤i λi ≥ 0, i = 1, · · · , m v
l ∈ L sao cho
λi gi (x) = 0 (i = 1, · · · , m), −l ∈ ∂L f (x)
v
l ∈ ∂L
m
X
!
λi gi (x).
i=1
Vîi méi x ∈ Rn , theo ành ngh¾a cõa L-d÷îi vi ph¥n, ta câ
f (x) ≥ f (x) − l(x) + l(x)
= f (x) − [l(x) − l(x)]
" m
!
X
≥ f (x) −
λi gi (x) −
i=1
= f (x) −
m
X
m
X
!
#
λi gi (x)
i=1
λi gi (x).
i=1
Suy ra f (x) ≥ f (x), vîi måi x ∈ S. Tø â, ta câ x l mët cüc tiºu to n
cöc cõa (P ).
M»nh · 1.3.3 Gi£ sû L l mët tªp c¡c h m mang gi¡ trà thüc ÷ñc
ành ngh¾a tr¶n Rn sao cho −l ∈ L vîi l ∈ L. Trong b i to¡n (P ), cho
15
x ∈ S.
Gi£ sû r¬ng f ∈ L. Khi â, (1.25) thäa m¢n n¸u v ch¿ n¸u
(∃λ ∈
Rm
+)
− f ∈ ∂L
m
X
!
λi gi (x)
v
λi gi (x) = 0.
(1.26)
i=1
i=1
Chùng minh .
m
X
Do f ∈ L, f ∈ ∂L f (x) n¶n ta câ (1.25) suy ra (1.24).
Ng÷ñc l¤i, gi£ sû (1.24) thäa m¢n. Khi â, nh÷ trong ph¦n chùng minh
cõa M»nh · 1.3.2, ta câ
m
X
f (x) ≥ f (x) −
λi gi (x) vîi måi x ∈ Rn .
i=1
Tø â, vîi måi x ∈ Rn , ta nhªn ÷ñc
m
X
λi gi (x) −
i=1
m
X
λi gi (x) ≥ −f (x) + f (x),
i=1
khi
m
X
λi gi (x) = 0.
i=1
Suy ra
−f ∈ ∂L
m
X
!
λi gi (x).
i=1
Do vªy, (1.25) ÷ñc thäa m¢n. M»nh · ÷ñc chùng minh.
Nhc l¤i r¬ng, nân ph¡p tuy¸n cõa mët tªp kh¡c réng D trong Rn èi
vîi L ÷ñc cho bði
(
NL,D (x) :=
{l ∈ L : l(y) − l(x) ≤ 0, ∀y ∈ D} n¸u x ∈ D
n¸u x ∈
/ D.
∅
Ta th§y r¬ng, n¸u L l tªp t§t c£ c¡c h m tuy¸n t½nh ÷ñc ành ngh¾a
tr¶n Rn v D l mët tªp lçi, th¼ NL,D (x) = ND (x), nân ph¡p tuy¸n cõa
D theo ngh¾a cõa gi£i t½ch lçi. Hìn núa, vîi S ÷ñc ành ngh¾a nh÷ trong
(1.24), k¸t luªn sau luæn ÷ñc thäa m¢n.
(
!
)
m
m
X
[
X
NL,S (x) ⊃
∂L
µi gi (x)
µi gi (x) = 0 .
m
µ∈R+
i=1
i=1
16
(1.27)
Nh÷ ta s³ th§y trong luªn v«n n y, ph÷ìng tr¼nh trong (1.27) âng vai trá
°c bi»t quan trång trong vi»c °c tr÷ng cõa tèi ÷u to n cöc thæng qua
c¡c nh¥n tû Lagrange.
ành ngh¾a 1.3.4 (T½nh ch§t-S )
C¡c r ng buëc ÷ñc gåi l thäa m¢n
t½nh ch§t-S (S -property ) n¸u
(
NL,S (x) =
[
µ∈Rm
+
∂L
m
X
)
m
X
(x)
µi gi (x) = 0 ,
!
µi gi
i=1
(1.28)
i=1
vîi måi x ∈ S.
Ta nâi t½nh ch§t-S thäa m¢n t¤i x n¸u (1.27) thäa m¢n t¤i x. Nhªn x²t
r¬ng, t½nh ch§t-S câ vai trá nh÷
t½nh gi£i ÷ñc (solvability property ). Vîi
c¡c h m g1 , · · · , gm , l ∈ L v α ∈ R, ta x²t c¡c h» sau:
(a)
(b)
gi (y) ≤ 0, i = 1, . . . , m =⇒ l(y) ≥ α;
Pm
n
(∃λ ∈ Rm
+ ) l(y) +
i=1 λi gi (y) ≥ α, ∀y ∈ R .
Ta câ thº th§y r¬ng, (b) suy ra ngay (a). Tuy nhi¶n, tø (a) d¨n ¸n (b) ch¿
x£y ra trong c¡c tr÷íng hñp °c bi»t. Khi (a) suy ra (b) ÷ñc thäa m¢n,
th¼ h» {g1 , . . . , gm , l, α} ÷ñc gåi l
thäa m¢n t½nh gi£i ÷ñc. Ch¯ng h¤n,
n¸u L l tªp c¡c h m tuy¸n t½nh v n¸u c¡c h m gi l affine, th¼ c¡c h»
(a) v (b) thäa m¢n t½nh gi£i ÷ñc. i·u n y suy ra tø ành lþ gi£i ÷ñc
¢ bi¸t, ÷ñc gåi l Bê · Farkas ([13]). T÷ìng tü, trong tr÷íng hñp m
c¡c h m gi l lçi, i·u ki»n Slater gi (x0 ) < 0, i = 1, 2, . . . , m vîi x0 ∈ Rn
n o â, th¼ £m b£o r¬ng c¡c h» (a) v (b) thäa m¢n t½nh gi£i ÷ñc ([7]).
Nhªn x²t 1.3.5
Vîi måi l ∈ L v vîi méi x ∈ Rn , h» {g1 , . . . , gm , l, l(x)}
thäa m¢n t½nh gi£i ÷ñc n¸u v ch¿ n¸u c¡c r ng buëc thäa m¢n t½nh ch§t-
S . Trong tr÷íng hñp L l tªp t§t c£ c¡c h m tuy¸n t½nh v f, g1 , g2 , . . . , gm
l c¡c h m lçi, th¼ t½nh ch§t-S l ành t½nh r ng buëc y¸u nh§t cho °c
tr÷ng nh¥n tû Lagrange cõa tèi ÷u èi vîi b i to¡n (P ) ([11], [14]). Trong
tr÷íng hñp n y, i·u ki»n Slater £m b£o t½nh gi£i ÷ñc cõa h» lçi.
M»nh · 1.3.6 Cho L l mët tªp c¡c h m mang gi¡ trà thüc ÷ñc ành
ngh¾a tr¶n Rn sao cho −l ∈ L vîi l ∈ L. Trong b i to¡n (P ), cho x ∈ S.
17
Gi£ sû r¬ng f ∈ L v t½nh ch§t-S thäa m¢n t¤i x. Khi â, x l mët cüc
tiºu to n cöc cõa (P ) n¸u v ch¿ n¸u (1.25) thäa m¢n.
Chùng minh .
Tø x l mët cüc tiºu to n cöc cõa (P ), theo ành ngh¾a
ta câ −f ∈ NL,S (x). Do â, nhí v o t½nh ch§t-S ta câ (1.25) thäa m¢n. Sû
döng M»nh · 1.3.2 v M»nh · 1.3.3, ta câ ngay i·u c¦n chùng minh.
ành lþ sau ¥y s³ ch¿ ra r¬ng t½nh ch§t-S l t½nh ch§t °c tr÷ng cho
c¡c cüc tiºu to n cöc thæng qua c¡c nh¥n tû Lagrange.
ành lþ 1.3.7 ( °c tr÷ng nh¥n tû Lagrange cõa t½nh ch§t-S ) Gi£ sû
r¬ng L l mët tªp c¡c h m mang gi¡ trà thüc ÷ñc ành ngh¾a tr¶n Rn sao
cho −l ∈ L vîi l ∈ L. Khi â, c¡c kh¯ng ành sau l t÷ìng ÷ìng:
(a) C¡c r ng buëc thäa m¢n t½nh ch§t-S .
(b) Vîi måi f ∈ L v vîi méi cüc tiºu to n cöc x cõa f tr¶n S,
(∃λ ∈
Rm
+)
− f ∈ ∂L
m
X
!
λi gi (x)
v
i=1
Chùng minh .
m
X
λi gi (x) = 0.
i=1
(a) =⇒ (b). i·u n y ÷ñc suy ra tø M»nh · 1.3.6.
(b) =⇒ (a). Gi£ sû r¬ng x ∈ S v l ∈ L. Khi â, n¸u l ∈ NL,S (x) th¼ theo
ành ngh¾a v· nân L-ph¡p tuy¸n (L-normal cone), ta câ x l mët cüc tiºu
to n cöc cõa −l tr¶n S. Theo (b), tçn t¤i λ ∈ Rm
+ sao cho
!
m
m
X
X
l ∈ ∂L
λi gi (x) v
λi gi (x) = 0.
i=1
i=1
Suy ra
(
NL,S (x) ⊂
[
µ∈Rm
+
∂L
m
X
)
m
X
(x)
µi gi (x) = 0 .
!
µi gi
i=1
i=1
Tø â, ta câ t½nh ch§t-S thäa m¢n. i·u â công câ ngh¾a l (b) ⇒ (a).
ành lþ ÷ñc chùng minh ho n to n.
18
- Xem thêm -
.PDF 
47 
17 
112 
