Optimization Online


A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

Frank Fischer(frank.fischer***at***mathematik.tu-chemnitz.de)
Christoph Helmberg(helmberg***at***mathematik.tu-chemnitz.de)

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

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Preprint 2012-2, Fakultät für Mathematik, Technische Universität Chemnitz, D-09107 Chemnitz, February 2012

Download: [PDF]

Entry Submitted: 02/16/2012
Entry Accepted: 02/16/2012
Entry Last Modified: 02/16/2012

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 Optimization Society