- | ||||
|
![]()
|
The s-Monotone Index Selection Rule for Criss-Cross Algorithms of Linear Complementarity Problems
Csizmadia Zsolt(zsolt.csizmadia Abstract: In this paper we introduce the s-monotone index selection rules for the well-known crisscross method for solving the linear complementarity problem (LCP). Most LCP solution methods require a priori information about the properties of the input matrix. One of the most general matrix properties often required for finiteness of the pivot algorithms (or polynomial complexity of interior point algorithms) is sufficiency. However, there is no known polynomial time method for checking the sufficiency of a matrix (classification of column sufficiency of a matrix is co-NP-complete). Following the ideas of Fukuda, Namiki and Tamura, using Existentially Polynomial (EP)- type theorems, a simple extension of the criss-cross algorithm is introduced for LCPs with general matrices. Computational results obtained using the extended version of the crisscross algorithm for bi-matrix games and for the Arrow-Debreu market equilibrium problem with different market size is presented. Keywords: Linear complementarity problems, Criss-cross method, pivot rule, index selection rule Category 1: Complementarity and Variational Inequalities Category 2: Linear, Cone and Semidefinite Programming (Other ) Citation: submitted Download: [PDF] Entry Submitted: 02/24/2013 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |