On Numerical Solution of the Maximum Volume Ellipsoid Problem
On Numerical Solution of the Maximum Volume Ellipsoid Problem
复制标题
DOI：
10.1137/s1052623401397230
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Yin Zhang;Liyan Gao
中科院分区：
文献类型：
--
作者：
Yin Zhang;Liyan Gao
在本文中，我们研究实际的解决方法，寻找最大体积椭球内接一个给定的全维多面体在$\Re^n$定义的一组有限的线性不等式。我们的目标是设计一个通用的算法框架，在实践中是可靠和有效的。为了评估一个实用算法的优点，我们考虑两个关键因素：每次迭代的计算成本和收敛所需的典型迭代次数。此外，数值稳定性也是一个重要因素。我们研究了一些新的配方上，我们建立原始-对偶类型的邻近点算法，我们提出的配方和算法框架提供了理论依据。大量的数值实验表明，新的算法之一是那些测试中的选择方法。
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 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 is the method of choice among those tested.