
Më ®Çu
Bµi to¸n tèi u vÐct¬ d¹ng chuÈn lµ bµi to¸n t×m cùc trÞ mét hµm
f:X→Y
,
ë ®ã
X
vµ
Y
lµ c¸c kh«ng gian vÐct¬ t«p«, díi mét sè rµng buéc. Kh¸i niÖm
cùc trÞ ë ®©y ®îc x¸c ®Þnh theo mét thø tù bé phËn trong kh«ng gian
Y
. Thø tù
nµy thêng ®îc ®Þnh nghÜa qua mét nãn låi
K⊂Y
:
y1Ky2⇔y2−y1∈K.
Nh vËy, bµi to¸n tèi u vÐct¬ lµ sù më réng cña bµi to¸n quy ho¹ch to¸n häc,
ë ®ã
Y=R
vµ
K=R+
.
Tèi u vÐct¬ (Vector optimization) ra ®êi vµo cuèi thÕ kû 19, víi kh¸i niÖm
nghiÖm ®îc ®Ò xuÊt bëi F. Y. Edgeworth (1881) vµ V. Pareto (1896). M« h×nh
bµi to¸n tèi u vÐct¬ cho phÐp nghiªn cøu mét sè vÊn ®Ò vÒ phóc lîi x· héi
(social welfare) vµ c©n b»ng kinh tÕ (economic equilibrium). Ngoµi ra, m« 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 kÕ kÜ thuËt, m«i trêng, tµi chÝnh,... Tèi u vÐct¬ lµ mét bé
phËn quan träng cña Lý thuyÕt 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 vµ
A. W. Tucker (1951) vÒ c¸c ®iÒu kiÖn cÇn vµ ®ñ cho mét vÐct¬ tháa c¸c rµng
buéc lµ nghiÖm h÷u hiÖu. §Õn nay, ®· cã rÊt nhiÒu cuèn s¸ch chuyªn kh¶o vÒ
Tèi u vÐct¬ vµ øng dông: M. Ehrgott (2005), J. Jahn (2004), D. T. Luc (1989),
Y. Sawaragi, H. Nakayama vµ T. Tanino (1985), R. E. Steuer (1986), M. Zeleny
(1982),...
Bªn c¹nh sù tån t¹i nghiÖm, ®iÒu cÇn vµ ®ñ cùc trÞ, tÝnh chÊt cña tËp nghiÖm
vµ c¸c thuËt to¸n t×m nghiÖm,
tÝnh æn ®Þnh nghiÖm
(solution stability/stability
analysis) vµ
®é nh¹y nghiÖm
(solution sensitivity/sensitivity analysis) lµ nh÷ng
vÊn ®Ò c¬ b¶n cña lý thuyÕt Tèi u vÐct¬ vµ øng dông.
Nghiªn cøu tÝnh æn ®Þnh nghiÖm tøc lµ kh¶o s¸t c¸c tÝnh chÊt liªn tôc cña
¸nh x¹ nghiÖm h÷u hiÖu hoÆc hµm gi¸ trÞ tèi u theo tham sè 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, vµ 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 vµ Y. Sawaragi (1980). Mét sè kÕt
qu¶ tæng qu¸t h¬n vÒ tÝnh æn ®Þnh cña c¸c bµi to¸n tèi u vÐct¬ cã trong c¸c
cuèn s¸ch chuyªn kh¶o cña Luc vµ cña Sawaragi, Nakayama vµ Tanino võa
®îc trÝch dÉn ë trªn. TÝnh liªn tôc Lipschitz-H
¨o
lder cña ¸nh x¹ nghiÖm trong
c¸c bµi to¸n tèi u vÐct¬ låi m¹nh phô thuéc tham sè ®· ®î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 vµ N. D. Yen (1998).
Ph©n tÝch ®é nh¹y nghiÖm trong Tèi u vÐct¬ cã nghÜa lµ tÝnh to¸n ®¹o hµm
(theo nghÜa cæ ®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 x¹ nghiÖm h÷u hiÖu hoÆc hµm
1