We give a method for minimizing a convex function f that generates a sequence {xk} by taking xk to be an approximate minimizer of &fcaron;k + Dh(·, xk–1)/tk, where &fcaron;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 tk > 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.
