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 可以生成的并行分布式代码将能够解决大规模数据分析问题，这些问题比目前通用优化软件可以处理的问题大几个数量级。