1-2期

最新文章

• Revisiting augmented Lagrangian duals AI翻译
  作者：Cordova, M.; Oliveira, W. de; Sagastizabal, C.
  作者单位：Universidade Federal de Santa Catarina (UFSC); Universite PSL; MINES ParisTech; Universidade Estadual de Campinas
  摘要：For nonconvex optimization problems, possibly having mixed-integer variables, a convergent primal-dual solution algorithm is proposed. The approach applies a proximal bundle method to certain augmented Lagrangian dual that arises in the context of the so-called generalized augmented Lagrangians. We recast these Lagrangians into the framework of a classical Lagrangian by means of a special reformulation of the original problem. Thanks to this insight, the methodology yields zero duality gap. La...
• Popular branchings and their dual certificates AI翻译
  作者：Kavitha, Telikepalli; Kiraly, Tamas; Matuschke, Jannik; Schlotter, Ildiko; Schmidt-Kraepelin, Ulrike
  作者单位：Tata Institute of Fundamental Research (TIFR); Eotvos Lorand University; KU Leuven; HUN-REN; HUN-REN Centre for Economic & Regional Studies; Budapest University of Technology & Economics; Technical University of Berlin
  摘要：Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in...
• Fully polynomial time (Σ, Π)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs AI翻译
  作者：Halman, Nir; Nannicini, Giacomo
  作者单位：Bar Ilan University; International Business Machines (IBM); IBM USA
  摘要：We study the nonlinear newsvendor problem concerning goods of a non-discrete nature, and a class of stochastic dynamic programs with several application areas such as supply chain management and economics. The class is characterized by continuous state and action spaces, either convex or monotone cost functions that are accessed via value oracles, and affine transition functions. We establish that these problems cannot be approximated to any degree of either relative or additive error, regardl...
• Adaptive Sampling line search for local stochastic optimization with integer variables AI翻译
  作者：Ragavan, Prasanna K.; Hunter, Susan R.; Pasupathy, Raghu; Taaffe, Michael R.
  作者单位：Purdue University System; Purdue University; Purdue University System; Purdue University; Virginia Polytechnic Institute & State University
  摘要：We consider optimization problems with an objective function that is estimable using a Monte Carlo oracle, constraint functions that are known deterministically through a constraint-satisfaction oracle, and integer decision variables. Seeking an appropriately defined local minimum, we propose an iterative adaptive sampling algorithm that, during each iteration, performs a statistical local optimality test followed by a line search when the test detects a stochastic descent direction. We prove ...
• Semidefinite programming hierarchies for constrained bilinear optimization AI翻译
  作者：Berta, Mario; Borderi, Francesco; Fawzi, Omar; Scholz, Volkher B.
  作者单位：Ecole Normale Superieure de Lyon (ENS de LYON); Centre National de la Recherche Scientifique (CNRS); Ghent University
  摘要：We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[H(D circle times E)], maximized with respect to semidefinite constraints on D and E. Applied to the problem of approximate error correction in quantum information theory, this gives hierarchies of efficiently computable outer bounds on the success probability of approximate quantum error correction codes in any dimension. The first level of our hierarchies corresponds to a...
• Rates of superlinear convergence for classical quasi-Newton methods AI翻译
  作者：Rodomanov, Anton; Nesterov, Yurii
  作者单位：Universite Catholique Louvain; Universite Catholique Louvain
  摘要：We study the local convergence of classical quasi-Newton methods for nonlinear optimization. Although it was well established a long time ago that asymptotically these methods converge superlinearly, the corresponding rates of convergence still remain unknown. In this paper, we address this problem. We obtain first explicit non-asymptotic rates of superlinear convergence for the standard quasi-Newton methods, which are based on the updating formulas from the convex Broyden class. In particular...
• Constructing lattice-free gradient polyhedra in dimension two AI翻译
  作者：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...
• Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles AI翻译
  作者：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 ...
• k-Point semidefinite programming bounds for equiangular lines AI翻译
  作者：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.
• Sparse optimization on measures with over-parameterized gradient descent AI翻译
  作者：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...