• Previous Article
    The Numerical Solution of the space-time fractional diffusion equation involving the Caputo-Katugampola fractional derivative
  • NACO Home
  • This Issue
  • Next Article
    $ V $-$ E $-invexity in $ E $-differentiable multiobjective programming
doi: 10.3934/naco.2021028
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

A dual Bregman proximal gradient method for relatively-strongly convex optimization

1. 

School of Science, Hebei University of Technology, Tianjin, China

2. 

Institute of Mathematics, Hebei University of Technology, Tianjin, China

* Corresponding author: Xin-Wei Liu

Received  January 2021 Revised  June 2021 Early access July 2021

Fund Project: The research is partially supported by NSFC grant 11671116

We consider a convex composite minimization problem, whose objective is the sum of a relatively-strongly convex function and a closed proper convex function. A dual Bregman proximal gradient method is proposed for solving this problem and is shown that the convergence rate of the primal sequence is $ O(\frac{1}{k}) $. Moreover, based on the acceleration scheme, we prove that the convergence rate of the primal sequence is $ O(\frac{1}{k^{\gamma}}) $, where $ \gamma\in[1,2] $ is determined by the triangle scaling property of the Bregman distance.

Citation: Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control & Optimization, doi: 10.3934/naco.2021028
References:
[1]

H. H. BauschkeJ. Bolte and M. Teboulle, A descent lemma beyond Lipschitz gradient continuity: first-order method revisited and applications, Mathematics of Operations Research, 42 (2017), 330-348.  doi: 10.1287/moor.2016.0817.  Google Scholar

[2]

H. H. Bauschke and J. M. Borwein, Joint and separate convexity of the Bregman distance, in Inherently Parallel Algorithms in Feasibility and Optimization and their Applications (eds. D. Butnariu, Y. Censor, and S. Reich), Elsevier, (2001), 23–26. doi: 10.1016/S1570-579X(01)80004-5.  Google Scholar

[3]

A. Beck, First-Order Methods in Optimization, SIAM, Philadelphia, 2017. doi: 10.1137/1.9781611974997.  Google Scholar

[4]

A. Beck and M. Teboulle, Gradient-based algorithms with applications to signal recovery, Convex Optimization in Signal Processing and Communications, (2009), 42–88. doi: 10.1017/CBO9780511804458.003.  Google Scholar

[5]

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

[6]

A. Beck and 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

[7]

M. BerteroP. BoccacciG. Desider and G. Vicidomini, Image deblurring with Poisson data: from cells to galaxies, Inverse Problems, 25 (2009), 1-26.  doi: 10.1088/0266-5611/25/12/123006.  Google Scholar

[8]

L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, 7 (1967), 200-217.  doi: 10.1016/0041-5553(67)90040-7.  Google Scholar

[9]

R. Bruck, On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space, Journal of Mathematical Analysis and Applications, 61 (1977), 159-164.  doi: 10.1016/0022-247X(77)90152-4.  Google Scholar

[10]

G. Chen and M. Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM Journal on Optimization, 3 (1993), 538-543.  doi: 10.1137/0803026.  Google Scholar

[11]

M. Fukushima and H. Milne, A generalized proximal point algorithm for certain nonconvex minimization problems, International Journal of Systems Science, 12 (1981), 989-1000.  doi: 10.1080/00207728108963798.  Google Scholar

[12]

D. H. Gutman and J. F. Pena, Perturbed Fenchel duality and first-order methods, preprint, arXiv: 1812.10198. Google Scholar

[13]

F. Hanzely, P. Richtarik and L. Xiao, Accelerated Bregman proximal gradient methods for relatively smooth convex optimization, preprint, arXiv: 1808.03045. doi: 10.1007/s10589-021-00273-8.  Google Scholar

[14]

J. Kiefer and J. Wolfowitz, Optimal design in regression problems, The Annals of Mathematical Statistics, 30 (1959), 271-294.  doi: 10.1214/aoms/1177706252.  Google Scholar

[15]

Fast dual proximal gradient algorithms with rate $O(1/k^{1.5} )$ for convex minimization, preprint, arXiv: 1609.09441., Google Scholar

[16]

E. Klintberg and S. Gros, Approximate inverses in preconditioned fast dual gradient methods for MPC, IFAC-PapersOnLine, 50 (2017), 5901-5906.  doi: 10.1016/j.ifacol.2017.08.1321.  Google Scholar

[17]

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

[18]

H. LuM. Freund and Y. Nesterov, Relatively smooth convex optimization by first-order methods and applications, SIAM Journal on Optimization, 28 (2018), 333-354.  doi: 10.1137/16M1099546.  Google Scholar

[19]

J. LiG. Chen and Z. Dong, A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints, Computational Optimization and Applications, 64 (2016), 671-697.  doi: 10.1007/s10589-016-9826-0.  Google Scholar

[20] D. P. Palomar and Y. C. Eldar, Convex Optimization in Signal Processing and Communications, Cambridge University Press, Cambridge, 2010.  doi: 10.1017/CBO9780511804458.  Google Scholar
[21] S. SraS. Nowozin and S. J. Wright, Optimization for Machine Learning, MIT Press, Massachusetts, 2011.  doi: 10.7551/mitpress/8996.001.0001.  Google Scholar
[22]

M. Teboulle, A simplified view of first order methods for optimization, Mathematical Programming, 170 (2018), 67-96.  doi: 10.1007/s10107-018-1284-2.  Google Scholar

[23]

T. TreskatisM. A. Moyers-Gonzalez and C. J. Price, An accelerated dual gradient method and applications in viscoplasticity, Journal of Non-Newtonian Fluid Mechanics, 238 (2016), 115-130.  doi: 10.1016/j.jnnfm.2016.09.004.  Google Scholar

[24]

H. Zhang, Y. H. Dai and L. Guo, Linear convergence of random dual coordinate incremental aggregated gradient methods, preprint, arXiv: 2008.13080. Google Scholar

show all references

References:
[1]

H. H. BauschkeJ. Bolte and M. Teboulle, A descent lemma beyond Lipschitz gradient continuity: first-order method revisited and applications, Mathematics of Operations Research, 42 (2017), 330-348.  doi: 10.1287/moor.2016.0817.  Google Scholar

[2]

H. H. Bauschke and J. M. Borwein, Joint and separate convexity of the Bregman distance, in Inherently Parallel Algorithms in Feasibility and Optimization and their Applications (eds. D. Butnariu, Y. Censor, and S. Reich), Elsevier, (2001), 23–26. doi: 10.1016/S1570-579X(01)80004-5.  Google Scholar

[3]

A. Beck, First-Order Methods in Optimization, SIAM, Philadelphia, 2017. doi: 10.1137/1.9781611974997.  Google Scholar

[4]

A. Beck and M. Teboulle, Gradient-based algorithms with applications to signal recovery, Convex Optimization in Signal Processing and Communications, (2009), 42–88. doi: 10.1017/CBO9780511804458.003.  Google Scholar

[5]

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

[6]

A. Beck and 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

[7]

M. BerteroP. BoccacciG. Desider and G. Vicidomini, Image deblurring with Poisson data: from cells to galaxies, Inverse Problems, 25 (2009), 1-26.  doi: 10.1088/0266-5611/25/12/123006.  Google Scholar

[8]

L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics, 7 (1967), 200-217.  doi: 10.1016/0041-5553(67)90040-7.  Google Scholar

[9]

R. Bruck, On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space, Journal of Mathematical Analysis and Applications, 61 (1977), 159-164.  doi: 10.1016/0022-247X(77)90152-4.  Google Scholar

[10]

G. Chen and M. Teboulle, Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM Journal on Optimization, 3 (1993), 538-543.  doi: 10.1137/0803026.  Google Scholar

[11]

M. Fukushima and H. Milne, A generalized proximal point algorithm for certain nonconvex minimization problems, International Journal of Systems Science, 12 (1981), 989-1000.  doi: 10.1080/00207728108963798.  Google Scholar

[12]

D. H. Gutman and J. F. Pena, Perturbed Fenchel duality and first-order methods, preprint, arXiv: 1812.10198. Google Scholar

[13]

F. Hanzely, P. Richtarik and L. Xiao, Accelerated Bregman proximal gradient methods for relatively smooth convex optimization, preprint, arXiv: 1808.03045. doi: 10.1007/s10589-021-00273-8.  Google Scholar

[14]

J. Kiefer and J. Wolfowitz, Optimal design in regression problems, The Annals of Mathematical Statistics, 30 (1959), 271-294.  doi: 10.1214/aoms/1177706252.  Google Scholar

[15]

Fast dual proximal gradient algorithms with rate $O(1/k^{1.5} )$ for convex minimization, preprint, arXiv: 1609.09441., Google Scholar

[16]

E. Klintberg and S. Gros, Approximate inverses in preconditioned fast dual gradient methods for MPC, IFAC-PapersOnLine, 50 (2017), 5901-5906.  doi: 10.1016/j.ifacol.2017.08.1321.  Google Scholar

[17]

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

[18]

H. LuM. Freund and Y. Nesterov, Relatively smooth convex optimization by first-order methods and applications, SIAM Journal on Optimization, 28 (2018), 333-354.  doi: 10.1137/16M1099546.  Google Scholar

[19]

J. LiG. Chen and Z. Dong, A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints, Computational Optimization and Applications, 64 (2016), 671-697.  doi: 10.1007/s10589-016-9826-0.  Google Scholar

[20] D. P. Palomar and Y. C. Eldar, Convex Optimization in Signal Processing and Communications, Cambridge University Press, Cambridge, 2010.  doi: 10.1017/CBO9780511804458.  Google Scholar
[21] S. SraS. Nowozin and S. J. Wright, Optimization for Machine Learning, MIT Press, Massachusetts, 2011.  doi: 10.7551/mitpress/8996.001.0001.  Google Scholar
[22]

M. Teboulle, A simplified view of first order methods for optimization, Mathematical Programming, 170 (2018), 67-96.  doi: 10.1007/s10107-018-1284-2.  Google Scholar

[23]

T. TreskatisM. A. Moyers-Gonzalez and C. J. Price, An accelerated dual gradient method and applications in viscoplasticity, Journal of Non-Newtonian Fluid Mechanics, 238 (2016), 115-130.  doi: 10.1016/j.jnnfm.2016.09.004.  Google Scholar

[24]

H. Zhang, Y. H. Dai and L. Guo, Linear convergence of random dual coordinate incremental aggregated gradient methods, preprint, arXiv: 2008.13080. Google Scholar

[1]

Carlos Munuera, Morgan Barbier. Wet paper codes and the dual distance in steganography. Advances in Mathematics of Communications, 2012, 6 (3) : 273-285. doi: 10.3934/amc.2012.6.273

[2]

Jia Cai, Junyi Huo. Sparse generalized canonical correlation analysis via linearized Bregman method. Communications on Pure & Applied Analysis, 2020, 19 (8) : 3933-3945. doi: 10.3934/cpaa.2020173

[3]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65

[4]

José Antonio Carrillo, Yingping Peng, Aneta Wróblewska-Kamińska. Relative entropy method for the relaxation limit of hydrodynamic models. Networks & Heterogeneous Media, 2020, 15 (3) : 369-387. doi: 10.3934/nhm.2020023

[5]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1783-1799. doi: 10.3934/jimo.2019029

[6]

Xinmin Yang, Jin Yang, Heung Wing Joseph Lee. Strong duality theorem for multiobjective higher order nondifferentiable symmetric dual programs. Journal of Industrial & Management Optimization, 2013, 9 (3) : 525-530. doi: 10.3934/jimo.2013.9.525

[7]

Denis Serre, Alexis F. Vasseur. The relative entropy method for the stability of intermediate shock waves; the rich case. Discrete & Continuous Dynamical Systems, 2016, 36 (8) : 4569-4577. doi: 10.3934/dcds.2016.36.4569

[8]

Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020178

[9]

D. V. Osin. Peripheral fillings of relatively hyperbolic groups. Electronic Research Announcements, 2006, 12: 44-52.

[10]

Y. Goto, K. Ishii, T. Ogawa. Method of the distance function to the Bence-Merriman-Osher algorithm for motion by mean curvature. Communications on Pure & Applied Analysis, 2005, 4 (2) : 311-339. doi: 10.3934/cpaa.2005.4.311

[11]

Xiaoling Sun, Xiaojin Zheng, Juan Sun. A Lagrangian dual and surrogate method for multi-dimensional quadratic knapsack problems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 47-60. doi: 10.3934/jimo.2009.5.47

[12]

Yunmei Chen, Xianqi Li, Yuyuan Ouyang, Eduardo Pasiliao. Accelerated bregman operator splitting with backtracking. Inverse Problems & Imaging, 2017, 11 (6) : 1047-1070. doi: 10.3934/ipi.2017048

[13]

Artur Avila, Sébastien Gouëzel, Masato Tsujii. Smoothness of solenoidal attractors. Discrete & Continuous Dynamical Systems, 2006, 15 (1) : 21-35. doi: 10.3934/dcds.2006.15.21

[14]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529

[15]

Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893

[16]

Wenye Ma, Stanley Osher. A TV Bregman iterative model of Retinex theory. Inverse Problems & Imaging, 2012, 6 (4) : 697-708. doi: 10.3934/ipi.2012.6.697

[17]

David Salas, Lionel Thibault, Emilio Vilches. On smoothness of solutions to projected differential equations. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 2255-2283. doi: 10.3934/dcds.2019095

[18]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[19]

Netra Khanal, Ramjee Sharma, Jiahong Wu, Juan-Ming Yuan. A dual-Petrov-Galerkin method for extended fifth-order Korteweg-de Vries type equations. Conference Publications, 2009, 2009 (Special) : 442-450. doi: 10.3934/proc.2009.2009.442

[20]

Bin Li, Hai Huyen Dam, Antonio Cantoni. A low-complexity zero-forcing Beamformer design for multiuser MIMO systems via a dual gradient method. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 297-304. doi: 10.3934/naco.2016012

 Impact Factor: 

Article outline

[Back to Top]