ECOS: An SOCP solver for embedded systems

TLDR

The paper presents ECOS, an interior‑point solver for second‑order cone programming tailored to embedded systems. ECOS is a compact, single‑threaded ANSI‑C library that implements a primal‑dual Mehrotra predictor‑corrector with Nesterov‑Todd scaling, solving the symmetric indefinite KKT system via a modified Davis SparseLDL routine with dynamic regularization and iterative refinement, eliminating the need for numerical pivoting. The resulting 750‑line implementation runs with virtually constant time, outperforming most existing SOCP solvers on small problems and remaining competitive for medium‑sized instances up to tens of thousands of variables.

Abstract

In this paper, we describe the embedded conic solver (ECOS), an interior-point solver for second-order cone programming (SOCP) designed specifically for embedded applications. ECOS is written in low footprint, single-threaded, library-free ANSI-C and so runs on most embedded platforms. The main interior-point algorithm is a standard primal-dual Mehrotra predictor-corrector method with Nesterov-Todd scaling and self-dual embedding, with search directions found via a symmetric indefinite KKT system, chosen to allow stable factorization with a fixed pivoting order. The indefinite system is solved using Davis' SparseLDL package, which we modify by adding dynamic regularization and iterative refinement for stability and reliability, as is done in the CVXGEN code generation system, allowing us to avoid all numerical pivoting; the elimination ordering is found entirely symbolically. This keeps the solver simple, only 750 lines of code, with virtually no variation in run time. For small problems, ECOS is faster than most existing SOCP solvers; it is still competitive for medium-sized problems up to tens of thousands of variables.