1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.