logo SBA

ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-01192023-150913


Thesis type
Tesi di laurea magistrale
Author
DE FRANCESCO, MATTEO
URN
etd-01192023-150913
Thesis title
An Asynchronous Ensemble Bundle Method
Department
INFORMATICA
Course of study
INFORMATICA
Supervisors
relatore Prof. Frangioni, Antonio
relatore van Ackooij, Wim
Keywords
  • Bundle Methods
  • Convex nondifferentiable optimization
  • Energy Optimization
  • Lagrangian Relaxation
  • Unit Commitment
Graduation session start date
24/02/2023
Availability
Full
Summary
Efficiently optimizing complex nondifferentiable functions, composed by a sum of a large number of terms the computation of each of which may be costly, is a crucial task in many applications such as energy optimization. The use of HPC architectures may be required to obtain appropriate performances, but the existing parallelisation approaches, mostly based on the standard master-slave paradigm, do not scale well to a large number of cores. This has justified the recent surge of interest in asynchronous approaches that may allow a higher scalability. We propose a very general asynchronous approach that exploits the availability of multiple resources not only for the "oracles" (black-box) that compute the function components, but also for the solution of multiple master problems, ran in parallel, to provide a stream of potential iterates for the oracles. Each of the master problems is in principle a separate algorithm, typically one of the many variants of bundle methods with some specific setting for its (numerous) algorithmic parameters, which would converge towards an (approximate) optimal solution if ran in isolation. We add to the mix a principal entity managing their interaction, thereby obtaining an "ensemble (asynchronous) bundle" approach, and we examine how different underlying algorithms can withstand interventions of the principal entity (such as information sharing, stability centre updates, and "near points" substitutions) aimed at fostering harmonious collaboration between them towards the goal of more efficiently solving the problem while retaining the good convergence properties that they originally had. We show how our approach can work with a very wide selection of the practical nondifferentiable optimization algorithms proposed in the literature. We test the performance of our ensemble bundle approach on a significant industrial application, i.e., Lagrangian relaxations of the Unit Commitment problem.
File