Optimization Online


Polynomial interior point algorithms for general LCPs

Tibor Illés(illes***at***math.elte.hu)
Marianna Nagy(nmariann***at***cs.elte.hu)
Tamás Terlaky(terlaky***at***mcmaster.hu)

Abstract: Linear Complementarity Problems ($LCP$s) belong to the class of $\mathbb{NP}$-complete problems. Therefore we can not expect a polynomial time solution method for $LCP$s without requiring some special property of the matrix coefficient matrix. Our aim is to construct some interior point algorithms which, according to the duality theorem in EP form, gives a solution of the original problem or detects the lack of property $\mathcal{P}_*(\tilde\kappa)$ (with arbitrary large, but apriori fixed $\tilde\kappa$) and gives a polynomial size certificate of it in polynomial time (depending on parameter $\tilde{\kappa}$, the initial interior point and the dimension of the $LCP$). We give the general idea of a modification of interior point algorithms and present three concrete methods: affine scaling, long-step path-following and predictor-corrector interior point algorithm.

Keywords: LCP, interior point method, sufficient matrix, EP theorem

Category 1: Linear, Cone and Semidefinite Programming

Citation: unpublished: ORR 2007-3 Eötvös Loránd University of Sciences, Department of Operations Research, Budapest, Hungary 02/2007

Download: [PDF]

Entry Submitted: 04/10/2007
Entry Accepted: 04/10/2007
Entry Last Modified: 04/10/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society