Quadratic programming: Difference between revisions

Content deleted Content added
Added Julia language.
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5
 
(4 intermediate revisions by 4 users not shown)
Line 100:
:<math>Z^\top Q Z \mathbf{y} = -Z^\top \mathbf{c}</math>
 
Under certain conditions on {{mvar|Q}}, the reduced matrix {{math|''Z''<sup>T</sup>''QZ''}} will be positive definite. It is possible to write a variation on the [[conjugate gradient method]] which avoids the explicit calculation of {{mvar|Z}}.<ref>{{Cite journal | last1 = Gould| first1 = Nicholas I. M.| last2 = Hribar| first2 = Mary E.| last3 = Nocedal| first3 = Jorge|date=April 2001| title = On the Solution of Equality Constrained Quadratic Programming Problems Arising in Optimization| journal = SIAM J. Sci. Comput.| pages = 1376–1395| volume = 23| issue = 4| citeseerx = 10.1.1.129.7555| doi = 10.1137/S1064827598345667| bibcode = 2001SJSC...23.1376G}}</ref>
 
==Lagrangian duality==
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==
Line 219:
|publisher=RAL Numerical Analysis Group Internal Report 2000-1
|url=ftp://ftp.numerical.rl.ac.uk/pub/qpbook/qp.pdf
|archive-url=https://web.archive.org/web/20170705054523/ftp://ftp.numerical.rl.ac.uk/pub/qpbook/qp.pdf|archive-date=2017-07-05|url-status=dead|date=2000
|date=2000
}}
==External links==
*[http://www.numerical.rl.ac.uk/qp/qp.html A page about quadratic programming] {{Webarchive|url=https://web.archive.org/web/20110607212051/http://www.numerical.rl.ac.uk/qp/qp.html |date=2011-06-07 }}
*[https://neos-guide.org/content/quadratic-programming NEOS Optimization Guide: Quadratic Programming]
*[https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf Quadratic Programming] {{Webarchive|url=https://web.archive.org/web/20230408093722/https://www.math.uh.edu/~rohop/fall_06/Chapter3.pdf |date=2023-04-08 }}
*[https://or.stackexchange.com/q/989/2576 Cubic programming and beyond], in Operations Research stack exchange