Orientadores: Aurelio Ribeiro Leite de Oliveira, Fernando da Rocha Villas-Bôas, Clóvis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T03:16:18Z (GMT). No. of bitstreams: 1 Santos_LuizRafaeldos_D.pdf: 1892418 bytes, checksum: f636057b6014ba9f4fdbc0c69c99bdeb (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, propomos um método de pontos interiores do tipo preditor-corretor para programação linear em um contexto primal-dual, em que o próximo iterado será escolhido através de um subproblema de minimização de uma função de mérito polinomial a três variáveis: a primeira variável é o tamanho de passo, a segunda define a trajetória central e a última modela o peso que uma direção corretora deve ter. A minimização da função de mérito é feita sujeitando-a à restrições definidas por uma vizinhança da trajetória central que permite passos largos. Dessa maneira, combinamos diferentes direções, tais como preditora, corretora e de centralização com o objetivo de obter uma direção melhor. O método proposto generaliza grande parte dos métodos de pontos interiores preditores-corretores, a depender da escolha do valor das variáveis acima descritas. É feita, então uma análise de convergência do método proposto, considerando um ponto inicial que tem bom desempenho na prática, e que resulta em convergência linear dos iterados em complexidade polinomial. São feitos experimentos numéricos, utilizando o conjunto de testes Netlib, que mostram que essa abordagem é competitiva, quando comparada a implementações de pontos interiores bem estabelecidas como o PCx / Abstract: In this work we propose a predictor-corrector interior point method for linear programming in a primal-dual context, where the next iterate is chosen by the minimization of a polynomial merit function of three variables: the first one is the step length, the second one defines the central path and the last one models the weight that a corrector direction must have. The merit function minimization is performed by restricting it to constraints defined by a neighborhood of the central path that allows wide steps. In this framework, we combine different directions, such as the predictor, the corrector and the centering directions, with the aim of producing a better direction. The proposed method generalizes most of predictor-corrector interior point methods, depending on the choice of the variables described above. Convergence analysis of the method is carried out, considering an initial point that has a good practical performance, which results in Q-linear convergence of the iterates with polynomial complexity. Numerical experiments are made, using the Netlib test set, which show that this approach is competitive when compared to well established solvers, such as PCx / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T19:56:24Z (GMT). No. of bitstreams: 1 Silva_LinoMarcosda_D.pdf: 2297954 bytes, checksum: 2213b987c2753edec9152998b30b7c74 (MD5) Previous issue date: 2014 / Resumo: O método de pontos interiores para programação linear resolve em poucas iterações problemas de grande porte. No entanto, requer a cada iteração a resolução de dois sistemas lineares, os quais possuem a mesma matriz de coeficientes. Essa etapa se constitui no passo mais caro do método por aumentar consideravelmente o tempo de processamento e a necessidade de armazenamento de dados. Reduzir o tempo de solução dos sistemas lineares é, portanto, uma forma de melhorar o desempenho do método. De um modo geral, problemas de programação linear de grande porte possuem matrizes esparsas. Uma vez que os sistemas lineares a serem resolvidos são simétricos positivos definidos, métodos iterativos como o método dos gradientes conjugados precondicionado podem ser utilizados na resolução dos mesmos. Além disso, fatores de Cholesky incompletos podem ser utilizados como precondicionadores para o problema. Por outro lado, fatorações incompletas podem sofrer falhas na diagonal durante o processo de fatoração, e quando tais falhas ocorrem uma correção é efetuada somando-se um valor positivo aos elementos da diagonal da matriz do sistema linear e a fatoração da nova matriz é reiniciada, aumentando dessa forma o tempo de precondicionamento, quer seja devido a reconstrução do precondicionador, quer seja devido a perda de qualidade do mesmo. O precondicionador fatoração controlada de Cholesky tem um bom desempenho nas iterações iniciais do método de pontos interiores e tem sido importante nas implementações de abordagens de precondicionamento híbrido. No entanto, sendo uma fatoração incompleta, o mesmo não está livre da ocorrência de falhas no cálculo do pivô. Neste estudo propomos duas modificações à fatoração controlada de Cholesky a fim de evitar ou diminuir o número de reinícios da fatoração das matrizes diagonalmente modificadas. Resultados computacionais mostram que a técnica pode reduzir significativamente o tempo de resolução de certas classes de problemas de programação linear via método de pontos interiores / Abstract: The interior point method solves large linear programming problems in few iterations. However, each iteration requires computing the solution of one or more linear systems. This constitutes the most expensive step of the method by greatly increasing the processing time and the need for data storage. According to it, reducing the time to solve the linear system is a way of improving the method performance. In general, large linear programming problems have sparse matrices. Since the linear systems to be solved are symmetric positive definite, iterative methods such as the preconditioned conjugate gradient method can be used to solve them. Furthermore, incomplete Cholesky factor can be used as a preconditioner to the problem. On the other hand, breakdown may occur during incomplete factorizations. When such failure occur, a correction is made by adding a positive number to diagonal elements of the linear system matrix and the factorization of the new matrix is restarted, thus increasing the time of preconditioning, either due to computing the preconditioner, or due to loss of its quality. The controlled Cholesky factorization preconditioner performs well in early iterations of interior point methods and has been important on implementations of hybrid preconditioning approaches. However, being an incomplete factorization, it is not free from faulty pivots. In this study we propose two modifications to the controlled Cholesky factorization in order to avoid or decrease the refactoring diagonally modified matrices number. Computational results show that the proposed techniques can significantly reduces the time for solving linear programming problems by interior point method / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Daniela Renata Cantane, Aurelio Ribeiro Leite de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-23T12:26:43Z (GMT). No. of bitstreams: 1 Kikuchi_PaulaAparecida_M.pdf: 1402695 bytes, checksum: 8339a3eaa502e0d7b3a9ebfe61097f83 (MD5) Previous issue date: 2013 / Resumo: Vários são os métodos propostos para reconstrução de sinal. Nosso enfoque é o método Basis Pursuit. Trabalhando com dicionários overcomplete, são inúmeras as combinações possíveis para a representação do sinal. Basis Pursuit encontra a mais esparsa, porque minimiza a soma dos módulos dos coeficientes da combinação, ou seja, minimiza os coeficientes na norma 1. Veremos que podemos reescrever o problema em questão como um problema de programação linear. Apresentaremos um método já existente para a resolução deste problema, o Método Primal-Dual Barreira Logarítmica. Em um primeiro momento, vamos aplicar o Método Barreira Logarítmica, e buscando maior eficiência, iremos incluir a direção afim-escala, a direção de centragem e a direção de correção no mesmo método, obtendo o Método Primal-Dual Barreira Logarítmica Preditor- Corretor, além de implementar uma variação deste. Resultados computacionais com problemas reais comprovam a eficiência do método proposto / Abstract: There are many proposed methods for signal reconstruction. However, our focus is on the Basis Pursuit method. When working with overcomplete dictionaries, there exist countless possible combinations to represent the signal. Basis Pursuit finds the sparsest, because it minimizes the sum of the combination coefficients absolute values, i.e., it minimizes the coefficients on norm 1. We will see that the problem in question can be rewritten as a linear programming problem. An existing method is shown for the solution of this problem, the Primal-Dual Logarithmic Barrier Method. Initially, we will apply the Logarithmic Barrier Method, and seeking higher efficiency, we will include the affine scaling direction, the centering direction and the nonlinear correction direction in the same method, obtaining the Predictor-Corrector Primal-Dual Logarithmic Barrier Method, of which a variation is also implemented. Computational results with real life problems show the efficiency of the proposed method / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Orientadores: Aurelio Ribeiro Leite de Oliveira, Carla Taviane Lucke da Silva Ghidini / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-20T05:01:05Z (GMT). No. of bitstreams: 1 Berti_LilianFerreira_M.pdf: 11222489 bytes, checksum: 8a581cf3762be9e96b4f77b7206e3112 (MD5) Previous issue date: 2012 / Resumo: Os métodos de pontos interiores têm sido amplamente utilizados para determinar a solução de problemas de programação linear de grande porte. O método preditor corretor, dentre todas as variações de métodos de pontos interiores, é um dos que mais se destaca, devido à sua eficiência e convergência rápida. Este método, em cada iteração, necessita resolver dois sistemas lineares para determinar a direção preditora corretora. Resolver estes sistemas lineares corresponde ao passo que requer mais tempo de processamento, devendo assim ser realizada de forma eficiente. Para resolver estes sistemas lineares a abordagem mais utilizada é a fatoração de Cholesky. No entanto, realizar a fatoração de Cholesky em cada iteração tem um alto custo computacional. Dessa forma, na busca de redução de esforços, precisamente, na redução do número de iterações foi desenvolvida a iteração continuada. Iteração continuada é uma iteração subsequente, realizada após o cálculo da direção preditora corretora, onde é determinada uma nova direção sem que seja necessário realizar uma nova fatoração de Cholesky. Os resultados computacionais dos testes realizados, principalmente em problemas de médio e grande porte mostraram que esta abordagem obtém bom desempenho em comparação com o método preditor corretor / Abstract: Interior point methods have been widely used in the solution of large linear programming problems. The predictor corrector method, among ali interior point variants, is one of mostly used due to its efficiency and convergence properties. This method needs the solution of two linear systems to determine the predictor corrector direction, in each iteration. Solving such systems corresponds to the step which requires more processing time. Therefore, it should be done efficiently. The most common approach to solve the linear systems is the Cholesky factorization, demanding in each iteration a high computacional effort. Thus, in search of effort reduction, in particular, to reduce the iterations number continued iteration was developed. The continued iteration is a subsequent iteration performed after the predictor corrector direction is computed, where a new direction is calculated without need to of Cholesky refactorization. The numerical tests show that the continued iteration performs better in comparison with the preditor corretor method / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientadores: Aurélio Ribeiro Leite de Oliveira, Marta Ines Velazco Fontova / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T12:49:39Z (GMT). No. of bitstreams: 1 Coelho_AlessandroFonsecaEsteves_M.pdf: 2659631 bytes, checksum: fc1bec925179612ee07a4aaef7092d8a (MD5) Previous issue date: 2011 / Resumo: Um método frequentemente utilizado para a solução de problemas de programação linear é o método de pontos interiores. Nestes métodos precisamos resolver sistemas lineares para calcular a direção de Newton a cada iteração. A solução desses sistemas consiste no passo de maior esforço computacional nos métodos de pontos interiores. A fatoração de Cholesky é a opção mais utilizada para resolver estes sistemas. Contudo, quando trabalhamos com problemas de grande porte, esta fatoração pode ser densa e torna-se inviável trabalhar com esses métodos. Nestes casos, uma boa opção consiste no uso de métodos iterativos precondicionados. Estudos anteriores utilizam o método dos gradientes conjugados precondicionado para obter uma solução destes sistemas. Particularmente, os sistemas originados dos métodos de pontos interiores, são, naturalmente, sistemas de equações normais. Porém, a versão padrão do método dos gradientes conjugados, não considera a estrutura de equações normais do sistema. Neste trabalho propomos a utilização de duas versões do método de gradientes conjugados precondicionado que consideram a estrutura de equações normais destes sistemas. Estas versões serão comparadas com a versão de gradientes conjugados precondicionada que não considera a estrutura de equações normais do sistema. Resultados numéricos com problemas de grande porte mostram que uma dessas versões é competitiva em relação à versão padrão / Abstract: An often used method for solving linear programming problems is the interior point method. In these methods we need to solve linear systems to compute the Newton search direction at each iteration. The solution of these systems is the procedure of most computational effort in interior point methods. The Cholesky factorization is the most often used method to solve these systems. However, when dealing with large scale problems, this factorization can be dense and it become impossible to apply such methods. In such cases, a good option is the use of preconditioned iterative methods. Previous studies have used the preconditioned conjugate gradient method to find the solution of these systems. Particularly, the systems arising from interior point methods are, naturally, systems of normal equations type. Nevertheless, the standard version of the conjugate gradient method, does not take into account the normal equations system structure. This study proposes the use of two versions of preconditioned conjugate gradient method considering the normal equations structure of these systems. These versions are compared with the preconditioned conjugate gradient version that does not consider that structure. Numerical results with large scale problems show that one of these versions is competitive with the standard one / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2017-07-11T12:50:27Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DissertaçãoRodrigoNunesdeMelo.pdf: 5589879 bytes, checksum: e851e203ef8b11b9711c04c1c34a7ede (MD5) / Made available in DSpace on 2017-07-11T12:50:27Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) DissertaçãoRodrigoNunesdeMelo.pdf: 5589879 bytes, checksum: e851e203ef8b11b9711c04c1c34a7ede (MD5) Previous issue date: 2016-06-17 / FACEPE / O planejamento da operação de um sistema elétrico de potência está diretamente relacionado com o despacho de usinas hidrelétricas e termelétricas. As características geográficas do Brasil contribuem para que o parque gerador seja predominantemente hidráulico. Devido à grande dimensão dos sistemas elétricos, a otimização do problema de despacho hidrotérmico é uma tarefa extremamente complexa que pode ser realizada de modo eficiente, buscando otimizar a operação dos reservatório das usinas hidráulicas, onde o objetivo é a redução do custo na geração térmica necessária para atendimento à carga e eventuais déficits de energia, além de maior nível de segurança. O presente trabalho aborda o desenvolvimento e a implementação de um software para resolução do problema do despacho hidrotérmico em três patamares de carga a ser atendido. Neste trabalho o problema de despacho foi formulado como um problema de programação linear, que por sua vez foi solucionado pelos métodos de pontos interiores primal-dual e preditor-corretor de barreira logarítmica. O trabalho faz uma avaliação do desempenho computacional dos métodos implementados e do método LINPROG presente no software Matlab® na solução do problema de planejamento da operação em larga escala, para horizontes de cinco e de dez anos. As simulações foram feitas baseados em dados do Plano Decenal de Energia (PDE) 2022 e apresentaram desempenhos satisfatórios. / The operational planning of electric power systems is directly related to the dispatch of hydroelectric and thermal power plants. The Brazilian electric energy park is a predominantly hydraulic system, due to its geographic characteristics. Due to the large size of the electrical systems, the optimization of the hydrothermal dispatch problem is an extremely complex task that can be carried out efficiently, seeking to optimize the operation of the reservoir in the hydroelectric plants aimed at reducing the cost of the necessary thermal generation to meet the load and possible energy deficits, and a high level of security. This work discusses the development and implementation of a software to solve the hydrothermal dispatch problem in three load steps. In this dissertation the hydrothermal dispatching problem is formulated as a linear programming program, which in term is solved by the following methods of interior point: primal-dual and predictor-corrector with logarithmic barrier. This work provides an evaluation of the computational performance of the implemented methods and LINPROG, presents in the software Matlab®, to solve a large scale operational planning problem, for horizons of five and ten years. The simulation were made based on data from the “Plano Decenal de Energia (PDE) 2022” and showed satisfactory performance.

O objetivo deste trabalho consiste no desenvolvimento, estudo e implementação de métodos de pontos interiores específicos para o problema de planejamento do tratamento de câncer por radioterapia. Este é um problema de grande porte que contém uma estrutura matricial particular. A exploração desta estrutura de forma eficiente obtém bom desempenho computacional, através da redução da dimensão dos sistemas lineares que devem ser resolvidos a cada iteração, agilizando a definição de um tratamento adequado, uma vez que tipicamente várias simulações são realizadas antes da definição de um plano definitivo. Resultados numéricos em Matlab ilustram a eficiência desta abordagem em problemas reais e mostram a superioridade do método preditor corretor em comparação ao método primal-dual. / In this work, a specialized interior point method is developed for planning cancer treatment by radiotherapy. This is a large-scale problem with a specific matrix structure. That structure is explored in an efficient way reducing the dimension of the linear system which must be solved at each iteration speeding up the treatment design since usually several versions must be solved to obtain a satisfactory plan. Moreover, the system obtained is sparse, symmetric and positive definite. Numerical results in Matlab illustrate the efficiency of this approach in real problems and show the superiority of the preditor-corrector method in comparison to the primal-dual method.

Neste trabalho a família de métodos de pontos interiores barreira logarítmica é desenvolvida para o problema de regressão pela norma Lp e a estrutura matricial resultante é explorada objetivando uma implementação eficiente. Apresentamos alguns conceitos sobre métodos de pontos interiores necessários para o desenvolvimento do método e descrevemos um método de convergência quadrática previamente conhecido. Uma implementação em Matlab dos métodos de pontos interiores desenvolvidos é comparada com uma implementação do método quadrático existente, obtendo desempenho computacional superior. / In this work the family of logarithmic barrier interior point methods is developed for the norm Lp fitting problem and the resultant matrix structure is exploited in order to have an efficient implementation. We introduce some concepts about interior point methods necessary for the development of the method and describe a previously known quadratic convergent problem. An implementation in Matlab of the interior point methods developed is compared with an implementation of the known quadratic method obtaining better computational performance.

Orientador: Aurelio Ribeiro Leite de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T01:00:20Z (GMT). No. of bitstreams: 1 Probst_RoyWilhelm_M.pdf: 553863 bytes, checksum: a1307892a77da1b88d7536dd9027a4c3 (MD5) Previous issue date: 2006 / Resumo: Os métodos de pontos interiores primais-duais de trajetória central e preditor-corretor são desenvolvidos para o problema de minimização das perdas na geração e transmissão do pré-despacho DC de um sistema de potência hidrotêrmico e a estrutura matricial resultante explorada obtendo uma implementação eficiente. No pré-despacho de sistemas hidrotêrmicos, as usinas hidroelétricas têm uma meta a cumprir em um determinado dia, estabelecida pelo planejamento de longo prazo. As usinas termoelétricas, por sua vez, apresentam restrições de rampa, pois necessitam de um determinado tempo tanto para aumentar quanto para reduzir sua produção de energia. A implementação dos métodos de pontos interiores é testada em estudos de casos com sistemas IEEE / Abstract: The central path and the predictor-corrector primal-dual interior points methods are developed for the generation and transmission losses optimization problem for a DC power flow model in a hydrothermal power system and the resulting matrix structure is exploited leading to an efficient implementation. In short term hydrothermal scheduling, the hydro generating units need to satisfy daily targets, established by long-term scheduling models. The thermal generating units have ramp constraints because they need a certain amount of time to change de level of power delivery. Case studies with the developed interior point implementation for IEEE power systems are presented. / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Aurelio R. Leite Oliveira, Marta Ines Velazco / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T08:57:24Z (GMT). No. of bitstreams: 1 Silva_Jairda1_D.pdf: 1755258 bytes, checksum: 2ecb493aab3646838f54c2df2012b5d9 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho apresentamos uma nova família de algoritmos para resolver problemas de programação linear. A vantagem desta família de algoritmos é a sua simplicidade, a possibilidade de explorar a esparsidade dos dados do problema original e geralmente possuir raio de convergência inicial rápido. Esta família de algoritmos surgiu da generalização da idéia apresentada por João Gonçalves, Robert Storer e Jacek Gondzio, para desenvolver o algoritmo de ajustamento pelo par ótimo. Este algoritmo foi desenvolvido por sua vez tendo como base o algoritmo de Von Neumann. O algoritmo de Von Neumann possui propriedades interessantes, como simplicidade e convergência inicial rápida, porém, ele não é muito prático para resolver problemas lineares, visto que sua convergência é muito lenta. Do ponto de vista computacional, nossa proposta não é utilizar a família de algoritmos para resolver os problemas de programação linear até encontrar uma solução e sim explorar a sua simplicidade e seu raio de convergência inicial geralmente rápido e usá-la em conjunto com um método primal-dual de pontos interiores infactível, para melhorar a eficiência deste. Experimentos numéricos revelam que ao usar esta família de algoritmos em conjunto com um método primal-dual de pontos interiores infactível melhoramos o seu desempenho na solução de algumas classes de problemas de programação linear de grande porte. / Abstract: In this work, we present a new family of algorithms to solve linear programming problems. The advantage of this family of algorithms relies in its simplicity, the possibility of exploiting the sparsity of the original problem data and usually to have fast initial ratio of convergence. This family of algorithms arose from the generalization of the idea presented by João Gonçalves, Robert Storer and Jacek Gondzio to develop the optimal pair adjustment algorithm. This algorithm was developed in its own turn based on the Von Neumann's algorithm. It has interesting properties, such as simplicity and fast initial convergence, but it is not very practical for solving linear problems, since its convergence is very slow. From the computational point of view, our suggestion is not to use the family of algorithms to solve problems of linear programming until optimality, but to exploit its simplicity and its fast initial ratio of convergence and use it together with a infeasible primal-dual interior point method to improve its efficiency. Numerical experiments show that using this family of algorithms with an infeasible primal-dual interior point method improves its performance in the solution of some classes of large-scale linear programming problems. / Doutorado / Doutor em Matemática Aplicada