2期

最新文章

• Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints AI翻译
  作者：Kim, Sunyoung; Kojima, Masakazu; Toh, Kim-Chuan
  作者单位：Ewha Womans University; Chuo University; National University of Singapore; National University of Singapore
  摘要：We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to which an accelerated bisection and projection (BP) algorithm is applied. The COP involves a single equality constraint in a matrix variable which is restricted ...
• General bounds for incremental maximization AI翻译
  作者：Bernstein, Aaron; Disser, Yann; Gross, Martin; Himburg, Sandra
  作者单位：Rutgers University System; Rutgers University New Brunswick; Technical University of Darmstadt; University of Waterloo
  摘要：We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardinality/support of the solution is bounded by a value k is an element of N that grows over time, and we allow the solution to be extended one element at a time. We investigate the best-possible competitive ratio of such an incremental solution, i.e., the worst ratio over all kbetween the incremental solution after kst...
• Complete positivity and distance-avoiding sets AI翻译
  作者：DeCorte, Evan; Filho, Fernando Mario de Oliveira; Vallentin, Frank
  作者单位：McGill University; Delft University of Technology; University of Cologne
  摘要：We introduce the cone of completely positive functions, a subset of the cone of positive-type functions, and use it to fully characterize maximum-density distance-avoiding sets as the optimal solutions of a convex optimization problem. As a consequence of this characterization, it is possible to reprove and improve many results concerning distance-avoiding sets on the sphere and in Euclidean space.
• Performance guarantees of local search for minsum scheduling problems AI翻译
  作者：Correa, Jose R.; Munoz, Felipe T.
  作者单位：Universidad de Chile; Universidad del Bio-Bio
  摘要：We study the worst-case performance guarantee of locally optimal solutions for the problem of minimizing the total weighted and unweighted completion time on parallel machine environments. Our method makes use of a mapping that maps a schedule into an inner product space so that the norm of the mapping is closely related to the cost of the schedule. We apply the method to study the most basic local search heuristics for scheduling, namely jump and swap, and establish their worst-case performan...
• Convex graph invariant relaxations for graph edit distance AI翻译
  作者：Candogan, Utkan Onur; Chandrasekaran, Venkat
  作者单位：California Institute of Technology; California Institute of Technology
  摘要：The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex...
• Sparse noncommutative polynomial optimization AI翻译
  作者：Klep, Igor; Magron, Victor; Povh, Janez
  作者单位：University of Ljubljana; Centre National de la Recherche Scientifique (CNRS); University of Ljubljana
  摘要：This article focuses on optimization of polynomials in noncommuting variables, while taking into account sparsity in the input data. A converging hierarchy of semidefinite relaxations for eigenvalue and trace optimization is provided. This hierarchy is a noncommutative analogue of results due to Lasserre (SIAM J Optim 17(3):822-843, 2006) and Waki et al. (SIAM J Optim 17(1):218-242, 2006). The Gelfand-Naimark-Segal construction is applied to extract optimizers if flatness and irreducibility co...
• Smoothed analysis for tensor methods in unsupervised learning AI翻译
  作者：Bhaskara, Aditya; Chen, Aidao; Perreault, Aidan; Vijayaraghavan, Aravindan
  作者单位：Utah System of Higher Education; University of Utah; Northwestern University
  摘要：Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in high-dimensional data analysis and unsupervised learning. While polynomial time smoothed analysis guarantees have been obtained for worst-case intractable problems like tensor decomposition and learning mixtures of Gaussians, such guarantees have been hard to obtain for several other important problems in data analysis. A core technical challenge in analyzing algorithms is obtaining lower bounds on the least si...
• A hybrid stochastic optimization framework for composite nonconvex optimization AI翻译
  作者：Quoc Tran-Dinh; Pham, Nhan H.; Phan, Dzung T.; Nguyen, Lam M.
  作者单位：University of North Carolina; University of North Carolina Chapel Hill; International Business Machines (IBM); IBM USA
  摘要：We introduce a new approach to develop stochastic optimization algorithms for a class of stochastic composite and possibly nonconvex optimization problems. The main idea is to combine a variance-reduced estimator and an unbiased stochastic one to create a new hybrid estimator which trades-off the variance and bias, and possesses useful properties for developing new algorithms. We first introduce our hybrid estimator and investigate its fundamental properties to form a foundational theory for a...
• Complexity of stochastic dual dynamic programming AI翻译
  作者：Lan, Guanghui
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：Stochastic dual dynamic programming is a cutting plane type algorithm for multi-stage stochastic optimization originated about 30 years ago. In spite of its popularity in practice, there does not exist any analysis on the convergence rates of this method. In this paper, we first establish the number of iterations, i.e., iteration complexity, required by a basic dual dynamic programming method for solving single-scenario multi-stage optimization problems, by introducing novel mathematical tools...
• 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...