M/E23

Bounding the arithmetic complexity of an optimization problem is very important. Recent work focus on semidefinite programming (SDP) for its outstanding importance and universality in polynomial optimization. Interior-point algorithms can be used to compute floating point approximations of a solution of an SDP in polynomial time (in finite precision arithmetic). Exploiting the algebraic structure of the problem, one can obtain exact algorithms and new bounds depending on the algebraic degree of the solution. In this talk I will discuss a series of examples where such an approach can be useful, and I will briefly describe possible extensions to hyperbolic programming. Keywords: Semidefinite programming, hyperbolic programming, nonnegative polynomials and sums of squares, semialgebraic geometry

Dr. Simone Naldi

TU Dortmund