Ellipsoid method (General, Constrained optimization Convex Optimization (Non-linear))

From Algorithm Wiki
Jump to navigation Jump to search

Time Complexity

$O(n^{2} \log n)$

Space Complexity

$O(nmL)$ words

(see orginal paper (noting that O(alpha*log(H*alpha)) = O(L)))

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1971

Reference

https://www.sciencedirect.com/science/article/abs/pii/0041555380900610