A while ago my team was implementing an interior point LP solver and we came across the following conundrum:
Is there a polynomial-time algorithm to find a feasible starting point in linear programming? If so, what is the algorithm?
Of course, it is a well-established result in the literature that LPs can be solved in polynomial-time, and we know from LP theory that the feasibility problem is as hard to solve as the LP.
However, looking deeper into the algorithms (as we had to implement them), we noticed that everything we could find either (i) assumed that a feasible starting point is already known, or (ii) required using an NP-complete/NP-hard method to locate the feasible point with a guarantee (the guarantee part is important).
Even though this is not a big issue in practice because the algorithms work pretty well, we were left with a contradiction between what we knew from theory, and what we could find in the literature (no-one seems to mention this explicitly).
I mentioned this in a couple of answers (namely here and here) and it naturally sparked some controversy, so I think it's an interesting question. It is of course very possible that at the time I missed/misunderstood something about the theoretical complexity of Phase I, so I am keen to know what you guys think!
Note: everything that follows assumes a general LP problem (inequality+equality constraints).
What we know
- Minimising the slack error during interior point is not guaranteed to get us to the interior of the feasible region.
- The ellipsoid method requires a feasible starting point.
- Phase I in the Two-Phase method (which is to identify a feasible basis) requires Simplex iterations, hence is not p-hard (especially if there is no feasible point at all).
- All algorithms we could find were based either on Simplex or Newton's method, neither of which is of polynomial complexity.
Why the worst-case for Newton's method for interior point is not polynomial
There are two main reasons for this. First, one of the assumptions for Newton's method requires us to be in the neighborhood of the solution, which we cannot guarantee in the general case. Second, Newton's method is not quite robust, as it depends not only on the quality of the derivatives but also on the step size. Therefore, the only way to always solve the Newton system in practice is to use a higher complexity method such as Interval Newton or to solve a global optimisation problem.
Characteristics of the polynomial time algorithm
Considering the above, if said algorithm exists I believe that it must have the following characteristics:
- It must always give a feasible point/prove no feasible point exists.
- It must not require a feasible starting point (otherwise it's a chicken and egg problem).
- It must not rely on Simplex pivots.
- It must be possible to implement this algorithm in a way that it works in polynomial-time in practice (see regular Newton vs Interval Newton).