A Deep Cut Ellipsoid Algorithm for convex Programming: theory and Applications

J.B.G. Frenk, J.A. Gromicho Dos Santos, S. Zhang

    Research output: Contribution to JournalArticleAcademic


    This paper proposes a deep cut version of the ellipsoid algorithm for solving a general class of continuous convex programming problems. In each step the algorithm does not require more computational effort to construct these deep cuts than its corresponding central cut version. Rules that prevent some of the numerical instabilities and theoretical drawbacks usually associated with the algorithm are also provided. Moreover, for a large class of convex programs a simple proof of its rate of convergence is given and the relation with previously known results is discussed. Finally some computational results of the deep and central cut version of the algorithm applied to a min-max stochastic queue location problem are reported. © 1994 The Mathematical Programming Society, Inc.
    Original languageEnglish
    Pages (from-to)83-108
    JournalMathematical Programming
    Issue number1
    Publication statusPublished - 1994


    Dive into the research topics of 'A Deep Cut Ellipsoid Algorithm for convex Programming: theory and Applications'. Together they form a unique fingerprint.

    Cite this