Seminar in Computational Statistics and Data Science

Speaker: Ying Cui, UC Berkeley

Title: Sketching the Global Landscape of Nonconvex Optimization

Abstract:

Convexification is a classical technique in global optimization, but standard convex relaxations are typically one-shot: they provide a single convex surrogate that cannot be systematically tightened. As a result, convexification plays a limited role in nonlinear programming, where progressively improving approximations are essential in the latter area. In this talk, we introduce a parametric relaxation framework for a broad class of nonconvex optimization problems. The relaxation is governed by a parameter \gamma that explicitly trades off between the convexity of the surrogate model and its tightness to the original objective. A key feature of this framework is its hierarchical approximation property: as \gamma increases, the relaxed problem first touches the set of global minimizers, then all local minimizers, and eventually all stationary points of the original problem. We show that this metric provides a principled way to assess the tightness of stationary points and to guide algorithmic strategies for approaching globally optimal solutions. Algorithms and convergence rates to sequentially solve the \gamma-relaxation will also be discussed.