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.  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.  doi: 10.1016/j.orl.2013.10.007.  Google Scholar

[3]

D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers,, New York, (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.  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, 49 (2011), 185.  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, (1983), 299.   Google Scholar

[7]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics,, volume 9, (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.  doi: 10.1137/0716071.  Google Scholar

[9]

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

[10]

Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function,, CORE Discussion Papers, (2007).   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.  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.  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, (2011).   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.  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.  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.  doi: 10.1016/j.orl.2013.10.007.  Google Scholar

[3]

D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers,, New York, (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.  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, 49 (2011), 185.  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, (1983), 299.   Google Scholar

[7]

R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics,, volume 9, (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.  doi: 10.1137/0716071.  Google Scholar

[9]

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

[10]

Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function,, CORE Discussion Papers, (2007).   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.  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.  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, (2011).   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.  doi: 10.1137/090777761.  Google Scholar

[1]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[2]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565
[3]

Tuan Hiep Pham, Jérôme Laverne, Jean-Jacques Marigo. Stress gradient effects on the nucleation and propagation of cohesive cracks. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 557-584. doi: 10.3934/dcdss.2016012
[4]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[5]

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363
[6]

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

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[8]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[9]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[10]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[11]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[12]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[13]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[14]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[15]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[16]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[17]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[18]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[19]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[20]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences