Resumo: O método preditor corretor de Mehrotra é uma variante dos métodos de pontos interiores para programação linear onde a cada iteração é necessária a resolução de dois sistemas lineares: o primeiro determina a direção preditora e o segundo a direção corretora. O cálculo desses sistemas lineares detém a maior parte do custo computacional, assim o método de resolução deve ser cuidadosamente escolhido. O método de gradientes conjugados precondicionado é utilizado para resolver tais sistemas lineares. O precondicionamento é realizado de forma híbrida, nas primeiras iterações usa-se o precondicionador fatoração controlada de Cholesky e nas iterações finais o precondicionador separador. O ponto chave do precondicionador híbrido é determinar o momento para a troca. O número de condição, estimado por meio dos valores de Ritz, é utilizado em uma heurística para troca dos precondicionadores. Testes computacionais foram realizados para avaliar a qualidade da heurística quando comparada com a literatura Ver menos

Abstract: The Mehrotra predictor corrector method is a variant of interior point methods for linear programming where at each iteration it is necessary to solve two linear systems: the first determines the predictor direction and the second the corrector direction. Solving these linear systems represents most of the computational cost. For this reason, the solution method must be carefully chosen. In this work the conjugate gradients method is applied, it depends on the convergence of the matrix condition number making it necessary a preconditioner. The preconditioning is performed by the hybrid preconditioner, where in the first iterations, the preconditioner controlled Cholesky factorization is applied and in later iterations, the splitting preconditioner is applied. The key point of the hybrid preconditioner approach is to determine the moment for the phase exchange. Ritz values are used to estimate the condition number and to develop a heuristic to the change of phases. Computational experiments were performed to evaluate the heuristic quality when compared with the literature Ver menos