A polynomial path-following interior point algorithm for general linear complementarity problems

A polynomial path-following interior point algorithm for general linear complementarity problems

0.00 Avg rating0 Votes
Article ID: iaor20104861
Volume: 47
Issue: 3
Start Page Number: 329
End Page Number: 342
Publication Date: Jul 2010
Journal: Journal of Global Optimization
Authors: , ,
Keywords: interior point methods
Abstract:

Linear Complementarity Problems (LCPs) belong to the class of NP -complete problems. Therefore we cannot expect a polynomial time solution method for LCPs without requiring some special property of the coefficient matrix. Our aim is to construct interior point algorithms which, according to the duality theorem in EP (Existentially Polynomial-time) form, in polynomial time either give a solution of the original problem or detects the lack of property 𝒫*(κ˜) equ1 , with arbitrary large, but apriori fixed κ˜ equ2). In the latter case, the algorithms give a polynomial size certificate depending on parameter κ˜ equ3 , the initial interior point and the input size of the LCP). We give the general idea of an EP-modification of interior point algorithms and adapt this modification to long-step path-following interior point algorithms.

Reviews

Required fields are marked *. Your email address will not be published.