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:
“From cradle to grave this problem of running order through chaos, direction through space, discipline through freedom, unity through multiplicity, has always been, and must always be, the task of education, as it is the moral of religion, philosophy, science, art, politics and economy; but a boys will is his life, and he dies when it is broken, as the colt dies in harness, taking a new nature in becoming tame.”
—Henry Brooks Adams (18381918)
“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)