On the Structure and Computation of Extremal Mediated Graphs with Applications to Conic Optimization
Journal of Optimization Theory and Applications · 2026-08 · 210 (2)
DOI: 10.1007/s10957-026-03048-5 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Optimization Theory and Applications, online erschienen am 11.07.2026. Verfasst von Víctor Blanco und 1 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministerio de Ciencia e Innovación, Consejería de Economía, Conocimiento, Empresas y Universidad, Junta de Andalucía.
Abstract (Originalsprache)
In this paper, we introduce a unified definition of mediated graphs , a combinatorial structure that underlies several constructions in polynomial and conic optimization. We investigate their geometric and algebraic properties and study extremal mediated graphs under the partial order induced by the cardinality of their vertex sets. We develop mixed-integer linear formulations that enable the exact computation of these graphs, which are typically difficult to obtain by direct enumeration. We show that mediated graphs play a crucial role in SOS and SONC decompositions of polynomials, as well as in second-order cone representations of convex cones, thereby providing new modeling tools with a direct impact on conic optimization. An extensive computational study demonstrates the effectiveness and scalability of the proposed methods.
Förderung
- Ministerio de Ciencia e Innovación
- Consejería de Economía, Conocimiento, Empresas y Universidad, Junta de Andalucía
Zitieren
APA
Blanco, V., & Martínez-Antón, M. (2026). On the Structure and Computation of Extremal Mediated Graphs with Applications to Conic Optimization. Journal of Optimization Theory and Applications, 210(2). https://doi.org/10.1007/s10957-026-03048-5
Vancouver
Blanco V, Martínez-Antón M. On the Structure and Computation of Extremal Mediated Graphs with Applications to Conic Optimization. Journal of Optimization Theory and Applications. 2026;210(2). doi:10.1007/s10957-026-03048-5
BibTeX
@article{Blanco2026,
author = {Blanco, Víctor and Martínez-Antón, Miguel},
title = {On the Structure and Computation of Extremal Mediated Graphs with Applications to Conic Optimization},
journal = {Journal of Optimization Theory and Applications},
year = {2026},
volume = {210},
number = {2},
doi = {10.1007/s10957-026-03048-5}
}
EUVIMED