polynomial-size extended formulation

Tight semidefinite programming relaxations for sparse box-constrained quadratic programs

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , , ,

    We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more

    A second-order cone representable class of nonconvex quadratic programs

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Integer Programming Tags , , , ,

    We consider the problem of minimizing a sparse nonconvex quadratic function over the unit hypercube. By developing an extension of the Reformulation Linearization Technique (RLT) to continuous quadratic sets, we propose a novel second-order cone (SOC) representable relaxation for this problem. By exploiting the sparsity of the quadratic function, we establish a sufficient condition under … Read more