-
作者：Scherrer, Bruno
作者单位：Inria
摘要：Given a Markov decision process (MDP) with n states and a total number m of actions, we study the number of iterations needed by policy iteration (PI) algorithms to converge to the optimal gamma-discounted policy. We consider two variations of PI: Howard's PI that changes the actions in all states with a positive advantage, and Simplex-PI that only changes the action in the state with maximal advantage. We show that Howard's PI terminates after at most O((nm/(1-gamma))log(1/(1-gamma))) iterati...
-
作者：Bauschke, Heinz H.; Hare, Warren L.; Moursi, Walaa M.
作者单位：University of British Columbia; Egyptian Knowledge Bank (EKB); Mansoura University
摘要：The problem of finding a minimizer of the sum of two convex functions-or, more generally, that of finding a zero of the sum of two maximally monotone operators-is of central importance in variational analysis. Perhaps the most popular method of solving this problem is the Douglas-Rachford splitting method. Surprisingly, little is known about the range of the Douglas-Rachford operator. In this paper, we set out to study this range systematically. We prove that for 3* monotone operators a very p...
-
作者：Wang, Bin; Wang, Ruodu
作者单位：Beijing Technology & Business University; University of Waterloo
摘要：Many optimization problems in probabilistic combinatorics and mass transportation impose fixed marginal constraints. A natural and open question in this field is to determine all possible distributions of the sum of random variables with given marginal distributions; the notion of joint mixability is introduced to address this question. A tuple of univariate distributions is said to be jointly mixable if there exist random variables, with respective distributions, such that their sum is a cons...
-
作者：Alfonsi, Aurelien; Kloeck, Florian; Schied, Alexander
作者单位：Institut Polytechnique de Paris; Ecole des Ponts ParisTech; Universite Gustave-Eiffel; University of Mannheim
摘要：We consider a model for linear transient price impact for multiple assets that takes cross-asset impact into account. Our main goal is to single out properties that need to be imposed on the decay kernel so that the model admits well-behaved optimal trade execution strategies. We first show that the existence of such strategies is guaranteed by assuming that the decay kernel corresponds to a matrix-valued positive definite function. An example illustrates, however, that positive definiteness a...
-
作者：Bayraktar, Erhan; Zhang, Yuchong
作者单位：University of Michigan System; University of Michigan; Columbia University
摘要：We prove the fundamental theorem of asset pricing for a discrete time financial market where trading is subject to proportional transaction costs and the asset price dynamic is modeled by a family of probability measures, possibly nondominated. Using a backward-forward scheme, we show that when the market consists of a money market account and a single stock, no-arbitrage in a quasi-sure sense is equivalent to the existence of a suitable family of consistent price systems. We also show that wh...
-
作者：Skutella, Martin; Verschae, Jose
作者单位：Technical University of Berlin; Pontificia Universidad Catolica de Chile
摘要：Scheduling a set of n jobs on m identical parallel machines so as to minimize the makespan or maximize the minimum machine load are two of the most important and fundamental scheduling problems studied in the literature. We consider the general online scenario where jobs are consecutively added to and/or deleted from an instance. The goal is to maintain a near-optimal assignment of the current set of jobs to the m machines. This goal is essentially doomed to failure unless, upon arrival or dep...
-
作者：Todd, Michael J.
作者单位：Cornell University
摘要：We give an efficient algorithm for computing a Cournot equilibrium when the producers are confined to integers, the inverse demand function is linear, and costs are quadratic. The method also establishes existence constructively. We use our characterization to discuss the multiplicity of integer Cournot equilibria and their relationship to the real Cournot equilibrium.
-
作者：Chen, Qin; Chen, Xujin; Zang, Wenan
作者单位：China Jiliang University; Chinese Academy of Sciences; University of Hong Kong
摘要：Let G be a digraph and let pi(G) be the linear system consisting of nonnegativity, stability, and domination inequalities. We call G kernel ideal if pi(H) defines an integral polytope for each induced subgraph H of G, and we call G kernel Mengerian if pi(H) is totally dual integral (TDI) for each induced subgraph H of G. In this paper we show that a digraph is kernel ideal iff it is kernel Mengerian iff it contains none of three forbidden structures; our characterization yields a polynomial-ti...
-
作者：Gapeev, Pavel V.
作者单位：University of London; London School Economics & Political Science
摘要：The switching multiple disorder problem seeks to determine an ordered infinite sequence of times of alarms which are as close as possible to the unknown times of disorders, or change-points, at which the observable process changes its probability characteristics. We study a Bayesian formulation of this problem for an observable Brownian motion with switching constant drift rates. The method of proof is based on the reduction of the initial problem to an associated optimal switching problem for...
-
作者：Goldberg, David A.; Katz-Rogozhnikov, Dmitriy A.; Lu, Yingdong; Sharma, Mayank; Squillante, Mark S.
作者单位：University System of Georgia; Georgia Institute of Technology; International Business Machines (IBM); IBM USA; International Business Machines (IBM); IBM USA
摘要：Lost sales inventory models with large lead times, which arise in many practical settings, are notoriously difficult to optimize due to the curse of dimensionality. In this paper, we show that when lead times are large, a very simple constant-order policy, first studied by Reiman, performs nearly optimally. The main insight of our work is that when the lead time is very large, such a significant amount of randomness is injected into the system between when an order for more inventory is placed...
