Inexact Approach for Interior Point Methods for Large Scale Quadratic Optimization


Abstract in English

Interior point methods are considered the most powerful tools for solving linear, quadratic and nonlinear programming. In each iteration of interior point method (IPM) at least one linear system has to be solved. The main computational effort of IPMs consist in the computational of these linear systems. That drives many researchers to tackle this subject, which make this area of research very active. The issue of finding a preconditioner for this linear system was investigated in many papers. In this paper, we provide a preconditioner for interior point methods for quadratic programming. This preconditioner makes the system easier to be solved comparing with the direct approach. The preconditioner used follows the ideas, which is used for linear approach. An explicit null space representation of linear constraints is constructed by using a non-singular basis matrix identified from an estimate of the optimal partition. This is achieved by means of efficient basis matrix factorisation techniques used in implementations of the revised simplex method.

References used

Al-Jeiroudi, G. and Gondzio, J. (2009). Convergence analysis of inexact infeasible interior point method for linear optimization. Journal on Optimization Theory and Applications, V.247, pp. 141:231
Al-Jeiroudi, G. Gondzio, J. and Hall, J. (2008). Preconditioning indefinite systems in interior point methods for large scale linear optimization. Optimization Methods and Software, V.23, pp.345–363
Andersen, E. Gondzio, J. Meszaros, C. and Xu, X. (1996). Implementation of interior point methods for large scale linear programming. In T. Terlaky, editor, Interior Point Methods in Mathematical Programming, Kluwer Academic Publishers, pp. 189–252

Download