-
作者：Glaeser, Max; Pfetsch, Marc E.
作者单位：Technical University of Darmstadt
摘要：This article investigates smallest branch-and-bound trees and their computation. We first revisit the notion of hiding sets to deduce lower bounds on the size of branch-and bound trees for certain binary programs, using both variable disjunctions and general disjunctions. We then provide exponential lower bounds for variable disjunctions by a disjoint composition of smaller binary programs. Moreover, we investigate the complexity of finding small branch-and-bound trees using variable disjuncti...
-
作者：Lim, Tongseok
作者单位：Purdue University System; Purdue University
摘要：The theory of Optimal Transport and Martingale Optimal Transport (MOT) were inspired by problems in economics and finance and have flourished over the past decades, making significant advances in theory and practice. MOT considers the problem of pricing and hedging of a financial instrument, referred to as an option, assuming its payoff depends on a single asset price. In this paper we introduce Vectorial Martingale Optimal Transport (VMOT) problem, which considers the more general and realist...
-
作者：Tang, Tianyun; Toh, Kim-Chuan
作者单位：National University of Singapore; National University of Singapore
摘要：In this paper, we focus on using the low-rank factorization approach to solve the SDP relaxation of a graph equipartition problem, which involves an additional spectral upper bound over the traditional linear SDP. We discuss the equivalence between the decomposed problem and the original SDP problem. We also derive a sufficient condition, under which a second order stationary point of the non-convex problem is also a global minimum. Moreover, the constraints of the non-convex problem involve a...
-
作者：Cecchetto, Federica; Traub, Vera; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Bonn; University of Bonn
摘要：The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the...
-
作者：Wang, Jun-Kun; Abernethy, Jacob; Levy, Kfir Y.
作者单位：Yale University; University System of Georgia; Georgia Institute of Technology; Technion Israel Institute of Technology
摘要：We develop an algorithmic framework for solving convex optimization problems using no-regret game dynamics. By converting the problem of minimizing a convex function into an auxiliary problem of solving a min-max game in a sequential fashion, we can consider a range of strategies for each of the two-players who must select their actions one after the other. A common choice for these strategies are so-called no-regret learning algorithms, and we describe a number of such and prove bounds on the...
-
作者：Oertel, Timm; Paat, Joseph; Weismantel, Robert
作者单位：University of Erlangen Nuremberg; University of British Columbia; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：The Steinitz constant in dimension d is the smallest value c(d) such that for any norm on R-d and for any finite zero-sum sequence in the unit ball, the sequence can be permuted such that the norm of each partial sum is bounded by c(d). Grinberg and Sevastyanov prove that c(d) = d and that the bound of d is best possible for arbitrary norms; we refer to their result as the Steinitz Lemma. We present a variation of the Steinitz Lemma that permutes multiple sequences at one time. Our result, whi...
-
作者：Dadush, Daniel; Huiberts, Sophie; Natura, Bento; Vegh, Laszlo A.
作者单位：Columbia University; University System of Georgia; Georgia Institute of Technology; University of London; London School Economics & Political Science
摘要：Following the breakthrough work of Tardos (Oper Res 34:250-256, 1986) in the bit-complexity model, Vavasis and Ye (Math Program 74(1):79-120, 1996) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear program (LP) max c(T)x, Ax = b, x >= 0, A is an element of R-mxn, Vavasis and Ye developed a primal-dual interior point method using a 'layered least squares' (LLS) step, and showed t...
-
作者：Asl, Azam; Lu, Haihao; Yang, Jinwen
作者单位：University of Chicago
摘要：Minimax problems have gained tremendous attentions across the optimization and machine learning community recently. In this paper, we introduce a new quasi-Newton method for the minimax problems, which we call J-symmetric quasi-Newton method. The method is obtained by exploiting the J-symmetric structure of the second-order derivative of the objective function in minimax problem. We show that the Hessian estimation (as well as its inverse) can be updated by a rank-2 operation, and it turns out...
-
作者：Klep, Igor; Magron, Victor; Volcic, Jurij; Wang, Jie
作者单位：University of Ljubljana; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); Drexel University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：This paper introduces state polynomials, i.e., polynomials in noncommuting variables and formal states of their products. A state analog of Artin's solution to Hilbert's 17th problem is proved showing that state polynomials, positive over all matrices and matricial states, are sums of squares with denominators. Somewhat surprisingly, it is also established that a Krivine-Stengle Positivstellensatz fails to hold in the state polynomial setting. Further, archimedean Positivstellensatze in the sp...
-
作者：Xie, Yue; Wright, Stephen J.
作者单位：University of Hong Kong; University of Hong Kong; University of Wisconsin System; University of Wisconsin Madison
摘要：This paper describes a method for solving smooth nonconvex minimization problems subject to bound constraints with good worst-case complexity guarantees and practical performance. The method contains elements of two existing methods: the classi-cal gradient projection approach for bound-constrained optimization and a recently proposed Newton-conjugate gradient algorithm for unconstrained nonconvex opti-mization. Using a new definition of approximate second-order optimality parametrized by some...
