# complexity order of the interior point method

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.

## 1 Answer

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.