-
作者：Jia, Xinrui; Sheth, Kshiteej; Svensson, Ola
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challen...
-
作者：Blekherman, Grigoriy; Madhusudhana, Bharath Hebbe
作者单位：University System of Georgia; Georgia Institute of Technology; University of Munich
摘要：Quantum states are represented by positive semidefinite Hermitian operators with unit trace, known as density matrices. An important subset of quantum states is that of separable states, the complement of which is the subset of entangled states. We show that the problem of deciding whether a quantum state is entangled can be seen as amoment problem in real analysis. Only a small number of such moments are accessible experimentally, and so in practice the question of quantum entanglement of a m...
-
作者：Garatti, S.; Campi, M. C.
作者单位：Polytechnic University of Milan; University of Brescia
摘要：Scenario optimization is a broad methodology to perform optimization based on empirical knowledge. One collects previous cases, called scenarios, for the set-up in which optimization is being performed, and makes a decision that is optimal for the cases that have been collected. For convex optimization, a solid theory has been developed that provides guarantees of performance, and constraint satisfaction, of the scenario solution. In this paper, we open a new direction of investigation: the ri...
-
作者：Bolusani, Suresh; Ralphs, Ted K.
作者单位：Lehigh University
摘要：We describe a framework for reformulating and solving optimization problems that generalizes the well-known framework originally introduced by Benders. We discuss details of the application of the procedures to several classes of optimization problems that fall under the umbrella of multilevel/multistage mixed integer linear optimization problems. The application of this abstract framework to this broad class of problems provides new insights and a broader interpretation of the core ideas, esp...
-
作者：Wiebe, J.; Cecilio, I; Dunlop, J.; Misener, R.
作者单位：Imperial College London; Schlumberger
摘要：Optimization problems with uncertain black-box constraints, modeled by warped Gaussian processes, have recently been considered in the Bayesian optimization setting. This work considers optimization problems with aggregated black-box constraints. Each aggregated black-box constraint sums several draws from the same black-box function with different decision variables as arguments in each individual black-box term. Such constraints are important in applications where, e.g., safety-critical meas...
-
作者：Munoz, Gonzalo; Serrano, Felipe
作者单位：Universidad de O'Higgins; Zuse Institute Berlin
摘要：The intersection cut paradigm is a powerful framework that facilitates the generation of valid linear inequalities, or cutting planes, for a potentially complex set S. The key ingredients in this construction are a simplicial conic relaxation of S and an S-free set: a convex zone whose interior does not intersect S. Ideally, such S-free set would be maximal inclusion-wise, as it would generate a deeper cutting plane. However, maximality can be a challenging goal in general. In this work, we sh...
-
作者：Lendl, Stefan; Peis, Britta; Timmermans, Veerle
作者单位：University of Graz; Graz University of Technology; RWTH Aachen University
摘要：Given two matroids M-1 = (E, B-1) and M-2 = (E, B-2) on a common ground set E with base sets B-1 and B-2, some integer k is an element of N, and two cost functions c(1), c(2) : E -> R, we consider the optimization problem to find a basis X is an element of B-1 and a basis Y is an element of B-2 minimizing the cost Sigma(e is an element of X) c(1)(e) + Sigma(e is an element of Y) c(2)(e) subject to either a lower bound constraint | X boolean AND Y| <= k, an upper bound constraint | X boolean AN...
-
作者：Conforti, Michele; Fiorini, Samuel; Huynh, Tony; Weltge, Stefan
作者单位：University of Padua; Universite Libre de Bruxelles; Monash University; Technical University of Munich
摘要：Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC'17) for bimodular integer programs can be used to find a maximum weight stable set in G in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-O(n(2)) extended formulation for the stable set polytope of G.
-
作者：Latafat, Puya; Themelis, Andreas; Patrinos, Panagiotis
作者单位：KU Leuven; Kyushu University
摘要：This paper analyzes block-coordinate proximal gradient methods for minimizing the sum of a separable smooth function and a (nonseparable) nonsmooth function, both of which are allowed to be nonconvex. The main tool in our analysis is the forward-backward envelope, which serves as a particularly suitable continuous and real-valued Lyapunov function. Global and linear convergence results are established when the cost function satisfies the Kurdyka-Lojasiewicz property without imposing convexity ...
-
作者：Frandsen, Abraham; Ge, Rong
作者单位：Duke University
摘要：Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gradient descent have become popular in practice. In this paper, we characterize the optimization landscape of the Tucker decomposition problem. In particular, we show that if the tensor has an exact Tucker decomposition, for a standard nonconve...
