Convergence of distributed approximate subgradient method for minimizing convex function with convex functional constraints

Jedsadapong Pioon; Narin Petrot; Nimit Nimana; Jedsadapong Pioon; Narin Petrot; Nimit Nimana

doi:10.3934/math.2024934

AIMS Mathematics

2024, Volume 9, Issue 7: 19154-19175. doi: 10.3934/math.2024934

Previous Article Next Article

Research article

Convergence of distributed approximate subgradient method for minimizing convex function with convex functional constraints

1.
Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand
2.
Department of Mathematics, Faculty of Science, Naresuan University, Phitsanulok 65000, Thailand
3.
Center of Excellence in Nonlinear Analysis and Optimization, Faculty of Science, Naresuan University, Phitsanulok 65000, Thailand

Received: 12 April 2024 Revised: 20 May 2024 Accepted: 27 May 2024 Published: 07 June 2024
MSC : 65K05, 65K10, 90C25

In this paper, we investigate the distributed approximate subgradient-type method for minimizing a sum of differentiable and non-differentiable convex functions subject to nondifferentiable convex functional constraints in a Euclidean space. We establish the convergence of the sequence generated by our method to an optimal solution of the problem under consideration. Moreover, we derive a convergence rate of order $ \mathcal{O}(N^{1-a}) $ for the objective function values, where $ a\in (0.5, 1) $. Finally, we provide a numerical example illustrating the effectiveness of the proposed method.
- approximate subgradient,
- subgradient method,
- convex,
- convergence
Citation: Jedsadapong Pioon, Narin Petrot, Nimit Nimana. Convergence of distributed approximate subgradient method for minimizing convex function with convex functional constraints[J]. AIMS Mathematics, 2024, 9(7): 19154-19175. doi: 10.3934/math.2024934

Related Papers:

Abstract

In this paper, we investigate the distributed approximate subgradient-type method for minimizing a sum of differentiable and non-differentiable convex functions subject to nondifferentiable convex functional constraints in a Euclidean space. We establish the convergence of the sequence generated by our method to an optimal solution of the problem under consideration. Moreover, we derive a convergence rate of order $ \mathcal{O}(N^{1-a}) $ for the objective function values, where $ a\in (0.5, 1) $. Finally, we provide a numerical example illustrating the effectiveness of the proposed method.

References

[1]	M. A. T. Figueiredo, R. D. Nowak, An EM algorithm for wavelet-based image restoration, IEEE T. Image Process., 12 (2003), 906–916. http://dx.doi.org/10.1109/TIP.2003.814255 doi: 10.1109/TIP.2003.814255
[2]	M. A. T. Figueiredo, J. M. Bioucas-Dias, R. D. Nowak, Majorization-minimization algorithms for wavelet-based image restoration, IEEE T. Image Process., 16 (2007), 2980–2991. http://dx.doi.org/10.1109/TIP.2007.909318 doi: 10.1109/TIP.2007.909318
[3]	A. Beck, M. Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE T. Image Process., 18 (2009), 2419–2434. http://dx.doi.org/10.1109/TIP.2009.2028250 doi: 10.1109/TIP.2009.2028250
[4]	A. Beck, M. Teboulle, 2-Gradient-based algorithms with applications to signal-recovery problems, Cambridge: Cambridge University Press, 2009, 42–88. https://doi.org/10.1017/CBO9780511804458.003
[5]	P. L. Combettes, V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Sim., 4 (2005), 1168–1200. https://doi.org/10.1137/050626090 doi: 10.1137/050626090
[6]	I. Necoara, General convergence analysis of stochastic first-order methods for composite optimization, J. Optim. Theory Appl., 189 (2021), 66–95. https://doi.org/10.1007/s10957-021-01821-2 doi: 10.1007/s10957-021-01821-2
[7]	Y. Nesterov, Gradient methods for minimizing composite functions, Math. Program., 140 (2013), 125–161. https://doi.org/10.1007/s10107-012-0629-5 doi: 10.1007/s10107-012-0629-5
[8]	V. N. Vapnik, Statistical learning theory, New York: John Wiley & Sons, 1998.
[9]	D. P. Bertsekas, Convex optimization algorithms, Belmont: Athena Scientific, 2015.
[10]	A. Nedić, I. Necoara, Random minibatch subgradient algorithms for convex problems with functional constraints, Appl. Math. Optim., 80 (2019), 801–833. https://doi.org/10.1007/s00245-019-09609-7 doi: 10.1007/s00245-019-09609-7
[11]	D. P. Bertsekas, Nonlinear programming, J. Oper. Res. Soc., 48 (1997), 334. https://doi.org/10.1057/palgrave.jors.2600425
[12]	A. Nedić, D. P. Bertsekas, The effect of deterministic noise in subgradient methods, Math. Program., 125 (2010), 75–99. https://doi.org/10.1007/s10107-008-0262-5 doi: 10.1007/s10107-008-0262-5
[13]	S. Bonettini, A. Benfenati, V. Ruggiero, Scaling techniques for $\epsilon$-Subgradient methods, SIAM J. Optimiz., 26 (2016), 1741–1772. https://doi.org/10.1137/14097642X doi: 10.1137/14097642X
[14]	E. S. Helou, L. E. A. Simões, $\epsilon$-subgradient algorithms for bilevel convex optimization, Inverse Probl., 33 (2017), 055020. https://doi.org/10.1088/1361-6420/aa6136 doi: 10.1088/1361-6420/aa6136
[15]	R. D. Millán, M. P. Machado, Inexact proximal $\epsilon$-subgradient methods for composite convex optimization problems, J. Global Optim., 75 (2019), 1029–1060. https://doi.org/10.1007/s10898-019-00808-8 doi: 10.1007/s10898-019-00808-8
[16]	Y. I. Alber, A. N. Iusem, M. V. Solodov, On the projected subgradient method for nonsmooth convex optimization in a Hilbert space, Math. Program., 81 (1998), 23–35. https://doi.org/10.1007/BF01584842 doi: 10.1007/BF01584842
[17]	K. C. Kiwiel, Convergence of approximate and incremental subgradient methods for convex optimization, SIAM J. Optimiz., 14 (2004), 807–840. https://doi.org/10.1137/S1052623400376366 doi: 10.1137/S1052623400376366
[18]	R. S. Burachik, J. E. Martínez-Legaz, M. Rezaie, M. Théra, An additive subfamily of enlargements of a maximally monotone operator, Set-Valued Var. Anal., 23 (2015), 643–665. https://doi.org/10.1007/s11228-015-0340-9 doi: 10.1007/s11228-015-0340-9
[19]	X. L. Guo, C. J. Zhao, Z. W. Li, On generalized $\epsilon$-subdifferential and radial epiderivative of set-valued mappings, Optim. Lett., 8 (2014), 1707–1720. https://doi.org/10.1007/s11590-013-0691-9 doi: 10.1007/s11590-013-0691-9
[20]	A. Simonetto, H. Jamali-Rad, Primal recovery from consensus-based dual decomposition for distributed convex optimization, J. Optim. Theory Appl., 168 (2016), 172–197. https://doi.org/10.1007/s10957-015-0758-0 doi: 10.1007/s10957-015-0758-0
[21]	M. V. Solodov, B. F. Svaiter, A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Var. Anal., 7 (1999), 323–345. https://doi.org/10.1023/A:1008777829180 doi: 10.1023/A:1008777829180
[22]	A. Beck, First-ordered methods in optimization, Philadelphia: SIAM, 2017. https://doi.org/10.1137/1.9781611974997
[23]	H. H. Bauschke, P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, New York: Springer, 2017. https://doi.org/10.1007/978-3-319-48311-5
[24]	C. Zalinescu, Convex analysis in general vector spaces, Singapore: World Scientific, 2002. https://doi.org/10.1142/5021
[25]	A. Nedić, Random algorithms for convex minimization problems, Math. Program., 129 (2011), 225–273. https://doi.org/10.1007/s10107-011-0468-9 doi: 10.1007/s10107-011-0468-9
[26]	B. T. Polyak, Introduction to optimization, New York: Optimization Software, 1987.

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)