Other Topics

Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and their Practical Implications

  • Luís Felipe Bueno
  • Gabriel Haeser
  • Frank Navarro Rojas
    • Categories Constrained Nonlinear Optimization, Game Theory Tags , , , ,

    Generalized Nash Equilibrium Problems (GNEPs) are a generalization of the classic Nash Equilibrium Problems (NEPs), where each player’s strategy set depends on the choices of the other players. In this work we study constraint qualifications and optimality conditions tailored for GNEPs and we discuss their relations and implications for global convergence of algorithms. Surprisingly, differently … Read more

    Network-based Approximate Linear Programming for Discrete Optimization

  • Andre Augusto Cire
  • Selvaprabu Nadarajah
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming, Linear Programming Tags , ,

    We develop a new class of approximate linear programs (ALPs) that project the high-dimensional value function of dynamic programs onto a class of basis functions, each defined as a network that represents aggregrations over the state space. The resulting ALP is a minimum-cost flow problem over an extended variable space that synchronizes flows across multiple … Read more

    A note on using performance and data profiles for training algorithms

  • Margherita Porcelli
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Optimization of Simulated Systems, Optimization Software Benchmark Tags , , ,

    It is shown how to use the performance and data profile benchmarking tools to improve algorithms’ performance. An illustration for the BFO derivative-free optimizer suggests that the obtained gains are potentially significant. CitationACM Transactions on Mathematical Software, 45:2 (2019), Article 20.ArticleDownload View PDF

    Variational inequality formulation for the games with random payoffs

  • Abdel Lisser
  • Vikas Vikram Singh
    • Categories Game Theory, Stochastic Programming

    We consider an n-player non-cooperative game with random payoffs and continuous strategy set for each player. The random payoffs of each player are defined using a finite dimensional random vector. We formulate this problem as a chance-constrained game by defining the payoff function of each player using a chance constraint. We first consider the case … Read more

    Approximations to Stochastic Dynamic Programs via Information Relaxation Duality

  • Santiago Balseiro
  • David B. Brown
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Stochastic Programming Tags , , , , , ,

    In the analysis of complex stochastic dynamic programs, we often seek strong theoretical guarantees on the suboptimality of heuristic policies. One technique for obtaining performance bounds is perfect information analysis: this approach provides bounds on the performance of an optimal policy by considering a decision maker who has access to the outcomes of all future … Read more

    Meta-Modeling to Assess the Possible Future of Paris Agreement

  • Frédéric Babonneau
  • A Bernard
  • Alain Haurie
  • Alain Vielle
    • Categories Game Theory Tags , , , , , ,

    In the meta-modeling approach one builds a numerically tractable dynamic optimization or game model in which the parameters are identified through statistical emulation of a detailed large scale numerical simulation model. In this paper we show how this approach can be used to assess the economic impacts of possible climate policies compatible with the Paris … Read more

    Generalized Dual Dynamic Programming for Infinite Horizon Problems in Continuous State and Action Spaces

  • Paul Beuchat
  • John Lygeros
  • Joseph Warrington
    • Categories Control Applications, Dynamic Programming Tags , , ,

    We describe a nonlinear generalization of dual dynamic programming theory and its application to value function estimation for deterministic control problems over continuous state and action (or input) spaces, in a discrete-time infinite horizon setting. We prove that the result of a one-stage policy evaluation can be used to produce nonlinear lower bounds on the … Read more

    Pareto efficient solutions in multi-objective optimization involving forbidden regions

  • Christian Günther
    • Categories Facility Planning and Design, Generalized Convexity/Monoticity, Multi-Criteria Optimization

    In this paper, the aim is to compute Pareto efficient solutions of multi-objective optimization problems involving forbidden regions. More precisely, we assume that the vector-valued objective function is componentwise generalized-convex and acts between a real topological linear pre-image space and a finite-dimensional image space, while the feasible set is given by the whole pre-image space … Read more

    A Bucket Graph Based Labeling Algorithm with Application to Vehicle Routing

  • Artur Alves Pessoa
  • Ruslan Sadykov
  • Eduardo Uchoa
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming

    We consider the Resource Constrained Shortest Path problem arising as a subproblem in state-of-the-art Branch-Cut-and-Price algorithms for vehicle routing problems. We propose a variant of the bi-directional label correcting algorithm in which the labels are stored and extended according to so-called bucket graph. Such organization of labels helps to decrease significantly the number of dominance … Read more

    Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems

  • Mengdi Wang
    • Categories Dynamic Programming

    Consider the problem of approximating the optimal policy of a Markov decision process (MDP) by sampling state transitions. In contrast to existing reinforcement learning methods that are based on successive approximations to the nonlinear Bellman equation, we propose a Primal-Dual π Learning method in light of the linear duality between the value and policy. The … Read more