ĐẠ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 fioan
T«i xin cam fioan r»ng c‚c k(cid:213)t qu¶ nghi“n cłu trong lu¸n v¤n n(cid:181)y l(cid:181) trung
thøc v(cid:181) kh«ng tr(cid:239)ng l˘p v(cid:237)i c‚c fi(cid:210) t(cid:181)i kh‚c. T«i c(cid:242)ng xin cam fioan r»ng m(cid:228)i sø
gi(cid:243)p fi(cid:236) cho vi(cid:214)c thøc hi(cid:214)n lu¸n v¤n n(cid:181)y fi• fi›(cid:238)c c¶m ‹n v(cid:181) c‚c th«ng tin tr(cid:221)ch
d(cid:201)n trong lu¸n v¤n fi• fi›(cid:238)c ch(cid:216) r(cid:226) ngu(cid:229)n gŁc.
Th‚i Nguy“n, th‚ng 4 n¤m 2015
Ng›Œi vi(cid:213)t lu¸n v¤n
Tr˙n Th(cid:222) Nh(cid:181)n
ii
LŒi c¶m ‹n
Lu¸n v¤n fi›(cid:238)c thøc hi(cid:214)n v(cid:181) ho(cid:181)n th(cid:181)nh t„i tr›Œng §„i h(cid:228)c s› ph„m - §„i h(cid:228)c
Th‚i Nguy“n d›(cid:237)i sø h›(cid:237)ng d(cid:201)n khoa h(cid:228)c cæa PGS. TS. §(cid:231) V¤n L›u. Qua fi'y,
t‚c gi¶ xin fi›(cid:238)c g(cid:246)i lŒi c¶m ‹n s'u s(cid:190)c fi(cid:213)n th˙y gi‚o, ng›Œi h›(cid:237)ng d(cid:201)n khoa
h(cid:228)c cæa m(cid:215)nh, PGS. TS. §(cid:231) V¤n L›u, ng›Œi fi• t¸n t(cid:215)nh h›(cid:237)ng d(cid:201)n trong suŁt
qu‚ tr(cid:215)nh nghi“n cłu cæa t‚c gi¶. §(cid:229)ng thŒi t‚c gi¶ c(cid:242)ng ch'n th(cid:181)nh c¶m ‹n c‚c
th˙y c« trong khoa To‚n, khoa Sau fi„i h(cid:228)c - Tr›Œng §„i h(cid:228)c s› ph„m, §„i h(cid:228)c
Th‚i Nguy“n, fi• t„o m(cid:228)i fii(cid:210)u ki(cid:214)n fi(cid:211) t‚c gi¶ ho(cid:181)n th(cid:181)nh b¶n lu¸n v¤n n(cid:181)y. T‚c
gi¶ c(cid:242)ng g(cid:246)i lŒi c¶m ‹n fi(cid:213)n gia fi(cid:215)nh v(cid:181) c‚c b„n trong l(cid:237)p Cao h(cid:228)c To‚n K21b,
fi• fiØng vi“n gi(cid:243)p fi(cid:236) t‚c gi¶ trong qu‚ tr(cid:215)nh h(cid:228)c t¸p v(cid:181) l(cid:181)m lu¸n v¤n.
Lu¸n v¤n kh«ng th(cid:211) tr‚nh khÆi nh(cid:247)ng thi(cid:213)u sªt, t‚c gi¶ r˚t mong nh¸n fi›(cid:238)c
sø ch(cid:216) b¶o t¸n t(cid:215)nh cæa c‚c th˙y c« v(cid:181) b„n b(cid:204) fi(cid:229)ng nghi(cid:214)p.
Th‚i Nguy“n, th‚ng 4 n¤m 2015
Ng›Œi vi(cid:213)t lu¸n v¤n
Tr˙n Th(cid:222) Nh(cid:181)n
iii
M(cid:244)c l(cid:244)c
LŒi cam fioan i
LŒi c¶m ‹n ii
M(cid:244)c l(cid:244)c iii
Mº fi˙u 1
3 1 §i(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u y(cid:213)u
3 . . . . . . . . 1.1 C‚c ki(cid:213)n thłc b(cid:230) tr(cid:238) . . . . . . . . . . . . . . . .
3 . . . . . . . . 1.1.1. D›(cid:237)i vi ph'n suy rØng . . . . . . . . . . . .
7 1.1.2. C‚c d›(cid:237)i vi ph'n Clarke-Rockafellar, Clarke, Michel-Penot
1.1.3. D›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy, d›(cid:237)i vi ph'n suy rØng tŁi
. . . . . . . . 10 thi(cid:211)u . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 13 1.2 §i(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u Pareto y(cid:213)u .
2 §i(cid:210)u ki(cid:214)n ch(cid:221)nh quy v(cid:181) fii(cid:210)u ki(cid:214)n tŁi ›u Karush-Kuhn-Tucker 24
. . 2.1 §i(cid:210)u ki(cid:214)n ch(cid:221)nh quy v(cid:181) fii(cid:210)u ki(cid:214)n c˙n Karush-Kuhn-Tucker . . 24
. . . . . . . . 28 2.2 §i(cid:210)u ki(cid:214)n fiæ cho cøc ti(cid:211)u Pareto y(cid:213)u . . . . . . . .
. . . . . . . . 30 K(cid:213)t lu¸n . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 31 T(cid:181)i li(cid:214)u tham kh¶o . . . . . . . . . . . . . . . . . . .
1
Mº fi˙u
1. L(cid:253) do ch(cid:228)n lu¸n v¤n
N¤m 1994, Demyanov [5] fi• fi›a ra kh‚i ni(cid:214)m d›(cid:237)i vi ph'n suy rØng comp¤c
l(cid:229)i. Kh‚i ni(cid:214)m n(cid:181)y l(cid:181) mØt t(cid:230)ng qu‚t ho‚ cæa kh‚i ni(cid:214)m l(cid:229)i tr“n v(cid:181) l(cid:226)m d›(cid:237)i (xem
[6]). C‚c kh‚i ni(cid:214)m d›(cid:237)i vi ph'n suy rØng fiªng, kh«ng l(cid:229)i v(cid:181) Jacobian x˚p x(cid:216)
fi›(cid:238)c fi(cid:210) xu˚t bºi Jeyakumar v(cid:181) Luc trong [9] v(cid:181) [10]. Kh‚i ni(cid:214)m d›(cid:237)i vi ph'n
suy rØng l(cid:181) t(cid:230)ng qu‚t ho‚ cæa mØt sŁ c‚c kh‚i ni(cid:214)m d›(cid:237)i vi ph'n fi• bi(cid:213)t cæa
Clarke [4], Michel-Penot [17], Mordukhovich [18]. MØt fii(cid:210)u ki(cid:214)n c˙n Fritz John
cho cøc ti(cid:211)u y(cid:213)u cæa b(cid:181)i to‚n quy ho„ch fia m(cid:244)c ti“u d›(cid:237)i ng«n ng(cid:247) Jacobian
x˚p x(cid:216) fi›(cid:238)c fi›a ra bºi Luc [12]. §i(cid:210)u ki(cid:214)n c˙n tŁi ›u Fritz John cho cøc ti(cid:211)u
y(cid:213)u d›(cid:237)i ng«n ng(cid:247) d›(cid:237)i vi ph'n suy rØng fi›(cid:238)c fi›a ra bºi Dutta- Chandra [7,8]
cho b(cid:181)i to‚n tŁi ›u fia m(cid:244)c ti“u v(cid:237)i c‚c r(cid:181)ng buØc b˚t fi…ng thłc. §i(cid:210)u ki(cid:214)n c˙n
cho cøc ti(cid:211)u y(cid:213)u v(cid:181) cøc ti(cid:211)u Pareto fi›(cid:238)c fi›a ra bºi Luu [15] v(cid:237)i c‚c r(cid:181)ng buØc
fi…ng thłc, b˚t fi…ng thłc v(cid:181) r(cid:181)ng buØc t¸p.
Døa tr“n fi(cid:222)nh l(cid:221) Ljusternik mº rØng cæa Jim—nez-Novo (2002), D.V.Luu
(2014) fi• thi(cid:213)t l¸p c‚c fii(cid:210)u ki(cid:214)n tŁi ›u cho cøc ti(cid:211)u Pareto y(cid:213)u cæa b(cid:181)i to‚n
tŁi ›u fia m(cid:244)c ti“u cª r(cid:181)ng buØc fi…ng thłc, b˚t fi…ng thłc v(cid:181) r(cid:181)ng buØc t¸p d›(cid:237)i
ng«n ng(cid:247) d›(cid:237)i vi ph'n suy rØng (convexificator). §'y l(cid:181) fi(cid:210) t(cid:181)i fiang fi›(cid:238)c nhi(cid:210)u
t‚c gi¶ trong v(cid:181) ngo(cid:181)i n›(cid:237)c quan t'm nghi“n cłu. Ch(cid:221)nh v(cid:215) th(cid:213) em ch(cid:228)n fi(cid:210) t(cid:181)i :
(cid:147)§i(cid:210)u ki(cid:214)n c˙n v(cid:181) fiæ cho nghi(cid:214)m h(cid:247)u hi(cid:214)u cæa b(cid:181)i to‚n tŁi ›u fia m(cid:244)c ti“u qua
d›(cid:237)i vi ph'n suy rØng(cid:148).
2. Ph›‹ng ph‚p nghi“n cłu
2
S›u t˙m v(cid:181) fi(cid:228)c t(cid:181)i li(cid:214)u tı c‚c s‚ch, t„p ch(cid:221) to‚n h(cid:228)c trong n›(cid:237)c v(cid:181) quŁc t(cid:213)
li“n quan fi(cid:213)n fii(cid:210)u ki(cid:214)n tŁi ›u cho b(cid:181)i to‚n tŁi ›u v—c t‹. Qua fiª, t(cid:215)m hi(cid:211)u v(cid:181)
nghi“n cłu v(cid:210) v˚n fi(cid:210) n(cid:181)y.
3. M(cid:244)c fi(cid:221)ch cæa lu¸n v¤n
Lu¸n v¤n tr(cid:215)nh b(cid:181)y c‚c fii(cid:210)u ki(cid:214)n c˙n v(cid:181) fiæ cho nghi(cid:214)m h(cid:247)u hi(cid:214)u d›(cid:237)i ng«n
ng(cid:247) d›(cid:237)i vi ph'n suy rØng trong b(cid:181)i b‚o cæa D. V. L›u fi¤ng trong t„p ch(cid:221) 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(cid:229)m ph˙n mº fi˙u, 2 ch›‹ng, k(cid:213)t lu¸n v(cid:181) danh m(cid:244)c c‚c t(cid:181)i li(cid:214)u
tham kh¶o
Ch›‹ng 1: §i(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u y(cid:213)u
Tr(cid:215)nh b(cid:181)y mØt sŁ ki(cid:213)n thłc c‹ b¶n v(cid:210) d›(cid:237)i vi ph'n suy rØng v(cid:181) fii(cid:210)u ki(cid:214)n c˙n
Fritz John cho cøc ti(cid:211)u Pareto y(cid:213)u cæa b(cid:181)i to‚n tŁi ›u fia m(cid:244)c ti“u cª r(cid:181)ng buØc
fi…ng thłc, b˚t fi…ng thłc v(cid:181) r(cid:181)ng buØc t¸p v(cid:237)i c‚c h(cid:181)m Lipschitz fi(cid:222)a ph›‹ng.
Ch›‹ng 2: §i(cid:210)u ki(cid:214)n ch(cid:221)nh quy v(cid:181) fii(cid:210)u ki(cid:214)n tŁi ›u Karush-Kuhn-Tucker
Tr(cid:215)nh b(cid:181)y c‚c fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy v(cid:181) fii(cid:210)u ki(cid:214)n c˙n Karush-Kuhn-Tucker cho
b(cid:181)i to‚n tŁi ›u fia m(cid:244)c ti“u cª r(cid:181)ng buØc fi…ng thłc, b˚t fi…ng thłc v(cid:181) r(cid:181)ng buØc
t¸p v(cid:237)i c‚c h(cid:181)m Lipschitz fi(cid:222)a ph›‹ng d›(cid:237)i ng«n ng(cid:247) d›(cid:237)i vi ph'n suy rØng v(cid:237)i
c‚c gi¶ thi(cid:213)t v(cid:210) t(cid:221)nh l(cid:229)i suy rØng, c‚c fii(cid:210)u ki(cid:214)n c˙n tŁi ›u trº th(cid:181)nh c‚c fii(cid:210)u ki(cid:214)n
fiæ tŁi ›u.
3
Ch›‹ng 1
§i(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u y(cid:213)u
Trong ch›‹ng 1 ch(cid:243)ng t«i tr(cid:215)nh b(cid:181)y mØt sŁ ki(cid:213)n thłc c‹ b¶n v(cid:210) d›(cid:237)i vi ph'n
suy rØng v(cid:181) fii(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u Pareto y(cid:213)u cæa b(cid:181)i to‚n tŁi ›u
fia m(cid:244)c ti“u cª r(cid:181)ng buØc fi…ng thłc, b˚t fi…ng thłc v(cid:181) r(cid:181)ng buØc t¸p d›(cid:237)i ng«n
ng(cid:247) d›(cid:237)i vi ph'n suy rØng. C‚c k(cid:213)t qu¶ tr(cid:215)nh b(cid:181)y trong ch›‹ng n(cid:181)y fi›(cid:238)c tham
kh¶o trong [9], [14].
1.1 C‚c ki(cid:213)n thłc b(cid:230) tr(cid:238)
1.1.1. D›(cid:237)i vi ph'n suy rØng
inf
,
f −(¯x; v) := lim t↓0
f (x + tv) − f (¯x) t
Cho f l(cid:181) h(cid:181)m gi‚ tr(cid:222) thøc mº rØng fi›(cid:238)c x‚c fi(cid:222)nh tr“n Rn. Nh(cid:190)c l„i r»ng fi„o h(cid:181)m theo ph›‹ng Dini d›(cid:237)i v(cid:181) tr“n f − v(cid:181) f + cæa f t„i ¯x ∈ Rn theo ph›‹ng v ∈ Rn fi›(cid:238)c x‚c fi(cid:222)nh nh› sau:
sup
.
f +(¯x; v) := lim t↓0
f (¯x + tv) − f (¯x) t
(cid:18) (cid:19)
N(cid:213)u f +(¯x; v) = f −(¯x; v), th(cid:215) gi‚ tr(cid:222) chung fiª fi›(cid:238)c g(cid:228)i l(cid:181) fi„o h(cid:181)m cæa h(cid:181)m f t„i ¯x theo ph›‹ng v v(cid:181) k(cid:253) hi(cid:214)u l(cid:181) f (cid:48)(¯x; v). H(cid:181)m f g(cid:228)i l(cid:181) kh¶ vi theo ph›‹ng
t„i ¯x n(cid:213)u t(cid:229)n t„i fi„o h(cid:181)m theo ph›‹ng cæa nª t„i ¯x theo m(cid:228)i ph›‹ng. N(cid:213)u f l(cid:181) kh¶ vi Fr—chet t„i ¯x v(cid:237)i fi„o h(cid:181)m Fr—chet ∇f (¯x) th(cid:215) f (cid:48)(¯x; v) = (cid:104)∇f (¯x, v)(cid:105) .
4
∂∗f (¯x)) t„i ¯x ∈ Rn n(cid:213)u ∂∗f (¯x) (hay (∂∗f (¯x)) ⊆ Rn) l(cid:181) t¸p fiªng v(cid:181)
f −(¯x; v) ≤ sup
(cid:104)ξ, v(cid:105)
(∀v ∈ Rn),
ξ∈∂∗f (¯x)
Theo [9] h(cid:181)m f fi›(cid:238)c g(cid:228)i l(cid:181) cª d›(cid:237)i vi ph'n suy rØng tr“n ∂∗f (¯x) (hay d›(cid:237)i
f +(¯x; v) ≥ inf
(cid:104)ξ, v(cid:105)
(∀v ∈ Rn)
.
ξ∈∂∗f (¯x)
(cid:18) (cid:19)
MØt t¸p fiªng ∂∗f (¯x) ⊆ Rn fi›(cid:238)c g(cid:228)i l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng cæa f t„i ¯x n(cid:213)u ∂∗f (¯x) fi(cid:229)ng thŒi l(cid:181) d›(cid:237)i vi ph'n suy rØng tr“n v(cid:181) d›(cid:237)i cæa f t„i ¯x .
∂∗f (¯x) ⊆ Rn t„i ¯x n(cid:213)u ∂∗f (¯x) l(cid:181) t¸p fiªng v(cid:181)
f +(¯x; v) ≤ sup
(cid:104)ξ, v(cid:105)
(∀v ∈ Rn).
Theo [8] h(cid:181)m f fi›(cid:238)c g(cid:228)i l(cid:181) cª d›(cid:237)i vi ph'n suy rØng b‚n ch(cid:221)nh quy tr“n
ξ∈∂∗f (¯x)
(1.1)
f (x) :=
x, x4 − 4x3 + 4x2,
V(cid:221) d(cid:244) 1.1.1 Cho h(cid:181)m f : R → R fi›(cid:238)c x‚c fi(cid:222)nh bºi
khi x ∈ Q ∩ [0; +∞[, khi x ∈ Q ∩ ]−∞; 0],
0,
trong c‚c tr›Œng h(cid:238)p kh‚c,
v,
trong fiª Q l(cid:181) t¸p c‚c sŁ h(cid:247)u tß. Khi fiª
f +(0; v) =
0,
khi v ≥ 0,
f −(0; v) = 0 (∀v ∈ R).
khi v < 0,
T¸p {0; 1} l(cid:181) d›(cid:237)i vi ph'n suy rØng b‚n ch(cid:221)nh quy tr“n cæa f t„i ¯x, cho n“n
nª c(cid:242)ng l(cid:181) d›(cid:237)i vi ph'n suy rØng tr“n cæa f t„i ¯x. T¸p {0} l(cid:181) d›(cid:237)i vi ph'n suy
rØng d›(cid:237)i cæa f t„i ¯x.
Theo [9], n(cid:213)u x¶y ra fi…ng thłc trong (1.1) th(cid:215) ∂∗f (¯x) fi›(cid:238)c g(cid:228)i l(cid:181) d›(cid:237)i vi
ph'n suy rØng ch(cid:221)nh quy tr“n. V(cid:237)i mØt h(cid:181)m Lipschitz fi(cid:222)a ph›‹ng, d›(cid:237)i vi ph'n
5
¯x (xem [9]). H‹n n(cid:247)a v(cid:237)i mØt h(cid:181)m Lipschitz fi(cid:222)a ph›‹ng ch(cid:221)nh quy trong theo
Clarke v(cid:181) d›(cid:237)i vi ph'n Michel-Penot l(cid:181) nh(cid:247)ng d›(cid:237)i vi ph'n suy rØng cæa f t„i
ngh(cid:220)a Clarke [4], d›(cid:237)i vi ph'n Clarke l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy
tr“n (xem [7]). Ch(cid:243) (cid:253) r»ng, n(cid:213)u h(cid:181)m f cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy
tr“n t„i ¯x th(cid:215) nª c(cid:242)ng l(cid:181) d›(cid:237)i vi ph'n suy rØng b‚n ch(cid:221)nh quy tr“n t„i ¯x, v(cid:181) do
fiª nª fi›(cid:238)c l(cid:181) d›(cid:237)i vi ph'n suy rØng tr“n t„i ¯x.
V(cid:221) d(cid:244) 1.1.2 Ta x—t h(cid:181)m f : R → R fi›(cid:238)c x‚c fi(cid:222)nh bºi:
f (x) =
x2 (cid:12) 0,
khi x (cid:54)= 0, (cid:12) (cid:12) , (cid:12)cos π x
khi x = 0.
Ta cª f +(0; v) = f −(0; v) = 0, (∀v ∈ R). D›(cid:237)i vi ph'n Clarke v(cid:181) Michile-
{−π; π} l(cid:181) c‚c d›(cid:237)i vi ph'n suy rØng cæa f t„i ¯x. T¸p {0} l(cid:181) d›(cid:237)i vi ph'n suy
Penot cæa f t„i ¯x = 0 t›‹ng łng l(cid:181) [−π; π] v(cid:181) {0}. C‚c t¸p {0}, [−π; π] v(cid:181)
rØng ch(cid:221)nh quy tr“n cæa f t„i ¯x.
Theo [16] mØt h(cid:181)m gi‚ tr(cid:222) thøc mº rØng f x‚c fi(cid:222)nh tr“n t¸p Q ⊆ Rn fi›(cid:238)c
f (x) ≤ f (¯x) ⇒ ∀t ∈ ]0, 1[ ,
f (tx + (1 − t)¯x) ≤ f (¯x).
f fi›(cid:238)c g(cid:228)i l(cid:181) tøa l(cid:229)i tr“n Q n(cid:213)u f l(cid:181) tøa l(cid:229)i t„i m(cid:231)i x ∈ Q. f g(cid:228)i l(cid:181) tøa tuy(cid:213)n
g(cid:228)i l(cid:181) tøa l(cid:229)i t„i ¯x ∈ Q theo Q n(cid:213)u v(cid:237)i m(cid:231)i x ∈ Q,
t(cid:221)nh t„i ¯x ∈ Q theo Q n(cid:213)u ±f l(cid:181) tøa l(cid:229)i t„i ¯x theo Q.
Trong [20] Yang ch(cid:216) ra r»ng, n(cid:213)u f l(cid:181) li“n t(cid:244)c, tøa l(cid:229)i v(cid:181) cª mØt d›(cid:237)i vi ph'n
(ξ(n), x − y) ≤ 0.
f (x) ≤ f (y) ⇒ ∃ξ(n) ∈ ∂∗f (y),
lim n→∞
suy rØng d›(cid:237)i l(cid:229)i tr“n mØt t¸p l(cid:229)i Q th(cid:215) v(cid:237)i m(cid:231)i x, y ∈ Q,
N(cid:213)u f cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n t„i ¯x th(cid:215) ta cª m(cid:214)nh fi(cid:210) sau
fi'y.
M(cid:214)nh fi(cid:210) 1.1.1 Gi¶ s(cid:246) f cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n ∂∗f (¯x) t„i ¯x v(cid:181) f tøa l(cid:229)i
6
∀x ∈ Q, f (x) ≤ f (¯x) ⇒ ∀ξ ∈ ∂∗f (¯x), (cid:104)ξ, x − ¯x(cid:105) ≤ 0.
t„i ¯x ∈ Q theo t¸p l(cid:229)i Q. Khi fiª,
Chłng minh
f +(¯x; x − ¯x) ≤ 0.
V(cid:215) f l(cid:181) tøa l(cid:229)i t„i ¯x theo Q, v(cid:237)i m(cid:231)i x ∈ Q thÆa m•n f (x) ≤ f (¯x), ta cª
Do t(cid:221)nh ch(cid:221)nh quy tr“n cæa d›(cid:237)i vi ph'n suy rØng ∂∗f (¯x), v(cid:237)i m(cid:231)i x ∈ Q thÆa
(cid:104)ξ, x − ¯x(cid:105) = f +(¯x; x − ¯x) ≤ 0.
sup ξ∈∂∗f (¯x)
(cid:50)
m•n f (x) ≤ f (¯x), ta cª
Tı fiª, ta cª fii(cid:210)u ph¶i chłng minh.
Theo [20], h(cid:181)m thøc mº rØng f cª mØt d›(cid:237)i vi ph'n suy rØng d›(cid:237)i l(cid:229)i ∂∗f (x)
tr“n Q fi›(cid:238)c g(cid:228)i l(cid:181) gi¶ l(cid:229)i ti(cid:214)m c¸n d›(cid:237)i tr“n Q n(cid:213)u v(cid:237)i m(cid:231)i x, y ∈ Q,
ξ(n), y − x
≥ 0 ⇒ f (y) ≥ f (x).
∃ξ(n) ∈ ∂∗f (x),
lim n→∞
(cid:68) (cid:69)
H(cid:181)m gi‚ tr(cid:222) thøc mº rØng f cª mØt d›(cid:237)i vi ph'n suy rØng ∂∗f (¯x) t„i ¯x fi›(cid:238)c g(cid:228)i
l(cid:181) gi¶ l(cid:229)i ti(cid:214)m c¸n t„i ¯x theo Q n(cid:213)u, v(cid:237)i m(cid:231)i x ∈ Q ta cª
∃ξ(n) ∈ conv∂∗f (¯x),
ξ(n), x − ¯x
≥ 0 ⇒ f (x) ≥ f (¯x).
lim n→∞
(cid:68) (cid:69)
trong ޻ conv k(cid:221) hi(cid:214)u bao l(cid:229)i
V(cid:221) d(cid:244) 1.1.3 Cho f, g : R → R
f (x) :=
x, khi x ≤ 0, 1 2x, khi x > 0,
x,
g(x) :=
khi x ∈ Q, khi x ∈ (R\Q) ∩ ]−∞, 0] , khi x ∈ (R\Q) ∩ [0, ∞[ .
2x, 1 2x,
7
2; 1(cid:9) v(cid:181) f l(cid:181) gi¶ Khi fiª mØt d›(cid:237)i vi ph'n suy rØng cæa f t„i 0 l(cid:181) ∂∗f (0) = (cid:8) 1 l(cid:229)i ti(cid:214)m c¸n t„i 0 theo Q = R. MØt d›(cid:237)i vi ph'n suy rØng d›(cid:237)i cæa g t„i 0 l(cid:181) ∂∗g(0) = (cid:8) 1 2; 2(cid:9) v(cid:181) g l(cid:181) gi¶ l(cid:229)i ti(cid:214)m c¸n d›(cid:237)i t„i 0 theo Q = R.
K ∗ := {ξ ∈ Rn : (cid:104)ξ, x(cid:105) ≥ 0, ∀x ∈ K}
Cho K l(cid:181) mØt nªn l(cid:229)i fiªng trong Rn v(cid:181)
l(cid:181) nªn cøc kh«ng 'm cæa K. Cho f : Q ⊆ Rn → Rm v(cid:181) nh› v¸y f = (f1, ..., fm). Gi¶ s(cid:246) fk cª mØt d›(cid:237)i vi ph'n suy rØng ∂∗fk (¯x) t„i ¯x. H(cid:181)m f fi›(cid:238)c g(cid:228)i l(cid:181) gi¶ l(cid:229)i K - ti(cid:214)m c¸n v« h›(cid:237)ng t„i ¯x theo Q n(cid:213)u v(cid:237)i m(cid:231)i λ ∈ K ∗, h(cid:181)m λT f l(cid:181) gi¶ l(cid:229)i ti(cid:214)m c¸n t„i ¯x tr“n Q.
C‚c nªn ti(cid:213)p tuy(cid:213)n Bouligand v(cid:181) Clarke cæa t¸p C ⊆ Rn t„i mØt fii(cid:211)m ¯x ∈ C
fi›(cid:238)c fi(cid:222)nh ngh(cid:220)a t›‹ng łng bºi K(C, ¯x) := {v ∈ Rn : ∃ vn → v, ∃ tn ↓ 0 sao cho ¯x + tnvn ∈ C, ∀n} , T (C, ¯x) := {v ∈ Rn : ∀ xn ∈ C, xn → ¯x, ∀ tn ↓ 0 , ∃ vn → v
sao cho xn + tnvn ∈ C, ∀n} .
Nªn c‚c ph›‹ng fi„t fi›(cid:238)c cæa C t„i ¯x ∈ C l(cid:181):
A(C, ¯x) =
v ∈ Rn : ∃δ > 0, ∃γ :
[0, δ] → Rn sao cho
(cid:110)
= v
.
γ(t)−γ(0) t
γ(0) = ¯x, γ(t) ∈ C, ∀t ∈ ]0, δ] , γ,(0) = lim t↓0
(cid:27)
N (C, ¯x) = {ξ ∈ Rn : (cid:104)ξ, v(cid:105) ≤ 0 ∀ v ∈ T (C, ¯x)} .
Nªn ph‚p tuy(cid:213)n Clarke cæa C t„i ¯x l(cid:181)
K(C, ¯x).
1.1.2. C‚c d›(cid:237)i vi ph'n Clarke-Rockafellar, Clarke, Michel-Penot
Ch(cid:243) (cid:253) r»ng c‚c nªn T (C, ¯x) v(cid:181) N (C, ¯x) l(cid:181) kh«ng r(cid:231)ng, fiªng v(cid:181) l(cid:229)i; N (C, ¯x) = −T ∗(C, ¯x) v(cid:181) T (C, ¯x) ⊆ K(C, ¯x). Trong tr›Œng h(cid:238)p C l(cid:229)i th(cid:215) T (C, ¯x) =
Sau fi'y ta sˇ th˚y r»ng c‚c d›(cid:237)i vi ph'n Clarke-Rockafellar, Clarke, Michel-
Penot,...fi(cid:210)u l(cid:181) d›(cid:237)i vi ph'n suy rØng.
8
Cho h(cid:181)m f : Rn → ¯R l(cid:181) h(cid:247)u h„n t„i fii(cid:211)m x ∈ X. N(cid:213)u f l(cid:181) n(cid:246)a li“n t(cid:244)c d›(cid:237)i t„i x th(cid:215) d›(cid:237)i fi„o h(cid:181)m tr“n Clarke - Rockafellar cæa f t„i x theo v fi›(cid:238)c
[f (x(cid:48) + tv(cid:48)) − f (x(cid:48))] /t,
inf v(cid:48)→v
f ↑ (x, v) = lim sup x
x(cid:48) →f t↓0
x‚c fi(cid:222)nh bºi:
trong fiª x(cid:48) → f x ngh(cid:220)a l(cid:181) x(cid:48) → x v(cid:181) f (x(cid:48)) → f (x) .
f t„i x theo v fi›(cid:238)c x‚c fi(cid:222)nh bºi
[f (x(cid:48) + tv(cid:48)) − f (x(cid:48))] /t.
f ↓ (x, v) = lim inf f x
sup v(cid:48)→v
x(cid:48) → t↓0
N(cid:213)u f l(cid:181) n(cid:246)a li“n t(cid:244)c tr“n t„i x th(cid:215) d›(cid:237)i fi„o h(cid:181)m d›(cid:237)i Clarke-Rockafellar cæa
∂↑f (x) = (cid:8)x∗ ∈ X ∗ : (cid:104)x∗, v(cid:105) ≤ f ↑ (x, v) , ∀v ∈ X(cid:9) ,
∂↓f (x) = (cid:8)x∗ ∈ X ∗ : (cid:104)x∗, v(cid:105) ≥ f ↓ (x, v) , ∀v ∈ X(cid:9) .
N(cid:213)u f l(cid:181) li“n t(cid:244)c t„i x th(cid:215) x(cid:48) → f x trong c‚c fi(cid:222)nh ngh(cid:220)a tr“n trº th(cid:181)nh x(cid:48) → x. D›(cid:237)i gradient suy rØng tr“n v(cid:181) d›(cid:237)i cæa f t„i x fi›(cid:238)c cho bºi
f ↑ (x, v) = sup
(cid:104)x∗, v(cid:105) .
x∗∈ ∂↑f (x)
N(cid:213)u f ↑ (x, 0) > −∞ th(cid:215) ∂↑f (x) l(cid:181) t¸p con kh«ng r(cid:231)ng, l(cid:229)i, fiªng cæa Rn v(cid:181) v(cid:237)i m(cid:231)i v ∈ Rn,
(cid:104)x∗, v(cid:105) .
f ↓ (x, v) = inf
x∗∈ ∂↓f (x)
T›‹ng tø, n(cid:213)u f ↓ (x, 0) < ∞ th(cid:215) ∂↓f (x) l(cid:181) t¸p con kh«ng r(cid:231)ng, l(cid:229)i, fiªng cæa Rn v(cid:181) v(cid:237)i m(cid:231)i v ∈ Rn,
f ↑ (x; v) = f o (x, v) , f ↓ (x; v) = fo (x, v) ,
N(cid:213)u f l(cid:181) Lipschitz fi(cid:222)a ph›‹ng t„i x th(cid:215)
[f (x(cid:48) + tv) − f (x(cid:48))] /t,
f o (x, v) = lim sup x
x(cid:48) → t↓0
[f (x(cid:48) + tv) − f (x(cid:48))] /t.
fo (x, v) = lim inf x
x(cid:48) → t↓0
trong ޻,
9
v. D›(cid:237)i vi ph'n suy rØng Clarke fi›(cid:238)c x‚c fi(cid:222)nh bºi
∂of (x) = {x∗ ∈ X ∗ : (cid:104)x∗, v(cid:105) ≤ f o (x, v) , ∀v ∈ X} .
l(cid:181) c‚c fi„o h(cid:181)m theo ph›‹ng suy rØng tr“n v(cid:181) d›(cid:237)i Clarke cæa f t„i x theo ph›‹ng
f o (x, v) = max
(cid:104)x∗, v(cid:105) ,
(cid:104)x∗, v(cid:105) .
fo (x, v) = min
x∗∈ ∂of (x)
x∗∈ ∂of (x)
H‹n n(cid:247)a,
Do fiª, n(cid:213)u f l(cid:181) Lipschitz fi(cid:222)a ph›‹ng t„i x th(cid:215) ∂of (x) l(cid:181) d›(cid:237)i vi ph'n suy rØng
f − (x, v) ≤ f o (x, v) ,
f + (x, v) ≥ fo (x, v) .
cæa f t„i x, bºi v(cid:215)
v(cid:237)i m(cid:231)i v ∈ X.
T›‹ng tø, n(cid:213)u f l(cid:181) Lipschitz fi(cid:222)a ph›‹ng t„i x th(cid:215) fi„o h(cid:181)m theo ph›‹ng tr“n v(cid:181)
λ−1 [f (x + λz + λv) − f (x + λz)] ,
f ♦ (x, v) = sup z∈X
lim sup λ↓0
λ−1 [f (x + λz + λv) − f (x + λz)] .
f♦ (x, v) = inf z∈X
lim inf λ↓0 Khi fiª d›(cid:237)i vi ph'n Michel (cid:150) Penot fi›(cid:238)c x‚c fi(cid:222)nh bºi
∂♦f (x) := (cid:8)x∗ ∈ Rn : f ♦ (x, v) ≥ (cid:104)x∗, v(cid:105) , ∀v ∈ Rn(cid:9) .
d›(cid:237)i Michel (cid:150) Penot cæa f t„i x t›‹ng łng fi›(cid:238)c cho bºi
f ♦ (x, v) = max
(cid:104)x∗, v(cid:105) ,
(cid:104)x∗, v(cid:105) .
f♦ (x, v) = min
x∗∈ ∂♦f (x)
x∗∈ ∂♦f (x)
§„o h(cid:181)m theo ph›‹ng tr“n v(cid:181) d›(cid:237)i Michel (cid:150) Penot f ♦ (x, .) v(cid:181) f♦ (x, .) l(cid:181) d›(cid:237)i tuy(cid:213)n t(cid:221)nh, h(cid:247)u h„n, ∂♦f (x) l(cid:181) compact l(cid:229)i
Do fiª, ∂♦f (x) c(cid:242)ng l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng cæa f t„i x, bºi v(cid:215) f − (x, v) ≤ f ♦ (x, v) v(cid:181) f + (x, v) ≥ f♦ (x, v) v(cid:237)i m(cid:231)i v ∈ Rn.
f (x, y) = |x| − |y| .
V(cid:221) d(cid:244) 1.1.4 §(cid:222)nh ngh(cid:220)a f : R2 → R x‚c fi(cid:222)nh bºi
10
∂∗f (0) = {(1, −1) , (−1, 1)} .
Khi ޻
∂♦f (0) = ∂of (0) = co ({(1, 1) , (−1, 1) , (1, −1) , (−1, −1)}) .
l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng cæa f t„i 0. Ta cª
co (∂∗f (0)) ⊆ ∂♦f (0) = ∂of (0) .
1.1.3. D›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy, d›(cid:237)i vi ph'n suy rØng tŁi thi(cid:211)u
Ch(cid:243) (cid:253) r»ng
R(cid:226) r(cid:181)ng tı fi(cid:222)nh ngh(cid:220)a ta th˚y d›(cid:237)i vi ph'n suy rØng tr“n v(cid:181) d›(cid:237)i kh«ng duy
nh˚t. V(cid:215) v¸y trong ph˙n n(cid:181)y ch(cid:243)ng ta sˇ tr(cid:215)nh b(cid:181)y c‚c fii(cid:210)u ki(cid:214)n v(cid:210) t(cid:221)nh duy nh˚t
v(cid:181) tŁi thi(cid:211)u cæa d›(cid:237)i vi ph'n suy rØng tr“n ho˘c d›(cid:237)i. Tr›(cid:237)c ti“n ta tr(cid:215)nh b(cid:181)y
kh‚i ni(cid:214)m d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n v(cid:181) d›(cid:237)i.
∂∗f (x) ⊆ Rn t„i x n(cid:213)u ∂∗f (x) l(cid:181) t¸p fiªng v(cid:181) v(cid:237)i m(cid:231)i v ∈ Rn,
f + (x, v) = sup
(cid:104)x∗, v(cid:105) .
x∗∈∂∗f (x)
H(cid:181)m f : Rn → R fi›(cid:238)c g(cid:228)i l(cid:181) cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n
f − (x, v) = inf
(cid:104)x∗, v(cid:105) .
x∗∈∂∗f (x)
T›‹ng tø, h(cid:181)m f fi›(cid:238)c g(cid:228)i l(cid:181) cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy d›(cid:237)i ∂∗f (x) ⊆ Rn t„i x n(cid:213)u ∂∗f (x) l(cid:181) t¸p fiªng v(cid:181) v(cid:237)i m(cid:231)i v ∈ Rn.
R(cid:226) r(cid:181)ng, m(cid:231)i d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n (d›(cid:237)i) cæa f t„i x l(cid:181) mØt
d›(cid:237)i vi ph'n suy rØng cæa f t„i x.
Trong m(cid:214)nh fi(cid:210) sau ch(cid:243)ng ta sˇ tr(cid:215)nh b(cid:181)y mŁi li“n h(cid:214) gi(cid:247)a t(cid:221)nh kh¶ vi v(cid:181) t(cid:221)nh
ch(cid:221)nh quy.
M(cid:214)nh fi(cid:210) 1.1.2 H(cid:181)m f : Rn → R l(cid:181) kh¶ vi G'teaux t„i x0 n(cid:213)u v(cid:181) ch(cid:216) n(cid:213)u f l(cid:181) kh¶ vi theo ph›‹ng t„i x0 v(cid:181) f cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n v(cid:181) ch(cid:221)nh quy
11
d›(cid:237)i t„i x0.
Chłng minh
(cid:104)x∗, v(cid:105)
f (cid:48) (x0, v) = f − (x0, v) = inf
x∗∈∂∗f (x)
(cid:104)x∗, v(cid:105) .
= f + (x0, v) = sup
x∗∈∂∗f (x)
(cid:50)
N(cid:213)u f l(cid:181) kh¶ vi G'teaux t„i x0 th(cid:215) nª kh¶ vi theo ph›‹ng v(cid:181) fi„o h(cid:181)m G'teaux {f (cid:48) (x0)} v(cid:181) l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n v(cid:181) d›(cid:237)i cæa f t„i x0. Ng›(cid:238)c l„i, n(cid:213)u f kh¶ vi theo ph›‹ng t„i x0 v(cid:181) n(cid:213)u ∂∗f (x0) l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n v(cid:181) d›(cid:237)i th(cid:215) v(cid:237)i m(cid:231)i v ∈ Rn.
Do fiª ∂∗f (x0) l(cid:181) t¸p mØt ph'n t(cid:246) v(cid:181) v(cid:215) v¸y f kh¶ vi G'teaux t„i x0.
Ta nªi r»ng ∂∗f (x) l(cid:181) d›(cid:237)i vi ph'n suy rØng tŁi thi(cid:211)u (tr“n/d›(cid:237)i) cæa f t„i x
n(cid:213)u kh«ng t(cid:229)n t„i mØt t¸p fiªng C (x) trong Rn sao cho C (x) ⊂ ∂∗f (x) , C (x) (cid:54)= ∂∗f (x) v(cid:181) C (x) l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng (tr“n/d›(cid:237)i) cæa f t„i x.
x l(cid:181) Ext (∂∗f (x)).
K(cid:253) hi(cid:214)u t¸p c‚c fii(cid:211)m cøc bi“n cæa d›(cid:237)i vi ph'n suy rØng ∂∗f (x) cæa f t„i
M(cid:214)nh fi(cid:210) 1.1.3 Gi¶ s(cid:246) r»ng f : Rn → R cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy comp¤c tr“n (d›(cid:237)i) ∂∗f (x) t„i x. Khi fiª Ext (co (∂∗f (x))) l(cid:181) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh
quy tr“n (d›(cid:237)i) tŁi thi(cid:211)u duy nh˚t cæa f t„i x.
(cid:104)x∗, v(cid:105) .
f + (x, v) = sup
(cid:104)x∗, v(cid:105) = sup x∗∈A
x∗∈∂∗f (x)
Chłng minh Cho A ⊂ Rn cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n cæa f t„i x. Khi fiª, v(cid:237)i m(cid:231)i v ∈ Rn,
co (∂∗f (x)) = co (A) .
N“n A l(cid:181) t¸p con fiªng v(cid:181) b(cid:222) ch˘n cæa Rn v(cid:237)i
Ext (co (∂∗f (x))) = Ext (co (A)) .
Khi ޻,
12
Ext (co (∂∗f (x))) ⊆ A.
Ch(cid:243)ng ta ch(cid:216) ra r»ng
Ext (co (A)) ⊆ Ext (A) .
Th¸t v¸y hi(cid:211)n nhi“n ta cª
Ext (co (∂∗f (x))) = Ext (co (A)) ⊆ Ext (A) ⊂ A.
Do ޻,
Ext (co (∂∗f (x))) ⊆ A.
Bºi v(cid:215) A l(cid:181) t¸p fiªng, ta cª
M˘t kh‚c bºi v(cid:215), ∂∗f (x) l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy comp¤c tr“n,
cho n“n Ext (co (∂∗f (x))) c(cid:242)ng l(cid:181) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy comp¤c
tr“n cæa f t„i x. Do fiª, Ext (co (∂∗f (x))) l(cid:181) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy
tŁi thi(cid:211)u tr“n duy nh˚t cæa f t„i x. Chłng minh t›‹ng tø cho tr›Œng h(cid:238)p f cª (cid:50) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy d›(cid:237)i.
v ∈ Rn,
f + (x, v) = f ↑ (x, v) .
Ta nªi h(cid:181)m f h(cid:247)u h„n v(cid:181) li“n t(cid:244)c t„i x l(cid:181) ch(cid:221)nh quy tr“n t„i x n(cid:213)u v(cid:237)i m(cid:231)i
f − (x, v) = f ↓ (x, v) .
T›‹ng tø h(cid:181)m f l(cid:181) ch(cid:221)nh quy d›(cid:237)i t„i x n(cid:213)u v(cid:237)i m(cid:231)i v ∈ Rn,
f + (x, v) = f o (x, v) = f ↑ (x, v) (cid:2)f − (x, v) = fo (x, v) = f ↓ (x, v)(cid:3) ,
Ch(cid:243) (cid:253) r»ng, n(cid:213)u f : Rn → R l(cid:181) Lipschitz fi(cid:222)a ph›‹ng tr“n Rn v(cid:181) n(cid:213)u v(cid:237)i m(cid:231)i v ∈ Rn, f + (., v) [f − (., v)] l(cid:181) n(cid:246)a li“n t(cid:244)c tr“n [d›(cid:237)i], th(cid:215) v(cid:237)i m(cid:231)i x ∈ Rn v(cid:181) v ∈ Rn,
cho n“n, f l(cid:181) ch(cid:221)nh quy tr“n [d›(cid:237)i] t„i x (xem [6]).
N(cid:213)u f ↑ (x, 0) > −∞ v(cid:181) n(cid:213)u f l(cid:181) ch(cid:221)nh quy tr“n t„i x th(cid:215) ∂↑f (x) kh‚c r(cid:231)ng,
(cid:104)x∗, v(cid:105) .
f + (x, v) = f ↑ (x, v) = sup
x∗∈∂↑f (x)
l(cid:229)i, fiªng cæa Rn v(cid:181) v(cid:237)i m(cid:231)i v ∈ Rn,
13
f − (x, v) = f ↓ (x, v) = inf
(cid:104)x∗, v(cid:105) .
x∗∈∂↓f (x)
Do fiª, ∂↑f (x) l(cid:181) mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n cæa f t„i x. T›‹ng tø, n(cid:213)u f ↓ (x, 0) < ∞ v(cid:181) f ch(cid:221)nh quy d›(cid:237)i t„i x th(cid:215) ∂↓f (x) kh‚c r(cid:231)ng, l(cid:229)i, fiªng cæa Rn v(cid:181) v(cid:237)i m(cid:231)i v ∈ Rn,
Cho n“n ∂↓f (x) l(cid:181) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy d›(cid:237)i cæa f t„i x.
N(cid:213)u f : Rn → R l(cid:181) Lipschitz fi(cid:222)a ph›‹ng tr“n Rn v(cid:181) ch(cid:221)nh quy tr“n t„i x, th(cid:215)
f + (x, v) = f ↑ (x, v) = f o (x, v) = max
(cid:104)x∗, v(cid:105) .
x∗∈∂of (x)
v(cid:237)i m(cid:231)i v ∈ Rn,
Do fiª, Ext (∂of (x)) l(cid:181) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tŁi thi(cid:211)u tr“n duy nh˚t
cæa f t„i x. Ch(cid:243) (cid:253) r»ng, n(cid:213)u f l(cid:181) l(cid:229)i th(cid:215) Ext (∂f (x)) l(cid:181) d›(cid:237)i vi ph'n suy rØng
∂f (x) := {x∗ ∈ X ∗ : f (y) − f (x) ≥ (cid:104)x∗, y − x(cid:105) , ∀y ∈ Rn}
ch(cid:221)nh quy tŁi thi(cid:211)u tr“n duy nh˚t cæa f t„i x, trong fiª
l(cid:181) d›(cid:237)i vi ph'n l(cid:229)i cæa f t„i x.
1.2 §i(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u Pareto y(cid:213)u
Ph˙n n(cid:181)y tr(cid:215)nh b(cid:181)y c‚c fii(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u y(cid:213)u fi(cid:222)a ph›‹ng
d›(cid:237)i ng«n ng(cid:247) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n v(cid:181) b‚n ch(cid:221)nh quy tr“n. X—t
b(cid:181)i to‚n tŁi ›u fia m(cid:244)c ti“u (P) sau:
min f (x),
g (x) ≤ 0,
h (x) = 0,
x ∈ C,
trong fiª f , g, h t›‹ng łng l(cid:181) c‚c ‚nh x„ tı Rn v(cid:181)o Rr, Rm, Rl; C l(cid:181) mØt t¸p con cæa Rn. Khi fiª f = (f1, ..., fr), g = (g1, ..., gm), h = (h1, ..., hl), trong fiª f1, ..., fr, g1, ..., gm, h1, ..., hl l(cid:181) nh(cid:247)ng h(cid:181)m gi‚ tr(cid:222) thøc mº rØng x‚c fi(cid:222)nh tr“n
14
Rn. V(cid:237)i x, y ∈ Rn, ta vi(cid:213)t x ≤ y n(cid:213)u xi ≤ yi , (i = 1, ..., n). Nh› v¸y g(x) ≤ 0 cª ngh(cid:220)a l(cid:181) gi(x) ≤ 0, (i = 1, ..., m) v(cid:181) h(x) = 0 cª ngh(cid:220)a l(cid:181) hj(x) = 0, (j = 1, ..., l). §˘t I = {1, ..., m}, J = {1, ..., r}, L = {1, ..., l}. Ch(cid:243) (cid:253) r»ng
fii(cid:210)u ki(cid:214)n c˙n d›(cid:237)i ng«n ng(cid:247) d›(cid:237)i vi ph'n suy rØng cho b(cid:181)i to‚n v(cid:237)i r(cid:181)ng buØc
t¸p ho˘c r(cid:181)ng buØc b˚t fi…ng thłc fi• fi›(cid:238)c nghi“n cłu bºi Dutta-Chandra [7,8]
v(cid:181) cª r(cid:181)ng buØc fi…ng thłc v(cid:181) b˚t fi…ng thłc fi• fi›(cid:238)c nghi“n cłu bºi Luu [15].
M := {x ∈ C : g(x) ≤ 0, h(x) = 0} ,
K(cid:221) hi(cid:214)u M l(cid:181) t¸p ch˚p nh¸n fi›(cid:238)c cæa b(cid:181)i to‚n (P):
I(¯x) := {i ∈ I : g(¯x) = 0} ,
H := {x ∈ Rn : h(x) = 0} .
v(cid:181)
Mº rØng cæa fi(cid:222)nh l(cid:253) Ljusternik c(cid:230) fii(cid:211)n cæa Jim—nez-Novo trong [11] sˇ fi›(cid:238)c
s(cid:246) d(cid:244)ng fi(cid:211) d(cid:201)n fii(cid:210)u ki(cid:214)n c˙n tŁi ›u.
M(cid:214)nh fi(cid:210) 1.2.1 [11]
Gi¶ s(cid:246) r»ng
(a) C l(cid:181) t¸p l(cid:229)i v(cid:181) ¯x ∈ H ∩ C;
(b) h li“n t(cid:244)c trong mØt l'n c¸n cæa ¯x v(cid:181) kh¶ vi Fr—chet t„i ¯x v(cid:237)i fi„o h(cid:181)m
Fr—chet l(cid:181) ∇h(¯x);
(c) §i(cid:210)u ki(cid:214)n ch(cid:221)nh quy (RC) sau fi'y fi(cid:243)ng:
0 ∈
γj∇hj(¯x) + N (C, ¯x) ⇒ γ1 = ... = γl = 0.
j∈L
(cid:88)
A(H ∩ C; ¯x) = T (H ∩ C; ¯x) = (ker ∇h(¯x)) ∩ T (C; ¯x)
= cl [(ker ∇h(¯x)) ∩ cone(C − ¯x)] ,
Khi ޻,
trong ޻ cl k(cid:221) hi(cid:214)u bao ޻ng.
15
Nh¸n x—t 1.2.1 N(cid:213)u C = Rn, h thuØc l(cid:237)p C 1 trong mØt l'n c¸n cæa ¯x v(cid:181) ∇h1(¯x), ..., ∇hr(¯x) l(cid:181) fiØc l¸p tuy(cid:213)n t(cid:221)nh, th(cid:215) m(cid:214)nh fi(cid:210) 1.2.1 trº th(cid:181)nh fi(cid:222)nh l(cid:253) Ljusternik c(cid:230) fii(cid:211)n. Th¸t v¸y, khi fiª ‚nh x„ ∇h(¯x) l(cid:181) to(cid:181)n ‚nh, T (C; ¯x) = Rn, fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (RC)
fi(cid:243)ng v(cid:181) ta cª ker ∇h(¯x) = T (C; ¯x).
§i(cid:210)u ki(cid:214)n (RC) sˇ fi›(cid:238)c minh h(cid:228)a bºi v(cid:221) d(cid:244) sau.
(¯x, ¯y, ¯z) = 0,
h := (h1, h2),
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} .
V(cid:221) d(cid:244) 1.2.1 Cho h : R3 → R2 v(cid:181) C ⊂ R3 fi›(cid:238)c x‚c fi(cid:222)nh nh› sau
0 ∈ γ1∇h1(0) + γ2∇h2(0) + N (C; 0),
Khi fiª ∇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(cid:181) fii(cid:210)u ki(cid:214)n (RC) thÆa m•n. Th¸t v¸y n(cid:213)u
(0, 0, 0) ∈ (γ1 + 2γ2, 2γ1 + 4γ2, γ1 − γ2) + R+ × {0} × {0} ,
cª ngh(cid:220)a l(cid:181)
khi fiª ta suy ra γ1 = γ2 = 0. Do fiª, fii(cid:210)u ki(cid:214)n (RC) fi(cid:243)ng
Nh(cid:190)c l„i r»ng fii(cid:211)m ¯x ∈ M fi›(cid:238)c g(cid:228)i l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa
b(cid:181)i to‚n (P) n(cid:213)u t(cid:229)n t„i mØt sŁ δ > 0 sao cho kh«ng t(cid:229)n t„i x ∈ M ∩ B (¯x; δ)
(∀k ∈ J) ,
fk (x) < fk (¯x)
thÆa m•n
trong fiª B (¯x; δ) l(cid:181) h(cid:215)nh c˙u mº b‚n k(cid:221)nh δ t'm ¯x.
Gi¶ thi(cid:213)t sau fi'y l(cid:181) c˙n thi(cid:213)t fi(cid:211) d(cid:201)n c‚c fii(cid:210)u ki(cid:214)n c˙n cho nghi(cid:214)m h(cid:247)u hi(cid:214)u
y(cid:213)u.
16
Gi¶ thi(cid:213)t 1.2.1 T(cid:229)n t„i mØt ch(cid:216) sŁ s ∈ J sao cho fs cª mØt d›(cid:237)i vi ph'n suy rØng tr“n ∂∗fs (¯x) t„i ¯x. V(cid:237)i m(cid:231)i k ∈ J, k (cid:54)= s v(cid:181) i ∈ I (¯x), c‚c h(cid:181)m fk v(cid:181) gi cª c‚c d›(cid:237)i vi ph'n suy rØng b‚n ch(cid:221)nh quy tr“n ∂∗fk (¯x) v(cid:181) ∂∗gi (¯x) t„i ¯x; t˚t c¶ c‚c h(cid:181)m gi (i /∈ I (¯x)) li“n t(cid:244)c t„i ¯x.
Tr“n c‹ sº fi(cid:222)nh l(cid:253) Ljusternik suy rØng cæa Jim—nez-Novo [11], ta chłng minh
fii(cid:210)u ki(cid:214)n c˙n cho cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa (P).
§(cid:222)nh l(cid:253) 1.2.1
Gi¶ s(cid:246) ¯x l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa (P). Gi¶ s(cid:246) r»ng t˚t c¶ c‚c gi¶
(cid:104)ξk, v(cid:105) < 0 (∀k ∈ J),
thi(cid:213)t cæa m(cid:214)nh fi(cid:210) 1.2.1 v(cid:181) gi¶ thi(cid:213)t 1.2.1 fi(cid:243)ng. Gi¶ s(cid:246) c‚c h(cid:181)m fk (k ∈ J) v(cid:181) gi (i ∈ I (¯x)) Lipschitz fi(cid:222)a ph›‹ng t„i ¯x. Khi fiª, c‚c h(cid:214) sau kh«ng cª nghi(cid:214)m v ∈ Rn:
sup ξk∈conv∂∗fk(¯x)
(cid:104)ξi, v(cid:105) < 0 (∀i ∈ I(¯x)),
(1.2)
sup ξi∈conv∂∗gi(¯x)
(1.3)
(cid:104)∇hj(¯x), v(cid:105) = 0 (∀j ∈ L),
(1.4)
v ∈ T (¯x; C).
(1.5)
Chłng minh Ta ch(cid:216) ra r»ng nh(cid:247)ng fii(cid:210)u ki(cid:214)n sau kh«ng cª nghi(cid:214)m v ∈ Rn:
f − s (¯x; v) < 0,
(1.6)
f + k (¯x; v) < 0 (∀k ∈ J; k (cid:54)= s),
(1.7)
g+ i (¯x; v) < 0 (∀i ∈ I(¯x)),
(1.8)
(cid:104)∇hj(¯x), v(cid:105) = 0 (∀j ∈ L),
(1.9)
v ∈ T (¯x; C).
(1.10)
17
v0 ∈ (ker∇h(¯x)) ∩ T (C; ¯x).
‚p d(cid:244)ng m(cid:214)nh fi(cid:210) 1.2.1 ta suy ra
(ker∇h(¯x)) ∩ T (C; ¯x) = A(H ∩ C; ¯x).
Gi¶ s(cid:246) ng›(cid:238)c l„i r»ng h(cid:214) (1.6) - (1.10) cª mØt nghi(cid:214)m v0 ∈ Rn. Khi fiª,
γ (0) = ¯x, γ (t) ∈ H ∩ C (∀t ∈ ]0, δ]) ,
Do fiª, ∃δ > 0 v(cid:181) γ : [0, δ] → Rn sao cho
= v0.
γ(cid:48) (0) = lim t↓0
γ (t) − γ (0) t
(1.11)
Nh› v¸y,
(∀t ∈ ]0, δ]).
γ (t) ∈ C v(cid:181) h (γ (t)) = 0
(1.12)
+
→ v0 v(cid:181)
→ v0 khi t ↓ 0,
γ (t) − γ (0) t
o (t) t
γ (t) − γ (0) t
Tı (1.11) ta suy ra
→ 0 khi t ↓ 0.
o (t) t V(cid:215) fs l(cid:181) Lipschitz fi(cid:222)a ph›‹ng t„i ¯x, n“n tı [3, tr.286] ta suy ra
f − s (¯x; v0) = lim inf
t↓0
+ o(t)
t
t ))−fs(¯x)
= lim inf
fs(¯x+tv0)−fs(¯x) t fs(¯x+t( γ(t)−γ(0) t
t↓0
= lim inf
fs(¯x+(γ(t)−¯x))−fs(¯x) t
t↓0
= lim inf
< 0.
fs(γ(t))−fs(¯x) t
t↓0
trong ޻
p ≤ δ
< 0.
= lim p→+∞
lim inf t↓0
fs (γ (t)) − fs (¯x) t
fs (γ (tp)) − fs (¯x) tp
(cid:17) (cid:104) (cid:16) 1 sao cho V(cid:215) v¸y, v(cid:237)i m(cid:231)i sŁ tø nhi“n p, t(cid:229)n t„i tp ∈ (cid:105) 0, 1 p
Do fiª, t(cid:229)n t„i sŁ tø nhi“n N1 sao cho v(cid:237)i m(cid:228)i p ≥ N1,
fs (γ (tp)) < fs (¯x) .
(1.13)
18
¯x + t
− fk (¯x)
fk
+ o(t) t
f + k (¯x; v0) = lim sup
t
t↓0
< 0.
= lim p→+∞
fk (γ (t)) − fk (¯x) t
sup p[ t∈]o, 1
V(cid:215) fk l(cid:181) Lipschitz fi(cid:222)a ph›‹ng t„i ¯x, cho n“n tı (1.11) v(cid:237)i ∀k ∈ J, k (cid:54)= s ta cª (cid:17)(cid:17) (cid:16) (cid:16) γ(t)−γ(0) t
,
0, 1 p
(cid:104) (cid:105)
Do fiª, t(cid:229)n t„i sŁ tø nhi“n N2 (≥ N1) sao cho v(cid:237)i m(cid:228)i p ≥ N2, t ∈ fk (γ (t)) < fk (¯x). V(cid:215) v¸y v(cid:237)i m(cid:228)i ∀k ∈ J, k (cid:54)= s, ta cª
fk (γ (tp)) < fk (¯x) .
(1.14)
T›‹ng tø, t(cid:229)n t„i mØt sŁ tø nhi“n N3 (≥ N2) sao cho v(cid:237)i ∀i ∈ I (¯x) , p ≥ N3,
ta cª
gi (γ (tp)) < 0.
(1.15)
Do t(cid:221)nh li“n t(cid:244)c cæa h(cid:181)m gi (i /∈ I (¯x)), t(cid:229)n t„i sŁ tø nhi“n N4 (≥ N3) sao cho v(cid:237)i m(cid:228)i ∀i /∈ I (¯x) , p ≥ N4, ta cª
gi (γ (tp)) < 0
(1.16)
(∀k ∈ J),
fk (γ (tp)) < fk (¯x)
gi (γ (tp)) < 0 (∀i ∈ I),
h (γ (tp)) = 0,
γ (tp) ∈ C.
K(cid:213)t h(cid:238)p (1.12) - (1.16), ta suy ra v(cid:237)i m(cid:228)i ∀p ≥ N4,
§i(cid:210)u n(cid:181)y m'u thu(cid:201)n v(cid:237)i gi¶ thi(cid:213)t ¯x l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa (P).
(cid:50)
Tı gi¶ thi(cid:213)t (1.2.1) ta suy ra r»ng h(cid:214) (1.2) - (1.5) kh«ng t›‹ng th(cid:221)ch.
Tı fiª ta suy ra fii(cid:210)u ph¶i chłng minh.
§˘t
D (¯x) := (cid:83)
λk conv ∂∗fk(¯x) + (cid:80)
µi conv ∂∗gi(¯x) + (cid:80)
γj∇hj(¯x)
(cid:26)
(cid:80) j∈L k∈J i∈I(¯x) +N (C; ¯x) : λk ≥ 0(∀k ∈ J), µi ≥ 0, (∀i ∈ I(¯x)),
γj ∈ R (∀j ∈ L) , (λ, µ, γ) (cid:54)= (0, 0, 0)
(cid:27) ,
19
trong fiª λ = (λk)k∈J , µ = (µi)i∈I(¯x), γ = (γj)j∈L
§i(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa (P) d›(cid:237)i
ng«n ng(cid:247) d›(cid:237)i vi ph'n suy rØng fi›(cid:238)c ph‚t bi(cid:211)u nh› sau.
§(cid:222)nh l(cid:253) 1.2.2
Gi¶ s(cid:246) r»ng ¯x l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa (P) v(cid:181) c‚c gi¶ thi(cid:213)t cæa fi(cid:222)nh l(cid:253) 1.2.1 tho¶ m•n. Khi fiª t(cid:229)n t„i ¯λk ≥ 0 (∀k ∈ J) , ¯µi ≥ 0 (∀i ∈ I (¯x)), (¯λ, ¯µ) (cid:54)= (0, 0) v(cid:181) ¯γ ∈ Rl sao cho
.
0 ∈ cl
¯µiconv∂∗gi(¯x) +
¯γj∇hj(¯x) + N (C; ¯x)
¯λkconv∂∗fk(¯x) +
j∈L
k∈J
i∈I(¯x)
(cid:19) (cid:88) (cid:88) (cid:18)(cid:88)
(1.17)
Chłng minh
Ta ch(cid:216) ra r»ng
0 ∈ clD (¯x) .
(1.18)
0 /∈ clD (¯x) .
Gi¶ s(cid:246) ng›(cid:238)c l„i
(cid:104)ξ, v0(cid:105) < 0.
Ta cª t¸p D (¯x) l(cid:181) kh«ng r(cid:231)ng v(cid:181) l(cid:229)i. Khi fiª ta ‚p d(cid:244)ng fi(cid:222)nh l(cid:253) t‚ch m„nh cho c‚c t¸p l(cid:229)i rŒi nhau D (¯x) v(cid:181) {0} (xem [19], h(cid:214) qu¶ 11.4.2), t(cid:229)n t„i v0 ∈ Rn, v0 (cid:54)= 0 sao cho
sup ξ∈D(¯x)
(1.19)
Theo fi(cid:222)nh l(cid:253) 1.2.1, h(cid:214) (1.2) - (1.5) l(cid:181) kh«ng t›‹ng th(cid:221)ch. Khi fiª, b»ng c‚ch
(cid:104)ξk, v0(cid:105) < 0 (∀k ∈ J).
ch(cid:228)n λk = 1, λp = 0, (∀p ∈ J, p (cid:54)= k), µi = 0 (∀i ∈ I(¯x)), γ = 0 v(cid:181) 0 = ζ ∈ N (C; ¯x), tı (1.19) ta suy ra
sup ξk∈conv∂∗fk(¯x)
(1.20)
(cid:104)ηi, v0(cid:105) < 0 (∀i ∈ I(¯x)).
T›‹ng tø nh› tr“n, ta cª
sup ηi∈conv∂∗gi(¯x)
(1.21)
20
Ta ch(cid:216) ra
(∀j ∈ L) .
(cid:104)∇hj(¯x), v0(cid:105) = 0
(1.22)
Th¸t v¸y n(cid:213)u (1.22) l(cid:181) sai, th(cid:215) (cid:104)∇hj0(¯x), v0(cid:105) (cid:54)= 0 v(cid:237)i j0 n(cid:181)o fiª ∈ L. B»ng c‚ch l˚y ξs ∈ ∂∗fs (¯x) , λs = 1, λk = 0 (∀k ∈ J, k (cid:54)= s) , µi = 0(∀i ∈ I(¯x)), γj = 0 (∀j ∈ L, j (cid:54)= j0) , 0 = ζ ∈ N (C; ¯x), tı (1.19) ta suy ra
(cid:104)ξs, v0(cid:105) + γj0 (cid:104)∇hj0(¯x), v0(cid:105) < 0.
(1.23)
|(cid:104)ξs, v0(cid:105)| < +∞ v(cid:181) |(cid:104)∇hj0(¯x), v0(cid:105)| < +∞.
Ta ch(cid:243) (cid:253) r»ng
Cho γj0 fiæ l(cid:237)n n(cid:213)u (cid:104)∇hj0(¯x), v0(cid:105) > 0, c(cid:223)n γj0 < 0 v(cid:237)i gi‚ tr(cid:222) tuy(cid:214)t fiŁi fiæ l(cid:237)n n(cid:213)u (cid:104)∇hj0(¯x), v0(cid:105) < 0, ta sˇ fii fi(cid:213)n mØt m'u thu(cid:201)n v(cid:237)i (1.23). Do v¸y, (1.22) l(cid:181) fi(cid:243)ng.
Ti(cid:213)p theo, ta ch(cid:216) ra r»ng
v0 ∈ T (C; ¯x).
(1.24)
Th¸t v¸y, n(cid:213)u (1.24) kh«ng fi(cid:243)ng th(cid:215) sˇ ∃η0 ∈ N (C; ¯x) sao cho (η0, v0) > 0. B»ng c‚ch cho λk = 0 (∀k ∈ J, k (cid:54)= s) , λs > 0, ξs ∈ ∂∗fs (¯x) , µi = 0(∀i ∈ I(¯x)), γ = 0, v(cid:237)i α > 0 ta cª αη0 ∈ N (C; ¯x) v(cid:181)
λs (cid:104)ξ0, v0(cid:105) + α (cid:104)η0, v0(cid:105) < 0.
(1.25)
(cid:104)η0, v0(cid:105) ≤ 0, (∀η ∈ N (C; ¯x)).
V(cid:215) (cid:104)η0, v0(cid:105) > 0 v(cid:237)i α fiæ l(cid:237)n ta nh¸n fi›(cid:238)c mØt m'u thu(cid:201)n v(cid:237)i (1.25). Do fiª
v0 ∈ N 0(C; ¯x) = T 00(C; ¯x) = T (C; ¯x).
Ch(cid:243) (cid:253) r»ng T (C; ¯x) l(cid:181) mØt nªn l(cid:229)i fiªng. Tı fiª ta cª
K(cid:213)t h(cid:238)p (1.20) - (1.22) v(cid:181) (1.24) ta suy ra h(cid:214) (1.6) - (1.10) cª mØt nghi(cid:214)m v0,
v(cid:181) c(cid:242)ng l(cid:181) nghi(cid:214)m cæa h(cid:214) (1.2) - (1.5). §i(cid:210)u n(cid:181)y m'u thu(cid:201)n v(cid:237)i fi(cid:222)nh l(cid:253) 1.2.1. V(cid:215)
21
k ≥ 0, ξ(n)
i ∈ conv∂∗gi (¯x) (∀i ∈ I (¯x)) , γ(n)
k ∈ conv∂∗fk (¯x) (∀k ∈ J) , µ(n) i ≥ j ∈ R (∀j ∈ L) v(cid:181) ζ (n) ∈ N (C; ¯x) v(cid:237)i
(cid:54)= (0, 0, 0) sao cho
v¸y (1.18) fi(cid:243)ng v(cid:181) do fiª t(cid:229)n t„i λ(n) 0, η(n) (cid:16) λ(n), µ(n)
I(¯x), γ(n)(cid:17) (cid:18)(cid:88)
,
i η(n) µ(n)
i +
γ(n) j ∇hj (¯x) + ξ(n)
k ξ(n) λ(n)
k +
0 = lim n→∞
j∈L
k∈J
i∈I(¯x)
(cid:19) (cid:88) (cid:88) (1.26)
trong ޻
λ(n) =
, µ(n)
, γ(n) =
.
γ(n) j
λ(n) k
I(¯x) =
k∈J
i∈I(¯x)
j∈L
(cid:17) (cid:16) (cid:17) (cid:17) (cid:16) (cid:16) µ(n) i
Bºi v(cid:215)
,
(cid:16) λ(n), µ(n) (cid:17) I(¯x), γ(n) (cid:54)= (0, 0, 0)
(cid:107) (λ(n), µ(n)
ta cª th(cid:211) xem nh›
→ (cid:0)¯λ, ¯µI(¯x), ¯γ(cid:1)
I(¯x), γ(n)) (cid:107)= 1 (∀n) . I(¯x), γ(n)(cid:17) λ(n), µ(n)
(cid:16)
clA + clB ⊆ cl(A + B),
Kh«ng m˚t t(cid:221)nh t(cid:230)ng qu‚t cª th(cid:211) gi¶ s(cid:246) v(cid:237)i ¯λ ≥ 0, ¯µI(¯x) ≥ 0, ¯γ ∈ Rl v(cid:181) (cid:107) (¯λ, ¯µI(¯x), ¯γ) (cid:107)= 1. Bºi v(cid:215)
¯λk clconv∂∗fk (¯x) + (cid:80)
¯µi clconv∂∗gi (¯x)
0 ∈ (cid:80) k∈J
i∈I(¯x)
¯γj∇hj (¯x) + N (C; ¯x)
+ (cid:80) j∈L
v(cid:181) tı (1.26) ta suy ra
⊆ cl
¯λkconv∂∗fk (¯x) +
¯µiconv∂∗gi (¯x) +
¯γj∇hj (¯x) + N (C; ¯x).
j∈L
k∈J
i∈I(¯x)
(cid:88) (cid:88) (cid:88)
(1.27) Ta cª (1.27) fi(cid:243)ng v(cid:237)i (cid:0)¯λ, ¯µ(cid:1) (cid:54)= (0, 0). Th¸t v¸y n(cid:213)u (cid:0)¯λ, ¯µ(cid:1) = (0, 0) th(cid:215) ¯γ (cid:54)= 0. Tuy nhi“n, k(cid:213)t h(cid:238)p v(cid:237)i (1.27) ta fii fi(cid:213)n m'u thu(cid:201)n v(cid:237)i fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (RC). Do fiª (cid:0)¯λ, ¯µ(cid:1) (cid:54)= (0, 0). Suy ra fii(cid:210)u ph¶i chłng minh. (cid:50)
22
H(cid:214) qu¶ 1.2.1 Gi¶ s(cid:246) r»ng C = Rn v(cid:181) c‚c gi¶ thi(cid:213)t cæa fi(cid:222)nh l(cid:253) 1.2.2 tho¶ m•n trong fiª
fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (RC) trong m(cid:214)nh fi(cid:210) 1.2.1 fi›(cid:238)c thay th(cid:213) bºi fii(cid:210)u ki(cid:214)n: h(cid:214) ∇h1(¯x), ..., ∇hl(¯x) l(cid:181) fiØc l¸p tuy(cid:213)n t(cid:221)nh. Khi fiª, t(cid:229)n t„i ¯λk ≥ 0 (∀k ∈ J), ¯µi ≥ 0 (∀i ∈ I(¯x)) v(cid:237)i (cid:0)¯λ, ¯µ(cid:1) (cid:54)= (0, 0) v(cid:181) ¯γj ∈ R (∀j ∈ L) sao cho (1.17) fi(cid:243)ng. Chłng minh V(cid:237)i C = Rn, ta cª N (C; ¯x) = {0}. Do fiª, n(cid:213)u ∇h1(¯x), ..., ∇hl(¯x) l(cid:181) fiØc l¸p tuy(cid:213)n t(cid:221)nh th(cid:215) fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (RC) thÆa m•n. Theo fi(cid:222)nh l(cid:253) 1.2.2 ta suy ra (cid:50) fii(cid:210)u ph¶i chłng minh.
Trong tr›Œng h(cid:238)p t¸p D(¯x) l(cid:181) t¸p fiªng, ta nh¸n fi›(cid:238)c h(cid:214) qu¶ trøc ti(cid:213)p sau fi'y
cæa fi(cid:222)nh l(cid:253) 1.2.1, trong fiª bao fiªng trong (1.17) cª th(cid:211) bÆ fi›(cid:238)c.
H(cid:214) qu¶ 1.2.2 Gi¶ s(cid:246) C = Rn. Gi¶ s(cid:246) c‚c gi¶ thi(cid:213)t cæa fi(cid:222)nh l(cid:253) 1.2.2 fi(cid:243)ng v(cid:181) t¸p D(¯x) fiªng. Khi fiª ∃¯λk ≥ 0 (∀k ∈ J), ¯µi ≥ 0 (∀i ∈ I(¯x)) v(cid:237)i (cid:0)¯λ, ¯µ(cid:1) (cid:54)= (0, 0) v(cid:181) ¯γj ∈ R (∀j ∈ L) sao cho
0 ∈
¯γj∇hj (¯x) + N (C; ¯x).
¯λkconv∂∗fk (¯x) +
¯µiconv∂∗gi (¯x) +
j∈L
k∈J
i∈I(¯x)
(cid:88) (cid:88) (cid:88)
Nh¸n x—t 1.2.2 Trong tr›Œng h(cid:238)p C = Rn, c(cid:242)ng nh› trong nh¸n x—t 3.1 trong [13], n(cid:213)u ∂∗fk(¯x) (k ∈ J) v(cid:181) ∂∗gi(¯x)(i ∈ (I(¯x)) b(cid:222) ch˘n v(cid:181) thÆa m•n fii(cid:210)u ki(cid:214)n sau fi'y:
0 /∈ conv
conv∂∗fk (¯x) ∪
conv∂∗gi (¯x)
+ lin {∇hj(¯x) : j ∈ L} ,
k∈J
i∈I(¯x)
(cid:19) (cid:18) (cid:91) (cid:91)
th(cid:215) D(¯x) l(cid:181) t¸p fiªng, trong fiª lin k(cid:221) hi(cid:214)u bao tuy(cid:213)n t(cid:221)nh. Th¸t v¸y ta cª conv∂∗fk(¯x) (k ∈ J) v(cid:181) conv∂∗gi(¯x)(i ∈ (I(¯x)) l(cid:181) comp¤c v(cid:181) do fiª t¸p sau c(cid:242)ng comp¤c:
conv
.
conv∂∗fk (¯x) ∪
conv∂∗gi (¯x)
k∈J
i∈I(¯x)
(cid:19) (cid:18) (cid:91) (cid:91)
23
Do ޻,
E(¯x) := conv
conv∂∗fk (¯x) ∪
conv∂∗gi (¯x)
+lin {∇hj(¯x) : j ∈ L}
k∈J
i∈I(¯x)
(cid:19) (cid:91) (cid:18) (cid:91)
D(¯x) = coneE(¯x),
l(cid:181) t¸p fiªng. H‹n n(cid:247)a, v(cid:215) 0 /∈ E(¯x) v(cid:181)
cho n“n D(¯x) l(cid:181) t¸p fiªng, trong fiª coneE(¯x) l(cid:181) nªn sinh bºi E(¯x).
Nh¸n x—t 1.2.3
§i(cid:210)u ki(cid:214)n c˙n thu fi›(cid:238)c trong fi(cid:222)nh l(cid:253) 1.2.2, c‚c h(cid:214) qu¶ 1.2.1, 1.2.2 v(cid:181) mØt v(cid:181)i fii(cid:210)u ki(cid:214)n tŁi ›u fi• tr(cid:215)nh b(cid:181)y d›(cid:237)i ng«n ng(cid:247) ∂∗f (¯x) l(cid:181) tŁt h‹n c‚c fii(cid:210)u ki(cid:214)n tŁi
›u d›(cid:237)i ng«n ng(cid:247) c‚c d›(cid:237)i vi ph'n nh› c‚c d›(cid:237)i vi ph'n Clarke, Mordukhovich
v(cid:181) Michel-Penot.
24
Ch›‹ng 2
§i(cid:210)u ki(cid:214)n ch(cid:221)nh quy v(cid:181) fii(cid:210)u ki(cid:214)n tŁi ›u
Karush-Kuhn-Tucker
Trong ch›‹ng 2 ch(cid:243)ng ta sˇ tr(cid:215)nh b(cid:181)y c‚c fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy v(cid:181) fii(cid:210)u ki(cid:214)n
c˙n Karush-Kuhn-Tucker, fii(cid:210)u ki(cid:214)n fiæ cho cøc ti(cid:211)u Pareto y(cid:213)u cæa b(cid:181)i to‚n tŁi
›u fia m(cid:244)c ti“u cª r(cid:181)ng buØc fi…ng thłc, b˚t fi…ng thłc v(cid:181) r(cid:181)ng buØc t¸p d›(cid:237)i
ng«n ng(cid:247) d›(cid:237)i vi ph'n suy rØng. C‚c k(cid:213)t qu¶ tr(cid:215)nh b(cid:181)y trong ch›‹ng n(cid:181)y fi›(cid:238)c
tham kh¶o trong [14].
2.1 §i(cid:210)u ki(cid:214)n ch(cid:221)nh quy v(cid:181) fii(cid:210)u ki(cid:214)n c˙n Karush-Kuhn-
Tucker
Ch›‹ng 1 fi• tr(cid:215)nh b(cid:181)y fii(cid:210)u ki(cid:214)n c˙n Fritz John (1.17) v(cid:237)i gi¶ thi(cid:213)t 1.2.1 v(cid:181)
gi¶ thi(cid:213)t cæa m(cid:214)nh fi(cid:210) 1.2.1, trong fiª fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (RC) fi(cid:243)ng:
0 ∈
γj∇hj (¯x) + N (C; ¯x) ⇒ γ1 = ... = γl = 0.
j∈L
(cid:88)
Trong tr›Œng h(cid:238)p C = Rn th(cid:215) fii(cid:210)u ki(cid:214)n n(cid:181)y trº th(cid:181)nh fii(cid:210)u ki(cid:214)n: h(cid:214) ∇h1, ..., ∇hl l(cid:181) fiØc l¸p tuy(cid:213)n t(cid:221)nh. Ch(cid:243) (cid:253) r»ng trong fii(cid:210)u ki(cid:214)n c˙n (1.17) ta cª (cid:0)¯λ, ¯µ(cid:1) (cid:54)= (0, 0). §(cid:211) nh¸n fi›(cid:238)c fii(cid:210)u ki(cid:214)n c˙n cho nghi(cid:214)m h(cid:247)u hi(cid:214)u trong fiª ¯λ (cid:54)= 0, ta fi›a v(cid:181)o fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy sau fi'y m(cid:181) ta k(cid:253) hi(cid:214)u l(cid:181) (CQ1): ∃s ∈ J, d0 ∈ T (C, ¯x), v(cid:181) c‚c sŁ ak > 0 (k ∈ J, k (cid:54)= s) , bi > 0 (i ∈ I (¯x)) sao cho
25
(cid:104)ξk, d0(cid:105) ≤ −ak (∀ξk ∈ conv∂∗fk (¯x) , ∀k ∈ J, k (cid:54)= s) ; (cid:104)ηi; d0(cid:105) ≤ −bi
(i)
(∀ηi ∈ conv∂∗gi (¯x) , ∀i ∈ I (¯x)) ; (cid:104)∇hj (¯x) , d0(cid:105) = 0 (∀j ∈ L) .
(ii)
Ch(cid:243)ng ta c(cid:239)ng fi›a v(cid:181)o fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (CQ2):
V(cid:237)i m(cid:228)i λk ≥ 0 (k ∈ J, k (cid:54)= s) ; µi ≥ 0 (∀i ∈ I (¯x)), kh«ng fi(cid:229)ng thŒi b»ng 0, v(cid:181) γj ∈ R (∀j ∈ L), ta cª
0 /∈ cl
µiconv∂∗gi (¯x)
λkconv∂∗fk (¯x) +
k∈J,k(cid:54)=s
i∈I(¯x)
(cid:88) (cid:18) (cid:88)
.
+
γj∇hj(¯x) + N (C; ¯x)
j∈L
(cid:19) (cid:88)
Trong ph˙n ti(cid:213)p theo ta tr(cid:215)nh b(cid:181)y mŁi quan h(cid:214) gi(cid:247)a (CQ1) v(cid:181) (CQ2).
M(cid:214)nh fi(cid:210) 2.1.1 Gi¶ s(cid:246) r»ng fk v(cid:181) gi cª c‚c d›(cid:237)i vi ph'n suy rØng tr“n ∂∗fk (¯x) v(cid:181) ∂∗gi (¯x) t„i ¯x, v(cid:237)i m(cid:231)i k ∈ J, k (cid:54)= s, i ∈ I (¯x), h kh¶ vi Fr—chet t„i ¯x v(cid:181) C l(cid:181) l(cid:229)i. Khi fiª
(CQ1) k—o theo (CQ2) (∀s ∈ J).
∈
k
Chłng minh
Gi¶ s(cid:246) ng›(cid:238)c l„i r»ng (CQ1) fi(cid:243)ng, nh›ng (CQ2) sai, cª ngh(cid:220)a l(cid:181) ∃λk ≥ 0 (∀k ∈ J, k (cid:54)= s) ; µi ≥ 0 (∀i ∈ I (¯x)) v(cid:237)i (λ(s), µ) (cid:54)= (0, 0), trong fiª (λ(s) = (λk)k∈J,k(cid:54)=s,µ = (µi)i∈I(¯x)), ξ(n) conv∂∗fk (¯x) (∀k ∈ J, k (cid:54)= s) , η(n) i ∈ conv∂∗gi (¯x) (∀i ∈ I (¯x)) , γj ∈ R (∀j ∈ L) v(cid:181) ζ (n) ∈ N (C; ¯x) sao cho
= 0.
λkξ(n)
µiη(n)
γj∇hj(¯x) + ζ (n)
i +
k +
lim n→∞
j∈L
k∈J,k(cid:54)=s
i∈I(¯x)
(cid:19) (cid:18) (cid:88) (cid:88) (cid:88)
Tı (CQ1) suy ra ∃d0 ∈ T (C; ¯x) sao cho
+
µi
, d0
λk
η(n) i
0 = lim n→∞
k∈J,k(cid:54)=s
i∈I(¯x)
(cid:68) (cid:69) (cid:69) (cid:88) (cid:18) (cid:88) (cid:68) ξ(n) k , d0
+
γj (cid:104)∇hj(¯x), d0(cid:105) +
j∈L
(cid:69)(cid:19) (cid:88) (cid:68) ζ (n), d0
26
+
.
λk
µi
, d0
ξ(n) k , d0
≤ lim n→∞
k∈J,k(cid:54)=s
i∈I(¯x)
(cid:68) (cid:69) (cid:69)(cid:19) (cid:18) (cid:88) (cid:88) (cid:68) η(n) i (2.1)
V(cid:215) (λ(s), µ) (cid:54)= (0, 0) tı fii(cid:210)u ki(cid:214)n (i) trong (CQ1) suy ra
+
µi
, d0
λk
η(n) i
lim n→∞
i∈I(¯x)
(cid:68) (cid:69)(cid:19) (cid:69) (cid:88) (cid:18) (cid:88) (cid:68) ξ(n) k , d0
k∈J,k(cid:54)=s (cid:88)
≤ −
λkak −
µibi < 0.
k∈J,k(cid:54)=s
i∈I(¯x)
(cid:50)
(cid:88)
§i(cid:210)u n(cid:181)y m'u thu(cid:201)n v(cid:237)i (2.1). Do fiª ta cª fii(cid:210)u ph¶i chłng minh.
MØt fii(cid:210)u ki(cid:214)n c˙n Karush-Kuhn-Tucker cho nghi(cid:214)m h(cid:247)u hi(cid:214)u cª th(cid:211) fi›(cid:238)c ph‚t
bi(cid:211)u nh› sau:
§(cid:222)nh l(cid:253) 2.1.1
Gi¶ s(cid:246) ¯x l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa (P). Gi¶ s(cid:246) t˚t c¶ c‚c gi¶
thi(cid:213)t cæa fi(cid:222)nh l(cid:253) 1.2.2 tho¶ m•n v(cid:181) gi¶ s(cid:246) fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (CQ1) ho˘c (CQ2) fi(cid:243)ng (v(cid:237)i s ∈ J). Khi fiª, t(cid:229)n t„i ¯λs > 0, ¯λk ≥ 0(∀k ∈ J, k (cid:54)= s), ¯µi ≥ 0(∀i ∈ I(¯x)), ¯γj ∈ R(∀j ∈ L) sao cho
0 ∈ cl
¯λk conv∂∗fk(¯x) +
¯µiconv∂∗gi(¯x)
k∈J
i∈I(¯x)
(cid:88) (cid:18) (cid:88)
.
+
¯γj∇hj(¯x) + N (C; ¯x)
j∈L
(cid:19) (cid:88) (2.2)
(¯λ, ¯µ) =
(¯λk)k∈J , (¯µi)i∈I(¯x)
(cid:50)
(cid:16) (cid:17)(cid:17) (cid:16)
Chłng minh ‚p d(cid:244)ng fi(cid:222)nh l(cid:253) 1.2.2 ta suy ra ∃ ¯λk ≥ 0 (∀k ∈ J) , ¯µi ≥ 0 (∀i ∈ I (¯x)) v(cid:237)i (¯λ, ¯µ) (cid:54)= (0, 0) v(cid:181) ¯γ ∈ Rl sao cho (2.2) fi(cid:243)ng. N(cid:213)u ¯λs = 0, th(cid:215) tı (CQ1) ho˘c (CQ2) ta suy ra m'u thu(cid:201)n v(cid:237)i (2.2). V(cid:215) v¸y ¯λs > 0. Tı fiª, ta suy ra fii(cid:210)u ph¶i chłng minh.
Nh¸n x—t 2.1.1
Ta fi›a v(cid:181)o fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (CQ3) y(cid:213)u h‹n h„n ch(cid:213) (CQ1): t(cid:229)n t„i d0 ∈
27
T (C, ¯x) v(cid:181) c‚c sŁ bi > 0 (i ∈ I (¯x)) sao cho fii(cid:210)u ki(cid:214)n (ii) trong (CQ1) fi(cid:243)ng v(cid:181)
thÆa m•n fii(cid:210)u ki(cid:214)n sau: (i’) (cid:104)ηi, d0(cid:105) ≤ −bi (∀ηi ∈ conv∂∗gi (¯x) , ∀i ∈ I(¯x)) .
µi ≥ 0 (∀i ∈ I (¯x)), kh«ng fi(cid:229)ng thŒi b»ng 0, v(cid:181) γj ∈ R (∀j ∈ L),
Ta c(cid:242)ng fi›a v(cid:181)o fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (CQ4) y(cid:213)u h‹n h„n ch(cid:213) (CQ2): v(cid:237)i m(cid:228)i
0 /∈ cl
.
µiconv∂∗gi (¯x) +
γj∇hj(¯x) + N (C; ¯x)
j∈L
i∈I(¯x)
(cid:19) (cid:88) (cid:18) (cid:88)
B»ng l¸p lu¸n t›‹ng tø nh› trong chłng minh cæa m(cid:214)nh fi(cid:210) 2.1.1, ta suy ra r»ng
¯λk > 0. §i(cid:210)u ki(cid:214)n n(cid:181)y y(cid:213)u h‹n fii(cid:210)u ki(cid:214)n ¯λs > 0.
(CQ3) k—o theo (CQ4). H‹n n(cid:247)a, n(cid:213)u trong fi(cid:222)nh l(cid:253) 2.1.1 (CQ1) v(cid:181) (CQ2) (v(cid:237)i s
n(cid:181)o fiª ∈ J) t›‹ng łng fi›(cid:238)c thay th(cid:213) bºi (CQ3) v(cid:181) (CQ4), ta thu fi›(cid:238)c fii(cid:210)u ki(cid:214)n c˙n (2.2) v(cid:237)i fii(cid:210)u ki(cid:214)n (cid:80) k∈J
C‚c gi¶ thi(cid:213)t sau l(cid:181) c˙n thi(cid:213)t fi(cid:211) d(cid:201)n fii(cid:210)u ki(cid:214)n c˙n v(cid:237)i c‚c h(cid:214) sŁ Lagrange
t›‹ng łng v(cid:237)i c‚c th(cid:181)nh ph˙n cæa h(cid:181)m m(cid:244)c ti“u l(cid:181) d›‹ng.
Gi¶ thi(cid:213)t 2.1.1
V(cid:237)i m(cid:231)i k ∈ J v(cid:181) i ∈ I(¯x), c‚c h(cid:181)m fk v(cid:181) gi cª c‚c d›(cid:237)i vi ph'n suy rØng b‚n ch(cid:221)nh quy tr“n ∂∗fk(¯x) v(cid:181) ∂∗gi(¯x) t„i ¯x; c‚c h(cid:181)m gi (i /∈ I(¯x)) li“n t(cid:244)c t„i ¯x.
Sau fi'y, ta tr(cid:215)nh b(cid:181)y mØt fii(cid:210)u ki(cid:214)n c˙n Karush-Kuhn-Tucker cho cøc ti(cid:211)u
Pareto y(cid:213)u fi(cid:222)a ph›‹ng v(cid:237)i c‚c nh'n t(cid:246) Lagrange d›‹ng t›‹ng łng v(cid:237)i c‚c th(cid:181)nh
ph˙n cæa h(cid:181)m m(cid:244)c ti“u.
§(cid:222)nh l(cid:253) 2.1.2
Gi¶ s(cid:246) ¯x l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng cæa (P). Gi¶ s(cid:246) c‚c gi¶ thi(cid:213)t cæa
fi(cid:222)nh l(cid:253) 1.2.2 tho¶ m•n trong fiª gi¶ thi(cid:213)t 1.2.1 fi›(cid:238)c thay th(cid:213) bºi gi¶ thi(cid:213)t 2.1.1.
Gi¶ s(cid:246) r»ng fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy (CQ1) ho˘c (CQ2) (v(cid:237)i m(cid:228)i s ∈ J) fi(cid:243)ng. Khi fiª, t(cid:229)n t„i ¯λk > 0(∀k ∈ J), ¯µi ≥ 0 (∀i ∈ I (¯x)) , ¯γj ∈ R (∀j ∈ L) sao cho
0 ∈ cl
¯λk conv∂∗fk(¯x) +
¯µiconv∂∗gi(¯x)
k∈J
i∈I(¯x)
(cid:18) (cid:88) (cid:88)
+
.
¯γj∇hj(¯x) + N (C; ¯x)
j∈L
(cid:19) (cid:88)
28
k ≥ 0
s > 0, λ(s) j ∈ R (∀j ∈ L) sao cho
i ≥ 0 (∀i ∈ I (¯x)) , γ(s) (cid:88)
.
0 ∈ cl
µ(s) i ∂∗gi (¯x) +
γ(s) j ∇hj (¯x) + N (C; ¯x)
λ(s) k ∂∗fk (¯x) +
j∈L
k∈J
i∈I(¯x)
(cid:19) (cid:88) Chłng minh V(cid:237)i m(cid:231)i s ∈ J, ‚p d(cid:244)ng fi(cid:222)nh l(cid:253) 2.1.1 ta suy ra t(cid:229)n t„i λ(s) (∀k ∈ J, k (cid:54)= s), µ(s) (cid:18)(cid:88)
(2.3)
Ch(cid:243) (cid:253) r»ng cl (A) + cl (B) ⊆ cl (A + B). L˚y s = 1, ..., r trong (2.3) v(cid:181) cØng
hai v(cid:213) cæa c‚c bao h(cid:181)m thłc nh¸n fi›(cid:238)c, ta suy ra
0 ∈
µ(s) i ∂∗gi (¯x) +
γ(s) j ∇hj (¯x) + N (C; ¯x)
λ(s) k ∂∗fk (¯x) +
s∈J
j∈L
k∈J
i∈I(¯x)
(cid:19) (cid:88) (cid:88) (cid:88) (cid:18)(cid:88) cl
⊆ cl
,
¯γj∇hj (¯x) + N (C; ¯x)
¯λk ∂∗fk (¯x) +
¯µi∂∗gi (¯x) +
j∈L
s + (cid:80)
k∈J trong fiª ¯λk = λ(s)
µ(s) i ≥ 0 ( ∀i ∈ I (¯x))
i∈I(¯x) k > 0 (∀k ∈ J), ¯µi = (cid:80) λ(s)
s∈J
(cid:19) (cid:18)(cid:88) (cid:88) (cid:88)
s∈J
(cid:50)
s∈J,s(cid:54)=k γ(s) j ∈ R (∀j ∈ L) . Tı fiª, ta suy ra ph¶i chłng minh.
v(cid:181) ¯γj = (cid:80)
2.2 §i(cid:210)u ki(cid:214)n fiæ cho cøc ti(cid:211)u Pareto y(cid:213)u
Trong ph˙n n(cid:181)y, ta cª th(cid:211) th˚y r»ng fii(cid:210)u ki(cid:214)n c˙n Karush-Kuhn-Tucker sˇ
trº th(cid:181)nh fii(cid:210)u ki(cid:214)n fiæ khi ta fi›a v(cid:181)o mØt v(cid:181)i gi¶ thi(cid:213)t l(cid:229)i suy rØng.
§(cid:222)nh l(cid:253) 2.2.1
Gi¶ s(cid:246) ¯x l(cid:181) mØt fii(cid:211)m ch˚p nh¸n fi›(cid:238)c cæa b(cid:181)i to‚n (P). Gi¶ s(cid:246) r»ng fk cª mØt d›(cid:237)i vi ph'n suy rØng ∂∗fk (¯x) t„i ¯x, ∀k ∈ J, gi cª mØt d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n ∂∗gi (¯x) t„i ¯x, ∀i ∈ I (¯x), v(cid:181) h l(cid:181) kh¶ vi Fr—chet t„i ¯x. H‹n n(cid:247)a, gi¶ s(cid:246) r»ng (i) ∃ ¯λk ≥ 0 (∀k ∈ J) v(cid:237)i λ = (λk)k∈J (cid:54)= 0, ¯µi ≥ 0 (∀i ∈ I (¯x)) v(cid:181) ¯γj ∈ R (∀j ∈ L) sao cho
0 ∈ cl
¯λk conv∂∗fk(¯x) +
¯µiconv∂∗gi(¯x)
k∈J
i∈I(¯x)
(cid:88) (cid:18) (cid:88)
29
+
,
¯γj∇hj(¯x) + N (C; ¯x)
j∈L
(cid:19) (cid:88) (2.4)
+ - ti(cid:214)m c¸n v« h›(cid:237)ng t„i ¯x theo C; gi l(cid:181) tøa l(cid:229)i v(cid:181) hj l(cid:181) tøa
(ii) f l(cid:181) gi¶ l(cid:229)i Rn
tuy(cid:213)n t(cid:221)nh t„i ¯x theo C (∀i ∈ I (¯x) , j ∈ L); C l(cid:181) t¸p l(cid:229)i.
∈ conv∂∗fk (¯x) (∀k ∈ J) , ¯η(n)
i ∈ conv∂∗gi (¯x)
k
Khi fiª ¯x l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u cæa (P).
Chłng minh Tı (2.4) suy ra t(cid:229)n t„i ¯ξ(n) (∀i ∈ I (¯x)) v(cid:181) ¯ζ (n) ∈ N (C; ¯x) sao cho
= 0.
¯ξ(n)
+
¯µi ¯η(n)
¯γj∇hj (¯x) + ¯ζ (n)
¯λk
i +
k
lim n→∞
j∈L
k∈J
i∈I(¯x)
(cid:19) (cid:88) (cid:88) (cid:18)(cid:88) (2.5)
(cid:104)ηi, x − ¯x(cid:105) ≤ 0
(∀ηi ∈ ∂∗gi (¯x)) ,
Bºi v(cid:215) gi l(cid:181) d›(cid:237)i vi ph'n suy rØng ch(cid:221)nh quy tr“n ∂∗gi (¯x) t„i ¯x theo M , v(cid:237)i m(cid:228)i ∀i ∈ I (¯x), tı m(cid:214)nh fi(cid:210) 1.1.1 ta suy ra v(cid:237)i m(cid:228)i ∀i ∈ M ,
(cid:104)ηi, x − ¯x(cid:105) ≤ 0
(∀ηi ∈ conv∂∗gi (¯x)) .
do gi(x) − gi(¯x) ≤ 0(∀x ∈ M ). §i(cid:210)u n(cid:181)y d(cid:201)n fi(cid:213)n
Do ޻,
, x − ¯x(cid:105) ≤ 0
(∀x ∈ M ) .
(cid:104)¯η(n) i
(2.6)
V(cid:215) hj (j ∈ L) l(cid:181) tøa tuy(cid:213)n t(cid:221)nh t„i ¯x theo C n“n ta cª
(∀x ∈ M ) .
(cid:104)∇hj (¯x) , x − ¯x(cid:105) = 0
(2.7)
V(cid:215) C l(cid:229)i n“n ta cª x − ¯x ∈ T (C; ¯x) ∀x ∈ C. V(cid:215) v¸y,
(cid:104)¯ζ (n), x − ¯x(cid:105) ≤ 0
(∀x ∈ M ) .
(2.8)
K(cid:213)t h(cid:238)p (2.5) - (2.9) ta suy ra
¯ξ(n)
, x − ¯x(cid:105) ≥ 0.
¯λk
k
lim n→∞
k∈J
(cid:88) (cid:104) (2.9)
k∈J
V(cid:215) fk cª mØt d›(cid:237)i vi ph'n suy rØng ∂∗fk (¯x) t„i ¯x v(cid:181) ¯λk ≥ 0 ∀k ∈ J, theo c‚c quy t(cid:190)c 4.1, 4.2 [9] ta suy ra ¯λT f cª (cid:80) ¯λk∂∗fk (¯x) l(cid:181) mØt d›(cid:237)i vi ph'n suy
30
+ - ti(cid:214)m c¸n v« h›(cid:237)ng cæa f , ta suy ra r»ng
(cid:104)¯λ, f (x)(cid:105) ≥ (cid:104)¯λ, f (¯x)(cid:105)
(∀x ∈ M ) .
rØng t„i ¯x. S(cid:246) d(cid:244)ng t(cid:221)nh gi¶ l(cid:229)i Rn ¯λT f l(cid:181) gi¶ l(cid:229)i ti(cid:214)m c¸n t„i ¯x theo M . Do fiª tı (2.9) ta cª
(cid:50)
Tı fiª suy ra ¯x l(cid:181) cøc ti(cid:211)u Pareto y(cid:213)u cæa (P).
§ª l(cid:181) fii(cid:210)u ph¶i chłng minh.
31
K(cid:213)t lu¸n
Lu¸n v¤n fi• tr(cid:215)nh b(cid:181)y c‚c k(cid:213)t qu¶ v(cid:210) fii(cid:210)u ki(cid:214)n tŁi ›u cæa D. V. L›u (2014)
cho nghi(cid:214)m h(cid:247)u hi(cid:214)u y(cid:213)u cæa b(cid:181)i to‚n tŁi ›u cª r(cid:181)ng buØc fi…ng thłc, b˚t fi…ng
thłc v(cid:181) r(cid:181)ng buØc t¸p v(cid:237)i c‚c h(cid:181)m Lipschitz fi(cid:222)a ph›‹ng d›(cid:237)i ng«n ng(cid:247) d›(cid:237)i vi
ph'n suy rØng, bao g(cid:229)m:
- C‚c ki(cid:213)n thłc v(cid:210) d›(cid:237)i vi ph'n suy rØng cæa Jeyakumar-Luc (1999);
- C‚c fii(cid:210)u ki(cid:214)n c˙n Fritz John cho cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng;
- C‚c fii(cid:210)u ki(cid:214)n ch(cid:221)nh quy;
- C‚c fii(cid:210)u ki(cid:214)n c˙n Karush-Kuhn-Tucker cho cøc ti(cid:211)u Pareto y(cid:213)u fi(cid:222)a ph›‹ng;
- C‚c fii(cid:210)u ki(cid:214)n fiæ cho cøc ti(cid:211)u Pareto y(cid:213)u.
L(cid:253) thuy(cid:213)t c‚c fii(cid:210)u ki(cid:214)n tŁi ›u cho nghi(cid:214)m h(cid:247)u hi(cid:214)u cæa b(cid:181)i to‚n tŁi ›u fia
m(cid:244)c ti“u kh«ng tr‹n d›(cid:237)i ng«n ng(cid:247) c‚c d›(cid:237)i vi ph'n l(cid:181) fi(cid:210) t(cid:181)i fi• v(cid:181) fiang fi›(cid:238)c
nhi(cid:210)u t‚c gi¶ quan t'm nghi“n cłu ph‚t tri(cid:211)n.
32
T(cid:181)i li(cid:214)u tham kh¶o
[T(cid:181)i li(cid:214)u Ti(cid:213)ng Vi(cid:214)t]
[1] §(cid:231) V¤n L›u, Phan Huy Kh¶ (2000), Gi¶i t(cid:221)ch l(cid:229)i, NXB khoa h(cid:228)c v(cid:181) k(cid:220)
thu¸t H(cid:181) NØi.
[2] §(cid:231) V¤n L›u (1999), Gi¶i t(cid:221)ch Lipschitz, NXB khoa h(cid:228)c v(cid:181) k(cid:220) thu¸t H(cid:181) NØi.
[T(cid:181)i li(cid:214)u Ti(cid:213)ng Anh]
[3] Aubin, J.P., Cellina, A. (1984): Differential Inclusions, Springer, Berlin.
[4] Clarke, F.H. (1983): Optimization and Nonsmooth Analysis, Wiley Inter-
science, New York.
[5] Demyanov, V.F. (1994): Convexification and concavification of a positively
homogeneous function by the same family of linear functions. Universia di
Pisa, Report 3, 208, 802.
[6] Demyanov, V.F., Rubinov, A.M. (1995): Constructive Nonsmooth Analysis,
Verlag Peter Lang, Frankfurt.
[7] Dutta, J., Chandra, S. (2004): Convexificators, generalized convexity and
vector optimization. Optimization 53, 77-94.
[8] Dutta, J., Chandra, S. (2002): Convexificators, generalized convexity and
optimality conditions. J. Optim. Theory Appl. 113, 41-65.
[9] Jeyakumar, V., Luc, D.T. (1999): Nonsmooth calculus, minimality, and
monotonicity of convexificators. J. Optim. Theory Appl. 101, 599-621.
33
[10] Jeyakumar, V., Luc, D.T. (1998): Approximate Jacobian matrices for non- smooth continuous maps and C 1 - optimization, SIAM J. Control Optim.
36, 1815-1832.
[11] Jim—nez, B., Novo, V. (2002): A finite dimensional extension of Lyusternik
theorem with applications to multiobjective optimization, J. Math. Anal.
Appl. 270, 340-356.
[12] Luc, D. T. (2002): A multiplier rule for multiobjective programming prob-
lems with continuous data. SIAM J. Optim. 13, 168-178.
[13] Luu, D. V. (2012): Necessary conditions for efficiency in terms of the
Michel-Penot subdifferentials, Optimization 61, 1099-1117.
[14] Luu, D. V. (2014): Necessary and sufficient conditions for efficiency via
convexificators, J. Optim. Theory Appl. 160, 510-526.
[15] Luu, D. V. (2014): Convexificators and necessary conditions for efficiency,
Optimization 63, 321-335.
[16] Mangassarian, O.L. (1969): Nonlinear Programming. McGraw-Hill, New
York.
[17] Michel, P., Penot, J. -P. (1984): Calcul sous-diff—rentiel pour des fonctions
lipschitziennes et nonlipschitziennes, C.R. Math. Acad. Sci. 12, 269-272.
[18] Mordukhovich, B.S., Shao, Y. (1995): On nonconvex subdifferential calcu-
lus in Banach spaces, J. Convex Anal. 2, 211-228.
[19] Rockafellar, R.T. (1970) : Convex Analysis, Priceton University Press,
Princeton.
[20] Yang, X.Q. (2005): Continuous generalized convex functions and their
characterizations. Optimization 54, 495-506.
