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.