Professor Dávid Papp (North Carolina State University) will be a guest of the Corvinus Center for Operation Research (CCOR) in November. As part of his visit, he will present a minicourse titled Sums of squares, nonnegativity certificates, and optimization over polynomials.
Venue: Corvinus University (Building C)
Date:
November 6. (Monday) 9:50-11:20 (Room C557)
November 7. (Tuesday) 9:50-11:20 (Room C427)
November 7. (Tuesday) 13:40-15:10 (Room C427)
We would like to inform you that the lectures will be broadcast online. Please be aware that this broadcast will not utilize professional-grade equipment, and we appreciate your understanding that we cannot ensure the broadcast’s quality.
If you would like to join online, please send an e-mail to anita dot varga at uni-corvinus dot hu by November 6, 8:00.
Abstract:
Polynomial optimization refers to nonlinear optimization problems in which the goal is to find the (global) optimal value of a polynomial over a set defined by polynomial inequalities. It is an NP-hard class of optimization problems (even when all polynomials involved are quadratic) but has numerous applications both within and outside the mathematical sciences: computer-assisted theorem proving, analysis of dynamical systems, approximation algorithms, control, design of experiments, and combinatorial geometry to name a few.
Even more broadly, many optimization models in these areas include constraints that a polynomial (whose coefficients are decision variables in the optimization problem) must be nonnegative over some domain. (“Optimization over nonnegative polynomials.”) Such constraints are convex, yet are usually intractable, because even recognizing nonnegative polynomials is difficult. Hence, in practice, tractable approximations of nonnegative polynomials are used. The most well-known of these techniques is sum-of-squares approximation, which leads to a sequence of semidefinite programming approximations that trade off efficiency (the size of the semidefinite program) and approximation error.
After some motivating examples, the course will give an introduction to the fundamental theoretical results and algorithmic tools in the area: nonnegativity certificates, sum-of-squares polynomials and their connection to semidefinite programming. Time permitting, we will also discuss some of the computational challenges that frequently arise during the numerical solution of polynomial optimization problems, and how to mitigate them with better modeling and algorithmic choices.