Hardness
Solving the general case is an NP-hard problem. To see this, note that the two constraints x1(x1 − 1) ≤ 0 and x1(x1 − 1) ≥ 0 are equivalent to the constraint x1(x1 − 1) = 0, which is in turn equivalent to the constraint x1 ∈ {0, 1}. Hence, any 0–1 integer program (in which all variables have to be either 0 or 1) can be formulated as a quadratically constrained quadratic program. Since 0–1 integer programming is NP-hard in general, QCQP is also NP-hard.
Read more about this topic: Quadratically Constrained Quadratic Program
Famous quotes containing the word hardness:
“Despots play their part in the works of thinkers. Fettered words are terrible words. The writer doubles and trebles the power of his writing when a ruler imposes silence on the people. Something emerges from that enforced silence, a mysterious fullness which filters through and becomes steely in the thought. Repression in history leads to conciseness in the historian, and the rocklike hardness of much celebrated prose is due to the tempering of the tyrant.”
—Victor Hugo (1802–1885)