Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 278C: Seminar in Optimization and Data Science

Prof. Heng Yang

Harvard University

A Field Theory of First-Order Methods for Linear Conic Optimization

Abstract:

First-order methods make large-scale conic optimization computationally accessible. Their convergence dynamics, however, are not well understood: some instances converge rapidly, others exhibit persistent slow progress, and still others pass through multiple plateaus before entering a fast local regime.

In this talk, I will present a unified framework for understanding these behaviors by viewing an algorithm’s one-step update as a vector field. The central concept is region-wise sharpness, which measures the strength of this field relative to the distance to the solution set. This framework yields four new results. First, strict complementarity guarantees local field sharpness around an individual solution and linear convergence of first-order methods for semidefinite programming, without requiring nondegeneracy or uniqueness. Second, at certain singular solutions, the field has vanishing first-order variation in directions that leave the solution set; second-order limit dynamics characterize the resulting slow motion and explain several empirical signatures. Third, a field rigidity principle establishes setwise sharpness around the entire solution set for a class of exact boolean moment–sos relaxations, allowing local linear convergence even when the limiting solution fails strict complementarity. Fourth, an afterimage principle identifies slow regions through nearby optimization problems whose solution geometries differ substantially while their algorithmic fields remain close. These regions provide certificates of long convergence transients beyond the reach of local analysis.

Complementing this analysis of convergence dynamics, i will also discuss computational advances that reduce the cost of each iteration in semidefinite programming. These include composite polynomial filtering for large-scale positive semidefinite cone projections, designed to exploit the high throughput of modern gpus, and a subsequEnt extension that improves projection accuracy through spectral deflation.

Host: Jiawang Nie

November 18, 2026

3:00 PM

Zoom (Meeting ID: 995 4559 2483 / Password: OPT278CFA2)

Research Areas

Optimization

****************************