Talk
Using Scalarizations for the Approximation of Multiobjective Optimization Problems
Both exact and approximate solution methods for multiobjective optimization problems are often based on scalarizations that transform multiobjective problems into singleobjective auxiliary problems based on procedures that might use additional parameters, auxiliary points, or variables. The resulting scalarized optimization problems are then solved using methods from singleobjective optimization and the obtained solutions are interpreted in the context of the original multiobjective problem.
In this talk, we study the approximation of general multiobjective optimization problems with the help of scalarizations. We first focus on the weighted sum scalarization, which is probably the best-known and most widely used scalarization technique in multiobjective optimization, and provide a precise analysis of the approximation quality obtainable by means of this scalarization for both minimization and maximization problems. In particular, we show that, while minimization problems can be approximated well by means of the weighted sum scalarization, strong impossibility results can be shown for maximization problems.
Afterwards, we turn to general scalarizations. Motivated by the above impossibility result concerning approximations of maximization problems based the weighted sum scalarization and similar impossibility results that are known for other scalarizations in the literature, we investigate whether there are intrinsic structural differences between minimization and maximization problems with respect to approximation via scalarizations. Here, countering the known impossibility results for maximization problems, we show that all multiobjective optimization problems can, in principle, be approximated equally well by scalarizations. In this context, we introduce a transformation theory for scalarizations that establishes the following: Suppose there exists a scalarization that yields an approximation of a certain quality for arbitrary instances of multiobjective optimization problems with a given decomposition specifying which objective functions are to be minimized / maximized. Then, for each other decomposition, our transformation yields another scalarization that yields the same approximation quality for arbitrary instances of problems with this other decomposition. In this sense, the existing results about the approximation via scalarizations for minimization problems carry over to any other objective decomposition – in particular, to maximization problems – when suitably adapting the employed scalarization.
Last modified: 28.06.2023
