In my blog Weighted Sum Approach I have introduced the weighted sum approach and have explained what a convex multi-objective problem is. If a multi-objective problem is not convex it is known as a non-convex problem. In this blog I will give a quick overview of why the weighted sum approach might not be suited for finding an optimal value for this type of problem.
In Miettinen (1999) we learn that as long as we chose positive weights then we can find every point on the Pareto-optimal front for a convex problem. (The explanation of the Pareto-optimal front can be found in my blog Weighted Sum Approach). However this is not the case for non-convex problems. This means that the weighted sum approach can miss some of the points on our Pareto-optimal front. Therefore potentially missing a solution that gives us the best balance for the different problems we are trying to optimise. To explain this more clearly I will now give a 2 dimensional example.
As you can see in the figure below there are certain points on our Pareto-optimal front which we are unable to find in the objective space. We are unable to get to any of Pareto-optimal solutions between A and B. This is because any choice of weights will result in a line which will hit point A or B before any of the points between them. This means that we will find an optimal solution, but it may not be the best optimal solution, for the weights we have chosen.
This has shown the importance of looking at your multi-objective problem in detail before deciding on which method to use. For other methods that try to tackle the issue with non-convex multi-objective problems, I would recommend reading Deb (2008).
References:
- Deb, K. (2008). Multi-objective optimization using evolutionary algorithms.
- Miettinen, K. (1999). Nonlinear multiobjective optimization.
1 thought on “Issues with Weighted Sum Approach for Non-Convex Sets”