This work encompasses three parts. The first part provides a concise review of the most prominent metaheuristic concepts currently available and gives essential preliminaries together with definition of the combinatorial optimization problems. It substantiates the choice of the investigation direction and basis idea of the developed methods. In the second part the new nonlinear global optimization routines based on the TS strategy are described. The new approaches are the Gradient Tabu Search (GTS), the Gradient Only Tabu Search (GOTS), and the Tabu Search with Powell’s Algorithm (TSPA). In the last part of the work the GOTS is applied for such chemical optimization problems. The chapter provides a systematic approach how the variables are chosen and the adjustable parameters are set. As test cases the global minimum energy conformation of some amino acids, of two angiotensin converting enzyme (ACE) inhibitors, of 2-acetoxy-N,N,N-trimethylethanaminium, and of a HIV-1 protease inhibitor is determined. / Die Arbeit umfasst drei Kapitel. Das erste Kapitel stellt eine kurze Zusammenfassung über die bekanntesten, zurzeit verwendeten Metaheuristischen-Konzepte dar und gibt notwendige Einleitungen zusammen mit der Definition der kombinatorischen Optimierungsprobleme. Das Kapitel begründet die Wahl des Tabu-Ansatzes und diskutiert die Basisideen der entwickelten Methoden. Im zweiten Kapitel werden die neuen entwickelten, nichtlinearen Optimierungsroutinen beschrieben, die auf Tabu-Suchstrategien beruhen. Die neuen Algorithmen sind Gradient Tabu Search (GTS), Gradient Only Tabu Search (GOTS) und Tabu Search with Powell’s Algorithm (TSPA). Das letzte Kapitel der Arbeit beschreibt die Anwendung der GOTS Methode auf dieses Problem. Diskutiert werden die Auswahl der Variablen und die Einstellung der justierbaren Parameter. Die Effizienz der GOTS Methode wird an Hand einiger Aminosäuren, zwei Angiotensin-Derivaten (ACE-Hemmer), des Acetylcholin und eines HIV-1-Protease-Hemmstoff gezeigt.

Würzburg, Univ., Diss., 2008 / Zsfassung in dt. Sprache

Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-08-17Bitstream added on 2014-06-13T18:49:37Z : No. of bitstreams: 1 campanha_ps_me_bauru.pdf: 713465 bytes, checksum: 80f1a0cfec7a9f0dda4e30ae9f1786ab (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Nesse trabalho propõe-se uma adaptação do método barreira penalidade quasi-Newton apresentado por P. Armand em 2003, para a resolução do problema do Fluxo de Potência Ótimo (FPO). Este método é denominado de método da função langrangiana barreira penalidade adaptada. Neste método as restrições de desigualdade são transformadas em igualdade pelo uso de variáveis de folga positivas. Estas variáveis são relaxadas, utilizando-se variáveis positivas, as quais, são incorporadas na função objetivo através de um termo de penalização. O novo problema restrito é então transformado em irrestrito associando a uma função lagrangiana às restrições de igualdade e uma função barreira penalidade às restrições de desigualdade. o algoritmo é composto por um ciclo interno e um externo. No ciclo interno é utilizado um método quasi-Newton para o cálculo das direções de busca e é determinado o tamanho do passo. No ciclo externo os parâmetros de barreira e penalidade são atualizados através de regras pré-definidas até que as condições de KKT sejam satisfeitas. Testes computacionais foram realizados utilizando problemas matemáticos e o problema de FPO, os quais demonstram a eficiência da adaptação proposta / This work proposes an adaptation of the quasi-Newton penalty barrier method presented by P. Armand in 2003. for the solution of the Optimal Power Flow (OPD) problem. This method is called method adapted penalty barrier lagrangian function. In this method the inequalities constraint are transformed in equality by adding non-negative slack variable. These variables are relaxed by positive auxiliary variables which are incorporated in the objective function through a penalty term. The new constraint problem is transformed in unconstraint by associating an lagrangian function for handling the equality constraint and an penalty barrier function for treating the inequality constraints. The algorithm is composed by an internal and external cycle. In the interanal cycle is used the quasi-Newton method to determine the search directions and the step size is calculated. In the external cycle the barrier parameters are updated through predefined rules until the KKT conditions are satisfied. Computational tests were accomplished using mathematical problems and the OPF problem which demonstrate the efficiency of the propose adaptation

Zugl.: Dresden, Techn. University, Diss., 2007.

Le système étudié durant cette thèse est un véhicule électrique hybride avec deux sources d’énergies (Pile à combustible et Super-capacité). L’objectif fixé est de minimiser la consommation du carburant tout en satisfaisant la demande instantanée en puissance sous des contraintes de puissance et de capacité et de stockage. Le problème a été modélisé sous la forme d’un problème d’optimisation globale. Nous avons développé de nouvelles méthodes heuristiques pour le résoudre et proposé le calcul d’une borne inférieure de consommation, en apportant de meilleurs résultats que ceux trouvés dans la littérature. En plus, une étude de robustesse a été réalisée afin de minimiser la consommation de pire-cas suite à une perturbation ou du fait d’incertitudes sur les données d’entrée, précisément sur la puissance demandée. Le but de cette étude est de prendre en compte les perturbations dès la construction des solutions afin d’éviter l’infaisabilité des solutions non robustes en situation perturbée. Les heuristiques de résolution du problème robuste modélisé sous la forme d’un problème de Minimax ont fourni des solutions moins sensibles aux perturbations que les solutions classiques. / The system studied in this thesis is a hybrid electrical vehicle with two energy sources (fuel cell system and super-capacitor). The first goal is to minimize the fuel consumption whilst satisfying the requested power for each instant, taking into account constraints on the availability and the state of charge of the storage element. The system was modeled as a global optimization problem. The heuristics developped for obtaining the best power split between the two sources and the lower bound consumption computation proposed provide better results than those found in the literature. The second goal of the thesis is the study of the robustness of the solutions in order to minimize the worst-case consumption when perturbation happens or uncertainty is added to the input data. In this study the uncertainty concerns the power required for traction. The objective is to maintain the feasibility of solutions and limit the worst consumption that can happen due to a demand fluctuation. Dedicated heuristics are proposed for solving the identified robust variant of the problem, modeled as a Minimax problem. The solutions provided are less sensitive to the perturbations than the previous ones.

La résolution des équations différentielles (EDP/EDO/EDA) est au cœur de la simulation de phénomènes physiques. L'accroissement de la taille et de la complexité des modèles nécessite la mise en œuvre de méthodes de résolution robustes et performantes en termes de temps de calcul. L'objectif de cette thèse est de proposer des méthodes pour accélérer la résolution des équations différentielles par des méthodes de décomposition de domaine. On considère d'abord les méthodes de décomposition de domaine de Schwarz pour la résolution de grands systèmes linéaires issus de la discrétisation d'EDP. Afin d'accélérer la convergence de la méthode de Schwarz, on propose une approximation de l'opérateur de propagation d'erreur. Cette approximation respectera la structure de l'opérateur exact, ce qui conduira à une réduction très significative des temps de calcul sur le problème des écoulements dans les milieux poreux hétérogènes. La deuxième contribution concerne la résolution de la suite de systèmes linéaires provenant de l'intégration en temps de problèmes non linéaires. On propose deux approches en utilisant le fait que la matrice jacobienne ne varie que peu d'un système à l'autre. Premièrement, on applique la mise à jour de Broyden au préconditionneur RAS (Restricted Additive Schwarz) au lieu de recalculer les factorisations LU. La deuxième approche consiste à dédier des processeurs a la mise à jour partielle et asynchrone du préconditionneur RAS. Des résultats numériques sur le problème de la cavité entrainée et sur un problème de réactiondiffusion montrent qu'une accélération super linéaire peut être obtenue. La dernière contribution a pour objet la résolution simultanée des problèmes non linéaires de pas de temps consécutifs. On étudie le cas où la méthode de Broyden est utilisée pour résoudre ces problèmes non linéaires. Dans ce cas, la mise à jour de Broyden peut être propagée d'un pas de temps à l'autre. La parallélisation à travers les pas de temps est également appliquée a la recherche d'une solution initiale consistante pour les équations différentielles algébriques / Solving differential equations (PDEs/ODEs/DAEs) is central to the simulation of physical phenomena. The increase in size and complexity of the models requires the design of methods that are robust and efficient in terms of computational time. The aim of this thesis is to design methods that accelerate the solution of differential equations by domain decomposition methods. We first consider Schwarz domain decomposition methods to solve large-scale linear systems arising from the discretization of PDEs. In order to accelerate the convergence of the Schwarz method, we propose an approximation of the error propagation operator. This approximation preserves the structure of the exact operator. A significant reduction of computational time is obtained for the groundwater flow problem in highly heterogeneous media. The second contribution concerns solving the sequence of linear systems arising from the time-integration of nonlinear problems. We propose two approaches, taking advantage of the fact that the Jacobian matrix does not change dramatically from one system to another. First, we apply Broyden’s update to the Restricted Additive Schwarz (RAS) preconditioner instead of recomputing the local LU factorizations. The second approach consists of dedicating processors to the asynchronous and partial update of the RAS preconditioner. Numerical results for the lid-driven cavity problem, and for a reaction-diffusion problem show that a super-linear speedup may be achieved. The last contribution concerns the simultaneous solution of nonlinear problems associated to consecutive time steps. We study the case where the Broyden method is used to solve these nonlinear problems. In that case, Broyden’s update of the Jacobian matrix may also be propagated from one time step to another. The parallelization through the time steps is also applied to the problem of finding a consistent initial guess for differential-algebraic equations

Resumo: Nesse trabalho propõe-se uma adaptação do método barreira penalidade quasi-Newton apresentado por P. Armand em 2003, para a resolução do problema do Fluxo de Potência Ótimo (FPO). Este método é denominado de método da função langrangiana barreira penalidade adaptada. Neste método as restrições de desigualdade são transformadas em igualdade pelo uso de variáveis de folga positivas. Estas variáveis são relaxadas, utilizando-se variáveis positivas, as quais, são incorporadas na função objetivo através de um termo de penalização. O novo problema restrito é então transformado em irrestrito associando a uma função lagrangiana às restrições de igualdade e uma função barreira penalidade às restrições de desigualdade. o algoritmo é composto por um ciclo interno e um externo. No ciclo interno é utilizado um método quasi-Newton para o cálculo das direções de busca e é determinado o tamanho do passo. No ciclo externo os parâmetros de barreira e penalidade são atualizados através de regras pré-definidas até que as condições de KKT sejam satisfeitas. Testes computacionais foram realizados utilizando problemas matemáticos e o problema de FPO, os quais demonstram a eficiência da adaptação proposta / Abstract: This work proposes an adaptation of the quasi-Newton penalty barrier method presented by P. Armand in 2003. for the solution of the Optimal Power Flow (OPD) problem. This method is called method adapted penalty barrier lagrangian function. In this method the inequalities constraint are transformed in equality by adding non-negative slack variable. These variables are relaxed by positive auxiliary variables which are incorporated in the objective function through a penalty term. The new constraint problem is transformed in unconstraint by associating an lagrangian function for handling the equality constraint and an penalty barrier function for treating the inequality constraints. The algorithm is composed by an internal and external cycle. In the interanal cycle is used the quasi-Newton method to determine the search directions and the step size is calculated. In the external cycle the barrier parameters are updated through predefined rules until the KKT conditions are satisfied. Computational tests were accomplished using mathematical problems and the OPF problem which demonstrate the efficiency of the propose adaptation / Orientador: Edméa Cássia Baptista / Coorientador: Vanusa Alves de Sousa / Banca: Geraldo Roberto Martins da Costa / Banca: Antonio Roberto Balbo / Mestre

<p>Posmatra se problem minimizacije bez ograničenja. U determinističkom&nbsp;slučaju ti problemi se uspe&scaron;no re&scaron;avaju iterativnim Kvazi Njutnovim postupcima.&nbsp;Ovde se istražuje &nbsp;stohastički slučaj, kada su poznate vrednosti funkcije cilja i njenog gradijenta na koje je uticao &scaron;um. Koristi se novi način određivanja dužina koraka, koji kombinuje metod linijskog pretraživanja i metod stohastičke aproksimacije tako da zadrži dobre osobine oba pristupa i obezbedi veću efikasnost postupka. Metod je testiran u kombinaciji sa vi&scaron;e načina izbora pravca u iterativnom postupku. Dokazana je konvergencija novog postupka i testiranjem na velikom broju standardnih test problema pokazana njegova efikasnost. Takođe se za re&scaron;avanje problema ekvilibriuma u Neoklasičnoj ekonomiji predlaže i dokazuje konvergencija jednog Fiksnog Njutnovog postupka. U zadatku nalaženja re&scaron;enja za niz problema kojima se preciznije modelira slučajni sistem, ovaj Fiksni Njutnov postupak ostvaruje veliku u&scaron;tedu CPU vremena u odnosu na Njutnov metod. U prvom delu teze je dat op&scaron;ti teoretski uvod. U drugom delu je dat pregled relevantnih rezultata iz posmatranih oblasti zajedno sa dva originalna rezultata. U trećem &nbsp;delu su dati rezultati numeričkih testova.</p> / <p>The problem under consideration is unconstrained minimization pro-blem. The problem in deterministic case is often solved with Quasi Newton met-hods. In noisy environment, which is considered, new approach for step length along descent direction is used. The new approach combines line search and stoc-hastic&nbsp; approximation method using good characteristics of both enabling better efficiency. The convergence is proved. New step length is tested with three de-scent directions. Many standard test problems show the efficiency of the met-hod. Also, a new, affordable procedure based on application of the fixed Newton method for a sequence of equilibrium problems generated by simulation is intro-duced. The convergence conditions of the method are derived. The numerical results show a clear difference in the quality of information obtained by solving a sequence of problems if compared with the single equilibrium problem. In the first part general theoretical introduction is given. In the second part a survey of results from scientific community is given together with original results. The third part contains many numerical tests of new methods that show its efficiency.</p>

Nous développons des modèles probabilistes pour l’impression à l’échelle micrométrique. Tenant compte de l’aléa de la forme des points qui composent les impressions, les modèles proposés pourront être ultérieurement exploités dans différentes applications dont l’authentification de documents imprimés. Une analyse de l’impression sur différents supports papier et par différentes imprimantes a été effectuée. Cette étude montre que la grande variété de forme dépend de la technologie et du papier. Le modèle proposé tient compte à la fois de la distribution du niveau de gris et de la répartition spatiale de l’encre sur le papier. Concernant le niveau de gris, les modèles des surfaces encrées/vierges sont obtenues en sélectionnant les distributions dans un ensemble de lois de forme similaire aux histogrammes et à l’aide de K-S critère. Le modèle de répartition spatiale de l’encre est binaire. Le premier modèle consiste en un champ de variables indépendantes de Bernoulli non-stationnaire dont les paramètres forment un noyau gaussien généralisé. Un second modèle de répartition spatiale des particules d’encre est proposé, il tient compte de la dépendance des pixels à l’aide d’un modèle de Markov non stationnaire. Deux méthodes d’estimation ont été développées, l’une approchant le maximum de vraisemblance par un algorithme de Quasi Newton, la seconde approchant le critère de l’erreur quadratique moyenne minimale par l’algorithme de Metropolis within Gibbs. Les performances des estimateurs sont évaluées et comparées sur des images simulées. La précision des modélisations est analysée sur des jeux d’images d’impression à l’échelle micrométrique obtenues par différentes imprimantes. / We develop the probabilistic models of the print at the microscopic scale. We study the shape randomness of the dots that originates the prints, and the new models could improve many applications such as the authentication. An analysis was conducted on various papers, printers. The study shows a large variety of shape that depends on the printing technology and paper. The digital scan of the microscopic print is modeled in: the gray scale distribution, and the spatial binary process modeling the printed/blank spatial distribution. We seek the best parametric distribution that takes account of the distributions of the blank and printed areas. Parametric distributions are selected from a set of distributions with shapes close to the histograms and with the Kolmogorov-Smirnov divergence. The spatial binary model handles the wide diversity of dot shape and the range of variation of spatial density of inked particles. At first, we propose a field of independent and non-stationary Bernoulli variables whose parameters form a Gaussian power. The second spatial binary model encompasses, in addition to the first model, the spatial dependence of the inked area through an inhomogeneous Markov model. Two iterative estimation methods are developed; a quasi-Newton algorithm which approaches the maximum likelihood and the Metropolis-Hasting within Gibbs algorithm that approximates the minimum mean square error estimator. The performances of the algorithms are evaluated and compared on simulated images. The accuracy of the models is analyzed on the microscopic scale printings coming from various printers. Results show the good behavior of the estimators and the consistency of the models.

Notre contribution concerne les trois domaines complémentaires suivants: la différentiation automatique de programmes, l'optimisation de formes pour de grands systèmes, l'adaptation de maillages. Dans le chapitre 1 de la partie 1, nous exposons une méthode de calcul de gradients par Différentiation Automatique pour un problème classique d'optimisation de formes. Nous expliquons comment déduire un gradient exact basé sur un état adjoint sans stocker explicitement le jacobien. Le mode adjoint de la DA que nous proposons utilise beaucoup moins d'espace mémoire. Dans le chapitre 2 de la partie 2, nous proposons une méthode de type SQP pour résoudre une classe de problèmes d'optimisation avec contraintes égalités. Le nouvel algorithme permet une résolution simultanée du système d'optimalité. Cette méthode one shot combine efficacité et robustesse. Dans le chapitre 3 de la partie 2, nous étudions une nouvelle stratégie de préconditionnement pour l'optimisation de formes. Nous construisons un préconditionnement multiniveau additif à partir du principe classique de Bramble-Pasciak-Xu et du principe d'agglomération. Nous spécifions aisément le gain en régularité de notre préconditionneur avec un seul paramètre réel. Dans le chapitre 1 de la partie 3, nous étudions le problème du meilleur maillage adapté pour de l'interpolation pure. La résolution du système d'optimalité donne une expression complètement explicite de la métrique optimale en fonction de la fonction à adapter. Dans le chapitre 2 de la partie 3, nous étendons la méthode du chapitre précédent au problème de l'adaptation de maillage pour EDP. Notre méthode repose sur une analyse a priori rigoureuse puis sur une modélisation.