American Institute of Mathematical Sciences

Advanced
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

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 l1-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 l1-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]

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]

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
[3]

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

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[5]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026
[6]

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
[7]

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
[8]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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

 Impact Factor: 

Tools

Metrics

  • PDF downloads (35)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences