Monique Laurent

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

    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

    On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs

  • Hao Hu
  • Monique Laurent
    • Categories Graphs and Matroids, Linear Programming Tags , ,

    We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we … Read more

    Comparison of Lasserre’s measure–based bounds for polynomial optimization to bounds obtained by simulated annealing

  • Etienne de Klerk
  • Monique Laurent
    • Categories Global Optimization, Nonlinear Optimization, Semi-definite Programming

    We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864-885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, … Read more

    Matrices with high completely positive semidefinite rank

  • David de Laat
  • Monique Laurent
  • Sander Gribling
    • Categories Linear, Cone and Semidefinite Programming

    A real symmetric matrix M is completely positive semidefinite if it admits a Gram representation by positive semidefinite matrices (of any size d). The smallest such d is called the completely positive semidefinite rank of M, and it is an open question whether there exists an upper bound on this number as a function of … Read more

    Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

  • Etienne de Klerk
  • Monique Laurent
  • Roxana Hess
    • Categories Semi-definite Programming Tags , , , , ,

    We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It … Read more

    On the convergence rate of grid search for polynomial optimization over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Zhao Sun
  • Juan C. Vera
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory Tags ,

    We consider the approximate minimization of a given polynomial on the standard simplex, obtained by taking the minimum value over all rational grid points with given denominator ${r} \in \mathbb{N}$. It was shown in [De Klerk, E., Laurent, M., Sun, Z.: An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric … Read more

    Bound-constrained polynomial optimization using only elementary calculations

  • Etienne de Klerk
  • Jean-Bernard Lasserre
  • Monique Laurent
  • Zhao Sun
    • Categories Bound-constrained Optimization, Global Optimization Theory Tags , ,

    We provide a monotone non increasing sequence of upper bounds $f^H_k$ ($k\ge 1$) converging to the global minimum of a polynomial $f$ on simple sets like the unit hypercube. The novelty with respect to the converging sequence of upper bounds in [J.B. Lasserre, A new look at nonnegativity on closed sets and polynomial optimization, SIAM … Read more

    A Lex-BFS-based recognition algorithm for Robinsonian matrices

  • Monique Laurent
  • Matteo Seminaroti
    • Categories Combinatorial Optimization

    Robinsonian matrices arise in the classical seriation problem and play an important role in many applications where unsorted similarity (or dissimilarity) information must be reordered. We present a new polynomial time algorithm to recognize Robinsonian matrices based on a new characterization of Robinsonian matrices in terms of straight enumerations of unit interval graphs. The algorithm … Read more

    On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings

  • Sabine Burgdorf
  • Monique Laurent
  • Teresa Piovesan
    • Categories Linear, Cone and Semidefinite Programming, Polyhedra Tags , , , , , ,

    We investigate structural properties of the completely positive semidefinite cone, consisting of all the nxn symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of … Read more