Principal pivoting algorithms for a concave generalized linear complementarity problem

• Type: Article in National Scientific Journal
• Date: 1994

Authors

Ana Maria Faustino (Author) FEUP; J. Júdice (Author) Other

Journal

Title: Revista Investigação Operacional

Vol. 14 No. 2 - Dezembro

Pages: 133-146

Publisher: Associação Portuguesa de Investigação Operacional

Scientific classification

FOS: Engineering and technology > Other engineering and technologies

Other information

Resumo (PT): Neste artigo são discutidos dois algoritmos pivotais principais simples e por biocos para a resolução do problema linear complementar com limites superiores nos valores das variáveis (BLCP) quando a sua matriz é negativa semi-definida- (NSD). Prova-se que ambos os algoritmos têm convergência finita quando M é simétrica NSD. Os algorilmos podem ainda ser utilizados no caso não simétrico, apesar de não se ter conseguido provar convergência finita. Contudo, mostra-se que o algoritmo pivotal por biocos possui convergência finita e é polinomial quando a matriz NSD tem elementos não diagonais do mesmo sinal. As mesmas propriedades são partilhadas pelo algoritmo pivotal simples quando a matriz é não positiva NSD. Finalmente são apresentados alguns resultados computacionais que atestam a grande eficiência dos dois algoritmos para a resolução de BLCPs com matrizes NSD de grandes dimensões.

Abstract (EN): We discuss a single and a block principal pivoting algorithms for the solution of a linear complementarity problem with finite upper-bounds on the variables (BLCP) when its matrix is negative semi-definite (NSD). We show that both algorithms possess finite convergence when M is a symmetric NSD matrix. The algorithms can still process the BLCP in the unsymmetric case, but we have not been able to establish their finite terminations. However. we show that the block algorithm has finite convergence and is strongly polynomial if all the nonzero off diagonal elements of the NSD matrix have the same sign. The same properties are shared by the single method when M is a nonpositive NSD matrix. Computational experience is included to highlight the great efficiency of those two algorithms for the solution of large-scale BLCPs with NSD matrices.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14