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:

    It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.
    John Dewey (1859–1952)

    In necessary things, unity; in disputed things, liberty; in all things, charity.
    —Variously Ascribed.

    The formulation was used as a motto by the English Nonconformist clergyman Richard Baxter (1615-1691)