Análise do Algoritmo de Ponto Interior e Direções Viáveis FDIPA

Resumen

Neste trabalho vamos apresentar uma análise do algoritmo FDIPA (Feasible Direction Interior Point Algorithm), aplicado a alguns tipos de problemas de minimização com restrições proposto por Herskovits [2]. O FDIPA é um algoritmo de pontos interiores que usa uma direção de busca com a propriedade de ser uma direção de descida para a função potencial, e direção viável para o conjunto de pontos viáveis do problema. O método se baseia em uma iteração de Newton no sistema de Karush-Kuhn-Tucker (KKT) de primeira ordem, porém realiza a busca linear somente na variável primal do problema, como apresentado em [2, 4]. Uma característica na técnica proposta por Herskovits se baseia na matriz do sistema linear usada para o cálculo das duas direções, de descida e viável, as quais, por meio de uma combinação linear adequada, obtêm a direção para a busca linear usada na execução iterativa do próximo ponto. Essa matriz B é a Hessiana da função Lagrangeana associada ao problema de minimização, e pode ser ”substituída” por uma matriz que seja simétrica e definida positiva, como mostrado em [4]. Essa substituição ou atualização da matriz B permite que o FDIPA se adapte aos mais variados problemas de programação matemática. Assim, serão apresentadas três atualizações diferentes para B, e para cada uma delas será aplicada um conjunto de problemas testes proposto em Test Examples for Non-Linear Programming Code [1], afim de verificar e comparar o desempenho do FDIPA nestas situações. [...]