7 papers · 1 filter
On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
Adam Kurpisz, Lucas Slot, Mikhail Zaytsev
We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of for 0/1 variables under the constraint $\s…
Computational complexity of sum-of-squares bounds for copositive programs
Marilena Palomba, Lucas Slot, Luis Felipe Vargas +1
In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations…
An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization
Monique Laurent, Lucas Slot
In this survey we consider polynomial optimization problems, asking to minimize a polynomial function over a compact semialgebraic set, defined by polynomial inequalities. This mod…
Nonconvergence of a sum-of-squares hierarchy for global polynomial optimization based on push-forward measures
Lucas Slot, Manuel Wiedmer
Let be a closed set, and consider the problem of computing the minimum of a polynomial on . Given a measure suppo…
A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization
Sander Gribling, Sven Polak, Lucas Slot
The moment-sum-of-squares (moment-SOS) hierarchy is one of the most celebrated and widely applied methods for approximating the minimum of an n-variate polynomial over a feasible r…
Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization
Lucas Slot, Monique Laurent
We consider a hierarchy of upper approximations for the minimization of a polynomial over a compact set proposed recently by Lasserre (arXiv:1907.097…