Luận văn: NGHIÊN CỨU HIỆU CHỈNH HÓA TRONG BÀI TOÁN CÂN BẰNG

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIÊN CỨU HIỆU CHỈNH HÓA

TRONG BÀI TOÁN CÂN BẰNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN – 2009

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn1

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIÊN CỨU HIỆU CHỈNH HÓA

TRONG BÀI TOÁN CÂN BẰNG

Chuyên ngành: Toán ứng dụng Mã số: 60. 46. 36 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 - 2009

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn2

M(cid:244)c l(cid:244)c

Mº ﬁ˙u

Ch›‹ng 1. B(cid:181)i to‚n c'n b»ng 4

1.1. C‚c ki(cid:213)n thłc chu¨n b(cid:222) . . . . . . . . . . . . . . . . . . . . 4

1.2. B(cid:181)i to‚n c'n b»ng v(cid:181) c‚c tr›Œng h(cid:238)p ri“ng . . . . . . . . . . 9

Ch›‹ng 2. Ph›‹ng ph‚p chi(cid:213)u v(cid:181) ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n

c'n b»ng 16

2.1. Ph›‹ng ph‚p chi(cid:213)u gi¶i b(cid:181)i to‚n c'n b»ng . . . . . . . . . . 16

2.2. Ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n c'n b»ng . . 25

Ch›‹ng 3. Ph›‹ng ph‚p h(cid:181)m ﬁ‚nh gi‚ 40

3.1. H(cid:181)m ﬁ‚nh gi‚ A.Auslender . . . . . . . . . . . . . . . . . . 42

K(cid:213)t lu¸n

T(cid:181)i li(cid:214)u tham kh¶o

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn3

3.2. H(cid:181)m ﬁ‚nh gi‚ M.Fukushima . . . . . . . . . . . . . . . . . 48

Mº ﬁ˙u

B(cid:181)i to‚n c'n b»ng cª nhi(cid:210)u łng d(cid:244)ng trong khoa h(cid:228)c, k(cid:220) thu¸t v(cid:181) ﬁŒi sŁng

nh›: v¸t l(cid:221) (ﬁ˘c bi(cid:214)t l(cid:181) c‹ h(cid:228)c), ho‚ h(cid:228)c, sinh h(cid:228)c, qu'n sø, n«ng nghi(cid:214)p,

kinh t(cid:213), vi(cid:212)n th«ng... B(cid:181)i to‚n c'n b»ng l(cid:181) b(cid:181)i to‚n t(cid:230)ng qu‚t, nª bao g(cid:229)m

c‚c tr›Œng h(cid:238)p ri“ng nh›: b(cid:181)i to‚n tŁi ›u, b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n,

b(cid:181)i to‚n b(cid:239) phi tuy(cid:213)n, b(cid:181)i to‚n Nash trong tr(cid:223) ch‹i h(cid:238)p t‚c... Do cª łng

d(cid:244)ng thøc t(cid:213) rØng r•i n“n vi(cid:214)c quy v(cid:210) b(cid:181)i to‚n c'n b»ng v(cid:181) ﬁ›a ra c‚c thu¸t

to‚n gi¶i b(cid:181)i to‚n c'n b»ng l(cid:181) c˙n thi(cid:213)t. Ng(cid:181)y nay v(cid:237)i sø ph‚t tri(cid:211)n nhanh chªng cæa k(cid:220) thu¸t tin h(cid:228)c n“n ph„m vi v(cid:181) kh¶ n¤ng łng d(cid:244)ng cæa b(cid:181)i to‚n

c'n b»ng ng(cid:181)y c(cid:181)ng mº rØng.

Lu¸n v¤n n(cid:181)y nh»m gi(cid:237)i thi(cid:214)u v(cid:210) b(cid:181)i to‚n c'n b»ng v(cid:181) mØt sŁ ph›‹ng

ph‚p hi(cid:214)u ch(cid:216)nh cho b(cid:181)i to‚n c'n b»ng. Lu¸n v¤n g(cid:229)m m(cid:244)c l(cid:244)c, ba ch›‹ng,

Ch›‹ng 1 tr›(cid:237)c h(cid:213)t nh(cid:190)c l„i kh‚i ni(cid:214)m v(cid:181) k(cid:213)t qu¶ c‹ b¶n nh˚t v(cid:210) t¸p l(cid:229)i v(cid:181) h(cid:181)m l(cid:229)i sˇ ﬁ›(cid:238)c d(cid:239)ng º c‚c ch›‹ng sau. Ti(cid:213)p theo l(cid:181) gi(cid:237)i thi(cid:214)u v(cid:210) b(cid:181)i

ph˙n k(cid:213)t lu¸n v(cid:181) t(cid:181)i li(cid:214)u tham kh¶o.

to‚n c'n b»ng v(cid:181) c‚c tr›Œng h(cid:238)p ri“ng cæa nª. Ph˙n n(cid:181)y ﬁ›(cid:238)c coi l(cid:181) c‹ sº

Ch›‹ng 2 tr(cid:215)nh b(cid:181)y hai ph›‹ng ph‚p hi(cid:214)u ch(cid:216)nh b(cid:181)i to‚n c'n b»ng, ﬁª

l(cid:221) thuy(cid:213)t cho c‚c ph›‹ng ph‚p sˇ d(cid:239)ng ﬁ(cid:213)n º c‚c ch›‹ng sau.

Ch›‹ng 3 gi(cid:237)i thi(cid:214)u hai lo„i h(cid:181)m ﬁ‚nh gi‚ l(cid:181) h(cid:181)m ﬁ‚nh gi‚ Auslender v(cid:181) h(cid:181)m ﬁ‚nh gi‚ Fukushima. C‚c thu¸t to‚n t›‹ng łng v(cid:237)i hai lo„i h(cid:181)m ﬁ‚nh

l(cid:181) ph›‹ng ph‚p chi(cid:213)u v(cid:181) ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng.

gi‚ n(cid:181)y ﬁ›(cid:238)c tr(cid:215)nh b(cid:181)y chi ti(cid:213)t trong ch›‹ng 3.

§(cid:211) ho(cid:181)n th(cid:181)nh lu¸n v¤n n(cid:181)y, t‚c gi¶ ﬁ• nh¸n ﬁ›(cid:238)c sø gi(cid:243)p ﬁ(cid:236) v(cid:181) h›(cid:237)ng

d(cid:201)n t¸n t(cid:215)nh cæa GS.TSKH. L“ D(cid:242)ng M›u. T‚c gi¶ xin b(cid:181)y tÆ l(cid:223)ng bi(cid:213)t ‹n

s'u s(cid:190)c ﬁ(cid:213)n th(cid:181)y cæa m(cid:215)nh.

T‚c gi¶ xin ch'n th(cid:181)nh c¶m ‹n c‚c th(cid:181)y c« trong BØ m«n to‚n, Tr›Œng §„i h(cid:228)c Khoa h(cid:228)c- §„i h(cid:228)c Th‚i Nguy“n, c(cid:239)ng c‚c b„n h(cid:228)c vi“n l(cid:237)p cao

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn4

h(cid:228)c to‚n K1 ﬁ• lu«n t„o ﬁi(cid:210)u ki(cid:214)n thu¸n l(cid:238)i, ﬁØng vi“n, kh(cid:221)ch l(cid:214) ﬁ(cid:211) lu¸n

v¤n ﬁ›(cid:238)c ho(cid:181)n th(cid:181)nh.

M˘c d(cid:239) t‚c gi¶ ﬁ• cŁ g(cid:190)ng nh›ng lu¸n v¤n khª tr‚nh khÆi nh(cid:247)ng thi(cid:213)u

sªt, h„n ch(cid:213). T‚c gi¶ mong nh¸n ﬁ›(cid:238)c nh(cid:247)ng (cid:253) ki(cid:213)n ﬁªng gªp cæa c‚c th(cid:181)y

c« v(cid:181) b„n ﬁ(cid:228)c ﬁ(cid:211) lu¸n v¤n ﬁ›(cid:238)c ho(cid:181)n thi(cid:214)n h‹n.

Th‚i Nguy“n, 10/2009

Ho(cid:181)ng Th(cid:222) Kim Ng(cid:228)c

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn5

H(cid:228)c vi“n

Ch›‹ng 1

B(cid:181)i to‚n c'n b»ng

Ch›‹ng n(cid:181)y nh»m gi(cid:237)i thi(cid:214)u mØt sŁ kh‚i ni(cid:214)m v(cid:181) ki(cid:213)n thłc c‹ b¶n v(cid:210) b(cid:181)i

to‚n c'n b»ng v(cid:181) c‚c tr›Œng h(cid:238)p ri“ng cæa nª. Tr›(cid:237)c ti“n ta kh‚i qu‚t l„i

mØt sŁ ki(cid:213)n thłc v(cid:210) gi¶i t(cid:221)ch l(cid:229)i sˇ d(cid:239)ng ﬁ(cid:213)n trong c‚c ph˙n cæa lu¸n v¤n.

1.1. C‚c ki(cid:213)n thłc chu¨n b(cid:222)

Gi¶i t(cid:221)ch l(cid:229)i ﬁªng vai tr(cid:223) quan tr(cid:228)ng trong vi(cid:214)c nghi“n cłu, ph'n t(cid:221)ch v(cid:181)

x'y døng c‚c thu¸t to‚n gi¶i b(cid:181)i to‚n c'n b»ng. M(cid:244)c ﬁ(cid:221)ch ch(cid:221)nh cæa ph˙n

n(cid:181)y l(cid:181) nh(cid:190)c l„i mØt sŁ ki(cid:213)n thłc v(cid:210) gi¶i t(cid:221)ch l(cid:229)i, c‚c ﬁ(cid:222)nh l(cid:253) kh«ng ﬁ›(cid:238)c chłng minh cª th(cid:211) xem trong [4].

K(cid:221) hi(cid:214)u R l(cid:181) t¸p sŁ thøc, Rn l(cid:181) kh«ng gian Euclid n chi(cid:210)u.

§(cid:222)nh ngh(cid:220)a 1.1.1. [4] Cho hai ﬁi(cid:211)m a, b trong kh«ng gian Euclid n-chi(cid:210)u Rn. §›Œng th…ng ﬁi qua hai ﬁi(cid:211)m a, b l(cid:181) t¸p h(cid:238)p c‚c ﬁi(cid:211)m x trong Rn cª d„ng:

§o„n th…ng nŁi a, b l(cid:181) t¸p h(cid:238)p t˚t c¶ c‚c ﬁi(cid:211)m x trong Rn cª d„ng:

x = λa + (1 − λ)b, ∀λ ∈ R.

x = λa + (1 − λ)b = λ(a − b) + b, 0 ≤ λ ≤ 1.

§(cid:222)nh ngh(cid:220)a 1.1.2. [4] T¸p A ⊆ Rn g(cid:228)i l(cid:181) t¸p l(cid:229)i, n(cid:213)u nª chła tr(cid:228)n ﬁo„n th…ng nŁi hai ﬁi(cid:211)m b˚t k(cid:215) thuØc nª.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn6

V(cid:221) d(cid:244) 1.1.1. H(cid:215)nh 1.1 cho ta v(cid:221) d(cid:244) ﬁ‹n gi¶n v(cid:210) t¸p l(cid:229)i v(cid:181) t¸p kh«ng l(cid:229)i

(b) (c) (d)

(a) H(cid:215)nh 1.1. (a), (c)- T¸p l(cid:229)i; (b), (d)- T¸p kh«ng l(cid:229)i

§(cid:222)nh l(cid:253) 1.1.1. [1] T¸p l(cid:229)i l(cid:181) ﬁªng v(cid:237)i ph—p giao, ph—p h(cid:238)p, ph—p cØng, ph—p nh'n v(cid:237)i mØt sŁ v(cid:181) ph—p l˚y t(cid:230) h(cid:238)p tuy(cid:213)n t(cid:221)nh. Tłc l(cid:181), n(cid:213)u A v(cid:181) B l(cid:181) hai t¸p l(cid:229)i trong Rn th(cid:215) c‚c t¸p sau c(cid:242)ng l(cid:181) t¸p l(cid:229)i: a, A ∩ B := {x : x ∈ A, x ∈ B},

b, αA + βB := {x = αa + βb : a ∈ A, b ∈ B}.

§(cid:222)nh ngh(cid:220)a 1.1.3. [1] T¸p A ⊂ Rn ﬁ›(cid:238)c g(cid:228)i l(cid:181) nªn n(cid:213)u:

x ∈ A, λ ≥ 0 ⇒ λx ∈ A.

MØt nªn lu«n chła ﬁi(cid:211)m gŁc 0 ∈ Rn. T¸p A ⊂ Rn ﬁ›(cid:238)c g(cid:228)i l(cid:181) nªn l(cid:229)i n(cid:213)u A vıa l(cid:181) nªn vıa l(cid:181) t¸p l(cid:229)i, tłc l(cid:181)

λ1x + λ2y ∈ A, ∀x, y ∈ A, ∀λ1, λ2 ≥ 0.

§(cid:222)nh ngh(cid:220)a 1.1.4. [4] Cho t¸p l(cid:229)i A ⊂ Rn v(cid:181) ﬁi(cid:211)m x0 ∈ clA. T¸p

(cid:26) (cid:27) t ∈ Rn : (cid:10)t, x − x0(cid:11) ≤ 0, ∀x ∈ A NC(x0) =

l(cid:181) mØt nªn l(cid:229)i ﬁªng hay l(cid:181) nªn ph‚p tuy(cid:213)n ngo(cid:181)i cæa A t„i x0.

§(cid:222)nh ngh(cid:220)a 1.1.5. [3] Cho t¸p l(cid:229)i kh‚c r(cid:231)ng A ⊆ Rn. Vecto d 6= 0 ﬁ›(cid:238)c g(cid:228)i l(cid:181) ph›‹ng l(cid:239)i xa cæa A n(cid:213)u v(cid:237)i m(cid:231)i x ∈ A cª:

Nh¸n x—t [3] ? M(cid:228)i n(cid:246)a ﬁ›Œng th…ng song song v(cid:237)i mØt ph›‹ng l(cid:239)i xa d xu˚t ph‚t tı mØt ﬁi(cid:211)m b˚t k(cid:215) cæa A ﬁ(cid:210)u n»m tr(cid:228)n trong A. R(cid:226) r(cid:181)ng, t¸p A kh«ng b(cid:222) ch˘n khi

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn7

{x + λd | λ ≥ 0} ⊂ A.

v(cid:181) ch(cid:216) khi A cª mØt ph›‹ng l(cid:239)i xa. ? T¸p t˚t c¶ c‚c ph›‹ng l(cid:239)i xa cæa t¸p l(cid:229)i A ⊆ Rn c(cid:239)ng vecto 0 t„o th(cid:181)nh nªn l(cid:229)i. Nªn l(cid:229)i ﬁ›(cid:238)c g(cid:228)i l(cid:181) nªn l(cid:239)i xa cæa t¸p A v(cid:181) k(cid:221) hi(cid:214)u l(cid:181) recA. ? Ta nªi hai ph›‹ng d1 v(cid:181) d2 l(cid:181) kh‚c bi(cid:214)t n(cid:213)u d1 6= αd2, α > 0. Ph›‹ng l(cid:239)i xa d cæa t¸p A ﬁ›(cid:238)c g(cid:228)i l(cid:181) ph›‹ng cøc bi“n cæa A n(cid:213)u kh«ng t(cid:229)n t„i c‚c ph›‹ng l(cid:239)i xa kh‚c bi(cid:214)t d1 v(cid:181) d2 cæa A sao cho d = λ1d1 +λ2d2, λ1, λ2 > 0.

§(cid:222)nh ngh(cid:220)a 1.1.6. [1] MØt t¸p h(cid:238)p l(cid:181) giao cæa mØt sŁ h(cid:247)u h„n c‚c n(cid:246)a kh«ng gian ﬁªng ﬁ›(cid:238)c g(cid:228)i l(cid:181) t¸p l(cid:229)i ﬁa di(cid:214)n hay g(cid:228)i l(cid:181) kh(cid:243)c l(cid:229)i.

§(cid:222)nh ngh(cid:220)a 1.1.7. [1] T¸p con B cæa kh(cid:243)c l(cid:229)i A ﬁ›(cid:238)c g(cid:228)i l(cid:181) mØt di(cid:214)n cæa A n(cid:213)u h(cid:212) B chła mØt ﬁi(cid:211)m trong cæa mØt ﬁo„n th…ng n(cid:181)o ﬁª cæa A th(cid:215) B chła c¶ ﬁo„n th…ng ﬁª cæa A. Tłc l(cid:181),

∀a, b ∈ A n(cid:213)u x = λa + (1 − λ)b ∈ B, 0 < λ < 1 ⇒ a, b ∈ B.

MØt di(cid:214)n cª thł nguy“n b»ng 0 ﬁ›(cid:238)c g(cid:228)i l(cid:181) mØt ﬁ(cid:216)nh hay mØt ﬁi(cid:211)m cøc bi“n. C„nh l(cid:181) di(cid:214)n cª thł nguy“n b»ng 1.

§(cid:222)nh l(cid:253) 1.1.2. [1] a, M(cid:228)i t¸p l(cid:229)i ﬁa di(cid:214)n kh«ng chła tr(cid:228)n mØt ﬁ›Œng th…ng ﬁ(cid:210)u cª (cid:221)t nh˚t mØt ﬁ(cid:216)nh. b, M(cid:228)i t¸p l(cid:229)i ﬁa di(cid:214)n A cª ﬁ(cid:216)nh b»ng t¸p h(cid:238)p cæa c‚c ﬁi(cid:211)m x cª d„ng:

i∈I

j∈J λi = 1, λi, βj ≥ 0 v(cid:237)i m(cid:228)i i, j c(cid:223)n vi l(cid:181) c‚c ﬁ(cid:216)nh, dj l(cid:181) c‚c

X X x = λivi + βjdj

trong ﬁª, P i∈I ph›‹ng cæa c‚c c„nh v« h„n cæa A.

§(cid:222)nh ngh(cid:220)a 1.1.8. [5] Cho M, K l(cid:181) c‚c t¸p l(cid:229)i kh‚c r(cid:231)ng cæa Rn, M ⊆ K v(cid:181) f : K × K → R ∪ {+∞}. Khi ﬁª: a, H(cid:181)m f ﬁ‹n ﬁi(cid:214)u m„nh tr“n M v(cid:237)i h»ng sŁ τ > 0 n(cid:213)u v(cid:237)i m(cid:231)i c˘p x, y ∈ M ta cª:

f (x, y) + f (y, x) ≤ −τ k x − y k2 .

b, H(cid:181)m f ﬁ‹n ﬁi(cid:214)u ch˘t tr“n M n(cid:213)u v(cid:237)i m(cid:228)i x, y ∈ M ta cª:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn8

f (x, y) + f (y, x) < 0.

c, H(cid:181)m f ﬁ‹n ﬁi(cid:214)u tr“n M n(cid:213)u v(cid:237)i m(cid:231)i c˘p x, y ∈ M ta cª:

f (x, y) + f (y, x) ≤ 0.

d, H(cid:181)m f gi¶ ﬁ‹n ﬁi(cid:214)u tr“n M n(cid:213)u v(cid:237)i m(cid:231)i c˘p x, y ∈ M th(cid:215):

f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0.

§(cid:222)nh ngh(cid:220)a 1.1.9. [4] a, H(cid:181)m f l(cid:181) h(cid:181)m l(cid:229)i x‚c ﬁ(cid:222)nh tr“n t¸p l(cid:229)i X ⊆ Rn, n(cid:213)u:

f (cid:2)λx + (1 − λ)y(cid:3) ≤ λf (x) + (1 − λ)f (y),

v(cid:237)i b˚t k(cid:215) x, y ∈ X v(cid:181) sŁ thøc λ ∈ [0, 1]. b, H(cid:181)m f l(cid:181) h(cid:181)m l(cid:229)i ch˘t tr“n t¸p l(cid:229)i X, n(cid:213)u:

f (cid:2)λx + (1 − λ)y(cid:3) < λf (x) + (1 − λ)f (y),

v(cid:237)i b˚t k(cid:215) x, y ∈ X, x 6= y v(cid:181) λ ∈ (0, 1). c, H(cid:181)m f l(cid:181) h(cid:181)m l(cid:229)i m„nh v(cid:237)i h(cid:214) sŁ β > 0 tr“n t¸p l(cid:229)i X n(cid:213)u:

f (cid:2)λx + (1 − λ)y(cid:3) ≤ λf (x) + (1 − λ)f (y) − β(1 − λ)λ k x − y k2,

v(cid:237)i b˚t k(cid:215) x, y ∈ X v(cid:181) λ ∈ (0, 1). d, H(cid:181)m f ﬁ›(cid:238)c g(cid:228)i l(cid:181) h(cid:181)m tøa l(cid:229)i tr“n t¸p l(cid:229)i X, n(cid:213)u v(cid:237)i ∀α ∈ R, t¸p młc d›(cid:237)i Lα(f ) = {x ∈ X : f (x) ≤ α} l(cid:181) t¸p l(cid:229)i.

§(cid:222)nh l(cid:253) 1.1.3. [1] Cho f l(cid:181) h(cid:181)m l(cid:229)i tr“n t¸p l(cid:229)i A v(cid:181) g l(cid:181) h(cid:181)m l(cid:229)i tr“n t¸p l(cid:229)i B. Khi ﬁª, c‚c h(cid:181)m sau l(cid:181) h(cid:181)m l(cid:229)i tr“n t¸p l(cid:229)i A ∩ B: a, λf + βg, ∀λ, β ≥ 0,

b, max(f, g).

§(cid:222)nh l(cid:221) 1.1.3 nh(cid:215)n chung kh«ng ﬁ(cid:243)ng cho h(cid:181)m tøa l(cid:229)i. MØt h(cid:181)m l(cid:229)i cª th(cid:211) kh«ng li“n t(cid:244)c t„i mØt ﬁi(cid:211)m tr“n bi“n mi(cid:210)n x‚c ﬁ(cid:222)nh cæa nª. Tuy nhi“n, nª

l„i li“n t(cid:244)c t„i m(cid:228)i ﬁi(cid:211)m trong cæa t¸p ﬁª theo ﬁ(cid:222)nh l(cid:221) sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn9

§(cid:222)nh l(cid:253) 1.1.4. [1] MØt h(cid:181)m l(cid:229)i x‚c ﬁ(cid:222)nh tr“n t¸p l(cid:229)i A th(cid:215) li“n t(cid:244)c t„i m(cid:228)i ﬁi(cid:211)m trong cæa t¸p A.

§(cid:222)nh l(cid:253) 1.1.5. [4] Cho h(cid:181)m f l(cid:229)i, kh¶ vi tr“n t¸p l(cid:229)i A. Khi ﬁª v(cid:237)i m(cid:228)i x, y ∈ A cª:

f (y) − f (x) ≥ (cid:10)∇f (x), y − x(cid:11).

N(cid:213)u f l(cid:229)i ch˘t, kh¶ vi tr“n t¸p l(cid:229)i A. Khi ﬁª v(cid:237)i m(cid:228)i x, y ∈ A v(cid:181) x 6= y ta cª:

f (y) − f (x) > (cid:10)∇f (x), y − x(cid:11).

N(cid:213)u f l(cid:181) l(cid:229)i m„nh v(cid:237)i h(cid:214) sŁ β > 0, kh¶ vi tr“n t¸p l(cid:229)i A. Khi ﬁª v(cid:237)i m(cid:228)i x, y ∈ A ta cª:

f (y) − f (x) ≥ (cid:10)∇f (x), y − x(cid:11) + β k y − x k2 .

§(cid:222)nh l(cid:253) 1.1.6. [1] Cho f l(cid:181) h(cid:181)m l(cid:229)i, kh¶ vi tr“n t¸p l(cid:229)i ﬁªng A. MØt ﬁi(cid:211)m x∗ ∈ A l(cid:181) nghi(cid:214)m tŁi ›u cæa b(cid:181)i to‚n quy ho„ch l(cid:229)i:

f (x) min x∈A

khi v(cid:181) ch(cid:216) khi nª l(cid:181) ﬁi(cid:211)m dıng cæa f tr“n A, tłc l(cid:181):

(cid:10)∇f (x∗), y − x∗(cid:11) ≥ 0, ∀y ∈ A.

Tı ﬁ(cid:222)nh l(cid:221) 1.1.5 v(cid:181) 1.1.6 cª: n(cid:213)u f l(cid:181) h(cid:181)m l(cid:229)i m„nh tr“n t¸p l(cid:229)i ﬁªng A th(cid:215) b(cid:181)i to‚n:

f (x) min x∈A

cª nghi(cid:214)m duy nh˚t.

§(cid:222)nh ngh(cid:220)a 1.1.10. [1] Cho f l(cid:181) mØt h(cid:181)m l(cid:229)i tr“n t¸p l(cid:229)i A. MØt vecto y∗ ∈ Rn ﬁ›(cid:238)c g(cid:228)i l(cid:181) d›(cid:237)i vi ph'n cæa f t„i x∗ ∈ A n(cid:213)u: f (x) ≥ f (x∗) + (cid:10)y∗, x − x∗(cid:11), ∀x ∈ A.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn10

T¸p h(cid:238)p t˚t c¶ c‚c ﬁi(cid:211)m y∗ tho¶ m•n b˚t ﬁ…ng thłc tr“n ﬁ›(cid:238)c k(cid:221) hi(cid:214)u ∂f (x∗). T¸p ∂f (x∗) nh(cid:215)n chung th›Œng chła nhi(cid:210)u ﬁi(cid:211)m. Trong tr›Œng h(cid:238)p ∂f (x∗) ch(cid:216) chła duy nh˚t mØt ﬁi(cid:211)m ta nªi r»ng f kh¶ vi t„i x∗.

V(cid:221) d(cid:244) 1.1.2. f (x) =k x k kh¶ vi t„i m(cid:228)i ﬁi(cid:211)m x 6= 0 do ∂f (x) = k x k−1x, kh«ng kh¶ vi t„i x = 0 do ∂f (x) = {y : k x k≥ (cid:10)y, x(cid:11), ∀y}.

§(cid:222)nh ngh(cid:220)a 1.1.11. [3] Cho D ⊂ Rn, D 6= ∅, f : D → R. MØt ﬁi(cid:211)m x∗ ∈ D ﬁ›(cid:238)c g(cid:228)i l(cid:181) cøc ti(cid:211)u ﬁ(cid:222)a ph›‹ng cæa f tr“n D, n(cid:213)u t(cid:229)n t„i mØt l'n c¸n mº U cæa x∗, sao cho f (x∗) ≤ f (x), ∀x ∈ D ∩ U . §i(cid:211)m x∗ ﬁ›(cid:238)c g(cid:228)i l(cid:181) cøc ti(cid:211)u tuy(cid:214)t ﬁŁi cæa f tr“n D n(cid:213)u f (x∗) ≤ f (x), ∀x ∈ D.

§(cid:222)nh l(cid:253) 1.1.7. [1] a, M(cid:228)i ﬁi(cid:211)m cøc ti(cid:211)u ﬁ(cid:222)a ph›‹ng cæa mØt h(cid:181)m l(cid:229)i tr“n mØt t¸p l(cid:229)i ﬁ(cid:210)u l(cid:181) ﬁi(cid:211)m cøc ti(cid:211)u tuy(cid:214)t ﬁŁi. b, N(cid:213)u x∗ l(cid:181) ﬁi(cid:211)m cøc ti(cid:211)u cæa h(cid:181)m l(cid:229)i f tr“n t¸p l(cid:229)i D v(cid:181) x∗ ∈ intD th(cid:215) 0 ∈ ∂f (x∗).

§(cid:222)nh l(cid:253) 1.1.8. [1] Cøc ﬁ„i cæa mØt h(cid:181)m l(cid:229)i (n(cid:213)u cª ) tr“n mØt t¸p l(cid:229)i cª ﬁi(cid:211)m cøc bi“n bao giŒ c(cid:242)ng ﬁ„t t„i mØt ﬁi(cid:211)m cøc bi“n.

1.2. B(cid:181)i to‚n c'n b»ng v(cid:181) c‚c tr›Œng h(cid:238)p ri“ng

B(cid:181)i to‚n c'n b»ng cª (cid:253) ngh(cid:220)a quan tr(cid:228)ng trong kinh t(cid:213) v(cid:181) nhi(cid:210)u l(cid:220)nh vøc

thøc ti(cid:212)n kh‚c. H‹n n(cid:247)a, b(cid:181)i to‚n c'n b»ng l(cid:181) sø mº rØng cæa nhi(cid:210)u b(cid:181)i

to‚n kh‚c nh›: b(cid:181)i to‚n tŁi ›u, b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n, b(cid:181)i to‚n

c'n b»ng Nash... V(cid:215) l(cid:221) do ﬁª m(cid:181) l(cid:237)p c‚c b(cid:181)i to‚n c'n b»ng ﬁ›(cid:238)c nhi(cid:210)u nh(cid:181)

to‚n h(cid:228)c quan t'm, nghi“n cłu. Ph˙n n(cid:181)y sˇ gi(cid:237)i thi(cid:214)u d„ng to‚n h(cid:228)c cæa

b(cid:181)i to‚n c'n b»ng v(cid:181) mØt sŁ b(cid:181)i to‚n t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng. NØi dung chæ y(cid:213)u cæa ph˙n n(cid:181)y ﬁ›(cid:238)c tham kh¶o trong [2].

Trong to(cid:181)n bØ lu¸n v¤n n(cid:181)y ta lu«n gi¶ thi(cid:213)t K l(cid:181) t¸p l(cid:229)i ﬁªng kh‚c r(cid:231)ng trong Rn.

§(cid:222)nh ngh(cid:220)a 1.2.1. [2] Cho h(cid:181)m f : K × K → R tho¶ m•n f (x, x) = 0, ∀x ∈ K. Khi ﬁª, b(cid:181)i to‚n c'n b»ng ﬁ›(cid:238)c ph‚t bi(cid:211)u nh› sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn11

T(cid:215)m x∗ ∈ K sao cho f (x∗, y) ≥ 0, ∀y ∈ K. (1.1)

H(cid:181)m sŁ f tho¶ m•n t(cid:221)nh ch˚t f (x, x) = 0, ∀x ∈ K ﬁ›(cid:238)c g(cid:228)i l(cid:181) h(cid:181)m c'n b»ng tr“n K.

Nh› ﬁ• nªi º tr“n, c‚c b(cid:181)i to‚n quan tr(cid:228)ng cª th(cid:211) ﬁ›a v(cid:210) b(cid:181)i to‚n c'n b»ng.

D›(cid:237)i ﬁ'y ta tr(cid:215)nh b(cid:181)y sø t›‹ng ﬁ›‹ng cæa b(cid:181)i to‚n c'n b»ng v(cid:237)i c‚c b(cid:181)i

B(cid:181)i to‚n tŁi ›u [2] Cho J : K → R l(cid:181) mØt h(cid:181)m sŁ x‚c ﬁ(cid:222)nh tr“n K. Khi ﬁª, b(cid:181)i to‚n tŁi ›u ﬁ›(cid:238)c ph‚t bi(cid:211)u nh› sau:

to‚n kh‚c.

T(cid:215)m x∗ ∈ K sao cho J(x∗) ≤ J(y), ∀y ∈ K. (1.2)

N(cid:213)u ta ﬁ˘t f (x, y) := J(y) − J(x) v(cid:237)i ∀x, y ∈ K th(cid:215) b(cid:181)i to‚n tŁi ›u t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng.

Th¸t v¸y, gi¶ s(cid:246) x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.2) n“n theo ﬁ(cid:222)nh ngh(cid:220)a ta cª:

J(x∗) ≤ J(y), ∀y ∈ K.

M˘t kh‚c,

f (x, y) = J(y) − J(x), ∀x, y ∈ K.

Do ﬁª,

f (x∗, y) = J(y) − J(x∗) ≥ 0, ∀y ∈ K.

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.1). Ng›(cid:238)c l„i, cho x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.1) n“n ta cª:

f (x∗, y) ≥ 0, ∀y ∈ K.

Theo c‚ch ﬁ˘t ta cª:

f (x∗, y) = J(y) − J(x∗) ≥ 0, ∀y ∈ K ⇒ J(y) ≥ J(x∗), ∀y ∈ K.

B(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n t(cid:230)ng qu‚t [2]

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn12

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.2).

Cho T : K → 2Rn l(cid:181) ‚nh x„ n(cid:246)a li“n t(cid:244)c tr“n tı mØt ﬁi(cid:211)m v(cid:181)o mØt t¸p h(cid:238)p sao cho T (x) l(cid:181) t¸p compact, ∀x ∈ K. Khi ﬁª, b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n t(cid:230)ng qu‚t ﬁ›(cid:238)c ph‚t bi(cid:211)u nh› sau:

(cid:10)ξ∗, y − x∗(cid:11) ≥ 0, ∀y ∈ K T(cid:215)m x∗ ∈ K, ξ∗ ∈ T (x∗) sao cho

(1.3) (cid:10)ξ, y − x(cid:11), ∀x, y ∈ K th(cid:215) b(cid:181)i to‚n c'n N(cid:213)u ta ﬁ˘t f (x, y) := maxξ∈T (x) b»ng (1.1) t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n t(cid:230)ng qu‚t.

Th¸t v¸y, gi¶ s(cid:246) x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.3) n“n cª:

(cid:10)ξ∗, y − x∗(cid:11) ≥ 0, ∀y ∈ K, ξ∗ ∈ T (x∗).

M˘t kh‚c theo c‚ch ﬁ˘t ta cª:

(cid:10)ξ∗, y − x∗(cid:11) ≥ 0, ∀y ∈ K. f (x∗, y) = max ξ∗∈T (x∗)

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.1). Ng›(cid:238)c l„i, cho x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.1) n“n

f (x∗, y) ≥ 0, ∀y ∈ K.

Theo c‚ch ﬁ˘t ta cª:

(cid:10)ξ∗, y − x∗(cid:11) ≥ 0, ∀y ∈ K. f (x∗, y) = max ξ∗∈T (x∗)

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.3).

• N(cid:213)u T l(cid:181) ‚nh x„ ﬁ‹n tr(cid:222) th(cid:215) b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n t(cid:230)ng qu‚t l(cid:181) b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n sau:

(cid:10)T (x∗), y − x∗(cid:11) ≥ 0, ∀y ∈ K. T(cid:215)m x∗ ∈ K sao cho

B(cid:181)i to‚n b(cid:239) phi tuy(cid:213)n [2] Cho K ⊆ Rn l(cid:181) mØt nªn l(cid:229)i ﬁªng, K ∗ = {x ∈ Rn | (cid:10)x, y(cid:11) ≥ 0, ∀y ∈ K} l(cid:181) nªn ﬁŁi cøc cæa nªn K.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn13

(1.4) N(cid:213)u ta ﬁ˘t f (x, y) := (cid:10)T (x), y − x(cid:11), ∀x, y ∈ K th(cid:215) v(cid:237)i c‚ch l¸p lu¸n nh› tr“n b(cid:181)i to‚n (1.4) t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng (1.1).

Cho ‚nh x„ T : K → Rn li“n t(cid:244)c. Khi ﬁª, b(cid:181)i to‚n b(cid:239) phi tuy(cid:213)n ﬁ›(cid:238)c ph‚t bi(cid:211)u nh› sau:

(cid:10)T (x∗), x∗(cid:11) = 0. T(cid:215)m x∗ ∈ K sao cho T (x∗) ∈ K v(cid:181)

(1.5) N(cid:213)u ta ﬁ˘t f (x, y) := (cid:10)T (x), y − x(cid:11), ∀x, y ∈ K th(cid:215) b(cid:181)i to‚n b(cid:239) phi tuy(cid:213)n (1.5) sˇ t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng (1.1).

Th¸t v¸y, gi¶ s(cid:246) x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.5) n“n ta cª:

(cid:10)T (x∗), x∗(cid:11) = 0. T (x∗) ∈ K v(cid:181)

M˘t kh‚c theo c‚ch ﬁ˘t ta cª:

f (x∗, y) = (cid:10)T (x∗), y − x∗(cid:11)

= (cid:10)T (x∗), y(cid:11) − (cid:10)T (x∗), x∗(cid:11) = (cid:10)T (x∗), y(cid:11) ≥ 0, ∀y ∈ K.

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng (1.1). Ng›(cid:238)c l„i, cho x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.1) ta cª:

f (x∗, y) ≥ 0 ∀y ∈ K.

Theo c‚ch ﬁ˘t ta cª:

f (x∗, y) = (cid:10)T (x∗), y − x∗(cid:11), ∀y ∈ K.

(cid:10)T (x∗), −x∗(cid:11) ≥ 0 hay

(cid:10)T (x∗), 2x∗ − x∗(cid:11) ≥ 0 hay

Do K l(cid:181) nªn n“n 0 ∈ K v(cid:181) 2x∗ ∈ K. Trong ﬁ…ng thłc tr“n n(cid:213)u l˚y (cid:10)T (x∗), x∗(cid:11) ≤ 0, c(cid:223)n n(cid:213)u l˚y y = 0 ∈ K cª (cid:10)T (x∗), x∗(cid:11) ≥ 0.V¸y y = 2x∗ ∈ K ta cª (cid:10)T (x∗), x∗(cid:11) = 0. H‹n n(cid:247)a, do 0 ≤ (cid:10)T (x∗), y − x∗(cid:11) = (cid:10)T (x∗), y(cid:11) − (cid:10)t(x∗), x∗(cid:11) = (cid:10)T (x∗), y(cid:11), ∀y ∈ K. (cid:10)T (x∗), y(cid:11) ≥ 0, ∀y ∈ K n“n T (x∗) ∈ K. Do ﬁª, x∗ ∈ K l(cid:181) nghi(cid:214)m

Ch(cid:243) (cid:253) Khi K l(cid:181) nªn l(cid:229)i ﬁªng th(cid:215) b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n (1.4)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn14

Do cæa (1.5).

ch(cid:221)nh l(cid:181) b(cid:181)i to‚n b(cid:239) phi tuy(cid:213)n (1.5).

B(cid:181)i to‚n ﬁi(cid:211)m b˚t ﬁØng Kakutani [2] Cho T : Rn → 2Rn Khi ﬁª, b(cid:181)i to‚n ﬁi(cid:211)m b˚t ﬁØng Kakutani ﬁ›(cid:238)c ph‚t bi(cid:211)u nh› sau:

v(cid:237)i K ∩T (x) l(cid:181) t¸p compact l(cid:229)i, kh‚c r(cid:231)ng, v(cid:237)i ∀x ∈ K.

T(cid:215)m x∗ ∈ K sao cho x∗ ∈ T (x∗)

(1.6) (cid:10)x − ξ, y − x(cid:11), ∀x, y ∈ K th(cid:215) b(cid:181)i to‚n c'n

N(cid:213)u ta ﬁ˘t f (x, y) := maxξ∈T (x) b»ng (1.1) t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n ﬁi(cid:211)m b˚t ﬁØng (1.6).

Th¸t v¸y, gi¶ s(cid:246) x∗ ∈ K l(cid:181) nghi(cid:214)m cæa (1.6) n“n

T (x∗) = x∗.

M˘t kh‚c theo c‚ch ﬁ˘t ta cª

f (x∗, y) = (cid:10)x∗ − T (x∗), y − x∗(cid:11), ∀y ∈ K.

Do ﬁª, x∗ ∈ K l(cid:181) nghi(cid:214)m cæa (1.1). Ng›(cid:238)c l„i, cho x∗ ∈ K l(cid:181) nghi(cid:214)m cæa (1.1) n“n

f (x∗, y) ≥ 0, ∀y ∈ K.

Theo c‚ch ﬁ˘t cª

f (x∗, y) = (cid:10)x∗ − T (x∗), y − x∗(cid:11), ∀y ∈ K.

Ch(cid:228)n y = T (x∗) ∈ K ta cª

f (x∗, y) = (cid:10)x∗ − T (x∗), T (x∗) − x∗(cid:11) ≥ 0, ∀y ∈ K ⇒ − k x∗ − T (x∗) k≥ 0, ∀y ∈ K ⇒k x∗ − T (x∗) k≤ 0, ∀y ∈ K ⇒ x∗ = T (x∗), ∀y ∈ K.

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa (1.6).

• N(cid:213)u T l(cid:181) ‚nh x„ ﬁ‹n tr(cid:222) th(cid:215) b(cid:181)i to‚n ﬁi(cid:211)m b˚t ﬁØng Kakutani trº th(cid:181)nh b(cid:181)i to‚n ﬁi(cid:211)m b˚t ﬁØng Brouwer sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn15

(1.7) T(cid:215)m x∗ ∈ K sao cho x∗ = T (x∗).

i (t¸p chi(cid:213)n l›(cid:238)c cæa ng›Œi ch‹i thł i ).

B(cid:181)i to‚n c'n b»ng Nash (trong tr(cid:223) ch‹i kh«ng h(cid:238)p t‚c) [2] • Cho I = {1, 2, . . . , p} l(cid:181) t¸p ch(cid:216) sŁ h(cid:247)u h„n (t¸p p−ng›Œi ch‹i ). • Ki l(cid:181) t¸p l(cid:229)i kh‚c r(cid:231)ng cæa Rn • H(cid:181)m fi : K1 × . . . × Kp → R cho tr›(cid:237)c (h(cid:181)m t(cid:230)n th˚t cæa ng›Œi ch‹i thł i khi vi ph„m chi(cid:213)n l›(cid:238)c cæa nh(cid:247)ng ng›Œi ch‹i v(cid:237)i ∀i ∈ I ) Cho x = (x1, . . . , xp) ∈ K1 × . . . Kp v(cid:181) y = (y1, . . . , yp) ∈ K1 × . . . Kp Ta ﬁ(cid:222)nh ngh(cid:220)a vecto x[yi] ∈ K1 × . . . × Kp nh› sau:

N(cid:213)u ta ﬁ˘t f (x, y) := (cid:10)x − T (x), y − x(cid:11), ∀x, y ∈ K th(cid:215) v(cid:237)i c‚ch l¸p lu¸n nh› tr“n ch(cid:216) ra ﬁ›(cid:238)c r»ng b(cid:181)i to‚n (1.7) t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng.

  xj, ∀j 6= i x[yi]j = ∀j = i  yi,

§˘t K = K1 × . . . × Kp Khi ﬁª, b(cid:181)i to‚n c'n b»ng Nash ﬁ›(cid:238)c ph‚t bi(cid:211)u nh› sau:

T(cid:215)m x∗ ∈ K sao cho fi(x∗) ≤ fi(x∗[yi]), ∀i ∈ I, ∀y ∈ K. (1.8)

§i(cid:211)m tho¶ m•n (1.8) g(cid:228)i l(cid:181) ﬁi(cid:211)m c'n b»ng Nash. V(cid:210) (cid:253) ngh(cid:220)a kinh t(cid:213), ﬁi(cid:211)m c'n b»ng n(cid:181)y nªi l“n r»ng b˚t k(cid:215) ﬁŁi thæ n(cid:181)o ch(cid:228)n ph›‹ng ‚n ra khÆi ﬁi(cid:211)m

c'n b»ng trong khi c‚c ﬁŁi thæ c(cid:223)n l„i v(cid:201)n gi(cid:247) ph›‹ng ‚n ﬁi(cid:211)m c'n b»ng

p P i=1

{fi(x[yi]) − fi(x)} th(cid:215) ﬁŁi thæ ra khÆi ﬁi(cid:211)m c'n b»ng sˇ b(cid:222) thua thi(cid:214)t. N(cid:213)u ta ﬁ˘t f : K×K → R ﬁ›(cid:238)c x‚c ﬁ(cid:222)nh bºi f (x, y) :=

v(cid:237)i ∀x, y ∈ K th(cid:215) b(cid:181)i to‚n c'n b»ng Nash (1.8) t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng (1.1).

Th¸t v¸y, gi¶ s(cid:246) x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.8) n“n:

p X

fi(x∗) ≤ fi(x∗[yi]), ∀i ∈ I, ∀yi ∈ Ki ⇒ fi(x∗[yi]) − fi(x∗) ≥ 0, ∀i ∈ I, ∀yi ∈ Ki

i=1

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn16

⇒ (cid:8)fi(x∗[yi]) − fi(x∗)(cid:9) ≥ 0, ∀y ∈ K.

Theo c‚ch ﬁ˘t cª:

f (x∗, y) ≥ 0, ∀y ∈ K.

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa (1.1). Ng›(cid:238)c l„i, cho x∗ ∈ K l(cid:181) nghi(cid:214)m cæa (1.1) m(cid:181) kh«ng l(cid:181) nghi(cid:214)m cæa (1.9). Do x∗ ∈ K l(cid:181) nghi(cid:214)m cæa (1.1) n“n ta cª:

f (x∗, y) ≥ 0, ∀y ∈ K.

p X

Theo c‚ch ﬁ˘t cª:

i=1

{fi(x∗[yi]) − fi(x∗)} ≥ 0, ∀i ∈ K, ∀y ∈ K.

Do x∗ ∈ K kh«ng l(cid:181) nghi(cid:214)m cæa (1.8) n“n ∃i0 ∈ K sao cho:

fi(x∗) > fi(x∗[yi]), ∀yi ∈ Ki.

Ta l˚y x∗[yj] = x∗, ∀j 6= i0 suy ra

fi(x∗[yj]) − fi(x∗) = 0, ∀j 6= i0.

p X

K(cid:213)t h(cid:238)p hai ﬁi(cid:210)u tr“n ta suy ra

i=1

(cid:8)fi(x∗[yi]) − fi(x∗)(cid:9) < 0, m'u thu(cid:201)n.

K(cid:213)t lu¸n ch›‹ng

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (1.8).

Ch›‹ng n(cid:181)y tr›(cid:237)c ti“n nh(cid:190)c l„i mØt sŁ k(cid:213)t qu¶ c‹ b¶n cæa gi¶i t(cid:221)ch l(cid:229)i sˇ

d(cid:239)ng ﬁ(cid:213)n trong c‚c ch›‹ng sau. Ti(cid:213)p theo l(cid:181) tr(cid:215)nh b(cid:181)y d„ng to‚n h(cid:228)c cæa

b(cid:181)i to‚n c'n b»ng, ﬁ(cid:229)ng thŒi th«ng qua c‚c ph—p bi(cid:213)n ﬁ(cid:230)i ph(cid:239) h(cid:238)p ch(cid:216) ra sø

t›‹ng ﬁ›‹ng gi(cid:247)a b(cid:181)i to‚n c'n b»ng v(cid:237)i b(cid:181)i to‚n tŁi ›u, b(cid:181)i to‚n b˚t ﬁ…ng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn17

thłc bi(cid:213)n ph'n, b(cid:181)i to‚n b(cid:239) phi tuy(cid:213)n, b(cid:181)i to‚n ﬁi(cid:211)m b˚t ﬁØng, b(cid:181)i to‚n c'n b»ng Nash.

Ch›‹ng 2

Ph›‹ng ph‚p chi(cid:213)u v(cid:181) ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n c'n b»ng

B(cid:181)i to‚n c'n b»ng cª (cid:253) ngh(cid:220)a thøc ti(cid:212)n l(cid:237)n, do ﬁª vi(cid:214)c t(cid:215)m lŒi gi¶i cho b(cid:181)i

to‚n c'n b»ng l(cid:181) r˚t c˙n thi(cid:213)t. Ch›‹ng n(cid:181)y nh»m gi(cid:237)i thi(cid:214)u ph›‹ng ph‚p

chi(cid:213)u v(cid:181) ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n c'n b»ng. NØi dung chæ y(cid:213)u cæa ch›‹ng n(cid:181)y ﬁ›(cid:238)c xem trong [2], [5].

2.1. Ph›‹ng ph‚p chi(cid:213)u gi¶i b(cid:181)i to‚n c'n b»ng

Ph›‹ng ph‚p chi(cid:213)u l(cid:181) ph›‹ng ph‚p c‹ b¶n nh˚t ﬁ(cid:211) gi¶i b(cid:181)i to‚n ﬁŁi ng(cid:201)u

cæa b(cid:181)i to‚n c'n b»ng. Tr›(cid:237)c ti“n ta ﬁ(cid:222)nh ngh(cid:220)a b(cid:181)i to‚n ﬁŁi ng(cid:201)u.

§(cid:222)nh ngh(cid:220)a 2.1.1. [2] B(cid:181)i to‚n ﬁŁi ng(cid:201)u cæa b(cid:181)i to‚n c'n b»ng ﬁ›(cid:238)c ph‚t bi(cid:211)u nh› sau:

T(cid:215)m x∗ ∈ K sao cho : f (y, x∗) ≤ 0, ∀y ∈ K. (2.1)

Trong ﬁª, f : K × K → R l(cid:181) h(cid:181)m li“n t(cid:244)c tho¶ m•n:

a, f (x, x) = 0, ∀x ∈ K, b, f (x, .) : K → R l(cid:181) h(cid:181)m l(cid:229)i v(cid:237)i ∀x ∈ K.

y∈K

Lf (y). V(cid:237)i m(cid:231)i x ∈ K ﬁ˘t Lf (x) = {y ∈ K | f (x, y) ≤ 0}. R(cid:226) r(cid:181)ng, x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n ﬁŁi ng(cid:201)u (2.1) khi v(cid:181) ch(cid:216) khi x∗ ∈ T

§(cid:222)nh l(cid:221) sau ch(cid:216) ra mŁi quan h(cid:214) gi(cid:247)a nghi(cid:214)m cæa b(cid:181)i to‚n ﬁŁi ng(cid:201)u v(cid:181) nghi(cid:214)m

cæa b(cid:181)i to‚n c'n b»ng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn18

§(cid:222)nh l(cid:253) 2.1.1. [2] T¸p nghi(cid:214)m cæa b(cid:181)i to‚n ﬁŁi ng(cid:201)u l(cid:181) t¸p con cæa t¸p nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Chłng minh Cho x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n ﬁŁi ng(cid:201)u, l˚y y ∈ K, ∀λ ∈ [0, 1] ta ﬁ(cid:222)nh ngh(cid:220)a zλ ∈ K nh› sau:

zλ := λy + (1 − λ)x∗.

(a) =f (zλ, zλ) = f (zλ, λy + (1 − λ)x∗) 0

(b) ≤λf (zλ, y) + (1 − λ)f (zλ, x∗). (2.2)

V(cid:237)i m(cid:231)i λ ∈ [0, 1] ta cª

Do x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n ﬁŁi ng(cid:201)u n“n:

y∈K

Lf (y) = T {x ∈ K | f (y, x) ≤ 0}. x∗ ∈ T y∈K

L˚y y = zλ, v(cid:237)i ∀λ ∈ [0, 1] ta lu«n cª f (zλ, x∗) ≤ 0. Do ﬁª, ∀λ ∈ [0, 1], ∀y ∈ K v(cid:181) tı (2.1) ta cª:

0 ≤ λf (zλ, y) ≤ f (λy + (1 − λ)x∗, y) = f (x∗ + λ(y − x∗), y).

Cho λ → 0, do t(cid:221)nh li“n t(cid:244)c cæa f n“n:

0 ≤ f (x∗, y), ∀y ∈ K.

(cid:3)

⇒ x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. Ta cª ﬁi(cid:210)u ph¶i chłng minh. Nh¸n x—t [2] ? M(cid:214)nh ﬁ(cid:210) ﬁ¶o cæa ﬁ(cid:222)nh l(cid:221) 2.1.1 kh«ng ﬁ(cid:243)ng. Th¸t v¸y, l˚y N = 1 v(cid:181) l˚y K = [0, 2] v(cid:181) k(cid:221) hi(cid:214)u S1 l(cid:181) t¸p nghi(cid:214)m cæa b(cid:181)i to‚n ﬁŁi ng(cid:201)u, S2 l(cid:181) t¸p nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. Khi ﬁª, a, f (x, y) = (x − y)2 ⇒ S1 = ∅, S2 = [0, 2] ⇒ S1 * S2. b, f (x, y) = max{0, | x − y | −1} ⇒ S1 = {1}, S2 = [0, 2] ⇒ S1 * S2. ? Khi f l(cid:181) gi¶ ﬁ‹n ﬁi(cid:214)u, ngh(cid:220)a l(cid:181) ∀x, y ∈ K : f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, m(cid:214)nh ﬁ(cid:210) ﬁ¶o cæa 2.1.1 ﬁ(cid:243)ng. Khi ﬁª, b(cid:181)i to‚n ﬁŁi ng(cid:201)u v(cid:181) b(cid:181)i to‚n c'n b»ng cª c(cid:239)ng t¸p nghi(cid:214)m.

Thu¸t to‚n chi(cid:213)u 2.1 [2] B›(cid:237)c 1: Cho k = 0, x0 ∈ K v(cid:181) r0 = k x0 k. B›(cid:237)c 2: L˚y xk v(cid:181) rk (i) §(cid:222)nh ngh(cid:220)a:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn19

Ta cª thu¸t to‚n chi(cid:213)u 2.1 sau ﬁ(cid:211) gi¶i b(cid:181)i to‚n ﬁŁi ng(cid:201)u.

(2.1a) Kk = {x ∈ K : k x k ≤ rk + 1}.

(ii) T(cid:215)m yk ∈ Kk cª t(cid:221)nh ch˚t:

(2.1b) f (y, xk) − (cid:15)k ≤ f (yk, xk), max y∈Kk

(cid:15)k = 0.

v(cid:237)i {(cid:15)k}k≥0 ⊂ [0, +∞] l(cid:181) d•y tho¶ m•n lim k→+∞ (iii) T(cid:221)nh xk+1 d„ng:

(2.1c) xk+1 = xk + tk (cid:2)PLf (yk)(xk) − xk(cid:3),

trong ﬁª, PLf (yk)(xk) l(cid:181) ph—p chi(cid:213)u trøc giao cæa xk l“n Lf (yk), v(cid:181) Lf (yk) = {x ∈ K | f (yk, x) ≤ 0} l(cid:181) t¸p l(cid:229)i, {tk}k≥0 ⊂ [α, 2 − α] v(cid:237)i α ∈ [0, 1]. (iv) T(cid:221)nh rk th«ng qua:

(2.1d) rk+1 = max{rk, k xk+1 k}

v(cid:181) trº v(cid:210) (i) cæa b›(cid:237)c 2.

Chłng minh • Chłng minh (2.1b) ﬁ(cid:243)ng. Th¸t v¸y, tı c«ng thłc (2.1a) v(cid:181) (2.1d) ta cª:

M(cid:214)nh ﬁ(cid:210) 2.1.1. [2] Thu¸t to‚n chi(cid:213)u 2.1 ﬁ›(cid:238)c x‚c ﬁ(cid:222)nh ﬁ(cid:243)ng ﬁ(cid:190)n.

Kk ⊂ Kk+1, ∀k ∈ N.

Do x0 ∈ K v(cid:181) k x0 k≤ r0 + 1 n“n suy ra x0 ∈ K0 ⇒ x0 ∈ Kk, ∀k ∈ N M˘t kh‚c, K l(cid:181) t¸p ﬁªng n“n m(cid:228)i Kk l(cid:181) kh‚c r(cid:231)ng v(cid:181) compact. L„i do t(cid:221)nh li“n t(cid:244)c cæa f n“n f (., yk) ﬁ„t cøc ﬁ„i tr“n Kk, v(cid:215) v¸y t(cid:229)n t„i yk ∈ Kk tho¶ m•n:

f (y, xk) − (cid:15)k ≤ f (yk, xk). max y∈Kk

• Chłng minh (2.1c) ﬁ(cid:243)ng. Th¸t v¸y, do t(cid:221)nh l(cid:229)i cæa f (yk, .) v(cid:181) t(cid:221)nh l(cid:229)i cæa t¸p K n“n t¸p kh‚c r(cid:231)ng:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn20

Lf (yk) = {x ∈ K | f (yk, x) ≤ 0}

l(cid:181) t¸p l(cid:229)i, ﬁªng. Do ﬁª,

xk+1 = xk + tk (cid:2)PLf (yk)(xk) − xk(cid:3)

ﬁ›(cid:238)c x‚c ﬁ(cid:222)nh duy nh˚t.

(cid:3) V¸y m(cid:214)nh ﬁ(cid:210) ﬁ›(cid:238)c chłng minh.

k=0

M(cid:214)nh ﬁ(cid:210) 2.1.2. [2] Gi¶ s(cid:246) r»ng: +∞ \ Lf (yk) 6= ∅, (2.3)

+∞ T k=0 b, D•y {xk}k≥0 b(cid:222) ch˘n. c,

th(cid:215): a, ∀x∗ ∈ Lf (yk) d•y {k xk − x∗ k}k≥0 kh«ng t¤ng v(cid:181) do ﬁª hØi t(cid:244).

Chłng minh a, Cho x∗ ∈

+∞ T k=0 xk+1 = xk + tk

k xk+1 − xk k= 0. lim k→+∞

do ﬁª: Lf (yk), tı c«ng thłc (2.1c) cæa thu¸t to‚n 2.1 ta cª (cid:2)PLf (yk)(xk) − xk(cid:3)

2 k PLf (yk)(xk) − xk k2

(2.4)

k xk+1 − x∗ k2 = k xk + tk[PLf (yk)(xk) − xk] − x∗ k2 = k xk − x∗ k2 + tk + 2 tk (cid:10)xk − x∗, PLf (yk)(xk) − xk(cid:11).

Ta l„i cª:

2 tk (cid:10)xk − x∗, PLf (yk)(xk) − xk(cid:11) =

(cid:10)xk − PLf (yk)(xk) + PLf (yk)(xk) − x∗, PLf (yk)(xk) − xk(cid:11)

= 2 tk = −2 tk k xk − PLf (yk)(xk) k2 +2 tk

(cid:10)PLf (yk)(xk) − x∗, PLf (yk)(xk) − xk(cid:11). (2.5)

Tı (2.4) v(cid:181) (2.5) ta cª:

2 k PLf (yk)(xk) − xk k2 −

k xk+1 − x∗ k2 = k xk − x∗ k2 + tk

(2.6)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn21

− 2 tk k xk − PLf (yk)(xk) k2 + + 2 tk (cid:10)PLf (yk)(xk) − x∗, PLf (yk)(xk) − xk(cid:11).

Do t(cid:221)nh ch˚t cæa ph—p chi(cid:213)u trøc giao v(cid:181) x∗ ∈ Lf (yk) n“n sŁ h„ng cuŁi c(cid:239)ng cæa (2.6) kh«ng d›‹ng, tłc l(cid:181):

2 tk (2.7) (cid:10)PLf (yk)(xk) − x∗, PLf (yk)(xk) − xk(cid:11) ≤ 0.

2 k PLf (yk)(xk) − xk k2 −

Tı (2.6), (2.7) v(cid:181) ∀k ∈ N ta suy ra: k xk+1 − x∗ k2 ≤ k xk − x∗ k2 + tk

(2.8)

− 2 tk k xk − PLf (yk)(xk) k2 = k xk − x∗ k2 −tk(2 − tk) k xk − PLf (yk)(xk) k2 ≤ k xk − x∗ k2 .

V¸y d•y {k xk − x∗ k}k≥0 kh«ng t¤ng v(cid:181) do ﬁª hØi t(cid:244). b, Theo k(cid:213)t qu¶ a, ta cª d•y {k xk − x∗ k}k≥0 hØi t(cid:244). M˘t kh‚c, k xk k= k xk − x∗ + x∗ k≤ k xk − x∗ k + k x∗ k. ⇒ {xk}k≥0 b(cid:222) ch˘n. c, Ta vi(cid:213)t l„i (2.8) d„ng:

tk(2 − tk) k xk − PLf (yk)(xk) k2≤ k xk − x∗ k2 − k xk+1 − x∗ k2 . (2.9)

V(cid:215) 0 < α ≤ tk ≤ 2 − α v(cid:237)i 0 < α < 1 ta cª 0 < α(2 − α) ≤ tk(2 − tk). Tı (2.9) ta suy ra:

(xk)} = 0. (2.11) α(2 − α) k xk − PLf (yk)(xk) k2≤ k xk − x∗ k2 − k xk+1 − x∗ k2 . (2.10) Tı (2.10), 0 < α(2 − α) v(cid:181) t(cid:221)nh hØi t(cid:244) cæa {k xk − x∗ k}k≥0 ta cª: {xk − PLf (yk) lim k→+∞

Do ﬁª,

= 0. xk+1 − xk tk

(cid:3) lim k→+∞ V(cid:215) 0 < α ≤ tk ≤ 2−α n“n (xk+1−xk) → 0 khi k → +∞.

M(cid:214)nh ﬁ(cid:210) 2.1.3. [3] Gi¶ s(cid:246): i, D•y {xk}k≥0 b(cid:222) ch˘n, ii, k xk+1 − xk k= 0. lim k→+∞

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn22

Khi ﬁª, d•y {xk}k≥0 hØi t(cid:244) t(cid:237)i nghi(cid:214)m x∗ cæa b(cid:181)i to‚n c'n b»ng.

Chłng minh • Do xk+1 = xk + tk Tı gi¶ thi(cid:213)t ii, ta suy ra:

(xk) − xk(cid:3) ⇒ xk+1 − xk (xk) − xk(cid:3) . (cid:2)PLf (yk) = (cid:2)PLf (yk) tk

(xk)} = 0. {xk − PLf (yk) lim k→+∞

• Chłng minh {yk}k≥0 b(cid:222) ch˘n? Theo gi¶ thi(cid:213)t ta cª d•y {xk}k≥0 b(cid:222) ch˘n, do v¸y ∃ r > 0 sao cho:

k xk k≤ r, ∀k ∈ N.

Tı c«ng thłc (2.1d) cæa thu¸t to‚n chi(cid:213)u 2.1: rk+1 = max{rk, k xk+1 k} ta cª:

rk = max{k x0 k, . . . , k xk k}.

Do ﬁª, rk ≤ r, ∀k ∈ N. L„i tı (2.1a) ta cª Kk = {x ∈ K : k x k≤ rk + 1} n“n Kk ⊂ B(0, r + 1). f (y, xk) − (cid:15)k ≤ f (yk, xk), yk ∈ Kk, ∀k ∈ N, do v¸y: Tı (2.1b) ta cª max y∈Kk

k yk k≤ r + 1.

Do ﬁª, {yk}k≥0 b(cid:222) ch˘n. • Gi¶ s(cid:246) x l(cid:181) ﬁi(cid:211)m gi(cid:237)i h„n cæa d•y {xk}k≥0 ⊂ K, v(cid:237)i K ﬁªng, x ∈ K. T(cid:229)n t„i d•y con {xkn}kn≥0 cæa d•y {xk}k≥0 tho¶ m•n:

xkn = x. lim kn→+∞

T›‹ng łng ta x—t d•y con {ykn}kn≥0 c(cid:242)ng b(cid:222) ch˘n. Do ﬁª, t(cid:229)n t„i d•y con {yknp }knp≥0 cæa d•y {ykn}kn≥0 hØi t(cid:244), gi¶ s(cid:246) hØi t(cid:244) t(cid:237)i y, tłc l(cid:181):

yknp = y. lim knp→+∞

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn23

(xk) = x. {xk −PLf (yk) PLf (yk) §(cid:211) cho ng(cid:190)n g(cid:228)n, ta k(cid:221) hi(cid:214)u yknp ≡ ykn, ta c(cid:242)ng l(cid:181)m t›‹ng tø v(cid:237)i xknp , ta k(cid:221) hi(cid:214)u xknp ≡ xkn. • Ta chłng minh f (y, x) = 0? Th¸t v¸y, tı tr“n cª lim k→+∞ (xk)} = 0 n“n lim k→+∞

kn→+∞

(xkn)(cid:1) Do t(cid:221)nh li“n t(cid:244)c cæa f n“n suy ra: f (y, x) = f (cid:0) lim kn→+∞ (2.12) PLf (ykn ) (xkn)(cid:1) ≤ 0. = lim ykn, lim kn→+∞ f (cid:0)ykn, PLf (ykn )

(xkn) ∈ Lf (ykn) = {x ∈ K | f (ykn, x) ≤ 0}.

Trong ﬁª, PLf (ykn ) Tı (2.1a), (2.1d) cª xk ∈ Kk, ∀k ∈ N. Tı ﬁ(cid:222)nh ngh(cid:220)a 2.1.1 v(cid:181) (2.1b), v(cid:237)i ∀k ∈ N ta cª:

f (y, xk) ≤ f (yk, xk) + (cid:15)k. (2.13) 0 = f (xk, xk) ≤ max y∈Kk

(cid:15)k = 0 v(cid:181) f li“n t(cid:244)c n“n tı (2.12) suy ra: Do lim k→+∞

kn→+∞

0 ≤ lim {f (ykn, xkn) + (cid:15)kn}

kn→+∞

= f ( lim ykn, xkn) + lim (2.14) (cid:15)kn lim kn→+∞

= f (y, x).

K(cid:213)t h(cid:238)p (2.12), (2.14) suy ra:

f (y, x) = 0. (2.15)

rk?

• V(cid:237)i m(cid:228)i 0 < δ < 1, x ∈ (cid:2)intB(0, r∗ + 1 − δ)(cid:3) ∩ K, v(cid:237)i r∗ = sup k∈N Do rk b(cid:222) ch˘n n“n r∗ = sup rk l(cid:181) h(cid:247)u h„n. k∈N V(cid:237)i 0 < δ < 1 x—t B(0, r∗ + 1 − δ) ≡ B(δ) Tı (2.1d) cª k xk k≤ rk ≤ r∗ < r∗+1−δ, ∀k ∈ N, n“n suy ra x ∈ intB(δ). V¸y x ∈ (cid:2)intB(0, r∗ + 1 − δ)(cid:3) ∩ K. • Cho bB(δ) = B(δ) ∩ K, x—t b(cid:181)i to‚n c'n b»ng ([EPδ) v(cid:237)i h(cid:181)m f v(cid:181) t¸p ch˚p nh¸n bB(δ):

T(cid:215)m bx ∈ ([EPδ) tho¶ m•n f (bx, y) ≥ 0, ∀y ∈ bB(δ)

([EPδ)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn24

Khi ﬁª ta cª kh…ng ﬁ(cid:222)nh sau: x ∈ bB(δ) l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n ([EPδ), v(cid:237)i 0 < δ < 1. Th¸t v¸y, l˚y d•y {rk}k∈N kh«ng gi¶m: rk ≤ rk+1. Ch(cid:228)n k0 ∈ N tho¶ m•n

rk0 ≥ r∗ − δ. Khi ﬁª:

r∗ + 1 − δ ≤ rk + 1, ∀k ≥ k0.

Do ﬁª,

bB(δ) ⊂ Kk, ∀k ≥ k0.

L˚y z ∈ bB(δ), ta cª z ∈ Kk, ∀k ≥ k0. V(cid:215) v¸y,

f (y, xk) ≤ f (yk, xk) + (cid:15)k, ∀k ≥ k0. (2.16) f (z, xk) ≤ max y∈Kk

Do t(cid:221)nh li“n t(cid:244)c cæa f , c«ng thłc (2.14), (2.15), (2.16) ta cª:

f (z, x) = f (z, xkn) lim kn→+∞

kn→+∞

f (z, xkn) = lim

(2.16) ≤ lim

(2.17)

kn→+∞

{f (ykn, xkn) + (cid:15)kn}

= f (y, x) = 0.

Tłc l(cid:181),

(2.18) f (z, x) ≤ 0, ∀z ∈ bB(δ).

Tı (2.18), do x ∈ K, v(cid:237)i m(cid:231)i 0 < δ < 1 ta cª:

x∈ bB(δ)

\ x ∈ Lf (z).

Theo ﬁ(cid:222)nh l(cid:221) 2.1.1 suy ra x l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (dEP δ) v(cid:237)i 0 < δ < 1. • x l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng 1.1? Cho x l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n ([EPδ), tłc l(cid:181) f (x, y) ≥ 0, ∀y ∈ bB(δ). Theo gi¶ thi(cid:213)t cª f (x, x) = 0. Tı c‚c ﬁi(cid:210)u tr“n ta kh…ng ﬁ(cid:222)nh x l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n tŁi ›u l(cid:229)i:

f (x, y). (2.19)

min y∈ bB(δ) H(cid:181)m g : Rn → R ∪ {+∞} cª d„ng:

f (x, y)   si y ∈ K, g(y) =

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn25

 +∞ si y 6∈ K.

V(cid:237)i h(cid:181)m g vıa ﬁ(cid:222)nh ngh(cid:220)a ta cª th(cid:211) vi(cid:213)t l„i (2.19) nh› sau:

g(y). min y∈B(δ)

Lf (z). Ta ﬁ• chłng minh ﬁ›(cid:238)c x l(cid:181) ﬁi(cid:211)m cøc ti(cid:211)u cæa g tr“n B(δ), thuØc ph˙n trong cæa B(δ). L„i do g l(cid:181) h(cid:181)m l(cid:229)i, n“n x l(cid:181) ﬁi(cid:211)m cøc ti(cid:211)u kh«ng r(cid:181)ng buØc cæa g. Tłc l(cid:181), g(x) ≤ g(y), ∀y ∈ Rn, trong ﬁª g(x) = f (x, x) = 0 ≤ g(y) = f (x, y), ∀y ∈ K. V¸y x l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng 1.1. xk = x ? •Ta chłng minh lim k→+∞ Ta ﬁ• chłng minh ﬁ›(cid:238)c x ∈ T z∈ bB(δ)

V(cid:215) th(cid:213) f (z, x) ≤ 0, ∀z ∈ K, k z k≤ r∗ + 1 − δ. Do δ ∈ [0, 1] ta cª f (z, x) ≤ 0, ∀z ∈ K, k z k≤ r∗ + 1. L„i do t(cid:221)nh li“n t(cid:244)c cæa h(cid:181)m f n“n f (z, x) ≤ 0, ∀z ∈ K, k z k≤ r∗ + 1. Do yk ∈ Kk, ∀k ∈ N n“n k yk k≤ rk+1 ≤ r∗+1 ⇒ f (yk, x) ≤ 0, ∀k ∈ N.

+∞ T k=0

⇒ x ∈ Lf (yk).

xk = x. Theo m(cid:214)nh ﬁ(cid:210) 2.1.2a, ta cª {k xk − x}k≥0 hØi t(cid:244). V(cid:215) th(cid:213) d•y con {k xkn −x}kn≥0 hØi t(cid:244) v(cid:210) 0, n“n {k xk −x}k≥0 hØi t(cid:244) v(cid:210) 0, tłc (cid:3) l(cid:181) lim k→+∞

§(cid:222)nh l(cid:221) sau ﬁ'y sˇ ch(cid:216) ra t(cid:221)nh ch˚t hØi t(cid:244) thu¸t to‚n chi(cid:213)u li“n ti(cid:213)p 2.1.

+∞ \

§(cid:222)nh l(cid:253) 2.1.2. [2] Cho {xk}k≥0 v(cid:181) {yk}k≥0 ⊂ K l(cid:181) d•y ﬁ›(cid:238)c t(cid:221)nh tı thu¸t to‚n 2.1. Khi ﬁª: a, N(cid:213)u

k=0

Lf (yk) 6= ∅, (2.20)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn26

th(cid:215) {xk}k≥0 hØi t(cid:244) ﬁ(cid:213)n nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. b, N(cid:213)u b(cid:181)i to‚n c'n b»ng v« nghi(cid:214)m th(cid:215) {xk}k≥0 kh«ng hØi t(cid:244).

Chłng minh

+∞ T k=0

a, Do Lf (yk) 6= ∅ v(cid:181) theo m(cid:214)nh ﬁ(cid:210) 2.1.2, 2.1.3 suy ra {xk}k≥0 hØi t(cid:244)

{xk+1 − xk} = 0.

ﬁ(cid:213)n nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. b, B»ng ph¶n chłng, gi¶ s(cid:246) {xk}k≥0 ⊂ Rn hØi t(cid:244) t(cid:237)i nghi(cid:214)m x∗ ∈ Rn. Do {xk}k≥0 hØi t(cid:244) n“n {xk}k≥0 b(cid:222) ch˘n v(cid:181) lim k→+∞ Ph˙n c(cid:223)n l„i cæa chłng minh ﬁ›(cid:238)c l¸p lu¸n nh› trong chłng minh m(cid:214)nh ﬁ(cid:210) 2.1.3. Do ﬁª, x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng 1.2.1. M'u thu(cid:201)n v(cid:237)i gi¶ (cid:3) thi(cid:213)t. V¸y b(cid:181)i to‚n c'n b»ng v« nghi(cid:214)m.

Chłng minh Do b(cid:181)i to‚n ﬁŁi ng(cid:201)u cª nghi(cid:214)m n“n T

H(cid:214) qu¶ 2.1.1. [2] N(cid:213)u b(cid:181)i to‚n ﬁŁi ng(cid:201)u cª nghi(cid:214)m th(cid:215) {xk}k≥0 hØi t(cid:244) t(cid:237)i nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

y∈K

+∞ T k=0

Lf (y) 6= ∅ n“n Lf (yk) 6= ∅,

y∈K

+∞ T k=0

Lf (y) ⊂ v(cid:215) T Lf (yk). Theo ﬁ(cid:222)nh l(cid:221) 2.1.2 suy ra ﬁi(cid:210)u ph¶i chłng minh.

H(cid:214) qu¶ 2.1.2. [2] Cho {xk}k≥0, {yk}k≥0 l(cid:181) c‚c d•y ﬁ›(cid:238)c t(cid:221)nh tı thu¸t to‚n 2.1. N(cid:213)u f l(cid:181) gi¶ ﬁ‹n ﬁi(cid:214)u v(cid:181) ho˘c {xk}k≥0 ho˘c {yk}k≥0 b(cid:222) ch˘n th(cid:215) {xk}k≥0 hØi t(cid:244) ﬁ(cid:213)n nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Chłng minh N(cid:213)u {xk}k≥0 b(cid:222) ch˘n th(cid:215) {yk}k≥0 c(cid:242)ng b(cid:222) ch˘n (theo chłng minh m(cid:214)nh ﬁ(cid:210) 2.1.3). Gi¶ s(cid:246) {yk}k≥0 b(cid:222) ch˘n v(cid:181) theo gi¶ thi(cid:213)t f l(cid:181) gi¶ ﬁ‹n ﬁi(cid:214)u n“n suy ra +∞ T (cid:3) k=0

Lf (yk) 6= ∅. Theo ﬁ(cid:222)nh l(cid:221) 2.1.2 suy ra ﬁi(cid:210)u ph¶i chłng minh.

2.2. Ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n c'n b»ng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn27

Ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng l˙n ﬁ˙u ti“n ﬁ›(cid:238)c Korpelevich ﬁ(cid:210) xu˚t ﬁ(cid:211) gi¶i b(cid:181)i to‚n t(cid:215)m ﬁi(cid:211)m y“n ngøa, sau ﬁª ﬁ›(cid:238)c ph‚t tri(cid:211)n cho b(cid:181)i to‚n b˚t

ﬁ…ng thłc bi(cid:213)n ph'n. Ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n c'n

b»ng l(cid:181) sø mº rØng cæa nguy“n l(cid:221) b(cid:181)i to‚n c'n b»ng ph(cid:244). Nh›ng º ph›‹ng

ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng cho ph—p gi¶i c‚c b(cid:181)i to‚n kh«ng c˙n gi¶ thi(cid:213)t ﬁ‹n ﬁi(cid:214)u m„nh cho h(cid:181)m f m(cid:181) ch(cid:216) y“u c˙u h(cid:181)m n(cid:181)y tho¶ m•n ﬁi(cid:210)u ki(cid:214)n Lipschitz. Tr›(cid:237)c ti“n ta ﬁ(cid:222)nh ngh(cid:220)a b(cid:181)i to‚n c'n b»ng ph(cid:244).

§(cid:222)nh ngh(cid:220)a 2.2.1. [2] Cho L : K × K → R v(cid:181) (cid:15) > 0, ta x—t b(cid:181)i to‚n c'n b»ng ph(cid:244) sau:

T(cid:215)m x∗ ∈ K sao cho : (cid:15)f (x∗, y) + L(x∗, y) ≥ 0, ∀y ∈ K (2.21)

M(cid:214)nh ﬁ(cid:210) 2.2.1. [2] Cho f : K × K → R v(cid:237)i f (x, x) = 0, ∀x ∈ K v(cid:181) cho x∗ ∈ K. Gi¶ s(cid:246) f (x∗, .) : K → R l(cid:181) h(cid:181)m l(cid:229)i kh¶ vi. Cho L : K × K → R l(cid:181) h(cid:181)m l(cid:229)i, kh¶ vi, kh«ng 'm tr“n t¸p l(cid:229)i K theo bi(cid:213)n thł hai y (∀x ∈ K) v(cid:181) tho¶ m•n:

a, L(x, x) = 0, ∀x ∈ K; b, ∇yL(x, x) = 0, ∀y ∈ K.

Chłng minh (⇒⇒⇒) Do x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng n“n f (x∗, y) ≥ 0 v(cid:237)i ∀y ∈ K. Ta cª (cid:15) > 0 ⇒ (cid:15)f (x∗, y) ≥ 0, ∀y ∈ K, ∀x∗ ∈ K. V(cid:215) L : K × K → R l(cid:181) h(cid:181)m l(cid:229)i, kh¶ vi, kh«ng 'm tr“n t¸p l(cid:229)i K tho¶ m•n:

Khi ﬁª, x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng khi v(cid:181) ch(cid:216) khi nª l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng ph(cid:244) (2.21).

a, L(x, x) = 0, ∀x ∈ K; b, ∇yL(x, x) = 0, ∀y ∈ K.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn28

n“n L(x∗, y) ≥ 0, ∀x∗, y ∈ K ⇒ (cid:15)f (x∗, y) + L(x∗, y) ≥ 0, ∀y ∈ K. V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng ph(cid:244). (⇐⇐⇐) Cho x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng ph(cid:244), ta sˇ chłng minh x∗ ∈ K c(cid:242)ng l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. Do x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng ph(cid:244) n“n nª c(cid:242)ng l(cid:181) nghi(cid:214)m

tŁi ›u cæa b(cid:181)i to‚n:

{(cid:15)f (x∗, y) + L(x∗, y)}. min y∈K

M˘t kh‚c, ta cª (cid:15)f (x∗, y) + L(x∗, y) ≥ 0, ∀y ∈ K,

⇒ (cid:15)f (x∗, x∗) + L(x∗, x∗) = 0.

{(cid:15)f (x∗, y) + L(x∗, y)}.

Ta cª x∗ ∈ K l(cid:181) nghi(cid:214)m tŁi ›u cæa b(cid:181)i to‚n min y∈K ⇔ (cid:10)(cid:15)∇yf (x∗, x∗) + ∇yL(x∗, x∗), y − x∗(cid:11) ≥ 0, ∀y ∈ K. Theo gi¶ thi(cid:213)t, ∇yL(x, x) = 0, ∀y ∈ K n“n (cid:10)(cid:15)∇yf (x∗, x∗), y − x∗(cid:11) ≥ 0, ∀y ∈ K. ⇔ (cid:15)(cid:10)∇yf (x∗, x∗), y − x∗(cid:11) ≥ 0, ∀y ∈ K. (cid:15)>0⇔ (cid:10)∇yf (x∗, x∗), y − x∗(cid:11) ≥ 0, ∀y ∈ K.

Do K l(cid:181) h(cid:181)m l(cid:229)i v(cid:181) theo t(cid:221)nh ch˚t l(cid:229)i kh¶ vi cæa f (x∗, .) : K → R n“n theo ﬁ(cid:222)nh ngh(cid:220)a ta cª:

f (x∗, y) ≥ f (x∗, x∗) + (cid:10)∇yf (x∗, x∗), y − x∗(cid:11), ∀y ∈ K.

⇒ f (x∗, y) ≥ f (x∗, x∗) = 0, ∀y ∈ K.

Ch(cid:243) (cid:253) N(cid:213)u G : K → R l(cid:181) h(cid:181)m l(cid:229)i m„nh, kh¶ vi v(cid:181)

V¸y x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng, m(cid:214)nh ﬁ(cid:210) ﬁ›(cid:238)c chłng minh.(cid:3)

L(x, y) = G(y) − G(x) − (cid:10)∇G(x), y − x(cid:11), ∀x, y ∈ K. (2.22)

th(cid:215) h(cid:181)m L tho¶ m•n c‚c t(cid:221)nh ch˚t cæa m(cid:214)nh ﬁ(cid:210) 2.2.1.

H(cid:214) qu¶ 2.2.1. [2] x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng khi v(cid:181) ch(cid:216) khi nª l(cid:181) nghi(cid:214)m tŁi ›u cæa b(cid:181)i to‚n tŁi ›u:

{(cid:15)f (x∗, y) + L(x∗, y)}. min y∈K

Nh¸n x—t ? x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng khi v(cid:181) ch(cid:216) khi nª l(cid:181) nghi(cid:214)m cæa

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn29

H(cid:214) qu¶ 2.2.2. [2] Cho f : K × K → R v(cid:237)i f (x, x) = 0, ∀x ∈ K. Gi¶ s(cid:246) f (x∗, .) : K → R l(cid:181) h(cid:181)m l(cid:229)i, kh¶ vi v(cid:181) (cid:15) > 0. Khi ﬁª, x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng khi v(cid:181) ch(cid:216) khi x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng ph(cid:244) (2.21) v(cid:181) h(cid:181)m L ﬁ›(cid:238)c ﬁ(cid:222)nh ngh(cid:220)a theo (2.22)..

Hay b(cid:181)i to‚n tŁi ›u: min y∈K min y∈K

{ξf (x∗, y) + G(y) − G(x∗) − (cid:10)∇G(x∗), y − x∗(cid:11)}. {ξf (x∗, y) + G(y) − (cid:10)∇G(x∗), y(cid:11)}. ? Do G l(cid:181) h(cid:181)m l(cid:229)i m„nh n“n nghi(cid:214)m cæa b(cid:181)i to‚n: {ξf (x∗, y) + G(y) − (cid:10)∇G(x∗), y(cid:11)}

min y∈K n(cid:213)u t(cid:229)n t„i l(cid:181) duy nh˚t.

Thu¸t to‚n 2.2 [2] B›(cid:237)c 0: L˚y x0 ∈ K, (cid:15) > 0 v(cid:181) k := 0; B›(cid:237)c 1: Gi¶i b(cid:181)i to‚n:

Trong to(cid:181)n ph˙n n(cid:181)y n(cid:213)u kh«ng nªi g(cid:215) th“m ta gi¶ s(cid:246) f (x, .) ﬁªng, l(cid:229)i v(cid:181) kh¶ d›(cid:237)i vi ph'n tr“n K, v(cid:237)i ∀x ∈ K. Sau ﬁ'y ta ﬁ›a ra thu¸t to‚n gi¶i b(cid:181)i to‚n c'n b»ng ph(cid:244).

{(cid:15)f (xk, y) + G(y) − (cid:10)OG(xk), y − xk(cid:11)}. (2.22a) min y∈K

cª nghi(cid:214)m tŁi ›u duy nh˚t yk. N(cid:213)u yk = xk th(cid:215) thu¸t to‚n dıng v(cid:181) k(cid:213)t lu¸n xk l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. Tr‚i l„i, ta chuy(cid:211)n sang b›(cid:237)c 2. B›(cid:237)c 2: Gi¶i b(cid:181)i to‚n:

{(cid:15)f (yk, y) + G(y) − (cid:10)OG(xk), y − xk(cid:11)}. (2.22b) min y∈K

t(cid:215)m nghi(cid:214)m duy nh˚t xk+1. B›(cid:237)c 3: L˚y k := k + 1 v(cid:181) quay l„i b›(cid:237)c 1.

B(cid:230) ﬁ(cid:210) d›(cid:237)i ﬁ'y ch(cid:216) ra r»ng n(cid:213)u thu¸t to‚n 2.2 k(cid:213)t th(cid:243)c t„i b›(cid:237)c l˘p k n(cid:181)o ﬁª th(cid:215) ta t(cid:215)m ﬁ›(cid:238)c nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn30

B(cid:230) ﬁ(cid:210) 2.2.1. [6] N(cid:213)u thu¸t to‚n k(cid:213)t th(cid:243)c t„i ﬁi(cid:211)m l˘p xk th(cid:215) xk l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Chłng minh N(cid:213)u xk = yk th(cid:215) do f (x, x) = 0 n“n ta cª:

(cid:15)f (xk, yk) + G(yk) − G(xk) − (cid:10)OG(xk), yk − xk(cid:11)} = 0.

Do yk = xk l(cid:181) nghi(cid:214)m cæa (2.22a), ta cª:

0 = (cid:15)f (xk, yk) + G(yk) − G(xk) − (cid:10)OG(xk), yk − xk(cid:11)}

≤ (cid:15)f (xk, y) + G(y) − G(xk) − (cid:10)OG(xk), y − xk(cid:11)}, ∀y ∈ K.

(cid:3) Tı m(cid:214)nh ﬁ(cid:210) 2.2.1 suy ra xk l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Ta k(cid:221) hi(cid:214)u K ∗ l(cid:181) t¸p nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng v(cid:181) K d l(cid:181) t¸p nghi(cid:214)m cæa b(cid:181)i to‚n ﬁŁi ng(cid:201)u (2.1). §(cid:222)nh l(cid:221) sau ch(cid:216) ra t(cid:221)nh hØi t(cid:244) cæa thu¸t to‚n.

§(cid:222)nh l(cid:253) 2.2.1. [6] Gi¶ s(cid:246) r»ng:

i, G l(cid:229)i m„nh v(cid:237)i h(cid:214) sŁ β > 0 v(cid:181) kh¶ vi li“n t(cid:244)c tr“n t¸p mº Ω ⊇ K. ii, T(cid:229)n t„i h»ng sŁ c1 v(cid:181) c2 > 0 tho¶ m•n:

f (x, y) + f (y, x) ≥ f (x, z) − c1 k y − x k2 −c2 k z − y k2 ∀x, y, z ∈ K. (2.23)

−(cid:15)c1 −(cid:15)c2 (cid:1) k xk+1−yk k2 (2.24) Khi ﬁª: a, V(cid:237)i m(cid:228)i x∗ ∈ K d, th(cid:215) l(xk)−l(xk+1) ≥ (cid:0)β 2 (cid:1) k yk −xk k2 +(cid:0)β 2

, β 2c2

Chłng minh a, L˚y x∗ ∈ K d b˚t k(cid:215). Theo ﬁ(cid:222)nh ngh(cid:220)a cæa h(cid:181)m l v(cid:181) cho xk, xk+1 ∈ K,

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn31

v(cid:237)i l(y) := G(x∗) − G(y) − (cid:10)∇G(y), x∗ − y(cid:11), ∀y ∈ K. b, Gi¶ s(cid:246) f l(cid:181) n(cid:246)a li“n t(cid:244)c d›(cid:237)i tr“n K × K, f (., y) l(cid:181) n(cid:246)a li“n t(cid:244)c tr“n tr“n K v(cid:181) 0 < (cid:15) < min (cid:8) β (cid:9), th(cid:215) d•y {xk} b(cid:222) ch˘n v(cid:181) m(cid:228)i ﬁi(cid:211)m t(cid:244) 2c1 cæa nª l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. H‹n th(cid:213), n(cid:213)u K d = K ∗ (trong tr›Œng h(cid:238)p n(cid:181)y f l(cid:181) gi¶ ﬁ‹n ﬁi(cid:214)u tr“n K) th(cid:215) {xk} hØi t(cid:244) t(cid:237)i nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

ta cª: l(xk) − l(xk+1) = G(xk+1) − G(xk) + (cid:10)∇G(xk+1), x∗ − xk+1(cid:11)

− (cid:10)∇G(xk), x∗ − xk(cid:11) = G(xk+1) − G(xk) + (cid:10)∇G(xk+1) − ∇G(xk), x∗ − xk+1(cid:11) − (cid:10)∇G(xk), xk+1 − xk(cid:11).

(2.25)

Ta cª xk+1 l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n:

{(cid:15)f (yk, y) + G(y) − G(xk) − (cid:10)∇G(xk), y − xk(cid:11)}, min y∈K

n(cid:213)u v(cid:181) ch(cid:216) n(cid:213)u

(cid:8)(cid:15)f (yk, xk+1)+G(xk+1)−G(xk)−(cid:10)∇G(xk), xk+1−xk(cid:11)(cid:9)+NK(xk+1). 0 ∈ ∂2

v(cid:237)i NK(x) l(cid:181) nªn ph‚p tuy(cid:213)n cæa K t„i x ∈ K. Do f (yk, .) l(cid:181) kh¶ d›(cid:237)i vi ph'n v(cid:181) G l(cid:181) l(cid:229)i m„nh, kh¶ vi tr“n K n“n theo ﬁ(cid:222)nh l(cid:221) Moreau-Rockafella ∃w ∈ ∂2f (yk, xk+1) tho¶ m•n:

(cid:10)∇G(xk+1) − ∇G(xk), y − xk+1(cid:11) ≥ (cid:15)(cid:10)w, xk+1 − y(cid:11), y ∈ K.

M˘t kh‚c ta cª: (cid:10)∇G(xk+1) − ∇G(xk), y − xk+1(cid:11) ≥ (cid:15)f (yk, xk+1) − (cid:15)f (yk, y), ∀y ∈ K.

N(cid:213)u x∗ = y th(cid:215) b˚t ﬁ…ng thłc tr“n cª d„ng:

(cid:10)∇G(xk+1) − ∇G(xk), x∗ − xk+1(cid:11) ≥ (cid:15)f (yk, xk+1) − (cid:15)f (yk, x∗).

Do x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n (2.1) n“n f (yk, x∗) ≤ 0. V(cid:215) v¸y

(cid:10)∇G(xk+1) − ∇G(xk), x∗ − xk+1(cid:11) ≥ (cid:15)f (yk, xk+1). (2.26)

Tı (2.23) v(cid:237)i x = xk, y = yk v(cid:181) z = xk+1, khi ﬁª (2.26) ﬁ›(cid:238)c vi(cid:213)t: (cid:10)∇G(xk+1) − ∇G(xk), x∗ − xk+1(cid:11) ≥ (cid:15)f (xk, xk+1) − (cid:15)f (xk, yk)

− (cid:15) c1 k yk − xk k2 − (cid:15) c2 k xk+1 − yk k2 .

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn32

(2.27)

Tı b›(cid:237)c 1 cæa thu¸t to‚n 2.2 ta cª yk l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n:

{(cid:15)f (xk, y) + G(y) − G(xk) − (cid:10)∇G(xk), y − xk(cid:11)}, min y∈K

n“n cª

0 ∈ ∂2 (cid:8)(cid:15)f (xk, yk) + G(yk) − G(xk) − (cid:10)∇G(xk), yk − xk(cid:11)(cid:9) + NK(yk).

T›‹ng tø ta th˚y r»ng

(cid:15)f (xk, y) − (cid:15)f (xk, yk) ≥ (cid:10)∇G(yk) − ∇G(xk), yk − y(cid:11), y ∈ K.

V(cid:237)i y = xk+1 ta cª:

(cid:15)f (xk, xk+1) − (cid:15)f (xk, yk) ≥ (cid:10)∇G(yk) − ∇G(xk), yk − xk+1(cid:11). (2.28)

Tı (2.25), (2.27), (2.28) ta suy ra

l(xk) − l(xk+1) ≥ G(xk+1) − G(xk) − (cid:10)∇G(xk), xk+1 − xk(cid:11)

(2.29)

+ (cid:10)∇G(yk) − ∇G(xk), yk − xk+1(cid:11) − (cid:15) c1 k yk − xk k2 −(cid:15) c2 k xk+1 − yk k2 = G(xk+1) − G(xk) − (cid:10)∇G(xk), yk − xk(cid:11) + (cid:10)∇G(yk), yk − xk+1(cid:11) − (cid:15) c1 k yk − xk k2 −(cid:15) c2 k xk+1 − yk k2 = (cid:2)G(xk+1) − G(yk) − (cid:10)∇G(yk), xk+1 − yk(cid:11)(cid:3) + (cid:2)G(yk) − G(xk) − (cid:10)∇G(xk), yk − xk(cid:11)(cid:3) − (cid:15) c1 k yk − xk k2 −(cid:15) c2 k xk+1 − yk k2 .

V(cid:215) G l(cid:229)i m„nh v(cid:237)i h(cid:214) sŁ β n“n v(cid:237)i m(cid:228)i x, y ta cª:

G(y) − G(x) − (cid:10)∇G(x), y − x(cid:11) ≥ k y − x k2, ∀x, y ∈ K. (2.30) β 2

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn33

− (cid:15) c1 − (cid:15) c2 Tı (2.29), (2.30) v(cid:181) ∀k ≥ 0 ta cª: l(xk) − l(xk+1) ≥ (cid:0)β 2 (cid:1) k yk − xk k2 +(cid:0)β 2 (cid:1) k xk+1 − yk k2 . (2.31)

, (cid:9), ta cª: Ta cª ﬁi(cid:210)u ph¶i chłng minh. b, Tı gi¶ thi(cid:213)t 0 < (cid:15) < min (cid:8) β 2c1 β 2c2

− (cid:15) c1 > 0, − (cid:15) c2 > 0. β 2 β 2

V(cid:215) v¸y tı b˚t ﬁ…ng thłc (2.31) ta cª kh…ng ﬁ(cid:222)nh sau:

(cid:1) k yk − xk k2≥ 0, ∀k. − (cid:15) c1 (2.32) l(xk) − l(xk+1) ≥ (cid:0)β 2

m X

Do ﬁª, d•y {l(xk)k≥0} l(cid:181) d•y kh«ng t¤ng. Nª b(cid:222) ch˘n d›(cid:237)i bºi 0 n“n nª hØi t(cid:244) ﬁ(cid:213)n l∗.Trong (2.32) cho k ch„y tı 0 ﬁ(cid:213)n m v(cid:181) cØng l„i ta cª:

k=0

k yk − xk k2≤ l(x0) − l(xk+1), ∀m ≥ 0. (β − (cid:15)c1)

∞ X

D•y {l(xk)}k≥0 hØi t(cid:244), cho m → ∞ tı b˚t ﬁ…ng thłc cuŁi cª:

k=0

k yk − xk k2< ∞.

Tı ﬁª k—o theo:

k yk − xk k= 0. (2.33) lim k→+∞

Do G l(cid:181) β−l(cid:229)i m„nh v(cid:181) tı ﬁ(cid:222)nh ngh(cid:220)a cæa l(xk) ta cª th(cid:211) vi(cid:213)t:

0 ≤ k x∗ − xk k2≤ l(xk), ∀k β 2

V¸y {l(xk)} hØi t(cid:244) v(cid:181) d•y {xk}k≥0 b(cid:222) ch˘n n“n nª cª (cid:221)t nh˚t mØt ﬁi(cid:211)m t(cid:244). G(cid:228)i x ∈ K l(cid:181) ﬁi(cid:211)m t(cid:244) v(cid:181) {xki}i≥0 l(cid:181) d•y con cæa {xk} n“n cª:

xki = x. lim i→+∞

Tı (2.33) ta cª

yki = x. lim i→+∞

Quay l„i b›(cid:237)c 1 cæa thu¸t to‚n 2.2, ta cª:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn34

(cid:15)f (xki, y) + G(y) − G(xki) − (cid:10)∇G(xki), y − xki(cid:11) ≥ (cid:15)f (xki, yki) + G(yki) − G(xki) − (cid:10)∇G(xki), yki − xki(cid:11), ∀y ∈ K.

V(cid:215) f l(cid:181) n(cid:246)a li“n t(cid:244)c d›(cid:237)i tr“n K × K, f (., y) l(cid:181) n(cid:246)a li“n t(cid:244)c tr“n tr“n K v(cid:181) f (x, x) = 0, cho i → +∞ ta cª;

(cid:15)f (x, y) + G(y) − G(x) − (cid:10)∇G(x), y − x(cid:11) ≥ 0, ∀y ∈ K, v(cid:237)i x l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n 2.22 v(cid:181) L(x, y) = G(y)−G(x)(cid:10)∇G(x), y −x(cid:11) Theo m(cid:214)nh ﬁ(cid:210) 2.2.1 th(cid:215) x l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. Gi¶ s(cid:246) r»ng K d = K ∗, ta kh…ng ﬁ(cid:222)nh d•y {xk}k≥0 hØi t(cid:244) ﬁ(cid:213)n x. Th¸t v¸y, theo ﬁ(cid:222)nh ngh(cid:220)a cæa l(xk) v(cid:237)i x∗ = x ∈ K d, cª l(x) = 0. V(cid:215) v¸y, do G l(cid:181) β− l(cid:229)i m„nh n“n ta cª th(cid:211) vi(cid:213)t:

l(xk)−l(x) = G(x)−G(xk)−(cid:10)∇G(xk), xk −x(cid:11) ≥ k xk −x k2, ∀k ≥ 0. β 2

Ch(cid:243) (cid:253) §i(cid:210)u ki(cid:214)n (2.23) kh«ng ﬁæ ﬁ(cid:211) suy ra f l(cid:181) li“n t(cid:244)c. Trong thøc t(cid:213), n(cid:213)u f (x, y) = ϕ(y) − ϕ(x) th(cid:215) r(cid:226) r(cid:181)ng (2.21) lu«n ﬁ(cid:243)ng v(cid:237)i ∀c1 ≥ 0, c2 ≥ 0 v(cid:181) h(cid:181)m ϕ tuœ (cid:253).

xk = x ∈ K ∗. (2.34) M˘t kh‚c, do {l(xk)}k≥0 kh«ng t¤ng v(cid:181) l(xki) → l(x), ta cª l(xk) → l(x) (cid:3) khi k → +∞. V(cid:215) v¸y, tı (2.34) suy ra lim k→+∞

Cho K l(cid:181) t¸p l(cid:229)i ﬁa di(cid:214)n d„ng:

K := {x ∈ Rn : Ax ≤ b}. (2.35)

v(cid:181) h(cid:181)m f : K × K → R ∪ {+∞} cª d„ng:

f (x, y) := (cid:10)F (x) + Qy + q, y − x(cid:11), (2.36)

v(cid:237)i F : K → Rn, Q ∈ Rn×n l(cid:181) ma tr¸n ﬁŁi xłng x‚c ﬁ(cid:222)nh d›‹ng v(cid:181) q ∈ Rn. Do Q l(cid:181) ﬁŁi xłng n(cid:246)a x‚c ﬁ(cid:222)nh d›‹ng, f (x, .) l(cid:181) l(cid:229)i v(cid:237)i m(cid:228)i x ∈ K. Ta sˇ minh ho„ thu¸t to‚n 2.2 cho l(cid:237)p b(cid:181)i to‚n c'n b»ng n(cid:181)y. Tr›(cid:237)c ti“n ta cª mØt sŁ k(cid:213)t qu¶ sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn35

B(cid:230) ﬁ(cid:210) 2.2.2. [5] N(cid:213)u f : K → Rn l(cid:181) τ −ﬁ‹n ﬁi(cid:214)u m„nh tr“n K. Khi ﬁª: a, f ﬁ‹n ﬁi(cid:214)u tr“n K khi τ =k Q k. b, f l(cid:181) (τ − k Q k)−ﬁ‹n ﬁi(cid:214)u m„nh tr“n K khi τ >k Q k.

Chłng minh Tı ﬁ(cid:222)nh ngh(cid:220)a cæa h(cid:181)m f ta cª:

f (x, y) + f (y, x) = (cid:10)Q(y − x), y − x(cid:11) − (cid:10)F (y) − F (x), y − x(cid:11). (2.37)

M˘t kh‚c,

(cid:10)Q(y − x), y − x(cid:11) ≤k Q kk y − x k2 . (2.38)

Do F l(cid:181) τ −ﬁ‹n ﬁi(cid:214)u m„nh tr“n K, tłc l(cid:181)

(cid:10)F (y) − F (x), y − x(cid:11) ≥ τ k y − x k2,

Tı (2.37), (2.38) suy ra f (x, y) + f (y, x) ≤ 0, khi τ =k Q k. V¸y f ﬁ‹n ﬁi(cid:214)u tr“n K khi τ =k Q k. Khi τ >k Q k tı (2.37), (2.38) ta suy ra

f (x, y)+f (y, x) ≤k Q kk y−x k2 −τ k y−x k2= −(τ − k Q k) k y−x k2 .

(cid:3) V¸y f l(cid:181) (τ − k Q k)− ﬁ‹n ﬁi(cid:214)u m„nh tr“n K khi τ >k Q k.

B(cid:230) ﬁ(cid:210) 2.2.3. [5] N(cid:213)u F l(cid:181) li“n t(cid:244)c L−Lipschitz tr“n K, tłc l(cid:181)

k F (y) − F (x) k≤ L k y − x k ∀x, y ∈ K,

th(cid:215) f tho¶ m•n ti“u chu¨n ki(cid:211)u Lipschitz (2.23), tłc l(cid:181) ta cª:

f (x, y) + f (y, z) ≥ f (x, z) − c1 k y − x k2 −c2 k z − y k2 ∀x, y, z ∈ K,

Chłng minh V(cid:237)i m(cid:228)i x, y, z ∈ K ta cª: f (x, y) + f (y, z) − f (x, z) = (cid:10)F (y) − F (x), z = y(cid:11) + (cid:10)Q(y − z), y − x(cid:11),

v(cid:237)i c1 > 0, c2 > 0 tho¶ m•n: √ 2 c1c2 ≥ L+ k Q k .

Theo b˚t ﬁ…ng thłc Cauchy-Schwartz, ta cª:

(cid:10)Q(y − z), y − x(cid:11) ≥ − k Q kk z − y kk y − x k .

v(cid:181)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn36

(cid:10)F (y) − F (x), z − y(cid:11) ≥ − k F (y) − F (x) kk z − y k .

Do F l(cid:181) L− Lipschitzs, ta cª th(cid:211) vi(cid:213)t:

− k F (y) − F (x) kk z − y k≥ −L k y − x kk z − y | .

Do v¸y ta suy ra

f (x, y) + f (y, z) − f (x, z) ≥ −(L+ k Q k) k y − x kk z − y k .

V(cid:215) v¸y, theo gi¶ thi(cid:213)t cª:

−(L+ k Q k) k y − x kk z − y k≥ −c1 k y − x k2 −c2 k z − y k2 .

Suy ra

(cid:3) f (x, y) + f (y, z) ≥ f (x, z) − c1 k y − x k2 −c2 k z − y k2 .

• Tr›Œng h(cid:238)p ﬁ˘c bi(cid:214)t, khi F l(cid:181) ﬁ‹n ‚nh v(cid:181) F (x) = P x, P ∈ Rn×n, th(cid:215) h(cid:181)m f ﬁ›(cid:238)c ﬁ(cid:222)nh ngh(cid:220)a bºi (2.36) d„ng

f (x, y) = (cid:10)P x + Qy + q, y − x(cid:11), (2.39)

Ta gi¶ s(cid:246) r»ng ma tr¸n P, Q ﬁ›(cid:238)c ch(cid:228)n tho¶ m•n Q l(cid:181) ﬁŁi xłng x‚c ﬁ(cid:222)nh d›‹ng v(cid:181) Q − P l(cid:181) n(cid:246)a x‚c ﬁ(cid:222)nh 'm. Khi ﬁª, f tho¶ m•n mØt sŁ t(cid:221)nh ch˚t sau ﬁ'y:

i, f ﬁ‹n ﬁi(cid:214)u, f (., y) li“n t(cid:244)c v(cid:181) f (x, .) kh¶ vi tr“n t¸p l(cid:229)i K. ii, V(cid:237)i m(cid:228)i x, y, z ∈ K ta cª:

f (x, y) + f (y, z) ≥ f (x, z) − c1 k z − y k2 −c2 k y − x k2, (2.40)

v(cid:237)i c1 = c2 = 1 Th¸t v¸y, v(cid:237)i m(cid:228)i x, y, z ∈ K, do Q − P l(cid:181) n(cid:246)a x‚c ﬁ(cid:222)nh 'm n“n ta cª: f (x, y) + f (y, x) = (cid:10)(Q − P )(y − x), y − x(cid:11) ≤ 0.

2 k P − Q k .

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn37

Do ﬁª, f l(cid:181) ﬁ‹n ﬁi(cid:214)u tr“n K. R(cid:226) r(cid:181)ng, f (x, .) kh¶ vi, do Q ﬁŁi xłng n(cid:246)a x‚c ﬁ(cid:222)nh d›‹ng n“n f (x, .) l(cid:229)i v(cid:237)i m(cid:228)i x.

Tı ii, ta th˚y r»ng, v(cid:237)i m(cid:228)i x, y, z ∈ K cª:

f (x, y) + f (y, z) − f (x, z) = = (cid:10)P x + Qy + q, y − x(cid:11) + (cid:10)P y + Qz + q, z − y(cid:11) − (cid:10)P x + Qz + q, z − x(cid:11) = (cid:10)P x + Qy, y − x(cid:11) + (cid:10)P y + Qz, z − y(cid:11) − (cid:10)P x + Qz, z − x(cid:11) + (cid:10)q, y − x + z − y − (z − x)(cid:11) = (cid:10)P x + Qy, y − x(cid:11) + (cid:10)P y + Qz, z − y(cid:11) − (cid:10)P x + Qz, z − x(cid:11) = (cid:10)P x, y − x − (z − x)(cid:11) + (cid:10)Qz, z − y − (z − x)(cid:11) + (cid:10)Qy, y − x(cid:11)+ + (cid:10)P y, z − y(cid:11) = (cid:10)P x, y − z(cid:11) + (cid:10)Qz, x − y(cid:11) + (cid:10)Qy, y − x(cid:11) + (cid:10)P y, z − y(cid:11) = (cid:10)P (y − x), z − y(cid:11) + (cid:10)Q(z − y), x − y(cid:11) = (cid:10)P (y − x), z − y(cid:11) + (cid:10)QT (x − y), z − y(cid:11) = (cid:10)P (y − x), z − y(cid:11) + (cid:10)Q(x − y), z − y(cid:11) do Q = QT = (cid:10)(P − Q)(y − x), z − y(cid:11) . Tı ﬁª suy ra: f (x, y) + f (y, z) − f (x, z) = (cid:10)(P − Q)(y − x), z − y(cid:11)

k y − x kk z − y k ≥ −2

≥ − k y − x k2 − k z − y k2 k P − Q k 2 k P − Q k 2 k P − Q k 2

Theo c‚ch ﬁ˘t, c1 = c2 = 1 2 k P − Q k, ta suy ra (2.40).

V(cid:221) d(cid:244) 2.2.1. [5] ‚p d(cid:244)ng thu¸t to‚n 2.2 v(cid:237)i h(cid:181)m ch(cid:221)nh quy ho‚ b¸c hai G(x) := 1 2 k x k2 ﬁ(cid:211) gi¶i b(cid:181)i to‚n c'n b»ng. Trong ﬁª, f (x, y) := (cid:10)P x − Qy + q, y − x(cid:11) v(cid:181) K := {x ∈ Rn : Ax ≤ b}.

Trong tr›Œng h(cid:238)p n(cid:181)y, theo thu¸t to‚n t„i b›(cid:237)c 1 ta cª b(cid:181)i to‚n con:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn38

{(cid:15)f (x, y) + k y − x k2}. min y∈K 1 2

Theo (2.39) f (x, .) l(cid:181) h(cid:181)m l(cid:229)i to(cid:181)n ph›‹ng, n“n b(cid:181)i to‚n con cª th(cid:211) gi¶i tr“n MATLAB Optimization Toolbox. V(cid:237)i n = 5 v(cid:181) ma tr¸n P, Q cª d„ng:

  3.1 2 0 0 1.6 1 0 0

2 3.6 0 0 1 1.6 0 0

; P = Q = 0 0 3.5 2 0 0 1.5 1

0 0 2 3.3 0 0 0 1 1.5 0              

0 0 0 0  0  0   0     3 0 0 0 0  0  0   0     2

V(cid:237)i q = (1, −2, −1, 2, −1)T ,

5 X

i=1

(cid:26) K = x ∈ R5 : (cid:27) , xi ≥ −1, −5 ≤ xi ≤ 5, i = 1, . . . , 5

2 k Q − P k= 1.4525, (cid:15) = 1 2c1 = 0.7262, x0 = (1, 3, 1, 1, 2)T

c1 = c2 = 1 v(cid:181) ζ = 10−3 ta cª:

k xk 1 xk 2 xk 5 xk 4

0 xk 3 1.00000 3.00000 1.00000 1.00000 2.00000

1 -0.34415 1.59236 0.68742 -0.15427 0.63458

2 3 -0.67195 1.10393 0.65016 -0.57872 0.30562 -0.73775 0.92351 0.66742 -0.74459 0.22567

4 -0.74236 0.85342 0.68785 -0.81261 0.20624

5 -0.73668 0.82486 0.70195 -0.84184 0.20152

6 -0.73168 0.81276 0.71030 -0.85493 0.20037

7 -0.72864 0.80747 0.71491 -0.86100 0.20009

8 -0.72700 0.80511 0.71737 -0.86389 0.20002

-0.72617 0.80403 0.71865 -0.86529 0.20001 9 10 -0.72576 0.80354 0.71931 -0.86598 0.20000

Nghi(cid:214)m x˚p x(cid:216) sau 10 b›(cid:237)c l˘p l(cid:181):

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn39

x10 = (−0.72576, 0.80354, 0.71931, −0.86598, 0.20000)T .

N(cid:213)u ch(cid:228)n   3.1 2.0 0.0 0.0 0.0

2.0 3.6 0.0 0.0 0.0

P = 0.0 0.0 3.5 2.0 0.0

0.0 0.0 2.0 3.3 0.0              

0.0 0.0 0.0 0.0 2.0

Khi ﬁª gi‚ tr(cid:222) ri“ng cæa ma tr¸n Q − P l(cid:181):

{−0.7192, −2.7808, 2.9050, −0.8950, 0.0000}

Theo i, cæa b(cid:230) ﬁ(cid:210) 2.2.2 cª f ﬁ‹n ﬁi(cid:214)u. Trong tr›Œng h(cid:238)p n(cid:181)y, m‚y t(cid:221)nh t(cid:221)nh ﬁ›(cid:238)c:

k xk 1 xk 2 xk 5 xk 4

0 xk 3 1.00000 3.00000 1.00000 1.00000 2.00000

1 -0.34006 1.59892 0.69395 -0.14884 0.69814

2 -0.67118 1.10637 0.65254 -0.57720 0.36476

3 4 -0.73773 0.92446 0.66833 -0.74422 0.27939 -0.74245 0.85380 0.68821 -0.81255 0.25753

5 -0.73676 0.82503 0.70210 -0.84185 0.25193

6 -0.73172 0.81283 0.71037 -0.85495 0.25049

7 8 -0.72866 0.80751 0.71494 -0.86102 0.25013 -0.72701 0.80512 0.71738 -0.86390 0.25003

9 -0.72618 0.80404 0.71866 -0.86530 0.25001

10 -0.72577 0.80354 0.71932 -0.86599 0.25000

v(cid:181) t(cid:221)nh ﬁ›(cid:238)c nghi(cid:214)m x˚p x(cid:216) l(cid:181)

x10 = {−0.72577, 0.80354, 0.71932, −0.86599, 0.25000}T

K(cid:213)t lu¸n ch›‹ng

v(cid:237)i ζ = 10−3.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn40

Ch›‹ng n(cid:181)y gi(cid:237)i thi(cid:214)u v(cid:210) ph›‹ng ph‚p chi(cid:213)u v(cid:181) ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng

c›Œng gi¶i b(cid:181)i to‚n c'n b»ng. §(cid:229)ng thŒi, ta x—t mØt v(cid:221) d(cid:244) minh ho„ vi(cid:214)c

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn41

łng d(cid:244)ng ph›‹ng ph‚p ﬁ„o h(cid:181)m t¤ng c›Œng v(cid:181)o gi¶i b(cid:181)i to‚n c'n b»ng.

Ch›‹ng 3

Ph›‹ng ph‚p h(cid:181)m ﬁ‚nh gi‚

MØt ph›‹ng ph‚p hi(cid:214)u ch(cid:216)nh c‹ b¶n ﬁ(cid:211) gi¶i b(cid:181)i to‚n c'n b»ng l(cid:181) ph›‹ng

ph‚p h(cid:181)m ﬁ‚nh gi‚. Tłc l(cid:181), ta quy vi(cid:214)c gi¶i b(cid:181)i to‚n c'n b»ng v(cid:210) vi(cid:214)c gi¶i

b(cid:181)i to‚n cøc tr(cid:222). C‚ch ti(cid:213)p c¸n theo h(cid:181)m ﬁ‚nh gi‚ ﬁ›(cid:238)c nghi“n cłu v(cid:181) ‚p

d(cid:244)ng rØng r•i ﬁ(cid:211) gi¶i b(cid:181)i to‚n c'n b»ng. Ch›‹ng n(cid:181)y tr(cid:215)nh b(cid:181)y c‹ sº l(cid:221)

thuy(cid:213)t v(cid:181) thu¸t to‚n hi(cid:214)u ch(cid:216)nh b(cid:181)i to‚n c'n b»ng theo ph›‹ng ph‚p h(cid:181)m

ﬁ‚nh gi‚ cæa Auslender v(cid:181) Fukushima. NØi dung chæ y(cid:213)u cæa ch›‹ng ﬁ›(cid:238)c tham kh¶o trong [2], [9].

Ch(cid:243)ng ta v(cid:201)n x—t b(cid:181)i to‚n c'n b»ng:

(1.1) T(cid:215)m x∗ ∈ K sao cho f (x∗, y) ≥ 0, ∀y ∈ K,

trong ﬁª, f : K × K → R l(cid:181) mØt h(cid:181)m tho¶ m•n f (x, x) = 0, ∀x ∈ K.

Nh› ta ﬁ• bi(cid:213)t (ch›‹ng 1), b(cid:181)i to‚n c'n b»ng (1.1) t›‹ng ﬁ›‹ng v(cid:237)i nhi(cid:210)u b(cid:181)i to‚n quan tr(cid:228)ng kh‚c nh›: b(cid:181)i to‚n tŁi ›u, b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n

ph'n, b(cid:181)i to‚n b(cid:239),... B(cid:230) ﬁ(cid:210) sau ﬁ'y cho ta d„ng minimax cæa b(cid:181)i to‚n c'n b»ng (1.1).

B(cid:230) ﬁ(cid:210) 3.0.4. [2] Cho f : K × K → R v(cid:237)i f (x, x) = 0, ∀x ∈ K. Khi ﬁª, c‚c m(cid:214)nh ﬁ(cid:210) sau l(cid:181) t›‹ng ﬁ›‹ng:

n = 0. sup y∈K

Chłng minh (a ⇒ b) Theo gi¶ thi(cid:213)t ta cª f (x, x) = 0, ∀x ∈ K.

f (x∗, y). a, ∃x∗ ∈ K sao cho f (x∗, y) ≥ 0, ∀y ∈ K. (cid:2) − f (x, y)(cid:3)o b, min x∈K c, x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n: min y∈K

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn42

f (x, y) ≤ 0, ∀x ∈ K ⇒ inf y∈K

f (x, y)} ≤ 0. { inf y∈K ⇒ sup x∈K f (x∗, y). { inf y∈K

f (x, y)} ≥ inf y∈K f (x∗, y) ≥ 0 M˘t kh‚c, cª x∗ ∈ K n“n ta suy ra ﬁ›(cid:238)c sup x∈K Theo ph˙n a, ta l„i cª f (x∗, y) ≥ 0, ∀y ∈ K ⇒ inf y∈K

f (x, y)} f (x∗, y) ≤ sup x∈K f (x, y)} = 0 { inf y∈K { inf y∈K

f (x, y)} = sup x∈K [−f (x, y)]} = 0. ⇒ 0 ≤ inf y∈K { inf y∈K {sup y∈K

[−f (x, y)]} = 0 ⇒ max x∈K V¸y min x∈K (b ⇒ a) Do min x∈K

[−f (x, y)]} = 0 [−f (x∗, y)] = min x∈K {sup y∈K ⇒ ∃x∗ ∈ K : sup y∈K {sup y∈K

⇒ −f (x∗, y) ≤ 0, ∀y ∈ K ⇒ f (x∗, y) ≥ 0, ∀y ∈ K.

(c ⇔ a) Do x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n min y∈K

f (x∗, y)

(cid:3) ⇔ f (x∗, y) ≥ f (x∗, x∗) = 0 (do f (x, x) = 0, ∀x ∈ K), ∀y ∈ K ⇔ f (x∗, y) ≥ 0, ∀y ∈ K.

Nh¸n x—t Theo b(cid:230) ﬁ(cid:210) tr“n th(cid:215) x∗ ∈ K l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng (1.1) khi v(cid:181) ch(cid:216) khi nª l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n tŁi ›u: (cid:2) − f (x, y(cid:3)o .

n (3.1) min x∈K sup y∈K

Xu˚t ph‚t tı nh¸n x—t tr“n, ng›Œi ta ﬁ• ﬁ›a ra kh‚i ni(cid:214)m h(cid:181)m ﬁ‚nh gi‚ v(cid:181)

h›(cid:237)ng t(cid:237)i vi(cid:214)c x'y døng thu¸t to‚n h(cid:181)m ﬁ‚nh gi‚ gi¶i b(cid:181)i to‚n c'n b»ng.

§(cid:222)nh ngh(cid:220)a 3.0.2. [9] Cho K l(cid:181) t¸p ﬁªng cæa Rn. Khi ﬁª, h(cid:181)m g : K → R ﬁ›(cid:238)c g(cid:228)i l(cid:181) h(cid:181)m ﬁ‚nh gi‚ cæa b(cid:181)i to‚n c'n b»ng n(cid:213)u v(cid:181) ch(cid:216) n(cid:213)u:

Nh¸n x—t ? Tı ﬁ(cid:222)nh ngh(cid:220)a 3.0.2 ta th˚y h(cid:181)m:

a, g(x) ≥ 0, ∀x ∈ K, b, x∗ ∈ K, g(x∗) = 0 ⇔ x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn43

[−f (x, y)] (3.2) g(x) := sup y∈K

y∈K

l(cid:181) h(cid:181)m ﬁ‚nh gi‚ cæa b(cid:181)i to‚n c'n b»ng (1.1). ? §Łi v(cid:237)i b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n, ta cª h(cid:181)m ﬁ‚nh gi‚: (cid:10)T (x), x − y(cid:11) (cid:8) − (cid:10)T (x), y − x(cid:11)(cid:9) = sup (3.3) g(x) := sup y∈K

h(cid:181)m ﬁ‚nh gi‚ (3.3) g(cid:228)i l(cid:181) h(cid:181)m ﬁ‚nh gi‚ A.Auslender [6]. Trong tr›Œng h(cid:238)p t(cid:230)ng qu‚t h(cid:181)m ﬁ‚nh gi‚ n(cid:181)y nh(cid:215)n chung kh«ng kh¶ vi.

V˚n ﬁ(cid:210) x'y døng h(cid:181)m ﬁ‚nh gi‚ kh¶ vi, li“n t(cid:244)c cho b(cid:181)i to‚n b˚t ﬁ…ng thłc

bi(cid:213)n ph'n ﬁ• ﬁ›(cid:238)c ﬁ(cid:210) xu˚t ﬁ˙u ti“n bºi M.Fukushima [8] v(cid:181) ﬁ›(cid:238)c ph‚t tri(cid:211)n

ti(cid:213)p theo bºi D.L.Zhu v(cid:181) P.Marcotte. D.L.Zhu v(cid:181) P.Marcotte ﬁ• chłng minh

ﬁ›(cid:238)c r»ng: (cid:27) (cid:26) (cid:10)T (x), x − y(cid:11) − L(x, y) (3.4) g(x) := max y∈K

l(cid:181) h(cid:181)m ﬁ‚nh gi‚ kh¶ vi, li“n t(cid:244)c cho b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n, v(cid:237)i ﬁi(cid:210)u ki(cid:214)n L : K × K → R l(cid:181) mØt h(cid:181)m kh«ng 'm, kh¶ vi li“n t(cid:244)c v(cid:181) l(cid:229)i m„nh tr“n t¸p l(cid:229)i K theo bi(cid:213)n y v(cid:181) tho¶ m•n:

a, L(x, x) = 0, ∀x ∈ K, b, ∇yL(x, x) = 0, ∀y ∈ K.

(cid:10)x − y, M (x − y)(cid:11)

Trong tr›Œng h(cid:238)p ﬁ˘c bi(cid:214)t, L(x, y) := 1 v(cid:237)i M l(cid:181) ma 2 tr¸n ﬁŁi xłng x‚c ﬁ(cid:222)nh d›‹ng c˚p n, th(cid:215) ﬁª ch(cid:221)nh l(cid:181) h(cid:181)m ﬁ‚nh gi‚ ﬁ›(cid:238)c ch(cid:216) ra bºi Fukushima [9].

3.1. H(cid:181)m ﬁ‚nh gi‚ A.Auslender

Nh(cid:215)n chung, h(cid:181)m ﬁ‚nh gi‚ Auslender th›Œng kh«ng kh¶ vi [9]. Do ﬁª, ﬁ(cid:211)

cª th(cid:211) ‚p d(cid:244)ng ph›‹ng ph‚p h(cid:181)m ﬁ‚nh gi‚ gi¶i b(cid:181)i to‚n c'n b»ng ta c˙n

c‚c ﬁi(cid:210)u ki(cid:214)n ﬁ(cid:211) mØt h(cid:181)m ﬁ‚nh gi‚ l(cid:181) kh¶ vi li“n t(cid:244)c.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn44

M(cid:214)nh ﬁ(cid:210) sau ﬁ'y sˇ ﬁ›a ra ﬁi(cid:210)u ki(cid:214)n ﬁ(cid:211) mØt h(cid:181)m ﬁ‚nh gi‚ cª d„ng (3.2) l(cid:181) kh¶ vi li“n t(cid:244)c v(cid:181) cho c«ng thłc t›Œng minh ﬁ(cid:211) t(cid:221)nh ﬁ„o h(cid:181)m cæa nª.

M(cid:214)nh ﬁ(cid:210) 3.1.1. [2] Gi¶ s(cid:246) r»ng f (x, .) : K → R l(cid:181) h(cid:181)m l(cid:229)i m„nh v(cid:237)i ∀x ∈ K, kh¶ vi v(cid:237)i bi(cid:213)n x v(cid:181) ∇xf (., .) li“n t(cid:244)c tr“n K × K. Khi ﬁª,

{−f (x, y)} g(x) := sup y∈K

l(cid:181) h(cid:181)m ﬁ‚nh gi‚ kh¶ vi li“n t(cid:244)c cæa b(cid:181)i to‚n c'n b»ng v(cid:181) ﬁ„o h(cid:181)m cæa nª

ﬁ›(cid:238)c cho bºi c«ng thłc:

∇g(x) := ∇xf (x, y(x)), (3.5)

Chłng minh Do f (., .) l(cid:229)i m„nh v(cid:237)i bi(cid:213)n y, n“n t(cid:229)n t„i duy nh˚t ﬁi(cid:211)m cøc ti(cid:211)u y(x) cæa b(cid:181)i to‚n:

trong ﬁª, y(x) := argminy∈Kf (x, y).

f (x, y) min y∈K

Theo ﬁ(cid:222)nh l(cid:221) 4.3.3 cæa B.Bank, ta suy ra ﬁ›(cid:238)c y(x) l(cid:181) n(cid:246)a li“n t(cid:244)c tr“n t„i x theo ngh(cid:220)a Berge v(cid:181) l(cid:181) h(cid:181)m ﬁ‹n tr(cid:222) t„i y(x). Do ﬁª suy ra y(x) li“n t(cid:244)c t„i x. L„i do ∇xf (., .) li“n t(cid:244)c tr“n K × K, tı ﬁ(cid:222)nh l(cid:221) 1.7 ch›‹ng 4 cæa Auslender [6] ta cª:

∇g(x) := −∇xf (x, y(x))

(cid:3) Do t(cid:221)nh li“n t(cid:244)c cæa ∇xf (., .) v(cid:181) y(x) n“n ∇g(x) li“n t(cid:244)c t„i x.

Thu¸t to‚n sau ﬁ'y ﬁ›(cid:238)c x'y døng døa v(cid:181)o vi(cid:214)c cøc ti(cid:211)u h(cid:181)m ﬁ‚nh gi‚ g cho º d„ng (3.2).

Thu¸t to‚n 3.1 [9]

B›(cid:237)c 1 Cho k = 0, x0 ∈ K. B›(cid:237)c 2 Cho xk+1 = xk + tkdk v(cid:237)i k = 1, 2, . . . trong ﬁª:

{−f (x, y)}. Cho g(x) := sup y∈K

dk := y(xk) − xk

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn45

y(xk) l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n tŁi ›u:

f (xk, y) min y∈K

v(cid:181) tk l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n:

B›(cid:237)c 3 N(cid:213)u k xk+1 − xk k≤ µ v(cid:237)i µ > 0 th(cid:215) thu¸t to‚n dıng. Ng›(cid:238)c l„i, thay k bºi k + 1 v(cid:181) quay l„i b›(cid:237)c 2.

{g(xk + tdk)} min y∈K

• Nh(cid:190)c l„i r»ng, dk l(cid:181) h›(cid:237)ng gi¶m cæa h(cid:181)m ﬁ‚nh gi‚ g t„i xk n(cid:213)u:

(cid:10)∇g(xk), dk(cid:11) < 0.

Ta c˙n chłng minh dk = y(xk) − xk l(cid:181) h›(cid:237)ng gi¶m cæa h(cid:181)m ﬁ‚nh gi‚ g t„i xk. §(cid:211) kh…ng ﬁ(cid:222)nh ﬁi(cid:210)u ﬁª ta c˙n gi¶ thi(cid:213)t th“m:

(cid:10) 5x f (x, y) + 5yf (x, y), y − x(cid:11) ≥ 0, ∀x, y ∈ K. (3.6)

Gi¶ thi(cid:213)t (3.6) tho¶ m•n trong tr›Œng h(cid:238)p b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n: f (x, y) = (cid:10)T (x), y − x(cid:11)

n(cid:213)u ∇T (x) l(cid:181) ma tr¸n x‚c ﬁ(cid:222)nh d›‹ng v(cid:237)i m(cid:228)i x ∈ K.

M(cid:214)nh ﬁ(cid:210) 3.1.2. [11] Gi¶ s(cid:246) r»ng gi¶ thi(cid:213)t cæa m(cid:214)nh ﬁ(cid:210) 3.1.1 l(cid:181) ﬁ(cid:243)ng v(cid:181) gi¶ thi(cid:213)t (3.6) tho¶ m•n. Khi ﬁª,

d(x) := y(x) − x

Chłng minh Ta th˚y r»ng x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng khi v(cid:181) ch(cid:216) khi y(x∗) = x∗. M˘t kh‚c y(x) l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n:

l(cid:181) h›(cid:237)ng gi¶m cæa h(cid:181)m ﬁ‚nh gi‚ g t„i x ∈ K, v(cid:237)i ﬁi(cid:210)u ki(cid:214)n y(x) 6= x.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn46

{f (x, y)} min y∈K

v(cid:181) f (x, .) l(cid:229)i m„nh n“n b˚t ﬁ…ng thłc sau lu«n ﬁ(cid:243)ng:

(cid:10)∇yf (x, y(x)), z − y(x)(cid:11) > 0, ∀z ∈ K, z 6= y(x) (3.7)

§˘t z := x ta cª:

(cid:10)∇yf (x, y(x)), x − y(x)(cid:11) > 0

ﬁi(cid:210)u n(cid:181)y t›‹ng ﬁ›‹ng v(cid:237)i:

(cid:10)∇yf (x, y(x)), y(x) − x(cid:11) < 0

K(cid:213)t h(cid:238)p v(cid:237)i (3.6) ta cª:

0 > (cid:10)∇yf (x, y(x)), y(x) − x(cid:11) − (cid:10)∇xf (x, y(x)), y(x) − x(cid:11)

Theo c«ng thłc ﬁ„o h(cid:181)m ta cª:

∇g(x) = −∇xf (x, y(x)),

ta suy ra ﬁ›(cid:238)c:

(cid:10)∇g(y), y − x(cid:11) < 0.

(cid:3) Tłc l(cid:181), d(x) = y(x) − x l(cid:181) h›(cid:237)ng gi¶m cæa g t„i x.

§(cid:222)nh l(cid:221) sau ﬁ'y ch(cid:216) ra t(cid:221)nh hØi t(cid:244) cæa d•y ﬁi(cid:211)m ﬁ›(cid:238)c sinh tı thu¸t to‚n 3.1.

Chłng minh V(cid:215) K l(cid:181) t¸p l(cid:229)i v(cid:181) 0 ≤ tk ≤ 1, n“n {xk}k∈N ⊂ K. H(cid:181)m d(x) = y(x) − x li“n t(cid:244)c tr“n K do y(x) li“n t(cid:244)c. Ta l„i cª ‚nh x„:

§(cid:222)nh l(cid:253) 3.1.1. [9] Cho K l(cid:181) t¸p l(cid:229)i v(cid:181) compact cæa Rn. Gi¶ s(cid:246) r»ng f (x, .) l(cid:181) h(cid:181)m l(cid:229)i ch˘t (v(cid:237)i bi(cid:213)n y) ∀x ∈ K, kh¶ vi theo bi(cid:213)n x v(cid:181) ∇xf li“n t(cid:244)c tr“n K × K. H‹n n(cid:247)a, gi¶ thi(cid:213)t (3.6) tho¶ m•n. Khi ﬁª, v(cid:237)i ∀x0 ∈ K, d•y {xk}k∈N ﬁ›(cid:238)c t(cid:215)m tı thu¸t to‚n 3.1 l(cid:181) thuØc K v(cid:181) m(cid:228)i ﬁi(cid:211)m t(cid:244) cæa d•y {xk}k∈N ﬁ(cid:210)u l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

t∈[0,1]

g(x + td)(cid:9) U (x, d) = (cid:8)y : y = x + tkd, g(x + tkd) = min

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn47

l(cid:181) ﬁªng khi h(cid:181)m g l(cid:181) h(cid:181)m li“n t(cid:244)c. Do ﬁª, d•y {xk}k∈N ﬁ›(cid:238)c x'y døng bºi xk+1 = U (xk, d(xk)) l(cid:181) ﬁªng [10].

(cid:3) Theo ﬁ(cid:222)nh l(cid:221) hØi t(cid:244) cæa Zangwill suy ra b˚t k(cid:215) ﬁi(cid:211)m t(cid:244) n(cid:181)o cæa d•y {xk}k∈N ﬁ›(cid:238)c t(cid:215)m tı thu¸t to‚n 3.1 l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

M(cid:214)nh ﬁ(cid:210) 3.1.3. [9] Gi¶ s(cid:246) r»ng K l(cid:181) t¸p l(cid:229)i v(cid:181) compact cæa Rn. Gi¶ s(cid:246):

(cid:10)∇xf (x, y) + ∇yf (x, y), y − x(cid:11) ≥ µ k x − y k2, ∀x, y ∈ K (3.8)

tho¶ m•n v(cid:237)i µ > 0. Khi ﬁª,

(cid:10)∇g(x), d(x)(cid:11) ≤ −µ k d(x) k2

Nh¸n x—t Trong thu¸t to‚n 3.1, vi(cid:214)c gi¶i b(cid:181)i to‚n:

trong ﬁª, d(x) := y(x) − x.

(cid:8)g(xk + tdk)(cid:9) min y∈K

ﬁ(cid:211) t(cid:215)m tk ﬁ«i khi r˚t phłc t„p. §(cid:211) kh(cid:190)c ph(cid:244)c nh›(cid:238)c ﬁi(cid:211)m n(cid:181)y ta ﬁ›a ra thu¸t to‚n 3.2 ﬁ(cid:211) gi¶i b(cid:181)i to‚n c'n b»ng trong tr›Œng h(cid:238)p h(cid:181)m ﬁ‚nh gi‚ g ﬁ›(cid:238)c cho bºi (3.2) v(cid:181) h(cid:181)m f tho¶ m•n ﬁi(cid:210)u ki(cid:214)n (3.8).

Thu¸t to‚n 3.2 [9]

B›(cid:237)c 1 Cho k = 0, x0 ∈ K. B›(cid:237)c 2 N(cid:213)u g(xk) = 0, th(cid:215) l˚y x∗ = xk v(cid:181) thu¸t to‚n dıng. Tr‚i l„i, ta ti(cid:213)p t(cid:244)c thøc hi(cid:214)n b›(cid:237)c 3. B›(cid:237)c 3 Cho xk+1 = xk + tkdk v(cid:237)i k = 1, 2, . . . trong ﬁª:

{−f (x, y)}. Cho g(x) := sup y∈K

dk := y(xk) − xk.

Ch(cid:228)n sŁ nguy“n kh«ng 'm m nhÆ nh˚t tho¶ m•n:

g(xk) − g(xk + αmdk) ≥ tαm k dk k2

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn48

v(cid:237)i αm = tk; t, α ∈ [0, 1]. B›(cid:237)c 4 N(cid:213)u k xk+1 − xk k≤ µ v(cid:237)i µ > 0 th(cid:215) thu¸t to‚n dıng. Tr‚i l„i, thay k bºi k + 1 v(cid:181) quay l„i b›(cid:237)c 2.

§(cid:222)nh l(cid:221) sau ﬁ'y kh…ng ﬁ(cid:222)nh sø hØi t(cid:244) cæa d•y ﬁi(cid:211)m ﬁ›(cid:238)c sinh tı thu¸t to‚n 3.2.

Chłng minh Do t(cid:221)nh l(cid:229)i cæa t¸p K v(cid:181) v(cid:237)i m(cid:228)i tk ∈ [0, 1] n“n ta suy ra {xk}k∈N ⊂ K. L„i do t(cid:221)nh compact cæa t¸p K n“n tı d•y {xk}k∈N ta cª th(cid:211) tr(cid:221)ch ra ﬁ›(cid:238)c mØt d•y con {xkn}kn∈N, d•y n(cid:181)y hØi t(cid:244) ﬁ(cid:213)n ﬁi(cid:211)m x∗. Ta sˇ chłng minh y(x∗) = x∗ v(cid:215) th(cid:213) n“n x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng. Cho d(x) := y(x)−x, v(cid:215) y(x) li“n t(cid:244)c (xem chłng minh cæa m(cid:214)nh ﬁ(cid:210) 3.1.1) n“n suy ra d(x) li“n t(cid:244)c. V(cid:215) v¸y, ta cª th(cid:211) kh…ng ﬁ(cid:222)nh d(xkn) → d(x∗) := d∗ v(cid:181) g(xkn) → g(x∗) := g∗. Ta cª:

§(cid:222)nh l(cid:253) 3.1.2. [9] Cho {xk}k∈N l(cid:181) d•y ﬁ›(cid:238)c t(cid:221)nh tı thu¸t to‚n 3.2. Gi¶ s(cid:246) K l(cid:181) t¸p l(cid:229)i v(cid:181) compact cæa Rn, f (x, .) l(cid:229)i m„nh v(cid:237)i ∀x ∈ K v(cid:181) gi¶ s(cid:246) (3.8) tho¶ m•n v(cid:237)i µ > 0 v(cid:181) t < µ/2. Khi ﬁª, v(cid:237)i m(cid:228)i x0 ∈ K, d•y {xk}k∈N ⊂ K v(cid:181) hØi t(cid:244) ﬁ(cid:213)n nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

g(xk) − g(xk+1) ≥ tαk k dk k2,

Do ﬁª,

αkn k d(xkn) k2→ 0,

v¸y {αkn} ⊆ {αk}. N(cid:213)u αkn > γ > 0, γ ∈ R, ∀k ∈ R th(cid:215) k d(xkn) k→ 0 n“n y(x∗) = x∗. Tr‚i l„i, gi¶ s(cid:246) t(cid:229)n t„i d•y {αkp} ⊆ {αkn}, αkp → 0. Ta cª,

< t k d(xkp) k2, (3.9) g(xkp) − g(xkp + αkpd(xkp) αkp

trong ﬁª, αkp = αkp/α. Cho (3.9) qua gi(cid:237)i h„n v(cid:237)i kp → 0, do αkp → 0 v(cid:181) g kh¶ vi li“n t(cid:244)c n“n suy ra:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn49

−(cid:10)∇g(x∗), d∗(cid:11) ≤ t k d∗ k2, (3.10)

M(cid:214)nh ﬁ(cid:210) 3.1.3 ta cª:

−(cid:10)∇g(x∗), d∗(cid:11) ≥ µ k d∗ k2 .

(cid:3) V(cid:215) t < µ/2 n“n k d∗ k= 0, tı ﬁª suy ra y(x∗) = x∗.

º ph˙n tr“n Auslender ﬁ• x'y døng thu¸t to‚n h(cid:181)m ﬁ‚nh gi‚ gi¶i b(cid:181)i to‚n c'n b»ng khi f (x, .) l(cid:229)i m„nh. Nh›ng kh«ng ph¶i l(cid:243)c n(cid:181)o gi¶ thi(cid:213)t v(cid:210) t(cid:221)nh l(cid:229)i m„nh c(cid:242)ng ﬁ›(cid:238)c tho¶ m•n. Ch…ng h„n, b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n khi f (x, .) l(cid:181) h(cid:181)m tuy(cid:213)n t(cid:221)nh. §(cid:211) kh(cid:190)c ph(cid:244)c nh›(cid:238)c ﬁi(cid:211)m n(cid:181)y Fukushima ﬁ• chuy(cid:211)n b(cid:181)i to‚n c'n b»ng v(cid:210) b(cid:181)i to‚n c'n b»ng ph(cid:244) v(cid:181) ﬁ›a ra thu¸t to‚n

3.2. H(cid:181)m ﬁ‚nh gi‚ M.Fukushima

h(cid:181)m ﬁ‚nh gi‚ gi¶i b(cid:181)i to‚n c'n b»ng.

§(cid:222)nh l(cid:253) 3.2.1. [2] Gi¶ s(cid:246) f (x, .) : K → R l(cid:181) h(cid:181)m l(cid:229)i v(cid:237)i ∀x ∈ K, kh¶ vi v(cid:237)i bi(cid:213)n x v(cid:181) ∇xf (., .) li“n t(cid:244)c tr“n K × K. Cho L(., .) kh«ng 'm, kh¶ vi li“n t(cid:244)c tr“n K × K, l(cid:229)i m„nh v(cid:237)i bi(cid:213)n y, ∀x ∈ K tho¶ m•n:

a, L(x, x) = 0, ∀x ∈ K, b, ∇yL(x, x) = 0, ∀x ∈ K.

Khi ﬁª,

{−f (x, y) − L(x, y)} (3.11) g(x) := max y∈K

l(cid:181) h(cid:181)m ﬁ‚nh gi‚ kh¶ vi li“n t(cid:244)c cæa b(cid:181)i to‚n c'n b»ng v(cid:181) ﬁ„o h(cid:181)m cæa nª

ﬁ›(cid:238)c cho bºi c«ng thłc:

∇g(x) := −∇xf (x, y(x)) − ∇xL(x, y(x)) (3.12)

Chłng minh Tı b(cid:230) ﬁ(cid:210) 3.0.5 v(cid:181) h(cid:214) qu¶ 2.2.1 (ch›‹ng 2), ta suy ra b(cid:181)i to‚n c'n b»ng t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng ph(cid:244) sau:

trong ﬁª, y(x) := arguminy∈K{f (x, y) + L(x, y)}.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn50

{(cid:15)f (x∗, y) + L(x∗, y)}. min y∈K

L˚y (cid:15) = 1 v(cid:181) ‚p d(cid:244)ng m(cid:214)nh ﬁ(cid:210) 3.1.1 cho b(cid:181)i to‚n c'n b»ng ph(cid:244) ta suy ra ﬁi(cid:210)u (cid:3) ph¶i chłng minh. Nh¸n x—t Khi f (x, y) := (cid:10)T (x), y − x(cid:11) th(cid:215)

{−f (x, y) − L(x, y)} g(x) := sup y∈K

l(cid:181) h(cid:181)m ﬁ‚nh gi‚ cho b(cid:181)i to‚n b˚t ﬁ…ng thłc bi(cid:213)n ph'n. ‚p d(cid:244)ng thu¸t to‚n 3.1 cho b(cid:181)i to‚n c'n b»ng ta cª thu¸t to‚n cho b(cid:181)i to‚n c'n b»ng ph(cid:244).

Thu¸t to‚n 3.3 [9] B›(cid:237)c 1 Cho k = 0, x0 ∈ K. B›(cid:237)c 2 Cho xk+1 = xk + tkdk v(cid:237)i k = 1, 2, . . . trong ﬁª,

{−f (x, y) − L(x, y)}. Cho g(x) := max y∈K

dk = y(xk) − xk

y(xk) l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n tŁi ›u:

{f (xk, y) + L(xk, y)}, min y∈K

v(cid:181) tk l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n:

B›(cid:237)c 3 N(cid:213)u k xk+1 − xk k≤ µ v(cid:237)i µ > 0 th(cid:215) thu¸t to‚n dıng. Tr‚i l„i, thay k bºi k + 1 v(cid:181) quay l„i b›(cid:237)c 2.

{g(xk + tdk)}. min y∈K

Trong thu¸t to‚n 3.3 thay th(cid:213) gi¶ thi(cid:213)t (3.6) cæa thu¸t to‚n 3.1 bºi ﬁi(cid:210)u ki(cid:214)n sau: (cid:10)∇xf (x, y) + ∇xL(x, y) + ∇yf (x, y) + ∇yL(x, y), y − x(cid:11) ≥ 0, ∀x, y ∈ K. (3.13) D(cid:212) th˚y r»ng n(cid:213)u ta gi¶ thi(cid:213)t ∇xL(x, y) + ∇yL(x, y) = 0, ∀x, y ∈ K th(cid:215) gi¶ thi(cid:213)t (3.13) ch(cid:221)nh l(cid:181) gi¶ thi(cid:213)t (3.6).

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn51

§(cid:222)nh l(cid:221) sau ch(cid:216) ra t(cid:221)nh hØi t(cid:244) cæa d•y ﬁi(cid:211)m ﬁ›(cid:238)c sinh bºi thu¸t to‚n 3.3.

§(cid:222)nh l(cid:253) 3.2.2. [2] Cho K l(cid:181) t¸p l(cid:229)i v(cid:181) compact cæa t¸p Rn. Gi¶ s(cid:246) r»ng f (x, .) l(cid:181) h(cid:181)m l(cid:229)i ∀x ∈ K, kh¶ vi v(cid:237)i bi(cid:213)n x v(cid:181) ∇xf li“n t(cid:244)c tr“n K × K. Cho L(., .) : K × K → R kh«ng 'm, kh¶ vi li“n t(cid:244)c tr“n K × K, L(x, .) l(cid:229)i ch˘t v(cid:237)i ∀x ∈ K v(cid:181) tho¶ m•n:

a, L(x, x) = 0, ∀x ∈ K, b, ∇yL(x, x) = 0, ∀x ∈ K.

Chłng minh Theo m(cid:214)nh ﬁ(cid:210) 3.0.5, b(cid:181)i to‚n c'n b»ng t›‹ng ﬁ›‹ng v(cid:237)i b(cid:181)i to‚n c'n b»ng ph(cid:244). L˚y (cid:15) = 1 v(cid:181) ‚p d(cid:244)ng ﬁ(cid:222)nh l(cid:221) 3.2.1 cho b(cid:181)i to‚n c'n b»ng (cid:3) ph(cid:244) ta suy ra ﬁi(cid:210)u ph¶i chłng minh.

Nh¸n x—t Ch(cid:243)ng ta nh¸n th˚y r»ng ﬁi(cid:210)u ki(cid:214)n l(cid:229)i m„nh cæa h(cid:181)m f (x, .) tr“n K trong thu¸t to‚n 3.2 l(cid:181)m h„n ch(cid:213) ph„m vi łng d(cid:244)ng. §i(cid:210)u ki(cid:214)n n(cid:181)y cª th(cid:211) bÆ ﬁ›(cid:238)c n(cid:213)u ta thay th(cid:213) gi¶ thi(cid:213)t (3.8) bºi gi¶ thi(cid:213)t sau [11]: (cid:10)∇xf (x, y) + ∇xL(x, y) + ∇yf (x, y) + ∇yL(x, y), y − x(cid:11) ≥ µ k x − y k2 . (3.14)

H‹n n(cid:247)a, gi¶ s(cid:246) ﬁi(cid:210)u ki(cid:214)n (3.13) tho¶ m•n. Khi ﬁª, v(cid:237)i m(cid:228)i ﬁi(cid:211)m x0 ∈ K, d•y {xk}k∈N ﬁ›(cid:238)c t(cid:215)m tı thu¸t to‚n 3.3 l(cid:181) thuØc K v(cid:181) hØi t(cid:244) t(cid:237)i nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Thu¸t to‚n sˇ tr(cid:215)nh b(cid:181)y sau ﬁ'y cª th(cid:211) ‚p d(cid:244)ng ngay c¶ trong tr›Œng h(cid:238)p f (x, .) l(cid:181) h(cid:181)m l(cid:229)i, nh›ng kh«ng nh˚t thi(cid:213)t l(cid:181) l(cid:229)i m„nh [9].

Thu¸t to‚n 3.4 [9] B›(cid:237)c 1 Cho k = 0, x0 ∈ K. B›(cid:237)c 2 N(cid:213)u g(xk) = 0 th(cid:215) thu¸t to‚n dıng. Tr‚i l„i ta ti(cid:213)p t(cid:244)c thøc hi(cid:214)n b›(cid:237)c 3. B›(cid:237)c 3 Cho xk+1 = xk + tkdk v(cid:237)i k = 1, 2, . . . trong ﬁª:

{−f (x, y) − L(x, y)}. Cho g(x) := max y∈K

dk := y(xk) − xk.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn52

Ch(cid:228)n sŁ nguy“n kh«ng 'm m nhÆ nh˚t tho¶ m•n:

g(xk) − g(xk + αmdk) ≥ tαm k dk k2

Sø hØi t(cid:244) cæa d•y ﬁi(cid:211)m ﬁ›(cid:238)c sinh tı thu¸t to‚n 3.4 ﬁ›(cid:238)c kh…ng ﬁ(cid:222)nh bºi h(cid:214) qu¶ (cæa ﬁ(cid:222)nh l(cid:221) 3.1.2) sau:

H(cid:214) qu¶ 3.2.1. [9] Cho {xk} l(cid:181) d•y ﬁ›(cid:238)c t(cid:215)m tı thu¸t to‚n 3.4. Gi¶ s(cid:246) r»ng K l(cid:181) t¸p l(cid:229)i v(cid:181) compact cæa Rn v(cid:181) gi¶ thi(cid:213)t (3.14) tho¶ m•n v(cid:237)i µ > 0 v(cid:181) t < µ/2. Khi ﬁª, v(cid:237)i m(cid:228)i x0 ∈ K d•y {xk} ⊂ K v(cid:181) hØi t(cid:244) t(cid:237)i nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

Ng›Œi ta chłng minh ﬁ›(cid:238)c r»ng cª th(cid:211) gi¶m nh(cid:209) ﬁi(cid:210)u ki(cid:214)n v(cid:210) t(cid:221)nh compact cæa t¸p ch˚p nh¸n ﬁ›(cid:238)c K trong tr›Œng h(cid:238)p h(cid:181)m f ﬁ‹n ﬁi(cid:214)u m„nh v(cid:181) ∇xL li“n t(cid:244)c Lipschitz tr“n K [11]. M(cid:214)nh ﬁ(cid:210) sau cho ph—p ta ﬁ‚nh gi‚ sai sŁ to(cid:181)n c(cid:244)c khi gi¶i b(cid:181)i to‚n c'n b»ng theo h(cid:181)m ﬁ‚nh gi‚ g trong tr›Œng h(cid:238)p f ﬁ‹n ﬁi(cid:214)u m„nh.

M(cid:214)nh ﬁ(cid:210) 3.2.1. [9] Cho f ﬁ‹n ﬁi(cid:214)u m„nh tr“n K v(cid:237)i h(cid:214) sŁ b. Khi ﬁª,

g(x) ≥ b k x − x∗ k2, ∀x ∈ K (3.15)

Chłng minh V(cid:215) v(cid:237)i ∀y ∈ K ta cª g(x) ≥ −f (x, y). Khi ﬁª døa v(cid:181)o gi¶ thi(cid:213)t v(cid:210) t(cid:221)nh ﬁ‹n ﬁi(cid:214)u m„nh theo h(cid:214) sŁ b cæa h(cid:181)m f v(cid:181) t(cid:221)nh ch˚t f (x, x) = 0, ∀x ∈ K ta cª:

v(cid:237)i x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

g(x) ≥ −f (x∗, x) − f (x, x∗) + f (x, x∗)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn53

(cid:3) ≥ b k x − x∗ k2 +f (x, x∗) ≥ b k x − x∗ k2 .

(cid:8) − f (x, y) − L(x, y)(cid:9)

Ta cª th(cid:211) mº rØng k(cid:213)t qu¶ n“u trong m(cid:214)nh ﬁ(cid:210) 3.2.1 ﬁŁi v(cid:237)i h(cid:181)m ﬁ‚nh gi‚ g := maxy∈K v(cid:181) c˙n x—t th“m ﬁi(cid:210)u ki(cid:214)n v(cid:210) t(cid:221)nh li“n t(cid:244)c Lipschitz cho h(cid:181)m ∇yL(x, y).

M(cid:214)nh ﬁ(cid:210) 3.2.2. [11] Cho f ﬁ‹n ﬁi(cid:214)u m„nh tr“n K v(cid:237)i h(cid:214) sŁ b, L(x, .) l(cid:229)i v(cid:181) ∇yL(x, .) li“n t(cid:244)c Lipschitz v(cid:237)i h(cid:214) sŁ L < 2b, ∀x ∈ K. Khi ﬁª,

g(x) ≥ (b − L/2) k x − x∗ k2, ∀x ∈ K (3.16)

Chłng minh V(cid:237)i ∀x, y ∈ K cª

v(cid:237)i x∗ l(cid:181) nghi(cid:214)m cæa b(cid:181)i to‚n c'n b»ng.

g(x) ≥ −f (x, y) − G(x, y).

Do ﬁª, v(cid:237)i x∗ = y cª

g(x) ≥ −f (x∗, x) − L(x∗, x) − f (x, x∗) + f (x, x∗) ≥ b k x − x∗ k2 +f (x, x∗) − L(x∗, x).

Cª

g(x) ≥ b k x − x∗ k2 − G(x∗, x). (3.17)

Do ∇yL(x, .) li“n t(cid:244)c Lipschitz n“n b˚t ﬁ…ng thłc sau ﬁ(cid:243)ng

L(x∗, x) = L(x∗, x) − L(x, x) ( do L(x, x) = 0) ≤ (L/2) k x∗ − x k2, ∀x ∈ K.

K(cid:213)t h(cid:238)p v(cid:237)i (3.17) cª

K(cid:213)t lu¸n ch›‹ng

(cid:3) g(x) ≥ (b − L/2) k x − x∗ k2, ∀x ∈ K.

Ch›‹ng n(cid:181)y ﬁ• tr(cid:215)nh b(cid:181)y l(cid:221) thuy(cid:213)t h(cid:181)m ﬁ‚nh gi‚ gi¶i b(cid:181)i to‚n c'n b»ng. Døa

v(cid:181)o l(cid:221) thuy(cid:213)t h(cid:181)m ﬁ‚nh gi‚, Auslender v(cid:181) Fukushima ﬁ• ﬁ›a ra c‚c thu¸t to‚n gi¶i b(cid:181)i to‚n c'n b»ng th«ng qua b(cid:181)i to‚n cøc ti(cid:211)u cª r(cid:181)ng buØc mØt

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn54

h(cid:181)m kh¶ vi li“n t(cid:244)c t›‹ng łng.

K(cid:213)t lu¸n

Nh› ﬁ• tr(cid:215)nh b(cid:181)y º tr“n, b(cid:181)i to‚n c'n b»ng (1.1) l(cid:181) b(cid:181)i to‚n t(cid:230)ng qu‚t v(cid:215) cª nhi(cid:210)u b(cid:181)i to‚n quen thuØc nh›: b(cid:181)i to‚n tŁi ›u, b(cid:181)i to‚n b˚t ﬁ…ng thłc

bi(cid:213)n ph'n, b(cid:181)i to‚n c'n b»ng Nash,... ﬁ(cid:210)u cª th(cid:211) ﬁ›a v(cid:210) b(cid:181)i to‚n c'n b»ng.

B(cid:181)i to‚n c'n b»ng cª th(cid:211) ﬁ›(cid:238)c nghi“n cłu v(cid:181) ti(cid:213)p c¸n theo nh(cid:247)ng c‚ch kh‚c

nhau. Lu¸n v¤n n(cid:181)y nghi“n cłu ph›‹ng ph‚p chi(cid:213)u, ph›‹ng ph‚p gradient

t¤ng c›Œng v(cid:181) ph›‹ng ph‚p h(cid:181)m ﬁ‚nh gi‚ gi¶i b(cid:181)i to‚n c'n b»ng. Nh(cid:247)ng

nØi dung ch(cid:221)nh ﬁ›(cid:238)c tr(cid:215)nh b(cid:181)y trong lu¸n v¤n bao g(cid:229)m:

• D„ng to‚n h(cid:228)c cæa b(cid:181)i to‚n c'n b»ng v(cid:181) mØt sŁ b(cid:181)i to‚n łng d(cid:244)ng quen

thuØc m(cid:181) cª th(cid:211) chuy(cid:211)n v(cid:210) b(cid:181)i to‚n c'n b»ng.

• Tr(cid:215)nh b(cid:181)y ph›‹ng ph‚p chi(cid:213)u v(cid:181) ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n c'n

b»ng.

• Tr(cid:215)nh b(cid:181)y ph›‹ng ph‚p h(cid:181)m ﬁ‚nh gi‚ gi¶i b(cid:181)i to‚n c'n b»ng. Ngh(cid:220)a l(cid:181), s(cid:246) d(cid:244)ng l(cid:221) thuy(cid:213)t h(cid:181)m ﬁ‚nh gi‚ ﬁ(cid:211) ﬁ›a vi(cid:214)c gi¶i b(cid:181)i to‚n c'n b»ng v(cid:210) vi(cid:214)c

gi¶i b(cid:181)i to‚n cøc ti(cid:211)u mØt h(cid:181)m ﬁ‚nh gi‚ theo ph›‹ng ph‚p h›(cid:237)ng gi¶m tr“n

t¸p r(cid:181)ng buØc.

Trong thŒi gian t(cid:237)i, t‚c gi¶ mong muŁn cª th(cid:211) nghi“n cłu s'u h‹n v(cid:210) b(cid:181)i

to‚n c'n b»ng ﬁ(cid:211) cª th(cid:211) ﬁ„t ﬁ›(cid:238)c mØt sŁ k(cid:213)t qu¶ ri“ng v(cid:210) l(cid:220)nh vøc n(cid:181)y. T‚c

gi¶ mong muŁn nh¸n ﬁ›(cid:238)c sø gi(cid:243)p ﬁ(cid:236) v(cid:181) ch(cid:216) d(cid:201)n c‚c th(cid:181)y c« gi‚o c(cid:239)ng c‚c

b„n b(cid:204) ﬁ(cid:229)ng nghi(cid:214)p ﬁ(cid:211) ﬁ„t ﬁ›(cid:238)c nh(cid:247)ng k(cid:213)t qu¶ ﬁ‚ng k(cid:211) trong h›(cid:237)ng nghi“n

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn55

cłu n(cid:181)y.

T(cid:181)i li(cid:214)u tham kh¶o

[1] L“ D(cid:242)ng M›u (1998), Nh¸p m«n c‚c ph›‹ng ph‚p tŁi ›u, Nh(cid:181) xu˚t b¶n

Khoa h(cid:228)c v(cid:181) K(cid:252) thu¸t, H(cid:181) NØi.

[2] Nguyen Van Hien (2002), Lecture Notes on Equilibrium Problems, Na-

mur, Belgium.

thuy(cid:213)t v(cid:181) Thu¸t to‚n, Nh(cid:181) xu˚t b¶n B‚ch Khoa -H(cid:181) NØi.

[3] Nguy(cid:212)n Th(cid:222) B„ch Kim (2008), Gi‚o tr(cid:215)nh C‚c Ph›‹ng ph‚p TŁi ›u L(cid:253)

[4] PGS.TS §(cid:231) V¤n L›u - PGS.TS Phan Huy Kh¶i (2000), Gi¶i t(cid:221)ch l(cid:229)i, Nh(cid:181)

xu˚t b¶n Khoa h(cid:228)c v(cid:181) K(cid:252) thu¸t, H(cid:181) NØi.

[5] D.Quoc Tran, M.Le Dung, Van Hien Nguyen (2008), "Extragradient

Algorithms Extended to Equilibrium Problems", Optimization.

[6] A.Auslender (1976), Opitimization-M—thodes num—riques, Masson,

Paris.

[7] E.Blum and W.Oettli (1994), "From Opitimization to Variational Inqual- ities to Equilibrium Problems", The Mathematics Student 63, pp.134-145.

[8] M.Fukushima (1992), "Equivalent Differentiable Opitimization Prob-

lems and Descent Methods for Asymmetric VariationalInquality Prob- lems", Mathematical Programming 53, pp. 99-110.

of Gloal Opitimization 27, pp. 411-426.

[9] G.Mastroeni (2003), "Gap Function for Equilibrium Problems", Journal

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn56

[10] D.L.Zhu and P.Marcotte (1994), "An Extended Descent Framework for Variational Inequalities", Journal of Opitimization Theory and Appli- cations 80, pp. 349-366.

Luận văn: NGHIÊN CỨU HIỆU CHỈNH HÓA TRONG BÀI TOÁN CÂN BẰNG

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIÊN CỨU HIỆU CHỈNH HÓA

TRONG BÀI TOÁN CÂN BẰNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN – 2009

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIÊN CỨU HIỆU CHỈNH HÓA

TRONG BÀI TOÁN CÂN BẰNG

Chuyên ngành: Toán ứng dụng Mã số: 60. 46. 36 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 - 2009

M(cid:244)c l(cid:244)c

Ch›‹ng 1

B(cid:181)i to‚n c'n b»ng

Ch›‹ng 2

Ph›‹ng ph‚p chi(cid:213)u v(cid:181) ﬁ„o h(cid:181)m t¤ng c›Œng gi¶i b(cid:181)i to‚n c'n b»ng

Ch›‹ng 3

Ph›‹ng ph‚p h(cid:181)m ﬁ‚nh gi‚

T(cid:181)i li(cid:214)u tham kh¶o

Có thể bạn quan tâm

Luận văn Thạc sĩ: Chế tạo và nghiên cứu tính chất điện, từ của vật liệu multiferroic Ba₀.₇Ca₀.₃TiO₃/ NiFe₂O₄

Luận văn Thạc sĩ: Nghiên cứu vật liệu biến hóa dạng chuỗi một chiều chế tạo từ kim loại đồng trên đế FR-4 hoạt động tại tần số MHz ứng dụng trong truyền năng lượng không dây

Luận văn Thạc sĩ: Đánh giá khả năng tác động tới môi trường biển của việc xả nước thải từ sự cố nhà máy điện hạt nhân Fukushima sử dụng công cụ ERICA

Luận văn Thạc sĩ: Xây dựng mô hình đầu dò nơtron và gamma sử dụng nhấp nháy EJ-276 ghép nối với mảng nhân quang silicon

Luận văn Thạc sĩ: Đánh giá khả năng ảnh hưởng của bức xạ ion hóa đến sức khỏe cư dân khu vực mỏ đất hiếm Đông Pao, xã Bản Hon, huyện Tam Đường, tỉnh Lai Châu

Luận văn Thạc sĩ: Sử dụng phương pháp nhiễu xạ neutron khảo sát cấu trúc tinh thể và pha trật tự từ trong vật liệu Pr2FeCrO6

Luận văn Thạc sĩ: Nghiên cứu phân lập, xác định cấu trúc và hoạt tính ức chế NO của các hợp chất thứ cấp từ chủng vi nấm biển Aspergillus sp. CL251

Luận văn Thạc sĩ: Phân tích một số hợp chất bisphenol thôi nhiễm từ bao bì nhựa lên một số mẫu thực phẩm nền tinh bột

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá hoạt tính kháng khuẩn, kháng nấm của loài hoa mộc (Osmanthus fragrans (Thunb.) Lour.) ở Việt Nam

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và đánh giá tác dụng kháng viêm của loài côi Turpinia montana (Blume) Kurz

Luận văn Thạc sĩ: Tổng hợp và đặc trưng tính chất vật liệu composite có cấu trúc nano chitosan–cyclodextrin/TiO₂–Ag

Luận văn Thạc sĩ: Nghiên cứu chế tạo và khảo sát một số tính chất của màng phủ trên cơ sở nhựa epoxy gốc nước và khung cơ kim - ZIF

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất napthoquinone chứa nguyên tố flo bằng phản ứng đa thành phần

Luận văn Thạc sĩ: Nghiên cứu điều chế vật liệu Bioglass và tổ hợp lai với polymer ALG-F127 định hướng ứng dụng trong điều trị nội nha

Luận văn Thạc sĩ: Khảo sát thành phần hóa học và hoạt tính ức chế enzyme α-glucosidase trên một số hợp chất phân lập từ thịt quả bình bát nước (Annona glabra L.).

Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine

Luận văn Thạc sĩ: Nghiên cứu tổng hợp một số dẫn xuất của benzazole

Luận văn Thạc sĩ: Nghiên cứu chiết tách lignin từ vỏ sầu riêng Ri6 (Durio zibethinus Murr.) và tổng hợp vật liệu biocomposite định hướng ứng dụng trong bảo quản sau thu hoạch

Luận văn Thạc sĩ: Nghiên cứu tổng hợp hạt nano bạc phủ acid hyaluronic mang doxorubicin định hướng ứng dụng trong điều trị ung thư

Luận văn Thạc sĩ: Nghiên cứu thành phần hóa học và hoạt tính kháng viêm của loài rau dừa nước (Ludwigia adscendens)

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok