-
作者：Averkov, Gennadiy; Basu, Amitabh
作者单位：Otto von Guericke University; Johns Hopkins University
摘要：We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu et al. (Math Oper Res 37(2):346-355, 2012) for simplicial maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterati...
-
作者：He, Bingsheng; Yuan, Xiaoming
作者单位：Nanjing University; Hong Kong Baptist University
摘要：This note provides a simple proof of a worst-case convergence rate measured by the iteration complexity for the Douglas-Rachford operator splitting method for finding a root of the sum of two maximal monotone set-valued operators. The accuracy of an iterate to the solution set is measured by the residual of a characterization of the original problem, which is different from conventional measures such as the distance to the solution set.
-
作者：Li, G.; Mordukhovich, B. S.; Pham, T. S.
作者单位：University of New South Wales Sydney; Wayne State University; King Fahd University of Petroleum & Minerals; Duy Tan University
摘要：In this paper we derive new fractional error bounds for polynomial systems with exponents explicitly determined by the dimension of the underlying space and the number/degree of the involved polynomials. Our major result extends the existing error bounds from the system involving only a single polynomial to a general polynomial system and do not require any regularity assumptions. In this way we resolve, in particular, some open questions posed in the literature. The developed techniques are l...
-
作者：Briet, Jop; Dadush, Daniel; Pokutta, Sebastian
作者单位：New York University; University System of Georgia; Georgia Institute of Technology
摘要：In Rothvo (Math Program 142(1-2):255-268, 2013) it was shown that there exists a 0/1 polytope (a polytope whose vertices are in ) such that any higher-dimensional polytope projecting to it must have facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high positive semidefinite extension complexity was left open. We answer this question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron projectin...
-
作者：Shitov, Yaroslav
作者单位：HSE University (National Research University Higher School of Economics)
摘要：The tropical arithmetic operations on , defined as and , arise from studying the geometry over non-Archimedean fields. We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to de...
-
作者：Pilanci, Mert; Wainwright, Martin J.; El Ghaoui, Laurent
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：We introduce novel relaxations for cardinality-constrained learning problems, including least-squares regression as a special but important case. Our approach is based on reformulating a cardinality-constrained problem exactly as a Boolean program, to which standard convex relaxations such as the Lasserre and Sherali-Adams hierarchies can be applied. We analyze the first-order relaxation in detail, deriving necessary and sufficient conditions for exactness in a unified manner. In the special c...
-
作者：Mahjoub, A. Ridha; Rinaldi, Giovanni; Woeginger, Gerhard
作者单位：Universite PSL; Universite Paris-Dauphine; Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR); Eindhoven University of Technology
-
作者：Fawzi, Hamza; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：The nonnegative rank of an entrywise nonnegative matrix is the smallest integer such that can be written as where and are both nonnegative. The nonnegative rank arises in different areas such as combinatorial optimization and communication complexity. Computing this quantity is NP-hard in general and it is thus important to find efficient bounding techniques especially in the context of the aforementioned applications. In this paper we propose a new lower bound on the nonnegative rank which, u...
-
作者：Burer, Samuel; Yang, Boshi
作者单位：University of Iowa; University of Iowa
摘要：This paper studies an extended trust region subproblem (eTRS) in which the trust region intersects the unit ball with linear inequality constraints. When , or and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial time. However, it is also known that, when and at least two of the linear constraints intersect within the ball, i.e., some feasible point of the eTRS satisfies both ...
-
作者：Chakrabarti, Amit; Kale, Sagar
作者单位：Dartmouth College
摘要：We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a monotone submodular function on subsets of edges. This problem, which we call maximum submodular-function matching (MSM), is a natural generalization of maximum weight matching (MWM), which is in turn a generalization of maximum cardinality matching. We give two incomparable algorithms for this problem with space usag...
