{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T22:46:33Z","timestamp":1781563593705,"version":"3.54.5"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T00:00:00Z","timestamp":1684540800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T00:00:00Z","timestamp":1684540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For a given multidimensional data set (point cloud), we investigate methods for computing the <jats:italic>minimum-volume enclosing ellipsoid<\/jats:italic> (MVEE), which provides an efficient representation of the data that is useful in many applications, including data analysis, optimal design, and computational geometry. Contrary to conventional wisdom, we demonstrate that careful exploitation of problem structure can enable high-order (Newton and Newton-like) methods with superlinear convergence rates to scale to very large MVEE problems. We also introduce a hybrid method that combines the benefits of both high-order and low-order methods, along with new initialization schemes that further enhance performance. Observing that computational cost depends significantly on the particular distribution of the data, we demonstrate that <jats:italic>kurtosis<\/jats:italic> serves as an excellent indicator of problem difficulty and provides useful guidance in choosing an appropriate solution algorithm and initialization.\n<\/jats:p>","DOI":"10.1007\/s12532-023-00242-8","type":"journal-article","created":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T11:02:06Z","timestamp":1684580526000},"page":"621-650","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Computing minimum-volume enclosing ellipsoids"],"prefix":"10.1007","volume":"15","author":[{"given":"Nathaniel","family":"Bowman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael T.","family":"Heath","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,5,20]]},"reference":[{"issue":"1","key":"242_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1080\/10556780701589669","volume":"23","author":"SD Ahipa\u015fao\u011flu","year":"2008","unstructured":"Ahipa\u015fao\u011flu, S.D., Sun, P., Todd, M.J.: Linear convergence of a modified Frank\u2013Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optim. Methods Softw. 23(1), 5\u201319 (2008)","journal-title":"Optim. Methods Softw."},{"key":"242_CR2","first-page":"342","volume":"66","author":"CL Atwood","year":"1973","unstructured":"Atwood, C.L.: Sequences converging to D-optimal designs of experiments. Ann. Stat. 66, 342\u2013352 (1973)","journal-title":"Ann. Stat."},{"key":"242_CR3","doi-asserted-by":"publisher","unstructured":"Bowman, N., Heath, M.T.: bowmnath\/mvee: reproducing MVEE paper (2023). https:\/\/doi.org\/10.5281\/ZENODO.7802417","DOI":"10.5281\/ZENODO.7802417"},{"key":"242_CR4","unstructured":"Bowman, N.L.: Computing Minimum-Volume Enclosing Ellipsoids. Ph.D. thesis, University of Illinois at Urbana-Champaign, Urbana (2020). http:\/\/hdl.handle.net\/2142\/109355"},{"key":"242_CR5","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01436084","volume":"7","author":"PA Businger","year":"1965","unstructured":"Businger, P.A., Golub, G.H.: Linear least squares solutions by Householder transformations. Numer. Math. 7, 269\u2013276 (1965)","journal-title":"Numer. Math."},{"key":"242_CR6","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/BF01899996","volume":"8","author":"L Danzer","year":"1957","unstructured":"Danzer, L., Laugwitz, D., Lenz, H.: \u00dcber das L\u00f6wnersche ellipsoid und sein analogon unter den einem eik\u00f6rper einbeschreibenen ellipsoiden. Archiv der Mathematik 8, 214\u2013219 (1957)","journal-title":"Archiv der Mathematik"},{"key":"242_CR7","unstructured":"Dua, D., Graff, C.: UCI machine learning repository (2017). http:\/\/archive.ics.uci.edu\/ml"},{"issue":"1\u20132","key":"242_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956)","journal-title":"Nav. Res. Logist. Q."},{"issue":"1","key":"242_CR9","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1016\/j.spl.2006.05.014","volume":"77","author":"R Harman","year":"2007","unstructured":"Harman, R., Pronzato, L.: Improvements on removing nonoptimal support points in D-optimum design algorithms. Stat. Probab. Lett. 77(1), 90\u201394 (2007)","journal-title":"Stat. Probab. Lett."},{"key":"242_CR10","doi-asserted-by":"crossref","unstructured":"Heath, M.T.: Scientific Computing: An Introductory Survey, rev. 2nd edn. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975581"},{"key":"242_CR11","first-page":"95","volume":"66","author":"M Henk","year":"2012","unstructured":"Henk, M.: L\u00f6wner\u2013John ellipsoids. Doc. Math. 66, 95\u2013106 (2012)","journal-title":"Doc. Math."},{"issue":"4","key":"242_CR12","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1093\/biomet\/asp053","volume":"96","author":"MC Jones","year":"2009","unstructured":"Jones, M.C., Pewsey, A.: Sinh\u2013arcsinh distributions. Biometrika 96(4), 761\u2013780 (2009)","journal-title":"Biometrika"},{"issue":"2","key":"242_CR13","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1287\/moor.21.2.307","volume":"21","author":"LG Khachiyan","year":"1996","unstructured":"Khachiyan, L.G.: Rounding of polytopes in the real number model of computation. Math. Oper. Res. 21(2), 307\u2013320 (1996)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"242_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10957-005-2653-6","volume":"126","author":"P Kumar","year":"2005","unstructured":"Kumar, P., Yildirim, E.A.: Minimum-volume enclosing ellipsoids and core sets. J. Optim. Theory App. 126(1), 1\u201321 (2005)","journal-title":"J. Optim. Theory App."},{"issue":"1","key":"242_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01588950","volume":"14","author":"BA Murtagh","year":"1978","unstructured":"Murtagh, B.A., Saunders, M.A.: Large-scale linearly constrained optimization. Math. Program. 14(1), 41\u201372 (1978)","journal-title":"Math. Program."},{"key":"242_CR16","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.: Numerical Optimization, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"key":"242_CR17","doi-asserted-by":"crossref","unstructured":"Silvey, S.D., Titterington, D.M.: A Geometric Approach to Optimal Design Theory (1973)","DOI":"10.1093\/biomet\/60.1.21"},{"issue":"5","key":"242_CR18","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1287\/opre.1040.0115","volume":"52","author":"P Sun","year":"2004","unstructured":"Sun, P., Freund, R.M.: Computation of minimum-volume covering ellipsoids. Oper. Res. 52(5), 690\u2013706 (2004)","journal-title":"Oper. Res."},{"issue":"2","key":"242_CR19","doi-asserted-by":"publisher","first-page":"313","DOI":"10.2307\/2335366","volume":"62","author":"DM Titterington","year":"1975","unstructured":"Titterington, D.M.: Optimal design: some geometrical aspects of D-optimality. Biometrika 62(2), 313\u2013320 (1975)","journal-title":"Biometrika"},{"key":"242_CR20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974386","volume-title":"Minimum-Volume Ellipsoids: Theory and Algorithms","author":"MJ Todd","year":"2016","unstructured":"Todd, M.J.: Minimum-Volume Ellipsoids: Theory and Algorithms. SIAM, Philadelphia (2016)"},{"issue":"2","key":"242_CR21","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/MCSE.2011.37","volume":"13","author":"S van der Walt","year":"2011","unstructured":"van der Walt, S., Colbert, S.C., Varoquaux, G.: The NumPy array: a structure for efficient numerical computation. Comput. Sci. Eng. 13(2), 22\u201330 (2011)","journal-title":"Comput. Sci. Eng."},{"key":"242_CR22","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1038\/s41592-019-0686-2","volume":"17","author":"P Virtanen","year":"2020","unstructured":"Virtanen, P., et al.: SciPy 1.0: fundamental algorithms for scientific computing in python. Nat. Methods 17, 261\u2013272 (2020). https:\/\/doi.org\/10.1038\/s41592-019-0686-2","journal-title":"Nat. Methods"},{"key":"242_CR23","first-page":"89","volume":"13","author":"VL Zaguskin","year":"1958","unstructured":"Zaguskin, V.L.: Circumscribed and inscribed ellipsoids of extremal volume. Uspehi Matematicheskikh Nauk 13, 89\u201393 (1958). (in Russian)","journal-title":"Uspehi Matematicheskikh Nauk"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-023-00242-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-023-00242-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-023-00242-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,14]],"date-time":"2023-10-14T14:11:41Z","timestamp":1697292701000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-023-00242-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,20]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["242"],"URL":"https:\/\/doi.org\/10.1007\/s12532-023-00242-8","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,20]]},"assertion":[{"value":"21 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Neither author has any relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}