Le travail général de cette thèse consiste à étendre les outils analytiques et algébriques usuellement employés dans la résolution de problèmes combinatoires déterministes à un cadre combinatoire stochastique. Deux cadres distincts sont étudiés : les problèmes combinatoires stochastiques discrets et les problèmes stochastiques continus. Le cadre discret est abordé à travers le problème de la forêt couvrante de poids maximal dans une formulation Two-Stage à multi-scénarios. La version déterministe très connue de ce problème établit des liens entre la fonction de rang dans un matroïde et la formulation duale, via l'algorithme glouton. La formulation stochastique discrète du problème de la forêt maximale couvrante est transformée en un problème déterministe équivalent, mais du fait de la multiplicité des scénarios, le dual associé est en quelque sorte incomplet. Le travail réalisé ici consiste à comprendre en quelles circonstances la formulation duale atteint néanmoins un minimum égal au problème primal intégral. D'ordinaire, une approche combinatoire classique des problèmes de graphes pondérés consiste à rechercher des configurations particulières au sein des graphes, comme les circuits, et à explorer d'éventuelles recombinaisons. Pour donner une illustration simple, si on change d'une manière infinitésimale les valeurs de poids des arêtes d'un graphe, il est possible que la forêt couvrante de poids maximal se réorganise complètement. Ceci est vu comme un obstacle dans une approche purement combinatoire. Pourtant, certaines grandeurs analytiques vont varier de manière continue en fonction de ces variations infinitésimales, comme la somme des poids des arêtes choisies. Nous introduisons des fonctions qui rendent compte de ces variations continues, et nous examinons dans quels cas les formulations duales atteignent la même valeur que les formulations primales intégrales. Nous proposons une méthode d'approximation dans le cas contraire et nous statuons sur la NP complétude de ce type de problème.Les problèmes stochastiques continus sont abordés via le problème de sac à dos avec contrainte stochastique. La formulation est de type ''chance constraint'', et la dualisation par variable lagrangienne est adaptée à une situation où la probabilité de respecter la contrainte doit rester proche de $1$. Le modèle étudié est celui d'un sac à dos où les objets ont une valeur et un poids déterminés par des distributions normales. Dans notre approche, nous nous attachons à appliquer des méthodes de gradient directement sur la formulation en espérance de la fonction objectif et de la contrainte. Nous délaissons donc une possible reformulation classique du problème sous forme géométrique pour détailler les conditions de convergence de la méthode du gradient stochastique. Cette partie est illustrée par des tests numériques de comparaison avec la méthode SOCP sur des instances combinatoires avec méthode de Branch and Bound, et sur des instances relaxées.

Nous étudions la convergence de systèmes dynamiques vers des équilibres. En particulier, nous nous intéressons à deux types d'équilibres. D'une part, les solutions d'inéquations variationnelles sous contraintes qui interviennent aussi dans la résolution de problèmes d'optimisation hiérarchique. D'autre part l'état stable d'un système dynamique, c'est à dire l'état où l'énergie du système est nulle. Cette thèse est divisée en deux parties principales, chacune focalisée sur la recherche d'un de ces équilibres. Dans la première partie nous étudions une classe d'algorithmes explicite-implicites pour résoudre certaines inéquations variationnelles sous contraintes. Nous introduisons un algorithme proximal-gradient pénalisé, "splitting forward-backward penalty scheme". Ensuite, nous prouvons sa convergence ergodique faible vers un équilibre dans le cas général d'un opérateur maximal monotone, et sa convergence forte vers l'unique équilibre si l'opérateur est de plus fortement monotone. Nous appliquons aussi notre algorithme pour résoudre des problèmes d'optimisation sous contrainte ou hiérarchique dont les fonctions objectif et de pénalisation sont formées d'une partie lisse et d'une autre non lisse. En effet, nous démontrons la convergence faible de l'algorithme vers un optimum hiérarchique lorsque l'opérateur est le sous-différentiel d'une fonction convexe semi-continue inférieurement et propre. Nous généralisons ainsi plusieurs algorithmes connus et nous retrouvons leurs résultats de convergence en affaiblissant les hypothèses utilisées dans nombre d'entre eux.Dans la deuxième partie, nous étudions l'action d'un contrôle interne local sur la stabilisation indirecte d'un système dynamique couplé formé de trois équations d'ondes, le système de Bresse. Sous la condition d'égalité des vitesses de propagation des ondes, nous montrons la stabilité exponentielle du système. En revanche, quand les vitesses sont différentes, nous prouvons sa stabilité polynomiale et nous établissons un nouveau taux de décroissance polynomial de l'énergie. Ceci étend des résultats présents dans la littérature au sens où le contrôle est localement distribué (et non pas appliqué à tout le domaine) et nous améliorons le taux de décroissance polynomial de l'énergie pour des conditions au bord de type Dirichlet et Dirichlet-Neumann. / We study the convergence of dynamical systems towards equilibria. In particular, we are interested in two types of equilibria. On one hand solutions of constrained variational inequations that are also involved in the resolution of hierarchical optimization problems. On the other hand the stable state of a dynamical system, i.e. the state when the energy of the system is zero. The thesis is divided into two parts, each focused on one of these equilibria. In the first part, we study a class of forward-backward algorithms for solving constrained variational inequalities. We consider a splitting forward-backward penalty scheme. We prove the weak ergodic convergence of the algorithm to an equilibrium for a general maximal monotone operator, and the strong convergence to the unique equilibrium if the operator is an addition strongly monotone. We also apply our algorithm for solving constrained or hierarchical optimization problems whose objective and penalization functions are formed of a smooth and a non-smooth part. In fact, we show the weak convergence to a hierarchical optimum when the operator is the subdifferential of a closed convex proper function. We then generalize several known algorithms and we find their convergence results by weakening assumptions used in a number of them. In the second part, we study the action of a locally internal dissipation law in the stabilization of a linear dynamical system coupling three wave equations, the Bresse system. Under the equal speed wave propagation condition we show that the system is exponentially stable. Otherwise, when the speeds are different, we prove the polynomial stability and establish a new polynomial energy decay rate. This extends results presented in the literature in the sense that the dissipation law is locally distributed (and not applied in the whole domain) and we improve the polynomial energy decay rate with both types of boundary conditions, Dirichlet and Dirichlet-Neumann.

Le travail général de cette thèse consiste à étendre les outils analytiques et algébriques usuellement employés dans la résolution de problèmes combinatoires déterministes à un cadre combinatoire stochastique. Deux cadres distincts sont étudiés : les problèmes combinatoires stochastiques discrets et les problèmes stochastiques continus. Le cadre discret est abordé à travers le problème de la forêt couvrante de poids maximal dans une formulation Two-Stage à multi-scénarios. La version déterministe très connue de ce problème établit des liens entre la fonction de rang dans un matroïde et la formulation duale, via l'algorithme glouton. La formulation stochastique discrète du problème de la forêt maximale couvrante est transformée en un problème déterministe équivalent, mais du fait de la multiplicité des scénarios, le dual associé est en quelque sorte incomplet. Le travail réalisé ici consiste à comprendre en quelles circonstances la formulation duale atteint néanmoins un minimum égal au problème primal intégral. D'ordinaire, une approche combinatoire classique des problèmes de graphes pondérés consiste à rechercher des configurations particulières au sein des graphes, comme les circuits, et à explorer d'éventuelles recombinaisons. Pour donner une illustration simple, si on change d'une manière infinitésimale les valeurs de poids des arêtes d'un graphe, il est possible que la forêt couvrante de poids maximal se réorganise complètement. Ceci est vu comme un obstacle dans une approche purement combinatoire. Pourtant, certaines grandeurs analytiques vont varier de manière continue en fonction de ces variations infinitésimales, comme la somme des poids des arêtes choisies. Nous introduisons des fonctions qui rendent compte de ces variations continues, et nous examinons dans quels cas les formulations duales atteignent la même valeur que les formulations primales intégrales. Nous proposons une méthode d'approximation dans le cas contraire et nous statuons sur la NP complétude de ce type de problème.Les problèmes stochastiques continus sont abordés via le problème de sac à dos avec contrainte stochastique. La formulation est de type ``chance constraint'', et la dualisation par variable lagrangienne est adaptée à une situation où la probabilité de respecter la contrainte doit rester proche de $1$. Le modèle étudié est celui d'un sac à dos où les objets ont une valeur et un poids déterminés par des distributions normales. Dans notre approche, nous nous attachons à appliquer des méthodes de gradient directement sur la formulation en espérance de la fonction objectif et de la contrainte. Nous délaissons donc une possible reformulation classique du problème sous forme géométrique pour détailler les conditions de convergence de la méthode du gradient stochastique. Cette partie est illustrée par des tests numériques de comparaison avec la méthode SOCP sur des instances combinatoires avec méthode de Branch and Bound, et sur des instances relaxées. / The global purpose of this thesis is to study the conditions to extend analytical and algebraical properties commonly observed in the resolution of deterministic combinatorial problems to the corresponding stochastic formulations of these problems. Two distinct situations are treated : discrete combinatorial stochastic problems and continuous stochastic problems. Discrete situation is examined with the Two Stage formulation of the Maximum Weight Covering Forest. The well known corresponding deterministic formulation shows the connexions between the rank function of a matroid, the greedy algorithm , and the dual formulation. The discrete stochastic formulation of the Maximal Covering Forest is turned into a deterministic equivalent formulation, but, due to the number of scenarios, the associated dual is not complete. The work of this thesis leads to understand in which cases the dual formulation still has the same value as the primal integer formulation. Usually, classical combinatorial approaches aim to find particular configurations in the graph, as circuits, in order to handle possible reconfigurations. For example, slight modifications of the weights of the edges might change considerably the configuration of the Maximum Weight Covering Forest. This can be seen as an obstacle to handle pure combinatorial proofs. However, some global relevant quantities, like the global weight of the selected edges during the greedy algorithm, have a continuous variation in function of slight modifications. We introduce some functions in order to outline these continuous variations. And we state in which cases Primal integral problems have the same objective values as dual formulations. When it is not the case, we propose an approximation method and we examine the NP completeness of this problem.Continuous stochastic problems are presented with the stochastic Knapsack with chance constraint. Chance constraint and dual Lagrangian formulation are adapted in the case where the expected probability of not exceeding the knapsack capacity is close to $1$. The introduced model consists in items whose costs and rewards follow normal distributions. In our case, we try to apply direct gradient methods without reformulating the problem into geometrical terms. We detail convergence conditions of gradient based methods directly on the initial formulation. This part is illustrated with numerical tests on combinatorial instances and Branch and Bound evaluations on relaxed formulations.

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières. / In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs.

Concorder un modèle à certaines observations, voilà qui résume assez bien ce que l’apprentissage machine cherche à accomplir. Ce concept est maintenant omniprésent dans nos vies, entre autre grâce aux percées récentes en apprentissage profond. La stratégie d’optimisation prédominante pour ces deux domaines est la minimisation d’un objectif donné. Et pour cela, la méthode du gradient, méthode de premier-ordre qui modifie les paramètres du modèle à chaque itération, est l’approche dominante. À l’opposé, les méthodes dites de second ordre n’ont jamais réussi à s’imposer en apprentissage profond. Pourtant, elles offrent des avantages reconnus qui soulèvent encore un grand intérêt. D’où l’importance de la méthode du col, qui unifie les méthodes de premier et second ordre sous un même paradigme. Dans ce mémoire, nous établissons un parralèle direct entre la méthode du col et le domaine du contrôle optimal ; domaine qui cherche à optimiser mathématiquement une séquence de décisions. Et certains des problèmes les mieux compris et étudiés en contrôle optimal sont les commandes linéaires quadratiques. Problèmes pour lesquels on connaît très bien la solution optimale. Plus spécifiquement, nous démontrerons l’équivalence entre une itération de la méthode du col et la résolution d’une Commande Linéaire Quadratique (CLQ). Cet éclairage nouveau implique une approche unifiée quand vient le temps de déployer nombre d’algorithmes issus de la méthode du col, tel que la méthode du gradient et celle des gradients naturels, sans être limitée à ceux-ci. Approche que nous étendons ensuite aux problèmes à horizon infini, tel que les modèles à équilibre profond. Ce faisant, nous démontrons pour ces problèmes que calculer les gradients via la différentiation implicite revient à employer l’équation de Riccati pour solutionner la CLQ associée à la méthode du gradient. Finalement, notons que l’incorporation d’information sur la courbure du problème revient généralement à rencontrer une inversion matricielle dans la méthode du col. Nous montrons que l’équivalence avec les CLQ permet de contourner cette inversion en utilisant une approximation issue des séries de Neumann. Surprenamment, certaines observations empiriques suggèrent que cette approximation aide aussi à stabiliser le processus d’optimisation quand des méthodes de second-ordre sont impliquées ; en agissant comme un régularisateur adaptif implicite. / Machine learning entails training a model to fit some given observations, and recent advances in the field, particularly in deep learning, have made it omnipresent in our lives. Fitting a model usually requires the minimization of a given objective. When it comes to deep learning, first-order methods like gradient descent have become a default tool for optimization in deep learning. On the other hand, second-order methods did not see widespread use in deep learning. Yet, they hold many promises and are still a very active field of research. An important perspective into both methods is steepest descent, which allows you to encompass first and second-order approaches into the same framework. In this thesis, we establish an explicit connection between steepest descent and optimal control, a field that tries to optimize sequential decision-making processes. Core to it is the family of problems known as Linear Quadratic Regulation; problems that have been well studied and for which we know optimal solutions. More specifically, we show that performing one iteration of steepest descent is equivalent to solving a Linear Quadratic Regulator (LQR). This perspective gives us a convenient and unified framework for deploying a wide range of steepest descent algorithms, such as gradient descent and natural gradient descent, but certainly not limited to. This framework can also be extended to problems with an infinite horizon, such as deep equilibrium models. Doing so reveals that retrieving the gradient via implicit differentiation is equivalent to recovering it via Riccati’s solution to the LQR associated with gradient descent. Finally, incorporating curvature information into steepest descent usually takes the form of a matrix inversion. However, casting a steepest descent step as a LQR also hints toward a trick that allows to sidestep this inversion, by leveraging Neumann’s series approximation. Empirical observations provide evidence that this approximation actually helps to stabilize the training process, by acting as an adaptive damping parameter.

Au cours de la dernière décennie, l'apprentissage profond est devenu une composante majeure de l'intelligence artificielle, ayant mené à une série d'avancées capitales dans une variété de domaines. L'un des piliers de l'apprentissage profond est l'optimisation de fonction de coût par l'algorithme du gradient stochastique (SGD). Traditionnellement en apprentissage profond, les réseaux de neurones sont des fonctions mathématiques différentiables, et les gradients requis pour l'algorithme SGD sont calculés par rétropropagation. Cependant, les architectures informatiques sur lesquelles ces réseaux de neurones sont implémentés et entraînés souffrent d’inefficacités en vitesse et en énergie, dues à la séparation de la mémoire et des calculs dans ces architectures. Pour résoudre ces problèmes, le neuromorphique vise à implementer les réseaux de neurones dans des architectures qui fusionnent mémoire et calculs, imitant plus fidèlement le cerveau. Dans cette thèse, nous soutenons que pour construire efficacement des réseaux de neurones dans des architectures neuromorphiques, il est nécessaire de repenser les algorithmes pour les implémenter et les entraîner. Nous présentons un cadre mathématique alternative, compatible lui aussi avec l’algorithme SGD, qui permet de concevoir des réseaux de neurones dans des substrats qui exploitent mieux les lois de la physique. Notre cadre mathématique s'applique à une très large classe de modèles, à savoir les systèmes dont l'état ou la dynamique sont décrits par des équations variationnelles. La procédure pour calculer les gradients de la fonction de coût dans de tels systèmes (qui dans de nombreux cas pratiques ne nécessite que de l'information locale pour chaque paramètre) est appelée “equilibrium propagation” (EqProp). Comme beaucoup de systèmes en physique et en ingénierie peuvent être décrits par des principes variationnels, notre cadre mathématique peut potentiellement s'appliquer à une grande variété de systèmes physiques, dont les applications vont au delà du neuromorphique et touchent divers champs d'ingénierie. / In the last decade, deep learning has become a major component of artificial intelligence, leading to a series of breakthroughs across a wide variety of domains. The workhorse of deep learning is the optimization of loss functions by stochastic gradient descent (SGD). Traditionally in deep learning, neural networks are differentiable mathematical functions, and the loss gradients required for SGD are computed with the backpropagation algorithm. However, the computer architectures on which these neural networks are implemented and trained suffer from speed and energy inefficiency issues, due to the separation of memory and processing in these architectures. To solve these problems, the field of neuromorphic computing aims at implementing neural networks on hardware architectures that merge memory and processing, just like brains do. In this thesis, we argue that building large, fast and efficient neural networks on neuromorphic architectures also requires rethinking the algorithms to implement and train them. We present an alternative mathematical framework, also compatible with SGD, which offers the possibility to design neural networks in substrates that directly exploit the laws of physics. Our framework applies to a very broad class of models, namely those whose state or dynamics are described by variational equations. This includes physical systems whose equilibrium state minimizes an energy function, and physical systems whose trajectory minimizes an action functional (principle of least action). We present a simple procedure to compute the loss gradients in such systems, called equilibrium propagation (EqProp), which requires solely locally available information for each trainable parameter. Since many models in physics and engineering can be described by variational principles, our framework has the potential to be applied to a broad variety of physical systems, whose applications extend to various fields of engineering, beyond neuromorphic computing.