A family of operator splitting methods revisited. (English) Zbl 1201.65110
Let \(H\) be a real Hilbert spacee; and \(A,B\) be (multivalued) maximal monotone operators from \(H\) to itself. The variable scaling DPRV algorithm Step 0: \(x^0\in H\), \(\mu_0\in (0,\infty)\), \(k:=0\);
Step 1: \(a^k\in A(x^k), (y^k,b^k)\in B\): \(y^k+\mu_kb^k=x^k-\mu_ka^k\), \(x^k=y^k\) \(\Rightarrow\) stop;
Step 2: \(\gamma_k> 0\), \((x^{k+1},a^{k+1})\in A\): \(x^{k+1}+\mu_ka^{k+1}=x^k+\mu_ka^k-\gamma_k(x^k-y^k)\);
Step 3: \(\tau_k\in [0,1)\), \(\mu_{k+1}\in [(1-\tau_k)\mu_k,(1+\tau_k)\mu_k]\), \(k:=k+1\), go to (Step 1)
for solving the inclusion \(0\in A(x)+B(x)\) is extended to the case when the parameters may vary in a non-monotonical way from iteration to iteration. Sufficient conditions are given so as to get a linear rate of convergence.
Step 1: \(a^k\in A(x^k), (y^k,b^k)\in B\): \(y^k+\mu_kb^k=x^k-\mu_ka^k\), \(x^k=y^k\) \(\Rightarrow\) stop;
Step 2: \(\gamma_k> 0\), \((x^{k+1},a^{k+1})\in A\): \(x^{k+1}+\mu_ka^{k+1}=x^k+\mu_ka^k-\gamma_k(x^k-y^k)\);
Step 3: \(\tau_k\in [0,1)\), \(\mu_{k+1}\in [(1-\tau_k)\mu_k,(1+\tau_k)\mu_k]\), \(k:=k+1\), go to (Step 1)
for solving the inclusion \(0\in A(x)+B(x)\) is extended to the case when the parameters may vary in a non-monotonical way from iteration to iteration. Sufficient conditions are given so as to get a linear rate of convergence.
Reviewer: Mihai Turinici (Iaşi)
MSC:
65K10 | Numerical optimization and variational techniques |
46N10 | Applications of functional analysis in optimization, convex analysis, mathematical programming, economics |
49M30 | Other numerical methods in calculus of variations (MSC2010) |
47J22 | Variational and other types of inclusions |
49J21 | Existence theories for optimal control problems involving relations other than differential equations |
47H05 | Monotone operators and generalizations |
90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Keywords:
splitting; convergence; nonlinear complementarity problem; quadratic minimization; Hilbert space; maximal monotone operators; variable scaling DPRV algorithm; variable scaling DPRV algorithm; inclusionReferences:
[1] | Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 877-898 (1976) · Zbl 0358.90053 |
[2] | Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602 |
[3] | Douglas, J.; Rachford, H. H., On the numerical solution of the heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82, 421-439 (1956) · Zbl 0070.35401 |
[4] | Peaceman, D.; Rachford, H. H., The numerical solution of parabolic and elliptic differential equations, J. Soc. Indust. Appl. Math., 3, 28-41 (1955) · Zbl 0067.35801 |
[5] | Wachspress, E. L.; Habetler, G. J., An alternating direction implicit iteration technique, J. Soc. Indust. Appl. Math., 8, 403-424 (1960) · Zbl 0158.33901 |
[6] | Kellogg, R. B., A nonlinear alternating direction method, Math. Comput., 23, 23-27 (1969) · Zbl 0185.39902 |
[7] | J. Lieutaud, Approximation d’opérateurs par des méthodes de décomposition, Doctoral Thesis, Université de Paris, 1969.; J. Lieutaud, Approximation d’opérateurs par des méthodes de décomposition, Doctoral Thesis, Université de Paris, 1969. |
[8] | Lions, P. L.; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979 (1979) · Zbl 0426.65050 |
[9] | Eckstein, J.; Ferris, M. C., Operator splitting methods for monotone affine variational inequalities with a parallel application to optimal control, INFORMS J. Comput., 10, 218-235 (1998) · Zbl 1034.90531 |
[10] | Glowinski, R.; Le Tallec, P., Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics (1989), SIAM: SIAM Philadelphia, PA · Zbl 0698.73001 |
[11] | B.S. He, A class of new methods for monotone variational inequalities, Report of the Institute of Mathematics, Nanjing University, 1995.; B.S. He, A class of new methods for monotone variational inequalities, Report of the Institute of Mathematics, Nanjing University, 1995. |
[12] | He, B. S., Inexact implicit methods for monotone general variational inequalities, Math. Program., 86, 199-227 (1999) · Zbl 0979.49006 |
[13] | Huang, N. J., A new method for a class of nonlinear variational inequalities with fuzzy mappings, Appl. Math. Lett., 10, 129-133 (1997) · Zbl 0906.49003 |
[14] | He, B. S.; Liao, L. Z.; Wang, S. L., Self-adaptive operator splitting methods for monotone variational inequalities, Numer. Math., 94, 715-737 (2003) · Zbl 1033.65047 |
[15] | Eckstein, J.; Bertsekas, D. P., On the Douglas-Rachford splitting method and the proximal algorithm for maximal monotone operators, Math. Program., 55, 293-318 (1992) · Zbl 0765.90073 |
[16] | Eckstein, J.; Svaiter, B. F., A family of projective splitting methods for the sum of two maximal monotone operators, Math. Program., 111, 173-199 (2008) · Zbl 1134.47048 |
[17] | Lawrence, J.; Spingarn, J. E., On fixed points of non-expansive piecewise isometric mappings, (Proceedings of the London Mathematical Society. Proceedings of the London Mathematical Society, 3rd Series, vol. 55 (1987), Oxford University Press: Oxford University Press Oxford), 605-624 · Zbl 0605.47052 |
[18] | Minty, G. J., Monotone (nonlinear) operators in Hilbert space, Duke Math. J., 29, 341-346 (1962) · Zbl 0111.31202 |
[19] | Han, D., Inexact operator splitting methods with selfadaptive strategy for variational inequality problems, J. Optim. Theory Appl., 132, 227-243 (2007) · Zbl 1149.49010 |
[20] | Li, M.; Bnouhachem, A., A modified inexact operator splitting method for monotone variational inequalities, J. Glob. Optim., 41, 417-426 (2008) · Zbl 1158.65045 |
[21] | Parente, L. A.; Lotito, P. A.; Solodov, M. V., A class of inexact variable metric proximal point algorithms, SIAM J. Optim., 19, 240-260 (2008) · Zbl 1190.90216 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.