Neste trabalho é introduzido e avaliado um conjunto de novas ideias para aumentar a eficiência do método Basin-Hopping Monte Carlo (BHMC) aplicado à otimização global de clusters e nanopartículas, que resultou no método BHMC revisado. Dentro deste método, tomou-se o cuidado de manter as características fundamentais do método BHMC padrão, que consistem na transformação da superfície de energia potencial em um conjunto de basins de atração, e no emprego de amostragem de Monte Carlo utilizando o critério de Metropolis. As ideias por trás do método BHMC revisado incluem um grande conjunto de operadores locais e não locais construídos especificamente para clusters e nanopartículas e que permitem maior mobilidade sobre a superfície de energia potencial durante a busca pelo mínimo global, duas estratégias de seleção de operadores, e um operador de filtro estrutural para remover soluções não físicas. A eficiência do método apresentado foi avaliada através da sua aplicação a um grande número de clusters e nanopartículas de tamanhos variados, compreendendo sistemas descritos tanto por potenciais empíricos, quanto por primeiros princípios dentro do formalismo da teoria do funcional da densidade (DFT). Os sistemas investigados foram clusters de Lennard-Jones e Sutton-Chen contendo até 148 átomos, um conjunto de nanopartículas de Lennard-Jones com tamanhos variando entre 200 e 1500 átomos, clusters binários de Lennard-Jones com até 100 átomos, clusters binários de metais de transição (AgPd)55 descritos pelo potencial de Sutton-Chen, clusters de alumínio puros com até 30 átomos descritos por DFT, e clusters de alumínio com até 15 átomos dopados com um átomo de cobre, também descritos por DFT. Através da otimização global sem bias de todas essas partículas, o método BHMC revisado foi capaz de reproduzir com sucesso os mínimos globais putativos mais recentes disponíveis na literatura obtidos por diversas técnicas de otimização global, e também foi capaz de identificar mínimos globais previamente desconhecidos. Além disso, em comparação com o método BHMC padrão, o método RBHMC mostrou maior eficiência para muitos dos sistemas investigados. As ideias contidas na metodologia apresentada constituem uma ferramenta valiosa para auxiliar investigações teóricas visando uma melhor compreensão da estrutura atômica de clusters e nanopartículas. / In this work it is introduced and evaluated a set of new ideas to increase the efficiency of the Basin-Hopping Monte Carlo (BHMC) method applied to the global optimization of clusters and nanoparticles, which resulted in the revised BHMC method. Within this method, care was taken to keep the main features of the standard BHMC method, which are the transformation of the potential energy surface into a set of basins of attraction, and the use of Monte Carlo sampling employing the Metropolis criterion. The ideas behind the revised BHMC method include a large set of local and non-local operators built specifically for clusters and nanoparticles which allow a greater mobility over the potential energy surface along of the search for the global minimum, two strategies for selecting the operators, and a structural filter operator to remove unphysical solutions. The efficiency of the presented method was evaluated by applying it to a large number of clusters and nanoparticles of various sizes, comprising systems described both by empirical potentials and by first-principles within the formalism of density functional theory (DFT). The systems that were investigated were Lennard-Jones and Sutton-Chen clusters with up to 148 atoms, a set of Lennard-Jones nanoparticles with sizes from 200 to 1500 atoms, binary Lennard-Jones clusters with up to 100 atoms, binary transition metal clusters (AgPd)55 described by the Sutton-Chen potential, pure aluminum clusters with up to 30 atoms described by DFT, and aluminum clusters with up to 15 atoms doped with a copper atom, also described by DFT. Through the unbiased global optimization of all those particles, the revised BHMC method was able to successfully reproduce the most recent putative global minima available in the literature obtained by several different global optimization techniques, and moreover, it was able to identify previously unkown global minima. Furthermore, in comparison with the standard BHMC method, the RBHMC method proved to be more efficient for many of the systems that were investigated. The ideas comprised within the presented methodology characterize a valuable tool for aiding theoretical investigations leading to a better understanding of the atomic structure of clusters and nanoparticles.

Este trabalho trata do problema de otimização do resultado para uma empresa (maximização da receita) que presta o serviço de transporte de carga conteinerizada por via marítima num cenário onde a demanda dos clientes supera a oferta de capacidade disponível. No trabalho são descritas as características do problema da escolha do mix de carga em um horizonte de planejamento típico de várias semanas (tipicamente de 6 a 8) com detalhamento diário, ou seja, caracterizando um problema de múltiplos períodos. Também são consideradas as restrições de peso e de volume dos navios utilizados e disponibilidade de contêineres. A proposta é maximizar o retorno gerado pelo transporte através da escolha do conjunto de clientes que apresentem a melhor rentabilidade total dentre um universo definido em um processo mensal de levantamento de demanda. Contribuem para o aumento da complexidade da modelagem do problema a necessidade de utilização de variáveis inteiras em função da escolha de cada carga de cada cliente, considerando também vários navios em múltiplas rotas e programação do reposicionamento de contêineres vazios em conjunto com os cheios. Para a resolução deste problema foi desenvolvida uma heurística para a solução do modelo matemático que analisa a rentabilidade relativa de cada carga segundo critérios de ocupação (volume e peso) dos navios. A partir daí, as cargas mais rentáveis são alocadas e são verificadas as restrições de capacidade do navio utilizado e a disponibilidade de contêineres vazios em um processo interativo, onde são analisadas as opções de reposicionamento dos contêineres vazios até a obtenção da solução ou recusa da carga. A heurística proposta permite considerar diferentes critérios de rentabilidade dos clientes e cargas, tendo sido aplicada a um problema real para a sua validação. Os resultados obtidos mostram uma oportunidade de melhoria no processo atual tanto no aspecto de aumento da lucratividade do negócio, objetivo principal do trabalho, como em outras questões como a programação antecipada do reposicionamento dos contêineres vazios e a flexibilização do espaço alocado para esta movimentação. / This work presents a problem of profit optimization (revenue maximization) in container shipment company by maritime modal in a scenario where demand surplus the available capacity. In this work is described the characteristics of cargo mix problem in a multiple planning period of several weeks (typically from 6 to 8) with diary scheduling, which means that it turns to a multiple period problem. It is also considered the weight and volume restrictions of the boats and availability of containers. The proposal is to maximize the return generated by the transportation service by choosing the set of clients that generates the bigger profitability in a major group defined in a monthly process of demand evaluation. The complexity of the problem is enhanced by the utilization of integer variables, because of the need of choosing each client and its cargo, also considering that it may be more than one ship in multiple routes and the empty containers transportation along with the cargo. For the solution of the problem, it was developed a heuristic for the solution of the mathematical model that analyses the profitability of each client according to occupation (volume and weight) of the ships. From this moment on, the most profitable cargos are allocated and the restriction of capacity of the ships and availability of empty containers are in a interactive process until the solution is found or the client discharged. This method was tested in a real problem of a maritime transportation company, comparing the various profitability criteria of the clients and cargos. The obtained results show an opportunity of actual process improvement concerning the profitability of the business, main objective of this work, as in the anticipation of the empty containers repositioning and flexibilization of the space allocated to this operation.

Modelos de Markov ocultos (MMOs) são uma ferramenta importante em matemática aplicada e estatística. Eles se baseiam em dois processos estocásticos. O primeiro é uma cadeia de Markov, que não é observada diretamente. O segundo é observável e sua distribuição depende do estado na cadeia de Markov. Supomos que os processos são discretos no tempo e assumem um número finito de estados. Para extrair informações dos MMOs, é necessário estimar seus parâmetros. Diversos algoritmos locais têm sido utilizados nas últimas décadas para essa tarefa. Nosso trabalho estuda a estimação de parâmetros em modelos de Markov ocultos, do ponto de vista da otimização global. Desenvolvemos algoritmos capazes de encontrar, em uma execução bem sucedida, todos os estimadores de máxima verossimilhança globais de um modelo de Markov oculto. Para tanto, usamos aritmética intervalar. Essa aritmética permite explorar sistematicamente o espaço paramétrico, excluindo regiões que não contém soluções. O cálculo da função objetivo é feito através da recursão \\textit, descrita na literatura estatística. Modificamos a extensão intervalar natural dessa recursão usando programação linear. Nossa abordagem é mais eficiente e produz intervalos mais estreitos do que a implementação padrão. Experimentos mostram ganhos de 16 a 250 vezes, de acordo com a complexidade do modelo. Revisamos os algoritmos locais, tendo em vista sua aplicação em métodos globais. Comparamos os algoritmos de Baum-Welch, pontos interiores e gradientes projetados espectrais. Concluímos que o método de Baum-Welch é o mais indicado como auxiliar em otimização global. Modificamos o \\textit{interval branch and bound} para resolver a estimação de modelos com eficiência. Usamos as condições KKT e as simetrias do problema na construção de testes para reduzir ou excluir caixas. Implementamos procedimentos de aceleração da convergência, como o método de Newton intervalar e propagação de restrições e da função objetivo. Nosso algoritmo foi escrito em \\textit{C++}, usando programação genérica. Mostramos que nossa implementação dá resultados tão bons quanto o resolvedor global BARON, porém com mais eficiência. Em média, nosso algoritmo é capaz de resolver $50\\%$ mais problemas no mesmo período de tempo. Concluímos estudando aspectos qualitativos dos MMOs com mistura Bernoulli. Plotamos todos os máximos globais detectados em instâncias com poucas observações e apresentamos novos limitantes superiores da verossimilhança baseados na divisão de uma amostra grande em grupos menores. / Hidden Markov models(HMMs) are an important tool in statistics and applied mathematics. Our work deals with processes formed by two discrete time and finite state space stochastic processes. The first process is a Markov chain and is not directly observed. On the other hand, the second process is observable and its distribution depends on the current state of the hidden component. In order to extract conclusions from a Hidden Markov Model we must estimate the parameters that defines it. Several local algorithms has been used to handle with this task. We present a global optimization approach based on interval arithmetic to maximize the likelihood function. Interval arithmetic allow us to explore parametric space systematically, discarding regions which cannot contain global maxima. We evaluate the objective function and its derivatives by the so called backward recursion and show that is possible to obtain sharper interval extensions for such functions using linear programming. Numerical experiments shows that our approach is $16$ to $250$ times more efficient than standard implementations. We also study local optimization algorithms hidden Markov model estimation. We compare Baum-Welch procedure with interior points and spectral projected gradients. We conclude that Baum-Welch is the best option as a sub-algorithm in a global optimization framework. We improve the well known interval branch and bound algorithm to take advantages on the problem structure. We derive new exclusion tests, based on its KKT conditions and symmetries. We implement our approach in C++, under generic programming paradigm. We show that our implementation is compatible with global optimization solver BARON in terms of precision. We also show that our algorithm is faster than BARON. In average, we can handle with $50\\%$ more problems within the same amount of time. We conclude studying qualitative aspects of Bernoulli hidden Markov models. We plot all global maxima found in small observations instances and show a new upper bound of the likelihood based on splitting observations in small groups.

Circuitos integrados analógicos são essenciais em sistemas eletrônicos modernos, sendo responsáveis por tarefas como conversão analógica/digital e digital/analógica, comunicação por radiofrequência, filtragem, etc. O projeto deste tipo de circuito e sistema é de grande complexidade uma vez que deve atender a especificações de desempenho cada vez mais exigentes e ter um tempo de projeto reduzido a fim de não comprometer o tempo total dos projetos de sinal misto. Diversas ferramentas são propostas na literatura visando auxiliar o projetista a aumentar sua produtividade. Apesar disso, devido à forte interligação entre etapas, o fluxo de projeto de circuitos integrados analógicos ainda é, tradicionalmente, realizado utilizando-se apenas cálculos manuais e posterior ajuste fino através de softwares de simulação elétrica. Neste trabalho, são estudadas técnicas de síntese de circuitos analógicos utilizando métodos modernos de otimização em nível de circuito e sistema. Após este estudo, é proposto um novo algoritmo de Simulated Annealing/Simulated Quenching, incluindo um mecanismo para utilização do operador de crossover considerando informações de múltiplos objetivos. É realizada a hibridização entre o algoritmo desenvolvido e um algoritmo de Particle Swarm Optimization para criação de um segundo algoritmo capaz de realizar a busca pela fronteira de Pareto. As características dos algoritmos propostos foram elaboradas visando a síntese de circuitos integrados analógicos, no entanto, resultados indicam que eles também têm excelente desempenho em comparação com diversos algoritmos atuais do tipo sem derivada para determinados problemas matemáticos. A generalidade dos métodos modernos de otimização permite que variações da mesma técnica sejam utilizadas em nível de circuito (dimensionamento e polarização de componentes do circuito) e de sistema (tradução de especificações de sistema em especificações de blocos). Dessa forma, são propostas técnicas para a criação de uma ferramenta de síntese em nível de sistema e circuito utilizando métodos modernos de otimização. Uma interface através de arquivos texto de entrada foi desenvolvida para tornar a ferramenta versátil e poder ser utilizada para uma grande variedade de tipos de circuitos eletrônicos. Para validar o algoritmo e a ferramenta na síntese em nível de circuito, foram sintetizados circuitos em tecnologia 0,35 µm, 180 nm e 130 nm. Entre eles, foram sintetizados amplificadores do tipo Miller, amplificadores do tipo folded cascode complementar, amplificadores de baixo ruído operando em 2,45 GHz e fontes de referência. Comparações utilizando o teste não paramétrico de Mann-Whitney-Wilcoxon mostram que o algoritmo proposto tem melhor desempenho que os demais algoritmos comparados para os casos estudados. Comparações com projetos manuais e outras ferramentas confirmam a eficácia dos algoritmos e ferramenta. Para validação da ferramenta em nível de sistema, foram sintetizados filtros do tipo Gm-C. / Analog integrated circuits are very important in modern electronic systems, performing tasks such as analog to digital conversion, digital to analog conversion, radio frequency communication, filtering and others. The design of this type of circuit requires attending to several performance specifications as well as a time specification in order to avoid compromising the overall design time of mixed signal projects. Several tools are proposed in the literature in order to aid the designer, however the traditional design flow for analog integrated circuits is usually accomplished using only hand calculations and adjusts through the use of electrical simulators. In this work, techniques for analog design synthesis for circuit and system level are studied. An optimization algorithm is proposed based on Simulated Annealing/Simulated Quenching with a mechanism for using the crossover operator considering multiobjective information. An hybrid algorithm combining the proposed algorithm with Particle Swarm Optimization was created to properly explore the Pareto front The characteristics of the algorithms are made to enable the synthesis of analog integrated circuits, however, tests indicate they have excellent performance in comparison with many other derivative-free algorithms when applied to certain mathematical problems. The generality of modern optimization methods allow that variations of the same techniques can be used in circuit level (sizing and biasing of circuit components) and in system level (translation of system specifications to block specifications). Therefore, techniques for the creation of a circuit-level and system-level tool are developed. An interface using spice-like text files as inputs is developed to allow the designer to use the tool for a wide range of electronic circuits. In order to validate the proposed algorithms and circuit level tool, circuits were synthesized in 0.35 m, 180 nm and 130 nm. The synthesized circuits included Miller amplifiers, complementary folded cascode amplifiers, low noise amplifiers operating at 2.45 GHz and voltage reference circuits. Comparisons using the non-parametric Mann-Whitney-Wilcoxon test showed that the proposed algorithm has better performance than the compared algorithms for the studied cases. At the system level, syntheses of Gm-C filters were performed to validate the tool.

Orientador: Paulo Augusto Valente Ferreira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-21T14:52:27Z (GMT). No. of bitstreams: 1 Ashtiani_AlirezaMohebi_D.pdf: 1381601 bytes, checksum: 9ae82bd53a7cf70422fed2348416f8f0 (MD5) Previous issue date: 2012 / Resumo: Muitos problemas práticos em Engenharia, Economia e Planejamento são modelados de maneira conveniente como problemas de Otimização Global. Esta tese tem como objetivo principal apresentar novas técnicas de Otimização Global com foco na resolução de duas importantes classes de problemas: problemas de Programação Multiplicativa Generalizada, os quais envolvem a minimização e a maximização de uma soma finita de produtos de funções convexas e côncavas, respectivamente, e problemas de Programação Fracionária Generalizada, os quais, por sua vez, envolvem a minimização e a maximização de uma soma finita de razões de funções convexa-côncava ou côncava-convexa, respectivamente. Na tese demonstra-se que todos estes problemas podem ser eficientemente resolvidos por um mesmo algoritmo de aproximação externa, a partir da reformulação dos problemas como problemas com infinitas restrições lineares de desigualdade. Um algoritmo baseado em enumeração de restrições e um algoritmo de aproximação externa combinado a uma técnica branch-and-bound são usados para resolver globalmente problemas de Programação Multiplicativa. Em seguida, as mesmas técnicas são empregadas na resolução de problemas de Programação Fracionária. Experiências computacionais atestam a viabilidade e a eficiência dos métodos de Otimização Global propostos, os quais também são facilmente programáveis a partir de pacotes de otimização disponíveis comercialmente / Abstract: Many practical problems in Engineering, Economics and Planning are modeled in a convenient way by Global Optimization problems. The principal objective of this thesis is to introduce new global optimization techniques with focus on the resolution of two important classes of problems: Generalized Multiplicative Programming Problems, in which involve the minimization and maximization of a finite sum of products of convex and concave functions, respectively, and Generalized Fractional Programming Problems, in which, in turn, involve the minimization and maximization of a finite sum of convex-concave and concave-convex ratio functions, respectively. The thesis demonstrates that all these problems can be efficiently solved by the same outer approximation algorithm, from the reformulation of the problems as problems with infinite linear inequality constraints. An algorithm based on a constraint enumeration and an outer approximation algorithm together with a branch-and-bound technique are used to globally solve Multiplicative Programming problems. Then, the same techniques are employed in the resolution of Fractional Programming problems. Computational experiments certify the viability and efficiency of the proposed Global Optimization methods, which are also easily programmable through commercially available optimization packages / Doutorado / Automação / Doutor em Engenharia Elétrica

Rapid advances of computer modeling and simulation tools and computing hardware have turned Model Based Design (MBD) a more viable technology. However, using a computationally intensive, “black-box” form MBD software tool to carry out design optimization leads to a number of key challenges. The non-unimodal objective function and/or non-convex feasible search region of the implicit numerical simulations in the optimization problems are beyond the capability of conventional optimization algorithms. In addition, the computationally intensive simulations used to evaluate the objective and/or constraint functions during the MBD process also make conventional stochastic global optimization algorithms unusable due to their requirement of a huge number of objective and constraint function evaluations. Surrogate model, or metamodeling-based global optimization techniques have been introduced to address these issues. Various surrogate models, including kriging, radial basis functions (RBF), multivariate adaptive regression splines (MARS), and polynomial regression (PR), are built using limited samplings on the original objective/constraint functions to reduce needed computation in the search of global optimum. In many real-world design optimization applications, computationally expensive numerical simulation models are used as objective and/or constraint functions. To solve these problems, enormous fitness function evaluations are required during the evolution based search process when advanced Global Optimization algorithms, such as DIRECT search, Differential Evolution (DE), and Bat Algorithm (BA) are used. In this work, improvements have been made to three widely used global optimization algorithms, Divided Rectangles (DIRECT), Differential Evolution (DE), and Bat Algorithm (BA) by integrating appropriate surrogate modeling methods to increase the computation efficiency of these algorithms to support MBD. The superior performance of these new algorithms in comparison with their original counterparts are shown using commonly used optimization algorithm testing benchmark problems. Integration of the surrogate modeling methods have considerably improved the search efficiency of the DIRECT, DE, and BA algorithms with significant reduction on the Number of Function Evaluations (NFEs). The newly introduced algorithms are then applied to a complex engineering design optimization problem, the design optimization of floating wind turbine platform, to test its effectiveness in real-world applications. These newly improved algorithms were able to identify better design solutions using considerably lower NFEs on the computationally expensive performance simulation model of the design. The methods of integrating surrogate modeling to improve DIRECT, DE and BA global optimization searches and the resulting algorithms proved to be effective for solving complex and computationally intensive global optimization problems, and formed a foundation for future research in this area. / Graduate

Neste trabalho, consideramos uma nova parametrização para o problema de empacotar a maior quantidade possível de círculos idênticos uma região elíptica dada. Apresentamos algoritmos com propriedades de convergência global e algumas estratégias heurísticas. Ilustramos com experimentos numéricos extensivos cada uma das estratégias utilizadas / In this work we consider a new parametrization for the problem of packing the maximum number of identical circles within a given elliptical region. We present algorithms with global convergence properties and some heuristic strategies. We illustrate each described strategy with extensive numerical experiments

This dissertation is concerned with the unconstrained global optimization of nonlinear problems. These problems are not easy to solve because of the multiplicity of local and global minima. In this dissertation, we first study the pattern search method for local optimization. We study the pattern search method numerically and provide a modification to it. In particular, we design a new pattern search method for local optimization. The new pattern search improves the efficiency and reliability of the original pattern search method. We then designed two simulated annealing algorithms for global optimization based on the basic features of pattern search. The new methods are therefore hybrid. The first hybrid method is the hybrid of simulated annealing and pattern search. This method is denoted by MSA. The second hybrid method is a combination of MSA and the multi-level single linkage method. This method is denoted by SAPS. The performance of MSA and SAPS are reported through extensive experiments on 50 test problems. Results indicate that the new hybrids are efficient and reliable.

No description available.

Indiana University-Purdue University Indianapolis (IUPUI) / The design optimization of laminated composite structures is of relevance in automobile, naval, aerospace, construction and energy industry. While several optimization methods have been applied in the design of laminated composites, the majority of those methods are only applicable to linear or simplified nonlinear models that are unable to capture multi-body contact. Furthermore, approaches that consider composite failure still remain scarce. This work presents an optimization approach based on design and analysis of computer experiments (DACE) in which smart sampling and continuous metamodel enhancement drive the design process towards a global optimum. Kriging metamodel is used in the optimization algorithm. This metamodel enables the definition of an expected improvement function that is maximized at each iteration in order to locate new designs to update the metamodel and find optimal designs. This work uses explicit finite element analysis to study the crash behavior of composite parts that is available in the commercial code LS-DYNA. The optimization algorithm is implemented in MATLAB. Single and multi-objective optimization problems are solved in this work. The design variables considered in the optimization include the orientation of the plies as well as the size of zones that control the collapse of the composite parts. For the ease of manufacturing, the fiber orientation is defined as a discrete variable. Objective functions such as penetration, maximum displacement and maximum acceleration are defined in the optimization problems. Constraints are included in the optimization problem to guarantee the feasibility of the solutions provided by the optimization algorithm. The results of this study show that despite the brittle behavior of composite parts, they can be optimized to resist and absorb impact. In the case of single objective problems, the algorithm is able to find the global solution. When working with multi-objective problems, an enhanced Pareto is provided by the algorithm.