-
作者：Torrico, Alfredo; Ahmed, Shabbir; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We study the i.i.d. online bipartite matching problem, a dynamic version of the classical model where one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various relaxations of the polyhedral set of achievable matching probabilities, introduce valid inequalities, and discuss when they are facet-defining. We also show how several...
-
作者：Correa, Rafael; Hantoute, Abderrahim; Perez-Aros, Pedro
作者单位：Universidad de Chile; Universidad de Chile; Universidad de Chile; Universidad de O'Higgins; Universidad de Chile
摘要：In this work we give an extension of the Brondsted-Rockafellar Theorem, and some of its important consequences, to proper convex lower-semicontinuous epi-pointed functions defined in locally convex spaces. We use a new approach based on a simple variational principle, which also allows recovering the classical results in a natural way.
-
作者：Parpas, Panos; Ralph, Daniel; Wiesemann, Wolfram
作者单位：Imperial College London; Imperial College London; University of Cambridge
-
作者：Jara-Moroni, Francisco; Pang, Jong-Shi; Wachter, Andreas
作者单位：Northwestern University; University of Southern California
摘要：This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results,...
-
作者：Beck, Amir; Pauwels, Edouard; Sabach, Shoham
作者单位：Technion Israel Institute of Technology; Universite de Toulouse; Universite Toulouse III - Paul Sabatier
摘要：We introduce the notion of predicted decrease approximation (PDA) for constrained convex optimization, a flexible framework which includes as special cases known algorithms such as generalized conditional gradient, proximal gradient, greedy coordinate descent for separable constraints and working set methods for linear equality constraints with bounds. The new scheme allows the development of a unified convergence analysis for these methods. We further consider a partially strongly convex nons...
-
作者：Ahmadian, Sara; Hosseinzadeh, Hamideh; Sanita, Laura
作者单位：University of Waterloo; Alzahra University
摘要：Cooperative matching games (Shapley and Shubik) and Network bargaining games (Kleinberg and Tardos) are games described by an undirected graph, where the vertices represent players. An important role in such games is played by stable graphs, that are graphs whose set of inessential vertices (those that are exposed by at least one maximum matching) are pairwise non adjacent. In fact, stable graphs characterize instances of such games that admit the existence of stable outcomes. In this paper, w...
-
作者：Lambrechts, Erik; Ficker, Annette M. C.; Goossens, Dries R.; Spieksma, Frits C. R.
作者单位：KU Leuven; KU Leuven; Ghent University
摘要：The Circle Method is widely used in the field of sport scheduling to generate schedules for round-robintournaments. If in such a tournament, team A played team B in its previous match and is now playing team C, team C is said to receive a carry-over effect from team B. The so-called carry-over effect value is a number that can be associated to each round-robin schedule; it represents a degree of unbalancedness of the schedule with respect to carry-over. Here, we prove that, for an even number ...
-
作者：Esfahani, Peyman Mohajerin; Kuhn, Daniel
作者单位：Delft University of Technology; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributio...
-
作者：Bauschke, Heinz H.; Schaad, Jason; Wang, Xianfu
作者单位：University of British Columbia
摘要：The problem of finding a zero of the sum of two maximally monotone operators is of central importance in optimization. One successful method to find such a zero is the Douglas-Rachford algorithm which iterates a firmly nonexpansive operator constructed from the resolvents of the given monotone operators. In the context of finding minimizers of convex functions, the resolvents are actually proximal mappings. Interestingly, as pointed out by Eckstein in 1989, the Douglas-Rachford operator itself...
-
作者：Lubin, Miles; Yamangil, Emre; Bent, Russell; Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT); United States Department of Energy (DOE); Los Alamos National Laboratory
摘要：Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solut...
