On Dual Convergence of the Generalized Proximal Point Method with Bregman Distances

A. Iusem and R.D.C. Monteiro

The use of generalized distances (e.g.\ Bregman distances), instead of the Euclidean one, in the proximal point method for convex optimization, allows for elimination of the inequality constraints from the subproblems. In this paper we consider the proximal point method with Bregman distances applied to linearly constrained convex optimization problems, and study the behavior of the dual sequence obtained from the optimal multipliers of the linear constraints of each subproblem. Under rather general assumptions, which cover most Bregman distances of interest, we obtain an ergodic convergence result, namely that a sequence of weighted averages of the dual sequence converges to the centroid of the dual optimal set. As an intermediate result, we prove under the same assumptions that the dual central path generated by a large class of barriers, including the generalized Bregman distances, converges to the same point.

manuscript, School of ISyE, Georgia Tech, Atlanta, GA 30332, October 1997.

Contact: monteiro@isye.gatech.edu