Luận văn Thạc sĩ Toán học: Bài toán tối ưu với ràng buộc là bài toán bù tổng quát

NGUY(cid:153)N THANH T(cid:133)M

(cid:30)(cid:132)I H¯C TH(cid:129)I NGUY(cid:150)N TR(cid:215)˝NG (cid:30)(cid:132)I H¯C S(cid:215) PH(cid:132)M

B(cid:128)I TO(cid:129)N T¨I (cid:215)U V˛I R(cid:128)NG BU¸C L(cid:128) B(cid:128)I TO(cid:129)N B(cid:210) T˚NG QU(cid:129)T

LU(cid:138)N V(cid:139)N TH(cid:132)C S(cid:223) TO(cid:129)N H¯C

TH(cid:129)I NGUY(cid:150)N - 2017

NGUY(cid:153)N THANH T(cid:133)M

(cid:30)(cid:132)I H¯C TH(cid:129)I NGUY(cid:150)N TR(cid:215)˝NG (cid:30)(cid:132)I H¯C S(cid:215) PH(cid:132)M

B(cid:128)I TO(cid:129)N T¨I (cid:215)U V˛I R(cid:128)NG BU¸C L(cid:128) B(cid:128)I TO(cid:129)N B(cid:210) T˚NG QU(cid:129)T

Chuy¶n ng(cid:160)nh: To¡n gi£i t‰ch

M¢ sŁ: 60. 46. 01. 02

LU(cid:138)N V(cid:139)N TH(cid:132)C S(cid:223) TO(cid:129)N H¯C

Ng(cid:247)(cid:237)i h(cid:247)(cid:238)ng d¤n khoa h(cid:229)c: GS.TSKH. NGUY(cid:153)N XU(cid:133)N T(cid:135)N

TH(cid:129)I NGUY(cid:150)N - 2017

L(cid:237)i cam (cid:31)oan

T(cid:230)i xin cam (cid:31)oan r‹ng c¡c k‚t qu£ trong lu“n v«n l(cid:160) trung th(cid:252)c v(cid:160) kh(cid:230)ng

tr(cid:242)ng l(cid:176)p v(cid:238)i c¡c (cid:31)• t(cid:160)i kh¡c. C¡c sŁ li»u, k‚t qu£ n¶u trong lu“n v«n (cid:31)(cid:247)æc

t(cid:230)i t…m (cid:31)(cid:229)c v(cid:160) tr‰ch d¤n tł c¡c t(cid:160)i li»u [2], [11].

Th¡i Nguy¶n, ng(cid:160)y th¡ng n«m 2017

Ng(cid:247)(cid:237)i vi‚t lu“n v«n

Nguy„n Thanh T¥m

L(cid:237)i c£m (cid:236)n

Lu“n v«n (cid:31)(cid:247)æc ho(cid:160)n th(cid:160)nh d(cid:247)(cid:238)i s(cid:252) h(cid:247)(cid:238)ng d¤n t“n t…nh cıa GS. TSKH.

Nguy„n Xu¥n T§n. T¡c gi£ xin b(cid:160)y t(cid:228) lÆng bi‚t (cid:236)n s¥u s›c (cid:31)‚n ng(cid:247)(cid:237)i thƒy

cıa m…nh, trong mºt th(cid:237)i gian d(cid:160)i (cid:31)¢ tłng b(cid:247)(cid:238)c d¤n d›t t¡c gi£ l(cid:160)m quen

v(cid:238)i bº m(cid:230)n l(cid:254) thuy‚t tŁi (cid:247)u, (cid:31)¢ truy•n cho t¡c gi£ nhœng kinh nghi»m

trong nghi¶n cøu khoa h(cid:229)c, (cid:31)ºng vi¶n kh‰ch l» t¡c gi£ v(cid:247)æt qua nhœng kh(cid:226)

kh«n trong chuy¶n m(cid:230)n v(cid:160) cuºc sŁng.

T¡c gi£ c(cid:244)ng xin b(cid:160)y t(cid:228) lÆng bi‚t (cid:236)n s¥u s›c t(cid:238)i c¡c gi¡o s(cid:247), c¡c thƒy,

c(cid:230) gi¡o cıa Vi»n To¡n h(cid:229)c v(cid:160) tr(cid:247)(cid:237)ng S(cid:247) Ph⁄m Th¡i Nguy¶n, nhœng ng(cid:247)(cid:237)i

(cid:31)¢ t“n t…nh gi£ng d⁄y, (cid:31)¢ t⁄o (cid:31)i•u ki»n v(cid:160) gi(cid:243)p (cid:31)(cid:239) t¡c gi£ trong suŁt qu¡

tr…nh h(cid:229)c t“p, nghi¶n cøu v(cid:160) ho(cid:160)n th(cid:160)nh lu“n v«n.

CuŁi c(cid:242)ng, t¡c gi£ muŁn b(cid:160)y t(cid:228) lÆng bi‚t (cid:236)n s¥u s›c t(cid:238)i anh ch(cid:224) em h(cid:229)c

vi¶n cao h(cid:229)c To¡n gi£i t‰ch k23, nhœng ng(cid:247)(cid:237)i th¥n trong gia (cid:31)…nh cıa m…nh

(cid:31)¢ lu(cid:230)n (cid:31)ºng vi¶n, chia s· v(cid:160) kh‰ch l» (cid:31)” t¡c gi£ c(cid:226) th” ho(cid:160)n th(cid:160)nh c(cid:230)ng

vi»c h(cid:229)c t“p v(cid:160) nghi¶n cøu cıa m…nh.

Th¡i Nguy¶n, ng(cid:160)y th¡ng n«m 2017

Ng(cid:247)(cid:237)i vi‚t lu“n v«n

Nguy„n Thanh T¥m

iii

M(cid:246)c l(cid:246)c

L(cid:237)i cam (cid:31)oan i

L(cid:237)i c£m (cid:236)n ii

M(cid:246)c l(cid:246)c iii

M(cid:240) (cid:31)ƒu 1

7 1 Mºt sŁ ki‚n thøc chu'n b(cid:224)

7 1.1 Mºt sŁ ki‚n thøc c(cid:236) b£n . . . . . . . . . . . . . . . . . . .

9 1.2 B(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh v(cid:160) ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh . . .

9 1.2.1 Kh¡i ni»m b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh . . . . . . . .

1.2.2 Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov . . . . . . . . . 10

1.2.3 Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho b(cid:160)i to¡n c(cid:252)c

11 tr(cid:224) tŒng qu¡t . . . . . . . . . . . . . . . . . . . . .

13 1.3 B(cid:160)i to¡n b(cid:242) . . . . . . . . . . . . . . . . . . . . . . . . . .

13 1.3.1 B(cid:160)i to¡n b(cid:242) tuy‚n t‰nh . . . . . . . . . . . . . . . .

20 1.3.2 B(cid:160)i to¡n b(cid:242) phi tuy‚n . . . . . . . . . . . . . . . .

32 1.3.3 B(cid:160)i to¡n b(cid:242) tŒng qu¡t . . . . . . . . . . . . . . . .

36 2 B(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng qu¡t

36 2.1 Ph¡t bi”u b(cid:160)i to¡n . . . . . . . . . . . . . . . . . . . . . .

2.2 Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho b(cid:160)i to¡n (cid:31)(cid:176)t ra . . 41

2.3 V‰ d(cid:246) minh h(cid:229)a . . . . . . . . . . . . . . . . . . . . . . . . 47

T(cid:160)i li»u tham kh£o 51

M(cid:240) (cid:31)ƒu

B(cid:160)i to¡n b(cid:242) c(cid:226) nhi•u øng d(cid:246)ng trong c¡c l(cid:190)nh v(cid:252)c: kinh t‚, t(cid:160)i ch‰nh, k(cid:255)

thu“t, v“t l(cid:254), sinh th¡i v(cid:160) (cid:31)i•u khi”n tŁi (cid:247)u,... Vi»c nghi¶n cøu b(cid:160)i to¡n b(cid:242)

hi»n nay v¤n (cid:31)ang l(cid:160) v§n (cid:31)• th(cid:237)i s(cid:252), (cid:31)(cid:176)c bi»t l(cid:160) vi»c t…m ra ph(cid:247)(cid:236)ng ph¡p

gi£i b(cid:160)i to¡n b(cid:242) (cid:31)ang (cid:31)(cid:247)æc nhi•u nh(cid:160) to¡n h(cid:229)c quan t¥m .

B(cid:160)i to¡n b(cid:242) nguy¶n gŁc (cid:31)(cid:247)æc ph¡t bi”u : Cho f : Rn → Rn,

+ sao cho

T…m ¯x ∈ Rn

+ v(cid:160) < ¯x, f (¯x) >= 0,

f (¯x) ∈ Rn (0.1)

+, xi ≥ 0, i = 1, 2, ...n}

+ = {x = (x1, x2, ...., xn) ∈ Rn

trong (cid:31)(cid:226) Rn l(cid:160) kh(cid:230)ng gian Euclid n - chi•u v(cid:160)

Trong nhœng n«m gƒn (cid:31)¥y ng(cid:247)(cid:237)i ta tŒng qu¡t th(cid:160)nh b(cid:160)i to¡n: T…m

− sao cho g(¯x) ≥ 0, h(¯x) ≥ 0 v(cid:160) < g(¯x), h(¯x) >= 0. M(cid:246)c (cid:31)‰ch cıa

¯x ∈ Rn

lu“n v«n n(cid:160)y l(cid:160) vi‚t mºt c¡ch tŒng quan v• vi»c gi£i b(cid:160)i to¡n tŁi (cid:247)u v(cid:238)i

r(cid:160)ng buºc tŒng qu¡t nh(cid:247) sau: Cho C ⊆ Rn, t“p (cid:31)(cid:226)ng S1, S2 ⊆ Rn, b(cid:160)i to¡n t…m ˜x ∈ C ∩ ˜S sao cho

ϕ(y), ˜C = C ∩ ˜S, (0.2) ϕ(˜x) = min y∈ ˜C

(cid:110)

(cid:111)

trong (cid:31)(cid:226) C l(cid:160) t“p (cid:31)(cid:226)ng, l(cid:231)i trong kh(cid:230)ng gian Euclid Rn, ˜S = ˜S1 ∩ ˜S2 v(cid:160)

x ∈ Rn : ˜g(x) ≤ 0, ˜h(x) = 0 , (0.3) ˜S1 = ˜S2 = {x ∈ Rn : g(x) ≤ 0, h(x) ≤ 0, (cid:104)g(x), h(x)(cid:105)Rq = 0}

c¡c h(cid:160)m th(cid:252)c ϕ : Rn → R, ˜g : Rn → Rm, ˜h : Rn → Rp, g v(cid:160) h: Rn → Rq l(cid:160)

li¶n t(cid:246)c, k(cid:254) hi»u y = (y1, y2, ...., ym) ≤ 0 c(cid:226) ngh(cid:190)a l(cid:160) yi ≤ 0, ∀i = 1, 2, ...n.

Ta gi£ thi‚t nghi»m cıa c¡c b(cid:160)i to¡n (0.1), (0.2) v(cid:160) (0.3) l(cid:160) kh¡c rØng.

Tr(cid:247)(cid:237)ng hæp khi m = n, g(x) = −x, h(x) = −F (x), v(cid:238)i F : Rn → Rn l(cid:160)

¡nh x⁄ affin, ngh(cid:190)a l(cid:160)

F (x) = M x + q, M ∈ Rn×n, q ∈ Rn,

b(cid:160)i to¡n (01) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh, k(cid:254) hi»u b(cid:240)i LCP(q,M).

T…m hi”u nghi»m cıa c¡c b(cid:160)i to¡n tr¶n ta (cid:31)¢ thu (cid:31)(cid:247)æc k‚t qu£ sau.

(cid:30)(cid:224)nh l(cid:254) 0.1. [8] Khi M ∈ Rn×n l(cid:160) P - ma tr“n v(cid:238)i t§t c£ c¡c (cid:31)(cid:224)nh thøc

con ch‰nh cıa M d(cid:247)(cid:236)ng th… LCP(q,M) c(cid:226) mºt nghi»m v(cid:238)i q ∈ Rn.

(cid:30)(cid:224)nh l(cid:254) 0.2. [8] N‚u q kh(cid:230)ng ¥m th… b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh LCP (q, M )

lu(cid:230)n gi£i (cid:31)(cid:247)æc v(cid:160) x = 0 l(cid:160) mºt nghi»m tƒm th(cid:247)(cid:237)ng cıa n(cid:226).

Nghi¶n cøu mŁi quan h» giœa b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh v(cid:160) b(cid:160)i to¡n b§t

(cid:31)ﬂng thøc bi‚n ph¥n, k(cid:254) hi»u b(cid:240)i VI(K,F), l(cid:160) b(cid:160)i to¡n t…m mºt vect(cid:236)

x ∈ K ⊂ Rn sao cho

(cid:104)y − x, F (x)(cid:105) ≥ 0, ∀y ∈ K

(cid:240) (cid:31)¥y F : K → Rn l(cid:160) h(cid:160)m li¶n t(cid:246)c v(cid:160) K l(cid:160) t“p (cid:31)(cid:226)ng, l(cid:231)i, ta c(cid:226) th¶m (cid:31)(cid:247)æc

k‚t qu£ sau.

+ th…

(cid:30)(cid:224)nh l(cid:254) 0.3. [8] N‚u F = M x + q, M ∈ Rn×n, q ∈ Rn, x ∈ Rn

+) v(cid:160) b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh LCP(q,M) c(cid:226) nghi»m ho(cid:160)n to(cid:160)n tr(cid:242)ng

VI (F, Rn

nhau.

Tr(cid:247)(cid:237)ng hæp khi n = m, g(x) = −x, h(x) = −F (x) v(cid:238)i F l(cid:160) ¡nh x⁄ phi

tuy‚n tł Rn v(cid:160)o Rn, b(cid:160)i to¡n (0.1) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) b(cid:160)i to¡n b(cid:242) phi tuy‚n, k(cid:254)

hi»u b(cid:240)i NCP(F), (cid:31)(cid:226) l(cid:160) b(cid:160)i to¡n t…m vect(cid:236) x ∈ Rn sao cho

x ≥ 0, F (x) ≥ 0, (cid:104)x, F (x)(cid:105) = 0, (0.4)

hi»n nay c¡c nh(cid:160) khoa h(cid:229)c (cid:31)¢ t…m ra r§t nhi•u ph(cid:247)(cid:236)ng ph¡p gi£i cho c¡c

lo⁄i b(cid:160)i to¡n n(cid:160)y. T§t c£ c¡c ph(cid:247)(cid:236)ng ph¡p (cid:31)(cid:247)a ra (cid:31)•u d¤n t(cid:238)i gi£i mºt b(cid:160)i

to¡n c(cid:252)c ti”u ho(cid:176)c mºt h» ph(cid:247)(cid:236)ng tr…nh t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng.

Nhi»m v(cid:246) cıa lu“n v«n l(cid:160) gi£i b(cid:160)i to¡n tŁi (cid:247)u v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n

b(cid:242) tŒng qu¡t b‹ng ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh. Tr(cid:247)(cid:238)c h‚t ta nh›c l⁄i mºt sŁ

ph(cid:247)(cid:236)ng ph¡p gi£i b(cid:160)i to¡n b(cid:242) tŒng qu¡t tr¶n.

1. Ph(cid:247)(cid:236)ng ph¡p sß d(cid:246)ng h(cid:160)m kho£ng

(cid:222) t(cid:247)(cid:240)ng cıa ph(cid:247)(cid:236)ng ph¡p n(cid:160)y l(cid:160) bi‚n (cid:31)Œi b(cid:160)i to¡n b(cid:242) phi tuy‚n NCP(F)

v• b(cid:160)i to¡n tŁi (cid:247)u qua vi»c sß d(cid:246)ng c¡c h(cid:160)m kho£ng. C(cid:230)ng c(cid:246) thu“n ti»n

(cid:31)” thi‚t l“p h(cid:160)m kho£ng l(cid:160) C - h(cid:160)m, (cid:31)(cid:226) l(cid:160) h(cid:160)m φ : R2 → R th(cid:228)a m¢n c¡c

t‰nh ch§t:

φ(a, b) = 0 ⇔ ab = 0, a ≥ 0, b ≥ 0.

Ta c(cid:226) mºt sŁ C - h(cid:160)m sau:

1. φN R (a, b) = min {a, b} ;

2α(max{0, a − αb}2 − a2 +max {0, b − αa}2 − b2), α >

2. φM S (a, b) = ab + 1

√ a2 + b2 − a − b. 3. φF B (a, b) =

H(cid:160)m kho£ng (cid:31)(cid:247)æc x¥y d(cid:252)ng tr¶n h(cid:160)m φN R (cid:31)(cid:247)æc g(cid:229)i l(cid:160) h(cid:160)m sŁ d(cid:247) t(cid:252) nhi¶n.

H(cid:160)m φF B kh(cid:230)ng ¥m tr¶n R2 v(cid:160) h(cid:160)m kho£ng (cid:31)(cid:247)æc x¥y d(cid:252)ng tr¶n n(cid:226) g(cid:229)i l(cid:160)

h(cid:160)m Lagrange 'n (cid:31)(cid:247)æc (cid:31)(cid:247)a v(cid:160)o b(cid:240)i c¡c nh(cid:160) khoa h(cid:229)c nh(cid:247) Mangasarian v(cid:160)

Solodov. H(cid:160)m φF B (cid:31)(cid:247)æc g(cid:229)i l(cid:160) h(cid:160)m Fischer. Gƒn (cid:31)¥y, d(cid:252)a tr¶n h(cid:160)m φF B

nhi•u nh(cid:160) khoa h(cid:229)c (cid:31)¢ m(cid:240) rºng nghi¶n cøu v(cid:160) (cid:31)(cid:247)a ra mºt sŁ h(cid:160)m m(cid:238)i c(cid:226)

n (cid:88)

t‰nh ch§t tŁt h(cid:236)n. Luo v(cid:160) Tseng (cid:31)¢ (cid:31)(cid:247)a ra mºt l(cid:238)p c¡c h(cid:160)m kho£ng m(cid:238)i ˜f : Rn → R x¡c (cid:31)(cid:224)nh b(cid:240)i

i=1

ψi (−xi, −Fi), ˜f (x) = ψ0 ((cid:104)x, F (x)(cid:105)Rn) +

(cid:240) (cid:31)¥y ψ0 :→ [0, ∞) v(cid:160) ψi : R2 → [0, ∞) , i = 1, 2, ..., n l(cid:160) c¡c h(cid:160)m li¶n t(cid:246)c.

(cid:222) t(cid:247)(cid:240)ng m(cid:238)i n(cid:160)y (cid:31)(cid:247)æc Kanzow C., Yamashita N. v(cid:160) Fukushima M. [10] sß

d(cid:246)ng (cid:31)” x¥y d(cid:252)ng h(cid:160)m kho£ng m(cid:238)i.

2. Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh

Ta sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov b‹ng c¡ch nhi„u h(cid:160)m ban

(cid:31)ƒu th(cid:160)nh mºt d¢y c¡c b(cid:160)i to¡n (cid:31)(cid:176)t ch¿nh. L(cid:247)æc (cid:31)(cid:231) hi»u ch¿nh Tikhonov

trong [5], [6] (cid:31)Łi v(cid:238)i b(cid:160)i to¡n b(cid:242) bao g(cid:231)m vi»c gi£i d¢y c¡c b(cid:160)i to¡n:

(0.5) x ≥ 0, Fε(x) ≥ 0, (cid:104)x, Fε(x)(cid:105)Rn = 0,

(cid:240) (cid:31)¥y, Fε(x) = F (x) + εx v(cid:160) ε l(cid:160) tham sŁ d(cid:247)(cid:236)ng hºi t(cid:246) t(cid:238)i 0.

3. Ph(cid:247)(cid:236)ng ph¡p k‚t hæp h(cid:160)m kho£ng v(cid:160) hi»u ch¿nh

Rn+1, (cid:31)(cid:247)æc x¥y d(cid:252)ng b(cid:240)i

(cid:30)” gi£i b(cid:160)i to¡n ta d(cid:252)a tr¶n h(cid:160)m H l(cid:160) h(cid:160)m (cid:31)i tł kh(cid:230)ng gian Rn+1 t(cid:238)i

H (ε, z) = 0 ⇔ ε = 0, x ∈ S0, (0.6)

trong (cid:31)(cid:226) S0 l(cid:160) t“p nghi»m cıa (0.4),

z := (ε, x) ∈ R × Rn, H(ε, z) := (cid:104)ε, G(ε, z)(cid:105)

v(cid:160) h(cid:160)m kho£ng G : Rn+1 → Rn, v(cid:238)i

Gi(ε, x) := φ(xi, Fε,i(x)), i = 1, 2, ..., n,

trong (cid:31)(cid:226) φ(.) l(cid:160) h(cid:160)m Fischer, Fε,i l(cid:160) th(cid:160)nh phƒn thø i cıa Fε.

S(cid:252) hºi t(cid:246) cıa nghi»m hi»u ch¿nh (cid:31)Łi v(cid:238)i (0.5) v(cid:160) (0.6) ch¿ (cid:31)(cid:247)æc thi‚t l“p

trong tr(cid:247)(cid:237)ng hæp F l(cid:160) (cid:31)(cid:236)n (cid:31)i»u ho(cid:176)c P0 - h(cid:160)m. H(cid:236)n nœa, tŁc (cid:31)º hºi t(cid:246) cıa

nghi»m hi»u ch¿nh v¤n ch(cid:247)a (cid:31)(cid:247)æc xem x†t.

Trong [3], N. B(cid:247)(cid:237)ng (cid:31)¢ sß d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov (cid:31)”

bi‚n (cid:31)Œi b(cid:160)i to¡n (0.2) th(cid:160)nh b(cid:160)i to¡n kh(cid:230)ng r(cid:160)ng buºc. Ti‚p nŁi v(cid:238)i (cid:254)

t(cid:247)(cid:240)ng tr¶n trong lu“n v«n n(cid:160)y, ch(cid:243)ng t(cid:230)i (cid:31)¢ nghi¶n cøu ph(cid:247)(cid:236)ng ph¡p gi£i

b(cid:160)i to¡n c(cid:252)c tr(cid:224) trong tr(cid:247)(cid:237)ng hæp b(cid:160)i to¡n c(cid:226) r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242)

tŒng qu¡t.

Nh(cid:247) v“y, trong nhœng tr(cid:247)(cid:237)ng hæp (cid:31)(cid:176)c bi»t, b(cid:160)i to¡n b(cid:242) c(cid:226) nhi•u ph(cid:247)(cid:236)ng

ph¡p gi£i kh¡c nhau. Tuy nhi¶n, c¡c k‚t qu£ (cid:31)(cid:247)a ra (cid:31)•u (cid:31)Æi h(cid:228)i c¡c h(cid:160)m

trong b(cid:160)i to¡n ph£i c(cid:226) t‰nh ch§t (cid:31)(cid:236)n (cid:31)i»u ho(cid:176)c l(cid:160) P0 - h(cid:160)m. M(cid:176)t kh¡c, (cid:31)Łi

v(cid:238)i b(cid:160)i to¡n b(cid:242) tŒng qu¡t, ch(cid:247)a c(cid:226) thu“t to¡n hi»u ch¿nh. Ch‰nh v… v“y,

lu“n v«n n(cid:160)y t“p trung nghi¶n cøu ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh b(cid:160)i to¡n b(cid:242)

tŒng qu¡t nh‹m kh¡c ph(cid:246)c nhœng nh(cid:247)æc (cid:31)i”m tr¶n. Ch(cid:243)ng t(cid:230)i (cid:31)¢ ti‚p c“n

b(cid:160)i to¡n theo h(cid:247)(cid:238)ng kh¡c v(cid:160) (cid:31)(cid:247)a ra mºt sŁ ph(cid:247)(cid:236)ng ph¡p gi£i b(cid:160)i to¡n n(cid:160)y.

Ph(cid:247)(cid:236)ng ph¡p m(cid:238)i y¶u cƒu h(cid:160)m g(x) v(cid:160) h(x) ph£i c(cid:226) t‰nh ch§t P0 - h(cid:160)m.

Thu“t to¡n hi»u ch¿nh d¤n t(cid:238)i c(cid:252)c ti”u mºt phi‚m h(cid:160)m ph(cid:246) thuºc tham

sŁ nh(cid:247)ng kh(cid:230)ng r(cid:160)ng buºc, do (cid:31)(cid:226) b(cid:160)i to¡n tr(cid:240) n¶n (cid:31)(cid:236)n gi£n h(cid:236)n r§t nhi•u.

C¡c k‚t qu£ (cid:31)(cid:247)æc gi(cid:238)i thi»u trong lu“n v«n bao g(cid:231)m:

1. Tr…nh b(cid:160)y thu“t to¡n hi»u ch¿nh cho b(cid:160)i to¡n b(cid:242) tŒng qu¡t;

2. Tr…nh b(cid:160)y thu“t to¡n hi»u ch¿nh cho b(cid:160)i to¡n tŁi (cid:247)u v(cid:238)i r(cid:160)ng buºc l(cid:160)

b(cid:160)i to¡n b(cid:242) tŒng qu¡t;

3. Minh h(cid:229)a c¡c ph(cid:247)(cid:236)ng ph¡p (cid:31)(cid:247)a ra b‹ng b(cid:160)i to¡n c(cid:246) th”.

Ngo(cid:160)i phƒn m(cid:240) (cid:31)ƒu, k‚t lu“n v(cid:160) danh m(cid:246)c c¡c t(cid:160)i li»u tham kh£o, lu“n

v«n (cid:31)(cid:247)æc bŁ c(cid:246)c g(cid:231)m hai ch(cid:247)(cid:236)ng.

Ch(cid:247)(cid:236)ng 1 c(cid:226) t‰nh ch§t bŒ træ, tr…nh b(cid:160)y s(cid:236) l(cid:247)æc v• mºt sŁ v§n (cid:31)• c(cid:226)

li¶n quan nh(cid:247): Kh(cid:230)ng gian vect(cid:236) Euclid Rn, P0 - h(cid:160)m, P - h(cid:160)m, P - h(cid:160)m

(cid:31)•u, h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u, h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u m⁄nh, P0 - ma tr“n, P - ma tr“n; gi(cid:238)i

thi»u b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh v(cid:160) ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho

b(cid:160)i to¡n c(cid:252)c tr(cid:224) tŒng qu¡t. Ch(cid:247)(cid:236)ng 1 c(cid:244)ng tr…nh b(cid:160)y kh¡i ni»m v• b(cid:160)i to¡n

b(cid:242) tuy‚n t‰nh, b(cid:160)i to¡n b(cid:242) phi tuy‚n v(cid:160) mºt sŁ ph(cid:247)(cid:236)ng ph¡p gi£i c¡c b(cid:160)i

to¡n n(cid:160)y.

Ch(cid:247)(cid:236)ng 2 tr…nh b(cid:160)y b(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng

qu¡t, bao g(cid:231)m: (cid:31)(cid:224)nh ngh(cid:190)a v(cid:160) mºt sŁ k‚t qu£ nghi¶n cøu gƒn (cid:31)¥y; ph(cid:247)(cid:236)ng

ph¡p hi»u ch¿nh Tikhonov cho b(cid:160)i to¡n n(cid:160)y v(cid:160) mºt sŁ (cid:31)(cid:224)nh l(cid:254) chøng minh

s(cid:252) t(cid:231)n t⁄i nghi»m. CuŁi ch(cid:247)(cid:236)ng l(cid:160) v‰ d(cid:246) minh h(cid:229)a cho ph(cid:247)(cid:236)ng ph¡p hi»u

ch¿nh Tikhonov.

Ch(cid:247)(cid:236)ng 1

Mºt sŁ ki‚n thøc chu'n b(cid:224)

Trong ch(cid:247)(cid:236)ng n(cid:160)y, ch(cid:243)ng t(cid:230)i tr…nh b(cid:160)y mºt sŁ kh¡i ni»m v(cid:160) k‚t qu£ quen

bi‚t v• c¡c ph(cid:247)(cid:236)ng ph¡p gi£i b(cid:160)i to¡n b(cid:242) nh(cid:247) ph(cid:247)(cid:236)ng ph¡p sß d(cid:246)ng h(cid:160)m

kho£ng, ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh, v(cid:160) c¡c ki‚n thøc v• b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng

ch¿nh, ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov. Mºt sŁ kh¡i ni»m trong ch(cid:247)(cid:236)ng

n(cid:160)y (cid:31)(cid:247)æc tr…nh b(cid:160)y d(cid:252)a tr¶n c¡c t(cid:160)i li»u [2] v(cid:160) [16].

1.1 Mºt sŁ ki‚n thøc c(cid:236) b£n

(cid:30)(cid:224)nh ngh(cid:190)a 1.1. Cho V l(cid:160) mºt kh(cid:230)ng gian vector tr¶n tr(cid:247)(cid:237)ng R. T‰ch v(cid:230) h(cid:247)(cid:238)ng tr¶n V l(cid:160) mºt ¡nh x⁄ (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh nh(cid:247) sau:

(cid:104)., .(cid:105) : V × V → R,

(x, y) (cid:55)→< x, y >

th(cid:228)a m¢n c¡c (cid:31)i•u ki»n sau:

i). (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105) , ∀x, y ∈ V ;

ii). (cid:104)x + y, z(cid:105) = (cid:104)x, y(cid:105) + (cid:104)y, z(cid:105) , ∀x, y, z ∈ V ;

iii). (cid:104)λx, y(cid:105) = λ (cid:104)x, y(cid:105) , ∀λ ∈ R; ∀x, y ∈ V ;

iv). (cid:104)x, x(cid:105) ≥ 0, ∀x ∈ V, (cid:104)x, x(cid:105) = 0 ⇔ x = 0.

(cid:104)x, y(cid:105) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) t‰ch v(cid:230) h(cid:247)(cid:238)ng cıa hai vect(cid:236) x v(cid:160) y.

R c(cid:242)ng v(cid:238)i t‰ch v(cid:230) h(cid:247)(cid:238)ng n(cid:160)y (cid:31)(cid:247)æc g(cid:229)i l(cid:160) kh(cid:230)ng gian ti•n Hilbert. Ti‚p theo ta (cid:31)(cid:247)a ra mºt sŁ (cid:31)(cid:224)nh ngh(cid:190)a v• ¡nh x⁄ tł Rn v(cid:160)o Rn.

(cid:30)(cid:224)nh ngh(cid:190)a 1.2. (cid:129)nh x⁄ F : Rn → Rn (cid:31)(cid:247)æc g(cid:229)i l(cid:160):

• P0 - h(cid:160)m n‚u v(cid:238)i m(cid:229)i x, y ∈ Rn, x (cid:54)= y t(cid:231)n t⁄i mºt ch¿ sŁ i sao cho

xi (cid:54)= yi,

(xi − yi)(Fi(x) − Fi(y)) ≥ 0;

• P - h(cid:160)m n‚u v(cid:238)i m(cid:229)i x, y ∈ Rn, x (cid:54)= y t(cid:231)n t⁄i mºt ch¿ sŁ i sao cho

xi (cid:54)= yi,

(xi − yi)(Fi(x) − Fi(y)) > 0;

• P - h(cid:160)m (cid:31)•u n‚u t(cid:231)n t⁄i mºt h‹ng sŁ d(cid:247)(cid:236)ng µ sao cho v(cid:238)i m(cid:229)i x, y ∈ Rn

t(cid:231)n t⁄i mºt ch¿ sŁ i sao cho

(xi − yi) (Fi(x) − Fi(y)) ≥ µ(cid:107)x − y(cid:107)2;

• H(cid:160)m (cid:31)(cid:236)n (cid:31)i»u n‚u v(cid:238)i m(cid:229)i x, y ∈ Rn,

(cid:104)x − y, F (x) − F (y)(cid:105) ≥ 0;

• H(cid:160)m (cid:31)(cid:236)n (cid:31)i»u m⁄nh n‚u v(cid:238)i m(cid:229)i x, y ∈ Rn v(cid:160) µ >0 cŁ (cid:31)(cid:224)nh:

(cid:104)x − y, F (x) − F (y)(cid:105) ≥ µ(cid:107)x − y(cid:107)2.

Tł c¡c (cid:31)(cid:224)nh ngh(cid:190)a tr¶n ta suy ra h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u l(cid:160) P0 - h(cid:160)m v(cid:160) h(cid:160)m (cid:31)(cid:236)n

(cid:31)i»u m⁄nh l(cid:160) P - h(cid:160)m (cid:31)•u.

V(cid:238)i ma tr“n ta c(cid:226) (cid:31)(cid:224)nh ngh(cid:190)a sau

(cid:30)(cid:224)nh ngh(cid:190)a 1.3. Ma tr“n M ∈ Rn×n (cid:31)(cid:247)æc g(cid:229)i l(cid:160)

• P0 - ma tr“n n‚u v(cid:238)i m(cid:229)i x ∈ Rn, x (cid:54)= 0 t(cid:231)n t⁄i mºt ch¿ sŁ i0 = i0(x)

sao cho

≥ 0; xi0 (cid:54)= 0, xi0[M x]i0

• P - ma tr“n n‚u v(cid:238)i m(cid:229)i x, y ∈ Rn, x (cid:54)= 0

xi[M x]i > 0. max i

1.2 B(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh v(cid:160) ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh

Trong phƒn n(cid:160)y ta (cid:31)• c“p (cid:31)‚n kh¡i ni»m b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh d(cid:247)(cid:238)i

d⁄ng ph(cid:247)(cid:236)ng tr…nh to¡n tß, c(cid:242)ng v(cid:238)i ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov

1.2.1 Kh¡i ni»m b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh

cho l(cid:238)p b(cid:160)i to¡n n(cid:160)y.

Ta tr…nh b(cid:160)y kh¡i ni»m b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh (cid:240) d⁄ng mºt ph(cid:247)(cid:236)ng

tr…nh to¡n tß, c(cid:246) th”:

X†t b(cid:160)i to¡n t…m nghi»m cıa ph(cid:247)(cid:236)ng tr…nh

A(x) = f, (1.1)

trong (cid:31)(cid:226) A l(cid:160) to¡n tß tł kh(cid:230)ng gian m¶tric X v(cid:160)o kh(cid:230)ng gian m¶tric Y

v(cid:238)i c¡c kho£ng c¡ch t(cid:247)(cid:236)ng øng l(cid:160) ρX, ρY v(cid:160) f ∈ Y . Theo Hadamard J. b(cid:160)i

to¡n (1.1) g(cid:229)i l(cid:160) (cid:31)(cid:176)t ch¿nh (ch‰nh quy) n‚u c¡c (cid:31)i•u ki»n sau (cid:31)(cid:247)æc th(cid:228)a

m¢n:

i). ph(cid:247)(cid:236)ng tr…nh (1.1) c(cid:226) nghi»m xf , ∀f ∈ Y ;

ii). nghi»m xf (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh mºt c¡ch duy nh§t;

iii). nghi»m xf ph(cid:246) thuºc li¶n t(cid:246)c v(cid:160)o f .

N‚u ‰t nh§t mºt trong ba (cid:31)i•u ki»n tr¶n kh(cid:230)ng (cid:31)(cid:247)æc th(cid:228)a m¢n th… b(cid:160)i to¡n

(1.1) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh.V(cid:160) (cid:31)” gi£i (cid:31)(cid:247)æc c¡c b(cid:160)i to¡n

d⁄ng n(cid:160)y th… ta cƒn ph(cid:247)(cid:236)ng ph¡p m(cid:238)i.

1.2.2 Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov

Ta tr…nh b(cid:160)y mºt c¡ch s(cid:236) l(cid:247)æc v• ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov, (cid:31)(cid:226)

l(cid:160) (cid:31)” t…m nghi»m x§p x¿ cıa b(cid:160)i to¡n (1.1) khi kh(cid:230)ng bi‚t th(cid:230)ng tin v•

nghi»m ch‰nh x¡c x0, Tikhonov N. A. (cid:31)¢ (cid:31)(cid:247)a ra mºt kh¡i ni»m m(cid:238)i. (cid:30)(cid:247)æc

g(cid:229)i l(cid:160) ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh d(cid:252)a tr¶n vi»c x¥y d(cid:252)ng to¡n tß hi»u ch¿nh

v(cid:160) c¡ch ch(cid:229)n gi¡ tr(cid:224) cıa mºt tham sŁ m(cid:238)i (cid:31)(cid:247)a v(cid:160)o.

Gi£ sß A−1 kh(cid:230)ng li¶n t(cid:246)c v(cid:160) thay cho f ta bi‚t fδ : ρY (fδ, f ) ≤ δ → 0. B(cid:160)i to¡n (cid:31)(cid:176)t ra l(cid:160) d(cid:252)a v(cid:160)o th(cid:230)ng tin v• (A, fδ) v(cid:160) møc sai sŁ δ, t…m mºt

phƒn tß xδ x§p x¿ nghi»m ch‰nh x¡c x0 cıa b(cid:160)i to¡n (1.1). Rª r(cid:160)ng ta kh(cid:230)ng th” x¥y d(cid:252)ng phƒn tß x§p x¿ xδ theo quy t›c xδ = A−1fδ, v… thø nh§t l(cid:160) A−1 c(cid:226) th” kh(cid:230)ng x¡c (cid:31)(cid:224)nh v(cid:238)i m(cid:229)i f ∈ Y , thø hai l(cid:160) A−1 kh(cid:230)ng li¶n t(cid:246)c, n¶n n‚u A−1fδ t(cid:231)n t⁄i, c(cid:244)ng ch(cid:247)a ch›c (cid:31)¢ x§p x¿ A−1f .

Tham sŁ δ ch¿ cho ta møc (cid:31)º sai sŁ v‚ ph£i cıa (1.1). V… v“y mºt (cid:31)i•u

n£y sinh t(cid:252) nhi¶n l(cid:160) li»u c(cid:226) th” x¥y d(cid:252)ng phƒn tß x§p x¿ ph(cid:246) thuºc v(cid:160)o

mºt tham sŁ n(cid:160)o (cid:31)(cid:226) v(cid:160) tham sŁ n(cid:160)y (cid:31)(cid:247)æc ch(cid:229)n t(cid:247)(cid:236)ng th‰ch v(cid:238)i δ sao cho

khi δ → 0 th… phƒn tß x§p x¿ n(cid:160)y hºi t(cid:246) (cid:31)‚n nghi»m x0. Ta c(cid:244)ng th§y n‚u

(cid:31)(cid:247)æc th… tł fδ ∈ Y ta c(cid:226) phƒn tß x§p x¿ thuºc X, tøc l(cid:160) t(cid:231)n t⁄i mºt to¡n

tß n(cid:160)o (cid:31)(cid:226) t¡c (cid:31)ºng tł kh(cid:230)ng gian Y v(cid:160)o kh(cid:230)ng gian X.

Ta c(cid:226) (cid:31)(cid:224)nh ngh(cid:190)a v• to¡n tß hi»u ch¿nh nh(cid:247) sau:

(cid:30)(cid:224)nh ngh(cid:190)a 1.4. To¡n tß R(f, α) ph(cid:246) thuºc tham sŁ α t¡c (cid:31)ºng tł Y v(cid:160)o

X (cid:31)(cid:247)æc g(cid:229)i l(cid:160) mºt to¡n tß hi»u ch¿nh cho b(cid:160)i to¡n (1.1) n‚u:

i). T(cid:231)n t⁄i hai sŁ d(cid:247)(cid:236)ng α1 v(cid:160) δ1 sao cho to¡n tß R(f, α) x¡c (cid:31)(cid:224)nh v(cid:238)i m(cid:229)i

α ∈ (0, α1) v(cid:160) v(cid:238)i m(cid:229)i fδ ∈ Y : ρY (fδ, f ) ≤ δ, δ ∈ (0, δ1);

ii). T(cid:231)n t⁄i mºt s(cid:252) ph(cid:246) thuºc α = α(fδ, f ) sao cho v(cid:238)i m(cid:229)i ε > 0, ∃δ(ε) ≤ δ1

(cid:31)” v(cid:238)i m(cid:229)i fδ ∈ Y th(cid:228)a m¢n ρY (fδ, f ) ≤ δ ≤ δ1 th… ρX(xα, x0) ≤ ε, (cid:240)

(cid:31)¥y x0 l(cid:160) nghi»m ch‰nh x¡c cıa (1.1) v(cid:160) xα ∈ R(fδ, α(fδ, f )).

Phƒn tß xα (cid:31)(cid:247)æc g(cid:229)i l(cid:160) nghi»m hi»u ch¿nh cıa b(cid:160)i to¡n (1.1) v(cid:160) α =

α(fα, δ) g(cid:229)i l(cid:160) tham sŁ hi»u ch¿nh.

Ch(cid:243) (cid:254) 1.1. Tr(cid:247)(cid:237)ng hæp α = δ, (cid:31)(cid:224)nh ngh(cid:190)a v• to¡n tß hi»u ch¿nh c(cid:226) d⁄ng

(cid:31)(cid:236)n gi£n sau;

i). T(cid:231)n t⁄i mºt sŁ d(cid:247)(cid:236)ng δ1 sao cho to¡n tß R(f, δ) x¡c (cid:31)(cid:224)nh v(cid:238)i m(cid:229)i

0 ≤ δ ≤ δ1 v(cid:160) v(cid:238)i m(cid:229)i f ∈ Y sao cho ρY (f, f0) ≤ δ;

ii). V(cid:238)i ε > 0 b§t k…, t(cid:231)n t⁄i δ0 = δ0(ε, fδ) ≤ δ1 sao cho tł ρY = (fδ, f0) ≤

δ ≤ δ0; ρX = (xδ, x0) ≤ ε, (cid:240) (cid:31)¥y xδ ∈ R(fδ, δ).

1.2.3 Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho b(cid:160)i to¡n c(cid:252)c tr(cid:224) tŒng qu¡t

Ch(cid:243) (cid:254) 1.2. To¡n tß hi»u ch¿nh R(fδ, δ) c(cid:226) th” l(cid:160) mºt ¡nh x⁄ (cid:31)a tr(cid:224).

X†t b(cid:160)i to¡n tŁi (cid:247)u phi tuy‚n c(cid:226) r(cid:160)ng buºc nh(cid:247) sau: t…m ˜x ∈ Rn sao cho

(1.2) ϕN (x),

ϕN (˜x) = min x∈S S = {x ∈ Rn : fi(x) = 0, i = 1, 2, ..., m; ˜ϕj(x) ≤ 0, j = 1, 2, ..., N − 1}

(cid:240) (cid:31)¥y fi, i = 1, 2, ...m; ˜ϕj, j = 1, 2, ..., N − 1 v(cid:160) ϕN l(cid:160) nhœng h(cid:160)m li¶n t(cid:246)c x¡c (cid:31)(cid:224)nh trong kh(cid:230)ng gian Euclide Rn. (cid:30)(cid:176)t:

S0 := {x ∈ Rn : fi(x) = 0} , i = 1, 2, ..., m,

(cid:26)

Sj := {x ∈ Rn : ˜ϕj(x) ≤ 0} , j = 1, 2, ..., N − 1, (cid:27)

j=0 Sj. Gi£ sß S0 :=

th… S = ∩N −1 (cid:54)= ∅. ϕN (x) ˜x ∈ S : ϕN (˜x) = min x∈S

Trong tr(cid:247)(cid:237)ng hæp S = Rn, b(cid:160)i to¡n (1.2) l(cid:160) b(cid:160)i to¡n c(cid:252)c tr(cid:224) kh(cid:230)ng r(cid:160)ng

buºc, c(cid:226) ngh(cid:190)a l(cid:160) b(cid:160)i to¡n t…m mºt phƒn tß ˜x ∈ Rn sao cho

(1.3) ϕj (x) , j = 1, 2, ..., N, ϕj(˜x) = min x∈S0

S0 = {x ∈ Rn : F (x) = 0} ,

(cid:240) (cid:31)¥y F (x) = (f1 (x) , ...., fm (x))T .

B(cid:160)i to¡n (1.3) c(cid:226) th” gi£i b‹ng c¡ch x†t b(cid:160)i to¡n tŁi (cid:247)u kh(cid:230)ng r(cid:160)ng buºc:

t…m mºt phƒn tß xα ∈ Rn sao cho

Fα(xα) = min x∈n

N (cid:88)

Fα (x) , α > 0,

Fα (x) = (cid:107)F (x)(cid:107)2

Rm +

Rn ,

j=1

(1.4) αµjϕj (x) + α (cid:107)x − x∗(cid:107)2

0 ≤ µ1 < µ2 < .... < µN < 1, j = 2, 3, ..., N − 1,

(cid:240) (cid:31)¥y, x∗ l(cid:160) phƒn tß n(cid:160)o (cid:31)(cid:226) trong Rn.

Trong [17] b(cid:160)i to¡n (1.4) (cid:31)¢ (cid:31)(cid:247)æc gi£i ra v(cid:160) c(cid:226) mºt nghi»m xα v(cid:238)i mØi α > 0. Kh(cid:230)ng l(cid:160)m m§t t‰nh tŒng qu¡t, c(cid:226) th” gi£ thi‚t ϕN (x) ≥ 0 ∀x ∈ Rn. H(cid:236)n nœa, gi£ sß ϕN c(cid:226) nhœng t“p møc (cid:31)(cid:226)ng, ngh(cid:190)a l(cid:160) {x ∈ Rn : ϕN (x) ≤ c} l(cid:160) (cid:31)(cid:226)ng v(cid:238)i m(cid:229)i c > 0.

Ph¡t tri”n b(cid:160)i to¡n (1.4) ta thu (cid:31)(cid:247)æc c¡c k‚t qu£ sau:

(cid:30)(cid:224)nh l(cid:254) 1.1. ([1]) N‚u αk → 0 khi k → ∞ th… m(cid:229)i d¢y (cid:8)xk(cid:9), (cid:240) (cid:31)¥y xk := xαk l(cid:160) mºt nghi»m cıa (1.4) v(cid:238)i α thay b(cid:240)i αk, c(cid:226) mºt d¢y hºi t(cid:246). Gi(cid:238)i h⁄n cıa m(cid:229)i d¢y con hºi t(cid:246) l(cid:160) nghi»m cıa (1.2). H(cid:236)n nœa, n‚u ˜x l(cid:160)

nghi»m duy nh§t th…

(cid:9) th(cid:228)a m¢n

xk = ˜x. lim k→∞

i , ϕδ j

Trong tr(cid:247)(cid:237)ng hæp {fi, ϕj} (cid:31)(cid:247)æc cho b(cid:240)i c¡c x§p x¿ (cid:8)f δ

(cid:12) ≤ δ, i = 1, 2, ..., m,

i (x)(cid:12)

(cid:12) (cid:12)ϕj (x) − ϕδ

(cid:12) ≤ δ, j = 1, 2, ..., N, ∀x ∈ Rn, δ → 0.

(cid:12) (cid:12)fi (x) − f δ j (x)(cid:12)

c¡c (cid:31)i•u ki»n:

α ∈ Rn sao cho

Fδ

Trong [1] N. B(cid:247)(cid:237)ng (cid:31)¢ x†t b(cid:160)i to¡n tŁi (cid:247)u kh(cid:230)ng r(cid:160)ng buºc nh(cid:247) sau: t…m mºt phƒn tß xδ

α (x) , α > 0, δ ≥ 0,

α(x) = min x∈Rn

N (cid:88)

F δ

Rn ,

(cid:13)F δ (x)(cid:13) 2 Rm + (cid:13)

α(x) = (cid:13) Fδ

j (x) + α (cid:107)x − x∗(cid:107)2

j=1

αµjϕδ (1.5)

α t¡c gi£ (cid:31)¢ chøng minh ti‚p (cid:31)(cid:247)æc k‚t qu£ sau.

Nh(cid:247) (cid:31)¢ n(cid:226)i (cid:240) tr¶n, v(cid:238)i mØi αk > 0 b(cid:160)i to¡n (1.6) c(cid:226) mºt nghi»m x¡c (cid:31)(cid:224)nh b(cid:240)i xδ

(cid:30)(cid:224)nh l(cid:254) 1.2. ([1]) Cho αk, δk → 0, sao cho δk αk {xk} ; xk = xδk

→ 0 khi k → ∞, (cid:240) (cid:31)¥y αk l(cid:160) mºt nghi»m cıa (1.5) v(cid:238)i α, δ t(cid:247)(cid:236)ng øng thay b(cid:240)i αk, δk, c(cid:226) mºt d¢y con hºi t(cid:246). Gi(cid:238)i h⁄n cıa m(cid:229)i d¢y con hºi t(cid:246) l(cid:160) nghi»m cıa

(1.2). H(cid:236)n nœa, n‚u nghi»m ˜x l(cid:160) duy nh§t th…

xk = ˜x. lim k→∞

1.3.1 B(cid:160)i to¡n b(cid:242) tuy‚n t‰nh

1.3 B(cid:160)i to¡n b(cid:242)

Tr(cid:247)(cid:238)c h‚t ta x†t b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh, k(cid:254) hi»u b(cid:240)i LCP (q, M ), l(cid:160) b(cid:160)i

to¡n t…m vect(cid:236) x ∈ Rn sao cho

x ≥ 0, F (x) ≥ 0, (cid:104)x, F (x)(cid:105) = 0,

trong (cid:31)(cid:226) F : Rn → Rn l(cid:160) ¡nh x⁄ affin, ngh(cid:190)a l(cid:160)

F (x) = M x + q, M ∈ Rn×n, q ∈ Rn.

B(cid:160)i to¡n n(cid:160)y c(cid:226) mºt sŁ ph(cid:247)(cid:236)ng ph¡p gi£i nh(cid:247) sau:

1. Ph(cid:247)(cid:236)ng ph¡p Lemke

Hi»n nay c(cid:226) kh¡ nhi•u thu“t to¡n (cid:31)¢ (cid:31)(cid:247)æc (cid:31)• xu§t (cid:31)” gi£i b(cid:160)i to¡n b(cid:242)

tuy‚n t‰nh, nh(cid:247)ng hay sß d(cid:246)ng nh§t l(cid:160) ph(cid:247)(cid:236)ng ph¡p Lemke. Bi‚n c(cid:236) s(cid:240) l(cid:160)

c¡c bi‚n m(cid:160) c¡c vect(cid:236) cºt h» sŁ t(cid:247)(cid:236)ng øng v(cid:238)i ch(cid:243)ng l(cid:160) (cid:31)ºc l“p tuy‚n t‰nh,

c¡c bi‚n cÆn l⁄i l(cid:160) bi‚n phi c(cid:236) s(cid:240). C¡c vect(cid:236) cºt n(cid:160)y t⁄o n¶n mºt c(cid:236) s(cid:240) cıa

h» b(cid:242). C(cid:236) s(cid:240) c(cid:226) th” thay (cid:31)Œi b‹ng c¡ch tr¡o (cid:31)Œi giœa hai bi‚n c(cid:236) s(cid:240) v(cid:160) bi‚n

phi c(cid:236) s(cid:240) cho nhau.

Trong ph(cid:247)(cid:236)ng ph¡p Lemke th… ph†p quay l(cid:160) thu“t ngœ th(cid:247)(cid:237)ng xuy¶n

(cid:31)(cid:247)æc d(cid:242)ng. Ph†p quay l(cid:160) s(cid:252) thay (cid:31)Œi c(cid:236) s(cid:240) b‹ng c¡ch (cid:31)Œi chØ mºt bi‚n phi

c(cid:236) s(cid:240) v(cid:238)i mºt bi‚n c(cid:236) s(cid:240), ngh(cid:190)a l(cid:160) mºt bi‚n phi c(cid:236) s(cid:240) s‡ (cid:31)(cid:247)æc (cid:31)(cid:247)a v(cid:160)o c(cid:236)

s(cid:240) v(cid:160) tr(cid:240) th(cid:160)nh bi‚n c(cid:236) s(cid:240) m(cid:238)i (cid:31)” thay th‚ cho mºt bi‚n c(cid:236) s(cid:240) b(cid:224) (cid:31)(cid:247)a ra

kh(cid:228)i c(cid:236) s(cid:240) v(cid:160) s‡ tr(cid:240) th(cid:160)nh bi‚n phi c(cid:236) s(cid:240) m(cid:238)i.

X†t b(cid:160)i to¡n LCP (q, M ) c(cid:226) d⁄ng: t…m hai vect(cid:236) z, ω ∈ Rn th(cid:228)a m¢n

ω − M z = q, z ≥ 0, ω ≥ 0, (1.6)

(cid:104)z, ω(cid:105) = 0, (1.7)

trong (cid:31)(cid:226) q ∈ Rn v(cid:160) M ∈ Rn×n.

N‚u q ≥ 0 d„ th§y nghi»m cıa b(cid:160)i to¡n l(cid:160) z = 0 v(cid:160) ω = q. Ng(cid:247)æc l⁄i

(tøc l(cid:160) c(cid:226) qi < 0 v(cid:238)i i n(cid:160)o (cid:31)(cid:226)), th… th¶m v(cid:160)o mºt bi‚n gi£ z0 v(cid:160) x†t b(cid:160)i

to¡n b(cid:242) suy rºng

(1.8) ω − M z − ez0 = q,

(1.9) z0 ≥, zj ≥ 0, ωj ≥ 0, j = 1, ..., n,

(1.10) zjωj = 0, ∀j = 1, 2, ..., n,

trong (cid:31)(cid:226) e ∈ Rn l(cid:160) vect(cid:236) v(cid:238)i m(cid:229)i th(cid:160)nh phƒn b‹ng 1. Ta g(cid:229)i (1.9) l(cid:160) (cid:31)i•u

ki»n kh(cid:230)ng ¥m v(cid:160) (1.10) l(cid:160) (cid:31)i•u ki»n b(cid:242).

(cid:222) t(cid:247)(cid:240)ng ph(cid:247)(cid:236)ng ph¡p Lemke nh(cid:247) sau: (cid:31)(cid:176)t

z0 = max {−qi : 1 ≤ i ≤ n} > 0, z = 0, ω = q + ez0,

nh“n (cid:31)(cid:247)æc nghi»m (b(cid:242) kh(cid:230)ng ¥m) ban (cid:31)ƒu cıa h» m(cid:240) rºng (1.8) - (1.9).

Th(cid:252)c hi»n mºt d¢y ph†p xoay t(cid:247)(cid:236)ng t(cid:252) nh(cid:247) c¡c ph†p bi‚n (cid:31)Œi (cid:31)(cid:236)n h…nh,

(cid:31)(cid:247)a nghi»m b(cid:242) kh(cid:230)ng ¥m ban (cid:31)ƒu v• nghi»m b(cid:242) kh(cid:230)ng ¥m v(cid:238)i bi‚n gi£

z0 = 0. Khi (cid:31)(cid:226) s‡ nh“n (cid:31)(cid:247)æc nghi»m cıa b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh LCP(q,M).

BŒ (cid:31)• sau (cid:31)(cid:247)æc chøng minh tr(cid:252)c ti‚p tł (cid:31)(cid:224)nh ngh(cid:190)a cıa b(cid:160)i to¡n.

BŒ (cid:31)• 1.1. ([15]) N‚u z0, z, ω l(cid:160) mºt nghi»m cıa b(cid:160)i to¡n suy rºng (1.8)

- (1.9) v(cid:238)i z0 = 0 th… z, ω s‡ l(cid:160) mºt nghi»m cıa b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh ban

(cid:31)ƒu LCP(q,M).

(cid:30)(cid:224)nh ngh(cid:190)a 1.5. Ta n(cid:226)i (z0, z, ω) ∈ R1+2n l(cid:160) mºt nghi»m ch§p nh“n (cid:31)(cid:247)æc

c(cid:236) s(cid:240) gƒn b(cid:242) cıa h» (1.8) - (1.10) n‚u

i). (z0, z, ω) l(cid:160) mºt nghi»m ch§p nh“n (cid:31)(cid:247)æc c(cid:236) s(cid:240) cıa h» (1.8) - (1.10);

ii). c(cid:226) ch¿ sŁ s ∈ {1, 2, ..., n} sao cho c£ hai bi‚n zs v(cid:160) ωs (cid:31)•u l(cid:160) bi‚n phi

c(cid:236) s(cid:240);

iii). z0 l(cid:160) bi‚n phi c(cid:236) s(cid:240) v(cid:160) c(cid:226) (cid:31)(cid:243)ng mºt bi‚n trong mØi c(cid:176)p b(cid:242) nhau (zj; ωj)

l(cid:160) bi‚n c(cid:236) s(cid:240) v(cid:238)i m(cid:229)i j = 1, 2, ..., n v(cid:160) j (cid:54)= s.

(cid:30)(cid:224)nh ngh(cid:190)a 1.6. Cho mºt nghi»m ch§p nh“n (cid:31)(cid:247)æc c(cid:236) s(cid:240) gƒn b(cid:242) (z0, z, ω),

trong (cid:31)(cid:226) c£ hai zs v(cid:160) ωs l(cid:160) bi‚n phi c(cid:236) s(cid:240). N‚u nghi»m ch§p nh“n (cid:31)(cid:247)æc c(cid:236)

s(cid:240) gƒn b(cid:242) (ˆz0, ˆz, ˆω) nh“n (cid:31)(cid:247)æc tł (z0, z, ω) b‹ng c¡ch (cid:31)(cid:247)a zs ho(cid:176)c ωs v(cid:160)o c(cid:236)

s(cid:240) cho ph†p bi‚n (cid:31)Œi h» (1.8) theo c(cid:236) s(cid:240) m(cid:238)i (g(cid:229)i l(cid:160) ph†p quay) (cid:31)'y mºt

bi‚n kh¡c z0 ra kh(cid:228)i c(cid:236) s(cid:240) th… nghi»m (cid:31)(cid:226) s‡ (cid:31)(cid:247)æc g(cid:229)i l(cid:160) nghi»m ch§p nh“n

(cid:31)(cid:247)æc c(cid:236) s(cid:240) gƒn b(cid:242) k• (z0, z, ω).

Thu“t to¡n Lemke gi£i b(cid:160)i to¡n LCP(q, M) g(cid:231)m c¡c thı t(cid:246)c sau:

Kh(cid:240)i s(cid:252) : N‚u q ≥ 0 th… dłng thu“t to¡n:(z, ω) = (0, q) l(cid:160) nghi»m ch§p

nh“n (cid:31)(cid:247)æc c(cid:236) s(cid:240) b(cid:242) cıa LCP(q, M). Ng(cid:247)æc l⁄i, ghi c¡c h» sŁ cıa h» ph(cid:247)(cid:236)ng

tr…nh x¡c (cid:31)(cid:224)nh theo (1.8) v(cid:160)o mºt b£ng chœ nh“t (nh(cid:247) b£ng (cid:31)(cid:236)n h…nh). Gi£

sß −qs = max {−qi : i = 1, 2, ..., n} > 0. (cid:129)p d(cid:246)ng "quy t›c h…nh chœ nh“t"

v(cid:160) bi‚n (cid:31)Œi b£ng nh(cid:247) v“y g(cid:229)i l(cid:160) ph†p quay theo tr(cid:246) (ωs, z0). Nh(cid:247) v“y, c¡c

bi‚n c(cid:236) s(cid:240) z0 v(cid:160) ωj v(cid:238)i m(cid:229)i j = 1, 2, ..., n, i (cid:54)= j (cid:31)•u kh(cid:230)ng ¥m. (cid:30)(cid:176)t ys = zs

r(cid:231)i chuy”n sang th(cid:252)c hi»n vÆng l(cid:176)p ch‰nh, g(cid:231)m c¡c b(cid:247)(cid:238)c sau:

B(cid:247)(cid:238)c 1: Gi£ sß ds l(cid:160) cºt trong b£ng nh“n (cid:31)(cid:247)æc t(cid:247)(cid:236)ng øng v(cid:238)i cºt bi‚n ys.

(cid:27)

N‚u ds ≤ 0 th… chuy”n sang b(cid:247)(cid:238)c 4. Ng(cid:247)æc l⁄i, x¡c (cid:31)(cid:224)nh ch¿ sŁ h(cid:160)ng r nh(cid:237) ki”m tra t¿ sŁ nh(cid:228) nh§t d(cid:247)(cid:238)i (cid:31)¥y, trong (cid:31)(cid:226) ˜d l(cid:160) cºt h» sŁ (cid:240) v‚ ph£i cıa h» (1.9)

(cid:26) ˜qi dis

. : dis > 0 = min 1≤i≤n ˜qr drs

N‚u bi‚n c(cid:236) s(cid:240) (cid:240) h(cid:160)ng r l(cid:160) z0 th… chuy”n sang b(cid:247)(cid:238)c 3. Ng(cid:247)æc l⁄i, chuy”n

sang b(cid:247)(cid:238)c 2.

B(cid:247)(cid:238)c 2: Gi£ sß bi‚n c(cid:236) s(cid:240) h(cid:160)ng r l(cid:160) zh ho(cid:176)c ωh v(cid:238)i ch¿ sŁ h n(cid:160)o (cid:31)(cid:226) kh¡c

s. (cid:30)(cid:247)a bi‚n ys v(cid:160)o c(cid:236) s(cid:240) v(cid:160) bi‚n (cid:31)Œi b£ng theo phƒn tß tr(cid:246) (cid:240) h(cid:160)ng r v(cid:160) cºt

ys. N‚u bi‚n ωh b(cid:224) lo⁄i kh(cid:228)i c(cid:236) s(cid:240) th… (cid:31)(cid:176)t ys = zh, cÆn n‚u bi‚n zh b(cid:224) lo⁄i

kh(cid:228)i c(cid:236) s(cid:240) th… (cid:31)(cid:176)t ys = ωh. Quay l⁄i b(cid:247)(cid:238)c 1.

B(cid:247)(cid:238)c 3: L(cid:243)c n(cid:160)y (cid:31)(cid:247)a bi‚n ys v(cid:160)o c(cid:236) s(cid:240) v(cid:160) lo⁄i kh(cid:228)i c(cid:236) s(cid:240) bi‚n z0. Sau khi

bi‚n (cid:31)Œi b£ng theo phƒn tß tr(cid:246) (cid:240) h(cid:160)ng z0 v(cid:160) cºt ys ta s‡ nh“n (cid:31)(cid:247)æc nghi»m

ch§p nh“n (cid:31)(cid:247)æc c(cid:236) s(cid:240) b(cid:242) cıa b(cid:160)i to¡n LCP(q,M). Dłng thu“t to¡n.

B(cid:247)(cid:238)c 4: Dłng (cid:240) tia R = {(z0, z, ω) + λd : λ ≥ 0} c(cid:226) t‰nh ch§t: mØi (cid:31)i”m tr¶n tia R (cid:31)•u th(cid:228)a m¢n (1.8) - (1.10), c(cid:246) th” l(cid:160) v†ct(cid:236) d ∈ R1+2n c(cid:226) phƒn tß (cid:240) h(cid:160)ng t(cid:247)(cid:236)ng øng v(cid:238)i ys b‹ng 1, phƒn tß kh¡c b‹ng 0.

Trong tr(cid:247)(cid:237)ng hæp LCP (q, M ) kh(cid:230)ng suy bi‚n nh(cid:160) khoa h(cid:229)c Olsson D .

[15] (cid:31)¢ chøng minh (cid:31)(cid:247)æc.

(cid:30)(cid:224)nh l(cid:254) 1.3. N‚u M l(cid:160) P - ma tr“n th… ph(cid:247)(cid:236)ng ph¡p Lemke s‡ lu(cid:230)n gi£i

(cid:31)(cid:247)æc v(cid:238)i b§t k(cid:253) LCP (q, M ) kh(cid:230)ng suy bi‚n.

2. Ph(cid:247)(cid:236)ng ph¡p d(cid:252) (cid:31)o¡n v(cid:160) hi»u ch¿nh

(cid:30)” gi£i b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh (cid:31)(cid:236)n (cid:31)i»u, Burke J. v(cid:160) Xu S.[3] (cid:31)¢ x†t b(cid:160)i

to¡n b(cid:242) tuy‚n t‰nh: t…m (x, y) ∈ Rn × Rn th(cid:228)a m¢n

M x − y + q = 0,

x ≥ 0, y ≥ 0, (cid:104)x, y(cid:105) = 0,

(cid:240) (cid:31)¥y M ∈ Rn × Rn l(cid:160) nßa x¡c (cid:31)(cid:224)nh d(cid:247)(cid:236)ng v(cid:160) q ∈ Rn.

Ta c(cid:226)

C = (cid:8)(x, y) : 0 < µ, 0 < x, 0 < y, M x − y + q = 0, Xy = µ2e(cid:9) ,

(cid:31)(cid:247)æc g(cid:229)i l(cid:160) qu(cid:255) (cid:31)⁄o trung t¥m. v(cid:238)i e ∈ Rn l(cid:160) vect(cid:236) m(cid:160) m(cid:229)i th(cid:160)nh phƒn cıa n(cid:226) l(cid:160) 1 v(cid:160) X l(cid:160) ma tr“n ch†o m(cid:160) m(cid:229)i phƒn tß n‹m tr¶n (cid:31)(cid:247)(cid:237)ng ch†o (cid:31)(cid:247)æc cho b(cid:240)i vector x ∈ Rn. Burke

J. v(cid:160) Xu S [3] (cid:31)¢ gi£i b(cid:160)i to¡n LCP(q,M) trong tr(cid:247)(cid:237)ng hæp (cid:31)(cid:236)n (cid:31)i»u b‹ng

(cid:113)

c¡ch x¥y d(cid:252)ng h(cid:160)m

φ (a, b, µ) = a + b − (a + b)2 + 4µ2, (1.11)

D„ th§y

φ (a, b, µ) = 0 ⇔ a ≥ 0, b ≥ 0, ab = µ2.

(cid:222) t(cid:247)(cid:240)ng ch‰nh cıa thu“t to¡n l(cid:160) ¡p d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p Newton gi£i h»

ph(cid:247)(cid:236)ng tr…nh c(cid:226) d⁄ng F (x, y, µ) = ν, (cid:240) (cid:31)¥y h(cid:160)m

F : Rn × Rn × R++ → Rn × Rn × R++,



x¡c (cid:31)(cid:224)nh b(cid:240)i

  ,



F (x, y, µ) :=

M x − y + q φ(x, y, µ) mu



v(cid:238)i

  .



φ(x, y, µ) :=

φ(x1, y1, µ) ... φ(xn, yn, µ)

Ch(cid:243) (cid:254) 1.3.

F (x, y, µ) = 0



khi v(cid:160) ch¿ khi (x , y) l(cid:160) nghi»m cıa LCP(q, M), v(cid:160)

  , ¯µ (cid:54)= 0



F (x, y, µ) :=

0 0 ¯µ

khi v(cid:160) ch¿ khi (x , y) n‹m tr¶n qu(cid:255) (cid:31)⁄o trung t¥m C v(cid:238)i tham sŁ tr(cid:236)n t(cid:247)(cid:236)ng

øng ¯µ.

K(cid:254) hi»u qu(cid:255) (cid:31)⁄o trung t¥m l(cid:160)

N(β) := {(x, y) |M x − y + q = 0, φ (x, y, µ) ≤ 0, (cid:107)φ (x, y, µ)(cid:107) ≤ βµ, µ > 0} ,

(cid:240) (cid:31)¥y β > 0 cho tr(cid:247)(cid:238)c. L¥n c“n n(cid:160)y c(cid:226) th” xem l(cid:160) hæp cıa t§t c£ c¡c l¡t

c›t

N(β, µ) := {(x, y) |M x − y + q = 0, φ (x, y, µ) ≤ 0, (cid:107)φ (x, y, µ)(cid:107) ≤ βµ, µ > 0} ,

Ta c(cid:226) thu“t to¡n d(cid:252) (cid:31)o¡n v(cid:160) hi»u ch¿nh (cid:31)” gi£i b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh

(cid:31)(cid:236)n (cid:31)i»u nh(cid:247) sau.

(cid:1) < (cid:1)(cid:13) (cid:13) ≤ βµ0, nh(cid:247) v“y (cid:0)x0, y0(cid:1) ∈

√ 1. Thu“t to¡n 1 B(cid:247)(cid:238)c 1: Ch(cid:229)n x0 ∈ Rn, (cid:31)(cid:176)t k := 0, y0 = M x0 + q, µ0 > 0 : φ (cid:0)x0, y0, µ0 (cid:13)φ (cid:0)x0, y0, µ0 0. Ch(cid:229)n β > 2



(cid:1)T

n sao cho (cid:13) N (β, µ0) ch(cid:229)n ti‚p ¯σ, α1, α2 trong kho£ng (0,1). B(cid:247)(cid:238)c 2: (∆xk, ∆yk, µk) l(cid:160) nghi»m cıa ph(cid:247)(cid:236)ng tr…nh

(cid:1) + ∇F (cid:0)xk, yk, µk

  = 0.



F (cid:0)xk, yk, µk

(cid:13) = 0 th… dłng, (cid:0)xk + ∆xk, yk + ∆yk(cid:1) l(cid:160) (cid:13)φ(xk + ∆xk, yk + ∆yk, µk)(cid:13) (cid:13) > βµk

∆xk ∆yk ∆µk

N‚u (cid:13) (cid:13)φ(xk + ∆xk, yk + ∆yk, 0)(cid:13) nghi»m cıa LCP(q, M); ng(cid:247)æc l⁄i, n‚u (cid:13) th… (cid:31)(cid:176)t

ˆxk := xk, ˆyk := yk, ˆµk := µk, ηk := 1;

1, (cid:240) (cid:31)¥y s l(cid:160) sŁ nguy¶n kh(cid:230)ng ¥m sao cho

(cid:13) (cid:13)φ (cid:0)xk + ∆xk, yk + ∆yk, αt

(cid:1)(cid:13) (cid:13) ≤ αt

1µk

1βµk, t = 0, 1, 2, ..., s,

tr¡i l⁄i ηk = αs

(cid:13) (cid:13)φ (cid:0)xk + ∆xk, yk + ∆yk, αs+1

(cid:1)(cid:13) (cid:13) > αs+1

1 µk

1 βµk,

v(cid:160)

(cid:31)(cid:176)t

ˆxk := xk + ∆xk, ˆyk := yk + ∆yk, ˆµk := ηkµk.

B(cid:247)(cid:238)c 3: (∆ˆxk, ∆ˆyk, ∆ˆµk) l(cid:160) nghi»m cıa ph(cid:247)(cid:236)ng tr…nh





  =



  ,

F (ˆxk, ˆyk, ˆµk) + ∇(ˆxk, ˆyk, ˆµk)T

∆ˆxk ∆ˆyk ∆ˆµk 0 0 (1 − ¯σ) ˆµk

2, ... sao cho

(cid:16)

(cid:17)

(cid:16)

(cid:17)

v(cid:160) ˆλk l(cid:160) gi¡ tr(cid:224) l(cid:238)n nh§t cıa c¡c gi¡ tr(cid:224) 1, α2, α2

(cid:13) (cid:13) (cid:13)φ

(cid:17)(cid:13) (cid:13) (cid:13) ≤

ˆxk + ˆλk∆ˆxk, ˆyk + ˆλk∆ˆyk, 1 − ¯σˆλk ˆµk 1 − ¯σˆλk β ˆµk.

(cid:16)

(cid:17)

(cid:30)(cid:176)t

xk+1 := ˆxk + ˆλk∆ˆxk, yk+1 := ˆyk + ˆλk∆ˆyk, µk+1 := 1 − ¯σˆλk ˆµk,

v(cid:160) quay tr(cid:240) l⁄i b(cid:247)(cid:238)c 2.

Khi b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh LCP (q, M ) (cid:31)(cid:236)n (cid:31)i»u ho(cid:176)c M l(cid:160) P0 - ma tr“n,

(cid:1) v(cid:160) (cid:0)xk+1, yk+1, µk+1

c¡c k‚t qu£ sau (cid:31)(cid:247)æc chøng minh.

(cid:30)(cid:224)nh l(cid:254) 1.4. ([3]) X†t thu“t to¡n tr¶n, gi£ sß M l(cid:160) P0 - ma tr“n. N‚u (cid:0)xk, yk(cid:1) ∈ N (β, µk) th… ho(cid:176)c (cid:0)xk + ∆xk, yk + ∆yk(cid:1) l(cid:160) nghi»m cıa LCP(q,M) ho(cid:176)c (cid:0)ˆxk, ˆyk, ˆµk (cid:1) l(cid:160) ho(cid:160)n to(cid:160)n x¡c (cid:31)(cid:224)nh trong b(cid:247)(cid:238)c 2 v(cid:160) 3. — tr(cid:247)(cid:237)ng hæp thø hai, ta c(cid:226) (cid:0)ˆxk, ˆyk(cid:1) ∈ N (β, ˆµk) v(cid:160) (cid:0)xk+1, yk+1(cid:1) ∈ N (β, µk+1) v(cid:238)i 0 < µk+1 < ˆµk. Tł (cid:0)x0, y0(cid:1) ∈ N (β, µ0) v(cid:238)i µ0 > 0, (cid:31)i•u n(cid:160)y cho th§y thu“t to¡n ho(cid:160)n to(cid:160)n x¡c (cid:31)(cid:224)nh.

(cid:13) (cid:13)

(cid:13) (cid:13) ≤ C,

(cid:13)∇(x,y)F (ˆx, ˆy, µ)−1(cid:13)

(cid:30)(cid:224)nh l(cid:254) 1.5. ([3]) N‚u LCP(q, M) (cid:31)(cid:236)n (cid:31)i»u, x > 0, y > 0, M x − y + q = 0 v(cid:238)i (x, y) ∈ Rn × Rn v(cid:160) β > 0, µ0 > 0, t(cid:231)n t⁄i C > 0 sao cho

v(cid:238)i 0 < µ ≤ µ0 v(cid:160) (ˆx, ˆy) ∈ N (β, µ) th… LCP (q, M ) c(cid:226) mºt nghi»m duy

nh§t.

1.3.2 B(cid:160)i to¡n b(cid:242) phi tuy‚n

Tr(cid:247)(cid:238)c ti¶n ta (cid:31)(cid:224)nh ngh(cid:190)a b(cid:160)i to¡n b(cid:242) phi tuy‚n N CP (F ) l(cid:160) b(cid:160)i to¡n t…m

vect(cid:236) x ∈ Rn sao cho

x ≥ 0, F (x) ≥ 0, (cid:104)x, F (x)(cid:105) = 0,

trong (cid:31)(cid:226) F l(cid:160) ¡nh x⁄ phi tuy‚n tł Rn v(cid:160)o Rn.

(cid:30)” gi£i b(cid:160)i to¡n b(cid:242) phi tuy‚n ta chia c¡c tr(cid:247)(cid:237)ng hæp (cid:31)Łi v(cid:238)i ¡nh x⁄ phi

tuy‚n F

Tr(cid:247)(cid:237)ng hæp 1: F (cid:31)(cid:236)n (cid:31)i»u

C¡c nh(cid:160) khoa h(cid:229)c Geiger v(cid:160) Kanzow [8], (cid:31)¢ sß d(cid:246)ng h(cid:160)m Fischer [7]

ϕF : R2 → R x¡c (cid:31)(cid:224)nh b(cid:240)i

√ a2 + b2 − a − b. (1.12) ϕF (a, b) :=

(cid:17)2

(cid:16)√

(cid:30)” (cid:31)(cid:247)æc h(cid:160)m kh(cid:230)ng ¥m ta b…nh ph(cid:247)(cid:236)ng v‚ ph£i h(cid:160)m (1.12)

a2 + b2 − a − b (1.13) . ϕ (a, b) := 1 2

Ti‚p theo x†t mŁi quan h» giœa b(cid:160)i to¡n b(cid:242) N CP (F ) v(cid:238)i b(cid:160)i to¡n tŁi (cid:247)u

kh(cid:230)ng r(cid:160)ng buºc

(1.14) ψ (x) , min x∈Rn

n (cid:88)

(cid:240) (cid:31)¥y ψ : Rn → R x¡c (cid:31)(cid:224)nh b(cid:240)i

i=1

ψ (x) := (1.15) ϕ (xi, Fi (x)),

Fi : Rn → R l(cid:160) h(cid:160)m th(cid:160)nh phƒn thø i cıa F (i ∈ I := {1, ....., n}) .

Hai nh(cid:160) khoa h(cid:229)c tr¶n (cid:31)¢ chøng minh (cid:31)(cid:247)æc mºt sŁ k‚t qu£ m⁄nh h(cid:236)n

khi F l(cid:160) h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u (cid:31)(cid:226) l(cid:160)

(cid:30)(cid:224)nh l(cid:254) 1.6. N‚u F ∈ C 1 (Rn) c(cid:226) Jacobian F (cid:48) (x) x¡c (cid:31)(cid:224)nh d(cid:247)(cid:236)ng v(cid:238)i m(cid:229)i x ∈ Rn th… x∗ l(cid:160) c(cid:252)c ti”u to(cid:160)n c(cid:246)c cıa ψ khi v(cid:160) ch¿ khi x∗ l(cid:160) (cid:31)i”m dłng cıa ψ.

(cid:30)(cid:224)nh l(cid:254) 1.7. N‚u F ∈ C 1 (Rn) l(cid:160) h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u th… x∗ ∈ Rn l(cid:160) c(cid:252)c ti”u

to(cid:160)n c(cid:246)c cıa b(cid:160)i to¡n tŁi (cid:247)u kh(cid:230)ng r(cid:160)ng buºc (1.14) - (1.15) v(cid:160) khi v(cid:160) ch¿ khi x∗ l(cid:160) (cid:31)i”m dłng cıa ψ.

(cid:30)” t…m c(cid:252)c ti”u cıa h(cid:160)m ψ, ta c(cid:226) ph(cid:247)(cid:236)ng ph¡p ri¶ng (cid:31)(cid:247)æc g(cid:229)i l(cid:160) ph(cid:247)(cid:236)ng

ph¡p (cid:31)(cid:247)(cid:237)ng dŁc nh§t, thu“t to¡n cıa n(cid:226) nh(cid:247) sau:

n (cid:80) i=1

(cid:0)xk, F (cid:0)xk(cid:1)(cid:1) .

2. Thu“t to¡n 2 B(cid:247)(cid:238)c 1: Gi£ sß F : Rn → Rn l(cid:160) h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u m⁄nh, x¡c (cid:31)(cid:224)nh ψ : Rn → R, ϕ (xi, Fi (x)). L§y x0 ∈ Rn, ε > 0, σ ∈ (0, 1) , β ∈ (0, 1) v(cid:160) (cid:31)(cid:176)t ψ(x) :=

k := 0. B(cid:247)(cid:238)c 2: N‚u ψ(xk) < ε th… dłng: xk l(cid:160) nghi»m gƒn (cid:31)(cid:243)ng cıa NCP(F). B(cid:247)(cid:238)c 3: T‰nh dk := − ∂ϕ ∂b B(cid:247)(cid:238)c 4: T‰nh tk = βmk, (cid:240) (cid:31)¥y mk l(cid:160) sŁ nguy¶n kh(cid:230)ng ¥m nh(cid:228) nh§t m

th(cid:228)a m¢n (cid:31)i•u ki»n Armijo

(cid:13)dk(cid:13) 2 (cid:13)

ψ (cid:0)xk + βmdk(cid:1) ≤ ψ (cid:0)xk(cid:1) − βmσ(cid:13) .

(cid:12)ψ(x) ≤ ψ (cid:0)x0(cid:1)(cid:9) v(cid:160) Jacobian F (cid:48)

k∈N sinh b(cid:240)i Thu“t to¡n 2 (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh v(cid:160) hºi t(cid:246)

B(cid:247)(cid:238)c 5: (cid:30)(cid:176)t xk+1 := xk + tkdk, k := k + 1, quay l⁄i B(cid:247)(cid:238)c 2.

(cid:30)(cid:224)nh l(cid:254) 1.8. ([8]) Gi£ sß F ∈ C 1 (Rn) l(cid:160) h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u m⁄nh v(cid:238)i µ > 0, x0 ∈ Rn l(cid:160) (cid:31)i”m xu§t ph¡t ban (cid:31)ƒu, t“p møc cıa n(cid:226) l(cid:160) L(x0) := (cid:8)x ∈ Rn (cid:12) li¶n t(cid:246)c Lipschitz trong L(x0). N‚u σ < µ th… d¢y (cid:8)xk(cid:9) t(cid:238)i nghi»m duy nh§t x∗ cıa NCP(F).

Tr(cid:247)(cid:237)ng hæp 2: F l(cid:160) h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u m⁄nh

Hai nh(cid:160) khoa h(cid:229)c Mangasarian L. O. v(cid:160) Scolodov V. M. [14] (cid:31)¢ sß d(cid:246)ng

ph(cid:247)(cid:236)ng ph¡p (cid:31)(cid:247)(cid:237)ng dŁc nh(cid:247)ng kh(cid:230)ng (cid:31)⁄o h(cid:160)m (cid:31)” t…m c(cid:252)c ti”u cıa h(cid:160)m

m(cid:246)c ti¶u Lagrange 'n

2 + (cid:13) (cid:13) (cid:13)

2 − (cid:107)F (x)(cid:107)2(cid:17) (cid:13) (cid:13)

(cid:13)(F (x) − αx)+

(cid:16)(cid:13) (cid:13)(x − αF (x))+ v(cid:238)i α > 1 l(cid:160) tham sŁ v(cid:160) (.)+ l(cid:160) ph†p tr(cid:252)c giao tr¶n kh(cid:230)ng gian Rn +.

, Mα (x) := (cid:104)x, F (x)(cid:105)+ 1 2α

r (x) := x − (x − F (x))+ = min {x, F (x)} ,

l(cid:160) phƒn d(cid:247) t(cid:252) nhi¶n (cid:31)Łi v(cid:238)i NCP(F), r (x) = 0 khi v(cid:160) ch¿ khi x l(cid:160) nghi»m

cıa NPC(F).

Hai nh(cid:160) to¡n h(cid:229)c tr¶n (cid:31)¢ chøng minh (cid:31)(cid:247)æc s(cid:252) t(cid:231)n t⁄i nghi»m v(cid:160) (cid:31)¡nh

gi¡ (cid:31)(cid:247)æc c¡c k‚t qu£ sau.

(cid:30)(cid:224)nh l(cid:254) 1.9. ([14]) N‚u α > 0 th…

i). Mα (x) ≥ 0 v(cid:238)i m(cid:229)i x ∈ Rn;

ii). x ∈ Rn l(cid:160) nghi»m cıa NCP(F) khi v(cid:160) ch¿ khi Mα (x) = 0;

iii). α−1 (α − 1) (cid:107)r (x)(cid:107)2 ≤ Mα (x) ≤ (α − 1) (cid:107)r (x)(cid:107)2 v(cid:238)i m(cid:229)i x ∈ Rn.

V“y b(cid:160)i to¡n NCP(F) gi£i (cid:31)(cid:247)æc th(cid:230)ng qua vi»c t…m c(cid:252)c ti”u kh(cid:230)ng r(cid:160)ng

buºc

Mα (x) . min x∈Rn

— (cid:31)¥y c¡c h(cid:160)m Mα (.) v(cid:160) F (.) l(cid:160) kh£ vi li¶n t(cid:246)c.

(cid:30)(cid:224)nh l(cid:254) 1.10. ([14]) N‚u F (.) (cid:31)(cid:236)n (cid:31)i»u m⁄nh v(cid:238)i µ > 0 v(cid:160) li¶n t(cid:246)c Lipschitz v(cid:238)i h‹ng sŁ L > 0 tr¶n t“p X chøa x∗ l(cid:160) nghi»m cıa NCP(F) th…

(cid:107)x − x∗(cid:107) ≤ (cid:107)r (x)(cid:107) , ∀x ∈ X. L + 1 µ

Ti‚p theo, Mangasarian L. O. v(cid:160) Scolodov V. M. [14] (cid:31)¢ bi‚n (cid:31)Œi h(cid:160)m

n (cid:88)

Lagrange 'n d(cid:247)(cid:238)i d⁄ng

i=1

Mα (x) = ψα(xi, Fi (x)),

+ − b2(cid:17)

+ − a2 + (b − αa)2

(cid:240) (cid:31)¥y ψα : R2 → R x¡c (cid:31)(cid:224)nh b(cid:240)i (cid:16) . (a − αb)2 ψα (a, b) := ab + 1 2α

Ta c(cid:226)

(cid:1) ,

(cid:0)(a − αb)+ − a − α(b − αa)+

(a, b) = b + ∂ψα ∂a 1 α

(cid:0)(a − αb)+ + (b − αa)+ − b(cid:1) .

(a, b) = a + ∂ψα ∂b 1 α





V(cid:160)

 

  ,





(x, F (x)) := ∂ψα ∂a

 

  .

∂ψα ∂a (x1, F1 (x)) ... ∂ψα ∂a (xn, Fn (x)) ∂ψα ∂b (x1, F1 (x)) ... ∂ψα ∂b (xn, Fn (x))

(x, F (x)) := ∂ψα ∂b

Gradient cıa Mα(.) (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh b(cid:240)i:

(x, F (x)) . ∇Mα(x) = ∂ψα ∂a (x, F (x)) + ∇F (x)T ∂ψα ∂b

(cid:30)” gi£i nhœng b(cid:160)i to¡n d⁄ng n(cid:160)y ta c(cid:226) thu“t to¡n sau

3. Thu“t to¡n 3 B(cid:247)(cid:238)c 1: Ch(cid:229)n x0 ∈ Rn , γ ∈ (0, 1), v(cid:160) h‹ng sŁ β > 0 (cid:31)ı nh(cid:228). V(cid:238)i mØi xi,

x¡c (cid:31)(cid:224)nh

(cid:0)xi, F (cid:0)xi(cid:1)(cid:1) − β

(cid:0)xi, F (cid:0)xi(cid:1)(cid:1) ,

di := − ∂ψα ∂a ∂ψα ∂b

B(cid:247)(cid:238)c 2: T‰nh

(cid:0)xi, F (cid:0)xi(cid:1)(cid:1)

(cid:0)xi, F (cid:0)xi(cid:1)(cid:1) +

xi+1 = xi + ηidi,

(cid:0)xi + γkidi(cid:1) ≥ γ2k

(cid:0)xi(cid:1) − Mα

(cid:13) 2 (cid:13) (cid:13) (cid:13)

. Mα ∂ψα ∂b V(cid:238)i ηi = γki v(cid:238)i ki l(cid:160) sŁ nguy¶n ¥m k kh(cid:230)ng ¥m nh(cid:228) nh§t th(cid:228)a m¢n (cid:13) (cid:13) (cid:13) (cid:13)

∂ψα ∂a (cid:30)(cid:224)nh ngh(cid:190)a 1.7. D¢y (cid:8)xk(cid:9) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) hºi t(cid:246) t(cid:238)i Q - tuy‚n t‰nh t(cid:238)i x∗ n‚u t(cid:231)n t⁄i mºt h‹ng sŁ 0 < r < 1 sao cho

≤ r, (cid:107)xk+1 − x∗(cid:107) (cid:107)xk − x∗(cid:107)

r g(cid:229)i l(cid:160) tŁc (cid:31)º hºi t(cid:246). (cid:30)(cid:224)nh ngh(cid:190)a 1.8. D¢y (cid:8)xk(cid:9) (cid:31)(cid:247)æc g(cid:229)i l(cid:160) hºi t(cid:246) R - tuy‚n t‰nh t(cid:238)i x∗ n‚u

(cid:107)xk − x∗(cid:107) ≤ δk,

v(cid:238)i δk hºi t(cid:246) t(cid:238)i Q - tuy‚n t‰nh t(cid:238)i 0.

(cid:30)(cid:224)nh l(cid:254) 1.11. ([14]) Gi£ sß F (.) kh£ vi li¶n t(cid:246)c, (cid:31)(cid:236)n (cid:31)i»u m⁄nh t(cid:238)i µ > 0. Cho x0 ∈ R l(cid:160) (cid:31)i”m xu§t ph¡t b§t k(cid:253), F (.) v(cid:160) ∇F (.) li¶n t(cid:246)c Lipschitz v(cid:238)i h‹ng sŁ L > 0 n(cid:160)o (cid:31)(cid:226) tr¶n t“p B (cid:0)x0(cid:1) th… v(cid:238)i d¢y (cid:8)xi(cid:9) sinh b(cid:240)i Thu“t to¡n 3, d¢y (cid:8)Mα (cid:0)xi(cid:1)(cid:9) hºi t(cid:246) t(cid:238)i Q - tuy‚n t‰nh t(cid:238)i 0 v(cid:160) (cid:8)xi(cid:9) hºi t(cid:246) R - tuy‚n t‰nh t(cid:238)i nghi»m cıa NCP(F).

— (cid:31)¥y

(cid:12)(cid:107)x(cid:107) ≤ D (cid:0)x0(cid:1)(cid:9) ,

(cid:12)Mα (x) ≤ Mα

B (cid:0)x0(cid:1) := L (cid:0)Mα, x0(cid:1) + (cid:8)x (cid:12)

(cid:0)x0(cid:1)(cid:9) , (cid:12)x ∈ L (cid:0)Mα, x0(cid:1)(cid:9) ,

L (cid:0)Mα, x0(cid:1) := (cid:8)x (cid:12) D (cid:0)x0(cid:1) := sup (cid:8)(cid:107)d (x)(cid:107) (cid:12)

v(cid:238)i d (x) l(cid:160) h(cid:247)(cid:238)ng t…m ki‚m trong Thu“t to¡n 3.

Tr(cid:247)(cid:237)ng hæp 3: F l(cid:160) P0 - h(cid:160)m, kh£ vi li¶n t(cid:246)c

Khi (cid:31)(cid:226) b(cid:160)i to¡n b(cid:242) phi tuy‚n NCP(F) (cid:31)(cid:247)æc k(cid:254) hi»u l(cid:160) P0 - NCP(F). (cid:30)”

gi£i b(cid:160)i to¡n n(cid:160)y, Fang L. [6] (cid:31)¢ l(cid:160)m nhi„u h(cid:160)m

g (µ, a, b) := min {a + µb, µa + b} .

(cid:113)

Ta l(cid:160)m tr(cid:236)n h(cid:160)m g (µ, a, b) v(cid:160) thu (cid:31)(cid:247)æc h(cid:160)m

(a + µb)2 + (µa + b)2 + 2µ2 φ (µ, a, b) := (1 + µ) (a, b) −

tr(cid:236)n.

Khi (cid:31)(cid:226), h(cid:160)m φ (µ, a, b) c(cid:226) c¡c t‰nh ch§t sau:

V(cid:238)i µ = 0 ta c(cid:226):

φ (0, a, b) = 0 ⇔ a ≥ 0, b ≥ 0, ab = 0.

(cid:48)

V(cid:238)i µ (cid:54)= 0 b§t k(cid:253), c(cid:226)

(cid:113)

(cid:48)

µa2 + 2ab + µb2 + 2µ , φ µ (µ, a, b) = a + b − (a + µb)2 + (µa + b)2 + 2µ2

a (µ, a, b) = 1 + µ −

(cid:113)

(1 + µ)2a + 2µb φ ,

(a + µb)2 + (µa + b)2 + 2µ2

(cid:48)

b (µ, a, b) = 1 + µ −

(cid:113)

(1 + µ)2b + 2µa φ .

(a + µb)2 + (µa + b)2 + 2µ2

b l(cid:160) li¶n t(cid:246)c v(cid:160)

C¡c h(cid:160)m φµ(cid:48) , φ(cid:48)

(cid:113)

(1 + µ)2a + 2µb ≤ 1 + µ,

(a + µb)2 + (µa + b)2 + 2µ2

(cid:113)

(1 + µ)2b + 2µa ≤ 1 + µ,

(cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

a v(cid:160) φ(cid:48) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

(a + µb)2 + (µa + b)2 + 2µ2

V(cid:238)i µ > 0.

Ngo(cid:160)i c¡ch gi£i b(cid:160)i to¡n P0 - NCP(F) tr(cid:252)c ti‚p th… Fang L. [6] (cid:31)¢ gi£i

(cid:19)

b(cid:160)i to¡n tr¶n th(cid:230)ng qua b(cid:160)i to¡n t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng sau G (z) = 0, v(cid:238)i

(cid:18) eµ − 1 φ (z)

G (z) := , (1.16)



v(cid:238)i z := (µ, x) ∈ R+ × Rn v(cid:160) φ : R+ × Rn → Rn x¡c (cid:31)(cid:224)nh b(cid:240)i 

   

   

. (1.17) φ (z) :=

φ (µ, x1, F1 (x)) φ (µ, x2, F2 (x)) ... φ (µ, xn, Fn (x))

Trong (cid:31)(cid:226) h(cid:160)m φ kh£ vi li¶n t(cid:246)c t⁄i z = (µ, x) ∈ R++ × Rn.

Fang L. [6] (cid:31)¢ x¥y d(cid:252)ng h(cid:160)m ψ : R+ × Rn → R+ nh(cid:247) sau:

ψ (z) := (cid:107)G(z)(cid:107)2 = (eµ − 1)2 + (cid:107)φ (z)(cid:107)2. (1.19)

(cid:30)” gi£i nhœng b(cid:160)i to¡n d⁄ng n(cid:160)y th… ta c(cid:226) ph(cid:247)(cid:236)ng ph¡p m(cid:238)i (cid:31)(cid:247)æc g(cid:229)i l(cid:160)

ph(cid:247)(cid:236)ng ph¡p Newton tr(cid:236)n mºt b(cid:247)(cid:238)c cho P0 - NCP(F).

4. Thu“t to¡n 4 (cid:1) v(cid:160) (cid:31)i”m xu§t ph¡t ban B(cid:247)(cid:238)c 1: Ch(cid:229)n h‹ng sŁ δ ∈ (0, 1) , σ ∈ (cid:0)0, 1 (cid:31)ƒu t(cid:242)y (cid:254) z0 := (cid:0)µ0, x0(cid:1) ∈ R++ × Rn. L§y η = (cid:112)ψ (z0) + 1 v(cid:160) ¯µ = µ0, ¯z := (¯µ, 0) ∈ R++ × Rn. Ch(cid:229)n γ ∈ (0, 1) sao cho

γ ¯µη < 1.

(cid:30)(cid:176)t k := 0 B(cid:247)(cid:238)c 2: N‚u ψ (cid:0)zk(cid:1) = 0 th… dłng, ng(cid:247)æc l⁄i, l§y

βk := β (cid:0)zk(cid:1) = eµkγ min (cid:8)1, ψ (cid:0)zk(cid:1)(cid:9) .

B(cid:247)(cid:238)c 3: T‰nh ∆zk := (cid:0)∆µk, ∆xk(cid:1) ∈ R × Rn

(cid:48) (cid:0)zk(cid:1) ∆zk = βk ¯z.

G (cid:0)zk(cid:1) + G

B(cid:247)(cid:238)c 4: L§y νk l(cid:160) sŁ nguy¶n kh(cid:230)ng ¥m nh(cid:228) nh§t ν sao cho

ψ (cid:0)zk + δν∆zk(cid:1) ≤ [1 − 2σ (1 − γη ¯µ) δν] ψ (cid:0)zk(cid:1) .

V(cid:238)i λk := δν k. B(cid:247)(cid:238)c 5: (cid:30)(cid:176)t zk+1 := zk + λk∆zk v(cid:160) k := k + 1, quay l⁄i B(cid:247)(cid:238)c 2.

(cid:8)zk := (cid:0)µk, xk(cid:1)(cid:9) ,

(cid:30)(cid:224)nh l(cid:254) 1.12. ([6]) Thu“t to¡n 4 x¡c (cid:31)(cid:224)nh v(cid:160) sinh ra mºt d¢y v(cid:230) h⁄n

v(cid:238)i µk > 0 v(cid:160)

zk ∈ Ω := {z = (µ, x) ∈ R+ × Rn |µ ≥ γ min {1, ψ (z)} ¯µ} ,

v(cid:238)i m(cid:229)i k ≥ 0. (cid:30)(cid:224)nh l(cid:254) 1.13. ([6]) N‚u F l(cid:160) P0 - h(cid:160)m, kh£ vi li¶n t(cid:246)c, d¢y (cid:8)zk(cid:9) sinh b(cid:240)i Thu“t to¡n 4, t“p nghi»m Θ := {x ∈ Rn : x ≥ 0, F (x) ≥ 0, (cid:104)x, F (x)(cid:105) = 0} cıa P0 - NCP(F) kh¡c rØng v(cid:160) b(cid:224) ch(cid:176)n th… (cid:8)zk(cid:9) c(cid:226) ‰t nh§t mºt (cid:31)i”m t(cid:246) z∗ := (µ∗, x∗) v(cid:238)i x∗ ∈ Θ v(cid:160) b§t k(cid:253) (cid:31)i”m t(cid:246) n(cid:160)o cıa (cid:8)zk(cid:9) c(cid:244)ng l(cid:160) nghi»m cıa G (z) = 0.

Trong tr(cid:247)(cid:237)ng hæp F l(cid:160) P0 - h(cid:160)m, th… Sun D. [16] (cid:31)¢ d(cid:242)ng ph(cid:247)(cid:236)ng ph¡p

(cid:110)

hi»u ch¿nh Newton b‹ng c¡ch ch(cid:229)n ¯ε ∈ (0, ∞) v(cid:160) γ ∈ (0, 1) sao cho γ ¯ε < 1. 2, 1(cid:1) v(cid:160) ¯z := (¯ε, 0) ∈ R × Rn. X¡c (cid:31)(cid:224)nh β : Rn+1 → R+, L§y t ∈ (cid:0) 1 V(cid:238)i

β (z) := γ min 1, f (z)t(cid:111) .

(cid:30)(cid:176)t

(cid:1). L§y ε0 :=

2, 1(cid:3) , v(cid:160) σ ∈ (cid:0)0, 1

Ω := {z = (ε, x) ∈ R × Rn |ε ≥ β (z) ¯ε} . N‚u ch(cid:229)n (cid:31)i”m ban (cid:31)ƒu z0 = (cid:0)¯ε, x0(cid:1), (cid:240) (cid:31)¥y x0 ∈ Rn l(cid:160) mºt (cid:31)i”m t(cid:242)y (cid:254) th… d¢y l(cid:176)p sinh b(cid:240)i thu“t to¡n sau v¤n thuºc Ω.

1, f (cid:0)zk(cid:1)t(cid:111) (cid:110)

5. Thu“t to¡n 5 B(cid:247)(cid:238)c 1: Ch(cid:229)n h‹ng sŁ δ ∈ (0, 1) , t ∈ (cid:2) 1 ¯ε, x0 ∈ Rn l(cid:160) mºt (cid:31)i”m t(cid:242)y (cid:254) v(cid:160) k := 0. B(cid:247)(cid:238)c 2: N‚u H (cid:0)zk(cid:1) = 0 th… dłng, ng(cid:247)æc l⁄i l§y βk := β (cid:0)zk(cid:1) = γ min . B(cid:247)(cid:238)c 3: Ch(cid:229)n Vk ∈ ∂H (cid:0)xk(cid:1) v(cid:160) t‰nh ∆zk = (cid:0)∆εk, ∆xk(cid:1) ∈ R × Rn

H (cid:0)zk(cid:1) + Vk∆ (cid:0)zk(cid:1) = βk ¯z.

B(cid:247)(cid:238)c 4: L§y lk l(cid:160) sŁ nguy¶n ¥m nh(cid:228) nh§t l th(cid:228)a m¢n

f (cid:0)zk + δl∆zk(cid:1) ≤ (cid:2)1 − 2α (1 − γ ¯ε) δl(cid:3) f (cid:0)zk(cid:1) .

X¡c (cid:31)(cid:224)nh zk+1 := zk + δlk∆zk.

B(cid:247)(cid:238)c 5: Thay k b(cid:240)i k + 1, quay l⁄i B(cid:247)(cid:238)c 2.

(cid:30)(cid:224)nh l(cid:254) 1.14. ([16]) Gi£ sß F l(cid:160) P0 - h(cid:160)m, v(cid:238)i b§t k(cid:253) k ≥ 0, n‚u zk = (cid:0)εk, xk(cid:1) ∈ R++ × Rn th… Thu“t to¡n 5 ho(cid:160)n to(cid:160)n x¡c (cid:31)(cid:224)nh t⁄i b(cid:247)(cid:238)c l(cid:176)p thø k v(cid:160) zk+1 ∈ R++ × Rn .

(cid:30)” gi£i c¡c b(cid:160)i to¡n b(cid:242) phi tuy‚n, Fachinei v(cid:160) Kanzow [5] (cid:31)¢ sß d(cid:246)ng

ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov b‹ng c¡ch gi£i d¢y c¡c b(cid:160)i to¡n b(cid:242)

N CP (Fε)

x ≥ 0, Fε (x) ≥ 0, (cid:104)x, Fε (x)(cid:105) = 0,

v(cid:238)i Fε (x) := F (x) + εx v(cid:160) ε l(cid:160) tham sŁ d(cid:247)(cid:236)ng hºi t(cid:246) t(cid:238)i 0. Fachinei v(cid:160) Kanzow (cid:31)¢ sß d(cid:246)ng h(cid:160)m kh(cid:230)ng tr(cid:236)n ϕ : R2 → R,

√ a2 + b2 − a − b. ϕ (a, b) :=





Ti‚p theo, h(cid:229) x¥y d(cid:252)ng h(cid:160)m φ : Rn → Rn v(cid:238)i





φ (x) =

ϕ (x1, F1 (x)) ... ϕ (xn, Fn (x))

v(cid:160) h(cid:160)m kho£ng t(cid:247)(cid:236)ng øng ψ : Rn → Rn x¡c (cid:31)(cid:224)nh b(cid:240)i

ψ (x) = φ(x)T (cid:107)φ (x)(cid:107)2. 1 2

Tł c¡c c(cid:230)ng c(cid:246) tr¶n h(cid:229) (cid:31)¢ chøng minh b(cid:160)i to¡n hi»u ch¿nh N CP (Fε) c(cid:226)

duy nh§t nghi»m x (ε) v(cid:238)i m(cid:229)i ε > 0.

Trong th(cid:252)c t‚ (cid:31)(cid:176)t ra th(cid:247)(cid:237)ng kh(cid:226) c(cid:226) kh£ n«ng t…m nghi»m ch‰nh x¡c cıa

b(cid:160)i to¡n N CP (Fε) v(cid:238)i mØi ε > 0. Do (cid:31)(cid:226) h(cid:229) (cid:31)¢ (cid:31)(cid:247)a ra ph(cid:247)(cid:236)ng ph¡p gi£i

gƒn (cid:31)(cid:243)ng sau.

6. Thu“t to¡n 6

(cid:0)xk(cid:1) ≤ αk;

B(cid:247)(cid:238)c 1: Ch(cid:229)n ε0 > 0, α0 ≥ 0 v(cid:160) (cid:31)(cid:176)t k := 0; B(cid:247)(cid:238)c 2: T‰nh nghi»m gƒn (cid:31)(cid:243)ng xk ∈ Rn cıa N P C (Fεk) sao cho

ψεk

B(cid:247)(cid:238)c 3: K‚t th(cid:243)c l(cid:176)p n‚u (cid:31)i•u ki»n dłng th(cid:228)a m¢n;

B(cid:247)(cid:238)c 4: Ch(cid:229)n εk+1 > 0, αk+1 ≥ 0, (cid:31)(cid:176)t k = k + 1 v(cid:160) quay l⁄i B(cid:247)(cid:238)c 2.

(cid:30)(cid:224)nh l(cid:254) 1.15. ([5]) Cho F l(cid:160) P0 - h(cid:160)m, S l(cid:160) t“p nghi»m cıa NCP(F), S kh¡c rØng v(cid:160) b(cid:224) ch(cid:176)n. Gi£ sß d¢y (cid:8)xk(cid:9) sinh ra b(cid:240)i thu“t to¡n 6, n‚u εk → 0, αk → 0 th… (cid:8)xk(cid:9) l(cid:160) nghi»m cıa b(cid:160)i to¡n NCP(F).

(cid:30)” gi£i b(cid:160)i to¡n b(cid:242) phi tuy‚n, Kanzow [10] (cid:31)¢ sß d(cid:246)ng h(cid:160)m ϕµ : R2 → R

(cid:113)

x¡c (cid:31)(cid:224)nh b(cid:240)i

(a − b)2 + 4µ, µ ≥ 0, (1.18) ϕµ (a, b) := a + b −

(cid:19)

ta c(cid:226) to¡n tß phi tuy‚n sau Fϕµ : R2n → R2n, v(cid:238)i

(cid:18) F (x) − y ϕµ (x, y)

(1.19) , Fϕµ (z) := Fϕµ (x, y) :=

(cid:240) (cid:31)¥y

ϕµ (x, y) := (ϕµ (x1, y1) , ...., ϕµ (xn, yn))T ∈ Rn.

(cid:30)(cid:224)nh ngh(cid:190)a 1.9. Cho µ ≥ 0 l(cid:160) h(cid:160)m sŁ b§t k(cid:253), b(cid:160)i to¡n b(cid:242) phi tuy‚n nhi„u, k(cid:254) hi»u: P N CP (F, µ), l(cid:160) b(cid:160)i to¡n t…m nghi»m (x (µ) , y (µ)) ∈ R2n

th(cid:228)a m¢n c¡c (cid:31)i•u ki»n sau:

x ≥ 0, y ≥ 0, xiyi = µ (i ∈ I) , y = F (x) .

N‚u µ = 0 th… b(cid:160)i to¡n P N CP (F, µ) l(cid:160) b(cid:160)i to¡n b(cid:242) phi tuy‚n.

Trong [10] Kanzow (cid:31)¢ d(cid:242)ng ph(cid:247)(cid:236)ng ph¡p kh¡c (cid:31)” gi£i b(cid:160)i to¡n NPC(F).

7. Thu“t to¡n 7

µk = 0. (cid:30)(cid:176)t k = 0.

B(cid:247)(cid:238)c 1: L§y {µk} l(cid:160) d¢y b§t k(cid:253) sao cho µk > 0 v(cid:160) lim k→∞ B(cid:247)(cid:238)c 2: T…m nghi»m zk := z (µk) cıa h» ph(cid:247)(cid:236)ng tr…nh phi tuy‚n

(cid:0)zk(cid:1) = 0(cid:13)

(cid:13) th… dłng, zk l(cid:160) nghi»m cıa NCP(F).

(cid:13)Fϕ0

(z) = 0. Fϕµk

B(cid:247)(cid:238)c 3: N‚u (cid:13) B(cid:247)(cid:238)c 4: (cid:30)(cid:176)t k := k + 1 v(cid:160) quay l⁄i B(cid:247)(cid:238)c 2.

(cid:30)(cid:224)nh l(cid:254) 1.16. ([12]) N‚u F : Rn → Rn li¶n t(cid:246)c v(cid:160) l(cid:160) P - h(cid:160)m (cid:31)•u th… b(cid:160)i to¡n b(cid:242) nhi„u P N CP (F, µ) c(cid:226) duy nh§t nghi»m z (µ) v(cid:238)i µ > 0.

(cid:30)(cid:224)nh l(cid:254) 1.17. ([10]) N‚u F : Rn → Rn kh£ vi li¶n t(cid:246)c v(cid:160) l(cid:160) P - h(cid:160)m (cid:31)•u th… d¢y {z (µk)} sinh b(cid:240)i Thu“t to¡n 7 hºi t(cid:246) t(cid:238)i nghi»m duy nh§t cıa

NCP(F).

Nh(cid:247)æc (cid:31)i”m cıa thu“t to¡n 7 l(cid:160) ph£i gi£i ch‰nh x¡c c¡c b(cid:160)i to¡n con

P N CP (F, µ) t⁄i mØi b(cid:247)(cid:238)c l(cid:176)p, do (cid:31)(cid:226) Kanzow [10] (cid:31)¢ (cid:31)(cid:247)a ra thu“t to¡n

m(cid:238)i (cid:31)” gi£i gƒn (cid:31)(cid:243)ng c¡c b(cid:160)i to¡n n(cid:160)y.

(cid:13) ≤ ε.

(cid:13)Fϕµ (z (ε))(cid:13)

(cid:30)(cid:224)nh ngh(cid:190)a 1.10. [10]) Vect(cid:236) z (ε) l(cid:160) nghi»m x§p x¿ ε cıa h» Fϕµ (z) = 0 n‚u (cid:13)

8. Thu“t to¡n 8

(z) = 0;

B(cid:247)(cid:238)c 1: Ch(cid:229)n µ0 > 0, ε0 > 0 v(cid:160) (cid:31)(cid:176)t k = 0; B(cid:247)(cid:238)c 2: T…m ε - nghi»m gƒn (cid:31)(cid:243)ng z (εk) cıa h» Fϕµk B(cid:247)(cid:238)c 3: Dłng l(cid:176)p n‚u (cid:31)i•u ki»n dłng th(cid:228)a m¢n;

B(cid:247)(cid:238)c 4: Ch(cid:229)n µk+1 < µk, εk+1 < εk, (cid:31)(cid:176)t k := k + 1 v(cid:160) quay l⁄i B(cid:247)(cid:238)c 2.

(cid:30)(cid:224)nh l(cid:254) 1.18. ([10]) Cho F : Rn → Rn kh£ vi li¶n t(cid:246)c v(cid:160) P - h(cid:160)m (cid:31)•u. Gi£ sß d¢y {εk} v(cid:160) {µk} hºi t(cid:246) t(cid:238)i 0 th… d¢y {z (εk)} sinh b(cid:240)i thu“t to¡n 8

hºi t(cid:246) t(cid:238)i nghi»m duy nh§t cıa NCP(F).

Tr¶n c(cid:236) s(cid:240) h(cid:160)m Fischet - Burmeister, (cid:31)” gi£i b(cid:160)i to¡n NCP(F), Chen v(cid:160)

Pan [4] (cid:31)¢ nghi¶n cøu v(cid:238)i C - h(cid:160)m m(cid:238)i φp : R2 → R, v(cid:238)i

(1.20) φp (a, b) := (cid:107)(a, b)(cid:107)p − (a, b) ,

p .

v(cid:238)i p l(cid:160) sŁ th(cid:252)c cŁ (cid:31)(cid:224)nh b§t k(cid:253) trong kho£ng (1, +∞) v(cid:160) k(cid:254) hi»u chu'n p cıa (a, b) l(cid:160) (cid:107)(a, b)(cid:107)p, c(cid:226) ngh(cid:190)a l(cid:160)

(cid:107)(a, b)(cid:107)p = (|a|p + |b|p)

— (cid:31)¥y h(cid:229) (cid:31)¢ x¥y d(cid:252)ng h(cid:160)m ψp : R2 → R+, x¡c (cid:31)(cid:224)nh b(cid:240)i

(1.21) ψp (a, b) := |φp (a, b)|2.



1 2 V(cid:238)i m(cid:229)i p > 1, h(cid:160)m ψp l(cid:160) C - h(cid:160)m kh(cid:230)ng ¥m v(cid:160) tr(cid:236)n tr¶n R2. H(cid:160)m ψp, φp : Rn → Rn, (cid:31)(cid:247)æc cho b(cid:240)i



  .

(1.22) φp (x) :=

φp (x1, F1 (x)) ... φp (xn, Fn (x))

n (cid:88)

Trong [4] th… Chen v(cid:160) Pan (cid:31)¢ x¥y d(cid:252)ng mºt h(cid:229) v(cid:238)i c¡c h(cid:160)m kho£ng ψp : Rn → R, trong (cid:31)(cid:226)

i=1

(cid:107)φ (x)(cid:107)2 = (1.23) φp (xi, Fi (x)). ψp (x) = 1 2 1 2

V(cid:238)i p > 1 b§t k(cid:253) th… ψp (x) l(cid:160) h(cid:160)m kh£ vi li¶n t(cid:246)c, do (cid:31)(cid:226) c(cid:226) th‚ sß d(cid:246)ng

c¡c ph(cid:247)(cid:236)ng ph¡p l(cid:176)p truy•n thŁng, chﬂng h⁄n nh(cid:247) ph(cid:247)(cid:236)ng ph¡p Newton

(cid:31)” t…m c(cid:252)c ti”u

(1.24) ψp (x) . min x∈Rn

Ti‚p theo, h(cid:229) (cid:31)¢ d(cid:242)ng ph(cid:247)(cid:236)ng ph¡p (cid:31)(cid:247)(cid:237)ng dŁc (cid:31)” gi£i b(cid:160)i to¡n c(cid:252)c ti”u

(cid:0)xk, F (cid:0)xk(cid:1)(cid:1) ,

kh(cid:230)ng r(cid:160)ng buºc (1.24). H(cid:229) t…m

(cid:0)xk

(cid:1)(cid:1)(cid:1)T .

(1.25) dk := −∇pψp

(cid:0)xk, F (cid:0)xk(cid:1)(cid:1) = (cid:0)∇pψp

(cid:1)(cid:1) , ..., ∇pψp

1, F (cid:0)xk

n, F (cid:0)xk

v(cid:238)i ∇pψp

(cid:0)xk(cid:1)T dk ≤ −µ(cid:13)

BŒ (cid:31)• 1.2. ([4]) N‚u xk ∈ Rn v(cid:160) F l(cid:160) h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u th… h(cid:247)(cid:238)ng t…m ki‚m (cid:0)xk(cid:1)T dk < 0 khi xk x¡c (cid:31)(cid:224)nh nh(cid:247) (1.25) th(cid:228)a m¢n c¡c (cid:31)i•u ki»n dŁc ∇ψp kh(cid:230)ng l(cid:160) nghi»m cıa NPC(F). H(cid:236)n nœa, n‚u F (cid:31)(cid:236)n (cid:31)i»u m⁄nh v(cid:238)i µ > 0

(cid:13)dk(cid:13) 2. (cid:13)

th… ∇ψp

D(cid:252)a v(cid:160)o bŒ (cid:31)• tr¶n, Chen v(cid:160) Pan [4] (cid:31)¢ x¥y d(cid:252)ng thu“t to¡n nh(cid:247) sau.

(cid:0)xk(cid:1) ≤ ε th… dłng.

9. Thu“t to¡n 9 B(cid:247)(cid:238)c 1: L§y mºt sŁ th(cid:252)c p > 1 v(cid:160) x0 ∈ Rn. Ch(cid:229)n tham sŁ ε ≥ 0,σ ∈ (0, 1) v(cid:160) β ∈ (0, 1). (cid:30)(cid:176)t k := 0.

B(cid:247)(cid:238)c 2: N‚u ψp

(cid:0)xk, F (cid:0)xk(cid:1)(cid:1) .

B(cid:247)(cid:238)c 3: (cid:30)(cid:176)t

dk := ∇pψp

(cid:0)xk, F (cid:0)xk(cid:1)(cid:1) ,

B(cid:247)(cid:238)c 4: T‰nh tk := βmk, mk, (cid:240) (cid:31)¥y mk l(cid:160) sŁ nguy¶n kh(cid:230)ng ¥m nh(cid:228) nh§t m th(cid:228)a m¢n (cid:31)i•u ki»n Armijo

(cid:0)xk(cid:1) .

(cid:0)xk + βmdk(cid:1) ≤ (cid:0)1 − σβ2m(cid:1) ψp

dk := −∇pψp

ψp

B(cid:247)(cid:238)c 5: (cid:30)(cid:176)t xk+1 := xk + tkdk, k := k + 1 v(cid:160) quay l⁄i B(cid:247)(cid:238)c 2.

M»nh (cid:31)• 1.1. ([4]) N‚u F l(cid:160) (cid:31)(cid:236)n (cid:31)i»u m⁄nh th… d¢y xk sinh b(cid:240)i thu“t

to¡n 9 c(cid:226) ‰t nh§t mºt (cid:31)i”m t(cid:246) v(cid:160) b§t k(cid:253) (cid:31)i”m t(cid:246) n(cid:160)o c(cid:244)ng l(cid:160) nghi»m cıa

NCP(F).

Ti‚p theo ta (cid:31)i nghi¶n cøu b(cid:160)i to¡n b(cid:242) tŒng qu¡t v(cid:160) s(cid:252) t(cid:231)n t⁄i nghi»m

1.3.3 B(cid:160)i to¡n b(cid:242) tŒng qu¡t

cıa b(cid:160)i to¡n b(cid:242) tŒng qu¡t.

(cid:30)(cid:224)nh ngh(cid:190)a 1.11. B(cid:160)i to¡n b(cid:242) tŒng qu¡t, k(cid:254) hi»u b(cid:240)i GCP(F,G), l(cid:160) b(cid:160)i to¡n t…m vect(cid:236) x ∈ Rn sao cho

F (x) ≥ 0, G(x) ≥ 0, (cid:104)F (x), G(x)(cid:105) = 0, (1.26)

trong (cid:31)(cid:226) F, G : Rn → Rn l(cid:160) c¡c ¡nh x⁄.

Nghi¶n cøu b(cid:160)i to¡n b(cid:242) tŒng qu¡t, Kanzow v(cid:160) Fukushima (cid:31)¢ sß d(cid:246)ng

h(cid:160)m Fischer √ a2 + b2 − a − b. (1.27) ϕF (a, b) :=

(cid:17)2

(cid:16)√

Do ϕF c(cid:226) th” ¥m n¶n h(cid:229) (cid:31)¢ b…nh ph(cid:247)(cid:236)ng v‚ ph£i cıa (1.18) (cid:31)” (cid:31)(cid:247)æc h(cid:160)m

a2 + b2 − a − b (1.28) , ϕ (a, b) := 1 2

(cid:88)

(cid:31)” bi‚n (cid:31)Œi b(cid:160)i to¡n GCP(F,G) v• b(cid:160)i to¡n c(cid:252)c ti”u kh(cid:230)ng r(cid:160)ng buºc

i∈I

ψ(x) := (1.29) ϕ (Fi(x), Gi (x)). min x∈Rn

H(cid:229) (cid:31)¢ chøng minh (cid:31)(cid:247)æc c(cid:226) s(cid:252) t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng giœa c(cid:252)c ti•u to(cid:160)n c(cid:246)c cıa ψ

v(cid:160) nghi»m cıa GCP(F,G) qua (cid:31)(cid:224)nh l(cid:254) sau.

(cid:30)(cid:224)nh l(cid:254) 1.19. ([14]) N‚u GCP(F,G) c(cid:226) t“p nghi»m kh¡c rØng th… x∗ ∈ Rn l(cid:160) c(cid:252)c ti”u to(cid:160)n c(cid:246)c cıa h(cid:160)m ψ kh(cid:230)ng ¥m.

Ti‚p theo, h(cid:229) c(cid:244)ng (cid:31)¢ ch¿ ra nghi»m cıa b(cid:160)i to¡n GCP(F,G) qua (cid:31)(cid:224)nh

l(cid:254) d(cid:247)(cid:238)i (cid:31)¥y.

(cid:30)(cid:224)nh l(cid:254) 1.20. ([14]) Cho F, G : Rn → Rn l(cid:160) c¡c h(cid:160)m kh£ vi li¶n t(cid:246)c. N‚u x∗ ∈ Rn l(cid:160) (cid:31)i”m dłng cıa ψ sao cho G(cid:48) (x∗) kh(cid:230)ng suy bi‚n v(cid:160) t‰ch (F (cid:48) (x) , G(cid:48) (x))−1 l(cid:160) P0 - ma tr“n th… x∗ l(cid:160) nghi»m cıa GCP(F,G).

N‚u h(cid:160)m F v(cid:160) G th(cid:228)a m¢n (cid:31)i•u ki»n: t(cid:231)n t⁄i mºt h‹ng sŁ ρ > 0 sao cho

(1.30) [Fi (x) − Fi (y)] [Gi (x) − Gi (y)] ≥ ρ(cid:107)x − y(cid:107)2∀x, y ∈ Rn, max i∈I

v(cid:238)i I = 1, 2, ..., N th… t‰nh duy nh§t cıa nghi»m c(cid:226) th” chøng minh (cid:31)(cid:247)æc

th(cid:230)ng qua k‚t qu£ sau.

(cid:30)(cid:224)nh l(cid:254) 1.21. ([14]) N‚u F, G : Rn → Rn th(cid:228)a m¢n (cid:31)i•u ki»n (1.30) v(cid:238)i ρ > 0 n(cid:160)o (cid:31)(cid:226) th… GCP(F,G) c(cid:226) nhi•u nh§t mºt nghi»m.

(cid:30)(cid:224)nh l(cid:254) 1.22. ([14]) Gi£ sß F, G : Rn → Rn th(cid:228)a m¢n (cid:31)i•u ki»n (1.30) v(cid:238)i ρ > 0 n(cid:160)o (cid:31)(cid:226), F li¶n t(cid:246)c v(cid:160) G l(cid:160) ph†p bi‚n (cid:31)Œi li¶n t(cid:246)c Lipschitz th…

GCP(F,G) c(cid:226) duy nh§t mºt nghi»m.

(cid:30)” gi£i b(cid:160)i to¡n b(cid:242) tŒng qu¡t ta c(cid:226) th” chia ra hai tr(cid:247)(cid:237)ng hæp nh(cid:247) sau:

Tr(cid:247)(cid:237)ng hæp 1 : Hi»u ch¿nh b(cid:160)i to¡n b(cid:242) tŒng qu¡t d(cid:252)a tr¶n phi‚n h(cid:160)m

Tikhonov.

Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho (1.26) (cid:31)(cid:247)æc x¥y d(cid:252)ng tr¶n c(cid:236)

s(cid:240) gi£i b(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) (cid:31)ﬂng thøc sau: t…m mºt phƒn tß ˜x ∈ Rn sao cho

ϕj (x) , j = 1, 2, ..., N. ϕj (˜x) = min x∈Rn

Ta x†t b(cid:160)i to¡n c(cid:252)c ti”u sau: t…m mºt phƒn tß xα ∈ Rn th(cid:228)a m¢n

(1.31) Fα (x) , Fα (xα) = min x∈Rn

N (cid:88)

(cid:240) (cid:31)¥y Fα (x) x¡c (cid:31)(cid:224)nh b(cid:240)i

Rm +

Rn ,

j=1

Fα (x) = (cid:107)F (x)(cid:107)2 αµjϕj (x) + α (cid:107)x − x∗(cid:107)2

0 ≤ µ1 ≤ µj ≤ µj+1 < 1, j = 2, ..., N − 1,

F (x) = (f1 (x) , ..., fm (x))T ,

v(cid:160) x∗ l(cid:160) phƒn tß n(cid:160)o (cid:31)(cid:226) trong Rn.

S(cid:252) hºi t(cid:246) cıa nghi»m hi»u ch¿nh (cid:31)(cid:247)æc chøng minh qua (cid:31)(cid:224)nh l(cid:254) sau. (cid:30)(cid:224)nh l(cid:254) 1.23. ([2]) Cho αk → 0, khi k → ∞ th… m(cid:229)i d¢y (cid:8)xk(cid:9), (cid:240) (cid:31)¥y xk := xαk l(cid:160) nghi»m cıa (1.31) v(cid:238)i α thay b(cid:240)i αk, c(cid:226) mºt d¢y con hºi t(cid:246). Gi(cid:238)i h⁄n cıa m(cid:229)i d¢y con hºi t(cid:246) l(cid:160) nghi»m c(cid:226) x∗ - chu'n nh(cid:228) nh§t (x∗ − M N S). N‚u ˜x c(cid:226) (x∗ − M N S) l(cid:160) duy nh§t th…

xk = ¯x. lim k→∞

— (cid:31)(cid:224)nh l(cid:254) tr¶n nghi»m hi»u ch¿nh hºi t(cid:246) (cid:31)‚n nghi»m cıa b(cid:160)i to¡n b(cid:242) tŒng qu¡t khi n(cid:226) c(cid:226) nghi»m x∗ - MNS duy nh§t. Trong tr(cid:247)(cid:237)ng hæp nghi»m

n(cid:160)y kh(cid:230)ng c(cid:226) t‰nh ch§t (cid:31)(cid:226) th… ta l(cid:160)m nh(cid:247) th‚ n(cid:160)o? Ta (cid:31)i x†t b(cid:160)i to¡n b(cid:242)

tŒng qu¡t c(cid:226) r(cid:160)ng buºc l(cid:160) mºt t“p (cid:31)(cid:226)ng l(cid:231)i.

Tr(cid:247)(cid:237)ng hæp 2: Hi»u ch¿nh b(cid:160)i to¡n b(cid:242) tŒng qu¡t c(cid:226) r(cid:160)ng buºc.

— (cid:31)¥y ta x†t b(cid:160)i to¡n b(cid:242) tŒng qu¡t c(cid:226) r(cid:160)ng buºc, k(cid:254) hi»u b(cid:240)i CGCP:

(cid:31)(cid:226) l(cid:160) t…m mºt phƒn tß

(1.32) ˜x ∈ C : g (˜x) ≤ 0, h (˜x) ≤ 0, (cid:104)g (˜x) , h (˜x)(cid:105)Rm = 0,

(cid:240) (cid:31)¥y C l(cid:160) t“p (cid:31)(cid:226)ng, l(cid:231)i trong Rn. (cid:30)(cid:176)t

ϕi (x) = max {0, gi (x)} , i = 1, m,

ϕm+i (x) = max {0, hi (x)} , i = 1, m.

Rª r(cid:160)ng

Si := {x ∈ Rn : gi (x) ≤ 0} = {x ∈ Rn : ϕi (x) = 0} , i = 1, m,

Sm+i := {x ∈ Rn : hi (x) ≤ 0} = {x ∈ Rn : ϕm+i (x) = 0} , i = 1, m,

h(cid:160)m ϕi li¶n t(cid:246)c, kh(cid:230)ng ¥m tr¶n Rn. Ngo(cid:160)i ra ta c(cid:226)

j=1Sj, j = 1, ...., 2m := N.

ϕj (y) = 0∀y ∈ ∩N

j=1Sj = {x ∈ Rn : g (x) ≤ 0, h (x) ≤ 0} . ∩N

v(cid:160)

m (cid:88)

Hi”n nhi¶n

i=1 ⇔ gi (˜x) , hi (˜x) = 0, i = 1, ..., m.

gi (˜x) , hi (˜x) = 0 (cid:104)g (˜x) , h (˜x)(cid:105)Rm =

X†t h(cid:160)m

fi (x) = gi (x) hi (x)

v(cid:160) (cid:31)(cid:176)t

(1.33) S0 := {x ∈ Rn : fi (x) = 0, i = 1, ..., m} .

(cid:1) sao cho

j=1Si

B(cid:160)i to¡n CGCP (1.32) t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng v(cid:238)i vi»c t…m mºt phƒn tß ˜x thuºc C ∩ (cid:0)∩N

j=1Si)

(1.34) ϕj (˜x) = ϕj (x) , j = 1, ..., N, min x∈C∩(∩N

(cid:30)” gi£i b(cid:160)i to¡n c(cid:252)c tr(cid:224), ta x†t b(cid:160)i to¡n tŁi (cid:247)u v(cid:230) h(cid:247)(cid:238)ng kh(cid:230)ng r(cid:160)ng buºc sau: t…m mºt phƒn tß xα ∈ Rn sao cho

(1.35) Fα (x) , α > 0, xα ∈ Rn, Fα (xα) = min x∈Rn

v(cid:238)i Fα (x) x¡c (cid:31)(cid:224)nh b(cid:240)i

Rn ,

j=1

Fα (x) = (cid:107)x − PC (x)(cid:107)2 Rm N (cid:88) + (1.36) αµjϕj (x) + (cid:107)x − x∗(cid:107)2

0 ≤ µ1 < µ2 < µj+1 < 1, j = 2, ..., N − 1, F (x) = (f1 (x) , f2 (x) , ...., fm (x))T , v(cid:238)i PC (x) l(cid:160) ph†p chi‚u m¶tric cıa x ∈ Rn tr¶n C v(cid:160) x∗ l(cid:160) phƒn tß n(cid:160)o (cid:31)(cid:226) trong Rn. Theo [17] b(cid:160)i to¡n (1.35) c(cid:226) mºt nghi»m xα v(cid:238)i mØi α > 0.

K‚t lu“n

Ch(cid:247)(cid:236)ng 1 d(cid:242)ng (cid:31)” nh›c l⁄i c¡c ki‚n thøc bŒ træ, l(cid:160)m c(cid:230)ng c(cid:246) ph(cid:246)c v(cid:246)

cho ch(cid:247)(cid:236)ng sau cıa lu“n v«n.

Ch(cid:247)(cid:236)ng 2

B(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i

to¡n b(cid:242) tŒng qu¡t

Trong ch(cid:247)(cid:236)ng n(cid:160)y ch(cid:243)ng t(cid:230)i tr…nh b(cid:160)y kh¡i ni»m b(cid:160)i to¡n tŁi (cid:247)u v(cid:238)i

r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng qu¡t v(cid:160) mºt sŁ k‚t qu£ nghi¶n cøu cıa

Kanzow v(cid:160) Schwartz [11]. Ti‚p theo l(cid:160) tr…nh b(cid:160)y ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh

b(cid:160)i to¡n tŁi (cid:247)u v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng qu¡t, c¡c (cid:31)(cid:224)nh l(cid:254) chøng

minh t(cid:231)n t⁄i nghi»m v(cid:160) cuŁi c(cid:242)ng l(cid:160) v‰ d(cid:246) sŁ minh h(cid:229)a ph(cid:247)(cid:236)ng ph¡p hi»u

ch¿nh b‹ng mºt b(cid:160)i to¡n c(cid:246) th”. C¡c ki‚n thøc (cid:240) tr¶n (cid:31)(cid:247)æc tr‰ch tł t(cid:160)i li»u

[2], [11].

2.1 Ph¡t bi”u b(cid:160)i to¡n

(cid:30)(cid:224)nh ngh(cid:190)a 2.1. B(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) hay b(cid:160)i to¡n

c¥n b‹ng (cid:31)(cid:247)æc k(cid:254) hi»u l(cid:160) MPEC (cid:31)(cid:226) l(cid:160) b(cid:160)i to¡n t…m:

min f (x) , (2.1)

v(cid:238)i c¡c r(cid:160)ng buºc

= 0, ∀i = 1, 2, ...., q, ˜gi (x) ≤ 0, ∀i = 1, 2, ...., m, ˜hi (x) ≤ 0, ∀i = 1, 2, ...., p, (cid:69) (cid:68) ˆgi (x) , ˆhi (x) ˆgi (x) ≥ 0, ˆhi (x) ≥ 0,

(cid:240) (cid:31)¥y f, ˜gi, ˜hi, ˆgi, ˆhi : Rn → R l(cid:160) c¡c h(cid:160)m kh£ vi li¶n t(cid:246)c.

Khi nghi¶n cøu MPEC, Kanzow v(cid:160) Schwartz [14] (cid:31)¢ x†t b(cid:160)i to¡n phi

tuy‚n

min f (x) , (2.2)

v(cid:238)i c¡c r(cid:160)ng buºc

˜gi (x) ≤ 0; ∀i = 1, 2, ...., m, ˜hi (x) ≤ 0; ∀i = 1, 2, ...., p,

v(cid:160) x¡c (cid:31)(cid:224)nh t“p I˜g (x∗) := {i |˜gi (x∗) = 0} v(cid:238)i b§t k(cid:253) x∗ ∈ Rn l(cid:160) (cid:31)i”m ch§p nh“n (cid:31)(cid:247)æc cıa b(cid:160)i to¡n (2.2). K(cid:254) hi»u Z l(cid:160) t“p c¡c (cid:31)i”m ch§p nh“n (cid:31)(cid:247)æc cıa b(cid:160)i to¡n (2.2) v(cid:160) x∗ ∈ Z t(cid:242)y (cid:254).

(cid:26)

(cid:27)

N(cid:226)n ti‚p tuy‚n cıa Z t⁄i x∗ (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh l(cid:160)

(cid:12) (cid:12) (cid:12) (cid:12)

d ∈ Rn → d , Tz (x∗) := ∃ (cid:8)xk(cid:9) ⊆ Z, ∃ {τk} ↓ 0 : xk → x∗, xk − x∗ τk

Lz (x∗) :=

n(cid:226)n tuy‚n t‰nh cıa Z t⁄i x∗ (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh b(cid:240)i: d ∈ Rn (cid:12) (cid:110) (cid:12)∇˜gi(x∗)T d ≤ 0 (i ∈ I ˜gi (x∗)) , (cid:12) ∇˜hi(x∗)T d = 0 (i = 1, 2, ..., p)} ,

v(cid:160) n(cid:226)n (cid:31)Łi c(cid:252)c t(cid:238)i mºt n(cid:226)n t(cid:242)y (cid:254) C ⊆ Rn (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh l(cid:160)

(cid:12)∀d ∈ C : sT d ≤ 0(cid:9) .

C 0 := (cid:8)s ∈ Rn (cid:12)

Tr¶n c(cid:236) s(cid:240) nhœng kh¡i ni»m ban (cid:31)ƒu n(cid:160)y, h(cid:229) (cid:31)¢ (cid:31)(cid:247)a ra (cid:31)(cid:224)nh ngh(cid:190)a.

(cid:30)(cid:224)nh ngh(cid:190)a 2.2. Mºt (cid:31)i”m ch§p nh“n (cid:31)(cid:247)æc x∗ cıa b(cid:160)i to¡n (2.2) (cid:31)(cid:247)æc g(cid:229)i

(cid:110)

(cid:111)

l(cid:160) th(cid:228)a m¢n

i). LICQ n‚u c¡c vect(cid:236) gradients {∇˜gi (x∗) |i ∈ I˜g (x∗)}∪ ∇˜hi (x∗) |i = 1, 2, ..., p

(cid:31)ºc l“p tuy‚n t‰nh;

ii). ACQ n‚u Tz (x∗) = Lz (x∗);

iii). GCQ n‚u Tz(x∗)o = Lz(x∗)o.

D„ th§y mŁi quan h»

LICQ ⇒ ACQ ⇒ GCQ.

Gi£ sß X l(cid:160) ch§p nh“n (cid:31)(cid:247)æc cıa (2.1) v(cid:160) x¡c (cid:31)(cid:224)nh c¡c t“p ch¿ sŁ (cid:31)Łi v(cid:238)i x∗ ∈ X nh(cid:247) sau

(cid:110)

(cid:111)

I˜g (x∗) := {i |˜gi (x∗) = 0} ,

(cid:110)

i , I0+ (x∗) :=

(cid:111)

(cid:110)

i , I00 (x∗) :=

(cid:12) (cid:12)ˆgi (x∗) = 0, ˆhi (x∗) > 0 (cid:12) (cid:12) (cid:111) (cid:12)ˆgi (x∗) = 0, ˆhi (x∗) = 0 (cid:12) (cid:12) (cid:12)ˆgi (x∗) = 0, ˆhi (x∗) = 0 (cid:12)

i . I+0 (x∗) :=

(cid:30)(cid:224)nh ngh(cid:190)a 2.3. Cho x∗ l(cid:160) (cid:31)i”m ch§p nh“n (cid:31)(cid:247)æc cıa b(cid:160)i to¡n MPEC (2.1), x∗ (cid:31)(cid:247)æc g(cid:229)i l(cid:160):

m (cid:88)

p (cid:88)

i). Dłng y‚u n‚u n(cid:226) c(cid:226) bº λ ∈ Rm, µ ∈ Rp, λ, ν ∈ Rq sao cho

i=1

q (cid:88)

∇f (x∗) + λi∇˜gi (x∗) + µi∇˜hi (x∗)

i=1

− γi∇ˆgi (x∗) − νi∇ˆhi (x∗) = 0

v(cid:160)

λi ≥ 0, λi˜gi (x∗) = 0 (i = 1, 2, ..., m) ,

γi = 0 (i ∈ I+0 (x∗)) , νi = 0 (i ∈ I0+ (x∗)) ;

ii). C - dłng n‚u n(cid:226) l(cid:160) dłng y‚u v(cid:160) λiνi ≥ 0 ∀i ∈ I00 (x∗) ;

iii). M - dłng n‚u n(cid:226) l(cid:160) dłng y‚u v(cid:160) λi > 0, νi > 0 ho(cid:176)c λiνi = 0 v(cid:238)i m(cid:229)i

i ∈ I00 (x∗) ;

iv). Dłng m⁄nh n‚u n(cid:226) l(cid:160) (cid:31)i”m dłng y‚u v(cid:160) λi > 0, νi > 0 v(cid:238)i m(cid:229)i i ∈

I00 (x∗) ;

v). B - dłng n‚u ∇f (x∗)T d ≥ 0 v(cid:238)i m(cid:229)i d ∈ TX (x∗).

C¡c kh¡i ni»m tr¶n c(cid:226) li¶n quan (cid:31)‚n nhau, d„ th§y

Dłng m⁄nh ⇒ M - dłng ⇒ C - dłng ⇒ dłng y‚u.

(cid:30)(cid:224)nh ngh(cid:190)a 2.4. Mºt (cid:31)i”m ch§p nh“n (cid:31)(cid:247)æc x∗ cıa MPEC (2.1) (cid:31)(cid:247)æc g(cid:229)i

l(cid:160) th(cid:228)a m¢n

(cid:111)

i). MPEC - LICQ n‚u gradients

(cid:110) ∇˜hi (x∗) |i = 1, 2, ..., p (cid:110)

(cid:111)

{∇˜gi (x∗) |i ∈ I˜g (x∗)} ∪

∪ {∇ˆgi (x∗) |i ∈ I00 (x∗) ∪ I0+ (x∗)} ∪ ∇ˆhi (x∗) |i ∈ I00 (x∗) ∪ I+0 (x∗)

(cid:31)ºc l“p tuy‚n t‰nh,

ii). MPEC - GCQ n‚u TX(x∗)o = LM P EC(x∗)o, (cid:240) (cid:31)¥y

(cid:17) (cid:16)

||LM P EC (x∗) := {d ∈ Rn (cid:12) (cid:12)∇˜gi(x∗)T d ≤ 0, ∀i ∈ I˜g (x∗) , (cid:12)

(cid:17) ∇ˆhi(x∗)T d

∇˜hi(x∗)T d = 0, ∀i = 1, 2, ..., p, ∇ˆgi(x∗)T d = 0, ∀i ∈ I0+ (x∗) , ∇ˆhi(x∗)T d = 0, ∀i ∈ I+0 (x∗) , ∇ˆgi(x∗)T d ≥ 0, ∇ˆhi(x∗)T d ≥ 0, ∀i ∈ I00 (x∗) , (cid:16) = 0, ∀i ∈ I00 (x∗)} ∇ˆgi(x∗)T d

(cid:30)” gi£i b(cid:160)i to¡n MPEC Kadrani, Dussault v(cid:160) Benchakroun [9] (cid:31)¢ sß

d(cid:246)ng ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh b‹ng c¡ch thay th‚ nhœng (cid:31)i•u ki»n b(cid:242)

(cid:69) (cid:68) ˆgi (x) , ˆhi (x)

= 0, ∀i = 1, 2, ..., q, (2.3) ˆgi (x) ≥ 0, ˆhi (x) ≥ 0,

(cid:16)

(cid:17)

b(cid:240)i

≤ 0, ∀i = 1, 2, ..., q ˆgi (x) ≥ −t, ˆhi (x) ≥ −t, ˆgi (x) − t, ˆhi (x) − t

v(cid:238)i h(cid:160)m sŁ t > 0. V• m(cid:176)t l(cid:254) thuy‚t, ph(cid:247)(cid:236)ng ph¡p n(cid:160)y tŁt h(cid:236)n nhi•u so

v(cid:238)i c¡c ph(cid:247)(cid:236)ng ph¡p tr(cid:247)(cid:238)c (cid:31)(cid:226); tuy nhi¶n t“p ch§p nh“n (cid:31)(cid:247)æc cıa b(cid:160)i to¡n

hi»u ch¿nh hƒu h‚t l(cid:160) r(cid:237)i r⁄c v… th‚ mºt sŁ b(cid:160)i to¡n g(cid:176)p kh(cid:226) kh«n khi gi£i.

(cid:30)” lo⁄i b(cid:228) nhœng nh(cid:247)æc (cid:31)i”m n(cid:160)y, Kanzow v(cid:160) Schwartz [11] (cid:31)¢ x¥y d(cid:252)ng

ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh m(cid:238)i m(cid:160) v¤n hºi t(cid:246) t(cid:238)i (cid:31)i”m M - dłng nh(cid:247) sau.

(cid:26)

Cho h(cid:160)m ϕ : Rn → R x¡c (cid:31)(cid:224)nh b(cid:240)i

ϕ (a, b) := ab n‚u a + b ≥ 0, (cid:0)a2 + b2(cid:1) n‚u a + b < 0. − 1 2

D(cid:252)a v(cid:160)o h(cid:160)m ϕ, h(cid:229) (cid:31)¢ x¡c (cid:31)(cid:224)nh ¡nh x⁄ kh£ vi li¶n t(cid:246)c φ : Rn → Rq sao

(cid:17) (cid:16) ˆgi (x) − t, ˆhi (x) − t

(cid:16)

(cid:17) ˆgi (x) − t, ˆhi (x) − t

cho



(cid:16)ˆhi (x) − t

2(ˆgi (x) − t)2 +

φi (x; t) : = ϕ   = n‚u ˆgi (x) + ˆhi (x) ≥ 2t, (cid:17)2 − 1 n‚u ˆgi (x) + ˆhi (x) < 2t,

(cid:240) (cid:31)¥y t ≥ 0 l(cid:160) mºt tham sŁ t(cid:242)y (cid:254). Khi (cid:31)(cid:226), c(cid:226) th” x¥y d(cid:252)ng b(cid:160)i to¡n hi»u

ch¿nh NLP(t), t ≥ 0 nh(cid:247) sau

min f (x) .

v(cid:238)i c¡c r(cid:160)ng buºc

˜gi(x) ≤ 0 ∀i = 1, 2, ..., m,

ˆgi(x) ≥ 0 ∀i = 1, 2, ..., q,

ˆhi(x) ≥ 0 ∀i = 1, 2, ..., q,

φi(x; t) ≤ 0 ∀i = 1, 2, ...., q.

Thay (cid:31)i•u ki»n b(cid:242) (2.3) b(cid:240)i

ˆgi (x) ≥ 0, ˆhi (x) ≥ 0, φi (x; t) ≤ 0 ∀i = 1, 2, ..., q

v(cid:160) x¡c (cid:31)(cid:224)nh c¡c c(cid:176)p ch¿ sŁ:

(cid:110) i

I˜g(x) := {i |˜gi(x) = 0} ,

, ˆhi(x) = 0 Iˆh(x) := Iˆg(x) := {i |ˆgi(x) = 0} , (cid:12) (cid:111) (cid:12) (cid:12)

Iφ (x; t) := {i |φi(x; t) = 0} ,

v(cid:238)i t ≥ 0 v(cid:160) x l(cid:160) (cid:31)i”m ch§p nh“n (cid:31)(cid:247)æc (cid:31)Łi v(cid:238)i NLP(t). Ph¥n ho⁄ch t“p ch¿

(cid:111)

(cid:110)

sŁ Iφ (x; t) sao cho

(cid:110)

(cid:111)

, i ∈ Iφ (x; t) I 00 φ (x; t) :=

(cid:111)

(cid:110)

, i ∈ Iφ (x; t) I 0+ φ (x; t) :=

(cid:12) (cid:12)ˆgi (x) − t = 0, ˆhi (x) − t = 0 (cid:12) (cid:12) (cid:12)ˆgi (x) − t = 0, ˆhi (x) − t > 0 (cid:12) (cid:12) (cid:12)ˆgi (x) − t > 0, ˆhi (x) − t = 0 (cid:12)

. i ∈ Iφ (x; t) I +0 φ (x; t) :=

(cid:17)

Tł (cid:31)(cid:224)nh ngh(cid:190)a cıa φ ta suy ra

(cid:16)ˆhi (x) − t

= 0. φi (x; t) = 0 ⇔ ˆgi (x) − t ≥ 0, ˆhi (x) − t ≥ 0, (ˆgi (x) − t)

Thay t b‹ng {tk}, h(cid:229) (cid:31)¢ thu (cid:31)(cid:247)æc k‚t qu£ sau:

(cid:0)xk(cid:1) ≤ tk, hi

(cid:30)(cid:224)nh l(cid:254) 2.1. ([11]) Cho {tk} ↓ 0 v(cid:160) (cid:8)(cid:0)xk, λk, µk, γk, νk, δk(cid:1)(cid:9) l(cid:160) mºt d¢y (cid:31)i”m KKT cıa N LP (tk) v(cid:238)i xk → x∗. N‚u MPEC - LICQ (cid:31)(cid:243)ng t⁄i x∗ th… x∗ l(cid:160) mºt (cid:31)i”m M - dłng cıa b(cid:160)i to¡n MPEC (2.1).

(cid:30)(cid:224)nh l(cid:254) 2.2. ([11]) Cho {tk} ↓ 0 v(cid:160) (cid:8)(cid:0)xk, λk, µk, γk, νk, δk(cid:1)(cid:9) l(cid:160) mºt d¢y (cid:31)i”m KKT cıa N LP (tk) v(cid:238)i xk → x∗. N‚u MPEC - LICQ (cid:31)(cid:243)ng t⁄i x∗ (cid:0)xk(cid:1) ≤ tk v(cid:238)i m(cid:229)i k ∈ K v(cid:238)i m(cid:229)i v(cid:160) c(cid:226) K ⊆ N sao cho gi i ∈ I00 (x∗) (cid:31)(cid:243)ng th… x∗ l(cid:160) mºt (cid:31)i”m dłng m⁄nh cıa b(cid:160)i to¡n MPEC (2.1).

2.2 Ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho b(cid:160)i to¡n (cid:31)(cid:176)t ra

(cid:30)” gi£i b(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng qu¡t, ta (cid:31)(cid:176)t g (x) = −ˆg (x) , h (x) = −ˆh (x) v(cid:160) x†t b(cid:160)i to¡n c(cid:252)c tr(cid:224): ˜x ∈ C ∩ ˜S, th(cid:228)a m¢n (cid:31)i•u ki»n

ϕ (y) , (2.4) ϕ (˜x) = min y∈C∩ ˜S

(cid:110)

(cid:111)

(cid:240) (cid:31)¥y C l(cid:160) t“p (cid:31)(cid:226)ng, l(cid:231)i trong kh(cid:230)ng gian Euclid Rn, ˜S = ˜S1 ∩ ˜S2, trong (cid:31)(cid:226)

x ∈ Rn : ˜g (x) ≤ 0, ˜h (x) = 0 , ˜S1 =

(2.5) ˜S2 = {x ∈ Rn : g (x) ≤ 0, h (x) ≤ 0, (cid:104)g (x) , h (x)(cid:105)Rm = 0} ,

c¡c h(cid:160)m th(cid:252)c ϕ : Rn → R, ˜g : Rn → Rm, ˜h : Rn → Rp, g v(cid:160) h : Rn → Rq l(cid:160) li¶n t(cid:246)c. Ta gi£ thi‚t t“p nghi»m cıa (2.4)-(2.5) kh¡c rØng.

Khi ˜S2 = Rn (2.4)-(2.5) l(cid:160) b(cid:160)i to¡n c(cid:252)c tr(cid:224) phi tuy‚n c(cid:226) r(cid:160)ng buºc tŒng qu¡t. B(cid:160)i to¡n n(cid:160)y (cid:31)(cid:247)æc c¡c nh(cid:160) khoa h(cid:229)c gi£i b‹ng ph(cid:247)(cid:236)ng ph¡p hi»u

ch¿nh Tikhonov cho b(cid:160)i to¡n c(cid:252)c ti”u kh(cid:230)ng r(cid:160)ng buºc nh(cid:247) sau

m (cid:88)

˜Fα (x) , α > 0,

j=1

+ (2.6) ˜Fα (xα) = αµjψj (x) + αµm+1ϕ (x) ˜Fα (xα) = min x∈n (cid:13) (cid:13) 2 ˜F (x) (cid:13) (cid:13) (cid:13) (cid:13)

Rn , 0 ≤ µ1 ≤ µ2 < .... < µm+1 < 1,

+ α (cid:107)x − x∗(cid:107)2

(cid:17)T

(cid:240) (cid:31)¥y

(cid:16) ˜f1 (x) , ˜f2 (x) , ...., ˜fp (x)

˜F (x) = , ˜fi = ˜hi (x)

v(cid:160) ψj (x) = max {0, ˜gj (x)}. Ti‚p theo, (cid:31)” c£i ti‚n (2.6), ch(cid:243)ng t(cid:230)i (cid:31)(cid:247)a ra

ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh m(cid:238)i ki”u Tikhonov cho MPEC (2.4)-(2.5). (cid:30)” l(cid:160)m

(cid:31)i•u n(cid:160)y, ta (cid:31)(cid:176)t:

ϕj (x) = max {0, ˜gj (x)} , j = 1, 2, ..., m,

ϕm+j (x) = max {0, gj (x)} , j = 1, 2, ..., q,

ϕm+q+j (x) = max {0, hj (x)} , j = 1, 2, ..., q,

fi (x) = ˜hi (x) , i = 1, 2, ..., p,

fp+i (x) = gi(x)hi (x) , i = 1, 2, ..., q.

Theo gi£ thi‚t, ˜g, ˜h, g, h li¶n t(cid:246)c, h(cid:160)m ϕj v(cid:160) fj x¡c (cid:31)(cid:224)nh nh(cid:247) tr¶n, v(cid:238)i j = 1, 2, ..., N (:= m + 2q) v(cid:160) i = 1, 2, ..., M (:= p + q) l(cid:160) li¶n t(cid:246)c. D„ ch¿

ra r‹ng

Sj := {x ∈ Rn : ˜gj (x) ≤ 0} = {x ∈ Rn : ϕj (x) = 0} , j = 1, m,

Sm+j := {x ∈ Rn : gj (x) ≤ 0} = {x ∈ Rn : ϕm+j (x) = 0} , j = 1, q,

Sm+q+j := {x ∈ Rn : hj (x) ≤ 0} = {x ∈ Rn : ϕm+q+j (x) = 0} , j = 1, m,

do ϕj (x) ≥ 0 v(cid:238)i m(cid:229)i x ∈ Rn, j = 1, 2, ..., N . Ta x†t t“p

(cid:111) (cid:110) x ∈ Rn : ˜h (x) = 0, (cid:104)g (x) , h (x)(cid:105)Rn = 0

, S0 :=

Rª r(cid:160)ng

S0 := {x ∈ Rn : fi (x) = 0, i = 1, 2, ..., M } .

Tł fi v(cid:160) ϕj li¶n t(cid:246)c, Sj, j = 1, 2, ..., N , (cid:31)(cid:226)ng. H(cid:236)n nœa, ta c(cid:226) ˜S = (cid:84)N j=0 Sj v(cid:160) C = {x ∈ Rn : x − PC (x) = 0}, (cid:240) (cid:31)¥y k(cid:254) hi»u PC (x) l(cid:160) ph†p chi‚u m¶tric cıa phƒn tß x ∈ Rn l¶n C. B(cid:240)i v“y, b(cid:160)i to¡n MPEC(2.4)-(2.5)

(cid:1) sao cho

j=0Sj

t(cid:247)(cid:236)ng (cid:31)(cid:247)(cid:236)ng v(cid:238)i b(cid:160)i to¡n tŁi (cid:247)u c(cid:226) r(cid:160)ng buºc (cid:31)ﬂng thøc sau: t…m mºt phƒn tß ˜x ∈ C ∩ (cid:0)∩N

j=0Sj)

ϕ (˜x) = ϕ (x) . (2.7) min x∈C∩(∩N

(cid:30)” gi£i (2.7), cƒn ph£i gi£i hai b(cid:160)i to¡n con

i). gi£i h» ph(cid:247)(cid:236)ng tr…nh phi tuy‚n ϕj (x) = 0, fi (x) = 0 v(cid:238)i j = 1, 2, ..., N, i =

(cid:1) .

1, 2, ..., M v(cid:160) x − Pc (x) = 0;

j=0Sj

ii). c(cid:252)c ti”u h(cid:160)m ϕ (x) tr¶n t“p C ∩ (cid:0)∩N

Hi”n nhi¶n, mØi b(cid:160)i to¡n con l(cid:160) kh(cid:230)ng ch¿nh. (cid:30)” hi»u ch¿nh (cid:31)(cid:231)ng th(cid:237)i c¡c

b(cid:160)i to¡n con n(cid:160)y, ch(cid:243)ng t(cid:230)i c(cid:252)c ti”u h(cid:160)m tr(cid:236)n Tikhonov tr¶n to(cid:160)n bº kh(cid:230)ng gian Rn. C(cid:246) th”, ch(cid:243)ng t(cid:230)i t…m mºt phƒn tß xα ∈ Rn sao cho

N (cid:88)

Fα (xα) = min Fα (x) , x∈Rn Fα (x) = (cid:107)x − Pc (x)(cid:107)2 (2.8)

Rn ,

j=1

+ ϕj (x) + αµϕ (x) + α (cid:107)x − x∗(cid:107)2

V(cid:238)i mØi tham sŁ cŁ (cid:31)(cid:224)nh α > 0, (cid:240) (cid:31)¥y

F (x) = (f1 (x) , f2 (x) , .....fM (x))T , µ ∈ (0, 1)

l(cid:160) mºt sŁ cŁ (cid:31)(cid:224)nh v(cid:160) x∗ l(cid:160) phƒn tß n(cid:160)o (cid:31)(cid:226) trong Rn. Gi£ sß ϕ (x) ≥ 0 v(cid:238)i m(cid:229)i x ∈ Rn v(cid:160) n(cid:226) c(cid:226) t“p møc gi(cid:238)i nºi, ngh(cid:190)a l(cid:160) t“p {x ∈ Rn : ϕ (x) ≤ c} gi(cid:238)i nºi v(cid:238)i c > 0 b§t k(cid:253). Nh(cid:247) (cid:31)¢ bi‚t trong [17], b(cid:160)i to¡n (2.8) c(cid:226) mºt nghi»m xα v(cid:238)i m(cid:229)i α > 0. H(cid:236)n nœa, nghi»m v¤n Œn (cid:31)(cid:224)nh khi ϕ, ˜g, ˜h, g, h c(cid:226) nhi„u [13].

Ch(cid:243)ng t(cid:230)i (cid:31)¢ chøng minh (cid:31)(cid:247)æc s(cid:252) hºi t(cid:246) cıa nghi»m hi»u ch¿nh qua

(cid:31)(cid:224)nh l(cid:254) sau.

(cid:30)(cid:224)nh l(cid:254) 2.3. Cho αk → 0, khi k → ∞ th… m(cid:229)i d¢y (cid:8)xk(cid:9), (cid:240) (cid:31)¥y xk := xαk l(cid:160) mºt nghi»m cıa (2.8) v(cid:238)i α thay b(cid:240)i αk , c(cid:226) mºt d¢y con hºi t(cid:246). Gi(cid:238)i

h⁄n cıa m(cid:229)i d¢y con hºi t(cid:246) l(cid:160) mºt nghi»m cıa (2.4)-(2.5). N‚u th¶m (cid:31)i•u

ki»n (2.4)-(2.5) c(cid:226) mºt nghi»m duy nh§t, k(cid:254) hi»u b(cid:240)i ˜x th…

xk = ˜x. lim k→∞

N (cid:88)

Chøng minh. Do xk l(cid:160) mºt c(cid:252)c ti”u cıa Fα (x), tł (2.8) ta c(cid:226)

(cid:13) (cid:13)xk − PC

Rn + (cid:13) (cid:0)xk(cid:1)(cid:13) 2 (cid:13)

(cid:13)F (cid:0)xk(cid:1)(cid:13) 2 RM + (cid:13)

kϕ (cid:0)xk(cid:1)

j=1

ϕj(xk) + αµ

Rn + (cid:107)F (y)(cid:107)2

(cid:13)xk − x∗(cid:13) 2 Rn ≤ (cid:107)y − PC (y)(cid:107)2 (cid:13)

N (cid:88)

(2.9) + αk (cid:13)

Rn ,

kϕ (y) + αk (cid:107)y − x∗(cid:107)2

j=1

(cid:1), ta c(cid:226) y −PC (y) =

j=0Sj

(cid:0)xk(cid:1) ≥ 0, j = 1, 2, ..., N . Tł (2.9) suy ra

+ ϕj (y) + αµ

v(cid:238)i phƒn tß cŁ (cid:31)(cid:224)nh y ∈ Rn b§t k(cid:253). L§y y ∈ C ∩(cid:0)∩N 0 = F (y) v(cid:160) ϕj

k (cid:107)y − x∗(cid:107)n R.

ϕ (cid:0)xk(cid:1) ≤ ϕ (y) + α1−µ (2.10)

Tł ϕ l(cid:160) ch(cid:176)n (cid:31)•u, t“p (cid:8)xk(cid:9) b(cid:224) ch(cid:176)n. L§y (cid:8)xl(cid:9) ⊂ (cid:8)xk(cid:9) sao cho xl → ¯x khi l → ∞ . Ta s‡ chøng minh ¯x l(cid:160) mºt nghi»m cıa (2.4)-(2.5). Tł (2.9) v(cid:160)

(cid:0)xl(cid:1) ≤ αµ

t‰nh ch§t cıa ϕ v(cid:160) ϕj, ta c(cid:226)

Rn .

(cid:13)xk − PC

(cid:13)F (cid:0)xl(cid:1)(cid:13) 2 RM , ϕj (cid:13)

Rn , (cid:13) (cid:0)xk(cid:1)(cid:13) 2 (cid:13)

l ϕ (y) + αl (cid:107)y − x∗(cid:107)2

0 ≤ (cid:13)

j=0Sj

(cid:9) sao cho

Cho l → ∞ (cid:240) b§t (cid:31)ﬂng thøc cuŁi, nh(cid:237) t‰nh ch§t li¶n t(cid:246)c cıa PC ([17]), F v(cid:160) ϕj (cid:31)£m b£o r‹ng ¯x = PC (¯x) , F (¯x) = 0 = ϕj (¯x), ngh(cid:190)a l(cid:160) ¯x ∈ C∩(cid:0)∩N (cid:1). B¥y gi(cid:237), ph£i chøng minh r‹ng ¯x l(cid:160) nghi»m cıa (2.4)- (2.5). Tł (2.10) thay k b(cid:240)i l, thu g(cid:229)n (cid:31)(cid:247)æc ϕ (¯x) ≤ ϕ (y) v(cid:238)i y b§t k(cid:253) thuºc C ∩ (cid:0)∩N (cid:1). Do (cid:31)(cid:226) ¯x l(cid:160) nghi»m cıa (2.7). Rª r(cid:160)ng, n‚u ¯x l(cid:160) duy nh§t th… ¯x = ˜x v(cid:160) t§t c£ d¢y (cid:8)xk(cid:9) hºi t(cid:246) t(cid:238)i ˜x khi k → ∞.

Gi£ sß thay {ϕ, C, fi, ϕj} b(cid:240)i c¡c nhi„u l(cid:160) (cid:8)ϕδ, Cδ, ϕδ

(cid:12)ϕ (x) − ϕδ (x)(cid:12) (cid:12) (cid:12) ≤ δ, H (Cδ, C) ≤ δ, (cid:12) (cid:12) δ (x) (cid:12) (cid:12) (cid:12) ≤ δ, i = 1, 2, ..., M, (cid:12)fi (x) − fi j (x)(cid:12) (cid:12) (cid:12) ≤ δ, j = 1, 2, ..., N, ∀x ∈ Rn, δ → 0, (cid:12)ϕj (x) − ϕδ

i v(cid:160) ϕδ

j (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh nh(cid:247) fi v(cid:160) ϕj (cid:240) tr¶n ˜g, ˜h, g, h (cid:31)(cid:247)æc cho x§p x¿

(2.11)

α trong Rn sao cho F δ

α (x) , α > 0, δ ≥ 0,

Fδ α

(cid:240) (cid:31)¥y f δ v(cid:160) H (Cδ, C) l(cid:160) kho£ng c¡ch Hausdorff giœa t“p (cid:31)(cid:226)ng l(cid:231)i Cδ v(cid:160) C.

N (cid:88)

X†t b(cid:160)i to¡n tŁi (cid:247)u kh(cid:230)ng r(cid:160)ng buºc sau T…m mºt phƒn tß xδ (cid:1) = min (cid:0)xδ α x∈Rn

Rn + (cid:13)

(cid:13)F δ (x)(cid:13) 2 RM + (cid:13)

α (x) = (cid:107)x − PCδ (x)(cid:107)2 Fδ

j (x)

j=1

(2.12) ϕδ

Rn .

+ αµϕδ (x) + α (cid:107)x − x∗(cid:107)2

1 (x) , f δ

M (x)(cid:1)T — (cid:31)¥y F δ (x) = (cid:0)f δ 2 (x) , ..., f δ to¡n (2.12) c(cid:226) nghi»m, k(cid:254) hi»u b(cid:240)i xδ α.

. Theo [17], v(cid:238)i mØi α > 0 b(cid:160)i

Ch(cid:243)ng t(cid:230)i (cid:31)¢ thu ti‚p (cid:31)(cid:247)æc k‚t qu£ sau:

(cid:30)(cid:224)nh l(cid:254) 2.4. Cho αk, δk → 0 sao cho δk → 0 khi k → ∞ th… m(cid:229)i d¢y αk (cid:8)xk(cid:9), (cid:240) (cid:31)¥y xk := xδk αk l(cid:160) mºt nghi»m cıa (2.12) v(cid:238)i α v(cid:160) δ lƒn l(cid:247)æt thay b(cid:240)i αk v(cid:160) δk, c(cid:226) mºt d¢y con hºi t(cid:246). Gi(cid:238)i h⁄n cıa m(cid:229)i d¢y con hºi t(cid:246) l(cid:160)

mºt nghi»m cıa (2.4)-(2.5) c(cid:226) mºt nghi»m duy nh§t, k(cid:254) hi»u b(cid:240)i ˜x th…

xk = ˜x. lim k→∞

N (cid:88)

(cid:0)xk(cid:1)

Chøng minh. Tł (2.12) ta c(cid:226)

(cid:13)F δk (cid:0)xk(cid:1)(cid:13) 2 RM + (cid:13)

(cid:13) (cid:13)xk − PCδk (cid:13)

(cid:0)xk(cid:1)(cid:13) 2 (cid:13) (cid:13)

j=1

+ (cid:13) ϕδk j

(cid:13)xk − x∗(cid:13) 2 Rn ≤ (cid:13)

kϕδk (cid:0)xk(cid:1) + αk (cid:13)

(cid:13) (cid:13) (cid:13)y − PCδk

(cid:13) 2 (cid:13) (cid:13)

N (cid:88)

(2.13) + αδ (y)

Rn ,

(cid:13)F δk (y)(cid:13) 2 RM + (cid:13)

j (y) + αµ ϕδk

kϕδk (y) + αk (cid:107)y − x∗(cid:107)2

j=1

(cid:1) ta c(cid:226) y − PC (y) =

j=0Sj

+ (cid:13)

kϕδk (cid:0)xk(cid:1)

(cid:0)xk(cid:1) ≥ ϕj (y) = 0, j = 1, 2, ..., N. Tł (2.13) suy ra (cid:0)xk(cid:1)(cid:13) 2 (cid:13) (cid:13)

v(cid:238)i phƒn tß y ∈ Rn b§t k(cid:253). L§y y ∈ C ∩ (cid:0)∩N 0, F (y) = 0 v(cid:160) ϕj

(cid:13) (cid:13)xk − PCδk (cid:13) (cid:13) (cid:13) (cid:13)PC (y) − PCδk

(cid:13)F δk (cid:0)xk(cid:1)(cid:13) + (cid:13) 2 RM + αµ (cid:13) (cid:13) 2 (cid:13) (cid:13)

(cid:104)

N (cid:88)

≤ + (cid:107)F δk (y)(cid:107)2 (y) (2.14)

Rn .

(cid:105) j (y) − ϕj (y)

kϕδk (y) + αk (cid:107)y − x∗(cid:107)2

j=1

+ ϕδk + αµ

Tł (2.11) v(cid:160) (2.14) suy ra

Rn ,

(cid:107)y − x∗(cid:107)2 + N ϕδk (cid:0)xk(cid:1) ≤ ϕδk (y) + + α1−µ k (1 + M ) δ2 k αµ k δk αµ k

v… th‚

Rn .

(cid:107)y − x∗(cid:107)2 + N (2.15) ϕ (cid:0)xk(cid:1) ≤ ϕ (y) + 2δk + + α1−µ k (1 + M ) δ2 k αµ k

δk αµ k → 0 khi k → ∞ v(cid:160) ϕ l(cid:160) møc ch(cid:176)n, t“p (cid:8)xk(cid:9) b(cid:224) ch(cid:176)n. L§y Tł δk, αk, δk αk (cid:8)xl(cid:9) l(cid:160) d¢y con cıa d¢y (cid:8)xk(cid:9) sao cho xl → ¯x khi l → ∞. Ta s‡ chøng minh ¯x l(cid:160) nghi»m cıa (2.4)-(2.5). Th“t v“y, tł (2.14) v(cid:160) ϕ (x) ≥ 0 v(cid:238)i x ∈ Rn ta

(cid:13) (cid:13)xl − PCδl (cid:13) ≤ (1 + M ) δ2

Rn .

(cid:0)xl(cid:1)(cid:13) 2 (cid:13) (cid:13) l + αµ

(cid:13)F δl (cid:0)xl(cid:1)(cid:13) + (cid:13) 2 (cid:13) Rn l ϕ (y) + 2δlαµ

l + N δ1 + αl (cid:107)y − x∗(cid:107)2

c(cid:226)

Cho l → ∞ trong b§t (cid:31)ﬂng thøc cuŁi, nh(cid:237) t‰nh ch§t li¶n t(cid:246)c cıa PC, F, αl, δl →

0 v(cid:160) (2.11), ta c(cid:226) ¯x − PC (¯x) = 0 = F (¯x), ngh(cid:190)a l(cid:160) ¯x ∈ C ∩ S0.

(cid:1) ϕj (y) = fi (y) = 0 tł (2.13) v(cid:160) ϕj

j=0Sj

B¥y gi(cid:237), ph£i chøng minh r‹ng ¯x ∈ Sj v(cid:238)i j = 1, 2, ..., N. V(cid:238)i phƒn tß (cid:0)xl(cid:1) ≥ 0, ta c(cid:226)

ϕδl i

(cid:13)F δl (y) − F (y)(cid:13) 2 RM + ϕδl (cid:13)

i (y)

(cid:104)

N (cid:88)

(cid:13) 2 (cid:13) (cid:13) (cid:0)xl(cid:1)(cid:105)

≤ + (cid:13) b§t k(cid:253) y ∈ C ∩ (cid:0)∩N (cid:0)xl(cid:1) + αµ l ϕδl (cid:0)xl(cid:1) (cid:13) (cid:13) (cid:13)PC (y) − PCδl (y)

j (y) − ϕδl ϕδl

l ϕδl (y) + αl (cid:107)y − x∗(cid:107)2

+ αµ +

(cid:13)F δl (y) − F (y)(cid:13) 2 RM + ϕδl (cid:13)

i (y)

j(cid:54)=i (cid:13) (cid:13) (cid:13)PC (y) − PCδl

(cid:13) 2 (cid:13) (cid:13)

(cid:104)

N (cid:88)

≤ (y) + (cid:13)

(cid:0)xl(cid:1)(cid:105)

Rn .

j (y) − ϕj (y) + ϕj

(cid:0)xl(cid:1) − ϕδl j

l ϕδl (y) + αl (cid:107)y − x∗(cid:107)2

j(cid:54)=i

ϕδl + + αµ

i (y)

Ti‚p theo, tł ϕ (cid:0)xl(cid:1) ≥ 0 ta c(cid:226): (cid:0)xl(cid:1) ≤ (1 + M ) δ2 0 ≤ ϕi

+ αµ l

i (y)

≤ (1 + M ) δ2

Rn .

l + 2δl + 2 (N − 1) δl + ϕδl (cid:2)ϕδl (y) + ϕ(xl) − ϕδl (cid:0)xl(cid:1)(cid:3) + αl (cid:107)y − x∗(cid:107)2 l + 2δl + 2 (N − 1) δl + ϕδl l δl + αl (cid:107)y − x∗(cid:107)2

l ϕδl (y) + αµ

+ αµ

Cho l → ∞ (cid:240) b§t (cid:31)ﬂng thøc cuŁi, ta c(cid:226) 0 ≤ ϕi (¯x) ≤ ϕi (y) = 0. Ngh(cid:190)a l(cid:160)

j=0Sj

¯x ∈ Si.

CuŁi c(cid:242)ng, cƒn ph£i chøng minh ¯x l(cid:160) nghi»m cıa (2.7). Nh(cid:247) tr¶n, v(cid:238)i (cid:1), tł (2.15) suy ra ϕ (¯x) ≤ ϕ (y) ∀y ∈ (cid:1). Rª r(cid:160)ng, n‚u ˜x l(cid:160) duy nh§t th… m(cid:229)i d¢y (cid:8)xk(cid:9) hºi t(cid:246) t(cid:238)i ˜x

b§t k(cid:253) phƒn tß y ∈ C ∩ (cid:0)∩N C ∩ (cid:0)∩N j=0Sj khi k → ∞.

(cid:30)(cid:224)nh l(cid:254) (cid:31)(cid:247)æc chøng minh.

2.3 V‰ d(cid:246) minh h(cid:229)a

X†t h(cid:160)m:

ϕ (x) = (x1 − 3)2 + (x2 − 2)2 + x2 3,

h(cid:160)m ˜g (x) (cid:31)(cid:247)æc ch(cid:229)n sao cho ˜g (x) ≤ 0 v(cid:238)i m(cid:229)i x ∈ R3, ˜h(x) = Ax − b, (cid:240) (cid:31)¥y A l(cid:160) ma tr“n vu(cid:230)ng c§p 3 c(cid:226) a22 = 1, aij = 0 v(cid:238)i i, j (cid:54)= 2 v(cid:160) b = (b1, b2, b3)T = (0, 1, 0)T , c¡c h(cid:160)m g, h : R3 → R2 c(cid:226) d⁄ng nh(cid:247) sau:

1 + x2

2 + x2

3 − 25, −x1 + 3(cid:1) , (cid:17)

g (x1, x2, x3) = (cid:0)x2

(cid:16) (x1 − 3)2 + x2

(cid:26)

2 + x2 3 − 4, x1 − 4 (cid:27) √ (cid:16)

, h (x1, x2, x3) =

2 +

≤ 1 . D„ th§y b(cid:160)i v(cid:160) t“p C = x ∈ R3 : (x1 − 3)2 + x2

(cid:17)2 3 (cid:17)

√ x3 − (cid:16) 3 to¡n (2.4)-(2.5) c(cid:226) nghi»m duy nh§t ˜x = .

Ch(cid:229)n µ = 1

3, 1, 2 v(cid:238)i x∗ = (0, 0, 0), tham sŁ hi»u ch¿nh αk = (1 + k)−1 v(cid:160) (cid:31)i”m ban (cid:31)ƒu cho tr(cid:247)(cid:237)ng hæp k = 0 l(cid:160) x0 = (20, 45, 15) (cid:31)” c(cid:252)c ti”u h(cid:160)m

4 (cid:88)

1 2

tr(cid:236)n Tikhonov

R3 +

R3 .

R3 + (cid:107)F (x)(cid:107)2

k ϕ (x) + αk (cid:107)x(cid:107)2

j=1

˜ϕj (x) + α Fαk (x) = (cid:107)x − PC (x)(cid:107)2

(cid:17)

(cid:16)

(cid:240) (cid:31)¥y

3 − 4

2 + x2

3 − 25(cid:1) (cid:16)

2 + x2

1 + x2

, F (x) = , (−x1 + 3) (x1 − 4) (x1 − 3)2 + x2 x2 − 1, (cid:0)x2

(cid:26) x2

3 − 25

1 + x2

v(cid:160)

3 − 25 > 0 3 − 25 ≤ 0,

2 + x2 2 + x2

1 + x2 1 + x2

˜ϕ1 (x) = ϕ1 (x) = n‚u x2 n‚u x2

2 (x) =

2 + x2 0 (cid:26) (x1 − 3)2 0

(cid:40)

˜ϕ2 (x) = ϕ2 n‚u x1 > 3 v(cid:160) x2, x3 b§t k(cid:253) n‚u x1 ≤ 3 v(cid:160) x2, x3 b§t k(cid:253) ,

2 + x2

3 − 4

2 + x2 2 + x2

3 − 4 > 0 3 − 4 ≤ 0,

(x1 − 3)2 + x2 ˜ϕ3 (x) = ϕ3 (x) = 0 n‚u (x1 − 3)2 + x2 n‚u (x1 − 3)2 + x2

4 (x) =

(cid:26) (x1 − 4)2 0

(cid:111)

˜ϕ4 (x) = ϕ2 n‚u x1 > 4 v(cid:160) x2, x3 b§t k(cid:253) n‚u x1 ≤ 4 v(cid:160) x2, x3 b§t k(cid:253) .

(cid:110) Cδk, f δk i

, ϕδk Trong tr(cid:247)(cid:237)ng hæp {C, fi, ϕi, ϕ} c(cid:226) nhi„u δk, ch(cid:243)ng t(cid:230)i t‰nh

(cid:26)

(cid:27)

v(cid:238)i

(cid:16)

(cid:17)2 3

2 +

√ , x ∈ R3 : (x1 − 3)2 + x2 x3 − ≤ (1 + δk)2 Cδk =

ϕδk (x) = ϕ (x) + δk, gδk (x) = g (x) , bδk = b + δk,

v(cid:160)

3 − 25 + δk, −x1 + 3 + δk

(cid:16)

(cid:1) , (cid:17)

gδk (x1, x2, x3) = (cid:0)x2

2 + x2 1 + x2 (x1 − 3)2 + x2

2 + x2

3 − 4 + δk, x1 − 4 + δk

. hδk (x1, x2, x3) =

1 ho(cid:176)c bδk 3 kh¡c 0 th… ph(cid:247)(cid:236)ng tr…nh Ax=bδk kh(cid:230)ng c(cid:226) nghi»m. Do (cid:31)(cid:226), b(cid:160)i to¡n nhi„u c(cid:244)ng s‡ kh(cid:230)ng gi£i (cid:31)(cid:247)æc. Tuy nhi¶n v(cid:238)i ph(cid:247)(cid:236)ng ph¡p gi£i m(cid:238)i n(cid:160)y th… xk

B(cid:160)i to¡n ban (cid:31)ƒu l(cid:160) b(cid:160)i to¡n (cid:31)(cid:176)t kh(cid:230)ng ch¿nh v(cid:160) th¶m n‚u bδk

l(cid:160) c(cid:252)c ti”u cıa h(cid:160)m sau:

(cid:13)F δk (x)(cid:13) 2 (cid:13) R3

(cid:13) (cid:13) (cid:13)x − PCδk

(cid:13) 2 (cid:13) (cid:13)

4 (cid:88)

1 2

(x) = (x) + (cid:13) F δk αk

R3 ,

j (x) + α

k ϕδk (x) + αk (cid:107)x(cid:107)2

j=1

+ ˜ϕδk

(cid:17)

4 , f δk

(cid:16)

(cid:17)

(cid:1) ,

(cid:31)(cid:247)æc t‰nh to¡n v(cid:238)i δk = (1 + k)−2 v(cid:160) αk = (1 + k)−1, (cid:240) (cid:31)¥y (cid:16) F δk (x) = , δk, x2 − 1 + δk, δk, f δk

1 + x2

2 + x2

3 − 25 + δk

2 + x2

3 − 4 + δk

4 = (cid:0)x2 f δk

, (x1 − 3)2 + x2

f δk 5 = (−x1 + 3 + δk) (x1 − 4 + δk) ,

j (x) , (cid:31)(cid:247)æc x¡c (cid:31)(cid:224)nh nh(cid:247) ˜ϕj (x) (cid:240) tr¶n.

v(cid:160) ˜ϕδk

K‚t lu“n

Trong ch(cid:247)(cid:236)ng hai (cid:31)¢ gi(cid:238)i thi»u ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh cho b(cid:160)i to¡n c(cid:252)c

tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng qu¡t.

K‚t lu“n chung

T(cid:226)m l⁄i, b(cid:160)i to¡n b(cid:242) c(cid:226) nhi•u øng d(cid:246)ng trong th(cid:252)c t‚. Do (cid:31)(cid:226), vi»c t…m

ra c¡c ph(cid:247)(cid:236)ng ph¡p gi£i ra nghi»m cıa n(cid:226) l(cid:160) r§t quan tr(cid:229)ng. Trong lu“n

v«n n(cid:160)y (cid:31)¢ gi(cid:238)i thi»u b(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng

qu¡t, v(cid:160) c¡ch gi£i cho b(cid:160)i to¡n (cid:31)(cid:226). Trong lu“n v«n n(cid:160)y ch(cid:243)ng t(cid:230)i (cid:31)¢ gi(cid:238)i

thi»u nhœng k‚t qu£ ch‰nh sau.

1. Nh›c l⁄i mºt sŁ ki‚n thøc li¶n quan nh(cid:247) P - h(cid:160)m, P0 - h(cid:160)m, P - h(cid:160)m

(cid:31)•u, h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u, h(cid:160)m (cid:31)(cid:236)n (cid:31)i»u m⁄nh....

2. Tr…nh b(cid:160)y (cid:31)(cid:224)nh ngh(cid:190)a v• b(cid:160)i to¡n b(cid:242) v(cid:160) c¡c ph(cid:247)(cid:236)ng ph¡p gi£i trong c£

hai tr(cid:247)(cid:237)ng hæp: b(cid:160)i to¡n b(cid:242) tuy‚n t‰nh v(cid:160) b(cid:160)i to¡n b(cid:242) phi tuy‚n.

3. Tr…nh b(cid:160)y v• b(cid:160)i to¡n b(cid:242) tŒng qu¡t v(cid:160) c¡c ph(cid:247)(cid:236)ng ph¡p gi£i cıa n(cid:226)

4. Tr…nh b(cid:160)y ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho b(cid:160)i to¡n b(cid:242) tŒng

qu¡t.

5. Tr…nh b(cid:160)y ph(cid:247)(cid:236)ng ph¡p hi»u ch¿nh Tikhonov cho b(cid:160)i to¡n tŁi (cid:247)u v(cid:238)i

r(cid:160)ng buºc l(cid:160) b(cid:160)i to¡n b(cid:242) tŒng qu¡t.

T(cid:160)i li»u tham kh£o

[1] N. Buong (2006), "Regularization for unconstrained vector opti-

mization of convex functionals in Banach spaces", Comput. Math.

Math. Phys, 46(3), pp. 372-378.

[2] N. Buong and N. T. T. Hoa (2015), "Tikhonov regularization

for mathematical programs with generalized complementarity con-

straints", Comput. Math. Math. phys, 55(4), pp. 564-571.

[3] Burke J. and Xu S. (2000), "A non-interior predictor-corrector

path following algorithm for the monotone linear complementarity

problem ", Math. Program., 87(1),pp.113-130.

[4] Chen - S. J and Pan S. (2008), "A family of NCP functions and

a descent methods for the nonlinear complementarity problem",

Comput. Optim. Appl., 40(3), pp. 389-404.

[5] Facchinei F. and Kanzow C. (1997), "beond monotonicity in reg-

ularization methods for nonlinear complementarity problems",

SIAM J. Control Optim, 9(2),pp. 1150-1161.

[6] Fang L. (2010), "A new one-step smoothing Newton methods for

nonlinear complementarity problems with P0- function ", Appl.

Math. comput., 216, pp. 1087-1095.

[7] Fischer A. (1992), "Solution of monotone complementarity prob-

lems with locally Lipschitzian functions", Math. Program., 76(3),

pp. 513-532.

[8] Geiger C. and Kanzow C. (1996), "On the resolution of monotone

complementarity problems", Comput. Optim. Appl., 5(2), pp. 155-

173.

[9] Kadrani A., Dussault P. J. and Benchakroun A. (2009), "A new

regularization scheme for mathematical programs with comple-

mentarity constraints", SIAM J. Optim.,, 20(1), pp. 78-103.

[10] Kanzow C. (1997), "A new approach to continuation methods for

complementarity programs with uniform P - functions", Oper. Res.

Lett., 20(2), pp. 85-92.

[11] Kanzow C. and Schwartz A. (2013), "A new regularization method

for mathematical programs with complementarity constraints with

strong convergence properties", SIAM J. Optim.,, pp. 770-798.

[12] Kojima M., Megiddo N. and Noma T. (1991), "Homotopy contin-

uation methods for nonlinear complementarity problems", Math.

Oper. Res., 16(4), pp. 754-774.

[13] Liskovets A. O. (1981), "Variational methods for the solution of

unstable problems", Naukai Tekhnika, Minsk.

[14] Mangasarian L. O. and Solodov V. M. (1999), " A linearly con-

vergent derivative - free descent methods for strongly monotone

complementarity properties", Comput . Optim. Appl., 14, pp. 15

- 16.

[15] Olsson D.(2010), "The linear complementarity problem: Methods

and applications", Springer, SF2827 Topics in Optim.

[16] Sun D. (1999), "A regularization Newton methods for solving non-

linear complementarity programs", Appl. Math. Optim., 40(3), pp.

351-339.

[17] Vasilev P. F. (1980), "Numerical methods for solving extreme

problems", "Nauka", Moscow.

Luận văn Thạc sĩ Toán học: Bài toán tối ưu với ràng buộc là bài toán bù tổng quát

B(cid:128)I TO(cid:129)N T¨I (cid:215)U V˛I R(cid:128)NG BU¸C L(cid:128) B(cid:128)I TO(cid:129)N B(cid:210) T˚NG QU(cid:129)T

B(cid:128)I TO(cid:129)N T¨I (cid:215)U V˛I R(cid:128)NG BU¸C L(cid:128) B(cid:128)I TO(cid:129)N B(cid:210) T˚NG QU(cid:129)T

L(cid:237)i cam (cid:31)oan

L(cid:237)i c£m (cid:236)n

M(cid:246)c l(cid:246)c

M(cid:240) (cid:31)ƒu

Ch(cid:247)(cid:236)ng 1

Mºt sŁ ki‚n thøc chu'n b(cid:224)

Ch(cid:247)(cid:236)ng 2

B(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i

to¡n b(cid:242) tŒng qu¡t

K‚t lu“n chung

T(cid:160)i li»u tham kh£o

Có thể bạn quan tâm

Tài liêu mới

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

Luận văn Thạc sĩ Toán học: Bài toán tối ưu với ràng buộc là bài toán bù tổng quát

B(cid:128)I TO(cid:129)N T¨I (cid:215)U V˛I R(cid:128)NG BU¸C L(cid:128) B(cid:128)I TO(cid:129)N B(cid:210) T˚NG QU(cid:129)T

B(cid:128)I TO(cid:129)N T¨I (cid:215)U V˛I R(cid:128)NG BU¸C L(cid:128) B(cid:128)I TO(cid:129)N B(cid:210) T˚NG QU(cid:129)T

L(cid:237)i cam (cid:31)oan

L(cid:237)i c£m (cid:236)n

M(cid:246)c l(cid:246)c

M(cid:240) (cid:31)ƒu

Ch(cid:247)(cid:236)ng 1

Mºt sŁ ki‚n thøc chu'n b(cid:224)

Ch(cid:247)(cid:236)ng 2

B(cid:160)i to¡n c(cid:252)c tr(cid:224) v(cid:238)i r(cid:160)ng buºc l(cid:160) b(cid:160)i

to¡n b(cid:242) tŒng qu¡t

K‚t lu“n chung

T(cid:160)i li»u tham kh£o

Có thể bạn quan tâm

Tài liêu mới

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