Algoritmo de Ponto Interior para Programação Linear Baseado no FDIPA
Autores
|
6530 |
2945,44,2008
|
|
|
6531 |
2945,44,2008
|
|
|
6532 |
2945,44,2008
|
Informações:
Publicações do PESC
Neste trabalho usamos um algoritmo de pontos interiores e direções viáveis denominado FDIPA, "Feasible Direction Interior Point Algorithm", para resolução de problemas de otimização linear. Em cada iteração o FDIPA calcula uma direção de descida viável do problema mediante uma iteração tipo Newton para resolver as condições de Karush-Kuhn-Tucker (KKT), gerando dois sistemas lineares de equações. São propostas técnicas numéricas para resolver os mesmos de forma eficiente, em particular, mediante um método de gradiente conjugado precondicionado, no qual conseguimos um critério para poder truncá-lo. Finalmente, vários problemas testes serão resolvidos e comparados com resultados da literatura.
In this work we use an algorithm of interior points and feasible directions called FDIPA, "Feasible Direction Interior Point Algorithm", for solving linear optimization problems. In each iteration FDIPA calculates a feasible descent direction of the problem by a Newton-type iteration to solve the Karush-Kuhn-Tucker (KKT) conditions; generating two linear systems of equations. Numerical techniques are proposed to solve them efficiently, in particular by means of a preconditioned conjugate gradient method, in which we obtain a criterion to truncate it. Finally, several test problems will be solved and compared with results from the literature.