-
作者：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...
-
作者：Combettes, Patrick L.; Eckstein, Jonathan
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite Paris Cite; Sorbonne Universite; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
摘要：We propose new primal-dual decomposition algorithms for solving systems of inclusions involving sums of linearly composed maximally monotone operators. The principal innovation in these algorithms is that they are block-iterative in the sense that, at each iteration, only a subset of the monotone operators needs to be processed, as opposed to all operators as in established methods. Flexible strategies are used to select the blocks of operators activated at each iteration. In addition, we allo...
-
作者：Marandi, Ahmadreza; den Hertog, Dick
作者单位：Tilburg University
摘要：Adjustable robust optimization (ARO) generally produces better worst-case solutions than static robust optimization (RO). However, ARO is computationally more difficult than RO. In this paper, we provide conditions under which the worst-case objective values of ARO and RO problems are equal. We prove that when the uncertainty is constraint-wise, the problem is convex with respect to the adjustable variables and concave with respect to the uncertain parameters, the adjustable variables lie in a...
-
作者：Yang, Boshi; Anstreicher, Kurt; Burer, Samuel
作者单位：Clemson University; University of Iowa
摘要：Let be a quadratically constrained, possibly nonconvex, bounded set, and let denote ellipsoids contained in with non-intersecting interiors. We prove that minimizing an arbitrary quadratic over is no more difficult than minimizing over in the following sense: if a given semidefinite-programming (SDP) relaxation for is tight, then the addition of l linear constraints derived from yields a tight SDP relaxation for . We also prove that the convex hull of equals the intersection of the convex hull...
