Amir Ali Ahmadi and Georgina Hall
Citation
The paper by A. A. Ahmadi and G. Hall "On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity” makes two major contributions in the area of nonconvex polynomial optimization problems (POPs). First, contrary to prior popular belief, it is shown that to obtain a converging hierarchy of lower bounds for POPs, the use of "Positivstellensatze" that certify positivity of polynomials on arbitrary basic semialgebraic sets is not needed. Instead, the authors show that the same result can be obtained from more elementary theorems in algebra, dating back to the early 20th century, which only certify positivity of polynomials globally. Second, where nearly all previous hierarchies use semidefinite programming as their computational backbone, this paper derives a converging hierarchy of lower bounds for POPs that does not require optimization at all, but simply the ability to multiply certain fixed polynomials together and check nonnegativity of the coefficients of their product. Thus this paper provides a surprising and elegant deep theoretical discovery that is likely to have a significant impact on a variety of questions in applied mathematics.
Selection Committee
Katya Scheinberg (chair), Yongpei Guan, Fatma Kilinc-Karzan, Andrea Lodi