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

 

Abstract:
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
manifolds.

 

 

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

Cordian Riener
Symmetry in polynomial optimization

 

Abstract:
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

 

Abstract:
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.

 

  Do you need Missouri Loans Online as soon as possible? What can cause long-term use of Canadian Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.