Optimization Online


A Parallel Bundle Framework for Asynchronous Subspace Optimisation of Nonsmooth Convex Functions

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

Abstract: An algorithmic framework is presented for optimising general convex functions by non synchronised parallel processes. Each process greedily picks a suitable adaptive subset of coordinates and runs a bundle method on a corresponding restricted problem stopping whenever a descent step is encountered or predicted decrease is reduced sufficiently. No prior knowledge on the dependencies between variables is assumed. Instead, dependency information is collected automatically by analysing aggregate subgradient properties required for ensuring convergence. Within this framework three strategies are discussed for supporting varying scenarios of structural independence: a single convex function, the sum of partially separable convex functions, and a scenario tuned to problem decomposition by Lagrangian relaxation of packing type constraints. The theoretical framework presented here generalises a practical method proposed by the authors for Lagrangian relaxation of large scale packing problems and simplifies the analysis.

Keywords: bundle methods, parallel programming, convex optimisation

Category 1: Convex and Nonsmooth Optimization

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

Citation: Preprint 2013-8, Fakultaet fuer Mathematik, Technische Universitaet Chemnitz, D-09107, July 2013

Download: [PDF]

Entry Submitted: 07/03/2013
Entry Accepted: 07/03/2013
Entry Last Modified: 07/03/2013

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