|
Quadratic programming (QP) is a special type of mathematical optimization problem. In mathematics, the term optimization refers to the study of problems that have the form Given: a function f : A R from some set A to the real numbers Sought: an element x0 in A such that f(x0) ≤ f(x) for all x in A (minimization) or such that...
The quadratic programming problem can be formulated like this:
Assume x belongs to  space. The n×n matrix Q is symmetric, and c is any n×1 vector. For the square matrix section, see square matrix. ...
Minimize (with respect to x)
 (Here  indicates the matrix transpose of v.) In mathematics, and in particular linear algebra, the transpose of a matrix is another matrix, produced by turning rows into columns and vice versa. ...
A quadratic programming problem has at least one of the following kinds of constraints:
- Ax ≤ b (inequality constraint)
- Ex = d (equality constraint)
If Q is positive definite, then f(x) is a convex function and constraints are linear functions. We know from optimization theory that for point x to be an optimum point it is necessary and sufficient that x is a Karush-Kuhn-Tucker (KKT) point. In linear algebra, a positive-definite matrix is a Hermitian matrix which in many ways is analogous to a positive real number. ...
In mathematics, an object is convex if for any pair of points within the object, any point on the straight line segment that joins them is also within the object. ...
Partial plot of a function f. ...
The word linear comes from the Latin word linearis, which means created by lines. ...
In mathematics, the Karush-Kuhn-Tucker conditions (also known as the Kuhn-Tucker or the KKT conditions) are necessary for a solution in nonlinear programming to be optimal. ...
If there are only equality constraints, then the QP can be solved by a linear system. Otherwise, the most common method of solving a QP is an interior point method, such as LOQO. Active set methods are also commonly used, as well as Conjugate gradient method with projection. A linear system is a model of a system based on some kind of linear operator. ...
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems. ...
In optimization, a problem is defined using an objective function to minimize or maximize, and a set of constraints that should be respected. ...
In mathematics, the conjugate gradient method is an algorithm for the numerical solution of particular systems of linear equations, namely those whose matrix is symmetric and positive definite. ...
Complexity For positive-definite Q, the ellipsoid algorithm solves the problem in polynomial time. If Q has at least one negative eigenvalue, the problem is NP-hard. In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...
In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing...
References - Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman. ISBN 0716710455. A6: MP2, pg.245.
- Jorge Nocedal and Stephen J. Wright (1999). Numerical Optimization, Springer. ISBN 0387987932. , pg.441.
- Quadratic programming with one negative eigenvalue is NP-hard, Panos M. Pardalos and Stephen A. Vavasis in Journal of Global Optimization, Volume 1, Number 1, 1991, pg.15-22.
Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ...
David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ...
External links - Software
|
Feeds |
Contact