English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study a class of quadratically constrained quadratic programs (QCQPs),called {\em diagonal QCQPs\/}, which contain no off-diagonal terms $x_j x_k$for $j \ne k$, and we provide a sufficient condition on the problem dataguaranteeing that the basic Shor semidefinite relaxation is exact. Ourcondition complements and refines those already present in the literature andcan be checked in polynomial time. We then extend our analysis from diagonalQCQPs to general QCQPs, i.e., ones with no particular structure. Byreformulating a general QCQP into diagonal form, we establish new,polynomial-time-checkable sufficient conditions for the semidefiniterelaxations of general QCQPs to be exact. Finally, these ideas are extended toshow that a class of random general QCQPs has exact semidefinite relaxationswith high probability as long as the number of constraints grows no faster thana fixed polynomial in the number of variables. To the best of our knowledge,this is the first result establishing the exactness of the semidefiniterelaxation for random general QCQPs.

Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs