2022

最新文章

• Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets AI翻译
  作者：Slot, Lucas; Laurent, Monique
  作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
  摘要：We consider the problem of computing the minimum value fmin, K of a polynomial f over a compact set K. Rn, which can be reformulated as finding a probability measure. on K minimizing K f d.. Lasserre showed that it suffices to consider such measures of the form. = q mu, where q is a sum-of-squares polynomial and mu is a given Borel measure supported on K. By bounding the degree of q by 2r one gets a converging hierarchy of upper bounds f (r) for fmin, K. When K is the hypercube [-1, 1]n, equip...
• Non-convex exact community recovery in stochastic block model AI翻译
  作者：Wang, Peng; Zhou, Zirui; So, Anthony Man-Cho
  作者单位：Chinese University of Hong Kong; Huawei Technologies
  摘要：Community detection in graphs that are generated according to stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the binary symmetric SBM-in which a graph of n vertices is randomly generated by first partitioning the vertices into two equal-sized communities and then connecting each pair of vertices with probability that depends on their community memberships-and study the associated exact community recovery problem. Although the maximum-likelihood fo...
• Sparse regression at scale: branch-and-bound rooted in first-order optimization AI翻译
  作者：Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We consider the least squares regression problem, penalized with a combination of the l(0) and squared l(2) penalty functions (a.k.a. l(0)l(2) regularization). Recent work shows that the resulting estimators enjoy appealing statistical properties in many high-dimensional settings. However, exact computation of these estimators remains a major challenge. Indeed, modern exact methods, based on mixed integer programming (MIP), face difficulties for problems where the number of features p similar ...
• 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...
• A primal-dual algorithm for risk minimization AI翻译
  作者：Kouri, Drew P.; Surowiec, Thomas M.
  作者单位：United States Department of Energy (DOE); Sandia National Laboratories; Philipps University Marburg
  摘要：In this paper, we develop an algorithm to efficiently solve risk-averse optimization problems posed in reflexive Banach space. Such problems often arise in many practical applications as, e.g., optimization problems constrained by partial differential equations with uncertain inputs. Unfortunately, for many popular risk models including the coherent risk measures, the resulting risk-averse objective function is nonsmooth. This lack of differentiability complicates the numerical approximation o...