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

DOI10.1137/20M1360748zbMATH Open1496.90108arXiv2105.10370MaRDI QIDQ5093643FDOQ5093643

Authors: Lei Yang, Kim-Chuan Toh 

Publication date: 29 July 2022

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

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.

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

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

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)

Cites Work

• Variational Analysis
• Computational Optimal Transport: With Applications to Data Science
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convex Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• An iterative row-action method for interval convex programming
• Enlargement of monotone operators with applications to variational inequalities
• A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator
• An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods
• Accelerated and inexact forward-backward algorithms
• On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean
• Monotone Operators and the Proximal Point Algorithm
• Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
• Title not available (Why is that?)
• Proximal Minimization Methods with Generalized Bregman Functions
• Title not available (Why is that?)
• Proximité et dualité dans un espace hilbertien
• Title not available (Why is that?)
• Approximation accuracy, gradient methods, and error bound for structured convex optimization
• Approximate iterations in Bregman-function-based proximal algorithms
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• On the Convergence of the Proximal Point Algorithm for Convex Minimization
• Convergence of Proximal-Like Algorithms
• A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS^*
• Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
• Proximal minimization algorithm with \(D\)-functions
• Entropy-Like Proximal Methods in Convex Programming
• Convergence Rate Analysis of Nonquadratic Proximal Methods for Convex and Linear Programming
• Multiplicative iterative algorithms for convex programming
• An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities
• An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions
• Interior Gradient and Proximal Methods for Convex and Conic Optimization
• Title not available (Why is that?)
• Entropic Proximal Mappings with Applications to Nonlinear Programming
• Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
• Error bounds for proximal point subproblems and associated inexact proximal point algorithms
• Joint and separate convexity of the Bregman distance.
• New Proximal Point Algorithms for Convex Minimization
• Title not available (Why is that?)
• First Order Methods Beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems
• Relatively Smooth Convex Optimization by First-Order Methods, and Applications
• A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications
• Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice
• A simplified view of first order methods for optimization
• Title not available (Why is that?)
• Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
• On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
• Perturbed Fenchel duality and first-order methods

Cited In (8)

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

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)