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

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

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 and 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, Springer, 2011. doi: 10.1007/978-1-4419-9467-7.
[2]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal of Imaging Sciences, 2 (2009), 183-202. doi: 10.1137/080716542.
[3]	D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, 1999.
[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-226. doi: 10.1145/1970392.1970395.
[5]	J. Duchi and Y. Singer, Efficient online and batch learning using forward backward splitting, The Journal of Machine Learning Research, 10 (2009), 2899-2934.
[6]	Y. Nesterov, Introductory lectures on convex optimization: A basic course, Springer, 2004. doi: 10.1007/978-1-4419-8853-9.
[7]	Y. Nesterov, Smooth minimization of non-smooth functions,, Mathematical Programming, 103 (): 127. doi: 10.1007/s10107-004-0552-5.
[8]	Y. Nesterov, Random gradient-free minimization of convex functions, Core discussion paper, 2001, http://www.uclouvain.be/core.
[9]	R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.
[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-1472.
[11]	M. Yuan and Y. Lin, Model selection and estimation in the Gaussian graphical model, Biometrika, 94 (2007), 19-35. doi: 10.1093/biomet/asm018.
[12]	C. Zalinescu, Convex Analysis in General Vector Spaces, World Scientific, 2002. doi: 10.1142/9789812777096.

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, Springer, 2011. doi: 10.1007/978-1-4419-9467-7.
[2]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal of Imaging Sciences, 2 (2009), 183-202. doi: 10.1137/080716542.
[3]	D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, 1999.
[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-226. doi: 10.1145/1970392.1970395.
[5]	J. Duchi and Y. Singer, Efficient online and batch learning using forward backward splitting, The Journal of Machine Learning Research, 10 (2009), 2899-2934.
[6]	Y. Nesterov, Introductory lectures on convex optimization: A basic course, Springer, 2004. doi: 10.1007/978-1-4419-8853-9.
[7]	Y. Nesterov, Smooth minimization of non-smooth functions,, Mathematical Programming, 103 (): 127. doi: 10.1007/s10107-004-0552-5.
[8]	Y. Nesterov, Random gradient-free minimization of convex functions, Core discussion paper, 2001, http://www.uclouvain.be/core.
[9]	R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.
[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-1472.
[11]	M. Yuan and Y. Lin, Model selection and estimation in the Gaussian graphical model, Biometrika, 94 (2007), 19-35. doi: 10.1093/biomet/asm018.
[12]	C. Zalinescu, Convex Analysis in General Vector Spaces, World Scientific, 2002. doi: 10.1142/9789812777096.

[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 and Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[2]	Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021028
[3]	Tengteng Yu, Xin-Wei Liu, Yu-Hong Dai, Jie Sun. Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021084
[4]	Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[5]	Hai Huyen Dam, Siow Yong Low, Sven Nordholm. Two-level optimization approach with accelerated proximal gradient for objective measures in sparse speech reconstruction. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021131
[6]	Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[7]	Nurullah Yilmaz, Ahmet Sahiner. On a new smoothing technique for non-smooth, non-convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 317-330. doi: 10.3934/naco.2020004
[8]	ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021150
[9]	Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[10]	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 and Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[11]	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 and Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021
[12]	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 and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859
[13]	Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[14]	Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047
[15]	Ahmet Sahiner, Nurullah Yilmaz, Gulden Kapusuz. A novel modeling and smoothing technique in global optimization. Journal of Industrial and Management Optimization, 2019, 15 (1) : 113-130. doi: 10.3934/jimo.2018035
[16]	Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[17]	Jiaxin Zhang, Hoang Tran, Guannan Zhang. Accelerating reinforcement learning with a Directional-Gaussian-Smoothing evolution strategy. Electronic Research Archive, 2021, 29 (6) : 4119-4135. doi: 10.3934/era.2021075
[18]	Jie Zhang, Yue Wu, Liwei Zhang. A class of smoothing SAA methods for a stochastic linear complementarity problem. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 145-156. doi: 10.3934/naco.2012.2.145
[19]	Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136
[20]	Ahmet Sahiner, Gulden Kapusuz, Nurullah Yilmaz. A new smoothing approach to exact penalty functions for inequality constrained optimization problems. Numerical Algebra, Control and Optimization, 2016, 6 (2) : 161-173. doi: 10.3934/naco.2016006

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Sanming Liu Zhijie Wang Chongyang Liu
on Google Scholar
Sanming Liu Zhijie Wang Chongyang Liu

[Back to Top]