A bundle Bregman proximal method for convex nondifferentiable minimization

We give a method for minimizing a convex function f that generates a sequence {x(k)} by taking x(k) to be an approximate minimizer of f(k) + D-h(., xk(-1))/t(k), where f(k) is a piecewise linear model of f constructed from accumulated subgradient linearizations of f, Dh is the D-function of a generalized Bregman function h and t(k) > 0. Convergence under implementable criteria is established by extending our recent framework of Bregman proximal minimization, which is of independent interest, e.g., for nonquadratic multiplier methods for constrained minimization. In particular, we provide new insights into the convergence properties of bundle methods based on h = 1/2\.\(2).