226
A. Riccardi et al.
• Global or local: many algorithms for non-linear optimisation problems find only
a local solution, i.e. a point at which the objective function is smaller than
all the other feasible points in a neighbourhood. They do not always find the
global solution, which is the point that has the lowest function value among
all the points of the feasible region. Only for linear programming problems
and convex programming problems, the local solution is also the global one.
An objective function that presents a large number of local optima is called
multimodal function.
• Single- or multi- or many-objective: if the objective function is a scalar function,
that is
n obj = 1
the problem is said to be single-objective. In many engineering applications, one
is seeking a trade-off between different objectives; f is in this case a vectorial
function with
n obj > 1
and the problem is called a multi-objective optimisation problem (1 < n obj ≤ 3)
or many-objective optimisation problem (n obj > 3). Multi-objective optimisation problems can be transformed into single-objective problems, for example,
by means of aggregating functions, condensing all objectives in a single-cost
function with the use of weights coefficients, or by using alternatives such as
the −constrained, and the goal-attainment methods. More details are given in
Sect. 7.2.3.
To apply the most suitable algorithm, the problem must first be understood and
categorised. An algorithm suitable for linear problems may not be suitable for nonlinear problems, and vice versa. By incorrectly categorising a problem, an unsuitable
optimisation category can be chosen, leading to invalid results, for example, a
convex problem. This is a problem where the constraint functions are all convex,
all minimising objectives are convex, and all maximising objectives are concave.
These problems typically have only one optimal solution, and so every local solution
is also a global solution. Using a global algorithm on a convex problem is generally
computationally more expensive than a local one while still leading to the correct
solution.
When selecting an algorithm, it should be noted also that there is not a single
most effective algorithm that can be applied to all optimisation problems. Each
algorithm has benefits and drawbacks. The main theorem of optimisation, the no free
lunch theorem (NFL) [1]), states: if any algorithm A outperforms another algorithm
B in the search for an extreme of an objective function, then algorithm B will
outperform A over some other desired trait such as computational cost, accuracy
or complexity. The NFL theorem suggests that the average performance overall
possible objective functions is the same for all search algorithms. All algorithms
A. Riccardi et al.
• Global or local: many algorithms for non-linear optimisation problems find only
a local solution, i.e. a point at which the objective function is smaller than
all the other feasible points in a neighbourhood. They do not always find the
global solution, which is the point that has the lowest function value among
all the points of the feasible region. Only for linear programming problems
and convex programming problems, the local solution is also the global one.
An objective function that presents a large number of local optima is called
multimodal function.
• Single- or multi- or many-objective: if the objective function is a scalar function,
that is
n obj = 1
the problem is said to be single-objective. In many engineering applications, one
is seeking a trade-off between different objectives; f is in this case a vectorial
function with
n obj > 1
and the problem is called a multi-objective optimisation problem (1 < n obj ≤ 3)
or many-objective optimisation problem (n obj > 3). Multi-objective optimisation problems can be transformed into single-objective problems, for example,
by means of aggregating functions, condensing all objectives in a single-cost
function with the use of weights coefficients, or by using alternatives such as
the −constrained, and the goal-attainment methods. More details are given in
Sect. 7.2.3.
To apply the most suitable algorithm, the problem must first be understood and
categorised. An algorithm suitable for linear problems may not be suitable for nonlinear problems, and vice versa. By incorrectly categorising a problem, an unsuitable
optimisation category can be chosen, leading to invalid results, for example, a
convex problem. This is a problem where the constraint functions are all convex,
all minimising objectives are convex, and all maximising objectives are concave.
These problems typically have only one optimal solution, and so every local solution
is also a global solution. Using a global algorithm on a convex problem is generally
computationally more expensive than a local one while still leading to the correct
solution.
When selecting an algorithm, it should be noted also that there is not a single
most effective algorithm that can be applied to all optimisation problems. Each
algorithm has benefits and drawbacks. The main theorem of optimisation, the no free
lunch theorem (NFL) [1]), states: if any algorithm A outperforms another algorithm
B in the search for an extreme of an objective function, then algorithm B will
outperform A over some other desired trait such as computational cost, accuracy
or complexity. The NFL theorem suggests that the average performance overall
possible objective functions is the same for all search algorithms. All algorithms