New infeasible interior-point algorithm based on monomial method

The authors propose a new infeasible path-following algorithm for the convex linearly-constrained quadratic programming problem. This algorithm utilizes the monomial method rather than Newton’s method for solving the Karush-Kahn-Tucker (KKT) equations at each iterion. As a result, the sequence of iterates generated by this new algorithm is infeasible in the primal and dual linear constraints, but, unlike the sequence of iterates generated by other path-following algorithms, does satisfy the complementarity equations. Performance of this new algorithm is demonstrated by the results of solving QP problems (both separable and non-separable) which are constructed so as to have known optimal solutions. Additionally, results of solving continuous quadratic knapsack problems indicate that for problems of a given size, the computational time of this new algorithm is less variable than other algorithms.