ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
TRẦN THỊ NHÀN
ĐIỀU KIỆN CẦN VÀ ĐỦ CHO NGHIỆM HỮU HIỆU
CỦA BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU QUA DƯỚI
VI PHÂN SUY RỘNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2015
i
Lêi cam ®oan
T«i xin cam ®oan r»ng 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. T«i còng xin cam ®oan r»ng mäi sù
gióp ®ì cho viÖc thùc hiÖn luËn v¨n nµy ®· ®îc c¶m ¬n vµ c¸c th«ng tin trÝch
dÉn trong luËn v¨n ®· ®îc chØ râ nguån gèc.
Th¸i Nguyªn, th¸ng 4 n¨m 2015
Ngêi viÕt luËn v¨n
TrÇn ThÞ Nhµn
ii
Lêi c¶m ¬n
LuËn v¨n ®îc thùc hiÖn vµ hoµn thµnh t¹i trêng §¹i häc s ph¹m - §¹i häc
Th¸i Nguyªn díi sù híng dÉn khoa häc cña PGS. TS. §ç V¨n Lu. Qua ®©y,
t¸c gi¶ xin ®îc göi lêi c¶m ¬n s©u s¾c ®Õn thÇy gi¸o,
ngêi híng dÉn khoa
häc cña m×nh, PGS. TS. §ç V¨n Lu, ngêi ®· tËn t×nh híng dÉn trong suèt
qu¸ tr×nh nghiªn cøu cña t¸c gi¶. §ång thêi t¸c gi¶ còng ch©n thµnh c¶m ¬n c¸c
thÇy c« trong khoa To¸n, khoa Sau ®¹i häc - Trêng §¹i häc s ph¹m, §¹i häc
Th¸i Nguyªn, ®· t¹o mäi ®iÒu kiÖn ®Ó t¸c gi¶ hoµn thµnh b¶n luËn v¨n nµy. T¸c
gi¶ còng göi lêi c¶m ¬n ®Õn gia ®×nh vµ c¸c b¹n trong líp Cao häc To¸n K21b,
®· ®éng viªn gióp ®ì t¸c gi¶ trong qu¸ tr×nh häc tËp vµ lµm luËn v¨n.
LuËn v¨n kh«ng thÓ tr¸nh khái nh÷ng thiÕu sãt, t¸c gi¶ rÊt mong nhËn ®îc
sù chØ b¶o tËn t×nh cña c¸c thÇy c« vµ b¹n bÌ ®ång nghiÖp.
Th¸i Nguyªn, th¸ng 4 n¨m 2015
Ngêi viÕt luËn v¨n
TrÇn ThÞ Nhµn
iii
Môc lôc
Lêi cam ®oan
i
Lêi c¶m ¬n
ii
Môc lôc
iii
Më ®Çu
1
1
3
§iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu
1.1
C¸c kiÕn thøc bæ trî
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
1.1.1.
Díi vi ph©n suy réng
1.1.2.
C¸c díi vi ph©n Clarke-Rockafellar, Clarke, Michel-Penot
1.1.3.
Díi vi ph©n suy réng chÝnh quy, díi vi ph©n suy réng tèi
thiÓu
1.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
§iÒu kiÖn cÇn Fritz John cho cùc tiÓu Pareto yÕu
7
.
.
.
.
.
.
.
.
.
10
.
.
.
.
.
.
.
.
.
13
§iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn tèi u Karush-Kuhn-Tucker
24
2.1
§iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn cÇn Karush-Kuhn-Tucker
.
.
.
.
24
2.2
§iÒu kiÖn ®ñ cho cùc tiÓu Pareto yÕu .
KÕt luËn
.
.
.
.
.
.
Tµi liÖu tham kh¶o
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
28
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31
1
Më ®Çu
1. Lý do chän luËn v¨n
N¨m 1994, Demyanov [5] ®· ®a ra kh¸i niÖm díi vi ph©n suy réng comp¨c
låi. Kh¸i niÖm nµy lµ mét tæng qu¸t ho¸ cña kh¸i niÖm låi trªn vµ lâm díi (xem
[6]).
C¸c kh¸i niÖm díi vi ph©n suy réng ®ãng, kh«ng låi vµ Jacobian xÊp xØ
®îc ®Ò xuÊt bëi Jeyakumar vµ Luc trong [9] vµ [10].
Kh¸i niÖm díi vi ph©n
suy réng lµ tæng qu¸t ho¸ cña mét sè c¸c kh¸i niÖm díi vi ph©n ®· biÕt cña
Clarke [4], Michel-Penot [17], Mordukhovich [18]. Mét ®iÒu kiÖn cÇn Fritz John
cho cùc tiÓu yÕu cña bµi to¸n quy ho¹ch ®a môc tiªu díi ng«n ng÷ Jacobian
xÊp xØ ®îc ®a ra bëi Luc [12].
§iÒu kiÖn cÇn tèi u Fritz John cho cùc tiÓu
yÕu díi ng«n ng÷ díi vi ph©n suy réng ®îc ®a ra bëi Dutta- Chandra [7,8]
cho bµi to¸n tèi u ®a môc tiªu víi c¸c rµng buéc bÊt ®¼ng thøc. §iÒu kiÖn cÇn
cho cùc tiÓu yÕu vµ cùc tiÓu Pareto ®îc ®a ra bëi Luu [15] víi c¸c rµng buéc
®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp.
Dùa
(2014)
trªn
®·
®Þnh
thiÕt
lÝ
lËp
Ljusternik
c¸c
®iÒu
më
kiÖn
réng
tèi
u
cña
cho
JimÐnez-Novo
cùc
tiÓu
Pareto
(2002),
yÕu
cña
D.V.Luu
bµi
to¸n
tèi u ®a môc tiªu cã rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp díi
ng«n ng÷ díi vi ph©n suy réng (convexificator). §©y lµ ®Ò tµi ®ang ®îc nhiÒu
t¸c gi¶ trong vµ ngoµi níc quan t©m nghiªn cøu. ChÝnh v× thÕ em chän ®Ò tµi :
§iÒu kiÖn cÇn vµ ®ñ cho nghiÖm h÷u hiÖu cña bµi to¸n tèi u ®a môc tiªu qua
díi vi ph©n suy réng.
2. Ph¬ng ph¸p nghiªn cøu
2
Su tÇm vµ ®äc tµi liÖu tõ c¸c s¸ch, t¹p chÝ to¸n häc trong níc vµ quèc tÕ
liªn quan ®Õn ®iÒu kiÖn tèi u cho bµi to¸n tèi u vÐc t¬.
Qua ®ã, t×m hiÓu vµ
nghiªn cøu vÒ vÊn ®Ò nµy.
3. Môc ®Ých cña luËn v¨n
LuËn v¨n tr×nh bµy c¸c ®iÒu kiÖn cÇn vµ ®ñ cho nghiÖm h÷u hiÖu díi ng«n
ng÷ díi vi ph©n suy réng trong bµi b¸o cña D. V. Lu ®¨ng trong t¹p chÝ Journal
of Optimization Theory and Applications, Vol. 160 (2014), pp. 510-526.
4. Néi dung cña luËn v¨n
LuËn v¨n bao gåm phÇn më ®Çu, 2 ch¬ng, kÕt luËn vµ danh môc c¸c tµi liÖu
tham kh¶o
Ch¬ng 1: §iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu
Tr×nh bµy mét sè kiÕn thøc c¬ b¶n vÒ díi vi ph©n suy réng vµ ®iÒu kiÖn cÇn
Fritz John cho cùc tiÓu Pareto yÕu cña bµi to¸n tèi u ®a môc tiªu cã rµng buéc
®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp víi c¸c hµm Lipschitz ®Þa ph¬ng.
Ch¬ng 2: §iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn tèi u Karush-Kuhn-Tucker
Tr×nh bµy c¸c ®iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn cÇn Karush-Kuhn-Tucker cho
bµi to¸n tèi u ®a môc tiªu cã rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc
tËp víi c¸c hµm Lipschitz ®Þa ph¬ng díi ng«n ng÷ díi vi ph©n suy réng víi
c¸c gi¶ thiÕt vÒ tÝnh låi suy réng, c¸c ®iÒu kiÖn cÇn tèi u trë thµnh c¸c ®iÒu kiÖn
®ñ tèi u.
3
Ch¬ng 1
§iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu
Trong ch¬ng 1 chóng t«i tr×nh bµy mét sè kiÕn thøc c¬ b¶n vÒ díi vi ph©n
suy réng vµ ®iÒu kiÖn cÇn Fritz John cho cùc tiÓu Pareto yÕu cña bµi to¸n tèi u
®a môc tiªu cã rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp díi ng«n
ng÷ díi vi ph©n suy réng. C¸c kÕt qu¶ tr×nh bµy trong ch¬ng nµy ®îc tham
kh¶o trong [9], [14].
1.1
C¸c kiÕn thøc bæ trî
1.1.1.
Cho
Díi vi ph©n suy réng
f
lµ hµm gi¸ trÞ thùc më réng ®îc x¸c ®Þnh trªn
hµm theo ph¬ng Dini díi vµ trªn
v ∈ Rn
f−
vµ
f+
f
cña
t¹i
Rn
. Nh¾c l¹i r»ng ®¹o
x̄ ∈ Rn
theo ph¬ng
®îc x¸c ®Þnh nh sau:
f (x + tv) − f (x̄)
,
t↓0
t
f (x̄ + tv) − f (x̄)
+
f (x̄; v) := lim sup
.
t↓0
t
f − (x̄; v) := lim inf
NÕu
f
t¹i
t¹i
x̄
x̄
f + (x̄; v) = f − (x̄; v)
, th× gi¸ trÞ chung ®ã ®îc gäi lµ ®¹o hµm cña hµm
theo ph¬ng
v
vµ ký hiÖu lµ
f 0 (x̄; v)
. Hµm
nÕu tån t¹i ®¹o hµm theo ph¬ng cña nã t¹i
kh¶ vi FrÐchet t¹i
x̄
víi ®¹o hµm FrÐchet
∇f (x̄)
f
x̄
th×
gäi lµ kh¶ vi theo ph¬ng
theo mäi ph¬ng. NÕu
f
f 0 (x̄; v) = h∇f (x̄, v)i .
lµ
4
f
Theo [9] hµm
∂∗ f (x̄)
) t¹i
®îc gäi lµ cã díi vi ph©n suy réng trªn
x̄ ∈ Rn
nÕu
∂ ∗ f (x̄)
(hay
(∂∗ f (x̄)) ⊆ Rn
f − (x̄; v) ≤ sup hξ, vi
f + (x̄; v) ≥
ξ∈∂∗ f (x̄)
Mét tËp ®ãng
nÕu
∂ ∗ f (x̄)
Theo
∂ ∗ f (x̄) ⊆ Rn
) lµ tËp ®ãng vµ
(∀v ∈ Rn ) .
hξ, vi
inf
®îc gäi lµ mét díi vi ph©n suy réng cña
®ång thêi lµ díi vi ph©n suy réng trªn vµ díi cña
[8]
hµm
∂ ∗ f (x̄) ⊆ Rn
t¹i
f
x̄
®îc
nÕu
(hay díi
(∀v ∈ Rn ),
ξ∈∂ ∗ f (x̄)
∂ ∗ f (x̄)
gäi
lµ
∂ ∗ f (x̄)
cã
díi
vi
ph©n
suy
réng
b¸n
f
t¹i
x̄
chÝnh
f
t¹i
x̄
.
quy
trªn
lµ tËp ®ãng vµ
f + (x̄; v) ≤ sup hξ, vi
(∀v ∈ Rn ).
ξ∈∂ ∗ f (x̄)
(1.1)
VÝ dô 1.1.1
Cho hµm
f :R→R
x,
f (x) := x4 − 4x3 + 4x2 ,
0,
®îc x¸c ®Þnh bëi
khi
x ∈ Q ∩ [0; +∞[,
x ∈ Q ∩ ]−∞; 0],
khi
,
trong c¸c trêng hîp kh¸c
trong ®ã
Q
lµ tËp c¸c sè h÷u tû. Khi ®ã
v,
+
f (0; v) =
0,
khi
v ≥ 0,
khi
v < 0,
f − (0; v) = 0 (∀v ∈ R).
TËp
{0; 1}
lµ díi vi ph©n suy réng b¸n chÝnh quy trªn cña
nã còng lµ díi vi ph©n suy réng trªn cña
réng díi cña
Theo
[9],
f
t¹i
nÕu
f
t¹i
x̄
. TËp
{0}
f
t¹i
x̄
, cho nªn
lµ díi vi ph©n suy
x̄
.
x¶y
ra
®¼ng
thøc
trong
(1.1)
th×
∂ ∗ f (x̄)
®îc
gäi
lµ
díi
vi
ph©n suy réng chÝnh quy trªn. Víi mét hµm Lipschitz ®Þa ph¬ng, díi vi ph©n
5
Clarke vµ díi vi ph©n Michel-Penot lµ nh÷ng díi vi ph©n suy réng cña
x̄
(xem [9]).
f
t¹i
H¬n n÷a víi mét hµm Lipschitz ®Þa ph¬ng chÝnh quy trong theo
nghÜa Clarke [4], díi vi ph©n Clarke lµ mét díi vi ph©n suy réng chÝnh quy
f
trªn (xem [7]). Chó ý r»ng, nÕu hµm
trªn t¹i
x̄
cã mét díi vi ph©n suy réng chÝnh quy
th× nã còng lµ díi vi ph©n suy réng b¸n chÝnh quy trªn t¹i
x̄
®ã nã ®îc lµ díi vi ph©n suy réng trªn t¹i
x̄
, vµ do
.
VÝ dô 1.1.2
Ta xÐt hµm
f :R→R
®îc x¸c ®Þnh bëi:
x2 cos π ,
x
f (x) =
0,
Ta cã
f
t¹i
x̄ = 0
t¬ng øng lµ
x = 0.
f
t¹i
f
x̄ ∈ Q
theo
tÝnh t¹i
x̄ ∈ Q
theo
Q
Q
nÕu
t¹i
{0}
ph©n Clarke
.
C¸c tËp
x̄
. TËp
{0}
vµ
Michile-
{0} [−π; π]
,
vµ
lµ díi vi ph©n suy
.
Q
nÕu víi mçi
f (x) ≤ f (x̄) ⇒ ∀t ∈ ]0, 1[ ,
®îc gäi lµ tùa låi trªn
vµ
vi
x̄
Theo [16] mét hµm gi¸ trÞ thùc më réng
gäi lµ tùa låi t¹i
Díi
[−π; π]
lµ c¸c díi vi ph©n suy réng cña
réng chÝnh quy trªn cña
nÕu
±f
f
x¸c ®Þnh trªn tËp
x∈Q
Q
f
Q ⊆ Rn
®îc
,
f (tx + (1 − t)x̄) ≤ f (x̄).
lµ tùa låi t¹i
suy réng díi låi trªn mét tËp låi
f
lµ tùa låi t¹i mçi
Trong [20] Yang chØ ra r»ng, nÕu
x̄
theo
Q
x∈Q f
.
gäi lµ tùa tuyÕn
.
lµ liªn tôc, tùa låi vµ cã mét díi vi ph©n
th× víi mçi
f (x) ≤ f (y) ⇒ ∃ξ (n) ∈ ∂∗ f (y),
f
khi
.
{−π; π}
NÕu
x 6= 0,
f + (0; v) = f − (0; v) = 0, (∀v ∈ R)
Penot cña
f
khi
x, y ∈ Q
,
lim (ξ (n) , x − y) ≤ 0.
n→∞
cã mét díi vi ph©n suy réng chÝnh quy trªn t¹i
x̄
th× ta cã mÖnh ®Ò sau
®©y.
MÖnh ®Ò 1.1.1
Gi¶ sö
f
cã mét díi vi ph©n suy réng chÝnh quy trªn
∂ ∗ f (x̄) t¹i x̄ vµ f
tùa låi
6
t¹i
x̄ ∈ Q theo tËp låi Q. Khi ®ã,
∀x ∈ Q, f (x) ≤ f (x̄) ⇒ ∀ξ ∈ ∂ ∗ f (x̄), hξ, x − x̄i ≤ 0.
Chøng minh
V×
f
x̄
lµ tùa låi t¹i
theo
Q
, víi mçi
x∈Q
tháa m·n
f (x) ≤ f (x̄)
, ta cã
f + (x̄; x − x̄) ≤ 0.
Do tÝnh chÝnh quy trªn cña díi vi ph©n suy réng
m·n
∂ ∗ f (x̄)
, víi mçi
x∈Q
tháa
f (x) ≤ f (x̄)
, ta cã
sup hξ, x − x̄i = f + (x̄; x − x̄) ≤ 0.
ξ∈∂ ∗ f (x̄)
2
Tõ ®ã, ta cã ®iÒu ph¶i chøng minh.
Theo [20], hµm thùc më réng
trªn
Q
f
cã mét díi vi ph©n suy réng díi låi
Q
x, y ∈ Q
D
E
(n)
lim ξ , y − x ≥ 0 ⇒ f (y) ≥ f (x).
®îc gäi lµ gi¶ låi tiÖm cËn díi trªn
∃ξ (n) ∈ ∂∗ f (x),
Hµm gi¸ trÞ thùc më réng
lµ gi¶ låi tiÖm cËn t¹i
x̄
f
nÕu víi mçi
,
n→∞
cã mét díi vi ph©n suy réng
theo
∃ξ (n) ∈ conv∂ ∗ f (x̄),
Q
∂ ∗ f (x̄)
t¹i
x̄
®îc gäi
x∈Q
D
E
lim ξ (n) , x − x̄ ≥ 0 ⇒ f (x) ≥ f (x̄).
nÕu, víi mçi
ta cã
n→∞
trong ®ã conv kÝ hiÖu bao låi
VÝ dô 1.1.3
Cho
∂∗ f (x)
f, g : R → R
x, khi x ≤ 0,
f (x) :=
1 x, khi x > 0,
2
khi x ∈ Q,
x,
g(x) :=
2x,
khi x ∈ (R\Q) ∩ ]−∞, 0] ,
1
khi x ∈ (R\Q) ∩ [0, ∞[ .
2 x,
7
Khi ®ã mét díi vi ph©n suy réng cña
låi tiÖm cËn t¹i 0 theo
1
∂∗ g(0) = 2 ; 2
Cho
K
vµ
g
Q=R
.
f
t¹i 0 lµ
∂ ∗ f (0) =
1
;
1
2
vµ
Mét díi vi ph©n suy réng díi cña
lµ gi¶ låi tiÖm cËn díi t¹i 0 theo
lµ mét nãn låi ®ãng trong
Rn
f
g
lµ gi¶
t¹i 0 lµ
Q=R
.
vµ
K ∗ := {ξ ∈ Rn : hξ, xi ≥ 0, ∀x ∈ K}
lµ
nãn
cùc
kh«ng
©m
. Gi¶ sö
fk
(f1 , ..., fm )
gäi lµ gi¶ låi
λT f
K
K
cña
.
Cho
f : Q ⊆ Rn → Rm
cã mét díi vi ph©n suy réng
- tiÖm cËn v« híng t¹i
lµ gi¶ låi tiÖm cËn t¹i
x̄
trªn
Q
x̄
theo
vµ
∂ ∗ fk (x̄)
Q
t¹i
nh
x̄
vËy
f =
f
®îc
. Hµm
λ ∈ K∗
nÕu víi mçi
, hµm
.
C¸c nãn tiÕp tuyÕn Bouligand vµ Clarke cña tËp
C ⊆ Rn
t¹i mét ®iÓm
x̄ ∈ C
®îc ®Þnh nghÜa t¬ng øng bëi
K(C, x̄) := {v ∈ Rn : ∃ vn → v, ∃ tn ↓ 0
sao cho
x̄ + tn vn ∈ C, ∀n} ,
T (C, x̄) := {v ∈ Rn : ∀ xn ∈ C, xn → x̄, ∀ tn ↓ 0 , ∃ vn → v
sao cho
Nãn c¸c ph¬ng ®¹t ®îc cña
A(C, x̄) =
n
C
t¹i
x̄ ∈ C
xn + tn vn ∈ C, ∀n} .
lµ:
v ∈ Rn : ∃δ > 0, ∃γ : [0, δ] → Rn
γ(0) = x̄, γ(t) ∈ C, ∀t ∈ ]0, δ] , γ , (0) =
Nãn ph¸p tuyÕn Clarke cña
C
t¹i
x̄
sao cho
lim γ(t)−γ(0)
t
t↓0
=v .
lµ
N (C, x̄) = {ξ ∈ Rn : hξ, vi ≤ 0 ∀ v ∈ T (C, x̄)} .
Chó ý r»ng c¸c nãn
−T ∗ (C, x̄)
vµ
T (C, x̄)
vµ
N (C, x̄)
T (C, x̄) ⊆ K(C, x̄)
.
lµ kh«ng rçng, ®ãng vµ låi;
Trong
trêng
hîp
C
låi
th×
N (C, x̄) =
T (C, x̄) =
K(C, x̄)
.
1.1.2.
C¸c díi vi ph©n Clarke-Rockafellar, Clarke, Michel-Penot
Sau ®©y ta sÏ thÊy r»ng c¸c díi vi ph©n Clarke-Rockafellar, Clarke, Michel-
Penot,...®Òu lµ díi vi ph©n suy réng.
8
f : Rn → R̄
Cho hµm
x
díi t¹i
lµ h÷u h¹n t¹i ®iÓm
x∈X
.
f
NÕu
th× díi ®¹o hµm trªn Clarke - Rockafellar cña
f
t¹i
lµ nöa liªn tôc
x
theo
v
®îc
x¸c ®Þnh bëi:
f ↑ (x, v) = lim sup inf
[f (x0 + tv 0 ) − f (x0 )] /t,
0
x0 →f x v →v
t↓0
trong ®ã
NÕu
f
t¹i
x
f
x0 → f x
nghÜa lµ
x0 → x
lµ nöa liªn tôc trªn t¹i
theo
v
x
vµ
f (x0 ) → f (x) .
th× díi ®¹o hµm díi Clarke-Rockafellar cña
®îc x¸c ®Þnh bëi
f ↓ (x, v) = lim
inf sup [f (x0 + tv 0 ) − f (x0 )] /t.
0
x → f x v 0 →v
t↓0
NÕu
f
lµ liªn tôc t¹i
x
th×
x0 → f x
trong c¸c ®Þnh nghÜa trªn trë thµnh
Díi gradient suy réng trªn vµ díi cña
f
t¹i
x
x0 → x
.
®îc cho bëi
∂ ↑ f (x) = x∗ ∈ X ∗ : hx∗ , vi ≤ f ↑ (x, v) , ∀v ∈ X ,
∂ ↓ f (x) = x∗ ∈ X ∗ : hx∗ , vi ≥ f ↓ (x, v) , ∀v ∈ X .
NÕu
mçi
f ↑ (x, 0) > −∞
th×
∂ ↑ f (x)
lµ tËp con kh«ng rçng, låi, ®ãng cña
Rn
vµ víi
v ∈ Rn ,
f ↑ (x, v) =
sup
hx∗ , vi .
x∗ ∈ ∂ ↑ f (x)
T¬ng tù, nÕu
f ↓ (x, 0) < ∞
Rn
v ∈ Rn ,
vµ víi mçi
th×
∂ ↓ f (x)
f ↓ (x, v) =
NÕu
f
lµ Lipschitz ®Þa ph¬ng t¹i
x
lµ tËp con kh«ng rçng, låi, ®ãng cña
inf↓
x∗ ∈ ∂ f (x)
hx∗ , vi .
th×
f ↑ (x; v) = f o (x, v) , f ↓ (x; v) = fo (x, v) ,
trong ®ã,
f o (x, v) = lim sup [f (x0 + tv) − f (x0 )] /t,
x0 → x
t↓0
fo (x, v) = lim
inf [f (x0 + tv) − f (x0 )] /t.
0
x →x
t↓0
9
f
lµ c¸c ®¹o hµm theo ph¬ng suy réng trªn vµ díi Clarke cña
v
t¹i
x
theo ph¬ng
. Díi vi ph©n suy réng Clarke ®îc x¸c ®Þnh bëi
∂ o f (x) = {x∗ ∈ X ∗ : hx∗ , vi ≤ f o (x, v) , ∀v ∈ X} .
H¬n n÷a,
f o (x, v) =
f
Do ®ã, nÕu
cña
f
t¹i
x
∗
max
hx
, vi ,
∗
o
x ∈ ∂ f (x)
lµ Lipschitz ®Þa ph¬ng t¹i
x
th×
min
∗
o
x ∈ ∂ f (x)
∂ o f (x)
hx∗ , vi .
lµ díi vi ph©n suy réng
, bëi v×
f − (x, v) ≤ f o (x, v) ,
víi mçi
fo (x, v) =
v∈X
T¬ng tù, nÕu
f + (x, v) ≥ fo (x, v) .
.
f
lµ Lipschitz ®Þa ph¬ng t¹i
díi Michel Penot cña
f
t¹i
x
x
th× ®¹o hµm theo ph¬ng trªn vµ
t¬ng øng ®îc cho bëi
f ♦ (x, v) = sup lim sup λ−1 [f (x + λz + λv) − f (x + λz)] ,
z∈X
λ↓0
f♦ (x, v) = inf lim inf λ−1 [f (x + λz + λv) − f (x + λz)] .
z∈X
λ↓0
Khi ®ã díi vi ph©n Michel Penot ®îc x¸c ®Þnh bëi
∂ ♦ f (x) := x∗ ∈ Rn : f ♦ (x, v) ≥ hx∗ , vi , ∀v ∈ Rn .
§¹o hµm theo ph¬ng trªn vµ díi Michel Penot
tuyÕn tÝnh, h÷u h¹n,
f ♦ (x, v) =
Do ®ã,
∂ ♦ f (x)
∂ ♦ f (x)
max
hx∗ , vi ,
f♦ (x, v) =
f + (x, v) ≥ f♦ (x, v)
VÝ dô 1.1.4
f : R2 → R
f♦ (x, .)
x¸c ®Þnh bëi
f (x, y) = |x| − |y| .
hx∗ , vi .
min
x∗ ∈ ∂ ♦ f (x)
còng lµ mét díi vi ph©n suy réng cña
vµ
vµ
lµ compact låi
x∗ ∈ ∂ ♦ f (x)
f − (x, v) ≤ f ♦ (x, v)
§Þnh nghÜa
f ♦ (x, .)
f
t¹i
víi mçi
x
, bëi v×
v ∈ Rn .
lµ díi
10
Khi ®ã
∂ ∗ f (0) = {(1, −1) , (−1, 1)} .
lµ mét díi vi ph©n suy réng cña
f
t¹i 0. Ta cã
∂ ♦ f (0) = ∂ o f (0) = co ({(1, 1) , (−1, 1) , (1, −1) , (−1, −1)}) .
Chó ý r»ng
co (∂ ∗ f (0)) ⊆ ∂ ♦ f (0) = ∂ o f (0) .
1.1.3.
Díi vi ph©n suy réng chÝnh quy, díi vi ph©n suy réng tèi thiÓu
Râ rµng tõ ®Þnh nghÜa ta thÊy díi vi ph©n suy réng trªn vµ díi kh«ng duy
nhÊt. V× vËy trong phÇn nµy chóng ta sÏ tr×nh bµy c¸c ®iÒu kiÖn vÒ tÝnh duy nhÊt
vµ tèi thiÓu cña díi vi ph©n suy réng trªn hoÆc díi.
Tríc tiªn ta tr×nh bµy
kh¸i niÖm díi vi ph©n suy réng chÝnh quy trªn vµ díi.
Hµm
f : Rn → R
∂ ∗ f (x) ⊆ Rn
t¹i
x
®îc gäi lµ cã mét díi vi ph©n suy réng chÝnh quy trªn
nÕu
∂ ∗ f (x)
lµ tËp ®ãng vµ víi mçi
f + (x, v) =
v ∈ Rn ,
hx∗ , vi .
sup
x∗ ∈∂ ∗ f (x)
T¬ng
tù,
hµm
∂∗ f (x) ⊆ Rn
f
t¹i
®îc
x
nÕu
gäi
lµ
cã
∂∗ f (x)
mét
vi
ph©n
suy
lµ tËp ®ãng vµ víi mçi
f − (x, v) =
Râ rµng,
díi
inf
x∗ ∈∂∗ f (x)
réng
chÝnh
f
t¹i
x
díi
v ∈ Rn .
hx∗ , vi .
mçi díi vi ph©n suy réng chÝnh quy trªn (díi) cña
díi vi ph©n suy réng cña
quy
f
t¹i
x
lµ mét
.
Trong mÖnh ®Ò sau chóng ta sÏ tr×nh bµy mèi liªn hÖ gi÷a tÝnh kh¶ vi vµ tÝnh
chÝnh quy.
MÖnh ®Ò 1.1.2
Hµm
f : Rn → R
ph¬ng t¹i
x0
vµ
f
lµ kh¶ vi G©teaux t¹i
x0
nÕu vµ chØ nÕu
f
lµ kh¶ vi theo
cã mét díi vi ph©n suy réng chÝnh quy trªn vµ chÝnh quy
11
díi t¹i
x0 .
Chøng minh
NÕu
f
lµ kh¶ vi G©teaux t¹i
{f 0 (x0 )}
x0
th× nã kh¶ vi theo ph¬ng vµ ®¹o hµm G©teaux
f
vµ lµ mét díi vi ph©n suy réng chÝnh quy trªn vµ díi cña
Ngîc l¹i, nÕu
f
kh¶ vi theo ph¬ng t¹i
x0
vµ nÕu
v ∈ Rn
suy réng chÝnh quy trªn vµ díi th× víi mçi
f 0 (x0 , v) = f − (x0 , v) =
= f + (x0 , v) =
∂ ∗ f (x0 )
t¹i
x0
.
lµ mét díi vi ph©n
.
inf
∗
x∗ ∈∂ f (x)
hx∗ , vi
hx∗ , vi .
sup
x∗ ∈∂ ∗ f (x)
Do ®ã
∂ ∗ f (x0 )
Ta nãi r»ng
lµ tËp mét ph©n tö vµ v× vËy
∂ ∗ f (x)
vµ
kh¶ vi G©teaux t¹i
C (x)
C (x)
trong
Rn
sao cho
lµ
2
.
f
t¹i
x
C (x) ⊂ ∂ ∗ f (x) ,
lµ mét díi vi ph©n suy réng (trªn/díi) cña
Ký hiÖu tËp c¸c ®iÓm cùc biªn cña díi vi ph©n suy réng
x
x0
lµ díi vi ph©n suy réng tèi thiÓu (trªn/díi) cña
nÕu kh«ng tån t¹i mét tËp ®ãng
C (x) 6= ∂ ∗ f (x)
f
∂ ∗ f (x)
f
cña
t¹i
x
f
t¹i
.
Ext (∂ ∗ f (x))
.
MÖnh ®Ò 1.1.3
Gi¶ sö r»ng
(díi)
f : Rn → R cã mét díi vi ph©n suy réng chÝnh quy comp¨c trªn
∂ ∗ f (x) t¹i x.
Khi ®ã
Ext (co (∂ ∗ f (x))) lµ díi vi ph©n suy réng chÝnh
quy trªn (díi) tèi thiÓu duy nhÊt cña
f
t¹i
x.
Chøng minh
Cho
A ⊂ Rn
víi mçi
cã mét díi vi ph©n suy réng chÝnh quy trªn cña
v ∈ Rn ,
f + (x, v) =
sup
hx∗ , vi = sup hx∗ , vi .
x∗ ∈A
x∗ ∈∂ ∗ f (x)
Nªn A lµ tËp con ®ãng vµ bÞ chÆn cña
Rn
víi
co (∂ ∗ f (x)) = co (A) .
Khi ®ã,
Ext (co (∂ ∗ f (x))) = Ext (co (A)) .
f
t¹i
x
. Khi ®ã,
12
Chóng ta chØ ra r»ng
Ext (co (∂ ∗ f (x))) ⊆ A.
ThËt vËy hiÓn nhiªn ta cã
Ext (co (A)) ⊆ Ext (A) .
Do ®ã,
Ext (co (∂ ∗ f (x))) = Ext (co (A)) ⊆ Ext (A) ⊂ A.
Bëi v×
A
lµ tËp ®ãng, ta cã
Ext (co (∂ ∗ f (x))) ⊆ A.
MÆt kh¸c bëi v×,
cho
nªn
trªn cña
∂ ∗ f (x)
lµ mét díi vi ph©n suy réng chÝnh quy comp¨c trªn,
Ext (co (∂ ∗ f (x)))
f
x
t¹i
. Do ®ã,
còng
lµ
díi
vi
Ext (co (∂ ∗ f (x)))
tèi thiÓu trªn duy nhÊt cña
f
t¹i x.
ph©n
suy
réng
chÝnh
quy
comp¨c
lµ díi vi ph©n suy réng chÝnh quy
Chøng minh t¬ng tù cho trêng hîp
f
2
díi vi ph©n suy réng chÝnh quy díi.
Ta nãi hµm
v ∈ Rn
f
cã
h÷u h¹n vµ liªn tôc t¹i
x
lµ chÝnh quy trªn t¹i
x
nÕu víi mçi
,
f + (x, v) = f ↑ (x, v) .
T¬ng tù hµm
f
lµ chÝnh quy díi t¹i
x
nÕu víi mçi
v ∈ Rn
,
f − (x, v) = f ↓ (x, v) .
Chó ý r»ng, nÕu
f : Rn → R
v ∈ Rn f + (., v) [f − (., v)]
,
lµ Lipschitz ®Þa ph¬ng trªn
Rn
vµ nÕu víi mçi
lµ nöa liªn tôc trªn [díi], th× víi mçi
x ∈ Rn
vµ
v ∈ Rn ,
f + (x, v) = f o (x, v) = f ↑ (x, v) f − (x, v) = fo (x, v) = f ↓ (x, v) ,
cho nªn,
NÕu
f
lµ chÝnh quy trªn [díi] t¹i
f ↑ (x, 0) > −∞
låi, ®ãng cña
Rn
vµ nÕu
vµ víi mçi
f
x
(xem [6]).
lµ chÝnh quy trªn t¹i
x
th×
v ∈ Rn ,
f + (x, v) = f ↑ (x, v) =
sup
x∗ ∈∂ ↑ f (x)
hx∗ , vi .
∂ ↑ f (x)
kh¸c rçng,
13
Do ®ã,
∂ ↑ f (x)
tù, nÕu
f ↓ (x, 0) < ∞
cña
Rn
lµ mét díi vi ph©n suy réng chÝnh quy trªn cña
vµ víi mçi
vµ
f
chÝnh quy díi t¹i
∂ ↓ f (x)
víi mçi
∂ ↓ f (x)
. T¬ng
kh¸c rçng, låi, ®ãng
inf
x∗ ∈∂ ↓ f (x)
hx∗ , vi .
lµ díi vi ph©n suy réng chÝnh quy díi cña
f : Rn → R
NÕu
th×
x
t¹i
v ∈ Rn ,
f − (x, v) = f ↓ (x, v) =
Cho nªn
x
f
lµ Lipschitz ®Þa ph¬ng trªn
Rn
f
t¹i
x
.
vµ chÝnh quy trªn t¹i
x
, th×
v ∈ Rn ,
∗
f + (x, v) = f ↑ (x, v) = f o (x, v) = ∗ max
hx
, vi .
o
x ∈∂ f (x)
Do ®ã,
cña
f
Ext (∂ o f (x))
t¹i
x
lµ díi vi ph©n suy réng chÝnh quy tèi thiÓu trªn duy nhÊt
. Chó ý r»ng, nÕu
f
lµ låi th×
chÝnh quy tèi thiÓu trªn duy nhÊt cña
f
Ext (∂f (x))
t¹i
lµ díi vi ph©n suy réng
x
, trong ®ã
∂f (x) := {x∗ ∈ X ∗ : f (y) − f (x) ≥ hx∗ , y − xi , ∀y ∈ Rn }
lµ díi vi ph©n låi cña
1.2
f
t¹i
x
.
§iÒu kiÖn cÇn Fritz John cho cùc tiÓu Pareto yÕu
PhÇn nµy tr×nh bµy c¸c ®iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu ®Þa ph¬ng
díi ng«n ng÷ díi vi ph©n suy réng chÝnh quy trªn vµ b¸n chÝnh quy trªn. XÐt
bµi to¸n tèi u ®a môc tiªu (P) sau:
min f (x),
g (x) ≤ 0,
h (x) = 0,
x ∈ C,
f g h
trong ®ã
con cña
,
Rn
,
t¬ng øng lµ c¸c ¸nh x¹ tõ
. Khi ®ã
,
vµo
Rr Rm Rl C
,
,
;
lµ mét tËp
f = (f1 , ..., fr ) g = (g1 , ..., gm ) h = (h1 , ..., hl )
f1 , ..., fr g1 , ..., gm h1 , ..., hl
,
Rn
,
,
, trong ®ã
lµ nh÷ng hµm gi¸ trÞ thùc më réng x¸c ®Þnh trªn
14
Rn
cã
x, y ∈ Rn
. Víi
nghÜa
, ta viÕt
x≤y
nÕu
xi ≤ yi , (i = 1, ..., n)
. Nh vËy
gi (x) ≤ 0 (i = 1, ..., m)
lµ
,
(j = 1, ..., l)
.
§Æt
vµ
h(x) = 0
cã
nghÜa
lµ
I = {1, ..., m} J = {1, ..., r} L = {1, ..., l}
,
,
.
g(x) ≤ 0
hj (x) = 0
,
Chó ý r»ng
®iÒu kiÖn cÇn díi ng«n ng÷ díi vi ph©n suy réng cho bµi to¸n víi rµng buéc
tËp hoÆc rµng buéc bÊt ®¼ng thøc ®· ®îc nghiªn cøu bëi Dutta-Chandra [7,8]
vµ cã rµng buéc ®¼ng thøc vµ bÊt ®¼ng thøc ®· ®îc nghiªn cøu bëi Luu [15].
KÝ hiÖu
M
lµ tËp chÊp nhËn ®îc cña bµi to¸n (P):
M := {x ∈ C : g(x) ≤ 0, h(x) = 0} ,
vµ
I(x̄) := {i ∈ I : g(x̄) = 0} ,
H := {x ∈ Rn : h(x) = 0} .
Më réng cña ®Þnh lý Ljusternik cæ ®iÓn cña JimÐnez-Novo trong [11] sÏ ®îc
sö dông ®Ó dÉn ®iÒu kiÖn cÇn tèi u.
MÖnh ®Ò 1.2.1
[11]
Gi¶ sö r»ng
x̄ ∈ H ∩ C ;
(a)
C
lµ tËp låi vµ
(b)
h
liªn tôc trong mét l©n cËn cña
FrÐchet lµ
x̄
vµ kh¶ vi FrÐchet t¹i
x̄
víi ®¹o hµm
∇h(x̄);
(c) §iÒu kiÖn chÝnh quy (RC) sau ®©y ®óng:
0∈
X
γj ∇hj (x̄) + N (C, x̄) ⇒ γ1 = ... = γl = 0.
j∈L
Khi ®ã,
A(H ∩ C; x̄) = T (H ∩ C; x̄) = (ker ∇h(x̄)) ∩ T (C; x̄)
= cl [(ker ∇h(x̄)) ∩ cone(C − x̄)] ,
trong ®ã
cl kÝ hiÖu bao ®ãng.
15
NhËn xÐt 1.2.1
NÕu
C = Rn h
,
thuéc líp
C1
trong mét l©n cËn cña
x̄
vµ
∇h1 (x̄), ..., ∇hr (x̄)
lµ
®éc lËp tuyÕn tÝnh, th× mÖnh ®Ò 1.2.1 trë thµnh ®Þnh lý Ljusternik cæ ®iÓn. ThËt
vËy, khi ®ã ¸nh x¹
®óng vµ ta cã
∇h(x̄)
lµ toµn ¸nh,
T (C; x̄) = Rn
, ®iÒu kiÖn chÝnh quy (RC)
ker ∇h(x̄) = T (C; x̄).
§iÒu kiÖn (RC) sÏ ®îc minh häa bëi vÝ dô sau.
VÝ dô 1.2.1
Cho
h R3 → R2
:
vµ
C ⊂ R3
®îc x¸c ®Þnh nh sau
h := (h1 , h2 )
(x̄, ȳ, z̄) = 0,
,
h1 (x, y, z) = x + 2y + z,
h2 (x, y, z) = 2x + 4y − z,
C := {(x, y, z) : −1 ≤ x ≤ 0, −1 ≤ y, z ≤ 1} .
Khi ®ã
∇h1 (0, 0, 0) = (1, 2, 1) ∇h2 (0, 0, 0) = (2, 4, −1) T (C; 0) = −R+ ×
,
R × R N (C; 0) = R+ × {0} × {0}
,
,
vµ ®iÒu kiÖn (RC) tháa m·n. ThËt vËy nÕu
0 ∈ γ1 ∇h1 (0) + γ2 ∇h2 (0) + N (C; 0),
cã nghÜa lµ
(0, 0, 0) ∈ (γ1 + 2γ2 , 2γ1 + 4γ2 , γ1 − γ2 ) + R+ × {0} × {0} ,
khi ®ã ta suy ra
γ1 = γ2 = 0
. Do ®ã, ®iÒu kiÖn (RC) ®óng
Nh¾c l¹i r»ng ®iÓm
x̄ ∈ M
bµi to¸n (P) nÕu tån t¹i mét sè
®îc gäi lµ cùc tiÓu Pareto yÕu ®Þa ph¬ng cña
δ>0
sao cho kh«ng tån t¹i
x ∈ M ∩ B (x̄; δ)
tháa m·n
(∀k ∈ J) ,
fk (x) < fk (x̄)
trong ®ã
B (x̄; δ)
lµ h×nh cÇu më b¸n kÝnh
δ
t©m
x̄
.
Gi¶ thiÕt sau ®©y lµ cÇn thiÕt ®Ó dÉn c¸c ®iÒu kiÖn cÇn cho nghiÖm h÷u hiÖu
yÕu.
16
Gi¶ thiÕt 1.2.1
Tån t¹i mét chØ sè
t¹i
x̄
ph©n
.
Víi
suy
mçi
réng
gi (i ∈
/ I (x̄))
s∈J
sao cho
k ∈ J, k 6= s
b¸n
chÝnh
liªn tôc t¹i
quy
fs
vµ
cã mét díi vi ph©n suy réng trªn
i ∈ I (x̄)
,
trªn
∂ ∗ fk (x̄)
c¸c
vµ
hµm
fk
∂ ∗ gi (x̄)
gi
vµ
t¹i
x̄
;
cã
tÊt
∂ ∗ fs (x̄)
c¸c
c¶
díi
c¸c
vi
hµm
x̄
.
Trªn c¬ së ®Þnh lý Ljusternik suy réng cña JimÐnez-Novo [11], ta chøng minh
®iÒu kiÖn cÇn cho cùc tiÓu Pareto yÕu ®Þa ph¬ng cña (P).
§Þnh lý 1.2.1
Gi¶ sö
x̄ lµ cùc tiÓu Pareto yÕu ®Þa ph¬ng cña (P). Gi¶ sö r»ng tÊt c¶ c¸c gi¶
thiÕt cña mÖnh ®Ò 1.2.1 vµ gi¶ thiÕt 1.2.1 ®óng. Gi¶ sö c¸c hµm
gi (i ∈ I (x̄))
Lipschitz ®Þa ph¬ng t¹i
x̄.
fk (k ∈ J)
vµ
Khi ®ã, c¸c hÖ sau kh«ng cã nghiÖm
v ∈ Rn :
hξk , vi < 0 (∀k ∈ J),
sup
(1.2)
ξk ∈conv∂ ∗ fk (x̄)
sup
hξi , vi < 0 (∀i ∈ I(x̄)),
(1.3)
ξi ∈conv∂ ∗ gi (x̄)
h∇hj (x̄), vi = 0 (∀j ∈ L),
(1.4)
v ∈ T (x̄; C).
(1.5)
Chøng minh
Ta chØ ra r»ng nh÷ng ®iÒu kiÖn sau kh«ng cã nghiÖm
v ∈ Rn
:
fs− (x̄; v) < 0,
(1.6)
fk+ (x̄; v) < 0 (∀k ∈ J; k 6= s),
(1.7)
gi+ (x̄; v) < 0 (∀i ∈ I(x̄)),
(1.8)
h∇hj (x̄), vi = 0 (∀j ∈ L),
(1.9)
v ∈ T (x̄; C).
(1.10)
- Xem thêm -