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

Sanming Liu; Zhijie Wang; Chongyang  Liu

doi:10.3934/naco.2015.5.79

Article Contents

2015, Volume 5, Issue 1: 79-89. Doi: 10.3934/naco.2015.5.79

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

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

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

Received: December 2014

Revised: March 2015

Published: February 2015

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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 (2005b), 127-152. 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.