Supportedness in Multiobjective Optimization

点击翻译按钮获取中文摘要

Although weighted sum scalarization is a popular method to find solutions of multiobjective optimization problems, it is well-known that in general not all solutions can be found this way, but only the supported ones. A standard assumption for guaranteeing the supportedness of all solutions is the convexity of the multiobjective problem. The first main aim of this project is to identify a significantly larger class than convex multiobjective problems, for which all solutions are supported and can thus be computed by weighted sum scalarization. We call such multiobjective optimization problems supported. Since the essential consequence of the above convexity assumption is the convexity of the so-called upper image set, also hidden convex problems possess the desired property, by which we mean problems which possess a convex upper image set despite being nonconvex. Moreover, a multiobjective problem may even be supported although the upper image set is nonconvex. We aim at a better understanding of the class of supported multiobjective optimization problems which, in the above sense, is a category between convex and general nonconvex multiobjective optimization. In this context we also study relaxation techniques, like copositive or semidefinite reformulations, for multiobjective optimization. We aim on understanding which relaxations may be promising for multiobjective optimization and which are tight in the supported solutions only and can also be obtained by first scalarizing with a weighted sum and then applying single-objective relaxation techniques. The second main aim of this project bases on the observation that supportedness of solutions of multiobjective problems is not an intrinsic property but may be enforced by a certain image space transformation technique for some or even for all solutions. After a thorough study of this technique, we aim at designing algorithmically feasible constructions which move multiobjective problems with nonsupported solutions into the class of supported problems. We call problems for which this is possible hidden supported. The transformation technique admits generalizations of algorithms based on supportedness like Benson's method and certain approaches for mixed-integer linear multiobjective problems. This leads in particular to the generation of nonlinear cuts which may promote tighter bounds in branch-and-bound frameworks.This the main aims of the project are to explore theoretical and algorithmic aspects of supportedness, ranging from the detection of hidden convexity and of hidden supportedness to the investigation of exactness of relaxations as well as the generalization of algorithms for the construction of supported efficient points to the case of nonsupported ones.