Search for: All records

Spectral functions on Euclidean Jordan algebras arise frequently in convex optimization models. Despite the success of primal-dual conic interior point solvers, there has been little work on enabling direct support for spectral cones, that is, proper nonsymmetric cones defined from epigraphs and perspectives of spectral functions. We propose simple logarithmically homogeneous barriers for spectral cones and we derive efficient, numerically stable procedures for evaluating barrier oracles such as inverse Hessian operators. For two useful classes of spectral cones—the root-determinant cones and the matrix monotone derivative cones—we show that the barriers are self-concordant, with nearly optimal parameters. We implement these cones and oracles in our open-source solver Hypatia, and we write simple, natural formulations for four applied problems. Our computational benchmarks demonstrate that Hypatia often solves the natural formulations more efficiently than advanced solvers such as MOSEK 9 solve equivalent extended formulations written using only the cones these solvers support. Funding: This work was supported by Office of Naval Research [Grant N00014-18-1-2079] and the National Science Foundation [Grant OAC-1835443]. 

Abstract In recent work, we provide computational arguments for expanding the class of proper cones recognized by conic optimization solvers, to permit simpler, smaller, more natural conic formulations. We define an exotic cone as a proper cone for which we can implement a small set of tractable (i.e. fast, numerically stable, analytic) oracles for a logarithmically homogeneous self-concordant barrier for the cone or for its dual cone. Our extensible, open-source conic interior point solver, Hypatia, allows modeling and solving any conic problem over a Cartesian product of exotic cones. In this paper, we introduce Hypatia’s interior point algorithm, which generalizes that of Skajaa and Ye (Math. Program. 150(2):391–422, 2015) by handling exotic cones without tractable primal oracles. To improve iteration count and solve time in practice, we propose four enhancements to the interior point stepping procedure of Skajaa and Ye: (1) loosening the central path proximity conditions, (2) adjusting the directions using a third order directional derivative barrier oracle, (3) performing a backtracking search on a curve, and (4) combining the prediction and centering directions. We implement 23 useful exotic cones in Hypatia. We summarize the complexity of computing oracles for these cones and show that our new third order oracle is not a bottleneck. From 37 applied examples, we generate a diverse benchmark set of 379 problems. Our computational testing shows that each stepping enhancement improves Hypatia’s iteration count and solve time. Altogether, the enhancements reduce the geometric means of iteration count and solve time by over 80% and 70% respectively. 

Many convex optimization problems can be represented through conic extended formulations (EFs) using only the small number of standard cones recognized by advanced conic solvers such as MOSEK 9. However, EFs are often significantly larger and more complex than equivalent conic natural formulations (NFs) represented using the much broader class of exotic cones. We define an exotic cone as a proper cone for which we can implement easily computable logarithmically homogeneous self-concordant barrier oracles for either the cone or its dual cone. Our goal is to establish whether a generic conic interior point solver supporting NFs can outperform an advanced conic solver specialized for EFs across a variety of applied problems. We introduce Hypatia, a highly configurable open-source conic primal-dual interior point solver written in Julia and accessible through JuMP. Hypatia has a generic interface for exotic cones, some of which we define here. For seven applied problems, we introduce NFs using these cones and construct EFs that are necessarily larger and more complex. Our computational experiments demonstrate the advantages, especially in terms of solve time and memory usage, of solving the NFs with Hypatia compared with solving the EFs with either Hypatia or MOSEK 9. 

Polynomial nonnegativity constraints can often be handled using thesum of squarescondition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz (Papp D in SIAM J O 29: 822–851, 2019), using the sum of squares cone directly in an interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and$$\ell _1$$${\ell }_1$-norm cones) can also be modeled through structured sum of squares programs. We take a different approach and propose using more specialized cones instead. This can result in lower dimensional formulations, more efficient oracles for interior point methods, or self-concordant barriers with smaller parameters.