Interior point and outer approximation methods for conic optimization
Any convex optimization problem may be represented as a conic problem that minimizes a linear function over the intersection of an affine subspace with a convex cone. An advantage of representing convex problems in conic form is that, under certain regularity conditions, a conic problem has a simple...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144941 https://orcid.org/0000-0002-1305-0141 |
| _version_ | 1811077798821888000 |
|---|---|
| author | Coey, Christopher Daniel Lang |
| author2 | Vielma Centeno, Juan Pablo |
| author_facet | Vielma Centeno, Juan Pablo Coey, Christopher Daniel Lang |
| author_sort | Coey, Christopher Daniel Lang |
| collection | MIT |
| description | Any convex optimization problem may be represented as a conic problem that minimizes a linear function over the intersection of an affine subspace with a convex cone. An advantage of representing convex problems in conic form is that, under certain regularity conditions, a conic problem has a simple and easily checkable certificate of optimality, primal infeasibility, or dual infeasibility. As a natural generalization of linear programming duality, conic duality allows us to design powerful algorithms for continuous and mixed-integer convex optimization.
The main goal of this thesis is to improve the generality and practical performance of (i) interior point methods for continuous conic problems and (ii) outer approximation methods for mixed-integer conic problems. We implement our algorithms in extensible open source solvers accessible through the convenient modeling language JuMP. From around 50 applied examples, we formulate continuous and mixed-integer problems over two dozen different convex cone types, many of which are new. Our extensive computational experiments with these examples explore which algorithmic features and what types of equivalent conic formulations lead to the best performance. |
| first_indexed | 2024-09-23T10:48:33Z |
| format | Thesis |
| id | mit-1721.1/144941 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:48:33Z |
| publishDate | 2022 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1449412022-08-30T03:46:31Z Interior point and outer approximation methods for conic optimization Coey, Christopher Daniel Lang Vielma Centeno, Juan Pablo Perakis, Georgia Massachusetts Institute of Technology. Operations Research Center Any convex optimization problem may be represented as a conic problem that minimizes a linear function over the intersection of an affine subspace with a convex cone. An advantage of representing convex problems in conic form is that, under certain regularity conditions, a conic problem has a simple and easily checkable certificate of optimality, primal infeasibility, or dual infeasibility. As a natural generalization of linear programming duality, conic duality allows us to design powerful algorithms for continuous and mixed-integer convex optimization. The main goal of this thesis is to improve the generality and practical performance of (i) interior point methods for continuous conic problems and (ii) outer approximation methods for mixed-integer conic problems. We implement our algorithms in extensible open source solvers accessible through the convenient modeling language JuMP. From around 50 applied examples, we formulate continuous and mixed-integer problems over two dozen different convex cone types, many of which are new. Our extensive computational experiments with these examples explore which algorithmic features and what types of equivalent conic formulations lead to the best performance. Ph.D. 2022-08-29T16:22:29Z 2022-08-29T16:22:29Z 2022-05 2022-07-05T19:56:03.294Z Thesis https://hdl.handle.net/1721.1/144941 https://orcid.org/0000-0002-1305-0141 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Coey, Christopher Daniel Lang Interior point and outer approximation methods for conic optimization |
| title | Interior point and outer approximation methods for conic optimization |
| title_full | Interior point and outer approximation methods for conic optimization |
| title_fullStr | Interior point and outer approximation methods for conic optimization |
| title_full_unstemmed | Interior point and outer approximation methods for conic optimization |
| title_short | Interior point and outer approximation methods for conic optimization |
| title_sort | interior point and outer approximation methods for conic optimization |
| url | https://hdl.handle.net/1721.1/144941 https://orcid.org/0000-0002-1305-0141 |
| work_keys_str_mv | AT coeychristopherdaniellang interiorpointandouterapproximationmethodsforconicoptimization |