Scholarlink

<p>This paper presents an enhanced second-order conic programming (ESOCP) relaxation-based branch and bound algorithm for the quadratic programming problem with a second-order cone constraint and linear inequalities. To enhance the conic relaxation performance, we first equivalently reformulate the objective function by incorporating a nonnegative parameter and the square of the linear term derived from the second-order cone constraint. Next, we reformulate the problem via variable substitution with a nonsingular matrix, yielding objective and constraint matrices that are simultaneously diagonalizable. We then develop an ESOCP relaxation and propose two choices for the nonnegative parameter. Finally, we compare the branch and bound algorithm based on the ESOCP relaxation with those based on the classical second-order conic programming (SOCP) relaxation and semidefinite programming (SDP) relaxation, as well as the global solver Gurobi. Computational results demonstrate that the branch and bound algorithm based on the ESOCP relaxation exhibits higher solution efficiency.</p>

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

An Enhanced SOCP Relaxation-Based Branch and Bound Algorithm for Quadratic Programming with a Second-Order Cone Constraint and Linear Inequalities

  • 期刊论文

  • 发表日期：

    2026年5月6日

查看全文
  • Jing Zhou,
  • Ye Tian,
  • Lei Zhang

摘要

This paper presents an enhanced second-order conic programming (ESOCP) relaxation-based branch and bound algorithm for the quadratic programming problem with a second-order cone constraint and linear inequalities. To enhance the conic relaxation performance, we first equivalently reformulate the objective function by incorporating a nonnegative parameter and the square of the linear term derived from the second-order cone constraint. Next, we reformulate the problem via variable substitution with a nonsingular matrix, yielding objective and constraint matrices that are simultaneously diagonalizable. We then develop an ESOCP relaxation and propose two choices for the nonnegative parameter. Finally, we compare the branch and bound algorithm based on the ESOCP relaxation with those based on the classical second-order conic programming (SOCP) relaxation and semidefinite programming (SDP) relaxation, as well as the global solver Gurobi. Computational results demonstrate that the branch and bound algorithm based on the ESOCP relaxation exhibits higher solution efficiency.