-
作者：Sviridenko, Maxim; Vondrak, Jan; Ward, Justin
作者单位：Yahoo! Inc; Stanford University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or minimize a monotone decreasing supermodular function with a bounded total curvature c. Intuitively, the parameter c represents how nonlinear a function f is: when c = 0, f is linear, while for c = 1, f may be an arbitrary monotone increasing...
-
作者：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...
-
作者：Babichenko, Yakov; Barman, Siddharth; Peretz, Ron
作者单位：Technion Israel Institute of Technology; Indian Institute of Science (IISC) - Bangalore; Bar Ilan University
摘要：We show that in any n-player, m-action normal-form game, we can obtain an approximate equilibrium by sampling any mixed-action equilibrium a small number of times. We study three types of equilibria: Nash, correlated, and coarse-correlated. For each one we obtain upper and lower bounds on the number of samples required for the empirical distribution over the sampled action profiles to form an approximate equilibrium with probability close to 1. These bounds imply that using a small number of s...
-
作者：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
-
作者：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...
-
作者：Bauschke, Heinz H.; Bolte, Jerome; Teboulle, Marc
作者单位：University of British Columbia; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Tel Aviv University
摘要：The proximal gradient and its variants is one of the most attractive first-order algorithm for minimizing the sum of two convex functions, with one being nonsmooth. However, it requires the differentiable part of the objective to have a Lipschitz continuous gradient, thus precluding its use in many applications. In this paper we introduce a framework which allows to circumvent the intricate question of Lipschitz continuity of gradients by using an elegant and easy to check convexity condition ...
-
作者：Pang, Jong-Shi; Razaviyayn, Meisam; Alvarado, Alberth
作者单位：University of Southern California
摘要：Motivated by a class of applied problems arising from physical layer based security in a digital communication system, in particular, by a secrecy sum-rate maximization problem, this paper studies a nonsmooth, difference-of-convex (dc) minimization problem. The contributions of this paper are (i) clarify several kinds of stationary solutions and their relations; (ii) develop and establish the convergence of a novel algorithm for computing a d-stationary solution of a problem with a convex feas...
-
作者：Del Pia, Alberto; Khajavirad, Aida
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Carnegie Mellon University
摘要：We study the polyhedral convex hull of a mixed-integer set S defined by a collection of multilinear equations over the unit hypercube. Such sets appear frequently in the factorable reformulation of mixed-integer nonlinear optimization problems. In particular, the set S represents the feasible region of a linearized unconstrained binary polynomial optimization problem. We define an equivalent hypergraph representation of the mixed-integer set S, which enables us to derive several families of fa...
