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

Jin-Zan Liu; Xin-Wei Liu

doi:10.3934/naco.2021028

Article Contents

2022, Volume 12, Issue 4: 679-692. Doi: 10.3934/naco.2021028

This issue Previous Article Smooth augmented Lagrangian method for twin bounded support vector machine Next Article On optimal stochastic jumps in multi server queue with impatient customers via stochastic control

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

Jin-Zan Liu^1, and
Xin-Wei Liu^2, ,

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
^* Corresponding author: Xin-Wei Liu

Received: December 31, 2020

Revised: May 31, 2021

Early access: July 2021

Published: December 2022

The research is partially supported by NSFC grant 11671116

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C25, 90C46; Secondary: 65K05.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	H. H. Bauschke, J. 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.
[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.
[3]	A. Beck, First-Order Methods in Optimization, SIAM, Philadelphia, 2017. doi: 10.1137/1.9781611974997.
[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.
[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.
[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.
[7]	M. Bertero, P. Boccacci, G. 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.
[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.
[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.
[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.
[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.
[12]	D. H. Gutman and J. F. Pena, Perturbed Fenchel duality and first-order methods, preprint, arXiv: 1812.10198.
[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.
[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.
[15]	Fast dual proximal gradient algorithms with rate $O(1/k^{1.5} )$ for convex minimization, preprint, arXiv: 1609.09441.,
[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.
[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.
[18]	H. Lu, M. 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.
[19]	J. Li, G. Chen and Z. Dong, et al., 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.
[20]	D. P. Palomar and Y. C. Eldar, Convex Optimization in Signal Processing and Communications, Cambridge University Press, Cambridge, 2010. doi: 10.1017/CBO9780511804458.
[21]	S. Sra, S. Nowozin and S. J. Wright, Optimization for Machine Learning, MIT Press, Massachusetts, 2011. doi: 10.7551/mitpress/8996.001.0001.
[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.
[23]	T. Treskatis, M. 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.
[24]	H. Zhang, Y. H. Dai and L. Guo, Linear convergence of random dual coordinate incremental aggregated gradient methods, preprint, arXiv: 2008.13080.