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

 

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

 

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

 

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

 

  Payday Loans In Texas. Since its introduction in the market buying Order Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.