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.

Kernel methods are a popular choice in solving a number of problems in statistical machine learning. In this thesis, we propose new methods for two important kernel based classification problems: 1) learning from highly unbalanced large-scale datasets and 2) selecting a relevant subset of input features for a given kernel specification. The first problem is known as the rare class problem, which is characterized by a highly skewed or unbalanced class distribution. Unbalanced datasets can introduce significant bias in standard classification methods. In addition, due to the increase of data in recent years, large datasets with millions of observations have become commonplace. We propose an approach to address both the problem of bias and computational complexity in rare class problems by optimizing area under the receiver operating characteristic curve and by using a rare class only kernel representation, respectively. We justify the proposed approach theoretically and computationally. Theoretically, we establish an upper bound on the difference between selecting a hypothesis from a reproducing kernel Hilbert space and a hypothesis space which can be represented using a subset of kernel functions. This bound shows that for a fixed number of kernel functions, it is optimal to first include functions corresponding to rare class samples. We also discuss the connection of a subset kernel representation with the Nystrom method for a general class of regularized loss minimization methods. Computationally, we illustrate that the rare class representation produces statistically equivalent test error results on highly unbalanced datasets compared to using the full kernel representation, but with significantly better time and space complexity. Finally, we extend the method to rare class ordinal ranking, and apply it to a recent public competition problem in health informatics. The second problem studied in the thesis is known as the feature selection problem in literature. Embedding feature selection in kernel classification leads to a non-convex optimization problem. We specify a primal formulation and solve the problem using a second-order trust region algorithm. To improve efficiency, we use the two-block Gauss-Seidel method, breaking the problem into a convex support vector machine subproblem and a non-convex feature selection subproblem. We reduce possibility of saddle point convergence and improve solution quality by sharing an explicit functional margin variable between block iterates. We illustrate how our algorithm improves upon state-of-the-art methods.

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.

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.

In recent years, mobile robots have gained tremendous attention from the entire society: the industry is aiming at selling more intelligent products while the academia is improving their performance from all perspectives. Real world examples include autnomous driving vehicles, multirotors, legged robots, etc. One of the challenging tasks commonly faced by all game players, and all robotics platforms, is to plan motion or locomotion of the robot, calculate an optimal trajectory according to certain criterion and control it accordingly. Difficulty of solving such task usually arises from high-dimensionality and complexity of the system dynamics, fast changing conditions imposed as constraints and necessity for real-time deployment. This work proposes a method over the aforementioned mission by solving an optimal control problem in a receding horizon fashion. Unlike the existing Sequential Linear Quadratic [1] algorithm which is a continuous-time variant of Differential Dynamic Programming [2], we tackle the problem in a discretized multiple shooting fashion. Sequential Quadratic Programming is employed as optimization technique to solve the constrained Nonlinear Programming iteratively. Moreover, we apply trust region method in the sub Quadratic Programming to handle potential indefiniteness of Hessian matrix as well as to improve robustness of the solver. Simulation and benchmark with previous method have been conducted on robotics platforms to show the effectiveness of our solution and superiority under certain circumstances. Experiments have demonstrated that our method is capable of generating trajectories under complicated scenarios where the Hessian matrix contains negative eigenvalues (e.g. obstacle avoidance). / De senaste åren har mobila robotar fått enorm uppmärksamhet från hela samhället: branschen siktar på att sälja mer intelligenta produkter samtidigt som akademin förbättrar sina prestationer ur alla perspektiv. Exempel på verkligheten inkluderar autonoma körande fordon, multirotorer, robotar med ben, etc. En av de utmanande uppgifterna som vanligtvis alla spelare och alla robotplattformar står inför är att planera robotens rörelse eller rörelse, beräkna en optimal bana enligt vissa kriterier och kontrollera det därefter. Svårigheter att lösa en sådan uppgift beror vanligtvis på hög dimensionalitet och komplexitet hos systemdynamiken, snabbt föränderliga villkor som åläggs som begränsningar och nödvändighet för realtidsdistribution. Detta arbete föreslår en metod över det tidigare nämnda uppdraget genom att lösa ett optimalt kontrollproblem på ett vikande horisont. Till skillnad från den befintliga Sequential Linear Quadratic [1] algoritmen som är en kontinuerlig tidsvariant av Differential Dynamic Programming [2], tar vi oss an problemet på ett diskretiserat multipelfotograferingssätt. Sekventiell kvadratisk programmering används som optimeringsteknik för att lösa den begränsade olinjära programmeringen iterativt. Dessutom tillämpar vi trust region-metoden i den sub-kvadratiska programmeringen för att hantera potentiell obestämdhet av hessisk matris samt för att förbättra lösarens robusthet. Simulering och benchmark med tidigare metod har utförts på robotplattformar för att visa effektiviteten hos vår lösning och överlägsenhet under vissa omständigheter. Experiment har visat att vår metod är kapabel att generera banor under komplicerade scenarier där den hessiska matrisen innehåller negativa egenvärden (t.ex. undvikande av hinder).

Este trabalho apresenta uma nova abordagem para a modelagem e resolução de problemas de fluxo de carga em sistemas elétricos de potência. O modelo proposto é formado simultaneamente pelo conjunto de equações não lineares que representam as restrições de carga do problema e por restrições de complementaridade associadas com as restrições de operação da rede, as quais propiciam o controle implícito das tensões nas barras com controle de geração. Também é proposta uma técnica para a obtenção dos valores discretos dos taps de tranformadores, de maneira que o ajuste dessas variáveis possa ser realizado em passos discretos. A metodologia desenvolvida consiste em tratar o sistema misto de equações e inequações não lineares como um problema de factibilidade não linear e transformá-lo em um problema de mínimos quadrados não lineares, o qual é resolvido por uma sequência de subproblemas linearizados dentro de uma região de confiança. Para a obtenção de soluções aproximadas desse subproblema foi adotado o método do gradiente conjugado de Steihaug, combinando estratégias de região de confiança e filtros multidimensionais para analisar a qualidade das soluções fornecidas. Foram realizados testes numéricos com os sistemas de 14, 30, 57, 118 e 300 barras do IEEE, e com um sistema brasileiro equivalente CESP 53 barras, os quais indicaram boa flexibilidade e robustez do método proposto. / This work presents a new approach to the load flow problem in electrical power systems and develops a methodology for its resolution. The proposed model is simultaneously composed by nonlinear equations and inequations which represent the load and operational restrictions of the system, where a set of complementarity constraints model the relationship between voltage and reactive power generation in controled buses. It is also proposed a new technique to obtaining a discrete solution for the transformer taps, allowing their discrete adjustment. The method developed treats the mixed system of equations and inequations of the load flow problem as a nonlinear feasibility problem and converts it in a nonlinear least squares problem, which is solved by minimizing a sequence of linearized subproblems, whitin a trust region. To obtain approximate solutions at every iteration, we use the Steihaug conjugate gradient method, combining trust region and multidimensional filters techniques to analyse the quality of the provided solution. Numerical results using 14, 30, 57, 118 and 300-bus IEEE power systems, and a real brazilian equivalent system CESP 53-bus, indicate the flexibility and robustness of the proposed method.

Este trabalho apresenta uma nova abordagem para a modelagem e resolução de problemas de fluxo de carga em sistemas elétricos de potência. O modelo proposto é formado simultaneamente pelo conjunto de equações não lineares que representam as restrições de carga do problema e por restrições de complementaridade associadas com as restrições de operação da rede, as quais propiciam o controle implícito das tensões nas barras com controle de geração. Também é proposta uma técnica para a obtenção dos valores discretos dos taps de tranformadores, de maneira que o ajuste dessas variáveis possa ser realizado em passos discretos. A metodologia desenvolvida consiste em tratar o sistema misto de equações e inequações não lineares como um problema de factibilidade não linear e transformá-lo em um problema de mínimos quadrados não lineares, o qual é resolvido por uma sequência de subproblemas linearizados dentro de uma região de confiança. Para a obtenção de soluções aproximadas desse subproblema foi adotado o método do gradiente conjugado de Steihaug, combinando estratégias de região de confiança e filtros multidimensionais para analisar a qualidade das soluções fornecidas. Foram realizados testes numéricos com os sistemas de 14, 30, 57, 118 e 300 barras do IEEE, e com um sistema brasileiro equivalente CESP 53 barras, os quais indicaram boa flexibilidade e robustez do método proposto. / This work presents a new approach to the load flow problem in electrical power systems and develops a methodology for its resolution. The proposed model is simultaneously composed by nonlinear equations and inequations which represent the load and operational restrictions of the system, where a set of complementarity constraints model the relationship between voltage and reactive power generation in controled buses. It is also proposed a new technique to obtaining a discrete solution for the transformer taps, allowing their discrete adjustment. The method developed treats the mixed system of equations and inequations of the load flow problem as a nonlinear feasibility problem and converts it in a nonlinear least squares problem, which is solved by minimizing a sequence of linearized subproblems, whitin a trust region. To obtain approximate solutions at every iteration, we use the Steihaug conjugate gradient method, combining trust region and multidimensional filters techniques to analyse the quality of the provided solution. Numerical results using 14, 30, 57, 118 and 300-bus IEEE power systems, and a real brazilian equivalent system CESP 53-bus, indicate the flexibility and robustness of the proposed method.