-
作者：Speakman, Emily; Lee, Jon
作者单位：University of Michigan System; University of Michigan
摘要：When using the standard McCormick inequalities twice to convexify trilinear monomials, as is often the practice in modeling and software, there is a choice of which variables to group first. For the important case in which the domain is a nonnegative box, we calculate the volume of the resulting relaxation, as a function of the bounds defining the box. In this manner, we precisely quantify the strength of the different possible relaxations defined by all three groupings, in addition to the tri...
-
作者：Baeuerle, Nicole; Rieder, Ulrich
作者单位：Helmholtz Association; Karlsruhe Institute of Technology; Ulm University
摘要：We consider the problem of minimizing a certainty equivalent of the total or discounted cost over a finite and an infinite time horizon that is generated by a partially observable Markov decision process (POMDP). In contrast to a risk-neutral decision maker, this optimization criterion takes the variability of the cost into account. It contains as a special case the classical risk-sensitive optimization criterion with an exponential utility. We show that this optimization problem can be solved...
-
作者：Bressaud, Xavier; Quas, Anthony
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; University of Victoria
摘要：We study a two player repeated zero-sum game with asymmetric information introduced by Renault in which the underlying state of the game undergoes Markov evolution (parameterized by a transition probability, p, in the range 12 to 1). Horner, Rosenberg, Solan and Vieille identified an optimal strategy, sigma* for the informed player for p in the range [1/2, 2/3]. We extend the range on which sigma* is proved to be optimal to about [1/2, 0.719] and prove that it fails to be optimal at a value ar...
-
作者：De Angelis, Tiziano; Federico, Salvatore; Ferrari, Giorgio
-
作者：Saldi, Naci; Yuksel, Serdar; Linder, Tamas
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Queens University - Canada
摘要：Calculating optimal policies is known to be computationally difficult for Markov decision processes (MDPs) with Borel state and action spaces. This paper studies finite-state approximations of discrete time Markov decision processes with Borel state and action spaces, for both discounted and average costs criteria. The stationary policies thus obtained are shown to approximate the optimal stationary policy with arbitrary precision under quite general conditions for discounted cost and more res...
-
作者：Whiteley, Nick; Kantas, Nikolas
作者单位：University of Bristol; Imperial College London
摘要：Often in applications such as rare events estimation or optimal control it is required that one calculates the principal eigenfunction and eigenvalue of a nonnegative integral kernel. Except in the finite-dimensional case, usually neither the principal eigenfunction nor the eigenvalue can be computed exactly. In this paper, we develop numerical approximations for these quantities. We show how a generic interacting particle algorithm can be used to deliver numerical approximations of the eigenq...
-
作者：Razborov, Alexander
作者单位：University of Chicago; University of Chicago; Russian Academy of Sciences; Steklov Mathematical Institute of the Russian Academy of Sciences
摘要：In this paper we study width of semialgebraic proof systems and various cut-based procedures in integer programming. We focus on two important systems: Gomory-Chvatal cutting planes and Lovasz-Schrijver lift-and-project procedures. We develop general methods for proving width lower bounds and apply them to random k-CNFs and several popular combinatorial principles, like the perfect matching principle and Tseitin tautologies. We also show how to apply our methods to various combinatorial optimi...
-
作者：Flesch, Janos; Predtetchinski, Arkadi
作者单位：Maastricht University; Maastricht University
摘要：We provide a characterization of subgame-perfect equilibrium plays in a class of perfect information games where each player's payoff function is Borel measurable and has finite range. The set of subgame-perfect equilibrium plays is obtained through a process of iterative elimination of plays. Extensions to games with bounded Borel measurable payoff functions are discussed. As an application of our results, we show that if every player's payoff function is bounded and upper semicontinuous, the...
