Workshop on algebraic techniques for optimization

Frank Vallentin 

Title: A semidefinite programming hierarchy for covering problems in discrete geometry

Abstract: In this talk I will present a new semidefinite programming hierarchy for covering problems in compact metric spaces. Over the last years, these kind of hierarchies were developed primarily for geometric packing and for energy minimization problems; they frequently provide the best known bounds. Starting from a semidefinite programming hierarchy for DOMINATING SET, I will derive the new hierarchy for covering and show some of its basic properties: The hierarchy converges in finitely many steps, but the first level collapses to the volume bound.

(based on joint work with Cordian Riener and Jan Rolfes)

Luis F. Zuluaga 

Title: Constraint penalization for non-convex optimization problems: Applications to Quantum Computing

Abstract: We begin by showing that conditions for strong Lagrangian duality of non-convex optimization problems can be obtained via a proof inspired by polynomial optimization techniques. By further looking into conditions for dual attainment, this approach leads to a generic way to reformulate equality constrained binary optimization problems as unconstrained binary optimization problems. This type of reformulations have gained recent importance, thanks to the fact that they allow quantum computers to be used to address the solution of a wide range of combinatorial optimization problems. We finish by discussing how to obtain the best reformulations of this type for quantum computers, and how to extend this approach to inequality constrained combinatorial optimization problems.

Juan Vera

Title: Lifting non-negativity over general semialgebraic sets to non-negativity over simple sets

Abstract: A non-negativity certificate (NNC) is a way to write a polynomial so that its non-negativity on a semialgebraic set becomes evident. Positivstellensätze (Psätze) guarantee the existence of NNCs. NNCs and Psätze underlie powerful algorithmic techniques for optimization. We propose a universal approach to derive new Psätze for general semialgebraic sets from ones developed for simpler sets, such as a box, a simplex, or the non-negative orthant. We provide several results illustrating the approach:

  1.  We show how to use Handelman's Positivstellensatz (Psatz) over a box to construct non-SOS Schmüdgen-type Psätze over any compact semialgebraic set.

  2.  We show how to derive a sparse Psatz over general compact sets by considering the simplex as the simple set. This sparse certificate requires no structural assumptions, such as the running intersection property.

  3.  We show how to derive new non-SOS Psatz over unbounded by considering Pólya's Psatz over the non-negative orthant.