An algorithm for minimizing a convex function over a convex set is given. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope is central to the algorithm. The algorithm has a much better rate of global convergence than the ellipsoid algorithm. A by-product of the algorithm is an algorithm for solving linear programming problems that performs a total of O(mn/sup 2/L+M(n)nL) arithmetic operations in the worst case, where m is the number of constraints, n the number of variables, and L a certain parameter. This gives an improvement in the time complexity of linear programming for m展开▼
机译：给出了最小化凸集上凸函数的算法。多面体的体积中心和该多面体中不可包涵的最大体积的相关椭球的概念是该算法的核心。与椭圆算法相比，该算法的全局收敛速度要好得多。该算法的副产品是用于解决线性规划问题的算法，该算法在最坏的情况下总共执行O（mn / sup 2 / L + M（n）nL）个算术运算，其中m是约束数， n变量的数量，L为某个参数。对于m 展开▼
