Artificial Intelligence and Data Analytics (AIDA) E-Learning Module

Introduction to Multi-
Objective Optimization

Dr. LI Bo
Department of Computing
The Hong Kong Polytechnic University
1
Roadmap

• What is Optimization?
• What is Multi-Objective Optimization?
• The History of Multi-Objective Optimization.
• Common Methods.
• Applications of Multi-Objective Optimization.

2
Optimization
• Life is about making decisions.

• We always attempt to make the “best” decision within a

specified set of possible decisions.

• Consider buying a computer?

3
Optimization
Objective: Max performance
• Consider buying a computer? Subject to: Budget-feasible
performance

optimal solution

cost
budget
4
Roadmap

• What is Optimization?
• What is Multi-Objective Optimization?
• The History of Multi-Objective Optimization.
• Common Methods.
• Applications of Multi-Objective Optimization.

5
 Multi-Objective Optimization
Multiple Objectives

performance Objective: Max 𝑓𝑓1 𝒙𝒙 , ⋯ , 𝑓𝑓𝑘𝑘 (𝒙𝒙)

Subject to: 𝒙𝒙 ∈ 𝒳𝒳

Feasibility Constraints

𝒳𝒳

portability
6
Multi-Objective Optimization

Objective 1: Max performance

Subject to: Budget-feasible

• In the single-objective optimization problem, the superiority

of a solution over other solutions is easily determined by
comparing their objective function values.

• How about multi-objective optimization problem?

 Multi-Objective Optimization
Objective 1: Max performance
• Consider buying a computer?
Objective 2: Max portability
performance
Subject to: Budget-feasible

vs

vs

𝒳𝒳 vs

portability
8
Multi-Objective Optimization
Objective 1: Max performance
Objective 2: Max portability
Subject to: Budget-feasible

• In multi-objective optimization problem, the goodness of a

solution is determined by the dominance:
Solution 𝑥𝑥1 (Pareto) dominates Solution 𝑥𝑥2 if
(1) 𝑥𝑥1 is no worse than 𝑥𝑥2 in all objectives, and
(2) 𝑥𝑥1 is strictly better than 𝑥𝑥2 in at least one objective.
Roadmap

• What is Optimization?
• What is Multi-Objective Optimization?
• The History of Multi-Objective Optimization.
• Common Methods.
• Applications of Multi-Objective Optimization.

10
Multicriteria Decision Making
• In 1881, King’s College (London) and later Oxford
Economics Prof. F.Y. Edgeworth is the first to
define an optimum for multicriteria economic
decision making.
• He does so for the multiutility problem within
the context of two consumers, P and 𝜋𝜋:

“It is required to find a point (𝑥𝑥, 𝑦𝑦) such that in whatever direction
we take an infinitely small step, P and 𝜋𝜋 do not increase together
but that, while one increases, the other decreases.”

Reference:
• Edgeworth, F.Y., Mathematical Psychics, P. Keagan, London, England, 1881.

11
Vilfredo Pareto
• Born in Paris in 1848 and graduated from the
University of Turin in 1870 with a degree in Civil
Engineering.

Thesis: “The Fundamental Principles of

Equilibrium in Solid Bodies”

• While working in Florence as a Civil Engineer from 1870-1893, Pareto

takes up the study of philosophy and politics and is one of the first to
analyze economic problems with mathematical tools.

12
 Vilfredo Pareto
• In 1893, Pareto becomes the Chair of Political
Economy at the University of Lausanne in
Switzerland, where he creates his two most famous
theories:
 Circulation of the Elites
 The Pareto Optimum
“The optimum allocation of the resources of a society is not
attained so long as it is possible to make at least one individual
better off in his own estimation while keeping others as well off as
before in their own estimation.”
Reference:
• Pareto, V., Manuale di Economia Politica, Societa Editrice Libraria, Milano, Italy, 1906.
Translated into English by A.S. Schwier as Manual of Political Economy, Macmillan, New
York, 1971.
13
 Extension to Engineering
• After the translation of Pareto’s Manual of Political
Economy into English, Prof. Wolfram Stadler of San
Francisco State University begins to apply the notion
of Pareto Optimality to the fields of engineering and
science in the middle 1970’s.
• The applications of multi-objective optimization in
engineering design grew over the following decades.

Reference:
• Stadler, W., “A Survey of Multicriteria Optimization, or the Vector Maximum Problem,” Journal of
Optimization Theory and Applications, 1979.
• Stadler, W. “Applications of Multicriteria Optimization in Engineering and the Sciences (A
Survey),” Multiple Criteria Decision Making –Past Decade and Future Trends, ed. M. Zeleny, JAI
Press, Greenwich, Connecticut, 1984.
• Ralph E. Steuer, “Multicriteria Optimization -Theory, Computation and Application”, 1985
14
Roadmap

• What is Optimization?
• What is Multi-Objective Optimization?
• The History of Multi-Objective Optimization.
• Common Methods.
• Applications of Multi-Objective Optimization.

15
Solutions
• Multiple Pareto optimal solutions.
• There are various ways to define "solving a multi-objective optimization
problem".

All are Pareto optimal solutions

Many methods convert multiple

objectives into a single-objective
-- scalarized problem.

16
Solutions

• When decision making is emphasized, the objective of solving a multi-

objective optimization problem is referred to supporting a decision
maker in finding the most preferred Pareto optimal solution according
to his/her subjective preferences.
 No preference methods: no decision maker is available, but a
neutral compromise solution is found without preferences.
 Priori methods: preferences are first asked from the decision
maker and then a solution best satisfying them is found.
 Posteriori methods: a representative set of Pareto optimal
solutions is first found and then the decision maker chooses one.
 Interactive methods: the decision maker is allowed to iteratively
search for the most preferred solution.

17
Roadmap

• What is Optimization?
• What is Multi-Objective Optimization?
• The History of Multi-Objective Optimization.
• Common Methods.
• Applications of Multi-Objective Optimization.

18
Finance
• In finance, a common problem is to choose a portfolio when there are
two conflicting objectives:
• the desire to have the expected value of portfolio returns be as
high as possible, and
• the desire to have risk, often measured by the standard deviation
of portfolio returns, be as low as possible.

• Efficient Frontier: the best

combinations of risk and
expected return that are
available.

19
Radio Resource Management
• The purpose of radio resource management is to satisfy the data rates
that are requested by the users of a cellular network.
• The main resources are time intervals, frequency blocks, and transmit
powers.

Each user has its own

objective function.

These objectives are

conflicting since the
frequency resources are
very scarce.

20
Inspection of Infrastructure
• Typically, planning inspection has been viewed as a single-objective
optimization problem, where one aims to minimize the energy or time
spent in inspecting an entire target structure.
• For complex, real-world structures, however, covering 100% of an
inspection target is not feasible, and generating an inspection plan may be
better viewed as a multi-objective optimization problem, where one aims
to both maximize inspection coverage and minimize time and costs.

21
Thank you!

22