Principal pivoting algorithms for a concave generalized linear complementarity problem

• Tipo: Artigo em Revista Científica Nacional
• Data: 1994

Autores

Ana Maria Faustino (Autor) FEUP; J. Júdice (Autor) Outra

Revista

Título: Revista Investigação Operacional

Vol. 14 Nº 2 - Dezembro

Páginas: 133-146

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

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Outras ciências da engenharia e tecnologias

Outras Informações

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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14