Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming

Technical Report ERGO-12-008

J. Gondzio

In this paper we will discuss two variants of an inexact feasible interior point algorithm for convex quadratic programming. We will consider two different neighbourhoods: a (small) one induced by the use of the Euclidean norm which yields a short-step algorithm and a symmetric one induced by the use of the infinity norm which yields a (practical) long-step algorithm. Both algorithms allow for the Newton equation system to be solved inexactly. For both algorithms we will provide conditions for the level of error acceptable in the Newton equation and establish the worst-case complexity results.

Key words: Inexact Newton Method, Interior Point Algorithms, Linear Programming, Quadratic Programming, Worst-case Complexity Analysis, Matrix-Free Methods.

PDF ERGO-12-008.pdf.

Written: July 25, 2012, revised February 14, 2013.
Published: SIAM Journal on Optimization 23 (2013) No 3, pp. 1510-1527.
Published online: July 30, 2013.