Aperfeiçoamento de precondicionadores para solução de sistemas lineares dos métodos de pontos interiores

• Processo: 09/16171-3
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Data de Início da vigência: 01 de abril de 2010
• Data de Término da vigência: 31 de julho de 2014
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Aurelio Ribeiro Leite de Oliveira
• Beneficiário: Luciana Casacio
• Instituição Sede: Faculdade de Engenharia Elétrica e de Computação (FEEC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Métodos iterativos Métodos de pontos interiores Programação linear
• Palavra(s)-Chave do Pesquisador: Métodos de Pontos Interiores | Métodos Iterativos | Precondicionadores | Sistemas Lineares Esparsos | Programação Linear

Resumo

A solução de problemas de otimização linear através de métodos de pontos interiores envolve a solução de sistemas lineares. Esses sistemas quase sempre possuem dimensões elevadas e alto grau de esparsidade em aplicações reais. Para solução, tipicamente são realizadas operações algébricas que os reduzem a duas formulações mais simples: uma delas, conhecida por "sistema aumentado", envolve matrizes simétricas indefinidas e geralmente esparsas; a outra, denominada "sistema de equações normais", usa matrizes de menor dimensão, simétricas e definidas positivas.A solução dos sistemas lineares é a fase que requer a maior parte do tempo de processamento dos métodos de pontos interiores. Consequentemente, a escolha dos métodos de solução é de extrema importância para que se tenha uma implementação eficiente. Normalmente, aplicam-se métodos diretos para a solução como, por exemplo, a fatoração de Bunch-Parllett ou a fatoração de Cholesky. No entanto, em problemas de grande porte, o uso de métodos diretos torna-se desaconselhável, por limitações de tempo e memória. Nesses casos, abordagens iterativas se tornam mais atraentes.O sucesso da implementação de métodos iterativos depende do uso de bons precondicionadores, pois a matriz de coeficientes torna-se muito mal condicionada, principalmente próximo da solução ótima. Uma alternativa para tratar o problema de malcondicionamento é o uso de abordagens híbridas com duas fases: a fase I utiliza um precondicionador para o sistema de equações normais construído com informações de fatorações incompletas, denominado fatoração controlada de Cholesky; a fase II, utilizada nas últimas iterações, adota o precondicionador separador desenvolvido especificamente para sistemas mal condicionados.O projeto propõe um novo critério de ordenamento das colunas para construção do precondicionador separador, que preservaa estrutura esparsa da matriz de coeficientes original a fim de economizar tempo de processamento e memória.

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

CASACIO, Luciana. Aperfeiçoamento de precondicionadores para solução de sistemas lineares dos métodos de pontos interiores. 2015. Tese de Doutorado - Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação Campinas, SP.