Engineering a Generic Solver for Convex Optimization Problems

点击翻译按钮获取中文摘要

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.