Large Structures Seminar: Matthew Morency

Semidefinite programs are ubiquitous within a myriad of disciplines in engineering and applied mathematics. While these problems in their canonical form are solvable in polynomial time, several physical problems imply additional constraints which render the problem non-convex, one example of which being rank constraints. The dominant approach to tackling such problems has been Semidefinite Relaxation. We propose a new approach based on the idea of algebraic restriction. Several problems are introduced wherein the underlying structure of univariate polynomial ideals may be leveraged to simultaneously reduce the problem dimension, while redering it convex and thus solvable. Simulation results are presented which show a dramatic improvement compared to the Semidefinite Relaxation approach.