Abstract: This work is concerned with the development and the implementation of a global optimization method for solving nonlinear nonconvex problems with continuous or mixed integer variables, related to power systems analysis. The proposed method relaxes the problem under study into a linear outer approximation problem by using the concept of special ordered sets. The obtained problem is then successively refined by a branch-and-bound strategy. In this way, the convergence to a global optimum is guaranteed, provided the discrete variables or those appearing nonlinearly in the original problem are bounded. Our method, conceived to solve a specific kind of problem, has been developed in a general framework in such a way that it can be easily extended to solve a large class of problems. We first derive the method theoretically and next present numerical results, fixing some choices inherent to the method to make it as optimal as possible. / Résumé: Ce travail a pour objet la conception et l'implémentation d'une méthode d'optimisation globale pour la résolution de problèmes non linéaires et non convexes, continus ou avec variables mixtes (entières et continues), issus de l'analyse des réseaux électriques. La méthode proposée relâche le problème traité en un problème d'approximation externe linéaire en se basant sur le concept d ensembles spécialement ordonnés. Le problème obtenu est alors successivement raffiné grâce à une stratégie de branch-and-bound. La convergence vers un optimum global est ainsi assurée, pour autant que les variables discrètes ou apparaissant non linéairement dans le problème de départ soient bornées. Notre méthode, mise au point pour résoudre un type de problème bien particulier, a été conçue dans un cadre général permettant une extension aisée à la résolution d'une grande variété de problèmes. Nous développons tout d'abord la méthode théoriquement et présentons ensuite des résultats numériques dont le but est de fixer certains choix inhérents à la méthode afin de la rendre la plus optimale possible.

Multiple gravity assist (MGA) spacecraft trajectories can be difficult to find, an intractable problem to solve completely. However, these trajectories have enormous benefits for missions to challenging destinations such as outer planets and primitive bodies. Techniques are presented to aid in solving this problem with a global search tool and additional investigation into one particular proximity operations option is discussed. Explore is a global grid-search MGA trajectory pathsolving tool. An efficient sequential tree search eliminates v∞ discontinuities and prunes trajectories. Performance indices may be applied to further prune the search, with multiple objectives handled by allowing these indices to change between trajectory segments and by pruning with a Pareto-optimality ranking. The MGA search is extended to include deep space maneuvers (DSM), v∞ leveraging transfers (VILT) and low-thrust (LT) transfers. In addition, rendezvous or nπ sequences can patch the transfers together, enabling automatic augmentation of the MGA sequence. Details of VILT segments and nπ sequences are presented: A boundaryvalue problem (BVP) VILT formulation using a one-dimensional root-solve enables inclusion of an efficient class of maneuvers with runtime comparable to solving ballistic transfers. Importantly, the BVP VILT also allows the calculation of velocity-aligned apsidal maneuvers (VAM), including inter-body transfers and orbit insertion maneuvers. A method for automated inclusion of nπ transfers such as resonant returns and back-flip trajectories is introduced: a BVP is posed on the v∞ sphere and solved with one or more nπ transfers – which may additionally fulfill specified science objectives. The nπ sequence BVP is implemented within the broader search, combining nπ and other transfers in the same trajectory. To aid proximity operations around small bodies, analytical methods are used to investigate stability regions in the presence of significant solar radiation pressure (SRP) and body oblateness perturbations. The interactions of these perturbations allow for heliotropic orbits, a stable family of low-altitude orbits investigated in detail. A novel constrained double-averaging technique analytically determines inclined heliotropic orbits. This type of knowledge is uniquely valuable for small body missions where SRP and irregular body shape are very important and where target selection is often a part of the mission design.

- / -

Cette thèse traite de stratégies d'évaluation séquentielle et batch-séquentielle de fonctions à valeurs réelles sous un budget d'évaluation limité, à l'aide de modèles à processus Gaussiens. Des stratégies optimales de réduction séquentielle d'incertitude (SUR) sont étudiées pour deux problèmes différents, motivés par des cas d'application en sûreté nucléaire. Tout d'abord, nous traitons le problème d'identification d'un ensemble d'excursion au dessus d'un seuil T d'une fonction f à valeurs réelles. Ensuite, nous étudions le problème d'identification de l'ensemble des configurations "robustes, contrôlées", c'est à dire l'ensemble des inputs contrôlés où la fonction demeure sous T quelle que soit la valeur des différents inputs non-contrôlés. De nouvelles stratégies SUR sont présentés. Nous donnons aussi des procédures efficientes et des formules permettant d'utiliser ces stratégies sur des applications concrètes. L'utilisation de formules rapides pour recalculer rapidement le posterior de la moyenne ou de la fonction de covariance d'un processus Gaussien (les "formules d'update de krigeage") ne fournit pas uniquement une économie computationnelle importante. Elles sont aussi l'un des ingrédient clé pour obtenir des formules fermées permettant l'utilisation en pratique de stratégies d'évaluation coûteuses en temps de calcul. Une contribution en optimisation batch-séquentielle utilisant le Multi-points Expected Improvement est également présentée.

This thesis presents the research results on the development of a microwave tomography imaging algorithm capable of reconstructing the dielectric properties of the unknown object. Our focus was on the theoretical aspects of the non-linear tomographic image reconstruction problem with particular emphasis on developing efficient numerical and non-linear optimization for solving the inverse scattering problem. A detailed description of a novel microwave tomography method based on frequency dependent finite difference time domain, a numerical method for solving Maxwell's equations and Genetic Algorithm (GA) as a global optimization technique is given. The proposed technique has the ability to deal with the heterogeneous and dispersive object with complex distribution of dielectric properties and to provide a quantitative image of permittivity and conductivity profile of the object. It is shown that the proposed technique is capable of using the multi-frequency, multi-view, and multi-incident planer techniques which provide useful information for the reconstruction of the dielectric properties profile and improve image quality. In addition, we show that when a-priori information about the object under test is known, it can be easily integrated with the inversion process. This provides realistic regularization of the solution and removes or reduces the possibility of non-true solutions. We further introduced application of the GA such as binary-coded GA, real-coded GA, hybrid binary and real coded GA, and neural-network/GA for solving the inverse scattering problem which improved the quality of the images as well as the conversion rate. The implications and possible advantages of each type of optimization are discussed, and synthetic inversion results are presented. The results showed that the proposed algorithm was capable of providing the quantitative images, although more research is still required to improve the image quality. In the proposed technique the computation time for solution convergence varies from a few hours to several days. Therefore, the parallel implementation of the algorithm was carried out to reduce the runtime. The proposed technique was evaluated for application in microwave breast cancer imaging as well as measurement data from university of Manitoba and Institut Frsenel's microwave tomography systems.

This thesis presents the research results on the development of a microwave tomography imaging algorithm capable of reconstructing the dielectric properties of the unknown object. Our focus was on the theoretical aspects of the non-linear tomographic image reconstruction problem with particular emphasis on developing efficient numerical and non-linear optimization for solving the inverse scattering problem. A detailed description of a novel microwave tomography method based on frequency dependent finite difference time domain, a numerical method for solving Maxwell's equations and Genetic Algorithm (GA) as a global optimization technique is given. The proposed technique has the ability to deal with the heterogeneous and dispersive object with complex distribution of dielectric properties and to provide a quantitative image of permittivity and conductivity profile of the object. It is shown that the proposed technique is capable of using the multi-frequency, multi-view, and multi-incident planer techniques which provide useful information for the reconstruction of the dielectric properties profile and improve image quality. In addition, we show that when a-priori information about the object under test is known, it can be easily integrated with the inversion process. This provides realistic regularization of the solution and removes or reduces the possibility of non-true solutions. We further introduced application of the GA such as binary-coded GA, real-coded GA, hybrid binary and real coded GA, and neural-network/GA for solving the inverse scattering problem which improved the quality of the images as well as the conversion rate. The implications and possible advantages of each type of optimization are discussed, and synthetic inversion results are presented. The results showed that the proposed algorithm was capable of providing the quantitative images, although more research is still required to improve the image quality. In the proposed technique the computation time for solution convergence varies from a few hours to several days. Therefore, the parallel implementation of the algorithm was carried out to reduce the runtime. The proposed technique was evaluated for application in microwave breast cancer imaging as well as measurement data from university of Manitoba and Institut Frsenel's microwave tomography systems.

L'objectiu d'aquesta tesi és l'estudi de les diferents tècniques per alinear vistes tridimensionals. Aquest estudi ens ha permès detectar els principals problemes de les tècniques existents, aprotant una solució novedosa i contribuint resolent algunes de les mancances detectades especialment en l'alineament de vistes a temps real. Per tal d'adquirir les esmentades vistes, s'ha dissenyat un sensor 3D manual que ens permet fer adquisicions tridimensionals amb total llibertat de moviments. Així mateix, s'han estudiat les tècniques de minimització global per tal de reduir els efectes de la propagació de l'error. / The goal of this thesis is to study the different techniques used to register 3D acquisitions. This study detects the main drawbacks of the existing techniques, presents a new classification and provides significant solutions of some perceived shortcomings, especially in 3D real time registration. A 3D hand-held sensor has been designed to acquire these views without any motion restriction and global minimization techniques have been studied to decrease the error propagation effects.

The Multi-Layer Perceptron (MLP) is one of the most widely applied and researched Artificial Neural Network model. MLP networks are normally applied to performing supervised learning tasks, which involve iterative training methods to adjust the connection weights within the network. This is commonly formulated as a multivariate non-linear optimization problem over a very high-dimensional space of possible weight configurations. Analogous to the field of mathematical optimization, training an MLP is often described as the search of an error surface for a weight vector which gives the smallest possible error value. Although this presents a useful notion of the training process, there are many problems associated with using the error surface to understand the behaviour of learning algorithms and the properties of MLP mappings themselves. Because of the high-dimensionality of the system, many existing methods of analysis are not well-suited to this problem. Visualizing and describing the error surface are also nontrivial and problematic. These problems are specific to complex systems such as neural networks, which contain large numbers of adjustable parameters, and the investigation of such systems in this way is largely a developing area of research. In this thesis, the concept of the error surface is explored using three related methods. Firstly, Principal Component Analysis (PCA) is proposed as a method for visualizing the learning trajectory followed by an algorithm on the error surface. It is found that PCA provides an effective method for performing such a visualization, as well as providing an indication of the significance of individual weights to the training process. Secondly, sampling methods are used to explore the error surface and to measure certain properties of the error surface, providing the necessary data for an intuitive description of the error surface. A number of practical MLP error surfaces are found to contain a high degree of ultrametric structure, in common with other known configuration spaces of complex systems. Thirdly, a class of global optimization algorithms is also developed, which is focused on the construction and evolution of a model of the error surface (or search spa ce) as an integral part of the optimization process. The relationships between this algorithm class, the Population-Based Incremental Learning algorithm, evolutionary algorithms and cooperative search are discussed. The work provides important practical techniques for exploration of the error surfaces of MLP networks. These techniques can be used to examine the dynamics of different training algorithms, the complexity of MLP mappings and an intuitive description of the nature of the error surface. The configuration spaces of other complex systems are also amenable to many of these techniques. Finally, the algorithmic framework provides a powerful paradigm for visualization of the optimization process and the development of parallel coupled optimization algorithms which apply knowledge of the error surface to solving the optimization problem.

Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho, abordamos um problema de otimização de parâmetros da biofísica em que o objetivo é a obtenção da taxa média de concentração de substrato no fígado. Este problema é altamente não-linear, multimodal e com função-objetivo não-diferenciável. Resolvemos o mesmo através de métodos de otimização da literatura e introduzimos três métodos de otimização. Os métodos introduzidos neste trabalho são baseados na hibridização de um método estocástico, que explora o espaço de busca, com um método determinístico de busca direta, que faz uma busca local mais refinada nas áreas mais promissoras deste espaço. Os novos métodos são comparados aos da literatura e é verificado que o desempenho dos primeiros é superior. / In this work, we attack a parameter optimization problem from Biophysics, where the aim is to obtain the substrate concentration rate of a liver. This problem is highly non-linear, multimodal, and with non-differentiable objective-function. We solve it using optimization methods from the literature and three methods introduced in this work. The latter methods are based on the hybridization of a stochastic technique which explores the search space, with a direct search deterministic technique which exploits the most promising areas. Our results show that the new optimization methods perform better than those from the literature.

Made available in DSpace on 2015-05-14T12:36:40Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2336902 bytes, checksum: 41580878008a0f84da693637a48ceb33 (MD5) Previous issue date: 2013-08-08 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The present work deals with the Continuous Global Optimization Problem, in its minimization form, by testing two approaches for the Continuous Greedy Randomized Adaptive Search Procedure (C-GRASP). The development of the first method - sequential and hybrid - comes from the deficiency of current approaches to provide a good neighborhood space exploration. Being constructed from the combination of two meta-heuristics, standard C-GRASP and Continuous General Variable Neighborhood Search (C-GVNS), as a strategy to achieving symmetric trades of neighborhood structures, it performed efficiently in the computational tests that were taken. The second procedure arises from the large consume of time when using high dimension functions with the standard C-GRASP construction procedure. As the optimization problems have a high dimensionality increase, it s preferable to have two parallel versions of the optimization method in order to handle bigger problems. Thus, for this new procedure developed, it was used the Compute Unified Device Architecture (CUDA), which provided promising acceleration regarding the processing time, based on the experiments performed. / O presente trabalho aborda o Problema de Otimização Global Contínua, em sua forma de minimização, através de duas abordagens para o procedimento Continuous Greedy Randomized Adaptive Search Procedure (C-GRASP). A elaboração do primeiro método, sequencial e híbrido, parte da deficiência presente nas abordagens atuais, em promover boa exploração no espaço de vizinhança. Sendo constituída da combinação de duas meta-heurísticas, C-GRASP padrão e Continuous General Variable Neighborhood Search (C-GVNS). Como estratégia para a realização de trocas sistemática de estruturas de vizinhanças, mostrou-se eficiente aos testes computacionais realizados. O segundo procedimento elaborado parte do grande consumo de tempo ao utilizar funções com alta dimensão, pelo procedimento de construção do método C-GRASP padrão. Como os problemas de otimização possuem crescimento elevado de dimensionalidade, é desejável ter versões paralelas do método de otimização para lidar com os problemas maiores. Desta forma, para o novo procedimento elaborado foi empregado a plataforma de computação paralela Compute Unified Device Architecture (CUDA), que, conforme verificado nos experimentos realizados, promoveu promissora aceleração quanto ao tempo de processamento.