Global linear convergent algorithm to compute the minimum volume enclosing ellipsoid

arXiv1702.06254MaRDI QIDQ6283425FDOQ6283425

Publication date: 20 February 2017

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.

Mathematics Subject Classification ID

Convex programming (90C25) Nonlinear programming (90C30) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

This page was built for publication: Global linear convergent algorithm to compute the minimum volume enclosing ellipsoid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283425)