Méthodes de points intérieurs appliquées au problème de complémentarité linéaire

Abstract

The systematic study of complementarity problems began with the work of R.W Cottle in the 1960s. The importance of complementarity can be measured by the crucial role it plays in solving many problems in different fields. These problems first manifested themselves in the optimality conditions of the optimization problems; the Karush, Kuhn and Tucker conditions of a linear or a quadratic program are equivalent to a linear complementarity problem. This thesis interests with the analysis and implementation of interior-point methods for solving horizontal linear complementarity problem. In chapter 1, we give some notations and definitions that will be used in the following chapters and we introduce the mathematical reformulation of the linear complementarity problem and some of its applications. In chapter 2, we present a theoretical and practical study of the transformation of an absolute value equation to an horizontal linear complementarity problem by introducing an infeasible primal-dual central path method. In chapter 3, we propose a feasible primal-dual interior-point meth-ods for horizontal linear complementarity problem. The method is based on a new class of parametric kernel functions. We show that the corresponding algorithm has the best known iteration bound for large-update methods. Then, we illustrate the performance of the proposed kernel function by some comparative numerical results. In chapter 4, a new variant of Mehrotra type-predictor-corrector al-gorithm is proposed for horizontal linear complementarity problem. We demonstrate the theoretical efficiency of this algorithm by showing its polynomial complexity. We test the practical efficiency and the validity of our algorithm by running some computational tests. Finally, this algorithm is com-pared with a Mehrotra-type predictor-corrector algorithm