-
作者：Chandra, Ashish; Tawarmalani, Mohit
作者单位：Purdue University System; Purdue University
摘要：This paper develops various optimization techniques to estimate probability of events where the optimal value of a convex program, satisfying certain structural assumptions, exceeds a given threshold. First, we relate the search of affine/polynomial policies for the robust counterpart to existing relaxation hierarchies in MINLP (Lasserre in Proceedings of the international congress of mathematicians (ICM 2018), 2019; Sherali and Adams in A reformulation-linearization technique for solving disc...
-
作者：Wei, Linchuan; Gomez, Andres; Kucukyavuz, Simge
作者单位：Northwestern University; University of Southern California
摘要：Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a o...
-
作者：Klein, Kim-Manuel
作者单位：University of Kiel
摘要：We consider so called 2-stage stochastic integer programs (IPs) and their generalized form, so calledmulti-stage stochastic IPs. A2-stage stochastic IP is an integer program of the form max{c(T) x vertical bar Ax = b, l <= x <= u, x epsilon Z(s+nt)} where the constraint matrix A epsilon Z(rnxs+nt) consists roughly of n repetitions of a matrix A epsilon Z(rxs) on the vertical line and n repetitions of a matrix B epsilon Z(rxt) on the diagonal. In this paper we improve upon an algorithmic result...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Huynh, Tony; Lee, Dabeen
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; Monash University; Institute for Basic Science - Korea (IBS)
摘要：A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that, for some integer k >= 4, every k-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it for k = 4 for the class of binary clutters. Two key ingredients for our proof are Jaeger's 8-flow theorem for graphs, and Seymour's characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture,...
-
作者：Beer, G.; Canovas, M. J.; Lopez, M. A.; Parra, J.
作者单位：California State University System; California State University Los Angeles; Universidad Miguel Hernandez de Elche; Universitat d'Alacant; Federation University Australia
-
作者：Zhang, Haixiang; Milzarek, Andre; Wen, Zaiwen; Yin, Wotao
作者单位：University of California System; University of California Berkeley; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shenzhen Institute of Artificial Intelligence & Robotics for Society; Peking University; Peking University; University of California System; University of California Los Angeles
摘要：This paper considers the problem of solving a special quartic-quadratic optimization problem with a single sphere constraint, namely, finding a global and local minimizer of 1/2z*Az + beta/2 Sigma(n)(k=1) vertical bar z(k)vertical bar(4) such that parallel to z parallel to(2) = 1. This problem spans multiple domains including quantum mechanics and chemistry sciences and we investigate the geometric properties of this optimization problem. Fourth-order optimality conditions are derived for char...
-
作者：Pashkovich, Kanstantsin
作者单位：University of Ottawa
摘要：In cooperative games, players have a possibility to form different coalitions. This leads to the questions about ways to motivate all players to collaborate, i.e. to motivate the players to form the so-called grand coalition. One of such ways is captured by the concept of nucleolus, which dates back to Babylonian Talmud. Weighted voting games form a class of cooperative games, that are often used to model decision making processes in parliaments. In this paper, we provide an algorithm for comp...
-
作者：van Hoeve, Willem-Jan
作者单位：Carnegie Mellon University
摘要：We introduce an iterative framework for solving graph coloring problems using decision diagrams. The decision diagram compactly represents all possible color classes, some of which may contain edge conflicts. In each iteration, we use a constrained minimum network flow model to compute a lower bound and identify conflicts. Infeasible color classes associated with these conflicts are removed by refining the decision diagram. We prove that in the best case, our approach may use exponentially sma...
-
作者：Lu, Cheng; Hochbaum, Dorit S.
作者单位：University of California System; University of California Berkeley
摘要：We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush-Kuhn-Tucker optimality conditions. This approach is shown here t...
-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：The present work is the first member of a pair of papers concerning decreasingly-minimal (dec-min) elements of a set of integral vectors, where a vector is dec-min if its largest component is as small as possible, within this, the next largest component is as small as possible, and so on. This discrete notion, along with its fractional counterpart, showed up earlier in the literature under various names. The domain we consider is an M-convex set, that is, the set of integral elements of an int...
