General approximation methods for multicriteria optimization problems

在许多优化问题中，需要同时优化多个不可通约的目标函数。这样的多目标优化问题是基于由排序关系诱导的最优性概念。最主要的概念是Pareto最优性的概念，它将最优解描述为相对于分量排序的最小值(或最大值)。然而，对于许多优化问题，Pareto最优解的集合和对应的映象集都很大，很难精确计算。因此，我们的建议旨在开发多准则优化问题的近似方法，这些方法(1)适用于弱假设，(2)产生可证明的良好的逼近质量，(3)具有可证明的最坏情况运行时间。申请者通过他们在多准则优化和近似算法方面的互补技能为这一目标作出贡献，并能够在以前的联合工作的基础上再接再厉。众所周知，现有的几种逼近多目标极小化问题的方法不能转化为极大化问题。最小化和最大化问题需要不同的技术。此外，帕累托最优性的概念意味着双目标优化问题和一般多目标优化问题在难度上的显著差异。我们的建议的结构考虑了这些发现，并区分了最小化和最大化问题，以及具有两个以上目标函数的问题和具有两个以上目标函数的问题。在这个项目完成后，这些优化问题的一般近似方法就可以使用了。此外，还将研究和更好地理解几个单准则问题(例如，属于稳健优化、参数优化或预算约束优化领域)和相关多准则问题之间的关系。因此，一方面，我们的目标是开发一种“可证明是好的”替代方法来解决当前的多准则优化问题的精确和启发式方法，另一方面，我们打算为数学规划理论的最新发展做出重大贡献。

In many optimization problems, several incommensurable objective functions are to be optimized simultaneously. Such multicriteria optimization problems are based on optimality concepts that are induced by ordering relations. The predominant concept is the concept of Pareto optimality, which characterizes optimal solutions as minima (or maxima) with respect to the componentwise ordering. For many optimization problems, however, the set of Pareto-optimal solutions and the corresponding image set are very large and very difficult to compute exactly. Hence, our proposal aims at developing approximation methods for multicriteria optimization problems that (1) are applicable under weak assumptions, (2) yield a provably good approximation quality, and (3) possess a provable worst-case running time. The applicants contribute to this goal with their complementary skills in multicriteria optimization and approximation algorithms and are able to build on joint previous work. It is known that several of the existing methods for approximating multicriteria minimization problems cannot be transferred to maximization problems. Minimization and maximization problems require substantially different techniques. Additionally, the concept of Pareto optimality implies a significant difference in the level of difficulty between bicriteria problems and general multicriteria optimization problems. The structure of our proposal takes these findings into account and distinguishes between minimization and maximization problems as well as between problems with two and problems with more than two objective functions. Upon completion of this project, general approximation methods for these optimization problems will be ready to use. Moreover, the relationship among several single-criterion problems (belonging, e.g. to the fields of robust optimization, parametric optimization, or budget-constrained optimization) and related multicriteria problems will be studied and better understood. Thus, on the one hand, we aim at developing a "provably good" alternative to the current exact and heuristic methods for multicriteria optimization problems and, on the other hand, we intend to contribute significantly to the state-of-the-art in the theory of mathematical programming.