Georgia Institute of Technology College of Sciences

Convex relaxations are of central interest in optimization, and it is typically challenging to determine whether a given convex relaxation will be tight for a given problem. We introduce a topological framework for analyzing  situations in which a constrained optimization problem over a nonconvex set (such as a manifold) has a tight convex relaxation. In particular, we give a criterion for the existence of such a tight convex relaxation in terms of the existence of a continuous function of Lagrange multipliers for the constrained problem maximizing the corresponding Lagrangian. We call such a function a Lagrangian dual section, in reference to the topological notion of a section of a bundle.

As a corollary of this result, we will give new criteria for the exactness of SDP relaxations for Stiefel manifold optimization and inverse eigenvalue problems in terms of linear subspaces of matrices satisfying spectral properties such as being nonsingular. We will also illustrate a homotopy continuation style algorithm with global optimality guarantees with applications to the unbalanced procrustes problem.