Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về sự hội tụ hữu hạn của các phương pháp lặp cho các bất đẳng thức biến phân trong không gian Hilbert
Tóm tắt
Trong một không gian Hilbert, chúng tôi nghiên cứu sự hội tụ hữu hạn của các phương pháp lặp để giải quyết một bất đẳng thức biến phân đơn điệu dưới giả thiết sắc yếu. Hầu hết các kết quả đến nay yêu cầu rằng chuỗi được tạo ra bởi phương pháp phải hội tụ mạnh đến một nghiệm. Trong bài báo này, chúng tôi chứng minh rằng thuật toán điểm gần nhất để giải quyết bất đẳng thức biến phân sẽ dừng lại tại một nghiệm trong một số bước lặp hữu hạn nếu tập nghiệm là sắc yếu. Do đó, chúng tôi suy ra các kết quả hội tụ hữu hạn cho phương pháp chiếu gradient và phương pháp ngoại gradient. Các kết quả của chúng tôi cho thấy rằng giả thiết về sự hội tụ mạnh của các chuỗi có thể được loại bỏ trong trường hợp không gian Hilbert.
Từ khóa
#bất đẳng thức biến phân #không gian Hilbert #phương pháp lặp #hội tụ hữu hạn #thuật toán điểm gần nhấtTài liệu tham khảo
Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York (1980)
Aubin, J.-P., Ekeland, I.: Applied Nonlinear Analysis. Pure and Applied Mathematics. Wiley, New York (1984)
Takahashi, W.: Nonlinear Functional Analysis. Yokohama, Japan (2000)
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems I. Springer, New York (2003)
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011)
Martinet, B.: Régularisation d’inéquations variationnelles par approximations successives. Rev. Fr. Inform. Rech. Opér. 4, 154–158 (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)
Goldstein, A.A.: Convex programming in Hilbert space. Bull. Am. Math. Soc. 70, 709–710 (1964)
Levitin, E.S., Polyak, B.T.: Constrained minimization methods. Comput. Math. Math. Phys. 6, 1–50 (1966)
Korpelevich, G.M.: Extragradient method for finding saddle points and other problems. Matecon 12, 747–756 (1976)
Iiduka, H., Takahashi, W., Toyoda, M.: Approximation of solutions of variational inequalities for monotone mappings. Panam. Math. J. 14, 49–61 (2004)
Nadezhkina, N., Takahashi, W.: Strong convergence theorem by a hybrid method for nonexpansive mappings and Lipschitz-continuous monotone mappings. SIAM J. Optim. 16, 1230–1241 (2006)
Calamai, P.H., Moré, J.J.: Projected gradient methods for linearly constrained problems. Math. Program. 39, 93–116 (1987)
Burke, J.V., Moré, J.J.: On the identification of active constraints. SIAM J. Numer. Anal. 25, 1197–1211 (1988)
Xiu, N.H., Zhang, J.Z.: Local convergence analysis of projection-type algorithms: a unified approach. J. Optim. Theory Appl. 115, 211–230 (2002)
Tseng, P.: On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. 60, 237–252 (1995)
Fukushima, M.: Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Program. 53, 99–110 (1992)
Bauschke, H.H., Combettes, P.L., Reich, S.: The asymptotic behavior of the composition of two resolvents. Nonlinear Anal. 60, 283–301 (2005)
Ferris, M.C.: Finite termination of the proximal point algorithm. Math. Program. 50, 359–366 (1991)
Burke, J.V., Ferris, M.C.: Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31, 1340–1359 (1993)
Mangasarian, O.L.: Error bounds for nondegenerate monotone linear complementarity problems. Math. Program. 48, 437–445 (1990)
Patriksson, M.: Unified framework of descent algorithms for nonlinear programs and variational inequalities. Ph.D. Thesis, Linköping Institute of Technology (1993)
Xiu, N.H., Zhang, J.Z.: On finite convergence of proximal point algorithms for variational inequalities. J. Math. Anal. Appl. 312, 148–158 (2005)
Hu, Y.H., Song, W.: Weak sharp solutions for variational inequalities in Banach spaces. J. Math. Anal. Appl. 374, 118–132 (2011)
Güler, O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29, 403–419 (1991)
Bauschke, H.H., Burke, J.V., Deutsch, F.R., Hundal, H.S., Vanderwerff, J.D.: A new proximal point iteration that converges weakly but not in norm. Proc. Am. Math. Soc. 133, 1829–1835 (2005)
Bauschke, H.H., Matoušková, E., Reich, S.: Projection and proximal point methods: convergence results and counterexamples. Nonlinear Anal. 56, 715–738 (2004)
Goebel, K., Reich, S.: Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. Marcel Dekker, New York (1984)
Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)
Kopecká, E., Reich, S.: A note on alternating projections in Hilbert space. J. Fixed Point Theory Appl. 12, 41–47 (2012)
Daniilidis, A., Hadjisavvas, N.: Coercivity conditions and variational inequalities. Math. Program. 86, 433–438 (1999)
Rockafellar, R.T.: On the maximality of sums of nonlinear monotone operators. Trans. Am. Math. Soc. 149, 75–88 (1970)
Reich, S.: Nonlinear evolution equations and nonlinear ergodic theorems. Nonlinear Anal. 1, 319–330 (1977)
Reich, S.: Weak convergence theorems for nonexpansive mappings in Banach spaces. J. Math. Anal. Appl. 67, 274–276 (1979)
Takahashi, W., Toyoda, M.: Weak convergence theorems for nonexpansive mappings and monotone mappings. J. Optim. Theory Appl. 118, 417–428 (2003)
Marcotte, P., Zhu, D.L.: Weak sharp solutions of variational inequalities. SIAM J. Optim. 9, 179–189 (1999)
Wu, Z.L., Wu, S.Y.: Weak sharp solutions of variational inequalities in Hilbert spaces. SIAM J. Optim. 14, 1011–1027 (2004)
Zhou, J., Wang, C.: A note on finite termination of iterative algorithms in mathematical programming. Oper. Res. Lett. 36, 715–717 (2008)
Matsushita, S., Xu, L.: Finite convergence of the proximal point algorithm for variational inequality problems. Set-Valued Var. Anal. 21, 297–309 (2013)
Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)
Kamimura, S., Takahashi, W.: Approximating solutions of maximal monotone operators in Hilbert spaces. J. Approx. Theory 106, 226–240 (2000)
Nevanlinna, O., Reich, S.: Strong convergence of contraction semigroups and of iterative methods for accretive operators in Banach spaces. Isr. J. Math. 32, 44–58 (1979)
Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53, 475–504 (2004)
Censor, Y., Gibali, A., Reich, S.: The subgradient extragradient method for solving variational inequalities in Hilbert space. J. Optim. Theory Appl. 148, 318–335 (2011)
Censor, Y., Gibali, A., Reich, S.: Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optim. Methods Softw. 26, 827–845 (2011)
Censor, Y., Gibali, A., Reich, S.: Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space. Optimization 61, 1119–1132 (2012)
Kassay, G., Reich, S., Sabach, S.: Iterative methods for solving systems of variational inequalities in reflexive Banach spaces. SIAM J. Optim. 21, 1319–1344 (2011)
Dunn, J.C.: Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals. SIAM J. Control Optim. 17, 187–211 (1979)
Wu, Z., Wu, S.Y.: Gâteaux differentiability of the dual function of a variational inequality. Eur. J. Oper. Res. 190, 328–344 (2008)
Mangasarian, O.L., Meyer, R.R.: Nonlinear perturbation of linear programs. SIAM J. Control Optim. 17, 745–752 (1979)