Navigation

Inhalt Hotkeys
Fakultät für Mathematik
Fakultät für Mathematik
Frank Fischer, Christoph Helmberg: A Parallel Bundle Framework for Asynchronous Subspace Optimisation of Nonsmooth Convex Functions

Frank Fischer, Christoph Helmberg: A Parallel Bundle Framework for Asynchronous Subspace Optimisation of Nonsmooth Convex Functions


Author(s):
Frank Fischer
Christoph Helmberg
Title:
Frank Fischer, Christoph Helmberg: A Parallel Bundle Framework for Asynchronous Subspace Optimisation of Nonsmooth Convex Functions
Electronic source:
application/pdf
Preprint series:
Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 08, 2013
Mathematics Subject Classification:
90C06 [large-scale problems]
65Y05 [parallel computation]
90C25 [convex programming]
65K05 [mathematical programming methods]
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
Language:
English
Publication time:
07/2013

Presseartikel