In this work we present a new tool for the convergence analysis of numerical optimization methods. It is based on the concepts of the Clarke derivative and set-valued mappings. Our goal is to apply this tool to minimization problems with non-smooth and noisy objective functions. After deriving a necessary condition for minimizers of such functions, we examine two unconstrained optimization routines. First, we prove new convergence theorems for Implicit Filtering and General Pattern Search. Then we show how these results can be used in practice, by executing some numerical computations. / Master of Science

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.

Cette thèse est dédiée à l'étude de la hiérarchie moments-sommes-de-carrés, une famille de problèmes de programmation semi-définie en optimisation polynomiale, couramment appelée hiérarchie de Lasserre. Nous examinons différents aspects de ses propriétés et applications. Comme application de la hiérarchie, nous approchons certains objets potentiellement compliqués, comme l'abscisse polynomiale et les plans d'expérience optimaux sur des domaines semi-algébriques. L'application de la hiérarchie de Lasserre produit des approximations par des polynômes de degré fixé et donc de complexité bornée. En ce qui concerne la complexité de la hiérarchie elle-même, nous en construisons une modification pour laquelle un taux de convergence amélioré peut être prouvé. Un concept essentiel de la hiérarchie est l'utilisation des modules quadratiques et de leurs duaux pour appréhender de manière flexible le cône des polynômes positifs et le cône des moments. Nous poursuivons cette idée pour construire des approximations étroites d'ensembles semi-algébriques à l'aide de séparateurs polynomiaux. / This thesis is dedicated to investigations of the moment-sums-of-squares hierarchy, a family of semidefinite programming problems in polynomial optimization, commonly called the Lasserre hierarchy. We examine different aspects of its properties and purposes. As applications of the hierarchy, we approximate some potentially complicated objects, namely the polynomial abscissa and optimal designs on semialgebraic domains. Applying the Lasserre hierarchy results in approximations by polynomials of fixed degree and hence bounded complexity. With regard to the complexity of the hierarchy itself, we construct a modification of it for which an improved convergence rate can be proved. An essential concept of the hierarchy is to use quadratic modules and their duals as a tractable characterization of the cone of positive polynomials and the moment cone, respectively. We exploit further this idea to construct tight approximations of semialgebraic sets with polynomial separators.

Cette thèse développe une méthode de faisceau non convexe pour la minimisation de fonctions localement lipschitziennes lower C1 puis l’applique à des problèmes de synthèse de lois de commande structurées issus de l’industrie aéronautique. Ici loi de commande structurée fait référence à une architecture de contrôle, qui se compose d’éléments comme les PIDs, combinés avec des filtres variés, et comprenant beaucoup moins de paramètres de réglage qu’un contrôleur d’ordre plein. Ce type de problème peut se formuler dans le cadre théorique et général de la programmation non convexe et non lisse. Parmi les techniques numériques efficaces pour résoudre ces problèmes non lisses, nous avons dans ce travail, opté pour les méthodes de faisceau, convenablement étendues au cas non convexe. Celles-ci utilisent un oracle qui, en chaque itéré x, retourne la valeur de la fonction et un sous-gradient de Clarke arbitraire. Afin de générer un pas de descente satisfaisant à partir de l’itéré sérieux courant, ces techniques stockent et accumulent de l’information, dans ce que l’on appelle le faisceau, obtenu à partir d’évaluations successives de l’oracle à chaque pas d’essai insatisfaisant. Dans cette thèse, on propose de construire le faisceau en décalant vers le bas une tangente de l’objectif en un pas d’essai ne constituant pas un pas de descente satisfaisant. Le décalage est indispensable dans le cas non convexe pour préserver la consistance, on dit encore l’exactitude, du modèle vis à vis de l’objectif. L’algorithme développé est validé sur un problème de synthèse conjointe du pilote automatique et de la loi des commandes de vol d’un avion civil en un point de vol donné et sur un problème de synthèse de loi de commande par séquencement de gain pour le contrôle longitudinal dans une enveloppe de vol. / This thesis develops a non convex bundle method for the minimization of lower C1 locally Lipschitz functions which it then applies to the synthesis of structured control laws for problems arising in aerospace control. Here a structured control law refers to a control architecture preferred by practitioners, which consist of elements like PIDs, combined with various filters, featuring significantly less tunable parameters than a full-order controller. This type of problem can be formulated under the theoretical and general framework of non convex and non smooth programming. Among the efficient numerical techniques to solve such non smooth problems, we have in this work opted for bundle methods, suitably extended to address non-convex optimization programs. Bundle methods use oracles which at every iterate x return the function value and one unspecified Clarke subgradient. In order to generate descent steps away from a current serious iterate, these techniques hinge on storing and accumulating information, called the bundle, obtained from successive evaluations of the oracle along the unsuccessful trial steps. In this thesis, we propose to build the bundle by shifting down a tangent of the objective at a trial step which is not a satisfactory descent step. The shift is essential in the non convex case in order to preserve the consistency, named also the exactitude, of the model with regard to the objective. The developed algorithm is validated on a synthesis problem combining the automatic pilot and the flight control law of a civil aircraft at a given flying point ; and a gain scheduled control law synthesis for the longitudinal control in a flight envelope.

[pt] Algoritmos para a resolução de problemas de programação mista 0-1 gerais baseados em cortes derivados dos métodos lift-and-project, tem se mostrado bastante eficientes na prática. Estes cortes são gerados resolvendo um problema que depende de uma certa normalização. Desde um ponto de vista teórico, o bom comportamento destes algoritmos não foi completamente compreendido, especialmente no que diz respeito à normalização. Neste trabalho consideramos normalizações gerais definidas por um conjunto convexo fechado arbitrário, estendendo assim a análise teórica desenvolvida nos anos noventa. Apresentamos um marco teórico que abarca todas as normalizações previamente estudadas e introduzimos novas normalizações, analisando as propriedades dos cortes associados.Introduzimos também uma nova fórmula de atualização do parâmetro proximal para uma variante dos métodos de feixes. Estes métodos são bem conhecidos pela sua eficiência na resolução de problemas de otimização não diferenciável. Por último, propomos uma metodologia para eliminr soluções redundantes de programas inteiros combinatórios. Nossa proposta baseia-se na utilização da informação de simetria do problema, eliminam a simetria sem prejudicar a solução do problema inteiro. / [en] Algorithms for general 0-1 mixed integer programs can be successfully developed by using lift-and-project methods to generate cuts. Cuts are generated by solving a cut- generation-program that depends on a certain normalization. From a theoretical point of view, the good numerical behavior of these cuts is not completely understood yet, specially, concerning to the normalization chosen. We consider a general normalization given by an arbitrary closed convex set, extending the theory developed in the 90's. We present a theoretical framework covering a wide group of already known normalizations. We also introduce new normalizations and analyze the properties of the associated cuts. In this work, we also propose a new updating rule for the prox parameter of a variant of the proximal bundle methods, making use of all the information available at each iteration. Proximal bundle methods are well known for their efficiency in nondifferentiable optimization. Finally, we introduce a way to eliminate redundant solutions ( due to geometrical symmetries ) of combinatorial integer program. This can be done by using the information about the problem symmetry in order to generate inequalities, which added to the formulation of the problem, eliminate this symmetry without affecting solution of the integer problem. / [es] Los algoritmos para la resolución de problemas de programación mixta 0-1 generales que utilizan cortes derivados de los métodos lift-and-project, se han mostrado bastante eficientes en la práctica. Estos cortes se generan resolviendo un problema que depende de una cierta normalización. Desde el punto de vista teórico, el buen comportamiento de estos algoritmos no fue completamente comprendido, especialmente respecto a la normalización. En este trabajo consideramos normalizaciones generales definidas por un conjunto convexo cerrado arbitrario, extendiendo así el análisis teórico desarrollado en los años noventa. Presentamos un marco teórico que abarca todas las normalizaciones previamente estudiadas e introducimos nuevas normalizaciones, analizando las propiedades de los cortes asociados. Introducimos una nueva fórmula de actualización del parámetro de. Estoss métodos son bien conocidos por su eficiencia en la resolución de problemas de optimización no diferenciable. Por último, proponemos una metodología para eliminar soluciones redundantes de programas enteros combinatorios. Nuestra propuesta se basa en la utilización de la información de simetría del problema, eliminan la simetría sin perjudicar la solución del problema entero.

Nichtglatte Optimierungsprobleme in reflexiven Banachräumen treten in vielen Anwendungen auf. Häufig wird angenommen, dass alle vorkommenden Nichtdifferenzierbarkeiten durch Lipschitz-stetige Operatoren wie abs, min und max gegeben sind. Bei solchen Problemen kann es sich zum Beispiel um optimale Steuerungsprobleme mit möglicherweise nicht glatten Zielfunktionen handeln, welche durch partielle Differentialgleichungen (PDG) eingeschränkt sind, die ebenfalls nicht glatte Terme enthalten können. Eine effiziente und robuste Lösung erfordert eine Kombination numerischer Simulationen und spezifischer Optimierungsalgorithmen. Lokal Lipschitz-stetige, nichtglatte Nemytzkii-Operatoren, welche direkt in der Problemformulierung auftreten, spielen eine wesentliche Rolle in der Untersuchung der zugrundeliegenden Optimierungsprobleme. In dieser Dissertation werden zwei spezifische Methoden und Algorithmen zur Lösung solcher nichtglatter Optimierungsprobleme in reflexiven Banachräumen vorgestellt und diskutiert. Als erste Lösungsmethode wird in dieser Dissertation die Minimierung von nichtglatten Operatoren in reflexiven Banachräumen mittels sukzessiver quadratischer Überschätzung vorgestellt, SALMIN. Ein neuartiger Optimierungsansatz für Optimierungsprobleme mit nichtglatten elliptischen PDG-Beschränkungen, welcher auf expliziter Strukturausnutzung beruht, stellt die zweite Lösungsmethode dar, SCALi. Das zentrale Merkmal dieser Methoden ist ein geeigneter Umgang mit Nichtglattheiten. Besonderes Augenmerk liegt dabei auf der zugrundeliegenden nichtglatten Struktur des Problems und der effektiven Ausnutzung dieser, um das Optimierungsproblem auf angemessene und effiziente Weise zu lösen. / Non-smooth optimization problems in reflexive Banach spaces arise in many applications. Frequently, all non-differentiabilities involved are assumed to be given by Lipschitz-continuous operators such as abs, min and max. For example, such problems can refer to optimal control problems with possibly non-smooth objective functionals constrained by partial differential equations (PDEs) which can also include non-smooth terms. Their efficient as well as robust solution requires numerical simulations combined with specific optimization algorithms. Locally Lipschitz-continuous non-smooth non-linearities described by appropriate Nemytzkii operators which arise directly in the problem formulation play an essential role in the study of the underlying optimization problems. In this dissertation, two specific solution methods and algorithms to solve such non-smooth optimization problems in reflexive Banach spaces are proposed and discussed. The minimization of non-smooth operators in reflexive Banach spaces by means of successive quadratic overestimation is presented as the first solution method, SALMIN. A novel structure exploiting optimization approach for optimization problems with non-smooth elliptic PDE constraints constitutes the second solution method, SCALi. The central feature of these methods is the appropriate handling of non-differentiabilities. Special focus lies on the underlying structure of the problem stemming from the non-smoothness and how it can be effectively exploited to solve the optimization problem in an appropriate and efficient way.