On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems

Previous Article
JIMO Home
This Issue
Next Article
A criterion for an approximation global optimal solution based on the filled functions

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

Abstract
Related Papers

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 and 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.
[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.
[3]	D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers, New York, Academic Press, 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-122. 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, 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.
[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.
[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.
[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.
[9]	J. J. Moreau., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), 273-299.
[10]	Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE Discussion Papers, (2007), 2007/76.
[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.
[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.
[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, Dec 2011, Grenada, Spain.
[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.

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.
[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.
[3]	D. P. Bertsekas, Constrained Optimization and Lagrangian Multipliers, New York, Academic Press, 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-122. 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, 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.
[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.
[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.
[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.
[9]	J. J. Moreau., Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France, 93 (1965), 273-299.
[10]	Y. Nesterov, Gradient Methods for Minimizing Composite Objective Function, CORE Discussion Papers, (2007), 2007/76.
[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.
[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.
[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, Dec 2011, Grenada, Spain.
[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.

[1]	Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021028
[2]	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 and Management Optimization, 2021 doi: 10.3934/jimo.2021084
[3]	Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[4]	Yuhong Dai, Ya-xiang Yuan. Analysis of monotone gradient methods. Journal of Industrial and Management Optimization, 2005, 1 (2) : 181-192. doi: 10.3934/jimo.2005.1.181
[5]	Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[6]	Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[7]	Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79
[8]	Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171
[9]	Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[10]	Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial and Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181
[11]	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 and Applied Analysis, 2020, 19 (10) : 4899-4920. doi: 10.3934/cpaa.2020217
[12]	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
[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 and Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021
[14]	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 and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859
[15]	Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[16]	Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete and Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328
[17]	Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial and Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[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 and Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003
[19]	Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems and Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357
[20]	Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1897-1920. doi: 10.3934/jimo.2018128

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Sanming Liu Zhijie Wang Chongyang Liu
on Google Scholar
Sanming Liu Zhijie Wang Chongyang Liu

[Back to Top]