October 2017, 13(4): 1841-1857. doi: 10.3934/jimo.2017021

Incremental gradient-free method for nonsmooth distributed optimization

1. 

School of Mathematical Sciences, Chongqing Normal University, Chongqing, 400047, China

2. 

Australasian Joint Research Center for Building Information Modelling, School of Built Environment, Curtin University, Bentley, WA, 6102, Australia

3. 

Department of Naval Architecture and Ocean Engineering, Pusan National University, Busan, Korea

Received  March 2015 Revised  August 2016 Published  December 2016

Fund Project: This research was partially supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) through GCRC-SOP (No. 2011-0030013), the Natural Science Foundation of China (11501070,11401064,11471062 and 61473326), by the Natural Science Foundation Projection of Chongqing (cstc2015jcyjA00011, cstc2013jjB00001 and cstc2013jcyjA00029), by the Chongqing Municipal Education Commission under Grant KJ1500301 and KJ1500302, and by the Chongqing Normal University Research Foundation 15XLB005

In this paper we consider the minimization of the sum of local convex component functions distributed over a multi-agent network. We first extend the Nesterov's random gradient-free method to the incremental setting. Then we propose the incremental gradient-free methods, including a cyclic order and a randomized order in the selection of component function. We provide the convergence and iteration complexity analysis of the proposed methods under some suitable stepsize rules. To illustrate our proposed methods, extensive numerical results on a distributed $l_1$-regression problem are presented. Compared with existing incremental subgradient-based methods, our methods only require the evaluation of the function values rather than subgradients, which may be preferred by practical engineers.

Citation: Jueyou Li, Guoquan Li, Zhiyou Wu, Changzhi Wu, Xiangyu Wang, Jae-Myung Lee, Kwang-Hyo Jung. Incremental gradient-free method for nonsmooth distributed optimization. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021
References:
[1]

A. M. BagirovM. Ghosh and D. Webb, A derivative-free method for linearly constrained nonsmooth optimization, J. Ind. Manag. Optim., 2 (2006), 319-338. doi: 10.3934/jimo.2006.2.319.

[2]

D. P. Bertsekas, Stochastic optimization problems with nondifferentiable cost functionals, J. Optim. Theory Appl., 12 (1973), 218-231. doi: 10.1007/BF00934819.

[3] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, Belmont, MA, 1989.
[4] D. P. BertsekasA. Nedić and E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 2003.
[5]

D. P. Bertsekas, Incremental proximal methods for large scale convex optimization, Math. Program. B., 129 (2011), 163-195. doi: 10.1007/s10107-011-0472-0.

[6] A. R. ConnK. Scheinberg and L. N. Vicente, Introduction to Derivative-Free Optimization, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718768.
[7]

J. C. DuchiA. Agarwal and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Trans. Autom. Control., 57 (2012), 592-606. doi: 10.1109/TAC.2011.2161027.

[8]

J. C. DuchiP. L. Bartlet and M. J. Wainwrighr, Randomized smoothing for stochastic optimization, SIAM J. Optim., 22 (2012), 674-701. doi: 10.1137/110831659.

[9]

X. X. HuangX. Q. Yang and K. L. Teo, A smoothing scheme for optimization problems with Max-Min constraints, J. Ind. Manag. Optim., 3 (2007), 209-222. doi: 10.3934/jimo.2007.3.209.

[10] J. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms Ⅰ, Springer, Berlin, 1996. doi: 10.1007/978-3-662-02796-7.
[11]

X. ZhangC. WuJ. LiX. WangZ. YangJ. M. Lee and K. H. Jung, Binary artificial algae algorithm for multidimensional knapsack problems, Applied Soft Computing, 43 (2016), 583-595. doi: 10.1016/j.asoc.2016.02.027.

[12]

B. JohanssonM. Rabi and M. Johansson, A randomized incremental subgradient method for distributed optimization in networked systems, SIAM J. Optim., 20 (2009), 1157-1170. doi: 10.1137/08073038X.

[13]

K. C. Kiwiel, Convergence of approximate and incremental subgradient methods for convex optimization, SIAM J. Optim., 14 (2004), 807-840. doi: 10.1137/S1052623400376366.

[14]

J. Y. LiC. Z. WuZ. Y. Wu and Q. Long, Gradient-free method for nonsmooth distributed optimization, J. Glob. Optim., 61 (2015), 325-340. doi: 10.1007/s10898-014-0174-2.

[15]

J. Y. LiC. Z. WuZ. Y. WuQ. Long and X. Y. Wang, Distributed proximal-gradient method for convex optimization with inequality constraints, ANZIAM J., 56 (2014), 160-178. doi: 10.1017/S1446181114000273.

[16]

A. Nedić and D. P. Bertsekas, Convergence rate of incremental subgradient algorithm, in Stochastic Optimization: Algorithms and Applications (eds. S. Uryasev and P. M. Pardalos), Applied Optimization, 54, Springer, 2001,223-264. doi: 10.1007/978-1-4757-6594-6_11.

[17]

A. Nedić and D. P. Bertsekas, Incremental subgradient methods for nondifferentiable optimization, SIAM J. Optim., 12 (2001), 109-138. doi: 10.1137/S1052623499362111.

[18]

A. Nedić and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control., 54 (2009), 48-61. doi: 10.1109/TAC.2008.2009515.

[19]

Y. Nesterov, Random Gradient-Free Minimization of Convex Functions, Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, January 2011. Available from: http://www.ecore.be/DPs/dp_1297333890.pdf. doi: 10.1007/s10208-015-9296-2.

[20]

B. T. Polyak and J. Tsypkin, Robust identification, Automatica, 16 (1980), 53-63. doi: 10.1016/0005-1098(80)90086-2.

[21]

M. G. Rabbat and R. D. Nowak, Quantized incremental algorithms for distributed optimization, IEEE J. Sel. Areas Commun., 23 (2005), 798-808. doi: 10.1109/JSAC.2005.843546.

[22]

S. S. RamA. Nedić and V. V. Veeravalli, Incremental stochastic subgradient algorithms for convex optimization, SIAM J. Optim., 20 (2009), 691-717. doi: 10.1137/080726380.

[23]

Q. J. ShiC. He and L. G. Jiang, Normalized incremental subgradient algorithm and its application, IEEE Signal Processing, 57 (2009), 3759-3774. doi: 10.1109/TSP.2009.2024901.

[24]

R. L. SheuM. J. Ting and I. L. Wang, Maximum folw problem in the distribution network, J. Ind. Manag. Optim., 2 (2006), 237-254. doi: 10.3934/jimo.2006.2.237.

[25]

M. V. Solodov, Incremental gradient algorithms with stepsizes bounded away from zero, Comput. Optim. Appl., 11 (1998), 28-35. doi: 10.1023/A:1018366000512.

[26]

D. M. YuanS. Y. Xu and J. W. Lu, Gradient-free method for distributed multi-agent optimization via push-sum algorithms, Int. J. Robust Nonlinear Control, 25 (2015), 1569-1580. doi: 10.1002/rnc.3164.

[27]

Q. Long and C. Wu, A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization, J. Ind. Manag. Optim., 10 (2014), 1279-1296. doi: 10.3934/jimo.2014.10.1279.

[28]

G. H. Yu, A derivative-free method for solving large-scale nonlinear systems of equations, J. Ind. Manag. Optim., 6 (2010), 149-160. doi: 10.3934/jimo.2010.6.149.

[29]

C. J. YuK. L. TeoL. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems, J. Ind. Manag. Optim., 6 (2010), 895-910. doi: 10.3934/jimo.2010.6.895.

[30]

F. YousefianA. Nedić and U. V. Shanbhag, On stochastic gradient and subgradient methods with adaptive steplength sequences, Automatica, 48 (2012), 56-67. doi: 10.1016/j.automatica.2011.09.043.

[31]

J. LiG. ChenZ. Dong and Z. Wu, A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints, Comp. Opt. Appl., 64 (2016), 671-697. doi: 10.1007/s10589-016-9826-0.

show all references

References:
[1]

A. M. BagirovM. Ghosh and D. Webb, A derivative-free method for linearly constrained nonsmooth optimization, J. Ind. Manag. Optim., 2 (2006), 319-338. doi: 10.3934/jimo.2006.2.319.

[2]

D. P. Bertsekas, Stochastic optimization problems with nondifferentiable cost functionals, J. Optim. Theory Appl., 12 (1973), 218-231. doi: 10.1007/BF00934819.

[3] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, Belmont, MA, 1989.
[4] D. P. BertsekasA. Nedić and E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 2003.
[5]

D. P. Bertsekas, Incremental proximal methods for large scale convex optimization, Math. Program. B., 129 (2011), 163-195. doi: 10.1007/s10107-011-0472-0.

[6] A. R. ConnK. Scheinberg and L. N. Vicente, Introduction to Derivative-Free Optimization, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2009. doi: 10.1137/1.9780898718768.
[7]

J. C. DuchiA. Agarwal and M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Trans. Autom. Control., 57 (2012), 592-606. doi: 10.1109/TAC.2011.2161027.

[8]

J. C. DuchiP. L. Bartlet and M. J. Wainwrighr, Randomized smoothing for stochastic optimization, SIAM J. Optim., 22 (2012), 674-701. doi: 10.1137/110831659.

[9]

X. X. HuangX. Q. Yang and K. L. Teo, A smoothing scheme for optimization problems with Max-Min constraints, J. Ind. Manag. Optim., 3 (2007), 209-222. doi: 10.3934/jimo.2007.3.209.

[10] J. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms Ⅰ, Springer, Berlin, 1996. doi: 10.1007/978-3-662-02796-7.
[11]

X. ZhangC. WuJ. LiX. WangZ. YangJ. M. Lee and K. H. Jung, Binary artificial algae algorithm for multidimensional knapsack problems, Applied Soft Computing, 43 (2016), 583-595. doi: 10.1016/j.asoc.2016.02.027.

[12]

B. JohanssonM. Rabi and M. Johansson, A randomized incremental subgradient method for distributed optimization in networked systems, SIAM J. Optim., 20 (2009), 1157-1170. doi: 10.1137/08073038X.

[13]

K. C. Kiwiel, Convergence of approximate and incremental subgradient methods for convex optimization, SIAM J. Optim., 14 (2004), 807-840. doi: 10.1137/S1052623400376366.

[14]

J. Y. LiC. Z. WuZ. Y. Wu and Q. Long, Gradient-free method for nonsmooth distributed optimization, J. Glob. Optim., 61 (2015), 325-340. doi: 10.1007/s10898-014-0174-2.

[15]

J. Y. LiC. Z. WuZ. Y. WuQ. Long and X. Y. Wang, Distributed proximal-gradient method for convex optimization with inequality constraints, ANZIAM J., 56 (2014), 160-178. doi: 10.1017/S1446181114000273.

[16]

A. Nedić and D. P. Bertsekas, Convergence rate of incremental subgradient algorithm, in Stochastic Optimization: Algorithms and Applications (eds. S. Uryasev and P. M. Pardalos), Applied Optimization, 54, Springer, 2001,223-264. doi: 10.1007/978-1-4757-6594-6_11.

[17]

A. Nedić and D. P. Bertsekas, Incremental subgradient methods for nondifferentiable optimization, SIAM J. Optim., 12 (2001), 109-138. doi: 10.1137/S1052623499362111.

[18]

A. Nedić and A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. Autom. Control., 54 (2009), 48-61. doi: 10.1109/TAC.2008.2009515.

[19]

Y. Nesterov, Random Gradient-Free Minimization of Convex Functions, Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, January 2011. Available from: http://www.ecore.be/DPs/dp_1297333890.pdf. doi: 10.1007/s10208-015-9296-2.

[20]

B. T. Polyak and J. Tsypkin, Robust identification, Automatica, 16 (1980), 53-63. doi: 10.1016/0005-1098(80)90086-2.

[21]

M. G. Rabbat and R. D. Nowak, Quantized incremental algorithms for distributed optimization, IEEE J. Sel. Areas Commun., 23 (2005), 798-808. doi: 10.1109/JSAC.2005.843546.

[22]

S. S. RamA. Nedić and V. V. Veeravalli, Incremental stochastic subgradient algorithms for convex optimization, SIAM J. Optim., 20 (2009), 691-717. doi: 10.1137/080726380.

[23]

Q. J. ShiC. He and L. G. Jiang, Normalized incremental subgradient algorithm and its application, IEEE Signal Processing, 57 (2009), 3759-3774. doi: 10.1109/TSP.2009.2024901.

[24]

R. L. SheuM. J. Ting and I. L. Wang, Maximum folw problem in the distribution network, J. Ind. Manag. Optim., 2 (2006), 237-254. doi: 10.3934/jimo.2006.2.237.

[25]

M. V. Solodov, Incremental gradient algorithms with stepsizes bounded away from zero, Comput. Optim. Appl., 11 (1998), 28-35. doi: 10.1023/A:1018366000512.

[26]

D. M. YuanS. Y. Xu and J. W. Lu, Gradient-free method for distributed multi-agent optimization via push-sum algorithms, Int. J. Robust Nonlinear Control, 25 (2015), 1569-1580. doi: 10.1002/rnc.3164.

[27]

Q. Long and C. Wu, A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization, J. Ind. Manag. Optim., 10 (2014), 1279-1296. doi: 10.3934/jimo.2014.10.1279.

[28]

G. H. Yu, A derivative-free method for solving large-scale nonlinear systems of equations, J. Ind. Manag. Optim., 6 (2010), 149-160. doi: 10.3934/jimo.2010.6.149.

[29]

C. J. YuK. L. TeoL. S. Zhang and Y. Q. Bai, A new exact penalty function method for continuous inequality constrained optimization problems, J. Ind. Manag. Optim., 6 (2010), 895-910. doi: 10.3934/jimo.2010.6.895.

[30]

F. YousefianA. Nedić and U. V. Shanbhag, On stochastic gradient and subgradient methods with adaptive steplength sequences, Automatica, 48 (2012), 56-67. doi: 10.1016/j.automatica.2011.09.043.

[31]

J. LiG. ChenZ. Dong and Z. Wu, A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints, Comp. Opt. Appl., 64 (2016), 671-697. doi: 10.1007/s10589-016-9826-0.

Figure 1.  Function value error versus number of cycles $K$ with a constant stepsize $\alpha=0.001$ for algorithms CIGF and CISG
Figure 2.  Function value error versus number of iterations $N$ with a constant stepsize $\alpha=0.001$ for algorithms RIGF and RISG
Figure 3.  (a) Function value error versus number of cycles $K$ with diminishing stepsize choices: $\alpha_{1}(k)={1}/{(m(k-1)+i)}, ~ \alpha_{2}(k)={1}/{(m(k-1)+i)^{\frac{2}{3}}}, k=0, 1, \ldots, i=1, \ldots, m$; (b) Function value error versus number of iterations $N$ with diminishing stepsize choices: $\theta_{1}(k)={1}/{k}, ~\theta_{2}(k)={0.1}/{k^{\frac{2}{3}}}, k=1, 2, \ldots$
Figure 4.  For a fixed target accuracy $\epsilon=0.01$ and a constant stepsize $\alpha=0.001$, comparisons between algorithms CIGF and CISG: (a) number of iterations $N$ versus dimensions of the agent $d$ for fixed $m=100$; (b) number of iterations $N$ versus number of agents $m$ for fixed $d=2$
[1]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

[2]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171

[3]

Zhongwen Chen, Songqiang Qiu, Yujie Jiao. A penalty-free method for equality constrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (2) : 391-409. doi: 10.3934/jimo.2013.9.391

[4]

Samuel Amstutz, Antonio André Novotny, Nicolas Van Goethem. Minimal partitions and image classification using a gradient-free perimeter approximation. Inverse Problems & Imaging, 2014, 8 (2) : 361-387. doi: 10.3934/ipi.2014.8.361

[5]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117

[6]

Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems & Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195

[7]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883

[8]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034

[9]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[10]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[11]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

[12]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial & Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[13]

René Henrion. Gradient estimates for Gaussian distribution functions: application to probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 655-668. doi: 10.3934/naco.2012.2.655

[14]

Dongsheng Yin, Min Tang, Shi Jin. The Gaussian beam method for the wigner equation with discontinuous potentials. Inverse Problems & Imaging, 2013, 7 (3) : 1051-1074. doi: 10.3934/ipi.2013.7.1051

[15]

Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395

[16]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[17]

Daniela Saxenhuber, Ronny Ramlau. A gradient-based method for atmospheric tomography. Inverse Problems & Imaging, 2016, 10 (3) : 781-805. doi: 10.3934/ipi.2016021

[18]

Wanyou Cheng, Zixin Chen, Donghui Li. Nomonotone spectral gradient method for sparse recovery. Inverse Problems & Imaging, 2015, 9 (3) : 815-833. doi: 10.3934/ipi.2015.9.815

[19]

Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems & Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010

[20]

Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033

2016 Impact Factor: 0.994

Metrics

  • PDF downloads (17)
  • HTML views (54)
  • Cited by (0)

[Back to Top]