Multi-Objective Optimization (MOO)
Optimization is finding the best solution out of many possible solutions, in order to achieve some objective. In many real-life situations, often we have more than one objective to achieve at the same time. However, it is usually impossible to have one unique optimal solution in a multi-objective setting.
Problems like, how can we maximize return while minimizing risk in investment? Which is the fastest route to reach my destination with the minimum cost? How can I design a machine learning algorithm that gives the best accuracy while preventing overfitting? When we have more than one objective, usually we have no single best solution — we need to consider trade-offs between the objectives. This is when multi-objective optimization comes into play. In this article, I will discuss the basic concepts of multi-objective optimization. Let’s get started!
Single-objective optimization
Let’s assume that we have an objective to achieve, expressed by f1 below:
To solve min f1, we need to find the values of x1 and x2 that give the minimum of the objective function f1. The objective function is just an equation of a circle, and we can quickly identify that the best solution is x1 = 5 and x2 = 5, which gives f1 = 0.
Two-objective optimization
Let’s say we have another objective to achieve, to minimize f2:
Again, we can easily identify that the best solution is x1 = 10 and x2 = 10 which gives f2 = 0. However, if we consider the two objectives together, f1 and f2, we soon notice that no solution gives f1 = 0 and f2 = 0 at the same time. The best solution to f1 is not the best solution to f2 and vice versa. Unfortunately, we can’t have the best from both simultaneously in this case. If you find it hard to visualize, imagine that we are playing the game of archery — however, with two targets. You can’t have two bullseyes in one shot, can you?
A Pareto Optimal Solution
While we can’t have one unique optimal solution, we can have a set of Pareto optimal solutions. Having a Pareto optimal solution means that we are in a situation where we can’t improve one objective without sacrificing another. In the figure below, let us look at an example of a Pareto optimal solution, point A.(I’ll explain how to get Pareto optimal solutions later on).
Standing at point A (x1 = 8, x2 = 8), we get f1 = 18 and f2 = 8. If we move our solution closer to (x1 = 5, x2 = 5), we will improve f1 but sacrifice f2. Similarly, if we move our solution closer to (x1 = 10, x2 = 10), we will improve f2 at the expense of f1. There is no other solution that improves both f1 and f2 simultaneously.
A Non-Pareto Optimal Solution
On the other hand, we want to avoid getting non-Pareto optimal solutions. Having a non-Pareto optimal solution means that we can still find a better solution to improve one or more objectives without sacrificing any other. Solution point B in the figure below is an example of a non-Pareto optimal solution.
Standing at point B (x1 = 10, x2 = 5), we get f1 = 25 and f2 = 25. Notice that we can move closer to (x1 = 5, x2 = 5) and (x1 = 10, x2 = 10), and improve both f1 and f2 at the same time. This means that we can have better solutions than B. Comparing solution A (Pareto optimal) and solution B (non-Pareto optimal), we can also see that solution A is better as it gives better objective value for both f1 and f2. Note the following terminologies:
- Solution A is Pareto optimal. (There is no other solution where one objective can improve without sacrificing another)
- Solution B is not Pareto optimal. (There exists better solution(s) where one or more objective values can improve without sacrificing another)
- Solution A dominates solution B.
- Solution A is a Pareto improvement to solution B.
- The set of all Pareto optimal solutions is called a Pareto frontier.
Finding Pareto Optimal Solutions
The goal of multi-objective optimization is to find (or approximate) a set of Pareto optimal solutions, use it to construct the Pareto frontier (the trade-off curve), then choose a solution that matches our preference. There are many ways to find Pareto optimal solutions. Few classical approaches are the weighted sum method and the e-constraint method. Note that we do not discuss non-convex multi-objective optimization problems here (which can involve heuristics).
Using the weighted sum method, let us try to solve our two-objective archery problem. First, we assign a weight to each objective function. Then, we aggregate the objectives into a single objective function and solve the weighted sum. The value of the weights, w, generally reflects the importance of the objectives:
If all the weights are equal, i.e. w1 = w2, then all the objectives have the same importance. Usually, we don’t solve the problem once, but we alter the weights systematically in many iterations to obtain a set of Pareto optimal solutions. For example, for the first iteration, we can set w1 = 0.0 and w2 = 1.0; for the second iteration, we can set w1 = 0.2 and w2 = 0.8; and so on. Then, we will get a set of Pareto optimal solutions out of the iterations with varying weights. You don’t have to solve the problem by hand — see how I solved it with Python here. Let’s skip to the good part.
After 6 iterations of varying weights, we have arrived at 6 different solutions:
Plotting the solutions:
Visualizing the Trade-Off
It’s time to make a decision! Now that we have 6 solutions to choose from, we can visualize the trade-off curve, known as the Pareto frontier, by plotting the objective values of f1 and f2 we obtained in the previous step. Have a look at the figure below. Notice that moving from one solution to the other will improve one objective at the expense of another objective. Are you willing to lose more from f1 to achieve better f2? Do you want to treat both f1 and f2 equally? I’ll leave it to you to pick your final solution. Have fun exploring!
Recap
In this article, we discussed the concept of multi-objective optimization and looked into an example with two objectives. Then, we took a step further to understand Pareto optimality and how we can obtain Pareto optimal solutions. Finally, we visualize the trade-off curve by plotting the Pareto Frontier. In my next article, I’ll demonstrate a use case of multi-objective optimization using real-life data with Python. Too-da-loo!
