Scholarlink

<p>In this paper, we introduce a unified definition of <i>mediated graphs</i>, 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the Structure and Computation of Extremal Mediated Graphs with Applications to Conic Optimization

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月11日

查看全文
  • Víctor Blanco,
  • Miguel Martínez-Antón

摘要

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.