Other Topics

Optimality Conditions and Duality for Nonsmooth Multiobjective Optimization Problems with Cone Constraints and Applications

  • Jiawei Chen
  • Zhong-Ping Wan
  • Zheng Yue
    • Categories Nonsmooth Optimization, Other Topics Tags , , , , , ,

    In this work, a nonsmooth multiobjective optimization problem involving generalized invexity with cone constraints and Applications (for short, (MOP)) is considered. The Kuhn-Tucker necessary and sufficient conditions for (MOP) are established by using a generalized alternative theorem of Craven and Yang. The relationship between weakly efficient solutions of (MOP) and vector valued saddle points of … Read more

    Approximating the Least Core Value and Least Core of Cooperative Games with Supermodular Costs

  • Andreas S. Schulz
  • Nelson A. Uhan
    • Categories Approximation Algorithms, Game Theory, Graphs and Matroids

    We study the approximation of the least core value and the least core of supermodular cost cooperative games. We provide a framework for approximation based on oracles that approximately determine maximally violated constraints. This framework yields a (3 + \epsilon)-approximation algorithm for computing the least core value of supermodular cost cooperative games, and a polynomial-time … Read more

    On the Equivalencey of Linear Programming Problems and Zero-Sum Games

  • Ilan Adler
    • Categories Game Theory, Linear Programming Tags , , , , ,

    In 1951, Dantzig showed the equivalence of linear programming and two-person zero-sum games. However, in the description of his reduction from linear programming to zero-sum games, he noted that there was one case in which his reduction does not work. This also led to incomplete proofs of the relationship between the Minmax Theorem of game … Read more

    Direct Multisearch for Multiobjective Optimization

  • Ana Luisa Custódio
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
  • J. F. A. Madeira
    • Categories Multi-Criteria Optimization Tags , , , , , , ,

    In practical applications of optimization it is common to have several conflicting objective functions to optimize. Frequently, these functions are subject to noise or can be of black-box type, preventing the use of derivative-based techniques. We propose a novel multiobjective derivative-free methodology, calling it direct multisearch (DMS), which does not aggregate any of the objective … Read more

    Fast population game dynamics for dominant sets and other quadratic optimization problems

  • Immanuel M. Bomze
  • Marcello Pelillo
  • Samuel Rota-Bulo
    • Categories Data-Mining, Game Theory, Quadratic Programming Tags ,

    We propose a fast population game dynamics, motivated by the analogy with infection and immunization processes within a population of “players,” for finding dominant sets, a powerful graph-theoretical notion of a cluster. Each step of the proposed dynamics is shown to have a linear time/space complexity and we show that, under the assumption of symmetric … Read more

    Aircraft landing problems with aircraft classes

  • Dirk Briskorn
  • Raik Stolletz
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Transportation Tags , , , ,

    This paper focuses on the aircraft landing problem that is to assign landing times to aircraft approaching the airport under consideration. Each aircraft’s landing time must be in a time interval encompassing a target landing time. If the actual landing time deviates from the target landing time additional costs occur which depend on the amount … Read more

    Flows and Decompositions of Games: Harmonic and Potential Games

  • Ozan Candogan
  • Ishai Menache
  • Asuman Ozdaglar
  • Pablo A. Parrilo
    • Categories Game Theory Tags , , ,

    In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this … Read more

    Robust Markov Decision Processes

  • Daniel Kuhn
  • Berc Rustem
  • Wolfram Wiesemann
    • Categories Dynamic Programming, Robust Optimization

    Markov decision processes (MDPs) are powerful tools for decision making in uncertain dynamic environments. However, the solutions of MDPs are of limited practical use due to their sensitivity to distributional model parameters, which are typically unknown and have to be estimated by the decision maker. To counter the detrimental effects of estimation errors, we consider … Read more

    Risk Adjusted Budget Allocation Models with Application in Homeland Security

  • Tito Homem-de-Mello
  • Jian Hu
  • Sanjay Mehrotra
    • Categories Multi-Criteria Optimization, Robust Optimization, Stochastic Programming Tags , , , , ,

    This paper presents and studies several models for multi-criterion budget allocation problems under uncertainty. We start by introducing a robust weighted objective model, which is developed further using the concept of stochastic dominance to incorporate risk averseness of the decision maker. A budget minimization variant of this model is also presented. We use a Sample … Read more

    Necessary optimality conditions for multiobjective bilevel programs

  • Jane J. Ye
    • Categories Game Theory, Multi-Criteria Optimization, Nonsmooth Optimization Tags , ,

    The multiobjective bilevel program is a sequence of two optimization problems where the upper level problem is multiobjective and the constraint region of the upper level problem is determined implicitly by the solution set to the lower level problem. In the case where the Karush-Kuhn-Tucker (KKT) condition is necessary and sufficient for global optimality of … Read more