VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
VIỆN TOÁN HỌC
———————–
THÁI DOÃN CHƯƠNG
HÀM GIÁ TR TI ƯU VÀ ÁNH X NGHIM
HU HIU TRONG CÁC BÀI TN TI ƯU
VÉCTƠ CÓ THAM S
Chuyên ngành: thuyết tối ưu
số: 62 46 20 01
TÓM TT LUẬN ÁN TIẾN TOÁN HỌC
Nội - 2011
Công trình y được hoàn thành tại Viện Toán học, Viện Khoa học và
Công nghệ Việt Nam.
Người hướng dẫn khoa học:
1. GS.TSKH. Nguyễn Đông Yên
2. TS. Nguyễn Quang Huy
Phản biện 1: GS.TSKH. Nguyễn Xuân Tấn
Phản biện 2: GS.TSKH. Nguyễn Hữu Công
Phản biện 3: PGS.TS. Nguyễn Thị Bạch Kim
Luận án sẽ được bảo v tại Hội đồng chấm luận án cấp viện họp tại Viện
Toán học - Viện Khoa học và Công nghệ Việt Nam
vào hồi 9 giờ 00 ngày 28 tháng 07 năm 2011
thể tìm hiểu luận án tại: - Thư viện của Viện Toán học
. - Thư viện quốc gia
®Çu
Bµi to¸n tèi u vÐct¬ d¹ng chuÈn bµi to¸n t×m cùc trÞ mét hµm
f:XY
,
ë ®ã
X
Y
c¸c kh«ng gian vÐct¬ t«p«, díi mét rµng buéc. Kh¸i niÖm
cùc trÞ ë ®©y ®îc x¸c ®Þnh theo mét thø bé phËn trong kh«ng gian
Y
. Thø
nµy thêng ®îc ®Þnh nghÜa qua mét nãn låi
KY
:
y1Ky2y2y1K.
Nh vËy, bµi to¸n tèi u vÐct¬ réng cña bµi to¸n quy ho¹ch to¸n häc,
ë ®ã
Y=R
K=R+
.
Tèi u vÐct¬ (Vector optimization) ra ®êi vµo cuèi thÕ 19, víi kh¸i niÖm
nghiÖm ®îc ®Ò xuÊt bëi F. Y. Edgeworth (1881) V. Pareto (1896). h×nh
bµi to¸n tèi u vÐct¬ cho phÐp nghiªn cøu mét vÊn ®Ò phóc lîi héi
(social welfare) c©n b»ng kinh (economic equilibrium). Ngoµi ra, h×nh
nµy còng h÷u Ých trong viÖc gi¶i quyÕt nh÷ng bµi to¸n ra quyÕt ®Þnh chøa ®ùng
nhiÒu lîi Ých kh«ng t¬ng thÝch hoÆc ®èi kh¸ng thêng gÆp trong c¸c vÊn ®Ò
liªn quan ®Õn thiÕt thuËt, m«i trêng, tµi chÝnh,... Tèi u vÐct¬ mét bé
phËn quan träng cña thuyÕt i u (Optimization theory). Tèi u vÐct¬ xuÊt
hiÖn nh mét chuyªn ngµnh to¸n häc ®éc lËp sau bµi b¸o cña H. W. Kuhn
A. W. Tucker (1951) c¸c ®iÒu kiÖn cÇn ®ñ cho mét vÐct¬ tháa c¸c rµng
buéc nghiÖm h÷u hiÖu. §Õn nay, ®· rÊt nhiÒu cuèn s¸ch chuyªn kh¶o
Tèi u vÐct¬ øng dông: M. Ehrgott (2005), J. Jahn (2004), D. T. Luc (1989),
Y. Sawaragi, H. Nakayama T. Tanino (1985), R. E. Steuer (1986), M. Zeleny
(1982),...
Bªn c¹nh tån t¹i nghiÖm, ®iÒu cÇn ®ñ cùc trÞ, tÝnh chÊt cña tËp nghiÖm
c¸c thuËt to¸n t×m nghiÖm,
tÝnh æn ®Þnh nghiÖm
(solution stability/stability
analysis)
®é nh¹y nghiÖm
(solution sensitivity/sensitivity analysis) nh÷ng
vÊn ®Ò b¶n cña thuyÕt Tèi u vÐct¬ øng dông.
Nghiªn cøu tÝnh æn ®Þnh nghiÖm tøc kh¶o s¸t c¸c tÝnh chÊt liªn tôc cña
¸nh nghiÖm h÷u hiÖu hoÆc hµm gi¸ trÞ tèi u theo tham cña bµi to¸n ®·
cho, nh tÝnh nöa liªn tôc trªn, tÝnh nöa liªn tôc díi, tÝnh gi¶-Lipschitz, tÝnh
Lipschitz, tÝnh liªn tôc H
¨o
lder,... Nh÷ng kÕt qu¶ ®Çu tiªn theo híng nµy
thuéc vÒ P. H. Naccache (1979), T. Tanino Y. Sawaragi (1980). Mét kÕt
qu¶ tæng qu¸t h¬n tÝnh æn ®Þnh cña c¸c bµi to¸n tèi u vÐct¬ trong c¸c
cuèn s¸ch chuyªn kh¶o cña Luc cña Sawaragi, Nakayama Tanino võa
®îc trÝch dÉn ë trªn. TÝnh liªn tôc Lipschitz-H
¨o
lder cña ¸nh nghiÖm trong
c¸c bµi to¸n tèi u vÐct¬ låi m¹nh phô thuéc tham ®· ®îc kh¶o s¸t lÇn ®Çu
tiªn trong bµi b¸o cña G. M. Lee, D. S. Kim, B. S. Lee N. D. Yen (1998).
Ph©n tÝch ®é nh¹y nghiÖm trong Tèi u vÐct¬ nghÜa tÝnh to¸n ®¹o hµm
(theo nghÜa ®iÓn hoÆc theo nghÜa suy réng), ®èi ®¹o hµm (®èi ®¹o hµm
FrÐchet, ®èi ®¹o hµm Mordukhovich,...) cña ¸nh nghiÖm h÷u hiÖu hoÆc hµm
1
gi¸ trÞ tèi u cña c¸c bµi to¸n phô thuéc tham sè. §«i khi, ngêi ta còng coi
c¸c kÕt qu¶ tÝnh liªn tôc a ¸nh nghiÖm nh c¸c kÕt qu¶ thuéc vµo chñ
®Ò ph©n tÝch ®é nh¹y nghiÖm. T. Tanino (1988) ®· ph©n tÝch d¸ng ®iÖu cña hµm
gi¸ trÞ tèi u b»ng c¸ch dông "®¹o hµm tiÕp liªn" (contingent derivative).
Ngêi ta còng ®· nghiªn cøu ®é nh¹y nghiÖm b»ng c¸c lo¹i ®¹o hµm suy
réng kh¸c: E. M. Bednarczuk W. Song (1998), míi ®©y W. Song L.-
J. Wan (2005), ®· dông "®¹o hµm tiÕp liªn trªn-®å-thÞ suy réng" (generalized
contingent epiderivative); G. M. Lee N. Q. Huy (2007) ng "tiÒn ®¹o
hµm" (proto-derivative). Mçi lo¹i ®¹o hµm suy réng ®Òu ®îc x©y ng qua
nh÷ng nãn tiÕp tuyÕn nµo ®ã cña ®å thÞ cña ¸nh ®a trÞ t¹i ®iÓm ®ang kh¶o s¸t:
®¹o hµm tiÕp liªn ®îc x©y dùng qua nãn tiÕp tuyÕn Bouligand, tiÒn ®¹o hµm
®îc x©y dùng qua nãn tiÕp tuyÕn Bouligand vµ nãn tiÕp tuyÕn trung gian,...
Ph¬ng ph¸p nghiªn cøu sö dông c¸c ®¹o hµm suy réng thêng ®îc gäi
ph¬ng ph¸p tiÕp cËn b»ng kh«ng gian nÒn
(the primal space approach).
dông nãn ph¸p tuyÕn t¹i mét ®iÓm cho tríc trªn ®å thÞ cña ¸nh ®a trÞ,
B. S. Mordukhovich (1980) ®· x©y dùng kh¸i niÖm
®èi ®¹o hµm
(coderivative)
- ®ã mét ¸nh ®a trÞ gi÷a c kh«ng gian ®èi ngÉu. Ph¬ng ph¸p nghiªn
cøu dông ®èi ®¹o hµm ®îc gäi
ph¬ng ph¸p tiÕp cËn b»ng kh«ng gian
®èi ngÉu
(the dual space approach). Trong nhiÒu t×nh huèng ë ®ã nãn ph¸p
tuyÕn (kh«ng nhÊt thiÕt ph¶i nãn låi) kh«ng ®èi ngÉu cña bÊt lo¹i nãn
tiÕp tuyÕn nµo, ph¬ng ph¸p tiÕp cËn b»ng kh«ng gian ®èi ngÉu thêng chiÕm
u thÕ h¬n ph¬ng ph¸p tiÕp cËn b»ng kh«ng gian nÒn.
LuËn ¸n nµy tr×nh bµy mét kÕt qu¶ míi tÝnh æn ®Þnh nghiÖm ®é
nh¹y nghiÖm cña c¸c bµi to¸n tèi u vÐct¬ tham sè. LuËn ¸n bao gåm phÇn
®Çu, 4 ch¬ng, phÇn kÕt luËn, danh môc tµi liÖu tham kh¶o. Hai ch¬ng
®Çu nghiªn cøu tÝnh æn ®Þnh nghiÖm cña c¸c bµi to¸n tèi u vÐct¬ nöa h¹n.
Hai ch¬ng sau kh¶o s¸t ®é nh¹y nghiÖm cña mét bµi to¸n d¹ng tæng qu¸t.
Ch¬ng 1 nghiªn cøu c¸c tÝnh chÊt a liªn tôc trªn nöa liªn tôc díi a
¸nh nghiÖm h÷u hiÖu trong bµi to¸n tèi u vÐct¬ nöa h¹n díi phÐp nhiÔu
hµm cña hµm môc tiªu tËp rµng buéc.
Ch¬ng 2 thiÕt lËp c¸c ®iÒu kiÖn ®ñ cho tÝnh gi¶-Lipschitz cña ¸nh nghiÖm
h÷u hiÖu trong bµi to¸n tèi u vÐct¬ nöa h¹n låi díi phÐp nhiÔu hµm cña
hµm môc tiªu phÐp nhiÔu liªn tôc bªn ph¶i cña c hµm rµng buéc.
Ch¬ng 3 dông ®¹o hµm trªn-®å-thÞ Clarke suy réng ®îc giíi thiÖu bëi
L. Chen (2002) ®Ó ph©n tÝch ®é nh¹y nghiÖm.
Ch¬ng 4 nghiªn cøu ®é nh¹y nghiÖm b»ng c¸ch dông ®èi ®¹o hµm
FrÐchet.
ViÖc ®¸nh cña c¸c ch¬ng, môc, ®Þnh lý, c«ng thøc,... trong b¶n tãm t¾t
nµy ®îc gi÷ nguyªn nh ë trong luËn ¸n.
2
Ch¬ng 1
TÝnh nöa liªn tôc cña nghiÖm bµi to¸n
tèi u vÐct¬ nöa h¹n tæng qu¸t
Ch¬ng 1 thiÕt lËp c¸c ®iÒu kiÖn cÇn ®ñ cho tÝnh chÊt nöa liªn tôc trªn
nöa liªn tôc díi cña ¸nh nghiÖm h÷u hiÖu trong bµi to¸n tèi u vÐct¬ nöa
h¹n díi phÐp nhiÔu hµm cña hµm môc tiªu tËp rµng buéc. Nh÷ng kÕt
qu¶ nµy ®· ®îc c«ng trong [1].
1.1. C¸c hiÖu kh¸i niÖm b¶n
Cho
Θ
t tËp con comp¾c a mét kh«ng gian t«p« Hausdorff cho
C,Rn]
kh«ng gian c¸c hµm vÐct¬ liªn tôc
Θ
vµo
Rn
®îc trang bëi
chuÈn
||f|| := max
xΘkf(x)knfC,Rn],
ë ®ã hiÖu
|| · ||n
®îc dïng ®Ó chØ chuÈn trong kh«ng gian Euclide
n
-chiÒu
Rn
. ChuÈn trong kh«ng gian tÝch
X×Y
cña c¸c kh«ng gian ®Þnh chuÈn
X
Y
nµo ®ã ®îc ®Þnh nghÜa bëi
||(x, y)|| := ||x|| +||y|| (x, y)X×Y.
Cho
tËp con comp¾c kh¸c rçng cña mét kh«ng gian mªtric
(X, d)
cho
T
tËp con comp¾c kh¸c rçng cña t kh«ng gian t«p« Hausdorff nµo ®ã.
Bµi to¸n
tèi u vÐct¬ nöa h¹n phô thuéc tham
(parametric semi-infinite
vector optimization), viÕt t¾t PSVO, ®îc ®Þnh nghÜa nh sau:
Cho kh«ng gian tham
P:= C[Ω,Rs]×C[Ω ×T, Rm]×C[T, Rm].
Víi
mçi tham
p:= (f, g, b)P
, ta xÐt bµi to¸n tèi u vÐct¬ nöa h¹n
(SVO)p: minRs
+f(x)
víi rµng buéc
xC(p),
(1.1.1)
ë ®©y
C(p) := {x|g(x, t)b(t) Rm
+tT}
(1.1.2)
tËp rµng buéc
Rk
+:= {x= (x1, ..., xk)Rk|xi0i= 1, ..., k}, k = 1,2, ...
hiÖu cho tËp c¸c vÐct¬ kh«ng ©m cña
Rk.
¸
nh ®a trÞ
C:P
, g¸n mçi ®iÓm
pP
víi tËp
C(p)
ë trong (1.1.2),
®îc i
¸nh tËp rµng buéc
cña bµi to¸n (PSVO).
Xuyªn suèt luËn ¸n nµy, ta hiÖu phÇn trong t«p« bao ®ãng t«p« cña
tËp con
A
cña mét kh«ng gian t«p«
Y
t¬ng øng
intA
clA
. hiÖu
N(y)
®îc ng ®Ó chØ tËp tÊt c¸c l©n cËn cña
yY
.
3