Quadratically Constrained Quadratic Program

In mathematical optimization, a quadratically constrained quadratic program (QCQP) is an optimization problem in which both the objective function and the constraints are quadratic functions. It has the form

\begin{align} & \text{minimize} && \tfrac12 x^\mathrm{T} P_0 x + q_0^\mathrm{T} x \\ & \text{subject to} && \tfrac12 x^\mathrm{T} P_i x + q_i^\mathrm{T} x + r_i \leq 0 \quad \text{for } i = 1,\dots,m, \\ &&& Ax = b, \end{align}

where P0, … Pm are n-by-n matrices and x ∈ Rn is the optimization variable.

If P0, … Pm are all positive semidefinite, then the problem is convex. If these matrices are neither positive or negative semidefinite, the problem is non-convex. If P1, … Pm are all zero, then the constraints are in fact linear and the problem is a quadratic program.

Read more about Quadratically Constrained Quadratic Program:  Hardness, Relaxation, Example, Solvers and Scripting (programming) Languages

Famous quotes containing the words constrained and/or program:

    “An expansive life, one not constrained by four walls, requires as well an expansive pocket.”
    —Anton Pavlovich Chekhov (1860–1904)

    “Chippenhook was the home of Judge Theophilus Harrington, known for his trenchant reply to an irate slave-owner in a runaway slave case. Judge Harrington declared that the owner’s claim to the slave was defective. The owner indignantly demanded to know what was lacking in his legally sound claim. The Judge exploded, ‘A bill of sale, sir, from God Almighty!’”
    —For the State of Vermont, U.S. public relief program (1935-1943)