Content deleted Content added
Citation bot (talk | contribs) Added bibcode. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Optimization algorithms and methods | #UCB_Category 132/168 |
m Open access bot: url-access updated in citation with #oabot. |
||
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 |last1=Ye |first1=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 |s2cid=35753865 |issn=1436-4646|url-access=subscription }}</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 book |last1=Kapoor |first1=S |last2=Vaidya |first2=P M |chapter=Fast algorithms for convex quadratic programming and multicommodity flows |date=1986-11-01 |title=Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 |chapter-url=https://dl.acm.org/doi/10.1145/12130.12145 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=147–159 |doi=10.1145/12130.12145 |isbn=978-0-89791-193-1|s2cid=18108815 }}</ref> present another algorithm, which requires O(''L'' * log ''L'' ''* n''<sup>3.67</sup> * log ''n'') arithmetic operations.
Line 200:
== Extensions ==
'''Polynomial optimization'''<ref>{{Citation |last=Tuy |first=Hoang |title=Polynomial Optimization |date=2016 |url=https://doi.org/10.1007/978-3-319-31484-6_12 |work=Convex Analysis and Global Optimization |pages=435–452 |editor-last=Tuy |editor-first=Hoang |access-date=2023-12-16 |series=Springer Optimization and Its Applications |volume=110 |place=Cham |publisher=Springer International Publishing |language=en |doi=10.1007/978-3-319-31484-6_12 |isbn=978-3-319-31484-6|url-access=subscription }}</ref> is a more general framework, in which the constraints can be [[polynomial function]]s of any degree, not only 2.
==See also==
| |||