Bregman proximal point algorithm revisited: a new inexact version and its inertial variant

DOI10.1137/20M1360748MaRDI QIDQ5093643zbMATHFDO

Authors Lei Yang, Kim-Chuan Toh

Publication date 29 July 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.10370

zbMATH Keywords

optimal transportBregman distanceproximal point algorithmNesterov's accelerationinexact condition

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Optimality conditions and duality in mathematical programming (90C46) Nonlinear programming (90C30) Optimality conditions for minimax problems (49K35)

Abstract: We study a general convex optimization problem, which covers various classic problems in different areas and particularly includes many optimal transport related problems arising in recent years. To solve this problem, we revisit the classic Bregman proximal point algorithm (BPPA) and introduce a new inexact stopping condition for solving the subproblems, which can circumvent the underlying feasibility difficulty often appearing in existing inexact conditions when the problem has a complex feasible set. Our inexact condition also covers several existing inexact conditions as special cases and hence makes our inexact BPPA (iBPPA) more flexible to fit different scenarios in practice. Moreover, inspired by Nesterov's acceleration technique, we develop an inertial variant of our iBPPA, denoted by V-iBPPA, and establish the iteration complexity of $O(1/k^{lambda})$, where $lambdageq1$ is a quadrangle scaling exponent of the kernel function. In particular, when the proximal parameter is a constant and the kernel function is strongly convex with Lipschitz continuous gradient (hence $lambda=2$), our V-iBPPA achieves a faster rate of $O(1/k^2)$ just as existing accelerated inexact proximal point algorithms. Some preliminary numerical experiments for solving the standard OT problem are conducted to show the convergence behaviors of our iBPPA and V-iBPPA under different inexactness settings. The experiments also empirically verify the potential of our V-iBPPA on improving the convergence speed.

Recommendations

• An accelerated inexact proximal point algorithm for convex minimization
• An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems
• On the linear convergence of a Bregman proximal point algorithm
• A general inertial proximal point algorithm for mixed variational inequality problem
• Gradient methods for problems with inexact model of the objective

Cites work

• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 4164577 (Why is no real title available?)
• scientific article; zbMATH DE number 4079168 (Why is no real title available?)
• scientific article; zbMATH DE number 1046019 (Why is no real title available?)
• scientific article; zbMATH DE number 1968261 (Why is no real title available?)
• scientific article; zbMATH DE number 1369459 (Why is no real title available?)
• scientific article; zbMATH DE number 1382772 (Why is no real title available?)
• scientific article; zbMATH DE number 854129 (Why is no real title available?)
• scientific article; zbMATH DE number 3252891 (Why is no real title available?)
• scientific article; zbMATH DE number 3296905 (Why is no real title available?)
• scientific article; zbMATH DE number 3341597 (Why is no real title available?)
• A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS^*
• A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
• A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator
• A simplified view of first order methods for optimization
• Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
• Accelerated and inexact forward-backward algorithms
• An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
• An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions
• An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities
• An iterative row-action method for interval convex programming
• Approximate iterations in Bregman-function-based proximal algorithms
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Catalyst acceleration for first-order convex optimization: from theory to practice
• Computational optimal transport. With applications to data sciences
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Convergence Rate Analysis of Nonquadratic Proximal Methods for Convex and Linear Programming
• Convergence of Proximal-Like Algorithms
• Convex Analysis
• Enlargement of monotone operators with applications to variational inequalities
• Entropic Proximal Mappings with Applications to Nonlinear Programming
• Entropy-Like Proximal Methods in Convex Programming
• Error bounds for proximal point subproblems and associated inexact proximal point algorithms
• First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• Introductory lectures on convex optimization. A basic course.
• Joint and separate convexity of the Bregman distance.
• Monotone Operators and the Proximal Point Algorithm
• Multiplicative iterative algorithms for convex programming
• New Proximal Point Algorithms for Convex Minimization
• Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
• On the Convergence of the Proximal Point Algorithm for Convex Minimization
• On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
• On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
• Perturbed Fenchel duality and first-order methods
• Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
• Proximal Minimization Methods with Generalized Bregman Functions
• Proximal minimization algorithm with \(D\)-functions
• Proximité et dualité dans un espace hilbertien
• Relatively smooth convex optimization by first-order methods, and applications
• Smooth minimization of non-smooth functions
• Variational Analysis

Cited in

(8)

• An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems
• Inexact version of Bregman proximal gradient algorithm
• Inertial proximal point regularization algorithm for unconstrained vector convex optimization problems
• An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions
• A highly efficient algorithm for solving exclusive lasso problems
• Analysis of two versions of relaxed inertial algorithms with Bregman divergences for solving variational inequalities
• Doubly iteratively reweighted algorithm for constrained compressed sensing models
• Approximate Bregman proximal gradient algorithm for relatively smooth nonconvex optimization

This page was built for publication: Bregman proximal point algorithm revisited: a new inexact version and its inertial variant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093643)