Frank Fischer, Christoph Helmberg: A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

Author(s):

Frank Fischer
Christoph Helmberg

Title:

Frank Fischer, Christoph Helmberg: A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

Electronic source:

application/pdf

Preprint series:

Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 02, 2012

Mathematics Subject Classification:

90C06	[Large-scale problems]
65Y05	[Parallel computation]
90C25	[Convex programming]
65K05	[Mathematical programming methods]

Abstract:

An algorithmic approach is proposed for exploiting parallelization possibilities in large scale optimization models of the following generic type. Objects change their state over time subject to a limited availability of common resources. These are modeled by linear coupling constraints and result in few objects competing for the same resource at each point in time. In a kind of asynchronous parallel coordinate descent, each independent process iteratively picks a free subset of violated constraints together with their interacting objects, improves the corresponding Lagrange multipliers by a bundle method to a certain level, and stores observed presumable dependencies leading to increased violation of other constraints in a common dependency graph. These dependencies have to be respected in future subset selections. No synchronization is required between the processes, for each subproblem the number of evaluations may differ arbitrarily. Under the assumption of boundedness of the set of dual optimizers we prove convergence of appropriate subsequences of the iterates to primal and dual optimal solutions of the relaxation. Preliminary computational results indicate that this approach may develop into a viable alternative to classical bundle methods using parallel evaluations.

Keywords:

bundle methods, parallel programming, Lagrangian relaxation

Language:

English

Publication time:

02/2012