Luận văn Một số thuật toán giải bài toán chấp nhận lồi

Ön lim inf n:n thiÕt thùc cho i µ (n) i > 0 t­¬ng ®­¬ng víi lim inf n:n thiÕt thùc cho i λ (n) i > 0 cßn ®iÒu kiÖn ∑ n µ (n) i = +∞ t­¬ng ®­¬ng víi ∑ n λ (n) i = +∞ • NÕu ta bá gi¶ thiÕt∑ n µ (n) i = +∞ trong vÝ dô 12 th× cã thÓ giíi h¹n cña d·y (x(n)) kh«ng n»m trong Ci. VÝ dô sau cho ta thÊy ®iÒu nµy. VÝ dô 14. Cho X := R, N := 2, C1 := C(n)1 :≡ (−∞, 0], C2 := C(n)2 :≡ [0,+∞). Gi¶ sö x(0) > 0, α(n)1 :≡ α(n)2 :≡ 3/2 vµ λ(n)1 < 2/3 ∀n. Khi ®ã x(n) = ( 1− 3 2 λ (n−1) 1 ) · · · ( 1− 3 2 λ (0) 1 ) x(0) vµ do ®ã, lim n x(n) ∈ C1 ⇐⇒ lim n x(n) = 0 ⇐⇒ ∑ n µ (n) 1 = +∞ §Þnh lý 6. Cho tr­íc mét thuËt to¸n chiÕu, gi¶ sö r»ng (P (n) i ) héi tô tõng ®iÓm tíi Pi víi mäi chØ sè i. Gi¶ sö thªm r»ng tån t¹i mét d·y con (n ′) cña (n) sao cho víi mäi chØ sè i ta cã α (n′) i −→ αi, λ(n ′) i −→ λi víi αi nµo ®ã thuéc (0, 2] vµ λi nµo ®ã thuéc (0, 1]. NÕu phÇn trong cña C kh¸c rçng, th× d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm thuéc C. Chøng minh: Theo hÖ qu¶ 4(i), d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm x. Ta ph¶i chØ ra r»ng x ∈ C. Ta sÏ chøng minh P (n′) i x (n′) −→ Pix ∀i. ThËt vËy, v× tÝnh kh«ng gi·n cña phÐp chiÕu, ta cã ‖P (n′)i x(n ′) − P (n′)i x‖ ≤ ‖x(n ′) − x‖. MÆt kh¸c, ta cã P (n′) i x (n′) − P (n′)i x −→ 0. Do λ(n ′) i −→ λi > 0, ta thÊy r»ng i lµ thiÕt thùc t¹i n′ víi mäi n′ ®ñ lín. Tõ gi¶ thiÕt cho P (n ′) i suy ra r»ng P (n′) i x (n′) −→ 31 Pix. B©y giê ta cã x(n ′+1) = N∑ i=1 λ (n′) i ( (1− α(n′)i )x(n ′) + α (n′) i P (n′) i x (n′)) B»ng c¸ch lÊy giíi h¹n theo d·y con (x(n ′)) vµ tõ chøng minh trªn ta cã x = N∑ i=1 λi ( (1− αi)x+ αiPix ) hay x = N∑ i=1 ( λiαi∑N j=1 λjαj ) Pix Tõ ®¼ng thøc trªn, ¸p dông mÖnh ®Ò 5(ii) ta suy ra x ∈ N⋂ i=1 Ci = C. §Þnh lý chøng minh xong. ¥ VÝ dô sau ®©y minh häa kÕt qu¶ cña ®Þnh lý võa nªu. VÝ dô 15 (Butnariu vµ Censor). Gi¶ sö X lµ h÷u h¹n chiÒu, thuËt to¸n chiÕu cã c¸c tËp h»ng, vµ c¸c tham sè níi láng chØ phô thuéc n, tøc lµ α (n) i ≡ α(n) víi mäi chØ sè i vµ mäi n. Gi¶ sö thªm r»ng tån t¹i mét d·y con nµo ®ã (n′) cña (n) sao cho víi mäi chØ sè i, λ (n′) i −→ λi víi mét sè λi > 0 nµo ®ã. (i) NÕu tån t¹i sè ε sao cho ε ≤ α(n) ≤ 2 − ε víi mäi n ®ñ lín, khi ®ã d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm thuéc C. (ii) NÕu phÇn trong cña C kh¸c rçng vµ tån t¹i mét d·y con (n′′) cña (n′) sao cho α(n ′′) −→ 2 th× d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm nµo ®ã thuéc C. Chøng minh: (i): Gi¶ thiÕt vÒ c¸c träng suy ra ∑ n µ (n) i = +∞ víi mäi chØ sè i. Do ®ã (i) suy ra tõ vÝ dô 12. (ii): Suy trùc tiÕp tõ ®Þnh lý 6 ¥ 32 §Þnh nghÜa 13 (§iÒu khiÓn). Ta nãi thuËt to¸n chiÕu lµ xÐt tËp xa nhÊt nÕu víi mäi n, Ýt nhÊt mét chØ sè xa nhÊt ®­îc xÐt; tøc lµ I(n)rem := {i : d(x(n), Ci) = max{d(x(n), Cj) : j = 1, . . . , N}} ∩ I(n) 6= ∅. Theo c¸ch gäi cña Censor, ta nãi ®iÒu khiÓn tËp xa nhÊt nÕu thuËt to¸n chiÕu lµ suy biÕn vµ xÐt tËp xa nhÊt. T­¬ng tù nh­ phÇn thuËt to¸n tæng qu¸t, tíi ®©y ta cã thÓ ph¸t biÓu vµ chøng minh mét kÕt qu¶ c¬ b¶n trong t«p« yÕu. §Þnh lý 7 (C¸c kÕt qu¶ trong t«p« yÕu). Gi¶ sö r»ng thuËt to¸n chiÕu lµ tô m¹nh vµ xÐt tËp xa nhÊt. Gi¶ sö thªm r»ng (i(n)) mét d·y c¸c chØ sè xa nhÊt; tøc lµ i(n) ∈ I(n)rem ∀n. (i) NÕu ∑ n µ (n) i(n) = +∞, khi ®ã tån t¹i mét d·y con (x(nk))k cña x(n) sao cho max{d(x(nk), Cj) : j = 1, . . . , N} −→ 0. vµ (x(nk))k héi tô yÕu tíi ®iÓm dÝnh yÕu duy nhÊt cña (x (n)) trong C. (ii) NÕu lim inf n µ (n) i(n) > 0 th× (x(n)) héi tô yÕu tíi mét ®iÓm thuéc C vµ max{d(x(n), Cj) : j = 1, . . . , N} −→ 0. Chøng minh: (i): Tõ bæ ®Ò 2(iv), chuçi ∑ n µ (n) i(n) d2(x(n), C (n) i(n) ) héi tô. Do ®ã, lim inf n d(x(n), C (n) i(n) ) = 0. Do ®ã ta cã thÓ trÝch ra mét d·y con (x(nk))k vµ cè ®Þnh mét chØ sè i sao cho d(x(n), C (n) i(n) ) −→ 0; i(nk) ≡ i,vµ d·y (x(nk))k héi tô yÕu. Do thuËt to¸n lµ tô m¹nh vµ xÐt chØ sè xa nhÊt, ta ®i tíi kÕt luËn lµ max{d(x(nk), Cj) : j = 1, . . . , N} −→ 0. Do tÝnh nöa liªn tôc d­íi yÕu cña d(·, Cj) víi mäi chØ sè j, giíi h¹n yÕu cña (x(nk))k n»m trong C. Theo ®Þnh lý 1(ii), (x (n)) cã nhiÒu nhÊt mét ®iÓm dÝnh yÕu trong C; do ®ã, (i) chøng minh xong. (ii): Chøng minh t­¬ng tù (i). ¥ 33 2.3. Mét sè ®iÒu kiÖn ®¶m b¶o sù héi tô theo chuÈn vµ héi tô tuyÕn tÝnh §Ó ®¶m b¶o sù héi tô theo chuÈn còng nh­ héi tô tuyÕn tÝnh, ta cÇn ®Õn kh¸i niÖm sau ®©y. §Þnh nghÜa 14. Ta nãi bé N tËp låi ®ãng (C1, . . . , CN) lµ chÝnh quy nÕu ∀ε > 0 ∃δ > 0∀x ∈ X : max{d(x,Cj) : j = 1 . . . N} ≤ δ ⇒ d(x,C) ≤ ε NÕu ®iÒu nµy chØ ®óng trªn c¸c tËp bÞ chÆn, tøc lµ: ∀S ⊆ X bÞ chÆn ∀ε > 0 ∃δ > 0 ∀x ∈ S : max{d(x,Cj) : j = 1 . . . N} ≤ δ ⇒ d(x,C) ≤ ε th× ta nãi bé N tËp trªn lµ chÝnh quy bÞ chÆn. ý nghÜa h×nh häc cña ®Þnh nghÜa nµy rÊt râ rµng: NÕu mét phÇn tö x ®· ë gÇn tÊt c¶ c¸c tËp Ci th× nã còng kh«ng thÓ ë xa giao C cña tÊt c¶ c¸c tËp Êy. Víi kh¸i niÖm võa nªu ta cã mét sè kÕt qu¶ sau. §Þnh lý 8. Gi¶ sö r»ng thuËt to¸n lµ tô m¹nh vµ p−lÆp ®o¹n víi sè nguyªn d­¬ng p nµo ®ã. Gi¶ sö thªm r»ng bé N tËp (C1, . . . , CN) lµ chÝnh quy bÞ chÆn. §Æt νn = min{µ(l)i : np ≤ l ≤ (n+ 1)p− 1 i thiÕt thùc t¹i l} ∀n ≥ 0. NÕu ∑ n νn = +∞, th× d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm n»m trong C. Nãi riªng, ®iÒu nµy ®óng nÕu lim inf n:n thiÕt thùc cho i µ (n) i > 0 ∀i. Chøng minh: Tõ ®Þnh lý 3, ta nhËn ®­îc mét d·y con (x(nkp))k sao cho (x (nkp))k héi tô yÕu tíi ®iÓm dÝnh yÕu duy nhÊt cña (x(n)) trong C, gi¶ sö ®ã lµ x, ngoµi ra ta cßn cã (nk+1)p−1∑ l=nkp ∑ i∈I(l) d(x(l), C (l) i ) −→ 0 (3.1) 34 x(nkp+rk) − x(nkp) −→ 0 (3.2) víi mäi d·y (rk) n»m trong {0, . . . , p − 1}. Cè ®Þnh mét chØ sè i. Do thuËt to¸n chiÕu lµ lÆp ®o¹n, ta cã mét d·y (rk) n»m trong {0, . . . , p−1} sao cho i ∈ I(nkp+rk) víi mäi k. Khi ®ã, do (3.1), d(x(nkp+rk), C (nkp+rk) i ) −→ 0. Do d·y (x(nkp+rk))k còng héi tô tíi x (do (3.2))vµ thuËt to¸n chiÕu lµ tô m¹nh, ta suy ra r»ng d(x(nkp+rk), Ci) −→ 0. Do ®ã, tõ (3.2), d(x(nkp), Ci) −→ 0. Do chØ sè i chän bÊt kú nªn ta cã max{d(x(nkp), Cj) : j = 1 . . . N} −→ 0. MÆt kh¸c, bé (C1, . . . , CN) lµ chÝnh quy bÞ chÆn vµ d·y (x (nkp)) bÞ chÆn. Tõ ®ã suy ra d(x(nkp), C) −→ 0. ¸p dông hÖ qu¶ 4(ii) d·y x(n) héi tô theo chuÈn tíi x. ¥ §Þnh lý 9. Gi¶ sö thuËt to¸n chiÕu lµ tô m¹nh vµ xÐt tËp xa nhÊt. Gi¶ sö thªm r»ng bé N tËp (C1, . . . , CN) lµ chÝnh quy bÞ chÆn vµ (i (n)) lµ mét d·y c¸c chØ sè xa nhÊt. NÕu ∑ n µ (n) i(n) = +∞ th× d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm thuéc C. Nãi riªng, ®iÒu nµy ®óng khi lim inf n µ (n) i(n) > 0. Chøng minh:Tõ ®Þnh lý 7(i), tån t¹i mét d·y con héi tô yÕu (x(nkp))k cña (x (n)) víi max{d(x(nkp), Cj) : j = 1, . . . , N} −→ 0. Do bé (C1, . . . , CN) chÝnh quy bÞ chÆn nªn d(x(nkp), C) −→ 0. ¸p dông hÖ qu¶ 4(ii) ta cã ®iÒu ph¶i chøng minh. ¥ §Ó cã thÓ sö dông ®­îc c¸c ®Þnh lý nªu trªn, ta cÇn cã nh÷ng ®iÒu kiÖn ®ñ ®¬n gi¶n ®Ó kiÓm tra khi nµo mét bé N tËp lµ chÝnh quy bÞ chÆn. MÖnh ®Ò 7. Cho mét bé N tËp låi ®ãng. (i) NÕu cã mét tËp Ci nµo ®ã lµ compact bÞ chÆn th× bé N tËp (C1, . . . , CN) lµ chÝnh quy bÞ chÆn. (ii) NÕu bé N tËp lµ chÝnh quy bÞ chÆn vµ mét tËp Ci nµo ®ã lµ bÞ chÆn th× bé N tËp lµ chÝnh quy. 35 (iii) NÕu X lµ kh«ng gian h÷u h¹n chiÒu th× mäi bé N tËp lµ chÝnh quy bÞ chÆn. §Þnh nghÜa sau ®©y cho phÐp ta ®¸nh gi¸ tèc ®é héi tô cña thuËt to¸n. §Þnh nghÜa 15. Ta nãi bé N tËp låi ®ãng (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh nÕu ∃κ > 0 ∀x ∈ X d(x,C) ≤ κmax{d(x,Cj) : j = 1, . . . , N} NÕu ®iÒu nµy chØ ®óng víi c¸c tËp bÞ chÆn ∀X ⊇ S bÞ chÆn ∃κS > 0 ∀x ∈ X d(x,C) ≤ κmax{d(x,Cj) : j = 1, . . . , N} th× ta nãi bé N tËp lµ chÝnh quy tuyÕn tÝnh bÞ chÆn. Víi ®Þnh nghÜa trªn ta cã kÕt qu¶ sau: §Þnh lý 10. Gi¶ sö thuËt to¸n chiÕu lµ tô tuyÕn tÝnh vµ lÆp ®o¹n. Gi¶ sö thªm r»ng bé N tËp lµ chÝnh quy tuyÕn tÝnh bÞ chÆn vµ tån t¹i mét sè ε > 0 sao cho ε ≤ α(n)i ≤ 2− ε víi mäi n ®ñ lín vµ i thiÕt thùc t¹i n. Khi ®ã, d·y (x(n)) héi tô tuyÕn tÝnh tíi mét ®iÓm thuéc C vµ tèc ®é héi tô kh«ng phô thuéc vµo ®iÓm xuÊt ph¸t nÕu bé N tËp lµ chÝnh quy tuyÕn tÝnh. Chøng minh: Gi¶ sö thuËt to¸n chiÕu lµ p−lÆp ®o¹n. Cè ®Þnh mét chØ sè i. Khi ®ã, víi mäi k ≥ 0, ta cã mk víi kp ≤ mk ≤ (k + 1)p − 1 sao cho i ∈ I(mk). Theo ®Þnh nghÜa phÐp lÆp, ta cã x(mk) = A(mk−1) . . . A(kp)x(kp) vµ tõ bæ ®Ò 1(iv) vµ mÖnh ®Ò 5(i), A(n) lµ min{2− α (n) j α (n) j : j thiÕt thùc t¹i n} − hót t­¬ng øng víi C∀n ≥ 0. Do ®ã, tõ gi¶ thiÕt vÒ c¸c tham sè níi láng, A(n) lµ ε/2-hót t­¬ng øng víi C víi mäi n ®ñ lín. Do ®ã, theo mÖnh ®Ò 5(i) A(mk−1) . . . A(kp) lµ ε 2p−1 − hót ®èi víi C víi mäi k ®ñ lín. 36 Do thuËt to¸n lµ tô tuyÕn tÝnh nªn tån t¹i mét sè β > 0 sao cho βd(x(n), Cj) ≤ d(x(n), C (n) j ) víi mäi n ®ñ lín vµ mäi chØ sè j thiÕt thùc t¹i n. Ta cã d2(x(kp), Ci) ≤ (‖x(kp) − x(mk)‖+ d(x(mk), Ci))2 ≤ 2‖x(kp) − x(mk)‖2 + 2d2(x(mk), Ci) Cè ®Þnh mét ®iÓm bÊt kú c ∈ C. Ta cã víi k ®ñ lín, ‖x(kp) − x(mk)‖2 = ‖A(mk−1) . . . A(kp)x(kp) − x(kp)‖ ≤ 2 p−1 ε (‖x(kp) − c‖2 − ‖x(mk) − c‖2) ≤ 2 p−1 ε (‖x(kp) − c‖2 − ‖x((k+1)p) − c‖2) MÆt kh¸c, tõ gi¶ thiÕt vÒ β, c¸c tham sè níi láng, c¸c träng vµ bæ ®Ò 2 vµ chó ý 1, ta cã ®¸nh gi¸ sau khi k ®ñ lín. d2(x(mk), Ci) ≤ 1 β2 d2(x(mk), C (mk) i ) = 1 β2 ‖x(mk) − P (mk)i x(mk)‖2 ≤ 1 β2µ (mk) i (‖x(mk) − c‖2 − ‖x(mk+1) − c‖2) ≤ 1 β2ε3 (‖x(mk) − c‖2 − ‖x(mk+1) − c‖2) ≤ 1 β2ε3 (‖x(kp) − c‖2 − ‖x((k+1)p) − c‖2) KÕt hîp l¹i ta ®­îc: d2(x(kp), Ci) ≤ (2p ε + 2 β2ε3 )(‖x(kp) − c‖2 − ‖x((k+1)p) − c‖2). Chän c = PCx (kp) ta ®­îc d2(x(kp), Ci) ≤ (2p ε + 2 β2ε3 )( d2(x(kp), C)− d2(x((k+1)p), C)). Do chØ sè i chän tïy ý nªn víi k ®ñ lín, ®¸nh gi¸ trªn ®óng cho mäi i. Do bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh bÞ chÆn, víi S := {x(n) : n ≥ 0} ta cã mét sè κS sao cho d(x(n), C) ≤ κS max{d(x(n), Cj) : j = 1, . . . , N} ∀n ≥ 0. 37 NhËn xÐt r»ng nÕu bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh, th× h»ng sè κS cã thÓ chän ®­îc ®éc lËp víi S. KÕt hîp l¹i ta ®­îc d(x(kp), C) ≤ κ2S (2p ε + 2 β2ε3 )( d2(x(kp), C)− d2(x((k+1)p), C)). Tõ ®ã, ¸p dông ®Þnh lý 1(iv) cho d·y con x(kp), d·y nµy héi tô tuyÕn tÝnh tíi mét ®iÓm x thuéc C. Tõ ®Þnh lý 1(i) vµ mÖnh ®Ò 4 toµn bé d·y (x(n)) héi tô tuyÕn tÝnh vÒ x vµ tèc ®é héi tô kh«ng phô thuéc c¸ch chän ®iÓm xuÊt ph¸t nÕu bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh. ¥ §Þnh lý 11. Gi¶ sö thuËt to¸n lµ tô tuyÕn tÝnh vµ xÐt tËp xa nhÊt. Gi¶ sö thªm r»ng bé N tËp (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh bÞ chÆn vµ (i (n)) lµ d·y c¸c chØ sè xa nhÊt. NÕu lim inf n µ (n) i(n) > 0 th× d·y x(n) héi tô tuyÕn tÝnh tíi mét ®iÓm thuéc C; tèc ®é héi tô kh«ng phô thuéc ®iÓm xuÊt ph¸t nÕu bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh. Chøng minh: Tr­íc hÕt, do thuËt to¸n chiÕu lµ tô tuyÕn tÝnh, ta cã β > 0 sao cho βd(x(n), Ci) ≤ d(x(n), C(n)i ) víi mäi n ®ñ lín vµ i thiÕt thùc t¹i n. TiÕp theo, do bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh bÞ chÆn, víi tËp S := {x(n) : n ≥ 0} tån t¹i mét h»ng sè κS > 0 sao cho d(x(n), C) ≤ κS max{d(x(n), Cj) : j = 1 . . . N} víi mäi n ≥ 0. DÔ thÊy h»ng sè κS cã thÓ chän ®éc lËp víi tËp S nÕu bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh. TiÕp theo, tån t¹i mét sè ε > 0 sao cho µ (n) i(n) ≥ ε víi mäi n ®ñ lín. KÕt hîp l¹i vµ sö dông bæ ®Ò 2(ii) ta cã ®¸nh gi¸ sau: d2(x(n), C) ≤ κ2S max{d2(x(n), Cj) : j = 1 . . . N} = κ2Sd 2(x(n), Ci(n)) ≤ (κS β )2 ‖x(n) − P (n) i(n) ‖2 ≤ (κS β )2 1 µ (n) i(n) (‖x(n) − PCx(n)‖2 − ‖x(n+1) − PCx(n)‖2) ≤ (κS β )21 ε ( d2(x(n), C)− d2(x(n+1), C)). 38 Do ®ã, theo ®Þnh lý 1(vi), d·y x(n) héi tô tuyÕn tÝnh tíi mét ®iÓm thuéc C. ¥ TÝnh chÊt chÝnh quy tuyÕn tÝnh (bÞ chÆn) cho phÐp ta ®­a ra nhiÒu kÕt qu¶, ta sÏ nghiªn cøu kü h¬n kh¸i niÖm nµy vµ ®­a ra mét vµi ®iÒu kiÖn ®ñ cho tÝnh chÊt nµy. 2.4. Mét vµi vÝ dô vÒ tÝnh chÝnh quy tuyÕn tÝnh (bÞ chÆn) MÖnh ®Ò 8. NÕu mçi tËp Ci lµ mét nãn låi ®ãng th× c¸c ®iÒu kiÖn sau t­¬ng ®­¬ng: (i) Bé (C1, . . . , CN) lµ chÝnh quy. (ii) Bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh. (iii) Bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh bÞ chÆn. §Þnh lý 12 (TÝnh chÝnh quy tuyÕn tÝnh (bÞ chÆn) ®­a vÒ tõng cÆp). NÕu mçi cÆp trong N − 1 cÆp: (C1, C2), (C1 ∩ C2, C3), . . . (C1 ∩ C2 ∩ . . . ∩ CN−2, CN−1), (C1 ∩ C2 ∩ . . . ∩ CN−2 ∩ CN−1, CN) lµ chÝnh quy tuyÕn tÝnh (bÞ chÆn) th× bé N tËp (C1, C2, . . . , CN) còng lµ chÝnh quy tuyÕn tÝnh (bÞ chÆn). Nh­ vËy tÝnh chÊt chÝnh quy tuyÕn tÝnh (bÞ chÆn) ta ®­a vÒ tÝnh chÝnh quy theo tõng cÆp. Víi tÝnh chÝnh quy tuyÕn tÝnh (bÞ chÆn) theo cÆp, ta c«ng nhËn ®iÒu kiÖn ®ñ sau ®©y Bæ ®Ò 4. Gi¶ sö E,F lµ hai tËp låi ®ãng. NÕu 0 ∈ icr(E −F )(icr(S) = intaff S S lµ nh©n trong cña S), th× cÆp (E,F ) lµ chÝnh quy tuyÕn tÝnh bÞ chÆn. Nãi riªng, ®iÒu nµy ®óng nÕu 39 (i) 0 ∈ int(E − F ). (ii) E − F lµ kh«ng gian con ®ãng. KÕt hîp ®Þnh lý vµ bæ ®Ò võa nªu ta cã hÖ qu¶ sau: HÖ qu¶ 14. NÕu 0 ∈ icr(C1 − C2) ∩ icr((C1 − C2)− C3) ∩ . . . icr((C1 ∩ . . . CN−1)− CN) th× bé N -tËp lµ chÝnh quy tuyÕn tÝnh bÞ chÆn. HÖ qu¶ 15. NÕu CN ∩ int(C1 ∩ . . . CN−1) 6= ∅ th× bé N -tËp lµ chÝnh quy tuyÕn tÝnh bÞ chÆn. TiÕp theo ta xÐt tÝnh chÝnh quy tuyÕn tÝnh (bÞ chÆn) cña mét sè bé tËp ®Æc biÖt. Ta cã mét sè kÕt qu¶ sau ®©y. MÖnh ®Ò 9. Bé N -tËp (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh nÕu (i) Mçi tËp Ci lµ mét siªu ph¼ng. (ii) Mçi tËp Ci lµ mét ®a diÖn. (iii) Mçi tËp Ci lµ mét nöa kh«ng gian. (iv) Mçi tËp Ci lµ mét kh«ng gian con ®ãng vµ Ýt nhÊt mét kh«ng gian con lµ h÷u h¹n chiÒu hoÆc tÊt c¶ c¸c kh«ng gian con (cã thÓ ngo¹i trõ mét kh«ng gian con) cã ®èi chiÒu h÷u h¹n. 40 Ch­¬ng 3. ThuËt to¸n d­íi gradient vµ ph­¬ng ph¸p chØnh lÆp song song Trong ch­¬ng nµy ta xÐt tr­êng hîp tæng qu¸t khi c¸c tËp Ci cã d¹ng Ci = {x ∈ X : fi(x) ≤ 0} trong ®ã fi lµ mét hµm låi. Nh­ vËy Ci lµ tËp møc d­íi cña mét hµm låi. Chó ý r»ng ¸nh x¹ kho¶ng c¸ch d(·, C) khi C lµ tËp låi còng lµ mét hµm låi vµ tËp låi C bÊt kú ®Òu cã thÓ xem nh­ tËp møc d­íi cña hµm f(·) = d(·, C). 3.1. ThuËt to¸n d­íi gradient 3.1.1. C¬ së §Þnh nghÜa 16 (D­íi vi ph©n). Gi¶ sö f : X −→ X lµ mét hµm låi. Cho tr­íc mét ®iÓm x0 ∈ X , tËp hîp {x∗ ∈ X : 〈x∗, x− x0〉 ≤ f(x)− f(x0) ∀x ∈ X} ®­îc gäi lµ d­íi vi ph©n cña f t¹i x0 vµ ký hiÖu lµ ∂f(x0) Bæ ®Ò 5. Gi¶ sö r»ng f : X −→ X lµ mét hµm låi vµ x0 ∈ X . Khi ®ã (i) f liªn tôc t¹i x0 vµ ∂f(x0) chØ cã mét phÇn tö nÕu vµ chØ nÕu f lµ nöa liªn 41 tôc d­íi vµ kh¶ vi G©teaux t¹i x0. Trong tr­êng hîp nµy, d­íi vi ph©n duy nhÊt cña f t¹i x0 chÝnh lµ ®¹o hµm G©teaux cña f t¹i x0. (ii) NÕu f liªn tôc t¹i x0 th× f kh¶ d­íi vi ph©n t¹i x0. (iii) NÕu X h÷u h¹n chiÒu th× f liªn tôc vµ kh¶ d­íi vi ph©n t¹i mäi ®iÓm. Bæ ®Ò 6. Gi¶ sö f : X −→ X lµ mét hµm låi, x0 ∈ X vµ f kh¶ d­íi vi ph©n t¹i x0. Gi¶ sö thªm r»ng tËp S := {x ∈ X : f(x) ≤ 0} 6= ∅. Víi mäi g(x0) ∈ ∂f(x0), ®Þnh nghÜa tËp låi ®ãng H bëi: H := H(f, x0, g(x0)) := {x ∈ X : f(x0) + 〈g(x0), x− x0〉 ≤ 0}. Khi ®ã (i) H ⊇ S. NÕu g(x0) 6= 0 th× H lµ mét nöa kh«ng gian; ng­îc l¹i th× H = X . (ii) PHx0 = x0 − f(x0) ‖g(x0)‖2 g(x0) nÕu f(x0) > 0 x0 ng­îc l¹i (iii) d(x0, H) =  f(x0) ‖g(x0)‖ nÕu f(x0) > 0 0 ng­îc l¹i Chó ý 5. Nöa kh«ng gian trong bæ ®Ò võa ®Þnh nghÜa ®­îc sö dông víi ý t­ëng sau. Gi¶ sö ta cÇn t×m mét phÇn tö cña tËp S = {x ∈ X : f(x) ≤ 0}. XuÊt ph¸t tõ ®iÓm x0, nÕu f(x0) ≤ 0 th× ta t×m ®­îc x0 ∈ S; ng­îc l¹i f(x0) > 0, ta ®i t×m nghiÖm cña ph­¬ng tr×nh f(x) = 0. Tuy nhiªn do ®iÒu nµy khã thùc hiÖn nªn ta thay f(x) bëi xÊp xØ bËc 1 cña nã tøc lµ f(x) ≈ f˜(x) := f(x0) + 〈g(x0), x− x0〉 víi g(x0) ∈ ∂f(x0), vµ gi¶i ph­¬ng tr×nh f˜(x0) = 0. Ph­¬ng tr×nh nµy cã mét nghiÖm lµ PH(x0) = x0 − f(x0)‖g(x0)‖2 g(x0). Ta ®­a ra ®Þnh nghÜa chÝnh x¸c cña thuËt to¸n d­íi gradient. 42 §Þnh nghÜa 17. Gi¶ sö víi mét chØ sè i ∈ {1, 2, . . . , N} nµo ®ã vµ mäi chØ sè n, c¸c tËp C (n) i cña thuËt to¸n chiÕu cã d¹ng C (n) i = H (n) i = {x ∈ X : fi(xn) + 〈gi(x(n)), x− xn〉 ≤ 0} víi mçi hµm låi fi : X −→ R, trong ®ã fi kh¶ d­íi vi ph©n t¹i mäi ®iÓm x(n) vµ gi(x (n)) ∈ ∂fi(x(n)). Gi¶ sö thªm r»ng Ci = {x ∈ X : fi(x) ≤ 0}. Khi ®ã ta gäi thuËt to¸n chiÕu nµy lµ thuËt to¸n d­íi gradient. Mçi chØ sè i ®­îc gäi lµ chØ sè d­íi gradient. Chó ý r»ng kh«ng ph¶i mäi chØ sè i ®Òu lµ chØ sè d­íi gradient. NhËn xÐt 1. ThuËt to¸n chiÕu vµ thuËt to¸n d­íi gradient cã mèi liªn hÖ mËt thiÕt theo nghÜa sau: (i) Mäi thuËt to¸n d­íi gradient ®Òu lµ thuËt to¸n chiÕu. (ii) Mäi thuËt to¸n chiÕu cã c¸c tËp h»ng th× ®Òu cã thÓ xem nh­ thuËt to¸n d­íi gradient b»ng c¸ch chän fi(·) = d(·, Ci) vµ ®Ó ý r»ng ∂fi(x) = ∂d(x,Ci) =  x−Pix ‖x−Pix‖ nÕu x 6∈ Ci NCi(x) ∩BX nÕu ng­îc l¹i trong ®ã NCi(x) = {x∗ ∈ X : 〈Ci − x, x∗〉 ≤ 0} gäi lµ nãn chuÈn t¾c cña Ci t¹i x. T­¬ng tù nh­ thuËt to¸n tæng qu¸t, tÝnh tô cña thuËt to¸n lµ mét ®ßi hái b¾t buéc. §Þnh lý 13 (D¹ng cña mét thuËt to¸n d­íi gradient tô). Cho mét thuËt to¸n d­íi gradient, gi¶ sö r»ng c¸c d­íi vi ph©n cña c¸c hµm fi kh¸c rçng vµ bÞ chÆn ®Òu trªn tËp bÞ chÆn víi mäi chØ sè i ∈ I∂. Gi¶ sö thªm r»ng d·y (P (n)i ) héi tô tõng ®iÓm tíi Pi víi mäi chØ sè i ∈ {1, 2, . . . , N} \ I∂. Khi ®ã thuËt to¸n d­íi gradient lµ tô. 43 Chøng minh: Cè ®Þnh mét chØ sè i ∈ {1, 2, . . . , N}. Gi¶ sö (x(nk)) lµ d·y con cña (x(n)) vµ x(nk) ⇀ x, x(nk) − P (nk)i x(nk) → 0, vµ i thiÕt thùc t¹i nk víi mäi k. Ta ph¶i chØ ra r»ng x ∈ Ci. Tõ kÕt qu¶ cña bæ ®Ò 3, ta chØ cÇn xÐt c¸c chØ sè i ∈ I∂. Khi ®ã, do fi lµ nöa liªn tôc d­íi yÕu, fi(x) ≤ lim inf k fi(x (nk)). NÕu fi(x (nk)) ≤ 0 víi v« h¹n chØ sè nkk th× fi(x) ≤ 0 vµ do ®ã x ∈ Ci. Ng­îc l¹i fi(x (nk)) > 0 víi mäi chØ sè k ®ñ lín. Do d·y (x(nk)) bÞ chÆn, tõ gi¶ thiÕt tån t¹i mét sè M > 0 sao cho chuÈn cña mäi d­íi vi ph©n cña fi t¹i x (n) ®Òu nhá h¬n M . Do ®ã theo bæ ®Ò 6(iii), 0 ←− d(x(nk), C(nk)i ) = fi(x (nk)) ‖gi(x(nk))‖ ≥ fi(x (nk)) M ; do ®ã fi(x (nk)) → 0. V× vËy, fi(x) ≤ 0 vµ x ∈ Ci. ¥ NhËn xÐt 2. TÝnh chÊt bÞ chÆn ®Òu trªn c¸c tËp bÞ chÆn cña d­íi vi ph©n ∂fi lµ mét gi¶ thiÕt tiªu chuÈn cho c¸c ®Þnh lý vÒ thuËt to¸n d­íi gradient. TÝnh chÊt nµy t­¬ng ®­¬ng víi mét vµi tÝnh chÊt kh¸c quen thuéc h¬n nh­ trong mÖnh ®Ò sau. MÖnh ®Ò 10 (TÝnh bÞ chÆn ®Òu trªn c¸c tËp bÞ chÆn cña d­íi vi ph©n). Gi¶ sö r»ng f : X −→ R lµ mét hµm låi. Khi ®ã, c¸c ®iÒu kiÖn sau t­¬ng ®­¬ng. (i) f bÞ chÆn trªn c¸c tËp bÞ chÆn. (i) f lµ liªn tôc Lipschitz (toµn côc) trªn c¸c tËp bÞ chÆn. (iii) D­íi vi ph©n cña f kh¸c rçng vµ bÞ chÆn ®Òu trªn c¸c tËp bÞ chÆn. Chøng minh: "(i) =⇒ (ii) " trong cuèn s¸ch "Convex Functions" cña Roberts vµ Varberg( [12]. §Þnh lý 41.B). "(ii) =⇒ (iii)": Do bæ ®Ò 5(ii), f lµ kh¶ d­íi vi ph©n t¹i mäi ®iÓm. ChØ cÇn chØ ra r»ng c¸c d­íi vi ph©n cña f bÞ chÆn ®Òu trªn c¸c h×nh cÇu më t©m t¹i 0. Cè 44 ®Þnh r > 0 vµ do gi¶ thiÕt tÝnh liªn tôc Lipschitz ta nhËn ®­îc h»ng sè Lipschitz L cña f trªn tËp int rBX . Cè ®Þnh x ∈ int rBX , khi ®ã tån t¹i sè d­¬ng s ®ñ nhá ®Ó x+ sBX ⊆ int rBX . Chän bÊt kú x∗ ∈ ∂f(x) vµ b ∈ BX . Khi ®ã 〈x∗, sb〉 ≤ f(x+ sb)− f(x) ≤ Ls‖b‖; do ®ã ‖x∗‖ = sup〈x∗, BX〉 ≤ L vµ v× vËy d­íi vi ph©n cña f lµ bÞ chÆn ®Òu trªn tËp int rBX bëi L. "(iii) =⇒ (i)". ChØ cÇn chØ ra r»ng f bÞ chÆn trªn rBX víi mäi r > 0. Do gi¶ thiÕt, tån t¹i sè M > 0 sao cho chuÈn cña mäi d­íi vi ph©n cña f t¹i mäi ®iÓm trong rBX kh«ng qu¸ M . Cè ®Þnh x ∈ rBX , chän bÊt kú x∗ ∈ ∂f(x). Ta cã 〈x∗, 0−x〉 ≤ f(0)−f(x); do ®ã f(x) ≤ f(0)+ 〈x∗, x〉 ≤ f(0)+Mr. Nh­ vËy f bÞ chÆn trªn trªn rBX bëi f(0) +Mr. MÆt kh¸c, chän x ∗ 0 ∈ ∂f(0), lµm t­¬ng tù nh­ trªn ta còng chØ ra ®­îc r»ng f bÞ chÆn d­íi trªn rBX bëi f(0)−Mr. §Þnh lý chøng minh xong. ¥ HÖ qu¶ 16. NÕu X lµ kh«ng gian h÷u h¹n chiÒu th× mäi hµm låi tõ X vµo R lµ kh¶ d­íi vi ph©n t¹i mäi ®iÓm vµ d­íi vi ph©n cña nã bÞ chÆn ®Òu trªn tËp bÞ chÆn. Chøng minh: Tõ bæ ®Ò 5(iii), mäi hµm låi tõ X vµo R liªn tôc t¹i mäi ®iÓm. Do X lµ kh«ng gian h÷u h¹n chiÒu, hµm nµy ®¹t ®­îc gi¸ trÞ lín nhÊt vµ gi¸ trÞ nhá nhÊt trªn c¸c tËp ®ãng, bÞ chÆn(do ®ã compact); nh­ vËy hµm bÞ chÆn trªn tËp bÞ chÆn, ¸p dông mÖnh ®Ò võa chøng minh ta cã kÕt qu¶. ¥ NhËn xÐt 3. NÕu X lµ kh«ng gian h÷u h¹n chiÒu th× mäi hµm låi tõ X vµo R ®Òu tháa m·n ®iÒu kiÖn cña ®Þnh lý 13. Tuy vËy, gi¶ thiÕt X h÷u h¹n chiÒu lµ kh«ng thÓ bá qua, ngay c¶ khi hµm liªn tôc vµ kh¶ d­íi vi ph©n kh¾p n¬i nh­ trong vÝ dô sau. 45 VÝ dô 16. Cho hµm f nh­ sau: f : X = `2 −→ R : x = (xn) 7−→ ∞∑ n=1 nx2nn . Khi ®ã f lµ h÷u h¹n, låi, liªn tôc vµ kh¶ d­íi vi ph©n kh¾p n¬i. Tuy nhiªn trªn h×nh cÇu ®¬n vÞ BX , hµm f kh«ng bÞ chÆn vµ d­íi vi ph©n cña f còng kh«ng bÞ chÆn ®Òu. Ta cã ®iÒu kiÖn d¹ng ®iÓm Slater cho tÝnh tô tuyÕn tÝnh cña thuËt to¸n d­íi gradient sau ®©y. §Þnh lý 14 (D¹ng cña thuËt to¸n d­íi gradient tô tuyÕn tÝnh). Cho mét thuËt to¸n d­íi gradient, gi¶ sö r»ng tån t¹i mét ®iÓm Slater xˆ ∈ X sao cho fi(xˆ) < 0 vµ d­íi vi ph©n cña fi kh¸c rçng vµ bÞ chÆn ®Òu trªn c¸c tËp bÞ chÆn víi mäi chØ sè d­íi vi ph©n i ∈ I∂. Gi¶ sö thªm r»ng tån t¹i mét sè β > 0 sao cho βd(x(n), Ci) ≤ d(x(n), C(n)i ) víi mäi chØ sè i ∈ {1, 2, . . . , N} \ I∂ vµ mäi n thiÕt thùc cho i. Khi ®ã thuËt to¸n d­íi gradient lµ tô tuyÕn tÝnh. Chøng minh: Cè ®Þnh mét chØ sè i ∈ {1, 2, . . . , N}. Ta chØ cÇn chøng minh r»ng tån t¹i sè βi > 0 sao cho βid(x (n), Ci) ≤ d(x(n), C(n)i ) víi mäi n ®ñ lín thiÕt thùc cho i. (*) NÕu i ∈ {1, 2, . . . , N} \ I∂ th× tõ gi¶ thiÕt ta cã ngay ®iÒu cÇn chøng minh víi βi = β. Ta xÐt tr­êng hîp i ∈ I∂. Do d·y x(n) bÞ chÆn, tån t¹i mét sè d­¬ng M sao cho víi mäi n ≥ 0, ‖xˆ − x(n)‖ ≤ M vµ chuÈn cña mäi d­íi vi ph©n cña fi t¹i mäi ®iÓm x(n) ®Òu nhá h¬nM . Cè ®Þnh n thiÕt thùc cho i. Ta cã thÓ xem nh­ fi(x (n)) > 0. §Æt ε := −fi(xˆ) > 0, λ := ε fi(x(n)) + ε ∈ (0, 1) vµ y := (1− λ)xˆ+ λx(n). 46 Khi ®ã fi(y) = fi((1− λ)xˆ+ λx(n)) ≤ (1− λ)fi(xˆ) + λfi(x(n)) = 0 do ®ã y ∈ Ci. Ta cã ®¸nh gi¸ sau: d2(x(n), Ci) ≤ ‖x(n) − y‖2 = (1− λ)2‖xˆ− x(n)‖2 = ( fi(x(n)) fi(x(n)) + ε )2 ‖xˆ− x(n)‖2 ≤ (fi(x(n)) ε )2 M 2 = (d(x(n), C(n)i )‖gi(x(n))‖2 ε )2 M 2 ≤ M 4 ε2 d2(x(n), C (n) i ). Khi ®ã (*) tháa m·n víi βi = ε M2 ¥ 3.1.2. C¸c kÕt qu¶ héi tô Trong môc nµy ta xÐt thuËt to¸n d­íi gradient ¸p dông trong tr­êng hîp mäi chØ sè ®Òu lµ chØ sè d­íi gradient, tøc lµ I∂ = {1, 2, . . . , N}. Khi ®ã tËp C = N⋂ i=1 Ci = N⋂ i=1 {x ∈ X : fi(x) ≤ 0} lµ nghiÖm cña bµi to¸n chÊp nhËn låi fi(x) ≤ 0 i = 1, 2, . . . , N. trong ®ã mçi hµm fi lµ hµm låi liªn tôc tõ X vµo R. §Þnh lý 15 (KÕt qu¶ cña Censor vµ Lent trong kh«ng gian Euclid). Gi¶ sö X lµ kh«ng gian h÷u h¹n chiÒu. Khi ®ã d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm nµo ®ã thuéc C nÕu mét trong c¸c ®iÒu kiÖn sau tháa m·n. (i) (§iÒu khiÓn ngÉu nhiªn) lim inf n thiÕt thùc cho i µ (n) i > 0 víi mäi chØ sè i. 47 (ii) (§iÒu khiÓn lÆp ®o¹n) ThuËt to¸n d­íi gradient lµ p−lÆp ®o¹n vµ∑ n νn = +∞(trong ®ã νn ®Þnh nghÜa nh­ trong ®Þnh lý 3(ii)). Chøng minh: Tõ ®Þnh lý 13 vµ hÖ qu¶ 16, thuËt to¸n d­íi gradient lµ tô. Khi ®ã (i) suy ra tõ hÖ qu¶ 6 cßn (ii) suy ra tõ hÖ qu¶ 9. ¥ VÝ dô 17. Gi¶ sö X lµ h÷u h¹n chiÒu vµ thuËt to¸n d­íi gradient lµ hÇu tuÇn hoµn. Gi¶ sö thªm r»ng tån t¹i sè ε > 0 sao cho ε ≤ α(n)i ≤ 2 − ε víi mäi n vµ mäi chØ sè i thiÕt thùc t¹i n. Khi ®ã d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm thuéc C. §Þnh lý 16 (KÕt qu¶ cña Censor vµ Lent trong kh«ng gian Hilbert). Gi¶ sö thuËt to¸n chiÕu lµ p−lÆp ®o¹n vµ c¸c hµm fi cã d­íi vi ph©n kh¸c rçng vµ bÞ chÆn ®Òu trªn tËp bÞ chÆn. Khi ®ã (i) NÕu lim inf n thiÕt thùc cho i µ (n) i > 0 víi mäi chØ sè i th× d·y (x (n)) héi tô yÕu tíi mét ®iÓm thuéc C. (ii) NÕu ∑ n νn = +∞(trong ®ã νn ®Þnh nghÜa nh­ trong ®Þnh lý 3(ii)) th× d·y (x(n)) cã duy nhÊt mét ®iÓm dÝnh yÕu trong C. Chøng minh: Tõ ®Þnh lý 13, thuËt to¸n d­íi gradient lµ tô. KÕt qu¶ ®­îc suy ra tõ ®Þnh lý 3. ¥ VÝ dô 18. Gi¶ sö N = 1 vµ f1 cã d­íi vi ph©n kh¸c rçng vµ bÞ chÆn ®Òu trªn tËp bÞ chÆn. Khi ®ã (i) NÕu tån t¹i mét sè ε > 0 sao cho ε ≤ α(n)1 ≤ 2− ε, th× d·y (x(n)) héi tô yÕu tíi mét ®iÓm thuéc C. (ii) NÕu lim supn α (n) 1 < 2 vµ ∑ n α (n) 1 = +∞ th× d·y (x(n)) héi tô yÕu tíi mét ®iÓm thuéc C. 48 §Þnh lý 17 (KÕt qu¶ cña Censor vµ Lent sö dông ®iÒu kiÖn ®iÓm Slater). Gi¶ sö mçi hµm fi cã d­íi vi ph©n kh¸c rçng vµ bÞ chÆn ®Òu trªn tËp bÞ chÆn vµ tån t¹i mét ®iÓm Slater xˆ ∈ C tøc lµ fi(xˆ) < 0 víi mäi i. Khi ®ã d·y (x(n)) héi tô theo chuÈn tíi mét ®iÓm x ∈ X . (i) NÕu ∑ n µ (n) i = +∞ víi mäi chØ sè i th× d·y x ∈ C. (ii) NÕu thuËt to¸n gradient lµ lÆp ®o¹n vµ tån t¹i mét sè ε > 0 sao cho ε ≤ α (n) i ≤ 2 − ε vµ ε ≤ λ(n)i víi mäi n ®ñ lín vµ chØ sè i thiÕt thùc t¹i n th× x ∈ C vµ d·y (x(n)) héi tô tuyÕn tÝnh tíi x. Chøng minh: Tõ ®Þnh lý 14, thuËt to¸n d­íi gradient lµ tô tuyÕn tÝnh. §iÓm Slater xˆ n»m trong phÇn trong cña Ci = {x ∈ X : fi(x) ≤ 0} nªn xˆ ∈ intC vµ bé (C1, . . . , CN) lµ chÝnh quy tuyÕn tÝnh bÞ chÆn(do hÖ qu¶ 15). Khi ®ã (i) suy tõ ®Þnh lý 3(iii), cßn (ii) suy tõ ®Þnh lý 10. ¥ VÝ dô 19. Gi¶ sö X lµ h÷u h¹n chiÒu vµ tån t¹i mét ®iÓm Slater xˆ ∈ C. Gi¶ sö thªm r»ng thuËt to¸n d­íi gradient lµ hÇu tuÇn hoµn vµ tån t¹i sè ε > 0 sao cho ε ≤ α(n)i ≤ 2− ε víi mäi n vµ mäi chØ sè i thiÕt thùc t¹i n. Khi ®ã d·y (x(n)) héi tô tuyÕn tÝnh tíi mét ®iÓm thuéc C. Chøng minh: Tõ hÖ qu¶ 16 do gi¶ thiÕt X h÷u h¹n chiÒu ta suy ra c¸c hµm fi ®Òu cã d­íi vi ph©n kh¸c rçng vµ bÞ chÆn ®Òu trªn tËp bÞ chÆn. Do thuËt to¸n lµ hÇu tuÇn hoµn nªn nã lµ lÆp ®o¹n theo ®Þnh nghÜa. ¸p dông ®Þnh lý 17(ii) ta ®­îc kÕt luËn. ¥ VÝ dô 20. Gi¶ sö mçi hµm fi cã d­íi vi ph©n kh¸c rçng vµ bÞ chÆn ®Òu trªn tËp bÞ chÆn. Gi¶ sö tån t¹i ®iÓm Slater xˆ ∈ C. NÕu 0 < λ(n)i ≡ λi vµ 0 < α(n)i ≡ αi < 2 víi mäi chØ sè i. Khi ®ã d·y (x(n)) héi tô tuyÕn tÝnh tíi mét ®iÓm thuéc C. Chøng minh: Tõ gi¶ thiÕt vÒ c¸c λ (n) i ta suy ra thuËt to¸n lµ ®ång bé; do ®ã nã lµ 1-lÆp ®o¹n. ¸p dông ®Þnh lý 17(ii) ta ®­îc ®iÒu cÇn chøng minh. ¥ 49 3.2. Ph­¬ng ph¸p chØnh lÆp song song Bµi to¸n chÊp nhËn låi ®ang xÐt cã thÓ xem nh­ bµi to¸n gi¶i hÖ ph­¬ng tr×nh Ai(x) = 0, trong ®ã Ai = Id− Pi. Trong bµi b¸o [3] ta ®· cã mét ph­¬ng ph¸p chØnh lÆp song song ®Ó gi¶i hÖ ph­¬ng tr×nh ®Æt kh«ng chØnh trong ®ã c¸c to¸n tö Ai cã tÝnh chÊt ng­îc ®¬n ®iÖu m¹nh. 3.2.1. Mét sè kÕt qu¶ bæ trî §Þnh nghÜa 18 (TÝnh ng­îc ®¬n ®iÖu m¹nh). Cho H lµ mét kh«ng gian Hilbert. To¸n tö A : H −→ H ®­îc gäi lµ c−1−ng­îc ®¬n ®iÖu m¹nh nÕu 〈A(x)− A(y), x− y〉 ≥ 1 c ‖A(x)− A(y)‖2 ∀x, y ∈ H. Bæ ®Ò 7. Cho {an} vµ {pn} lµ c¸c d·y sè kh«ng ©m, {bn} lµ mét d·y sè d­¬ng tháa m·n c¸c ®iÒu kiÖn sau: an+1 ≤ (1− pn)an + bn vµ pn < 1 ∀n ≥ 0; lim n→∞ bn pn = 0; ∞∑ n=1 pn = +∞. Khi ®ã lim n→∞ an = 0. §Þnh lý 18 (VÒ sù héi tô cña ph­¬ng ph¸p chØnh lÆp Èn). (Xem [3]) Cho αn vµ γn lµ hai d·y sè d­¬ng tháa m·n: αn → 0, γn → +∞, γn(αn+1−αn)α2n → 0 khi n →∞ vµ ∞∑ n=1 αn γn = +∞. Ai (i = 1, . . . , N) lµ c¸c to¸n tö ng­îc ®¬n ®iÖu m¹nh. Gi¶ sö r»ng xÊp xØ thø n ®· tÝnh ®­îc(x0 cho tr­íc). Khi ®ã thuËt to¸n lÆp hiÖu chØnh song song sau ®©y sau ®©y Ai(x n i ) + ( αn N + γn ) xni = γnx n, i = 1, 2, . . . , N ; xn+1 = 1N N∑ i=1 xni , n = 1, 2, . . . (2.1) héi tô tíi nghiÖm cã chuÈn nhá nhÊt x†. §Þnh lý 19 (Sù héi tô cña phÐp chØnh lÆp hiÖn). (Xem [3]) Gi¶ sö c¸c d·y αn, γn tháa m·n c¸c ®iÒu kiÖn trong ®Þnh lý 18. H¬n n÷a, gi¶ sö r»ng αnγn → +∞. Khi 50 ®ã phÐp lÆp hiÓn hiÖu chØnh song song sau ®©y héi tô tíi nghiÖm cã chuÈn nhá nhÊt x†. zk+1n,i := zn − 1γn [ Ai(z k n,i) + αn γn zkn,i ] , z0n,i := zn; k = 0, 1, . . . ,m− 1; zn+1 := 1 N N∑ i=1 zmn,i;n = 0, 1, 2, . . . (2.2) 3.2.2. Mét sè vÝ dô minh ho¹ Tr­êng hîp c¸c tËp Ci lµ siªu ph¼ng XÐt bµi to¸n chÊp nhËn låi: T×m mét ®iÓm n»m trong giao cña c¸c tËp låi Ci cho bëi biÓu thøc Ci = {x ∈ Rn | 〈x, vi〉 = µi}; i = 1, 2, . . . N. PhÐp chiÕu Pi lªn tËp Ci cho bëi c«ng thøc Pi(y) = y − 〈y,vi〉−µi‖vi‖2 vi. Sö dông c«ng thøc (1.1) ta thu ®­îc c«ng thøc lÆp sau ®©y x(n+1) = N∑ i=1 λ (n) i [ (1− α(n)i )x(n) + α(n)i ( x(n) − 〈x(n),vi〉−µi‖vi‖2 )] , x(0) cho tr­íc bÊt kú. (2.3) Bæ ®Ò 8. (Xem [7])Ai = Id− Pi lµ ¸nh x¹ kh«ng gi·n v÷ng vµ còng lµ 1−ng­îc ®¬n ®iÖu m¹nh. Bæ ®Ò 9. XÐt ph­¬ng tr×nh d¹ng 〈g, y〉u + ky = b; g, u, b ∈ Rn, k ∈ R, y lµ Èn. NghiÖm cña ph­¬ng tr×nh cho bëi c«ng thøc y = 1 k ( b− 〈g, b〉 k + 〈g, u〉 u ) Chøng minh: Gi¶ sö k 6= 0, ph­¬ng tr×nh ®· cho t­¬ng ®­¬ng víi y = 1 k ( b− 〈g, y〉u). Nh©n v« h­íng hai vÕ víi g ta ®­îc 〈g, y〉 = 1k (〈g, b〉 − 〈g, y〉.〈g, u〉). Tõ ®ã 〈g, y〉 = 〈g, b〉 k + 〈g, u〉 51 ⇒ y = 1 k ( b− 〈g, b〉 k + 〈g, u〉 u ) . ¥ Bµi to¸n chÊp nhËn låi ®ang xÐt t­¬ng ®­¬ng víi hÖ ph­¬ng tr×nh Ai(x) = 0, i = 1, 2, . . . N trong ®ã Ai = Id− Pi. Do ®ã ta cã thÓ ¸p dông c¸c kÕt qu¶ trong c¸c ®Þnh lý 18 vµ 19 cho hÖ ph­¬ng tr×nh nµy. XÐt phÐp lÆp (2.1) víi Ai = Id− Pi, ph­¬ng tr×nh cña phÐp lÆp trë thµnh x (n) i − ( x (n) i − 〈x(n)i , vi〉 − µi ‖vi‖2 vi ) + (αn N + γn ) x (n) i = γnx (n) ⇐⇒ 〈x (n) i , vi〉 − µi ‖vi‖2 vi + (αn N + γn ) x (n) i = γnx (n) ⇐⇒ (〈x(n)i , vi〉 − µi)vi + ‖vi‖2.(αnN + γn)x(n)i = ‖vi‖2γnx(n) ⇐⇒ (〈x(n)i , vi〉)vi + ‖vi‖2.(αnN + γn)x(n)i = ‖vi‖2γnx(n) + µivi sö dông bæ ®Ò 9, nghiÖm cña ph­¬ng tr×nh trªn cho bëi x (n) i = 1 ‖vi‖2 ( αn N + γn )[‖vi‖2γnx(n) + µivi − 〈vi, ‖vi‖2γnx(n) + µivi〉‖vi‖2(αnN + γn)+ 〈vi, vi〉vi ] = 1 ‖vi‖2 ( αn N + γn )[‖vi‖2γnx(n) + µivi − γn〈vi, x(n)〉+ µiαn N + γn + 1 vi ] = Nγn αn +Nγn x(n) + αn+Nγn N µi − γn〈x(n), vi〉( αn N + γn )( αn N + γn + 1 )‖vi‖2 vi = Nγn αn +Nγn [ x(n) + N αn +Nγn +N αn+Nγn Nγn µi − 〈x(n), vi〉 ‖vi‖2 ] B»ng c¸ch ®Æt µ (n) i = αn+Nγn Nγn µi vµ λn = N αn+Nγn+N ta cã x (n) i = Nγn αn +Nγn ( x(n) + λ(n) µ (n) i − 〈x(n), vi〉 ‖vi‖2 ) = Nγn αn +Nγn ( (1− λ(n))x(n) + λ(n)[x(n) − 〈x(n), vi〉 − µ(n)i‖vi‖2 ] ) = Nγn αn +Nγn ( (1− λ(n))x(n) + λ(n)P (n)i x(n) ) 52 Trong ®ã P (n) i lµ phÐp chiÕu lªn siªu ph¼ng C (n) i = {x ∈ Rn | 〈x, vi〉 = µ(n)i } lµ siªu ph¼ng song song víi siªu ph¼ng Ci. Nh­ vËy x(n+1) = 1 N N∑ i=1 x (n) i = Nγn αn +Nγn ( (1− λ(n))x(n) + λ (n) N N∑ i=1 P (n) i x (n) ) . Do αn rÊt nhá so víi γn nªn Nγn αn+Nγn ≈ 1, ý nghÜa h×nh häc cña ph­¬ng ph¸p chØnh lÆp song song lµ dïng phÐp chiÕu lªn mét siªu ph¼ng song song vµ c¸ch siªu ph¼ng cò mét kho¶ng rÊt nhá t­¬ng øng víi tham sè hiÖu chØnh. Tr­êng hîp c¸c tËp Ci lµ h×nh cÇu Gi¶ sö mçi tËp Ci lµ mét h×nh cÇu t©m ai vµ b¸n kÝnh ri. PhÐp chiÕu Pi cho bëi Pi(y) = ai + ri(y−ai) ‖y−ai‖ nÕu ‖y − ai‖ > ri y nÕu ‖y − ai‖ ≤ ri vµ Ai(y) = (Id− Pi)(y) =  ( 1− ri‖y−ai‖ ) (y − ai) nÕu ‖y − ai‖ > ri 0 nÕu ‖y − ai‖ ≤ ri. . C«ng thøc cña Aicã thÓ viÕt l¹i lµ Ai(x i n) = ‖xin − ai‖ − ri + |‖xin − ai‖ − ri| 2‖xin − ai‖ (xin − ai). NÕu ¸p dông ph­¬ng ph¸p chØnh lÆp song song ta ph¶i gi¶i mét ph­¬ng tr×nh phi tuyÕn phøc t¹p trong mçi b­íc lÆp, ®Ó gi¶m bít sù phøc t¹p ta cã thÓ c¶i biªn thuËt to¸n trªn nh­ sau: T¹i b­íc lÆp thø n, víi ph­¬ng ph¸p chØnh lÆp song song ta ph¶i gi¶i ph­¬ng tr×nh Ai(x i n) + (αn N + γn ) xin = γnxn. (2.4) Víi Ai nh­ trªn, ®©y lµ mét ph­¬ng tr×nh phi tuyÕn khã gi¶i, t¹i b­íc lÆp thø n, ta thay c¸c chuÈn ‖xin − ai‖ b»ng c¸c chuÈn ®· cã ‖xn − ai‖ vµ ®i tíi ph­¬ng 53 tr×nh A˜i(x i n) + (αn N + γn ) xin = γnxn. (2.5) trong ®ã A˜i(x i n) = ‖xn−ai‖−ri+|‖xn−ai‖−ri| 2‖xn−ai‖ (x i n − ai) = κin(xin − ai). Ph­¬ng tr×nh 2.5 lµ mét ph­¬ng tr×nh tuyÕn tÝnh vµ xin cã thÓ tÝnh dÔ dµng. Bæ ®Ò 10. Gi¶ sö (αn), (γn) lµ hai d·y sè d­¬ng sao cho αn → 0; γn → +∞; γn(αn+1−αn) α2n → 0 khi n →∞ vµ ∞∑ n=1 αn γn = +∞; αnγn → +∞. Gi¶ sö xÊp xØ thø n ®· ®­îc tÝnh, y0 cho tr­íc, phÐp lÆp sau ®©y héi tô tíi nghiÖm cã chuÈn nhá nhÊt x†.  A˜i(y i n) + ( αn N + γn ) yin = γnyn, (i = 1, 2, . . . , N); yn+1 = 1 N N∑ i=1 yin ;n = 0, 1, 2, . . . (2.6) Chøng minh: C¸c d·y (αn) vµ (γn) tháa m·n c¸c ®iÒu kiÖn cña ®Þnh lý 18 nªn phÐp lÆp (2.1) héi tô. §Ó chøng minh phÐp lÆp 2.6 héi tô, ta chøng minh hai d·y (xn) vµ (yn) cã cïng giíi h¹n b»ng c¸ch chØ ra ‖yn − xn‖ → 0. ThËt vËy, ta cã ‖yn+1 − xn+1‖ = ∥∥∥ 1 N N∑ i=1 (yin − xin) ∥∥∥ ≤ 1 N N∑ i=1 ‖yin − xin‖. (2.7) TiÕp theo ta ®¸nh gi¸ ‖yin − xin‖. Trõ tõng vÕ c¸c ph­¬ng tr×nh t×m yin vµ xin ta ®­îc A˜i(y i n)−Ai(yin) +Ai(yin)−Ai(xin) + ( αn N + γn ) (yin − xin) = γn(yn − xn). Nh©n v« h­íng hai vÕ víi (yin − xin) vµ sö dông tÝnh chÊt ng­îc ®¬n ®iÖu m¹nh cña to¸n tö Ai ta ®­îc γn〈yn − xn, yin − xin〉 ≥ 〈A˜i(yin)− Ai(yin), yin − xin〉+ (αn N + γn ) ‖yin − xin‖2, tõ ®ã suy ra(αn N + γn ) ‖yin − xin‖2 ≤ γn‖yn − xn‖‖yin − xin‖+ ‖A˜i(yin)−Ai(yin)‖‖yin − xin‖ hay (αn N + γn ) ‖yin − xin‖ ≤ γn‖yn − xn‖+ ‖A˜i(yin)− Ai(yin)‖. 54 Tõ ®©y suy ra ‖yin − xin‖ ≤ ( 1− αn Nγn ) ‖yn − xn‖+ N αn +Nγn ‖A˜i(yin)− Ai(yin)‖. Cã thÓ chøng minh ®­îc: ‖A˜i(yin)− Ai(yin)‖ ≤ M‖yn − yin‖. Víi bÊt ®¼ng thøc trªn ta cã ®¸nh gi¸ sau cho ‖yn − yin‖. Tõ ph­¬ng tr×nh (2.6), ta cã ‖yn − yin‖ = 1γn‖A˜i(yin) + αnN yin‖ ≤ Kγn v× dÔ thÊy A˜i(y i n) bÞ chÆn cßn αn → 0 vµ d·y yn còng bÞ chÆn. KÕt hîp l¹i ta ®­îc ‖yin − xin‖ ≤ ( 1− αn Nγn ) ‖yn − xn‖+ L Nγ2n . KÕt hîp víi ®¼ng thøc (2.7) ta cã ‖yn+1 − xn+1‖ ≤ 1 N N∑ i=1 ‖yin − xin‖ ≤ ( 1− αn αn +Nγn ) ‖yn − xn‖+ L γ2n . ¸p dông bæ ®Ò 7 víi an = ‖yn − xn‖, pn = αnαn+Nγn vµ bn = Lγ2n , sö dông c¸c ®iÒu kiÖn cho hai d·y (αn) vµ γn ta thÊy an, bn, pn tháa m·n c¸c ®iÒu kiÖn cña bæ ®Ò. Do ®ã ‖yn − xn‖ → 0. ¥ 3.3. Mét vµi thö nghiÖm sè 3.3.1. Bµi to¸n víi Ci lµ h×nh cÇu Ta xÐt vÝ dô sau: Cho c¸c tËp • C1 = {x ∈ R2 | f1(x) = (x1 − a)2 + (x2 − a)2 − a2 ≤ 0} • C2 = {x ∈ R2 | f2(x) = x21 + x22 − a2 ≤ 0} • C3 = {x ∈ R2 | f3(x) = ( x1 − a2 )2 + ( x2 − a2 )2 − a22 ≤ 0} 55 • C4 = {x ∈ R2 | f4(x) = (x1 + a)2 + (x2 − a)2 − (a+ ε)2 ≤ 0} Ta thÊy bèn tËp ®Òu lµ c¸c h×nh cÇu, trong ®ã ε lµ mét sè d­¬ng rÊt nhá. Khi ε = 0, bµi to¸n chÊp nhËn låi trªn chØ cã mét nghiÖm duy nhÊt lµ (x1, x2) = (0, a). Khi ε > 0 bµi to¸n cã v« sè nghiÖm. B¶ng sau cho kÕt qu¶ cña thuËt to¸n d­íi gradient lËp tr×nh b»ng MATLAB 7.4 vµ ch¹y trªn m¸y tÝnh laptop HP-Dv2613TU víi bé xö lý Core 2 Duo T5250 1.5GHz vµ dung l­îng RAM 3GB. §iÒu kiÖn dõng thuËt to¸n lµ fi(z) ≤ δ, i = 1, 2, 3, 4; Nmax lµ sè vßng lÆp ®· thùc hiÖn ®Õn khi dõng thuËt to¸n hoÆc sè vßng lÆp tèi ®a. a ε z0 δ Nmax time(s) f1 f2 f3 f4 z 100 0.1 1000 0 113 0.078 -19.9 -11.6 -15.7 0 0.1 1000 99.9421 1000 0.1 10000 0 110 0.03 -0 -16847 -8423 -57 0.0358 10000 991.5405 100 0.01 1000 1e-8 368396 33.67 1e-8 -199 -99 1e-8 0.00500025 1000 98.99998749 1000 0.01 10000 1e-8 107 900 2e-8 -6314 -3517 1e-8 0.0005000025 10000 996.8377 B¶ng 1: ThuËt to¸n d­íi gradient cho bµi to¸n víi 4 h×nh cÇu . Tõ b¶ng trªn ta nhËn thÊy r»ng khi ε nhá th× d·y lÆp héi tô rÊt chËm. B¶ng d­íi ®©y cho ta kÕt qu¶ cña thuËt to¸n tuÇn tù kiÓu xÐt tËp xa nhÊt cho bµi to¸n trªn. Trong mçi b­íc, ta tÝnh kho¶ng c¸ch tõ x(n) ®Õn c¸c tËp vµ chän ra tËp xa x(n) nhÊt ®Ó chiÕu. Nh­ vËy vÒ mÆt khèi l­îng tÝnh to¸n, ph­¬ng ph¸p nµy gièng víi ph­¬ng ph¸p ®ång bé. Ký hiÖu t­¬ng tù nh­ trªn thªm α lµ tham sè níi láng, RelErr lµ sai sè t­¬ng ®èi cña kÕt qu¶; ®iÒu kiÖn dõng thuËt to¸n lµ ‖z− xi‖ ≤ ri + δ hoÆc max{d(z, Ci) | i = 1, 2, 3, 4} ≤ δ. α a ε z0 δ Nmax time(s) z RelErr 1.0 1000 0 1 1e-10 105 7.9 0.002499964 0.0022407 1 997.763949 1.5 1000 0 1 1e-10 105 7.9 0.002499 0.001292 1 998.70919 1.9 1000 0 1 1e-20 105 7.9 0.00000002 0.00000152 1 999.998479 1.99 1000 0 1 1e-20 3750 0.3594 0.00000000 0.682181e-15 1 999.9999999 B¶ng 1A: ThuËt to¸n d­íi gradient xÐt tËp xa nhÊt cho bµi to¸n víi 4 h×nh cÇu. 56 3.3.2. Bµi to¸n víi Ci lµ tËp møc d­íi cña mét hµm låi VÝ dô 1. C¸c hµm fi lµ hµm kh¶ vi. Ta xÐt bµi to¸n chÊp nhËn låi víi 3 tËp • C1 = {x ∈ R2 | f1(x) = x21 + x22 − 3 ≤ 0} • C2 = {x ∈ R2 | f2(x) = x41 + 3x21x22 + 2x42 − 8 ≤ 0} • C3 = {x ∈ R2 | f3(x) = 3x21 − 2x1x2 + x22 − 4 ≤ 0} C¸c hµm fi trªn ®Òu lµ hµm låi v× Hessian cÊp 2 cña nã x¸c ®Þnh d­¬ng. Trong thö nghiÖm sè, c¸c tham sè níi láng vµ träng ®­îc chän ngÉu nhiªn trong tõng vßng lÆp. Trong b¶ng sau, x0 lµ vector xuÊt ph¸t, Nmax lµ sè lÇn lÆp ®Õn khi t×m ra nghiÖm, time lµ thêi gian ch¹y m¸y tÝnh b»ng gi©y; f1, f2, f3 lµ c¸c gi¸ trÞ hµm tÝnh t¹i nghiÖm; ε lµ tham sè kiÓm tra tÝnh chÊp nhËn cña nghiÖm. NÕu fi(x) ≤ ε; i = 1, 2, 3 th× x ®­îc chÊp nhËn vµ dõng thuËt to¸n. B¶ng sau cho kÕt qu¶ cña thuËt to¸n d­íi gradient lËp tr×nh b»ng MATLAB 7.4 vµ ch¹y trªn m¸y tÝnh laptop HP-Dv2613TU víi bé xö lý Core 2 Duo T5250 1.5GHz vµ dung l­îng RAM 3GB. x0 Nmax ε time(s) f1 f2 f3 (10, 10) 69 1e-16 0.0625 -0.845056 < ε -2.579387 (100, 100) 28 1e-16 0.03125 -0.945823 -0.003045 -2.773669 (1000, 1000) 25 1e-16 0.03125 -0.867516 -0.108774 -2.620157 B¶ng 2: ThuËt to¸n d­íi gradient cho bµi to¸n chÊp nhËn låi d¹ng tæng qu¸t. Do c¸c tham sè níi láng vµ träng ®­îc chän ngÉu nhiªn nªn nghiÖm cña bµi to¸n cã thÓ lµm cho c¸c gi¸ trÞ fi ®Òu nhá h¬n 0 thùc sù. NÕu cè ®Þnh c¸c tham sè níi láng vµ träng, kÕt qu¶ nhËn ®­îc chØ cã thÓ tháa m·n fi(x) < ε. KÕt qu¶ sau ®©y minh häa ®iÒu nµy (víi α vµ λ ®­îc chän ngÉu nhiªn tõ tr­íc vµ cè ®Þnh qua c¸c b­íc lÆp). α λ x0 Nmax ε time(s) f1 f2 f3 0.8848 0.332874 1.8087 0.187130 (10, 10) 106 1e-16 231.25 -0.632 1.598e-014 -1.261 0.0663 0.479996 57 VÝ dô 2. Trong vÝ dô nµy ta xÐt bµi to¸n chÊp nhËn låi víi 4 tËp • C1 = {(x, y, z) ∈ R3 | f1(x) = x2a2 + y 2 b2 + z2 c2 − 1 ≤ 0} • C2 = {(x, y, z) ∈ R3 | f2(x) = x2a2 + (y−2b) 2 (b+ε)2 + z2 c2 − 1 ≤ 0} • C3 = {(x, y, z) ∈ R3 | f3(x) = x2 + y2 + z2 − (b+ ε)2 ≤ 0} • C4 = {(x, y, z) ∈ R3 | f4(x) = x2 + (y − b)2 + (z − b)2 − (b+ ε)2 ≤ 0} C¸c tËp C1, C2 lµ hai h×nh ellip, C3, C4 lµ c¸c h×nh cÇu. ε lµ mét sè d­¬ng vµ rÊt nhá so víi b. Trong tr­êng hîp ®Æc biÖt, khi ε = 0 bèn tËp C1, C2, C3, C4 giao nhau chØ t¹i mét ®iÓm vµ ®ã còng lµ nghiÖm duy nhÊt cña bµi to¸n. Ch­¬ng tr×nh ®­îc lËp tr×nh b»ng ng«n ng÷ C vµ ch¹y trªn bã m¸y tÝnh nÒn Linux IBM 1350 víi 8 node tÝnh to¸n, mçi node chøa 2 bé xö lý Intel Xeon Dual Core 3.2GHz vµ dung l­îng RAM 2GB. (a, b, c) lµ c¸c tham sè chØ kÝch cì h×nh ellip vµ h×nh cÇu, ε lµ tham sè bÐ, δ lµ sè kiÓm tra tÝnh chÊp nhËn cña nghiÖm, ta dõng tÝnh nÕu fi(x) ≤ δ, i = 1, 2, 3, 4. Nmax lµ sè vßng lÆp ®· thùc hiÖn ®Õn khi dõng tÝnh. Vector xuÊt ph¸t lu«n chän lµ (1, 1, 1). (a, b, c) Nmax time(s) ε δ f1 f2 f3 f4 (100, 200, 140) 645062 2.26 0.1 10−7 < 10−7 < 10−7 −50.3 −1268.6 (250, 300, 300) 433687 1.51 0.25 10−7 < 10−7 < 10−7 −150.0 −5269.5 (1000, 500, 1500) 2542539 9.11 0.1 10−7 −0.00024 < 10−7 < 10−7 −13324 (1000, 500, 1500) 3310 0.01 0.5 10−8 < 10−8 −0.00177 −277.7 −16060 (1000, 500, 1500) 3140 0.01 0.3 10−9 < 10−9 −0.00097 −73.9 −15984 B¶ng 3: ThuËt to¸n d­íi gradient ch¹y trªn m¸y tÝnh song song. VÝ dô 3. C¸c hµm fi kh«ng kh¶ vi vµ chØ cã d­íi vi ph©n. Bæ ®Ò 11. Gi¶ sö f lµ hµm maximum tõng ®iÓm cña f1, f2, . . . , fm tøc lµ f(x) = max{f1(x), f2(x), . . . , fm(x)}, trong ®ã c¸c hµm fi ®Òu kh¶ d­íi vi ph©n. Khi ®ã d­íi vi ph©n ∂f(x) tÝnh bëi: ∂f(x) = co( ⋃ {∂fk(x) | fk(x) = f(x)}). Chøng minh: Xem phô lôc A. ¥ 58 Bæ ®Ò 12. Mét d­íi ®¹o hµm cña hµm f(x) = ‖x‖1 tÝnh bëi g = (gi); gi =  1 nÕu xi > 0, −1 nÕu xi < 0, ±1 nÕu xi = 0 . Chøng minh: Xem phô lôc A. ¥ Víi f(x) = ‖x‖∞ ta cã thÓ tÝnh nh­ sau: Tr­íc hÕt, hµm ‖x‖∞ = max{|xi| : i = 1, 2, . . . , n} cã thÓ xem nh­ max{fi(x) : i = 1, 2, . . . n} trong ®ã fi(x) = |xi| l¹i cã thÓ coi lµ max〈s(i), x〉 trong ®ã s (i) i = ±1; s(i)j = 0 (j 6= i). ¸p dông ph­¬ng ph¸p trong phô lôc A ta cã thÓ tÝnh ®­îc d­íi vi ph©n ∂fi(x) lµ g (i) j (x) =  0 nÕu j 6= i 1 nÕu xi > 0 −1 nÕu xi < 0 ±1 nÕu xi = 0. Do ®ã d­íi vi ph©n cña f(x) = ‖x‖∞ tÝnh nh­ sau: T×m chØ sè i sao cho fi(x) = |xi| = ‖x‖∞, chän ∂fi(x) sÏ ®­îc mét d­íi ®¹o hµm cÇn t×m. Trong vÝ dô nµy ta xÐt c¸c hµm f1(x) vµ f2(x) cã d¹ng. f1(x) = ∥∥∥ A1x+ b1〈c1, x〉+ d1 ∥∥∥ 2 + ‖x‖1 − ‖b1‖2|d1| , f2(x) = ∥∥∥ A2x+ b2〈c2, x〉+ d2 ∥∥∥ 2 + ‖x‖∞ − ‖b2‖2|d2| . Trong ®ã A1, A2 ∈ Mn×m; b1, b2 ∈ Rn; c1, c2 ∈ Rm; d1, d2 ∈ R vµ xÐt bµi to¸n chÊp nhËn låi: T×m x ∈ Rm | f1(x) ≤ 0; f2(x) ≤ 0. Dùa vµo 3 bæ ®Ò nªu trªn, d­íi vi ph©n cña c¸c chuÈn ‖ · ‖1 vµ ‖ · ‖∞ dÔ dµng tÝnh ®­îc, hµm ‖ · ‖2 lµ hµm kh¶ vi vµ cã ®¹o hµm lµ x‖x‖2 víi x 6= 0. Víi x = 0, tËp d­íi vi ph©n cho bëi {g ∈ Rn | 〈g, z〉 ≤ ‖z‖2 ∀z ∈ Rn}. Tõ bÊt ®¼ng 59 thøc Bunyakovsky |〈g, z〉| ≤ ‖g‖2‖z‖2 ≤ ‖z‖2, nÕu ‖g‖2 ≤ 1 ta thÊy tËp d­íi vi ph©n t¹i 0 chøa h×nh cÇu ®¬n vÞ; v× thÕ cã thÓ chän mét vector ®é dµi ®¬n vÞ bÊt kú. Thö nghiÖm sè cho vÝ dô sau f1(x) = ∥∥∥ A1x+ b1〈c1, x〉+ d1 ∥∥∥ 2 + ‖x‖1 − ‖b1‖2|d1| ≤ 0 f2(x) = ∥∥∥ A2x+ b2〈c2, x〉+ d2 ∥∥∥ 2 + ‖x‖∞ − ‖b2‖2|d2| ≤ 0 f3(x) = ∥∥∥ A3x+ b3〈c3, x〉+ d3 ∥∥∥ 2 + ‖x‖1 − ‖b3‖2|d3| ≤ 0 f4(x) = ∥∥∥ A4x+ b4〈c4, x〉+ d4 ∥∥∥ 2 + ‖x‖∞ − ‖b4‖2|d4| ≤ 0 Trong ®ã c¸c ma trËn Ai ∈ Rm×n; bi ∈ Rm; ci ∈ Rn; di ∈ R, i = 1, 2, 3, 4. Trong thö nghiÖm sè ta ký hiÖu: n sè chiÒu cña vector x, Nmax lµ sè lÇn lÆp ®Õn khi tháa m·n ®iÒu kiÖn dõng fi(x) ≤ ε, i = 1, 2, 3, 4. §Ó ®¬n gi¶n ta coi Ai, i = 1, 2, 3, 4 lµ c¸c ma trËn vu«ng. Chó ý r»ng bµi to¸n lu«n cã mét nghiÖm lµ vector θ. KÕt qu¶ tÝnh to¸n cho trong b¶ng d­íi ®©y, thuËt to¸n d­íi gradient lËp tr×nh trªn phÇn mÒm MATLAB 7.4, ch¹y trªn m¸y laptop HP-Dv2613TU, bé xö lý Core 2 Duo T5250 1.5GHz, RAM 3GB. C¸c vector bi, ci vµ c¸c sè thùc di ®­îc lÊy ngÉu nhiªn, c¸c ma trËn A1, A2 lµ ma trËn Hilbert vµ chuyÓn vÞ cña nã, A3 lµ ma trËn toµn phÇn tö 1 (cho bëi lÖnh g¸n A3 = ones(n, n)), A4 lµ tæng cña ma trËn Hilbert cÊp n vµ ma trËn toµn phÇn tö 1. n Nmax time(s) ε f1 f2 f3 f4 3000 127 205.6 1e− 20 −58562 −44581 < ε −12077 1000 126 21.9 1e− 16 −13643 −30560 < ε −1394 4000 151 434.4 1e− 16 −12383 −573986 < ε −6821 B¶ng 4: Bµi to¸n chÊp nhËn låi víi c¸c tËp møc d­íi cña hµm chØ cã d­íi vi ph©n. 60 3.3.3. Ph­¬ng ph¸p chØnh lÆp trong kh«ng gian v« h¹n chiÒu Trong phÇn nµy ta xÐt kh«ng gian v« h¹n chiÒu L2([0, 1]) víi tÝch v« h­íng 〈f, g〉 = ∫ 10 f(x)g(x) dx. XÐt hai h×nh cÇu C1 = B(f1, 0.5) víi f1(x) ≡ 1 vµ C2 = B(f2, 0.5) víi f2(x) ≡ 2. Bµi to¸n cã 1 nghiÖm lµ hµm f(x) ≡ 1.5. H×nh chiÕu lªn 2 h×nh cÇu ®­îc tÝnh theo c«ng thøc Pi(y) = (1− λ)fi + λy λ ≤ 1y λ > 1 trong ®ã λ = 0.5‖y − fi‖L2 Chän hµm xuÊt ph¸t lµ x(0) = sin t. ChuÈn ®­îc tÝnh gÇn ®óng b»ng tÝch ph©n theo c«ng thøc Simpson víi sè ®iÓm chia N tïy chän. C¸c tham sè αn = 1 n0.5−φ , γn = n0.5+φ víi φ = 10−6. N RelErr time(s) Nmax 2000 0.026078 289.875 200000 1500 0.026001 343.797 300000 B¶ng 5: ThuËt to¸n chØnh lÆp song song trong kh«ng gian v« h¹n chiÒu. 61 KÕt luËn Qua ba ch­¬ng, luËn v¨n ®· tr×nh bµy kh¸i qu¸t vÒ bµi to¸n chÊp nhËn låi vµ c¸c thuËt to¸n tuÇn tù vµ song song ®Ó gi¶i bµi to¸n cïng øng dông cña ph­¬ng ph¸p chØnh lÆp song song. §èi víi bµi to¸n chÊp nhËn låi khi c¸c tËp låi cho ë d¹ng tËp møc d­íi cña hµm låi, t¸c gi¶ cßn ch­a ¸p dông ®­îc ph­¬ng ph¸p chØnh lÆp song song mét c¸ch hiÖu qu¶. Ngoµi ra viÖc tÝnh to¸n c¸c d­íi vi ph©n cÇn thiÕt cho thuËt to¸n d­íi gradient khi c¸c hµm fi kh«ng cã ®¹o hµm mµ chØ cã d­íi vi ph©n míi chØ thùc hiÖn ®­îc cho mét sè hµm ®Æc biÖt. H­íng ph¸t triÓn tiÕp theo cho ®Ò tµi lµ: • T×m c¸ch ¸p dông hiÖu qu¶ h¬n ph­¬ng ph¸p chØnh lÆp song song cho bµi to¸n chÊp nhËn låi. Chøng minh sù héi tô cho tr­êng hîp bµi to¸n chÞu nhiÔu. • TÝnh to¸n c¸c d­íi vi ph©n cho thuËt to¸n d­íi gradient cho c¸c tr­êng hîp hµm f cho ë d¹ng phøc t¹p. Do thêi gian vµ tr×nh ®é cã h¹n, nªn dï ®· rÊt cè g¾ng vµ còng ®· häc thªm ®­îc nhiÒu kiÕn thøc míi song ch¾c ch¾n luËn v¨n cßn cã nhiÒu h¹n chÕ. T¸c gi¶ rÊt mong nhËn ®­îc sù gãp ý, nhËn xÐt, phª b×nh cña c¸c thÇy c«, ®ång nghiÖp vµ nh÷ng ng­êi quan t©m ®Õn ®Ò tµi ®Ó tiÕp tôc hoµn thiÖn. 62 Tµi liÖu tham kh¶o [1] Y.Alber, I.Ryazantseva,"Nonlinear ill-posed problems of monotone type", Springer, 2006. [2] P.K.Anh, N.B­êng , "Bµi to¸n ®Æt kh«ng chØnh", NXB §H Quèc gia Hµ Néi, 2007. [3] P. K.Anh, C.V.Chung, "Parallel iterative regularization methods for solving systems of ill-posed equations ", Applied Mathematics and Computation, (2009). [4] H.H.Bauschke, J.M.Borwein, "On projection algorithms for solving convex feasibility problems", SIAM Review , Vol.38, (1996), 367-426 [5] S.Boyd, L.Vandenberghe,"Convex Optimization", Cambridge, 2004. [6] S.Boyd, L.Vandenberghe,"Subgradients",Notes for EE364b, Stanford Uni- versity, Winter 2006-07, April 13, 2008. [7] N.Buong, P.V.Son, "An explicit iteration method for convex feasibility prob- lems in Hilbert spaces", Applied Mathematical Science 2, 15, (2008), 725- 734. [8] Y.Censor , "On sequential and parallel projection algorithms for feasibility and optimization"; Proceedings of the SPIE, Vol.4553, 2001, 1-9. [9] Y.Censor, D.Gordon, R.Gordon, "Component averaging: An efficient itera- tive parallel algorithm for large and sparse unstructured problems", Parallel Computing 27 , 2001, pp. 777-808. 63 [10] N. Q. Hïng, ''Hµm kho¶ng c¸ch vµ mét sè øng dông", LuËn v¨n th¹c sü khoa häc, 2009. [11] T.Lu, P.Neittaanmaki, X.-C. Tai, "A parallel splitting up method for par- tial differential equations and its application to Navier-Stokes equations", RAIRO Mathematical Modelling and Numerical Analysis 26 6, 1992, pp. 673-708. [12] A.W.Roberts, D.E.Varberg, "Convex Functions", Academic Press, New York, (1973). [13] R.Tyrrell Rockafellar, "Convex Analysis", Princeton University Press,1970. [14] M.Tsukada, "Convergence of best approximations in a smooth Banach space", J. Approx. Theory 40, (1984). 64 Phô lôc A Mét sè ®iÓm l­u ý khi tÝnh d­íi vi ph©n Trong môc nµy ta ®­a ra mét sè quy t¾c tÝnh d­íi vi ph©n. Ta ph©n biÖt hai møc ®é tÝnh to¸n d­íi vi ph©n. Møc ®é I: Víi mçi x ∈ int dom f ta chØ tÝnh ra mét phÇn tö n»m trong tËp d­íi vi ph©n cña f . Trong thùc hµnh ta chØ cÇn ®Õn møc nµy. Møc ®é II: Víi mçi x ∈ int(dom f) ta m« t¶ toµn bé tËp d­íi vi ph©n ∂f(x). Møc ®é nµy cÇn dïng trong c¸c kh¶o s¸t lý thuyÕt, ch¼ng h¹n khi cÇn m« t¶ ®Çy ®ñ vµ chÝnh x¸c c¸c ®iÒu kiÖn tèi ­u. 1.1. Mét vµi tÝnh chÊt cña d­íi vi ph©n TÝnh chÊt 1. TÝnh thuÇn nhÊt kh«ng ©m. Víi mäi α ≥ 0 ta cã ∂(αf)(x) = α∂f(x). TÝnh chÊt 2. D­íi vi ph©n cña tæng vµ tÝch ph©n. Gi¶ sö f = f1 + f2 + · · ·+ fm, trong ®ã fi (i = 1, 2, . . . ,m) lµ c¸c hµm låi. Khi ®ã ∂f(x) = ∂f1(x) + . . .+ ∂fm(x). TÝnh chÊt nµy më réng cho c¸c tæng v« h¹n, tÝch ph©n vµ kú väng(nÕu tån t¹i). TÝnh chÊt 3. PhÐp hîp thµnh víi mét ¸nh x¹ affine. Gi¶ sö f lµ mét hµm låi vµ h(x) = f(Ax+ b). Khi ®ã ∂h(x) = AT∂f(Ax+ b). 65 1.2. Mét sè vÝ dô VÝ dô A.1. Hµm låi nhËn ®­îc b»ng c¸ch lÊy maximum tõng ®iÓm. Gi¶ sö f lµ hµm maximum tõng ®iÓm cña f1, f2, . . . , fm tøc lµ f(x) = max{f1(x), f2(x), . . . , fm(x)}, trong ®ã c¸c hµm fi ®Òu kh¶ d­íi vi ph©n. Tr­íc hÕt ta tÝnh d­íi vi ph©n víi møc ®é I. Gi¶ sö k lµ chØ sè sao cho fk(x) = f(x) vµ g − k(x) ∈ ∂fk(x). Khi ®ã gk(x) ∈ ∂f(x). Nãi c¸ch kh¸c lµ muèn t×m d­íi vi ph©n cña hµm maximum tõng ®iÓm, ta t×m mét trong sè c¸c hµm ®¹t maximum råi lÊy mét phÇn tö n»m trong d­íi vi ph©n cña hµm nµy. §iÒu nµy suy ra tõ f(z) ≥ fk(z) ≥ fk(x) + 〈gk(x), z − x〉 = f(x) + 〈gk(x), z − x〉. Tæng qu¸t h¬n ta cã ∂f(x) = co( ⋃ {∂fk(x) | fk(x) = f(x)}). VÝ dô A.1.1. Hµm maximum tõng ®iÓm cña c¸c hµm kh¶ vi. Gi¶ sö f(x) = max i=1,2,...,m fi(x), trong ®ã fi lµ hµm låi vµ kh¶ vi. Khi ®ã ∂f(x) = co{5fi(x) | fi(x) = f(x)} T¹i x nµo ®ã, nÕu chØ cã mét hµm ®¹t max th× ∂f(x) chØ lµ mét ®iÓm, chÝnh lµ ®¹o hµm cña hµm nµy. NÕu cã nhiÒu h¬n mét hµm ®¹t max th× ∂f(x) lµ mét ®a diÖn låi. VÝ dô A.1.2. ChuÈn ‖ · ‖1. Gi¶ sö f(x) = ‖x‖1 = |x1|+ |x2|+ · · ·+ |xn|. Hµm nµy lµ hµm låi nh­ng kh«ng kh¶ vi. §Ó t×m gradient cña nã, chó ý r»ng f(x) cã thÓ xem nh­ maximum cña 2n hµm tuyÕn tÝnh f(x) = ‖x‖1 = |x1|+|x2|+· · ·+|xn| = max{sTx | s = (si)i=1,...,n; si ∈ {−1, 1}}. 66 Ta cã thÓ ¸p dông vÝ dô 1 ®Ó t×m d­íi vi ph©n cña f . Tr­íc hÕt ta t×m s ∈ {−1, 1}n sao cho sTx = ‖x‖1. Ta cã thÓ chän si = 1 nÕu xi > 0, si = −1 nÕu xi < 0; nÕu xi = 0 th× cã thÓ chän tïy ý si = 1 hay -1 vµ cã Ýt nhÊt hai hµm ®¹t maximum. Tõ ®ã cã thÓ chän d­íi ®¹o hµm gi =  1 nÕu xi > 0, −1 nÕu xi < 0, ±1 nÕu xi = 0 . TËp d­íi vi ph©n lµ bao låi cña c¸c d­íi ®¹o hµm vµ cã d¹ng ∂f(x) = {g | ‖g‖∞ ≤ 1; gTx = ‖x‖1}. VÝ dô A.2. Hµm supremum. Ta më réng vÝ dô 1, xÐt hµm f lµ supremum trªn mét tËp v« h¹n c¸c hµm. f(x) = sup α∈A fα(x), trong ®ã c¸c hµm fα lµ kh¶ d­íi vi ph©n. Ta chØ t×m d­íi vi ph©n cña f víi møc ®é I. Gi¶ sö r»ng supremum ®¹t ®­îc t¹i mét chØ sè β ∈ A nµo ®ã, tøc lµ fβ(x) = f(x) vµ g ∈ ∂fβ(x). Khi ®ã g ∈ ∂f(x). NÕu supremum kh«ng ®¹t ®­îc th× hµm f cã thÓ cã hoÆc kh«ng kh¶ d­íi vi ph©n t¹i x vµ tïy thuéc vµo tËp A. Gi¶ sö thªm r»ng tËp A lµ compact (theo mét metric nµo ®ã) vµ hµm α 7−→ fα(x) lµ hµm nöa liªn tôc trªn víi mçi x. Khi ®ã ∂f(x) = co (⋃{∂fα(x) | fα(x) = f(x)}) VÝ dô A.2.1. Gi¸ trÞ riªng lín nhÊt cña ma trËn ®èi xøng. XÐt f(x) = λmax(A(x)), trong ®ã A(x) = A0 + x1A1 + · · ·+ xnAn, Ai ∈ Sm. Ta cã thÓ biÓu diÔn hµm f nh­ lµ hµm maximum tõng ®iÓm cña hä c¸c hµm låi fy(x) = y TA(x)y, f(x) = sup ‖y‖2=1 yTA(x)y. Trong biÓu thøc nµy tËp A = {y ∈ Rm | ‖y‖2 = 1} lµ mét tËp compact theo metric trong Rm. 67 Mçi hµm fy(x) = y TA(x)y = yTA0y + x1y TA1y + · · · + xnyTAny lµ mét hµm affine theo x víi mçi y cè ®Þnh do ®ã nã cã d­íi vi ph©n chÝnh lµ gradient 5fy(x) = (yTA1y, . . . , yTAny). Hµm fy(x) ®¹t gi¸ trÞ supremum víi mçi x lµ hµm øng víi y lµ vector riªng øng víi gi¸ trÞ riªng lín nhÊt cña A(x). Do ®ã, ®Ó t×m d­íi ®¹o hµm, ta t×m vector riªng øng víi gi¸ trÞ riªng λmax sau ®ã chuÈn hãa vµ ký hiÖu lµ yx. Khi ®ã mét d­íi ®¹o hµm cña f t¹i x cho bëi g = (yTxA1yx, . . . , y T xAnyx). TËp chØ sè trong tr­êng hîp nµy lµ A = {y ∈ Rn | ‖y‖2 = 1} lµ compact, ¸nh x¹ y 7−→ fy(x) dÔ thÊy lµ liªn tôc; do ®ã ∂f(x) = co{5fy(x) | A(x)y = λmax(A(x))y; ‖y‖2 = 1}. 68