-
作者：Lozano, Leonardo; Smith, J. Cole
作者单位：Clemson University; Clemson University
摘要：We consider a special class of two-stage stochastic integer programming problems with binary variables appearing in both stages. The class of problems we consider constrains the second-stage variables to belong to the intersection of sets corresponding to first-stage binary variables that equal one. Our approach seeks to uncover strong dual formulations to the second-stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. We demonstrat...
-
作者：Del Pia, Alberto; Ma, Mingchen
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of n Delta on the proximity of optimal solutions of an Integer Linear Programming problem and its standard linear relaxation. In this bound, n is the number of variables and Delta denotes the maximum of the absolute values of the subdeterminants of the constraint matrix. Hochbaum and Shanthikumar, and Werman and Magagnosc showed that the same upper bound is valid if a more general convex function is minimized, ins...
-
作者：Dragomir, Radu-Alexandru; Taylor, Adrien B.; D'Aspremont, Alexandre; Bolte, Jerome
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Universite PSL; Ecole Normale Superieure (ENS); Inria; Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：We provide a lower bound showing that the O(1/k) convergence rate of the NoLips method (a.k.a. Bregman Gradient or Mirror Descent) is optimal for the class of problems satisfying the relative smoothness assumption. This assumption appeared in the recent developments around the Bregman Gradient method, where acceleration remained an open issue. The main inspiration behind this lower bound stems from an extension of the performance estimation framework of Drori and Teboulle (Mathematical Program...
-
作者：Rodriguez-Heck, Elisabeth; Stickler, Karl; Walter, Matthias; Weltge, Stefan
作者单位：RWTH Aachen University; University of Twente; Technical University of Munich
摘要：The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of other LP formulations have been studied and one may wonder wh...
-
作者：Wang, Alex L.; Kilinc-Karzan, Fatma
作者单位：Carnegie Mellon University
摘要：Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study conditions under which the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such sufficient conditions. Then using this framework, we show that the SDP relaxation is tight whenever the quadratic eigenvalue multiplicity, a parameter capturing the amount of symmetry...
-
作者：Slot, Lucas; Laurent, Monique
作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
摘要：We consider the problem of computing the minimum value fmin, K of a polynomial f over a compact set K. Rn, which can be reformulated as finding a probability measure. on K minimizing K f d.. Lasserre showed that it suffices to consider such measures of the form. = q mu, where q is a sum-of-squares polynomial and mu is a given Borel measure supported on K. By bounding the degree of q by 2r one gets a converging hierarchy of upper bounds f (r) for fmin, K. When K is the hypercube [-1, 1]n, equip...
-
作者：Wang, Peng; Zhou, Zirui; So, Anthony Man-Cho
作者单位：Chinese University of Hong Kong; Huawei Technologies
摘要：Community detection in graphs that are generated according to stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the binary symmetric SBM-in which a graph of n vertices is randomly generated by first partitioning the vertices into two equal-sized communities and then connecting each pair of vertices with probability that depends on their community memberships-and study the associated exact community recovery problem. Although the maximum-likelihood fo...
-
作者：Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider the least squares regression problem, penalized with a combination of the l(0) and squared l(2) penalty functions (a.k.a. l(0)l(2) regularization). Recent work shows that the resulting estimators enjoy appealing statistical properties in many high-dimensional settings. However, exact computation of these estimators remains a major challenge. Indeed, modern exact methods, based on mixed integer programming (MIP), face difficulties for problems where the number of features p similar ...
-
作者：Cordova, M.; Oliveira, W. de; Sagastizabal, C.
作者单位：Universidade Federal de Santa Catarina (UFSC); Universite PSL; MINES ParisTech; Universidade Estadual de Campinas
摘要：For nonconvex optimization problems, possibly having mixed-integer variables, a convergent primal-dual solution algorithm is proposed. The approach applies a proximal bundle method to certain augmented Lagrangian dual that arises in the context of the so-called generalized augmented Lagrangians. We recast these Lagrangians into the framework of a classical Lagrangian by means of a special reformulation of the original problem. Thanks to this insight, the methodology yields zero duality gap. La...
-
作者：Kavitha, Telikepalli; Kiraly, Tamas; Matuschke, Jannik; Schlotter, Ildiko; Schmidt-Kraepelin, Ulrike
作者单位：Tata Institute of Fundamental Research (TIFR); Eotvos Lorand University; KU Leuven; HUN-REN; HUN-REN Centre for Economic & Regional Studies; Budapest University of Technology & Economics; Technical University of Berlin
摘要：Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in...
