Scaling Up Generic Optimization

扩大通用优化规模

• 批准号: 254643541
• 负责人: Professor Dr. Joachim Giesen
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Priority Programmes
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2020-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/254643541?language=en
• 关键词: Scaling; Up; Generic; Optimization

Optimization problems are ubiquitous in science, engineering and economics. Thus, it is not surprising that optimization problems come in many different flavors. In our proposal we focus on large-scale convex optimization problems. Another important class are discrete optimization problems, like for instance computing shortest paths, minimum or maximum cuts, network flows, or vertex covers in the context of graph algorithms. Many discrete problems have relaxations as linear or semidefinite programs, or can even be cast as convex optimization problems. Relaxations are often an essential part of approximation algorithms for combinatorial optimization problems. Hence, discrete and combinatorial Big Data optimization problems can greatly benefit from generic, parallel and distributed convex optimization software. Such software will be provided by the generic optimization code generator (GENO) that we want to build within this project. When developing GENO we will closely follow the algorithms engineering development cycle which includes a thorough theoretical analysis of the algorithms that we will design and implement. Another area where convex optimization plays an important role is Big Data analytics, i.e., learning structure from massive amounts of data for enabling reliable predictions. Machine learning is concerned with the design and analysis of methods for learning from data. At its algorithmic core these methods often boil down to convex optimization problems. The parallel and distributed code that can be generated by GENO will allow to tackle large-scale data analytics problems that are orders of magnitude larger than what currently can be handled by generic optimization software.

最优化问题在科学、工程和经济中普遍存在。因此，优化问题有多种不同的形式也就不足为奇了。在我们的方案中，我们将重点放在大规模凸优化问题上。另一类重要的问题是离散优化问题，例如在图算法的上下文中计算最短路径、最小或最大割、网络流或顶点覆盖。许多离散问题将松弛化为线性或半定规划，甚至可以归结为凸优化问题。松弛算法通常是组合优化问题近似算法的重要组成部分。因此，离散和组合大数据优化问题可以从通用、并行和分布式凸优化软件中受益匪浅。这样的软件将由通用优化代码生成器(GENO)提供，我们希望在这个项目中建立。在开发Geno时，我们将密切遵循算法工程开发周期，其中包括对我们将设计和实现的算法进行彻底的理论分析。凸优化发挥重要作用的另一个领域是大数据分析，即从海量数据中学习结构以实现可靠的预测。机器学习涉及从数据中学习的方法的设计和分析。在其算法核心中，这些方法通常归结为凸优化问题。Geno可以生成的并行和分布式代码将允许处理大规模数据分析问题，这些问题比目前通用优化软件可以处理的问题大几个数量级。