7 Introduction to Optimisation
237
an initial box and to delete the sub-boxes that cannot contain the global solution
by a branch-and-bound procedure. The process terminates, when the bounds on
the solutions and on the global minimum are below a predefined tolerance. The
main drawback of the interval approach is its computational complexity. It is
applicable to MINLP problems and non-smooth functions.
On the other hand, there is no proof of exactness for the following global
deterministic strategy.
• Sequential improvements of local optima [16]: the basic idea is to generate an
improving sequence of local minima. Deflection techniques, tunnelling and filled
function methods are examples of this approach. The tunnelling method consists
of two phases: seek for a local minimum and apply a tunnelling function to find a
point in the domain that has the same value of the objective function. The newly
formed point is the starting point for the next iteration. The process terminates
when it is not possible to detect any point during the second phase. The last
found local optimum is also the global one. There is no rigorously established
convergence theory associated with these methods, and they are applicable only
to smooth continuous optimisation problems.
7.2.2.2 Stochastic Strategies
Stochastic strategies are methods that contain not deterministic elements, either
random generated algorithm parameters or stochastic approximations of model
functions. As expected it is difficult to develop a rigorous convergence theory for
such a class of algorithms, due to the randomness introduced in the optimisation
process. However two of them provide a convergence proof based on probabilistic
theories, and they can be classified as exact methods.
• Random search methods [17]: the objective of these search methods is to
find the global minimum with an adaptive-probabilistic distribution of random
points over the feasible region. These algorithms ensure that the global minimum
will be found with probability one as the sample size grows to infinity. The
difference to the deterministic grid search algorithm lies in its adaptivity. The
number of experimental points doesn’t need to be decided in advance, but it is
generated in the successive steps. These methods are applicable to both discrete
and continuous global optimisation problems with very mild assumptions on the
model regularity.
• Random function approach [18, 19]: also known in literature as Bayesian
methods, they are the stochastic counterpart of the sequential approximation
approach with an adaptive probabilistic model for the approximation of the
objective function. They are suitable for cost functions that have a highly
computational load. They can deal with continuous and discrete variables and
non-smooth functions. A theoretical convergence to the global optimum is
guaranteed only by generating a dense set of search points.
237
an initial box and to delete the sub-boxes that cannot contain the global solution
by a branch-and-bound procedure. The process terminates, when the bounds on
the solutions and on the global minimum are below a predefined tolerance. The
main drawback of the interval approach is its computational complexity. It is
applicable to MINLP problems and non-smooth functions.
On the other hand, there is no proof of exactness for the following global
deterministic strategy.
• Sequential improvements of local optima [16]: the basic idea is to generate an
improving sequence of local minima. Deflection techniques, tunnelling and filled
function methods are examples of this approach. The tunnelling method consists
of two phases: seek for a local minimum and apply a tunnelling function to find a
point in the domain that has the same value of the objective function. The newly
formed point is the starting point for the next iteration. The process terminates
when it is not possible to detect any point during the second phase. The last
found local optimum is also the global one. There is no rigorously established
convergence theory associated with these methods, and they are applicable only
to smooth continuous optimisation problems.
7.2.2.2 Stochastic Strategies
Stochastic strategies are methods that contain not deterministic elements, either
random generated algorithm parameters or stochastic approximations of model
functions. As expected it is difficult to develop a rigorous convergence theory for
such a class of algorithms, due to the randomness introduced in the optimisation
process. However two of them provide a convergence proof based on probabilistic
theories, and they can be classified as exact methods.
• Random search methods [17]: the objective of these search methods is to
find the global minimum with an adaptive-probabilistic distribution of random
points over the feasible region. These algorithms ensure that the global minimum
will be found with probability one as the sample size grows to infinity. The
difference to the deterministic grid search algorithm lies in its adaptivity. The
number of experimental points doesn’t need to be decided in advance, but it is
generated in the successive steps. These methods are applicable to both discrete
and continuous global optimisation problems with very mild assumptions on the
model regularity.
• Random function approach [18, 19]: also known in literature as Bayesian
methods, they are the stochastic counterpart of the sequential approximation
approach with an adaptive probabilistic model for the approximation of the
objective function. They are suitable for cost functions that have a highly
computational load. They can deal with continuous and discrete variables and
non-smooth functions. A theoretical convergence to the global optimum is
guaranteed only by generating a dense set of search points.