-
作者：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...
