The goal of this thesis was to implement a practical tool for optimizing hy- perparameters of neural networks using Bayesian optimization. We show the theoretical foundations of Bayesian optimization, including the necessary math- ematical background for Gaussian Process regression, and some extensions to Bayesian optimization. In order to evaluate the performance of Bayesian op- timization, we performed multiple real-world experiments with different neural network architectures. In our comparison to a random search, Bayesian opti- mization usually obtained a higher objective function value, and achieved lower variance in repeated experiments. Furthermore, in three out of four experi- ments, the hyperparameters discovered by Bayesian optimization outperformed the manually designed ones. We also show how the underlying Gaussian Process regression can be a useful tool for visualizing the effects of each hyperparameter, as well as possible relationships between multiple hyperparameters. 1

In this thesis we propose four new methods for solving constrained global optimization problems. The first proposed algorithm is a differential evolution (DE) algorithm using penalty functions for constraint handling. The second algorithm is based on the first DE algorithm but also incorporates a filter set as a diversification mechanism. The third algorithm is also based on DE but includes an additional local refinement process in the form of the pattern search (PS) technique. The last algorithm incorporates both the filter set and PS into the DE algorithm for constrained global optimization. The superiority of feasible points (SFP) and the parameter free penalty (PFP) schemes are used as constraint handling mechanisms. The new algorithms were numerically tested using two sets of test problems and the results where compared with those of the genetic algorithm (GA). The comparison shows that the new algorithms outperformed GA. When the new methods are compared to each other, the last three methods performed better than the first method i.e. the DE algorithm. The new algorithms show promising results with potential for further research. Keywords: constrained global optimization, differential evolution, pattern search, filter method, penalty function, superiority of feasible points, parameter free penalty. ii

M.Sc., Faculty of Sciences, University of the Witwatersrand, 2011 / Abstract This dissertation is concerned with discrete global optimization of nonlinear problems. These problems are constrained and unconstrained and are not easily solvable since there exists multiplicity of local and global minima. In this dissertation, we study the current methods for solving such problems and highlight their ine ciencies. We introduce a new local search procedure. We study the rapidly-exploring random tree (RRT) method, found mostly in the research area of robotics. We then design two global optimization algorithms based on RRT. RRT has never been used in the eld of global optimization. We exploit its attractive properties to develop two new algorithms for solving the discrete nonlinear optimization problems. The rst method is called RRT-Optimizer and is denoted as RRTOpt. RRTOpt is then modi ed to include probabilistic elements within the RRT. We have denoted this method by RRTOptv1. Results are generated for both methods and numerical comparisons are made with a number of recent methods.

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.

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

The aim of thiswork is to locate a semi-obnoxious facility, i.e. tominimize the distances to a given set of customers in order to save transportation costs on the one hand and to avoid undesirable interactions with other facilities within the region by maximizing the distances to the corresponding facilities on the other hand. Hence, the goal is to satisfy economic and environmental issues simultaneously. Due to the contradicting character of these goals, we obtain a non-convex objective function. We assume that distances can be measured by rectilinear distances and exploit the structure of this norm to obtain a very efficient dual pair of algorithms.

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.

"Recently, sequencing technologies have generated massive and heterogeneous data sets. However, interpretation of these data sets is a major barrier to understand genomic heterogeneity in complex diseases. In this dissertation, we develop a Bayesian statistical method for single nucleotide level analysis and a global optimization method for gene expression level analysis to characterize genomic heterogeneity in mixed samples. The detection of rare single nucleotide variants (SNVs) is important for understanding genetic heterogeneity using next-generation sequencing (NGS) data. Various computational algorithms have been proposed to detect variants at the single nucleotide level in mixed samples. Yet, the noise inherent in the biological processes involved in NGS technology necessitates the development of statistically accurate methods to identify true rare variants. At the single nucleotide level, we propose a Bayesian probabilistic model and a variational expectation maximization (EM) algorithm to estimate non-reference allele frequency (NRAF) and identify SNVs in heterogeneous cell populations. We demonstrate that our variational EM algorithm has comparable sensitivity and specificity compared with a Markov Chain Monte Carlo (MCMC) sampling inference algorithm, and is more computationally efficient on tests of relatively low coverage (27x and 298x) data. Furthermore, we show that our model with a variational EM inference algorithm has higher specificity than many state-of-the-art algorithms. In an analysis of a directed evolution longitudinal yeast data set, we are able to identify a time-series trend in non-reference allele frequency and detect novel variants that have not yet been reported. Our model also detects the emergence of a beneficial variant earlier than was previously shown, and a pair of concomitant variants. Characterization of heterogeneity in gene expression data is a critical challenge for personalized treatment and drug resistance due to intra-tumor heterogeneity. Mixed membership factorization has become popular for analyzing data sets that have within-sample heterogeneity. In recent years, several algorithms have been developed for mixed membership matrix factorization, but they only guarantee estimates from a local optimum. At the gene expression level, we derive a global optimization (GOP) algorithm that provides a guaranteed epsilon-global optimum for a sparse mixed membership matrix factorization problem for molecular subtype classification. We test the algorithm on simulated data and find the algorithm always bounds the global optimum across random initializations and explores multiple modes efficiently. The GOP algorithm is well-suited for parallel computations in the key optimization steps. "

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.

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.