Scholarlink

<p>In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising as part of an extended formulation and exploiting the supermodularity of a set function defined on its extreme points. Our computational results confirm that the proposed convex relaxation provides an exact optimal solution and may be an effective alternative, especially for instances with large integrality gaps that are challenging with the standard approaches.</p>

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

Polyhedral analysis of quadratic optimization problems with Stieltjes matrices and indicators

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月27日

查看全文
  • Peijing Liu,
  • Alper Atamtürk,
  • Andrés Gómez,
  • Simge Küçükyavuz

摘要

In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising as part of an extended formulation and exploiting the supermodularity of a set function defined on its extreme points. Our computational results confirm that the proposed convex relaxation provides an exact optimal solution and may be an effective alternative, especially for instances with large integrality gaps that are challenging with the standard approaches.