-
作者：Bungert, Leon; Roith, Tim; Wacker, Philipp
作者单位：University of Wurzburg; Helmholtz Association; Deutsches Elektronen-Synchrotron (DESY); University of Canterbury
摘要：In this paper we propose polarized consensus-based dynamics in order to make consensus-based optimization (CBO) and sampling (CBS) applicable for objective functions with several global minima or distributions with many modes, respectively. For this, we polarize the dynamics with a localizing kernel and the resulting model can be viewed as a bounded confidence model for opinion formation in the presence of common objective. Instead of being attracted to a common weighted mean as in the origina...
-
作者：Burer, Samuel
作者单位：University of Iowa
摘要：Globally optimizing a nonconvex quadratic over the intersection of m balls in Rn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}<^>n$$\end{document} is known to be polynomial-time solvable for fixed m. Moreover, when m=1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{a...
-
作者：Harks, Tobias; Schwarz, Julian
作者单位：University of Passau
摘要：We consider generalized Nash equilibrium problems (GNEPs) with non-convex strategy spaces and non-convex cost functions. This general class of games includes the important case of games with mixed-integer variables for which only a few results are known in the literature. We present a new approach to characterize equilibria via a convexification technique using the Nikaido-Isoda function. To any given instance of the GNEP, we construct a set of convexified instances and show that a feasible st...
-
作者：Poremba, Joseph; Shepherd, F. Bruce
作者单位：University of British Columbia
摘要：In multicommodity network flows, a supply-demand graph pair (G, H) (called a multiflow topology) is cut-sufficient if, for all capacity and demand weights, the cut condition is enough to guarantee the existence of a feasible multiflow. We characterize cut-sufficiency for two classes of directed 2-commodity flows: roundtrip demands, where H is a 2-cycle, and 2-path demands, where H is a directed path of length two. We then extend these characterizations to some larger demand graphs, namely dire...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; University of Waterloo
摘要：A rational number is dyadic if it has a finite binary representation p/2k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p/2<^>k$$\end{document}, where p is an integer and k is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-poin...
-
作者：Ilandarideva, Sasila; Juditsky, Anatoli; Lan, Guanghui; Li, Tianjiao
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); University System of Georgia; Georgia Institute of Technology
摘要：We consider a class of stochastic smooth convex optimization problems under rather general assumptions on the noise in the stochastic gradient observation. As opposed to the classical problem setting in which the variance of noise is assumed to be uniformly bounded, herein we assume that the variance of stochastic gradients is related to the sub-optimality of the approximate solutions delivered by the algorithm. Such problems naturally arise in a variety of applications, in particular, in the ...
-
作者：Wei, Ningji; Walteros, Jose L.
作者单位：Texas Tech University System; Texas Tech University; State University of New York (SUNY) System; University at Buffalo, SUNY
摘要：Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction games. Specifically, we provide a general characterization of inequalities that a...
-
作者：de Meijer, Frank; Sotirov, Renata
作者单位：Delft University of Technology; Tilburg University
摘要：In this paper we study the well-known Chvatal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of spectrahedra is derived by exploiting total dual integrality for SDPs. Moreover, we show how to exploit (strengthened)...
-
作者：Liu, Peijing; Atamturk, Alper; Gomez, Andres; Kucukyavuz, Simge
作者单位：University of Southern California; University of California System; University of California Berkeley; Northwestern University
摘要：In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising as part of an extended formulation and exploiting the supermodularity of a set function defined on its extreme points. Ou...
-
作者：Gupta, Neelima; Dabas, Rajni; Garg, Naveen
作者单位：University of Delhi; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi
摘要：We consider the capacitated facility location problem with outliers when facility costs are uniform. Our main result is the first constant factor approximation for this problem. We give a local search algorithm that requires only 2 operations and is a 6.373 +& varepsilon;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{documen...
