Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems

Previous Article
Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times
NACO Home
This Issue
Next Article

2015, 5(1): 79-89. doi: 10.3934/naco.2015.5.79

Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems

Sanming Liu ^1, , Zhijie Wang ^2, and Chongyang Liu ^3,

1.	Department of Mathematics and Physics, Shanghai Dianji University, 1350 Ganlan Road, Shanghai, 201306, China
2.	School of Electrical Engineering, Shanghai Dianji University, 1350 Ganlan Road, Shanghai, 201306, China
3.	School of Mathematics and Information Science, Shandong Institute of Business and Technology, 191 Binhaizhong Road, Yantan, Shandong Province, 264005, China

Received December 2014 Revised March 2015 Published March 2015

Abstract
Related Papers

In this paper, we consider the problem of minimizing a convex objective which is the sum of three parts: a smooth part, a simple non-smooth Lipschitz part, and a simple non-smooth non-Lipschitz part. A novel optimization algorithm is proposed for solving this problem. By making use of the Gaussian smoothing function of the functions occurring in the objective, we smooth the second part to a convex and differentiable function with Lipschitz continuous gradient by using both variable and constant smoothing parameters. The resulting problem is solved via an accelerated proximal-gradient method and this allows us to recover approximately the optimal solutions to the initial optimization problem with a rate of convergence of order $O(\frac{\ln k}{k})$ for variable smoothing and of order $O(\frac{1}{k})$ for constant smoothing.

Keywords: accelerated proximal-gradient methods, smoothing method., nonsmooth convex optimization, Gaussian smoothing.

Mathematics Subject Classification: Primary: 90C30; Secondary: 90C2.

Citation: 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

References:

[1]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces,, CMS Books in Mathematics, (2011). doi: 10.1007/978-1-4419-9467-7. Google Scholar
[2]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM Journal of Imaging Sciences, 2 (2009), 183. doi: 10.1137/080716542. Google Scholar
[3]	D. P. Bertsekas, Nonlinear Programming,, Athena Scientific, (1999). Google Scholar
[4]	E. J. Candes, X. Li, Y. Ma and J. Wright, Robust principal component analysis,, Journal of the Association for Computing Machinery, 58 (2011), 219. doi: 10.1145/1970392.1970395. Google Scholar
[5]	J. Duchi and Y. Singer, Efficient online and batch learning using forward backward splitting,, The Journal of Machine Learning Research, 10 (2009), 2899. Google Scholar
[6]	Y. Nesterov, Introductory lectures on convex optimization: A basic course,, Springer, (2004). doi: 10.1007/978-1-4419-8853-9. Google Scholar
[7]	Y. Nesterov, Smooth minimization of non-smooth functions,, Mathematical Programming, 103 (): 127. doi: 10.1007/s10107-004-0552-5. Google Scholar
[8]	Y. Nesterov, Random gradient-free minimization of convex functions,, Core discussion paper, (2001). Google Scholar
[9]	R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970). Google Scholar
[10]	M. J. Wainwright, P. Ravikumar and J. D. Lafferty, High-dimensional graphical model selection using l₁-regularized logistic regression,, In Advances in Neural Information Processing Systems, 19 (2007), 1465. Google Scholar
[11]	M. Yuan and Y. Lin, Model selection and estimation in the Gaussian graphical model,, Biometrika, 94 (2007), 19. doi: 10.1093/biomet/asm018. Google Scholar
[12]	C. Zalinescu, Convex Analysis in General Vector Spaces,, World Scientific, (2002). doi: 10.1142/9789812777096. Google Scholar

show all references

References:

[1]	H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces,, CMS Books in Mathematics, (2011). doi: 10.1007/978-1-4419-9467-7. Google Scholar
[2]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM Journal of Imaging Sciences, 2 (2009), 183. doi: 10.1137/080716542. Google Scholar
[3]	D. P. Bertsekas, Nonlinear Programming,, Athena Scientific, (1999). Google Scholar
[4]	E. J. Candes, X. Li, Y. Ma and J. Wright, Robust principal component analysis,, Journal of the Association for Computing Machinery, 58 (2011), 219. doi: 10.1145/1970392.1970395. Google Scholar
[5]	J. Duchi and Y. Singer, Efficient online and batch learning using forward backward splitting,, The Journal of Machine Learning Research, 10 (2009), 2899. Google Scholar
[6]	Y. Nesterov, Introductory lectures on convex optimization: A basic course,, Springer, (2004). doi: 10.1007/978-1-4419-8853-9. Google Scholar
[7]	Y. Nesterov, Smooth minimization of non-smooth functions,, Mathematical Programming, 103 (): 127. doi: 10.1007/s10107-004-0552-5. Google Scholar
[8]	Y. Nesterov, Random gradient-free minimization of convex functions,, Core discussion paper, (2001). Google Scholar
[9]	R. T. Rockafellar, Convex Analysis,, Princeton University Press, (1970). Google Scholar
[10]	M. J. Wainwright, P. Ravikumar and J. D. Lafferty, High-dimensional graphical model selection using l₁-regularized logistic regression,, In Advances in Neural Information Processing Systems, 19 (2007), 1465. Google Scholar
[11]	M. Yuan and Y. Lin, Model selection and estimation in the Gaussian graphical model,, Biometrika, 94 (2007), 19. doi: 10.1093/biomet/asm018. Google Scholar
[12]	C. Zalinescu, Convex Analysis in General Vector Spaces,, World Scientific, (2002). doi: 10.1142/9789812777096. Google Scholar

[1]	Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[2]	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
[3]	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
[4]	Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[5]	Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[6]	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
[7]	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
[8]	Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[9]	Ahmet Sahiner, Nurullah Yilmaz, Gulden Kapusuz. A novel modeling and smoothing technique in global optimization. Journal of Industrial & Management Optimization, 2019, 15 (1) : 113-130. doi: 10.3934/jimo.2018035
[10]	Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018136
[11]	Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145
[12]	Ahmet Sahiner, Gulden Kapusuz, Nurullah Yilmaz. A new smoothing approach to exact penalty functions for inequality constrained optimization problems. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 161-173. doi: 10.3934/naco.2016006
[13]	X. X. Huang, Xiaoqi Yang, K. L. Teo. A smoothing scheme for optimization problems with Max-Min constraints. Journal of Industrial & Management Optimization, 2007, 3 (2) : 209-222. doi: 10.3934/jimo.2007.3.209
[14]	Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2018181
[15]	Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019013
[16]	Hui-Qiang Ma, Nan-Jing Huang. Neural network smoothing approximation method for stochastic variational inequality problems. Journal of Industrial & Management Optimization, 2015, 11 (2) : 645-660. doi: 10.3934/jimo.2015.11.645
[17]	Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235
[18]	Yafeng Li, Guo Sun, Yiju Wang. A smoothing Broyden-like method for polyhedral cone constrained eigenvalue problem. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 529-537. doi: 10.3934/naco.2011.1.529
[19]	Burcu Özçam, Hao Cheng. A discretization based smoothing method for solving semi-infinite variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 219-233. doi: 10.3934/jimo.2005.1.219
[20]	C. M. Elliott, B. Gawron, S. Maier-Paape, E. S. Van Vleck. Discrete dynamics for convex and non-convex smoothing functionals in PDE based image restoration. Communications on Pure & Applied Analysis, 2006, 5 (1) : 181-200. doi: 10.3934/cpaa.2006.5.181

Impact Factor:

American Institute of Mathematical Sciences