Algorithmes pour l’optimisation sans dérivées avec variables mixtes

Derivative free-optimization is a popular tool for addressing complex problems in which the analytical description of the objective function is not available and the computation of derivative information is impractical, if not impossible. Many of these problems consider non-relaxable discrete variables that add further complexity to the optimization and the convergence analysis. This thesis concerns the development of two mixed-integer derivative-free algorithms that address some of these complications.The first algorithm is an adaptation of the trust-region method that uses a tailored quadratic-surrogate approximation of the unknown function. Such model approximations are constructed under the assumption of a local mixed-integer quadratic structure. Moreover, these surrogates are proved to be fully-linear in restricted mixed-integer neighborhoods. This algorithm is proved to be globally convergent to several definitions of local optimality, even in the optimization of functions that do not display the local quadratic structure.The second algorithm is a hybrid of the difference of convex algorithm (DCA) and the trust-region method that takes advantage of potential structures on the objective function. It is based on the assumption that the partial optimization with respect to the discrete variables can be performed using a polynomial number of objective evaluations. This algorithm is globally convergent to a point that is stationary with respect to the continuous variables and the global optimum in the discrete domain. In addition, this thesis presents a general definition of a mixed-integer fully-linear model and explores the mechanisms to evaluate and maintain error bounded approximations. The final contribution of this work is the introduction of new mixed-integer stationarity measures that prevent the early algorithmic termination and facilitate the convergence analysis.L'optimisation sans dérivées est un outil populaire pour résoudre des problèmes complexes dans lesquels la description analytique de la fonction objectif n'est pas disponible et le calcul des dérivées n'est pas pratique, sinon impossible. Beaucoup de ces problèmes considèrent des variables discrètes non relaxables qui ajoutent une complexité supplémentaire à l'optimisation et à l'analyse de convergence. Cette thèse concerne le développement de deux algorithmes sans dérivées avec variables mixtes qui adressent certains de ces complications. Le premier algorithme est une adaptation de la méthode à région de confiance qui utilise une approximation quadratique adaptée de la fonction inconnue. Ces modèles sont construits sous l’hypothèse d’une structure quadratique locale. De plus, ces modèles se sont prouvés complètement linéaires dans voisinages réels et entiers restreints. Cet algorithme se prouve globalement convergent vers plusieurs définitions d’optimalité locale, même dans l’optimisation de fonctions qui n’affichent pas la structure quadratique locale. Le deuxième algorithme est un hybride de la programmation DC et de la méthode de région confiance qui tire parti des structures potentielles sur la fonction objectif. Il est basé sur l’hypothèse que l’optimisation partielle par rapport aux variables discrètes peut être effectuée en utilisant un nombre polynomial d’évaluations de la fonction objectives. Cet algorithme est globalement convergent vers un point stationnaire par rapport aux variables continues et à l’optimum global dans le domaine entier. De plus, cette thèse présente une définition générale d’un modèle entièrement linéaire et explore les mécanismes pour évaluer et maintenir des modèles avec des erreurs bornées. La contribution finale de ce travail est l’introduction de nouvelles mesures de stationnarité entière qui empêchent la terminaison algorithmique précoce et facilitent l’analyse de convergence