Projection algorithms with dynamic stepsize for constrained composite minimization

Wu, Yujing ¹ ; Shi, Luoyi ² ; Chen, Rudong ²

¹ Tianjin Vocational Institute, Tianjin 300410, P. R. China
² Department of Mathematics, Tianjin Polytechnic University, Tianjin 300387, P. R. China

Journal of nonlinear sciences and its applications, Tome 11 (2018) no. 7, p. 927-936.

Résumé

The problem of minimizing the sum of a large number of component functions over the intersection of a finite family of closed convex subsets of a Hilbert space is researched in the present paper. In the case of the number of the component functions is huge, the incremental projection methods are frequently used. Recently, we have proposed a new incremental gradient projection algorithm for this optimization problem. The new algorithm is parameterized by a single nonnegative constant $\mu$. And the algorithm is proved to converge to an optimal solution if the dimensional of the Hilbert space is finite the step size is diminishing (such as $\alpha_n=\mathcal{O}(1/n)$). In this paper, the algorithm is modified by employing the constant and the dynamic stepsize, and the corresponding convergence properties are analyzed.

Détail

DOI : 10.22436/jnsa.011.07.05

Classification : 47H10, 54H25
Keywords: Composite minimization, projection algorithm, dynamic stepsize

Bibliographie

[1] Bauschke, H. H.; J. M. Borwein On projection algorithms for solving convex feasibility problems, SIAM Rev., Volume 38 (1996), pp. 367-426 | DOI

[2] Bertsekas, D. P. Nonlinear Programming, Athena Scientific, Belmont, MA, 1995

[3] Bertsekas, D. P. Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey, MIT Press, Cambridge, 2011

[4] Bertsekas, D. P. Incremental aggregated proximal and augmented Lagrangian algorithms, arXiv preprint, Volume 2015 (2015), pp. 1-38

[5] Bertsekas, D. P.; Tsitsikls, J. N. Neuro-Dynamic Programming, Athena Scientific, Belmont, MA, 1996

[6] Combettes, P. L. Hilbertian convex feasibility problem: convergence of projection methods, Appl. Math. Optim., Volume 35 (1997), pp. 311-330 | Zbl | DOI

[7] Geobel, K.; Kirk, W. A. Topics in Metric Fixed Point Theory, Cambridge University Press, Cambridge, 1990 | DOI

[8] Geobel, K.; Reich, S. Uniform convexity, hyperbolic geometry, and nonexpansive mappings, Marcel Dekker, Inc., New York, 1984

[9] Goffin, J.-L.; K. C. Kiwiel Convergence of a simple subgradient level method, Math. Program., Volume 85 (1999), pp. 207-211 | DOI | Zbl

[10] Hastie, T.; Tibshirani, R.; Friedman, J. The elements of statistical learning, Data mining, inference, and prediction, Second edition, Springer, New York, 2009 | DOI

[11] Kiwiel, K. C.; Lindberg, P. O. Parallel subgradient methods for convex optimization, Inherently parallel algorithms in feasibility and optimization and their applications (Haifa, 2000), 335–344, Stud. Comput. Math., North-Holland, Amsterdam, 2001 | DOI

[12] K. C. Krzysztof Convergence of approximate and incremental subgradient methods for convex optimization, SIAM J. Optim., Volume 14 (2004), pp. 807-840 | DOI | Zbl

[13] Luo, Z.-Q. On the convergence of the LMS algorithm with adaptive learning rate for linear feedforward networks, Neural Computation, Volume 3 (1991), pp. 226-245 | DOI

[14] Nedić, A.; Bertsekas, D. P. Incremental subgradient methods for nondifferentiable optimization, SIAM J. Option, Volume 12 (2001), pp. 109-138 | DOI

[15] Nedić, A.; Bertsekas, D. P.; Borkar, V. S. Distributed Asynchronous Incremental Subgradient Methods , Stud. Comput. Math., Volume 8 (2001), pp. 381-407 | Zbl | DOI

[16] B. T. Polyak Minimization of unsmooth functionals, USSR Comput. Math. & Math. Phys., Volume 9 (1969), pp. 509-521 | Zbl | DOI

[17] B. T. Polyak Introduction to Optimization, Translated from the Russian. With a foreword by Dimitri P. Bertsekas. Translations Series in Mathematics and Engineering, Optimization Software, Inc., Publications Division, New York, 1987

[18] Schöpfer, F.; Schuster, T.; Louis, A. K. An iterative regularization method for the solution of the split feasibility problem in Banach spaces, Inverse Problems, Volume 2008 (2008), pp. 1-20 | DOI | Zbl

[19] Shi, L. Y.; Ansari, Q. H.; Wen, C. F.; Yao, J. C. A new algorithm for constrained composite minimization, J. Nonlinear Var. Anal., Volume 1 (2017), pp. 253-264

[20] Sra, S.; Nowozin, S.; Wright, S. J. Optimization for machine learning , MIT Press, Cambridge, Massachusetts, 2011

[21] Xu, H.-K. Averaged mappings and the gradient-projection algorithm, J. Optim. Theory Appl., Volume 150 (2011), pp. 360-378 | DOI

[22] Yang, X.; H.-K. Xu Projection algorithms for composite minimization, Carpathian J. Math., Volume 33 (2017), pp. 389-397

[23] Zhao, X.; Luh, P. B.; Wang, J. Surrogate gradient algorithm for Lagrangian relaxation, J. Optim. Theory Appl., Volume 100 (1999), pp. 699-712 | Zbl | DOI