3期

最新文章

• Bound-Constrained Polynomial Optimization Using Only Elementary Calculations AI翻译
  作者：de Klerk, Etienne; Lasserre, Jean B.; Laurent, Monique; Sun, Zhao
  作者单位：Tilburg University; Delft University of Technology; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centrum Wiskunde & Informatica (CWI)
  摘要：We provide a monotone nonincreasing sequence of upper bounds f(k)(H) (k >= 1) converging to the global minimum of a polynomial f on simple sets like the unit hypercube in R-n. The novelty with respect to the converging sequence of upper bounds in Lasserre [Lasserre JB (2010) A new look at nonnegativity on closed sets and polynomial optimization, SIAM J. Optim. 21: 864-885] is that only elementary computations are required. For optimization over the hypercube [0,1](n), we show that the new boun...
• Matroids Are Immune to Braess' Paradox AI翻译
  作者：Fujishige, Satoru; Goemans, Michel X.; Harks, Tobias; Peis, Britta; Zenklusen, Rico
  作者单位：Kyoto University; Massachusetts Institute of Technology (MIT); University of Augsburg; RWTH Aachen University; Swiss Federal Institutes of Technology Domain; ETH Zurich; Johns Hopkins University
  摘要：The famous Braess paradox describes the counterintuitive phenomenon in which, in certain settings, an increase of resources, such as a new road built within a congested network, may in fact lead to larger costs for the players in an equilibrium. In this paper, we consider general nonatomic congestion games and give a characterization of the combinatorial property of strategy spaces for which the Braess paradox does not occur. In short, matroid bases are precisely the required structure. We pro...
• Polynomial-Time Computation of Strong and n-Present-Value Optimal Policies in Markov Decision Chains AI翻译
  作者：O'Sullivan, Michael; Veinott, Arthur F., Jr.
  作者单位：University of Auckland; Stanford University
  摘要：This paper studies the problem of finding a stationary strong present-value optimal and, more generally, an n-present-value optimal, policy for an infinite-horizon stationary finite-state-action substochastic Markov decision chain. A policy is strong present-value optimal if it has maximum present value for all small positive interest rates rho. A policy is n-present-value optimal if its present value falls below the maximum present value for all small positive rho by O(rho(n+1)). The importan...
• Convergence Rate Analysis for the Alternating Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming AI翻译
  作者：He, Bingsheng; Tao, Min; Yuan, Xiaoming
  作者单位：Southern University of Science & Technology; Nanjing University; Hong Kong Baptist University
  摘要：Recently, in He et al. [He BS, Tao M, Yuan XM (2012) Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2):313-340], we have showed the first possibility of combining the Douglas-Rachford alternating direction method of multipliers (ADMM) with a Gaussian back substitution procedure for solving a convex minimization model with a general separable structure. This paper is a further study on this theme. We first derive a general algori...
• Optimal Dynamic Risk Taking AI翻译
  作者：Subramanian, Ajay; Yang, Baozhong
  作者单位：University System of Georgia; Georgia State University; University System of Georgia; Georgia State University
  摘要：We analyze a continuous-time stochastic control problem that arises in the study of several important issues in financial economics. An agent controls the drift and volatility of a diffusion output process by dynamically selecting one of an arbitrary (but finite) number of projects and the termination time. The optimal policy depends on the projects' risk-adjusted drifts that are determined by their drifts, volatilities, and the curvature (or relative risk aversion) of the agent's payoff funct...
• An ε-Nash Equilibrium with High Probability for Strategic Customers in Heavy Traffic AI翻译
  作者：Atar, Rami; Saha, Subhamay
  作者单位：Technion Israel Institute of Technology; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Guwahati
  摘要：A multiclass queue with many servers is considered, where customers make a join-or-leave decision upon arrival based on queue length information, without knowing the state of other queues. A game theoretic formulation is proposed and analyzed, that takes advantage of a phenomenon unique to heavy traffic regimes, namely, Reiman's snaphshot principle, by which waiting times are predicted with high precision by the information available upon arrival. The payoff considered is given as a random var...
• A Generalization of the Borkar-Meyn Theorem for Stochastic Recursive Inclusions AI翻译
  作者：Ramaswamy, Arunselvan; Bhatnagar, Shalabh
  作者单位：Indian Institute of Science (IISC) - Bangalore
  摘要：In this paper, the stability theorem of Borkar and Meyn is extended to include the case when the mean field is a set-valued map. Two different sets of sufficient conditions are presented that guarantee the stability and convergence of stochastic recursive inclusions. Our work builds on the works of Benaim, Hofbauer and Sorin as well as Borkar and Meyn. As a corollary to one of the main theorems, a natural generalization of the Borkar and Meyn theorem follows. In addition, the original theorem ...
• Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization AI翻译
  作者：Wen, Zheng; Van Roy, Benjamin
  作者单位：Adobe Systems Inc.; Stanford University
  摘要：We consider the problem of reinforcement learning over episodes of a finite-horizon deterministic system and as a solution propose optimistic constraint propagation (OCP), an algorithm designed to synthesize efficient exploration and value function generalization. We establish that when the true value function lies within a given hypothesis class, OCP selects optimal actions over all but at most D episodes, where D is the eluder dimension of the given hypothesis class. We establish further eff...
• Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints AI翻译
  作者：Gayon, Jean-Philippe; Massonnet, Guillaume; Rapine, Christophe; Stauffer, Gautier
  作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); IMT - Institut Mines-Telecom; IMT Atlantique; Universite de Lorraine
  摘要：We consider a well-studied multi-echelon (deterministic) inventory control problem, known in the literature as the one-warehouse multi-retailer (OWMR) problem. We propose a simple and fast 2-approximation algorithm for this NP-hard problem, by recombining the solutions of single-echelon relaxations at the warehouse and at the retailers. We then show that our approach remains valid under quite general assumptions on the cost structures and under capacity constraints at some retailers. In partic...
• Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions AI翻译
  作者：Davis, Damek; Yin, Wotao
  作者单位：Cornell University; University of California System; University of California Los Angeles
  摘要：In this paper, we provide a comprehensive convergence rate analysis of the Douglas-Rachford splitting (DRS), Peaceman-Rachford splitting (PRS), and alternating direction method of multipliers (ADMM) algorithms under various regularity assumptions including strong convexity, Lipschitz differentiability, and bounded linear regularity. The main consequence of this work is that relaxed PRS and ADMM automatically adapt to the regularity of the problem and achieve convergence rates that improve upon...