Application of Newton's and Broyden's methods in linear programming

Abstract

Nessa dissertação, são apresentados os métodos de Newton e de Broyden com o objetivo de estudar a sua utilização na resolução de problemas de programação linear. Nesse sentido, primeiramente a versão padrão de um método de pontos interiores (IPM) primal-dual e introduzida, a qual usa o método de Newton como base para a sua operação. Em seguida, é estudado um IPM com aproximação quasi-Newton proposto recentemente, e é apresentado um resultado original desta pesquisa: a convergência local linear desse método sob algumas fortes hipóteses. Posteriormente, _e estudado um sistema de equações não-suaves equivalente as condições de Karush-Kuhn-Tucker (KKT) de um problema de programação linear. São aplicadas variantes não-suaves dos métodos de Newton e de Broyden para resolver tal sistema e são observados os resultados sobre sua convergência. Com a finalidade de obter propriedades de convergência global em relação à resolução desse sistema, _e estudado um algoritmo que utiliza métodos locais em sua operação. Considerando um problema de programação linear específico, são aplicadas duas versões desse algoritmo: uma utilizando o método de Newton e a outra utilizando o método de Broyden. A análise dos experimentos numéricos realizados sugere resultados teóricos relacionados _a operação desse algoritmo e resulta em uma modificação com melhor desempenho de convergência global no problema selecionado.

In this dissertation, Newton's and Broyden's methods are presented with the aim of studying their use in solving linear programming problems. To this end, _rst the standard version of a primal-dual interior point method (IPM) is introduced, which uses Newton's method as the basis for its operation. Next, a recently proposed IPM with quasi-Newton approach is studied, and an original result of this research is presented: the linear local convergence of this method under some strong assumptions. Subsequently, a system of nonsmooth equations equivalent to the Karush-Kuhn-Tucker (KKT) conditions of a linear programming problem is studied. Nonsmooth variants of Newton's and Broyden's methods are applied to solve such system and results on its convergence are observed. In order to obtain global convergence properties with respect to solving this system, it is studied an algorithm that uses local methods in its operation. By considering a specific linear programming problem, two versions of this algorithm are applied: one using Newton's method and the other using Broyden's method. The analysis of the numerical experi- ments suggests theoretical results related to the operation of this algorithm and results in a modification with better global convergence performance on the selected problem.