-
作者：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...
-
作者：Cifuentes, Diego; Agarwal, Sameer; Parrilo, Pablo A.; Thomas, Rekha R.
作者单位：University System of Georgia; Georgia Institute of Technology; Alphabet Inc.; Google Incorporated; University of Washington; University of Washington Seattle; Massachusetts Institute of Technology (MIT)
摘要：We consider a parametric family of quadratically constrained quadratic programs and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the parameter at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood around the nominal value. Our framework captures a wide array of statistical estimation problems including tensor principal component an...
-
作者：Hirai, Hiroshi; Ikeda, Motoki
作者单位：University of Tokyo
摘要：In this paper, we address the minimum-cost node-capacitated multiflow problem in undirected networks. For this problem, Babenko and Karzanov (JCO 24: 202-228, 2012) showed strong polynomial-time solvability via the ellipsoid method. Our result is the first combinatorial polynomial-time algorithm for this problem. Our algorithm finds a half-integral minimum-cost maximum multiflow in O(mlog(nCD)SF(kn,m,k)) time, where n is the number of nodes, m is the number of edges, k is the number of termina...
-
作者：Faenza, Yuri; Munoz, Gonzalo; Pokutta, Sebastian
作者单位：Columbia University; Universidad de O'Higgins; Zuse Institute Berlin; Technical University of Berlin
摘要：Sparse structures are frequently sought when pursuing tractability in optimization problems. They are exploited from both theoretical and computational perspectives to handle complex problems that become manageable when sparsity is present. An example of this type of structure is given by treewidth: a graph theoretical parameter that measures how tree-like a graph is. This parameter has been used for decades for analyzing the complexity of various optimization problems and for obtaining tracta...
-
作者：Fairbrother, Jamie; Turner, Amanda; Wallace, Stein W.
作者单位：Lancaster University; Norwegian School of Economics (NHH)
摘要：Scenario generation is the construction of a discrete random vector to represent parameters of uncertain values in a stochastic program. Most approaches to scenario generation aredistribution-driven, that is, they attempt to construct a random vector which captures well in a probabilistic sense the uncertainty. On the other hand, aproblem-drivenapproach may be able to exploit the structure of a problem to provide a more concise representation of the uncertainty. In this paper we propose an ana...
-
作者：Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin
作者单位：Technical University of Berlin; Technical University of Darmstadt
摘要：We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are APX-hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategy...
