Scholarlink

<p>We consider the problem of minimizing a (possibly nonconvex) quadratic function over a (possibly unbounded) polyhedron, referred to as a quadratic program. By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality conditions on the strength of linear and semidefinite programming (SDP) relaxations based on the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). We establish that the RLT and SDP-RLT bounds arising from the complementarity formulation do not strengthen finite RLT and SDP-RLT bounds arising from the original formulation. On the other hand, the complementarity formulation may yield strictly tighter lower bounds for quadratic programs with a finite optimal value, but unbounded RLT and SDP-RLT relaxations. We present several classes of instances of quadratic programs to illustrate the behavior of the relaxations arising from the complementarity formulation. In particular, our examples reveal that the complementarity formulation should be used with some caution as it may even fail to yield a valid lower bound for unbounded quadratic programs.</p>

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

Relaxations of KKT conditions do not strengthen finite RLT and SDP-RLT bounds for nonconvex quadratic programs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年3月10日

查看全文
  • E. Alper Yıldırım

摘要

We consider the problem of minimizing a (possibly nonconvex) quadratic function over a (possibly unbounded) polyhedron, referred to as a quadratic program. By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality conditions on the strength of linear and semidefinite programming (SDP) relaxations based on the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). We establish that the RLT and SDP-RLT bounds arising from the complementarity formulation do not strengthen finite RLT and SDP-RLT bounds arising from the original formulation. On the other hand, the complementarity formulation may yield strictly tighter lower bounds for quadratic programs with a finite optimal value, but unbounded RLT and SDP-RLT relaxations. We present several classes of instances of quadratic programs to illustrate the behavior of the relaxations arising from the complementarity formulation. In particular, our examples reveal that the complementarity formulation should be used with some caution as it may even fail to yield a valid lower bound for unbounded quadratic programs.