Repositorio da Producao Cientifica e Intelectual da Unicamp: Escolha adiada do parametro de penalização e do tamanho de passo em algoritmos de pontos interiores
Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/306882
Title: Escolha adiada do parametro de penalização e do tamanho de passo em algoritmos de pontos interiores
Author: Villas-Bôas, Fernando Rocha
Abstract: Resumo: Nesse trabalho estudamos, no contexto de métodos de pontos interiores para programação linear, algumas possíveis vantagens de se adiar as escolhas do parâmetro de penalização e do tamanho de passo, que ocorrem tanto quando usamos o método de Newton para resolver o sistema de Karush-Kuhn- Thcker, como quando aplicamos um esquema preditor-corretor. Nós mostramos que, tanto para um passo de Newton quanto para um passo preditor-corretor, o próximo iterando pode ser expresso como uma função linear do parâmetro de penalização J1 e, no caso de um passo preditor-corretor, como uma função quadrática de J1. Mostramos também que essa parametrização é útil para garantir, por exemplo, a não-negatividade do próximo iterando ou sua proximidade da trajetória central. Resultados computacionais dessas estratégias são apresentados e comparados com PCx, uma implementação do método preditor-corretor de Mehrotra
Abstract: We study, in the context of interior-point methods for linear programming, some possible advantages of postponing the choice of the per. ",lty parameter and the step length, which happens both when we apply Newton's method to the Karush-Kuhn-Thcker system and when we apply a predictor-corrector scheme. We show that for a Newton or a strictly predictor step the next iterate can be expressed as a linear function of the penalty parameter J1, and, in the case of a predictor-corrector step, as a quadratic function of J1. We also show that this parameterization is useful to guarantee either the non-negativity of the next iterate or the proximity to the central path. Computational results of these strategies are shown and compared with PCx, an implementation of Mehrotra's predictor-corrector method
Citation: VILLAS-BÔAS, Fernando Rocha. Escolha adiada do parametro de penalização e do tamanho de passo em algoritmos de pontos interiores. 2000. 92 p. Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/306882>. Acesso em: 25 jul. 2018.