17 Introduction to Evidence-Based Robust Optimisation
559
Furthermore, it is desirable to have a method that iteratively converges to the exact
value with a sequence of outer approximations.
In [20], Bel and P l functions were approximated, for any threshold ν ∈
[ν min , ν max ], with an Evolutionary Binary Tree (EBT ) algorithm. EBT consists
in an iterative bisection of the uncertainty space U , where U is the collection of all
the focal elements into a unit hypercube. The assumption is that focal elements are
formed from a number of disjoint or overlapping intervals along every dimension.
The mapping between the uncertainty space U and the unit hypercube U is given
by an affine transformation.
Every time a subset B i,j of U is bisected (where i represents the level of the tree
and j the index of the branch at level i) the maximum of f in one of two new halves
is computed. The other half inherits the maximum of f in B i,j . At every iteration,
subsets are pruned from the tree if the maxima belonging to those subset are below
the threshold ν and the cumulative bpa associated to those subsets is added to the
calculation of Bel. In the original formulation in [20] a subset was bisected along
the longest edge and along the extreme of the interval that was closest to the middle
point of the edge. Thus the partitioning rule was agnostic of the distribution of focal
elements.
The partition of the unit hypercube eventually reduces to all the focal elements
whose maxima are above the threshold ν. Hence this method eventually converges
to the true Bel and produces better and better outer approximations of its value as
the partitioning process progresses.
In [21] a more sophisticated and efficient partitioning scheme was proposed that
exploits the distribution of the maxima and the bpa associated to each focal element.
The method is based on the variance of the distribution of the maxima in the subsets
B i,j generated by the partitioning of U . The partitioning rule bisects the subset
along the edge (or dimension) where distribution of the maxima displays the highest
variance. The process is finally stopped when a maximum number of evaluations of
f is reached or when the difference between the value of Bel after two subsequent
iterations is below a given tolerance.
17.4.4 Outer Belief Estimation via Decomposition
In some cases the structure and nature of the function f can be exploited to
drastically reduce the computation of Bel(f ≤ ν) in (17.26). In particular, in this
section we consider the model introduced in [90] and the decomposition method
proposed in [90–92].
17.4.4.1 Evidence Network Models
Consider a generic complex system with N sub-systems connected with a known
topology. We model this complex system as a non-directed graph or network where
559
Furthermore, it is desirable to have a method that iteratively converges to the exact
value with a sequence of outer approximations.
In [20], Bel and P l functions were approximated, for any threshold ν ∈
[ν min , ν max ], with an Evolutionary Binary Tree (EBT ) algorithm. EBT consists
in an iterative bisection of the uncertainty space U , where U is the collection of all
the focal elements into a unit hypercube. The assumption is that focal elements are
formed from a number of disjoint or overlapping intervals along every dimension.
The mapping between the uncertainty space U and the unit hypercube U is given
by an affine transformation.
Every time a subset B i,j of U is bisected (where i represents the level of the tree
and j the index of the branch at level i) the maximum of f in one of two new halves
is computed. The other half inherits the maximum of f in B i,j . At every iteration,
subsets are pruned from the tree if the maxima belonging to those subset are below
the threshold ν and the cumulative bpa associated to those subsets is added to the
calculation of Bel. In the original formulation in [20] a subset was bisected along
the longest edge and along the extreme of the interval that was closest to the middle
point of the edge. Thus the partitioning rule was agnostic of the distribution of focal
elements.
The partition of the unit hypercube eventually reduces to all the focal elements
whose maxima are above the threshold ν. Hence this method eventually converges
to the true Bel and produces better and better outer approximations of its value as
the partitioning process progresses.
In [21] a more sophisticated and efficient partitioning scheme was proposed that
exploits the distribution of the maxima and the bpa associated to each focal element.
The method is based on the variance of the distribution of the maxima in the subsets
B i,j generated by the partitioning of U . The partitioning rule bisects the subset
along the edge (or dimension) where distribution of the maxima displays the highest
variance. The process is finally stopped when a maximum number of evaluations of
f is reached or when the difference between the value of Bel after two subsequent
iterations is below a given tolerance.
17.4.4 Outer Belief Estimation via Decomposition
In some cases the structure and nature of the function f can be exploited to
drastically reduce the computation of Bel(f ≤ ν) in (17.26). In particular, in this
section we consider the model introduced in [90] and the decomposition method
proposed in [90–92].
17.4.4.1 Evidence Network Models
Consider a generic complex system with N sub-systems connected with a known
topology. We model this complex system as a non-directed graph or network where