On the finite convergence of a projected cutter method. (English) Zbl 1353.90108
A mapping \(T\) from a real Hilbert space into itself is said to be a cutter if the set \(\operatorname{Fix}T\) of its fixed points is nonempty and for every \(x\in X\) and \(y\in \operatorname{Fix}T\) one has \(\| Tx-y\| ^{2}+\| x-Tx\| ^{2}\leq \| x-y\| ^{2}\). Assuming that the set \(C\subseteq X\) intersects the interior of \(\operatorname{Fix}T\), a finitely convergent iterative algorithm for finding an element in \(C\cap \operatorname{Fix}T\) is proposed. This algorithm involves a quasi projector of \(C,\) that is, a mapping \(Q:X\to X\) such that \(\operatorname{ran}Q=\operatorname{Fix}Q=C\) and \(\| Qx-c\|\leq \| x-c\|\) for every \(x\in X\) and \(c\in C\). When \(T\) is the resolvent of a maximally monotone operator \(A\), the algorithm finitely converges to an element of \(C\cap A^{-1}0\). Several examples are provided to show that the convergence theorems do not hold true without the assumptions their statements contain on the parameters defining the algorithm.
Reviewer: Juan-Enrique Martínez-Legaz (Barcelona)
MSC:
| 90C25 | Convex programming |
| 47H04 | Set-valued operators |
| 47H05 | Monotone operators and generalizations |
| 47H09 | Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc. |
| 65K10 | Numerical optimization and variational techniques |
References:
| [1] | Polyak, T.: Random algorithms for solving convex inequalities. In: Butnariu, D., Censor, Y., Reich, S. (eds.) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 409-422. Elsevier, Amsterdam (2001) · Zbl 0997.90053 |
| [2] | Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces. Lecture Notes in Mathematics, vol. 2057. Springer, Berlin (2012) · Zbl 1256.47043 |
| [3] | Censor, Y., Chen, W., Pajoohesh, H.: Finite convergence of a subgradient projection method with expanding controls. Appl. Math. Optim. 64, 273-285 (2011) · Zbl 1254.90162 · doi:10.1007/s00245-011-9139-8 |
| [4] | Crombez, G.: Finding common fixed points of a class of paracontractions. Acta Math. Hung. 103, 233-241 (2004) · Zbl 1065.47055 · doi:10.1023/B:AMHU.0000028410.94541.fb |
| [5] | Censor, Y., Zenios, A.: Parallel Optimization, Oxford University Press, New York (1997) · Zbl 0945.90064 |
| [6] | Polyak, T.: Introduction to Optimization. Optimization Software, New York (1987) · Zbl 0625.62093 |
| [7] | Censor, Y., Lent, A.: Cyclic subgradient projections. Math. Program. 24, 233-235 (1982) · Zbl 0491.90077 · doi:10.1007/BF01585107 |
| [8] | Censor, Y., Segal, A.: Sparse string-averaging and split common fixed points. In: Leizarowitz, A., Mordukhovich, B.S., Shafrir, I., Zaslavski, A.J. (eds) Nonlinear Analysis and Optimization. I. Contemporary Mathematics, vol. 513, pp. 125-142. AMS, Haifa (2010) · Zbl 1229.47107 |
| [9] | Combettes, L.: The foundations of set theoretic estimation. Proc. IEEE 81, 182-208 (1993) · doi:10.1109/5.214546 |
| [10] | Combettes, L.: Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections. IEEE Trans. Image Process. 6, 493-506 (1997) · doi:10.1109/83.563316 |
| [11] | Combettes, P.L., Luo, J.: An adaptive level set method for nondifferentiable constrained image recovery. IEEE Trans. Image Process. 11, 1295-1304 (2002) · doi:10.1109/TIP.2002.804527 |
| [12] | Polyak, T.: Minimization of unsmooth functionals, USSR Comput. Math. Math. Phys. 9, 14-29 (1969) (The original version appeared in Akademija Nauk SSSR. Žurnal Vyčislitel’ noĭ Matematiki i Matematičeskoĭ Fiziki 9 (1969), 509-521.) · Zbl 0229.65056 |
| [13] | Slavakis, K., Yamada, I.: The adaptive projected subgradient method constrained by families of quasi-nonexpansive mappings and its application to online learning. SIAM J. Optim. 23, 126-152 (2013) · Zbl 1266.47113 · doi:10.1137/100807004 |
| [14] | Yamada, I., Ogura, N.: Adaptive projected subgradient method for asymptotic minimization of sequence of nonnegative convex functions. Numer. Funct. Anal. Optim. 25, 593-617 (2004) · Zbl 1156.90428 · doi:10.1081/NFA-200045806 |
| [15] | Yamada, I., Ogura, N.: Hybrid steepest descent method for variational inequality problem over the fixed point set of certain quasi-nonexpansive mappings. Numer. Funct. Anal. Optim. 25, 619-655 (2004) · Zbl 1095.47049 · doi:10.1081/NFA-200045815 |
| [16] | Yamada, I., Slavakis, K., Yamada, K.: An efficient robust adaptive filtering algorithm based on parallel subgradient projection techniques. IEEE Trans. Signal Process. 50, 1091-1101 (2002) · doi:10.1109/78.995065 |
| [17] | Yamagishi, M., Yamada, I.: A deep monotone approximation operator based on the bestquadratic lower bound of convex functions. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E91-A, 1858-1866 (2008) · Zbl 0865.47039 |
| [18] | Bauschke, H.H., Borwein, M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367-426 (1996) · Zbl 0865.47039 · doi:10.1137/S0036144593251710 |
| [19] | Bauschke, H.H., Combettes, P.L.: A weak-to-strong convergence principlefor Fejér-monotone methods in Hilbert space. Math. Oper. Res. 26, 248-264 (2001) · Zbl 1082.65058 · doi:10.1287/moor.26.2.248.10558 |
| [20] | Bauschke, H.H., Wang, C., Wang, X., Xu, J.: On subgradient projectors. http://arxiv.org/abs/1403.7135v1 (2014) · Zbl 1316.47043 |
| [21] | Pauwels, B.: Subgradient projection operators. http://arxiv.org/abs/1403.7237v1 (2014) · Zbl 1095.47049 |
| [22] | Bauschke, H.H., Combettes, L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011) · Zbl 1218.47001 |
| [23] | Bauschke, H.H.: Projection Algorithms and Monotone Operators. PhD thesis, Simon Fraser University, Burnaby, BC, Canada (1996) |
| [24] | Bauschke, H.H., Kruk, G.: Reflection-projection method for convex feasibility problems with an obtuse cone. J. Optim. Theory Appl. 120, 503-531 (2004) · Zbl 1136.90432 · doi:10.1023/B:JOTA.0000025708.31430.22 |
| [25] | Raik, E.: A class of iterative methods with Fejér-monotone sequences, Eesti NSV Teaduste Akadeemia Toimetised. Füüsika-Matemaatika 18, 22-26 (1969) · Zbl 0181.16803 |
| [26] | Rockafellar, T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877-898 (1976) · Zbl 0358.90053 · doi:10.1137/0314056 |
| [27] | Fukushima, M.: A finite convergent algorithm for convex inequalities. IEEE Trans. Autom. Control 27, 1126-1127 (1982) · Zbl 0495.49022 · doi:10.1109/TAC.1982.1103081 |
| [28] | De Pierro, A.R., Iusem, A.N.: A finitely convergent “row-action” method for the convex feasibility problem. Appl. Math. Optim. 17, 225-235 (1988) · Zbl 0655.65085 · doi:10.1007/BF01448368 |
| [29] | Iusem, A.N., Moledo, L.: A finitely convergent method of simultaneous subgradient projections for the convex feasibility problem. Matemática Aplicada e Computacional 5, 169-184 (1986) · Zbl 0625.90079 |
| [30] | Iusem, A.N., Moledo, L.: On finitely convergent iterative methods for the convexfeasibility problem. Boletim da Sociedade Brasileira de Matemática 18, 11-18 (1987) · Zbl 0742.65045 · doi:10.1007/BF02584829 |
| [31] | Pang, J.: Finitely convergent algorithm for nonconvex inequality problems. http://arxiv.org/abs/1405.7280v1 (2014) |
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.
