Dual Convergence of the Proximal Point Method with Bregman Distances for Linear Programming

J. X. Cruz Neto, (jxavierufpi.br)
O. P. Ferreira (orizonmat.ufg.br)
A. N. Iusem (iuspimpa.br)
R. D. C. Monteiro ( monteiroisye.gatech.edu)

Abstract: In this paper we consider the proximal point method with Bregman distance applied to linear programming problems, and study the dual sequence obtained from the optimal multipliers of the linear constraints of each subproblem. We establish the convergence of this dual sequence, as well as convergence rate results for the primal sequence, for a suitable family of Bregman distances. These results are obtained by studying first the limiting behavior of a certain perturbed dual path and then the behavior of the dual and primal paths.

Keywords: generalized proximal point methods, barrier function, Bregman distances, dual path, primal path, convergence of dual, dual convergence rate, primal convergence rate

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 3: Convex and Nonsmooth Optimization (Other )

Citation: Preprint

Download: [Postscript]

Entry Submitted: 03/13/2004
Entry Accepted: 03/15/2004
Entry Last Modified: 03/13/2004

Modify/Update this entry