-
作者：de Klerk, Etienne; Kuhn, Daniel; Postek, Krzysztof
作者单位：Tilburg University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam
摘要：In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a knownambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distributions that give nature too much freedom to inflict damage. We thus introduce a new class of ambiguity sets that cont...
-
作者：Verdugo, Victor; Verschae, Jose; Wiese, Andreas
作者单位：University of London; London School Economics & Political Science; Universidad de O'Higgins; Universidad de Chile; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：The sum of squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of this hierarchy give integrality gaps matching the best known approximation algorithms. For many other problems, however, ad-hoc techniques give better approximation ratios than SoS in the worst case, as shown by corresponding lower bound instances. Notably, in many cases these insta...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Moran R, Diego A.
作者单位：International Business Machines (IBM); IBM USA; Universidad Adolfo Ibanez
摘要：Given P. Rn, a mixed-integer set PI = P n (Zt x Rn-t), and a k-tuple of ndimensional integral vectors (p1,..., pk) where the last n - t entries of each vector is zero, we consider the relaxation of PI obtained by taking the convex hull of points x in P for which pT 1 x,..., pT k x are integral. We then define the k-dimensional lattice closure of PI to be the intersection of all such relaxations obtained from k-tuples of n-dimensional vectors. When P is a rational polyhedron, we show that given...
-
作者：Johnstone, Patrick R.; Moulin, Pierre
作者单位：Rutgers University System; Rutgers University New Brunswick; University of Illinois System; University of Illinois Urbana-Champaign
摘要：The purpose of this manuscript is to derive new convergence results for several subgradient methods applied to minimizing nonsmooth convex functions with Holderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and weakly sharp minima as special cases. To this end there are three main contributions. First, for a constant and sufficiently small stepsize, we show that the subgradient method achieves linear convergence up to a certain r...
-
作者：Basu, Amitabh; Conforti, Michele; Di Summa, Marco
作者单位：Johns Hopkins University; University of Padua
摘要：We consider Gomory and Johnson's infinite group model with a single row. Valid inequalities for this model are expressed by valid functions and it has been recently shown that any valid function is dominated by some nonnegative valid function, modulo the affine hull of the model. Within the set of nonnegative valid functions, extreme functions are the ones that cannot be expressed as convex combinations of two distinct valid functions. In this paper we construct an extreme function pi:R ->[0,1...
-
作者：Klatte, Diethard; Kummer, Bernd
作者单位：University of Zurich; Humboldt University of Berlin
-
作者：Ahmadi, Amir Ali; Zhang, Jeffrey
作者单位：Princeton University
摘要：We prove that unlessP=NP there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known Frank-Wolfe type theorems imply that exactly one of two cases can occur: either the optimal value is attained on every instance, or it is strongly NP-...
-
作者：D'Ambrosio, Claudia; Liberti, Leo; Poirion, Pierre-Louis; Vu, Ky
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; RIKEN; FPT University
摘要：Random projections map a set of points in a high dimensional space to a lower dimensional one while approximately preserving all pairwise Euclidean distances. Although random projections are usually applied to numerical data, we show in this paper that they can be successfully applied to quadratic programming formulations over a set of linear inequality constraints. Instead of solving the higher-dimensional original problem, we solve the projected problem more efficiently. This yields a feasib...
-
作者：Graf, Lukas; Harks, Tobias; Sering, Leon
作者单位：Technical University of Berlin
摘要：We study dynamic network flows and introduce a notion of instantaneous dynamic equilibrium (IDE) requiring that for any positive inflow into an edge, this edge must lie on a currently shortest path towards the respective sink. We measure current shortest path length by current waiting times in queues plus physical travel times. As our main results, we show: existence and constructive computation of IDE flows for multi-source single-sink networks assuming constant network inflow rates, finite t...
-
作者：Menickelly, Matt; Wild, Stefan M.
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
摘要：We develop an algorithm for minimax problems that arise in robust optimization in the absence of objective function derivatives. The algorithm utilizes an extension of methods for inexact outer approximation in sampling a potentially infinite-cardinality uncertainty set. Clarke stationarity of the algorithm output is established alongside desirable features of the model-based trust-region subproblems encountered. We demonstrate the practical benefits of the algorithm on a new class of test pro...
