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:
“The great problem of American life [is] the riddle of authority: the difficulty of finding a way, within a liberal and individualistic social order, of living in harmonious and consecrated submission to something larger than oneself.... A yearning for self-transcendence and submission to authority [is] as deeply rooted as the lure of individual liberation.”
—Wilfred M. McClay, educator, author. The Masterless: Self and Society in Modern America, p. 4, University of North Carolina Press (1994)
“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)