  We study sum of squares (SOS) relaxations to optimize polynomial functions
over a set $V\cap R^n$, where $V$ is a complex algebraic variety. We propose a
new methodology that, rather than relying on some algebraic description,
represents $V$ with a generic set of complex samples. This approach depends
only on the geometry of $V$, avoiding representation issues such as
multiplicity and choice of generators. It also takes advantage of the
coordinate ring structure to reduce the size of the corresponding semidefinite
program (SDP). In addition, the input can be given as a straight-line program.
Our methods are particularly appealing for varieties that are easy to sample
from but for which the defining equations are complicated, such as $SO(n)$,
Grassmannians or rank $k$ tensors. For arbitrary varieties we can obtain the
required samples by using the tools of numerical algebraic geometry. In this
way we connect the areas of SOS optimization and numerical algebraic geometry.

Optimization and Control;Algebraic Geometry