Vários problemas do mundo real podem ser modelados como problemas de otimização global, os quais são comuns em diversos campos da Engenharia e Ciência. Em geral, problemas complexos e de larga-escala não podem ser resolvidos de forma eficiente por técnicas determinísticas. Desse modo, algoritmos probabilísticos, como as metaheurísticas, têm sido amplamente empregados para otimização global. Duas das principais dificuldades nesses problemas são escapar de regiões sub-ótimas e evitar convergência prematura do algoritmo. À medida que a complexidade do problema aumenta, devido a um grande número de variáveis ou de regiões sub-ótimas, o tempo computacional torna-se grande e a possibilidade de que o algoritmo encontre o ótimo global diminui consideravelmente. Para solucionar esses problemas, propõe-se o uso de técnicas de aumento ou melhoria de eficiência. Com essas técnicas, buscase desenvolver estratégias que sejam aplicáveis a diversos algoritmos de otimização global, ao invés de criar um novo algoritmo de otimização ou um algoritmo híbrido. No contexto de problemas contínuos, foram desenvolvidas técnicas para determinação de uma ou mais regiões promissoras do espaço de busca, que contenham uma grande quantidade de soluções de alta qualidade, com maior chance de conterem o ótimo global. Duas das principais técnicas propostas, o Algoritmo de Otimização de Domínio (DOA) e a arquitetura de Amostragem Inteligente (SS), foram testadas com sucesso significativo em vários problemas de otimização global utilizados para benchmark na literatura. A aplicação do DOA para metaheurísticas produziu melhoria de desempenho em 50% dos problemas testados. Por outro lado, a aplicação da SS produziu reduções de 80% da quantidade de avaliações da função objetivo, bem como aumentou a taxa de sucesso em encontrar o ótimo global. Em relação a problemas discretos (binários), foram abordados problemas nos quais existem correlações entre as variáveis, que devem ser identificadas por um modelo probabilístico. Das duas técnicas de aumento de eficiência propostas para esses problemas, a técnica denominada Gerenciamento do Tamanho da População (PSM) possibilita a construção de modelos probabilísticos mais representativos. Com o PSM foi possível atingir uma redução de cerca de 50% na quantidade de avaliações, mantendo a taxa de sucesso em 100%. Em resumo, as técnicas de aumento de eficiência propostas mostramse capazes de aumentar significativamente o desempenho de metaheurísticas, tanto para problemas contínuos quanto para discretos / Several real-world problems from various fields of Science and Engineering can be modeled as global optimization problems. In general, complex and large-scale problems can not be solved eficiently by exact techniques. In this context, Probabilistic algorithms, such as metaheuristics, have shown relevant results. Nevertheless, as the complexity of the problem increases, due to a large number of variables or several regions of the search space with sub-optimal solutions, the running time augments and the probability that the metaheuristics will find the global optimum is significantly reduced. To improve the performance of metaheuristics applied to these problems, new eficiency-enhancement techniques (EETs) are proposed in this thesis. These EETs can be applied to different types of global optimization algorithms, rather than creating a new or a hybrid optimization algorithm. For continuous problems, the proposed EETs are the Domain Optimization Algorithm (DOA) and the Smart Sampling (SS) architecture. In fact, they are pre-processing algorithms that determine one or more promising regions of the search-space, containing a large amount of high-quality solutions, with higher chance of containing the global optimum. The DOA and SS were tested with signicant success in several global optimization problems used as benchmark in the literature. The application of DOA to metaheuristics produced a performance improvement in 50% of problems tested. On the other hand, the application of SS have produced reductions of 80% of the evaluations of the objective function, as well as increased the success rate of finding the global optimum. For discrete problems (binary), we focused on metaheuristics that use probabilistic models to identify correlations among variables that are frequent in complex problems. The main EET proposed for discrete problems is called Population Size Management (PSM), which improves the probabilistic models constructed by such algorithms. The PSM produced a reduction of 50% of function evaluations maintaining the success rate of 100%. In summary, the results show that the proposed EETs can significantly increase the performance of metaheuristics for both discrete and continuous problems

O Problema do Lapidário tem como objetivo encontrar o modelo de lapidação que resulte no maior aproveitamento volumétrico para uma dada gema bruta. Nesta dissertação apresentamos um Algoritmo Genético com variáveis de valores reais, e um GRASP Contínuo como heurísticas para resolução deste problema. Ambos os algoritmos maximizam o fator de escala do modelo de lapidação, sobre todas as posições de centro e ângulos de giro que o modelo pode assumir, buscando encontrar o modelo de maior volume inscrito no interior da gema, representada virtualmente por uma malha triangular. Propomos também um algoritmo de avaliação de uma instância do problema, o qual determina eficientemente o maior fator de escala, para um dado centro e orientação, que o modelo de lapidação pode assumir permanecendo completamente no interior da gema. Os algoritmos propostos foram avaliados em um conjunto de 50 gemas reais para o problema, utilizando como modelos base os cortes redondo e oval. Por fim, comparamos os resultados computacionais obtidos em relação a aproveitamento volumétrico e tempo de execução com os principais trabalhos relatados na literatura, demonstrando que as heurísticas propostas são competitivas com as demais abordagens. / The goal of the gemstone cutting problem is to find the largest cutting design which fits inside a given rough gemstone. In this work, we propose a real-valued Genetic Algorithm and a Continuous GRASP heuristic to solve it. The algorithms determine the largest scaling factor, over all possibilities of centers and orientations which the cutting could assume, finding the cutting with the largest volume as possible inside a gemstone, represented by a triangular mesh. We also propose an algorithm to evaluate a problem instance. This method efficiently determines the greatest scaling factor, for a given center and orientation, such that the cutting fits inside the rough gemstone. The proposed algorithms are validated for an instance set of 50 real-world gemstones, using the round and oval cuttings. Finally, we compare our computational results, for volume yield and running time, with the state-of-art. Ours methods are proved be competitive with the previous approachs.

Orientador: Marcia Aparecida Gomes Ruggiero / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T09:36:27Z (GMT). No. of bitstreams: 1 Goncalves_DouglasSoares_M.pdf: 1768338 bytes, checksum: c4cc7b4b0fd9fd75e8b01510162d7662 (MD5) Previous issue date: 2009 / Resumo: Neste trabalho analisamos dois métodos para otimização global irrestrita: DIRECT, um método tipo branch-and-select, baseado em otimização Lipschitziana, com um critério especial de seleção que balanceia a ênfase entre busca local e global; e um método tipo branch-and-bound empregando as mais recentes técnicas em análise intervalar, junto com back-boxing e busca local, para acelerar o processo de convergência. Variações do método branch-and-bound intervalar, e combinaçções deste com as idéias do DIRECT foram formuladas e implementadas. A aplicação a problemas clássicos encontrados na literatura mostrou que as estratégias adotadas contribuíram para melhorar o desempenho dos algoritmos. / Abstract: In this work we analyze two unconstrained global optimization methods: DIRECT, a branch-and-select method, based on Lipschitzian optimization, with a special selection criterion that balances the emphasis between local and global search; and a branch-and-bound method incorporating the state of art interval analysis techniques, with back-boxing and local search, to speed up the convergence process. Interval branch-and-bound method variations, and combinations of them with the ideas of DIRECT were proposed and implemented. Application to classical problems found in literature, shows that the adopted strategies contribute to improve the performance of the algorithms. / Mestrado / Otimização / Mestre em Matemática Aplicada

Philosophiae Doctor - PhD / Antimicrobial peptides (AMPs) play a key role in the innate immune response. They can be ubiquitously found in a wide range of eukaryotes including mammals, amphibians, insects, plants, and protozoa. In lower organisms, AMPs function merely as antibiotics by permeabilizing cell membranes and lysing invading microbes. Prediction of antimicrobial peptides is important because experimental methods used in characterizing AMPs are costly, time consuming and resource intensive and identification of AMPs in insects can serve as a template for the design of novel antibiotic. In order to fulfil this, firstly, data on antimicrobial peptides is extracted from UniProt, manually curated and stored into a centralized database called dragon antimicrobial peptide database (DAMPD). Secondly, based on the curated data, models to predict antimicrobial peptides are created using support vector machine with optimized hyperparameters. In particular, global optimization methods such as grid search, pattern search and derivative-free methods are utilised to optimize the SVM hyperparameters. These models are useful in characterizing unknown antimicrobial peptides. Finally, a webserver is created that will be used to predict antimicrobial peptides in haemotophagous insects such as Glossina morsitan and Anopheles gambiae. / South Africa

Traditionally, linear programming (LP) has been used to construct convex relaxations in the context of branch and bound for determining global optimal solutions to nonconvex optimization problems. As second-order cone programming (SOCP) and semidefinite programming (SDP) become better understood by optimization researchers, they become alternative choices for obtaining convex relaxations and producing bounds on the optimal values. In this thesis, we study the use of these convex optimization tools in constructing strong relaxations for several nonconvex problems, including 0-1 integer programming, nonconvex box-constrained quadratic programming (BoxQP), and general quadratic programming (QP). We first study a SOCP relaxation for 0-1 integer programs and a sequential relaxation technique based on this SOCP relaxation. We present desirable properties of this SOCP relaxation, for example, this relaxation cuts off all fractional extreme points of the regular LP relaxation. We further prove that the sequential relaxation technique generates the convex hull of 0-1 solutions asymptotically. We next explore nonconvex quadratic programming. We propose a SDP relaxation for BoxQP based on relaxing the first- and second-order KKT conditions, where the difficulty and contribution lie in relaxing the second-order KKT condition. We show that, although the relaxation we obtain this way is equivalent to an existing SDP relaxation at the root node, it is significantly stronger on the children nodes in a branch-and-bound setting. New advance in optimization theory allows one to express QP as optimizing a linear function over the convex cone of completely positive matrices subject to linear constraints, referred to as completely positive programming (CPP). CPP naturally admits strong semidefinite relaxations. We incorporate the first-order KKT conditions of QP into the constraints of QP, and then pose it in the form of CPP to obtain a strong relaxation. We employ the resulting SDP relaxation inside a finite branch-and-bound algorithm to solve the QP. Comparison of our algorithm with commercial global solvers shows potential as well as room for improvement. The remainder is devoted to new techniques for solving a class of large-scale linear programming problems. First order methods, although not as fast as second-order methods, are extremely memory efficient. We develop a first-order method based on Nesterov's smoothing technique and demonstrate the effectiveness of our method on two machine learning problems.

This thesis will deal with the use of artificial intelligence methods for solving optimization problems with multiple variables. A theorethical part presents problems of global optimization and overview of solution methods. For practical reasons, special attention is paid to evolutionary algorithms. The subject of optimization itself is energy harvester based on a piezoelectric effect. Its nature and modeling is devoted to one chapter. A part of the thesis is the implementation of the SOMA algorithm for finding the optimal parameters of the generator for maximum performance.

Microsized hexagonal gallium nitride pyramids show promise as next generation Light Emitting Diodes (LEDs) due to certain quantum properties within the pyramids. One metric for evaluating the efficiency of a LED device is by studying its Light Extraction Efficiency (LEE). To calculate the LEE for different pyramid designs, simulations can be performed using the FDTD method. Maximizing the LEE is treated as a black-box optimization problem with an interpolation method that utilizes radial basis functions. A simple heuristic is implemented and tested for various pyramid parameters. The LEE is shown to be highly dependent on the pyramid size, the source position and the polarization. Under certain circumstances, a LEE over 17% is found above the pyramid. The results are however in some situations very sensitive to the simulation parameters, leading to results not converging properly. Establishing convergence for all simulation evaluations must be done with further care. The results imply a high LEE for the pyramids is possible, which motivates the need for further research.

Radio resource allocation in communication networks is essential to achieve optimal performance and resource utilization. In modern interference networks the corresponding optimization problems are often nonconvex and their solution requires significant computational resources. Hence, practical systems usually use algorithms with no or only weak optimality guarantees for complexity reasons. Nevertheless, asserting the quality of these methods requires the knowledge of the globally optimal solution. State-of-the-art global optimization approaches mostly employ Tuy's monotonic optimization framework which has some major drawbacks, especially when dealing with fractional objectives or complicated feasible sets. In this thesis, two novel global optimization frameworks are developed. The first is based on the successive incumbent transcending (SIT) scheme to avoid numerical problems with complicated feasible sets. It inherently differentiates between convex and nonconvex variables, preserving the low computational complexity in the number of convex variables without the need for cumbersome decomposition methods. It also treats fractional objectives directly without the need of Dinkelbach's algorithm. Benchmarks show that it is several orders of magnitude faster than state-of-the-art algorithms. The second optimization framework is named mixed monotonic programming (MMP) and generalizes monotonic optimization. At its core is a novel bounding mechanism accompanied by an efficient BB implementation that helps exploit partial monotonicity without requiring a reformulation in terms of difference of increasing (DI) functions. While this often leads to better bounds and faster convergence, the main benefit is its versatility. Numerical experiments show that MMP can outperform monotonic programming by a few orders of magnitude, both in run time and memory consumption. Both frameworks are applied to maximize throughput and energy efficiency (EE) in wireless interference networks. In the first application scenario, MMP is applied to evaluate the EE gain rate splitting might provide over point-to-point codes in Gaussian interference channels. In the second scenario, the SIT based algorithm is applied to study throughput and EE for multi-way relay channels with amplify-and-forward relaying. In both cases, rate splitting gains of up to 4.5% are observed, even though some limiting assumptions have been made.

<div>Distillation is the most important separation process that accounts for 90-95% of all separations in the chemical industries. Even slight improvements can tremendously impact the landscape of the chemical economy world. The goal of this thesis is to develop mathematical modeling and global optimization approaches as well as systematic process intensification strategies to design and synthesize compact, easy-to-operate, energy-efficient, and cost-effective multicomponent distillation systems.</div><div><br></div><div>Towards this goal, we discuss the following aspects in this thesis:</div><div><br></div><div><div>1. We solve a longstanding challenge in chemical engineering of developing a short-cut method to determine the minimum reflux condition for any multi-feed, multi-product distillation column separating ideal multicomponent mixtures. The classic Underwood's method turns out to be a special case of our approach.</div><div><br></div><div>2. We develop the first enumeration based global optimization algorithm to identify optimal distillation configurations that can potentially save up to 50% of total cost or total exergy loss compared to conventional schemes from the immense configuration search space. For the first time in the literature, global optimality is guaranteed.</div><div><br></div><div>3. We propose a systematic and comprehensive multi-layer approach for process intensification in multicomponent distillation. For the first time, industrial practitioners have an easy-to-follow recipe to generate an array of completely new and attractive highly intensified configuration designs that further enhance operability, improve efficiency, and reduce total costs.</div></div>

No description available.