The effective implementation of an accelerated method for solving variational inequalities
Abstract
A nonlocally converging algorithm for solving variational inequalities with strongly monotone operator and convex constraints-inequalities has been constructed. The algorithm has a high rate of convergence. The method is based on a combination of the global first-order algorithm that uses an iterative sequence in the space of direct variables with Newton's method of solving the Kuhn-Tucker conditions of variational inequalities in the neighborhood of the solution. The effective implementation of the proposed algorithm has been performed. The computational aspects associated with the two time-consuming sub-tasks of a presented algorithm — the quadratic programming problem and solving a system of nonlinear equations have been considered. The implementation of the method has been tested by solving the variational inequalities with a nonpotential operator. A comparative analysis of the accelerated algorithm and the first order algorithm has been performed. The high convergence of the proposed algorithm has been confirmed by the results of computational experiments.
References
Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity, Volume I. — Springer, 2003. — 728 p.
Facchinei F., Pang J.-S. Finite-Dimensional Variational Inequalities and Complementarity, Volume II. — Springer, 2003. — 702 p.
Xiao B., Harker P.T. A nonsmooth Newton method for variational inequalities, I:Theory // Math.Progr. — 1994. — 65, № 2. — P. 151–194.
Bakushinskiy YA. M., Polyak B. T. O reshenii variatsionnykh neravenstv // Dokl. АN SSSR. — 1974. — 219, № 5, — S. 1038–1041.
Panin V.M., Аleksandrova V.M. Nelokal’nyy kvazin’yutonovskiy metod resheniya vypuklykh variatsionnykh neravenstv // Kibernetika i sistem. analiz. — 1994. — № 6. — S. 78–91.
Fukushima, M. Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems // Math. Progr. — 1992. — 53, № 2. — P. 99–110.
Аleksandrova V.M., SHubenkova I.А. Ob usovershenstvovanii metoda resheniya variatsionnykh neravenstv // Kibernetika i sistemnyy analiz. — 2013. — № 2. — S. 150–156.
Danilin YU.M., SHubenkova I.А. Optimizatsiya i resheniye vypuklykh variatsionnykh neravenstv // Systemni doslidzhennya ta informatsiyni tekhnolohiyi. — 2003. — # 3. — S. 66–74.
Pshenichnyy B.N. Metod linearizatsii. — M.: Nauka, 1983. — 136 s.
Sobolenko L.А. Uskorennyye modifikatsii metoda linearizatsii. — Dep. VINITI 7525. — V.89. — 1989. — 35 s.
Аleksandrova V.M. Uskorennyy metod resheniya variatsionnykh neravenstv // Teoriya optimal’nykh resheniy. — Kiyev: In-t kibernetiki im. V.M. Glushkova NАN Ukrainy, 1995. — S. 8–13.
Gill F., Myurrey K., Rayt M. Prakticheskaya optimizatsiya. — M.: Mir, 1985. — 509 s.
Goldfarb D, Idnani A. A numerically stable dual method for solving strictly convex quadratic problem // Math. Progr. — 1983. — 27, № 1. — P. 1–33.
Fukushima M. A relaxed projection method for variational inequalitities // Math. Progr. — 1986. — 35, № 1. — P. 58–70.
Taji K., Fukushima M., Ibaraki T. A globally convergent Newton method for solving strongly monotone variational inequalities // Math. Progr. — 1993. — 58, № 3. — P. 369–383.
