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

T. Illes, M. Nagy, T. Terlaky

Research output: Contribution to journalArticle

13 Citations (Scopus)

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.
LanguageEnglish
Pages329-342
Number of pages13
JournalJournal of Global Optimization
Volume47
Issue number3
DOIs
Publication statusPublished - Jul 2010

Fingerprint

Path-following Algorithm
Interior-point Algorithm
Linear Complementarity Problem
Polynomial time
Polynomials
Polynomial
Duality Theorems
Interior Point
Certificate
Linear complementarity problem
Arbitrary
Coefficient

Keywords

  • linear complementarity problems
  • LCPs
  • polynomial
  • sufficient matrix
  • long-step method

Cite this

@article{55f7107d1d044d1d90ff2d02bc1e1802,
title = "A polynomial path-following interior point algorithm for general linear complementarity problems",
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.",
keywords = "linear complementarity problems, LCPs, polynomial, sufficient matrix, long-step method",
author = "T. Illes and M. Nagy and T. Terlaky",
year = "2010",
month = "7",
doi = "10.1007/s10898-008-9348-0",
language = "English",
volume = "47",
pages = "329--342",
journal = "Journal of Global Optimization",
issn = "0925-5001",
number = "3",

}

A polynomial path-following interior point algorithm for general linear complementarity problems. / Illes, T.; Nagy, M.; Terlaky, T.

In: Journal of Global Optimization, Vol. 47, No. 3, 07.2010, p. 329-342.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Illes, T.

AU - Nagy, M.

AU - Terlaky, T.

PY - 2010/7

Y1 - 2010/7

N2 - 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.

AB - 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.

KW - linear complementarity problems

KW - LCPs

KW - polynomial

KW - sufficient matrix

KW - long-step method

UR - http://portal.acm.org/citation.cfm?id=1825423

U2 - 10.1007/s10898-008-9348-0

DO - 10.1007/s10898-008-9348-0

M3 - Article

VL - 47

SP - 329

EP - 342

JO - Journal of Global Optimization

T2 - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 3

ER -