Search

Showing total 6 results
Start Over Topic mathematics - optimization and control
6 results

1. Stability of optimal traffic plans in the irrigation problem

Author

Antoine Prouff, Antonio De Rosa, Andrea Marchese, Maria Colombo, Paul Pegon, Ecole Polytechnique Fédérale de Lausanne (EPFL), Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), Department of mathematics/Dipartimento di Matematica [Univ. Trento], Università degli Studi di Trento (UNITN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Maria Colombo was partially supported by the Swiss National Science Foundation grant 200021_182565. Antonio De Rosa has been supported by the NSF DMS Grant No. 1906451. Andrea Marchese acknowledges partial support from GNAMPA-INdAM., Department of Mathematics [College Park], University of Maryland [College Park], University of Maryland System-University of Maryland System, Bocconi Institute for Data Science and Analytics (BIDSA), Bocconi University [Milan, Italy], Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, M. C. was partially supported by the Swiss National Science Foundation grant 200021_182565. A. D. R. has been supported by the NSF DMS Grant No. 1906451 and the NSF DMS Grant No. 2112311. A. M. acknowledges partial support from GNAMPA-INdAM. A.P. was supported by the Fondation Mathématiques Jacques Hadamard. P.P and A.P. both acknowledge EPFL for hosting them during the semester this paper was prepared., Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)

Subjects
BRANCHED TRANSPORT, Mathematical optimization, Irrigation, TRAFFIC PLANS, [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], 01 natural sciences, Stability (probability), symbols.namesake, Mathematics - Analysis of PDEs, Classical Analysis and ODEs (math.CA), FOS: Mathematics, Computer Science::Networking and Internet Architecture, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Discrete Mathematics and Combinatorics, Limit (mathematics), 0101 mathematics, Mathematics - Optimization and Control, Mathematics, TRANSPORTATION NETWORK, BRANCHED TRANSPORT, IRRIGATION PROBLEM, TRAFFIC PLANS, STABILITY, STABILITY, IRRIGATION PROBLEM, Applied Mathematics, TRANSPORTATION NETWORK, 010102 general mathematics, Eulerian path, Flow network, 010101 applied mathematics, Optimization and Control (math.OC), Mathematics - Classical Analysis and ODEs, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis, Lagrangian, Analysis of PDEs (math.AP)
Abstract

We prove the stability of optimal traffic plans in branched transport. In particular, we show that any limit of optimal traffic plans is optimal as well. This result goes beyond the Eulerian stability proved in [7], extending it to the Lagrangian framework.

Published
2022

2. Linear Bandits on Uniformly Convex Sets

Author

Kerdreux, Thomas, Roux, Christophe, d'Aspremont, Alexandre, Pokutta, Sebastian, Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Equipe de droit public de Lyon, Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon, Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Zuse Institute Berlin (ZIB), Research reported in this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers 05M14ZAM,05M20ZBM) as well as the Deutsche Forschungsgemeinschaft (DFG) through the DFG Cluster of Excellence MATH+.AA is at the département d’informatique de l’École Normale Supérieure, UMR CNRS 8548, PSL Research University, 75005 Paris, France, and INRIA. AA would like to acknowledge support from the ML and Optimisation joint research initiative with the fonds AXA pour la recherche and Kamet Ventures, a Google focused award, as well as funding by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute)., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, d'Aspremont, Alexandre, and PaRis Artificial Intelligence Research InstitutE - - PRAIRIE2019 - ANR-19-P3IA-0001 - P3IA - VALID

Subjects
FOS: Computer and information sciences, Computer Science::Machine Learning, Computer Science - Machine Learning, Statistics::Machine Learning, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], Optimization and Control (math.OC), FOS: Mathematics, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Mathematics - Optimization and Control, [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Machine Learning (cs.LG)
Abstract

Linear bandit algorithms yield $\tilde{\mathcal{O}}(n\sqrt{T})$ pseudo-regret bounds on compact convex action sets $\mathcal{K}\subset\mathbb{R}^n$ and two types of structural assumptions lead to better pseudo-regret bounds. When $\mathcal{K}$ is the simplex or an $\ell_p$ ball with $p\in]1,2]$, there exist bandits algorithms with $\tilde{\mathcal{O}}(\sqrt{nT})$ pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond $\ell_p$ balls that enjoy pseudo-regret bounds of $\tilde{\mathcal{O}}(\sqrt{nT})$, which answers an open question from [BCB12, \S 5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than $\mathcal{O}(\sqrt{n})$. However, this comes at the expense of asymptotic rates in $T$ varying between $\tilde{\mathcal{O}}(\sqrt{T})$ and $\tilde{\mathcal{O}}(T)$.

Published
2021

3. Local and Global Uniform Convexity Conditions

Author

Kerdreux, Thomas, d'Aspremont, Alexandre, Pokutta, Sebastian, d'Aspremont, Alexandre, PaRis Artificial Intelligence Research InstitutE - - PRAIRIE2019 - ANR-19-P3IA-0001 - P3IA - VALID, Département d'informatique - ENS Paris (DI-ENS), Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Zuse Institute Berlin (ZIB), Technische Universität Berlin (TU), Laboratoire d'informatique de l'école normale supérieure (LIENS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Paris (ENS Paris), Centre National de la Recherche Scientifique (CNRS), Statistical Machine Learning and Parsimony (SIERRA), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris sciences et lettres (PSL), Research reported in this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers 05M14ZAM,05M20ZBM) as well as the Deutsche Forschungsgemeinschaft (DFG) through the DFG Cluster of Excellence MATH+. AA would like to acknowledge support from the ML and Optimisation joint research initiative with the fonds AXA pour la recherche and Kamet Ventures, a Google focused award, as well as funding by the French government under management of Agence Nationale de la Recherche as part of the 'Investissements d’avenir' program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute)., ANR-19-P3IA-0001,PRAIRIE,PaRis Artificial Intelligence Research InstitutE(2019), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, École normale supérieure - Paris (ENS-PSL), Technical University of Berlin / Technische Universität Berlin (TU), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Paris (ENS-PSL)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Optimization and Control (math.OC), FOS: Mathematics, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Mathematics - Optimization and Control, [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], Machine Learning (cs.LG)
Abstract

We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with \textit{scaling inequalities} used in analysing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results.

Published
2021

4. Bounding Fixed Points of Set-Based Bellman Operator and Nash Equilibria of Stochastic Games

Author

Li, Sarah H. Q., Assalé, Adjé, Garoche, Pierre-Loïc, Açıkmeşe, Behçet, University of Washington [Seattle], Université de Perpignan Via Domitia (UPVD), Ecole Nationale de l'Aviation Civile (ENAC), This work has been partially supported by Feanicses project, France ANR-17-CE25-0018 and NSF, USA CNS-1736582. The material in this paper was presented at the 21st IFAC World Congress (IFAC 2020), July 12–17, 2020, Berlin, Germany., and ANR-17-CE25-0018,FEANICSES,Analyses formelles et exhaustives de systèmes embarqués de contrôle à base de calculs intensifs(2017)

Subjects
FOS: Computer and information sciences, 0209 industrial biotechnology, Mathematical optimization, Computer Science::Computer Science and Game Theory, Computer science, MathematicsofComputing_NUMERICALANALYSIS, 02 engineering and technology, Interval (mathematics), Fixed point, learning in games, decision making and autonomy, symbols.namesake, 020901 industrial engineering & automation, Operator (computer programming), [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science - Computer Science and Game Theory, Bellman equation, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], FOS: Mathematics, stochastic control, multi-agent systems, Electrical and Electronic Engineering, Mathematics - Optimization and Control, Stochastic control, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 020208 electrical & electronic engineering, Stochastic game, Control and Systems Engineering, Nash equilibrium, learning theory, Optimization and Control (math.OC), symbols, Markov decision process, Computer Science and Game Theory (cs.GT)
Abstract

Motivated by uncertain parameters encountered in Markov decision processes (MDPs) and stochastic games, we study the effect of parameter uncertainty on Bellman operator-based algorithms under a set-based framework. Specifically, we first consider a family of MDPs where the cost parameters are in a given compact set; we then define a Bellman operator acting on a set of value functions to produce a new set of value functions as the output under all possible variations in the cost parameter. We prove the existence of a fixed point of this set-based Bellman operator by showing that it is contractive on a complete metric space, and explore its relationship with the corresponding family of MDPs and stochastic games. Additionally, we show that given interval set bounded cost parameters, we can form exact bounds on the set of optimal value functions. Finally, we utilize our results to bound the value function trajectory of a player in a stochastic game., 15 pages, 4 figures

Published
2020

5. About strong string stability of a vehicle chain with time-headway control

Author

Alain Sarlette, Arash Farnam, Universiteit Gent = Ghent University [Belgium] (UGENT), QUANTum Information Circuits (QUANTIC), MINES ParisTech - École nationale supérieure des mines de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office., École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-MINES ParisTech - École nationale supérieure des mines de Paris, Universiteit Gent = Ghent University (UGENT), Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de physique de l'ENS - ENS Paris (LPENS), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, Université Paris sciences et lettres (PSL), and Sarlette, Alain

Subjects
Time headway, 050210 logistics & transportation, 0209 industrial biotechnology, String length, Technology and Engineering, Proportional derivative, SUBJECT, PLATOONS, 05 social sciences, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], 02 engineering and technology, Chain length, 020901 industrial engineering & automation, Control theory, Optimization and Control (math.OC), Norm (mathematics), Bounded function, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0502 economics and business, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Absolute velocity, Mathematics - Optimization and Control, [INFO.INFO-AU] Computer Science [cs]/Automatic Control Engineering, Mathematics
Abstract

This paper deals with the problem of string stability in a chain of acceleration-controlled vehicles, i.e. how input disturbances affect the distributed system for very long chains. There exist variants of string stability, like avoiding that a local disturbance gets amplified along the chain, or more strongly ensuring that the output vector's p-norm remains bounded for any bounded vector of input disturbances independently of the string length. They are all impossible to achieve with any linear controller if the vehicles only use relative information of few vehicles in front. Previous work has shown that adding absolute velocity into the controller, allows to at least avoid amplification of a local disturbance. In this paper, we consider the stronger definitions of string stability, under this same relaxation of using absolute velocity in the controller. We prove that the influence from input vector to output vector cannot be bounded independently of chain length in the most popular 2-norm sense, with any bounded stabilizing linear controller; while a proportional derivative (PD) controller can guarantee it in the practically relevant infinity-norm sense. Moreover, we identify the disturbance acting on the leader as the main issue for string stability., Comment: presented at IEEE-CDC 2018, Miami; more complete version and correcting a few typos

Published
2019

6. Markov games with frequent actions and incomplete information

Author

Pierre Cardaliaguet, Catherine Rainer, Nicolas Vieille, Dinah Rosenberg, CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS), Laboratoire de mathématiques de Brest (LM), Université de Brest (UBO)-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS), Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), and HEC Paris Research Paper Series

Subjects
Mathematical optimization, Computer Science::Computer Science and Game Theory, Optimization problem, MathematicsofComputing_NUMERICALANALYSIS, jel:C00, Markov model, 01 natural sciences, Bayesian game, Markov games, Complete information, zero-sum games, 91A05, 91A15, 60J10, 0502 economics and business, incomplete information, FOS: Mathematics, 0101 mathematics, Mathematics - Optimization and Control, 050205 econometrics, Mathematics, Markov chain, Variable-order Markov model, 010102 general mathematics, 05 social sciences, Stochastic game, ComputingMilieux_PERSONALCOMPUTING, TheoryofComputation_GENERAL, stochastic, zero sum, Hamilton-Jacobi equation, repeated games, Optimization and Control (math.OC), Balance equation, [SHS.GESTION]Humanities and Social Sciences/Business administration, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Hamilton-Jacobi equations
Abstract

We study a two-player, zero-sum, stochastic game with incomplete information on one side in which the players are allowed to play more and more frequently. The informed player observes the realization of a Markov chain on which the payoffs depend, while the non-informed player only observes his opponent's actions. We show the existence of a limit value as the time span between two consecutive stages vanishes; this value is characterized through an auxiliary optimization problem and as the solution of an Hamilton-Jacobi equation.

Published
2013
Full Text
View/download PDF