On numerical solution of the maximum volume ellipsoid problem We study practical solution methods for finding the maximum volume ellipsoid inscribing a given full-dimensional polytope in ℜ 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 (Source:

References in zbMATH (referenced in 13 articles , 1 standard article )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Lu, Haihao; Freund, Robert M.; Nesterov, Yurii: Relatively smooth convex optimization by first-order methods, and applications (2018)
  2. Diouane, Y.; Gratton, S.; Vicente, L. N.: Globally convergent evolution strategies for constrained optimization (2015)
  3. Shekhar, Rohan C.; Manzie, Chris: Optimal move blocking strategies for model predictive control (2015)
  4. Belloni, Alexandre; Freund, Robert M.: Projective re-normalization for improving the behavior of a homogeneous conic linear system (2009)
  5. Vaz, A. I. F.; Vicente, L. N.: PSwarm: a hybrid solver for linearly constrained global derivative-free optimization (2009)
  6. Gotoh, Jun-Ya; Takeda, Akiko: Conditional minimum volume ellipsoid with application to multiclass discrimination (2008)
  7. Shioda, Romy; Tunçel, Levent: Clustering via minimum volume ellipsoids (2007)
  8. Todd, Michael J.; Yıldırım, E. Alper: On Khachiyan’s algorithm for the computation of minimum-volume enclosing ellipsoids (2007)
  9. Gotoh, Jun-Ya; Konno, Hiroshi: Minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities (2006)
  10. Xie, Yulai; Snoeyink, Jack; Xu, Jinhui: Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope (2006)
  11. Kumar, P.; Yildirim, E. A.: Minimum-volume enclosing ellipsoids and core sets (2005)
  12. Zhang, Yin; Gao, Liyan: On numerical solution of the maximum volume ellipsoid problem (2003)
  13. Anstreicher, Kurt M.: Improved complexity for maximum volume inscribed ellipsoids (2002)