Cette thèse est consacrée à l'analyse qualitative (optimalités locale et globale, stabilité de la dualité...) et quantitative (algorithmes numériques de résolution qui en sont issus) de l'optimisation d.c. (difféence de deux fonctions convexes). Le premier chapitre est destiné à l'étude générale de la théorie et des algorithmes de l'optimisation d.c. - approche locale. Dans le deuxième chapitre, nous nous intéressons à la fois à l'étude théorique - la dualité Langrangienne, conditions d'optimalité globale et locale, et algorithmique - algorithmes globaux, DCA - du problème de minimisation d'une forme quadratique sur une boule et une sphère Euclidiennes. Nous présentons dans le troisième chapitre deux nouvelles méthodes - méthode globale de décomposition - branch & bound et DCA - pour la minimisation d'une forme quadratique indéfinie sur un polyèdre convexe borné. La résolution du problème d'optimisation multicritère par DCA via la pénalité exacte et par un algorithme global de type branch & bound fait l'objet du quatrième chapitre. Le cinquième chapitre concerne le traitement du problème multidimensionnel des tableaux de dissimilarités (MDS) par DCA. La résolution du problème de calcul des valeurs propres extrêmes d'une matrice réelle symétrique par DCA est étudiée dans le sixième chapitre. Enfin, dans le dernier chapitre nous étudions une méthode globale d'optimisation d.c. et son application à la résolution d'un problème industriel d'optimisation non convexe de Pool carburant.
Mots clés :
Optimisation d.c., algorithmes d'optimisation d.c. (DCA), optimisation
globale, méthode de décomposition - branch & bound, optimalité locale,
optimalité globale, dualité Lagrangienne, programmation quadratique non
convexe, optimisation multicritère, MDS, valeurs propres.
Abstract
This Ph.D. Thesis is devoted to the qualitative analysis (local and global optimality, duality...) and the quantitative analysis (solution algorithms which are based on these tools) of d.c. (difference of convex function) optimization. The first chapter deals with the general theory and algorithms of d.c. optimization. In the second chapter, we are interested in both theoretical study (Lagrangian duality, local and global optimalities conditions) and numerical algorithms (global algorithms and DCA) for minimizing quadratic forms over Euclidean balls and spheres. We present in the third chapter two new algorithms (global decomposition branch and bound algorithm and DCA) for minimizing quadratic forms over a polytope. Chapter IV concerns the solution of the problem of optimization over the efficient set by DCA and a global decomposition algorithm. The fifth chapter is consecrated to the mathematical modelling of the multidimensional scaling problem as d.c. optimization problems and to DCA for solving these problems. Different d.c. optimization problems which are equivalent to the problem of computing extreme symmetric eigenvalues are provided via Lagrangian stability in chapter VI where DCA have been used for solving these problems. Finally, in the last chapter we are interested in a global algorithm for solving d.c. optimization problems and its application to fuel mixture nonconvex optimization problem.
Keywords:
d.c. optimization, d.c. optimization algorithm (DCA), local optimality, global
optimality, global optimization, global decomposition - branch & bound
algorithms, Lagrangian duality, nonconvex quadratic programming, optimization
over the efficient set, multidimensional scaling problem (MDS), symmetric
eigenvalues problems.
