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
