Many optimization problems of practical interest arise from the discretization of continuous problems. Classical examples can be found in calculus of variations, optimal control and image processing. In recent years a number of strategies have been proposed for the solution of such problems, broadly known as multilevel methods. Inspired by classical multigrid schemes for linear systems, they exploit the possibility of solving the problem on coarser discretization levels to accelerate the computation of a finest-level solution. In this paper, we study the applicability of coordinate search algorithms in a multilevel optimization paradigm. We develop a multilevel derivative-free coordinate search method, where coarse-level objective functions are defined by suitable surrogate models. We employ a recursive v-cycle correction scheme, which exhibits multigrid-like error smoothing properties. On a practical level, the algorithm is implemented in tandem with a full-multilevel initialization. A suitable strategy to manage the coordinate search stepsize on different levels is also proposed, which gives a substantial contribution to the overall speed of the algorithm. Numerical experiments on several examples show promising results. The presented algorithm can solve large problems in a reasonable time, thus overcoming size and convergence speed limitations typical of coordinate search methods.

Coordinate search algorithms in multilevel optimization / E. Frandi; A. Papini. - In: OPTIMIZATION METHODS & SOFTWARE. - ISSN 1055-6788. - STAMPA. - 29:(2014), pp. 1020-1041. [10.1080/10556788.2013.841691]

Coordinate search algorithms in multilevel optimization

PAPINI, ALESSANDRA
2014

Abstract

Many optimization problems of practical interest arise from the discretization of continuous problems. Classical examples can be found in calculus of variations, optimal control and image processing. In recent years a number of strategies have been proposed for the solution of such problems, broadly known as multilevel methods. Inspired by classical multigrid schemes for linear systems, they exploit the possibility of solving the problem on coarser discretization levels to accelerate the computation of a finest-level solution. In this paper, we study the applicability of coordinate search algorithms in a multilevel optimization paradigm. We develop a multilevel derivative-free coordinate search method, where coarse-level objective functions are defined by suitable surrogate models. We employ a recursive v-cycle correction scheme, which exhibits multigrid-like error smoothing properties. On a practical level, the algorithm is implemented in tandem with a full-multilevel initialization. A suitable strategy to manage the coordinate search stepsize on different levels is also proposed, which gives a substantial contribution to the overall speed of the algorithm. Numerical experiments on several examples show promising results. The presented algorithm can solve large problems in a reasonable time, thus overcoming size and convergence speed limitations typical of coordinate search methods.
2014
29
1020
1041
E. Frandi; A. Papini
File in questo prodotto:
File Dimensione Formato  
OMS_CRETA_online.pdf

Accesso chiuso

Descrizione: Articolo principale
Tipologia: Pdf editoriale (Version of record)
Licenza: DRM non definito
Dimensione 419.16 kB
Formato Adobe PDF
419.16 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/827471
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 9
social impact