Engineering a Generic Solver for Convex Optimization Problems

科学、工程和经济中的许多问题都可以归结为凸优化问题。这些问题的非穷举列表包括投资组合优化，电路设计，最优控制理论问题，包装和覆盖线性程序，网络流，高分辨率显微镜中使用的优化问题，以及机器学习和数据分析问题。然而，直到今天，这些优化问题中的任何一个的有效解决方案仍然需要实现定制的，和高度调优的求解器。这个项目的成果将是一个优化器生成器，它可以自动生成C++代码，用于几乎任何在上述应用程序中遇到的凸优化问题类。优化器生成器将提供易于使用的原型语言，如Matlab/CVX用于建模和解决此类凸优化问题，同时生成与问题大小很好匹配的生产质量代码。特别是，我们希望实现与流行的建模工具CVX相同的功能，但以更简单，更灵活的方式，同时与定制的优化求解器一样高效，因此比CVX以及最先进的商业求解器快几个数量级。该项目包括建模语言的设计，矢量和矩阵表达式的符号微分模块的设计和实现，以及使用符号导数的通用求解器的实现。生成的求解器还将包括重要的半定规划问题（SDP）类。为此，我们将设计一种新的算法来解决SDP，这将是数量级快于目前最先进的SDP求解器，因此规模更大的问题实例。我们将为所有算法提供数学收敛性和运行时间保证。

Many problems in science, engineering, and economics can be cast as convex optimization problems. A non-exhaustive list of such problems includes portfolio optimization, circuit design, problems from optimal control theory, packing and covering linear programs, network flows, optimization problems used in high-resolution microscopy, and machine learning and data analysis problems. However, up to this day, efficient solutions to any of these optimization problems still require the implementation of customized, and highly-tuned solvers.The outcome of this project will be an optimizer generator that automatically generates C++-code for almost any convex optimization problem class that is encountered in the applications mentioned above.The optimizer generator will provide the ease of use of a prototyping language like Matlab/CVX for modeling and solving such convex optimization problems while at the same time generating production quality code that scales well with the problem size. In particular we want to achieve the same functionality as the popular modeling tool CVX but in a simpler and more flexible way while being as efficient as customized optimization solvers, and thus a few orders of magnitude faster than CVX together with state-of-the-art commercial solvers.The project comprises the design of the modeling language, the design and implementation of a symbolic differentiation module for vector- and matrix expressions, and the implementation of a generic solver that makes use of the symbolic derivatives.The generated solvers will also include the important class of semidefinite programming problems (SDPs). For this purpose we will design a new algorithm for solving SDPs that will be orders of magnitude faster than current state-of-the-art SDP solvers and hence scales to much larger problem instances. We will provide mathematical convergence and runtime guarantees for all algorithms.