ellipsoid method

On Khachiyan’s Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids

  • Michael J. Todd
  • E. Alper Yildirim
    • Categories Convex Optimization Tags , , , ,

    Given $\cA := \{a^1,\ldots,a^m\} \subset \R^d$ whose affine hull is $\R^d$, we study the problems of computing an approximate rounding of the convex hull of $\cA$ and an approximation to the minimum volume enclosing ellipsoid of $\cA$. In the case of centrally symmetric sets, we first establish that Khachiyan’s barycentric coordinate descent (BCD) method is … Read more

    A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

  • Renato D.C. Monteiro
  • Arkadi Nemirovski
  • Jerome W. O'Neal
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , , ,

    The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the … Read more