Asynchronous level bundle methods
- PDF / 693,020 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 41 Downloads / 246 Views
Series A
Asynchronous level bundle methods Franck Iutzeler1 · Jérôme Malick2 · Welington de Oliveira3 Received: 18 September 2018 / Accepted: 2 July 2019 © Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2019
Abstract In this paper, we consider nonsmooth convex optimization problems with additive structure featuring independent oracles (black-boxes) working in parallel. Existing methods for solving these distributed problems in a general form are synchronous, in the sense that they wait for the responses of all the oracles before performing a new iteration. In this paper, we propose level bundle methods handling asynchronous oracles. These methods require original upper-bounds (using upper-models or scarce coordinations) to deal with asynchronicity. We prove their convergence using variational-analysis techniques and illustrate their practical performance on a Lagrangian decomposition problem. Keywords Nonsmooth optimization · Level bundle methods · Distributed computing · Asynchronous algorithms Mathematics Subject Classification 90C25 · 90C30 · 65K05
B
Welington de Oliveira [email protected] Franck Iutzeler [email protected] Jérôme Malick [email protected]
1
Lab. J. Kuntzmann, UGA, Grenoble, France
2
Lab. J. Kuntzmann, CNRS, Grenoble, France
3
MINES ParisTech, PSL - Research University, CMA - Centre de Mathématiques Appliquées, Sophia Antipolis, France
123
F. Iutzeler et al.
1 Introduction: context, related work and contributions 1.1 Nonsmooth convex optimization and bundle methods We consider convex optimization problems of the form
f := min f (x) x∈X
with
f (x) :=
m
f i (x) ,
(1)
i=1
where the constraint set X is compact convex, and the functions f i : Rn → R (for all i = 1, . . . , m) are convex and possibly nonsmooth. Typically, nonsmoothness comes from the fact that the f i are themselves the results of inner optimization problems, as in Lagrangian relaxation (see e.g. [22]), in stochastic optimization (see e.g. [33]), or in Benders decomposition (see e.g. [14]). In such cases, the functions f i are known only implicitly through oracles providing values and subgradients (or approximations of them) for a given point. The so-called bundle methods are a family of nonsmooth optimization algorithms adapted to solve such problems. Using oracle information, these methods construct cutting-plane approximations of the objective function together with quadratic stabilization techniques. Bundle methods can be traced back to [21]; we refer to the textbook [16] and the recent surveys [12,32] for relevant references. Real-life applications of such methods are numerous, ranging from combinatorial problems [5] to energy optimization [6,31]. 1.2 Centralized distributed setting In this paper, we further consider the situation where (1) is scattered over several machines/oracles: each function f i corresponds to one oracle and associated local data. This scattering is due to the privacy of the data,
Data Loading...
