Epsilon-proximal decomposition method

Epsilon-proximal decomposition method

0.00 Avg rating0 Votes
Article ID: iaor20051092
Country: Germany
Volume: 99
Issue: 1
Start Page Number: 89
End Page Number: 108
Publication Date: Jan 2004
Journal: Mathematical Programming
Authors:
Abstract:

We propose a modification of the proximal decomposition method investigated by Spingarn and Mahey et al. for minimizing a convex function on a subspace. For the method to be favorable from a computational point of view, particular importance is the introduction of approximations in the proximal step. First, we couple decomposition on the graph of the epsilon-subdifferential mapping and cutting plane approximations to get an algorithmic pattern that falls in the general framework of Rockafellar inexact proximal-point algorithms. Recently, Solodov and Svaiter proposed a new proximal point-like algorithm that uses improved error criteria and an enlargement of the maximal monotone operator defining the problem. We combine their idea with bundle mechanism to devise an inexact proximal decomposition method with error condition which is not hard to satisfy in practice. Then, we present some applications favorable to our development. First, we give a new regularized version of Benders decomposition method in convex programming called the proximal convex Benders decomposition algorithm. Second, we derive a new algorithm for nonlinear multicommodity flow problems among which is the message routing problem in telecommunications data networks.

Reviews

Required fields are marked *. Your email address will not be published.