Picture of a black hole

Strathclyde Open Access research that creates ripples...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of research papers by University of Strathclyde researchers, including by Strathclyde physicists involved in observing gravitational waves and black hole mergers as part of the Laser Interferometer Gravitational-Wave Observatory (LIGO) - but also other internationally significant research from the Department of Physics. Discover why Strathclyde's physics research is making ripples...

Strathprints also exposes world leading research from the Faculties of Science, Engineering, Humanities & Social Sciences, and from the Strathclyde Business School.

Discover more...

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

Illes, T. and Nagy, M. and Terlaky, T. (2010) A polynomial path-following interior point algorithm for general linear complementarity problems. Journal of Global Optimization, 47 (3). pp. 329-342. ISSN 0925-5001

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

Linear Complementarity Problems (LCPs) belong to the class of -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 , with arbitrary large, but apriori fixed ). In the latter case, the algorithms give a polynomial size certificate depending on parameter , 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.