[pt] Apresentamos nesta dissertação novos métodos interativos para resolver o Problema de Complementaridade Linear (PCL) e Problemas de Norma Mínima. Após uma revisão geral sobre métodos interativos para o PCL, apresentaremos no Capítulo 2, uma forma de aceleração aplicada a métodos clássicos para o PCL simétrico, através de uma decomposição (Splitting) conveniente da matriz associada ao problema. A aceleração para os novos métodos consiste em calcular uma direção de avanço usando o método básico mais uma minimização unidimensional que respeite as condições de não negatividade, provas de convergência forte são apresentadas. No Capítulo 3 comparamos algoritmos do tipo seqüencial e paralelo para solução de um Problema de Programação Linear e Problemas de Norma Mínima em l 1: para o segundo problema os métodos iterativos são aplicados no dual do problema original penalizado com um termo quadrático. Introduzimos um novo método paralelo para o Problema de Norma mínima em l 1 e provamos sua convergência. Propomos no capítulo 4, novos métodos iterativos paralelos para Problemas de Norma Mínima, convenientes para problemas de grande porte, provas de convergência são fornecidas. Finalmente, no capítulo 5 baseados sobre uma combinação da iteração de ponto proximal e métodos iterativos clássicos, propomos novos métodos iterativos para a solução de um PCL monótono não simétrico. Ilustramos todos os algoritmos apresentados, em diferentes versões, com um extensa experimentação numérica. / [en] We present in this dissertation new iterative methods for solving Linear Complementarity (LCP) and Least Norm (LNP) Problems. After a general overview on iterative methods for the LCP, in chapter 2 we present an acceleration techinique applied to classic methods for symmetric LCP generated by considering appropriate splittings of the associated matrix. The acceleration gives rise to new methods consisting of computing a search direction using the basic method plus a one dimensional minimization taking into account the nonnegative constraints. Strong convergence proofs are given. In chapter 3 we compare sequential and parallel algorithms for solving Linear Programming and least 1-Norm Problems obtained by applying iterative methods to a dual of the original problem penalized with a quadratic term. We introduce a new parallel method for the Least 1-Norm Problem, proving its convergence. In chapter 4, we present new parallel iterative methods for solving large LNP, giving convergence proofs. Finally, in chapter 5 we propose new iterative methods for solving monotone nonsymmetric LCp based on a combination of proximal point iterations and classic iterative methods. All the algorithms, in their different versions are illustrated and compared through many numerical experiments.

O objetivo deste trabalho, por um lado, é estudar as bases teóricas, dentro do contexto variacional, a fim de formular o problema de acoplamento entre modelos matemáticos dimensionalmente heterogêneos. Por outro lado, devido às características do problema algébrico resultante e à necessidade de acesso completo a códigos numéricos de resolução aproximada, objetiva-se estudar o emprego de estratégias de decomposição de domínio para resolver o problema de forma iterativa através da sucessiva resolução de problemas dimensionalmente homogêneos, cuja resolução é mais simples e para os quais códigos já existentes estão disponíveis. Portanto, primeiramente estabelecemos um princípio variacional para o problema sob estudo. Logo, discretizamos o problema por meio do método dos elementos finitos e discutimos as características e dificuldades que o sistema algébrico compreende. A partir daí, empregamos técnicas baseadas na decomposição de domínios especialmente formuladas para problemas envolvendo modelos heterogêneos e, por fim, apresentamos vários exemplos numéricos a fim de mostrar o funcionamento da metodologia. Com esta abordagem passo-a-passo buscamos obter um ganho no entendimento dos conceitos teóricos envolvidos, assim como uma maior facilidade na aplicação destas ideias a novas situações.

Made available in DSpace on 2015-03-04T18:50:25Z (GMT). No. of bitstreams: 1 KarineDamasio.pdf: 5773113 bytes, checksum: afa593104cc7e14a3d65575271995ed4 (MD5) Previous issue date: 2011-03-14 / Conselho Nacional de Desenvolvimento Cientifico e Tecnologico / O objetivo deste trabalho, por um lado, é estudar as bases teóricas, dentro do contexto variacional, a fim de formular o problema de acoplamento entre modelos matemáticos dimensionalmente heterogêneos. Por outro lado, devido às características do problema algébrico resultante e à necessidade de acesso completo a códigos numéricos de resolução aproximada, objetiva-se estudar o emprego de estratégias de decomposição de domínio para resolver o problema de forma iterativa através da sucessiva resolução de problemas dimensionalmente homogêneos, cuja resolução é mais simples e para os quais códigos já existentes estão disponíveis. Portanto, primeiramente estabelecemos um princípio variacional para o problema sob estudo. Logo, discretizamos o problema por meio do método dos elementos finitos e discutimos as características e dificuldades que o sistema algébrico compreende. A partir daí, empregamos técnicas baseadas na decomposição de domínios especialmente formuladas para problemas envolvendo modelos heterogêneos e, por fim, apresentamos vários exemplos numéricos a fim de mostrar o funcionamento da metodologia. Com esta abordagem passo-a-passo buscamos obter um ganho no entendimento dos conceitos teóricos envolvidos, assim como uma maior facilidade na aplicação destas ideias a novas situações.

[pt] Otimização Robusta é uma das formas mais comuns de considerar in- certeza nos parâmetros de um problema de otimização. A forma tradicional de achar soluções robustas consiste em resolver a contraparte robusta de um problema, o que em muitos casos, na prática, pode ter um custo computacional proibitivo. Neste trabalho, estudamos métodos iterativos para resolver problemas de Otimização Convexa Robusta de forma aproximada, que não exigem a formulação da contraparte robusta. Utilizamos conceitos de Online Learning para propor um novo algoritmo que utiliza agregação de restrições, demonstrando garantias teóricas de convergência. Desenvolvemos ainda uma modificação deste algoritmo que, apesar de não possuir tais garantias, obtém melhor performance prática. Por fim, implementamos outros métodos iterativos conhecidos da literatura de Otimização Robusta e fazemos uma análise computacional de seus desempenhos. / [en] Robust Optimization is a common paradigm to consider uncertainty in the parameters of an optimization problem. The traditional way to find robust solutions requires solving the robust counterpart of an optimiza- tion problem, which, in practice, can often be prohibitively costly. In this work, we study iterative methods to approximately solve Robust Convex Optimization problems, which do not require solving the robust counter- part. We use concepts from the Online Learning framework to propose a new algorithm that performs constraint aggregation, and we demonstrate theoretical convergence guarantees. We then develop a modification of this algorithm that, although without such guarantees, obtains better practical performance. Finally, we implement other classical iterative methods from the Robust Optimization literature and present a computational study of their performances.

[pt] Companhias de petróleo investindo no desenvolvimento de campos de hidrocarboneto dependem de estudos de reservatórios para realizarem previsões de produção e quantificarem os riscos associados à economicidade dos projetos. Neste sentido, a área de modelagem de reservatórios é de suma importância, sendo responsável por prever o desempenho futuro do reservatório sob diversas condições operacionais. Considerando que a solução dos sistemas de equações construídos a cada passo de tempo de uma simulação, durante o ciclo de linearização, é a parte que apresenta a maior demanda computacional, esta dissertação foca na análise de diferentes técnicas de solvers numéricos que podem ser aplicadas a simuladores, para mensurar seus desempenhos. Os solvers numéricos mais adequados para a solução de grandes sistemas de equações, tais como os encontrados em simulações de reservatórios, são os denominados solvers iterativos, que gradativamente aproximam a solução de um dado problema por meio da combinação de um método iterativo e um precondicionador. Os métodos iterativos avaliados nesta pesquisa foram o Gradiente Biconjugado Estabilizado (BiCGSTAB), Mínimos Resíduos Generalizado (GMRES) e Minimização Ortogonal (ORTHOMIN). Além disso, três técnicas de precondicionamento foram implementadas para auxiliar os métodos iterativos, sendo estas a Decomposição LU Incompleta (ILU), Fatoração Aninhada (NF) e Pressão Residual Restrita (CPR). A combinação destes diferentes métodos iterativos e precondicionadores permite a avaliação de diversas configurações distintas de solvers, em termos de seus desempenhos em um simulador. Os testes numéricos conduzidos neste trabalho utilizaram um novo simulador de reservatórios que está sendo desenvolvido pela Pontifícia Universidade Católica (PUC-Rio) em conjunto com a Petrobras. O objetivo dos testes foi analisar a robustez e eficiência de cada um dos solvers quanto à sua capacidade de resolver as equações de escoamento multifásico no meio poroso, visando assim auxiliar na seleção do solver mais adequado para o simulador. / [en] Petroleum companies investing in the development of hydrocarbon fields rely upon a variety of reservoir studies to perform production forecasts and quantify the risks associated with the economics of their projects. Integral to these studies is the discipline of reservoir modeling, responsible for predicting future reservoir performance under various operational conditions. Considering that the most time-demanding aspect of reservoir simulations is the solution of the systems of equations that arise within the linearization cycles at each time-step, this research focuses on analyzing different numerical solver techniques to be applied to a simulator, in order to assess their performance. The numerical solvers most suited for the solution of very large systems of equations, such as those encountered in reservoir simulations, are the so-called iterative solvers, which gradually approach the solution to a problem by combining an iterative strategy with a preconditioning method. The iterative methods examined in this research were the Stabilized Biconjugate Gradient (BiCGSTAB), the Generalized Minimum Residual (GMRES), and the Orthogonal Minimization (ORTHOMIN) methods. Furthermore, three preconditioning techniques were implemented to aid the iterative methods, namely the Incomplete LU Factorization (ILU), the Nested Factorization (NF), and the Constrained Pressure Residual (CPR) methods. The combination of these different iterative methods and preconditioners enables the appraisal of several distinct solver configurations, in terms of their performance in a simulator. The numerical tests conducted in this work made use of a new reservoir simulator currently under development at Pontifical Catholic University of Rio de Janeiro (PUC-Rio), as part of a joint project with Petrobras. The objective of these tests was to assess the robustness and efficiency of each solver in the solution of the multiphase flow equations in porous media, and support the selection of the solver most suited for the simulator.