American Institute of Mathematical Sciences

Advanced
January  2016, 12(1): 389-402. doi: 10.3934/jimo.2016.12.389

On convergence analysis of dual proximal-gradient methods with approximate gradient 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, Shanghai, 200240, China
2. 

School of Electric Engineering, Shanghai Dianji University, Shanghai, 200240, China
3. 

School of Mathematics and Information Science, Shandong Institute of Business and Technology, Yantai, 264005, China

Received  January 2014 Revised  February 2015 Published  April 2015

In this paper, we consider the problem of minimizing a nonsmooth convex objective which is the sum of a proper, nonsmooth, closed, strongly convex extend real-valued function with a proper, nonsmooth, closed, convex extend real-valued function which is a composition of a proper closed convex function and a nonzero affine map. We first establish its dual problem which consists of minimizing the sum of a smooth convex function with a closed proper nonsmooth convex function. Then we apply first order proximal gradient methods on the dual problem, where an error is present in the calculation of the gradient of the smooth term. Further we present a dual proximal-gradient methods with approximate gradient. We show that when the errors are summable although the dual lowest objective function sequence generated by the proximal-gradient method with the errors converges to the optimal value with the rate $O(\frac{1}{k})$, the rate of convergence of the primal sequence is of the order $O(\frac{1}{\sqrt{k}}$).
Keywords: convergence analysis., Strongly convex, approximate gradient, dual problem, proximal-gradient methods, nonsmooth convex optimization.
Mathematics Subject Classification: Primary: 90C25, 65K05; Secondary: 90C59, 49M2.
Citation: 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
References:
[1]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), 183-202. doi: 10.1137/080716542.  Google Scholar

[2]

A. Beck, M. Teboulle, A Fast Dual Proximal Gradient Algorithm for Convex Minimization and Applications, Operations Research Letters, 42 (2014), 1-6. doi: 10.1016/j.orl.2013.10.007.  Google Scholar

[3]

D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers, New York, Academic Press, 1982. Google Scholar

[4]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2011), 1-122. doi: 10.1561/2200000016.  Google Scholar

[5]

P. L. Combettes and J. C. Presquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering (eds. H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz), Springer Verlag series in Optimization and Its Applications, 49 (2011), 185-212. doi: 10.1007/978-1-4419-9569-8_10.  Google Scholar

[6]

D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, chapter IX" (eds. M. Fortin and R. Glowinski), North-Holland, Amsterdam, (1983), 299-340. Google Scholar

[7]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, volume 9, Society for Industrial Mathematics, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[8]

P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 16 (1979), 964-979. doi: 10.1137/0716071.  Google Scholar

[9]

J. J. Moreau., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), 273-299.  Google Scholar

[10]

Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE Discussion Papers, (2007), 2007/76. Google Scholar

[11]

G. B. Passty, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl., 72 (1979), 383-390. doi: 10.1016/0022-247X(79)90234-8.  Google Scholar

[12]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), 877-898. doi: 10.1137/0314056.  Google Scholar

[13]

R. T. Rockafellar, Convex Analysis, Princeton NJ: Princeton Univ. Press, 1970.  Google Scholar

[14]

M. Schmidt, N. Le Roux, and F. Bach, Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization, NIPS'11 - 25 th Annual Conference on Neural Information Processing Systems, Dec 2011, Grenada, Spain. Google Scholar

[15]

J. Yang and Y. Zhang, Alternating direction algorithms for l1-problems in compressive sensing, SIAM journal on scientific computing, 33 (2011), 250-278. doi: 10.1137/090777761.  Google Scholar

show all references

References:
[1]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, 2 (2009), 183-202. doi: 10.1137/080716542.  Google Scholar

[2]

A. Beck, M. Teboulle, A Fast Dual Proximal Gradient Algorithm for Convex Minimization and Applications, Operations Research Letters, 42 (2014), 1-6. doi: 10.1016/j.orl.2013.10.007.  Google Scholar

[3]

D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers, New York, Academic Press, 1982. Google Scholar

[4]

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2011), 1-122. doi: 10.1561/2200000016.  Google Scholar

[5]

P. L. Combettes and J. C. Presquet, Proximal splitting methods in signal processing, in Fixed-Point Algorithms for Inverse Problems in Science and Engineering (eds. H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz), Springer Verlag series in Optimization and Its Applications, 49 (2011), 185-212. doi: 10.1007/978-1-4419-9569-8_10.  Google Scholar

[6]

D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, chapter IX" (eds. M. Fortin and R. Glowinski), North-Holland, Amsterdam, (1983), 299-340. Google Scholar

[7]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics, volume 9, Society for Industrial Mathematics, 1989. doi: 10.1137/1.9781611970838.  Google Scholar

[8]

P. L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 16 (1979), 964-979. doi: 10.1137/0716071.  Google Scholar

[9]

J. J. Moreau., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), 273-299.  Google Scholar

[10]

Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE Discussion Papers, (2007), 2007/76. Google Scholar

[11]

G. B. Passty, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl., 72 (1979), 383-390. doi: 10.1016/0022-247X(79)90234-8.  Google Scholar

[12]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization, 14 (1976), 877-898. doi: 10.1137/0314056.  Google Scholar

[13]

R. T. Rockafellar, Convex Analysis, Princeton NJ: Princeton Univ. Press, 1970.  Google Scholar

[14]

M. Schmidt, N. Le Roux, and F. Bach, Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization, NIPS'11 - 25 th Annual Conference on Neural Information Processing Systems, Dec 2011, Grenada, Spain. Google Scholar

[15]

J. Yang and Y. Zhang, Alternating direction algorithms for l1-problems in compressive sensing, SIAM journal on scientific computing, 33 (2011), 250-278. doi: 10.1137/090777761.  Google Scholar

[1]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021084
[2]

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

Yuhong Dai, Ya-xiang Yuan. Analysis of monotone gradient methods. Journal of Industrial & Management Optimization, 2005, 1 (2) : 181-192. doi: 10.3934/jimo.2005.1.181
[4]

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

Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[6]

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

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

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

Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial & Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181
[10]

Yinzheng Sun, Qin Wang, Kyungwoo Song. Subsonic solutions to a shock diffraction problem by a convex cornered wedge for the pressure gradient system. Communications on Pure & Applied Analysis, 2020, 19 (10) : 4899-4920. doi: 10.3934/cpaa.2020217
[11]

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
[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 & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859
[13]

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

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[15]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328
[16]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[17]

Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
[18]

Jie Shen, Jian Lv, Fang-Fang Guo, Ya-Li Gao, Rui Zhao. A new proximal chebychev center cutting plane algorithm for nonsmooth optimization and its convergence. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003
[19]

Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1897-1920. doi: 10.3934/jimo.2018128
[20]

Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences