Orientadores: Margarida Pinheiro Mello, Maria Aparecida Diniz Ehrhardt / 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-22T15:49:27Z (GMT). No. of bitstreams: 1 Ferreira_DaianeGoncalves_M.pdf: 1441315 bytes, checksum: 1196d8b21c6254dbdd0e0d68266fa707 (MD5) Previous issue date: 2013 / Resumo: Métodos de Otimização de terceira ordem, embora de longa tradição, eram considerados, até passado recente, impraticáveis, devido à taxa com que o esforço computacional cresce em função da dimensão do problema. Avanços no desenvolvimento de estruturas de dados, rotinas que trabalham com estas estruturas e a exploração da esparsidade de grande parte dos problemas encontrados na prática já permitem implementações destes métodos que podem torná-los competitivos com métodos de segunda ordem. O objeto desta dissertação é a apresentação do método de Halley, um método de terceira ordem, sua implementação em MATLAB e a realização de testes computacionais, visando uma comparação empírica de sua eficiência frente ao método de Newton, o método de segunda ordem mais empregado na atualidade / Abstract: Higher order optimization methods, though of long-standing tradition, until recently have been deemed impractical, due to the rate of increase of the computational effort as a function of the size of the problem. Advances in the development of data structures, routines that work with these structures and the use of the sparsity of a vast range of practical problems have led to implementations of these methods that are competitive with second order methods. The object of this dissertation is the study of Halley's method, a thirdorder method, the development of a MATLAB implementation thereof and its testing, aiming at an empirical comparison of its efficiency against that of Newton's method, the second-order method most widely used today / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Orientador: Francisco de Assis Magalhães Gomes Neto / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-24T00:24:19Z (GMT). No. of bitstreams: 1 Siqueira_AbelSoares_D.pdf: 1465105 bytes, checksum: 2cba750df9607e9cb37b5799b157c850 (MD5) Previous issue date: 2013 / Resumo: Uma maneira de resolver problemas gerais de programação não linear é utilizar estratégias de passos compostos. Essas estratégias normalmente combinam um passo tangente às restrições e um passo normal, alternando entre a diminuição da função objetivo e da norma da infactibilidade. Esse tipo de método exige o controle dos passos ou dos iterandos, para que não se perca o progresso de um vii passo no outro. Apresentaremos uma extensão do método de Controle Dinâmico da Infactibilidade, que utiliza uma estratégia de controle de passos chamado de Cilindros de Confiança. Esse método foi desenvolvido para problemas com restrições apenas de igualdade, e nossa extensão lida com restrições gerais. Mostraremos testes numéricos comparando nosso método com um método do mesmo tipo / Abstract: One way to solve general nonlinear programming problems is the composite-step strategies. These strategies usually combine a step tangent to the constraints and a normal step, alternating between reducing the objective function value and the norm of the infeasibility. This kind of method requires the control of the steps or the iterates, in order to prevent one step from destroying the progress of another. We will present an extension of the Dynamic Control of Infeasibility method, which utilizes a strategy to control the steps known as Trust Cylinders. This method was originally designed for problems with equality contraints only, and our extension will handle general constraints. We'll show numerical experiments comparing our method with another composite-step method / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: José Mario Martínez Pérez, Margarida Pinheiro Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-19T12:33:50Z (GMT). No. of bitstreams: 1 Lima_RodrigoSilva_D.pdf: 3475914 bytes, checksum: e7fad42e859de59d5e4db3f0a5a41417 (MD5) Previous issue date: 2012 / Resumo: Neste trabalho estudamos inicialmente o problema da reconstrução 3D de uma proteína dadas as distâncias entre pares de átomos de sua estrutura. Formulamos a situação como um problema de otimização não linear com função objetivo contínua no domínio de variáveis e mostramos através de experimentos computacionais que a estrutura original da proteína é recuperada mesmo quando admitimos conhecidas apenas um subconjunto de distâncias intra- átomos. Em seguida, estudamos problema da representação de um conjunto de proteínas comparadas em relação as suas estruturas tridimensionais. Propomos algumas formulações para este problema onde as proteínas são representadas por objetos em espaços euclidianos e elaboramos também um procedimento para classificar proteínas novas sem a necessidade de realizar exaustivas comparações estruturais envolvendo as proteínas analisadas / Abstract: In this work we initially study the problem of reconstruct the 3D structure of a protein given the distances between pairs of its atoms. We formulate this situation as a nonlinear optimization problem with a continuous objective function over the domain of variables. We show by computational experiments that the original protein structure is recovered even when we do not use all the distances between its atoms. Next, we study the problem of representing a set of proteins. The proteins are compared with respect to their 3D structures. We propose some formulations to this problem, where the proteins are represented by objects in euclidean spaces and we elaborate also a form of use these representations to classify new proteins without perform many comparisons between the analyzed structures / Doutorado / Doutor em Matemática Aplicada

Orientadores: Marcia Aparecida Gomes Ruggiero, Carlile Campos Lavor / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-21T21:36:13Z (GMT). No. of bitstreams: 1 Goncalves_DouglasSoares_D.pdf: 2439739 bytes, checksum: 5c9361d700cb32cae7880de49fa5e892 (MD5) Previous issue date: 2013 / Resumo: A preparação, manipulação e caracterização de sistemas quânticos são tarefas essenciais para a computação quântica. Em Tomografia de Estados Quânticos, o objetivo é encontrar uma estimativa para a matriz de densidade, associada a um ensemble de estados quânticos identicamente preparados, baseando-se no resultado de medições. Este é um importante procedimento em computação e informação quântica, sendo aplicado, por exemplo, para verificar a fidelidade de um estado preparado ou em tomografia de processos quânticos. Nesta tese, estudamos métodos matemáticos aplicados aos problemas que surgem na reconstrução de estados quânticos. Na estimação por Máxima Verossimilhança, apresentamos dois métodos para a resolução dos problemas de otimização dessa abordagem. O primeiro se baseia em uma reparametrização da matriz de densidade e, neste caso, provamos a equivalência das soluções locais do problema de otimização irrestrita associado. No segundo, relacionado à verossimilhança multinomial, demonstramos a convergência global do método sob hipóteses mais fracas que as da literatura. Apresentamos também duas formulações para o caso de tomografia com um conjunto incompleto de medidas: Máxima Entropia e Tomografia Quântica Variacional. Propusemos uma nova formulação para a segunda, de modo a apresentar propriedades mais parecidas as da Máxima Entropia, mantendo a estrutura de um problema de programação semidefinida linear. Para outros problemas de otimização sobre o espaço de matrizes de densidade além do problema da Tomografia de Estados Quânticos, apresentamos um método de Gradiente Projetado que se mostrou efetivo em testes numéricos preliminares. Por fim, discutimos sobre a implementação de inferência Bayesiana, através de métodos Monte Carlo via cadeias de Markov, no problema de estimação da matriz de densidade / Abstract: Preparation, manipulation and characterization of quantum states are essential tasks for quantum computation. In Quantum State Tomography, the aim is to find an estimate for the density matrix associated to an ensemble of identically prepared quantum systems, based on the measurement outcomes. This is an important procedure in quantum information and computation applied for instance, to verify the fidelity of a prepared state or in quantum process tomography. In this thesis we study mathematical methods applied to problems that raise from the reconstruction of quantum states. In the Maximum Likelihood Estimation we present two methods to solve the optimization problems of this approach. The first one is based on a reparameterization of the density matrix and, in this case, we prove the equivalence of local solutions of the related unconstrained optimization problem. In the second one, related to multinomial likelihoods, we prove the global convergence of the method under weaker assumptions than those of literature. We also discuss two formulations to the case of quantum state tomography with incomplete measurements: Maximum Entropy and Variational Quantum Tomography. We propose a new formulation for the second one in order to have a similar behavior to the Maximum Entropy approach, keeping the linear semidefinite positive programming structure. Furthermore, in order to solve other optimization problems over the density matrices space besides the Quantum State Tomography, we present a Projected Gradient method which shows a good performance in preliminary numerical tests. We also briefly talk about the implementation of a Bayesian inference scheme, through Monte Carlo Markov chains methods, to the density matrix estimation problem / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador : Wagner Caradori do Amaral / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T05:38:50Z (GMT). No. of bitstreams: 1 Campello_RicardoJoseGabrielliBarreto_D.pdf: 2631759 bytes, checksum: 149a2466bf0190a5ae28f2819f5db427 (MD5) Previous issue date: 2002 / Doutorado

Orientador : Anesio dos Santos Junior / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T23:25:26Z (GMT). No. of bitstreams: 1 Carvalho_EsdrasPenedode_D.pdf: 1776464 bytes, checksum: 0190f59fa01ca49b0518113d289152c6 (MD5) Previous issue date: 2004 / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientadores: Wagner Caradori do Amaral, Ricardo Jose Gabrielli Barreto Campello / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T02:57:58Z (GMT). No. of bitstreams: 1 Rosa_Alexda_M.pdf: 896715 bytes, checksum: 1baf3dbaef2a1280f09feabed84d996c (MD5) Previous issue date: 2005 / Resumo: Este trabalho analisa a modelagem de sistemas nao-lineares utilizando modelos de Wiener/Volterra com funcoes ortonormais de Kautz. Os modelos de Volterra sao uma generalizacao do modelo resposta ao impulso para a descricao de sistemas naolineares. Esses modelos necessitam de um numero consideravel de termos para a representacao dos kernels de Volterra. Essa complexidade pode ser reduzida utilizando-se uma representacao do tipo Wiener/Volterra, em que os kernels sao desenvolvidos utilizando uma base de funcoes ortonormais. Sao discutidos aspectos da selecao dos parametros livres (polos) que caracterizam essas funcoes, particularmente a selecao otima dos polos complexos das funcoes de Kautz. Este problema e resolvido minimizando-se o limitante superior do erro que surge a partir da aproximação truncada dos kernels de Volterra usando-se as funcoes de Kautz. Obtem-se a solu¸cao analitica para a escolha otima de um dos parametros relacionados com o polo de Kautz, sendo os resultados validos para modelos Wiener/Volterra de qualquer ordem. Apresentam-se ainda resultados de simulacoes que ilustram a metodologia apresentada, bem como a modelagem de um sistema de levitacao magnetica / Abstract: This work investigates the modelling of nonlinear systems using the Wiener/Volterra models with Kautz orthonormal functions. The Volterra models constitute a generalization of the impulse response model to describe nonlinear systems. Such models require a large number of terms for representing the Volterra kernels. However, this complexity can be reduced by using Wiener/Volterra models, in which the kernels are expanded using an orthonormal basis functions. Aspects about selection of the free parameters (poles) characterizing theses functions are discussed, in particular the optimal selection of the complex poles of the Kautz functions. This problem is solved by minimizing the upper bound of the error arising from the truncated approximation of Volterra kernels using Kautz functions. An analytical solution for the optimal choice of one of the parameters related to the Kautz pole is thus obtained, with the results valid for any-order Wiener/Volterra models. Simulations that illustrate the methodology described above are presented. Also, the modelling of a magnetic levitation system is discussed. / Mestrado / Engenharia / Mestre em Engenharia Elétrica

Orientador: Jose Mario Martinez / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-04T03:19:31Z (GMT). No. of bitstreams: 1 Francisco_JulianodeBem_D.pdf: 963435 bytes, checksum: 88cedcb7cfb40d6a63f0ce67f0abb970 (MD5) Previous issue date: 2005 / Resumo: Algoritmos robustos e numericamente viáveis para resolver problemas de otimização têm sido cada vez mais solicitados em problemas práticos que aparecem em engenharia, química, física, entre outras áreas. Com isso em mente, este trabalho apresenta um novo método globalmente convergente baseado em região de confiança para resolver sistemas não-lineares indeterminados (mais incógnitas do que equações) com restrições de caixa, podendo, portanto, ser aproveitado para a fase de viabilidade nos algoritmos baseados em restauração periódica. É mostrado que esse método apresenta, sob certas hipóteses, convergência localmente quadrática. Em uma outra parte deste trabalho é apresentado um novo algoritmo globalmente convergente, o qual se baseia em região de confiança, para resolver problemas de otimização do tipo min f(x); s:a: x 2 D; onde f : Rn ! R é assumida para ser continuamente diferenciável e D C Rn, um subconjunto fechado arbitrário. Em vez de considerar a região de confiança explicitamente nos subproblemas, esse método introduz um parâmetro de regularização que busca imitar a região de confiança. Com essa caracterização, os subproblemas consistem em minimizar um modelo quadratico de f sujeito ao subconjunto D. Uma importante aplicação desse novo algoritmo aparece em química quântica e resultará em um novo algoritmo globalmente convergente, robusto e numericamente viável para calcular estruturas eletrônicas de átomos e moléculas / Abstract: Abstract Robust and numerically feasible algorithms for solving optimization problems have been demanded for solving practice problems that appear in Engineering, Chemistry, Physics and others. This work present a new globally convergent method based on trust regions for solving box-constrained underdetermined nonlinear systems (more unknowns than equations), that can be used on the feasibility fase of algorithms based on periodic restoration. Under some assumptions, it will be proved locally quadratic convergence. In other part of this work, a new globally convergent algorithm is introduced, based on trust regions, for solving the optimization problem min f(x); s:t: x 2 D; where f : Rn ! R is continuously dierentiable and D C Rn is an arbitrary closed subset. Instead of considering explicitly the trust region on the subproblems, the method introduces a regularization parameter that mimics the trust region. With this characterization, the subproblems consist on minimizing a quadratic model of f subject to D. numerically feasible globally convergent algorithm for electronic structure calculations is obtained. / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Roberto Andreani / 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-04T05:03:19Z (GMT). No. of bitstreams: 1 Gaujoux_RenaudGilles_M.pdf: 1743739 bytes, checksum: a3548a59bc983f4398cb0136c62c1d6a (MD5) Previous issue date: 2005 / Resumo: Esta dissertação trata da aplicação de um método de tipo Newton generalizado aos sistemas KKT. Graças às funções chamadas de NCP, o sistema KKT pode ser reformulado como uma equação do tipo H(z) = O, onde H é uma função semi-suave. Nos preliminares teóricos apresentamos os conceitos importantes para a análise desse tipo de sistema quando a função involvida não é diferenciável. Trata-se de subdiferencial, semi-suavidade, semi-derivada. Então, usando um ponto de vista global, descrevemos de uma vez só as diferentes generalizações do método de Newton, apresentando as condições suficientes de convergência local. Uma versão globalizada do método é também detalhada. Com o fim de aplicar o algoritmo à reformulação semi-suave do sistema KKT, estudamos as propriedades da função H, primeiro independentemente da função NCP usada. Então analisamos o caso de três funções NCP particulares: a função do Mínimo, a função de Fischer-Burmeister, a função de Fischer-Burmeister Penalizada. Apresentamos os resultados de testes numéricos que comparam o desempenho do algoritmo quando usa as diferentes funções NCP acima / Abstract: This work deals with the use of generalized Newton type method to solve KKT systems. By the mean of so called NCP functions, any KKT system can be writen as an equation of type H(z) = O, where H is a semismooth function. In a teorical preliminaries part, we present some key notions for the analysis of such a type of system, whose the involved function is not differentiable. It deals with subdifferential, semismoothness, semiderivative. Then, tackling the problem with a very general point of view, we make a unified description of different generalizations of N ewton method, giving sufficient local convergence conditions. More over, we detail a possible globalization of such methods. In order to use this global algorithm to solve semismooth form of KKT systems, we study some of the H function's properties, first without specifying any underlying NCP function, and then in the case of three known NCP functions: the minimum function, the Fischer-Burmeister function and the penalized Fischer-Burmeister function. Finally, we give the results of numerical tests, which compare the algorithm's performance for each of these three NCP functions / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientadores: Carlos Alberto de Castro Junior, Luiz Carlos Pereira da Silva / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T14:18:50Z (GMT). No. of bitstreams: 1 Meireles_EduardoDavid_M.pdf: 1486956 bytes, checksum: 1e441015d6ae62bfd66ac90c0c7635dd (MD5) Previous issue date: 2005 / Resumo: A literatura técnica registra uma série de metodologias propostas para a obtenção do estado de operação das chamadas redes mal condicionadas, ou seja, redes cujos modelos resultam em sistemas de equações de difícil resolução [1, 2]. Estas metodologias mostraram-se úteis também em situações em que a operação da rede é infactível, ou seja, situações em que o sistema de equações que representa a rede não apresenta soluções. Nestes casos, os métodos de resolução do problema de fluxo de carga convencionais divergem, não oferecendo informações úteis sobre a rede. Já as metodologias específicas para redes mal condicionadas oferecem, mesmo na situação de divergência, informações que podem ser úteis no sentido de apontar suas possíveis causas. Recentemente, foi levantada a possibilidade de que estas supostas redes mal condicionadas não existissem de fato, mas estivessem simplesmente operando em torno do seu limite de estabilidade de tensão [3], ou seja, o mal condicionamento seria resultado de problemas de estabilidade de tensão e não do mal condicionamento propriamente dito. De acordo com [3], após uma série de simulações não foram encontradas situações em que a rede fosse mal condicionada e estivesse operando em condições normais de operação no que diz respeito à estabilidade de tensão. Os testes mostrados em [3] foram realizados utilizando-se o fluxo de carga da continuação [4]. O objetivo deste trabalho é realizar alguns testes para analisar e discutir as conclusões de [3]. Para isso, algumas simulações adicionais foram realizadas para redes teste mal condicionadas apresentadas em [2], dentre outras. As conclusões deste trabalho apontam para a importância de se continuar a pesquisa para o desenvolvimento de métodos para a resolução de sistemas mal condicionados / Abstract: A number of methods for computing the operating state of the so-called ill-conditioned systems can be found in the literature. A power system is called ill-conditioned if its model results in a set of equations for which the resolution presents numerical difficulties [1, 2]. Those methods also showed to be useful tools in situations where the operation is unfeasible, that is, situations in which the set of equations that represents the network do not present any solution. In these cases the conventional load flow methods diverge and do not provide any useful information about the system operating condition. On the other hand, specific load flow methods for ill-conditioned systems do provide such information, even in divergence situations, and the possible causes of the numerical problems may be inferred. Recently, the possibility that the alleged ill-conditioned systems are in fact systems operating close to or beyond their voltage stability limit was discussed [3]. Therefore, the ill-conditioning would be the result of voltage stability problems rather than ill-conditioning itself. According to [3], after a number of simulations no situations where found such that the system was indeed ill-conditioned and was operating in normal condition as far as voltage stability is concerned. The tests carried out in [3] used continuation load method [4]. The main goal of this work is to carry out some simulation tests to analyze and discuss the conclusion presented in [3]. Also, some additional simulations were done for other ill-conditioned systems shown in [2], among others. The conclusions of this work point towards the importance of a continuing effort in the development of efficient methods for solving ill-conditioned systems / Mestrado / Energia Eletrica / Mestre em Engenharia Elétrica