Title: Global linear convergent algorithm to compute the minimum volume enclosing ellipsoid,
Abstract: The minimum volume enclosing ellipsoid (MVEE) problem is an optimization
problem in the basis of many practical problems. This paper describes some new
properties of this model and proposes a first-order oracle algorithm, the
Adjusted Coordinate Descent (ACD) algorithm, to address the MVEE problem. The
ACD algorithm is globally linear convergent and has an overwhelming advantage
over the other algorithms in cases where the dimension of the data is large.
Moreover, as a byproduct of the convergence property of the ACD algorithm, we
prove the global linear convergence of the Frank-Wolfe type algorithm
(illustrated by the case of Wolfe-Atwood's algorithm), which supports the
conjecture of Todd. Furthermore, we provide a new interpretation for the means
of choosing the coordinate axis of the Frank-Wolfe type algorithm from the
perspective of the smoothness of the coordinate axis, i.e., the algorithm
chooses the coordinate axis with the worst smoothness at each iteration. This
finding connects the first-order oracle algorithm and the linear optimization
oracle algorithm on the MVEE problem. The numerical tests support our
theoretical results.