A new algorithm for minimizing convex functions over convex sets
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 37, 338-343
- https://doi.org/10.1109/sfcs.1989.63500
Abstract
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>n/sup 2/.Keywords
This publication has 4 references indexed in Scilit:
- Speeding-up linear programming using fast matrix multiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Geometric Algorithms and Combinatorial OptimizationPublished by Springer Nature ,1988
- A polynomial-time algorithm, based on Newton's method, for linear programmingMathematical Programming, 1988
- Matrix multiplication via arithmetic progressionsPublished by Association for Computing Machinery (ACM) ,1987