Techniques for handling nonsymmetric cones in interior point algorithms
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 set...
| Главный автор: | |
|---|---|
| Другие авторы: | |
| Формат: | Диссертация |
| Опубликовано: |
Massachusetts Institute of Technology
2022
|
| Online-ссылка: | https://hdl.handle.net/1721.1/145003 https://orcid.org/0000-0002-1043-393X |
| _version_ | 1826207318312747008 |
|---|---|
| author | Kapelevich, Lea |
| author2 | Van Parys, Bart P.G. |
| author_facet | Van Parys, Bart P.G. Kapelevich, Lea |
| author_sort | Kapelevich, Lea |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:47:28Z |
| format | Thesis |
| id | mit-1721.1/145003 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:47:28Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1450032022-08-30T03:27:07Z Techniques for handling nonsymmetric cones in interior point algorithms Kapelevich, Lea Van Parys, Bart P.G. Massachusetts Institute of Technology. Operations Research Center 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. Ph.D. 2022-08-29T16:26:35Z 2022-08-29T16:26:35Z 2022-05 2022-07-05T19:56:40.754Z Thesis https://hdl.handle.net/1721.1/145003 https://orcid.org/0000-0002-1043-393X In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Kapelevich, Lea Techniques for handling nonsymmetric cones in interior point algorithms |
| title | Techniques for handling nonsymmetric cones in interior point algorithms |
| title_full | Techniques for handling nonsymmetric cones in interior point algorithms |
| title_fullStr | Techniques for handling nonsymmetric cones in interior point algorithms |
| title_full_unstemmed | Techniques for handling nonsymmetric cones in interior point algorithms |
| title_short | Techniques for handling nonsymmetric cones in interior point algorithms |
| title_sort | techniques for handling nonsymmetric cones in interior point algorithms |
| url | https://hdl.handle.net/1721.1/145003 https://orcid.org/0000-0002-1043-393X |
| work_keys_str_mv | AT kapelevichlea techniquesforhandlingnonsymmetricconesininteriorpointalgorithms |