Scholarlink

<p>Random projection, a dimensionality reduction technique, has been found useful in recent years for reducing the size of optimization problems. In this paper, we explore the use of sparse sub-gaussian random projections to approximate semidefinite programming (SDP) problems by reducing the size of matrix variables, thereby solving the original problem with much less computational effort. We provide some theoretical bounds on the quality of the projection in terms of feasibility and optimality that explicitly depend on the sparsity parameter of the projector. We investigate the performance of the approach for semidefinite relaxations appearing in polynomial optimization, with a focus on combinatorial optimization problems. In particular, we apply our method to the semidefinite relaxations of <span>Maxcut</span> and <span>Max-2-sat</span>. We show that for large unweighted graphs, we can obtain a good bound by solving a projection of the semidefinite relaxation of <span>Maxcut</span>. We also explore how to apply our method to find the stability number of four classes of imperfect graphs by solving a projection of the second level of the Lasserre Hierarchy. Overall, our computational experiments show that semidefinite programming problems appearing as relaxations of combinatorial optimization problems can be approximately solved using random projections as long as the number of constraints is not too large.</p>

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

Sparse sub-gaussian random projections for semidefinite programming relaxations

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月4日

查看全文
  • Monse Guedes-Ayala,
  • Pierre-Louis Poirion,
  • Lars Schewe,
  • Akiko Takeda

摘要

Random projection, a dimensionality reduction technique, has been found useful in recent years for reducing the size of optimization problems. In this paper, we explore the use of sparse sub-gaussian random projections to approximate semidefinite programming (SDP) problems by reducing the size of matrix variables, thereby solving the original problem with much less computational effort. We provide some theoretical bounds on the quality of the projection in terms of feasibility and optimality that explicitly depend on the sparsity parameter of the projector. We investigate the performance of the approach for semidefinite relaxations appearing in polynomial optimization, with a focus on combinatorial optimization problems. In particular, we apply our method to the semidefinite relaxations of Maxcut and Max-2-sat. We show that for large unweighted graphs, we can obtain a good bound by solving a projection of the semidefinite relaxation of Maxcut. We also explore how to apply our method to find the stability number of four classes of imperfect graphs by solving a projection of the second level of the Lasserre Hierarchy. Overall, our computational experiments show that semidefinite programming problems appearing as relaxations of combinatorial optimization problems can be approximately solved using random projections as long as the number of constraints is not too large.