An interior point algorithm for convex quadratic programming withstrict equilibrium constraints

Author: Benouahboun Rachid   Mansouri Abdelatif  

Publisher: Edp Sciences

E-ISSN: 1290-3868|39|1|13-33

ISSN: 0399-0559

Source: RAIRO - Operations Research, Vol.39, Iss.1, 2010-03, pp. : 13-33

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We describe an interior point algorithm for convex quadratic problem with astrict complementarity constraints. We show that under some assumptions theapproach requires a total of $O(\sqrt{n}L)$ number of iterations, where Lis the input size of the problem. The algorithm generates a sequence of problems, each of which isapproximately solved by Newton's method.