exact semidefinite programming relaxations

Constructing QCQP Instances Equivalent to Their SDP Relaxations

  • Masakazu Kojima
  • Naohiko Arima
  • Sunyoung Kim
    • Categories Global Optimization Applications, Quadratic Programming, Semi-definite Programming Tags , ,

    General quadratically constrained quadratic programs (QCQPs) are challenging to solve as they are known to be NP-hard. A popular approach to approximating QCQP solutions is to use semidefinite programming (SDP) relaxations. It is well-known that the optimal value η of the SDP relaxation problem bounds the optimal value ζ  of the QCQP from below, i.e., … Read more

    Exact SDP relaxations for a class of quadratic programs with finite and infinite quadratic constraints

  • Naohiko Arima
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Cone Programming, Semi-definite Programming Tags , , ,

    We investigate exact semidefinite programming (SDP) relaxations for the problem of minimizing a nonconvex quadratic objective function over a feasible region defined by both finitely and infinitely many nonconvex quadratic inequality constraints (semi-infinite QCQPs). Specifically, we present two sufficient conditions on the feasible region under which the QCQP, with any quadratic objective function over the … Read more