Minimum-Volume Covering Ellipsoids: Improving the Efficiency of the Wolfe-Atwood Algorithm for Large-Scale Instances by Pooling and Batching

Jakub Kudela

doi:10.13164/mendel.2019.2.019

Jakub Kudela

DOI: https://doi.org/10.13164/mendel.2019.2.019

Keywords: minimum-volume covering ellipsoid, Lowner-John ellipsoid, large-scale optimization, Wolfe-Atwood algorithm, pooling, batching

Abstract

The Minimum-Volume Covering Ellipsoid (MVCE) problem is an important optimization problem that comes up in various areas of engineering and statistics. In this paper, we improve the state-of-the-art Wolfe-Atwood algorithm for solving the MVCE problem with pooling and batching procedures. This implementation yields significant improvements on the runtime of the algorithm for large-scale instances of the MVCE problem, which is demonstrated on quite extensive computational experiments.

References

Todd, M. J. 2016. Minimum-Volume Ellipsoids: Theory and Algorithms. SIAM, Philadelphia, USA. ISBN 9781611974379.

Danzer, L., Laugwitz, D., and Lenz, H. 1957. Uber das Lownersche ellipsoid und sein analogon unter den einem eikorper einbeschreibenen ellipsoiden. Archiv der Mathematik 8,l pp. 214–219.

Zaguskin, V. L. 1958. Circumscribed and inscribed ellipsoids of extremal volume (in Russian). Uspehi Matematicheskikh Nauk 13, pp. 89–93.

John, F. 1948. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays, presented to R. Courant on his 60th birthday, Interscience, New York, pp. 187–204.

Silvey, S. D. 1980. Optimal Design: An Introduction to the Theory for Parameter Estimation. Chapman and Hall, New York.

Silverman, B. W. and Titterington, D. M. 1980. Minimum covering ellipses. SIAM Journal on Scientific and Statistical Computing 1, pp. 401–409.

Holesovsky, J. and Kudela, J. 2016. Outlier identification based on local extreme quantile estimation. Mendel, 22, 1, pp. 255–260.

Somplak, R., Smidova, Z., Smejkalova, V., and Nevrly, N. 2018. Statistical evaluation of large-scale data logistics system. Mendel, 24, 2, pp. 9–16. doi: 10.13164/mendel.2018.2.009

Gill, P. E., Golub, G. H., Murray, W. , and Saunders, M. A. 1974. Methods for modifying matrix factorizations. Mathematics of Computation 28, 505–535.

Viktorin, A., Senkerik, R., Pluhacek, M., and Kadavy T. 2018. Clustering analysis of the population in Db SHADE algorithm. Mendel, 24, 1, pp. 9–16. DOI:10.13164/mendel.2018.1.009

Grabusts, P. 2018. Numerical data clustering ontology approach. Mendel, 24, 1, pp. 31–38. doi:10.13164/mendel.2018.1.031

Hrabec, D., Kudela, J., Somplak, R., Nevrly, V., and Popela, P. 2019. Circular economy implementation in waste management network design problem: a case study. Preprint in Central European Journal of Operations Research. DOI: 10.1007/s10100-019-00626-z

Chernousko, F. L. 2005. Ellipsoidal state estimation for dynamical systems. Nonlinear Analysis 63, pp. 872–879.

Eberly, D. 2001. 3D Game Engine Design. Morgan Kaufmann, San Francisco, CA.

Lacoste-Julien, S. and Jaggi, M. 2015. On the global linear convergence of Frank-Wolfe optimization variants. In C. Cortes et al., editors, Advances in Neural Information Processing Systems 28 (NIPS 2015), Curran Associates, Inc., New York, pp. 496–504.

Pena, J. and Rodriguez, D. 2015. Polytope conditioning and linear convergence of the Frank-Wolfe algorithm. Technical report. Tepper School of Business, Carnegie-Mellon University, Pittsburgh, PA.

Wolfe, P. 1970. Convergence theory in nonlinear programming. In J. Abadie, editor, Integer and Nonlinear Programming, North-Holland, Amsterdam, pp. 1–36.

Atwood, C. L. 1973. Sequences converging to D-optimal designs of experiments. The Annals of Statistics 1, pp. 342–352.

Kumar, P. and Yildirim, E. A. 2005. Minimum-volume enclosing ellipsoids and core sets. J. Optimization Theory and Applications 126, 1, pp. 1–21.

Kudela, J. and Popela, P. 2018. Chance constrained optimal beam design: Convex reformulation and probabilistic robust design. Kybernetika 54, 6, pp. 1201–1217.

Kudela, J. 2019. Advanced Decomposition Methods in Stochastic Convex Optimization. Doctoral thesis, Brno University of Technology, Brno, Czech Republic.

Todd, M. J. and Yildirim, E. A. 2007. On Khachiyan's algorithm for the computation of minimum volume enclosing ellipsoids. Discrete and Applied Mathematics 155, 13, pp. 1731–1744.

Boyd, S. and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press.

Frank, M. and Wolfe, P. 1956. An algorithm for quadratic programming. Naval Research Logistics Quarterly 3, pp. 95–110.

Fedorov, V. V. 1972. Theory of Optimal Experiments. Academic Press, New York.

Wynn, H. P. 1970. The sequential generation of D-optimum experimental design. Annals of Mathematical Statistics 41, pp. 1655–1664.

Ahipasaoglu, S. D., Sun, P., and Todd, M. J. 2008. Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optimization Methods and Software 23, pp. 5–19.

Sun, P. and Freund, R. M. 2004. Computation of minimum volume covering ellipsoids. Operations Research 52, pp. 690–706.

Khachiyan, L. G. 1996. Rounding of polytopes in the real number model of computation. Mathematics of Operations Research 21, 307–320.

Betke, U. and Henk, M. 1993. Approximating the volume of convex bodies. Discrete Computational Geometry 10, 15–21.

Harman, R. and Pronzato, L. 2007. Improvements on removing nonoptimal support points in D-optimum design algorithms. Statistics and Probability Letters 77, pp. 90–94.

Ahipasaoglu, S. D. 2009. Solving ellipsoidal inclusion and optimal experimental design problems: Theory and algorithms. Doctoral thesis, Cornell University, Ithaca, NY.

Kudela, J. and Popela, P. 2017. Warm-start cuts for Generalized Benders Decomposition. Kybernetika 53, 6, pp. 1012–1025. doi:10.14736/kyb-2017-6-1012

Ahipasaoglu, S. D. 2015. Fast algorithms for the minimum volume estimator. J. Global Optimization 62, pp. 351–370. doi: 10.1007/s10898-014-0233-8