Chicken or egg problem: Which comes first duality or numerical precision in following the central path in LP?

73 Views Asked by At

In the interior point method, the path-following version follows the "central path", which is the path that minimizes the Barrier function in a minimization problem $B(x,u) = c^T\cdot x - \mu \cdot \Sigma \log(c_i(x))$ at every value of $\mu$ while varying $\mu$ from $\mu=\infty$ to $\mu=0$. And, I have heard that we follow the central path for different reasons, so I'd like to know what is the real reason.

I have heard from this source that we follow the central path for "numerical reasons ONLY". Because if we vary $\mu$ in a different way, then we would suffer from lack of numerical precision. Because we could be adding numbers of very different orders of magnitude, which is numerically unstable when using floating point precision.

But, there's something else that the central path gives us that I'm surprised is not the reason we follow it -> dual feasibility. If we maintain dual feasibility, then we can know how close we are to the optimal value by using the duality gap ($c^Tx - b^Ty$). Here is a resource that agrees with that: Why do we need to check both primal and dual feasibility in LP programs?

Do we follow the central path for numerical reasons ONLY, or do we follow it because it guarantees us dual feasibility for our stopping conditions?