Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 124:
For [[positive-definite matrix|positive definite]] {{mvar|Q}}, when the problem is convex, the [[ellipsoid method]] solves the problem in (weakly) [[polynomial time]].<ref>{{cite journal| last=Kozlov | first=M. K. |author2=S. P. Tarasov | author3-link=Leonid Khachiyan |author3=Leonid G. Khachiyan | year=1979 | title=[Polynomial solvability of convex quadratic programming] | journal=[[Doklady Akademii Nauk SSSR]] | volume=248 | pages=1049–1051}} Translated in: {{cite journal| journal=Soviet Mathematics - Doklady | volume=20 | pages=1108–1111}}</ref>
Ye and Tse<ref>{{Cite journal |last=Ye |first=Yinyu |last2=Tse |first2=Edison |date=1989-05-01 |title=An extension of Karmarkar's projective algorithm for convex quadratic programming |url=https://doi.org/10.1007/BF01587086 |journal=Mathematical Programming |language=en |volume=44 |issue=1 |pages=157–179 |doi=10.1007/BF01587086 |issn=1436-4646}}</ref> present a polynomial-time algorithm, which extends [[Karmarkar's algorithm]] from linear programming to convex quadratic programming. On a system with ''n'' variables and ''L'' input bits, their algorithm requires O(L n) iterations, each of which can be done using O(L n<sup>3</sup>) arithmetic operations, for a total runtime complexity of O(''L''<sup>2</sup> ''n''<sup>4</sup>).
Kapoor and Vaidya<ref>{{Cite journal |last=Kapoor |first=S |last2=Vaidya |first2=P M |date=1986-11-01 |title=Fast algorithms for convex quadratic programming and multicommodity flows |url=https://dl.acm.org/doi/10.1145/12130.12145 |journal=Proceedings of the eighteenth annual ACM symposium on Theory of computing |series=STOC '86 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=147–159 |doi=10.1145/12130.12145 |isbn=978-0-89791-193-1}}</ref> present === Non-convex quadratic programming ===
| |||