  The affine inverse eigenvalue problem consists of identifying a real
symmetric matrix with a prescribed set of eigenvalues in an affine space. Due
to its ubiquity in applications, various instances of the problem have been
widely studied in the literature. Previous algorithmic solutions were typically
nonconvex heuristics and were often developed in a case-by-case manner for
specific structured affine spaces. In this short note we describe a general
family of convex relaxations for the problem by reformulating it as a question
of checking feasibility of a system of polynomial equations, and then
leveraging tools from the optimization literature to obtain semidefinite
programming relaxations. Our system of polynomial equations may be viewed as a
matricial analog of polynomial reformulations of 0/1 combinatorial optimization
problems, for which semidefinite relaxations have been extensively
investigated. We illustrate numerically the utility of our approach in stylized
examples that are drawn from various applications.
