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.  Google Scholar

[2]

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

[3] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, Belmont, MA, 1989.   Google Scholar
[4] D. P. BertsekasA. Nedić and E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 2003.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10] J. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms Ⅰ, Springer, Berlin, 1996.  doi: 10.1007/978-3-662-02796-7.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[20]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

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

[3] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, Belmont, MA, 1989.   Google Scholar
[4] D. P. BertsekasA. Nedić and E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 2003.   Google Scholar
[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.  Google Scholar

[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.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10] J. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms Ⅰ, Springer, Berlin, 1996.  doi: 10.1007/978-3-662-02796-7.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

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

[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.  Google Scholar

[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.  Google Scholar

[20]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[2]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[3]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[4]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[5]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[6]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[7]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[8]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[9]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[10]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[11]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[12]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[13]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[14]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[15]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[16]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[17]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[18]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[19]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (93)
  • HTML views (458)
  • Cited by (0)

[Back to Top]