-
作者：Fawzi, Hamza; Saunderson, James; Parrilo, Pablo A.
作者单位：University of Cambridge; Monash University; Massachusetts Institute of Technology (MIT)
摘要：Given a polytope P subset of R-n, we say that P has a positive semidefinite lift (psd lift) of size d if one can express P as the projection of an affine slice of the d x d positive semidefinite cone. Such a representation allows us to solve linear optimization problems over P using a semidefinite program of size d and can be useful in practice when d is much smaller than the number of facets of P. If a polytope P has symmetry, we can consider equivariant psd lifts, i.e., those psd lifts that ...
-
作者：Herings, P. Jean-Jacques; Predtetchinski, Arkadi
作者单位：Maastricht University
摘要：We consider n-player perfect information games with payoff functions having a finite image. We do not make any further assumptions, so in particular we refrain from making assumptions on the cardinality or the topology of the set of actions and assumptions like continuity or measurability of payoff functions. We show that there exists a best response cycle of length four, that is, a sequence of four pure strategy profiles where every successive element is a best response to the previous one. T...
-
作者：Renault, Jerome; Venel, Xavier
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Paris School of Economics
摘要：We study long-term Markov Decision Processes and Gambling Houses, with applications to any partial observation MDPs with finitely many states and zero-sum repeated games with an informed controller. We consider a decision-maker which is maximizing the weighted sum Sigma(t >= 1) theta(t)r(t), where rt is the expected reward of the t-th stage. We prove the existence of a very strong notion of long-term value called general uniform value, representing the fact that the decision-maker can play wel...
-
作者：Keskin, N. Bora; Zeevi, Assaf
作者单位：Duke University; Columbia University
摘要：We consider a dynamic pricing problem in which a seller faces an unknown demand model that can change over time. The amount of change over a time horizon of T periods is measured using a variation metric that allows for a broad spectrum of temporal behavior. Given a finite variation budget, we first derive a lower bound on the expected performance gap between any pricing policy and a clairvoyant who knows a priori the temporal evolution of the underlying demand model, and then we design famili...
-
作者：Queyranne, Maurice; Tardella, Fabio
作者单位：University of British Columbia; Universite Catholique Louvain; Sapienza University Rome
摘要：The Caratheodory, Helly, and Radon numbers are three main invariants in convexity theory. These invariants have been determined, exactly or approximately, for a number of different convexity structures. We consider convexity structures defined by the sublattices and by the convex sublattices of finite-dimensional Euclidian, integer, and Boolean spaces. Such sublattices arise in submodular optimization (lattice programming) and in monotone comparative statics of optimization and fixed point pro...
-
作者：Buchbinder, Niv; Feldman, Moran; Schwartz, Roy
作者单位：Tel Aviv University; Open University Israel; Technion Israel Institute of Technology
摘要：Fast algorithms for submodular maximization problems have a vast potential use in applicative settings, such as machine learning, social networks, and economics. Though fast algorithms were known for some special cases, only recently such algorithms were considered in the general case of maximizing a monotone submodular function subject to a matroid independence constraint. The known fast algorithm matches the best possible approximation guarantee, while trying to reduce the number of value or...
-
作者：Bo, Lijun; Capponi, Agostino
作者单位：Chinese Academy of Sciences; University of Science & Technology of China, CAS; Chinese Academy of Sciences; Columbia University
摘要：We consider the portfolio decision problem of a risky investor. The investor borrows at a rate higher than his lending rate and invests in a risky bond whose market price is correlated with the credit quality of the investor. By viewing the concave drift of the wealth process as a continuous function of the admissible control, we characterize the optimal strategy in terms of a relation between a critical borrowing threshold and solutions of a system of first-order conditions. We analyze the no...
-
作者：Huang, Chien-Chung; Kavitha, Telikepalli
作者单位：Chalmers University of Technology; Tata Institute of Fundamental Research (TIFR)
摘要：We revisit the classical maximum weight matching problem in general graphs with nonnegative integral edge weights. We present an algorithm that operates by decomposing the problem into W unweighted versions of the problem, where W is the largest edge weight. Our algorithm has running time as good as the current fastest algorithms for the maximum weight matching problem when W is small. One of the highlights of our algorithm is that it also produces an integral optimal dual solution; thus our a...
-
作者：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 ...
-
作者：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...
