complexity order of the interior point method

Question

I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5?

Much appreciate your time and consideration.

Answer 1

For a linear program in standard form \begin{align} \min_{x} \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b,\\ & x \geq 0, \end{align} where the constraint matrix $A \in \mathbb{R}^{m \times n}$ (i.e., $m$ constraints and $n$ variables) has full row rank (which implies $n \geq m$), the best-known interior-point algorithms require $O(\sqrt{n} \log(1/\epsilon))$ iterations to achieve a precision of $\epsilon$. See for instance the textbook of S. Wright on interior-point methods for a detailed description.

This means that after $O(\sqrt{n} \log(1/\epsilon))$ iterations, you get a primal-dual solution which is feasible and optimal up to some tolerance measured by $\epsilon$. Now, each iteration requires the solution of a linear system of size $m$, whose complexity is roughly $O(n^{3})$ (recall that $n \geq m$).

This gives an overall complexity of $O(n^{3.5} \log(1 / \epsilon))$ to solve the problem to $\epsilon$ accuracy.

PS:

• I am voluntarily vague w.r.t $\epsilon$ since the OP was about complexity w.r.t $n$. There are plenty of details in Wright's book.
• The $O(n^{3})$ is a slight upper estimate: AFAIK, the theoretical complexity for matrix inversion is around $O(n^{2.37})$. In practice, all this is not as relevant since we deal with sparse matrices.