Phương pháp lặp giải bài toán tìm nghiệm có chuẩn nhỏ nhất - Nguyễn Tất Thắng

ISSN: 1859-2171 e-ISSN: 2615-9562 TNU Journal of Science and Technology 208(15): 169 - 175 Email: jst@tnu.edu.vn 169 PHƯƠNG PHÁP LẶP GIẢI BÀI TOÁN TÌM NGHIỆM CÓ CHUẨN NHỎ NHẤT Nguyễn Tất Thắng Đại học Thái Nguyên TÓM TẮT Trong bài báo này chúng tôi nghiên cứu bài toán hai cấp trong không gian Hilbert thực: tìm nghiệm có chuẩn nhỏ nhất trên tập nghiệm của bài toán bất đẳng thức biến phân. Chúng tôi đề xuất một phương pháp lặp mới giải bài toán hai cấp này, đồng thời thiết lập sự hội tụ mạnh của phương pháp. Từ khóa: Bất đẳng thức biến phân; không gian Hilbert; chuẩn nhỏ nhất; bài toán hai cấp; toán tử đơn điệu. Ngày nhận bài: 23/9/2019; Ngày hoàn thiện: 23/10/2019; Ngày đăng: 27/11/2019 ITERATIVE METHOD FOR SOLVING A MINIMUM NORM PROBLEM Nguyen Tat Thang Thai Nguyen University ABSTRACT In this paper we study the problem of finding a minimum norm solution over the set of solutions of a variational inequality in Hilbert spaces. In order to solve this bilevel problem, we propose a new iterative method and establish a strong convergence theorem for it. Keywords: Variational inequality; Hilbert space; minimum norm; bilevel problem; monotone operator. Received: 23/9/2019; Revised: 23/10/2019; Published: 27/11/2019 Email: thangnt@tnu.edu.vn 1 Giîi thi»u Cho H l  mët khæng gian Hilbert thüc vîi t½ch væ h÷îng h
;
i v  chu©n k
k. Cho C l  mët tªp con lçi âng kh¡c réng cõa H. Cho ¡nh x¤ G : C ! H (th÷íng ÷ñc gåi l  ¡nh x¤ gi¡). B i to¡n b§t ¯ng thùc bi¸n ph¥n (ìn trà) trong H ÷ñc ph¡t biºu nh÷ sau: T¼m x 2 C sao cho hG(x); x xi  0 8x 2 C: (1) Kþ hi»u G l  tªp nghi»m cõa b i to¡n (1). B i to¡n b§t ¯ng thùc bi¸n ph¥n (1) ÷ñc giîi thi»u l¦n ¦u ti¶n v o n«m 1966 khi Philip Hartman v  Guido Stampacchia cæng bè nhúng nghi¶n cùu ¦u ti¶n cõa m¼nh v· b§t ¯ng thùc bi¸n ph¥n li¶n quan ¸n vi»c gi£i c¡c b i to¡n bi¸n ph¥n, b i to¡n i·u khiºn tèi ÷u v  c¡c b i to¡n bi¶n trong lþ thuy¸t ph÷ìng tr¼nh ¤o h m ri¶ng. B i to¡n b§t ¯ng thùc bi¸n ph¥n ¢ v  ang thu hót ÷ñc nhi·u sü quan t¥m cõa c¡c nh  to¡n håc v¼ c¡c mæ h¼nh cõa nâ chùa nhi·u b i to¡n quan trång cõa mët sè l¾nh vüc kh¡c nhau trong to¡n håc ùng döng nh÷ tèi ÷u hâa, b i to¡n iºm b§t ëng, lþ thuy¸t trá chìi, c¥n b¬ng m¤ng l÷îi giao thæng . . . (xem [2,4,5,10]). Nhi·u ph÷ìng ph¡p gi£i b i to¡n b§t ¯ng thùc bi¸n ph¥n ¢ x¥y düng, trong â ph÷ìng ph¡p chi¸u âng vai trá quan trång v¼ sü ìn gi£n v  thuªn lñi trong qu¡ tr¼nh t½nh to¡n . . . (xem [1,6, 7]). B i to¡n t¼m nghi»m câ chu©n nhä nh§t l  b i to¡n t¼m ph¦n tû x 2 C sao cho kxk  kxk 8x 2 C: (2) Trong b i b¡o n y, chóng tæi · xu§t mët ph÷ìng ph¡p l°p mîi gi£i b i to¡n (2) trong tr÷íng hñp C l  tªp nghi»m cõa b i to¡n b§t ¯ng thùc bi¸n ph¥n (1), ngh¾a l  t¼m ph¦n tû x 2 G sao cho kxk  kxk 8x 2 G: (3) Kþ hi»u l  tªp nghi»m cõa b i to¡n (3). Gi£ thi¸t r¬ng 6= ;. 2 Mët sè ki¸n thùc bê trñ º x¥y düng d¢y l°p v  chùng minh ành lþ hëi tö m¤nh, ta c¦n mët sè ki¸n thùc bê trñ sau. Cho C l  mët tªp con, lçi, âng, kh¡c réng cõa khæng gian Hilbert thüc H. H¼nh chi¸u cõa mët iºm x 2 H tr¶n C, kþ hi»u PC(x), l  mët iºm thuëc C v  g¦n iºm x nh§t, ÷ñc x¡c ành bði PC(x) = argmin fkx yk : y 2 Cg: (4) H¼nh chi¸u PC(x) cõa x tr¶n C luæn tçn t¤i v  duy nh§t v  PC l  mët ¡nh x¤ khæng gi¢n, ngh¾a l  kPC(x) PC(y)k  kx yk: Mët ¡nh x¤ G : C ! H ÷ñc gåi l  -ìn i»u m¤nh ng÷ñc tr¶n C, n¸u hG(x)G(y); x yi  kG(x)G(y)k2 8x; y 2 C;  > 0: (5) Kþ hi»u Fix(S) l  tªp iºm b§t ëng cõa ¡nh x¤ S : C ! C, ngh¾a l  Fix(S) = fx 2 C : S(x) = xg: Bê · 2.1 (xem [3]) Cho C l  mët tªp con lçi âng trong khæng gian Hilbert thüc H, S : C ! H l  mët ¡nh x¤ khæng gi¢n. Khi â n¸u Fix(S) 6= ; th¼ ¡nh x¤ IHS l  ¡nh x¤ nûa âng t¤i y 2 H, ngh¾a l  vîi måi d¢y fxkg  C hëi tö y¸u ¸n ph¦n tû x 2 C v  d¢y f(IHS)(xk)g hëi tö m¤nh ¸n y th¼ (IH S)(x) = y. Bê · 2.2 (xem [8]) Cho fsng l  d¢y sè thüc khæng ¥m thäa m¢n sn+1  (1n)sn + n vîi måi n  0, trong â fng v  f ng l  c¡c d¢y sè thüc thäa m¢n c¡c i·u ki»n sau: (i) fng  (0; 1) v  P1n=0 n =1, (ii) lim supn!1 n n  0 ho°c P1n=0 jn nj <1. Khi â limn!1 sn = 0. 3 K¸t qu£ ch½nh Cho H l  mët khæng gian Hilbert thüc, C l  mët tªp con lçi âng kh¡c réng cõa H, G : H ! H l  mët ¡nh x¤. Ta x¥y düng d¢y l°p fxkg nh÷ sau: yk = PC(x k G(xk)); xk+1 = (1 k)yk; (6) trong â ,  l  c¡c sè thüc khæng ¥m v  fkg l  d¢y tham sè thüc. Sü hëi tö cõa ph÷ìng ph¡p l°p (6) ÷ñc cho trong ành lþ sau ¥y. ành lþ 3.1 Cho C l  mët tªp con, lçi, âng, kh¡c réng cõa khæng gian Hilbert thüc H v  ¡nh x¤ G : H ! H l  ¡nh x¤ -ìn i»u m¤nh ng÷ñc tr¶n H. N¸u c¡c sè thüc ,  v  d¢y tham sè thüc fkg thäa m¢n c¡c i·u ki»n (C1) 0 <   2; 0 <  < 2, (C2) 0 < k  minf1; 1 g;  = 1 j1 j, (C3) lim k!1 k = 0, lim k!1  1 k+1 1 k  = 0, 1P k=0 k =1, th¼ d¢y fxkg ÷ñc x¡c ành bði (6) hëi tö m¤nh ¸n nghi»m duy nh§t cõa b i to¡n (3). Chùng minh. Ta x¥y düng ¡nh x¤ Sk : H ! H nh÷ sau Sk(x) = PC(x G(x)) k[PC(x G(x))] 8x 2 H: (7) Sû döng t½nh -ìn i»u m¤nh ng÷ñc cõa ¡nh x¤ G, t½nh ch§t khæng gi¢n cõa ph²p chi¸u PC ta nhªn ÷ñc kPC(x G(x)) PC(y G(y))k2  kx G(x) y + G(y)k2 = kx yk2 + 2kG(x)G(y)k2 2hx y;G(x)G(y)i  kx yk2 + ( 2)kG(x)G(y)k2  kx yk2 8x; y 2 H: (8) Tø ¥y suy ra kSk(x)Sk(y)k = kPC(xG(x))k[PC(xG(x))]PC(yG(y))+k[PC(yG(y))]k  (1 k)kx yk; (9) vîi  = 1 j1 j 2 (0; 1] (xem [9]). Do â, Sk l  ¡nh x¤ co tr¶n H. Theo Nguy¶n lþ ¡nh x¤ co Banach, tçn t¤i iºm b§t ëng k thäa m¢n Sk( k) = k. Vîi méi x^ 2 G, °t C = ( x 2 H : kx x^k  kx^k  ) ; k¸t hñp vîi t½nh ch§t khæng gi¢n cõa ph²p chi¸u PC , suy ra ¡nh x¤ SkPC l  ¡nh x¤ co tr¶n H. Do vªy, tçn t¤i duy nh§t iºm zk thäa m¢n Sk[PC(z k)] = zk. °t zk = PC(z k), tø (7) v  (9) ta suy ra kzk x^k = kSk(zk) x^k  kSk(zk) Sk(x^)k+ kSk(x^) x^k = kSk(zk) Sk(x^)k+ kSk(x^) PC(x^ kG(x^))k  (1 k)kzk x^k+ kkPC(x^ kG(x^))k  (1 k)kx^k  + kkx^k = kx^k  : i·u n y ch¿ ra r¬ng zk 2 C v  Sk[PC(zk)] = Sk(zk) = zk. Do vªy, k = zk 2 C. M°t kh¡c, vîi b§t ký d¢y con fkig cõa d¢y fkg thäa m¢n ki *  ; lim k!1 k = 0; khi i!1 kPC(kiG(ki))kik = kPC(kiG(ki))Ski(ki)k = kikPC(kiG(ki))k ! 0 (10) Theo (8), ¡nh x¤ PC(
kG(
)) l  khæng gi¢n tr¶n H, k¸t hñp vîi (10), Bê · 2.1 v  ki * , suy ra PC( G()) = . Vªy  2 G. Ti¸p theo, ta chùng minh lim j!1 kj = x 2 : Thªt vªy, °t zk = PC( k G(k)), v = ( 1)(x); vk = ( 1)(zk). V¼ Skj( kj) = kj v  x = PC(x G(x)) n¶n ta câ (1 kj)(kj zkj) + kj(kj + vkj) = 0 v  (1 kj)[I PC(
G(
))](x) + kj(x + v) = kj(x + v): Khi â, kjhx+v; kjxi = (1kj)hkjx(zkjx); kjxi+kjhkjx+vkjv; kjxi: (11) Theo b§t ¯ng thùc Schwarz, ta câ hkj x (zkj x); kj xi  kkj xk2 kzkj xkkkj xk  kkj xk2 kkj xk2 = 0; (12) v  hkj x + vkj v; kj xi  kkj xk2 kvkj vkkkj xk  kkj xk2 (1 )kkj xk2 = kkj xk2: (13) K¸t hñp (11), (12) v  (13), ta ÷ñc kkjxk2  hx+v; kjx) = hx; kjxi = hx; kji+hx; xi  hx; kji: Vªy kkj xk2  hx;  kji: Cho j ! 1, d¢y fkjg hëi tö m¤nh ¸n x. Khi â, tçn t¤i mët d¢y con fkjg cõa d¢y fkg thäa m¢n 0  lim inf k!1 kk xk  lim sup k!1 kk xk = lim j!1 kkj xk = 0: Vªy, d¢y fkg hëi tö m¤nh ¸n iºm x 2 . M°t kh¡c, theo (9), ta x²t kxk kk  kxk k1k+ kk1 kk = kSk1(xk1) Sk1(k1)k+ kk1 kk  (1 k1)kxk1 k1k+ kk1 kk: (14) Tø ¡nh gi¡ kk1 kk = kSk1(k1) Sk(k)k = k(1 k)zk kvk (1 k1)zk1 + k1vk1k = k(1 k)(zk zk1) k(vk vk1) + (k1 k)(zk1 + vk1)k  (1 k)kzk zk1k+ kkvk vk1k+ jk1 kjkzk1k  (1 k)kzk zk1k+ kj1 jkk k1k+ jk1 kjkzk1k; ta suy ra kkk1 kk  jk1 kjkzk1k; hay kk k1k  jk1 kjkz k1k k : (15) Thay (15) v o (14), ta ÷ñc kxk kk  (1 k1)kxk1 k1k+ jk1 kjkz k1k k : °t k = jk k+1jkzkk kk+1 2 ; k  0: Khi â kxk kk  (1 k1)kxk1 k1k+ k1k1 8k  1: V¼ d¢y fzkg bà ch°n, gi£ sû kzkk M vîi måi k  0, ta câ lim k!1 k = lim k!1 jk k+1jkzkk kk+1 2  M  2 lim k!1  1 k+1 1 k  = 0: (16) Do â, theo Bê · 2.2 suy ra lim k!1 kxk kk = 0: M°t kh¡c, theo chùng minh tr¶n, d¢y fkg hëi tö m¤nh ¸n nghi»m x, suy ra d¢y fxkg công hëi tö m¤nh ¸n nghi»m duy nh§t x cõa b i to¡n (3). Email: jst@tnu.edu.vn 5 TÀI LIỆU THAM KHẢO [1]. Y. Censor, A. Gibali, S. Reich, "The subgradient extragradient method for solving variational inequalities in Hilbert space", J. Optim. Theory Appl., 148(2), pp. 318–335, 2011. [2]. R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer, New York, NY, 1984. [3]. K. Goebel, W.A. Kirk, Topics on metric fixed point theory, Cambridge University Press, Cambridge, England, 1990. [4]. P. Jaillet, D. Lamberton, B. Lapeyre, “Variational Inequalities and the Pricing of American Options”, Acta Applicandae Mathematica, 21, pp. 263–289, 1990. [5]. D. Kinderlehrer, and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, NY, 1980. [6]. R. Kraikaew, S. Saejung, "Strong convergence of the Halpern subgradient extra-gradient method for solving variational inequalities in Hilbert spaces", J. Optim. Theory Appl., 163(2), pp. 399–412, 2014. [7]. Y.V. Malitsky, "Projected reflected gradient methods for monotone variational inequalities.", SIAM J. Optim., 25(1), pp. 502–520, 2015. [8]. H.K. Xu, "Iterative algorithms for nonliner operators", J. London Math. Soc., 66, pp. 240–256, 2002. [9]. I. Yamada, "The hybrid steepest descent method for the variational inequality problem over the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings", In inherently parallel algorithm for feasibility and optimization and their applications edited by: D. Butnariu, Y. Censor, and S. Reich, Elsevier., 473–504, 2001. [10]. E. Zeidler, Nonlinear Functional Analysis and Its Applications, III: Variational Methods and Applications, Springer, New York, 1985. Email: jst@tnu.edu.vn 176