Algorithms for the split variational inequality problem. (English) Zbl 1239.65041

Censor, Yair; Gibali, Aviv; Reich, Simeon

Numer. Algorithms 59, No. 2, 301-323 (2012).

The authors present a new problem, the split variational inequality problem (SVIP). SVIP is quite general and should enable split minimization between two spaces so that the image of a solution point of one minimization problem, under a given bounded linear operator, is a solution point of another minimization problem. Here two approaches to the solution of the SVIP, are considered. The first approach is to look at the product space \(H_1 \times H_2\) and to transform the SVIP:
Find a point \(x^* \in C\) such that \(\langle f (x^*), x-x^* \rangle \geq0\) for all \(x \in C\) (and given operators \(f: H_1 \rightarrow H_1\) and \(g: H_2 \rightarrow H_2\), where \(H_1\) and \(H_2\) are two Hilbert spaces) and such that the point \(y^* = Ax^* \in Q\) and solves \(\langle g (y^*), y-y^* \rangle \geq0\) for all \(y \in Q\). (\(A: H_1 \rightarrow H_2\) is a bounded linear operator, and \(C\subseteq H_1, Q \subseteq H_2\) are nonempty, closed and convex subsets) into an equivalent constrained variational inequality problem in the product space. A prototypical split inverse problem concerns a model in which there are two spaces \(X\) and \(Y\) and there is given a bounded linear operator \(A: X \rightarrow Y\). Additionally, there are two inverse problems involved, one inverse problem \(IP_1\) formulated in the space \(X\) and another inverse problem \(IP_2\) formulated in the space \(Y\). the split inverse problem is the following:
Find a point \(x^* \in X\) that solves \(IP_1\) such that the point \(y^* = Ax^* \in Y\) solves \(IP_2\).
The algorithm for the constrained variational inequality problem (VIP) is presented. The authors propose their own method for solving the SVIP which does not rely on any product space formulation, and then prove convergence: For \(f= \nabla F\) and \(g = \nabla G\) in the SVIP (\(F:{\mathbb{R}}^n \rightarrow {\mathbb{R}}^n, G: {\mathbb{R}}^m \rightarrow {\mathbb{R}}^m\) are continuously differentiable convex functions on closed and convex subsets \(C \subseteq {\mathbb{R}}^n\) and \(Q \subseteq {\mathbb{R}}^m\)) the split minimization problem:
Find a point \(x^* \in C\) such that \(x^* = \arg \min \{f(x) | x\in C \}\) and such that, the point \(y^* = Ax^*\) is in \(Q\) and solves \(y^* = \arg\min \{g(y)|y \in Q\}\).
Finally the split zeros problem (SZP), newly introduced in this paper, is defined as follows. For given operators \(B_1: H_1 \rightarrow H_1\) and \(B_2: H_2 \rightarrow H_2\) (\(H_1, H_2\) are Hilbert spaces) and a bounded linear operator \(A: H_1 \rightarrow H_2\) the authors formulate SZP as follows: find a point \(x^* \in H_1\) such that \(B_1(x^*) = 0\) and \(B_2(Ax^*) = 0\). (This problem is a special case of the SVIP if \(A\) is a surjective operator.) The authors construct iterative algorithms that solve such problems under reasonable conditions in Hilbert space and show when the unique solution of an SVIP is a solution of an SZP. A similar result concerning the relationship between the (un-split) zero finding problem and the VIP is proposed.

Reviewer: Jan Lovíšek (Bratislava)

MSC:

65K15

Numerical methods for variational inequalities and related problems

Keywords:

Hilbert space; constrained variational inequality problem; inverse strongly monotone operator; iterative method; metric projection; monotone operator; product space; split inverse problem; split variational inequality problem; variational inequality problem

References:

[1]	Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996) · Zbl 0865.47039
[2]	Bauschke, H.H., Combettes, P.L.: A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces. Math. Oper. Res. 26, 248–264 (2001) · Zbl 1082.65058
[3]	Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, Englwood Cliffs (1989) · Zbl 0743.65107
[4]	Browder, F.E.: Fixed point theorems for noncompact mappings in Hilbert space. Proc. Natl. Acad. Sci. USA 53, 1272–1276 (1965) · Zbl 0125.35801
[5]	Byrne, C.L.: Iterative projection onto convex sets using multiple Bregman distances. Inverse Probl. 15, 1295–1313 (1999) · Zbl 0940.65072
[6]	Byrne, C.: Iterative oblique projection onto convex sets and the split feasibility problem. Inverse Probl. 18, 441–453 (2002) · Zbl 0996.65048
[7]	Byrne, C.: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20 103–120 (2004) · Zbl 1051.65067
[8]	Cegielski, A.: Generalized relaxations of nonexpansive operators and convex feasibility problems. Contemp. Math. 513, 111–123 (2010) · Zbl 1217.47111
[9]	Cegielski, A., Censor, Y.: Opial-type theorems and the common fixed point problem. In: Bauschke, H., Burachik, R., Combettes, P., Elser, V., Luke, R., Wolkowicz, H. (eds.) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 155–183. Springer, New York (2011)
[10]	Censor, Y., Altschule, M.D., Powlis, W.D.: On the use of Cimmino’s simultaneous projections method for computing a solution of the inverse problem in radiation therapy treatment planning. Inverse Probl. 4, 607–623 (1988) · Zbl 0653.65049
[11]	Censor, Y., Bortfeld, T., Martin, B., Trofimov, A.: A unified approach for inversion problems in intensity-modulated radiation therapy. Phys. Med. Biol. 51, 2353–2365 (2006)
[12]	Censor, Y., Chen, W., Combettes, P.L., Davidi, R., Herman, G.T.: On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints. Comput. Optim. Appl. (2011, accepted for publication). doi: 10.1007/s10589-011-9401-7 . http://arxiv.org/abs/0912.4367 · Zbl 1244.90155
[13]	Censor, Y., Davidi, R., Herman, G.T.: Perturbation resilience and superiorization of iterative algorithms. Inverse Probl. 26 065008 (17 pp.) (2010) · Zbl 1193.65019
[14]	Censor, Y., Elfving, T.: A multiprojection algorithm using Bregman projections in product space. Numer. Algorithms 8, 221–239 (1994) · Zbl 0828.65065
[15]	Censor, Y., Elfving, T., Kopf, N., Bortfeld, T.: The multiple-sets split feasibility problem and its applications for inverse problems. Inverse Probl. 21, 2071–2084 (2005) · Zbl 1089.65046
[16]	Censor, Y., Gibali, A., Reich, S.: Extensions of Korpelevich’s extragradient method for solving the variational inequality problem in Euclidean space. Optimization (2011, accepted for publication) · Zbl 1260.65056
[17]	Censor, Y., Gibali, A., Reich, S.: The subgradient extragradient method for solving the variational inequality problem in Hilbert space. J. Optim. Theory Appl. 148, 318–335 (2011) · Zbl 1229.58018
[18]	Censor, Y., Gibali, A., Reich, S.: Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optim. Methods Softw. (2011, accepted for publication) · Zbl 1232.58008
[19]	Censor, Y., Gibali, A., Reich, S., Sabach, S.: Common solutions to variational inequalities. Technical Report, 5 April 2011. Revised: July 18, 2011 · Zbl 1296.47060
[20]	Censor, Y., Segal, A.: The split common fixed point problem for directed operators. J. Convex Anal. 16, 587–600 (2009) · Zbl 1189.65111
[21]	Censor, Y., Segal, A.: On the string averaging method for sparse common fixed point problems. Int. Trans. Oper. Res. 16, 481–494 (2009) · Zbl 1226.47070
[22]	Censor, Y., Segal, A.: On string-averaging for sparse problems and on the split common fixed point problem. Contemp. Math. 513, 125–142 (2010) · Zbl 1229.47107
[23]	Censor, Y., Zenios, S. A.: Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, New York (1997) · Zbl 0945.90064
[24]	Combettes, P.L.: Quasi-Fejérian analysis of some optimization algorithms. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 115–152. Elsevier, Amsterdam (2001) · Zbl 0992.65065
[25]	Crombez, G.: A geometrical look at iterative methods for operators with fixed points. Numer. Funct. Anal. Optim. 26, 157–175 (2005) · Zbl 1074.65064
[26]	Crombez, G.: A hierarchical presentation of operators with fixed points on Hilbert spaces. Numer. Funct. Anal. Optim. 27, 259–277 (2006) · Zbl 1100.47044
[27]	Dang, Y., Gao, Y.: The strong convergence of a KM–CQ-like algorithm for a split feasibility problem. Inverse Probl. 27, 015007 (2011) · Zbl 1211.65065
[28]	Goebel, K., Reich, S.: Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. Marcel Dekker, New York (1984) · Zbl 0537.46001
[29]	He, S., Yang, C., Duan, P.: Realization of the hybrid method for Mann iteration. Appl. Math. Comput. 217, 4239–4247 (2010) · Zbl 1207.65065
[30]	Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Ekon. Mat. Metody 12, 747–756 (1976) · Zbl 0342.90044
[31]	López, G., Martín-Márquez, V., Xu, H.K.: Iterative algorithms for the multiple-sets split feasibility problem. In: Censor, Y., Jiang, M., Wang, G. (eds.) Biomedical Mathematics: Promising Directions in Imaging, Therapy Planning and Inverse Problems, pp. 243–279. Medical Physics Publishing, Madison (2010)
[32]	Măruşter, Ş., Popirlan, C.: On the Mann-type iteration and the convex feasibility problem. J. Comput. Appl. Math. 212, 390–396 (2008) · Zbl 1135.65027
[33]	Masad, E., Reich, S.: A note on the multiple-set split convex feasibility problem in Hilbert space. J. Nonlinear Convex Anal. 8, 367–371 (2007) · Zbl 1171.90009
[34]	Moudafi, A.: The split common fixed-point problem for demicontractive mappings. Inverse Probl. 26, 1–6 (2010) · Zbl 1219.90185
[35]	Nadezhkina, N., Takahashi, W.: Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings. J. Optim. Theory Appl. 128, 191–201 (2006) · Zbl 1130.90055
[36]	Opial, Z.: Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Am. Math. Soc. 73, 591–597 (1967) · Zbl 0179.19902
[37]	Pierra, G.: Decomposition through formalization in a product space. Math. Program. 28, 96–115 (1984) · Zbl 0523.49022
[38]	Qu, B., Xiu, N.: A note on the CQ algorithm for the split feasibility problem. Inverse Probl. 21, 1655–1666 (2005) · Zbl 1080.65033
[39]	Rockafellar, R.T.: On the maximality of sums of nonlinear monotone operators. Trans. Am. Math. Soc. 149, 75–88 (1970) · Zbl 0222.47017
[40]	Schöpfer, F., Schuster, T., Louis, A.K.: An iterative regularization method for the solution of the split feasibility problem in Banach spaces. Inverse Probl. 24, 055008 (2008) · Zbl 1153.46308
[41]	Segal, A.: Directed operators for common fixed point problems and convex programming problems. Ph.D. Thesis, University of Haifa (2008)
[42]	Takahashi, W., Toyoda, M.: Weak convergence theorems for nonexpansive mappings and monotone mappings. J. Optim. Theory Appl. 118, 417–428 (2003) · Zbl 1055.47052
[43]	Xu, H.K.: A variable Krasnosel’skii–Mann algorithm and the multiple-set split feasibility problem. Inverse Probl. 22, 2021–2034 (2006) · Zbl 1126.47057
[44]	Xu, H.K.: Iterative methods for the split feasibility problem in infinite-dimensional Hilbert spaces. Inverse Probl. 26, 105018 (2010) · Zbl 1213.65085
[45]	Yamada, I., Ogura, N.: Adaptive projected subgradient method for asymptotic minimization of sequence of nonnegative convex functions. Numer. Funct. Anal. Optim. 25, 593–617 (2005) · Zbl 1156.90428
[46]	Yang, Q.: The relaxed CQ algorithm solving the split feasibility problem. Inverse Probl. 20, 1261–1266 (2004) · Zbl 1066.65047
[47]	Zaknoon, M.: Algorithmic developments for the convex feasibility problem. Ph.D. Thesis, University of Haifa (2003)
[48]	Zhang, W., Han, D., Li, Z.: A self-adaptive projection method for solving the multiple-sets split feasibility problem. Inverse Probl. 25, 115001 (2009) · Zbl 1185.65102
[49]	Zhao, J., Yang, Q.: Several solution methods for the split feasibility problem. Inverse Probl. 21, 1791–1800 (2005) · Zbl 1080.65035