(3) A Contribuição de Karmarkar (1984): O trabalho de Karmarkar em 1984 não foi o primeiro método de pontos interiores, mas sim um avanço em sua aplicação à programação linear. O que foi novo e significativo no trabalho de Karmarkar?
- Introduziu um algoritmo polinomial projetivo para PL, diferente das funções barreira usadas na PNL.
- Demonstrou desempenho computacional significativamente melhor que o método dos elipsoides e, em casos grandes, superior ao simplex, especialmente em sistemas paralelos.
- Seu trabalho revolucionou o campo, popularizando os métodos de pontos interiores e tornando-os competitivos com o simplex.
Passo 1
O enunciado aborda o marco de Karmarkar em 1984 na área de programação linear (PL) por meio de métodos de pontos interiores. Vamos revisar o que era esperado até então (elipsoide, simplex) e entender qual foi a inovação central de Karmarkar.
Passo 2
Karmarkar apresentou um algoritmo projetivo de complexidade polinomial para PL, o que o diferenciou das abordagens de programação não-linear (PNL) baseadas em funções barreira. Em vez de manter-se próximo à fronteira viável por penalidades logarítmicas, seu método realizava projeções sucessivas no simplex, garantindo convergência em número de iterações polinomiais.
Passo 3
Do ponto de vista prático, ele mostrou que esse algoritmo tinha desempenho muito superior ao método do elipsoide, reduzindo drasticamente o número de iterações na prática. Em instâncias de grande porte, especialmente em arquiteturas paralelas, o seu método chegou a superar o simplex, que até então era imbatível na prática.
Passo 4
O trabalho de Karmarkar foi um divisor de águas porque popularizou os métodos de pontos interiores, mostrando que eles não eram apenas curiosidades teóricas, mas sim ferramentas competitivas para PL. Isso provocou uma nova linha de pesquisa, aperfeiçoamentos e incorporações em softwares de otimização.
Resposta
- Introduziu um algoritmo projetivo de complexidade polinomial para programação linear, diferente das funções barreira usadas em programação não-linear.
- Demonstrou desempenho prático muito melhor que o método dos elipsoides e, em grandes sistemas (sobretudo paralelos), chegou a superar o simplex.
- Popularizou os métodos de pontos interiores, tornando-os competitivos com o simplex e impulsionando todo o campo de otimização.