Um estudo computacional de algoritmos de trajetoria central para problemas de complementariedade linear monotona

Abstract

Neste trabalho analisamos, em particular, um algoritmo que segue a trajetória central associada a um problema de complementariedade linear monótona, gerando pontos em vizinhanças grandes da trajetória. Esse algoritmo baseia-se em passos que procuram uma aproximação rápida da face ótima do problema, e, quando houver necessidade, em passos corretores, que provocam uma aproximação à trajetória central. A trajetória central termina no ponto conhecido como ótimo central, que é o centro analítico da face ótima. Neste trabalho mostramos como este algoritmo gera seqüências que convergem para o ótimo central, e como o algoritmo de centralização é acelerado pela aproximação desse ponto.