Introduction Metrics BiMADS Other methods References

Multiobjective Optimization

MTH8418

S. Le Digabel, Polytechnique Montréal

Winter 2020
(v2)

MTH8418: Multiobjective 1/37

Introduction Metrics BiMADS Other methods References

Plan

Introduction

Metrics

BiMADS

Other methods

References

MTH8418: Multiobjective 2/37

Introduction Metrics BiMADS Other methods References

Introduction

Metrics

BiMADS

Other methods

References

MTH8418: Multiobjective 3/37

Introduction Metrics BiMADS Other methods References

Multiobjective optimization problem

I The multiobjective optimization problem (MOP) can be
formally stated as
min F (x)
x∈Ω
I where
F : Ω → {R ∪ {+∞}}p
and
F (x) = f (1) (x), f (2) (x), . . . , f (p) (x)

I p is the number of objective functions

I Case p = 2: Biobjective optimization problem (BOP)
I The feasible set Ω remains unchanged
I Typically, the different objectives are contradictory: A decrease
in one objective causes an increase in the other objectives
MTH8418: Multiobjective 4/37
Introduction Metrics BiMADS Other methods References

Difficulty

I Single-objective optimization: Particular case where p = 1. An

optimal solution typically consists of one single vector x ∈ Ω
I Multiobjective optimization: There is usually no such vector
that simultaneously minimizes all of the p ≥ 2 objective
functions
I The solution consists of a set of trade-off solutions in Ω, the
Pareto solutions
I The methods presented in this lesson construct an
approximation to this set

MTH8418: Multiobjective 5/37

Introduction Metrics BiMADS Other methods References

Pareto notion
I Single-objective: u, v ∈ Ω can be trivially ranked by
comparing f (u) and f (v)
I Generalization with p > 1:
I u dominates v, denoted u ≺ v, if and only if F (u) ≤ F (v) and
f (q) (u) < f (q) (v) for at least one index q in {1, 2, . . . , p}
I u is indifferent to v, denoted u ∼ v, if and only if u does not
dominate v and v does not dominate u

I A point u ∈ Ω is Pareto optimal if and only if there is no

w ∈ Ω such that w ≺ u
I The set of Pareto (optimal) solutions is the Pareto set ΩP
I The image of ΩP under the mapping F defines the solution to
the problem and is called the Pareto front FP ⊆ Rp
MTH8418: Multiobjective 6/37
Introduction Metrics BiMADS Other methods References

Pareto front example

f (2) 6
.................................................................................................................................
................................
.....................
c
.... ............................. ......
................. ........ ............. .................
.............. ....... ........
......... ...... .......
.... .
.........
. .... ..
..........
. ...... ..
................................................................................................ F (x ) 2 ..............
...
..........
. ...
................
..........................................................
.
.... .
..
c
.................
...
......
.....
....
......... .......... ... ....
.............
. ...
.............. .....F (x ) 1
....
....
......... .
......... .. ...
s
......
. ..... .. .
.
..
.. ..... . ...
c .
. . .
.....
..... ....
.......
. .
......
. F (Ω) ....
.. ...
s
..... ...... ........ ...
..
.. . ....
..... ......... F (x ) . ..... ...
x ∈Ω .
.... .
......
. . ... 3 ............
..
.. ..
2
c
......
..
..
.
.....
.
..
....
s
x ∈Ω3 ...
... ..................
............ .
..
.........................
......... .
. ..
.....
.
F (x )......... ...
. ....
..... ..
........... ..............
.
.........
...
..
..
.
...........
4 ..
..
.
.......................
............................................................. ................. ........ ........... ...
. ............ .
..
x s∈Ω
4....... x ∈Ω ........
.................
.. . ... . ..... .
......
..
.
........................................ 1 .......................... ......... .......
............................................................................................................................................................................................. ........ .........
.. .. ...........
Dominance zone ........... .. .
..............................

for F (x1 ) -
f (1)
Feasible region : Ω ⊂ R3 Image of Ω in objective space R2

MTH8418: Multiobjective 7/37

Introduction Metrics BiMADS Other methods References

Individual minima

The individual minima of F are the solutions to the

single-objective optimization problems
min f (q) (x) , for q ∈ {1, 2, . . . p}
x∈Ω

MTH8418: Multiobjective 8/37

Introduction Metrics BiMADS Other methods References

How to choose one solution?

I Can be done visually with p = 2 and some knowledge of the

problem. Large and small slopes should be identified

I For p ≥ 2, engineers use carpet plots

I More generally, this is the subject of multicriteria optimization

MTH8418: Multiobjective 9/37

Introduction Metrics BiMADS Other methods References

The ε-constraint method

I The most commonly used method

I It transforms objectives into constraints: The original problem

with p objectives becomes a problem with one objective and
p − 1 constraints

I Then, change the bounds on the constraints in order to grasp

the Pareto front

MTH8418: Multiobjective 10/37

Introduction Metrics BiMADS Other methods References

Weighted sums of objectives for BOP (p = 2)

Natural single-objective reformulation: Solve
min αf (1) (x) + (1 − α)f (2) (x) (1)
x∈Ω

Inconvenient: Some regions of the Pareto front are never optimal

for (1), regardless of α
MTH8418: Multiobjective 11/37
Introduction Metrics BiMADS Other methods References

Application: Constraint sensitivity analysis

I Biobjective optimization can be used in order to conduct
sensitivity analyses relative to constraints
I The constraint of interest is transformed as an objective
function
I The analysis of the approximated Pareto front allows to
interpret the impact of this constraint on the original objective
I Two different tools are available within NOMAD:
I A post-optimization analysis. Cheap and rough approximation
of the sensitivities
I An additional biobjective execution. More expensive, but gives
a good approximation of the sensitivities

MTH8418: Multiobjective 12/37

Introduction Metrics BiMADS Other methods References

Sensitivity analysis: Example

Sensitivity to x1−2 0
26.5

26.4
objective function value

26.3

26.2

26.1

26

25.9

25.8
−0.1 −0.05 0 0.05 0.1
constraint value

MTH8418: Multiobjective 13/37

Introduction Metrics BiMADS Other methods References

Introduction

Metrics

BiMADS

Other methods

References

MTH8418: Multiobjective 14/37

Introduction Metrics BiMADS Other methods References

Metrics
I [Audet et al., 2018]
I How to compare the approximations to the Pareto front
obtained by different solvers?
I S: Set of solvers; P: Set of problems

I To draw performance and data profiles, we need a

performance measure tp,s > 0 for each p ∈ P and s ∈ S
I Fp,s : Approximated Pareto front determined by the solver
s ∈ S for problem p ∈ P
I Fp : Approximated Pareto front for problem p. Obtained by
∪s∈S Fp,s and by removing the dominated points

MTH8418: Multiobjective 15/37

Introduction Metrics BiMADS Other methods References

Purity metric

I Purity metric:

|Fp,s ∩ Fp |
purityp,s = ∈ [0; 1]
|Fp,s |

I The higher the better

I Take tp,s = 1/purityp,s if purityp,s 6= 0, +∞ otherwise

I Problem: The purity is equal to one (i.e. perfect) for a solver

that gives only one non-dominated solution

MTH8418: Multiobjective 16/37

Introduction Metrics BiMADS Other methods References

Largest hole
I These measures compute the spread of an approximated
Pareto front with the maximum size of the “holes” in the
front. We need |Fp,s | > 1
 n o
(q) (q)
I tp,s = Γp,s = max max δi where δi
q∈{1,2,...,p} i∈{1,2,...,|Fp,s |}
represents the distance between the ith point of Fp,s and its
closest neighbor, in terms of f (q)

I HRS (Hole Relative Size): tp,s = max di /d where
i∈{1,2,...,|Fp,s |}
di represents the distance between the ith point of Fp,s and
P|Fp,s |
its closest neighbor, and d = i=1 di /|Fp,s |
v
u |Fp,s |
u P (d −d)2
t i
I Standard deviation: tp,s = i=1
|Fp,s |−1

MTH8418: Multiobjective 17/37

Introduction Metrics BiMADS Other methods References

Progress measures (1/2)

I These measures are focused on the convergence of the

methods. Useful for plotting simplified data profiles
I Progress for objective q ∈ {1, 2, . . . , p} at evaluation k:
r
(q)
(q) f1 (q)
progk = log (q) where fk represents the best value
fk
obtained after the kth evaluation, in terms of f (q)
I We need feasible starting solutions, and all objective values
need to be > 0
(q)
I We could consider tp,s = max {progk for s and p}
q∈{1,2,...,p}

MTH8418: Multiobjective 18/37

Introduction Metrics BiMADS Other methods References

Progress measures (2/2)

I Number of non-dominated points at each evaluation: For k

the number of evaluation or a group of n + 1 evaluations,
consider |Fp,s |
I Or consider the number of new non-dominated points
between two values of k
I Number of waves: Consider all the solutions produced by
solver s on problem p. Recursively remove the non-dominated
points, and W is the number of times that this operation is
necessary to consider all the points. The more W is close
to 1, the better is s

MTH8418: Multiobjective 19/37

Introduction Metrics BiMADS Other methods References

Generational Distance (GD)

I Measures a distance between Fp,s and Fp
q
P|Fp,s |
i=1 d2i,p
I GDp,s = |Fp,s |

I di,p represents the distance between the ith point in Fp,s and
the closest point of Fp
I The standard deviation of the GD measures the deformation
of the front obtained by s ∈ S compared to the global
P|Fp,s |
(di,p −GDp,s )2
approximation: ST DGDp,s = i=1
|Fp,s |−1

I Maximum Pareto Front Error: M Ep,s = max di,p

i∈{1,2,...,|Fp,s |}

MTH8418: Multiobjective 20/37

Introduction Metrics BiMADS Other methods References

Hypersurface for p = 2

Sp,s
I Consider tp,s = HSp,s = Sp

I Sp,s represents the surface under the plot of Fp,s and Sp the
surface under the plot of Fp

I Not easy to generalize/compute for p > 2 (hypervolume)

MTH8418: Multiobjective 21/37

Introduction Metrics BiMADS Other methods References

Introduction

Metrics

BiMADS

Other methods

References

MTH8418: Multiobjective 22/37

Introduction Metrics BiMADS Other methods References

BiMADS: Series of single-optimization executions

I [Audet et al., 2008]
I Based on a single-objective optimization algorithm: MADS
I MADS is launched on a series of subproblems
I Constraints are handled by MADS with EB/PB/PEB
techniques
I Each subproblem is obtained by a single-objective
reformulation that is not based on weights
I The solutions of each of these subproblems produces a local
approximation of the Pareto set
I The set of undominated solutions produces an approximation
of the entire Pareto set
I BiMADS is implemented in NOMAD
MTH8418: Multiobjective 23/37
Introduction Metrics BiMADS Other methods References

I Reference point in the objective space: r ∈ R2

I Reformulated objective:
 p
(rq − f (q) (x))2
Q


 − if F (x) ≤ r
q=1
φr (F (x)) := p
2
(f (q) (x) − rq )+
P
otherwise



q=1

I When minimized on x ∈ Ω, starting from xr (with

F (xr ) = r), it potentially gives a solution that dominates r

MTH8418: Multiobjective 24/37

Introduction Metrics BiMADS Other methods References

I Reference point in the objective space: r ∈ R2

I Reformulated objective:
 p
(rq − f (q) (x))2
Q


 − if F (x) ≤ r
q=1
φr (F (x)) := p
2
(f (q) (x) − rq )+
P
otherwise



q=1

I When minimized on x ∈ Ω, starting from xr (with

F (xr ) = r), it potentially gives a solution that dominates r
f (2) 6 φ. r >0
............
....
φr =0 ...
r ..

.....................................
φ <0
.............r
.........
.......
....
.................................. ....
........... ...
φ <0 ....... ...
r .....
.... ...
... ..
.. ..
.. .

- f (1)

MTH8418: Multiobjective 24/37

Introduction Metrics BiMADS Other methods References

I Reference point in the objective space: r ∈ R2

I Reformulated objective:
 p
(rq − f (q) (x))2
Q


 − if F (x) ≤ r
q=1
φr (F (x)) := p
2
(f (q) (x) − rq )+
P
otherwise



q=1

I When minimized on x ∈ Ω, starting from xr (with

F (xr ) = r), it potentially gives a solution that dominates r
f (2) 6 φ. r >0 f (2) 6
............
.... ...........................................
... ......... ........
φr =0 ....... .......
r ..
.....
..........
. ......
......
......
.....
.. .....
.....................................
φ <0
.............r .... ....
.........
....... .... ...
...
.... .....
.... ...
..................................
...........
....
... ......
...
....... ...
.... .
................................................... r
....... .
.... ..
..................... ........
φ <0 r .....
....
...
... ....
....
..
...
.. ............. .
.
... .. .... .....
.
..
.. . .......... .......
........
.....................................
.........
..
............
- f (1) ... - f (1)
I Every Pareto solution can be obtained with some r
MTH8418: Multiobjective 24/37
Introduction Metrics BiMADS Other methods References

Reference point selection

I Use the ordering property
inherent to p = 2 to compute
gaps between 3 successive
undominated solutions in the
objective space
I Choose r with the largest gap

I Associate a weight to r to
decrease the probability of
choosing it again and prevent
stalling when the Pareto front is
discontinuous

MTH8418: Multiobjective 25/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 c

I Initialization: -
Solve min f (q) (x) for q ∈ {1, 2} f (1)
x∈Ω

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 s c c
c c
c

I Initialization: -
Solve min f (q) (x) for q ∈ {1, 2} f (1)
x∈Ω

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 s c c
c c
c
c
c c
c
c
c s

I Initialization: -
Solve min f (q) (x) for q ∈ {1, 2} f (1)
x∈Ω

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 s c c
cs c
cs
c
sc c
c
sc
cs s

I Initialization: -
Solve min f (q) (x) for q ∈ {1, 2} f (1)
x∈Ω
I Main iterations:
I Reference point determination:
Use the set of feasible ordered undominated points generated
so far to generate a reference point r

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 s c c
cs c
cs
c r
...................................
............
........ sc c
................................
.....
.... c
.......... ...
.....
.... ... sc
...
...
... ... cs s
I Initialization:
-
Solve min f (q) (x) for q ∈ {1, 2}
x∈Ω f (1)
I Main iterations:
I Reference point determination:
Use the set of feasible ordered undominated points generated
so far to generate a reference point r
I Single-objective minimization:
Solve the subproblem min φr (F (x))
x∈Ω

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 s c
s
s r
c
...................................
............c s
cc ..c........c...
................................ s c ... c .
.......... ...
.....
. ... s
... ...
...
...
...
.
s s
I Initialization:
-
Solve min f (q) (x) for q ∈ {1, 2}
x∈Ω f (1)
I Main iterations:
I Reference point determination:
Use the set of feasible ordered undominated points generated
so far to generate a reference point r
I Single-objective minimization:
Solve the subproblem min φr (F (x))
x∈Ω

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 s c c
s c
c
c
s
c c
sc c c c
c
sc c
s
s s
I Initialization:
-
Solve min f (q) (x) for q ∈ {1, 2}
x∈Ω f (1)
I Main iterations:
I Reference point determination:
Use the set of feasible ordered undominated points generated
so far to generate a reference point r
I Single-objective minimization:
Solve the subproblem min φr (F (x))
x∈Ω

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

BiMADS: successive MADS runs

f (2) 6 s c c
s c
c
c
s
c c
sc c c c
c
sc c
s r
.........................................................
..............
........
s s
................................................... .....
I Initialization: ................
....
...
... -
Solve min f (q) (x) for q ∈ {1, 2}
x∈Ω f (1)
I Main iterations:
I Reference point determination:
Use the set of feasible ordered undominated points generated
so far to generate a reference point r
I Single-objective minimization:
Solve the subproblem min φr (F (x))
x∈Ω

MTH8418: Multiobjective 26/37

Introduction Metrics BiMADS Other methods References

MultiMADS
I [Audet et al., 2010]
I Based on the natural boundary intersection (NBI) framework,
and the convex hull of individual minima
I Consider the simplex {g (1) , g (2) , g (3) } obtained from the
individual minima

MTH8418: Multiobjective 27/37

Introduction Metrics BiMADS Other methods References

MultiMADS: Example of solution

MTH8418: Multiobjective 28/37

Introduction Metrics BiMADS Other methods References

Convergence analysis
I MADS solves the single objective subproblems
I These solutions x̂ are such that if φr (F (.)) is Lipschitz near x̂,
then φ◦r (F (x̂); d) ≥ 0 for every direction d in the hypertangent
cone TΩH (x̂) to the domain Ω at x̂
I Every Pareto point is the optimal solution of a reformulation

I Let x̂ ∈ Ω be a refining point produced by MADS on a

single-objective subproblem for some r ∈ Rp . If F is Lipschitz
near x̂, then for any direction d ∈ TΩH (x̂), there exists a

◦
q ∈ {1, 2, . . . , p} such that f (q) (x̂; d) ≥ 0
I When the functions are regular, it means that moving in a
feasible direction deteriorates at least one objective: This is a
tradeoff solution (Pareto)
MTH8418: Multiobjective 29/37
Introduction Metrics BiMADS Other methods References

Introduction

Metrics

BiMADS

Other methods

References

MTH8418: Multiobjective 30/37

Introduction Metrics BiMADS Other methods References

Direct Multisearch (DMS)

I [Custódio et al., 2011]
I Native adaptation of GPS to the unconstrained multiobjective
case (p ≥ 2 and use of the EB)
I Intensification with a poll step in which the acceptation
criteria are based on the Pareto dominance
I Diversification with a search step
I Convergence based on the Clarke derivatives
I Differences with biMADS and multiMADS:
I BiMADS is a framework using MADS in a subproblem while
DMS is a native multiobjective method
I At each step, DMS tries to improve the entire front, while
biMADS focuses on a specific part of it

MTH8418: Multiobjective 31/37

Introduction Metrics BiMADS Other methods References

NSGA-II
I NSGA-II: Non-dominated Sorting Genetic Algorithm, for BOP
(p ≥ 2) [Deb et al., 2002]
I Constraints are treated with the inclusion of the violation in
the dominance relation
I Each objective parameter is treated separately
I Mutation and crossover are performed on the population
I Selection based on “non-dominated sorting” (intensification),
and “crowded-distance sorting” (diversification)
I Heuristic: No guarantee on the quality of the approximated
Pareto front
I From the same team: Archive-based Micro Genetic Algorithm
(AMGA) [Tiwari et al., 2008]
MTH8418: Multiobjective 32/37
Introduction Metrics BiMADS Other methods References

Multiobjective solvers
I NOMAD (p = 2)

I NSGA-II: Several implementations can be found:

I MATLAB version
I C versions

I AMGA2 [Tiwari et al., 2011]

I DMS: MATLAB version (by email)

I DFL toolbox:
I DFMO: Linesearch, constraints, FORTRAN
I MODIR: DIRECT, constraints, FORTRAN
I MOIF: Implicit filtering, bounds, MATLAB

MTH8418: Multiobjective 33/37

Introduction Metrics BiMADS Other methods References

Introduction

Metrics

BiMADS

Other methods

References

MTH8418: Multiobjective 34/37

Introduction Metrics BiMADS Other methods References

References I
Audet, C., Bigeon, J., Cartier, D., Le Digabel, S., and Salomon, L. (2018).
Performance indicators in multiobjective optimization.
Technical Report G-2018-90, Les cahiers du GERAD.

Audet, C., Dennis, Jr., J., and Le Digabel, S. (2012).

Trade-off studies in blackbox optimization.
Optimization Methods and Software, 27(4–5):613–624.
(Constraint Sensitivity Analysis).

Audet, C., Savard, G., and Zghal, W. (2008).

Multiobjective Optimization Through a Series of Single-Objective Formulations.
SIAM Journal on Optimization, 19(1):188–210.
(biMADS).

Audet, C., Savard, G., and Zghal, W. (2010).

A mesh adaptive direct search algorithm for multiobjective optimization.
European Journal of Operational Research, 204(3):545–556.
(multiMADS).

Collette, Y. and Siarry, P. (2002).

Optimisation multiobjectif.
Eyrolles.
(metrics).

MTH8418: Multiobjective 35/37

Introduction Metrics BiMADS Other methods References

References II
Custódio, A., Madeira, J., Vaz, A., and Vicente, L. (2011).
Direct multisearch for multiobjective optimization.
SIAM Journal on Optimization, 21(3):1109–1140.
(DMS, metrics, profiles).

Das, I. and Dennis, Jr., J. (1998).

Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria
Optimization Problems.
SIAM Journal on Optimization, 8(3):631–657.
(NBI).

Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).

A fast and elitist multiobjective genetic algorithm: NSGA-II.
IEEE Transactions on Evolutionary Computation, 6(2):182–197.

E.F.Campana, M.Diez, G.Liuzzi, S.Lucidi, R.Pellegrini, V.Piccialli, F.Rinaldi, and A.Serani (2018).
A Multi-objective DIRECT algorithm for ship hull optimization.
Computational Optimization and Applications, 71(1):53–72.
(MODIR).

G.Cocchi, G.Liuzzi, A.Papini, and M.Sciandrone (2018).

An implicit filtering algorithm for derivative-free multiobjective optimization with box constraints.
Computational Optimization and Applications, 69(2):267–296.
(MOIF).

MTH8418: Multiobjective 36/37

Introduction Metrics BiMADS Other methods References

References III
Laumanns, M., Zitzler, E., and Thiele, L. (2000).
A Unified Model for Multi-Objective Evolutionary Algorithms with Elitism.
In Congress on Evolutionary Computation, volume 1, pages 46–53, Piscataway, New Jersey, USA.
(metrics).

Liuzzi, G., Lucidi, S., and Rinaldi, F. (2016).

A Derivative-Free Approach to Constrained Multiobjective Nonsmooth Optimization.
SIAM Journal on Optimization, 26(4):2744–2774.
(DFMO).

Tiwari, S., Fadel, G., and Deb, K. (2011).

AMGA2: improving the performance of the archive-based micro-genetic algorithm for multi-objective
optimization.
Engineering Optimization, 43(4):377–401.

Tiwari, S., Koch, P., Fadel, G., and Deb, K. (2008).

AMGA: An Archive-based Micro Genetic Algorithm for Multi-objective Optimization.
In Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, GECCO ’08,
pages 729–736, New York, NY, USA. ACM.

Zitzler, E., Deb, K., and Thiele, L. (2000).

Comparison of Multiobjective Evolutionary Algorithms: Empirical Results.
Evolutionary Computation, 8(2):173–195.
(metrics).

MTH8418: Multiobjective 37/37