Invited Session Thu.3.H 0110

Thursday, 15:15 - 16:45 h, Room: H 0110

Cluster 16: Nonlinear programming [...]

Polynomial optimization and semidefinite programming


Chair: Jiawang Nie



Thursday, 15:15 - 15:40 h, Room: H 0110, Talk 1

Lihong Zhi
Computing real solutions of polynomial systems via low-rank moment matrix completion

Coauthor: Yue Ma


We propose a new algorithm for computing real
roots of polynomial equations or a subset of real roots in a
given semi-algebraic set described by additional polynomial
inequalities. The algorithm is based on using modified fixed
point continuation method for solving Lasserre's hierarchy
of moment relaxations. We establish convergence properties
for our algorithm. For a large-scale polynomial system with
only few real solutions in a given area, we can extract them
quickly. Moreover, for a polynomial system with an infinite
number of real solutions, our algorithm can also be used
to find some isolated real solutions or real solutions on the



Thursday, 15:45 - 16:10 h, Room: H 0110, Talk 2

Cordian Riener
Symmetry in polynomial optimization


Solving polynomial optimization problems is known to be
a hard task in general. In order to turn the recently emerged
relaxation paradigms into efficient tools for these optimization questions it is necessary to
exploit further structure whenever presented in the problem structure.
In this talk we will focus on the situation of optimization problems
that are given by symmetric polynomials in order to highlight several
approaches to take advantage of symmetry.
The techniques presented in the talk will also give a better
understanding of the cones of symmetric sums of squares and symmetric
non negative forms and the symmetric mean inequalities associated to
these. In particular, we will show that in degree four, symmetric mean
inequalities are characterized by sum of squares decomposition.



Thursday, 16:15 - 16:40 h, Room: H 0110, Talk 3

Markus Schweighofer
The sums of squares dual of a semidefinite program

Coauthor: Igor Klep


It is now commonly known that many polynomial optimization problems can be modeled or at least approximated by semidefinite programs (SDPs). In this talk we go the other way around: We consider an SDP from the perspective of polynomial optimization and real algebraic geometry. We will see that, from this perspective, the standard duality of an SDP can be seen as a theorem on representation of positive polynomials. We will prove that natural variants of this theorem hold true, and these can be refined with some effort to yield what we call the sums of squares dual of a semidefinite program. This dual has polynomial size in the primal and, unlike the standard dual, ensures always strong duality. Based on completely different ideas, another dual with this property has already been given by Matt Ramana in 1995. However, we think that our dual is interesting because it shows that ideas from real algebraic geometry might lead very naturally to seriously exploitable concepts in optimization.


  Today, Payday Loans Ohio are legitimate, but there are illegal transactions that are still on the rise. What makes Viagra Strips better than other forms of this medicine is its easiness of usage.