Month: August 2017

Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Semi-definite Programming Tags , ,

    In this paper we study bipartite quantum correlations using techniques from tracial polynomial optimization. We construct a hierarchy of semidefinite programming lower bounds on the minimal entanglement dimension of a bipartite correlation. This hierarchy converges to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum … Read more

    Lower bounds on matrix factorization ranks via noncommutative polynomial optimization

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Semi-definite Programming Tags ,

    We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogues: the completely positive rank and the completely positive semidefinite rank. We study the convergence properties of our hierarchies, compare them … Read more

    On the effectiveness of primal and dual heuristics for the transportation problem

  • Jonas Schwinn
  • Ralf Werner
    • Categories Linear Programming, Optimization Software Benchmark

    The transportation problem is one of the most popular problems in linear programming. Over the course of time a multitude of exact solution methods and heuristics have been proposed. Due to substantial progress of exact solvers since the mid of the last century, the interest in heuristics for the transportation problem over the last few … Read more

    FOM — A MATLAB Toolbox of First Order Methods for Solving Convex Optimization Problems

  • Amir Beck
  • Nili Guttmann-Beck
    • Categories Optimization Software and Modeling Systems

    This paper presents the FOM MATLAB toolbox for solving convex optimization problems using first order methods. The diverse features of the eight solvers included in the package are illustrated through a collection of examples of different nature. Article Download View FOM — A MATLAB Toolbox of First Order Methods for Solving Convex Optimization Problems

    The Adaptive Robust Multi-Period Alternating Current Optimal Power Flow Problem

  • Alvaro Lorca
  • Xu Andy Sun
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , ,

    This paper jointly addresses two major challenges in power system operations: i) dealing with non-convexity in the power flow equations, and ii) systematically capturing uncertainty in renewable power availability and in active and reactive power consumption at load buses. To overcome these challenges, this paper proposes a two-stage adaptive robust optimization model for the multi-period … Read more

    Optimized Assignment Patterns in Mobile Edge Cloud Networks

  • Alberto Ceselli
  • Marco Fiore
  • Marco Premoli
  • Stefano Secci
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Telecommunications Tags , , ,

    Given an existing Mobile Edge Cloud (MEC) network including virtualization facilities of limited capacity, and a set of mobile Access Points (AP) whose data traffic demand changes over time, we aim at finding plans for assigning APs traffic to MEC facilities so that the demand of each AP is satisfied and MEC facility capacities are … Read more

    On Affine Invariant Descent Directions

  • Yu-Hong Dai
  • Florian Jarre
  • Felix Lieder
    • Categories Nonlinear Optimization Tags , ,

    This paper explores the existence of affine invariant descent directions for unconstrained minimization. While there may exist several affine invariant descent directions for smooth functions $f$ at a given point, it is shown that for quadratic functions there exists exactly one invariant descent direction in the strictly convex case and generally none in the nondegenerate … Read more

    Distributionally robust simple integer recourse

  • Shabbir Ahmed
  • Weijun Xie
    • Categories Integer Programming, Robust Optimization, Stochastic Programming Tags , , , ,

    The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two stage stochastic linear programming. Structural properties and approximations of SIR … Read more

    Dynamic Scaling and Submodel Selection in Bundle Methods for Convex Optimization

  • Christoph Helmberg
  • Alois Pichler
    • Categories Convex and Nonsmooth Optimization Tags ,

    Bundle methods determine the next candidate point as the minimizer of a cutting model augmented with a proximal term. We propose a dynamic approach for choosing a quadratic proximal term based on subgradient information from past evaluations. For the special case of convex quadratic functions, conditions are studied under which this actually reproduces the Hessian. … Read more

    A Data-Driven Distributionally Robust Bound on the Expected Optimal Value of Uncertain Mixed 0-1 Linear Programming

  • Samuel Burer
  • Guanglin Xu
    • Categories Robust Optimization, Semi-definite Programming, Stochastic Programming

    This paper studies the expected optimal value of a mixed 0-1 programming problem with uncertain objective coefficients following a joint distribution. We assume that the true distribution is not known exactly, but a set of independent samples can be observed. Using the Wasserstein metric, we construct an ambiguity set centered at the empirical distribution from … Read more