236
A. Riccardi et al.
optimum. The success of the local search obviously depends on the finesse of the
search grid, and global convergence can be trivially guaranteed by the fact that
the mesh can be made arbitrarily dense. Such a simple scheme however rapidly
becomes inefficient with the enlargement of the bounds on the optimisation
variables and the raising of the dimension. The computational load will increase
as an exponential function of the dimensionality of the problem.
• Complete (enumerative) search [5]: it is based on the simple principle of
searching through all potentially optimum points in the search space, through
enumeration of the possible candidates and evaluation of the objective. If, for
example, the feasible region D is a polyhedra and the objective function is
concave, then it is possible to prove that the problem must have a global optimal
solution which is a corner of D. Since D has a finite number of extreme points,
the problem could be solved by enumerating the extreme points of D in an
appropriate way until an optimal solution is found [10]. Enumerative methods
have few applications in continuous optimisation. Convergence properties are
trivially provable.
• Homotopy and trajectory methods [11, 12]: the two strategies have the
ambitious objective of visiting all stationary points of the objective function on
the feasible domain, tracing the paths on the feasible space that include them.
The solutions are then explored through enumeration techniques and evaluation
of the objective. The two methods differ in the way of constructing their paths: the
homotopy method makes use of homotopy transformations between the solution
of a simplified problem and the original one; the trajectory problem solves a set
of ordinary differential equations. The methodologies are applicable to smooth
problems with continuous variables, and the enumeration techniques employed
guarantee convergence to the optimum.
• Sequential approximation (relaxation) methods [13]: the idea is to build and
solve a series of approximate (or relaxed) optimisation subproblems converging
to the exact (or approximate) global optimum. A classification of such methods
is based on the target of the approximation (relaxation), either specific model
parameters or the entire system and subsystem models in a non-decomposed or
decomposed problem, and the method employed to perform the approximated
model fitting (response surface methodology (RSM), Taguchi methods, kriging
[14]). The methods can be applied to a wide range of optimisation problems
with continuous and discrete variables, and they are particularly suitable for
expensive or noisy simulation models as a complete analysis is performed
only in the experimental data points of the metamodeling techniques. The
methods form a subset of the derivative-free optimisation techniques, based on
model approximation, as they are completely free from derivative computation
or approximation. Method-specific convergence theories are available in the
suggested reference.
• Interval arithmetic methods [15]: it is possible to develop a complete theory
based on interval entities analogous to the real one. The strength of exploiting the
global information over large domains given by interval analysis in optimisation
methods ensures the convergence to all global optima. The idea is to start with
A. Riccardi et al.
optimum. The success of the local search obviously depends on the finesse of the
search grid, and global convergence can be trivially guaranteed by the fact that
the mesh can be made arbitrarily dense. Such a simple scheme however rapidly
becomes inefficient with the enlargement of the bounds on the optimisation
variables and the raising of the dimension. The computational load will increase
as an exponential function of the dimensionality of the problem.
• Complete (enumerative) search [5]: it is based on the simple principle of
searching through all potentially optimum points in the search space, through
enumeration of the possible candidates and evaluation of the objective. If, for
example, the feasible region D is a polyhedra and the objective function is
concave, then it is possible to prove that the problem must have a global optimal
solution which is a corner of D. Since D has a finite number of extreme points,
the problem could be solved by enumerating the extreme points of D in an
appropriate way until an optimal solution is found [10]. Enumerative methods
have few applications in continuous optimisation. Convergence properties are
trivially provable.
• Homotopy and trajectory methods [11, 12]: the two strategies have the
ambitious objective of visiting all stationary points of the objective function on
the feasible domain, tracing the paths on the feasible space that include them.
The solutions are then explored through enumeration techniques and evaluation
of the objective. The two methods differ in the way of constructing their paths: the
homotopy method makes use of homotopy transformations between the solution
of a simplified problem and the original one; the trajectory problem solves a set
of ordinary differential equations. The methodologies are applicable to smooth
problems with continuous variables, and the enumeration techniques employed
guarantee convergence to the optimum.
• Sequential approximation (relaxation) methods [13]: the idea is to build and
solve a series of approximate (or relaxed) optimisation subproblems converging
to the exact (or approximate) global optimum. A classification of such methods
is based on the target of the approximation (relaxation), either specific model
parameters or the entire system and subsystem models in a non-decomposed or
decomposed problem, and the method employed to perform the approximated
model fitting (response surface methodology (RSM), Taguchi methods, kriging
[14]). The methods can be applied to a wide range of optimisation problems
with continuous and discrete variables, and they are particularly suitable for
expensive or noisy simulation models as a complete analysis is performed
only in the experimental data points of the metamodeling techniques. The
methods form a subset of the derivative-free optimisation techniques, based on
model approximation, as they are completely free from derivative computation
or approximation. Method-specific convergence theories are available in the
suggested reference.
• Interval arithmetic methods [15]: it is possible to develop a complete theory
based on interval entities analogous to the real one. The strength of exploiting the
global information over large domains given by interval analysis in optimisation
methods ensures the convergence to all global optima. The idea is to start with