Quadratic Programming - Problem Formulation

Problem Formulation

The quadratic programming problem can be formulated as:

Assume x belongs to space. Both x and c are column vectors with n elements (n×1 matrices), and Q is a symmetric n×n matrix.

Minimize (with respect to x)

Subject to one or more constraints of the form:

(inequality constraint)
(equality constraint)

where indicates the vector transpose of . The notation means that every entry of the vector is less than or equal to the corresponding entry of the vector .

If the matrix is positive semidefinite, then is a convex function: In this case the quadratic program has a global minimizer if there exists some feasible vector (satisfying the constraints) and if is bounded below on the feasible region. If the matrix is positive definite and the problem has a feasible solution, then the global minimizer is unique.

If is zero, then the problem becomes a linear program.

A related programming problem, quadratically constrained quadratic programming, can be posed by adding quadratic constraints on the variables.

Read more about this topic:  Quadratic Programming

Famous quotes containing the words problem and/or formulation:

    Theology, I am persuaded, derives its initial impulse from a religious wavering; for there is quite as much, or more, that is mysterious and calculated to awaken scientific curiosity in the intercourse with God, and it [is] a problem quite analogous to that of theology.
    Charles Sanders Peirce (1839–1914)

    You do not mean by mystery what a Catholic does. You mean an interesting uncertainty: the uncertainty ceasing interest ceases also.... But a Catholic by mystery means an incomprehensible certainty: without certainty, without formulation there is no interest;... the clearer the formulation the greater the interest.
    Gerard Manley Hopkins (1844–1889)