ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC -------------------------------
VÀNG VĂN HÀ
VỀ TOÁN TỬ CHIẾU METRIC LÊN TẬP LỒI ĐÓNG VÀ ỨNG DỤNG VÀO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2020
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC -------------------------------
VÀNG VĂN HÀ
VỀ TOÁN TỬ CHIẾU METRIC LÊN TẬP LỒI ĐÓNG VÀ ỨNG DỤNG VÀO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN
Chuyên ngành: Toán ứng dụng Mã số : 8 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH. Lê Dũng Mưu
THÁI NGUYÊN - 2020
M(cid:246)c l(cid:246)c
B£ng k(cid:254) hi»u i
L(cid:237)i c£m (cid:236)n ii
L(cid:237)i n(cid:226)i (cid:31)ƒu 1
Ch(cid:247)(cid:236)ng 1. Mºt sŁ ki‚n thøc chu'n b(cid:224) 3
1.1 T“p l(cid:231)i v(cid:160) h(cid:160)m l(cid:231)i . . . . . . . . . . . . . . . . . . . . . . 3
1.2 To¡n tß chi‚u kho£ng c¡ch . . . . . . . . . . . . . . . . . 15
Ch(cid:247)(cid:236)ng 2. (cid:217)ng d(cid:246)ng v(cid:160)o b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n 22
2.1 B(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n . . . . . . . . . . . . . 22
2.2 Mºt thu“t to¡n chi‚u gi£i b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n
ph¥n para-(cid:31)(cid:236)n (cid:31)i»u . . . . . . . . . . . . . . . . . . . . . 25
T(cid:160)i li»u tham kh£o 37
i
B£ng k(cid:254) hi»u
R t“p sŁ th(cid:252)c
Rn kh(cid:230)ng gian Euclide n-chi•u
∅ t“p rØng
∀x v(cid:238)i m(cid:229)i x
∃x t(cid:231)n t⁄i x
(cid:107)x(cid:107) chu'n cıa vect(cid:236) x
(cid:104)x, y(cid:105) t‰ch v(cid:230) h(cid:247)(cid:238)ng cıa hai v†c-t(cid:236) x v(cid:160) y
(cid:107)x(cid:107) chu'n cıa v†c-t(cid:236) x
V IP (F ; C) b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n
S(F ; C) t“p nghi»m cıa b(cid:160)i to¡n V IP (F ; C)
ii
L(cid:237)i c£m (cid:236)n
Lu“n v«n (cid:31)(cid:247)æc ho(cid:160)n th(cid:160)nh t⁄i Tr(cid:247)(cid:237)ng (cid:30)⁄i h(cid:229)c Khoa h(cid:229)c - (cid:30)⁄i h(cid:229)c
Th¡i Nguy¶n d(cid:247)(cid:238)i s(cid:252) h(cid:247)(cid:238)ng d¤n cıa GS.TSKH. L¶ D(cid:244)ng M(cid:247)u. T¡c gi£
xin b(cid:160)y t(cid:228) lÆng bi‚t (cid:236)n s¥u s›c t(cid:238)i Thƒy, ng(cid:247)(cid:237)i (cid:31)¢ d(cid:160)nh nhi•u th(cid:237)i gian,
t“n t…nh h(cid:247)(cid:238)ng d¤n v(cid:160) gi(cid:243)p (cid:31)(cid:239) t¡c gi£ trong suŁt qu¡ tr…nh nghi¶n cøu
v(cid:160) ho(cid:160)n thi»n lu“n v«n. T¡c gi£ c(cid:244)ng xin b(cid:160)y t(cid:228) lÆng bi‚t (cid:236)n ch¥n th(cid:160)nh
t(cid:238)i c¡c Thƒy C(cid:230) trong khoa To¡n-Tin tr(cid:247)(cid:237)ng (cid:30)⁄i h(cid:229)c Khoa h(cid:229)c, (cid:30)⁄i h(cid:229)c
Th¡i Nguy¶n (cid:31)¢ gi£ng d⁄y v(cid:160) gi(cid:243)p (cid:31)(cid:239) cho t¡c gi£ trong suŁt th(cid:237)i gian
h(cid:229)c t“p t⁄i Tr(cid:247)(cid:237)ng.
(cid:30)(cid:231)ng th(cid:237)i, t(cid:230)i c(cid:244)ng xin gßi l(cid:237)i c£m (cid:236)n t(cid:238)i gia (cid:31)…nh, b⁄n b– v(cid:160) (cid:31)(cid:231)ng
nghi»p (cid:31)¢ t⁄o (cid:31)i•u ki»n thu“n læi nh§t cho t(cid:230)i trong th(cid:237)i gian h(cid:229)c t“p
v(cid:160) trong qu¡ tr…nh ho(cid:160)n th(cid:160)nh lu“n v«n.
Xin ch¥n th(cid:160)nh c£m (cid:236)n!
Th¡i Nguy¶n, th¡ng 05 n«m 2020.
T¡c gi£
V(cid:160)ng V«n H(cid:160)
1
L(cid:237)i n(cid:226)i (cid:31)ƒu
Trong ch(cid:247)(cid:236)ng tr…nh to¡n phŒ th(cid:230)ng, ch(cid:243)ng ta (cid:31)¢ l(cid:160)m quen v(cid:238)i ph†p
chi‚u vu(cid:230)ng g(cid:226)c xuŁng mºt m(cid:176)t phflng trong khi gi£i c¡c b(cid:160)i to¡n h…nh
h(cid:229)c v(cid:160) l(cid:247)æng gi¡c. Kh¡i ni»m n(cid:160)y (cid:31)¢ (cid:31)(cid:247)æc m(cid:240) rºng l¶n kh(cid:230)ng gian nhi•u
chi•u, th“m ch‰ v(cid:230) h⁄n chi•u c(cid:242)ng v(cid:238)i vi»c thay m(cid:176)t phflng b‹ng mºt t“p
l(cid:231)i (cid:31)(cid:226)ng v(cid:160) v(cid:238)i mºt kho£ng c¡ch (metric) kh(cid:230)ng nh§t thi‚t l(cid:160) kho£ng c¡ch
(cid:204)-c(cid:236)-lit. (cid:129)nh x⁄ chuy”n mºt (cid:31)i”m b§t k(cid:253) cho tr(cid:247)(cid:238)c trong kh(cid:230)ng gian
(cid:31)‚n mºt (cid:31)i”m trong mºt t“p cho tr(cid:247)(cid:238)c v(cid:238)i kho£ng c¡ch nh(cid:228) nh§t (cid:31)(cid:247)æc
g(cid:229)i l(cid:160) to¡n tß chi‚u l¶n t“p (cid:31)(cid:226). Ng(cid:247)(cid:237)i ta (cid:31)¢ ch¿ ra r‹ng, trong kh(cid:230)ng gian
Hilbert th(cid:252)c, to¡n tß chi‚u l¶n mºt t“p l(cid:231)i (cid:31)(cid:226)ng (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh duy nh§t.
To¡n tß chi‚u chi‚u l¶n t“p l(cid:231)i (cid:31)(cid:226)ng c(cid:226) nhi•u (cid:31)(cid:176)c tr(cid:247)ng th(cid:243) v(cid:224), do (cid:31)(cid:226)
n(cid:226) c(cid:226) vai trÆ quan tr(cid:229)ng trong nhi•u v§n (cid:31)• cıa to¡n h(cid:229)c v(cid:160) th(cid:252)c t‚ nh(cid:247)
trong l(cid:254) thuy‚t x§p x¿, tŁi (cid:247)u h(cid:226)a, b§t (cid:31)flng thøc bi‚n ph¥n, c¥n b‹ng
v(cid:160) nhi•u l(cid:190)nh v(cid:252)c kh¡c.
Nºi dung cıa b£n lu“n v«n bao g(cid:231)m c¡c ki‚n thøc c(cid:236) b£n nh§t v• t“p l(cid:231)i trong kh(cid:230)ng gian (cid:204)-c(cid:236)-lit Rn, c¡c k‚t qu£ v• to¡n tß chi‚u l¶n
t“p l(cid:231)i (cid:31)(cid:226)ng. Nºi dung ch‰nh ti‚p theo li¶n quan (cid:31)‚n vi»c ¡p d(cid:246)ng to¡n
tß chi‚u v(cid:160)o vi»c gi£i b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n para-(cid:31)(cid:236)n (cid:31)i»u trong kh(cid:230)ng gian Rn.
Ngo(cid:160)i phƒn m(cid:240) (cid:31)ƒu, k‚t lu“n v(cid:160) t(cid:160)i li»u tham kh£o, c¡c k‚t qu£ nghi¶n
2
cøu trong b£n lu“n v«n (cid:31)(cid:247)æc tr…nh b(cid:160)y th(cid:160)nh hai ch(cid:247)(cid:236)ng v(cid:238)i ti¶u (cid:31)•:
Ch(cid:247)(cid:236)ng 1: Mºt sŁ ki‚n thøc chu'n b(cid:224).
Ch(cid:247)(cid:236)ng 2: (cid:217)ng d(cid:246)ng v(cid:160)o b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n.
Nºi dung ch‰nh cıa c¡c ch(cid:247)(cid:236)ng nh(cid:247) sau:
Trong ch(cid:247)(cid:236)ng 1, t(cid:230)i tr…nh b(cid:160)y (cid:31)(cid:224)nh ngh(cid:190)a t“p l(cid:231)i, mºt sŁ t‰nh ch§t c(cid:236)
b£n cıa t“p l(cid:231)i, h(cid:160)m l(cid:231)i. Ti‚p theo l(cid:160) tr…nh b(cid:160)y (cid:31)(cid:224)nh l(cid:254) t¡ch c¡c t“p l(cid:231)i.
Mºt phƒn cıa ch(cid:247)(cid:236)ng tr…nh b(cid:160)y v• (cid:31)(cid:224)nh ngh(cid:190)a to¡n tß chi‚u, mºt sŁ t‰nh
ch§t c(cid:236) b£n cıa to¡n tß chi‚u.
Ch(cid:247)(cid:236)ng 2 cıa lu“n v«n tr…nh b(cid:160)y øng d(cid:246)ng cıa to¡n tß chi‚u metric
l¶n mºt t“p l(cid:231)i (cid:31)(cid:226)ng v(cid:160)o vi»c gi£i b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n.
B§t (cid:31)flng thøc bi‚n ph¥n l(cid:160) mºt l(cid:238)p b(cid:160)i to¡n quan tr(cid:229)ng cıa Gi£i t‰ch
øng d(cid:246)ng. B(cid:160)i to¡n n(cid:160)y l(cid:160) mºt l(cid:238)p b(cid:160)i to¡n tŒng qu¡t cıa b(cid:160)i to¡n quy
ho⁄ch l(cid:231)i; h(cid:236)n nœa nhi•u b(cid:160)i to¡n trong ph(cid:247)(cid:236)ng tr…nh vi ph¥n, (cid:31)⁄o h(cid:160)m
ri¶ng (cid:31)•u c(cid:226) th” m(cid:230) t£ d(cid:247)(cid:238)i b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n.
3
Ch(cid:247)(cid:236)ng 1. Mºt sŁ ki‚n thøc chu'n
b(cid:224)
Nºi dung ch‰nh cıa ch(cid:247)(cid:236)ng tr…nh b(cid:160)y (cid:31)(cid:224)nh ngh(cid:190)a, mºt sŁ t‰nh ch§t c(cid:236)
b£n, (cid:31)(cid:224)nh l(cid:254) v(cid:160) bŒ (cid:31)• li¶n quan (cid:31)‚n t“p l(cid:231)i v(cid:160) h(cid:160)m l(cid:231)i. Mºt phƒn cıa
ch(cid:247)(cid:236)ng (cid:31)• c“p (cid:31)‚n ph†p chi‚u metric, chøng minh s(cid:252) t(cid:231)n t⁄i v(cid:160) t‰nh duy
nh§t cıa h…nh chi‚u l¶n mºt t“p l(cid:231)i (cid:31)(cid:226)ng v(cid:160) kh£o s¡t mºt sŁ t‰nh ch§t
c(cid:236) b£n cıa to¡n tß chi‚u. Nºi dung ch‰nh cıa ch(cid:247)(cid:236)ng n(cid:160)y (cid:31)(cid:247)æc tham
kh£o chı y‚u tł c¡c t(cid:160)i li»u [1, 3].
1.1 T“p l(cid:231)i v(cid:160) h(cid:160)m l(cid:231)i
Tr(cid:247)(cid:238)c h‚t, ch(cid:243)ng t(cid:230)i gi(cid:238)i thi»u kh¡i ni»m v• t“p l(cid:231)i v(cid:160) mºt sŁ t‰nh
ch§t cƒn thi‚t.
Nh›c l⁄i r‹ng, mºt (cid:31)(cid:247)(cid:237)ng thflng nŁi hai (cid:31)i”m (hai v†c-t(cid:236)) a, b trong
Rn l(cid:160) t“p hæp t§t c£ c¡c v†c-t(cid:236) x ∈ Rn c(cid:226) d⁄ng
{x ∈ Rn|x = αa + βb, α, β ∈ Rn, α + β = 1}.
(cid:30)o⁄n thflng nŁi hai (cid:31)i”m a v(cid:160) b trong Rn l(cid:160) t“p hæp c¡c v†c-t(cid:236) x c(cid:226) d⁄ng
{x ∈ Rn|x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}.
(cid:30)(cid:224)nh ngh(cid:190)a 1.1. Mºt t“p C ⊆ Rn (cid:31)(cid:247)æc g(cid:229)i l(cid:160) mºt t“p l(cid:231)i, n‚u C chøa
m(cid:229)i (cid:31)o⁄n thflng (cid:31)i qua hai (cid:31)i”m b§t k(cid:253) cıa n(cid:226). Tøc l(cid:160) C l(cid:231)i khi v(cid:160) ch¿ khi
4
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
V‰ d(cid:246) 1.1.
a) T“p ∅ v(cid:160) Rn l(cid:160) c¡c t“p con l(cid:231)i cıa Rn.
(cid:30)o⁄n thflng AB l(cid:160) mºt t“p l(cid:231)i.
H…nh trÆn bao g(cid:231)m c£ bi¶n m(cid:160)u n¥u l(cid:160) mºt t“p l(cid:231)i, v… (cid:31)o⁄n thflng nŁi
H…nh 1.1: T“p l(cid:231)i
hai (cid:31)i”m X, Y trong h…nh trÆn n‹m tr(cid:229)n v(cid:181)n trong h…nh trÆn.
b) H…nh d(cid:247)(cid:238)i (cid:31)¥y l(cid:160) hai t“p kh(cid:230)ng l(cid:231)i, v… c¡c (cid:31)(cid:247)(cid:237)ng n†t (cid:31)øt chøa nhi•u
H…nh 1.2: T“p kh(cid:230)ng l(cid:231)i
(cid:31)i”m kh(cid:230)ng n‹m trong c¡c t“p (cid:31)(cid:226).
k (cid:88)
k (cid:88)
(cid:30)(cid:224)nh ngh(cid:190)a 1.2. Ta n(cid:226)i x l(cid:160) tŒ hæp l(cid:231)i cıa c¡c (cid:31)i”m x1, . . . , xk n‚u
j=1
j=1
x = λjxj, λj > 0 ∀j = 1, . . . , k, λj = 1.
5
M»nh (cid:31)• 1.1. T“p hæp C l(cid:160) l(cid:231)i khi v(cid:160) ch¿ khi n(cid:226) chøa m(cid:229)i tŒ hæp l(cid:231)i
k (cid:88)
k (cid:88)
cıa c¡c (cid:31)i”m cıa n(cid:226). Tøc l(cid:160): C l(cid:231)i khi v(cid:160) ch¿ khi
j=1
j=1
∀k ∈ N, ∀λ1, . . . , λk > 0 : λj = 1, ∀x1, . . . , xk ∈ C ⇒ λjxj ∈ C.
Chøng minh. (cid:30)i•u ki»n (cid:31)ı l(cid:160) hi”n nhi¶n tł (cid:31)(cid:224)nh ngh(cid:190)a. Ta chøng minh
(cid:31)i•u ki»n cƒn b‹ng quy n⁄p theo sŁ (cid:31)i”m. V(cid:238)i k = 2, (cid:31)i•u cƒn chøng
minh suy ra ngay tł (cid:31)(cid:224)nh ngh(cid:190)a cıa t“p l(cid:231)i v(cid:160) tŒ hæp l(cid:231)i. Gi£ sß m»nh
(cid:31)• (cid:31)(cid:243)ng v(cid:238)i k − 1 (cid:31)i”m. Ta cƒn chøng minh v(cid:238)i k (cid:31)i”m.
k (cid:88)
k (cid:88)
Gi£ sß x l(cid:160) tŒ hæp l(cid:231)i cıa k (cid:31)i”m x1, . . . , xk ∈ C. Tøc l(cid:160)
j=1
j=1
x = λjxj, λj > 0 ∀j = 1, . . . , k, λj = 1.
k−1 (cid:88)
(cid:30)(cid:176)t
j=1
ξ = λj.
k−1 (cid:88)
Khi (cid:31)(cid:226) 0 < ξ < 1 v(cid:160)
j=1
k−1 (cid:88)
x = λjxj + λkxk
j=1
= ξ (1.1) xj + λkxk. λj ξ
k−1 (cid:88)
Do
j=1
= 1 λj ξ
ξ > 0 v(cid:238)i m(cid:229)i j = 1, . . . , k − 1, n¶n theo gi£ thi‚t quy n⁄p, (cid:31)i”m
k−1 (cid:88)
v(cid:160) λj
j=1
y := xj ∈ C. λj ξ
6
Ta c(cid:226)
x = ξy + λxk.
k (cid:88)
Do ξ > 0, λk > 0 v(cid:160)
j=1
ξ + λk = λj = 1,
n¶n x l(cid:160) mºt tŒ hæp l(cid:231)i cıa hai (cid:31)i”m y v(cid:160) xk (cid:31)•u thuºc C. V“y x ∈ C.
L(cid:238)p c¡c t“p l(cid:231)i l(cid:160) (cid:31)(cid:226)ng v(cid:238)i c¡c ph†p giao, ph†p cºng (cid:31)⁄i sŁ v(cid:160) ph†p
nh¥n t‰ch Descartes. C(cid:246) th”, ta c(cid:226) m»nh (cid:31)• sau:
M»nh (cid:31)• 1.2. N‚u A, B l(cid:160) c¡c t“p l(cid:231)i trong Rn, C l(cid:160) l(cid:231)i trong Rm, th…
c¡c t“p sau l(cid:160) l(cid:231)i:
(i) A ∩ B := {x|x ∈ A, x ∈ B},
(ii) λA + βB := {x|x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R},
(iii) A × C := {x ∈ Rn+m|x = (a, c) : a ∈ A, c ∈ C}.
Chøng minh. D„ d(cid:160)ng (cid:31)(cid:247)æc suy ra tr(cid:252)c ti‚p tł (cid:31)(cid:224)nh ngh(cid:190)a.
(cid:30)(cid:224)nh ngh(cid:190)a 1.3. Ta n(cid:226)i x l(cid:160) tŒ hæp a-phin cıa c¡c (cid:31)i”m (v†c-t(cid:236))
k (cid:88)
k (cid:88)
x1, . . . , xk n‚u
j=1
j=1
x = λjxj, λj = 1.
T“p hæp cıa c¡c tŒ hæp a-phin cıa x1, . . . , xk th(cid:247)(cid:237)ng (cid:31)(cid:247)æc g(cid:229)i l(cid:160) bao
a-phin cıa c¡c (cid:31)i”m n(cid:160)y.
(cid:30)(cid:224)nh ngh(cid:190)a 1.4. Mºt t“p C (cid:31)(cid:247)æc g(cid:229)i l(cid:160) t“p a-phin n‚u n(cid:226) chøa (cid:31)(cid:247)(cid:237)ng
thflng (cid:31)i qua hai (cid:31)i”m b§t k(cid:253) cıa n(cid:226), tøc l(cid:160)
∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C.
7
V“y t“p a-phin l(cid:160) mºt tr(cid:247)(cid:237)ng hæp ri¶ng cıa t“p l(cid:231)i.
V‰ d(cid:246) 1.2. Mºt v‰ d(cid:246) (cid:31)i”n h…nh cıa t“p a-phin l(cid:160) c¡c kh(cid:230)ng gian con.
M»nh (cid:31)• 1.3. M (cid:54)= ∅ l(cid:160) t“p a-phin khi v(cid:160) ch¿ khi n(cid:226) c(cid:226) d⁄ng M = L+a
v(cid:238)i L l(cid:160) mºt kh(cid:230)ng gian con v(cid:160) a ∈ M , kh(cid:230)ng gian con L n(cid:160)y (cid:31)(cid:247)æc x¡c
(cid:31)(cid:224)nh duy nh§t.
Kh(cid:230)ng gian L trong m»nh (cid:31)• tr¶n (cid:31)(cid:247)æc g(cid:229)i l(cid:160) kh(cid:230)ng gian con song
song v(cid:238)i M , ho(cid:176)c n(cid:226)i ng›n g(cid:229)n h(cid:236)n l(cid:160) kh(cid:230)ng gian con cıa M . Chi•u cıa
mºt t“p a-phin M (cid:31)(cid:247)æc (cid:31)(cid:224)nh ngh(cid:190)a b(cid:240)i chi•u cıa kh(cid:230)ng gian song song
v(cid:238)i M v(cid:160) (cid:31)(cid:247)æc k(cid:254) hi»u l(cid:160) dimM .
M»nh (cid:31)• 1.4. B§t k(cid:253) mºt t“p a-phin M ⊂ Rn c(cid:226) sŁ chi•u r (cid:31)•u c(cid:226) d⁄ng
M = {x ∈ Rn : Ax = b}, (1.2)
trong (cid:31)(cid:226) A l(cid:160) ma tr“n c§p (m × n), b ∈ Rm v(cid:160) rankA = n − r. Ng(cid:247)æc
l⁄i, m(cid:229)i t“p hæp c(cid:226) d⁄ng (1.2) v(cid:238)i rankA = n − r (cid:31)•u l(cid:160) t“p a-phin c(cid:226) sŁ
chi•u l(cid:160) r.
(cid:30)(cid:224)nh ngh(cid:190)a 1.5. Mºt t“p C (cid:31)(cid:247)æc g(cid:229)i l(cid:160) n(cid:226)n n‚u
∀λ > 0, ∀x ∈ C ⇒ λx ∈ C.
Mºt n(cid:226)n (cid:31)(cid:247)æc g(cid:229)i l(cid:160) n(cid:226)n l(cid:231)i n‚u n(cid:226) (cid:31)(cid:231)ng th(cid:237)i l(cid:160) mºt t“p l(cid:231)i.
V‰ d(cid:246) 1.3.
+ = {x ∈ Rn : x ≥ 0} l(cid:160) mºt n(cid:226)n l(cid:231)i.
a) T“p Rn
b) Cho bα ∈ Rn (α ∈ I) v(cid:238)i I l(cid:160) t“p ch¿ sŁ n(cid:160)o (cid:31)(cid:226). Khi (cid:31)(cid:226) t“p
K = {x ∈ Rn : (cid:104)x, bα(cid:105) ≤ 0, ∀α ∈ I}
8
α∈I
l(cid:160) mºt n(cid:226)n l(cid:231)i v… K = (cid:84) Kα, v(cid:238)i Kα = {x ∈ Rn : (cid:104)x, bα(cid:105) ≤ 0} l(cid:160) n(cid:226)n l(cid:231)i.
M»nh (cid:31)• 1.5. Mºt t“p C l(cid:160) n(cid:226)n l(cid:231)i khi v(cid:160) ch¿ khi n(cid:226) c(cid:226) c¡c t‰nh ch§t sau:
(i) λC ⊆ C, ∀λ > 0;
(ii) C + C ⊆ C.
Ti‚p theo, ch(cid:243)ng t(cid:230)i gi(cid:238)i thi»u kh¡i ni»m h(cid:160)m l(cid:231)i v(cid:160) (cid:31)(cid:224)nh l‰ t¡ch c¡c
t“p l(cid:231)i.
(cid:30)(cid:224)nh ngh(cid:190)a 1.6.
(i) Cho h(cid:160)m f : C → R x¡c (cid:31)(cid:224)nh tr¶n mºt t“p l(cid:231)i C ⊆ Rn. Khi (cid:31)(cid:226) f
(cid:31)(cid:247)æc g(cid:229)i l(cid:160) h(cid:160)m l(cid:231)i n‚u v(cid:238)i m(cid:229)i x, y ∈ C v(cid:160) m(cid:229)i λ ∈ (0, 1) ta c(cid:226)
f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ)f (y).
H…nh 1.3: H(cid:160)m l(cid:231)i
H…nh d(cid:247)(cid:238)i (cid:31)¥y l(cid:160) mºt h(cid:160)m l(cid:231)i.
(ii) H(cid:160)m f (cid:31)(cid:247)æc g(cid:229)i l(cid:160) h(cid:160)m l(cid:231)i ch(cid:176)t tr¶n C n‚u v(cid:238)i m(cid:229)i x, y ∈ C, x (cid:54)= y
v(cid:160) m(cid:229)i sŁ th(cid:252)c λ ∈ (0, 1) ta c(cid:226)
f [λx + (1 − λ)y] < λf (x) + (1 − λ)f (y).
(iii) H(cid:160)m f (cid:31)(cid:247)æc g(cid:229)i l(cid:160) h(cid:160)m l(cid:231)i m⁄nh tr¶n C v(cid:238)i h» sŁ η > 0 n‚u v(cid:238)i
9
m(cid:229)i x, y ∈ C, x (cid:54)= y v(cid:160) m(cid:229)i sŁ th(cid:252)c λ ∈ (0, 1) ta c(cid:226)
f [λx + (1 − λ)y] < λf (x) + (1 − λ)f (y) − ηλ(1 − λ)(cid:107)x − y(cid:107)2. 1 2
(cid:30)(cid:224)nh ngh(cid:190)a 1.7.
(i) H(cid:160)m f (cid:31)(cid:247)æc g(cid:229)i l(cid:160) h(cid:160)m lªm tr¶n C n‚u −f l(cid:160) h(cid:160)m l(cid:231)i tr¶n C.
(ii) H(cid:160)m f (cid:31)(cid:247)æc g(cid:229)i l(cid:160) h(cid:160)m tuy‚n t‰nh a-phin (hay h(cid:160)m a-phin) tr¶n C
n‚u f hœu h⁄n v(cid:160) vła l(cid:231)i, vła lªm tr¶n C.
V‰ d(cid:246) 1.4.
a) M(cid:229)i h(cid:160)m chu'n (cid:31)•u l(cid:160) h(cid:160)m l(cid:231)i tr¶n Rn:
i=1
(cid:32) n (cid:33)1/p (cid:88) (cid:107)x(cid:107)p = |xi|p |xi|. v(cid:238)i p ≥ 1 v(cid:160) (cid:107)x(cid:107)∞ = max 1≤i≤n
b) H(cid:160)m kho£ng c¡ch tł (cid:31)i”m x ∈ Rn t(cid:238)i C (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh b(cid:240)i dC(x) =
inf y∈C (cid:107)x − y(cid:107) l(cid:160) h(cid:160)m l(cid:231)i.
(cid:30)(cid:224)nh ngh(cid:190)a 1.8. Cho f : Rn → R ∪ {+∞}. Ta n(cid:226)i x∗ ∈ Rn l(cid:160) d(cid:247)(cid:238)i (cid:31)⁄o
h(cid:160)m cıa f t⁄i x n‚u
(cid:104)x∗, z − x(cid:105) + f (x) ≤ f (z), ∀z ∈ Rn.
T“p hæp t§t c£ c¡c d(cid:247)(cid:238)i (cid:31)⁄o h(cid:160)m cıa f t⁄i x (cid:31)(cid:247)æc g(cid:229)i l(cid:160) d(cid:247)(cid:238)i vi ph¥n
cıa f t⁄i x v(cid:160) (cid:31)(cid:247)æc k‰ hi»u l(cid:160) ∂f (x).
BŒ (cid:31)• 1.1. Cho C l(cid:160) mºt t“p con l(cid:231)i cıa Rn. Mºt h(cid:160)m kh£ vi f : C → R
l(cid:160) l(cid:231)i khi v(cid:160) ch¿ khi
f (x) − f (y) ≥ (cid:104)(cid:53)f (y), x − y(cid:105), ∀x, y ∈ C.
(cid:30)(cid:224)nh ngh(cid:190)a 1.9. Si¶u phflng trong kh(cid:230)ng gian Rn l(cid:160) mºt t“p hæp c¡c
(cid:31)i”m c(cid:226) d⁄ng
{x ∈ Rn : aT x = α},
10
trong (cid:31)(cid:226) a ∈ Rn l(cid:160) mºt v†c-t(cid:236) kh¡c 0 v(cid:160) α ∈ R.
V†c-t(cid:236) a th(cid:247)(cid:237)ng (cid:31)(cid:247)æc g(cid:229)i l(cid:160) v†c-t(cid:236) ph¡p tuy‚n cıa si¶u phflng. Mºt
si¶u phflng s‡ chia kh(cid:230)ng gian ra hai nßa kh(cid:230)ng gian. Nßa kh(cid:230)ng gian
(cid:31)(cid:247)æc (cid:31)(cid:224)nh ngh(cid:190)a nh(cid:247) sau:
(cid:30)(cid:224)nh ngh(cid:190)a 1.10. Nßa kh(cid:230)ng gian l(cid:160) mºt t“p hæp c(cid:226) d⁄ng
{x ∈ Rn : aT x ≥ α},
trong (cid:31)(cid:226) a (cid:54)= 0 v(cid:160) α ∈ R.
(cid:30)(cid:224)nh ngh(cid:190)a 1.11. Cho hai t“p C v(cid:160) D kh¡c rØng, ta n(cid:226)i si¶u phflng
aT x = α t¡ch C v(cid:160) D n‚u
aT x ≤ α ≤ aT y, ∀x ∈ C, ∀y ∈ D. (1.3)
Ta n(cid:226)i si¶u phflng aT x = α t¡ch ch(cid:176)t C v(cid:160) D n‚u
aT x < α < aT y, ∀x ∈ C, ∀y ∈ D.
(cid:30)(cid:224)nh l(cid:254) 1.1. ((cid:30)(cid:224)nh l(cid:254) t¡ch 1) Cho C v(cid:160) D l(cid:160) hai t“p l(cid:231)i kh¡c rØng trong Rn sao cho C ∩ D = ∅. Khi
(cid:31)(cid:226) c(cid:226) mºt si¶u phflng t¡ch C v(cid:160) D.
(cid:30)(cid:224)nh l(cid:254) t¡ch vła n¶u c(cid:226) th” suy ra ngay tł BŒ (cid:31)• 1.2 d(cid:247)(cid:238)i (cid:31)¥y, ch‰nh
l(cid:160) (cid:31)(cid:224)nh l(cid:254) t¡ch mºt t“p l(cid:231)i v(cid:160) mºt phƒn tß kh(cid:230)ng thuºc n(cid:226).
BŒ (cid:31)• 1.2. (BŒ (cid:31)• li¶n thuºc) Cho C ⊂ Rn l(cid:160) mºt t“p l(cid:231)i kh¡c rØng. Gi£ sß x0 ∈ C. Khi (cid:31)(cid:226) t(cid:231)n t⁄i t ∈ Rn, t (cid:54)= 0 tho£ m¢n
(cid:104)t, x(cid:105) ≥ (cid:104)t, x0(cid:105) ∀x ∈ C. (1.4)
11
Chøng minh (cid:30)(cid:224)nh l(cid:254) 1.1. Do C v(cid:160) D l(cid:160) l(cid:231)i, n¶n C − D c(cid:244)ng l(cid:231)i. H(cid:236)n nœa
0 /∈ (C − D), v… C ∩ D = ∅. Theo bŒ (cid:31)• tr¶n ¡p d(cid:246)ng v(cid:238)i x0 = 0, t(cid:231)n t⁄i v†c-t(cid:236) t ∈ Rn, t (cid:54)= 0 sao cho (cid:104)t, z(cid:105) ≥ 0 v(cid:238)i m(cid:229)i z ∈ C − D. V… z = x − y
v(cid:238)i x ∈ C, y ∈ D, n¶n ta c(cid:226)
(cid:104)t, x(cid:105) ≥ (cid:104)t, y(cid:105) ∀x ∈ C, y ∈ D.
L§y
(cid:104)t, y(cid:105), α := sup y∈D
khi (cid:31)(cid:226) si¶u phflng (cid:104)t, x(cid:105) t¡ch C v(cid:160) D.
(cid:30)(cid:224)nh l(cid:254) 1.2. ((cid:30)(cid:224)nh l(cid:254) t¡ch 2)
Cho C v(cid:160) D l(cid:160) hai t“p l(cid:231)i, (cid:31)(cid:226)ng, kh¡c rØng sao cho C ∩ D = ∅. Gi£ sß
c(cid:226) ‰t nh§t mºt t“p l(cid:160) compact. Khi (cid:31)(cid:226) hai t“p n(cid:160)y c(cid:226) th” t¡ch m⁄nh (cid:31)(cid:247)æc
b(cid:240)i mºt si¶u phflng.
C(cid:244)ng nh(cid:247) tr¶n, (cid:31)(cid:224)nh l(cid:254) t¡ch m⁄nh (cid:31)(cid:247)æc d„ d(cid:160)ng suy ra tł bŒ (cid:31)• sau n(cid:226)i
v• s(cid:252) t¡ch m⁄nh giœa mºt t“p l(cid:231)i (cid:31)(cid:226)ng v(cid:160) mºt (cid:31)i”m b¶n ngo(cid:160)i t“p n(cid:160)y.
BŒ (cid:31)• 1.3. Cho C ⊂ Rn l(cid:160) mºt t“p l(cid:231)i, (cid:31)(cid:226)ng, kh¡c rØng sao cho 0 /∈ C. Khi (cid:31)(cid:226) t(cid:231)n t⁄i mºt v†c-t(cid:236) t ∈ Rn, t (cid:54)= 0 v(cid:160) α > 0 sao cho
(cid:104)t, x(cid:105) ≥ α > 0, ∀x ∈ C.
Theo bŒ (cid:31)• n(cid:160)y, th… C v(cid:160) (cid:31)i”m gŁc to⁄ (cid:31)º c(cid:226) th” t¡ch m⁄nh, v‰ d(cid:246) b(cid:240)i
. si¶u phflng (cid:104)t, x(cid:105) = α 2
Chøng minh bŒ (cid:31)•. Do C (cid:31)(cid:226)ng v(cid:160) 0 ∈ C, n¶n t(cid:231)n t⁄i qu£ cƒu B t¥m (cid:240)
gŁc, b¡n k‰nh r > 0 sao cho C ∩ B = ∅. (cid:129)p d(cid:246)ng (cid:31)(cid:224)nh l(cid:254) t¡ch 1 cho hai
12
t“p C v(cid:160) B, ta c(cid:226) t ∈ Rn \ {0} v(cid:160) α ∈ R, sao cho
(cid:104)t, x(cid:105) ≥ α ≥ (cid:104)t, y(cid:105)∀x ∈ C, ∀y ∈ B.
B‹ng c¡ch chu'n h(cid:226)a ta c(cid:226) th” xem (cid:107)t(cid:107) = 1 v(cid:160) do (cid:31)(cid:226) kho£ng c¡ch tł
gŁc (cid:31)‚n si¶u phflng ‰t nh§t l(cid:160) b‹ng α ≥ r. V“y th…
(cid:104)t, x(cid:105) ≥ α ≥ r > 0.
Chøng minh (cid:30)(cid:224)nh l(cid:254) 1.2. Gi£ sß C l(cid:160) t“p compact. Ta ch¿ ra t“p C − D
(cid:31)(cid:226)ng. Th“t v“y, gi£ sß zk ∈ C − D v(cid:160) zk → z. Ta c(cid:226) zk = xk − yk
v(cid:238)i xk ∈ C, yk ∈ D. V… C compact, n¶n c(cid:226) mºt d¢y con xkj → x khi
j → +∞. V“y ykj = zkj − xkj → z − x ∈ D. V“y z = x − y ∈ C − D.
Chøng t(cid:228) C − D l(cid:160) t“p (cid:31)(cid:226)ng. Do 0 /∈ C − D, n¶n theo bŒ (cid:31)• tr¶n, t(cid:231)n
t⁄i t (cid:54)= 0, sao cho (cid:104)t, x − y(cid:105) ≥ α > 0 v(cid:238)i m(cid:229)i x ∈ C, y ∈ D. V“y
(cid:104)t, x(cid:105) − (cid:104)t, y(cid:105) + . inf x∈C α 2 α 2 ≥ sup y∈D
Chøng t(cid:228) C v(cid:160) D c(cid:226) th” t¡ch m⁄nh.
Ch(cid:243) (cid:254) 1.1. (cid:30)i•u ki»n mºt trong hai t“p l(cid:160) compact trong (cid:31)(cid:224)nh l(cid:254) l(cid:160)
kh(cid:230)ng th” b(cid:228) (cid:31)(cid:247)æc. H¢y x†t v‰ d(cid:246) trong (cid:31)(cid:226)
C := {(x, t) ∈ R2 : x ≥ 0, t = 0}, D := {(x, t) ∈ R2 : t ≥ , t > 0, x > 0}. 1 x
Rª r(cid:160)ng hai t“p n(cid:160)y l(cid:231)i, (cid:31)(cid:226)ng kh(cid:230)ng c(cid:226) (cid:31)i”m chung, nh(cid:247)ng ch(cid:243)ng kh(cid:230)ng
th” t¡ch m⁄nh (cid:31)(cid:247)æc. (Xem h…nh 1.4).
Tł (cid:31)(cid:224)nh ngh(cid:190)a ta th§y r‹ng, n‚u hai t“p n‹m trong c(cid:242)ng mºt si¶u
phflng, th… ch(cid:243)ng v¤n t¡ch (cid:31)(cid:247)æc, v‰ d(cid:246) ch‰nh b‹ng si¶u phflng (cid:31)(cid:226).
(cid:30)” lo⁄i b(cid:228) tr(cid:247)(cid:237)ng hæp c(cid:252)c (cid:31)oan n(cid:160)y, ng(cid:247)(cid:237)i ta (cid:31)(cid:247)a ra kh¡i ni»m t¡ch
(cid:31)(cid:243)ng sau:
13
(a) T¡ch nh(cid:247)ng kh(cid:230)ng t¡ch m⁄nh
(b) T¡ch m⁄nh
H…nh 1.4: T¡ch v(cid:160) t¡ch m⁄nh
Ta n(cid:226)i hai t“p C v(cid:160) D (cid:31)(cid:247)æc t¡ch (cid:31)(cid:243)ng b(cid:240)i si¶u phflng aT x = α n‚u
(1.12) th(cid:228)a m¢n v(cid:160) c£ hai t“p n(cid:160)y kh(cid:230)ng c(cid:242)ng n‹m tr(cid:229)n trong si¶u phflng
t¡ch.
Ch(cid:243) (cid:254) r‹ng n‚u A v(cid:160) B l(cid:160) hai t“p l(cid:231)i m(cid:160) riA∩riB (cid:54)= ∅, th… hai t“p n(cid:160)y
v¤n c(cid:226) th” t¡ch (cid:31)(cid:247)æc, v‰ d(cid:246) A v(cid:160) B l(cid:160) hai (cid:31)(cid:247)(cid:237)ng ch†o cıa mºt h…nh chœ
nh“t trong m(cid:176)t phflng 2 chi•u. Tuy nhi¶n ch(cid:243)ng kh(cid:230)ng th” t¡ch (cid:31)(cid:243)ng.
Mºt h» qu£ r§t quan tr(cid:229)ng cıa (cid:31)(cid:224)nh l(cid:254) t¡ch l(cid:160) bŒ (cid:31)• ch(cid:229)n mang t¶n
nh(cid:160) to¡n h(cid:229)c Farkas ng(cid:247)(cid:237)i Hungary, (cid:31)(cid:247)æc chøng minh tł n«m 1892 d(cid:247)(cid:238)i
d⁄ng mºt (cid:31)(cid:224)nh l(cid:254) h…nh h(cid:229)c. BŒ (cid:31)• n(cid:160)y r§t tr(cid:252)c quan, d„ ¡p d(cid:246)ng trong
nhi•u l(cid:190)nh v(cid:252)c nh(cid:247) tŁi (cid:247)u, (cid:31)i•u khi”n, l(cid:254) thuy‚t to¡n tß v.v...
H» qu£ 1.1. Cho A l(cid:160) mºt ma tr“n th(cid:252)c c§p m × n v(cid:160) a ∈ Rn. Khi (cid:31)(cid:226)
trong hai h» d(cid:247)(cid:238)i (cid:31)¥y c(cid:226) mºt h» v(cid:160) ch¿ duy nh§t mºt h» c(cid:226) nghi»m:
Ax ≥ 0, aT x < 0 v(cid:238)i mºt x ∈ Rn, (1.5)
AT y = a, y ≥ 0 v(cid:238)i mºt y ∈ Rm. (1.6)
Mºt c¡ch ph¡t bi”u t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng, d(cid:247)(cid:238)i ng(cid:230)n ngœ h…nh h(cid:229)c, cıa BŒ (cid:31)•
Farkas l(cid:160):
14
Nßa kh(cid:230)ng gian {x|aT x ≥ 0} chøa n(cid:226)n {x|Ax ≥ 0} khi v(cid:160) ch¿ khi
v†c-t(cid:236) a n‹m trong n(cid:226)n sinh b(cid:240)i c¡c h(cid:160)ng cıa ma tr“n A. Tøc l(cid:160)
AT x ≥ 0 ⇒ aT x ≥ 0 khi v(cid:160) ch¿ khi AT y = a, y ≥ 0.
T‰nh ch§t h…nh h(cid:229)c cıa bŒ (cid:31)• n(cid:160)y r§t rª. N(cid:226) n(cid:226)i r‹ng n(cid:226)n l(cid:231)i, (cid:31)(cid:226)ng
{x|Ax ≥ 0} n‹m trong nßa kh(cid:230)ng gian {x|aT x ≥ 0} khi v(cid:160) ch¿ khi
H…nh 1.5: BŒ (cid:31)• Farkas
v†c-t(cid:236) ph¡p tuy‚n a (cid:240) trong n(cid:226)n sinh b(cid:240)i c¡c h(cid:160)ng cıa ma tr“n A.
Chøng minh bŒ (cid:31)• Farkas. Gi£ sß (1.6) c(cid:226) mºt nghi»m y n(cid:160)o (cid:31)(cid:226). N‚u
nh(cid:247) Ax ≥ 0, th… tł AT y = a, nh¥n t‰ch v(cid:230) h(cid:247)(cid:238)ng v(cid:238)i x, v(cid:160) do Ax ≥
0, y ≥ 0, ta c(cid:226) aT x = yT Ax ≥ 0. V“y (1.5) kh(cid:230)ng th” c(cid:226) nghi»m.
B¥y gi(cid:237) ta gi£ sß h» (1.6) kh(cid:230)ng c(cid:226) nghi»m. L§y t“p C = {x|∃y ≥ 0 :
AT y = x}. Hi”n nhi¶n C l(cid:160) t“p l(cid:231)i (cid:31)(cid:226)ng v(cid:160) 0 ∈ C.
Do (1.6) kh(cid:230)ng c(cid:226) nghi»m, n¶n a /∈ C. Theo (cid:31)(cid:224)nh l(cid:254) t¡ch m⁄nh, t(cid:231)n t⁄i p (cid:54)= 0 v(cid:160) mºt sŁ α ∈ R sao cho pT a < α < pT x v(cid:238)i m(cid:229)i x ∈ C. Do 0 ∈ C,
n¶n α < 0. Thay x = AT y, v(cid:238)i y ≥ 0, ta vi‚t (cid:31)(cid:247)æc α ≤ pT AT y = yT Ap.
15
Ch(cid:243) (cid:254) r‹ng n‚u x ∈ C, th… ξx ∈ C v(cid:238)i m(cid:229)i ξ ≥ 0, v… tł x = AT y, c(cid:226)
ξx = AT ξy. V“y c¡c to⁄ (cid:31)º cıa y c(cid:226) th” l(cid:238)n tu(cid:253) (cid:254), n¶n tł b§t (cid:31)flng thøc
α ≤ pT AT y = yT Ap, suy ra Ap ≥ 0. V“y ta (cid:31)¢ ch¿ ra s(cid:252) t(cid:231)n t⁄i cıa mºt
v†c-t(cid:236) p sao cho Ap ≥ 0 v(cid:160) aT p < 0. Chøng t(cid:228) h» (1.5) c(cid:226) nghi»m.
1.2 To¡n tß chi‚u kho£ng c¡ch
B(cid:160)i to¡n t…m h…nh chi‚u l¶n mºt t“p l(cid:231)i c(cid:226) vai trÆ quan tr(cid:229)ng v(cid:160) c(cid:226) r§t
nhi•u øng d(cid:246)ng trong tŁi (cid:247)u, c¥n b‹ng v(cid:160) b§t (cid:31)flng thøc bi‚n ph¥n,...
C(cid:246) th”, ta s‡ chøng minh s(cid:252) t(cid:231)n t⁄i v(cid:160) t‰nh duy nh§t cıa h…nh chi‚u l¶n
mºt t“p l(cid:231)i (cid:31)(cid:226)ng v(cid:160) kh£o s¡t mºt sŁ t‰nh ch§t c(cid:236) b£n cıa to¡n tß chi‚u.
(cid:30)(cid:224)nh ngh(cid:190)a 1.12. Cho C (cid:54)= ∅ (kh(cid:230)ng nh§t thi‚t l(cid:231)i) v(cid:160) y l(cid:160) mºt v†c-t(cid:236)
b§t k(cid:253), (cid:31)(cid:176)t
(cid:107)x − y(cid:107). dC(y) := inf x∈C
Ta n(cid:226)i dC(y) l(cid:160) kho£ng c¡ch tł y (cid:31)‚n C. N‚u t(cid:231)n t⁄i π ∈ C sao cho
dC(y) = (cid:107)π − y(cid:107),
th… ta n(cid:226)i π l(cid:160) h…nh chi‚u cıa y tr¶n C. (Xem h…nh 1.6).
Ch(cid:243) (cid:254) 1.2. Theo (cid:31)(cid:224)nh ngh(cid:190)a 1.12, ta th§y h…nh chi‚u pC(y) cıa y tr¶n
C s‡ l(cid:160) nghi»m cıa b(cid:160)i to¡n tŁi (cid:247)u
(cid:107)x − y(cid:107)2 : x ∈ C}. { min x 1 2
Do (cid:31)(cid:226), vi»c t…m h…nh chi‚u cıa y tr¶n C c(cid:226) th” (cid:31)(cid:247)a v• vi»c t…m c(cid:252)c ti”u
cıa h(cid:160)m to(cid:160)n ph(cid:247)(cid:236)ng (cid:107)x − y(cid:107)2 tr¶n C.
Ta k(cid:254) hi»u π = PC(y), ho(cid:176)c (cid:31)(cid:236)n gi£n h(cid:236)n l(cid:160) P (y) n‚u kh(cid:230)ng cƒn nh§n
m⁄nh (cid:31)‚n t“p chi‚u C.
16
(a) T“p C l(cid:231)i
(b) T“p C kh(cid:230)ng l(cid:231)i
H…nh 1.6: H…nh chi‚u vu(cid:230)ng g(cid:226)c
(cid:30)(cid:224)nh ngh(cid:190)a 1.13. Cho C l(cid:160) t“p l(cid:231)i (cid:31)(cid:226)ng kh¡c rØng trong kh(cid:230)ng gian Rn, ¡nh x⁄ PC : Rn → C x¡c (cid:31)(cid:224)nh b(cid:240)i nghi»m cıa b(cid:160)i to¡n:
(cid:107)x − y(cid:107) (cid:107)x − PC(x)(cid:107) = min y∈C
(cid:31)(cid:247)æc g(cid:229)i l(cid:160) to¡n tß chi‚u tr¶n C.
(cid:30)(cid:224)nh ngh(cid:190)a 1.14. Cho C ⊆ Rn, x0 ∈ C. N(cid:226)n ph¡p tuy‚n (ngo(cid:160)i) cıa
t“p C t⁄i x0 l(cid:160) t“p hæp
NC(x0) := {w : wT (x − x0) ≤ 0 ∀x ∈ C}.
M»nh (cid:31)• 1.6. Cho C l(cid:160) mºt t“p l(cid:231)i (cid:31)(cid:226)ng kh¡c rØng. Khi (cid:31)(cid:226):
(i) V(cid:238)i m(cid:229)i y ∈ Rn, π ∈ C hai t‰nh ch§t sau l(cid:160) t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng:
a) π = pC(y),
b) y − π ∈ NC(π).
(ii) V(cid:238)i m(cid:229)i y ∈ Rn, h…nh chi‚u pC(y) cıa y tr¶n C lu(cid:230)n t(cid:231)n t⁄i v(cid:160) duy
nh§t.
(iii) N‚u y /∈ C, th… (cid:104)pC(y) − y, x − pC(y)(cid:105) = 0 l(cid:160) si¶u phflng t(cid:252)a cıa C
17
t⁄i pC(y) v(cid:160) t¡ch hfln y kh(cid:228)i C (h…nh 1.7), tøc l(cid:160)
(cid:104)pC(y) − y, x − pC(y)(cid:105) ≥ 0, ∀x ∈ C,
v(cid:160)
H…nh 1.7:
(cid:104)pC(y) − y, y − pC(y)(cid:105) < 0.
(iv) (cid:129)nh x⁄ y (cid:44)→ pC(y) c(cid:226) c¡c t‰nh ch§t sau:
a) T‰nh kh(cid:230)ng gi¢n: (cid:107)pC(x) − pC(y)(cid:107) ≤ (cid:107)x − y(cid:107) ∀x, ∀y.
b) T‰nh (cid:31)(cid:231)ng bøc: (cid:104)pC(x) − pC(y), x − y(cid:105) ≥ (cid:107)pC(x) − pC(y)(cid:107)2.
Chøng minh. (i) Gi£ sß c(cid:226) π = pC(y). L§y x ∈ C v(cid:160) λ ∈ (0, 1). (cid:30)(cid:176)t
xλ := λx + (1 − λ)π.
V… x, π ∈ C v(cid:160) C l(cid:231)i, n¶n xλ ∈ C. M(cid:176)t kh¡c v… π l(cid:160) h…nh chi‚u cıa y,
n¶n (cid:107)π − y(cid:107) ≤ (cid:107)y − xλ(cid:107). Khi (cid:31)(cid:226)
(cid:107)π − y(cid:107)2 ≤ (cid:107)λ(x − π) + (π − y)(cid:107)2
⇔(cid:107)π − y(cid:107)2 ≤ λ2(cid:107)x − π(cid:107)2 + 2λ(cid:104)x − π, π − y(cid:105) + (cid:107)π − y(cid:107)2
⇔λ(cid:107)x − π(cid:107)2 + 2(cid:104)x − π, π − y(cid:105) ≥ 0.
18
(cid:30)i•u n(cid:160)y (cid:31)(cid:243)ng v(cid:238)i m(cid:229)i x ∈ C v(cid:160) λ ∈ (0, 1). Do (cid:31)(cid:226) khi cho λ ti‚n (cid:31)‚n 0,
ta (cid:31)(cid:247)æc
(cid:104)π − y, x − π(cid:105) ≥ 0 ∀x ∈ C.
V“y y − π ∈ NC(π).
Ng(cid:247)æc l⁄i, gi£ sß c(cid:226) y − π ∈ NC(π). V(cid:238)i m(cid:229)i x ∈ C, ta c(cid:226)
0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π)
= (cid:107)y − π(cid:107)2 + (y − π)T (x − y).
Khi (cid:31)(cid:226), theo gi£ sß v(cid:160) b§t (cid:31)flng thøc Cauchy-Schwarz ta c(cid:226)
(cid:107)y − π(cid:107)2 ≤ (y − π)T (y − x) ≤ (cid:107)y − π(cid:107)(cid:107)y − x(cid:107).
Suy ra (cid:107)y − π(cid:107) ≤ (cid:107)y − x(cid:107), ∀x ∈ C v(cid:160) do (cid:31)(cid:226) π = p(y).
(ii) V… dC(y) = inf x∈c (cid:107)x − y(cid:107), n¶n theo (cid:31)(cid:224)nh ngh(cid:190)a cıa c“n d(cid:247)(cid:238)i (cid:31)(cid:243)ng,
t(cid:231)n t⁄i mºt d¢y {xk} ∈ C sao cho
(cid:107)xk − y(cid:107) = dC(y) < +∞. lim k
V“y d¢y xk b(cid:224) ch(cid:176)n, do (cid:31)(cid:226) n(cid:226) c(cid:226) mºt d¢y con {xkj} hºi t(cid:246) (cid:31)‚n mºt (cid:31)i”m
π n(cid:160)o (cid:31)(cid:226). V… C (cid:31)(cid:226)ng, n¶n π ∈ C. V“y
j
(cid:107)π − y(cid:107) = lim (cid:107)xk − y(cid:107) = dC(y). (cid:107)xkj − y(cid:107) = lim k
V“y π l(cid:160) h…nh chi‚u cıa y tr¶n C.
Ta (cid:31)i chøng minh t‰nh duy nh§t cıa h…nh chi‚u. Th“t v“y, n‚u t(cid:231)n t⁄i
hai (cid:31)i”m π v(cid:160) π1 (cid:31)•u l(cid:160) h…nh chi‚u cıa y tr¶n C, th…
y − π ∈ NC(π), y − π1 ∈ NC(π).
Tøc l(cid:160)
(cid:104)π − y, π1 − π(cid:105) ≥ 0 (1.7)
19
v(cid:160)
(cid:104)π1 − y, π − π1(cid:105) ≥ 0. (1.8)
Cºng (1.7) v(cid:160) (1.8), ta suy ra (cid:107)π − π1(cid:107) ≤ 0, v(cid:160) do (cid:31)(cid:226) π = π1.
(iii) V… y − π ∈ NC(π) n¶n (cid:104)π − y, x − π(cid:105) ≥ 0 ∀x ∈ C. V“y (cid:104)π − y, x(cid:105) =
(cid:104)π − y, π(cid:105) l(cid:160) mºt si¶u phflng t(cid:252)a cıa C t⁄i π. Si¶u phflng n(cid:160)y t¡ch y kh(cid:228)i
C v… y (cid:54)= π n¶n
(cid:104)π − y, y − π(cid:105) = −(cid:107)π − y(cid:107)2 < 0.
(iv) Theo (ii) ¡nh x⁄ x (cid:44)→ p(x) x¡c (cid:31)(cid:224)nh kh›p n(cid:236)i. V… z − p(z) ∈
NC(p(z)) v(cid:238)i m(cid:229)i z n¶n ¡p d(cid:246)ng v(cid:238)i z = x v(cid:160) z = y, ta c(cid:226)
(cid:104)x − p(x), p(y) − p(x)(cid:105) ≤ 0 (1.9)
v(cid:160)
(cid:104)y − p(y), p(x) − p(y)(cid:105) ≤ 0. (1.10)
Cºng (1.9) v(cid:160) (1.10) ta (cid:31)(cid:247)æc
(cid:104)p(y) − p(x), p(y) − p(x) + x − y(cid:105) ≤ 0.
Do (cid:31)(cid:226), theo b§t (cid:31)flng thøc Cauchy-Schwarz, suy ra
(cid:107)p(x) − p(y)(cid:107) ≤ (cid:107)x − y(cid:107).
(cid:30)” chøng minh t‰nh (cid:31)(cid:231)ng bøc, ¡p d(cid:246)ng t‰nh ch§t b) cıa (i) lƒn l(cid:247)æt v(cid:238)i
p(x) v(cid:160) p(y), ta c(cid:226):
(cid:104)p(x) − x, p(x) − p(y)(cid:105) ≤ 0. (1.11)
(cid:104)y − p(y), p(x) − p(y)(cid:105) ≤ 0. (1.12)
20
Cºng (1.11) v(cid:160) (1.12), ta (cid:31)(cid:247)æc
(cid:104)p(x) − p(y) + y − x, p(x) − p(y)(cid:105)
=(cid:104)p(x) − p(y), y − x(cid:105) + (cid:107)p(x) − p(y)(cid:107)2 ≤ 0
⇔(cid:104)p(x) − p(y), y − x(cid:105) ≥ (cid:107)p(x) − p(y)(cid:107)2.
Ta c(cid:226) (cid:31)i•u ph£i chøng minh.
Ch(cid:243) (cid:254) 1.3. To¡n tß chi‚u metric cÆn c(cid:226) mºt t‰nh ch§t m⁄nh h(cid:236)n t‰nh
kh(cid:230)ng gi¢n n¶u (cid:240) tr¶n. C(cid:246) th”, ta c(cid:226)
(cid:107)p(x) − p(y)(cid:107)2 ≤ (cid:107)x − y(cid:107)2 − (cid:107)p(x) − p(y) − x + y(cid:107)2 ∀x, y.
Trong nhi•u øng d(cid:246)ng th(cid:247)(cid:237)ng g(cid:176)p, t“p chi‚u c(cid:226) nhœng t‰nh ch§t (cid:31)(cid:176)c
bi»t: v‰ d(cid:246) n(cid:226) l(cid:160) nßa kh(cid:230)ng gian, h…nh cƒu (cid:31)(cid:226)ng hay si¶u hºp th… (cid:31)i”m
chi‚u c(cid:226) th” t‰nh (cid:31)(cid:247)æc mºt c¡ch t(cid:247)(cid:237)ng minh. Ta c(cid:226) c¡c tr(cid:247)(cid:237)ng hæp sau:
V‰ d(cid:246) 1.5. (Chi‚u l¶n nßa kh(cid:230)ng gian)
Cho C l(cid:160) mºt nßa kh(cid:230)ng gian (cid:31)(cid:247)æc (cid:31)(cid:224)nh ngh(cid:190)a b(cid:240)i
C = {x ∈ R : aT x ≤ α}
trong (cid:31)(cid:226) a (cid:54)= 0 l(cid:160) mºt v†c-t(cid:236) n‹m trong Rn v(cid:160) α l(cid:160) mºt sŁ th(cid:252)c.
Khi (cid:31)(cid:226), h…nh chi‚u cıa a v†c-t(cid:236) u ∈ Rn l¶n C (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh nh(cid:247) sau:
}a. PC(u) := u − max{0; (cid:104)a, u(cid:105) − α (cid:107)a(cid:107)2
V‰ d(cid:246) 1.6. (Chi‚u l¶n h…nh cƒu (cid:31)(cid:226)ng)
Cho C l(cid:160) h…nh cƒu t¥m a b¡n k‰nh r (cid:31)(cid:247)æc (cid:31)(cid:224)nh ngh(cid:190)a b(cid:240)i
C := {x : (cid:107)x − a(cid:107) ≤ r}.
Khi (cid:31)(cid:226), h…nh chi‚u cıa u l¶n C (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh nh(cid:247) sau:
21
• N‚u u ∈ C th… PC(u) = u.
• N‚u u /∈ C th… h…nh chi‚u cıa u l¶n C l(cid:160) giao (cid:31)i”m cıa nßa (cid:31)(cid:247)(cid:237)ng
thflng ((cid:31)(cid:247)(cid:237)ng thflng (cid:52)) nŁi u v(cid:160) t¥m a cıa C v(cid:238)i h…nh cƒu C.
Ta c(cid:226)
(cid:52) = {x : x = a + t(u − a), t ≥ 0}.
Thay x = a + (u − a)t, ta (cid:31)(cid:247)æc
t(cid:107)u − a(cid:107) = r.
Do (cid:31)(cid:226)
t = . r (cid:107)u − a(cid:107)
V‰ d(cid:246) 1.7. (Chi‚u l¶n si¶u hºp)
Cho C l(cid:160) mºt si¶u hºp (cid:31)(cid:247)æc (cid:31)(cid:224)nh ngh(cid:190)a b(cid:240)i
C := {x ∈ Rn : a ≤ x ≤ b}
v(cid:160) cho u ∈ Rn.
Khi (cid:31)(cid:226), v = PC(u) h…nh chi‚u cıa u l¶n C (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh nh(cid:247) sau: V(cid:238)i
a = (aj), b = (bj), x = (xj), j = 1, 2, ..., n, ta c(cid:226)
n‚u uj ≤ aj aj
vj = n‚u uj ≥ bj bj
uj n‚u aj ≤ uj ≤ bj
trong (cid:31)(cid:226) xj ∈ [aj; bj], ∀j = 1, n.
22
Ch(cid:247)(cid:236)ng 2. (cid:217)ng d(cid:246)ng v(cid:160)o b(cid:160)i to¡n
b§t (cid:31)flng thøc bi‚n ph¥n
Cho C l(cid:160) mºt t“p con kh¡c rØng l(cid:231)i (cid:31)(cid:226)ng cıa Rn v(cid:160) cho F : Rn → Rn.
Ta x†t b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n sau:
T…m x∗ ∈ C sao cho (cid:104)F (x∗), y − x∗(cid:105) ≥ 0, ∀y ∈ C.
Gƒn (cid:31)¥y, nhi•u ph(cid:247)(cid:236)ng ph¡p (cid:31)¢ (cid:31)(cid:247)æc ph¡t tri”n (cid:31)” gi£i quy‚t b(cid:160)i to¡n
n(cid:160)y, trong (cid:31)(cid:226) ph(cid:247)(cid:236)ng ph¡p chi‚u l(cid:160) mºt ph(cid:247)(cid:236)ng ph¡p c(cid:236) b£n.
Trong ch(cid:247)(cid:236)ng n(cid:160)y, ch(cid:243)ng ta s‡ gi(cid:238)i thi»u mºt thu“t to¡n chi‚u d(cid:247)(cid:238)i
(cid:31)⁄o h(cid:160)m cho mºt l(cid:238)p b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n v(cid:160) kh£o s¡t t‰nh
hºi t(cid:246) cıa thu“t to¡n n(cid:160)y. Thu“t to¡n n(cid:160)y l(cid:160) mºt tr(cid:247)(cid:237)ng hæp ri¶ng cıa
thu“t to¡n trong [4] (cid:31)” gi£i b(cid:160)i to¡n c¥n b‹ng.
2.1 B(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n
Trong phƒn n(cid:160)y ta lu(cid:230)n gi£ thi‚t Rn l(cid:160) kh(cid:230)ng gian Euclid n-chi•u v(cid:238)i
t‰ch v(cid:230) h(cid:247)(cid:238)ng v(cid:160) chu'n lƒn l(cid:247)æt (cid:31)(cid:247)æc k(cid:254) hi»u b(cid:240)i (cid:104)·, ·(cid:105) v(cid:160) (cid:107) · (cid:107).
Ta ph¡t bi”u l⁄i b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n.
(cid:30)(cid:224)nh ngh(cid:190)a 2.1. Cho C l(cid:160) mºt t“p con l(cid:231)i, (cid:31)(cid:226)ng, kh¡c rØng trong Rn, F l(cid:160) ¡nh x⁄ (cid:31)i tł Rn v(cid:160)o Rn. Khi (cid:31)(cid:226) b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n
23
k‰ hi»u l(cid:160) V IP (F ; C) (cid:31)(cid:247)æc ph¡t bi”u nh(cid:247) sau:
T…m x∗ ∈ C sao cho (cid:104)F (x∗), y − x∗(cid:105) ≥ 0, ∀y ∈ C. (2.1)
T“p hæp t§t c£ c¡c nghi»m cıa b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n (2.1)
(cid:31)(cid:247)æc k(cid:254) hi»u l(cid:160) S(F ; C).
V‰ d(cid:246) 2.1. Trong R, x†t t“p C = [2; 6] ⊂ R v(cid:160) ¡nh x⁄ F : [2; 6] → R
(cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh b(cid:240)i
F (x) = x − 2, x ∈ [2; 6].
Khi (cid:31)(cid:226) b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n V IP (F ; C) l(cid:160) t…m x∗ ∈ [2; 6]
sao cho
(cid:104)x∗ − 2, y − x∗(cid:105) ≥ 0, ∀y ∈ [2; 6]. (2.2)
Ta chøng minh r‹ng: S(F ; C) = {2}.
Th“t v“y, hi”n nhi¶n x∗ = 2 l(cid:160) mºt nghi»m. N‚u x∗ ∈ (1; 2) th… (2.2) ch¿
th(cid:228)a m¢n v(cid:238)i y ≤ x∗. Ng(cid:247)æc l⁄i, n‚u x∗ > 2 th… (2.2) ch¿ th(cid:228)a m¢n v(cid:238)i
y ≥ x∗. (cid:30)i•u n(cid:160)y chøng t(cid:228) r‹ng x∗ = 2 l(cid:160) nghi»m duy nh§t.
B(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n c(cid:226) c¡c tr(cid:247)(cid:237)ng hæp ri¶ng quan tr(cid:229)ng
l(cid:160) b(cid:160)i to¡n c(cid:252)c ti”u h(cid:160)m l(cid:231)i tr¶n t“p l(cid:231)i v(cid:160) b(cid:160)i to¡n b(cid:242) phi tuy‚n.
M»nh (cid:31)• 2.1. Cho C l(cid:160) mºt t“p l(cid:231)i, (cid:31)(cid:226)ng, kh¡c rØng trong Rn v(cid:160) f : C → R l(cid:160) mºt h(cid:160)m l(cid:231)i, kh£ vi. F l(cid:160) mºt ¡nh x⁄ (cid:31)i tł t“p C v(cid:160)o Rn
v(cid:160) F (x) = (cid:53)f (x). Khi (cid:31)(cid:226) b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n V IP (F ; C)
t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng v(cid:238)i b(cid:160)i to¡n c(cid:252)c tr(cid:224):
(OP) T…m x∗ ∈ C th(cid:228)a m¢n f (x∗) ≤ f (y) ∀y ∈ C.
Chøng minh. Gi£ sß x∗ l(cid:160) nghi»m cıa b(cid:160)i to¡n V IP (F ; C), tøc l(cid:160)
(cid:104)F (x∗), y − x∗(cid:105) ≥ 0 ∀y ∈ C.
24
Theo BŒ (cid:31)• 1.1, h(cid:160)m f l(cid:160) l(cid:231)i n¶n ta c(cid:226)
f (y) − f (x∗) ≥ (cid:104)(cid:53)f (x∗), y − x∗(cid:105), ∀y ∈ C.
M(cid:160) F (x) = (cid:53)f (x) n¶n f (x∗) ≤ f (y) ∀y ∈ C, (cid:31)i•u n(cid:160)y c(cid:226) ngh(cid:190)a l(cid:160) x∗ l(cid:160)
nghi»m cıa b(cid:160)i to¡n (OP).
Ng(cid:247)æc l⁄i, gi£ sß x∗ l(cid:160) nghi»m cıa b(cid:160)i to¡n (OP), theo (cid:31)i•u ki»n tŁi
(cid:247)u cıa h(cid:160)m l(cid:231)i ta c(cid:226)
0 ∈ (cid:53)f (x∗) + NC(x∗).
Tł (cid:31)(cid:226), ta suy ra − (cid:53) f (x∗) ∈ NC(x∗) hay −F (x∗) ∈ NC(x∗). Tøc l(cid:160)
(cid:104)−F (x∗), y − x∗(cid:105) ≤ 0, ∀y ∈ C ⇔ (cid:104)F (x∗), y − x∗(cid:105) ≥ 0, ∀y ∈ C.
V“y x∗ l(cid:160) mºt nghi»m cıa b(cid:160)i to¡n V IP (F ; C).
Khi C l(cid:160) mºt n(cid:226)n l(cid:231)i trong kh(cid:230)ng gian Rn th… b(cid:160)i to¡n V IP (F ; C)
tr(cid:240) th(cid:160)nh b(cid:160)i to¡n b(cid:242):
(CP) T…m x∗ ∈ C, F (x∗) ∈ C (cid:48) sao cho (cid:104)F (x∗), x∗(cid:105) = 0
trong (cid:31)(cid:226) C (cid:48) := {y ∈ C : (cid:104)x, y(cid:105) ≥ 0, ∀x ∈ C} l(cid:160) n(cid:226)n (cid:31)Łi ng¤u cıa C.
Ta c(cid:226) m»nh (cid:31)• sau:
M»nh (cid:31)• 2.2. N‚u C l(cid:160) mºt n(cid:226)n l(cid:231)i, compact trong kh(cid:230)ng gian Rn
th… b(cid:160)i to¡n b(cid:242) (CP) t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng v(cid:238)i b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n
V IP (F ; C), ngh(cid:190)a l(cid:160) t“p nghi»m hai b(cid:160)i to¡n n(cid:160)y tr(cid:242)ng nhau.
Chøng minh. Gi£ sß x∗ l(cid:160) nghi»m cıa b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n
V IP (F ; C), tøc l(cid:160)
(cid:104)F (x∗), y − x∗(cid:105) > 0. (2.3)
25
V… C l(cid:160) n(cid:226)n l(cid:231)i, x∗ ∈ C n¶n y + x∗ ∈ C, ∀y ∈ C. Thay y = y + x∗ v(cid:160)o
b§t (cid:31)flng thøc (2.3) ta (cid:31)(cid:247)æc
(cid:104)F (x∗), y + x∗ − x∗(cid:105) ≥ 0, ∀y ∈ C ⇔ (cid:104)F (x∗), y(cid:105) ≥ 0, ∀y ∈ C.
Suy ra F (x∗) thuºc n(cid:226)n (cid:31)Łi ng¤u C (cid:48).
Thay y = x∗ v(cid:160)o b§t (cid:31)flng thøc (2.3) ta (cid:31)(cid:247)æc 1 2
(cid:104)F (x∗), x∗(cid:105) ≤ 0, ∀y ∈ C.
Suy ra (cid:104)F (x∗), x∗(cid:105) = 0 hay x∗ ∈ C, F (x∗) ∈ C (cid:48) l(cid:160) nghi»m cıa b(cid:160)i to¡n
b(cid:242) phi tuy‚n (CP).
Ng(cid:247)æc l⁄i, n‚u x∗ ∈ C l(cid:160) nghi»m cıa b(cid:160)i to¡n b(cid:242) (CP) th…
(cid:104)F (x∗), x∗(cid:105) = 0, F (x∗) ∈ C (cid:48).
V… F (x∗) ∈ C (cid:48) n¶n (cid:104)F (x∗), y(cid:105) ≥ 0, ∀y ∈ C. Ta c(cid:226)
(cid:104)F (x∗), y − x∗(cid:105) ≥ 0, ∀y ∈ C
hay x∗ ∈ C l(cid:160) nghi»m cıa b(cid:160)i to¡n V IP (F ; C).
2.2 Mºt thu“t to¡n chi‚u gi£i b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n
ph¥n para-(cid:31)(cid:236)n (cid:31)i»u
(cid:30)(cid:224)nh ngh(cid:190)a 2.2. Cho C l(cid:160) mºt t“p con l(cid:231)i trong kh(cid:230)ng gian Rn v(cid:160) F : C → Rn. Khi (cid:31)(cid:226), ¡nh x⁄ F l(cid:160)
(i) (cid:30)(cid:236)n (cid:31)i»u m⁄nh tr¶n C n‚u t(cid:231)n t⁄i mºt h‹ng sŁ γ > 0 sao cho
(cid:104)F (x) − F (y), x − y(cid:105) ≥ γ(cid:107)x − y(cid:107)2, ∀x, y ∈ C;
(ii) (cid:30)(cid:236)n (cid:31)i»u tr¶n C n‚u
(cid:104)F (x) − F (y), x − y(cid:105) ≥ 0, ∀x, y ∈ C;
26
(iii) Gi£ (cid:31)(cid:236)n (cid:31)i»u tr¶n C n‚u
(cid:104)F (x), y − x(cid:105) ≥ 0 ⇒ (cid:104)F (y), y − x(cid:105) ≥ 0, ∀x, y ∈ C.
(iv) Para-(cid:31)(cid:236)n (cid:31)i»u tr¶n C n‚u
x∗ ∈ S(F, C), x ∈ C, (cid:104)F (x), x∗−x(cid:105) = 0, (cid:104)F (x∗), x−x∗(cid:105) = 0 ⇒ x ∈ S(F, C).
Nh“n x†t 2.1. Ta c(cid:226) (i) ⇒ (ii), (ii) ⇒ (iii) l(cid:160) hi”n nhi¶n.
V‰ d(cid:246) 2.2.
a) Cho ¡nh x⁄ F (cid:31)(cid:236)n tr(cid:224) x¡c (cid:31)(cid:224)nh tr¶n R nh(cid:247) sau:
F (x) = 2x, ∀x ∈ R
v(cid:238)i F (x) l(cid:160) (cid:31)⁄o h(cid:160)m c§p 1 cıa h(cid:160)m l(cid:231)i x2 x¡c (cid:31)(cid:224)nh tr¶n R. Khi (cid:31)(cid:226) d„ th§y r‹ng F l(cid:160) (cid:31)(cid:236)n (cid:31)i»u tr¶n R. b) Cho F (x) = Qx, trong (cid:31)(cid:226) Q l(cid:160) ma
tr“n vu(cid:230)ng c(cid:239) n × n. Theo (cid:31)(cid:224)nh ngh(cid:190)a, ta th§y F l(cid:160) (cid:31)(cid:236)n (cid:31)i»u tr¶n to(cid:160)n
kh(cid:230)ng gian khi Q l(cid:160) ma tr“n vu(cid:230)ng, (cid:31)Łi xøng, nßa x¡c (cid:31)(cid:224)nh d(cid:247)(cid:236)ng. N‚u
Q l(cid:160) (cid:31)Łi xøng, x¡c (cid:31)(cid:224)nh d(cid:247)(cid:236)ng, th… F (cid:31)(cid:236)n (cid:31)i»u m⁄nh. TŒng qu¡t h(cid:236)n
n‚u f l(cid:160) mºt h(cid:160)m l(cid:231)i tr¶n C th… (cid:53)f l(cid:160) (cid:31)(cid:236)n (cid:31)i»u tr¶n C.
Ch(cid:243) (cid:254) kh(cid:230)ng ph£i m(cid:229)i to¡n tß (cid:31)(cid:236)n (cid:31)i»u (cid:31)•u l(cid:160) (cid:31)⁄o h(cid:160)m cıa h(cid:160)m l(cid:231)i.
Ta c(cid:226) c¡c bŒ (cid:31)• sau s‡ cƒn (cid:31)” s(cid:252) chøng minh s(cid:252) hºi t(cid:246) cıa thu“t to¡n.
k=1 δk < +∞. Khi (cid:31)(cid:226) d¢y {νk} hºi t(cid:246).
BŒ (cid:31)• 2.1. [4] Gi£ sß {νk} v(cid:160) {δk} l(cid:160) hai d¢y sŁ th(cid:252)c kh(cid:230)ng ¥m th(cid:228)a m¢n νk+1 ≤ νk + δk v(cid:238)i (cid:80)+∞
BŒ (cid:31)• 2.2. [4] Gi£ sß θ, β v(cid:160) ξ l(cid:160) c¡c sŁ th(cid:252)c kh(cid:230)ng ¥m th(cid:228)a m¢n
θ2 − βθ − ξ ≤ 0, khi (cid:31)(cid:226)
βθ ≤ β2 + ξ. (2.4)
27
Chøng minh. X†t h(cid:160)m sŁ b“c hai s(θ) = θ2 − βθ − ξ, khi (cid:31)(cid:226) s(θ) ≤ 0
suy ra
θ ≤ , β + (cid:112)β2 + 4ξ 2
v… θ > 0.
Nh¥n b§t (cid:31)flng thøc tr¶n v(cid:238)i β v(cid:160) ¡p d(cid:246)ng t‰nh ch§t
ab ≤ a2 + b2 2
ta (cid:31)(cid:247)æc
(cid:105) (cid:112) β2 + 4ξ
(cid:21) βθ ≤ 2−1 (cid:104) β2 + β (cid:20) ≤ 2−1 β2 +
β2 + β2 + 4ξ 2 = 2−1 (cid:2)β2 + β2 + 2ξ(cid:3)
= β2 + ξ.
Suy ra (cid:31)i•u ph£i chøng minh.
(cid:30)” chøng minh s(cid:252) hºi t(cid:246) ta s‡ gi£ sß t“p nghi»m cıa (2.1) (cid:31)(cid:247)æc chøa
trong t“p nghi»m cıa b(cid:160)i to¡n sau
T…m x∗ ∈ C sao cho (cid:104)F (y), x∗ − y(cid:105) ≤ 0, ∀y ∈ C. (2.5)
T“p nghi»m cıa b(cid:160)i to¡n n(cid:160)y (cid:31)(cid:247)æc k(cid:254) hi»u b(cid:240)i Sd(F ; C).
Thu“t to¡n (cid:31)(cid:247)æc ph¡t bi”u nh(cid:247) sau.
Cho tham sŁ d(cid:247)(cid:236)ng ρ v(cid:160) c¡c d¢y sŁ th(cid:252)c {ρk} v(cid:160) {βk} th(cid:228)a m¢n c¡c
(cid:31)i•u ki»n sau:
(2.6) ρk > ρ, βk > 0, ∀k ∈ N,
(cid:88) = +∞, (2.7) β2 k < +∞, (cid:88) βk ρk
28
v(cid:238)i m > 0. V‰ d(cid:246) ta l§y ρk = 1 v(cid:238)i m(cid:229)i k, βk = m k + 1
Ph(cid:247)(cid:236)ng ph¡p chi‚u.
B(cid:247)(cid:238)c 0: Ch(cid:229)n x0 ∈ C. (cid:30)(cid:176)t k = 0.
B(cid:247)(cid:238)c 1: Gi£ sß xk ∈ C. L§y gk = F (xk). Ta (cid:31)(cid:224)nh ngh(cid:190)a
(2.8) αk = trong (cid:31)(cid:226) γk = max{ρk, (cid:107)gk(cid:107)}. βk γk
B(cid:247)(cid:238)c 2: T‰nh xk+1 ∈ C sao cho
(2.9) (cid:104)αkgk + xk+1 − xk, x − xk+1(cid:105) ≥ 0, ∀x ∈ C,
ngh(cid:190)a l(cid:160) xk+1 = PC(xk − αkgk).
(cid:30)i•u ki»n dłng: Thu“t to¡n s‡ dłng t⁄i b(cid:247)(cid:238)c l(cid:176)p k, n‚u gk = 0 hay
xk+1 = xk.
H…nh 2.8: S(cid:236) (cid:31)(cid:231) thu“t to¡n
Ta c(cid:226) s(cid:236) (cid:31)(cid:231) thu“t to¡n sau:
29
M»nh (cid:31)• 2.3. N‚u thu“t to¡n chi‚u d(cid:247)(cid:238)i (cid:31)⁄o h(cid:160)m sinh ra mºt d¢y hœu
h⁄n th… (cid:31)i”m cuŁi c(cid:242)ng l(cid:160) mºt nghi»m cıa b(cid:160)i to¡n V IP (F ; C).
Chøng minh. N‚u gk = 0 th… (cid:104)F (xk), y − xk(cid:105) = 0 v(cid:238)i m(cid:229)i y, v“y xk l(cid:160)
nghi»m cıa b(cid:160)i to¡n V IP (F ; C).
B¥y gi(cid:237) gi£ sß thu“t to¡n k‚t th(cid:243)c t⁄i b(cid:247)(cid:238)c 2, ngh(cid:190)a l(cid:160) xk = xk+1. N‚u
xk = xk+1 th… tł xk+1 = PC(xk − αkF (xk)), theo (cid:31)(cid:224)nh ngh(cid:190)a cıa ph†p
chi‚u, ta c(cid:226)
(cid:104)xk+1 − (xk − αkF (xk)), y − xk(cid:105) ≤ 0, ∀y ∈ C.
Do xk = xk+1 v(cid:160) αk > 0, b§t (cid:31)flng thøc cuŁi c(cid:242)ng tr(cid:240) th(cid:160)nh
(cid:104)F (xk)), y − xk(cid:105) ≥ 0 ∀y ∈ C,
ngh(cid:190)a l(cid:160) xk l(cid:160) mºt nghi»m.
Tł gi(cid:237) tr(cid:240) (cid:31)i, ch(cid:243)ng ta gi£ sß thu“t to¡n sinh ra mºt d¢y v(cid:230) h⁄n (cid:31)(cid:247)æc
k(cid:254) hi»u l(cid:160) {xk}.
Ta c(cid:226) t‰nh ch§t sau.
BŒ (cid:31)• 2.3. V(cid:238)i mØi k, c¡c b§t (cid:31)flng thøc sau (cid:31)(cid:243)ng
(i) αk(cid:107)gk(cid:107) ≤ βk;
(ii) βk(cid:107)xk+1 − xk(cid:107) ≤ β2 k.
Chøng minh. (i) Tł (2.8) ta c(cid:226)
(2.10) αk(cid:107)gk(cid:107) = ≤ βk. βk(cid:107)gk(cid:107) max{ρk, (cid:107)gk(cid:107)}
(ii) B‹ng c¡ch l§y x = xk trong (2.9) ta (cid:31)(cid:247)æc
(cid:107)xk+1 − xk(cid:107)2 ≤ (cid:104)αkgk, xk − xk+1(cid:105)
30
(2.11) ≤ αk(cid:107)gk(cid:107)(cid:107)xk+1 − xk(cid:107)
≤ βk(cid:107)xk+1 − xk(cid:107).
Do (cid:31)(cid:226), tł BŒ (cid:31)• 2.2 v(cid:238)i θ = (cid:107)xk+1 − xk(cid:107), β = βk v(cid:160) ξ = 0, v(cid:238)i mØi
k ∈ N ta suy ra (cid:31)i•u ph£i chøng minh.
Gi£ thi‚t ti‚p theo s‡ (cid:31)(cid:247)æc sß d(cid:246)ng trong chøng minh sau n(cid:160)y.
A1. T“p nghi»m S(F ; C) kh¡c rØng;
M»nh (cid:31)• 2.4. Gi£ sß A1 th(cid:228)a m¢n. Khi (cid:31)(cid:226), v(cid:238)i m(cid:229)i x∗ ∈ S(F ; C) v(cid:160)
v(cid:238)i mØi k, ta c(cid:226) c¡c khflng (cid:31)(cid:224)nh sau
(2.12) (cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 + 2αk(cid:104)F (xk), x∗ − xk(cid:105) + δk,
trong (cid:31)(cid:226) δk = 2β2 k.
Chøng minh. B‹ng ph†p bi‚n (cid:31)Œi (cid:31)(cid:236)n gi£n, ta c(cid:226)
(cid:107)xk+1 − x∗(cid:107)2 = (cid:107)xk − x∗(cid:107)2 − (cid:107)xk+1 − xk(cid:107)2 + 2(cid:104)xk − xk+1, x∗ − xk+1(cid:105)
≤ (cid:107)xk − x∗(cid:107)2 + 2(cid:104)xk − xk+1, x∗ − xk+1(cid:105). (2.13)
K‚t hæp (2.13) v(cid:160) (2.9) v(cid:238)i x = x∗ ta suy ra
(cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 + 2(cid:104)αkgk, x∗ − xk+1(cid:105)
(2.14) = (cid:107)xk − x∗(cid:107)2 + 2(cid:104)αkgk, x∗ − xk(cid:105)
+ 2(cid:104)αkgk, xk − xk+1(cid:105).
(cid:129)p d(cid:246)ng b§t (cid:31)flng thøc Cauchy - Schwarz v(cid:160) BŒ (cid:31)• 2.3 (i), suy ra
(2.15) (cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 + 2αk(cid:104)gk, x∗ − xk(cid:105) + 2βk(cid:107)xk − xk+1(cid:107).
Theo (2.15) v(cid:160) BŒ (cid:31)• 2.3 (ii), ta c(cid:226)
(2.16) (cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 + 2αk(cid:104)F (xk), x∗ − xk(cid:105) + 2β2 k.
31
Do (cid:31)(cid:226), v… αk > 0 n¶n ta suy ra (cid:31)i•u ph£i chøng minh.
(cid:30)i•u ki»n sau (cid:31)(cid:247)æc d(cid:242)ng (cid:31)” chøng minh t‰nh b(cid:224) ch(cid:176)n cıa d¢y {xk}
(cid:31)(cid:247)æc sinh b(cid:240)i thu“t to¡n.
A2. S(F ; C) ⊆ Sd(F ; C);
Ch(cid:243) (cid:254) r‹ng n‚u F li¶n t(cid:246)c v(cid:160) gi£ (cid:31)(cid:236)n (cid:31)i»u, th… gi£ thi‚t A2 (cid:31)(cid:243)ng.
(cid:30)(cid:224)nh l(cid:254) 2.1. Gi£ sß A1 v(cid:160) A2 (cid:31)•u th(cid:228)a m¢n. Khi (cid:31)(cid:226),
(i) {(cid:107)xk − x∗(cid:107)2} l(cid:160) d¢y hºi t(cid:246) v(cid:238)i m(cid:229)i x∗ ∈ S(F ; C);
(ii) {xk} l(cid:160) d¢y b(cid:224) ch(cid:176)n.
Chøng minh. (i) Gi£ sß x∗ ∈ S(F ; C) v(cid:160) k ∈ N. Theo A2 ta c(cid:226) (cid:104)F (xk), x∗−
xk(cid:105) ≤ 0 c(cid:242)ng v(cid:238)i M»nh (cid:31)• 2.4 suy ra
(2.17) (cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 + δk,
trong (cid:31)(cid:226) δk = 2β2 k.
+∞ (cid:88)
Do (cid:31)(cid:226), theo (2.7) v(cid:160) (2.8) ta c(cid:226)
k=0
(2.18) δk < +∞.
Do (cid:31)(cid:226), tł (2.17), (2.18) v(cid:160) BŒ (cid:31)• 2.3 suy ra {(cid:107)xk − x∗(cid:107)2} l(cid:160) mºt d¢y
hºi t(cid:246).
(ii) Suy ra tł (i).
(cid:30)(cid:224)nh l(cid:254) 2.2. Gi£ sß F li¶n t(cid:246)c v(cid:160) c¡c gi£ thi‚t A1, A2 (cid:31)•u th(cid:228)a m¢n.
Khi (cid:31)(cid:226), ta c(cid:226)
(cid:104)F (xk), x∗ − xk(cid:105) = 0 ∀x∗ ∈ S(F ; C). lim sup k→+∞
32
Chøng minh. Gi£ sß x∗ ∈ S(F ; C). Theo M»nh (cid:31)• 2.4 v(cid:160) A2 suy ra
(2.19) 0 ≤ 2αk[−(cid:104)F (xk), x∗ − xk(cid:105)] ≤ (cid:107)xk − x∗(cid:107)2 − (cid:107)xk+1 − x∗(cid:107)2 + δk.
m (cid:88)
Do (cid:31)(cid:226),
k=0
m (cid:88)
0 ≤ 2 αk[−(cid:104)F (xk), x∗ − xk(cid:105)]
k=0
m (cid:88)
≤ (cid:107)x0 − x∗(cid:107)2 − (cid:107)xm+1 − x∗(cid:107)2 + (2.20) δk
k=0
≤ (cid:107)x0 − x∗(cid:107)2 + δk.
+∞ (cid:88)
+∞ (cid:88)
Khi m → +∞ ta c(cid:226)
k=0
k=0
0 ≤ 2 (2.21) αk[−(cid:104)F (xk), x∗ − xk(cid:105)] ≤ (cid:107)x0 − x∗(cid:107)2 + δk,
+∞ (cid:88)
k‚t hæp v(cid:238)i (2.18) suy ra
k=0
0 ≤ (2.22) αk[−(cid:104)F (xk), x∗ − xk(cid:105)] < +∞.
M(cid:176)t kh¡c, ta c(cid:226) {(cid:107)gk(cid:107)} l(cid:160) d¢y b(cid:224) ch(cid:176)n. Khi (cid:31)(cid:226),
k (cid:107)gk(cid:107)} ≤
= max{1, ρ−1 ∀k ∈ N. L ρ γk ρk
Do (cid:31)(cid:226)
≥ ∀k ∈ N. (2.23) αk = ρ L βk γk βk ρk
+∞ (cid:88)
Tł (2.22) v(cid:160) (2.23), ta c(cid:226)
k=0
[−(cid:104)F (xk), x∗ − xk(cid:105)] < +∞. (2.24) βk ρk
V“y, tł (2.24) v(cid:160) (2.7) suy ra (cid:31)i•u ph£i chøng minh.
33
(cid:30)” c(cid:226) (cid:31)(cid:247)æc s(cid:252) hºi t(cid:246) cıa c£ d¢y ch(cid:243)ng ta (cid:31)(cid:247)a ra gi£ thi‚t sau.
A3. Gi£ sß x∗ ∈ S(F ; C) v(cid:160) ¯x ∈ C. N‚u
(cid:104)F (¯x), x∗ − ¯x(cid:105) = (cid:104)F (x∗), ¯x − x∗(cid:105) = 0
th… ¯x ∈ S(F ; C);
(cid:30)(cid:224)nh l(cid:254) 2.3. Gi£ sß A1, A2 v(cid:160) A3 (cid:31)•u th(cid:228)a m¢n. Khi (cid:31)(cid:226), d¢y {xk} hºi
t(cid:246) (cid:31)‚n mºt nghi»m cıa V IP (F ; C).
Chøng minh. Gi£ sß x∗ ∈ S(F ; C). Theo (cid:30)(cid:224)nh l(cid:254) 2.2, t(cid:231)n t⁄i mºt d¢y
con {xkj} cıa {xk} sao cho
(cid:104)F (xkj), x∗ − xkj(cid:105). (2.25) (cid:104)F (xk), x∗ − xk(cid:105) = lim j→+∞ lim sup k→+∞
Trong (cid:30)(cid:224)nh l(cid:254) 2.1, ta c(cid:226) {xkj} l(cid:160) d¢y b(cid:224) ch(cid:176)n. V“y, c(cid:226) ¯x ∈ C v(cid:160) mºt d¢y
con cıa {xkj}, kh(cid:230)ng m§t tŒng qu¡t, c(cid:246) th” l(cid:160) {xkj} sao cho
xkj = ¯x. (2.26) lim j→+∞
Do F li¶n t(cid:246)c, n¶n
(cid:104)F (xkj), x∗ − xkj(cid:105) (2.27) (cid:104)F (¯x), x∗ − ¯x(cid:105) = lim j→+∞
= 0.
Tł gi£ thi‚t A2 ta c(cid:226) (cid:104)F (¯x), x∗ − ¯x(cid:105) ≤ 0, d(cid:226) (cid:31)(cid:226) ta c(cid:226)
(cid:104)F (¯x), x∗ − ¯x(cid:105) = 0. (2.28)
Do (cid:31)(cid:226), ta suy ra ¯x ∈ S(F ; C). (cid:129)p d(cid:246)ng (cid:30)(cid:224)nh l(cid:254) 2.1 lƒn nœa ta (cid:31)(cid:247)æc d¢y
{(cid:107)xk − ¯x(cid:107)2} hºi t(cid:246), k‚t hæp v(cid:238)i (2.26) suy ra
xk = ¯x, ¯x ∈ S(F ; C). lim k→+∞
34
2 0 V‰ d(cid:246) 2.3. Cho F : R2 → R2 x¡c (cid:31)(cid:224)nh b(cid:240)i: F (x) = Ax v(cid:238)i A = . 0 2
Cho C = {x = (x1, x2) ∈ R2 : (cid:107)x(cid:107) ≤ 1}.
V(cid:238)i m(cid:229)i x = (x1, x2) ∈ C, v(cid:238)i m(cid:229)i y = (y1, y2) ∈ C ta c(cid:226):
(cid:104)F (x) − F (y), x − y(cid:105) = (cid:104)A(x − y), x − y(cid:105)
= 2(x1 − y1)(x1 − y1) + 2(x2 − y2)(x2 − y2)
= 2(x1 − y1)2 + 2(x2 − y2)2
= 2(cid:107)x − y(cid:107)2.
Do (cid:31)(cid:226) F l(cid:160) (cid:31)(cid:236)n (cid:31)i»u m⁄nh tr¶n C v(cid:238)i γ = 2.
Ta c(cid:226)
(cid:107)F (x) − F (y)(cid:107) = (cid:107)A(x − y)(cid:107) = 2(cid:107)x − y(cid:107).
Do (cid:31)(cid:226) F l(cid:160) 2 - li¶n t(cid:246)c Lipschitz tr¶n C.
Tł t‰nh (cid:31)(cid:236)n (cid:31)i»u m⁄nh cıa F suy ra b(cid:160)i to¡n:
T…m x∗ ∈ C: (cid:104)F (x∗), y − x∗(cid:105) ≥ 0, ∀y ∈ C
c(cid:226) duy nh§t nghi»m. D„ th§y r‹ng x∗ = (0, 0) l(cid:160) nghi»m duy nh§t cıa
b(cid:160)i to¡n.
Ch(cid:229)n c¡c tham sŁ th(cid:228)a m¢n gi£ thi‚t
, ∀k ≥ 1. ρk = 1, βk = 2 k + 1
Ph(cid:247)(cid:236)ng ph¡p chi‚u d(cid:247)(cid:238)i (cid:31)⁄o h(cid:160)m c(cid:226) d⁄ng:
x ∈ C
gk = A(xk) = (2xk 1 2xk 2)
xk+1 = PC(xk − αkgk)
35
v(cid:238)i γk = max{ρk, (cid:107)gk(cid:107)}. Ph†p chi‚u tr¶n C c(cid:226) d⁄ng trong (cid:31)(cid:226) αk = βk γk
n‚u (cid:107)x(cid:107) ≤ 1
PC(x) =
0 + (x − 0) n‚u (cid:107)x(cid:107) > 1. x 1 (cid:107)x − 0(cid:107)
Hay
x n‚u (cid:107)x(cid:107) ≤ 1
PC(x) =
n‚u (cid:107)x(cid:107) > 1. x (cid:107)x(cid:107)
(cid:19) , . L“p tr…nh tr¶n Matlab ta c(cid:226) b£ng k‚t V(cid:238)i (cid:31)i”m ban (cid:31)ƒu x0 = (cid:18)1 2 1 2
qu£ sau:
k (cid:107)xk − x∗(cid:107) xk 1 xk 2
1 -0.207106781 -0.207106781 0.292893218
2 0.069035593 0.0690335593 0.0976310729
3 0 0 0
36
K(cid:152)T LU(cid:138)N
Lu“n v«n nghi¶n cøu v• to¡n tß chi‚u metric l¶n t“p l(cid:231)i (cid:31)(cid:226)ng v(cid:160) øng
d(cid:246)ng v(cid:160)o b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n para-(cid:31)(cid:236)n (cid:31)i»u. C(cid:246) th” l(cid:160):
1. Nh›c l⁄i mºt sŁ kh¡i ni»m v(cid:160) t‰nh ch§t c(cid:236) b£n cıa t“p l(cid:231)i, h(cid:160)m l(cid:231)i v(cid:160)
(cid:31)(cid:224)nh l(cid:254) t¡ch c¡c t“p l(cid:231)i.
2. Gi(cid:238)i thi»u (cid:31)(cid:224)nh ngh(cid:190)a v(cid:160) c¡c t‰nh ch§t cıa ph†p chi‚u l¶n mºt t“p l(cid:231)i
(cid:31)(cid:226)ng v(cid:160) c(cid:230)ng thøc t‰nh h…nh chi‚u cıa mºt (cid:31)i”m l¶n c¡c t“p (cid:31)(cid:176)c bi»t
nh(cid:247) nßa kh(cid:230)ng gian, h…nh cƒu (cid:31)(cid:226)ng hay si¶u hºp,...
3. Gi(cid:238)i thi»u b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n v(cid:160) n¶u mŁi li¶n quan cıa
b(cid:160)i to¡n n(cid:160)y v(cid:238)i b(cid:160)i to¡n c(cid:252)c ti”u h(cid:160)m l(cid:231)i tr¶n t“p l(cid:231)i v(cid:160) b(cid:160)i to¡n b(cid:242)
phi tuy‚n.
4. Sß d(cid:246)ng ph†p chi‚u (cid:31)” x¥y d(cid:252)ng thu“t to¡n chi‚u d(cid:247)(cid:238)i (cid:31)⁄o h(cid:160)m gi£i
b(cid:160)i to¡n b§t (cid:31)flng thøc bi‚n ph¥n para-(cid:31)(cid:236)n (cid:31)i»u.
37
T(cid:160)i li»u tham kh£o
Ti‚ng Vi»t
[1] Nguy„n V«n Hi•n, L¶ D(cid:244)ng M(cid:247)u, Nguy„n Hœu (cid:30)i”n (2015), Gi¡o
Ti‚ng Anh
tr…nh Gi£i t‰ch l(cid:231)i øng d(cid:246)ng, NXB (cid:30)⁄i h(cid:229)c QuŁc Gia H(cid:160) Nºi.
[2] I. Konnov (2011), Combined Relaxation Algorithms for Variational
Inequalities, Springer.
[3] Hoang Tuy (2013), Convex Analysis and Global Optimization,
Springer.
[4] P. Santos and S. Scheimberg (2011), (cid:16)An inexact subgradient algo-
rithm for equilibrium problems(cid:17), Computational and Applied Math-
ematics, 30, pp. 91-107.
