Alex L. Wang

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

    The Generalized Trust Region Subproblem: solution complexity and convex hull results

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Constrained Nonlinear Optimization, Quadratic Programming

    We consider the Generalized Trust Region Subproblem (GTRS) of minimizing a nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting of this problem recasts the GTRS as minimizing a linear objective subject to two nonconvex quadratic constraints. Our first main contribution is structural: we give an explicit description of the convex hull of this … Read more