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