International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong

 

Invited Speakers

Female Forum


A Faster Interior-Point Method for Sum-of-Squares Optimization

Shunhua Jiang

Shunhua Jiang

PhD student at Columbia University

Abstract:

Sum-of-squares (SOS) optimization is a conic optimization problem that optimizes a linear objective while restricting the polynomials to be sum of squares. It is a central tool in polynomial optimization and capture convex programming in the Lasserre hierarchy. In this talk I will present a recent result in ICALP ’22 that shows a polynomially faster interior-point method for sum-of-squares optimization. The centerpiece of our algorithm is a dynamic data structure for maintaining the inverse of the Hessian of the SOS barrier function under the polynomial interpolant basis.

Bio:
Shunhua Jiang is a third-year PhD student at Columbia University, advised by Prof. Omri Weinstein and Prof. Alexandr Andoni. Previously she received her bachelor’s degree from Yao class, Tsinghua University. Her main research interests are optimization and data structures.

Website https://www.cs.columbia.edu/~jiangsh/