2023

最新文章

• On the integrality gap of binary integer programs with Gaussian data AI翻译
  作者：Borst, Sander; Dadush, Daniel; Huiberts, Sophie; Tiwari, Samarth
  作者单位：Centrum Wiskunde & Informatica (CWI)
  摘要：For a binary integer program (IP) max c(T)x, Ax <= b, x is an element of {0, 1}(n), where A is an element of R-mxn and c is an element of R-n have independent Gaussian entries and the right-hand side b is an element of R-m satisfies that its negative coordinates have l(2) norm at most n/10, we prove that the gap between the value of the linear programming relaxation and the IP is upper bounded by poly(m)(log n)(2)/n with probability at least 1 - 2/n(7) - 2(-poly(m)). Our results give a Gaussia...
• A new perspective on low-rank optimization AI翻译
  作者：Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean
  作者单位：Massachusetts Institute of Technology (MIT); Imperial College London; International Business Machines (IBM); IBM USA; University of London; London Business School
  摘要：A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable relaxations. We invoke the matrix perspective function-the matrix analog of the perspective function-to characterize explicitly the convex hull of epigraphs of simple matrix convex functions under low-rank constraints. Further, we combine the matrix p...
• k-median: exact recovery in the extended stochastic ball model AI翻译
  作者：Del Pia, Alberto; Ma, Mingchen
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
  摘要：We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (Relax, no need to round: integrality of clustering formulations. arXiv:1408.4045, 2015; in: Proceedings of the 2015 conference on innovations in theoretical computer science, pp 191-200, 2015), the authors give a tight result for the k-median LP in the SBM, saying that exact recovery can be achieved as long as the balls are pairwise disjoint. W...
• Exact computation of an error bound for the balanced linear complementarity problem with unique solution AI翻译
  作者：Dussault, Jean-Pierre; Gilbert, Jean Charles
  作者单位：University of Sherbrooke
  摘要：This paper considers the balanced form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang and published in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a satisfactory upper estimate of that factor in terms of the data bitlength when the data is formed of rational numbers. Along the way, we show that,...
• Complexity of optimizing over the integers AI翻译
  作者：Basu, Amitabh
  作者单位：Johns Hopkins University
  摘要：In the first part of this paper, we present a unified framework for analyzing the algorithmic complexity of any optimization problem, whether it be continuous or discrete in nature. This helps to formalize notions like input, size and complexity in the context of general mathematical optimization, avoiding context dependent definitions which is one of the sources of difference in the treatment of complexity within continuous and discrete optimization. In the second part of the paper, we employ...
• New valid inequalities and formulations for the static joint Chance-constrained Lot-sizing problem AI翻译
  作者：Zhang, Zeyang; Gao, Chuanhou; Luedtke, James
  作者单位：Zhejiang University; University of Wisconsin System; University of Wisconsin Madison
  摘要：We study the static joint chance-constrained lot-sizing problem, in which production decisions over a planning horizon are made before knowing random future demands, and the inventory variables are then determined by the demand realizations. The joint chance constraint imposes a service level requirement that the probability that all demands are met on time be above a threshold. We model uncertain outcomes with a finite set of scenarios and begin by applying existing results about chance-const...
• Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints AI翻译
  作者：Oliveira, Roberto, I; Thompson, Philip
  作者单位：Purdue University System; Purdue University; Purdue University System; Purdue University
  摘要：We derive new and improved non-asymptotic deviation inequalities for the sample average approximation (SAA) of an optimization problem. Our results give strong error probability bounds that are sub-Gaussian even when the randomness of the problem is fairly heavy tailed. Additionally, we obtain good (often optimal) dependence on the sample size and geometrical parameters of the problem. Finally, we allow for random constraints on the SAA and unbounded feasible sets, which also do not seem to ha...
• On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones AI翻译
  作者：Song, Dogyoon; Parrilo, Pablo A.
  作者单位：University of Michigan System; University of Michigan; Massachusetts Institute of Technology (MIT)
  摘要：We study the problem of approximating the cone of positive semidefinite (PSD) matrices with a cone that can be described by smaller-sized PSD constraints. Specifically, we ask the question: how closely can we approximate the set of unit-trace nxn PSD matrices, denoted by D, using at most N number of k x k PSD constraints? In this paper, we prove lower bounds on N to achieve a good approximation of D by considering two constructions of an approximating set. First, we consider the unit-trace nxn...
• Computational aspects of relaxation complexity: possibilities and limitations AI翻译
  作者：Averkov, Gennadiy; Hojny, Christopher; Schymura, Matthias
  作者单位：Brandenburg University of Technology Cottbus; Eindhoven University of Technology
  摘要：The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the smallest number of facets of any polyhedron P such that the integer points in P coincide with X. It is a useful tool to investigate the existence of compact linear descriptions of X. In this article, we derive tight and computable upper bounds on rc(Q)(X), a variant of rc(X) in which the polyhedra P are required to be rational, and we show that rc(X) can be computed in polynomial time if X is 2-dime...
• First- and second-order optimality conditions for second-order cone and semidefinite programming under a constant rank condition AI翻译
  作者：Andreani, Roberto; Haeser, Gabriel; Mito, Leonardo M.; Ramirez, Hector; Silveira, Thiago P.
  作者单位：Universidade Estadual de Campinas; Universidade de Sao Paulo; Universidad de Chile; Universidad de Chile
  摘要：The well known constant rank constraint qualification [Math. Program. Study 21:110-126, 1984] introduced by Janin for nonlinear programming has been recently extended to a conic context by exploiting the eigenvector structure of the problem. In this paper we propose a more general and geometric approach for defining a new extension of this condition to the conic context. The main advantage of our approach is that we are able to recast the strong second-order properties of the constant rank con...