An improved search direction based on algebraic equivalent transformation technique for convex quadratic optimization

Abstract

This work presents an improved interior point algorithm with full Newton step for convex quadratic optimization. Based on the technique of algebraic equivalent transformation, we first propose a new search direction for convex quadratic optimization with the aim of improving the algorithmic complexity of the proposed algorithm. We then perform a complete theoretical study of convergence and complexity, proving that our algorithm is well-defined, converge quadratically and achieves the best known polynomial complexity bounds established for primal-dual interior point methods. Following this, we conduct comparative numerical tests to evaluate the efficiency of the algorithm. The theoretical and numerical results are encouraging and clearly confirm our purpose.