Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.

Neste trabalho analisamos a hipótese de diferenciabilidade da função valor-ótimo em uma classe de problemas de otimização dinâmica. A classe de problemas analisada é cálculo variacional com horizonte infinito. O artigo de Benveniste e Scheinkman (1979) é apresentado de forma detalhada, além disso, seu lema fundamental é generalizado ao excluirmos a hipótese de concavidade sobre a função auxiliar. Finalmente, aplicamos alguns resultados estabelecidos por Milgrom e Segal (2002), a fim de obtermos a diferenciabilidade da função valor-ótimo para a mesma classe de problemas, mas de uma nova maneira, ampliando a análise sobre o tema.

Os algoritmos baseados no paradigma Simulated Annealing e suas variações são atualmente usados de forma ampla na resolução de problemas de otimização de larga escala. Esta popularidade é resultado da estrutura extremamente simples e aparentemente universal dos algoritmos, da aplicabilidade geral e da habilidade de fornecer soluções bastante próximas da ótima. No início da década de 80, Kirkpatrick e outros apresentaram uma proposta de utilização dos conceitos de annealing (resfriamento lento e controlado de sólidos) em otimização combinatória. Esta proposta considera a forte analogia entre o processo físico de annealing e a resolução de problemas grandes de otimização combinatória. Simulated Annealing (SA) é um denominação genérica para os algoritmos desenvolvidos com base nesta proposta. Estes algoritmos combinam técnicas de busca local e de randomização. O objetivo do presente trabalho é proporcionar um entendimento das características do Simulated Annealing e facilitar o desenvolvimento de algoritmos com estas características. Assim, é apresentado como Simulated Annealing e suas variações estão sendo utilizados na resolução de problemas de otimização combinatória, proposta uma formalização através de um método de desenvolvimento de algoritmos e analisados aspectos de complexidade. O método de desenvolvimento especifica um programa abstrato para um algoritmo Simulated Annealing seqüencial, identifica funções e predicados que constituem os procedimentos deste programa abstrato e estabelece axiomas que permitem a visualização das propriedades que estes procedimentos devem satisfazer. A complexidade do Simulated Annealing é analisada a partir do programa abstrato desenvolvido e de seus principais procedimentos, permitindo o estabelecimento de uma equação genérica para a complexidade. Esta equação genérica é aplicável aos algoritmos desenvolvidos com base no método proposto. Uma prova de correção é apresentada para o programa abstrato e um código exemplo é analisado com relação aos axiomas estabelecidos. O estabelecimento de axiomas tem como propósito definir uma semântica para o algoritmo, o que permite a um desenvolvedor analisar a correção do código especificado para um algoritmo levando em consideração estes axiomas. O trabalho foi realizado a partir de um estudo introdutório de otimização combinatória, de técnicas de resolução de problemas, de um levantamento histórico do uso do Simulated Annealing, das variações em torno do modelo e de embasamentos matemáticos documentados. Isto permitiu identificar as características essenciais dos algoritmos baseados no paradigma, analisar os aspectos relacionados com estas características, como as diferentes formas de realizar uma prescrição de resfriamento e percorrer um espaço de soluções, e construir a fundamentação teórica genérica proposta.

[pt] O aumento da complexidade dos circuitos eletrônicos motivou o emprego de técnicas de projeto apoiadas no uso intensivo do computador. Estas técnicas, baseadas essencialmente nos métodos de otimização, auxiliam o projecionista na solução dos problemas relacionados com a área de Projeto de Circuitos Eletrônicos. A produção de circuitos em larga escala, em contraste com o desenvolvimento de prototipos, introduz um ambiente de projeto onde as flutuações estatísticas são consideradas, caracterizando o que é chamado de Projeto Estatístico. Os problemas relacionados com este ambiente de projeto e os métodos utilizados na sua solução são aqui analisados. São descritas as técnicas derivadas da formulação destes problemas através de um critério Minimax e apresentados os detalhes de implementação dos algorítmos utilizados neste trabalho. Para testar a aplicação dos algorítmos em problemas reais, foi desenvolvido em linguagem Fortran, um pacote de Simulação e Projeto no domínio de freqüência. Este programa, sem alterar a topologia e de suas tolerâncias, através dos algoritmos que otimizam o seu desempenho. / [en] The increase of the electronic circuits complexity motivated the use of computer supported design techniques. These techniques, mainly based on the optimization methods, aids the designers to solve different problems related to the Electronic Circuit Design area. The large scale production of circuits, contrasting with the development of prototypes, creates a design envionment where the statitiscal fluctuations are considered and it gives rise to the so called Statistical Design. It is analized here the problems related to this design envionment and their solutions via Optimization Methods. It is shown the description of the techniques derived during the formulation of these problems through a Minimax criteria as well as the details of the implementation of the developed algorithms. In order to test the algorithms in real world problems it was developed a Simulation Package for linear Circuits Design in the frequency domain. This program, without changes in the circuit topology, actuates over the values of the project prameters and their tolerancies through algorithms that optimize the circuit performance.

[pt] É apresentado um modelo para resolução de problemas de caminhos. Em seguida é feita a sua particularização para o problema de traçado de ligações num circuito impresso. E finalmente, procurou-se discutir a eficiência computacional do modelo proposto indicando alguns melhoramentos necessários. / [en] Under study in this research was a computational model for optimizing the solution of parth-problems. Additionaly an application of this model was made to the desing of priinted circuits. Finaly, the eficiency of the model was discussed leading to the identification of some needed improvements.

[pt] Nesta tese, é apresentado e analisado em termos da propriedade de convergência global um novo algoritmo para problemas de otimização quadrática sujeitos ou a restrições de desigualdades matriciais bilineares (BMIs) ou a restrições de desigualdades matriciais lineares (LMIs) dependentes da freqüência, estes problemas são muito relevantes para a teoria de controle porque uma ampla classe de controladores (por exemplo, controladores H2/Hinf de ordem fixa, síntese de controladores descentralizados, análise do desempenho robusto H2 ou Hinf, etc.) pode ser computada a partir da solução de problemas de otimização desta natureza. Infelizmente, estes problemas são reconhecidamente de difícil solução, pois envolvem, entre outras coisas, não convexidade (restrição BMI), não diferenciabilidade da restrição, etc. em função dessa complexibilidade, algumas alternativas para a obtenção de soluções aproximadas têm sido adotada na literatura especializada recente (Safonov, 1994; Paganini, 1996). O algoritmo proposto neste trabalho de tese é uma alternativa para as abordagens atuais com vantagens no sentido de permitir a obtenção de melhores aproximações assim como a possibilidade de explorar a estrutura particular de cada problema de interesse e, com isso, viabilizar do ponto de vista computacional o projeto de controladores envolvendo plantas de ordem mais elevada. Este algoritmo pode ser visto como a generalização de um algoritmo anterior com boas propriedades proposto por Corrêa & Sales (1998) para problemas quadráticos sujeitos a restrições envolvendo LMIs canônicas. De forma bastante genética, a solução do problema original (um problema envolvendo um número infinito de restrições é substituído por uma única) onde, em cada passo do algoritmo, a restrição é interativamente modificada. Demonstrar-se-á que para problemas quadráticos envolvendo restrições BMIs (problemas não convexos) a seqüência de soluções geradas pelo algoritmo convergirá para a solução ótima global do problema original. Por outro lado, no caso dos problemas quadráticos envolvendo restrições LMIs dependentes da freqüência, a seqüência gerada de custos auxiliares é monótona crescente e, adicionalmente, se a seqüência de matrizes de ponderação for limitada superiormente (uma condição suficiente), demonstrar-se-á que a seqüência de soluções geradas pelo algoritmo convergirá para a solução ótima global do problema original. Finalmente, são apresentadas algumas aplicações a problemas de controle acompanhadas de alguns exemplos numéricos ilustrativos. / [en] In this thesis, it is proposed and analysed in terms of the global-convergence property a new algorithm for solving quadratic optimisation problems under either a BMI (bilinear matrix inequality) or a frequency-dependent LMI (linear matrix inequality) constraints. These problems are of special interest in the control literature a some very important control problems such as the H2/H(infinite) fixed-order controller, multiobjectives, H2 and H (infinite) robust performance analysis among others problems can be posed as problems of this kind for which does not still exist yet a reliable global convergent algorithm. Nowadays, approximate solutions to those problems are based upon grid and interpolation techniques as suggested by Paganini (1996) in the case of frequency- wise LMI constraints or branch and bound algorithms or branch and bound algorithms mainly and alternating LMIs as far as BMIs constraints are involved (Safonov, 1994). All of those approaches suffer, of course, from obvious numerical difficulties. In fact, those approaches were introduced as preliminary attempts in solving the problems just mentioned. The algorithm to presented here, which can be seen as a generalisation of an earlier algorithm proposed by Corrêa e Sales (1998) for solving standard feasibility LMIs problems, is a step forward in an attempt of handling difficulties not faced properly by those methodologies. In a broaden sense, the proposed algorithm solves the original problem (a problem subject to an infinite number of constraints is replaced by a single one properly chosen. It is worth noting that this basic idea was introduced by Lawson (1961) in a rather different context, namely, the problem of computing Tchebycheff approximations by means of sequences of weighted quadratic problems. It is pointed out here that in the case of quadratic problems under a BMI constraint (a nonconvex problem); it is proved that the sequence of auxiliary solutions generated by the algorithm converges to the global optimal solution of the original one. On the other hand, as for quadratic problems under a frequency-dependent LMI constraint (an infinite-dimensional problem) it is proved that the auxiliary cost-sequence values increases asymptotically and, If the weight updating sequence is bounded from above (a sufficient condition), the sequence of auxiliary solutions will converge to the optimal solution of the original problem as well. Finally, some applications to control problem are presented accompanied by some numerical examples.

[pt] A geração de malhas geomecânicas de reservatórios ainda é uma tarefa tediosa que consome muito tempo. Para acelerar este processo, soluções que reconstroem analiticamente a geometria do reservatório têm sido propostas, mas essas soluções não são as mais adequadas para modelagem de objetos naturais. Este trabalho propõe uma modelagem discreta para a geometria do reservatório, onde os vértices da malha são posicionados por meio da solução de um problema de otimização quadrático e convexo. O problema de otimização é modelado de forma a garantir que as malhas geomecânicas de saída sejam suaves e que ao mesmo tempo respeitem as restrições do reservatório e dos horizontes presentes. Além disso, a metodologia proposta permite uma implementação eficiente, paralelizável e de baixo consumo de memória. Casos de teste com milhões de variáveis são apresentados para validar essa abordagem. Finalmente, a metodologia proposta neste trabalho para malhas de geomecânica pode ser naturalmente estendida para a modelagem estrutural de sub-superfícies na interpretação sísmica e de restauração geológica. / [en] Geomechanical mesh generation of complex reservoirs remains a tedious task prone to errors. Recently proposed solutions based on analytical reconstruction of the sub-surfaces are not capable to represent all the geometric details of natural objects. This work proposes a discrete model where the mesh vertices are positioned based on a convex quadratic optimization process. The optimization problem seeks to guarantee smooth meshes that conform with prescribed constraints. The resulting mesh therefore respects, as far as possible, the finite volume mesh of the reservoir pay zone and the existing horizons. Finally, the proposed methodology for Geomechanical meshes can be easily extend to model sub-surfaces present in the structural interpretation and geological restauration.

[pt] A indústria do petróleo sempre investiu em pesquisa de modo a otimizar as operações de perfuração. O objetivo é desenvolver tecnologia para aumentar a taxa de penetração e reduzir o tempo não produtivo durante a perfuração. As recentes descobertas de campos de petróleo localizados em camadas profundas, cobertas por espessas camadas de evaporitos aumentaram a importância dos estudos associados com a otimização nas bacias marítimas brasileiras do pré-sal. Existem muitos modelos para a previsão da taxa de penetração baseados em parâmetros operacionais tais como peso sobre a Broca (WOB), taxa de penetração (ROP), torque a rotação da broca (RPM), e resistência à compressão da rocha. A energia mecânica específica é o parâmetro freqüentemente usado como referência para estabelecer a eficiência das operações de perfuração assim como identificar o que deve ser modificado de modo a melhorar a perfuração. Esta dissertação analisa diferente métodos de otimização de perfuração baseados na energia mecânica específica. Estes métodos são aplicados a um conjunto de dados que consiste nos parâmetros de perfuração (WOB, T, RPM, ROP) obtidos ao longo dos trechos de evaporitos em 6 poços perfurados com broca PDC. Dados de ensaios de perfuração de grande escala realizados em laboratório também foram analisados nesta dissertação. Este estudo conclui que a energia mecânica específica ideal em muitas das operações está relacionada com uma parcela da resistência à compressão confinada da rocha. / [en] The oil industry has always invested in research in order to optimize drilling operation. The aim is to develop technology to increase the rate of penetration and reduce the non-productive time during drilling. The recent discovery of large oil reserves located in very deep layers that are covered with thick salt layers has increased the importance of studies associated with drilling optimization in Brazilian offshore sub-salt oil fields. There are many models to predict rate of penetration based on operational parameters, drill bit type and rock properties. The specific mechanical energy is the parameter often used as reference to guide the efficiency of the drilling operation as well as to identify what has to be changed in order to improve the drilling. This dissertation analyses different methods for drilling optimization based on the specific mechanical energy. These methods are applied to a data set that consists of drilling parameters (weight-onbit, torque, rate of penetration, rotation per minute) for 6 wells along the sections of evaporites. Large-scale drilling experiments carried out at the laboratory were also used. The study concludes that the ideal specific mechanical energy on most operations is related to a fraction of the confined compressive strength of the rock.

[pt] Os mercados de ações dos países emergentes tem como principal característica a presença de dias atípicos, os quais fazem impossível o uso, com sucesso, dos modelos de equilíbrio. O principal objetivo desta pesquisa é a de desenvolver uma nova teoria, baseada na estatísica robusta, que possa ser aplicada a estes mercados sem ser seriamente afetada por observações extremas, e que ao mesmo tempo, ofereça resultados eficientes e precisos. / [en] Emergent stock markets are characterized by the presence of atypical days, which make impossible the use of equilibrium models with sucess. The main aim of this research is to define a new theory, based on the robust statistical theory, which could be applied to those markets without being affected by extreme observations and, at the same time, offer efficient and accurate results. / [es] Los mercados de acciones de los países emergentes tienen como principal característica la presencia de días atípicos, lo que hace imposible el uso, con suceso, de los modelos de equilibrio. EL objetivo principal de esta investigación es desarrollar una nueva teoría, basada en la estadística robusta, que pueda ser aplicada a estos mercados sin ser seriamente afectada por observaciones extremas, y que al mismo tiempo, obtenga resultados eficientes y precisos.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Mecância, Florianópolis, 1992. / Made available in DSpace on 2012-10-16T22:55:47Z (GMT). No. of bitstreams: 1 274130.pdf: 2149963 bytes, checksum: 4db7506d460130a0ca920b029be8b8d6 (MD5) / O presente trabalho apresenta um estudo e aplicação de um método de otimização estrutural. Esse método reúne técnicas da teoria de controle ótimo e elementos finitos para obter um procedimento que oferece suporte teórico quanto às condições de ótimo a serem satisfeitas e abrangência de aplicação quanto ao tipo e tamanho do problema estrutural considerado. O procedimento é aqui utilizado para deduzir as condições de ótimo do problema de peso mínimo de placas homogêneas semi-espessas e placas sanduíche, ambas com restrição na frequência fundamental de vibração. Vários exemplos de placas sanduíche são testados e analisados.