-
作者：Bertsimas, Dimitris; Goyal, Vineet
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right-hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm ball) and the probability measure is also ...
-
作者：Rusmevichientong, Paat; Tsitsiklis, John N.
作者单位：Cornell University; Massachusetts Institute of Technology (MIT)
摘要：We consider bandit problems involving a large (possibly infinite) collection of arms, in which the expected reward of each arm is a linear function of an r-dimensional random vector Z is an element of R-r, where r >= 2. The objective is to minimize the cumulative regret and Bayes risk. When the set of arms corresponds to the unit sphere, we prove that the regret and Bayes risk is of order Theta(r root T), by establishing a lower bound for an arbitrary policy, and showing that a matching upper ...
-
作者：Faure, Mathieu; Roth, Gregory
作者单位：University of Neuchatel
摘要：A successful method to describe the asymptotic behavior of a discrete time stochastic process governed by some recursive formula is to relate it to the limit sets of a well-chosen mean differential equation. Under an attainability condition, Benaim proved that convergence to a given attractor of the flow induced by this dynamical system occurs with positive probability for a class of Robbins Monro algorithms. Benaim, Hofbauer, and Sorin generalised this approach for stochastic approximation al...
-
作者：Goberna, M. A.; Terlaky, T.; Todorov, M. I.
作者单位：Universitat d'Alacant; Lehigh University; Bulgarian Academy of Sciences; Universidad Americas Puebla (UDLAP)
摘要：This paper provides sufficient conditions for the optimal value function of a given linear semi-infinite programming (LSIP) problem to depend linearly on the size of the perturbations, when these perturbations involve either the cost coefficients or the right-hand side function or both, and they are sufficiently small. Two kinds of partitions are considered. The first concerns the effective domain of the optimal value as a function of the cost coefficients and consists of maximal regions on wh...
-
作者：Yu, Huizhen; Bertsekas, Dimitri P.
作者单位：University of Helsinki; Massachusetts Institute of Technology (MIT)
摘要：We consider linear fixed point equations and their approximations by projection on a low dimensional subspace. We derive new bounds on the approximation error of the solution, which are expressed in terms of low dimensional matrices and can be computed by simulation. When the fixed point mapping is a contraction, as is typically the case in Markov decision processes (MDP), one of our bounds is always sharper than the standard contraction-based bounds, and another one is often sharper. The form...
-
作者：Andersen, Kent; Louveaux, Quentin; Weismantel, Robert
作者单位：Otto von Guericke University; University of Liege
摘要：A maximal lattice free polyhedron L has max-facet-width equal to w if max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x <= w for all facets pi(T) x <= pi(0) of L, and max(x is an element of L) pi(T) x-min(x is an element of L) pi(T) x = w for some facet pi(T) x <= pi(0) of L. The set obtained by adding all cuts whose validity follows from a maximal lattice free polyhedron with max-facet-width at most w is called the wth split closure. We show the wth split closure is a polyhe...
-
作者：Vazirani, Vijay V.
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：The notion of a market has undergone a paradigm shift with the Internet. Totally new and highly successful markets have been defined and launched by Internet companies, which already form an important part of today's economy and are projected to grow considerably in the future. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner. In view of these new realities, the study of market equilibria, an important, tho...
-
作者：Seifried, Frank Thomas
作者单位：University of Kaiserslautern
摘要：We investigate the optimal portfolio problem under the threat of a financial market crash in a multidimensional jump-diffusion framework. We set up a nonprobabilistic crash model and consider an investor that seeks to maximize CRRA utility in the worst possible crash scenario. We recast the problem as a stochastic differential game; with the help of the fundamental notion of indifference strategies, we completely solve the portfolio problem using martingale arguments.
-
作者：Hoda, Samid; Gilpin, Andrew; Pena, Javier; Sandholm, Tuomas
作者单位：Carnegie Mellon University; Carnegie Mellon University
摘要：We develop first-order smoothing techniques for saddle-point problems that arise in finding a Nash equilibrium of sequential games. The crux of our work is a construction of suitable prox-functions for a certain class of polytopes that encode the sequential nature of the game. We also introduce heuristics that significantly speed up the algorithm, and decomposed game representations that reduce the memory requirements, enabling the application of the techniques to drastically larger games. An ...
-
作者：Lu, Shu
作者单位：University of North Carolina; University of North Carolina Chapel Hill
摘要：This paper studies solution properties of a parametric variational condition under the constant rank constraint qualification (CRCQ), and properties of its underlying set. We start by showing that if the CRCQ holds at a point in a fixed set, then there exists a one-to-one correspondence between the collection of nonempty faces of the normal cone to the set at that point and the collection of active index sets at points nearby. We then study the behavior of the Euclidean projector, and prove un...
