Dissertations / Theses on the topic 'DCA, DC programming'

Dans cette thèse, nous développons certaines techniques avancées d'apprentissage automatique dans le cadre de l'apprentissage en ligne et de l'apprentissage par renforcement (« reinforcement learning » en anglais -- RL). L'épine dorsale de nos approches est la programmation DC (Difference of Convex functions) et DCA (DC Algorithm), et leur version en ligne, qui sont reconnues comme de outils puissants d'optimisation non convexe, non différentiable. Cette thèse se compose de deux parties : la première partie étudie certaines techniques d'apprentissage automatique en mode en ligne et la deuxième partie concerne le RL en mode batch et mode en ligne. La première partie comprend deux chapitres correspondant à la classification en ligne (chapitre 2) et la prédiction avec des conseils d'experts (chapitre 3). Ces deux chapitres mentionnent une approche unifiée d'approximation DC pour différents problèmes d'optimisation en ligne dont les fonctions objectives sont des fonctions de perte 0-1. Nous étudions comment développer des algorithmes DCA en ligne efficaces en termes d'aspects théoriques et computationnels. La deuxième partie se compose de quatre chapitres (chapitres 4, 5, 6, 7). Après une brève introduction du RL et ses travaux connexes au chapitre 4, le chapitre 5 vise à fournir des techniques efficaces du RL en mode batch basées sur la programmation DC et DCA. Nous considérons quatre différentes formulations d'optimisation DC en RL pour lesquelles des algorithmes correspondants basés sur DCA sont développés. Nous traitons les problèmes clés de DCA et montrons l'efficacité de ces algorithmes au moyen de diverses expériences. En poursuivant cette étude, au chapitre 6, nous développons les techniques du RL basées sur DCA en mode en ligne et proposons leurs versions alternatives. Comme application, nous abordons le problème du plus court chemin stochastique (« stochastic shortest path » en anglais -- SSP) au chapitre 7. Nous étudions une classe particulière de problèmes de SSP qui peut être reformulée comme une formulation de minimisation de cardinalité et une formulation du RL. La première formulation implique la norme zéro et les variables binaires. Nous proposons un algorithme basé sur DCA en exploitant une approche d'approximation DC de la norme zéro et une technique de pénalité exacte pour les variables binaires. Pour la deuxième formulation, nous utilisons un algorithme batch RL basé sur DCA. Tous les algorithmes proposés sont testés sur des réseaux routiers artificiels
In this dissertation, we develop some advanced machine learning techniques in the framework of online learning and reinforcement learning (RL). The backbones of our approaches are DC (Difference of Convex functions) programming and DCA (DC Algorithm), and their online version that are best known as powerful nonsmooth, nonconvex optimization tools. This dissertation is composed of two parts: the first part studies some online machine learning techniques and the second part concerns RL in both batch and online modes. The first part includes two chapters corresponding to online classification (Chapter 2) and prediction with expert advice (Chapter 3). These two chapters mention a unified DC approximation approach to different online learning algorithms where the observed objective functions are 0-1 loss functions. We thoroughly study how to develop efficient online DCA algorithms in terms of theoretical and computational aspects. The second part consists of four chapters (Chapters 4, 5, 6, 7). After a brief introduction of RL and its related works in Chapter 4, Chapter 5 aims to provide effective RL techniques in batch mode based on DC programming and DCA. In particular, we first consider four different DC optimization formulations for which corresponding attractive DCA-based algorithms are developed, then carefully address the key issues of DCA, and finally, show the computational efficiency of these algorithms through various experiments. Continuing this study, in Chapter 6 we develop DCA-based RL techniques in online mode and propose their alternating versions. As an application, we tackle the stochastic shortest path (SSP) problem in Chapter 7. Especially, a particular class of SSP problems can be reformulated in two directions as a cardinality minimization formulation and an RL formulation. Firstly, the cardinality formulation involves the zero-norm in objective and the binary variables. We propose a DCA-based algorithm by exploiting a DC approximation approach for the zero-norm and an exact penalty technique for the binary variables. Secondly, we make use of the aforementioned DCA-based batch RL algorithm. All proposed algorithms are tested on some artificial road networks

Nous abordons dans cette thèse les approches de la Programmation DC et DCAen Data Mining (fouille de données). Plus particulièrement, nous nous intéressons aux problèmes de parcimonie en modélisation parcimonieuse de données. Le travail porte sur des recherches théoriques et algorithmiques et la principale approche utilisée est la programmation DC et DCA.Nous avons établi des propriétés intéressantes, des reformulations DC, voire quadratiques,équivalentes pour ces problèmes grâce à de nouvelles techniques de pénalité exacte développées durant cette thèse. Ces résultats donnent une nouvelle facette et une nouvelle manière de voir ces problèmes de parcimonie afin de permettre une meilleure compréhension et prise en main de ces problèmes. Ces nouvelles techniques ont été appliquées dans le cadre de la modélisation parcimonieuse pour le problème de la valeur propre maximale et dans le cadre de la modélisation parcimonieuse dans les modèles de régression linéaire.La structure simple des reformulations obtenues se prête bien à la programmation DC et DCA pour la résolution. Les simulations numériques, obtenues avec DCA et un algorithme combiné DCA et la procédure Séparation et Evaluation pour l'optimisation globale, sont très intéressantes et très prometteuses et illustrent bien le potentiel de cette nouvelle approche.

La communication sans fil joue un rôle de plus en plus important dans de nombreux domaines. Un grand nombre d'applications sont exploitées tels que l'e-banking, l'e-commerce, les services médicaux,….Ainsi, la qualité de service (QoS), et la confidentialité d'information sur le réseau sans fil sont primordiales dans la conception du réseau sans fil. Dans le cadre de cette thèse, nous nous concentrons sur le développement des approches d'optimisation pour résoudre certains problèmes concernant les deux sujets suivants : la qualité de service et la sécurité de la couche physique. Nos méthodes sont basées sur la programmation DC (Difference of convex functions) et DCA (DC Algorithms) qui sont reconnues comme de puissants outils d'optimisation non convexes et non différentiables. Ces outils ont connu de grands succès au cours des deux dernières décennies dans la modélisation et la résolution de nombreux problèmes d'applications dans divers domaines de sciences appliquées. Outre les chapitres d'introduction et de conclusion, le contenu principal de cette thèse est divisé en quatre chapitres: Le chapitre 2 concerne la QoS dans les réseaux sans fil tandis que les trois chapitres suivants étudient la sécurité de la couche physique. Le chapitre 2 considère un critère de QoS qui consiste à assurer un service équitable entre les utilisateurs dans un réseau sans fil. Plus précisement, on doit s'assurer qu'aucun utilisateur ne souffre d'un mauvais rapport signal sur bruit (“signal to noise ratio (SNR)" en anglais). Le problème revient à maximiser le plus petit SNR. Il s'agit donc un problème d'optimisation DC général (minimisation d'une fonction DC sur un ensemble défini par des contraintes convexes et des contraintes DC). La programmation DC et DCA ont été développés pour résoudre ce problème. Tenant compte de la structure spécifique du problème, nous avons proposé une nouvelle décomposition DC qui était plus efficace que la précédente décomposition. Une méthode de résolution basée sur la programmation DC et DCA a été développée. De plus, nous avons prouvé la convergence de notre algorithme. L'objectif commun des trois chapitres suivants (Chapitre 3, 4, 5) est de garantir la sécurité de la couche physique d'un système de communication sans fil. Nous nous concentrons sur l'approche qui consiste à maximiser le taux de secret (“secrecy rate” en anglais). Trois diverses architectures du réseau sans fil utilisant différentes techniques coopératives pour la transmission sont considérées dans ces trois chapitres. Dans le chapitre 3, nous considérons un réseau point-à-point utilisant une technique coopérative de brouillage. Le chapitre 4 étudie un réseau de relais utilisant une combinaison de technique de formation de faisceau ("beamforming technique" en anglais) et de technique de relais coopératifs. Deux protocoles de technique de relais coopératifs, Amplifier-et-Transmettre (“Amplify-and-Forward (AF)'') et Décoder-et-Transmettre (“Decode-and-Forward (DF)'' en anglais), sont considérés. Dans le chapitre 3 et le chapitre 4, nous considérons qu'il y a seulement un espion (“eavesdropper" en anglais) dans le réseau tandis que le chapitre 5 est une extension du chapitre 4 où on peut avoir plusieurs espions. Tous ces problèmes sont des problèmes d'optimisation non-convexes qui peuvent être ensuite reformulés sous forme d'une programmation DC pour lesquels nous développons les méthodes efficaces et robustes basées sur la programmation DC et DCA. Dans les chapitres 3 et 4, nous reformulons les problèmes étudiés sous forme d'un programme DC standard (minimisation d'une fonction DC avec les contraintes convexes). La structure spécifique est bien exploitée afin de concevoir des schémas DCA standard efficaces où les sous-problèmes convexes de ces schémas sont résolus soit explicitement soit de manière peu coûteuse. Les problèmes d'optimisation dans le chapitre 5 sont reformulés comme les programmes DC généraux et les schémas [...]
Wireless communication plays an increasingly important role in many aspects of life. A lot of applications of wireless communication are exploited to serve people's life such as e-banking, e-commerce and medical service. Therefore, quality of service (QoS) as well as confidentiality and privacy of information over the wireless network are of leading interests in wireless network designs. In this dissertation, we focus on developing optimization techniques to address some problems in two topics: QoS and physical layer security. Our methods are relied on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which are powerful, non-differentiable, non-convex optimization tools that have enjoyed great success over the last two decades in modelling and solving many application problems in various fields of applied science. Besides the introduction and conclusion chapters, the main content of the dissertation is divided into four chapters: the chapter 2 concerns QoS in wireless networks whereas the next three chapters tackle physical layer security. The chapter 2 discusses a criterion of QoS assessed by the minimum of signal-to-noise (SNR) ratios at receivers. The objective is to maximize the minimum SNR in order to ensure the fairness among users, avoid the case in which some users have to suffer from a very low SNR. We apply DC programming and DCA to solve the derived max-min fairness optimization problem. With the awareness that the efficiency of DCA heavily depends on the corresponding DC decomposition, we recast the considered problem as a general DC program (minimization of a DC function on a set defined by some convex constraints and some DC constraints) using a DC decomposition different from the existing one and design a general DCA scheme to handle that problem. The numerical results reveal the efficiency of our proposed DCA compared with the existing DCA and the other methods. In addition, we rigorously prove the convergence of the proposed general DCA scheme. The common objective of the next three chapters (Chapter 3,4,5) is to guarantee security at the physical layer of wireless communication systems based on maximizing their secrecy rate. Three different architectures of the wireless system using various cooperative techniques are considered in these three chapters. More specifically, a point-to-point wireless system including single eavesdropper and employing cooperative jamming technique is considered in the chapter 3. Chapter 4 is about a relay wireless system including single eavesdropper and using a combination of beamforming technique and cooperative relaying technique with two relaying protocols Amplify-and-Forward (AF) and Decode-and-Forward (DF). Chapter 5 concerns a more general relay wireless system than the chapter 4, in which multiple eavesdroppers are considered instead of single eavesdropper. The difference in architecture of wireless systems as well as in the utilized cooperative techniques result in three mathematically different optimization problems. The unified approach based on DC programming and DCA is proposed to deal with these problems. The special structures of the derived optimization problems in the chapter 3 and the chapter 4 are exploited and explored to design efficient standard DCA schemes in the sense that the convex subproblems in these schemes are solved either explicitly or in an inexpensive way. The max-min forms of the optimization problems in the chapter 5 are reformulated as the general DC programs with DC constraints and the general DCA schemes are developed to address these problems. The results obtained by DCA show the efficiency of our approach in comparison with the existing methods. The convergence of the proposed general DCA schemes is thoroughly shown

Dans cette thèse, nous étudions des approches basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithm) pour la programmation mathématique avec des contraintes d'équilibre, notée MPEC (Mathematical Programming with Equilibrum Constraints en anglais). Etant un sujet classique et difficile de la programmation mathématique et de la recherche opérationnelle, et de par ses diverses applications importantes, MPEC a attiré l'attention de nombreux chercheurs depuis plusieurs années. La thèse se compose de quatre chapitres principaux. Le chapitre 2 étudie une classe de programmes mathématiques avec des contraintes de complémentarité linéaire. En utilisant quatre fonctions de pénalité, nous reformulons le problème considéré comme des problèmes DC standard, i.e minimisation d'une fonction DC sous les contraintes convexes. Nous développons ensuite des algorithmes appropriés basés sur DCA pour résoudre les problèmes DC résultants. Deux d'entre eux sont reformulés encore sous la forme des problèmes DC généraux (i.e. minimisation d'une fonction DC sous des contraintes DC) pour que les sous-problèmes convexes dans DCA soient plus faciles à résoudre. Après la conception de DCA pour le problème considéré, nous développons ces schémas DCA pour deux cas particuliers: la programmation quadratique avec des contraintes de complémentarité linéaire, et le problème de complémentarité aux valeurs propres. Le chapitre 3 aborde une classe de programmes mathématiques avec des contraintes d'inégalité variationnelle. Nous utilisons une technique de pénalisation pour reformuler le problème considéré comme un programme DC. Une variante de DCA et sa version accélérée sont proposées pour résoudre ce programme DC. Comme application, nous résolvons le problème de détermination du prix de péages dans un réseau de transport avec des demandes fixes (" the second-best toll pricing problem with fixed demands" en anglais). Le chapitre 4 se concentre sur une classe de problèmes d'optimisation à deux niveaux avec des variables binaires dans le niveau supérieur. En utilisant une fonction de pénalité exacte, nous reformulons le problème considéré comme un programme DC standard pour lequel nous développons un algorithme efficace basé sur DCA. Nous appliquons l'algorithme proposé pour résoudre le problème d'interdiction de flot maximum dans un réseau ("maximum flow network interdiction problem" en anglais). Dans le chapitre 5, nous nous intéressons au problème de conception de réseau d'équilibre continu ("continuous equilibrium network design problem" en anglais). Il est modélisé sous forme d'un programme mathématique avec des contraintes de complémentarité, brièvement nommé MPCC (Mathematical Program with Complementarity Constraints en anglais). Nous reformulons ce problème MPCC comme un programme DC général et proposons un schéma DCA approprié pour le problème résultant
In this dissertation, we investigate approaches based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) for mathematical programs with equilibrium constraints. Being a classical and challenging topic of nonconvex optimization, and because of its many important applications, mathematical programming with equilibrium constraints has attracted the attention of many researchers since many years. The dissertation consists of four main chapters. Chapter 2 studies a class of mathematical programs with linear complementarity constraints. By using four penalty functions, we reformulate the considered problem as standard DC programs, i.e. minimizing a DC function on a convex set. The appropriate DCA schemes are developed to solve these four DC programs. Two among them are reformulated again as general DC programs (i.e. minimizing a DC function under DC constraints) in order that the convex subproblems in DCA are easier to solve. After designing DCA for the considered problem, we show how to develop these DCA schemes for solving the quadratic problem with linear complementarity constraints and the asymmetric eigenvalue complementarity problem. Chapter 3 addresses a class of mathematical programs with variational inequality constraints. We use a penalty technique to recast the considered problem as a DC program. A variant of DCA and its accelerated version are proposed to solve this DC program. As an application, we tackle the second-best toll pricing problem with fixed demands. Chapter 4 focuses on a class of bilevel optimization problems with binary upper level variables. By using an exact penalty function, we express the bilevel problem as a standard DC program for which an efficient DCA scheme is developed. We apply the proposed algorithm to solve a maximum flow network interdiction problem. In chapter 5, we are interested in the continuous equilibrium network design problem. It was formulated as a Mathematical Program with Complementarity Constraints (MPCC). We reformulate this MPCC problem as a general DC program and then propose a suitable DCA scheme for the resulting problem

Dans cette thèse, nous nous concentrons sur le développement des méthodes d'optimisation pour résoudre certaines classes de problèmes d'apprentissage avec la parcimonie et/ou avec l'incertitude des données. Nos méthodes sont basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithms) étant reconnues comme des outils puissants d'optimisation. La thèse se compose de deux parties : La première partie concerne la parcimonie tandis que la deuxième partie traite l'incertitude des données. Dans la première partie, une étude approfondie pour la minimisation de la norme zéro a été réalisée tant sur le plan théorique qu'algorithmique. Nous considérons une approximation DC commune de la norme zéro et développons quatre algorithmes basées sur la programmation DC et DCA pour résoudre le problème approché. Nous prouvons que nos algorithmes couvrent tous les algorithmes standards existants dans le domaine. Ensuite, nous étudions le problème de la factorisation en matrices non-négatives (NMF) et fournissons des algorithmes appropriés basés sur la programmation DC et DCA. Nous étudions également le problème de NMF parcimonieuse. Poursuivant cette étude, nous étudions le problème d'apprentissage de dictionnaire où la représentation parcimonieuse joue un rôle crucial. Dans la deuxième partie, nous exploitons la technique d'optimisation robuste pour traiter l'incertitude des données pour les deux problèmes importants dans l'apprentissage : la sélection de variables dans SVM (Support Vector Machines) et le clustering. Différents modèles d'incertitude sont étudiés. Les algorithmes basés sur DCA sont développés pour résoudre ces problèmes
In this thesis, we focus on developing optimization approaches for solving some classes of optimization problems in sparsity and robust optimization for data uncertainty. Our methods are based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which are well-known as powerful tools in optimization. This thesis is composed of two parts: the first part concerns with sparsity while the second part deals with uncertainty. In the first part, a unified DC approximation approach to optimization problem involving the zero-norm in objective is thoroughly studied on both theoretical and computational aspects. We consider a common DC approximation of zero-norm that includes all standard sparse inducing penalty functions, and develop general DCA schemes that cover all standard algorithms in the field. Next, the thesis turns to the nonnegative matrix factorization (NMF) problem. We investigate the structure of the considered problem and provide appropriate DCA based algorithms. To enhance the performance of NMF, the sparse NMF formulations are proposed. Continuing this topic, we study the dictionary learning problem where sparse representation plays a crucial role. In the second part, we exploit robust optimization technique to deal with data uncertainty for two important problems in machine learning: feature selection in linear Support Vector Machines and clustering. In this context, individual data point is uncertain but varies in a bounded uncertainty set. Different models (box/spherical/ellipsoidal) related to uncertain data are studied. DCA based algorithms are developed to solve the robust problems

Notre objectif dans cette thèse est de résoudre un problème quadratique binaire sous contraintes mixtes par les techniques d'optimisation DC. Puisque l'optimisation DC a prouvé son efficacité pour résoudre des problèmes de grandes tailles dans différents domaines, nous avons décidé d'appliquer cette approche d'optimisation pour résoudre ce problème. La partie la plus importante de l'optimisation DC est le choix d'une décomposition adéquate qui facilite la détermination et accélère la convergence de deux suites construites. La première suite converge vers la solution optimale du problème primal et la seconde converge vers la solution optimale du problème dual. Dans cette thèse, nous proposons deux décompositions DC efficaces et simples à manipuler. L'application de l'algorithme DC (DCA) nous conduit à résoudre à chaque itération un problème quadratique convexe avec des contraintes mixtes, linéaires et quadratiques. Pour cela, il faut trouver une méthode efficace et rapide pour résoudre ce dernier problème à chaque itération. Pour cela, nous appliquons trois méthodes différentes: la méthode de Newton, la programmation semi-définie positive et la méthode de points intérieurs. Nous présentons les résultats numériques comparatifs sur les mêmes repères de ces trois approches pour justifier notre choix de la méthode la plus rapide pour résoudre efficacement ce problème
Our objective in this work is to solve a binary quadratic problem under mixed constraints by the techniques of DC optimization. As DC optimization has proved its efficiency to solve large-scale problems in different domains, we decided to apply this optimization approach to solve this problem. The most important part of D.C. optimization is the choice of an adequate decomposition that facilitates determination and speeds convergence of two constructed suites where the first converges to the optimal solution of the primal problem and the second converges to the optimal solution of the dual problem. In this work, we propose two efficient decompositions and simple to manipulate. The application of the DC Algorithm (DCA) leads us to solve at each iteration a convex quadratic problem with mixed, linear and quadratic constraints. For it, we must find an efficient and fast method to solve this last problem at each iteration. To do this, we apply three different methods: the Newton method, the semidefinite programing and interior point method. We present the comparative numerical results on the same benchmarks of these three approaches to justify our choice of the fastest method to effectively solve this problem

De nos jours, avec l'abondance croissante de données de très grande taille, les problèmes de classification de grande dimension ont été mis en évidence comme un challenge dans la communauté d'apprentissage automatique et ont beaucoup attiré l'attention des chercheurs dans le domaine. Au cours des dernières années, les techniques d'apprentissage avec la parcimonie et l'optimisation stochastique se sont prouvées être efficaces pour ce type de problèmes. Dans cette thèse, nous nous concentrons sur le développement des méthodes d'optimisation pour résoudre certaines classes de problèmes concernant ces deux sujets. Nos méthodes sont basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithm) étant reconnues comme des outils puissants d'optimisation non convexe. La thèse est composée de trois parties. La première partie aborde le problème de la sélection des variables. La deuxième partie étudie le problème de la sélection de groupes de variables. La dernière partie de la thèse liée à l'apprentissage stochastique. Dans la première partie, nous commençons par la sélection des variables dans le problème discriminant de Fisher (Chapitre 2) et le problème de scoring optimal (Chapitre 3), qui sont les deux approches différentes pour la classification supervisée dans l'espace de grande dimension, dans lequel le nombre de variables est beaucoup plus grand que le nombre d'observations. Poursuivant cette étude, nous étudions la structure du problème d'estimation de matrice de covariance parcimonieuse et fournissons les quatre algorithmes appropriés basés sur la programmation DC et DCA (Chapitre 4). Deux applications en finance et en classification sont étudiées pour illustrer l'efficacité de nos méthodes. La deuxième partie étudie la L_p,0régularisation pour la sélection de groupes de variables (Chapitre 5). En utilisant une approximation DC de la L_p,0norme, nous prouvons que le problème approché, avec des paramètres appropriés, est équivalent au problème original. Considérant deux reformulations équivalentes du problème approché, nous développons différents algorithmes basés sur la programmation DC et DCA pour les résoudre. Comme applications, nous mettons en pratique nos méthodes pour la sélection de groupes de variables dans les problèmes de scoring optimal et d'estimation de multiples matrices de covariance. Dans la troisième partie de la thèse, nous introduisons un DCA stochastique pour des problèmes d'estimation des paramètres à grande échelle (Chapitre 6) dans lesquelles la fonction objectif est la somme d'une grande famille des fonctions non convexes. Comme une étude de cas, nous proposons un schéma DCA stochastique spécial pour le modèle loglinéaire incorporant des variables latentes
These days with the increasing abundance of data with high dimensionality, high dimensional classification problems have been highlighted as a challenge in machine learning community and have attracted a great deal of attention from researchers in the field. In recent years, sparse and stochastic learning techniques have been proven to be useful for this kind of problem. In this thesis, we focus on developing optimization approaches for solving some classes of optimization problems in these two topics. Our methods are based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) which are wellknown as one of the most powerful tools in optimization. The thesis is composed of three parts. The first part tackles the issue of variable selection. The second part studies the problem of group variable selection. The final part of the thesis concerns the stochastic learning. In the first part, we start with the variable selection in the Fisher's discriminant problem (Chapter 2) and the optimal scoring problem (Chapter 3), which are two different approaches for the supervised classification in the high dimensional setting, in which the number of features is much larger than the number of observations. Continuing this study, we study the structure of the sparse covariance matrix estimation problem and propose four appropriate DCA based algorithms (Chapter 4). Two applications in finance and classification are conducted to illustrate the efficiency of our methods. The second part studies the L_p,0regularization for the group variable selection (Chapter 5). Using a DC approximation of the L_p,0norm, we indicate that the approximate problem is equivalent to the original problem with suitable parameters. Considering two equivalent reformulations of the approximate problem we develop DCA based algorithms to solve them. Regarding applications, we implement the proposed algorithms for group feature selection in optimal scoring problem and estimation problem of multiple covariance matrices. In the third part of the thesis, we introduce a stochastic DCA for large scale parameter estimation problems (Chapter 6) in which the objective function is a large sum of nonconvex components. As an application, we propose a special stochastic DCA for the loglinear model incorporating latent variables

Cette thèse s'articule autour des fonctions booléennes liées à la cryptographie et la cryptanalyse de certains schémas d'identification. Les fonctions booléennes possèdent des propriétés algébriques fréquemment utilisées en cryptographie pour constituer des S-Boxes (tables de substitution).Nous nous intéressons, en particulier, à la construction de deux types de fonctions : les fonctions courbes et les fonctions équilibrées de haut degré de non-linéarité.Concernant la cryptanalyse, nous nous focalisons sur les techniques d'identification basées sur les problèmes de perceptron et de perceptron permuté. Nous réalisons une nouvelle attaque sur le schéma afin de décider de sa faisabilité.Nous développons ici des nouvelles méthodes combinant l'approche déterministe DCA (Difference of Convex functions Algorithm) et heuristique (recuit simulé, entropie croisée, algorithmes génétiques...). Cette approche hybride, utilisée dans toute cette thèse, est motivée par les résultats intéressants de la programmation DC.

La sécurité de la couche physique consiste à permettre la transmission des données confidentielles via un réseau sans fil en présence d'utilisateurs illégitimes, sans s'appuyer sur un cryptage de couche supérieure. L'essence de la sécurité de la couche physique est de maximiser le taux de secret, qui est le taux maximal d'informations sans interception par les espions. De plus, la conception de la sécurité de la couche physique prend en compte la minimisation de la puissance de transmission. Ces deux objectifs sont souvent en conflit l'un avec l'autre. Ainsi, la recherche sur les conceptions de sécurité de la couche physique se concentre souvent sur les deux principales classes de problèmes d’optimisation : maximiser le taux de secret sous contrainte de puissance de transmission et minimiser la puissance de transmission sous contrainte de taux de secret. Ces problèmes sont non convexes, donc difficiles à résoudre. Dans cette thèse, nous nous concentrons sur le développement des méthodes d'optimisation pour résoudre ces deux classes de problèmes d'optimisation. Nos méthodes sont basées sur la programmation DC (Difference of Convex functions) et DCA (DC Algorithm) étant reconnues comme des outils puissants d'optimisation non convexe. Dans la première partie, nous considérons trois classes de problèmes de maximisation du taux de secret (chapitre 2, 3, 4). Le chapitre 2 étudie la transmission sécurisée des informations dans un système de relais MISO. Le relais utilise une combinaison de technique de formation de faisceau et de technique de bruit artificiel sous les modèles déterministes des canaux d'incertitude. Sans utiliser de relais, le chapitre 3 étudie le problème du transfert simultané d'information sans fil et de l’énergie dans un système sécurisé sous parfaite connaissance des canaux et imparfaite connaissance des canaux. Deux stratégies de transmission : formation de faisceaux avec bruit artificiel et sans bruit artificiel sont étudiés. Avec l'hypothèse du canal statistique des espions, chapitre 4 aborde le problème de maximisation du taux de secret sous la contrainte en probabilité dans un système SWIPT ("simultaneous wireless information and power transfer (SWIPT)" en anglais) multi-utilisateur. L'approche unifiée basée sur la programmation DC et DCA est proposée pour résoudre trois classes de problèmes d'optimisation. Le problème d'optimisation du chapitre 2 est reformulé comme deux programmes DC généraux. Les schémas DCA généraux sont proposés pour résoudre ces deux programmes DC. Dans le chapitre 3, nous considérons quatre problèmes d'optimisation conformément à quatre scénarios. Nous exploitons la structure particulière des problèmes considérés de les reformuler comme programmes DC généraux. Les schémas DCA généraux correspondants sont développés pour les résoudre. Dans le chapitre 4, nous transformons d’abord le problème considéré en une forme traitable. Nous développons ensuite un algorithme alternatif pour résoudre le problème transformé. Deux programmes DC généraux sont proposés à chaque itération du schéma alternatif. Pour résoudre ces programmes DC, nous étudions une variante de DCA général, à savoir le schéma DCA−ρ. La convergence de l’algorithme proposé est rigoureusement prouvée. La deuxième partie étudie le problème de minimisation de la puissance de transmission sous les contraintes de probabilité du taux de secret et de récolte l’énergie dans le réseau SWIPT (chapitre 5). Nous reformulons le problème d’origine comme trois programmes DC généraux pour lequel nous d´développons trois schémas DCA généraux correspondants. Les résultats numériques démontrent l’efficacité des algorithmes proposés
Physical layer security is to enable confidential data transmission through wireless networks in the presence of illegitimate users, without basing on higher-layer encryption. The essence of physical layer security is to maximize the secrecy rate, that is the maxi- mum rate of information without intercepted by the eavesdroppers. Besides, the design of physical layer security considers the transmit power minimization. These two objectives conflict with each other. Consequently, the research on physical layer security designs often focuses on the two main classes of optimization problems: maximizing secrecy rate under the transmit power constraint and minimizing power consumption while guaranteeing the secrecy rate constraint. These problems are nonconvex, thus, hard to solve. In this thesis, we focus on developing optimization approaches to solve these two optimization problem classes. Our methods are based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) which well-known as one of the most powerful approaches in optimization. In the first part, we consider three classes of secrecy rate maximization problems (chapters 2, 3, 4). In particular, chapter 2 studies the secure information transmission in a multiple-input single-output (MISO) relay system by using joint beamforming and artificial noise strategy under the deterministic uncertainty channel models of all links. Without using a relay, chapter 3 addresses the problem of transfer wireless information and power simultaneously in MISO secure system where scenarios of perfect channel state information and deterministic uncertainty channel models are concerned. Transmit beamforming without artificial noise and that with artificial noise are investigated. Under the assumption of statistical channel state information to eavesdroppers, chapter 4 studies the probability constrained secrecy rate maximization problem in multiuser MISO simultaneous wireless information and power transfer (SWIPT) system. The unified approach based on DC programming and DCA is proposed to solve three classes of optimization problems. The optimization problem in chapter 2 is recast as two general DC programs. The general DCA schemes are proposed to solve these two DC programs. In chapter 3, we consider four optimization problems in accordance with four scenarios. Exploiting the special structures of these original optimization problems, we transform it into four general DC programs for which the corresponding general DCA based algorithms are developed. In chapter 4, we first transform the considered problem into a tractable form. We then develop an alternating scheme to solve the transformed problem. Two general DC programs are proposed in each step of the alternating scheme. For solving these DC programs, we study a variant of general DCA, namely, DCA−ρ scheme. The convergence of alternating general DCA−ρ scheme is proven. The second part studies the transmit power optimization problem under the probability constraints of secrecy rate and harvested energy in a MISO SWIPT system (chapter 5). We reformulate the original problem as three general DC programs for which the corresponding general DCA-based algorithms are investigated. Numerical results demonstrate the efficiency of the proposed algorithms

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.

Basés sur les outils théoriques et algorithmiques de la programmation DC et DCA, les travaux de recherche dans cette thèse portent sur les approches locales et globales pour l'optimisation non convexe et l'optimisation globale en variables mixtes entières. La thèse comporte 5 chapitres. Le premier chapitre présente les fondements de la programmation DC et DCA, et techniques de Séparation et Evaluation (B&B) (utilisant la technique de relaxation DC pour le calcul des bornes inférieures de la valeur optimale) pour l'optimisation globale. Y figure aussi des résultats concernant la pénalisation exacte pour la programmation en variables mixtes entières. Le deuxième chapitre est consacré au développement d'une méthode DCA pour la résolution d'une classe NP-difficile des programmes non convexes non linéaires en variables mixtes entières. Ces problèmes d'optimisation non convexe sont tout d'abord reformulées comme des programmes DC via les techniques de pénalisation en programmation DC de manière que les programmes DC résultants soient efficacement résolus par DCA et B&B bien adaptés. Comme première application en optimisation financière, nous avons modélisé le problème de gestion de portefeuille sous le coût de transaction concave et appliqué DCA et B&B à sa résolution. Dans le chapitre suivant nous étudions la modélisation du problème de minimisation du coût de transaction non convexe discontinu en gestion de portefeuille sous deux formes : la première est un programme DC obtenu en approximant la fonction objectif du problème original par une fonction DC polyèdrale et la deuxième est un programme DC mixte 0-1 équivalent. Et nous présentons DCA, B&B, et l'algorithme combiné DCA-B&B pour leur résolution. Le chapitre 4 étudie la résolution exacte du problème multi-objectif en variables mixtes binaires et présente deux applications concrètes de la méthode proposée. Nous nous intéressons dans le dernier chapitre à ces deux problématiques challenging : le problème de moindres carrés linéaires en variables entières bornées et celui de factorisation en matrices non négatives (Nonnegative Matrix Factorization (NMF)). La méthode NMF est particulièrement importante de par ses nombreuses et diverses applications tandis que les applications importantes du premier se trouvent en télécommunication. Les simulations numériques montrent la robustesse, rapidité (donc scalabilité), performance et la globalité de DCA par rapport aux méthodes existantes.

De nos jours, le Big Data est devenu essentiel et omniprésent dans tous les domaines. Par conséquence, il est nécessaire de développer des techniques innovantes et efficaces pour traiter la croissance rapide du volume des masses de données. Nous considérons les problèmes suivants dans le contexte de Big Data : la sélection de groupes de variables pour la régression logistique multi-classes, la réduction de dimension par t-SNE (« t-distributed Stochastic Neighbor Embedding « en anglais) et l'apprentissage en profondeur pour la classification non-supervisée (« Deep Clustering « en anglais). Nous développons des algorithmes DC (Difference of Convex functions) avancés pour ces problèmes, qui sont basés sur la programmation DC et DCA (DC Algorithm) -- des outils puissants pour les problèmes d'optimisation non-convexes non-différentiables. Dans la première partie, nous étudions le problème de la sélection de groupes de variables pour la régression logistique multi-classes. Nous résolvons ce problème en utilisant des DCAs avancés – Stochastic DCA et DCA-Like. Plus précisément, Stochastic DCA se spécialise dans le problème de la minimisation de la grande somme des fonctions DC, et ne nécessite qu'un sous-ensemble de fonctions DC à chaque itération. DCA-Like relaxe la condition de convexité de la deuxième composante DC en assurant la convergence. Accelerated DCA-Like intègre la technique d'accélération de Nesterov dans DCA-Like pour améliorer sa performance. Les expériences numériques sur plusieurs jeux de données benchmark de grande taille montrent l'efficacité de tous les algorithmes proposés en termes de temps d'exécution et de qualité de la solution. La deuxième partie concerne t-SNE, une technique efficace de réduction de dimension non linéaire. t-SNE est modélisé sous forme d'un problème d'optimisation non-convexe. Motivés par le caractère novateur de DCA-Like et Accelerated DCA-Like, nous développons ces deux algorithmes pour résoudre le problème t-SNE. La supériorité de nos algorithmes, appliqués à la visualisation de données, par rapport aux méthodes existantes est illustrée via des expériences numériques réalisées sur les jeux de données de très grande taille. La troisième partie est consacrée à la classification non-supervisée par l'apprentissage en profondeur. Dans la première application, nous proposons deux algorithmes basés sur DCA pour combiner t-SNE avec MSSC (Minimum Sum-of-Squares Clustering) par ces deux approches : « tandem analysis » et joint-clustering. La deuxième application considère le clustering en utilisant l'auto-encodeur. Nous avons proposé une extension d'une classe d'algorithmes de joint-clustering pour résoudre le problème de mise à l'échelle de données (« scaling problem » en anglais), et appliqué pour un cas spécifique de joint-clustering avec MSSC. Les résultats numériques sur plusieurs jeux de données benchmark montre l'efficacité de notre algorithme comparé aux méthodes existantes
Big Data has become gradually essential and ubiquitous in all aspects nowadays. Therefore, there is an urge to develop innovative and efficient techniques to deal with the rapid growth in the volume of data. This dissertation considers the following problems in Big Data: group variable selection in multi-class logistic regression, dimension reduction by t-SNE (t-distributed Stochastic Neighbor Embedding), and deep clustering. We develop advanced DCAs (Difference of Convex functions Algorithms) for these problems, which are based on DC Programming and DCA – the powerful tools for non-smooth non-convex optimization problems. Firstly, we consider the problem of group variable selection in multi-class logistic regression. We tackle this problem by using recently advanced DCAs -- Stochastic DCA and DCA-Like. Specifically, Stochastic DCA specializes in the large sum of DC functions minimization problem, which only requires a subset of DC functions at each iteration. DCA-Like relaxes the convexity condition of the second DC component while guaranteeing the convergence. Accelerated DCA-Like incorporates the Nesterov's acceleration technique into DCA-Like to improve its performance. The numerical experiments in benchmark high-dimensional datasets show the effectiveness of proposed algorithms in terms of running time and solution quality. The second part studies the t-SNE problem, an effective non-linear dimensional reduction technique. Motivated by the novelty of DCA-Like and Accelerated DCA-Like, we develop two algorithms for the t-SNE problem. The superiority of proposed algorithms in comparison with existing methods is illustrated through numerical experiments for visualization application. Finally, the third part considers the problem of deep clustering. In the first application, we propose two algorithms based on DCA to combine t-SNE with MSSC (Minimum Sum-of-Squares Clustering) by following two approaches: “tandem analysis” and joint-clustering. The second application considers clustering with auto-encoder (a well-known type of neural network). We propose an extension to a class of joint-clustering algorithms to overcome the scaling problem and applied for a specific case of joint-clustering with MSSC. Numerical experiments on several real-world datasets show the effectiveness of our methods in rapidity and clustering quality, compared to the state-of-the-art methods

Cette thèse a pour but de développer des approches déterministes et heuristiques pour résoudre certaines classes des problèmes d'optimisation en télécommunication et la mobilité d'un réseau de transport : problèmes de routage, problèmes de covoiturage, problèmes de contrôle de l'alimentation dans un réseau sans fil, problèmes d'équilibrage du spectre dans les réseaux DSL. Il s'agit des problèmes d'optimisation non convexe de très grande taille. Nos approches sont basées sur la programmation DC&DCA, méthode de décomposition proximale et la méthode d'étiquetage des graphes. Grâce aux techniques de formulation/reformulation et de pénalité exacte, nous avons établi des programmes DC équivalents en vue de leur résolution par DCA. Selon la structure de ces problèmes, on peut fournir des décompositions DC appropriées ou de bons points initiaux de DCA. Nos méthodes ont été programmées sous MATLAB, C/C++. Ils montrent la performance de nos algorithmes par rapport à des méthodes existantes.

Dans cette thèse, nous nous intéressons au développement des approches coopératives pour la résolution de certaines classes de problèmes d'optimisation non convexe qui jouent un rôle très important de par leurs applications dans de nombreux domaines. Il s'agit de combiner plusieurs algorithmes connus sous les noms des algorithmes composants (participants). La combinaison est basée principalement sur la programmation DC (Difference of Convex Functions) et DCA (DC Algorithm) avec des métaheuristiques. Pour la conception des logiciels nous utilisons les paradigmes de la programmation parallèle et distribuée. Chaque processus s'occupe d'un algorithme et communique avec les autres en appelant les fonctions de la bibliothèque MPI (Message Passing Interface) qui est un protocole de communication en programmation parallèle et distribuée. Outre l'introduction et la conclusion, la thèse est composée de quatre chapitres. Le chapitre 1 concerne les outils théoriques et algorithmiques comme servant de base méthodologique aux chapitres suivants. Le chapitre 2 s'articule autour les problèmes linéaires à variables mixtes binaires. Pour la résolution de ces problèmes, nous proposons une approche coopérative entre DCA et VNS (Variable Neighborhood Search). Puisque le schéma est constitué de deux algorithmes, nous optons pour la communication point à point entre les processus. Nous adaptons notre schéma pour résoudre le problème de localisation de l'installation avec des contraintes de capacités. Dans le chapitre 3, nous étudions la programmation quadratique à variables binaires. Nous développons une coopération entre DCA-Like (une nouvelle version de DCA) et deux autres métaheuristiques : GA (Genetic Algorithm) et MBO (Migrating Birds Optimization). Pour la communication entre les processus, nous utilisons la communication collective. Plus précisément une fonction qui permet la diffusion simultanée l'information d'un processus à tous les autres. Cette approche est adaptée et appliquée au problème d'affectation quadratique. Dans le chapitre 4, nous résolvons les problèmes de "clustering" via la minimisation de la somme des carrés par deux approches coopératives. La première consiste à combiner le DCA avec VNS et TS (Tabu Search). Quant à la deuxième, elle utilise la MBO avec les trois derniers algorithmes précités. Dans ces deux approches, nous utilisons une fonction de communication qui permet au processus d'accéder aux mémoires des autres et y enregistrer son information sans un temps d'attente
In this thesis, we are interested in developing new cooperative approaches for solving some classes of nonconvex problems which play a very important role to model real-world problems. To design the schemes of our approaches, we combine several algorithms which we call the component (participant) algorithms. The combination is mainly based on DC (Difference of Convex Functions) and DCA (DC Algorithm) with metaheuristics. To develop our solution methods, we use the paradigm of parallel and distributed programming. Therefore, each process deals with an algorithm and communicates with the others by calling the functions of the MPI (Message Passing Interface) library which is a communication protocol in parallel and distributed programming. Besides the introduction and conclusion, this thesis is composed of four chapters. Chapter 1 concerns the theoretical and algorithmic tools serving as a methodological basis for the following chapters. Chapter 2 is about the mixed binary linear programs. To solve these problems, we propose a cooperative approach between DCA and VNS (Variable Neighborhood Search). Since the scheme is constituted by two algorithms, we use the point to point communication between the processes. As an application, we adapt our scheme to solve the capacitated facility location problem. Concerning chapter 3, we study the class of binary quadratic problems. Regarding the solution methods, we develop a cooperation between DCA-like which is a new version of DCA and two other metaheuristics: GA (Genetic Algorithm) and MBO (Migrating Birds Optimization). The exchange of information between the processes is expressed by using collective communication's function. More precisely, we call a function which allows broadcasting information of a process to all the others at the same time. This cooperative approach is adapted to the quadratic assignment problem. In chapter 4, we solve the MSSC (Minimum-Sum-of-Squares Clustering) using two cooperative approaches. The first combines DCA, VNS, and TS (Tabu Search). As for the second, it combines the MBO with the other three algorithms cited before. In these two approaches, we use a function of communication that allows a process to access the memories of the others and save the information there without blocking the work of the receiving processes

La présente thèse a pour objectif principal de développer des approches déterministes et heuristiques pour résoudre certaines classes de problèmes d'optimisation en Finance, Affectation et Recherche d’Informations. Il s’agit des problèmes d’optimisation non convexe de grande dimension. Nos approches sont basées sur la programmation DC&DCA et la méthode Cross-Entropy (CE). Grâce aux techniques de formulation/reformulation, nous avons donné la formulation DC des problèmes considérés afin d’obtenir leurs solutions en utilisant DCA. En outre, selon la structure des ensembles réalisables de problèmes considérés, nous avons conçu des familles appropriées de distributions pour que la méthode Cross-Entropy puisse être appliquée efficacement. Toutes ces méthodes proposées ont été mises en œuvre avec MATLAB, C/C++ pour confirmer les aspects pratiques et enrichir notre activité de recherche
In this thesis we focus on developing deterministic and heuristic approaches for solving some classes of optimization problems in Finance, Assignment and Search Information. They are large-scale nonconvex optimization problems. Our approaches are based on DC programming & DCA and the Cross-Entropy method. Due to the techniques of formulation/reformulation, we have given the DC formulation of considered problems such that we can use DCA to obtain their solutions. Also, depending on the structure of feasible sets of considered problems, we have designed appropriate families of distributions such that the Cross-Entropy method could be applied efficiently. All these proposed methods have been implemented with MATLAB, C/C++ to confirm the practical aspects and enrich our research works

Cette thèse est particulièrement destinée à traiter deux types de problèmes : clustering et l'alignement multiple de séquence. Notre objectif est de résoudre de manière satisfaisante ces problèmes globaux et de tester l'approche de la Programmation DC et DCA sur des jeux de données réelles. La thèse comporte trois parties : la première partie est consacrée aux nouvelles approches de l'optimisation non convexe. Nous y présentons une étude en profondeur de l'algorithme qui est utilisé dans cette thèse, à savoir la programmation DC et l'algorithme DC (DCA). Dans la deuxième partie, nous allons modéliser le problème clustering en trois sous-problèmes non convexes. Les deux premiers sous-problèmes se distinguent par rapport au choix de la norme utilisée, (clustering via les normes 1 et 2). Le troisième sous-problème utilise la méthode du noyau, (clustering via la méthode du noyau). La troisième partie sera consacrée à la bio-informatique. On va se focaliser sur la modélisation et la résolution de deux sous-problèmes : l'alignement multiple de séquence et l'alignement de séquence d'ARN par structure. Tous les chapitres excepté le premier se terminent par des tests numériques
This Ph.D. thesis is particularly intended to treat two types of problems : clustering and the multiple alignment of sequence. Our objective is to solve efficiently these global problems and to test DC Programming approach and DCA on real datasets. The thesis is divided into three parts : the first part is devoted to the new approaches of nonconvex optimization-global optimization. We present it a study in depth of the algorithm which is used in this thesis, namely the programming DC and the algorithm DC ( DCA). In the second part, we will model the problem clustering in three nonconvex subproblems. The first two subproblems are distinguished compared to the choice from the norm used, (clustering via norm 1 and 2). The third subproblem uses the method of the kernel, (clustering via the method of the kernel). The third part will be devoted to bioinformatics, one goes this focused on the modeling and the resolution of two subproblems : the multiple alignment of sequence and the alignment of sequence of RNA. All the chapters except the first end in numerical tests