exact SDP relaxation

Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

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

    We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more

    Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in two categories. The first one is for determining an optimal solution and the second one is for finding an optimal value. The first category of conditions includes the existence of a saddle … Read more