La plupart des travaux de recherches sur les problèmes d'ordonnancement traitent le cas des ressources renouvelables, c'est-à-dire des ressources qui sont exigées en début d'exécution de chaque tâche et sont restituées en fin d'exécution. Peu d'entre eux abordent les problèmes à ressources consommables, c'est-à-dire des ressources non restituées en fin d'exécution. Le problème de gestion de projet à contraintes de ressources (RCPSP) est le problème à ressources renouvelables le plus traité dans la littérature. Dans le cadre de cette thèse, nous nous sommes intéressés à une généralisation du problème RCPSP qui correspond au cas où les tâches sont remplacées par des événements liés par des relations de précédence étendues. Chaque événement peut produire ou consommer une quantité de ressources à sa date d'occurrence et la fonction économique reste la durée totale à minimiser. Nous avons nommé cette généralisation ERCPSP (Extended RCPSP). Nous avons élaboré des modèles de programmation linéaire pour résoudre ce problème. Nous avons proposé plusieurs bornes inférieures algorithmiques exploitant les travaux de la littérature sur les problèmes cumulatifs. Ensuite, nous avons élargi la portée des méthodes utilisées pour la mise en place de méthodes de séparation et évaluation. Nous avons traité aussi des cas particuliers par des méthodes basées sur la programmation dynamique. / This thesis investigates the Extended Resource Constrained Project Scheduling Problem (ERCPSP). ERCPSP is a general scheduling problem where the availability of a resource is depleted and replenished at the occurrence times of a set of events. It is an extension of the Resource Constrained Project Scheduling Problem (RCPSP) where activities are replaced by events, which have to be scheduled subject to generalized precedence relations. We are interested in this thesis in proposing new methodologies and approaches to solve ERCPSP. First, we study some polynomial cases of this problem and we propose a dynamic programming algorithm to solve the parallel chain case. Then, we propose lower bounds, mixed integer programming models, and a branch-and-bound method to solve ERCPSP. Finally, we develop an instance generator dedicated to this problem.

La première partie de cette thèse introduit de nouveaux algorithmes de décomposition parcimonieuse de signaux. Basés sur Matching Pursuit (MP) ils répondent au problème suivant : comment réduire le temps de calcul de l'étape de sélection de MP, souvent très coûteuse. En réponse, nous sous-échantillonnons le dictionnaire à chaque itération, en lignes et en colonnes. Nous montrons que cette approche fondée théoriquement affiche de bons résultats en pratique. Nous proposons ensuite un algorithme itératif de descente de gradient par blocs de coordonnées pour sélectionner des caractéristiques en classification multi-classes. Celui-ci s'appuie sur l'utilisation de codes correcteurs d'erreurs transformant le problème en un problème de représentation parcimonieuse simultanée de signaux. La deuxième partie expose de nouvelles inégalités de concentration empiriques de type Bernstein. En premier, elles concernent la théorie des U-statistiques et sont utilisées pour élaborer des bornes en généralisation dans le cadre d'algorithmes de ranking. Ces bornes tirent parti d'un estimateur de variance pour lequel nous proposons un algorithme de calcul efficace. Ensuite, nous présentons une version empirique de l'inégalité de type Bernstein proposée par Freedman [1975] pour les martingales. Ici encore, la force de notre borne réside dans l'introduction d'un estimateur de variance calculable à partir des données. Cela nous permet de proposer des bornes en généralisation pour l'ensemble des algorithmes d'apprentissage en ligne améliorant l'état de l'art et ouvrant la porte à une nouvelle famille d'algorithmes d'apprentissage tirant parti de cette information empirique. / The first part of this thesis introduces new algorithms for the sparse encoding of signals. Based on Matching Pursuit (MP) they focus on the following problem : how to reduce the computation time of the selection step of MP. As an answer, we sub-sample the dictionary in line and column at each iteration. We show that this theoretically grounded approach has good empirical performances. We then propose a bloc coordinate gradient descent algorithm for feature selection problems in the multiclass classification setting. Thanks to the use of error-correcting output codes, this task can be seen as a simultaneous sparse encoding of signals problem. The second part exposes new empirical Bernstein inequalities. Firstly, they concern the theory of the U-Statistics and are applied in order to design generalization bounds for ranking algorithms. These bounds take advantage of a variance estimator and we propose an efficient algorithm to compute it. Then, we present an empirical version of the Bernstein type inequality for martingales by Freedman [1975]. Again, the strength of our result lies in the variance estimator computable from the data. This allows us to propose generalization bounds for online learning algorithms which improve the state of the art and pave the way to a new family of learning algorithms taking advantage of this empirical information.

Cette thèse est dédié à l’étude de la problématique des interférences multi utilisateurs dans le système Argos et à la proposition des diverses techniques pour réduire les effets de ces interférences. Le système Argos est un système mondial de localisation et de collecte de données géo positionnées par satellite. Il permet à l’échelle mondiale de collecter et de traiter les données émises par des émetteurs installés sur la surface de terre. Ces émetteurs sont connus sous le nom de balises. Ces balises sont installées sur des voiliers, des stations météo, des bouées, ainsi que sur quelques animaux (phoques, penguins, etc.…). Le système Argos a été créé en 1978 par le Centre National des Études spatiales (CNES), l’agence spatiale américaine (NASA) et l’agence américaine d’étude de l’atmosphère et de l’océan (NOAA). Depuis sa création, le nombre de balises Argos n’a cessé d’augmenter afin de couvrir au mieux la couverture mondiale. Nous sommes orientés ainsi à la saturation de la bande d’émission et à la présence des interférences multi utilisateurs (MUI) provenant de la réception simultanée de plusieurs signaux émis par les balises. Cette MUI limite la capacité du système Argos et dégrade les performances en termes de Taux Erreur Bit (TEB). Actuellement, le système Argos n’est capable de traiter qu’un seul signal reçu à un instant donné. D’où, l’intérêt d’implanter des techniques au niveau du récepteur capable de réduire les effets des interférences et de traiter les signaux émis par toutes les balises. Plusieurs techniques de détection multi utilisateurs (MUD) ont été développées dans le cadre de cette problématique. Ces techniques sont principalement implantées dans les systèmes CDMA où des codes d’étalement sont utilisés afin de différencier entre les différents signaux. Ceci n’est pas le cas du système Argos où les signaux ne présentent pas des séquences d’étalement et que les bandes de fréquences pour ces différents signaux ne sont pas disjointes à cause de l’effet Doppler et donc, un recouvrement spectral au niveau du récepteur est très probable. Dans ce contexte, l’objectif du travail présenté dans cette thèse est d’étudier différentes techniques MUD appliquées au système Argos et d’évaluer ces techniques au niveau des performances en termes de TEB et de complexité d’implantation. Dans ce travail, nous présentons les différentes composantes du système Argos ainsi que son mode de fonctionnement. Ensuite, nous présentons la problématique dans le système Argos ainsi que les différentes solutions proposées. Parmi ces solutions, nous montrons celle basant sur l’implantation des techniques MUD au niveau du récepteur. Ces différentes techniques MUD sont alors présentées ainsi que les avantages et les inconvénients de chacune d’elles. Parmi les techniques possédant un bon compromis entre les performances d’une part et la complexité d’autre part, nous notons la technique d’annulation par série d’interférence (SIC). Dans cette technique, les signaux sont démodulés successivement suivant l’ordre décroissant des puissances. Cette technique nécessite une étape d’estimation des paramètres des signaux à chaque étape. L’impact d’une estimation imparfaite des différents paramètres est aussi étudié. Après l’étude des impacts des erreurs d’estimation, nous proposons des estimateurs adaptables au système Argos. Les performances de ces estimateurs sont obtenues en comparant les variances de leurs erreurs aux bornes de Cramer Rao (CRB). Enfin, nous terminons le travail par une conclusion générale des résultats obtenus et nous envisageons les perspectives des prochains travaux. / In our thesis, we investigate the application of multi user detection techniques to a Low Polar Orbit (LPO) satellite used in the Argos system. Argos is a global satellite-based location and data collection system dedicated for studying and protecting the environment. User platforms, each equipped with a Platform Transmitter Terminal (PTT), transmit data messages to a 850 km LPO satellite. An ARGOS satellite receives, decodes, and forwards the signals to ground stations. All PTTs transmit at random times in a 100 kHz bandwidth using different carrier frequencies. The central carrier frequency f0 is 401.65 MHz. Due to the relative motion between the satellite and the platforms, signals transmitted by PTTs are affected by both a different Doppler shift and a different propagation delay. Thus, the Argos satellite receives overlapping signals in both frequency and time domains inducing Multiple Access Interference (MAI). One common approach to mitigate the MAI problem is to implement Multi User Detection (MUD) techniques at the receiver. To tackle this problem, several MUD techniques have been proposed for the reception of synchronous and asynchronous users. In particular, the Successive Interference Cancelation (SIC) detector has been shown to offer a good optimality-complexity trade-off compared to other common approaches such as the Maximum Likelihood (ML) receiver. In an Argos SIC receiver, users are decoded in a successive manner, and the signals of successfully decoded users are subtracted from the waveform before decoding the next user. This procedure involves a parameter estimation step and the impact of erroneous parameter estimates on the performance of Argos SIC receiver has been studied. Argos SIC receiver has been shown to be both robust to imperfect amplitude and phase estimation and sensitive to imperfect time delay estimation. The last part of our work focuses on the implementation of digital estimators for the Argos system. In particular, we propose a time delay estimator, a frequency estimator, a phase estimator and an amplitude estimator. These estimators are derived from the ML principle and they have been already derived for the single user transmission. In our work, we adapt successfully these estimators for the multi user detector case. These estimators use the Non Data Aided (NDA) cases in which no a priori information for the transmitted bits is required. The performance of these different estimators are compared to the Cramer Rao Bound (CRB) values. Finally, we conclude in our work by showing the different results obtained during this dissertation. Also, we give some perspectives for future work on Argos system.

Cette thèse a pour objet la résolution exacte d’un problème d’optimisation des flux de puissance (OPF) dans un réseau électrique. Dans l’OPF, on doit planifier la production et la répartition des flux de puissances électriques permettant de couvrir, à un coût minimal, la consommation en différents points du réseau. Trois variantes du problème de l’OPF sont étudiées dans ce manuscrit. Nous nous concentrerons principalement sur la résolution exacte des deux problèmes (OPF − L) et (OPF − Q), puis nous montrerons comment notre approche peut naturellement s’´étendre à la troisième variante (OPF − UC). Cette thèse propose de résoudre ces derniers à l’aide d’une méthode de reformulation que l’on appelle RC-OPF. La contribution principale de cette thèse réside dans l’étude, le développement et l’utilisation de notre méthode de résolution exacte RC-OPF sur les trois variantes d’OPF. RC-OPF utilise également des techniques de contractions de bornes, et nous montrons comment ces techniques classiques peuvent être renforcées en utilisant des résultats issus de notre reformulation optimale. / Alternative Current Optimal Power Flow (ACOPF) is naturally formulated as a non-convex problem. In that context, solving (ACOPF) to global optimality remains a challenge when classic convex relaxations are not exact. We use semidefinite programming to build a quadratic convex relaxation of (ACOPF). We show that this quadratic convex relaxation has the same optimal value as the classical semidefinite relaxation of (ACOPF) which is known to be tight. In that context, we build a spatial branch-and-bound algorithm to solve (ACOPF) to global optimality that is based on a quadratic convex programming bound.

Une qualité de service uniforme pour les utilisateurs mobiles et une utilisation distribuée du spectre représentent les ingrédients clés des réseaux cellulaires de prochaine génération. Dans ce but, la coopération au niveau de la couche physique entre les nœuds de l’infrastructure et les nœuds du réseau sans fil a émergé comme une technique à fort potentiel. La coopération s’appuie sur les propriétés de diffusion du canal sans fil, c’est-à-dire que la même transmission peut être entendue par plusieurs nœuds, ouvrant ainsi la possibilité pour les nœuds de s’aider à transmettre les messages à leur destination finale. La coopération promet aussi d’offrir une façon nouvelle et intelligente de gérer les interférences, au lieu de simplement les ignorer et les traiter comme du bruit. Comprendre comment concevoir ces systèmes radio coopératifs, afin que les ressources disponibles soient pleinement utilisées, est d’une importance fondamentale. L’objectif de cette thèse est de mener une étude du point de vue de la théorie de l’information, pour des systèmes sans fil pertinents dans la pratique, où les nœuds de l’infrastructure coopèrent en essayant d’améliorer les performances du réseau. Les systèmes radio avec des relais semi-duplex ainsi que les scénarios où une station de base aide à servir les utilisateurs mobiles associés à une autre station de base, sont les réseaux sans fil coopératifs étudiés dans cette thèse. Le but principal est la progression vers la caractérisation de la capacité de ces systèmes sans fil au moyen de dérivation de nouvelles bornes supérieures pour les performances et la conception de nouvelles stratégies de transmission permettant de les atteindre. / A uniform mobile user quality of service and a distributed use of the spectrum represent the key-ingredients for next generation cellular networks. Toward this end, physical layer cooperation among the network infrastructure and the wireless nodes has emerged as a potential technique. Cooperation leverages the broadcast nature of the wireless medium, that is, the same transmission can be heard by multiple nodes, thus opening up the possibility that nodes help one another to convey the messages to their intended destination. Cooperation also promises to offer novel and smart ways to manage interference, instead of just simply disregarding it and treating it as noise. Understanding how to properly design such cooperative wireless systems so that the available resources are fully utilized is of fundamental importance.The objective of this thesis is to conduct an information theoretic study on practically relevant wireless systems where the network infrastructure nodes cooperate among themselves in an attempt to enhance the network performance in many critical aspects, such as throughput, robustness and coverage. Wireless systems with half-duplex relay stations as well as scenarios where a base station overhears another base station and consequently helps serving this other base station's associated mobile users, represent the wireless cooperative networks under investigation in this thesis. The prior focus is to make progress towards characterizing the capacity of such wireless systems by means of derivation of novel outer bounds and design of new provably optimal transmission strategies.

Ce travail de recherche vise à contribuer au développement de nouveaux outils d'estimation d'erreur globale et locale en ingénierie mécanique. Les estimateurs d'erreur globale étudiés reposent sur le concept d'erreur en relation de comportement à travers des techniques spécifiques de construction de champs admissibles, assurant l'aspect conservatif ou garanti de l'estimation. Une nouvelle méthode de construction de champs admissibles est mise en place et comparée à deux autres méthodes concurrentes, en matière de précision, coût de calcul et facilité d'implémentation dans les codes éléments finis. Une amélioration de cette nouvelle méthode hybride fondée sur une minimisation locale de l'énergie complémentaire est également proposée. Celle-ci conduit à l'introduction et à l'élaboration de critères géométriques et énergétiques judicieux, permettant un choix approprié des régions à sélectionner pour améliorer localement la qualité des champs admissibles. Dans le cadre des estimateurs d'erreur locale basés sur l'utilisation conjointe des outils d'extraction et des estimateurs d'erreur globale, deux nouvelles techniques d'encadrement de l'erreur en quantité d'intérêt sont proposées. Celles-ci sont basées sur le principe de Saint-Venant à travers l'emploi de propriétés spécifiques d'homothétie, afin d'améliorer la précision des bornes d'erreur locale obtenues à partir de la technique d'encadrement classique fondée sur l'inégalité de Cauchy-Schwarz. Les diverses études comparatives sont menées dans le cadre des problèmes d'élasticité linéaire en quasi-statique. Le comportement des différents estimateurs d'erreur est illustré et discuté sur des exemples numériques tirés d'applications industrielles. Les travaux réalisés constituent des éléments de réponse à la problématique de la vérification dans un contexte industriel. / This research work aims at contributing to the development of innovative global and goal-oriented error estimation tools applied to Computational Mechanics. The global error estimators considered rely on the concept of constitutive relation error through specific techniques for constructing admissible fields ensuring the recovery of strict and high-quality error estimates. A new hybrid method for constructing admissible stress fields is set up and compared to two other techniques with respect to three different criteria, namely the quality of associated error estimators, the computational cost and the simplicity of practical implementation into finite element codes. An enhanced version of this new technique based on local minimization of the complementary energy is also proposed. Judicious geometric and energetic criteria are introduced to select the relevant zones for optimizing the quality of the admissible fields locally. In the context of goal-oriented error estimation based on the use of both extraction techniques and global error estimators, two new improved bounding techniques are proposed. They lean on Saint-Venant's principle through specific homotheticity properties in order to obtain guaranteed and relevant bounds of better quality than with the classical bounding technique based on the Cauchy-Schwarz inequality. The various comparative studies are conducted on linear elasticity problems under quasi-static loading conditions. The behaviour of the different error estimators is illustrated and discussed through several numerical experiments carried out on industrial cases. The associated results may open up opportunities and help broaden the field of model verification for both academic research and industrial applications.

Dans le contexte de l'estimation paramétrique, les performances d'un estimateur peuvent être caractérisées, entre autre, par son erreur quadratique moyenne (EQM) et sa résolution limite. La première quantifie la précision des valeurs estimées et la seconde définit la capacité de l'estimateur à séparer plusieurs paramètres. Cette thèse s'intéresse d'abord à la prédiction de l'EQM "optimale" à l'aide des bornes inférieures pour des problèmes d'estimation simultanée de paramètres aléatoires et non-aléatoires (estimation hybride), puis à l'extension des bornes de Cramér-Rao pour des modèles d'observation moins standards. Enfin, la caractérisation des estimateurs en termes de résolution limite est également étudiée. Ce manuscrit est donc divisé en trois parties :Premièrement, nous complétons les résultats de littérature sur les bornes hybrides en utilisant deux bornes bayésiennes : la borne de Weiss-Weinstein et une forme particulière de la famille de bornes de Ziv-Zakaï. Nous montrons que ces bornes "étendues" sont plus précises pour la prédiction de l'EQM optimale par rapport à celles existantes dans la littérature.Deuxièmement, nous proposons des bornes de type Cramér-Rao pour des contextes d'estimation moins usuels, c'est-à-dire : (i) Lorsque les paramètres non-aléatoires sont soumis à des contraintes d'égalité linéaires ou non-linéaires (estimation sous contraintes). (ii) Pour des problèmes de filtrage à temps discret où l'évolution des états (paramètres) est régit par une chaîne de Markov. (iii) Lorsque la loi des observations est différente de la distribution réelle des données.Enfin, nous étudions la résolution et la précision des estimateurs en proposant un critère basé directement sur la distribution des estimées. Cette approche est une extension des travaux de Oh et Kashyap et de Clark pour des problèmes d'estimation de paramètres multidimensionnels. / In the parametric estimation context, estimators performances can be characterized, inter alia, by the mean square error and the resolution limit. The first quantities the accuracy of estimated values and the second defines the ability of the estimator to allow a correct resolvability. This thesis deals first with the prediction the "optimal" MSE by using lower bounds in the hybrid estimation context (i.e. when the parameter vector contains both random and non-random parameters), second with the extension of Cramér-Rao bounds for non-standard estimation problems and finally to the characterization of estimators resolution. This manuscript is then divided into three parts :First, we fill some lacks of hybrid lower bound on the MSE by using two existing Bayesian lower bounds: the Weiss-Weinstein bound and a particular form of Ziv-Zakai family lower bounds. We show that these extended lower bounds are tighter than the existing hybrid lower bounds in order to predict the optimal MSE.Second, we extend Cramer-Rao lower bounds for uncommon estimation contexts. Precisely: (i) Where the non-random parameters are subject to equality constraints (linear or nonlinear). (ii) For discrete-time filtering problems when the evolution of states are defined by a Markov chain. (iii) When the observation model differs to the real data distribution.Finally, we study the resolution of the estimators when their probability distributions are known. This approach is an extension of the work of Oh and Kashyap and the work of Clark to multi-dimensional parameters estimation problems.

Ce manuscrit est dédié à l’analyse de performances en traitement d’antenne pour l’estimation des paramètres d’intérêt à l’aide d’un réseau de capteurs. Il est divisé en deux parties :– Tout d’abord, nous présentons l’étude de certaines bornes inférieures de l’erreur quadratique moyenne liées à la localisation de sources dans le contexte champ proche. Nous utilisons la borne de Cramér-Rao pour l’étude de la zone asymptotique (notamment en terme de rapport signal à bruit avec un nombre fini d’observations). Puis, nous étudions d’autres bornes inférieures de l’erreur quadratique moyenne qui permettent de prévoir le phénomène de décrochement de l’erreur quadratique moyenne des estimateurs (on cite, par exemple, la borne de McAulay-Seidman, la borne de Hammersley-Chapman-Robbins et la borne de Fourier Cramér-Rao).– Deuxièmement, nous nous concentrons sur le concept du seuil statistique de résolution limite, c’est-à-dire, la distance minimale entre deux signaux noyés dans un bruit additif qui permet une ”correcte” estimation des paramètres. Nous présentons quelques applications bien connues en traitement d’antenne avant d’étendre les concepts existants au cas de signaux multidimensionnels. Par la suite, nous étudions la validité de notre extension en utilisant un test d’hypothèses binaire. Enfin, nous appliquons notre extension à certains modèles d’observation multidimensionnels / This manuscript concerns the performance analysis in array signal processing. It can bedivided into two parts :- First, we present the study of some lower bounds on the mean square error related to the source localization in the near eld context. Using the Cramér-Rao bound, we investigate the mean square error of the maximum likelihood estimator w.r.t. the direction of arrivals in the so-called asymptotic area (i.e., for a high signal to noise ratio with a nite number of observations.) Then, using other bounds than the Cramér-Rao bound, we predict the threshold phenomena.- Secondly, we focus on the concept of the statistical resolution limit (i.e., the minimum distance between two closely spaced signals embedded in an additive noise that allows a correct resolvability/parameter estimation.) We de ne and derive the statistical resolution limit using the Cramér-Rao bound and the hypothesis test approaches for the mono-dimensional case. Then, we extend this concept to the multidimensional case. Finally, a generalized likelihood ratio test based framework for the multidimensional statistical resolution limit is given to assess the validity of the proposed extension.

Cette thèse a pour objet l'étude des<br />propriétés statistiques d'algorithmes d'apprentissage dans le cas de<br />l'estimation de la régression et de la densité. Elle est divisée en<br />trois parties.<br /><br />La première partie consiste en une généralisation des théorèmes<br />PAC-Bayésiens, sur la classification, d'Olivier Catoni, au cas de la régression avec une fonction de perte<br />générale.<br /><br />Dans la seconde partie, on étudie plus particulièrement le cas de la<br />régression aux moindres carrés et on propose un nouvel algorithme de<br />sélection de variables. Cette méthode peut être appliquée notamment<br />au cas d'une base de fonctions orthonormales, et conduit alors à des<br />vitesses de convergence optimales, mais aussi au cas de fonctions de<br />type noyau, elle conduit alors à une variante des méthodes dites<br />"machines à vecteurs supports" (SVM).<br /><br />La troisième partie étend les résultats de la seconde au cas de<br />l'estimation de densité avec perte quadratique.

Ce travail de recherche vise à contribuer au développement de nouveaux outils d'estimation d'erreur globale et locale en ingénierie mécanique. Les estimateurs d'erreur globale étudiés reposent sur le concept d'erreur en relation de comportement à travers des techniques spécifiques de construction de champs admissibles, assurant l'aspect conservatif ou garanti de l'estimation. Une nouvelle méthode de construction de champs admissibles est mise en place et comparée à deux autres méthodes concurrentes, en matière de précision, coût de calcul et facilité d'implémentation dans les codes éléments finis. Une amélioration de cette nouvelle méthode hybride fondée sur une minimisation locale de l'énergie complémentaire est également proposée. Celle-ci conduit à l'introduction et à l'élaboration de critères géométriques et énergétiques judicieux, permettant un choix approprié des régions à sélectionner pour améliorer localement la qualité des champs admissibles. Dans le cadre des estimateurs d'erreur locale basés sur l'utilisation conjointe des outils d'extraction et des estimateurs d'erreur globale, deux nouvelles techniques d'encadrement de l'erreur en quantité d'intérêt sont proposées. Celles-ci sont basées sur le principe de Saint-Venant à travers l'emploi de propriétés spécifiques d'homothétie, afin d'améliorer la précision des bornes d'erreur locale obtenues à partir de la technique d'encadrement classique fondée sur l'inégalité de Cauchy-Schwarz. Les diverses études comparatives sont menées dans le cadre des problèmes d'élasticité linéaire en quasi-statique. Le comportement des différents estimateurs d'erreur est illustré et discuté sur des exemples numériques tirés d'applications industrielles. Les travaux réalisés constituent des éléments de réponse à la problématique de la vérification dans un contexte industriel.