Session: Algebraic Methods in Optimization (Part 2)
Chair: Kevin Shu
Cluster: Conic and Semidefinite Optimization
Talk 1: Hidden Convexity via Algebraic Topology
Speaker: Kevin Shu
Abstract: Hidden convexity is a general term used to describe situations in which a seemingly nonconvex optimization problem can be reformulated as a convex optimization problem. For this talk, we will focus on examples in which the image of a nonconvex set (which we think of as the domain of some optimization problem) under a (possibly) nonlinear map is convex, and we will highlight the connections between this question and some basic notions in algebraic topology. Specific examples will be various projections of the group of rotation matrices that are convex, and applications to orientation finding will be given.
Talk 2: Spectral methods for polynomial optimization
Speaker: Elvira Moreno Ferreira
Abstract: We propose a hierarchy of tractable relaxations based on spectral methods for polynomial optimization problems (POPs). Concretely, our hierarchy of spectral relaxations yields a monotonic sequence of bounds for the optimal value of a POP, each of which is computed as the minimum eigenvalue of a matrix obtained from the problem data. Because spectral methods are less computationally demanding than semidefinite programs, which underpin state-of-the-art techniques based on SOS certificates of non-negativity, our hierarchy provides an attractive alternative for obtaining bounds on large-scale problems. We identify the algebraic structure underlying a POP that makes it amenable to spectral relaxations, and we demonstrate the efficiency and applicability of our framework with numerical examples.
Talk 3: The landscape analysis problem of non-convex reformulations
Speaker: Chenyang Yuan
Abstract: We consider the problem of determining whether non-convex parametrizations of convex optimization problems have no spurious first- and second-order critical points. We show that this problem is equivalent to determining whether an infinite family of convex programs has a non-zero solution. When these optimization problems have polynomial structure, we use algebraic tools to develop strategies for partitioning and searching this infinite family, as well as finding counterexamples. We also discuss situations when strong duality fails to hold and how to remedy this with extended dual formulations.
