
Minimum-Volume Ellipsoids
Theory and Algorithms
Michael J. Todd(Author)
Society for Industrial & Applied Mathematics,U.S. (Publisher)
Published on 30. July 2016
Book
Paperback/Softback
164 pages
978-1-61197-437-9 (ISBN)
Description
This book, the first on these topics, addresses the problem of finding an ellipsoid to represent a large set of points in high-dimensional space, which has applications in computational geometry, data representations, and optimal design in statistics. The book covers the formulation of this and related problems, theoretical properties of their optimal solutions, and algorithms for their solution. Due to the high dimensionality of these problems, first-order methods that require minimal computational work at each iteration are attractive. While algorithms of this kind have been discovered and rediscovered over the past fifty years, their computational complexities and convergence rates have only recently been investigated. The optimization problems in the book have the entries of a symmetric matrix as their variables, so the author's treatment also gives an introduction to recent work in matrix optimization.
Provides historical perspective on the problems studied by optimizers, statisticians, and geometric functional analysts.
Demonstrates the huge computational savings possible by exploiting simple updates for the determinant and the inverse after a rank-one update.
Highlights the difficulties in algorithms when related problems are studied that do not allow simple updates at each iteration.
Gives rigorous analyses of the proposed algorithms, MATLAB codes, and computational results.
Provides historical perspective on the problems studied by optimizers, statisticians, and geometric functional analysts.
Demonstrates the huge computational savings possible by exploiting simple updates for the determinant and the inverse after a rank-one update.
Highlights the difficulties in algorithms when related problems are studied that do not allow simple updates at each iteration.
Gives rigorous analyses of the proposed algorithms, MATLAB codes, and computational results.
More details
Series
Language
English
Place of publication
New York
United States
Target group
Professional and scholarly
Product notice
Paperback (trade)
Dimensions
Height: 254 mm
Width: 178 mm
Thickness: 12 mm
Weight
380 gr
ISBN-13
978-1-61197-437-9 (9781611974379)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Person
Michael J. Todd is Leon C. Welch Professor Emeritus of the School of Operations Research and Information Engineering at Cornell University. He received a Guggenheim Fellowship (1980-1981), a Sloan Research Fellowship (1981-1985), the George B. Dantzig Prize (1988) and the John von Neumann Theory Prize (2003). He is an INFORMS Fellow and a SIAM Fellow. He has served on the editorial boards of Mathematics of Operations Research, Operations Research, and the SIAM Journal on Optimization. He was also Managing Editor of Foundations of Computational Mathematics and has served on the boards of Acta Numerica and Foundations and Trends in Optimization. He is the author of one book and the co-editor of five others.
Content
Chapter 1: Introduction
Chapter 2: Minimum-Volume Ellipsoids
Chapter 3: Algorithms for the MVEE Problem
Chapter 4: Minimum-Area Ellipsoidal Cylinders
Chapter 5: Algorithms for the MAEC Problem
Chapter 6: Related Problems and Algorithms
Appendix A: Background Material
Appendix B: MATLAB Codes
Chapter 2: Minimum-Volume Ellipsoids
Chapter 3: Algorithms for the MVEE Problem
Chapter 4: Minimum-Area Ellipsoidal Cylinders
Chapter 5: Algorithms for the MAEC Problem
Chapter 6: Related Problems and Algorithms
Appendix A: Background Material
Appendix B: MATLAB Codes