Invited Session Fri.2.H 2036

Friday, 13:15 - 14:45 h, Room: H 2036

Cluster 4: Conic programming [...]

Algebraic geometry and conic programming, part II


Chair: Cordian Riener and Lek-Heng Lim



Friday, 13:15 - 13:40 h, Room: H 2036, Talk 1

Jiawang Nie
Certifying convergence of Lasserre's hierarchy via flat truncation


Consider the optimization problem of minimizing a polynomial function subject to polynomial constraints. A typical approach for solving it globally is applying Lasserre's hierarchy of semidefinite relaxations, based on either
Putinar's or Schmüdgen's Positivstellensatz. A practical question in applications is: how to certify its convergence and get minimizers? In this paper, we propose flat truncation as a certificate for this purpose. Assume the set of global minimizers is nonempty and finite. Our main results are: (i) Putinar type Lasserre's hierarchy has finite convergence if and only if flat truncation holds, under some generic assumptions; the same conclusion holds for the Schmüdgen type one under weaker assumptions. (ii) Flat truncation is asymptotically satisfied for Putinar type Lasserre's hierarchy if the Archimedean condition holds; the same conclusion holds for the Schmüdgen type one if the feasible set is compact. (iii) We show that flat truncation can be used as a certificate to check exactness of standard SOS relaxations and Jacobian SDP relaxations.



Friday, 13:45 - 14:10 h, Room: H 2036, Talk 2

Jordan Ninin
Abstract cones of positive polynomials and sums of squares

Coauthor: Roland Hildebrand


In [Recent Advances in Optimization and its Applications in Engineering, pp. 41-50, Springer, 2010] we presented a new approach to the construction of sums of squares relaxations, that of abstract cones of positive polynomials. In this framework, a fixed cone of positive polynomials is considered as a subset in an abstract coefficient space and corresponds to an infinite, partially ordered set of concrete cones of positive polynomials of different degrees and in a different number of variables. To each such concrete cone corresponds its own SOS cone, leading to a hierarchy of increasingly tighter SOS relaxations for the abstract cone.
In the present contribution, we consider further theoretical properties and test the practical performance of this approach. In particular, we propose an alternative method for the construction of SOS relaxations to general polynomially constrained optimization problems and apply it to some classical combinatorial optimization problems which can be cast in a polynomially constrained form.



Friday, 14:15 - 14:40 h, Room: H 2036, Talk 3

André Uschmajew
Convergence of algorithms on quotient manifolds of Lie groups


When it comes to analyzing the (local) convergence properties of algorithms for optimization with respect to certain tensor formats of fixed low rank, such as PARAFAC-ALS or TUCKER-ALS, one is confronted with the non-uniqueness of the low-rank representations, which causes naive contraction arguments to fail. This non-uniqueness is (at least partially) caused by a Lie group action on the parameters of the tensor format (scaling indeterminacy). On the other hand, for instance in the case of ALS, the algorithm has an invariance property (with respect to the Lie group), namely to map equivalent representations to equivalent ones.
In this talk we show how these ingredients lead to natural convergence results for the equivalence classes (orbits) of the Lie group, which are the true objects of interest. For subspace tensor formats, such as the Tucker format, the quotient manifold is diffeomorphic to the variety of tensors of fixed subspace rank. For the CP format one has to make additional assumptions. The results are presented in a generality which does not restrict them to the low-rank tensor approximation problem only


  . Cialis Professional online is capableto release you reliably from the erection problems, its improved formula gives the new properties to the drug.