Approximation of Pareto surfaces in multicriteria optimization

In many practical optimization problems, several objectives need to be considered. A common task is to approximate the nondominated set which allows a decision maker to study the trade-offs between conflicting objectives.

In this thesis, the simplicial sandwiching algorithm, a well-known algorithm for the approximation of convex bounded nondominated sets, is analyzed, extended, and improved. In the first part, an analysis of the convergence behavior of the sandwiching algorithm is presented. Then, a method for the efficient computation of the approximation quality of approximations created by the sandwiching algorithm is derived which improves the sandwiching approximation time by up to 94%. In the last part, the ideas of the sandwiching algorithm are extended to the efficient approximation of multiple convex nondominated sets, which can arise from multiobjective mixed-integer convex optimization problems. An algorithm is introduced that exploits convexity and is applicable to general numbers of objective functions. Its performance is illustrated using several numerical examples.