Mathematics of Operations Research

最新文章

• A Study of Convex Convex-Composite Functions via Infimal Convolution with Applications AI翻译
  作者：Burke, James, V; Tim, Hoheisel; Nguyen, Quang, V
  作者单位：University of Washington; University of Washington Seattle; McGill University
  摘要：In this paper, we provide a full conjugacy and subdifferential calculus for convex convex-composite functions in finite-dimensional space. Our approach, based on infimal convolution and cone convexity, is straightforward. The results are established under a verifiable Slater-type condition, with relaxed monotonicity and without lower semi continuity assumptions on the functions in play. The versatility of our findings is illustrated by a series of applications in optimization and matrix analys...
• On Polyhedral Approximations of the Positive Semidefinite Cone AI翻译
  作者：Fawzi, Hamza
  作者单位：University of Cambridge
  摘要：It is well known that state-of-the-art linear programming solvers are more efficient than their semidefinite programming counterparts and can scale to much larger problem sizes. This leads us to consider the question, how well can we approximate semidefinite programs with linear programs? In this paper, we prove lower bounds on the size of linear programs that approximate the positive semidefinite cone. Let D be the set of n x n positive semidefinite matrices of trace equal to one. We prove tw...
• The Running Intersection Relaxation of the Multilinear Polytope AI翻译
  作者：Del Pia, Alberto; Khajavirad, Aida
  作者单位：University of Wisconsin System; University of Wisconsin Madison; Lehigh University
  摘要：The multilinear polytope of a hypergraph is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of the multilinear polytope, referred to as the running intersection relaxation, and identify conditions under which this relaxation is tight. Namely, we show that for kite-free beta-acy...
• Fair Allocation of Indivisible Goods: Improvement AI翻译
  作者：Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi
  作者单位：Sharif University of Technology; Institute for Research in Fundamental Sciences IPM; University System of Maryland; University of Maryland College Park
  摘要：We study the problem of fair allocation for indivisible goods. We use the maximin share paradigm introduced by Budish [Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061-1103.] as a measure of fairness. Kurokawa et al. [Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8.] were the first to investigate this fundamental problem in the additive sett...
• Online Learning over a Finite Action Set with Limited Switching AI翻译
  作者：Altschuler, Jason M.; Talwar, Kunal
  作者单位：Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
  摘要：This paper studies the value of switching actions in the Prediction From Experts problem (PFE) and Adversarial Multiarmed Bandits problem (MAB). First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms achieve the minimax optimal order for both regret and switches in expectation; however, high probability guarantees are an open problem. We present the first algorithms that achieve this optimal order for both quantities with high probabil...
• Trust Your Data or Not-StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization AI翻译
  作者：Bomze, Immanuel M.; Kahr, Michael; Leitner, Markus
  作者单位：University of Vienna; University of Vienna; University of Vienna; Vrije Universiteit Amsterdam
  摘要：We consider the robust standard quadratic optimization problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is optimized over the standard simplex. Following most approaches, we model the uncertainty sets by balls, polyhedra, or spectrahedra, more generally, by ellipsoids or order intervals intersected with subcones of the copositive matrix cone. We show that the copositive relaxation gap of the RStQP equals the minimax gap under some mild assumptions on the curvature of...
• Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis AI翻译
  作者：Kim, Jinhak; Tawarmalani, Mohit; Richard, Jean-Philippe P.
  作者单位：Northern Illinois University; Purdue University System; Purdue University; University of Minnesota System; University of Minnesota Twin Cities
  摘要：We develop techniques to convexify a set that is invariant under permutation and/or change of sign of variables and discuss applications of these results. First, we convexify the intersection of the unit ball of a permutation and sign-invariant norm with a cardinality constraint. This gives a nonlinear formulation for the feasible set of sparse principal component analysis (PCA) and an alternative proof of the K-support norm. Second, we characterize the convex hull of sets of matrices defined ...
• Sparse Solutions of a Class of Constrained Optimization Problems AI翻译
  作者：Yang, Lei; Chen, Xiaojun; Xiang, Shuhuang
  作者单位：National University of Singapore; Hong Kong Polytechnic University; Central South University
  摘要：In this paper, we consider a well-known sparse optimization problem that aims to find a sparse solution of a possibly noisy underdetermined system of linear equations. Mathematically, it can be modeled in a unified manner by minimizing parallel to x parallel to(p)(p) subject to parallel to Ax - b parallel to(q) <= sigma for given A is an element of R-mxn, b is an element of R-m, sigma >= 0, 0 <= p <= 1 and q >= 1. We then study various properties of the optimal solutions of this problem. Speci...
• Learning Optimal Forecast Aggregation in Partial Evidence Environments AI翻译
  作者：Babichenko, Yakov; Garber, Dan
  作者单位：Technion Israel Institute of Technology
  摘要：We consider the forecast aggregation problem in repeated settings where the forecasts are of a binary state of nature. In each period multiple experts provide forecasts about the state. The goal of the aggregator is to aggregate those forecasts into a subjective accurate forecast. We assume that the experts are Bayesian and the aggregator is non-Bayesian and ignorant of the information structure (i.e., the distribution over the signals) under which the experts make their forecasts. The aggrega...
• ε-Strong Simulation of Fractional Brownian Motion and Related Stochastic Differential Equations AI翻译
  作者：Chen, Yi; Dong, Jing; Ni, Hao
  作者单位：Northwestern University; Columbia University; University of London; University College London
  摘要：Consider a fractional Brownian motion (fBM) B-H = {B-H(t) : t is an element of [0, 1]} with Hurst index H is an element of (0, 1). We construct a probability space supporting both B-H and a fully simulatable process (B) over cap (H)(epsilon) such that sup(t is an element of[0,1])vertical bar B-H(t) - (B) over cap (H)(epsilon)(t)vertical bar <= epsilon with probability one for any user-specified error bound epsilon > 0. When H > 1/2, we further enhance our error guarantee to the alpha-Holder no...