L'objectif de cette thèse porte sur des recherches théoriques et algorithmiques d'optimisation locale et globale via les techniques de programmation DC & DCA, Séparation et Evaluation (SE) ainsi que les techniques de relaxation DC/SDP, pour résoudre plusieurs types de problèmes d'optimisation non convexe (notamment en Optimisation Combinatoire et Optimisation Polynomiale). La thèse comporte quatre parties :La première partie présente les outils fondamentaux et les techniques essentielles en programmation DC & l'Algorithme DC (DCA), ainsi que les techniques de relaxation SDP, et les méthodes de séparation et évaluation (SE).Dans la deuxième partie, nous nous intéressons à la résolution de problèmes de programmation quadratique et linéaire mixte en variables entières. Nous proposons de nouvelles approches locales et globales basées sur DCA, SE et SDP. L'implémentation de logiciel et des simulations numériques sont aussi étudiées.La troisième partie explore des approches de la programmation DC & DCA en les combinant aux techniques SE et SDP pour la résolution locale et globale de programmes polynomiaux. Le programme polynomial avec des fonctions polynomiales homogènes et son application à la gestion de portefeuille avec moments d'ordre supérieur en optimisation financière ont été discutés de manière approfondie dans cette partie.Enfin, nous étudions dans la dernière partie un programme d'optimisation sous contraintes de type matrices semi-définies via nos approches de la programmation DC. Nous nous consacrons à la résolution du problème de réalisabilité des contraintes BMI et QMI en contrôle optimal.L'ensemble de ces travaux a été implémenté avec MATLAB, C/C++ ... nous permettant de confirmer l'utilisation pratique et d'enrichir nos travaux de recherche.

Les travaux de thèse effectués dans le cadre de la convention Cifre conclue entrele laboratoire de mathématiques de Besançon et Digital Surf, entreprise éditrice dulogiciel d’analyse métrologique Mountains, portent sur les techniques d’analyse hyperspectrale.Sujet en plein essor, ces méthodes permettent d’exploiter des imagesissues de micro-spectroscopie, et en particulier de spectroscopie Raman. Digital Surfambitionne aujourd’hui de concevoir des solutions logicielles adaptées aux imagesproduites par ces appareils. Ces dernières se présentent sous forme de cubes de valeurs,où chaque pixel correspond à un spectre. La taille importante de ces données,appelées images hyperspectrales en raison du nombre important de mesures disponiblespour chaque spectre, obligent à repenser certains des algorithmes classiquesd’analyse d’image.Nous commençons par nous intéresser aux techniques de partitionnement de données.L’idée est de regrouper dans des classes homogènes les différents spectres correspondantà des matériaux similaires. La classification est une des techniques courammentutilisée en traitement des données. Cette tâche fait pourtant partie d’unensemble de problèmes réputés trop complexes pour une résolution pratique : les problèmesNP-durs. L’efficacité des différentes heuristiques utilisées en pratique était jusqu’àrécemment mal comprise. Nous proposons des argument théoriques permettantde donner des garanties de succès quand les groupes à séparer présentent certainespropriétés statistiques.Nous abordons ensuite les techniques de dé-mélange. Cette fois, il ne s’agit plus dedéterminer un ensemble de pixels semblables dans l’image, mais de proposer une interprétationde chaque pixel comme un mélange linéaire de différentes signatures spectrales,sensées émaner de matériaux purs. Cette déconstruction de spectres compositesse traduit mathématiquement comme un problème de factorisation en matrices positives.Ce problème est NP-dur lui aussi. Nous envisageons donc certaines relaxations,malencontreusement peu convaincantes en pratique. Contrairement au problème declassification, il semble très difficile de donner de bonnes garanties théoriques sur laqualité des résultats proposés. Nous adoptons donc une approche plus pragmatique,et proposons de régulariser cette factorisation en imposant des contraintes sur lavariation totale de chaque facteur.Finalement, nous donnons un aperçu d’autres problèmes d’analyse hyperspectralerencontrés lors de cette thèse, problèmes parmi lesquels figurent l’analyse en composantesindépendantes, la réduction non-linéaire de la dimension et la décompositiond’une image par rapport à une librairie regroupant un nombre important de spectresde référence. / This dissertation addresses hyperspectral image analysis, a set of techniques enabling exploitation of micro-spectroscopy images. Images produced by these sensors constitute cubic arrays, meaning that every pixel in the image is actually a spectrum.The size of these images, which is often quite large, calls for an upgrade for classical image analysis algorithms.We start out our investigation with clustering techniques. The main idea is to regroup every spectrum contained in a hyperspectralimage into homogeneous clusters. Spectrums taken across the image can indeed be generated by similar materials, and hence display spectral signatures resembling each other. Clustering is a commonly used method in data analysis. It belongs nonetheless to a class of particularly hard problems to solve, named NP-hard problems. The efficiency of a few heuristics used in practicewere poorly understood until recently. We give theoretical arguments guaranteeing success when the groups studied displaysome statistical property.We then study unmixing techniques. The objective is no longer to decide to which class a pixel belongs, but to understandeach pixel as a mix of basic signatures supposed to arise from pure materials. The mathematical underlying problem is again NP-hard.After studying its complexity, and suggesting two lengthy relaxations, we describe a more practical way to constrain the problemas to obtain regularized solutions.We finally give an overview of other hyperspectral image analysis methods encountered during this thesis, amongst whomare independent component analysis, non-linear dimension reduction, and regression against a spectrum library.

L’objectif de cette thèse porte sur des recherches théoriques et algorithmiques d’optimisation locale et globale via les techniques de programmation DC & DCA, Séparation et Evaluation (SE) ainsi que les techniques de relaxation DC/SDP, pour résoudre plusieurs types de problèmes d’optimisation non convexe (notamment en Optimisation Combinatoire et Optimisation Polynomiale). La thèse comporte quatre parties :La première partie présente les outils fondamentaux et les techniques essentielles en programmation DC & l’Algorithme DC (DCA), ainsi que les techniques de relaxation SDP, et les méthodes de séparation et évaluation (SE).Dans la deuxième partie, nous nous intéressons à la résolution de problèmes de programmation quadratique et linéaire mixte en variables entières. Nous proposons de nouvelles approches locales et globales basées sur DCA, SE et SDP. L’implémentation de logiciel et des simulations numériques sont aussi étudiées.La troisième partie explore des approches de la programmation DC & DCA en les combinant aux techniques SE et SDP pour la résolution locale et globale de programmes polynomiaux. Le programme polynomial avec des fonctions polynomiales homogènes et son application à la gestion de portefeuille avec moments d’ordre supérieur en optimisation financière ont été discutés de manière approfondie dans cette partie.Enfin, nous étudions dans la dernière partie un programme d’optimisation sous contraintes de type matrices semi-définies via nos approches de la programmation DC. Nous nous consacrons à la résolution du problème de réalisabilité des contraintes BMI et QMI en contrôle optimal.L’ensemble de ces travaux a été implémenté avec MATLAB, C/C++ ... nous permettant de confirmer l’utilisation pratique et d’enrichir nos travaux de recherche. / The main objective of this thesis focuses on theoretical and algorithmic researches of local and global optimization techniques to DC programming & DCA with Branch and Bound (B&B) and the DC/SDP relaxation techniques to solve several types of non-convex optimization problems (including Combinatorial Optimization and Polynomial Optimization). This thesis is divided into four parts :We present in the first part some fondamental theorems and essential techniques in DC programming & DC Algorithm (DCA), the SDP Relaxation techniques, as well as the Branch and Bound methods (B&B).In the second part, we are interested in solving mixed integer quadratic and linear programs. We propose new local and global approaches based on DCA, B&B and SDP. The implementation of software and numerical simulations have also been investigated.The third part explores the DC programming approaches & DCA combined with a B&B technique and SDP for locally and globally solving a class of polynomial programming. The polynomial program with homogeneous polynomial functionsand its application to portfolio selection problem involving higher order moments in financial optimization have been deeply studied in this part.Finally, in the last part, we present our research on optimization problems under constraints of semi-definite matrices via our DC programming approaches. This part is dedicated to the resolution of the BMI and QMI feasibility problems in the field of optimal control.All these proposed methods have been implemented with MATLAB, C++ etc., that allowing us to confirm the practical use and enrich our research works.