Conference abstracts

Session B3 - Symbolic Analysis

July 15, 17:00 ~ 17:25 - Room B2

Algebraic certificates of disconnectedness

Didier Henrion

LAAS-CNRS University of Toulouse, France   -

Given two disjoint semialgebraic subsets of a given compact semialgebraic set, we describe an algorithm that certifies that the two subsets are disconnected, i.e. that there is no continuous trajectory connecting them. The certificate of disconnectedness is a polynomial satisfying specific positivity conditions. It is computed by solving a hierarchy of convex moment-sum-of-squares semidefinite programs obtained by applying infinite-dimensional convex duality on a transport equation satisfied by measures attached to trajectories.

Joint work with Mohab Safey El Din (Université Pierre et Marie Curie, Paris, France).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.