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 P₀, … P_m are n-by-n matrices and x ∈ Rn is the optimization variable.

If P₀, … P_m are all positive semidefinite, then the problem is convex. If these matrices are neither positive or negative semidefinite, the problem is non-convex. If P₁, … P_m 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:

“What a hell of an economic system! Some are replete with everything while others, whose stomachs are no less demanding, whose hunger is just as recurrent, have nothing to bite on. The worst of it is the constrained posture need puts you in. The needy man does not walk like the rest; he skips, slithers, twists, crawls.”
—Denis Diderot (1713–1784)

“The average Kentuckian may appear a bit confused in his knowledge of history, but he is firmly certain about current politics. Kentucky cannot claim first place in political importance, but it tops the list in its keen enjoyment of politics for its own sake. It takes the average Kentuckian only a matter of moments to dispose of the weather and personal helath, but he never tires of a political discussion.”
—For the State of Kentucky, U.S. public relief program (1935-1943)