Content deleted Content added
No edit summary |
Marekpetrik (talk | contribs) m Complexity |
||
Line 17:
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 [http://www.orfe.princeton.edu/~loqo LOQO]. [[Active set]] methods are also commonly used.
==Complexity==
For positive-definite ''E'', the ellipsoid algorithm solves the problem in polynomial time. If ''E'' has at least one negative [[eigenvalue]], the problem is NP-hard.
==References==
* {{Book reference|Author = [[Michael R. Garey]] and [[David S. Johnson]] | Year = 1979 | Title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | Publisher = W.H. Freeman | ID = ISBN 0716710455}} A6: MP2, pg.245.
* {{Book reference|Author = [[Jorge Nocedal]] and [[Stephen J. Wright]] | Year = 1999 | Title = [[Numerical Optimization]] | Publisher = Springer | ID = 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.
==External links==
| |||