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

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}}$).
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. doi: 10.1137/080716542.

[2]

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

[3]

D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers,, New York, (1982).

[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. doi: 10.1561/2200000016.

[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, 49 (2011), 185. doi: 10.1007/978-1-4419-9569-8_10.

[6]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, (1983), 299.

[7]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics,, volume 9, (1989). doi: 10.1137/1.9781611970838.

[8]

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

[9]

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

[10]

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

[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. doi: 10.1016/0022-247X(79)90234-8.

[12]

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

[13]

R. T. Rockafellar, Convex Analysis,, Princeton NJ: Princeton Univ. Press, (1970).

[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, (2011).

[15]

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

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. doi: 10.1137/080716542.

[2]

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

[3]

D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers,, New York, (1982).

[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. doi: 10.1561/2200000016.

[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, 49 (2011), 185. doi: 10.1007/978-1-4419-9569-8_10.

[6]

D. Gabay, Applications of the method of multipliers to variational inequalities,, in Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, (1983), 299.

[7]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics,, volume 9, (1989). doi: 10.1137/1.9781611970838.

[8]

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

[9]

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

[10]

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

[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. doi: 10.1016/0022-247X(79)90234-8.

[12]

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

[13]

R. T. Rockafellar, Convex Analysis,, Princeton NJ: Princeton Univ. Press, (1970).

[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, (2011).

[15]

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

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2018128

[14]

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

[15]

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

[16]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743

[17]

Wenqing Hu, Chris Junchi Li. A convergence analysis of the perturbed compositional gradient flow: Averaging principle and normal deviations. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 4951-4977. doi: 10.3934/dcds.2018216

[18]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023

[19]

Murat Adivar, Shu-Cherng Fang. Convex optimization on mixed domains. Journal of Industrial & Management Optimization, 2012, 8 (1) : 189-227. doi: 10.3934/jimo.2012.8.189

[20]

Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305

2017 Impact Factor: 0.994

Metrics

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

Other articles
by authors

[Back to Top]