Minimum-volume ellipsoids : theory and algorithms / Michael J. Todd, Cornell University, Ithaca, New York.

Format:

Book

Author/Creator:

Todd, Michael J., 1947- author.

Contributor:

Society for Industrial and Applied Mathematics, publisher.

Series:

MOS-SIAM series on optimization.

MOS-SIAM series on optimization ; 23

Language:

English

Subjects (All):

Ellipse.

Cylinders.

Physical Description:

1 PDF (xiv, 149 pages).

Other Title:

Ellipsoids.

Place of Publication:

Philadelphia, Pennsylvania : Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), [2016]

Language Note:

English

System Details:

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Summary:

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. This book 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, and highlights the difficulties in algorithms when related problems are studied that do not allow simple updates at each iteration; and gives rigorous analyses of the proposed algorithms, MATLAB codes, and computational results.

Contents:

Preface

1. Introduction

2. Minimum-volume ellipsoids

3. Algorithms for the MVEE problem

4. Minimum-Area ellipsoidal cylinders

5. Algorithms for the MAEC problem

6. Related Problems and algorithms

Appendix A. Background material

Appendix B. MATLAB codes.

Notes:

Bibliographic Level Mode of Issuance: Monograph

Includes bibliographical references and index.

Description based on title page of print version.

ISBN:

1-61197-438-0

Publisher Number:

MO23 SIAM