-
作者：Cvetkovic, Aleksandar; Protasov, Vladimir Yu
作者单位：Gran Sasso Science Institute (GSSI); Lomonosov Moscow State University
摘要：We address the problems of minimizing and of maximizing the spectral radius over a compact family of non-negative matrices. Those problems being hard in general can be efficiently solved for some special families. We consider the so-called product families, where each matrix is composed of rows chosen independently from given sets. A recently introduced greedy method works very fast. However, it is applicable mostly for strictly positive matrices. For sparse matrices, it often diverges and giv...
-
作者：Ge, Rong; Ma, Tengyu
作者单位：Duke University; Stanford University
摘要：Non-convex optimization with local search heuristics has been widely used in machine learning, achieving many state-of-art results. It becomes increasingly important to understand why they can work for these NP-hard problems on typical data. The landscape of many objective functions in learning has been conjectured to have the geometric property that all local optima are (approximately) global optima, and thus they can be solved efficiently by local search algorithms. However, establishing suc...
-
作者：Paat, Joseph; Schloter, Miriam; Speakman, Emily
作者单位：University of British Columbia; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Colorado System; University of Colorado Denver
摘要：Lattice-free gradient polyhedra can be used to certify optimality for mixed integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables under the assumption that all level sets are bounded. In this setting, a classic result of Bell, Doignon, and Scarf states the existence of a lattice-free gradient polyhedron with at most four facets. We present an algorithm for creating a sequence of gradient polyhedra, each of which has...
-
作者：Kobayashi, Yusuke
作者单位：Kyoto University
摘要：The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give the first polynomial-time algorithm for the weighted T-free 2-matching problem ...
-
作者：de Laat, David; Machado, Fabricio Caluza; de Oliveira Filho, Fernando Mario; Vallentin, Frank
作者单位：Delft University of Technology; Universidade de Sao Paulo; University of Cologne
摘要：We propose a hierarchy of k-point bounds extending the Delsarte-Goethals-Seidel linear programming 2-point bound and the Bachoc-Vallentin semidefinite programming 3-point bound for spherical codes. An optimized implementation of this hierarchy allows us to compute 4, 5, and 6-point bounds for the maximum number of equiangular lines in Euclidean space with a fixed common angle.
-
作者：Chizat, Lenaic
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay
摘要：Minimizing a convex function of a measure with a sparsity-inducing penalty is a typical problem arising, e.g., in sparse spikes deconvolution or two-layer neural networks training. We show that this problem can be solved by discretizing the measure and running non-convex gradient descent on the positions and weights of the particles. For measures on a d-dimensional manifold and under some non-degeneracy assumptions, this leads to a global optimization algorithm with a complexity scaling as log...
-
作者：Atamturk, Alper; Narayanan, Vishnu
作者单位：University of California System; University of California Berkeley; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
摘要：Using polarity, we give an outer polyhedral approximation for the epigraph of set functions. For a submodular function, we prove that the corresponding polar relaxation is exact; hence, it is equivalent to the Lovasz extension. The polar approach provides an alternative proof for the convex hull description of the epigraph of a submodular function. Computational experiments show that the inequalities from outer approximations can be effective as cutting planes for solving submodular as well as...
-
作者：Kozhasov, Khazhgali; Lasserre, Jean Bernard
作者单位：Braunschweig University of Technology; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite de Toulouse
摘要：We show that the Euclidean ball has the smallest volume among sublevel sets of nonnegative forms of bounded Bombieri norm as well as among sublevel sets of sum of squares forms whose Gram matrix has bounded Frobenius or nuclear (or, more generally, p-Schatten) norm. These volume-minimizing properties of the Euclidean ball with respect to its representation (as a sublevel set of a form of fixed even degree) complement its numerous intrinsic geometric properties. We also provide a probabilistic ...
-
作者：Stozhkov, Vladimir; Buchanan, Austin; Butenko, Sergiy; Boginski, Vladimir
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater; Texas A&M University System; Texas A&M University College Station; State University System of Florida; University of Central Florida
摘要：The celebrated Motzkin-Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Turan's theorem in graph theory, but was later used to develop competitive algorithms for the maximum clique problem based on continuous optimization. Clique relaxations, such ass-defective clique ands-plex, emerged a...
-
作者：de Klerk, Etienne; Laurent, Monique
作者单位：Tilburg University; Centrum Wiskunde & Informatica (CWI)
摘要：We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre (SIAM J Optim 21(3):864-885, 2011), for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r is an element of N of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respe...
