lagrange function

On convex hulls of epigraphs of QCQPs

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , ,

    Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditions for a convex hull result that immediately implies that the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such … Read more

    On the tightness of SDP relaxations of QCQPs

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show … Read more