-
作者：Abdi, Ahmad; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Korea Advanced Institute of Science & Technology (KAIST)
摘要：Take a prime power q, an integer n >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 2$$\end{document}, and a coordinate subspace S subset of GF(q)n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \use...
-
作者：Liu, Shutian; Zhu, Quanyan
作者单位：New York University; New York University Tandon School of Engineering
摘要：Risk measures are commonly used to capture the risk preferences of decision-makers (DMs). The decisions of DMs can be nudged or manipulated when their risk preferences are influenced by factors such as the availability of information about the uncertainties. This work proposes a Stackelberg risk preference design (STRIPE) problem to capture a designer's incentive to influence DMs' risk preferences. STRIPE consists of two levels. In the lower level, individual DMs in a population, known as the ...
-
作者：Xu, Liding; Liberti, Leo
作者单位：Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; Ecole Polytechnique
摘要：We study a mixed-integer set S:={(x,t)is an element of{0,1}nxR:f(x)>= t}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {S}:=\{(x,t) \in \{0,1\}<^>n \times \mathbb {R}: f(x) \ge t\}$$\end{document} arising in the submodular maximization problem, where f is a submodular function defined over {0,1}n\document...
-
作者：Joswig, Michael; Klimm, Max; Spitz, Sylvain
作者单位：Technical University of Berlin; Max Planck Society; Technical University of Berlin
摘要：The difference set of an outcome in an auction is the set of types that the auction mechanism maps to the outcome. We give a complete characterization of the geometry of the difference sets that can appear for a dominant strategy incentive compatible multi-unit auction showing that they correspond to regular subdivisions of the unit cube. Similarly, we describe the geometry for affine maximizers for n players and m items, showing that they correspond to regular subdivisions of the m-fold produ...
-
作者：Hoppenot, Pierre; Martin, Mathis; Szigeti, Zoltan
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
-
作者：Zhang, Richard Y.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider minimizing a twice-differentiable, L-smooth, and mu -strongly convex objective 4 over an n x n positive semidefinite matrix M 0, under the assumption that the minimizer M* has low rank r* << n . Following the Burer-Monteiro approach, we instead minimize the nonconvex objective f (X) = 4 (XXT) over a factor matrix X of size nxr. This substantially reduces the number of variables from O(n2) to as few as O(n) and also enforces positive semidefiniteness for free, but at the cost of giv...
-
作者：van Doornmalen, Jasper; Hojny, Christopher
作者单位：Eindhoven University of Technology
摘要：Handling symmetries in optimization problems is essential for devising efficient solution methods. In this article, we present a general framework that captures many of the already existing symmetry handling methods. While these methods are mostly discussed independently from each other, our framework allows to apply different methods simultaneously and thus outperforming their individual effect. Moreover, most existing symmetry handling methods only apply to binary variables. Our framework al...
-
作者：Hu, Yaohua; Hu, Xinlin; Yang, Xiaoqi
作者单位：Shenzhen University; Audencia; Shenzhen University; Hong Kong Polytechnic University
摘要：This paper aims to find an approximate true sparse solution of an underdetermined linear system. For this purpose, we propose two types of iterative thresholding algorithms with the continuation technique and the truncation technique respectively. We introduce a notion of limited shrinkage thresholding operator and apply it, together with the restricted isometry property, to show that the proposed algorithms converge to an approximate true sparse solution within a tolerance relevant to the noi...
-
作者：Upadhyaya, Manu; Banert, Sebastian; Taylor, Adrien B.; Giselsson, Pontus
作者单位：Lund University; Inria; Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL
摘要：We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In particular, we consider (i) classes of optimization problems of finite-sum form with (possibly strongly) convex and possibly smooth functional components, (ii) first-order methods that can be written as a linear system on state-space form in feedback interconnection with the subdifferentials of the functional component...
-
作者：Munoz, Gonzalo; Paat, Joseph; Xavier, Alinson S.
作者单位：Universidad de O'Higgins; University of British Columbia; United States Department of Energy (DOE); Argonne National Laboratory
摘要：A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB treeTthat certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node inTor (2) removing leaves fromT? We believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by co...
