Please use this identifier to cite or link to this item: http://repositorio.uem.br:8080/jspui/handle/1/6599
Authors: Moschen, Lucas
Orientador: Sobral, Francisco Nogueira Calmon
Title: Application of Newton's and Broyden's methods in linear programming
Keywords: Método de Newton;Método de Broyden;Métodos de pontos interiores;Equações não-suaves;Newton's Method;Broyden's method
Issue Date: 2022
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.
Description: Orientador: Prof. Dr. Francisco Nogueira Calmon Sobral
Dissertação (mestrado em Matemática)--Universidade Estadual de Maringá, Dep. de Matemática, Programa de Pós-Graduação em Matemática, Área de Concentração: Matemática Aplicada, 2022
URI: http://repositorio.uem.br:8080/jspui/handle/1/6599
Appears in Collections:2.5 Dissertação - Ciências Exatas (CCE)

Files in This Item:
File SizeFormat 
Lucas Moschen_2022.pdf801,54 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.