Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.03288 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917914003636224 |
|---|---|
| author | Blanco, Víctor Martínez-Antón, Miguel |
| author_facet | Blanco, Víctor Martínez-Antón, Miguel |
| contents | In this paper, we provide a unified definition of mediated graph, a combinatorial structure with multiple applications in mathematical optimization. We study some geometric and algebraic properties of this family of graphs and analyze extremal mediated graphs under the partial order induced by the cardinalty of their vertex sets. We derive mixed integer linear formulations to compute these challenging graphs and show that these structures are crucial in different fields, such as sum of squares decomposition of polynomials and second-order cone representations of convex cones, with a direct impact on conic optimization. We report the results of an extensive battery of experiments to show the validity of our approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_03288 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Mediated Graphs: The role of Combinatorics in Conic Optimization Blanco, Víctor Martínez-Antón, Miguel Optimization and Control In this paper, we provide a unified definition of mediated graph, a combinatorial structure with multiple applications in mathematical optimization. We study some geometric and algebraic properties of this family of graphs and analyze extremal mediated graphs under the partial order induced by the cardinalty of their vertex sets. We derive mixed integer linear formulations to compute these challenging graphs and show that these structures are crucial in different fields, such as sum of squares decomposition of polynomials and second-order cone representations of convex cones, with a direct impact on conic optimization. We report the results of an extensive battery of experiments to show the validity of our approaches. |
| title | Optimal Mediated Graphs: The role of Combinatorics in Conic Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2502.03288 |