Optimizing over three-dimensional subspaces in an interior-point method for linear programming (Q808189)

The authors discuss an enhanced version of the dual affine interior point method for linear programming. At each iterate, three search directions are considered: the dual affine direction, a rank-one correction to this direction which depends on the first constraint encountered by it, and a third-order correction term. A search is then performed to minimize the (linear) objective function on the three-dimensional manifold formed by these three search directions. A step of 99 \% of the distance to the boundary of the feasible polytope is taken. Numerical results on the netlib test set show that the algorithm runs about 20 \% faster than the authors' efficient implementation of the unadorned dual affine variant.