Programme SMAI MODE 2018

Cet exposé s'intéresse à un modèle de jeu à champ moyen motivé par les mouvements de foule, où l'objectif de chaque agent est de sortir d'un domaine donné par une partie de son bord en temps minimal. Chaque agent est libre de se déplacer dans toutes les directions, mais sa vitesse maximale est bornée en termes de la distribution d'agents autour de sa position afin de prendre en compte des phénomènes de congestion. Dans un premier temps, nous formulerons ce jeu à champ moyen dans un cadre Lagrangien et montrerons l'existence d'un équilibre par une méthode de point fixe. Grâce à des propriétés supplémentaires de régularité des trajectoires optimales des agents obtenues par le principe du maximum de Pontryagin, nous caractériserons ensuite les équilibres à travers un système d'une équation de continuité sur la distribution d'agents couplée avec une équation de Hamilton--Jacobi sur la fonction valeur du problème de contrôle optimal de chaque agent. Nous montrerons finalement que, si la distribution des agents à l'instant initial est une mesure absolument continue à densité $L^p$, alors cette mesure reste à densité $L^p$ pour tout instant $t \geq 0$.

I will present some recent uses of game-theoretical ideas in mathematical models of cancer, in particular the incorporation of evolutionary dynamics modeling the interaction between different kinds of cells within a tumor.

In a Markov Decision Process (MDP), at each stage, knowing the current state, the decision-maker chooses an action, and receives a reward depending on the current state of the world. Then a new state is randomly drawn from a distribution depending on the action and on the past state. Many optimal payoffs concepts have been introduced to analyze the strategic aspects of MDPs with long duration: asymptotic value, uniform value, liminf average payoff criterion, limsup average payoff criterion… We provide sufficient conditions under which these concepts coincide completing previous results of Renault and Venel (2016) and Venel and Zilioto (2016).

We consider inverse problems in separable Hilbert spaces where the prior on the data is an assumption of structured sparsity. We look at a class of regularizers for which minimization algorithms identify in finite time the extended support of the original data. This is a direct consequence of a more general identification theorem, involving the mirror stratifiability of the regularizer, a notion developped recently, and based on duality arguments. As a by-product, we derive improved rates of convergence for the minimization algorithms, like a new linear rate result for the soft-thresholding algorithm in $\ell^2(\mathbb{N})$ with no assumptions. We then provide necessary and sufficient conditions for norm regularizers to be mirror stratifiable, and show its tight relationship with the geometry of the corresponding unit ball. We apply this characterization result to show that norm regularizers inducing group sparsity with overlap are not mirror-stratifiable. We then discuss how to adapt the notion of mirror-stratifiability to treat these regularizers.

Operator splitting methods have been recently concerned with inclusions problems based on composite operators made of the sum of two monotone operators, one of them associated with a linear transformation. We analyze here a general and new splitting method which indeed splits both operator proximal steps, and avoids costly numerical algebra on the linear operator. The family of algorithms induced by our generalized setting includes known methods like Chambolle-Pock primal-dual algorithm and Shefi-Teboulle’s Proximal Alternate Direction Method of Multipliers. A convergence analysis is given and separable augmented Lagrangian algorithms are derived from our scheme to solve convex optimization problems with separable structure and coupling constraints.

Nous proposons de nouvelles stratégies de redémarrage pour la méthode de descente par coordonnée accélérée. Notre contribution principale est de montrer que pour une suite bien choisie d'instants de redémarrage, la méthode redémarrée a un taux de convergence presque géométrique. Une caractéristique majeure de la méthode est qu'elle profite de la borne d'erreur quadratique locale sans utiliser explicitement sa valeur effective. Nous montrons aussi que sous l'hypothèse plus restrictive de forte convexité, un redémarrage à période fixe donne une taux de convergence géométrique, quelle que soit la période. Nous illustrons les performances de l'algorithme sur un problème de régression logistique et sur un problème de Lasso.

We consider a minimal time control problem governed by an affine system w.r.t. the control. Our aim is to study properties of the optimal synthesis in presence of a singular locus that involves a saturation point for the singular control. We show that the optimal synthesis exhibits a prior saturation point at the intersection of the singular arc and a switching curve, and we also provide qualitative properties of this curve. We highlight this phenomenon on several models arising in nuclear magnetic resonance and in bioprocesses.

Microorganisms have evolved complex strategies for controlling the distribution of available resources over cellular functions. Biotechnology aims at interfering with these strategies, so as to optimize the production of metabolites and other compounds of interest, by (re)engineering the underlying regulatory networks of the cell. The resulting reallocation of resources can be described by simple so-called self-replicator models and the maximization of the synthesis of a product of interest formulated as a dynamic optimal control problem. Motivated by recent experimental work, we are specifically interested in the maximization of metabolite production in cases where growth can be switched off through an external control signal. We study various optimal control problems for the corresponding self-replicator models by means of a combination of analytical and computational techniques. We show that the optimal solutions for biomass maximization and product maximization are very similar in the case of unlimited nutrient supply, but diverge when nutrient are limited. Moreover, external growth control overrides natural feedback growth control and leads to an optimal scheme consisting of a first phase of growth maximization followed by a second phase of product maximization. This two-phase scheme agrees with strategies that have been proposed in metabolic engineering. More generally, our work shows the potential of optimal control theory for better understanding and improving biotechnological production processes.

Dans cet exposé, nous proposons une nouvelle modélisation pour le calcul de la probabilité de collision entre deux objets sphériques en orbite autour de la Terre. Dans un premier temps, nous montrerons comment, à l'aide des mesures d'occupation, le calcul de la probabilité de collision peut se reformuler en un problème de programmation linéaire de dimension infinie dans le cône des mesures semi-définies positives (SDP), dont la valeur optimale est exactement la probabilité cherchée. Dans un second temps, nous verrons comment résoudre numériquement ce problème d'optimisation linéaire dans l'espace des mesures par la manipulation de leurs moments en construisant une hiérarchie de relaxations SDP. On construit ainsi une suite de majorants convergeant vers la probabilité de collision cherchée. Nous conclurons cet exposé par quelques tests numériques montrant les forces et les limitations de cette approche au regard de l'application visée.

The Stochastic Dual Dynamic Programming (SDDP) algorithm has become one of the main tools to address convex multistage stochastic optimal control problem. Recently a large amount of work has been devoted to improve the convergence speed of the algorithm through cut-selection and regularization, or to extend the field of applications to non-linear, integer or risk-averse problems. However one of the main downside of the algorithm remains the difficulty to give an upper bound of the optimal value, usually estimated through Monte Carlo methods and therefore difficult to use in the algorithm stopping criterion. In this paper we present a dual SDDP algorithm that yields a converging exact upper bound for the optimal value of the optimization problem. Incidently we show how to compute an alternative control policy based on an inner approximation of Bellman value functions instead of the outer approximation given by the standard SDDP algorithm. We illustrate the approach on an energy production problem involving zones of production and transportation links between the zones. The numerical experiments we carry out on this example show the effectiveness of the method.

We consider well-known decomposition techniques for multistage stochastic programming and a new scheme based on normal solutions for stabilizing iterates during the solution process. The given algorithms combine ideas from finite perturbation of convex programs and level bundle methods to regularize the so-called forward step of these decomposition methods. Numerical experiments on a hydrothermal scheduling problem indicate that our algorithms are competitive with the state-of-the-art approaches such as multistage regularized decomposition and stochastic dual dynamic programming.

We propose a data-driven method to optimize public transport schedules. Using transit data to construct scenarios that reflect the uncertainty of the system, we compute schedules that minimize the expected waiting time during transfers. We model the problem as a two-stage stochastic program and propose two equivalent formulations: a mixed integer linear program (MILP) and a mixed integer quadratic program (MIQP). The MILP version is solved exactly using a generic solver but does not scale well; whereas the MIQP has a partially separable structure that we exploit to design an efficient local search heuristic. We provide results of the two approaches and compare them to the state of the art using transit data collected from Nancy, France.

Motivés par des défis actuels (réseaux, biologie, ...) nous avons étudié des algorithmes qui peuvent être appliqués à un grand nombre de joueurs qui ont une connaissance limitée du jeu. Dans de tels jeux, les algorithmes de non regret sont largement utilisés. Ces algorithmes garantissent que la différence entre les sommes dans le temps des revenus d'un joueur et des revenus de sa meilleure stratégie est sous-linéaire. Les équilibres de Nash sont des états où aucun joueur ne bénéficierait de changer seul de stratégie. Des études récentes ont montré que la limite de la séquence de stratégies de certains types d'algorithmes de non regret peut être arbitrairement proche d'un équilibre de Nash avec une probabilité proche de $1$. Les équilibres de Nash peuvent-ils être la limite presque surement d'un algorithme de non regret ? Nous répondons positivement à cette question en analysant l'algorithme Hedge qui a la propriété de non regret. Nous nous plaçons dans le cadre d'une information imparfaite (bandit), où les joueurs ont uniquement accès à une estimation du revenu rapporté par la stratégie pure qu'ils ont joué. Nous montrons que lorsque Hedge est appliqué à des jeux de potentiel génériques, la séquence de stratégies obtenues converge vers un équilibre de Nash.

Dans cet exposé, nous considérons le problème de minimisation de la variation totale, en 2D, suivant $$ \min\{\int_{\Omega} |\nabla u| dx : u \in BV(\Omega), u=g on \partiel\Omega\}$$ (GP) où $g: \partial\Omega \mapsto \mathbb{R}$ est une fonction $L^1$ donnée et $\Omega \subset \mathbb{R}^2$ est un domaine uniformément convexe. Tout d'abord, on montrera comment ce problème est, en fait, équivalent au problème de Beckmann suivant $$ \min\{\int_{\Omega} |w| dx : w \in L^1(\Omega,\mathbb{R}^2), \div(w)=0, w.n=f on \partial\Omega\}$$ (BP) où $f$ est la dérivée tangentielle de $g$. Ainsi, nous abordons le problème de la régularité $W^{1, p}$ pour une solution $u$ de (GP) en étudiant la sommabilité $L^p$ du flot minimal $w$ de (BP) quand on transporte des mesures concentrées sur le bord. Plus précisément, nous montrons que pour une donnée au bord $g$ dans $W^{1, p}$, la solution $u$ est aussi dans $W^{1, p}$, dès que $p \leq 2$. D'autre part, par un contre-exemple, nous montrons que ce résultat échoue pour $p>2$.

En considérant un domaine donné $R$ contenant un obstacle $O$, nous allons établir la dérivée première de forme du temps moyen de sortie des partilucles quand ces dernières sortent du domaine suivant une EDP modélisant le mouvement de foule. Cette fonction qui est le temps moyen de sortie dépend effectivement de la géométrie de l'obstacle $O$. Cette dérivée première est un pas important pour la minimisation du temps moyen de sortie des particles dans le domaine $R$. Dans ce travail, nous allons considérer la famille suivante d'équations aux dérivées partielles: Fokker-Planck, le cas des Mileux poreux et un cas plus général. En outre, dans le cas de dimension deux nous allons expliciter l'expression de la dérivée de forme mettant en evidence le théoreme de Hadamard.

The Colonel Blotto game is a well-known strategic resource allocation problem with important applications in a vast range of domains, from advertising to security. Two players simultaneously allocate a fixed budget of resources across $n$ battlefields, each player trying to maximize the aggregate value of the battlefields where she has higher allocation. Despite its long-standing history and importance, the Colonel Blotto game still lacks a complete Nash equilibrium solution in its general form with asymmetric players' budgets and heterogeneous battlefield values. In this paper, we propose an approximate equilibrium for this general case. We construct a simple strategy (the independently uniform strategy) and prove that it is an epsilon-equilibrium. We give a theoretical bound on the approximation error in terms of the number of battlefields and players’ budgets which identifies precisely the parameters regime for which our strategy is a good approximation. We also investigate an extension to the discrete version (where players can only have integer allocations), for which we proposed a modified strategy that can be computed very efficiently and gives an epsilon-equilibrium of the game.

In this paper we design and analyze a distributed algorithm to compute a Nash equilibrium in potential games based on best response. This algorithm can be implemented in a distributed way using Poisson clocks and does not rely on the usual assumption that players take no time to compute their best response and change their strategy. We show that if one takes this time lag into account, the algorithm may suffer from collisions (one player starts to play while another player has not changed her strategy yet). We first show that collisions do not jeopardize convergence to a Nash equilibrium but our main result is to show that the average time complexity of the algorithm (time to reach a Nash equilibrium) is bounded by 2n log n + o(n log n), where n is the number of players and p is 1−p the probability that a player gets in a collision. Furthermore, exhaustive simulations suggest that the term log n is superfluous.

Physicians at the Hospices Civils of Lyon (HCL) have at their disposal a Health Information System (HIS) which provides them access to all the available information about their patients. Our goal is to identify relevant improvements that we can make on the current HIS used by physicians at the HCL, to help them during the diagnostic process. According to this aim, we develop an analysis and a model of clinical diagnostic process. We first show that the decision process unfolded by a physician is mainly based on searching information about the patient. Then, we propose a rule-based model of the decision process to detect which information the physician will need and when s/he will need it during her/his diagnostic process.

Many papers have recently focused on the issue of the existence of a Nash equilibrium of {\it normal-form} games with {\it discontinuous payoffs}. For {\it extensive-form } games, several papers have provided existence proof of a subgame perfect equilibrium (in short, SPE, a generalization of Nash equilibrium) for infinite sets of actions at each period, when the payoff functions are assumed to be {\it continuous}. In this paper, we provide the first general existence result of a SPE for a class of discontinuous extensive-form games. This class is called extensive-form better-reply secure, and has some similarity, in terms of definition, with the class of better-reply secure games.\footnote{The class of better-reply secure games was introduced by Reny in 1999. It is a class of discontinuous normal-form games for which a Nash equilibrium can be proved to exist.} Roughly, a game is extensive-form better-reply secure if for every strategy profile $s^*$ which is not a subgame perfect equilibrium, there is an history $h$ from time 0 to time i (where player $i$ has to play), such that for every payoff $u_i$ of player $i$ obtained as a limit of the payoffs generated by some paths begining at $h$, there exists a deviation of player $i$ beginning at $h$, which gives him a payoff strictly above $u_i^*$ , even if one perturbs slightly the path defined by $s^*$ after $h$. Our result is the counterpart of Reny's existence theorem (true only for normal form games) for extensive form games. The idea is to approximate the game not by {\it a given finite approximation} (which would raise the question of its choice), as it is usually done, but by {\it any finite approximation}. This allows to improve the quality of the existence result, and relax the assumption of continuity of payoffs. We provide several examples of extensive-form better-reply secure games.

Nous présentons deux jeux à deux joueurs et à somme nulle modélisant une situation dans laquelle l'un d'eux attaque (ou se cache) dans un ensemble compact en dimension finie, et l'autre tente d'empêcher l'attaque (ou de le trouver). Le premier jeu, dit jeu de patrouille, correspond à une formulation dynamique de cette situation, au sens où l'attaquant choisit un temps et un point d'attaque tandis que le patrouilleur choisit une trajectoire continue afin de maximiser la probabilité de trouver le point d'attaque dans un délais donné. Le second jeu, dit jeu de dissimulation, correspond à une formulation statique dans laquelle les deux joueurs choisissent simultanément un point, le chercheur maximise la probabilité d'être à une distance inférieure à un rayon donné de son adversaire.

Routing games find many applications in various fields such as transportation, telecommunications or energy. The set of Nash Equilibria in this class of games is in general hard to compute. Here, we focus on the particular case of a parallel network and we address the computational issue of equilibria by providing two algorithms: the cycling best response dynamics and a projected gradient descent method. Under some monotonicity assumptions, we prove the convergence of those methods and we provide an upper bound on their convergence rate. Our convergence results state that, using one of these algorithms, the unique equilibrium of the game can be computed at an arbitrary precision in polynomial time. We give a practical application in the energy sector, where this framework and the associated results can be used to optimize the electricity consumption of flexible users

Various machine learning problem can be written as a minimization of a loss function $f$ plus a regularization $R$ calibrated by a positive hyperparameter $\lambda$ \ie $\min_{\beta} f(X\beta) + \lambda R(\beta)$. A major weakness of these methods is the tuning of the regularization parameter $\lambda$ where the difficulty are both theoretical (for statistical guarantees) as well as algorithmic (for numerical stability). A common approach is to choose the best parameter among the entire solution path on a given range. Unfortunately, these methods have a worst case complexity that is exponential in the number of parameter (Gartner et al 2012). In order to avoid this issue, approximation of the solution path was proposed and an optimal complexity was known to be ($1/\epsilon$) (Giesen et al 2010). Surprisingly, (Mairal and Yu 2012) show an important improvement to ($1/\sqrt{\epsilon}$) for the special case of the Lasso. Their result was generalized in (Giesen et al 2012) with a lower and upper bound of ($1/\sqrt{\epsilon}$) and derive a generic algorithm by assuming a polynomial lower bound on the objective function. Following those ideas, (Shibagaki et al 2015) have proposed the approximation of the validation path which is more natural for selecting a hyperparameter that are guaranteed to achieve a validation error close to the optimal one. We revisit the approximation and validation path theory in a unified framework under general regularity assumptions that are commonly verified in machine learning problems. We apply it to examples that encompass classification and regression problem and provide a complexity analysis along with optimality guarantees. We highlight the relationship between the complexity of the approximation path and the regularity of the loss function and show that the previously proposed complexity analysis can be too pessimistic or even insufficient in some situations.

We study the concept of information. Regarding a stochastic control problems model by Witsenhausen we look at a usual game theoretical problem without knowing a priori the order in which decisions are made by agents. This approach yields configurations that are not covered by classical theory. We are as well studying possible systems and classify them using four types of orderings. We show that the extensive form model is embedded into Witsenhausen model with the potential of embedding Bayesian games as well.

We present a primal-dual algorithm for solving a bound constrained optimization problem. The algorithm uses a regularization technique to handle the case where the second order sufficient optimality conditions do not hold at a local minimum. The local convergence analysis is done under a weaker assumption and is related to a local error bound condition. It is proved that locally the algorithm is superlinearly convergent. Some examples are also given to see the advantage of this new algorithm.

The mixed-integer quadratically-constrained quadratic programs are a very general class of instances that allow to model many reallife problems. We will present improvements on convex relaxations of such problems, and an augmented lagrangian dual approach to solve these relaxations. The framework is then integrated in a non-linear branch-and-bound algorithm to find near optimal bounds.

We study a stochastic model of anonymous influence with conformist and anti-conformist individuals. Each agent with a "yes" or "no" initial opinion on a certain issue can change his opinion due to social influence. We consider anonymous influence, which depends on the number of agents having a certain opinion, but not on their identity. An individual is conformist/anti-conformist if his probability of saying "yes" increases/decreases with the number of "yes"- agents. The seminal work of DeGroot (1974) and some of its extensions consider a non-anonymous influence in which agents update their opinions by using a weighted average of the opinions of their neighbors. We are interested in anonymous influence, which depends only on the number of individuals having a certain opinion and is not dependent on agents' identities. Forster and al (2013) investigate such kind of social influence by using the ordered weighted averages (commonly called OWA operators, Yager (1988) which are the unique anonymous aggregation functions. The authors departure from a general framework of influence based on aggregation functions Grabisch and Rusinowska (2013), where every individual updates his opinion by aggregating the agents' opinions which determines the probability that his opinion will be "yes" in the next period. Both frameworks of Forster and al (2013) and Grabisch and Rusinowska (2013) cover only positive influence (imitation), since by definition aggregation functions are nondecreasing, and hence cannot model anti-conformism. In order therefore to extend the analysis of anonymous influence to anti-conformism, we assume that every agent has a coefficient of conformism which is a real number in [-1,1], with negative/positive values corresponding to anti-conformists/conformists. The two extreme values -1 and 1 represent a pure anti-conformist and a pure conformist, respectively, and the remaining values -- so called "mixed" agents. We consider two kinds of a society: without mixed agents, and with mixed agents who play randomly either as conformists or anti-conformists. For both cases of the model, we deliver a qualitative analysis of convergence, i.e., find all absorbing classes and conditions for their occurrence. We find nineteen terminal classes, whose dynamics can be distinguished into three categories : terminal states, periodic classes and aperiodic classes. Though we do not examine issues like speed of convergence, average time between peaks in aperiodic classes and other quantitative results, we emphasize the need for such problem to be examined later. Another case for the need of such future research is that simulations show that, from a qualitative point of view, a society represented by a given absorbing class may exhibit a behavior similar to another terminal class, sometimes temporarily; i.e the behavior between two terminal classes, though qualitatively different, can be undistinguishable on data. We argue that anti-conformism can be a word labelling different contexts, such as incomplete information or bounded rationality, that is, a wide range of processes based on imitation, signaling or coordination. Based on this remark and simulations of time series, we suggest that if some econometric method could be invented as a tool to disentangle a conformist and anti-conformist behaviors from time series, then such model could be useful to model irregular periodicity patterns, amplifying oscillations, booms and bursts; in particular, if an econometric method was to be designed to recover parameters of our model from times series, it could probably be used to predict some of the shocks due to imitation processes.

Nous étudions un problème de contrôle optimal discret en horizon fini, de dynamique linéaire, de coûts instantanés et final quadratiques et de contrôles à la fois continus et discrets. Nous développons un algorithme et prouvons sa convergence en s'inspirant du travail effectué dans~\cite{Zheng} et~\cite{Zhengbis}. Les opérateurs de Bellman associés à l'équation de la programmation dynamique de notre problème sont min-plus linéaires sur les formes quadratiques, permettant ainsi de déterminer explicitement les fonctions valeurs comme des infimums finis de formes quadratiques. Une telle approche n'est pas soumise à la fameuse malédiction de la dimension, toutefois le nombre de formes quadratiques nécessaires au calcul de l'infimum croît exponentiellement avec le temps. L'algorithme proposé ici sélectionne certaines formes quadratiques impliquées dans le calcul de l'infimum en testant si une forme quadratique améliore l'approximation courante en un point tiré aléatoirement uniformément sur la sphère. Dans notre cadre, le calcul explicite des opérateurs de Bellman à contrôle discret fixé est donné par une équation de Riccati et nous prouvons la convergence de notre algorithme en nous basant sur l'existence d'un ensemble borné, pour l'ordre de Loewner sur les matrices symétriques, stable par tous les opérateurs de Bellman.

Stochastic optimization algorithms with variance reduction have proven successful for minimizing large finite sums of functions. Unfortunately, these techniques are unable to deal with stochastic perturbations of input data, induced for example by data augmentation. In such cases, the objective is no longer a finite sum, and the main candidate for optimization is the stochastic gradient descent method (SGD). We introduce a variance reduction approach for these settings when the objective is composite and strongly convex. The convergence rate outperforms SGD with a typically much smaller constant factor, which depends on the variance of gradient estimates only due to perturbations on a single example.

Motivated by Nesterov’s dual averaging method for solving (stochastic) convex programs and monotone variational inequalities, we propose a primal-dual algorithm for finding zeros of random, non-monotone operators. Given the close connection between the zero set of a maximal monotone operator and the set of solutions of a (Minty-type) variational inequality, we focus on a class of non-monotone operators for which the associated Minty variational inequality admits a solution. This property, which we call variational coherence, is wide enough to properly include all maximal monotone, pseudomonotone (“+” or “∗”), and other relevant classes of operators. Under mild assumptions for the randomness of the problem at hand (bounded second moments), we show that the algorithm converges to a zero point with probability 1, and we estimate its rate of convergence.

We present a matrix-factorization algorithm that scales to input matrices with both huge number of rows and columns. Learned factors may be sparse or dense and/or non-negative, which makes our algorithm suitable for dictionary learning, sparse component analysis, and non-negative matrix factorization. Our algorithm streams matrix columns while subsampling them to iteratively learn the matrix factors. At each iteration, the row dimension of a new sample is reduced by subsampling, resulting in lower time complexity compared to a simple streaming algorithm. Our method comes with convergence guarantees to reach a stationary point of the matrix-factorization problem. We demonstrate its efficiency on massive functional Magnetic Resonance Imaging data (2 TB), and on patches extracted from hyperspectral images (103 GB). For both problems, which involve different penalties on rows and columns, we obtain significant speed-ups compared to state-of-the-art algorithms.

Nous étudions l'optimisation de la forme de dispositifs nano-photoniques par la méthode des dérivées de forme d'Hadamard. Nos recherches nous ont porté vers l'optimisation robuste (au pire cas) de ces dispositifs lorsque des incertitudes sont attendues soit au niveau de la longueur d'onde de la lumière incidente soit au niveau de la forme réalisée. Mathématiquement on cherche à résoudre le problème $$\max_{\Omega} \inf_{\|\delta\| \leq m} \mathcal{J}(\Omega,\delta)$$ où $\Omega$ est la forme recherchée, $\delta$ un paramètre représentant l'incertitude d'amplitude maximale $m$ et $\mathcal{J}$ un objectif, tel que la puissance en sortie, qui dépend de la forme par l'intermédiaire du champs électrique, solution des équations de Maxwell à l'intérieur du dispositif. La plupart des méthodes proposées pour ce type de problème d'optimisation robuste repose sur l'ajout d'un terme de pénalisation au niveau de l'objectif. Dans cet exposé nous présenterons les résultats que nous avons obtenus en appliquant une méthode d'optimisation multi-objectifs.

In this presentation, we consider a finite version of Mean Field Games (MFGs) introduced by Gomes et al. (2010) and study, first the convergence of the fictitious play procedure to equilibrium and second, the relation of some finite MFGs with the continuous first order MFGs system.

We propose an efficient distributed algorithm for solving regularized learning problems. In a distributed framework with a master machine coordinating the computations of many slave machines, our proximal-gradient algorithm allows local computations and sparse communications from slaves to master. Furthermore, with the $\ell_1$-regularizer, our approach automatically identifies the support of the solution, leading to sparse communications from master to slaves, with near-optimal support. We thus obtain an algorithm with two-way sparse communications.

In this work, we consider a descent algorithm for the Sparse Reduced-Rank Regression problem. A recent litterature revisited such non- convex problems based on an explicit parametrization of the low-rank matrix. However, no general convergence rate result was provided, in particular not in the nondifferentiable case. Reformulating the minimization problem and analyzing its geometry in a neighborhood of the optimal set, we show the Polyak-Łojasiewicz inequality or its extension to the nondifferentiable case are satisfied. Consequently, we establish the linear convergence of the proximal block-coordinate gradient algorithm in this neighborhood.

We consider an optimal control on networks in the spirit of the works of Achdou et al. (2013) and Imbert et al. (2013). The main new feature is that there are entry costs at the edges of the network leading to a possible discontinuous value function. We characterize the value function as the unique viscosity solution of a new Hamilton-Jacobi system. The uniqueness is a consequence of a comparison principle for which we give two different proofs, one with arguments from the theory of optimal control inspired by Achdou et al. (2014) and one based on partial differential equations techniques inspired by a recent work of Lions and Souganidis (2016).

L'article [HEN09] propose une méthode pour le calcul du volume d'un compact semi-algébrique basique, utilisant les hiérarchies moments / SOS développées dans [LAS09]. L'article [HEN14] s'inspire de ces travaux pour estimer la région d'attraction (R.O.A.) d'un compact semi-algébrique basique pour une E.D.O. polynomiale. Dans ces deux approches, le recours au calcul SDP pose un problème de passage à l'échelle : la complexité des algorithmes est polynomiale en la dimension du problème. Nous proposons ici une méthode originale et non triviale pour le calcul de volumes, transposable à l'estimation de R.O.A., qui permet de traiter des problèmes de dimension relativement élevée à condition qu'ils présentent une certaine structure creuse.