A New Hybrid Preconditioner for the Interior Point Method

AUTOR(ES)
FONTE

TEMA (São Carlos)

DATA DE PUBLICAÇÃO

16/09/2019

RESUMO

RESUMO Este trabalho visa melhorar o cálculo da direção de busca no Método de Pontos Interiores primal-dual usando métodos iterativos precondicionados. Trata-se de uma abordagem híbrida que combina o precondicionador Fatoração Controlada de Cholesky e o precondicionador Separador. Esta abordagem tem mostrado bons resultados, entretanto, nesses précondicioandores existem fatores que reduzem sua eficiência, como falhas na diagonal ao calcular a Fatoração Incompleta de Cholesky, assim como a demanda por memória excessiva no precondicionador Separador, entre outros. Assim, algumas modificações são propostas nestes precondicionadores, bem como uma nova mudança de fase, a fim de melhorar o desempenho da aboradagem híbrida. Na Fatoração Controlada de Cholesky, os parâmetros que controlam o preenchimento e a correção das falhas que ocorrem na diagonal são modificados, para tal considera-se a relação entre os componentes da Fatoração Controlada de Cholesky obtidos antes e depois da falha na diagonal. No precondicionador Separador, por sua vez, a base esparsa é construída usando um ordenamento apropriado das colunas da matriz do problema de otimização. Além disso, é apresentado um resultado teórico que mostra que, com a ordenação proposta, o número da condição da matriz de Equações Normais precondicionada com o Precondicionador Separador é uniformemente limitado por uma quantidade que depende apenas dos dados originais do problema e não da iteração do Método do Pontos Interiores. Experimentos numéricos com problemas de grande porte corroboram a robustez e eficiência computacional desta abordagem.ABSTRACT This study aims to improve the computation of the search direction in the primal-dual Interior Point Method through preconditioned iterative methods. It is about a hybrid approach that combines the Controlled Cholesky Factorization preconditioner and the Splitting preconditioner. This approach has shown good results, however, in these preconditioners there are factors that reduce their efficiency, such as faults on the diagonal when performing the Cholesky factorization, as well as a demand for excessive memory, among others. Thus, some modifications are proposed in these preconditioners, as well as a new phase change, in order to improve the performance of the hybrid preconditioner. In the Controlled Cholesky Factorization, the parameters that control the fill-in and the correction of the faults which occur on the diagonal are modified. It considers the relationship between the components from Controlled Cholesky Factorization obtained before and after the fault on the diagonal. In the Splitting preconditioner, in turn, a sparse base is constructed through an appropriate ordering of the columns from constrained matrix optimization problem. In addition, a theoretical result is presented, which shows that, with the proposed ordering, the condition number of the preconditioned Normal Equation matrix with the Splitting preconditioner is uniformly limited by an amount that depends only on the original data of the problem and not on the iteration of the Interior Point Method. Numerical experiments with large scale problems, corroborate the robustness and computational efficiency from this approach.

Documentos Relacionados