-
作者：Cartis, Coralia; Roberts, Lindon
作者单位：University of Oxford; Australian National University
摘要：We introduce a general framework for large-scale model-based derivative-free optimization based on iterative minimization within random subspaces. We present a probabilistic worst-case complexity analysis for our method, where in particular we prove high-probability bounds on the number of iterations before a given optimality is achieved. This framework is specialized to nonlinear least-squares problems, with a model-based framework based on the Gauss-Newton method. This method achieves scalab...
-
作者：Del Pia, Alberto; Linderoth, Jeff; Zhu, Haoran
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus, we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have a number of interesting properties. First, they generalize the well-known (1, k)-configuration inequalities. Second, they are no...
-
作者：Josz, Cedric; Lai, Lexiao
作者单位：Columbia University
-
作者：Guo, Shaoyan; Xu, Huifu
作者单位：Dalian University of Technology; Chinese University of Hong Kong
摘要：Sample average approximation which is also known as Monte Carlo method has been widely used for solving stochastic programming and equilibrium problems. In a data-driven environment, samples are often drawn from empirical data and hence may be potentially contaminated. Consequently it is legitimate to ask whether statistical estimators obtained from solving the sample average approximated problems are statistically robust, that is, the difference between the laws of the statistical estimators ...
-
作者：Teboulle, Marc; Vaisbourd, Yakov
作者单位：Tel Aviv University; McGill University
摘要：This work presents a novel analysis that allows to achieve tight complexity bounds of gradient-based methods for convex optimization. We start by identifying some of the pitfalls rooted in the classical complexity analysis of the gradient descent method, and show how they can be remedied. Our methodology hinges on elementary and direct arguments in the spirit of the classical analysis. It allows us to establish some new (and reproduce known) tight complexity results for several fundamental alg...
-
作者：Jin, Qiujiang; Mokhtari, Aryan
作者单位：University of Texas System; University of Texas Austin
摘要：In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon-Fletcher-Powell (DFP) method and the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite-time local convergence rate is not fully investigated. In this paper, we provide a finite-time (non-asymptot...
-
作者：Wu, Zijun; Moehring, Rolf H.; Ren, Chunying; Xu, Dachuan
作者单位：Hefei University; Technical University of Berlin; Beijing University of Technology
摘要：We analyze the convergence of the price of anarchy (PoA) of Nash equilibria in atomic congestion games with growing total demand T. When the cost functions are polynomials of the same degree, we obtain explicit rates for a rapid convergence of the PoAs of pure and mixed Nash equilibria to 1 in terms of 1/T and d(max)/T, where d(max) is the maximum demand controlled by an individual. Similar convergence results carry over to the random inefficiency of the random flow induced by an arbitrary mix...
-
作者：Kapelevich, Lea; Coey, Chris; Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Polynomial nonnegativity constraints can often be handled using the sum of squares condition. This can be efficiently enforced using semidefinite programming formulations, or as more recently proposed by Papp and Yildiz (Papp D in SIAM J O 29: 822-851, 2019), using the sum of squares cone directly in an interior point algorithm. Beyond nonnegativity, more complicated polynomial constraints (in particular, generalizations of the positive semidefinite, second order and l(1)-norm cones) can also ...
-
作者：Haddadan, Arash; Newman, Alantha
作者单位：Carnegie Mellon University; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes and in proving bounds for 2-edge-connected subgraph problem, but not much was known in this direction for gluing connected multigraphs. We apply this approach to the traveling salesman problem (TSP) in the case when the objective function of the subtour elimination relaxation is minimized by a theta-cyclic point: x(...
-
作者：Slot, Lucas; Laurent, Monique
作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
摘要：We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube B-n = {0, 1}(n). This hierarchy provides for each integer r epsilon N a lower bound f((r)) on the minimum f(min) of f, given by the largest scalar lambda for which the polynomial f - lambda is a sum-of-squares on B-n with degree at most 2r. We analyze the quality of these bounds by estimating the worstcase error f(min) - f((r)) in terms of the least roots of the Kr...
