In this article a primaldual interiorpoint method for solving linear programs is proposed. A new approach for generating higherorder search directions, and a new method for an efficient higherorder subspace search along several search directions are the basis of the proposed extension. The subspace search is reduced to a linear program in several variables. The method using the simplest (twodimensional) subprograms is a slight variation of Mehrotra's predictorcorrector method, and is thus known to be practically very efficient. The higherdimensional subproblems are guaranteed to be at least as effective --- with respect to a certain measure --- as the twodimensional ones. Numerical experiments with the PCxpackage indicate that also in practice the higher order subspace search is very cheap and efficient. |