{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:06:51Z","timestamp":1784268411221,"version":"3.55.0"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T00:00:00Z","timestamp":1597190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-06516, DGECR-00303"],"award-info":[{"award-number":["RGPIN-06516, DGECR-00303"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI-1548562 - CCF-1657175"],"award-info":[{"award-number":["ACI-1548562 - CCF-1657175"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            Quadratic programs (QP), minimizations of quadratic objectives subject to linear inequality and equality constraints, are at the heart of algorithms across scientific domains. Applications include fundamental tasks in geometry processing, simulation, engineering, animation and finance where the accurate, reliable, efficient, and scalable solution of QP problems is critical. However, available QP algorithms generally provide either accuracy or scalability - but not both. Some algorithms reliably solve QP problems to high accuracy but work only for smaller-scale QP problems due to their reliance on dense matrix methods. Alternately, many other QP solvers scale well via sparse, efficient algorithms but cannot reliably deliver solutions at requested accuracies. Towards addressing the need for accurate\n            <jats:italic toggle=\"yes\">and<\/jats:italic>\n            efficient QP solvers at scale, we develop NASOQ, a new, full-space QP algorithm that provides accurate, efficient, and scalable solutions for QP problems. To enable NASOQ we construct a new row modification method and fast implementation of LDL factorization for indefinite systems. Together they enable efficient updates and accurate solutions of the iteratively modified KKT systems required for accurate QP solves. While QP methods have been previously tested on large synthetic benchmarks, to test and compare NASOQ's suitability for real-world applications we collect here a new benchmark set comprising a wide range of graphics-related QPs across physical simulation, animation, and geometry processing tasks. We combine these problems with numerous pre-existing stress-test QP benchmarks to form, to our knowledge, the largest-scale test set of application-based QP problems currently available. Building off of our base NASOQ solver we then develop and test two NASOQ variants against best, state-of-the-art available QP libraries - both commercial and open-source. Our two NASOQ-based methods each solve respectively 98.8% and 99.5% of problems across a range of requested accuracies from 10\n            <jats:sup>-3<\/jats:sup>\n            to 10\n            <jats:sup>-9<\/jats:sup>\n            with average speedups ranging from 1.7\u00d7 to 24.8\u00d7 over fastest competing methods.\n          <\/jats:p>","DOI":"10.1145\/3386569.3392486","type":"journal-article","created":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T11:44:27Z","timestamp":1597232667000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["NASOQ"],"prefix":"10.1145","volume":"39","author":[{"given":"Kazem","family":"Cheshmi","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danny M.","family":"Kaufman","sequence":"additional","affiliation":[{"name":"Adobe Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shoaib","family":"Kamil","sequence":"additional","affiliation":[{"name":"Adobe Research"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maryam Mehri","family":"Dehnavi","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,8,12]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Advances in Neural Information Processing Systems 32. Curran Associates","author":"Agrawal Akshay","unstructured":"Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico Kolter. 2019. Differentiable Convex Optimization Layers. In Advances in Neural Information Processing Systems 32. Curran Associates, Inc."},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the 34th International Conference on Machine Learning -","volume":"70","author":"Amos Brandon","unstructured":"Brandon Amos and J. Zico Kolter. 2017. OptNet: Differentiable Optimization as a Layer in Neural Networks. In Proceedings of the 34th International Conference on Machine Learning - Volume 70 (ICML'17). JMLR.org."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/060661545"},{"key":"e_1_2_2_4_1","unstructured":"Jernej Barbic. 2007. Real-Time Reduced Large-Deformation Models and Distributed Contact for Computer Graphics and Haptics. Ph.D. Dissertation. USA."},{"key":"e_1_2_2_5_1","volume-title":"Numerical solution of saddle point problems. Acta numerica 14","author":"Benzi Michele","year":"2005","unstructured":"Michele Benzi, Gene H Golub, and J\u00f6rg Liesen. 2005. Numerical solution of saddle point problems. Acta numerica 14 (2005)."},{"key":"e_1_2_2_6_1","volume-title":"Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning 3, 1","author":"Boyd Stephen","year":"2011","unstructured":"Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. 2011. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning 3, 1 (2011)."},{"key":"e_1_2_2_7_1","volume-title":"Convex optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization. Cambridge university press."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126908.3126936"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00065"},{"key":"e_1_2_2_11_1","volume-title":"Direct methods for sparse linear systems","author":"Davis Timothy A","unstructured":"Timothy A Davis. 2006. Direct methods for sparse linear systems. Vol. 2. Siam."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3322125"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479897321076"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089547980343641X"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462173.1462176"},{"key":"e_1_2_2_16_1","volume-title":"Benchmarking optimization software with performance profiles. Mathematical programming 91, 2","author":"Dolan Elizabeth D","year":"2002","unstructured":"Elizabeth D Dolan and Jorge J Mor\u00e9. 2002. Benchmarking optimization software with performance profiles. Mathematical programming 91, 2 (2002)."},{"key":"e_1_2_2_17_1","volume-title":"2013 European Control Conference (ECC).","author":"Domahidi A.","unstructured":"A. Domahidi, E. Chu, and S. Boyd. 2013. ECOS: An SOCP solver for embedded systems. In 2013 European Control Conference (ECC)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/992200.992202"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the Joint Symposium on Computational Aesthetics and Sketch-Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering (Expressive '18)","author":"Dvoro\u017e\u0148\u00e1k Marek","year":"2018","unstructured":"Marek Dvoro\u017e\u0148\u00e1k, Saman Sepehri Nejad, Ond\u0159ej Jamri\u0161ka, Alec Jacobson, Ladislav Kavan, and Daniel S\u00fdkora. 2018. Seamless Reconstruction of Part-Based High-Relief Models from Hand-Drawn Images. In Proceedings of the Joint Symposium on Computational Aesthetics and Sketch-Based Interfaces and Modeling and Non-Photorealistic Animation and Rendering (Expressive '18). Association for Computing Machinery, New York, NY, USA, Article 5."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02275347"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Kenny Erleben. 2013. Numerical methods for linear complementarity problems in physics-based animation. In Acm Siggraph 2013 Courses.","DOI":"10.1145\/2504435.2504443"},{"key":"e_1_2_2_22_1","volume-title":"Hans Georg Bock, and Moritz Diehl","author":"Ferreau Hans Joachim","year":"2014","unstructured":"Hans Joachim Ferreau, Christian Kirches, Andreas Potschka, Hans Georg Bock, and Moritz Diehl. 2014. qpOASES: A parametric active-set algorithm for quadratic programming. Mathematical Programming Computation 6, 4 (2014)."},{"key":"e_1_2_2_23_1","volume-title":"Hybridizing harmony search algorithm with sequential quadratic programming for engineering optimization problems. Computer methods in applied mechanics and engineering 197, 33--40","author":"Fesanghary M","year":"2008","unstructured":"M Fesanghary, Mehrdad Mahdavi, M Minary-Jolandan, and Y Alizadeh. 2008. Hybridizing harmony search algorithm with sequential quadratic programming for engineering optimization problems. Computer methods in applied mechanics and engineering 197, 33--40 (2008)."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118723203"},{"key":"e_1_2_2_25_1","first-page":"1","article-title":"Object-Oriented Software for Quadratic Programming","volume":"29","author":"Michael Gertz E.","year":"2003","unstructured":"E. Michael Gertz and Stephen J. Wright. 2003. Object-Oriented Software for Quadratic Programming. ACM Trans. Math. Softw. 29, 1 (March 2003).","journal-title":"ACM Trans. Math. Softw."},{"key":"e_1_2_2_26_1","unstructured":"Philip E Gill Walter Murray Michael A Saunders and Elizabeth Wong. 2005. User guide for SQOPT 7: Software for large-scale linear and quadratic programming."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1033001"},{"key":"e_1_2_2_28_1","volume-title":"A numerically stable dual method for solving strictly convex quadratic programs. Mathematical programming 27, 1","author":"Goldfarb Donald","year":"1983","unstructured":"Donald Goldfarb and Ashok Idnani. 1983. A numerically stable dual method for solving strictly convex quadratic programs. Mathematical programming 27, 1 (1983)."},{"key":"e_1_2_2_29_1","volume-title":"Matrix computations","author":"Golub Gene H","unstructured":"Gene H Golub and Charles F Van Loan. 2012. Matrix computations. Vol. 3. JHU press."},{"key":"e_1_2_2_30_1","volume-title":"Solving nonlinear financial planning problems with 109 decision variables on massively parallel architectures. WIT Transactions on Modelling and Simulation 43","author":"Gondzio Jacek","year":"2006","unstructured":"Jacek Gondzio and Andreas Grothey. 2006. Solving nonlinear financial planning problems with 109 decision variables on massively parallel architectures. WIT Transactions on Modelling and Simulation 43 (2006)."},{"key":"e_1_2_2_31_1","unstructured":"Nicholas Gould. 2006. An introduction to algorithms for continuous optimization."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598345667"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/962437.962438"},{"key":"e_1_2_2_34_1","series-title":"SIAM review 31, 2","volume-title":"Updating the inverse of a matrix","author":"Hager William W","year":"1989","unstructured":"William W Hager. 1989. Updating the inverse of a matrix. SIAM review 31, 2 (1989)."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231821"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(01)00141-7"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275107"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130849"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.4513"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513109.2513113"},{"key":"e_1_2_2_41_1","unstructured":"Hanh M Huynh. 2008. A large-scale quadratic programming solver based on block-LU updates of the KKT system. Technical Report. STANFORD UNIV CA DEPT OF COMPUTER SCIENCE."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964973"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo et al. 2018. libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_44_1","volume-title":"METIS: Unstructured graph partitioning and sparse matrix ordering system. Technical Report","author":"Karypis G.","year":"1997","unstructured":"G. Karypis. 1997. METIS: Unstructured graph partitioning and sparse matrix ordering system. Technical Report (1997)."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409117"},{"key":"e_1_2_2_46_1","unstructured":"David I.W. Levin. 2019. GAUSS Library. https:\/\/github.com\/dilevin\/GAUSS."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"e_1_2_2_48_1","unstructured":"Christopher Mario Maes. 2011. A regularized active-set method for sparse convex quadratic programming. Ph.D. Dissertation. Stanford University USA."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805768"},{"key":"e_1_2_2_50_1","volume-title":"CVXGEN: A code generator for embedded convex optimization. Optimization and Engineering 13, 1","author":"Mattingley Jacob","year":"2012","unstructured":"Jacob Mattingley and Stephen Boyd. 2012. CVXGEN: A code generator for embedded convex optimization. Optimization and Engineering 13, 1 (2012)."},{"key":"e_1_2_2_51_1","volume-title":"Retrieved","author":"Mittelmann Hans","year":"2020","unstructured":"Hans Mittelmann. 2020. Benchmarks for Optimization Software. Retrieved April 13, 2020 from http:\/\/plato.asu.edu\/bench.html"},{"key":"e_1_2_2_52_1","unstructured":"ApS Mosek. 2015. The MOSEK optimization toolbox for MATLAB manual."},{"key":"e_1_2_2_53_1","volume-title":"Numerical optimization","author":"Nocedal Jorge","unstructured":"Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer Science & Business Media."},{"key":"e_1_2_2_54_1","unstructured":"Gurobi Optimization. 2014. Inc. \"Gurobi optimizer reference manual \" 2015."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2926664"},{"key":"e_1_2_2_56_1","unstructured":"Michael James David Powell. 1985. On the quadratic programming algorithm of Goldfarb and Idnani. In Mathematical Programming Essays in Honor of George B. Dantzig Part II. Springer."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/HUMANOIDS.2012.6651572"},{"key":"e_1_2_2_58_1","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Saad Yousef","unstructured":"Yousef Saad. 2003. Iterative Methods for Sparse Linear Systems (second ed.). Society for Industrial and Applied Mathematics."},{"key":"e_1_2_2_59_1","first-page":"2","article-title":"Two-Level Dynamic Scheduling in PARDISO","volume":"28","author":"Schenk Olaf","year":"2002","unstructured":"Olaf Schenk and Klaus G\u00e4rtner. 2002. Two-Level Dynamic Scheduling in PARDISO: Improved Scalability on Shared Memory Multiprocessing Systems. Parallel Comput. 28, 2 (Feb. 2002).","journal-title":"Improved Scalability on Shared Memory Multiprocessing Systems. Parallel Comput."},{"key":"e_1_2_2_60_1","volume-title":"On fast factorization pivoting methods for sparse symmetric indefinite systems. ETNA. Electronic Transactions on Numerical Analysis [electronic only] 23","author":"Schenk Olaf","year":"2006","unstructured":"Olaf Schenk and Klaus G\u00e4rtner. 2006. On fast factorization pivoting methods for sparse symmetric indefinite systems. ETNA. Electronic Transactions on Numerical Analysis [electronic only] 23 (2006). http:\/\/eudml.org\/doc\/127439"},{"key":"e_1_2_2_61_1","volume-title":"QL: A Fortran code for convex quadratic programming-User guide. Report, Department of Mathematics","author":"Schittkowski K","year":"2003","unstructured":"K Schittkowski. 2003. QL: A Fortran code for convex quadratic programming-User guide. Report, Department of Mathematics, University of Bayreuth (2003)."},{"key":"e_1_2_2_62_1","unstructured":"Michele Segata. 2019. MPC Library. https:\/\/github.com\/michele-segata\/mpclib."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185602"},{"key":"e_1_2_2_64_1","volume-title":"OSQP: An operator splitting solver for quadratic programs. Mathematical Programming Computation","author":"Stellato Bartolomeo","year":"2020","unstructured":"Bartolomeo Stellato, Goran Banjac, Paul Goulart, Alberto Bemporad, and Stephen Boyd. 2020. OSQP: An operator splitting solver for quadratic programs. Mathematical Programming Computation (2020)."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591011"},{"key":"e_1_2_2_66_1","doi-asserted-by":"crossref","unstructured":"John Towns Timothy Cockerill Maytal Dahan Ian Foster Kelly Gaither Andrew Grimshaw Victor Hazlewood Scott Lathrop Dave Lifka Gregory D Peterson et al. 2014. XSEDE: accelerating scientific discovery. Computing in science & engineering 16 5 (2014).","DOI":"10.1109\/MCSE.2014.80"},{"key":"e_1_2_2_67_1","volume-title":"Biegler","author":"W\u00e4chter Andreas","year":"2006","unstructured":"Andreas W\u00e4chter and Lorenz T. Biegler. 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming 106, 1 (01 Mar 2006)."},{"key":"e_1_2_2_68_1","volume-title":"Ziena Optimization","author":"Waltz Richard A","year":"2004","unstructured":"Richard A Waltz and Jorge Nocedal. 2004. KNITRO 2.0 User's Manual. Ziena Optimization, Inc.[en ligne] disponible sur http:\/\/www.ziena.com 7 (2004)."},{"key":"e_1_2_2_69_1","volume-title":"High-Performance Computing on the Intel\u00ae Xeon Phi","author":"Wang Endong","unstructured":"Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, and Yajuan Wang. 2014. Intel math kernel library. In High-Performance Computing on the Intel\u00ae Xeon Phi. Springer."},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201281"},{"key":"e_1_2_2_71_1","unstructured":"Elizabeth Lai Sum Wong. 2011. Active-set methods for quadratic programming. Ph.D. Dissertation. UC San Diego USA."},{"key":"e_1_2_2_72_1","volume-title":"Primal-dual interior-point methods","author":"Wright Stephen J","unstructured":"Stephen J Wright. 1997. Primal-dual interior-point methods. Vol. 54. Siam."},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3054740"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2856317"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964933"},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201359"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392486","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386569.3392486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T05:38:02Z","timestamp":1750829882000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392486"}},"subtitle":["numerically accurate sparsity-oriented QP solver"],"short-title":[],"issued":{"date-parts":[[2020,8,12]]},"references-count":76,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3386569.3392486"],"URL":"https:\/\/doi.org\/10.1145\/3386569.3392486","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,12]]},"assertion":[{"value":"2020-08-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}