Optimization Online


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

J. X. Cruz Neto, (jxavier***at***ufpi.br)
O. P. Ferreira (orizon***at***mat.ufg.br)
A. N. Iusem (iusp***at***impa.br)
R. D. C. Monteiro ( monteiro***at***isye.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society