An infeasible interior point methods for convex quadratic problems

Abstract

In this paper, we deal with the study and implementation of an infeasible interior point method for convex quadratic problems (CQP). The algorithm uses a Newton step and suitable proximity measure for approximately tracing the central path and guarantees that after one feasibility step, the new iterate is feasible and suciently close to the central path. For its complexity analysis, we reconsider the analysis used by the authors for linear optimisation (LO) and linear complementarity problems (LCP). We show that the algorithm has the best known iteration bound, namely \(n log (n+1)\). Finally, to measure the numerical performance of this algorithm, it was tested on convex quadratic and linear problems.

Keywords

• Convex quadratic programs
• Infeasible interior-point method
• Newton step