Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

Techniques for handling nonsymmetric cones in interior point algorithms

Authors: Kapelevich, Lea;

Techniques for handling nonsymmetric cones in interior point algorithms

Abstract

Conic programs that seek to minimize a linear function over an intersection of symmetric (self-dual and homogeneous) cones are amenable to highly efficient primal-dual interior point methods, which are implemented by many popular off-the-shelf conic solvers. On the other hand, many useful conic sets cannot be modeled exactly or can be modeled more efficiently using cones that are not symmetric. Algorithms for nonsymmetric cones have been implemented in significantly fewer solvers. Practically efficient, self-concordant barrier functions have not been previously suggested for many useful nonsymmetric cones. For the nonsymmetric cones with known barriers, there is little published work on how to implement numerically stable and computationally fast barrier oracles for interior point methods. We begin this thesis by describing the interior point algorithm we implement in the solver Hypatia for exotic cones. The exotic cones are a broad class of cones (including symmetric and nonsymmetric cones) that admit a small set of oracles needed by Hypatia's algorithm. We justify a number of practical algorithmic enhancements from an empirical standpoint. We derive new logarithmically-homogeneous, self-concordant barrier functions for several useful nonsymmetric cones. In Chapter 3, these are barriers for cones derived from spectral functions on Euclidean Jordan algebras while in Chapter 5, these are barriers related to sum-of-squares polynomial cones. We show that using these cones with our new barriers is computationally favorable in comparison to alternative formulations. We show how to evaluate the oracles needed by Hypatia's algorithm for these barriers and others in a computationally efficient and numerically stable fashion throughout Chapters 3-5. In the final two chapters, we derive efficient techniques for calculating information related to convex conjugates of the barriers for seven nonsymmetric cones. This information is not used by Hypatia, but is necessary for the alternative algorithm by Dahl and Andersen (2021) that is implemented by the solver MOSEK. We implement the stepping procedure described by Dahl and Andersen (2021) in Hypatia and make some empirical comparisons between MOSEK's algorithm and Hypatia's.

Country
United States
Related Organizations
  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green