General approximation methods for multicriteria optimization problems

多标准优化问题的通用近似方法

• 批准号: 398572517
• 负责人: Professor Dr. Stefan Ruzika
• 金额: --
• 依托单位: Professur für Komplexe Netzwerke
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2022-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/398572517?language=en
• 关键词: General; approximation; methods; multicriteria; optimization

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.

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