Cette thèse porte sur la recherche des techniques d’optimisation pour la résolution de certains problèmes importants en deux domaines : gestion de production. Il s’agit des problèmes d’optimisation non convexe de grande dimension. Notre travail est basé sur la programmation DC (Différence de fonctions convexes), DCA (DC algorithmes), la méthode par séparation et évaluation (SE). Cette démarche est motivée par la robustesse et la performance DC et DCA comparée aux autres méthodes. La thèse comprend trois parties : dans la première partie, nous présentons les outils fondamentaux et les techniques essentielles en programmation DC, DCA ainsi que les méthodes par séparation et évaluation. La deuxième partie concerne les problèmes d’optimisation non convexes en gestion de portefeuille. Nous avons étudié deux problèmes : problème min max continu en gestion de portefeuille en présence des contraintes de cardinalité ; une classe des problèmes d’optimisation à deux niveaux et son application en sélection de portefeuille. La troisième partie est consacrée à la recherche sur les problèmes d’optimisation non convexe en gestion de production. Trois problèmes ont été étudiés : minimisation du coût de maintenance comprenant le temps de séjour et la pénalité du retard ; minimisation du coût d’un système de production/stockage multi-étapes en présence de goulot d’étrangement. Détermination des prix de transfert et les politiques de stockage pour une chaîne d’approvisionnement de deux entreprises / This thesis deals with optimization techniques for solving some optimization problems in two domains : portfolio selection and production management. They are large scale non convex optimization problems due to integer variables and/or the non convexity of the objective function. Our approach is based on DC programming and DCA, DC relaxation techniques and the algorithm Branch and Bound. This work is motivated by the robustness and the performance of the DC programming and DCA compared to other methods. The thesis includes three parts : In the first part, we present the fundamental tools and the essential techniques in DC programming, DCA as well as the method Branch and Bound. The second one concerns some non convex optimization problem in portfolio selection. Two following problems are considered : Min max continuous problem with the cardinality constraints in portfolio selection ; A class of bilevel programming problems and its application in portfolio selection. The third part contains some non convex optimization problems in production management. We study three problems : Minimization of the maintenance cost involving the flow time and the tardiness penalty ; Minimization of the cost of multi-stages production/inventory systems with bottleneck ; Determination of transfer prices and inventory policy in supply chain of two enterprises

La thèse étudie des méthodes d'allocation de ressources, distribuées par station de base (BS) dans les réseaux OFDMA multi-cellulaires. L'objectif est de fournir la Qualité de Service (QdS) requise par chaque utilisateur, quelle que soit sa localisation dans la cellule. Les travaux portent d'abord sur la coordination causale de réseaux. Deux BSs forment un lien MIMO virtuel pour les utilisateurs localisés en bordure de cellule. Ces utilisateurs bénéficient d'un gain de diversité et d'une diminution de l'interférence inter-cellulaire. L'efficacité de la méthode d'allocation de ressources associée dépend de l'équité du contrôle de puissance. En conséquence, la coordination de réseaux est utilisée pour les utilisateurs à Débit Contraint (DC), mais pas pour les utilisateurs Best Effort (BE), dans un algorithme permettant de gérer conjointement les deux objectifs de QdS. La thèse étudie ensuite les réseaux totalement distribués. Pour les utilisateurs DC, une méthode d'allocation de ressources incluant une allocation de puissance itérative est déterminée pour résoudre le problème Margin Adaptive. Cette méthode est étendue aux utilisateurs DC en MIMO, lorsque le transmetteur connaît tout l'information de canal, ou uniquement ses caractéristiques statistiques. Pour les utilisateurs BE, enfin, l'objectif est de maximiser la somme des débits pondérés, le poids de chaque utilisateur étant proportionnel à la longueur de sa file d'attente. Une méthode d'allocation de sous-porteuses, déduite d'un graphe d'interférence, et une méthode de contrôle de puissance distribuée sont proposées pour résoudre ce problème d'optimisation.

Cette thèse décrit des méthodes de construction de martingales avec marginales spécifiées. La première collection de méthodes procède par quantization. C'est-à-dire en approximant une mesure par une autre mesure dont le support consiste en un nombre fini de points. Nous introduisons une méthode de quantization qui préserve l'ordre convexe. L'ordre convexe est un ordre partiel sur l'espace des mesures qui les compare en termes de leur dispertion relative. Cette nouvelle méthode de quantization présente l'avantage que si deux mesures admettent une transition de martingale alors les mesures quantisées en admettent aussi. Ceci n'est pas le cas pour la méthode de quantization habituellement utilisée en probabilités (la méthode de quantization L2). Pour les mesures quantifiés nous présentons plusieurs méthodes de construction de transition de martingale. La première méthode procède par programmation linéaire. La deuxième méthode procède par construction de matrices avec diagonale et spectre données. La troisième méthode procède par l'algorithme de Chacon et Walsh. Dans une seconde partie la thèse présente une nouvelle solution au problème du plongement de Skorokhod. Dans une troisième partie la thèse étudie la construction de martingales à temps continu avec marginales données. Des constructions sont données à l'aide du draps Brownien. D'autres constructions sont données en modifiant une méthode développée par Albin, les martingales construites ainsi possèdent une propriété de scaling.. Dans une partie annexe, certaines conséquences de cette théorie concernant le management du risque des options asiatiques, par rapport à leur sensibilité à la volatilité et à la maturité sont établies.

La transformation de Legendre envoie des fonctions convexes définies sur un espace vectoriel à des fonctions convexes définies sur l'espace vectoriel dual. Elle est reliée à la dualité projective, aux coordonnées tangentielles en géometrie algébrique et à la construction des espaces de Banach duaux en analyse. On l'utilise aussi en mécanique statistique pour définir des potentiels thermodynamiques à partir des fonctions de variables d'état. Plus précisément, la transformation de Legendre permet de transformer une fonction d'état d'un système en une autre fonction d'état mieux adaptée à un problème particulier. Le chapitre un se veut un résumé des résultats connus à propos de la transformation de Legendre en analyse. Nous donnons plusieurs exemples afin d'illustrer les propriétés essentielles de cette transformation. Dans le chapitre deux, nous rappelons quelques notions en thermodynamique statistique: Les variables intensives, les variables extensives, l'énergie interne, l'entropie. Ensuite nous définissons les potentiels thermodynamiques qui sont des transformées de Legendre de l'énergie interne. Dans le chapitre trois, nous rappelons des résultats fondamentaux de la théorie des espèces de structures. Mentionnons en particulier le théorème de dissymétrie pour les arbres et pour les graphes, ainsi que les équations fonctionnelles fondamentales pour les CB-graphes, i.e les graphes connexes dont tous les blocs sont dans une classe des graphes inséparables B, ainsi que pour les CM-graphes, i.e les graphes connexes dont toutes les mottes sont dans une classe de graphes irréductibles (2-arêtes-connexes). Dans le chapitre quatre, nous donnons la définition de la transformation de Legendre pour les espèces de structures à une sorte ou à deux sortes par rapport à une sorte. En effet, Pierre Leroux a été le premier à relier ces deux notions (Transformation de Legendre et espèces de structures). Il a démontré (Leroux, 2003) que les CM-graphes sont liées au M-graphes par transformation de Legendre. Dans ce mémoire on montre par une construction originale que l'espèce M des graphes irréductibles peut être remplacée par une espèce N quelconque, avec N[0] =0. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Fonctions convexes, Ensembles convexes, Transformation de Legendre, Potentiels thermodynamiques, Énergie interne, Fonction de partition, Graphes, Isthme, Bloc, Motte, Graphes inséparables, Graphes irréductibles, Espèce de structures, Note.

Thèse de doctorat : Informatique : Metz : 2007. / DC = Différence de deux fonctions Convexes. DCA = DC algorithmes. Titre provenant de l'écran-titre. Notes bibliogr.

Le domaine de l'apprentissage de dictionnaire est le sujet d'attentions croissantes durant cette dernière décennie. L'apprentissage de dictionnaire est une approche adaptative de la représentation parcimonieuse de données. Les méthodes qui constituent l'état de l'art en DL donnent d'excellentes performances en approximation et débruitage. Cependant, la complexité calculatoire associée à ces méthodes restreint leur utilisation à de toutes petites images ou "patchs". Par conséquent, il n'est pas possible d'utiliser l'apprentissage de dictionnaire pour des applications impliquant de grandes images, telles que des images de télédétection. Dans cette thèse, nous proposons et étudions un modèle original d'apprentissage de dictionnaire, combinant une méthode de décomposition des images par convolution et des structures d'arbres de convolution pour les dictionnaires. Ce modèle a pour but de fournir des algorithmes efficaces pour traiter de grandes images, sans les décomposer en patchs. Dans la première partie, nous étudions comment optimiser une composition de convolutions de noyaux parcimonieux, un problème de factorisation matricielle non convexe. Ce modèle est alors utilisé pour construire des atomes de dictionnaire. Dans la seconde partie, nous proposons une structure de dictionnaire basée sur des arbres de convolution, ainsi qu'un algorithme de mise à jour de dictionnaire adapté à cette structure. Enfin, une étape de décomposition parcimonieuse est ajoutée à cet algorithme dans la dernière partie. À chaque étape de développement de la méthode, des expériences numériques donnent un aperçu de ses capacités d'approximation. / The dictionary learning problem has received increasing attention for the last ten years. DL is an adaptive approach for sparse data representation. Many state-of-the-art DL methods provide good performances for problems such as approximation, denoising and inverse problems. However, their numerical complexity restricts their use to small image patches. Thus, dictionary learning does not capture large features and is not a viable option for many applications handling large images, such as those encountered in remote sensing. In this thesis, we propose and study a new model for dictionary learning, combining convolutional sparse coding and dictionaries defined by convolutional tree structures. The aim of this model is to provide efficient algorithms for large images, avoiding the decomposition of these images into patches. In the first part, we study the optimization of a composition of convolutions with sparse kernels, to reach a target atom (such as a cosine, wavelet or curvelet). This is a non-convex matrix factorization problem. We propose a resolution method based on a Gaus-Seidel scheme, which produces good approximations of target atoms and whose complexity is linear with respect to the image size. Moreover, numerical experiments show that it is possible to find a global minimum. In the second part, we introduce a dictionary structure based on convolutional trees. We propose a dictionary update algorithm adapted to this structure and which complexity remains linear with respect to the image size. Finally, a sparse coding step is added to the algorithm in the last part. For each evolution of the proposed method, we illustrate its approximation abilities with numerical experiments.

Dans cette thèse, nous donnons de nouveaux résultats sur la taille moyenne d’enveloppes convexes de points choisis dans un convexe. Cette taille est connue lorsque les points sont choisis uniformément (et indépendamment) dans un polytope convexe, ou un convexe suffisamment «lisse» ; ou encore lorsque les points sont choisis indépendamment selon une loi normale centrée. Dans la première partie de cette thèse, nous développons une technique nous permettant de donner de nouveaux résultats lorsque les points sont choisis arbitrairement dans un convexe, puis «bruités» par une perturbation aléatoire. Ce type d’analyse, appelée analyse lissée, a initialement été développée par Spielman et Teng dans leur étude de l’algorithme du simplexe. Pour un ensemble de points arbitraires dans une boule, nous obtenons une borne inférieure et une borne supérieure de cette complexité lissée dans le cas de perturbations uniformes dans une boule en dimension arbitraire, ainsi que dans le cas de perturbations gaussiennes en dimension 2. La taille de l'enveloppe convexe de points choisis uniformément dans un convexe, peut avoir un comportement logarithmique si ce convexe est un polytope ou polynomial s’il est lisse. Nous construisons un convexe produisant un comportement oscillant entre ces deux extrêmes. Dans la dernière partie, nous présentons un algorithme pour engendrer efficacement une enveloppe convexe aléatoire de points choisis uniformément et indépendamment dans un disque sans avoir à engendrer explicitement tous les points. Il a été implémenté en C++ et intégré dans la bibliothèque CGAL. / In this thesis, we give some new results about the average size of convex hulls made of points chosen in a convex body. This size is known when the points are chosen uniformly (and independently) in a convex polytope or in a "smooth" enough convex body. This average size is also known if the points are independently chosen according to a centered Gaussian distribution. In the first part of this thesis, we introduce a technique that will give new results when the points are chosen arbitrarily in a convex body, and then noised by some random perturbations. This kind of analysis, called smoothed analysis, has been initially developed by Spielman and Teng in their study of the simplex algorithm. For an arbitrary set of point in a ball, we obtain a lower and a upper bound for this smoothed complexity, in the case of uniform perturbation in a ball (in arbitrary dimension) and in the case of Gaussian perturbations in dimension 2. The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body is polynomial for a "smooth" body and polylogarithmic for a polytope. In the second part, we construct a convex body so that the expected size of the convex hull of points uniformly chosen in that body oscillates between these two behaviors when the number of points increases. In the last part, we present an algorithm to generate efficiently a random convex hull made of points chosen uniformly and independently in a disk. We also compute its average time and space complexity. This algorithm can generate a random convex hull without explicitly generating all the points. It has been implemented in C++ and integrated in the CGAL library.

Cette thèse est consacrée à l'étude des mesures convexes ainsi qu'aux analogies entre la théorie de Brunn-Minkowski et la théorie de l'information. Je poursuis les travaux de Costa et Cover qui ont mis en lumière des similitudes entre deux grandes théories mathématiques, la théorie de Brunn-Minkowski d'une part et la théorie de l'information d'autre part. Partant de ces similitudes, ils ont conjecturé, comme analogue de la concavité de l'entropie exponentielle, que la racine n-ième du volume parallèle de tout ensemble compact de $R^n$ est une fonction concave, et je résous cette conjecture de manière détaillée. Par ailleurs, j'étudie les mesures convexes définies par Borell et je démontre pour ces mesures une inégalité renforcée de type Brunn-Minkowski pour les ensembles convexes symétriques. Cette thèse se décompose en quatre parties. Tout d'abord, je rappelle un certain nombre de notions de base. Dans une seconde partie, j'établis la validité de la conjecture de Costa-Cover sous certaines conditions et je démontre qu'en toute généralité, cette conjecture est fausse en exhibant des contre-exemples explicites. Dans une troisième partie, j'étends les résultats positifs de cette conjecture de deux manières, d'une part en généralisant la notion de volume et d'autre part en établissant des versions fonctionnelles. Enfin, je prolonge des travaux récents de Gardner et Zvavitch en améliorant la concavité des mesures convexes sous certaines hypothèses telles que la symétrie / This thesis is devoted to the study of convex measures as well as the relationships between the Brunn-Minkowski theory and the Information theory. I pursue the works by Costa and Cover who highlighted similarities between two fundamentals inequalities in the Brunn-Minkowski theory and in the Information theory. Starting with these similarities, they conjectured, as an analogue of the concavity of entropy power, that the n-th root of the parallel volume of every compact subset of $R^n$ is concave, and I give a complete answer to this conjecture. On the other hand, I study the convex measures defined by Borell and I established for these measures a refined inequality of the Brunn-Minkowski type if restricted to convex symmetric sets. This thesis is split in four parts. First, I recall some basic facts. In a second part, I prove the validity of the conjecture of Costa-Cover under special conditions and I show that the conjecture is false in such a generality by giving explicit counterexamples. In a third part, I extend the positive results of this conjecture by extending the notion of the classical volume and by establishing functional versions. Finally, I generalize recent works of Gardner and Zvavitch by improving the concavity of convex measures under different kind of hypothesis such as symmetries

Sont concernes les problèmes d'optimisation non convexe et non différentiable du type d.c canonique. L'aspect théorique et l'aspect algorithmique sont abordés

Une approche efficace pour la résolution de problèmes inverses consiste à définir le signal (ou l'image) recherché(e) par minimisation d'un critère pénalisé. Ce dernier s'écrit souvent sous la forme d'une somme de fonctions composées avec des opérateurs linéaires. En pratique, ces fonctions peuvent n'être ni convexes ni différentiables. De plus, les problèmes auxquels on doit faire face sont souvent de grande dimension. L'objectif de cette thèse est de concevoir de nouvelles méthodes pour résoudre de tels problèmes de minimisation, tout en accordant une attention particulière aux coûts de calculs ainsi qu'aux résultats théoriques de convergence. Une première idée pour construire des algorithmes rapides d'optimisation est d'employer une stratégie de préconditionnement, la métrique sous-jacente étant adaptée à chaque itération. Nous appliquons cette technique à l'algorithme explicite-implicite et proposons une méthode, fondée sur le principe de majoration-minimisation, afin de choisir automatiquement les matrices de préconditionnement. L'analyse de la convergence de cet algorithme repose sur l'inégalité de Kurdyka-L ojasiewicz. Une seconde stratégie consiste à découper les données traitées en différents blocs de dimension réduite. Cette approche nous permet de contrôler à la fois le nombre d'opérations s'effectuant à chaque itération de l'algorithme, ainsi que les besoins en mémoire, lors de son implémentation. Nous proposons ainsi des méthodes alternées par bloc dans les contextes de l'optimisation non convexe et convexe. Dans le cadre non convexe, une version alternée par bloc de l'algorithme explicite-implicite préconditionné est proposée. Les blocs sont alors mis à jour suivant une règle déterministe acyclique. Lorsque des hypothèses supplémentaires de convexité peuvent être faites, nous obtenons divers algorithmes proximaux primaux-duaux alternés, permettant l'usage d'une règle aléatoire arbitraire de balayage des blocs. L'analyse théorique de ces algorithmes stochastiques d'optimisation convexe se base sur la théorie des opérateurs monotones. Un élément clé permettant de résoudre des problèmes d'optimisation de grande dimension réside dans la possibilité de mettre en oeuvre en parallèle certaines étapes de calculs. Cette parallélisation est possible pour les algorithmes proximaux primaux-duaux alternés par bloc que nous proposons: les variables primales, ainsi que celles duales, peuvent être mises à jour en parallèle, de manière tout à fait flexible. A partir de ces résultats, nous déduisons de nouvelles méthodes distribuées, où les calculs sont répartis sur différents agents communiquant entre eux suivant une topologie d'hypergraphe. Finalement, nos contributions méthodologiques sont validées sur différentes applications en traitement du signal et des images. Nous nous intéressons dans un premier temps à divers problèmes d'optimisation faisant intervenir des critères non convexes, en particulier en restauration d'images lorsque l'image originale est dégradée par un bruit gaussien dépendant du signal, en démélange spectral, en reconstruction de phase en tomographie, et en déconvolution aveugle pour la reconstruction de signaux sismiques parcimonieux. Puis, dans un second temps, nous abordons des problèmes convexes intervenant dans la reconstruction de maillages 3D et dans l'optimisation de requêtes pour la gestion de bases de données / An efficient approach for solving an inverse problem is to define the recovered signal/image as a minimizer of a penalized criterion which is often split in a sum of simpler functions composed with linear operators. In the situations of practical interest, these functions may be neither convex nor smooth. In addition, large scale optimization problems often have to be faced. This thesis is devoted to the design of new methods to solve such difficult minimization problems, while paying attention to computational issues and theoretical convergence properties. A first idea to build fast minimization algorithms is to make use of a preconditioning strategy by adapting, at each iteration, the underlying metric. We incorporate this technique in the forward-backward algorithm and provide an automatic method for choosing the preconditioning matrices, based on a majorization-minimization principle. The convergence proofs rely on the Kurdyka-L ojasiewicz inequality. A second strategy consists of splitting the involved data in different blocks of reduced dimension. This approach allows us to control the number of operations performed at each iteration of the algorithms, as well as the required memory. For this purpose, block alternating methods are developed in the context of both non-convex and convex optimization problems. In the non-convex case, a block alternating version of the preconditioned forward-backward algorithm is proposed, where the blocks are updated according to an acyclic deterministic rule. When additional convexity assumptions can be made, various alternating proximal primal-dual algorithms are obtained by using an arbitrary random sweeping rule. The theoretical analysis of these stochastic convex optimization algorithms is grounded on the theory of monotone operators. A key ingredient in the solution of high dimensional optimization problems lies in the possibility of performing some of the computation steps in a parallel manner. This parallelization is made possible in the proposed block alternating primal-dual methods where the primal variables, as well as the dual ones, can be updated in a quite flexible way. As an offspring of these results, new distributed algorithms are derived, where the computations are spread over a set of agents connected through a general hyper graph topology. Finally, our methodological contributions are validated on a number of applications in signal and image processing. First, we focus on optimization problems involving non-convex criteria, in particular image restoration when the original image is corrupted with a signal dependent Gaussian noise, spectral unmixing, phase reconstruction in tomography, and blind deconvolution in seismic sparse signal reconstruction. Then, we address convex minimization problems arising in the context of 3D mesh denoising and in query optimization for database management