The diploma thesis deals with vehicle movement dynamics and defining a theoretical model for software simulation of vehicle passing a given trajectory, while main aim is time minimization driving mode. Simulation (algorithm for computing speed profile) is then applicated for passing experimental vehicle along Masaryk circuit in Brno. At the end, we optimize chosen vehicle parameters with derivate-free algorithms Multilevel Coordinate Search and Particle Swarm.

In this thesis, we have considered two important problems, Boolean satisfiability (SAT) and derivative free optimization in the context of large scale quantum computers. In the first part, we survey well known classical techniques for solving satisfiability. We compute the approximate time it would take to solve SAT instances using quantum techniques and compare it with state-of-the heart classical heuristics employed annually in SAT competitions. In the second part of the thesis, we consider a few classically well known algorithms for derivative free optimization which are ubiquitously employed in engineering problems. We propose a quantum speedup to this classical algorithm by using techniques of the quantum minimum finding algorithm. In the third part of the thesis, we consider practical applications in the fields of bio-informatics, petroleum refineries and civil engineering which involve solving either satisfiability or derivative free optimization. We investigate if using known quantum techniques to speedup these algorithms directly translate to the benefit of industries which invest in technology to solve these problems. In the last section, we propose a few open problems which we feel are immediate hurdles, either from an algorithmic or architecture perspective to getting a convincing speedup for the practical problems considered.

Emulation of computer experiments via surrogate models can be difficult when the number of input parameters determining the simulation grows any greater than a few dozen. In this dissertation, we explore dimension reduction in the context of computer experiments. The active subspace method is a linear dimension reduction technique which uses the gradients of a function to determine important input directions. Unfortunately, we cannot expect to always have access to the gradients of our black-box functions. We thus begin by developing an estimator for the active subspace of a function using kernel methods to indirectly estimate the gradient. We then demonstrate how to deploy the learned input directions to improve the predictive performance of local regression models by ``undoing" the active subspace. Finally, we develop notions of sensitivities which are local to certain parts of the input space, which we then use to develop a Bayesian optimization algorithm which can exploit locally important directions. / Doctor of Philosophy / Increasingly, scientists and engineers developing new understanding or products rely on computers to simulate complex phenomena. Sometimes, these computer programs are so detailed that the amount of time they take to run becomes a serious issue. Surrogate modeling is the problem of trying to predict a computer experiment's result without having to actually run it, on the basis of having observed the behavior of similar simulations. Typically, computer experiments have different settings which induce different behavior. When there are many different settings to tweak, typical surrogate modeling approaches can struggle. In this dissertation, we develop a technique for deciding which input settings, or even which combinations of input settings, we should focus our attention on when trying to predict the output of the computer experiment. We then deploy this technique both to prediction of computer experiment outputs as well as to trying to find which of the input settings yields a particular desired result.

Derivative free optimization algorithms are implementations of trust region based derivative-free methods using multivariate polynomial interpolation. These are designed to minimize smooth functions whose derivatives are not available or costly to compute. The trust region based multilevel optimization algorithms for solving large scale unconstrained optimization problems resulting by discretization of partial differential equations (PDEs), make use of different discretization levels to reduce the computational cost. In this thesis, a derivative free multilevel optimization algorithm is derived and its convergence behavior is analyzed. The effectiveness of the algorithms is demonstrated on a shape optimization problem.

Dans cette thèse, on s’intéresse à un problème inverse classique en ingénierie pétrolière, àsavoir le calage d’historique. Plus précisément, une nouvelle méthode de paramétrisation géostatistiqueainsi qu’un nouvel algorithme d’optimisation sans dérivées adaptés aux particularitésdu problème sont présentés ici. La nouvelle méthode de paramétrisation repose sur les principes des méthodes de déformation graduelle et de déformation de domaines. Comme la déformation graduelle locale, elle consiste àcombiner à l’intérieur de zones préalablement définies deux réalisations ou plus de modèle avec lapossibilité supplémentaire de modifier dynamiquement la forme des zones choisies. La flexibilitéapportée par cette méthode dans le choix des zones a ainsi permis de garantir l’obtention d’unbon point initial pour l’optimisation. Concernant l’optimisation, l’hypothèse que les paramètres locaux dans le modèle de réservoir n’influent que faiblement sur les données de puits distants conduit à considérer que la fonction àoptimiser est à variables partiellement séparables. La nouvelle méthode d’optimisation développée,nommée DFO-PSOF, de type région de confiance avec modèle quadratique d’interpolation,exploite alors au maximum cette propriété de séparabilité partielle. Les résultats numériquesobtenus sur plusieurs cas de réservoir valident à la fois l’hypothèse effectuée ainsi que la qualitéde l’algorithme pour le problème de calage d’historique. En complément de cette validation numérique,un résultat théorique de convergence vers un point critique est prouvé pour la méthoded’optimisation construite / We worked in this thesis on a classical inverse problem in the petroleum industry, historymatching. We proposed a new geostatistical parameterization technique as well as a new derivativefree optimization algorithm adapted to the problem specificities. The parameterization method is based on two approaches found in the literature, the local gradual deformation method and the domain deformation method. Similarly to the local gradual deformation method, our method combines two or more model realizations inside previouslydefined zones. Moreover, our method adds the possibility to dynamically update the shape ofthe zones during the optimization process. This property substantially improves its robustnesswith regard to the initial choice of the zones. Thus, the greater flexibility brought by our methodallowed us to develop an initialization methodology which garantees a good initial point for theoptimization. To reduce the number of evaluations needed to minimize the objective function, we madethe assumption that a local parameter does not influence the production data of a distantwell. With this hypothesis, the objective function is then considered partially separable. Theoptimization algorithm we developped, called DFO-PSOF, is a trust region algorithm basedon quadratic interpolation models which exploits this partial separability property. Numericalresults obtained on some reservoir test cases validate both the hypothesis and the quality of ouralgorithm for the history matching problem. Moreover, a theoretical convergence result towardsa first order critical point, is proved for this new optimization method

L’optimisation sans dérivées (OSD) a connu un regain d’intérêt ces dernières années, principalement motivée par le besoin croissant de résoudre les problèmes d’optimisation définis par des fonctions dont les valeurs sont calculées par simulation (par exemple, la conception technique, la restauration d’images médicales ou de nappes phréatiques).Ces dernières années, un certain nombre de méthodes d’optimisation sans dérivée ont été développées et en particulier des méthodes fondées sur un modèle de région de confiance se sont avérées obtenir de bons résultats.Dans cette thèse, nous présentons un nouvel algorithme de région de confiance, basé sur l’interpolation, qui se montre efficace et globalement convergent (en ce sens que sa convergence vers un point stationnaire est garantie depuis tout point de départ arbitraire). Le nouvel algorithme repose sur la technique d’auto-correction de la géométrie proposé par Scheinberg and Toint (2010). Dans leur théorie, ils ont fait avancer la compréhension du rôle de la géométrie dans les méthodes d’OSD à base de modèles. Dans notre travail, nous avons pu améliorer considérablement l’efficacité de leur méthode, tout en maintenant ses bonnes propriétés de convergence. De plus, nous examinons l’influence de différents types de modèles d’interpolation sur les performances du nouvel algorithme.Nous avons en outre étendu cette méthode pour prendre en compte les contraintes de borne par l’application d’une stratégie d’activation. Considérer une méthode avec ensemble actif pour l’optimisation basée sur des modèles d’interpolation donne la possibilité d’économiser une quantité importante d’évaluations de fonctions. Il permet de maintenir les ensembles d’interpolation plus petits tout en poursuivant l’optimisation dans des sous-espaces de dimension inférieure. L’algorithme résultant montre un comportement numérique très compétitif. Nous présentons des résultats sur un ensemble de problèmes-tests issu de la collection CUTEr et comparons notre méthode à des algorithmes de référence appartenant à différentes classes de méthodes d’OSD.Pour réaliser des expériences numériques qui intègrent le bruit, nous créons un ensemble de cas-tests bruités en ajoutant des perturbations à l’ensemble des problèmes sans bruit. Le choix des problèmes bruités a été guidé par le désir d’imiter les problèmes d’optimisation basés sur la simulation. Enfin, nous présentons des résultats sur une application réelle d’un problème de conception de forme d’une aile fourni par Airbus. / Derivative-free optimization (DFO) has enjoyed renewed interest over the past years, mostly motivated by the ever growing need to solve optimization problems defined by functions whose values are computed by simulation (e.g. engineering design, medical image restoration or groundwater supply).In the last few years, a number of derivative-free optimization methods have been developed and especially model-based trust-region methods have been shown to perform well.In this thesis, we present a new interpolation-based trust-region algorithm which shows to be efficient and globally convergent (in the sense that its convergence is guaranteed to a stationary point from arbitrary starting points). The new algorithm relies on the technique of self-correcting geometry proposed by Scheinberg and Toint [128] in 2009. In their theory, they advanced the understanding of the role of geometry in model-based DFO methods, in our work, we improve the efficiency of their method while maintaining its good theoretical convergence properties. We further examine the influence of different types of interpolation models on the performance of the new algorithm.Furthermore, we extended this method to handle bound constraints by applying an active-set strategy. Considering an active-set method in bound-constrained model-based optimization creates the opportunity of saving a substantial amount of function evaluations. It allows to maintain smaller interpolation sets while proceeding optimization in lower dimensional subspaces. The resulting algorithm is shown to be numerically highly competitive. We present results on a test set of smooth problems from the CUTEr collection and compare to well-known state-of-the-art packages from different classes of DFO methods.To report numerical experiments incorporating noise, we create a test set of noisy problems by adding perturbations to the set of smooth problems. The choice of noisy problems was guided by a desire to mimic simulation-based optimization problems. Finally, we will present results on a real-life application of a wing-shape design problem provided by Airbus.

Optimization theory is a key technology for inverse problems of reconstruction in science, engineering and economy. Discrete tomography is a modern research field dealing with the reconstruction of finite objects in, e.g., VLSI chip design, where this thesis will focus on. In this work, a framework with its supplementary algorithms and a new problem reformulation are introduced to approximately resolve this NP-hard problem. The framework is modular, so that other reconstruction methods, optimization techniques, optimal experimental design methods can be incorporated within. The problem is being revisited with a new optimization formulation, and interpretations of known methods in accordance with the framework are also given. Supplementary algorithms are combined or incorporated to improve the solution or to reduce the cost in terms of time and space from the computational point of view.

L'utilisation d'aspects aléatoires a contribué de façon majeure aux dernières avancées dans le domaine de l'optimisation numérique; cela est dû en partie à la recrudescence de problèmes issus de l'apprentissage automatique (machine learning). Dans un tel contexte, les algorithmes classiques d'optimisation non linéaire, reposant sur des principes déterministes, se révèlent en effet bien moins performants que des variantes incorporant de l'aléatoire. Le coût de ces dernières est souvent inférieur à celui de leurs équivalents déterministes; en revanche, il peut s'avérer difficile de maintenir les propriétés théoriques d'un algorithme déterministe lorsque de l'aléatoire y est introduit. Effectuer une analyse de complexité d'une telle méthode est un procédé très répandu dans ce contexte. Cette technique permet déstimer la vitesse de convergence du schéma considéré et par là même d'établir une forme de convergence de celui-ci. Les récents travaux sur ce sujet, en particulier pour des problèmes d'optimisation non convexes, ont également contribué au développement de ces aspects dans le cadre déterministe, ceux-ci apportant en effet un éclairage nouveau sur le comportement des algorithmes. Dans cette thèse, on s'intéresse à l'amélioration pratique d'algorithmes d'optimisation sans dérivées à travers l'introduction d'aléatoire, ainsi qu'à l'impact numérique des analyses de complexité. L'étude se concentre essentiellement sur les méthodes de recherche directe, qui comptent parmi les principales catégories d'algorithmes sans dérivées; cependant, l'analyse sous-jacente est applicable à un large éventail de ces classes de méthodes. On propose des variantes probabilistes des propriétés requises pour assurer la convergence des algorithmes étudiés, en mettant en avant le gain en efficacité induit par ces variantes: un tel gain séxplique principalement par leur coût très faible en évaluations de fonction. Le cadre de base de notre analyse est celui de méthodes convergentes au premier ordre, que nous appliquons à des problèmes sans ou avec contraintes linéaires. Les bonnes performances obtenues dans ce contexte nous incitent par la suite à prendre en compte des aspects d'ordre deux. A partir des propriétés de complexité des algorithmes sans dérivées, on développe de nouvelles méthodes qui exploitent de l'information du second ordre. L'analyse de ces procédures peut être réalisée sur un plan déterministe ou probabiliste: la deuxième solution nous permet d'étudier de nouveaux aspects aléatoires ainsi que leurs conséquences sur l'éfficacité et la robustesse des algorithmes considérés. / Randomization has had a major impact on the latest developments in the field of numerical optimization, partly due to the outbreak of machine learning applications. In this increasingly popular context, classical nonlinear programming algorithms have indeed been outperformed by variants relying on randomness. The cost of these variants is usually lower than for the traditional schemes, however theoretical guarantees may not be straightforward to carry out from the deterministic to the randomized setting. Complexity analysis is a useful tool in the latter case, as it helps in providing estimates on the convergence speed of a given scheme, which implies some form of convergence. Such a technique has also gained attention from the deterministic optimization community thanks to recent findings in the nonconvex case, as it brings supplementary indicators on the behavior of an algorithm. In this thesis, we investigate the practical enhancement of deterministic optimization algorithms through the introduction of random elements within those frameworks, as well as the numerical impact of their complexity results. We focus on direct-search methods, one of the main classes of derivative-free algorithms, yet our analysis applies to a wide range of derivative-free methods. We propose probabilistic variants on classical properties required to ensure convergence of the studied methods, then enlighten their practical efficiency induced by their lower consumption of function evaluations. Firstorder concerns form the basis of our analysis, which we apply to address unconstrained and linearly-constrained problems. The observed gains incite us to additionally take second-order considerations into account. Using complexity properties of derivative-free schemes, we develop several frameworks in which information of order two is exploited. Both a deterministic and a probabilistic analysis can be performed on these schemes. The latter is an opportunity to introduce supplementary probabilistic properties, together with their impact on numerical efficiency and robustness.

No description available.

Recent developments show that derivative free methods are highly demanded by researches for solving optimization problems in various practical contexts. Although well-known optimization methods that employ derivative information can be very effcient, a derivative free method will be more effcient in cases where the objective function is nondifferentiable, the derivative information is not available or is not reliable. Derivative Free Optimization (DFO) is developed for solving small dimensional problems (less than 100 variables) in which the computation of an objective function is relatively expensive and the derivatives of the objective function are not available. Problems of this nature more and more arise in modern physical, chemical and econometric measurements and in engineering applications, where computer simulation is employed for the evaluation of the objective functions. In this thesis, we give an example of the implementation of DFO in an approach for optimizing stirrer configurations, including a parametrized grid generator, a flow solver, and DFO. A derivative free method, i.e., DFO is preferred because the gradient of the objective function with respect to the stirrer&rsquo / s design variables is not directly available. This nonlinear objective function is obtained from the flow field by the flow solver. We present and interpret numerical results of this implementation. Moreover, a contribution is given to a survey and a distinction of DFO research directions, to an analysis and discussion of these. We also state a derivative free algorithm used within a clustering algorithm in combination with non-smooth optimization techniques to reveal the effectiveness of derivative free methods in computations. This algorithm is applied on some data sets from various sources of public life and medicine. We compare various methods, their practical backgrounds, and conclude with a summary and outlook. This work may serve as a preparation of possible future research.