On Numerical Solution of the Maximum Volume Ellipsoid Problem

Yin Zhang (yzhangcaam.rice.edu)
Liyan Gao (gaolycaam.rice.edu)

Abstract: In this paper we study practical solution methods for finding the maximum-volume ellipsoid inscribing a given full-dimensional polytope in $\Re^n$ defined by a finite set of linear inequalities. Our goal is to design a general-purpose algorithmic framework that is reliable and efficient in practice. To evaluate the merit of a practical algorithm, we consider two key factors: the computational cost per iteration and the typical number of iterations required for convergence. In addition, numerical stability is also an important factor. We investigate some new formulations upon which we build primal-dual type, interior-point algorithms, and we provide theoretical justifications for the proposed formulations and algorithmic framework. Extensive numerical experiments have shown that one of the new algorithms should be the method of choice among the tested algorithms.

Keywords: maximum-volume ellipsoid, interior-point method

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report TR01-15 Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005

Download: [Postscript]

Entry Submitted: 10/26/2001
Entry Accepted: 10/26/2001
Entry Last Modified: 10/30/2001

Modify/Update this entry