Supportedness in Multiobjective Optimization

虽然加权和标量化是求解多目标优化问题的一种流行方法，但众所周知，通常不是所有的解都能用这种方法找到，而只能找到支持的解。保证所有解的支撑性的一个标准假设是多目标问题的凸性。这个项目的第一个主要目标是识别比凸多目标问题大得多的一类问题，对于凸多目标问题，所有的解都被支持，因此可以通过加权和标量化来计算。我们称这样的多目标优化问题为支持的。由于上述凸性假设的本质结果是所谓的上像集的凸性，所以隐凸问题也具有所期望的性质，即尽管是非凸的，但仍具有凸上像集的问题。此外，即使上像集是非凸的，也可以支持多目标问题。我们的目的是为了更好地理解这类支持多目标优化问题，在上面的意义上，它是介于凸和一般非凸多目标优化之间的一类问题。在此背景下，我们还研究了多目标优化的松弛技术，如共正或半定重排。我们的目标是了解哪些松弛措施对多目标优化是有希望的，哪些松弛措施只在支持解中是紧的，也可以通过首先用加权和标量化，然后应用单目标松弛技术来获得。这个项目的第二个主要目的是基于这样的观察，即多目标问题的解的支持性不是一种内在属性，而是可以通过某种图像空间变换技术来加强对一些甚至所有解的支持。在深入研究这一技术之后，我们的目标是设计算法上可行的结构，将具有非支撑解的多目标问题归入支撑型问题。对于可能隐藏的问题，我们将其称为支持。这种变换技术允许基于支持度的算法的推广，如Benson方法和混合整数线性多目标问题的某些方法。这个项目的主要目的是探索支撑性的理论和算法方面，从隐凸性和隐支性的检测到松弛的准确性的研究，以及构造支撑点的算法的推广到无支撑点的情况。

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.