Convergence analysis of iterative methods for nonsmooth convex optimization over fixed point sets of quasi-nonexpansive mappings. (English) Zbl 1351.65035
The paper focuses on a networked system consisting of a finite number of participating users and considers the problem of minimizing the sum of their nondifferentiable, convex functions over the intersection of their fixed point constraint sets of quasi-nonexpansive mappings in a real Hilbert space. The author proposes a parallel subgradient method for solving the problem and describes its convergence properties for a constant step size and for a diminishing step size and the rates of convergence under certain situations. Another incremental subgradient method is proposed to solve the problem and its convergence properties for a constant step size and for a diminishing step size and the rates of convergence under certain situations are described. The two proposed methods are compared numerically with an existing method for nonsmooth convex optimization problem over the intersection of sublevel sets of convex functions.
Reviewer: Hang Lau (Montréal)
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C25 | Convex programming |
| 90C90 | Applications of mathematical programming |
| 90C35 | Programming involving graphs or networks |
| 47H09 | Contraction-type mappings, nonexpansive mappings, \(A\)-proper mappings, etc. |
Keywords:
fixed point; incremental subgradient method; nonsmooth convex optimization; parallel subgradient method; quasi-nonexpansive mapping; networked system; quasi-nonexpansive mappings; Hilbert space; convergenceSoftware:
UNLocBoXReferences:
| [1] | Bauschke, H.H., Chen, J.: A projection method for approximating fixed points of quasi nonexpansive mappings without the usual demiclosedness condition. J. Nonlinear Convex Anal. 15, 129-135 (2014) · Zbl 1311.47085 |
| [2] | Bauschke, H.H., Combettes, P.L.: A weak-to-strong convergence principle for 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 |
| [3] | Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011) · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7 |
| [4] | Bertsekas, D.P., Nedić, A., Ozdaglar, A.E.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003) · Zbl 1140.90001 |
| [5] | Blatt, D., Hero, A.O., Gauchman, H.: A convergent incremental gradient method with a constant step size. SIAM J. Optim. 18, 29-51 (2007) · Zbl 1154.90015 · doi:10.1137/040615961 |
| [6] | Combettes, P.L.: A block-iterative surrogate constraint splitting method for quadratic signal recovery. IEEE Trans. Signal Process. 51, 1771-1782 (2003) · Zbl 1369.94121 · doi:10.1109/TSP.2003.812846 |
| [7] | Combettes, P.L.: Iterative construction of the resolvent of a sum of maximal monotone operators. J. Convex Anal. 16, 727-748 (2009) · Zbl 1193.47067 |
| [8] | Combettes, P.L., Pesquet, J.C.: A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Top. Signal Process. 1, 564-574 (2007) · doi:10.1109/JSTSP.2007.910264 |
| [9] | Combettes, P.L., Pesquet, J.C.: A proximal decomposition method for solving convex variational inverse problems. Inverse Probl. 24, 065014 (2008) · Zbl 1154.49025 · doi:10.1088/0266-5611/24/6/065014 |
| [10] | Combettes, PL; Pesquet, JC; Bauschke, HH (ed.); Burachik, RS (ed.); Combettes, PL (ed.); Elser, V. (ed.); Luke, DR (ed.); Wolkowicz, H. (ed.), Proximal splitting methods in signal processing, 185-212 (2011), New York · Zbl 1242.90160 · doi:10.1007/978-1-4419-9569-8_10 |
| [11] | Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachfold splitting method and proximal point algorithm for maximal monotone operators. Math. Program. 55, 293-318 (1992) · Zbl 0765.90073 · doi:10.1007/BF01581204 |
| [12] | Goebel, K., Kirk, W.A.: Topics in Metric Fixed Point Theory. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (1990) · Zbl 0708.47031 · doi:10.1017/CBO9780511526152 |
| [13] | Helou Neto, E.S., De Pierro, A.R.: Incremental subgradients for constrained convex optimization: a unified framework and new methods. SIAM J. Optim. 20, 1547-1572 (2009) · Zbl 1207.65082 · doi:10.1137/070711712 |
| [14] | Iiduka, H.: Fixed point optimization algorithms for distributed optimization in networked systems. SIAM J. Optim. 23, 1-26 (2013) · Zbl 1266.49067 · doi:10.1137/120866877 |
| [15] | Iiduka, H.: Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping. Math. Program. 149, 131-165 (2015) · Zbl 1338.90301 · doi:10.1007/s10107-013-0741-1 |
| [16] | Iiduka, H.: Convergence analysis of iterative methods for nonsmooth convex optimization over fixed point sets of quasi-nonexpansive mappings. arXiv:1510.06148 (2015) · Zbl 1338.90080 |
| [17] | Iiduka, H., Hishinuma, K.: Acceleration method combining broadcast and incremental distributed optimization algorithms. SIAM J. Optim. 24, 1840-1863 (2014) · Zbl 1317.49044 · doi:10.1137/130939560 |
| [18] | Iiduka, H., Yamada, I.: A use of conjugate gradient direction for the convex optimization problem over the fixed point set of a nonexpansive mapping. SIAM J. Optim. 19, 1881-1893 (2009) · Zbl 1176.47064 · doi:10.1137/070702497 |
| [19] | Johansson, B., Rabi, M., Johansson, M.: A randomized incremental subgradient method for distributed optimization in networked systems. SIAM J. Optim. 20, 1157-1170 (2009) · Zbl 1201.65100 · doi:10.1137/08073038X |
| [20] | Kiwiel, K.C.: Convergence of approximate and incremental subgradient methods for convex optimization. SIAM J. Optim. 14, 807-840 (2004) · Zbl 1063.90039 · doi:10.1137/S1052623400376366 |
| [21] | Lee, S., Nedić, A.: Distributed random projection algorithm for convex optimization. IEEE J. Sel. Top. Signal Process. 7, 221-229 (2013) · doi:10.1109/JSTSP.2013.2247023 |
| [22] | 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 · doi:10.1137/0716071 |
| [23] | Lobel, I., Ozdaglar, A., Feijer, D.: Distributed multi-agent optimization with state-dependent communication. Math. Program. 129, 255-284 (2011) · Zbl 1229.90201 · doi:10.1007/s10107-011-0467-x |
| [24] | Maingé, P.E.: The viscosity approximation process for quasi-nonexpansive mappings in Hilbert spaces. Comput. Math. Appl. 59, 74-79 (2010) · Zbl 1189.49011 · doi:10.1016/j.camwa.2009.09.003 |
| [25] | Nedić, A.: Random algorithms for convex minimization problems. Math. Program. 129, 225-253 (2011) · Zbl 1229.90128 · doi:10.1007/s10107-011-0468-9 |
| [26] | Nedić, A., Bertsekas, D.P.: Incremental subgradient methods for nondifferentiable optimization. SIAM J. Optim. 12, 109-138 (2001) · Zbl 0991.90099 · doi:10.1137/S1052623499362111 |
| [27] | Nedić, A., Olshevsky, A., Ozdaglar, A., Tsitsiklis, J.N.: On distributed averaging algorithms and quantization effects. IEEE Trans. Autom. Control 54, 2506-2517 (2009) · Zbl 1367.93405 · doi:10.1109/TAC.2009.2031203 |
| [28] | Nedić, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Trans. Autom. Control 54, 48-61 (2009) · Zbl 1175.90415 · doi:10.1109/TAC.2008.2009515 |
| [29] | Nedić, A., Ozdaglar, A.: Cooperative distributed multi-agent optimization. In: Convex Optimization in Signal Processing and Communications, pp. 340-386 (2010) · Zbl 1241.90100 |
| [30] | Opial, Z.: Weak convergence of the sequence of successive approximation for nonexpansive mappings. Bull. Am. Math. Soc. 73, 591-597 (1967) · Zbl 0179.19902 · doi:10.1090/S0002-9904-1967-11761-0 |
| [31] | Pesquet, J.C., Pustelnik, N.: A parallel inertial proximal optimization method. Pac. J. Optim. 8, 273-306 (2012) · Zbl 1259.47080 |
| [32] | Pesquet, J.C., Repetti, A.: A class of randomized primal-dual algorithms for distributed optimization. J. Nonlinear Convex Anal. (to appear) · Zbl 1336.65113 |
| [33] | Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173 |
| [34] | Solodov, M.V., Zavriev, S.K.: Error stability properties of generalized gradient-type algorithms. J. Optim. Theory Appl. 98, 663-680 (1998) · Zbl 0913.90245 · doi:10.1023/A:1022680114518 |
| [35] | Vasin, V.V., Ageev, A.L.: Ill-Posed Problems with A Priori Information. V.S.P. Intl Science, Utrecht (1995) · Zbl 0840.65048 · doi:10.1515/9783110900118 |
| [36] | Wang, M., Bertsekas, D.P.: Incremental constraint projection-proximal methods for nonsmooth convex optimization. SIAM J. Optim. (to appear) · Zbl 1063.90039 |
| [37] | Yamada, I.; Butnariu, D. (ed.); Censor, Y. (ed.); Reich, S. (ed.), The hybrid steepest descent method for the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings, 473-504 (2001), Amsterdam · Zbl 1013.49005 · doi:10.1016/S1570-579X(01)80028-8 |
| [38] | Yamada, I.; Yukawa, M.; Yamagishi, M.; Bauschke, HH (ed.); Burachik, RS (ed.); Combettes, PL (ed.); Elser, V. (ed.); Luke, DR (ed.); Wolkowicz, H. (ed.), Minimizing the Moreau envelope of nonsmooth convex functions over the fixed point set of certain quasi-nonexpansive mappings, 345-390 (2011), New York · Zbl 1263.47088 · doi:10.1007/978-1-4419-9569-8_17 |
| [39] | Zeidler, E.: Nonlinear Functional Analysis ans Its Applications II/B. Nonlinear Monotone Operators. Springer, New York (1985) · Zbl 0583.47051 · doi:10.1007/978-1-4612-5020-3 |
| [40] | Zenios, S., Censor, Y.: Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press on Demand, New York (1998) · Zbl 0945.90064 |
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.
