EconPapers    
Economics at your fingertips  
 

Solving Natural Conic Formulations with Hypatia.jl

Chris Coey (coey@mit.edu), Lea Kapelevich (lkap@mit.edu) and Juan Pablo Vielma (jvielma@google.com)
Additional contact information
Chris Coey: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Lea Kapelevich: Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Juan Pablo Vielma: Google Research and MIT Sloan School of Management, Cambridge, Massachusetts 02142

INFORMS Journal on Computing, 2022, vol. 34, issue 5, 2686-2699

Abstract: 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.

Keywords: conic optimization; extended formulations; interior point methods (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1202 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:5:p:2686-2699

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher (casher@informs.org).

 
Page updated 2024-12-28
Handle: RePEc:inm:orijoc:v:34:y:2022:i:5:p:2686-2699