ウィキペディア: 二次計画法では、線形制約のある正定値二次計画法 (QP) を多項式時間で解くことができると述べています。
一方、混合整数線形計画法 (MILP) は、二次制約付き二次計画法 (QCQP) に変換できます。MILP は NP 困難であることを知っているので、QCQD は一般的に NP 困難でなければなりません ( Wikipedia:Quadratically Constrained quadratic programから)。
つまり、制約に二次項がある場合、問題は NP 困難であり、それが目的関数にあり、正定である場合、多項式時間で解決できるということですか?